Computer Engineering & Science >
District,Changsha,Hunan 410073,P.R.China Network Analysis Based on the Dioid Theory
Received date: 2009-05-25
Revised date: 2009-11-12
Online published: 2011-02-25
We study the application of the dioid theory especially maxplus algebra in computer network analysis. The IO characteristics of a discrete token bucket is analyzed under the maxplus algebra. Moreover we obtain the (b,ρ) token bucket’s transfer matrix and state space equations under the maxplus algebra, we also propose a framework of maxplus network calculus and give the definition of the maxplus arrival curve and the maxplus service curve. On the basis of these two concepts, we prove the theorems about the delay and the burst of output flow. And finally, we give the application of maxplus network calculus in network analyisis, we use the nonpremptive priority node and the Guaranteed rate server as our analyzing objects and obtain their maxplus service curves respectively. We also compare our results to the minplus network calculus and show the advantages of maxplus based network analysis.
FAN Baohua,ZHANG Heying,DOU Wenhua . District,Changsha,Hunan 410073,P.R.China Network Analysis Based on the Dioid Theory[J]. Computer Engineering & Science, 2011 , 33(2) : 17 -22 . DOI: 10.3969/j.issn.1007130X.2011.
［1］Baccelli F,Cohen G, Olsder G J, et al. Synchronization and Linearity: An Algebra for Discrete Event Systems［M］. John Wiley and Sons, 1992.
［2］陈文德, 齐向东. 离散事件动态系统：极大代数方法［M］. 北京: 科学出版社, 1994.
［3］彭永进, 肖雁鸿, 彭崇, 等. 离散事件动态系统［M］. 长沙: 湖南科学技术出版社, 1994.
［4］郑大钟, 赵千川. 离散事件动态系统［M］.北京: 清华大学出版社, 2000.
［5］Cruz R L. A Calculus for Network Delay, Part I: Network Elements in Isolation［J］.IEEE Trans on Information Theory, 1991, 37(1):114131.
［6］Cruz R L. A Calculus for Network Delay, Part II: Network Analysis［J］. IEEE Trans on Information Theory, 1991, 37(1):132141.
［7］Chang C S. On Deterministic Traffic Regulation and Service Guarantees: A Systematic Approach by Filtering［J］. IEEE/ACM Trans on Information Theory, 1998, 44(3):10971110.
［8］Boudec J Y L, Thiran P. Network Calculus: A Theory of Deterministic Queuing System for the Internet［M］.SpringerVerlag, 2004.
［9］Chang C S. Performance Guarantees in Communication Networks［M］. Springer, 2000.
［10］Xie J, Jiang Y. Stochastic Service Guarantee Analysis Based on TimeDomain Models［EB/OL］. ［20090418］.http://arxiv.org/abs/0904.2018v1.
［11］Baccelli F, Hong D. Tcp Is MaxPlus Linear: and What It Tells Us on Its Throughput［J］. ACM SIGCOMM Computer Communication Review, 2000, 30(4):219230.
［12］蔡研, 赵千川. 基于极大代数的TCP协议分析［J］. 计算机学报, 2002, 25(11):11331143.
/
| 〈 |
|
〉 |