Chinese Journal of Computers   Full Text
Title	A Matrix Interpretation of Network Calculus
Authors	FAN Bao-Hua DOU Qiang ZHANG He-Ying
Address	(School of Computer Science, National University of Defense Technology, Changsha 410073)
Year	2009
Issue	No.12(2411—2419)
Abstract &   Background	Abstract Network calculus is the application of Discrete Event Dynamic System theory in computer networks. Network calculus uses arrival curve and service curve to calculate performance parameters. The definition of arrival curve and service curve encapsulates complex theoretical background, so it is more compatible in practice. Unfortunately there is a lack of theoretical study on arrival and service curve. The authors regard arrival curve and service curve as idempotent matrices, and the calculation process can be represented by matrix operations. By corresponding results in idempotent matrix theory and residuation theory, the basic theorem of matrix network calculus is obtained. This research proves that idempotent matrix theory give network calculus a good theoretic interpretation. Keywords discrete event dynamic system; network calculus; arrival matrix; service matrix; idempotent matrix; residuation theory Background Network calculus is a deterministic queuing theory based on non-linear algebra. It has been successfully applied to a number of important issues in the field of computer networks modeling and performance analysis. It is also an efficiency tool for calculating the deterministic bounds of end-to-end performance parameters such as delay and backlog. Aimed at these shortcomings of theory research, and based on the summary of existing research results, the authors study network calculus theoretically by idempotent matrices and DEDS theory. They study arrival curve and service curve by idempotent matrix theory, also define the concept of arrival matrix and service matrix, and propose a matrix network calculus based on these two notions. Network calculus is divided into four categories by order of flow’s generated matrix. There are many advantages of matrix network calculus: First, in matrix network calculus, min-plus convolution turns into our familiar matrix multiplication; Second, the results can be used in developed idempotent matrix theory to analyze network calculus; At last matrix network calculus deepens the relationship between network calculus and DEDS theory, thus makes it possible for using DEDS theory to further study network calculus. The work is supported by National Natural Science Foundation of China (60603064) and (60603061). The authors have been made great progress in the field of network calculus, and have publicized many papers in this research direction.