Fanning route generation technique for multi-path networks

• US 20030095509A1
• Filed: 11/19/2001
• Published: 05/22/2003
• Est. Priority Date: 11/19/2001
• Status: Active Grant

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: Abali, Bulent, Ramanan, Aruna V.
• Granted Patent: US 7,110,389 B2
• Time in Patent Office: Days
• US Class Current: 370/256
• 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/12 Shortest path evaluation
• CPC Class Codes: H04L 45/24 Multipath

Abstract

A fanning route generation technique is provided for multi-path networks having a shared communications fabric. The technique includes selecting a source node—destination node (S-D) group having common starting and ending sets of links from the network of interconnected nodes. Within this group, selecting the shortest routes between the S-D nodes of the group so that: selected routes substantially uniformly fan out from the source node to a center of the network and fan in from the center of the network to the destination node, thereby achieving local balance; and global balance of routes passing through links that are at a same level of the network is achieved.

Claims

1. A method for generating routes for routing data packets in a network of interconnected nodes, the nodes being at least partially interconnected by links, the method comprising:

(i) selecting a source node—

destination node (S-D) group with common starting and ending sets of links from the network of interconnected nodes;

(ii) selecting shortest routes between at least some S-D nodes of the S-D group so that;

(a) selected routes substantially uniformly fan out from the source nodes to a center of the network and fan in from the center of the network to the destination nodes; and

(b) global balance of routes passing through links that are at the same level of the network is achieved.

2. The method of claim 1, further comprising repeating said selecting (i) of the S-D group for a plurality of S-D groups from the network, and for each S-D group, selecting (ii) the shortest routes between S-D nodes of the group so that (a) &

(b) are met, wherein links within the network that are at a same level of the network have a substantially balanced number of routes passing therethrough and are locally balanced.

3. The method of claim 1, wherein said selecting (ii) comprises exploring the network from a source node until a destination node is reached, and for each S-D pair of the group, prioritizing output ports at each stage based on least global weight of links on a node switch board (NSB), and by rank ordering output ports based on next level usage before prioritizing based on global weight of links on an intermediate switch board (ISB).

4. The method of claim 3, wherein said selecting (ii) further comprises building the shortest routes between S-D nodes of the S-D group employing said prioritizing and said rank ordering.

5. The method of claim 3, wherein said rank ordering comprises rank ordering output ports of the ISB such that ports with less traffic have a higher rank, and if more than one output port has a same rank, reordering the ranking so that an output port with a lower global weight on its link receives higher priority.

6. The method of claim 1, further comprising repeating said selecting (i) of the S-D group for each S-D group of the network, and wherein said selecting (ii) comprises substantially equalizing load on links within the network at a same level of the network considering the selected routes passing through said links by the multiple S-D groups.

7. The method of claim 1, wherein said selecting (ii) comprises selecting the shortest routes without prior knowledge of the type of data packages to be forwarded across said routes.

8. The method of claim 1, wherein said selecting (i) further comprises selecting an S-D group with at least one cross connection within an intermediate switch board (ISB) disposed between the common starting and ending sets of links of the network of interconnected nodes.

9. The method of claim 8, wherein said selecting (ii) comprises selecting said shortest routes by employing cross connected links within the ISB that are disjoint.

10. A system for generating routes for routing data packets in a network of interconnected nodes, the nodes being at least partially interconnected by links, the system comprising:

(i) means for selecting a source node destination node (S-D) group with common starting and ending sets of links from the network of interconnected nodes;

(ii) means for selecting shortest routes between at least some S-D nodes of the S-D group so that;

(a) selected routes substantially uniformly fan out from the source nodes to a center of the network and fan in from the center of the network to the destination nodes; and

(b) global balance of routes passing through links that are at a same level of the network is achieved.

11. The system of claim 10, further comprising means for repeating said means for selecting (i) of the S-D group for a plurality of S-D groups from the network, and for each S-D group, means for selecting (ii) the shortest routes between S-D nodes of the group so that (a) &

(b) are met, wherein links within the network that are at a same level of the network have a substantially balanced number of routes passing therethrough and are locally balanced.

12. The system of claim 10, wherein said means for selecting (ii) comprises means for exploring the network from a source node until a destination node is reached, and for each S-D pair of the group, means for prioritizing output ports at each stage based on least global weight of links on a node switch board (NSB), and by rank ordering output ports based on next level usage before prioritizing based on global weight of links on an intermediate switch board (ISB).

