Method and apparatus for determining paths between source/destination pairs

• US 9,379,971 B2
• Filed: 09/28/2012
• Issued: 06/28/2016
• Est. Priority Date: 05/11/2012
• Status: Active Grant

• Current Assignee: IP3 2017, Series 200 of Allied Security Trust I (Allied Security Trust)
• Original Assignee: Simula Innovation AS
• Inventors: Sem-Jacobsen, Frank O., Vo, Hung Quoc, Kvalbein, Amund, Lysne, Olav
• Primary Examiner(s): Elliott, IV, Benjamin H
• Assistant Examiner(s): Nowlin, Eric
• Application Number:
  US13/630,826
• Publication Number:
  US 20130308444A1
• Time in Patent Office: 1,369 Days
• Field of Search: 370/218, 370/229, 370/235, 370/237, 370/238, 370/241, 370/248, 370/252, 370/254, 370/255, 370/392, 370/465, 709/224, 709/238
• US Class Current: 1/1
• CPC Class Codes: H04L 45/02 Topology update or discovery
• CPC Class Codes: H04L 45/12 Shortest path evaluation
• CPC Class Codes: H04L 45/18 Loop-free operations
• CPC Class Codes: H04L 45/28 using route fault recovery
• CPC Class Codes: H04L 45/34 Source routing
• CPC Class Codes: H04L 47/125 by balancing the load, e.g. traffic engineering
• CPC Class Codes: H04L 49/358 Infiniband Switches

Abstract

Described herein are a method and device for determining paths in a network topology. The method and device provide a source/destination pair representing a source and a destination in the network topology, provide a channel list comprising a topological ordering of channel identifiers representing communication channels in the network topology, and provide at least one path connecting the source and the destination based on the channel list.

Claims

1. A method of determining paths in a network topology using a computer including a microprocessor, comprising:

providing at least one source/destination pair, each pair representing a source and a destination in the topology;

providing a node list comprising a topological ordering of node identifiers representing communication nodes in the network topology;

providing at least one path connecting the source and the destination based on the node list;

selecting a source from the topology;

identifying the position of the source in the node list; and

generating at least one path from the selected source to the destination based on traversing the node list from the identified position to a first position.

2. The method according to claim 1, wherein the providing a node list further comprises:

a) selecting the first position in the node list;

b) selecting a destination from the at least one source/destination pairs;

c) associating the selected destination with the first position;

d) determining a subset of nodes, the subset comprising nodes directly connected to the destination;

e) selecting a current position in the node list higher than the first position;

f) selecting, based on a constraint function, a next node from the subset;

g) associating the next node with the current position;

h) for each selected node in the subset, extending the subset with a next subset including further nodes connected to the selected node;

i) selecting a further position in the node list higher than the first and current positions, the further position hereafter being the current position; and

j) repeating steps f)-i) until all nodes in the topology have been associated with a position in the node list.

3. The method according to claim 2, wherein the constraint function is defined to realize a routing objective.

4. The method according to claim 3, wherein generating the at least one path comprises generating a plurality of paths.

5. The method according to claim 4, wherein the routing objective comprises an objective to maximize routing choices at each node.

6. The method according to claim 4, wherein the routing objective comprises an objective to balance the traffic load of each link at each node.

7. The method according to claim 1, further comprising:

storing the at least one path connecting the source and the destination in one or more routing tables in at least one network router or switch.

8. The method according to claim 1, wherein the providing at least one path further comprises:

generating at least one path connecting the source and the destination of each pair based additionally on a predefined traffic pattern utilizing the at least one path.

9. The method according to claim 1, wherein the providing at least one path further comprises:

generating at least one path connecting the source and the destination of each pair based additionally on a traffic load utilizing the at least one path.

10. The method according to claim 1, wherein the providing at least one path comprises:

selecting, from a pre-computed set of paths, at least one path compatible with the node list.

11. The method according to claim 2, wherein the associating comprises storing an identifier of the node at the current position in the node list.

12. A method of determining paths in a network topology using a computer including a microprocessor, comprising:

providing at least one source/destination pair, each pair representing a source and a destination in the topology;

providing a channel list comprising a topological ordering of channel identifiers representing communication channels in the network topology;

providing at least one path connecting the source and the destination based on the channel list; and

selecting a source from the topology;

identifying channels whose ingress node is the source;

identifying positions associated with the identified channels;

generating at least one path from the selected source to the destination based on traversing the channel list from the identified positions to a position associated with a channel whose egress node is the destination.

13. The method according to claim 12, wherein the providing a channel list further comprises:

a) selecting a first position in the channel list;

b) selecting a destination from the at least one source/destination pairs;

c) associating the selected destination with the first position;

d) determining a subset of channels, the subset comprising channels whose egress node is the destination;

e) selecting a current position in the channel list higher than the first position;

f) selecting, based on a constraint function, a next channel from the subset;

g) associating the next channel with the current position;

h) for each selected channel in the subset, extending the subset with a next subset including further channels whose egress node is the ingress node of the selected channel;

i) selecting a further position in the channel list higher than the first and current positions, the further position hereafter being the current position; and

j) repeating steps f)-i) until all channels in the topology have been associated with a position in the channel list.

14. The method according to claim 13, wherein the constraint function is defined to realize a routing objective.

15. The method according to claim 14, wherein generating the at least one path comprises generating a plurality of paths.

16. The method according to claim 15, wherein the routing objective comprises an objective to maximize routing choices at each node.

17. The method according to claim 15, wherein the routing objective comprises an objective to balance the traffic load of each channel.

18. The method according to claim 12, further comprising:

