Scalable routing scheme for a multi-path interconnection fabric

• US 7,072,976 B2
• Filed: 01/04/2001
• Issued: 07/04/2006
• Est. Priority Date: 01/04/2001
• Status: Active Grant

• Current Assignee: Oracle America, Inc. (Oracle Corporation)
• Original Assignee: Sun Microsystems Incorporated (Oracle Corporation)
• Inventors: Lee, Whay S.
• Primary Examiner(s): Najjar, Saleh
• Assistant Examiner(s): WON, MICHAEL YOUNG
• Application Number:
  US09/755,479
• Publication Number:
  US 20020147841A1
• Time in Patent Office: 2,007 Days
• Field of Search: 709/238, 709/243, 710/1, 710/31, 710/33, 710/34, 710/38
• US Class Current: 709/238
• CPC Class Codes: H04L 45/06 Deflection routing, e.g. hot-potato routing

Abstract

Various embodiments of a scalable routing system for use in an interconnection fabric are disclosed. In this routing scheme, a routing directive describes a route in the interconnection fabric between a sending node and a destination node. Either the sending node or a sending device connected to the sending node encodes the routing directive in a message to be sent to the destination node. The routing directive may include a variable number of segments. Each segment includes a distance component and a direction component that tell each node along the route how it should send the message. Generally, each distance component describes a distance in the interconnection fabric while each direction component specifies a direction in the interconnection fabric.

Claims

1. A method of sending messages in an interconnection fabric, wherein the interconnection fabric couples together a plurality of nodes, wherein each node of the plurality of nodes comprises a plurality of input ports and a plurality of output ports, comprising:

for each of a plurality of messages;

dynamically selecting a route in the interconnection fabric from among a plurality of independent routes for sending the message from a sending node to a destination node, wherein said dynamically selecting a route comprises identifying a routing directive for the selected one of the plurality of independent routes from the sending node to the destination node;

wherein said dynamically selecting a route comprises selecting different ones of the independent routes from the sending node to the destination node for at least two of the messages;

encoding the routing directive in the message, wherein the routing directive describes the route and comprises at least one segment, wherein each segment comprises a direction component and a distance component;

sending the message on one of the output ports of the sending node;

receiving the message on one of the input ports of a first node connected to the output port of the sending node;

decrementing the distance component for a current segment of the routing directive;

selecting one of the output ports of the first node according to the current segment of the routing directive in the message; and

sending the message on the selected one of the output ports of the first node.

2. The method as recited in claim 1, wherein said selecting one of the output ports comprises:

if, after said decrementing, the distance component for the current segment is greater than zero, selecting the output port corresponding to a same routing direction in which the message was traveling when received; and

if, after said decrementing, the distance component for the current segment is zero, selecting the output port corresponding to the direction component of the current segment.

3. The method as recited in claim 2, wherein if, after said decrementing, the distance component for the current segment is zero, and the output port is selected according to the direction component of the current segment, the method further comprises removing the current segment from the routing directive so that a next segment becomes the current segment when the message is sent on the selected output port.

4. The method as recited in claim 3, wherein the routing directive further comprises a pointer to the current segment, and wherein said removing the current segment comprises moving the pointer to the next segment.

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

a subsequent node receiving the message;

the subsequent node decrementing the distance component for the current segment of the routing directive;

wherein after said decrementing;

if the distance component for the current segment is greater than zero, the subsequent node selecting the output port corresponding to a same routing direction in which the message was traveling when received; and

if the distance component for the current segment is zero, the subsequent node selecting a port corresponding to the direction component of the current segment.

6. The method as recited in claim 5, wherein the subsequent node selecting a port corresponding to the direction component comprises:

selecting the corresponding output port if the direction component for the current segment specifies a routing direction; and

selecting a device port if the direction component for the current segment specifies that the subsequent node is the destination for the message.

7. The method as recited in claim 1 wherein the interconnection fabric is a torus interconnection fabric.

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

