基于双子代数理论的网络建模与分析
收稿日期: 2009-05-25
修回日期: 2009-11-12
网络出版日期: 2011-02-25
基金资助
国家自然科学基金资助项目(60603064，60633050)
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
本文研究了双子代数尤其是极大代数理论在计算机网络建模与性能分析中的应用。采用极大代数分析了令牌桶的输入输出特性，得到了(b,ρ)令牌桶在极大代数下的状态空间方程组与传输矩阵；提出了基于极大代数的网络演算，定义了极大到达曲线与极大服务曲线，利用这两个概念得出了极大代数下有关延迟以及输出流突发性的定理。最后采用基于极大代数的网络演算对非抢占优先级多路复用以及保证速率服务器两个模型进行了分析，得出了两种模型各自在极大代数网络演算下的服务曲线。本文还把基于极大代数的网络分析方法与基于极小代数的分析方法进行了比较，阐明了基于极大代数方法的优点与适用场合。
樊葆华，张鹤颖，窦文华 . 基于双子代数理论的网络建模与分析[J]. 计算机工程与科学, 2011 , 33(2) : 17 -22 . DOI: 10.3969/j.issn.1007130X.2011.
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.
［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.
/
| 〈 |
|
〉 |