Skip to main content

Link-State Routing With Hop-by-Hop Forwarding Can Achieve Optimal Traffic Engineering

Author(s): Xu, Dahai; Chiang, Mung; Rexford, Jennifer

To refer to this page use:
Abstract: This paper settles an open question with a positive answer: Optimal traffic engineering (or optimal multicommodity flow) can be realized using just link-state routing protocols with hop-by-hop forwarding. Today's typical versions of these protocols, Open Shortest Path First (OSPF) and Intermediate System-Intermediate System (IS-IS), split traffic evenly over shortest paths based on link weights. However, optimizing the link weights for OSPF/IS-IS to the offered traffic is a well-known 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. The new protocol also leads to a significant reduction in the time needed to compute the best link weights. Both the protocol and the computational methods are developed in a conceptual framework, called Network Entropy Maximization, that is used to identify the traffic distributions that are not only optimal, but also realizable by link-state routing.
Publication Date: 2011
Citation: Xu, Dahai, Mung Chiang, and Jennifer Rexford. "Link-state routing with hop-by-hop forwarding can achieve optimal traffic engineering." IEEE/ACM Transactions on Networking 19, no. 6 (2011): 1717-1730. doi:10.1109/TNET.2011.2134866
DOI: 10.1109/TNET.2011.2134866
ISSN: 1063-6692
EISSN: 1558-2566
Pages: 1717 - 1730
Type of Material: Journal Article
Journal/Proceeding Title: IEEE/ACM Transactions on Networking
Version: Author's manuscript

Items in OAR@Princeton are protected by copyright, with all rights reserved, unless otherwise indicated.