Survey of Distributed Multipath Routing Protocols for Traffic Management
---
paper_title: An overview of routing optimization for internet traffic engineering

paper_content:

Traffic engineering is an important mechanism for Internet network providers seeking to optimize network performance and traffic delivery. Routing optimization plays a key role in traffic engineering, finding efficient routes so as to achieve the desired network performance. In this survey we review Internet traffic engineering from the perspective of routing optimization. A taxonomy of routing algorithms in the literature is provided, dating from the advent of the TE concept in the late 1990s. We classify the algorithms into multiple dimensions: unicast/multicast, intra-/inter- domain, IP-/MPLS-based and offline/online TE schemes. In addition, we investigate some important traffic engineering issues, including robustness, TE interactions, and interoperability with overlay selfish routing. In addition to a review of existing solutions, we also point out some challenges in TE operation and important issues that are worthy of investigation in future research activities.
---
paper_title: Rethinking internet traffic management: from multiple decompositions to a practical protocol

paper_content:

In the Internet today, traffic management spans congestion control (at end hosts), routing protocols (on routers), and traffic engineering (by network operators). Historically, this division of functionality evolved organically. In this paper, we perform a top-down redesign of traffic management using recent innovations in optimization theory. First, we propose an objective function that captures the goals of end users and network operators. Using all known optimization decomposition techniques, we generate four distributed algorithms that divide traffic over multiple paths based on feedback from the network links. Combining the best features of the algorithms, we construct TRUMP: a traffic management protocol that is distributed, adaptive, robust, flexible and easy to manage. Further, TRUMP can operate based on implicit feedback about packet loss and delay. We show that using optimization decompositions as a foundation, simulations as a building block, and human intuition as a guide can be a principled approach to protocol design.
---
paper_title: Don't optimize existing protocols, design optimizable protocols

paper_content:

As networks grow in size and complexity, network management has become an increasingly challenging task. Many protocols have tunable parameters, and optimization is the process of setting these parameters to optimize an objective. In recent years, optimization techniques have been widely applied to network management problems, albeit with mixed success. Realizing that optimization problems in network management are induced by assumptions adopted in protocol design, we argue that instead of optimizing existing protocols, protocols should be designed with optimization in mind from the beginning. Using examples from our past research on traffic management, we present principles that guide how changes to existing protocols and architectures can lead to optimizable protocols. We also discuss the trade-offs between making network optimization easier and the overhead these changes impose.
---
paper_title: LBMP: A Logarithm-Barrier-Based Multipath Protocol for Internet Traffic Management

paper_content:

Traffic management is the adaptation of source rates and routing to efficiently utilize network resources. Recently, the complicated interactions between different Internet traffic management modules have been elegantly modeled by distributed primal-dual utility maximization, which sheds new light for developing effective management protocols. For single-path routing with given routes, the dual is a strictly concave network optimization problem. Unfortunately, the general form of multipath utility optimization is not strictly concave, making its solution quite unstable. Decomposition-based techniques like TRaffic-management Using Multipath Protocol (TRUMP) alleviates the instability, but their convergence is not guaranteed, nor is their optimality. They are also inflexible in differentiating the control at different links. In this paper, we address the above issues through a novel logarithm-barrier-based approach. Our approach jointly considers user utility and routing/congestion control. It translates the multipath utility maximization into a sequence of unconstrained optimization problems, with infinite logarithm barriers being deployed at the constraint boundary. We demonstrate that setting up barriers is much simpler than choosing traditional cost functions and, more importantly, it makes optimal solution achievable. We further demonstrate a distributed implementation, together with the design of a practical Logarithm Barrier-based-Multipath Protocol (LBMP). We evaluate the performance of LBMP through both numerical analysis and packet-level simulations. The results show that LBMP achieves high throughput and fast convergence over diverse representative network topologies. Such performance is comparable to TRUMP, and is often better. Moreover, LBMP is flexible in differentiating the control at different links, and its optimality and convergence are theoretically guaranteed.
---
paper_title: Towards Robust Multi-Layer Traffic Engineering: Optimization of Congestion Control and Routing

paper_content:

In the Internet today, traffic engineering is performed assuming that the offered traffic is inelastic. In reality, end hosts adapt their sending rates to network congestion, and network operators adapt the routing to the measured traffic. This raises the question of whether the joint system of congestion control (transport layer) and routing (network layer) is stable and optimal. Using the established optimization models for TCP and traffic engineering as a basis, we find the joint system can be stabilized and often maximizes aggregate user utility. We prove that both stability and optimality of the joint system can be guaranteed for sufficiently elastic traffic simply by tuning the cost function used for traffic engineering. Then, we present a new algorithm that adapts on a smaller timescale to changes in traffic distribution and is more robust to large traffic bursts. Uniting the network and transport layers in a multi-layer approach, this algorithm, distributed adaptive traffic engineering (DATE), jointly optimizes the goals of end users and network operators and reacts quickly to avoid bottlenecks. Simulations demonstrate that DATE converges quickly
---
paper_title: Walking the tightrope: responsive yet stable traffic engineering

paper_content:

