Fault-tolerant, self-healing routing scheme for a multi-path interconnection fabric in a storage network

• US 6,909,695 B2
• Filed: 05/07/2001
• Issued: 06/21/2005
• Est. Priority Date: 05/07/2001
• Status: Active Grant

• Current Assignee: Oracle America, Inc. (Oracle Corporation)
• Original Assignee: Sun Microsystems Incorporated (Oracle Corporation)
• Inventors: Lee, Whay S., Rettberg, Randall D.
• Primary Examiner(s): Phan, Man U.
• Application Number:
  US09/850,930
• Publication Number:
  US 20030021227A1
• Time in Patent Office: 1,506 Days
• Field of Search: 370/230, 370/235, 370/238, 370/253, 370/260, 370/351, 370/389, 370/395, 370/396, 370/401, 709/205, 709/218, 709/219, 709/238, 709/239, 709/240, 709/241, 709/245, 714/4, 714/100, 714/114
• US Class Current: 370/238
• CPC Class Codes: G06F 11/2002 where interconnections or communication control functionality are redundant flexible arrangements for bus networks involving redundancy H04L12/40176
• CPC Class Codes: H04L 41/0681 Configuration of triggering conditions
• CPC Class Codes: H04L 45/00 Routing or path finding of packets in data switching networks routing or path finding in wireless networks H04W40/00
• CPC Class Codes: H04L 45/06 Deflection routing, e.g. hot-potato routing
• CPC Class Codes: H04L 45/125 based on throughput or bandwidth
• CPC Class Codes: H04L 45/22 Alternate routing

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.

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.

2. The method as recited in claim 1, wherein the plurality of communications comprises communications to one or more disk drives.

3. The method as recited in claim 1, further comprising:

maintaining a routing table of the communication paths, wherein the routing table comprises a plurality of entries, wherein each entry indicates one of the communication paths; and

wherein said selecting comprises selecting a next entry from the routing table.

4. The method as recited in claim 1, further comprising:

detecting an error on one of the communication paths during said sending of one of the communications; and

resending on a different one of the communication paths the one of the communications that was being sent when the error was detected.

5. The method as recited in claim 1, wherein said selecting the communication path comprises calculating the communication path.

6. The method as recited in claim 1, wherein said assigning comprises setting each preference to a default value.

7. The method as recited in claim 1, wherein said updating does not decrease one of the preferences beyond a minimum preference.

8. The method as recited in claim 7, wherein in response to a failure of one of the communication paths, said updating decreases a preference assigned to the failed communication path to the minimum preference.

9. The method as recited in claim 8, wherein in response to the failure being repaired, said updating increases the preference assigned to the repaired communication path above the minimum preference.

10. The method as recited in claim 1, wherein said updating does not increase one of the preferences beyond a maximum preference.

11. The method as recited in claim 1, wherein said updating comprises changing one of the preferences to indicate that a communication path that preference is assigned to is more preferred if a communication is sent over the communication path successfully.

12. The method as recited in claim 11, wherein said changing comprises increasing one of the preferences.

13. The method as recited in claim 1, wherein said updating comprises changing one of the preferences to indicate that a communication path that preference is assigned to is less preferred if a communication is sent over the communication path unsuccessfully.

14. The method as recited in claim 11, wherein said changing comprises decreasing one of the preferences.

15. The method as recited in claim 1, further comprising updating one of the preferences every time a communication path that preference is assigned to is chosen.

16. The method as recited in claim 1, further comprising assigning a threshold to one of the preferences.

17. The method as recited in claim 16, wherein the threshold specifies an update condition, and wherein said updating at least one of the assigned preferences comprises updating the one of the preferences assigned the threshold when the update condition is met.

18. The method as recited in claim 16, wherein the threshold comprises a minimum number of communications that must be sent over one of the communication paths successfully before the preference assigned to that communication path is updated.

19. The method as recited in claim 16, wherein the threshold comprises a minimum number of communications that must be sent over one of the communication paths unsuccessfully before the preference assigned to that communication path is updated.

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.

21. The storage system of claim 20, wherein the plurality of communications comprises communications to one or more disk drives.

22. The storage system of claim 20, wherein the source is further configured to maintain a routing table of the plurality of communication paths, wherein the routing table comprises a plurality of entries, and wherein each entry indicates one of the communication paths.

23. The storage system of claim 20, wherein the source is further configured to receive an indication that an error occurred on one of the communication paths used to send one of the communications and to resend the communication that was being sent when the error occurred on a different one of the communication paths.

24. The storage system of claim 20, wherein the source is further configured to select the communication path by calculating the communication path.

25. The storage system as recited in claim 20, wherein the source is further configured to update one of the preferences by changing that preference to indicate that a communication path that preference is assigned to is more preferred if a communication is sent over the communication path successfully.

26. The storage system as recited in claim 25, wherein the source is further configured to increase the preference.

27. The storage system as recited in claim 20, wherein the source is further configured to update one of the preferences by changing that preference to indicate that a communication path that preference is assigned to is less preferred if a communication is sent over the communication path unsuccessfully.

28. The storage system as recited in claim 27, wherein the source is further configured to decrease the preference.

29. The storage system as recited in claim 20, wherein the source is further configured so that it cannot decrease one of the preferences beyond a minimum preference.

30. The storage system as recited in claim 29, wherein in response to a failure of one of the communication paths, the source is further configured to decrease a preference assigned to the failed communication path to the minimum preference.

31. The storage system as recited in claim 30, wherein in response to the failure being repaired, the source is further configured to increase the preference assigned to the repaired communication path above the minimum preference.

32. The storage system as recited in claim 20, wherein the source is further configured to not increase one of the preferences beyond a maximum preference.

