TY - GEN
T1 - DEFT
T2 - IEEE INFOCOM 2007: 26th IEEE International Conference on Computer Communications
AU - Xu, Dahai
AU - Chiang, Mung
AU - Rexford, Jennifer L.
N1 - Copyright:
Copyright 2008 Elsevier B.V., All rights reserved.
PY - 2007
Y1 - 2007
N2 - Network operators control the flow of traffic through their networks by adapting the configuration of the underlying routing protocols. For example, they tune the integer link weights that interior gateway protocols like OSPF and IS-IS use to compute shortest paths. The resulting optimization problem - to find the best link weights for a given topology and traffic matrix-is computationally intractable even for the simplest objective functions, forcing the use of local-search techniques. The optimization problem is difficult in part because these protocols split traffic evenly along shortest paths, with no ability to adjust the splitting percentages or direct traffic on other paths. In this paper, we propose an extension to these protocols, called Distributed Exponentially-weighted Flow SpliTting (DEFT), where the routers can direct traffic on non-shortest paths, with an exponential penalty on longer paths. DEFT leads not only to an easier-to-solve optimization problem, but also to weight settings that provably perform no worse than OSPF and IS-IS. Furthermore, in our optimization problem, both link weights and flows of traffic are integrated as optimization variables into the formulation and jointly solved by a twostage iterative method. Our novel formulation leads to a much more efficient way to identify good link weights than the local-search heuristics used for OSPF and IS-IS today. DEFT retains the simplicity of having routers compute paths based on configurable link weights, while approaching the performance of more complex routing protocols that can split traffic arbitrarily over any paths.
AB - Network operators control the flow of traffic through their networks by adapting the configuration of the underlying routing protocols. For example, they tune the integer link weights that interior gateway protocols like OSPF and IS-IS use to compute shortest paths. The resulting optimization problem - to find the best link weights for a given topology and traffic matrix-is computationally intractable even for the simplest objective functions, forcing the use of local-search techniques. The optimization problem is difficult in part because these protocols split traffic evenly along shortest paths, with no ability to adjust the splitting percentages or direct traffic on other paths. In this paper, we propose an extension to these protocols, called Distributed Exponentially-weighted Flow SpliTting (DEFT), where the routers can direct traffic on non-shortest paths, with an exponential penalty on longer paths. DEFT leads not only to an easier-to-solve optimization problem, but also to weight settings that provably perform no worse than OSPF and IS-IS. Furthermore, in our optimization problem, both link weights and flows of traffic are integrated as optimization variables into the formulation and jointly solved by a twostage iterative method. Our novel formulation leads to a much more efficient way to identify good link weights than the local-search heuristics used for OSPF and IS-IS today. DEFT retains the simplicity of having routers compute paths based on configurable link weights, while approaching the performance of more complex routing protocols that can split traffic arbitrarily over any paths.
KW - Interior gateway protocol
KW - Mathematical programming
KW - Network optimization
KW - OSPF
KW - Routing
KW - Traffic engineering
UR - http://www.scopus.com/inward/record.url?scp=34548305304&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=34548305304&partnerID=8YFLogxK
U2 - 10.1109/INFCOM.2007.17
DO - 10.1109/INFCOM.2007.17
M3 - Conference contribution
AN - SCOPUS:34548305304
SN - 1424410479
SN - 9781424410477
T3 - Proceedings - IEEE INFOCOM
SP - 71
EP - 79
BT - Proceedings - IEEE INFOCOM 2007
Y2 - 6 May 2007 through 12 May 2007
ER -