Current intra-domain Traffic Engineering (TE) relies on offline methods, which use long term average traffic demands. It cannot react to realtime traffic changes caused by BGP reroutes, diurnal traffic variations, attacks, or flash crowds. Further, current TE deals with network failures by pre-computing alternative routings for a limited set of failures. It may fail to prevent congestion when unanticipated or combination failures occur, even though the network has enough capacity to handle the failure.This paper presents TeXCP, an online distributed TE protocol that balances load in realtime, responding to actual traffic demands and failures. TeXCP uses multiple paths to deliver demands from an ingress to an egress router, adaptively moving traffic from over-utilized to under-utilized paths. These adaptations are carefully designed such that, though done independently by each edge router based on local information, they balance load in the whole network without oscillations. We model TeXCP, prove the stability of the model, and show that it is easy to implement. Our extensive simulations show that, for the same traffic demands, a network using TeXCP supports the same utilization and failure resilience as a network that uses traditional offline TE, but with half or third the capacity.
---
paper_title: Link-State Routing with Hop-by-Hop Forwarding Can Achieve Optimal Traffic Engineering

paper_content:

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, which is used to identify the traffic distributions that are not only optimal but also realizable by link-state routing.
---
paper_title: DEFT: Distributed Exponentially-Weighted Flow Splitting

paper_content:

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 ISIS use to compute shortest paths. The resulting optimization problem -to find the best link weights for a given topology and traffic matrix -is computationally intractable even for the simplest objective functions, forcing the use of local-search techniques. The optimization problem is difficult in part because these protocols split traffic evenly along shortest paths, with no ability to adjust the splitting percentages or direct traffic on other paths. In this paper, 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 an easier-to-solve optimization problem, but also to weight settings that provably perform no worse than OSPF and IS-IS. Furthermore, in our optimization problem, both link weights and flows of traffic are integrated as optimization variables into the formulation and jointly solved by a two-stage iterative method. Our novel formulation leads to a much more efficient way to identify good link weights than the local-search heuristics used for OSPF and IS-IS today. 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.
---
paper_title: Towards Robust Multi-Layer Traffic Engineering: Optimization of Congestion Control and Routing

paper_content:

In the Internet today, traffic engineering is performed assuming that the offered traffic is inelastic. In reality, end hosts adapt their sending rates to network congestion, and network operators adapt the routing to the measured traffic. This raises the question of whether the joint system of congestion control (transport layer) and routing (network layer) is stable and optimal. Using the established optimization models for TCP and traffic engineering as a basis, we find the joint system can be stabilized and often maximizes aggregate user utility. We prove that both stability and optimality of the joint system can be guaranteed for sufficiently elastic traffic simply by tuning the cost function used for traffic engineering. Then, we present a new algorithm that adapts on a smaller timescale to changes in traffic distribution and is more robust to large traffic bursts. Uniting the network and transport layers in a multi-layer approach, this algorithm, distributed adaptive traffic engineering (DATE), jointly optimizes the goals of end users and network operators and reacts quickly to avoid bottlenecks. Simulations demonstrate that DATE converges quickly
---
paper_title: Link-State Routing with Hop-by-Hop Forwarding Can Achieve Optimal Traffic Engineering

paper_content:

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, which is used to identify the traffic distributions that are not only optimal but also realizable by link-state routing.
---
paper_title: Don't optimize existing protocols, design optimizable protocols

paper_content:

As networks grow in size and complexity, network management has become an increasingly challenging task. Many protocols have tunable parameters, and optimization is the process of setting these parameters to optimize an objective. In recent years, optimization techniques have been widely applied to network management problems, albeit with mixed success. Realizing that optimization problems in network management are induced by assumptions adopted in protocol design, we argue that instead of optimizing existing protocols, protocols should be designed with optimization in mind from the beginning. Using examples from our past research on traffic management, we present principles that guide how changes to existing protocols and architectures can lead to optimizable protocols. We also discuss the trade-offs between making network optimization easier and the overhead these changes impose.
---

Title: Survey of Distributed Multipath Routing Protocols for Traffic Management

Section 1: INTRODUCTION
Description 1: Provide an overview of traffic management in networks, including the roles of users, routers, and operators, and introduce the concept of distributed traffic management protocols.

Section 2: TRAFFIC MANAGEMENT WITH DISTRIBUTED MULTIPATH ROUTING
Description 2: Explain how traffic management can be handled using distributed multipath routing protocols and detail the necessary requirements for implementation in today's internet.

Section 3: MATE: MPLS Adaptive Traffic Engineering
Description 3: Describe the MPLS Adaptive Traffic Engineering (MATE) protocol, focusing on its measurement and analysis functions.

Section 4: Limitations of MATE
Description 4: Discuss the limitations of the MATE protocol, including its assumptions and areas where it may not perform well.

Section 5: TeXCP
Description 5: Outline the TeXCP protocol, an online distributed traffic engineering protocol, including its components and how it balances network load in real-time.

Section 6: Limitations of DEFT
Description 6: Highlight the limitations of the DEFT protocol and potential challenges for optimization and implementation.

Section 7: The TRUMP Algorithm
Description 7: Provide an overview of the TRUMP algorithm, a combination of four distributed algorithms for traffic management.

Section 8: Limitations of TRUMP algorithm
Description 8: Discuss the limitations and potential drawbacks of the TRUMP algorithm in traffic management scenarios.

Section 9: RELATED WORK
Description 9: Summarize related work in the field of traffic management, referencing how optimization theory has been applied to improve existing protocols and develop new ones.

Section 10: CONCLUSION
Description 10: Conclude by summarizing the presented algorithms and discussing ongoing and future work in developing new optimization-based traffic management protocols.