Electrical computers and digital processing systems: multicomput – Computer-to-computer data routing – Alternate path routing
Reexamination Certificate
2000-03-31
2004-09-14
Wiley, David (Department: 2143)
Electrical computers and digital processing systems: multicomput
Computer-to-computer data routing
Alternate path routing
C711S100000, C714S004110
Reexamination Certificate
active
06792472
ABSTRACT:
FIELD OF THE INVENTION
The present invention relates generally to systems and methods for routing data in a computer system having multiple storage devices, and more particularly, to systems and methods utilizing RAID controllers as intelligent data routers.
BACKGROUND OF THE INVENTION
The standard storage sub-system model consists of one or more host computers attached to at least one storage device. This is true for the external storage controller model, whereas the internal storage controller model tends to be one of one or more host computers, each with its own storage controller, attached to a common array of disks. Centralization of data is a common goal in both cases.
FIG. 1
shows a block diagram of a typical multiple-controller RAID system
100
(RAID is an acronym for “Redundant Array of Independent Disks”). Each host computer
102
is connected to a respective RAID controller
106
(e.g.
106
-
1
,
106
-
2
,
106
-
3
) through either a Fibre Channel or SCSI bus
104
(e.g.
104
-
1
,
104
-
2
,
104
-
3
). Each RAID controller
106
(e.g.
106
-
1
,
106
-
2
,
106
-
3
) coordinates reading and writing requests from a respective host
102
(e.g.
102
-
1
,
102
-
2
,
102
-
3
) directed to a shared set of storage devices
116
(e.g.
116
-
1
,
116
-
2
,
116
-
3
) to which the RAID controllers
106
are connected, for instance, via a device such as a backend bus
114
, again typically a Fibre Channel or SCSI disk bus
114
. The controllers
106
may share or use the same storage devices
116
so that each host computer
102
can access the same data.
FIG. 1
shows three controllers; however, the illustrated architecture is extendable to systems of N controllers (where N is an integer greater than 2). Each controller
106
include processors
108
as well as memory
110
, coupled to the processor
108
in a conventional manner. Controllers
106
are currently used as forwarding devices for host data traffic to a non-volatile storage medium such as disks. Often a RAID controller has a cache
112
to improve the rate at which data can be written to or be retrieved from the backing storage medium.
Centralized data storage in a single storage pool has been implemented to minimize the difficulty of accessing the data from multiple systems and reduces the management effort required for the data. The problem with centralized data storage is that it requires either a large investment up front in excess capacity to allow the system to accommodate future storage requirements, growth or the addition of storage sub-systems at a later date which may not easily work or integrate with the other sub-systems in the storage pool. Fault tolerance may also be compromised as a system grows to include a large number of controllers servicing multiple disks arranged in disk loops because more different error handling routines are required of a routing processor as different equipment is added. Another problem with current RAID systems is that a single processing unit is responsible for managing all of the data movements and interactions with the host systems and storage devices, which can become a bottleneck for system performance. For a configuration having a large number of disk loops and controllers as may be found in current systems, it is impractical to connect all of the disk loops to all controllers, but a routing structure and mechanism for getting to the data on disk loops which are not directly attached to a controller is still needed to provide for fault tolerance and a more efficient management of storage resources.
SUMMARY OF THE INVENTION
The present invention allows multiple controllers to communicate with any number of other controllers through the use of a routing table. The controllers do not need to be directly connected to each other as long as there is a path through other controllers to communicate with each other. Each controller maintains a routing table which can be used to determine the optimal path to allow two controllers to communicate. Three techniques allow the controllers to compute the optimal communications path between two controllers. A first technique is to compute the path which crosses the least number of controllers to reach or otherwise communicate with the controller to which the message is being sent. A second technique is to compute the path which has the least data traffic crossing the controllers and the interconnects. A third technique combines the first two techniques in that its uses both pieces of information, shortest route and minimal data traffic to determine an optimal routing path. A dynamic communications path between controllers can optionally be locked into place to minimize the need to compute the data routing path between controllers every time a message needs to be sent between two controllers. The data path can change as controllers or interconnects in the system change. The routing table may be dynamic in nature, and take into account the insertion and removal of controllers into the system. Each controller may optionally have the ability to cache messages that are routed through it such that if another controller requests the same message it does not always need to go back to the source controller to access the information. Each controller may optionally also have a method for invalidating cached data within itself and to inform other controllers that the cached data needs to be invalidated.
In one aspect, the present invention provides a system of storage device controllers controllably connected to allow routing of messages between the controllers, the system comprising: a selection means for selecting one or more messaging paths across the controllers; a message to be transported across the messaging paths; and a routing means to transport the message between a source controller and a destination controller across the messaging path.
In another aspect, the present invention provides a method of routing messages across a network of storage device controllers comprising the steps of: identifying paths between source controllers and destination controllers; and routing messages across between the paths between the source controllers and the destination controllers.
In yet another aspect, the present invention provides a computer program and a computer readable medium containing instructions which, when executed by a computer, route messages across a network of storage device controllers by: identifying paths between source controllers and destination controllers; and routing messages across between the paths between the source controllers and the destination controllers.
REFERENCES:
patent: 6094699 (2000-07-01), Surugucchi et al.
patent: 6215765 (2001-04-01), McAllister et al.
patent: 6324161 (2001-11-01), Kirch
patent: 6496505 (2002-12-01), La Porta et al.
patent: 6519224 (2003-02-01), Hrastar et al.
patent: 6625650 (2003-09-01), Stelliga
Spiegel et al. “An Alternative Path Routing Scheme Supporting QOS and Fast Connection Setup in ATM Networks”, IEEE GLOBECOM '94, vol. 2, pp. 1224-1230.*
Clarke, Ian “A Distributed Decentralized Information Storage and Retrieval System” Division of Informatics, Univ. of Edinburgh, 1999.
Otterness Noel S.
Skazinski Joseph G.
Avellino Joseph E
Dorsey & Whitney LLP
Wiley David
LandOfFree
System, method and computer readable medium for intelligent... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with System, method and computer readable medium for intelligent..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and System, method and computer readable medium for intelligent... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3243691