Fault-tolerant, self-healing routing scheme for a multi-path interconnection fabric in a storage network
First Claim
1. A method for routing communications in a storage system, comprising:
- assigning a preference to each of a plurality of communication paths between a source node and a destination node, wherein each preference indicates a relative measure of how often one of the communication paths should be selected for sending one of a plurality of communications, and wherein each preference indicates that a corresponding communication path should be chosen at least once when sending the communications;
receiving one of the communications to be sent from the source node to the destination node;
selecting a communication path from the plurality of communication paths between the source node and the destination node;
sending the communication on the selected communication path from the source node to the destination node;
repeating said receiving, said selecting, and said sending for a plurality of communications to be sent from the source node to the destination node, wherein said selecting is performed so that a more preferred path is selected more often than a less preferred path; and
updating at least one of the assigned preferences corresponding to one of the selected communication paths;
wherein each of the communication paths between the source node and the destination node is independent of the other communication paths.
3 Assignments
0 Petitions
Accused Products
Abstract
Embodiments of a routing system are disclosed, including a method for routing communications in a storage system. The storage system may include multiple nodes interconnected by an interconnection fabric that provides multiple independent paths between a source node and a destination node. Some nodes may be connected to one or more disk drives. The method may include receiving a communication to be sent from a source node to a destination node, selecting a communication path from the multiple independent paths, and sending the communication on the selected communication path. This process may be repeated so that multiple communications may be sent. Each communication path may be selected according to a preference assigned to it, so that a more preferred path is selected more often than a less preferred path. The preferences may be updated to reflect changed conditions in the interconnection fabric.
-
Citations
74 Claims
-
1. A method for routing communications in a storage system, comprising:
-
assigning a preference to each of a plurality of communication paths between a source node and a destination node, wherein each preference indicates a relative measure of how often one of the communication paths should be selected for sending one of a plurality of communications, and wherein each preference indicates that a corresponding communication path should be chosen at least once when sending the communications;
receiving one of the communications to be sent from the source node to the destination node;
selecting a communication path from the plurality of communication paths between the source node and the destination node;
sending the communication on the selected communication path from the source node to the destination node;
repeating said receiving, said selecting, and said sending for a plurality of communications to be sent from the source node to the destination node, wherein said selecting is performed so that a more preferred path is selected more often than a less preferred path; and
updating at least one of the assigned preferences corresponding to one of the selected communication paths;
wherein each of the communication paths between the source node and the destination node is independent of the other communication paths. - View Dependent Claims (2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19)
-
-
20. A storage system, comprising:
-
a plurality of nodes interconnected by an interconnection fabric, and wherein a portion of the nodes are coupled to one or more storage devices;
a source configured to send a plurality of communications to a destination node, wherein the source comprises a source node and a source device configured to communicate with the source node;
wherein the source is further configured to send the communications from the source node to the destination node by selecting one of a plurality of communication paths between the source node and the destination node according to a preference assigned to that communication path, wherein the source is configured to repeatedly select communication paths according to preferences assigned to the communication paths until all of the communications are sent, and wherein the source is configured to select a more preferred communication path more frequently than a less preferred communication path;
wherein the source is further configured to select each of the plurality of communication paths at least once and thus to send at least one of the communications on each of the communication paths;
wherein the source is further configured to update at least one of the preferences assigned to one of the communication paths; and
wherein each of the communication paths between the source node and the destination node is independent of the other communication paths. - View Dependent Claims (21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 33, 34, 35, 36)
-
-
37. A device, comprising:
-
an interface configured to communicate with a source node in an interconnection fabric coupling together a plurality of nodes and providing a plurality of independent communication paths between the source node and a destination node; and
a controller configured to communicate a plurality of communications to the source node to be sent on the independent communication paths to one or more disk drives coupled to the destination node;
wherein the controller is further configured to communicate the communications to the source node by selecting one of the communication paths according to a preference assigned to that communication path, encoding the selected path in a communication, and communicating the communication to the source node, wherein the controller is configured to repeatedly select communication paths according to preferences assigned to the communication paths, encode communication paths in communications, and communicate communications until all of the communications have been communicated;
wherein the controller is configured to select a more preferred communication path more frequently than a less preferred path;
wherein the controller is further configured to update at least one of the preferences assigned to one of the communication paths; and
wherein the controller is further configured to select each of the independent communication paths at least once and thus to encode each of the communication paths in at least one of the communications. - View Dependent Claims (38, 39, 40, 41, 42, 43, 44, 45, 46, 47, 48, 49, 50, 51, 52, 53, 54, 55, 56)
-
-
57. A node, comprising:
-
a routing unit;
a plurality of input ports; and
a plurality of output ports;
wherein the node is configured to be connected to an interconnection fabric coupling together a plurality of nodes and comprising a plurality of independent communication paths between the node and a destination node;
wherein the routing unit is configured to send a plurality of communications on the independent communication paths to one or more disk drives coupled to the destination node;
wherein the routing unit is further configured to send the communications to the one or more disk drives coupled to the destination node by repeatedly selecting each of the communication paths according to preferences assigned to each of the communication paths and sending a communication on the selected communication path;
wherein the routing unit is configured to select a more preferred communication path more frequently than a less preferred path;
wherein the routing unit is further configured to update at least one of the preferences assigned to one of the communication paths; and
wherein the routing unit is further configured to select each of the independent communication paths at least once and thus to send a communication on each of the communication paths at least once. - View Dependent Claims (58, 59, 60, 61, 62, 63, 64, 65, 66, 67, 68, 69, 70, 71, 72, 73, 74)
-
Specification