Thumbnail
Access Restriction
Open

Author Xu, Dahai ♦ Chiang, Mung ♦ Rexford, Jennifer
Source CiteSeerX
Content type Text
File Format PDF
Subject Domain (in DDC) Computer science, information & general works ♦ Data processing & computer science
Subject Keyword Hop-by-hop Forwarding ♦ Link Weight ♦ Achieve Optimal Traffic Engineering ♦ New Protocol ♦ Optimal Traffic Engineering ♦ Computational Method ♦ Optimal Multi-commodity Flow ♦ Significant Reduction ♦ Multiple Path ♦ Link-state Routing Protocol ♦ Open Question ♦ New Link-state Routing Protocol ♦ Traffic Distribution ♦ Optimal Distribution ♦ Exponential Penalty ♦ Typical Version ♦ Split Traffic ♦ Link-state Routing ♦ Well-known Np-hard Problem ♦ Ospf Is-is ♦ Network Entropy Maximization ♦ Positive Answer ♦ Conceptual Framework
Abstract Abstract—This paper settles an open question with a positive answer: optimal traffic engineering (or optimal multi-commodity flow) can be realized using just link-state routing protocols with hop-by-hop forwarding. Today’s typical versions of these protocols, OSPF and 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 [1], 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, which is used to identify the traffic distributions that are not only optimal but also realizable by link-state routing.
Educational Role Student ♦ Teacher
Age Range above 22 year
Educational Use Research
Education Level UG and PG ♦ Career/Technical Study