Delay Bounds under Arbitrary Multiplexing: When Network Calculus Leaves You in the Lurch...
Key: SZF08-1
Author: Jens Schmitt, Frank Zdarsky, Markus Fidler
Date: April 2008
Kind: In proceedings
Publisher: IEEE Press
Book title: Proceedings of IEEE INFOCOM
Keywords: Network Calculus
Abstract: Network calculus has proven as a valuable and versatile methodology for worst-case analysis of communication networks. One issue in which it is still lacking is the treatment of aggregate multiplexing, in particular if the FIFO property cannot be assumed when flows are merged. In this paper, we address the problem of bounding the delay of individual traffic flows in feed-forward networks under arbitrary multiplexing. Somewhat surprisingly, we find that direct application of network calculus results in loose bounds even in seemingly simple scenarios. The reasons for this ``failure'' of network calculus are discussed in detail and a method to arrive at tight delay bounds for arbitrary (aggregate) multiplexing is presented. This method is based on the solution of an optimization problem. For the special case of sink-tree networks this optimization problem is solved explicitly, thus arriving at a closed-form expression for the delay bound. Numerical experiments illustrate that in sink-tree networks the improvement over bounds based on direct application of network calculus can be considerable.

The documents distributed by this server have been provided by the contributing authors as a means to ensure timely dissemination of scholarly and technical work on a non-commercial basis. Copyright and all rights therein are maintained by the authors or by other copyright holders, not withstanding that they have offered their works here electronically. It is understood that all persons copying this information will adhere to the terms and constraints invoked by each author's copyright. These works may not be reposted without the explicit permission of the copyright holder.