Bandwidth load consideration in network route selection

• US 6,697,333 B1
• Filed: 03/04/1998
• Issued: 02/24/2004
• Est. Priority Date: 03/04/1998
• Status: Expired due to Term

• Current Assignee: WSOU Investments, LLC (WSOU Holdings, LLC)
• Original Assignee: Alcatel Canada Inc. (Nokia Corporation)
• Inventors: Holloway, Mike, Brown, Bruce, Bawa, Satvinder Singh
• Primary Examiner(s): Pham, Chi
• Assistant Examiner(s): Boakye, Alexander O.
• Application Number:
  US09/034,399
• Time in Patent Office: 2,183 Days
• Field of Search: 370/238, 370/351, 370/400, 370/395, 370/410, 370/254, 370/255, 370/401, 370/230, 370/238.1, 370/252, 709/238, 709/239, 709/241, 340/827
• US Class Current: 370/238
• CPC Class Codes: H04L 45/10 Routing in connection-oriented networks, e.g. X.25 or ATM
• CPC Class Codes: H04L 45/124 using a combination of metrics
• CPC Class Codes: H04L 45/125 based on throughput or bandwidth
• CPC Class Codes: H04L 45/22 Alternate routing
• CPC Class Codes: H04L 45/28 using route fault recovery

Abstract

Methods of considering bandwidth load or load balancing in the selection of an optimal path for routing calls through a switched digital network are described. The described methods are applicable to both new calls and existing connected calls. Algorithms that take into consideration selection criteria such as route cost, number of link hops in the route in addition to bandwidth load are presented.

Claims

1. A method of determining an optimal path between a source and a destination in a digital communications network having multiple alternate paths, comprising:

evaluating routing criteria of each of the alternate paths, each of the alternate paths having multiple link hops, said routing criteria including cost, number of link hops and bandwidth;

selecting the alternate representing the least cost;

if several alternatives have equal least cost then select from equal least cost paths an alternative having least number of link hops;

if several alternatives have equal least cost and equal least number of link hops then select from paths having equal least cost and equal least number of link hops an alternative having the best bandwidth criteria;

wherein said bandwidth criteria is an average bandwidth represented as an aggregate of bandwidth usage for each link hop making up said path between said source and said destination divided by the number of link hops in said path.

2. A method as defined in claim 1 wherein said switched digital communication network is an Asynchronous Transfer Mode (ATM) network.

3. A method as defined in claim 1 wherein said switched digital communication network is a Frame Relay (FR) network.

4. A method as defined in claim 1 wherein said multiple alternate paths between said source and said destination comprise links between multiple intermediate switching nodes.

5. A method as defined in claim 4 wherein said links are physical links.

6. A method as defined in claim 4 wherein said links are logical links.

7. The method as defined in claim 1 wherein said bandwidth criteria is bandwidth utilization of said link hops on said path.

8. The method as defined in claim 7 wherein said bandwidth utilization is the sum of bandwidth utilization on said alternate path.

9. A method of selecting an optimal path for rerouting a connected call between a source and a destination in a digital communication network having multiple alternate paths comprising:

determining relative routing criteria respecting each of said multiple paths, said multiple of said paths each having multiple link hops, said routing criteria including cost, number of link hops in said path and bandwidth load;

selecting a re-route path having least cost;

if several of said multiple alternatives have equal least cost selecting a re-route path having the least number of link hops;

if several of said alternate paths have equal least cost and equal least number of link hops, selecting re-route path having a lowest average bandwidth usage;

if several of said multiple paths have equal least cost, equal least number of link hops and equal average bandwidth usage select a re-route path having the largest number of link hops carrying said connected call;

wherein said average bandwidth is an aggregate of bandwidth usage for each link hop making up said path between said source and said destination divided by the number of link hops in said path.

10. A method as defined in claim 9 wherein said switched digital communication network is an Asynchronous Transfer Mode (ATM) network.

11. A method as defined in claim 9 wherein said switched digital communication network is a Frame Relay (FR) network.

12. A method as defined in claim 9 wherein said multiple alternate paths between said source and said destination comprise links between multiple intermediate switching nodes.

13. A method as defined in claim 12 wherein said links are physical links.

14. A method as defined in claim 12 wherein said links are logical links.

15. A method of determining an optimal path in a switched digital communication network having multiple alternate paths between a source and a destination comprising evaluating routing criteria of each of the alternate paths, each of the alternate paths having multiple link hops, the routine criteria including cost, number of link hops and bandwidth criteria;

and selecting the alternate having the best bandwidth criteria wherein the bandwidth criteria is an average bandwidth represented as an aggregate of bandwidth usage for each link hop making up the alternate path between source and the destination divided by the number of link hops in the alternate path, and if several alternate paths have equal bandwidth criteria, selecting the alternate representing the least cost; and

if several alternatives have equal least cost and equal bandwidth criteria then selecting from paths having equal least cost and equal bandwidth criteria an alternative having the least number of link hops.