Multi-constraint routing system and method

• US 20030118027A1
• Filed: 12/26/2001
• Published: 06/26/2003
• Est. Priority Date: 12/26/2001
• Status: Active Grant

• Current Assignee: Alcatel-Lucent Canada Incorporated (Nokia Corporation)
• Original Assignee: Tropic Networks, Inc. (Nokia Corporation)
• Inventors: Lee, Byoung-Joon, Srinivasan, Anand, Wong, Vincent Chi Chiu, Ganti, Sudhakar, Neustadter, Udo Mircea, Carpini, Walter Joseph, Dang, Cuong Tu
• Granted Patent: US 6,925,061 B2
• Time in Patent Office: Days
• US Class Current: 370/395.21
• CPC Class Codes: H04L 45/24 Multipath
• CPC Class Codes: H04L 49/205 Quality of Service based
• CPC Class Codes: H04L 49/25 Routing or path finding in a switch fabric
• CPC Class Codes: H04L 49/254 Centralised controller, i.e. arbitration or scheduling

Abstract

A routing system and method are provided which use a composite cost in identifying routes. This allows a simple way of identifying the best route taking multiple metrics into account for each link simultaneously. The system allows for the inclusion of pruning constraints, and allows for various objectives such as bin packing or load balancing to be achieved.

Claims

1. A method of performing multi-constraint routing comprising:

determining a composite cost;

composite cost(link)=f(metric₁, . . . , metric_N)

for each of a plurality of links under consideration in a network topology, the composite cost being a function f of a plurality of metrics metric₁, . . . metric_N for each link, where N>

=2;

performing routing through the network topology from a source to a destination based on the composite costs.

2. A method according to claim 1 wherein the composite cost is determined according to:

3. A method according to claim 2 wherein the composite cost is determined according to:

composite cost(link)=a*(1/Bandwidth)+b*Admin cost+c*Delay

where metric₁=bandwidth, metric₂=Admin cost and metric₃=delay, and wherein c₁=a, c₂=b, and c₃=c, n(1)=−

1, n(2)=1 and n(3)=1.

4. A method according to claim 1 further comprising:

for each link, at least one network node advertising the link'"'"'s metrics across the network such that any node in the network may implement the multi-constraint routing.

5. A method according to claim 1 further wherein:

the composite cost increases with decreasing available bandwidth such routing is performed in a manner which promotes load balancing.

6. A method according to claim 5 further comprising:

performing the routing in a manner which promotes load balancing with demand reservation on at least one link.

7. A method according to claim 6 further comprising:

defining a respective demand threshold for at least one link representing demand reservation for the at least one link.

8. A method according to claim 7 further comprising:

computing a cost for each said at least one link as follows;

if (available bandwidth<

demand_threshold)cost=composite cost+very large valueelse cost=composite cost

where demand_threshold is a respective demand reservation for the link.

9. A method according to claim 8 wherein the demand_threshold is set to a first value for at least one of the links, and is set to a second larger value for at least one of the links whereby bandwidth on the at least one of the links having the first value is reserved for larger bandwidth requests.

10. A method according to claim 1 further comprising:

for each of a plurality of different traffic types, using a respective different composite cost equation for calculating the composite costs.

11. A method according to claim 10 wherein the different traffic types include video, voice and data.

12. A method according to claim 10 wherein the different traffic types include different classes of service/qualities of service.

13. A method according to claim 1 further comprising:

providing at least one pruning constraint for each link;

pruning the network topology on the basis of the at least one pruning constraints to remove at least one link from the network topology;

wherein performing routing through the network from a source to a destination based on the composite costs is conducted using only the links not pruned from the network topology.

14. A method according to claim 13 wherein:

pruning the network topology on the basis of the at least one pruning constraints to remove at least one link from the network topology is performed on an as needed basis to remove one or more links from a set of candidate links.

15. A method according to claim 13 wherein:

pruning the network topology on the basis of the at least one pruning constraints to remove at least one link from the network topology is performed on the entire network topology prior to performing the routing.

16. A method according to claim 14 wherein at least one constraint is used both as a pruning constraint and as a constraint used in the composite costs.

17. A routing system adapted to perform multi-constraint routing, the system comprising:

a topology repository adapted to store information identifying links, nodes and connections of a network

a multi-constraint router adapted to determine a composite cost;

composite cost (link)=f(metric₁, . . . , metric_N)

 

for each of a plurality of the links in the network topology, the composite cost being a function f of a plurality of metrics metric₁, . . . metric_N for each link, where N>

=2, and to perform routing through the network topology from a source to a destination based on the composite costs.

18. A routing system according to claim 17 wherein the multi-constraint router is adapted to determine the composite cost is determined according to:

19. A routing system according to claim 18 wherein the multi-constraint router is adapted to determine the composite cost is determined according to:

composite cost(link)=a*(1/Bandwidth)+b*Admin cost+c*Delay

metric₁=bandwidth, metric₂=Admin cost and metric₃=delay, and wherein c₁=a, c₂=b and c₃=c, n(1)=−

1, n(2)=1 and n(3)=1.

20. A routing system according to claim 17 further comprising:

an input for receiving on an ongoing basis for each link, updated values for the metrics for the link.

21. A routing system according to claim 17 wherein the multi-constraint router is adapted to perform the routing in a manner which promotes load balancing.

22. A routing system according to claim 21 wherein the multi-constraint router is adapted to perform the routing in a manner which promotes load balancing with demand reservation.

23. A routing system according to claim 22 wherein the multi-constraint router is adapted to allocate at least one link to contain bandwidth reserved for higher bandwidth requests.

24. A routing system according to claim 23 wherein the multi-constraint router is adapted to compute the cost for each said at least one link as follows:

if (available bandwidth<

demand_threshold)cost=composite cost+very large valueelse cost=composite cost

where demand_threshold is respective demand reservation for the link.

25. A routing system according to claim 17 wherein the multi-constraint router is adapted to, for each of a plurality of different traffic types, use a respective different composite cost equation for calculating the composite costs.

26. A routing system according to claim 17 further comprising:

a pruning filter adapted to implement at least one pruning constraint by pruning the network topology on the basis of the at least one pruning constraint to remove at least one link from the network topology;

wherein the multi-constraint router performs routing through the network from a source to a destination based on the composite costs is conducted using only the links not pruned from the network topology.

27. A routing system according to claim 26 adapted to prune and compute costs only for links belonging to routes in a candidate list.