METHOD AND APPARATUS FOR DETERMINING PATHS BETWEEN SOURCE/DESTINATION PAIRS

• US 20130308444A1
• Filed: 09/28/2012
• Published: 11/21/2013
• 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., LYSNE, Olav, VO, Hung Quoc, KVALBEIN, Amund
• Granted Patent: US 9,379,971 B2
• Time in Patent Office: Days
• US Class Current: 370/230
• 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 a source/destination pair representing a source and a destination in the network topology;

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

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

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

selecting from the topology a first path connecting the source and destination;

identifying channel identifiers for channels along the first path;

determining dependencies between the channel identifiers based on a deadlock-free routing algorithm; and

constructing the channel list by topologically ordering the channel identifiers according to the dependencies.

3. The method according to claim 1, wherein any dependency from one channel to another in the channel list only points to a channel identifier with a higher position in the channel list.

4. The method according to claim 2, wherein the selecting and identifying further comprises:

receiving an indication of a failure of the first path in the topology; and

identifying channel identifiers for the failed path.

6. The method according to claim 1, wherein the providing a source/destination pair comprises:

selecting the source/destination pair from the topology based on a predefined traffic pattern provided by an application.

7. The method according to claim 1, wherein the providing a source/destination pair comprises:

selecting the source/destination pair from the topology based on traffic load for at least one network router or switch.

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

storing the at least one provided path in a routing table.

9. The method according to claim 2, further comprising:

replacing, in a routing table, the first path with the at least one provided path.

10. The method according to claim 2, wherein the determining dependencies further comprises:

generating a new valid channel list in which channels dependencies from the first path are removed, and

generating at least one path based on the new valid channel list.

11. The method according to claim 10, wherein the generating the new valid channel list further comprises:

moving the target channel of a dependency to a higher position in the channel list, and repeating the step of moving for any following dependencies.

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

searching the topology to create a route around the first path using only legal turns.

13. The method according to claim 12, wherein the searching utilizes a shortest path algorithm.

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

searching the topology to create a route around the first path using legal turns, and if necessary illegal turns.

15. The method according to claim 13, wherein the shortest path algorithm is Dijkstra shortest path algorithm.

16. The method according to claim 15, wherein the shortest path algorithm obtains the shortest path between the source and the destination considering constraints of the channel list and any pre-existing routing table entries for the source and destination.

17. The method according to claim 13, wherein the shortest path algorithm is implemented on a reverse path from the destination to the source.

18. The method according to claim 13, wherein the shortest path algorithm utilizes a cost function which considers a number of hops, a number of illegal turns performed on the path from the source to the destination, and an index of all illegal turns utilized by the shortest path algorithm.

19. 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 channel list.

5. (canceled)

20. 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; and

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

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

a) selecting a 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.

22. The method according to claim 20, further comprising:

selecting a source from the topology;

identifying the position of the source in the node list;

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

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

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

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

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

27. The method according to claim 20, 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.

28. The method according to claim 20, 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.

29. The method according to claim 20, 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.

30. The method according to claim 20, 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.

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

32. 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; and

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

33. The method according to claim 32, 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.

34. The method according to claim 32, further comprising:

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.

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

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

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

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

39. The method according to claim 32, 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.

40. The method according to claim 32, 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.

41. The method according to claim 32, 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.

42. The method according to claim 32, 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.

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

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

a microprocessor configured to

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.

45. The device according to claim 44, wherein the microprocessor is configured to provide the channel list by being further configured to

select from the topology a first path connecting the source and destination,

identify channel identifiers for channels along the first path;

determine dependencies between the channel identifiers based on a deadlock-free routing algorithm, and

construct the channel list by topologically ordering the channel identifiers according to the dependencies.

46. The device according to claim 44, wherein any dependency from one channel to another in the channel list only points to a channel identifier with a higher position in the channel list.

47. The device according to claim 45, wherein the microprocessor is configured to select, from the topology, the first path connecting the source and destination and identify channel identifiers for channels along the first path by being further configured to

receive an indication of a failure of the first path in the topology, and

identify channel identifiers for the failed path.

49. The device according to claim 44, wherein the microprocessor is configured to provide a source/destination pair by being further configured to select the source/destination pair from the topology based on a predefined traffic pattern provided by an application.

50. The device according to claim 44, wherein the microprocessor is configured to provide a source/destination pair by being further configured to select the source/destination pair from the topology based on traffic load for at least one network router or switch.

51. The device according to claim 44, wherein the microprocessor is further configured to

store the at least one provided path in a routing table.

52. The device according to claim 45, wherein the microprocessor is further configured to

replace, in a routing table, the first path with the at least one provided path.

53. The device according to claim 45, wherein the microprocessor is configured to determine dependencies between the channel identifiers by being further configured to

generate a new valid channel list in which channels dependencies from the first path are removed, and

generate at least one path based on the new valid channel list.

54. The device according to claim 53, wherein the microprocessor is configured to generate the new valid channel list by being further configured to

move the target channel of a dependency to a higher position in the channel list, and repeat the move for any following dependencies.

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

search the topology to create a route around the first path using only legal turns.

56. The device according to claim 55, wherein the microprocessor is configured to search the topology to create the route around the first path using only legal turns by being further configured to utilize a shortest path algorithm.

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

search the topology to create a route around the first path using legal turns, and if necessary illegal turns.

58. The device according to claim 56, wherein the shortest path algorithm is Dijkstra shortest path algorithm.

59. The device according to claim 58, wherein the shortest path algorithm obtains the shortest path between the source and the destination considering constraints of the channel list and any pre-existing routing table entries for the source and destination.

60. The device according to claim 56, wherein the shortest path algorithm is implemented on a reverse path from the destination to the source.

61. The device according to claim 56, wherein the shortest path algorithm utilizes a cost function which considers a number of hops, a number of illegal turns performed on the path from the source to the destination, and an index of all illegal turns utilized by the shortest path algorithm.

62. The device according to claim 44, 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 channel list.

48. (canceled)

63. 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, and

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

64. The device according to claim 63, wherein the microprocessor configured to provide the node list by being further configured to

a) select a 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.

65. The device according to claim 63, wherein the microprocessor is further configured to

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 the first position.

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

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

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

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

70. The device according to claim 63, 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.

71. The device according to claim 63, 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.

72. The device according to claim 63, 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.

73. The device according to claim 63, 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.

74. The method according to claim 64, 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.

75. 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, and

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

76. The device according to claim 75, wherein 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.

77. The device according to claim 75, wherein the microprocessor is further configured to

select a source from the topology,

identify channels whose ingress node is the source;

identify positions associated with the identified channels,

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.

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

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

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

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

82. The device according to claim 75, 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.

83. The device according to claim 75, 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.

84. The device according to claim 75, 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.

85. The device according to claim 75, 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.

86. The device according to claim 76, 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.