identifying a return route from the destination node to the sending node; and

encoding a return routing directive in the message, wherein the return routing directive describes the return route and comprises at least one segment, wherein each segment comprises a direction component and a distance component.

9. The method as recited in claim 8, further comprising calculating the return routing directive.

10. The method as recited in claim 9, wherein the interconnection fabric is bi-directional, and wherein calculating the return routing directive comprises reversing the routing directive.

11. The method as recited in claim 1, further comprising incrementally encoding a return routing directive in the message, wherein the return routing directive describes a return route from the destination node to the sending node and comprises at least one segment, and wherein each segment comprises a direction component and a distance component.

12. The method as recited in claim 11, wherein incrementally encoding comprises:

incrementing the distance component for a current segment of the return routing directive;

wherein if, after said decrementing, the distance component for the current segment of the routing directive is zero, the method further comprises modifying the direction component of a current segment of the return routing directive and adding a new segment to the return routing directive so that the new segment becomes the current segment of the return routing directive when the message is sent on the selected output port.

13. The method as recited in claim 12, wherein the return routing directive further comprises a pointer to the current segment, wherein adding a new segment to the return routing directive further comprises moving the pointer to the new segment.

14. The method as recited in claim 1 wherein a first number of segments of a first routing directive differs from a second number of segments of a second routing directive.

15. The method as recited in claim 3 further comprising a subsequent node receiving the message and, if all of the segments of the routing directive have been removed, the subsequent node identifying itself as the destination node and selecting a device port.

16. The method as recited in claim 1, wherein each direction component comprises a direction relative to a routing direction the message was traveling in when received.

17. The method as recited in claim 1, wherein each direction component comprises an identifier of one of the output ports of one of the nodes.

18. The method as recited in claim 1, wherein the destination node is configured to communicate with a storage device.

19. The method as recited in claim 18, wherein the storage device comprises a disk drive.

20. 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, wherein the interconnection fabric is configured to connect the node to a plurality of nodes;

wherein the routing unit is configured to receive a message being sent along a route from a sending node to a destination node in the interconnection fabric;

wherein the routing unit is further configured to receive a routing directive encoded in the message, wherein the routing directive describes the route and comprises at least one segment, and wherein a segment comprises a direction component and a distance component;

wherein the node is configured to receive the message on one of the input ports when the node is not the sending node, wherein the node is further configured to decrement the distance component of a current segment of the routing directive and to select one of the output ports according to the current segment;

wherein, when the node is the sending node, the node is further configured to dynamically select a route from among a plurality of independent routes from the sending node to the destination node and wherein the node is configured to encode the routing directive for the dynamically selected route in a message and wherein the node is configured to send the message on one of the output ports;

wherein for at least two messages, the node is further configured to dynamically select different ones of the independent routes from the sending node to the destination node when the node is the sending node.

21. The node as recited in claim 20, wherein the node is configured to communicate with a device on a device port, wherein the device is configured to select a route, encode a routing directive in the message and communicate a message to the node on the device port when the node is the sending node.

22. The node as recited in claim 21, wherein the node is further configured to select one of the output ports according to the current segment.

23. The node as recited in claim 20, wherein the node is configured to select:

one of the output ports corresponding to a same routing direction in which the message was traveling when received if, after said decrementing, the distance component for the current segment is greater than zero; and

one of the output ports corresponding to the direction component of the current segment if, after said decrementing, the distance component for the current segment is zero.

24. The node as recited in claim 23, wherein the node is further configured to remove the current segment from the routing directive if, after said decrementing, the distance component for the current segment is zero, and the wherein the node is configured to select the output port according to the direction component of the current segment, so that a next segment becomes the current segment when the message is sent on the selected output port.

25. The node as recited in claim 24, wherein the routing directive further comprises a pointer to the current segment, and wherein said being configured to remove the current segment comprises being configured to move the pointer to the next segment.

