Method of optimizing network capacity and fault tolerance in deadlock-free routing

• US 20030142627A1
• Filed: 01/31/2002
• Published: 07/31/2003
• Est. Priority Date: 01/31/2002
• Status: Active Grant

• Current Assignee: Oracle America, Inc. (Oracle Corporation)
• Original Assignee: Sun Microsystems Incorporated (Oracle Corporation)
• Inventors: Yuksel, Murat, Chiu, Dah Ming, Kadansky, Miriam C.
• Granted Patent: US 7,200,117 B2
• Time in Patent Office: Days
• US Class Current: 370/238
• 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/124 using a combination of metrics
• CPC Class Codes: H04L 45/22 Alternate routing

Abstract

A system for selecting routing information from a routing table describing alternative routes between end nodes. The routing table represents a set of minimum cost, deadlock-free routes between end nodes. The selected routing information is included in forwarding tables, and sent to networking devices in the network. The selected routing information is optimized for at least one network performance metric, such as overall network capacity or fault tolerance. Capacity optimization is obtained by selecting from alternative routes stored within the routing table such that the standard deviation of the number of routes flowing over each link in the network is minimized. Fault tolerance optimization is achieved by selecting from the alternative routes stored in the routing table such that the selected route for a given end node pair has a “failover” route with a maximum number of dissimilar links from the selected route.

Claims

1. A method for selecting routing information to be provided to devices in a communication network, comprising:

obtaining routing information describing a plurality of routes between forwarding devices of said communication network, wherein said plurality of routes is deadlock free, and wherein said routing information includes a plurality of alternative routes;

selecting one of said plurality of alternative routes, wherein said selecting optimizes a performance metric; and

delivering said selected one of said plurality of alternative routes to at least one forwarding device in said communication network.

2. The method of claim 1, wherein said performance metric is network capacity.

3. The method of claim 2, wherein said step of selecting one of said plurality of alternative routes further comprises:

determining a first set of data flows between end nodes attached to said communication network, wherein said first set of data flows is determined, at least in part, responsive to a first one of said alternative routes;

determining, responsive to said first set of data flows, a first standard deviation, wherein said first standard deviation describes a distribution of said first set of data flows across links in said communication network;

determining a second set of data flows between end nodes attached to said communication network, wherein said second set of data flows is determined response to a second one of said alternative routes;

determining, responsive to said second set of data flows, a second standard deviation, wherein said second standard deviation describes a distribution of said second set of data flows across links in said communication network;

comparing said first standard deviation and said second standard deviation;

selecting said first one of said alternative routes in the event that said first standard deviation is lower than said second standard deviation; and

selecting said second one of said alternative routes in the event that said second standard deviation is lower than said first standard deviation.

4. The method of claim 1, wherein said performance metric is fault tolerance.

5. The method of claim 4, wherein said step of selecting one of said plurality of alternative routes comprises:

determining a first difference measure, said first difference measure reflecting a number of differing links between a first pair of said alternative routes;

determining a second difference measure, said second difference measure reflecting a number of differing links between a second pair of said alternative routes;

comparing said first difference measure and said second difference measure;

determining a selected pair of said alternative routes, wherein said selected pair of said alternative routes comprises said first pair of said alternative routes in the event said first difference measure is greater than said second difference measure, and wherein said selected pair of alternative routes comprises said second pair of alternative routes in the event said second difference measure is greater than said first difference measure; and

designating a first one of said selected pair of said alternative routes as an enabled route, and designating a second one of said selected pair of said alternative routes as a backup route.

6. The method of claim 5, further comprising:

detecting a failure of said enabled route; and

replacing said enabled route with said backup route.

7. A system for selecting routing information to be provided to devices in a communication network, comprising routing logic operable to:

obtain routing information describing a plurality of routes between forwarding devices of said communication network, wherein said plurality of routes is deadlock free, and wherein said routing information includes a plurality of alternative routes;

select one of said plurality of alternative routes, wherein said selecting optimizes a performance metric; and

deliver said selected one of said plurality of alternative routes to at least one forwarding device in said communication network.

8. The system of claim 7, wherein said performance metric is network capacity.

9. The system of claim 8, wherein said routing logic is further operable to:

determine a first set of data flows between end nodes attached to said communication network, wherein said first set of data flows is determined, at least in part, responsive to a first one of said alternative routes;

determine, responsive to said first set of data flows, a first standard deviation, wherein said first standard deviation describes a distribution of said first set of data flows across links in said communication network;

determine a second set of data flows between end nodes attached to said communication network, wherein said second set of data flows is determined response to a second one of said alternative routes;

determine, responsive to said second set of data flows, a second standard deviation, wherein said second standard deviation describes a distribution of said second set of data flows across links in said communication network;

compare said first standard deviation and said second standard deviation;

select said first one of said alternative routes in the event that said first standard deviation is lower than said second standard deviation; and

select said second one of said alternative routes in the event that said second standard deviation is lower than said first standard deviation.

10. The system of claim 8, wherein said performance metric is fault tolerance.

11. The system of claim 10, wherein said routing logic is further operable to:

determine a first difference measure, said first difference measure reflecting a number of differing links between a first pair of said alternative routes;

determine a second difference measure, said second difference measure reflecting a number of differing links between a second pair of said alternative routes;

compare said first difference measure and said second difference measure;

determine a selected pair of said alternative routes, wherein said selected pair of said alternative routes comprises said first pair of said alternative routes in the event said first difference measure is greater than said second difference measure, and wherein said selected pair of alternative routes comprises said second pair of alternative routes in the event said second difference measure is greater than said first difference measure; and

designate a first one of said selected pair of said alternative routes as an enabled route, and designating a second one of said selected pair of said alternative routes as a backup route.

12. The system of claim 11, wherein said routing logic is further operable to:

detect a failure of said enabled route; and

replace said enabled route with said backup route.

13. The system of claim 7, wherein said routing logic comprises at least one digital logic circuit.

14. The system of claim 7, wherein said routing logic comprises program code loaded into a memory of a computer system.

15. A system for selecting routing information to be provided to devices in a communication network, comprising:

means for obtaining routing information describing a plurality of routes between forwarding devices of said communication network, wherein said plurality of routes is deadlock free, and wherein said routing information includes a plurality of alternative routes;

means for selecting one of said plurality of alternative routes, wherein said selecting optimizes a performance metric; and

means for delivering said selected one of said plurality of alternative routes to at least one forwarding device in said communication network.

16. A computer program product including a computer readable medium, said computer readable medium having a computer program stored thereon, said computer program for selecting routing information for distribution to at least one networking device, said computer program comprising:

program code for obtaining routing information describing a plurality of routes between forwarding devices of said communication network, wherein said plurality of routes is deadlock free, and wherein said routing information includes a plurality of alternative routes;

program code for selecting one of said plurality of alternative routes, wherein said selecting optimizes a performance metric; and

program code for delivering said selected one of said plurality of alternative routes to at least one forwarding device in said communication network.