13. The system of claim 12, wherein said means for selecting (ii) further comprises means for building the shortest routes between S-D nodes of the S-D group employing said prioritizing and said rank ordering.

14. The system of claim 12, wherein said rank ordering comprises means for rank ordering output ports of the ISB such that ports with less traffic have a higher rank, and if more than one output port has a same rank, means for reordering the ranking so that an output port with a lower global weight on its link receives higher priority.

15. The system of claim 10, further comprising means for repeating said means for selecting (i) of the S-D group for each S-D group of the network, and wherein said means for selecting (ii) comprises means for substantially equalizing load on links within the network at a same level of the network considering the selected routes passing through said links by the multiple S-D groups.

16. The system of claim 10, wherein said means for selecting (ii) comprises means for selecting the shortest routes without prior knowledge of the type of data packages to be forwarded across said routes.

17. The system of claim 10, wherein said means for selecting (i) further comprises means for selecting an S-D group with at least one cross connection within an intermediate switch board (ISB) disposed between the common starting and ending sets of links of the network of interconnected nodes.

18. The system of claim 17, wherein said means for selecting (ii) comprises means for selecting said shortest routes by employing cross connected links within the ISB that are disjoint.

19. A system for generating routes for routing data packets in a network of interconnected nodes, the nodes being at least partially interconnected by links, the system comprising:

(i) at least one computing unit adapted to select a source node—

destination node (S-D) group with common starting and ending sets of links from the network of interconnected nodes;

(ii) said at least one computing unit being further adapted to select shortest routes between at least some S-D nodes of the S-D group so that;

(a) selected routes substantially fan out from the source nodes to a center of the network and fan in from the center of the network to the destination nodes; and

(b) global balance of routes passing through links that are at a same level of the network is achieved.

20. At least one program storage device readable by a machine, tangibly embodying at least one program of instructions executable by the machine to perform a method of generating routes for routing data packets in a network of interconnected nodes, the nodes being at least partially interconnected by links, the method comprising:

(i) selecting a source node—

destination node (S-D) group with common starting and ending sets of links from the network of interconnected nodes;

(ii) selecting shortest routes between at least some S-D nodes of the S-D group so that;

(a) selected routes substantially uniformly fan out from the source nodes to a center of the network and fan in from the center of the network to the destination nodes; and

(b) global balance of routes passing through links that are at the same level of the network is achieved.

21. The at least one program storage device of claim 20, further comprising repeating said selecting (i) of the S-D group for a plurality of S-D groups from the network, and for each S-D group, selecting (ii) the shortest routes between S-D nodes of the group so that (a) &

(b) are met, wherein links within the network that are at a same level of the network have a substantially balanced number of routes passing therethrough and are locally balanced.

22. The at least one program storage device of claim 20, wherein said selecting (ii) comprises exploring the network from a source node until a destination node is reached, and for each S-D pair of the group, prioritizing output ports at each stage based on least global weight of links on a node switch board (NSB), and by rank ordering output ports based on next level usage before prioritizing based on global weight of links on an intermediate switch board (ISB).

23. The at least one program storage device of claim 22, wherein said selecting (ii) further comprises building the shortest routes between S-D nodes of the S-D group employing said prioritizing and said rank ordering.

24. The at least one program storage device of claim 22, wherein said rank ordering comprises rank ordering output ports of the ISB such that ports with less traffic have a higher rank, and if more than one output port has a same rank, reordering the ranking so that an output port with a lower global weight on its link receives higher priority.

25. The at least one program storage device of claim 20, further comprising repeating said selecting (i) of the S-D group for each S-D group of the network, and wherein said selecting (ii) comprises substantially equalizing load on links within the network at a same level of the network considering the selected routes passing through said links by the multiple S-D groups.

26. The at least one program storage device of claim 20, wherein said selecting (ii) comprises selecting the shortest routes without prior knowledge of the type of data packages to be forwarded across said routes.

27. The at least one program storage device of claim 20, wherein said selecting (i) further comprises selecting an S-D group with at least one cross connection within an intermediate switch board (ISB) disposed between the common starting and ending sets of links of the network of interconnected nodes.

28. The at least one program storage device of claim 27, wherein said selecting (ii) comprises selecting said shortest routes by employing cross connected links within the ISB that are disjoint.