33. The storage system as recited in claim 20, wherein the source is further configured to update one of the preferences every time a communication path that preference is assigned to is used to send a communication.

34. The storage system as recited in claim 20, wherein a threshold assigned to one of the preferences specifies an update condition, and wherein the source is further configured to update at least one of the preferences by updating the one of the preferences assigned the threshold when the update condition is met.

35. The storage system as recited in claim 34, wherein the threshold value comprises a minimum number of messages that must be sent over the first route successfully before the sender can update the first preference value.

36. The storage system as recited in claim 34, wherein the threshold value comprises a minimum number of messages that must be sent over the first route unsuccessfully before the sender can update the first preference value.

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.

38. The device of claim 37, wherein the plurality of communications comprises communications to one or more disk drives.

39. The device of claim 37, wherein the controller is further configured to maintain a routing table of the plurality of communication paths, wherein the routing table comprises a plurality of entries, and wherein each entry indicates one of the communication paths.

40. The device of claim 37, wherein the controller is further configured to receive an indication that an error occurred on one of the communication paths used to send one of the communications, to encode a different one of the communication paths in the communication that was being sent when the error occurred, and to recommunicate that communication to the source node.

41. The device of claim 37, wherein the controller is further configured to select the communication path by calculating the communication path.

42. The device as recited in claim 37, wherein the controller is further configured to update one of the preferences by changing the preference to indicate that a communication path that preference is assigned to is more preferred if a communication is sent over the communication path successfully.

43. The device as recited in claim 42, wherein the controller is further configured to increase the preference.

44. The device as recited in claim 37, wherein the controller is further configured to update one of the preferences by changing the preference to indicate that a communication path that preference is assigned to is less preferred if a communication is sent over the communication path unsuccessfully.

45. The device as recited in claim 44, wherein the controller is further configured to decrease the preference.

46. The device as recited in claim 37, wherein the controller is further configured so that it cannot decrease one of the preferences beyond a minimum preference.

47. The device as recited in claim 46, wherein in response to a failure of one of the communication paths, the controller is further configured to decrease a preference assigned to the failed communication path to the minimum preference.

48. The storage system as recited in claim 47, wherein in response to the failure being repaired, the controller is further configured to increase the preference assigned to the repaired communication path above the minimum preference.

49. The device as recited in claim 37, wherein the controller is further configured to not increase one of the preferences beyond a maximum preference.

50. The device as recited in claim 37, wherein the controller is further configured to update one of the preferences every time a communication path that preference is assigned to is used to send a communication.

51. The device as recited in claim 37, wherein a threshold assigned to one of the preferences specifies an update condition, and wherein the controller is further configured to update at least one of the preferences by updating the one of the preferences assigned the threshold when the update condition is met.

52. The device as recited in claim 51, wherein the threshold value comprises a minimum number of messages that must be sent over the first route successfully before the sender can update the first preference value.

53. The device as recited in claim 51, wherein the threshold value comprises a minimum number of messages that must be sent over the first route unsuccessfully before the sender can update the first preference value.

54. The device as recited in claim 37, wherein the controller comprises a RAID controller.

55. The device as recited in claim 37, wherein the controller comprises a host interface configured to communicate with a host computer.

56. The device as recited in claim 37, wherein the controller comprises a disk drive controller.

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.

58. The node of claim 57, wherein the routing unit is further configured to maintain a routing table of the plurality of independent communication paths, wherein the routing table comprises a plurality of entries, and wherein each entry indicates one of the communication paths.

59. The node of claim 57, wherein the routing unit is further configured to receive an indication that an error occurred on one of the communication paths used to send one of the communications and to resend the communication that was being sent when the error occurred on a different one of the communication paths.

60. The node of claim 57, wherein the routing unit is further configured to select the communication path by calculating the communication path.

61. The node as recited in claim 57, wherein the routing unit is further configured to update one of the preferences by changing the preference to indicate that a communication path that preference is assigned to is more preferred if a communication is sent over the communication path successfully.

62. The node as recited in claim 61, wherein the routing unit is further configured to increase the preference.

63. The node as recited in claim 57, wherein the routing unit is further configured to update one of the preferences by changing the preference to indicate that a communication path that preference is assigned to is less preferred if a communication is sent over the communication path unsuccessfully.

64. The node as recited in claim 63, wherein the routing unit is further configured to decrease the preference.

65. The node as recited in claim 57, wherein the routing unit is further configured so that it cannot decrease one of the preferences beyond a minimum preference.

66. The node as recited in claim 65, wherein in response to a failure of one of the communication paths, the routing unit is further configured to decrease a preference assigned to the failed communication path to the minimum preference.

67. The node as recited in claim 66, wherein in response to the failure being repaired, the routing unit is further configured to increase the preference assigned to the repaired communication path above the minimum preference.

68. The node as recited in claim 57, wherein the routing unit is further configured to not increase one of the preferences beyond a maximum preference.

69. The node as recited in claim 57, wherein the routing unit is further configured to update one of the preferences every time a communication path that preference is assigned to is used to send a communication.

70. The node as recited in claim 57, wherein a threshold assigned to one of the preferences specifies an update condition, and wherein the routing unit is further configured to update at least one of the preferences by updating the one of the preferences assigned the threshold when the update condition is met.

71. The node as recited in claim 70, wherein the threshold value comprises a minimum number of messages that must be sent over the first route successfully before the sender can update the first preference value.

72. The node as recited in claim 70, wherein the threshold value comprises a minimum number of messages that must be sent over the first route unsuccessfully before the sender can update the first preference value.

73. The node as recited in claim 57, wherein one of the input ports is configured to communicate with a RAID controller.

74. The node as recited in claim 57, wherein one of the output ports is configured to communicate with a disk drive.