Optimizing path selection for multiple service classes in a network

• US 7,346,056 B2
• Filed: 02/01/2002
• Issued: 03/18/2008
• Est. Priority Date: 02/01/2002
• Status: Active Grant

• Current Assignee: Fujitsu Limited
• Original Assignee: Fujitsu Limited
• Inventors: Devi, Bharathi B.
• Primary Examiner(s): Orgad; Edan
• Assistant Examiner(s): Park; Jung
• Application Number:
  US10/061,426
• Publication Number:
  US 20030147400A1
• Time in Patent Office: 2,237 Days
• Field of Search: None
• US Class Current: 370/392
• 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/123 Evaluation of link metrics techniques for monitoring network metrics H04L43/08
• CPC Class Codes: H04L 45/125 based on throughput or bandwidth
• CPC Class Codes: H04L 45/302 Route determination based on requested QoS

Abstract

A method for routing traffic in a network includes determining topology information for the network and determining traffic demands for multiple service classes. The method further includes determining an objective function for an optimization problem using the topology information and demands, and determining a solution to that specifies a network path for each demand.

Claims

1. A method for routing traffic in a network, comprising:

determining topology information for a network comprising a plurality of nodes and a plurality of links between the nodes;

determining a plurality of demands, each demand comprising a source node, a destination node, and service class for traffic between the source node and the destination node;

determining an objective function for an optimization problem using the topology information and the demands;

using the objective function, determining a solution to the optimization problem that simultaneously specifies a network path for each demand, wherein the objective function comprises a maximum capacity term, and wherein the solution is determined such that each link is subject to a traffic load less than a capacity of the link; and

transmitting data along the network path, wherein the maximum capacity term is weighted by multiplying the maximum capacity term by a logarithmic function of the capacity.

2. The method of claim 1, wherein the step of determining a solution to the optimization problem comprises:

determining a trial solution to the optimization problem;

determining whether the trial solution is an optimized solution to the optimization problem; and

if the trial solution is not an optimized solution, updating the trial solution.

3. The method of claim 1, wherein:

the objective function further comprises constraints specifying restrictions on traffic of one or more of the service classes; and

the solution is further determined based on the constraints.

4. The method of claim 1, wherein:

the objective function comprises a load-balancing term; and

the step of determining a solution to the optimization problem includes load balancing as a factor in the determination.

5. The method of claim 1, wherein the demands are used to populate a demand matrix comprising a plurality of paired entries, one of the entries of each pair comprising a bandwidth requirement between the source node and the destination node for one of the services classes and the other entry comprising a constraint on the service class;

and

the step of determining a solution uses the demand matrix.

6. A server, comprising:

a memory operable to store;

topology information of a network comprising a plurality of nodes and a plurality of links between the nodes; and

a plurality of demands, each demand associated with one of a plurality of service classes and each demand comprising a requested amount of traffic between a source node and a destination node; and

a processor operable to;

determine an objective function for an optimization problem using the topology information and the demands;

determine a solution to the optimization problem;

using the solution, determine a network path for each demand that provides sufficient traffic capacity between the source node and the destination node for the requested amount of traffic, wherein the objective function comprises a maximum capacity term, and wherein the solution is determined such that each link is subject to a traffic load less than a capacity of the link; and

transmitting data along the network path,

wherein the maximum capacity term is weighted by multiplying the maximum capacity term by a logarithmic function of the capacity.

7. The server of claim 6, wherein:

the memory is further operable to store constraints on traffic of one or more of the services classes; and

the processor is further operable to determine the solution to the optimization problem based on the constraints.

8. The server of claim 6, wherein the processor is further operable to:

detect a failure in one or more components of the network;

update the topology information in response to detecting the failure;

determine an updated objective function based on the updated topology information; and

determine an updated solution to the updated objective function.

9. The server of claim 6, wherein the processor is further operable to:

include a load-balancing term in the objective function; and

determine the solution to the optimization problem including the load-balancing term.

10. The server of claim 6, wherein:

the interface couples the server to the network; and

the server is operable to collect the topology information from components of the network automatically.

11. The server of claim 6, wherein:

the interface couples the server to the network; and

the processor is further operable to;

generate a message instructing components of the network to provision the determined network paths; and

communicate the message to the components using the interface.

12. The server of claim 6, wherein the interface is further operable to:

receive input from a user; and

display the network paths determined by the processor to the user.

13. A computer readable medium embodied with a computer program to perform the steps of:

determining topology information for a network comprising a plurality of nodes and a plurality of links between the nodes;

determining a plurality of demands, each demand comprising a requested amount of traffic between a source node and a destination node for one of a plurality of service classes;

determining an objective function for an optimization problem using the topology information and the demands;

using the objective function, determining a solution that specifies a network path for each demand, wherein the objective function comprises a maximum capacity term, and wherein the solution is determined such that each link is subject to a traffic load less than a capacity of the link; and

transmitting data along the network path,

wherein the maximum capacity term is weighted by multiplying the maximum capacity term by a logarithmic function of the capacity.

14. The logic of claim 13, wherein the step of determining a solution to the optimization problem comprises:

determining a trial solution to the optimization problem;

determining whether the trial solution is an optimized solution to the optimization problem; and

if the trial solution is not an optimized solution, updating the trial solution.

15. The logic of claim 13, wherein:

the objective function further comprises constraints specifying restrictions on traffic of one or more of the service classes; and

the solution is further determined based on the constraints.

16. The logic of claim 13, wherein:

the objective function comprises a load-balancing term; and

the step of determining a solution to the optimization problem includes load balancing as a factor in the determination.

17. The logic of claim 13, wherein:

the demands are used to populate a demand matrix comprising a plurality of paired entries, one of the entries of each pair comprising a bandwidth requirement between the source node and the destination node for a particular one of the services classes and the other entry comprising a constraint on the particular service class; and

the step of determining a solution uses the demand matrix.

18. A method for routing traffic in a network, comprising:

determining topology information for a network comprising a plurality of nodes and a plurality of links between the nodes;

determining a plurality of demands, each demand comprising a request for bandwidth between a source node and a destination node for one of a plurality of service classes;

determining one or more constraints, each constraint comprising a limit on traffic of one of the service classes in the network;

determining an objective function representing the network, the demands, and the constraints;

minimizing the objective function to determine a solution, the solution comprising a network path for each demand;

provisioning the network paths of the solution in the network, wherein the objective function comprises a maximum capacity term, and wherein the solution is determined such that each link is subject to a traffic load less than a capacity of the link; and

transmitting data along the network path,

wherein the maximum capacity term is weighted by multiplying the maximum capacity term by a logarithmic function of the capacity.