News Archives

  • UNM
  • >Home
  • >News
  • >2007
  • >February
  • >[Colloquium] Link-State Routing Can Achieve Optimal Traffic Engineering From Entropy to IP

[Colloquium] Link-State Routing Can Achieve Optimal Traffic Engineering From Entropy to IP

February 8, 2007

Watch Colloquium: 

AVI file (312 MB)
Quicktime (121 MB)


  • Date: Thursday, February 8th, 2007 
  • Time: 11 am — 12:15 pm 
  • Place: ECE 118

Dahai Xu Electrical
Engineering Department Princeton University

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.

Bio: Dr. Dahai Xu is currently a Postdoctoral Research Associate in the Department of Electrical Engineering at Princeton University. He received his Ph.D. degree in Computer Science and Engineering from University at Buffalo in 2005. His research interests include survivability and restoration in IP/MPLS, optical networks, network design and protocol development for next generation Internet and performance evaluation (modeling, simulation and measurements). More information can be found at http://www.princeton.edu/~dahaixu/.