Link-State Routing Can Achieve Optimal Traffic Engineering
Abstract
In this talk, I will focus on Intra-domain traffic engineering where
network operators control the flow of traffic in their networks by
tuning the configuration of link-state routing protocols. We settle
a long-standing question with a positive answer: optimal traffic
engineering can be realized using just link-state routing protocols.
In conventional link-state protocols like OSPF and IS-IS, routers
compute shortest paths from link weights, splitting traffic evenly
when multiple shortest paths exist. Unfortunately, for these
protocols, computing the optimal link weights for a given traffic
matrix is an NP-hard problem. Even the best setting of the weights
can lead to traffic loads that deviate significantly from the ideal
distribution of the traffic. In this work, we show that splitting
traffic over multiple paths as an exponential function of path
length can achieve optimal traffic engineering. We also present a
polynomial-time algorithm for computing the optimal link weights,
which in practice is also much more efficient than the local-search
heuristics used today. In addition, we show how to apply the
algorithm to robust traffic engineering, where one set of link
weights must perform well for multiple traffic matrices or failure
scenarios. These results are based on our new Network Entropy
Maximization framework for routing-protocol design, which parallels
the role of Network Utility Maximization for congestion control.
<