Constraint-based routing between ingress-egress points in a packet network

• US 6,538,991 B1
• Filed: 08/03/1999
• Issued: 03/25/2003
• Est. Priority Date: 08/03/1999
• Status: Expired due to Term

• Current Assignee: WSOU Investments, LLC (WSOU Holdings, LLC)
• Original Assignee: Lucent Technologies, Inc. (Nokia Corporation)
• Inventors: Kodialam, Muralidharan S., Lakshman, T. V.
• Primary Examiner(s): Kizou, Hassan
• Assistant Examiner(s): ODLAND, DAVID E
• Application Number:
  US09/366,619
• Time in Patent Office: 1,330 Days
• Field of Search: 370/229-235, 370/237, 370/238, 370/351-356, 370/389, 370/392, 370/393, 370/395--39, 370/396, 709/226, 709/238-243
• US Class Current: 370/229
• CPC Class Codes: H04L 41/5003 Managing SLA; Interaction between SLA and QoS
• CPC Class Codes: H04L 41/5025 by proactively reacting to service quality change, e.g. by reconfiguration after service quality degradation or upgrade
• 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/14 Routing performance; Theoretical aspects
• CPC Class Codes: H04L 45/302 Route determination based on requested QoS
• CPC Class Codes: H04L 45/308 Route determination based on user's profile, e.g. premium users
• CPC Class Codes: H04L 45/50 using label swapping, e.g. multi-protocol label switch [MPLS]
• CPC Class Codes: H04L 47/15 in relation to multipoint traffic arrangements for broadcast or multicast in data networks H04L12/18
• CPC Class Codes: H04L 47/70 Admission control; Resource allocation
• CPC Class Codes: H04L 47/724 at intermediate nodes, e.g. resource reservation protocol [RSVP]
• CPC Class Codes: H04L 47/781 Centralised allocation of resources
• CPC Class Codes: H04L 47/783 Distributed allocation of resources, e.g. bandwidth brokers
• CPC Class Codes: H04L 47/822 Collecting or measuring resource availability data
• CPC Class Codes: H04L 47/825 Involving tunnels, e.g. MPLS
• CPC Class Codes: H04L 47/829 Topology based
• CPC Class Codes: H04L 47/83 based on usage prediction

Abstract

A packet network of interconnected nodes employs a constraint-based routing method to determine a path through the network for a requested label-switched path (LSP). Each of the nodes includes one or more routers that forward packets based on a forwarding table constructed from paths determined in accordance with the constraint-based routing method. The constraint-based method determines the path of the requested LSP based on the effect that routing those packets of the requested LSP may have on current and/or future demands on the capacity of network nodes for currently provisioned LSPs. Such constraint-based routing method may not necessarily route packets of a requested LSP along the shortest path, or minimum number of hops, through the network. Given the packet network and LSP request, a linear programming system is defined by a set of linear programming equations. The linear programming system is based on the network topology, the values of the ingress-egress point pair o and t and demand bd of the LSP request, and the total maxflow values of the existing ingress-egress point pair for currently provisioned LSPs. The solution is estimated for a linear programming system of either split demand, non-split demand, or batch demand implementations for routing packets of the LSP. The constraint-based routing method may solve the linear programming system using common linear programming techniques.

Claims

1. A method of routing data through a network of nodes interconnected by links and having a plurality of ingress-egress point pairs, comprising the steps of:

(a) receiving a request for a path for routing data between one of the ingress-egress point pairs of the network; and

(b) allocating service levels within the links of the network for the path taking into account impacts to existing service levels of paths corresponding to the other ingress-egress point pairs of the network, wherein step (b) comprises the steps of;

(b1) defining a system of equations in accordance with the network based on a maximization criteria for a set of maxflow values;

(b2) calculating the set of maxflow values for the network and system of equations defined in step (b1); and

(b3) estimating a solution to the system of equations by allocating the service levels for the path accounting for the set of maxflow values.

2. The method as recited in claim 1, wherein the maximization criteria is either maximizing the sum of the maxflow values or maximizing the sum of the minimum maxflow values.

