TY - JOUR
T1 - Link-state routing with hop-by-hop forwarding can achieve optimal traffic engineering
AU - Xu, Dahai
AU - Chiang, Mung
AU - Rexford, Jennifer L.
N1 - Funding Information:
Manuscript received April 12, 2010; revised January 04, 2011; accepted March 19, 2011; approved by IEEE/ACM TRANSACTIONS ON NETWORKING Editor P. Van Mieghem. Date of publication April 07, 2011; date of current version December 16, 2011. This work was supported in part by DARPA W911NF-07-1-0057, ONR YIP N00014-07-1-0864, AFOSR FA9550-06-1-0297, and NSF CNS-0519880 and CNS 0720570. A preliminary short version of this paper was presented under the same title in the Proceedings of the IEEE Conference on Computer Communications (INFOCOM), Phoenix, AZ, April 13–19, 2008.
PY - 2011/12
Y1 - 2011/12
N2 - 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.
AB - 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.
KW - Interior gateway protocol
KW - Open Shortest Path First (OSPF)
KW - network entropy maximization
KW - optimization
KW - routing
KW - traffic engineering
UR - http://www.scopus.com/inward/record.url?scp=84655169959&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=84655169959&partnerID=8YFLogxK
U2 - 10.1109/TNET.2011.2134866
DO - 10.1109/TNET.2011.2134866
M3 - Article
AN - SCOPUS:84655169959
SN - 1063-6692
VL - 19
SP - 1717
EP - 1730
JO - IEEE/ACM Transactions on Networking
JF - IEEE/ACM Transactions on Networking
IS - 6
M1 - 5743044
ER -