关键词: 极大代数, 网络演算, 令牌桶, 到达曲线, 服务曲线

Abstract:

We study the application of the dioid theory especially maxplus algebra in computer network analysis. The IO characteristics of a discrete token bucket is analyzed under the maxplus algebra. Moreover we obtain the (b,ρ) token bucket’s transfer matrix and state space equations under the maxplus algebra, we also propose a framework of maxplus network calculus and give the definition of the maxplus arrival curve and the maxplus 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 maxplus network calculus in network analyisis, we use the nonpremptive priority node and the Guaranteed rate server as our analyzing objects and obtain their maxplus service curves respectively. We also compare our results to the minplus network calculus and show the advantages of maxplus based network analysis.

Key words: maxplus algebra;network calculus;token bucket;arrival curve;service curve