3. The method as recited in claim 1, wherein the step of defining in step (b1) includes a set of nodes, a set of links, and a set of available capacity values for each of the set of links of the network.

4. The method as recited in claim 3, wherein the system of equations for the request is either split demand linear programming system for a split demand case;

an integer programming system for a non-split demand case;

or a batch demand integer programming system for a batch demand case.

5. The method as recited in claim 1, further comprising the step of (b4) testing the solution estimated in step (b3) and, if the test fails , not allocating service levels for the path of the request.

6. The method as recited in claim 1, wherein the request of step (a) is a network tunnel request of either an asynchronous mode (ATM) network, an internet protocol (IP) network, or a multi-protocol label switched path (MPLS) network.

7. The method as recited in claim 6, wherein the request is in accordance with either a reservation protocol or a label distribution protocol.

8. A router that routes data in a network of nodes interconnected by links and having a plurality of ingress-egress point pairs, the router having a controller comprising:

a control module for receiving a request for a path for routing data between one of the ingress-egress point pairs of the network; and

a routing module for allocating service levels within the links of the network for the path taking into account impacts to existing service levels of paths corresponding to the other ingress-egress point pairs of the network;

wherein the routing module allocates service levels by

     1) defining a system of equations in accordance with the network based on a maximization criteria for a set of maxflow values;

     2) calculating the set of maxflow values for the network and defined system of equations; and

     3) estimating a solution to the system of equations by allocating the service levels for the path accounting for the set of maxflow values.

9. The invention as recited in claim 8, wherein the maximization criteria is either maximizing the sum of the maxflow values or maximizing the sum of the minimum maxflow values.

10. The invention as recited in claim 8, wherein the system of equations is defined using a set of nodes, a set of links, and a set of available capacity values for each of the set of links of the network.

11. The invention as recited in claim 10, wherein the system of equations for the request is either split demand linear programming system for a split demand case;

an integer programming system for a non-split demand case;

or a batch demand integer programming system for a batch demand case.

12. The invention as recited in claim 8, wherein the request is a network tunnel request of either an asynchronous mode (ATM) network, an internet protocol (IP) network, or a multi-protocol label switched path (MPLS) network.

13. The invention as recited in claim 12, wherein the request is in accordance with either a reservation protocol or a label distribution protocol.

14. A computer-readable medium having stored thereon a plurality of instructions, the plurality of instructions including instructions which, when executed by a processor, cause the processor to implement a method for of routing data through a network of nodes interconnected by links and having a plurality of ingress-egress point pairs, the method comprising the steps of:

(a) receiving a request for a path for routing data between one of the ingress-egress point pairs of the network; and

(b) allocating service levels within the links of the network for the path taking into account impacts to existing service levels of paths corresponding to the other ingress-egress point pairs of the network, wherein step (b) comprises the steps of;

(b1) defining a system of equations in accordance with the network based on a maximization criteria for a set of maxflow values;

(b2) calculating the set of maxflow values for the network and system of equations defined in step (b1); and

(b3) estimating a solution to the system of equations by allocating the service levels for the path accounting for the set of maxflow values.

15. The invention as recited in claim 16, wherein the maximization criteria is either maximizing the sum of the maxflow values or maximizing the sum of the minimum maxflow values.

16. The invention as recited in claim 14, wherein the step of defining in step (b1) includes a set of nodes, a set of links, and a set of available capacity values for each of the set of linkks the network.

17. The invention as recited in claim 16, wherein the system of equations for the request is either split demand linear programming system for a split demand case;

an integer programming system for a non-split demand case;

or a batch demand integer programming system for a batch demand case.

18. The invention as recited in claim 14, further comprising the step of (b4) testing the solution estimated in step (b3) and, if the test fails , not allocating service levels for the path of the request.

19. The invention as recited in claim 14, wherein the request of step (a) is a network tunnel request of either an asynchronous mode (ATM) network, an internet protocol (IP) network, or a multi-protocol label switched path (MPLS) network.

20. The invention as recited in claim 19, wherein the request is in accordance with either a reservation protocol or a label distribution protocol.