Link-state routing with hop-by-hop forwarding can achieve optimal traffic engineering

Dahai Xu, Mung Chiang, Jennifer L. Rexford

Research output: Chapter in Book/Report/Conference proceedingConference contribution

36 Scopus citations

Abstract

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 [1], 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.

Original languageEnglish (US)
Title of host publicationINFOCOM 2008
Subtitle of host publication27th IEEE Communications Society Conference on Computer Communications
Pages1139-1147
Number of pages9
DOIs
StatePublished - 2008
EventINFOCOM 2008: 27th IEEE Communications Society Conference on Computer Communications - Phoenix, AZ, United States
Duration: Apr 13 2008Apr 18 2008

Publication series

NameProceedings - IEEE INFOCOM
ISSN (Print)0743-166X

Other

OtherINFOCOM 2008: 27th IEEE Communications Society Conference on Computer Communications
CountryUnited States
CityPhoenix, AZ
Period4/13/084/18/08

All Science Journal Classification (ASJC) codes

  • Computer Science(all)
  • Electrical and Electronic Engineering

Keywords

  • Interior gateway protocol
  • Network entropy maximization
  • OSPF
  • Optimization
  • Routing
  • Traffic engineering

Fingerprint Dive into the research topics of 'Link-state routing with hop-by-hop forwarding can achieve optimal traffic engineering'. Together they form a unique fingerprint.

  • Cite this

    Xu, D., Chiang, M., & Rexford, J. L. (2008). Link-state routing with hop-by-hop forwarding can achieve optimal traffic engineering. In INFOCOM 2008: 27th IEEE Communications Society Conference on Computer Communications (pp. 1139-1147). [4509689] (Proceedings - IEEE INFOCOM). https://doi.org/10.1109/INFOCOM.2007.94