Optimal routing with multiple traffic matrices tradeoff between average and worst case performance

Chun Zhang, Zihui Ge, Jim Kurose, Yong Liu, Don Towsley

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Abstract

In this paper, we consider the problem of finding an "efficient" and "robust" set of routes in the face of changing/uncertain traffic. The changes/uncertainty in exogenous traffic are characterized by multiple traffic matrices. Our goal is to find a set of routes that results in good average case performance over the set of traffic matrices, while avoiding bad worst case performance for any single traffic matrix. With multiple traffic matrices, previous work aims solely to optimize the average case performance [1], or the worst case performance [2]. For a given set of traffic matrices, different sets of routes offer a different tradeoff between the average case and the worst case performance. In this paper, we quantify the performance of a routing configuration at both network level and link level. We propose a simple metric - a weighted sum of the average case and the worst case performance - to control the tradeoff between these two considerations. Despite of its simple form, this metric is very effective. We prove that optimizing routing using this metric has desirable properties, such as the average case performance being a decreasing, convex and differentiable function to the worst case performance. By extending previous work [1][3], we derive methods to find the optimal routes with respect to the proposed metric for two classes of intradomain routing protocols: MPLS and OSPF/IS-IS. We evaluate our approach with data collected from an operational tier-1 ISP. For MPLS, we find that there exists significant tradeoff (e.g., 15% - 23% difference) between optimizing solely on the average case performance and solely on the worst case performance. Our approach can identify solutions that can dramatically improve the worst case performance (13% - 15%j while only slightly sacrificing the average case performance (2.2% -3%), in comparison to that by optimizing solely on the average case performance. For OSPF/IS-IS, we still find a significant difference between the two optimization objectives, however, a fine-grained tradeoff is difficult to achieve due to the limited control that OSPF/IS-IS provide.

Original languageEnglish (US)
Title of host publicationProceedings - 13TH IEEE International Conference on Network Protocols, ICNP 2005
Pages215-224
Number of pages10
DOIs
StatePublished - 2005
Event13TH IEEE International Conference on Network Protocols, ICNP 2005 - Boston, MA, United States
Duration: Nov 6 2005Nov 9 2005

Publication series

NameProceedings - International Conference on Network Protocols, ICNP
Volume2005
ISSN (Print)1092-1648

Other

Other13TH IEEE International Conference on Network Protocols, ICNP 2005
CountryUnited States
CityBoston, MA
Period11/6/0511/9/05

ASJC Scopus subject areas

  • Engineering(all)

Fingerprint Dive into the research topics of 'Optimal routing with multiple traffic matrices tradeoff between average and worst case performance'. Together they form a unique fingerprint.

Cite this