26. The node as recited in claim 20, wherein the node is configure to select:

one of the output ports corresponding to a same routing direction in which the message was traveling when received if, after said decrementing, the distance component for the current segment is greater than zero;

one of the output ports corresponding to the direction component of the current segment if, after said decrementing, the distance component for the current segment is zero, and if the direction component for the current segment does not identify that the node is the destination node; and

a device port if, after said decrementing, the distance component for the current segment is zero and if the direction component for the current segment identifies that the node is the destination node.

27. The node as recited in claim 20, wherein the interconnection fabric comprises a torus interconnection fabric.

28. The node as recited in claim 20, wherein, if the node is the sending node, the routing unit is further configured to identify a return route from the destination node to the sending node and to encode a return routing directive in the message, wherein the return routing directive describes the return route and comprises at least one segment, wherein each segment comprises a direction component and a distance component.

29. The node as recited in claim 28, wherein, if the node is the sending node, the routing unit is further configured to calculate the return routing directive.

30. The node as recited in claim 29, wherein the interconnection fabric is bi-directional, and wherein calculating the return routing directive comprises reversing the routing directive.

31. The node as recited in claim 20, wherein the node is configured to communicate with a RAID controller.

32. The node as recited in claim 20, wherein the node is configured to communicate with a mass storage device.

33. The node as recited in claim 32, wherein the mass storage device is a disk drive.

34. A device, comprising:

an interface configured to communicate with a source node in an interconnection fabric, wherein the interconnection fabric comprises a plurality of routes between the source node and a destination node; and

a controller configured to provide a first routing directive describing a first route from the source node to the destination node, wherein the routing directive comprises at least one segment, wherein each segment comprises a distance component and a direction component, wherein the distance component is configured to be decremented by a receiving node;

wherein the controller is further configured to encode the first routing directive in a message, and to communicate the message to the source node to be sent on the interconnection fabric to the destination node; and

wherein the controller is further configured to maintain a routing table comprising a plurality of independent routes from the source node to the destination node, and wherein the controller is further configured to dynamically select the first routing directive from the routing table when communicating the message to the source node to be sent on the interconnection fabric to the destination node.

35. The device of claim 34, wherein said controller comprises a RAID controller.

36. The device of claim 34, wherein the controller comprises a host interface configured to communicate with a host computer.

37. The device of claim 34, wherein the controller comprises a disk storage device controller.

38. The device of claim 34, wherein the routing table further comprises a second routing directive describing a second route from the source node to the destination node.

39. The device of claim 38, wherein the second routing directive comprises a different number of segments than the first routing directive.

40. The device of claim 34, wherein the controller is further configured to calculate the first routing directive.

41. The device of claim 34, wherein the controller is further configured to provide a return routing directive describing a return route from the destination node to the source node, and wherein the controller is further configured to encode the return routing directive in the message.

42. The device of claim 41, wherein the controller is further configured to select the return routing directive from a routing table.

43. The device of claim 41, wherein the controller is further configured to calculate the return routing directive from the first routing directive.

44. The device of claim 34, wherein the controller is further configured to encode a return routing directive describing a return route from the destination node to the source node in the message, and wherein the return routing directive is configured to be incrementally added to as the message is routed to the destination node.

45. The device of claim 44, wherein the return routing directive is further configured to be used to return an error message to the source node if a routing error is encountered.

46. The device of claim 45, wherein the controller is further configured to use the incrementally created return routing directive to locate the routing error if an error message is returned, wherein the incrementally created return routing directive indicates a last node that successfully received the message.

47. A method of sending a message in an interconnection fabric, wherein the interconnection fabric couples together a plurality of nodes, wherein each node of the plurality of nodes comprises a plurality of input ports and a plurality of output ports, comprising:

identifying a route in the interconnection fabric for sending the message from a sending node to a destination node;

encoding a routing directive in the message, wherein the routing directive describes the route and comprises at least one segment, wherein each segment comprises a direction component and a distance component;

