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 restoring a network by providing at least one substitute path in place of a plurality of existing paths of a network carrying traffic of a plurality of service classes to reallocate the traffic carried by the plurality of existing paths, said method comprising:
(a) determining total bandwidth needed to carry the traffic of the plurality of existing paths and determining a plurality of needed bandwidths each corresponding to one of the plurality of service classes;
(b) providing a list of the plurality of needed bandwidths in decreasing bandwidth order;
(c) generating a proposed route from available links in the network;
(d) for a greatest non-allocated bandwidth of the plurality of needed bandwidths, if the greatest non-allocated bandwidth is less than or equal to the bandwidth of the proposed route, allocating a portion of the bandwidth of the proposed route to the greatest non-allocated bandwidth, assigning the traffic of the respective service class to the proposed route, removing the greatest non-allocated bandwidth from the list, and defining the next non-allocated bandwidth in the list as a current non-allocated bandwidth;
(e) determining whether the current non-allocated bandwidth is less than or equal to a remaining bandwidth of the proposed route;
(f) if the current non-allocated bandwidth is less than or equal to the remaining bandwidth of the proposed route, allocating a respective part of the remaining portion of the bandwidth of the proposed route to the current non-allocated bandwidth and assigning the traffic of the respective service class to the proposed route, removing the current non-allocated bandwidth from the list, and then if the current non-allocated bandwidth was not the last non-allocated bandwidth in the list remaining to be considered, defining the next non-allocated bandwidth as the current non-allocated bandwidth and returning to action (e);
(g) if the current non-allocated bandwidth is greater than the remaining bandwidth of the proposed route, and if the current non-allocated bandwidth was not the last non-allocated bandwidth in the list remaining to be considered, defining the next non-allocated bandwidth as the current non-allocated bandwidth and returning to action (e); and,
(h) when in action (g) the current non-allocated bandwidth was the last non-allocated bandwidth in the list remaining to be considered and the list includes non-allocated bandwidths, returning to action (c).
2. The method according to claim 1 , wherein each of the plurality of existing paths includes at least one failed link.
3. The method according to claim 1 , wherein the network includes a multi-protocol label switching (MPLS) network, and the plurality of existing paths and the plurality of substitute paths are each respective pluralities of label-switched paths (LSPs).
4. The method according to claim 1 , wherein the proposed route is the route having the maximum available bandwidth.
5. The method according to claim 1 , wherein:
when in action (d) the greatest non-allocated bandwidth is greater than the bandwidth of the proposed route, the proposed route is defined to be the current proposed route, and
the method further comprising:
(i) allocating as much of the bandwidth of the current proposed route to the non-allocated portion of the greatest non-allocated bandwidth as the current proposed route can accommodate; and
(j) if not all the greatest non-allocated bandwidth was assigned, generating a new proposed route, defining the new proposed route to be the current proposed route, and returning to action (i).
6. The method according to claim 5 , wherein:
once the greatest non-allocated bandwidth is fully assigned, the greatest non-allocated bandwidth is removed from the list, and
the method further comprising:
(k) selecting one of the proposed routes;
(l) defining the next non-allocated bandwidth in the list as the current non-allocated bandwidth;
(m) determining whether the current non-allocated bandwidth is less than or equal to the remaining bandwidth of the selected proposed route; and
(n) if the current non-allocated bandwidth is less than or equal to the remaining bandwidth of the selected proposed route, allocating a respective part of the remaining portion of the bandwidth of the selected proposed route to the current non-allocated bandwidth and assigning the traffic of the respective service class to the selected proposed route, removing the current non-allocated bandwidth from the list, and then if the current non-allocated bandwidth was not the last non-allocated bandwidth in the list remaining to be considered, defining the next non-allocated bandwidth as the current non-allocated bandwidth and returning to action (m).
7. The method according to claim 6 , further comprising:
(o) if the current non-allocated bandwidth is greater than the remaining bandwidth of the selected proposed route, and if the current non-allocated bandwidth was not the last non-allocated bandwidth in the list remaining to be considered, defining the next non-allocated bandwidth as the current non-allocated bandwidth and returning to action (m); and,
(p) when in action (o) the current non-allocated bandwidth was the last non-allocated bandwidth in the list remaining to be considered, the list includes non-allocated bandwidths, and not all proposed routes have been considered, selecting a proposed route not yet considered and returning to action (l).
8. The method according to claim 1 , further comprising providing available bandwidths and links prior to said generating of a proposed route, and including:
a first determining action to determine, for each of a plurality of links of the network, the respective ones of the plurality of existing paths that traverse each respective link;
a second determining action to determine the reserved bandwidth on each of the plurality of links, the second determination being based on the respective ones of the plurality of existing paths that traverse each respective link;
a third determining action to determine the maximum bandwidth on each respective link; and
a fourth determining action to determine the available bandwidth on each respective link, the fourth determination being based on the maximum bandwidth and the respective non-allocated bandwidth of each respective link.
9. The method according to claim 8 , wherein the plurality of existing paths carry traffic of a plurality of service classes, said first, second, third, and fourth determining actions are carried out for each of the plurality of classes to subsequently 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. An apparatus for providing at least one substitute path in place of a plurality of existing paths for a plurality of service classes of a network to reallocate the traffic carried by the plurality of existing paths, said apparatus comprising:
a replacement unit including software modules operating on a hardware platform configured to:
determine the total bandwidth needed to carry the traffic of the plurality of existing paths; and,
further determine a plurality of needed bandwidths each corresponding to one of the plurality of service classes; and,
execute a process comprising:
(a) providing a list of the plurality of needed bandwidths in decreasing bandwidth order;
(b) generating a proposed route from available links in the network;
(c) for a greatest non-allocated bandwidth of the plurality of needed bandwidths, if the greatest non-allocated bandwidth is less than or equal to the bandwidth of the proposed route, allocating a portion of the bandwidth of the proposed route to the greatest non-allocated bandwidth, assigning the traffic of the respective service class to the proposed route, removing the greatest non-allocated bandwidth from the list, and defining the next non-allocated bandwidth in the list as a current non-allocated bandwidth;
(d) determining whether the current non-allocated bandwidth is less than or equal to a remaining bandwidth of the proposed route;
(e) if the current non-allocated bandwidth is less than or equal to the remaining bandwidth of the proposed route, allocating a respective part of the remaining portion of the bandwidth of the proposed route to the current non-allocated bandwidth and assigning the traffic of the respective service class to the proposed route, removing the current non-allocated bandwidth from the list, and then if the current non-allocated bandwidth was not the last non-allocated bandwidth in the list remaining to be considered, defining the next non-allocated bandwidth as the current non-allocated bandwidth and returning to action (d);
(f) if the current non-allocated bandwidth is greater than the remaining bandwidth of the proposed route, and if the current non-allocated bandwidth was not the last non-allocated bandwidth in the list remaining to be considered, defining the next non-allocated bandwidth as the current non allocated bandwidth and returning to action (d); and,
(g) when in action (f) the current non-allocated bandwidth was the last non-allocated bandwidth in the list remaining to be considered and the list includes non-allocated bandwidths, returning to action (b).
11. An apparatus for providing at least one substitute path as in claim 10 , wherein each of the plurality of existing paths includes at least one failed link.
12. An apparatus for providing at least one substitute path as in claim 10 , wherein the network includes a multi-protocol label switching (MPLS) network, and the plurality of existing paths and the plurality of substitute paths are each respective pluralities of label-switched paths (LSPs).
13. An apparatus for providing at least one substitute path as in claim 10 , wherein the proposed route is the route having the maximum available bandwidth.