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

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.