The Max-plus Algebra And The Network Calculus

Discrete Event Dynamic Systems (DEDS) are systems whose state transitions are triggered by events that occur at discrete instants of time. The communication networks are examples of this kind of systems. The mathematical constraints of some DEDS can be described more adequately using the Max-Plus algebra. Previous works show that the problem of determining performance bounds for communication networks is simplified if modeled using this algebra. The compilation of existing rules and results on this field is called Network Calculus. The goal of this article is to improve a systematic use of the Max-Plus algebra in the formulation and derivation of results on Network Calculus. To illustrate the introduced methodology, we analyze a window flow controller, a system that controls the traffic admitted by a network in order to limit its backlog in a specified manner. © 2006 IEEE.433438Cassandras, C.G., Lafortune, S., (1999) Introduction to Discrete Event Systems, , Kluwer Academic PublishersChang, 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., Boudec, J.-Y.L., Thiran, P., A Min,+ system theory for constrained traffic regulation and dynamic service guarantees (2002) IEEE/ACM Transactions on Networking, 10 (6), pp. 805-817. , DecemberLe Boudec, J.-Y., Application of Network Calculus to guaranteed service networks (1998) IEEE Transactions on Information Theory, 44 (3), pp. 1087-1096. , MayLe Boudec, J.-Y., Thiran, P., Network Calculus- A Theory of Deterministic Queuing Systems for the Internet (2003) Online Version of the Book Springer Verlag - LNCS 2050, , http: //ica1www.epflch/PSfiles/ NetCal.htm, June 25Le Boudec, J.-Y., (1996) Network Calculus made easy, , DI-EPFL, Lausanne, Switzerland, Tech. Rep. 96/218, CH-1015, DecemberJ.-Y. Le Boudec, P. Thiran, and S. Giordano, A short tutorial on Network Calculus I: Fundamental bounds in communication networks, in ISCAS 2000 - IEEE International Symposium on Circuits and Systems, Geneva, Switzerland, May 28-31 2000, pp. IV-93-IV-96_, A short tutorial on Network Calculus II: Min-plus system theory applied to communications networks, in ISCAS 2000 - IEEE International Symposium on Circuits and Systems, Geneva, Switzerland, May 28-31 2000, pp. IV-365Agrawal, R., Rajan, R., (1996) Performance bounds for guaranteed and adaptive services, , IBM, Tech. Rep. RC 20649, 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. , AugustBaccelli, F., Cohen, G., Olsder, G.J., Quadrat, J.-P., (1992) Synchronization and Linearity: An Algebra for Discrete Event Systems, , England: John Wiley & Son