Dynamic traffic rearrangement and restoration for mpls networks with differentiated services capabilities

Abstract

At least one substitute path is provided in place of a plurality of existing paths of a network to reallocate traffic carried by the plurality of existing paths. The total bandwidth needed to carry the traffic of the plurality of existing paths is determined. A proposed route is generated from the available links in the network. A portion of the bandwidth of a proposed route may be allocated to the needed bandwidth when the bandwidth of a proposed route is greater than or equal to the needed bandwidth. When the bandwidth of the proposed route is less than the needed bandwidth, at least one further route is generated, and the needed bandwidth is divided among the proposed route and the at least one further route such that a minimum number of further routes are generated.

What is claimed is: 
     
         1 . A method comprising:
 determining a total bandwidth needed to carry traffic of a plurality of existing paths of a network, the determining carried out when the plurality of existing paths includes at least one failed link and the determining including determining a plurality of needed bandwidths;   generating a proposed route from available links in the network;   successively allocating in order of decreasing bandwidth for each non-allocated bandwidth of the plurality of needed bandwidths, a respective part of a remaining portion of the bandwidth of the proposed route to the needed bandwidth and assigning corresponding traffic to the proposed route when the bandwidth of the proposed route is greater than or equal to the needed bandwidth; and   generating at least one further route when the bandwidth of the proposed route is less than the needed bandwidth and dividing the needed bandwidth among the proposed route and the at least one further route such that a minimum number of further routes are generated.   
     
     
         2 . The method of  claim 1 , wherein the needed bandwidths correspond to a plurality of service classes. 
     
     
         3 . The method according to  claim 2 , further comprising: allocating a part of a remaining portion of the bandwidth of the proposed route to another bandwidth of the plurality of needed bandwidths and assigning traffic of the corresponding service class to the proposed route when the remaining portion of the bandwidth of the proposed route is greater than or equal to the another bandwidth. 
     
     
         4 . The method according to  claim 3 , wherein the another bandwidth is the largest one of the remaining non-allocated bandwidths of the plurality of needed bandwidths that has a bandwidth less than or equal to the remaining portion of the bandwidth of the proposed route. 
     
     
         5 . The method according to  claim 2 , further comprising: allocating a part of a remaining portion of the bandwidth of a selected one of the proposed route and the at least one further route to another bandwidth of the plurality of needed bandwidths, and assigning traffic of the corresponding service class to the selected route. 
     
     
         6 . The method according to  claim 5 , wherein the another bandwidth is the largest one of the remaining non-allocated bandwidths of the plurality of needed bandwidths that has a bandwidth less than or equal to the remaining portion of the bandwidth of the selected route. 
     
     
         7 . The method according to  claim 2 , further comprising: successively allocating, in order of decreasing bandwidth for each non-allocated bandwidth of the plurality of needed bandwidths, a respective part of a remaining portion of the bandwidth of a selected one of the proposed route and the at least one further route to that bandwidth and assigning traffic of the corresponding service class to the selected route when the remaining portion of the bandwidth of the selected route is greater than or equal to that bandwidth. 
     
     
         8 . The method according to  claim 1 , further comprising providing available bandwidths and links prior to said generating of a proposed route, and including:
 determining, for each of a plurality of links of the network, the respective ones of the plurality of existing paths that traverse that link;   determining the reserved bandwidth on each of the plurality of links, the determination being based on the respective ones of the plurality of existing paths that traverse that link;   determining the maximum bandwidth on each of the plurality of links; and   determining the available bandwidth on each of the plurality of links, the determination being based on the maximum bandwidth and the reserved bandwidth of that link.   
     
     
         9 . The method according to  claim 8 , wherein the plurality of existing paths carry traffic of a plurality of service classes, the actions of determining the reserved bandwidth, determining the maximum bandwidth, and determining the available bandwidth are carried out for each of the plurality of classes to determine the reserved bandwidth associated with that class on each of the plurality of links, the maximum bandwidth associated with that class on each of the plurality of links, and the available bandwidth associated with that class on each of the plurality of links. 
     
     
         10 . The method according to  claim 1 , wherein the network includes a multi-protocol label switching (MPLS) network, and the plurality of existing paths are label-switched paths (LSPs). 
     
     
         11 . The method according to  claim 1 , wherein the proposed route is the route having the maximum available bandwidth. 
     
     
         12 . An apparatus comprising:
 a replacement unit operable to:   determine a total bandwidth needed to carry traffic of a plurality of existing paths of a network, the determining carried out when the plurality of existing paths includes at least one failed link and the determining including determining a plurality of needed bandwidths;   generate a proposed route from available links in the network;   successively allocate in order of decreasing bandwidth for each non-allocated bandwidth of the plurality of needed bandwidths a respective part of a remaining portion of the bandwidth of the proposed route to the needed bandwidth and assigning corresponding traffic to the proposed route when the bandwidth of the proposed route is greater than or equal to the needed bandwidth; and   generate at least one further route when the bandwidth of the proposed route is less than the needed bandwidth and divide the needed bandwidth among the proposed route and the at least one further route such that a minimum number of further routes are generated.