identifying a return route from the destination node to the sending node;

encoding a return routing directive in the message, wherein the return routing directive describes the return route and comprises at least one segment, wherein each segment comprises a direction component and a distance component;

sending the message on one of the output ports of the sending node, wherein the message includes both the routing directive and the return routing directive when sent from the initial sending node;

receiving the message on one of the input ports of a first node connected to the output port of the sending node;

decrementing the distance component for a current segment of the routing directive;

selecting one of the output ports of the first node according to the current segment of the routing directive in the message; and

sending the message on the selected one of the output ports of the first node.

48. The method as recited in claim 47, further comprising calculating the return routing directive.

49. The method as recited in claim 48, wherein the interconnection fabric is bi-directional, and wherein calculating the return routing directive comprises reversing the routing directive.

50. 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, wherein the interconnection fabric is configured to connect the node to a plurality of nodes;

wherein the routing unit is configured to receive a message being sent along a route from a sending node to a destination node in the interconnection fabric;

wherein the routing unit is further configured to receive a routing directive encoded in the message, wherein the routing directive describes the route and comprises at least one segment, and wherein a segment comprises a direction component and a distance component;

wherein the node is configured to receive the message on one of the input ports when the node is not the sending node, wherein the node is further configured to decrement the distance component of a current segment of the routing directive and to select one of the output ports according to the current segment; and

wherein, when the node is the sending node, the routing unit is further configured to identify a return route from the destination node to the sending node and to encode a return routing directive in the message, wherein the return routing directive describes the return route and comprises at least one segment, wherein each segment comprises a direction component and a distance component, wherein the message includes both the routing directive and the return routing directive when sent from the initial sending node.

51. The node as recited in claim 50, wherein, when the node is the sending node, the routing unit is further configured to calculate the return routing directive.

52. The node as recited in claim 51, wherein the interconnection fabric is bi-directional, and wherein calculating the return routing directive comprises reversing the routing directive.

53. A device, comprising:

an interface configured to communicate with a source node in an interconnection fabric, wherein the interconnection fabric comprises a plurality of routes between the source node and a destination node; and

a controller configured to provide a first routing directive describing a first route from the source node to the destination node, wherein the routing directive comprises at least one segment, wherein each segment comprises a distance component and a direction component, wherein the distance component is configured to be decremented by a receiving node;

wherein the controller is further configured to encode the first routing directive in a message, and to communicate the message to the source node to be sent on the interconnection fabric to the destination node; and

wherein the controller is further configured to provide a return routing directive describing a return route from the destination node to the source node, wherein the return routing directive comprises at least one segment, wherein each segment comprises a direction component and a distance component; and

wherein the controller is further configured to encode the return routing directive in the message, wherein the message includes both the routing directive and the return routing directive when sent from the initial sending node.

54. The device of claim 53, wherein the controller is further configured to select the return routing directive from a routing table.

55. The device of claim 53, wherein the controller is further configured to calculate the return routing directive from the first routing directive.

56. The device of claim 53, wherein the return routing directive is further configured to be used to return an error message to the source node if a routing error is encountered.

57. A method of sending a message in an interconnection fabric, wherein the interconnection fabric couples together a plurality of nodes, wherein each node of the plurality of nodes comprises a plurality of input ports and a plurality of output ports, comprising:

identifying a route in the interconnection fabric for sending the message from a sending node to a destination node;

encoding a routing directive in the message, wherein the routing directive describes the route and comprises at least one segment, wherein each segment comprises a direction component and a distance component;

sending the message on one of the output ports of the sending node;

receiving the message on one of the input ports of a first node connected to the output port of the sending node;

decrementing the distance component for a current segment of the routing directive;

selecting one of the output ports of the first node according to the current segment of the routing directive in the message;

sending the message on the selected one of the output ports of the first node; and

