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

Dahai Xu, Mung Chiang, Jennifer L. Rexford

Research output: Contribution to journalArticle

78 Scopus citations

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.

Original languageEnglish (US)
Article number5743044
Pages (from-to)1717-1730
Number of pages14
JournalIEEE/ACM Transactions on Networking
Volume19
Issue number6
DOIs
StatePublished - Dec 1 2011

All Science Journal Classification (ASJC) codes

  • Software
  • Computer Science Applications
  • Computer Networks and Communications
  • Electrical and Electronic Engineering

Keywords

  • Interior gateway protocol
  • Open Shortest Path First (OSPF)
  • network entropy maximization
  • 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