DocumentCode :
3436410
Title :
On the performance of averaged optimal routing
Author :
Michael, Nithin ; Tang, Ao ; Suh, G. Edward
Author_Institution :
Sch. of Electr. & Comput. Eng., Cornell Univ., Ithaca, NY, USA
fYear :
2012
fDate :
21-23 March 2012
Firstpage :
1
Lastpage :
6
Abstract :
Traffic uncertainty makes designing optimal routing protocols for many networks a difficult problem. A good way to capture uncertainty is via an uncertainty set - a collection of traffic matrices with associated probabilities of occurrence. Averaged optimal routing, where the performance metric is averaged over the potential traffic matrices, allows us to incorporate an uncertainty set into an optimization framework. We derive bounds on the performance of averaged optimal routing where the objective is to minimize maximum channel load, a commonly used metric. Furthermore, we provide examples of networks and uncertainty sets where the bounds are tight. These bounds can be used to quickly check whether averaged optimal routing is an effective routing protocol for a given network and uncertainty set. Numerical evaluations of the performance of the bounds for uncertainty sets drawn from random graphs are presented and some interesting trends are noted. Also, simulations performed on a cycle level on-chip network simulator demonstrate that averaged optimal routing outperforms general-purpose routing algorithms.
Keywords :
matrix algebra; optimisation; probability; routing protocols; telecommunication traffic; averaged optimal routing protocol; cycle level on-chip network simulator; maximum channel load minimization; numerical evaluation; optimization framework; probability; random graph presentation; traffic matrix collection; Internet; Linear programming; Measurement; Optimization; Routing; System-on-a-chip; Uncertainty;
fLanguage :
English
Publisher :
ieee
Conference_Titel :
Information Sciences and Systems (CISS), 2012 46th Annual Conference on
Conference_Location :
Princeton, NJ
Print_ISBN :
978-1-4673-3139-5
Electronic_ISBN :
978-1-4673-3138-8
Type :
conf
DOI :
10.1109/CISS.2012.6310848
Filename :
6310848
Link To Document :
بازگشت