Max-plus: A Network Algebra

Networks can support Quality of Service (QoS) architectures for a wide variety of applications. The Network Calculus (NC) appeared as a set of rules and results for computing bounds for QoS parameters. The goal of this paper is to improve the systematic use of the Max-Plus algebra in the formulation and derivation of NC results. To illustrate the presented methodology, we analyze the problem of optimizing the playback delay and the buffer size of an optimal video decoder with some look-ahead. © 2006 Springer-Verlag Berlin/Heidelberg.341375382Baccelli, F., Cohen, G., Olsder, G.J., Quadrat, J.-P., (1992) Synchronization and Linearity: An Algebra for Discrete Event Systems, , John Wiley & Sons, EnglandChang, C.-S., On deterministic traffic regulation and service guarantees: A systematic approach by filtering (1998) IEEE Transactions on Information Theory, 44 (3), pp. 1097-1110. , MayChang, C.-S., Cruz, R.L., Le Boudec, J.-Y., Thiran, P., A Min,+ system theory for constrained traffic regulation and dynamic service guarantees (2002) IEEE/ACM Trans. on Networking, 10 (6), pp. 805-817. , DecemberCruz, R.L., Quality of Service guarantees in virtual circuit switched networks (1995) IEEE Journal on Selected Areas in Communications, 13 (6), pp. 1048-1056. , AugustLe Boudec, J.-Y., Network Calculus made easy (1996) Technical Report, 96 (218). , CH-1015, DI-EPFL, Lausanne, Switzerland, DecemberLe Boudec, J.-Y., Application of Network Calculus to guaranteed service networks (1998) IEEE Trans. on Information Theory, 44 (3), pp. 1087-1096. , MayLe Boudec, J.-Y., Thiran, P., (2003) Network Calculus- A Theory of Deterministic Queuing Systems for the Internet, , http://ica1www.epfl.ch/PS_files/NetCal.htm, Springer Verlag - LNCS 2050, June 25Le Boudec, J.-Y., Thiran, P., Giordano, S., A short tutorial on Network Calculus I: Fundamental bounds in communication networks (2000) IS-CAS 2000 - IEEE Int. Symp. on Circuits and Systems, pp. IV93-IV96. , Geneva, Switzerland, May 28-31Le Boudec, J.-Y., Thiran, P., Giordano, S., A short tutorial on Network Calculus II: Min-plus system theory applied to communications networks (2000) ISCAS 2000 - IEEE Int. Symp. on Circuits and Systems, pp. IV-365. , Geneva, Switzerland, May 28-3