Dynamic traffic rearrangement and restoration for MPLS networks with differentiated services capabilities
View Patent ↗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.
1. A method of providing at least one substitute path in place of a plurality of existing paths of a network to reallocate traffic carried by the plurality of existing paths, said method comprising:
determining total bandwidth needed to carry the traffic of the plurality of existing paths wherein the plurality of existing paths carry traffic of a plurality of service classes, said determining step includes determining a plurality of needed bandwidths corresponding to the plurality of service classes;
providing available bandwidths and links and generating a proposed route from available links in the network;
wherein the providing of available bandwidth and links comprises:
determining, for each of a plurality of links of the network, a respective ones of the plurality of existing paths that traverse that link;
determining a reserved bandwidth on each of the plurality of links, the determining of the reserved bandwidth being based on the respective ones of the plurality of existing paths that traverse that link;
determining a maximum bandwidth on each of the plurality of links; and
determining an available bandwidth on each of the plurality of links, the determining of the available bandwidth being based on the maximum bandwidth and the reserved bandwidth of that link; and
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 at least one of the plurality of needed bandwidths and assigning the traffic of its corresponding class to the proposed route when the bandwidth of the proposed route is greater than or equal to the needed bandwidth;
wherein the at least one substitute path comprises a plurality of replacement label-switched paths (LSPs) in a multi-protocol label switching (MPLS) network, the plurality of existing paths comprises a plurality of failed LSPs in the MPLS network, the plurality of failed LSPs were intended to carry traffic from an ingress point in the MPLS network to an egress point in the MPLS network, the MPLS network includes the plurality of links and is capable of carrying traffic for each of a plurality of differentiated services (diffserv) classes, and each of the plurality of links is configured to carry traffic for at least one of the plurality of diffserv classes at an associated bandwidth;
said determining the total bandwidth needed to carry the traffic of the plurality of existing paths includes:
providing a list of available bandwidths and links in the MPLS network, each element of the list including a respective one of the plurality of links and the available bandwidths for each of the plurality of diffserv classes carried on that link, and
providing a list of desired bandwidths, each element of the list including a respective one of the plurality of diffserv classes and an associated bandwidth needed to carry the traffic of that diffserv class, the elements of the list being arranged in order of decreasing bandwidth;
said generating the proposed route from available links in the network includes:
designating the diffserv class corresponding to a current first element in the list of desired bandwidths to be a current diffserv class, designating the bandwidth associated with the current first element to be a current desired bandwidth, and removing the current first element from the list of desired bandwidths such that each of the remaining elements of the list of desired bandwidths advance one position in the list, and
generating, from the list of available bandwidths and links, a current proposed route from the ingress point to the egress point, the bandwidth of the proposed route being a maximum bandwidth available for carrying the traffic of the current diffserv class;
said successively allocating the respective part of the remaining portion of the bandwidth of the proposed route includes:
determining whether the bandwidth of the proposed route is greater than or equal to the current desired bandwidth,
when the bandwidth of the proposed route is greater than or equal to the current desired bandwidth:
assigning the traffic of the current diffserv class to the proposed route, and allocating a portion of the bandwidth of the proposed route to the current desired bandwidth,
reducing the available bandwidths of the links traversed by the proposed route by the allocated bandwidth portion, and
determining whether a remaining portion of the bandwidth of the proposed route is able to carry traffic of at least another diffserv class from the list of desired bandwidths, and if so, assigning the traffic of the at least another diffserv class to the proposed route, allocating a further portion of the bandwidth of the proposed route to the bandwidth associated with to the at least another diffserv class, and removing at least one corresponding element from the list of desired bandwidths, and
when the bandwidth of the proposed route is less than the current desired bandwidth:
generating a plurality of further routes from the ingress point to the egress point from the list of available bandwidths and links, each further route being designated to carry a portion of the traffic of the current diffserv class, the current desired bandwidth being divided among the plurality of further routes such that a minimum number of further routes are generated,
reducing the available bandwidths of the links traversed by each of the plurality of further routes by the allocated bandwidth portion, and
determining whether any of the remaining portions of the bandwidths associated with each of the plurality of further routes is able to carry traffic of at least another diffserv class from the list of desired bandwidths, and if so, assigning the traffic of the at least another diffserv class to at least one of the plurality of further routes, allocating a further portion of the bandwidth of the at least one further route to the bandwidth associated with the at least another diffserv class, and removing at least one corresponding element from the list of desired bandwidths; and
said generating the proposed route from the available links in the network step and said successively allocating the respective part of the remaining portion of the bandwidth of the proposed route steps are repeated until all of the elements of the list of desired bandwidths are removed.
2. The method according to claim 1 , wherein said bandwidth of the proposed route is the largest non-allocated bandwidth of the plurality of needed bandwidths.
3. An apparatus for providing at least one substitute path in place of a plurality of existing paths of a network to reallocate traffic carried by the plurality of existing paths, said apparatus comprising a non-transitory computer-readable medium storing instructions for execution by a processor, which when executed by the processor, cause the processor to:
determining total bandwidth needed to carry the traffic of the plurality of existing paths wherein the plurality of existing paths carry traffic of a plurality of service classes, said determining step includes determining a plurality of needed bandwidths corresponding to the plurality of service classes;
providing available bandwidths and links and generating a proposed route from available links in the network;
wherein the providing of available bandwidth and links comprises:
determining, for each of a plurality of links of the network, a respective ones of the plurality of existing paths that traverse that link;
determining a reserved bandwidth on each of the plurality of links, the determining of the reserved bandwidth being based on the respective ones of the plurality of existing paths that traverse that link;
determining a maximum bandwidth on each of the plurality of links; and
determining an available bandwidth on each of the plurality of links, the determining of the available bandwidth being based on the maximum bandwidth and the reserved bandwidth of that link; and
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 at least one of the plurality of needed bandwidths and assigning the traffic of its corresponding class to the proposed route when the bandwidth of the proposed route is greater than or equal to the needed bandwidth;
wherein the at least one substitute path comprises a plurality of replacement label-switched paths (LSPs) in a multi-protocol label switching (MPLS) network, the plurality of existing paths comprises a plurality of failed LSPs in the MPLS network, the plurality of failed LSPs were intended to carry traffic from an ingress point in the MPLS network to an egress point in the MPLS network, the MPLS network includes the plurality of links and is capable of carrying traffic for each of a plurality of differentiated services (diffserv) classes, and each of the plurality of links is configured to carry traffic for at least one of the plurality of diffserv classes at an associated bandwidth;
said determining the total bandwidth needed to carry the traffic of the plurality of existing paths includes:
providing a list of available bandwidths and links in the MPLS network, each element of the list including a respective one of the plurality of links and the available bandwidths for each of the plurality of diffserv classes carried on that link, and
providing a list of desired bandwidths, each element of the list including a respective one of the plurality of diffserv classes and an associated bandwidth needed to carry the traffic of that diffserv class, the elements of the list being arranged in order of decreasing bandwidth;
said generating the proposed route from available links in the network includes:
designating the diffserv class corresponding to a current first element in the list of desired bandwidths to be a current diffserv class, designating the bandwidth associated with the current first element to be a current desired bandwidth, and removing the current first element from the list of desired bandwidths such that each of the remaining elements of the list of desired bandwidths advance one position in the list, and
generating, from the list of available bandwidths and links, a current proposed route from the ingress point to the egress point, the bandwidth of the proposed route being a maximum bandwidth available for carrying the traffic of the current diffserv class;
said successively allocating the respective part of the remaining portion of the bandwidth of the proposed route includes:
determining whether the bandwidth of the proposed route is greater than or equal to the current desired bandwidth,
when the bandwidth of the proposed route is greater than or equal to the current desired bandwidth:
assigning the traffic of the current diffserv class to the proposed route, and allocating a portion of the bandwidth of the proposed route to the current desired bandwidth,
reducing the available bandwidths of the links traversed by the proposed route by the allocated bandwidth portion, and
determining whether a remaining portion of the bandwidth of the proposed route is able to carry traffic of at least another diffserv class from the list of desired bandwidths, and if so, assigning the traffic of the at least another diffserv class to the proposed route, allocating a further portion of the bandwidth of the proposed route to the bandwidth associated with to the at least another diffserv class, and removing at least one corresponding element from the list of desired bandwidths, and
when the bandwidth of the proposed route is less than the current desired bandwidth:
generating a plurality of further routes from the ingress point to the egress point from the list of available bandwidths and links, each further route being designated to carry a portion of the traffic of the current diffserv class, the current desired bandwidth being divided among the plurality of further routes such that a minimum number of further routes are generated,
reducing the available bandwidths of the links traversed by each of the plurality of further routes by the allocated bandwidth portion, and
determining whether any of the remaining portions of the bandwidths associated with each of the plurality of further routes is able to carry traffic of at least another diffserv class from the list of desired bandwidths, and if so, assigning the traffic of the at least another diffserv class to at least one of the plurality of further routes, allocating a further portion of the bandwidth of the at least one further route to the bandwidth associated with the at least another diffserv class, and removing at least one corresponding element from the list of desired bandwidths; and
said generating the proposed route from the available links in the network step and said successively allocating the respective part of the remaining portion of the bandwidth of the proposed route steps are repeated until all of the elements of the list of desired bandwidths are removed.