Routing with service level guarantees between ingress-egress points in a packet network

• US 6,584,071 B1
• Filed: 08/03/1999
• Issued: 06/24/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: Lakshman, T. V., Kodialam, Muralidharan S.
• Primary Examiner(s): Kizou, Hassan
• Assistant Examiner(s): WAXMAN, ANDREW
• Application Number:
  US09/366,620
• Time in Patent Office: 1,421 Days
• Field of Search: 370/235-238, 370/354, 370/355, 370/395, 370/397, 370/399, 370/252, 370/359, 379/221-6-2, 709/235-241
• US Class Current: 370/238
• CPC Class Codes: H04L 45/02 Topology update or discovery
• CPC Class Codes: H04L 45/10 Routing in connection-oriented networks, e.g. X.25 or ATM
• CPC Class Codes: H04L 45/12 Shortest path evaluation
• CPC Class Codes: H04L 45/122 by minimising distances, e.g. by selecting a route with minimum of number of hops
• CPC Class Codes: H04L 45/124 using a combination of metrics
• 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]

Abstract

A packet network of interconnected nodes employs a method of routing with service level guarantees 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 method of routing with service level guarantees. The method of routing with service level guarantees 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 method of routing with service level guarantees 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 may be defined by a set of linear programming equations for a non-split demand case. 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. To estimate the solution for the linear programming system, a subnetwork is formed using link weights and links removed that cannot support the requested demand. Link weights are calculated based on the critical links of a pseudo-network in which increased maximum flow along existing paths between ingress-egress point pairs is maintained. A shortest path routing algorithm may then be employed to generate a path, if available, for the LSP request using the subnetwork with the calculated link weights.

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 with a service demand for routing data between one of the ingress-egress point pairs of the network;

(b) defining a subnetwork of nodes and links employing the nodes and the links of the network and based on the service demand;

(c) defining a set of link weights for the links of the subnetwork accounting for impacts to existing service levels of paths corresponding to the other ingress-egress point pairs of the network, wherein step (c) comprises the steps of;

(c1) calculating a set of maxflow values for the network,

(c2) defining a pseudo-network having nodes and links corresponding to the nodes and links of the network,

(c3) adjusting an available capacity for each of the links in the pseudo-network based on existing capacity of the links when allowing for the existing service levels of paths of the other ingress-egress point pairs of the network,

(c4) setting the available capacity for each of the links in the pseudo-network to a corresponding pseudo-capacity, the pseudo-capacity for each link based on the difference between the corresponding available capacity of the link and the service demand of the request,

(c5) determining a set of critical links for the pseudo-network based on each pseudo-capacity, each critical link corresponding to a link of the network that, when the service demand of the request is routed through the link, relates to a reduction of one or more maxflow values, and

(c6) calculating each link weight based on a number of the other ingress-egress point pairs having a path including the corresponding link as a critical link; and

(d) determining a shortest path through the subnetwork for the request in accordance with the set of weights for the links, the shortest path being the path with the service demand between the one of the ingress-egress point pairs of the network.

2. The invention as recited in claim 1, wherein step (b) comprises the steps of:

(b1) defining the subnetwork having the nodes and the links corresponding to the nodes and links of the network;

(b2) adjusting an available capacity for each of the links in the subnetwork accounting for existing capacity of the links when allowing for the existing service levels of paths of the other ingress-egress point pairs of the network;

(b3) calculating a value for each link based on the difference between the corresponding available capacity of the link and the service demand of the request; and

(b4) removing one or more the links of the subnetwork based on each link value.

3. The invention as recited in claim 1, wherein step c(5) determines the set of critical links by adding a link of the pseudo-network to the set of critical links if the link has a predefined amount of pseudo capacity or the link is not included in any path between the ingress-egress point pair of the request.

4. The invention as recited in claim 1, wherein step c(1) computes the maxflow values in accordance with a maximization criteria of either maximizing the sum of the maxflow values or maximizing the sum of the minimum maxflow values.

5. The invention 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.

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

7. Apparatus for routing data through a network of nodes interconnected by links and having a plurality of ingress-egress point pairs, comprising:

an input module for receiving

     1) a request for a path with a service demand for routing data between one of the ingress-egress point pairs of the network; and

     2) the data associated with the request;

a processing module for determining the path of the request, wherein the processing module;

1) determines the path by;

(A) defining a subnetwork of nodes and links employing the nodes and the links of the network and based on the service demand;

(B) defining a set of link weights for the links of the subnetwork accounting for impacts to existing service levels of paths corresponding to the other ingress-egress point pairs of the network; and

(C) determining a shortest path through the subnetwork for the request in accordance with the set of weights for the links, the shortest path being the path with the service demand between the one of the ingress-egress point pairs of the network; and

2) defines the set of weights by;

(B1) calculating a set of maxflow values for the network;

(B2) defining a pseudo-network having nodes and links corresponding to the nodes and links of the network;

(B3) adjusting an available capacity for each of the links in the pseudo-network based on existing capacity of the links when allowing for the existing service levels of paths of the other ingress-egress point pairs of the network;

