Link-state routing with hop-by-hop forwarding is widely used in the Internet today. The current versions of these protocols, like OSPF, split traffic evenly over shortest paths based on link weights. However, optimizing the link weights for OSPF to the offered traffic is an NP-hard problem, and even the best setting of the weights can deviate significantly from an optimal distribution of the traffic. In this paper, we propose a new link-state routing protocol, PEFT, that splits traffic over multiple paths with an exponential penalty on longer paths. Unlike its predecessor, DEFT, our new protocol provably achieves optimal traffic engineering while retaining the simplicity of hop-by-hop forwarding. A gain of 15% in capacity utilization over OSPF is demonstrated using the Abilene topology and traffic traces. The new protocol also leads to significant reduction in the time needed to compute the best link weights. Both the protocol and the computational methods are developed in a new conceptual framework, called Network Entropy Maximization, where a specific notion of entropy is used to identify the traffic distributions that are not only optimal but also realizable by link-state routing.

Network operators control the flow of traffic through their networks by adapting the configuration of the underlying routing protocols. For example, they tune the integer link weights that interior gateway protocols like OSPF and IS-IS use to compute shortest paths. The resulting optimization problem is difficult because these protocols split traffic evenly along shortest paths, with no ability to adjust the splitting percentages or direct traffic on other paths. We propose an extension to these protocols, called Distributed Exponentially-weighted Flow SpliTting (DEFT), where the routers can direct traffic on non-shortest paths, with an exponential penalty on longer paths. DEFT leads not only to a simpler optimization problem, but also to weight settings that provably perform always better than OSPF and IS-IS. In the optimization problem we present, both link weights and flows of traffic are integrated as optimization variables into the formulation and jointly solved by a two-stage iterative method. DEFT retains the simplicity of having routers compute paths based on configurable link weights, while approaching the performance of more complex routing protocols that can split traffic arbitrarily over any paths.

For the topology on the right, which has 5 nodes and 8 bi-directed edges (for a total of 16 links), the link capacities are all 5 units, and the traffic demand between each node pair is randomly chosen from [0, 5] units. The objective is to minimize the sum of link cost (as defined by Bernard Fortz and Mikkel Thorup).
Topology and traffic demand (AMPL)

With economic constraints and limited routing capability, the structure of an access network is typically a ``fat tree'', where the terminal has to relay the traffic from another terminal of the same or higher level. New graph theory problems naturally arise from such features of access network models, different from those targeted towards survivable backbone (mesh) networks. We model the important problem of provisioning survivability to an existing single-level fat tree through two graph theory problem formulations: the Terminal Backup problem and the Simplex Cover problem, which we show to be equivalent. We then develop two polynomial-time approaches, indirect and direct, for the Simplex Cover problem. The indirect approach of solving the matching version of Simplex Cover is convenient in proving polynomial-time solvability though it is prohibitively slow in practice. In contrast, leveraging the special properties of Simplex Cover itself, we demonstrate that the direct approach can solve the Simplex Cover problem very efficiently even for large networks. Extensive numerical results of applying our algorithms are also reported for designing survivable access networks over different types of topologies.

Service availability is one of the most closely scrutinized metrics in offering network services. The network vendor can earn more revenue from the customers by guaranteeing higher service availability at the cost of higher operational expense. It is important to cost-effectively provision a managed and differentiated network with various service availability guarantees under a unified platform. We establish the framework of provisioning elastic service availability through network utility maximization and propose an optimal and distributed solution using differentiated failure recovery schemes.

Several observations are made from this investigation. For example, indiscriminately provisioning service availabilities for different kinds of users within one network leads to noteworthy sub-optimality in terms of maximizing network utility. In addition, provisioning high service availability exclusively for critical users/applications leads to significant waste in bandwidth resource.

Shared Risk Link Group (SRLG) has been widely recognized as an important concept in survivable optical networks and a similar concept is also applicable to other networking techniques with different physical and virtual topologies (e.g. overlay networks). In networks with SRLGs, ILP based approaches are not feasible for large networks while a simple heuristic may run into traps up to 30% of the time (i.e. fail to find an SRLG-disjoint path pair when it exists). As an alternative to K shortest paths (KSP) based heuristic, we propose an innovative trap avoidance heuristic that requires much less running time than the KSP (and ILP) and yet can effectively avoid almost all the avoidable traps as an ILP based approach. We also propose an efficient shared SRLG protection scheme based on the heuristic that can achieve a bandwidth efficiency that is nearly as high as other schemes based on ILP or KSP.

Most existing failure recovery approaches invariably make tradeoffs between bandwidth efficiency and recovery speed. In this work, We propose novel shared segment protection algorithms which make little or no compromise between high bandwidth efficiency and quick recovery. We develop an elegant link-labeling scheme that facilitated the formulation of the problem using Integer Linear Program (ILP) model to determine an optimal set of segments to protect a given active path. We also design a fast heuristic algorithm based on dynamic programming to obtain a near-optimal set of segments.

Many emerging applications including nation-wide collaborative science and engineering projects require that reliable, high-bandwidth connections be dynamically set up and released between large computing resources. To meet the requirements of these emerging applications in an economical way, a network must be able to quickly provision bandwidth-guaranteed survivable connections. The major challenges are how to allocate minimal amount of spare resources using fast algorithms, and in case a failure occurs, be able to quickly recover from it. We design a novel framework called Distributed Partial Information Management (or DPIM) to address: (1) how much partial information about the existing active (working) and backup paths is maintained and exchanged; (2) how to distributively allocate minimal backup bandwidth (and de-allocate maximal backup bandwidth) via distributed signaling; (3) how to update and subsequently exchange the partial information, and (4) how to develop a so-called Potential Backup Cost function when selecting an active path in the first phase, in order to take into consideration the backup bandwidth needed by the corresponding backup path which is yet to be chosen in the second phase.