storing the at least one path connecting the source and the destination in one or more routing tables in at least one network router or switch.

19. The method according to claim 12, wherein the providing at least one path further comprises:

generating at least one path connecting the source and the destination of each pair based additionally on a predefined traffic pattern utilizing the at least one path.

20. The method according to claim 12, wherein the providing at least one path further comprises:

generating at least one path connecting the source and the destination of each pair based additionally on a traffic load utilizing the at least one path.

21. The method according to claim 12, wherein the providing at least one path comprises:

selecting, based on the channel list, the at least one path from a pre-computed set of paths.

22. The method according to claim 13, wherein each associating comprises storing an identifier of the channel at the current position in the channel list.

23. A device for determining paths in a network topology, comprising:

a microprocessor configured to

provide at least one source/destination pair, each pair representing a source and a destination in the topology,

provide a node list comprising a topological ordering of node identifiers representing communication nodes in the network topology,

provide at least one path connecting the source and the destination based on the node list,

select a source from the topology,

identify the position of the source in the node list, and

generate at least one path from the selected source to the destination based on traversing the node list from the identified position to a first position.

24. The device according to claim 23, wherein the microprocessor is configured to provide the node list by being further configured to

a) select the first position in the node list,

b) select a destination from the at least one source/destination pairs,

c) associate the selected destination with the first position,

d) determine a subset of nodes, the subset comprising nodes directly connected to the destination,

e) select a current position in the node list higher than the first position,

f) select, based on a constraint function, a next node from the subset,

g) associate the next node with the current position,

h) for each selected node in the subset, extend the subset with a next subset including further nodes connected to the selected node,

i) select a further position in the node list higher than the first and current positions, the further position hereafter being the current position, and

j) repeat f)-i) until all nodes in the topology have been associated with a position in the node list.

25. The device according to claim 24, wherein the constraint function is defined to realize a routing objective.

26. The device according to claim 25, wherein the microprocessor is configured to generate the at least one path by being further configured to generate a plurality of paths.

27. The device according to claim 26, wherein the routing objective comprises an objective to maximize routing choices at each node.

28. The device according to claim 26, wherein the routing objective comprises an objective to balance the traffic load of each link at each node.

29. The device according to claim 23, further comprising:

storing the at least one path connecting the source and the destination in one or more routing tables in at least one network router or switch.

30. The device according to claim 23, wherein the microprocessor is configured to provide at least one path by being further configured to

generate at least one path connecting the source and the destination of each pair based additionally on a predefined traffic pattern utilizing the at least one path.

31. The device according to claim 23, wherein the microprocessor is configured to provide at least one path by being further configured to

generate at least one path connecting the source and the destination of each pair based additionally on a traffic load utilizing the at least one path.

32. The device according to claim 23, wherein the microprocessor is configured to provide at least one path by being further configured to

select, from a pre-computed set of paths, at least one path compatible with the node list.

33. The method according to claim 24, wherein the microprocessor is configured to associate the selected destination with the first position or associate the next node with the current position by being further configured to store an identifier of the node at the current position in the node list.

34. A device for determining paths in a network topology, comprising:

a microprocessor configured to

provide at least one source/destination pair, each pair representing a source and a destination in the topology,

provide a channel list comprising a topological ordering of channel identifiers representing communication channels in the network topology,

provide at least one path connecting the source and the destination based on the channel list,

select a source from the topology,

identify channels whose ingress node is the source,

identify positions associated with the identified channels, and

generate at least one path from the selected source to the destination based on traversing the channel list from the identified positions to a position associated with a channel whose egress node is the destination.

35. The device according to claim 34, wherein the microprocessor is configured to provide a channel list by being further configured to

a) select a first position in the channel list,

b) select a destination from the at least one source/destination pairs,

c) associate the selected destination with the first position,

d) determine a subset of channels, the subset comprising channels whose egress node is the destination,

e) select a current position in the channel list higher than the first position,

f) select, based on a constraint function, a next channel from the subset,

g) associate the next channel with the current position,

h) for each selected channel in the subset, extend the subset with a next subset including further channels whose egress node is the ingress node of the selected channel,

i) select a further position in the channel list higher than the first and current positions, the further position hereafter being the current position, and

j) repeat f)-i) until all channels in the topology have been associated with a position in the channel list.

36. The device according to claim 35, wherein the constraint function is defined to realize a routing objective.

37. The device according to claim 36, wherein the microprocessor is configured to generate the at least one path by being further configured to generate a plurality of paths.

38. The device according to claim 37, wherein the routing objective comprises an objective to maximize routing choices at each node.

39. The device according to claim 37, wherein the routing objective comprises an objective to balance the traffic load of each channel.

40. The device according to claim 34, wherein the microprocessor is further configured to

store the at least one path connecting the source and the destination in one or more routing tables in at least one network router or switch.

41. The device according to claim 34, wherein the microprocessor is further configured to provide at least one path by being further configured to

generate at least one path connecting the source and the destination of each pair based additionally on a predefined traffic pattern utilizing the at least one path.

42. The device according to claim 34, wherein the microprocessor is further configured to provide at least one path by being further configured to

generate at least one path connecting the source and the destination of each pair based additionally on a traffic load utilizing the at least one path.

43. The device according to claim 34, wherein the microprocessor is further configured to provide at least one path by being further configured to

select, based on the channel list, the at least one path from a pre-computed set of paths.

44. The device according to claim 35, wherein the microprocessor is configured to associate the selected destination with the first position or associate the next channel with the current position by being further configured to store an identifier of the channel at the current position in the channel list.