(B4) setting the available capacity for each of the links in the pseudo-network to a corresponding pseudo-capacity, the pseudo-capacity for each link based on the difference between the corresponding available capacity of the link and the service demand of the request;

(B5) determining a set of critical links for the pseudo-network based on each pseudo-capacity, each critical link corresponding to a link of the network that, when the service demand of the request is routed through the link, relates to a reduction of one or more maxflow values; and

(B6) calculating each link weight based on a number of the other ingress-egress point pairs having a path including the corresponding link as a critical link; and

a switch-fabric for transferring the packets from the input module to an output module of the router in accordance with the path of the request.

8. The invention as recited in claim 7, wherein the processing module defines the subnetwork by:

(A1) defining the subnetwork having the nodes and the links corresponding to the nodes and links of the network;

(A2) adjusting an available capacity for each of the links in the subnetwork accounting for existing capacity of the links when allowing for the existing service levels of paths of the other ingress-egress point pairs of the network;

(A3) calculating a value for each link based on the difference between the corresponding available capacity of the link and the service demand of the request; and

(A4) removing one or more the links of the subnetwork based on each link value.

9. 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 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 with a service demand for routing data between one of the ingress-egress point pairs of the network;

(b) defining a subnetwork of nodes and links employing the nodes and the links of the network and based on the service demand;

(c) defining a set of weights for the links of the subnetwork accounting for impacts to existing service levels of paths corresponding to the other ingress-egress point pairs of the network, wherein step (c) comprises the steps of;

(c1) calculating a set of maxflow values for the network,

(c2) defining a pseudo-network having nodes and links corresponding to the nodes and links of the network,

(c3) adjusting an available capacity for each of the links in the pseudo-network based on existing capacity of the links when allowing for the existing service levels of paths of the other ingress-egress point pairs of the network,

(c4) setting the available capacity for each of the links in the pseudo-network to a corresponding pseudo-capacity, the pseudo-capacity for each link based on the difference between the corresponding available capacity of the link and the service demand of the request,

(c5) determining a set of critical links for the pseudo-network based on each pseudo-capacity, each critical link corresponding to a link of the network that, when the service demand of the request is routed through the link, relates to a reduction of one or more maxflow values, and

(c6) calculating each link weight based on a number of the other ingress-egress point pairs having a path including the corresponding link as a critical link; and

(d) determining a shortest path through the subnetwork for the request in accordance with the set of weights for the links, the shortest path being the path with the service demand between the one of the ingress-egress point pairs of the network.

10. The invention as recited in claim 9, wherein step (b) comprises the steps of:

(b1) defining the subnetwork having the nodes and the links corresponding to the nodes and links of the network;

(b2) adjusting an available capacity for each of the links in the subnetwork accounting for existing capacity of the links when allowing for the existing service levels of paths of the other ingress-egress point pairs of the network;

(b3) calculating a value for each link based on the difference between the corresponding available capacity of the link and the service demand of the request; and

(b4) removing one or more the links of the subnetwork based on each link value.

11. The invention as recited in claim 9, wherein step c(5) determines the set of critical links by adding a link of the pseudo-network to the set of critical links if the link has a predefined amount of pseudo capacity or the link is not included in any path between the ingress-egress point pair of the request.

12. A router for routing data through a network of nodes interconnected by links and having a plurality of ingress-egress point pairs, comprising:

an input module for receiving

     1) a request for a path with a service demand for routing data between one of the ingress-egress point pairs of the network; and

     2) the data associated with the request;

a processing module for determining the path of the request, wherein the processing module;

1) determines the path by;

(A) defining a subnetwork of nodes and links employing the nodes and the links of the network and based on the service demand;

(B) defining a set of link weights for the links of the subnetwork accounting for impacts to existing service levels of paths corresponding to the other ingress-egress point pairs of the network; and

(C) determining a shortest path through the subnetwork for the request in accordance with the set of weights for the links, the shortest path being the path with the service demand between the one of the ingress-egress point pairs of the network; and

2) defines set of the weights by;

(B1) calculating a set of maxflow values for the network;

(B2) defining a pseudo-network having nodes and links corresponding to the nodes and links of the network;

(B3) adjusting an available capacity for each of the links in the pseudo-network based on existing capacity of the links when allowing for the existing service levels of paths of the other ingress-egress point pairs of the network;

(B4) setting the available capacity for each of the links in the pseudo-network to a corresponding pseudo-capacity, the pseudo-capacity for each link based on the difference between the corresponding available capacity of the link and the service demand of the request;

(B5) determining a set of critical links for the pseudo-network based on each pseudo-capacity, each critical link corresponding to a link of the network that, when the service demand of the request is routed through the link, relates to a reduction of one or more maxflow values; and

(B6) calculating each link weight based on a number of the other ingress-egress point pairs having a path including the corresponding link as a critical link; and

a switch-fabric for transferring the packets from the input module to an output module of the router in accordance with the path of the request.