Optimal routing for end-to-end guarantees using Network Calculus

被引:16
作者
Bouillard, Anne [2 ]
Gaujal, Bruno [1 ]
Lagrange, Sebastien [3 ]
Thierry, Eric [4 ,5 ]
机构
[1] INRIA LIG, F-38330 Montbonnot St Martin, France
[2] ENS Cachan IRISA, F-35000 Rennes, France
[3] ISTIA LISA, F-49000 Angers, France
[4] CNRS, LIAFA, F-69007 Lyon, France
[5] ENS, IXXI, F-69007 Lyon, France
关键词
Network calculus; Multiplexing; Shortest paths;
D O I
10.1016/j.peva.2008.04.008
中图分类号
TP3 [计算技术、计算机技术];
学科分类号
0812 ;
摘要
In this paper we show how Network Calculus can be used to compute the optimal route for a flow (w.r.t. end-to-end guarantees on the delay or the backlog) in a network ill the presence of cross-traffic. When cross-traffic is independent, the computation is shown to boil down to a functional shortest path problem. Under usual assumptions (concave arrival curves and convex service curves), a simple min-max lemma enables us to solve the problem in polynomial time by a sequence of classical shortest path computations. When cross-traffic perturbs the main flow over more than one node and under blind multiplexing, one can take into account the "Pay Multiplexing Only Once" (PMOO) phenomenon identified in [J.B. Schmitt, F.A. Zdarsky, The disco network calculator: A toolbox for worst case analysis. in: Proceedings of Valuetools'06, 2006; J.B. Schmitt, F.A. Zdarsky, I. Martinovic, Performance bounds in feed-forward networks under blind multiplexing. Technical Report 349/06, University of Kaiserslautern, Germany, 2006.]. It enables us to improve bounds on delays and backlogs, but it makes the computation more involved. We provide a formula which gives a service curve for a path with PMOO conditions. It introduces a new multi-dimensional Network Calculus operator and it generalizes a formula in the above reference. Moreover, when arrival (resp. service) curves are affine (resp. convex), we describe an efficient algorithm to compute this formula. We finally show how to adapt our routing algorithms to have optimal end-to-end guarantees for these new bounds on delays and backlogs which take into account PMOO. (C) 2008 Elsevier B.V. All rights reserved.
引用
收藏
页码:883 / 906
页数:24
相关论文
共 41 条
[1]   Nash equilibria for combined flow control and routing in networks: Asymptotic behavior for a large number of users [J].
Altman, E ;
Basar, T ;
Srikant, R .
IEEE TRANSACTIONS ON AUTOMATIC CONTROL, 2002, 47 (06) :917-930
[2]  
Andrews M, 2007, P SODA 07
[3]  
AWERBUCH B, 1993, AN S FDN CO, P459
[4]  
Baccelli F, 1992, SYNCHRONIZATION LINE
[5]   Asymptotically optimal algorithms for job shop scheduling and packet routing [J].
Bertsimas, D ;
Gamarnik, D .
JOURNAL OF ALGORITHMS-COGNITION INFORMATICS AND LOGIC, 1999, 33 (02) :296-318
[6]  
BOUILLARD A, 2007, P VAL 07
[7]   An algorithmic toolbox for network calculus [J].
Bouillard, Anne ;
Thierry, Eric .
DISCRETE EVENT DYNAMIC SYSTEMS-THEORY AND APPLICATIONS, 2008, 18 (01) :3-49
[8]   Deterministic traffic specification via projections under the min-plus algebra [J].
Chang, CS .
IEEE INFOCOM '99 - THE CONFERENCE ON COMPUTER COMMUNICATIONS, VOLS 1-3, PROCEEDINGS: THE FUTURE IS NOW, 1999, :43-50
[9]  
CHANG CS, 2000, TNCS
[10]  
Cormen T. H., 2001, Introduction to Algorithms, V2nd