Efficient and robust routing of potentially-variable traffic with local restoration against link failures

摘要

In one embodiment, a method for supporting recovery from failure of a link in a network of nodes interconnected by links. An intermediate node between an ingress point and an egress point of the network is selected to minimize the sum of (i) a capacity constraint between the ingress point and the intermediate node and (ii) a capacity constraint between the intermediate node and the egress point. The selection identifies two path structures, each comprising a primary path and one or more link backup detours protecting each link on the primary path, with a first path structure between the ingress point and the intermediate node, and a second path structure between the intermediate node and the egress point. To maximize network throughput, packets are routed in two phases, first to the intermediate node via the first path structure in predetermined proportions, and then from the intermediate node to the final destination via the second path structure.