incrementally encoding a return routing directive in the message, wherein the return routing directive describes a return route from the destination node to the sending node and comprises at least one segment, and wherein each segment comprises a direction component and a distance component;

wherein said incrementally encoding comprises;

incrementing the distance component for a current segment of the return routing directive;

wherein if, after said decrementing, the distance component for the current segment of the routing directive is zero, the method further comprises modifying the direction component of a current segment of the return routing directive and adding a new segment to the return routing directive so that the new segment becomes the current segment of the return routing directive when the message is sent on the selected output port.

58. The method as recited in claim 57, wherein the return routing directive further comprises a pointer to the current segment, wherein adding a new segment to the return routing directive further comprises moving the pointer to the new segment.

59. 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, wherein the interconnection fabric is configured to connect the node to a plurality of nodes;

wherein the routing unit is configured to receive a message being sent along a route from a sending node to a destination node in the interconnection fabric;

wherein the routing unit is further configured to receive a routing directive encoded in the message, wherein the routing directive describes the route and comprises at least one segment, and wherein a segment comprises a direction component and a distance component;

wherein the node is configured to receive the message on one of the input ports when the node is not the sending node, wherein the node is further configured to decrement the distance component of a current segment of the routing directive and to select one of the output ports according to the current segment; and

wherein the routing unit is further configured to incrementally encode a return routing directive in the message, wherein the return routing directive describes a return route from the destination node to the sending node and comprises at least one segment, and wherein each segment comprises a direction component and a distance component, wherein in incrementally encoding a return routing directive, the routing unit is further configured to;

increment the distance component for a current segment of the return routing directive;

wherein if, after said decrementing, the distance component for the current segment of the routing directive is zero, the routing unit is further configured modify the direction component of a current segment of the return routing directive and add a new segment to the return routing directive so that the new segment becomes the current segment of the return routing directive when the message is sent on the selected output port.

60. A device, comprising:

an interface configured to communicate with a source node in an interconnection fabric, wherein the interconnection fabric comprises a plurality of routes between the source node and a destination node; and

a controller configured to provide a first routing directive describing a first route from the source node to the destination node, wherein the routing directive comprises at least one segment, wherein each segment comprises a distance component and a direction component, wherein the distance component is configured to be decremented by a receiving node;

wherein the controller is further configured to encode the first routing directive in a message, and to communicate the message to the source node to be sent on the interconnection fabric to the destination node; and

wherein the controller is further configured to incrementally encode a return routing directive describing a return route from the destination node to the source node in the message, wherein the return routing directive describes a return route from the destination node to the sending node and comprises at least one segment, and wherein each segment comprises a direction component and a distance component, and wherein the return routing directive is configured to be incrementally added to as the message is routed to the destination node, wherein the return routing directive is further configured to be used to return an error message to the source node if a routing error is encountered.

61. The device of claim 60, wherein the controller is further configured to use the incrementally created return routing directive to locate the routing error if an error message is returned, wherein the incrementally created return routing directive indicates a last node that successfully received the message.

62. A storage system, comprising a plurality of nodes interconnected by an interconnection fabric;

wherein different ones of said plurality of nodes perform different functions in the storage system;

wherein each one of a first portion of said plurality of nodes is a storage node comprising at least one mass storage device;

wherein each one of a second portion of said plurality of nodes is a host interface node configured to provide an interface for the storage system to a host computer;

wherein each node of the plurality of nodes comprises;

a routing unit;

a plurality of input ports; and

a plurality of output ports;

wherein the routing unit of each node is configured to receive a message being sent along a route from a sending node to a destination node in the interconnection fabric;

wherein the routing unit of each node is further configured to receive a routing directive encoded in the message, wherein the routing directive describes the route and comprises at least one segment, and wherein a segment comprises a direction component and a distance component; and

wherein each node is configured to receive the message on one of the input ports when the node is not the sending node, wherein the node is further configured to decrement the distance component of a current segment of the routing directive and to select one of the output ports according to the current segment.