US 6,584,071 B1 · Routing with service level guarantees between ingress-egress points in a packet network

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.

Claims12

Dependent claims

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.

8 more elements

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.

15 more elements

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.

8 more elements

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.

15 more elements

Dependencies are inferred from the claim text.

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

Life of this patent

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

Life of this patent

Abstract

Claims12