电子学报990623

	电子学报 ACTA ELECTRONICA SINICA 1999年第27卷第6期 vol.27 No.6 1999

分组交换网中两路合用系统的性能分析*

牛志升　刘　宇　林孝康

提要　本文提出一种级联排队模型对两路合用系统进行了系统建模，并且利用矩阵几何解析法对该模型进行精确的理论分析，推导出分组平均延迟时间和两条链路的平均利用率这两个重要的性能指标.利用计算结果，着重讨论了两条链路的速率差异、同步缓冲器的长度、系统归一化到达率以及到达过程的突发性对于系统性能指标的影响.
关键词:通信网，逆复用，分散路由，合用技术，突发信元

Performance Analysis of a Two-Link Striping
System in Packet-Switched Networks

Niu Zhisheng,Liu Yu,Lin Xiaokang

(Tsinghua University,Beijing 100084)

Abstract:　In this paper we propose a two-stage tandem queue model for a two-link striping system in packet-switched networks.By using the matrix-geometric solution,we derive the average packet delay time and the link utilization ratio in exact form.Through the numerical examples,the effects of the link difference,the buffer size,the packet arrival rates,and the input burstiness on key performance measures are discussed.
Key words:　Communication networks,Inverse multiplexing,Dispersion routing,Striping,Bursty arrivals

一、引　言
　　目前，虽然光纤传输与ATM交换技术的发展在一定程度上满足了宽带综合业务的带宽需求，但随着业务量(比如Internet数据业务)的飞速增加和新兴业务的不断涌现，网络带宽与业务需求之间的矛盾将仍然是网络发展的主要瓶颈之一.同时，目前在许多现有的通信网络中仍然存在着业务需求与传输带宽之间的矛盾，典型的有移动通信、卫星通信系统领域.因此，在进一步提高传输带宽资源的同时，如何有效地利用现有网络资源是一个非常重要的研究课题.
　　合用(striping)技术是一种联合使用多个并行独立的同类资源以获得所需性能的体系结构技术^［1］.在通信领域中，合用技术主要用于联合使用多条并行的通信链路(路由)，构成一条虚拟的链路(路由)来传输一条高速信息流.最近由ATM论坛提出的逆复用(inverse multiplexing)技术^［2］以及分散路由(dispersion routing)技术^［3］均是基于同样的思想并已开始被广泛利用.尤其是在网络负荷较重的情况下，将流量较大的业务分散到多条网络路由中来承担，不仅可以减轻网络中部分重载路由的业务负荷，同时也提高了网络资源的利用率.
　　在合用系统中，由于并行链路的速率差异会造成信息分组之间顺序的颠倒，提供并行链路间的同步功能是保证系统性能的关键.保证这些分组顺序的方法可以采用按顺序编号的方法，在合用点为每个分组编号，而在解合用点，按照分组序号进行同步.分组序号可以加在信元头部，也可以利用专用的信令通道(Virtual Channel)传输序号信息.由于该方法实现起来比较简单，顺序编号方法是一种广为接受的同步机制，在本文中也采用此算法.此时，如何设计接收端的同步缓冲器的大小将是一个普遍关心的问题.缓冲器过大将导致资源浪费，并且有可能导致网络锁死(deadlock)^［4］；相反，如果缓冲器过小，网络性能将难以得到保证.
　　迄今为止，有关合用技术的论著大多停留在技术本身或同步机制的讨论上.其建模和性能分析，以及缓冲器大小设计问题仍然是一个急需解决的理论问题.尽管已有文献讨论同速率链路合用系统的性能分析问题^［13］，异速率链路合用系统的理论分析问题仍然没有被解决.

二、两路合用系统的排队模型
　　如图1所示，输入的信息流以一定的信息单位到达发送端的合用点，为了一致起见，这里将信息单位统称为分组.每个到达合用点的分组首先按照到达的顺序编号，然后依次被分配到空闲的链路中传输.如果两条链路都空闲，那么最早到达(序号较小)的分组进入速率高的链路中传输；如果两条链路都被占用，那么编号后的分组在输入缓冲区中等待，输入缓冲区按照先进先出规则排队.一旦某条链路空闲，输入缓冲区队头的分组即进入这条链路传输.在接收端，两个链路接口将收到的分组按顺序送入同步缓冲区；当分组被全部接收后，所有分组一并离开同步缓冲区.当接收端的同步缓冲区被占满时，如果一条链路中又收到分组，并且这个分组也不能立即离开系统，那么这个分组将在链路接口中等待，同时利用信令通知发送端的相应接口停止在该链路上继续发送分组，这条链路进入阻塞状态，当该链路接口中的分组离开后，再利用信令通知发送端继续发送分组，将链路恢复到正常状态.
　　针对上述合用系统的工作原理，我们提出用图2所示的级联排队模型对其建模.两个队列分别对应发送端的输入缓冲区队列Q₁和接收端的同步缓冲区Q₂.Q₁是一个无限容量的FIFO(first-in-first-out)队列，Q₂是一个容量为n的有限队列，其排队规则是随机进入依序号离去.两个服务器S₁和S₂分别代表两条链路.如果两条链路都是空闲的，那么传输速率高的链路对应于S₂，传输速率低的链路对应于S₁，即先到分组(序号较小的分组)选择S₂，后到分组(序号较大的分组)选择S₁.若系统中只有一条链路中有分组传输时，那么该链路既对应于S₂，空闲链路对应于S₁，此时若有分组到达，则在S₁中接受服务.当两条链路中都有分组在传输时，序号较小的分组所在的服务器既对应于S₂，序号较大的分组所在的服务器既对应于S₁.当S₂中的分组离开系统时，S₂对应的链路可能空闲，也可能继续传输后续分组，这时，两个服务器与两条链路的对应关系将发生交换，即原来S₁对应的链路由于其正在传输的分组由序号较大的分组变成序号较小的分组而对应于S₂，同时原来S₂对应的链路对应为S₁.
　　利用这种在分组离去时改变服务器与实际链路对应关系的服务器动态对应方法，在实际系统与排队模型之间建立了固定的联系，是整个建模工作的关键步骤.虽然它导致了模型中服务器参数在服务离去时刻产生变化，使得S₁的参数依S₂的变化而变化，不利于使用传统的排队论方法进行分析.但是利用下述的分析手段，这一问题得到了妥善的解决.

23.1.gif (3908 bytes)

图1　两种合用系统描述

23.2.gif (2916 bytes)

图2　两种合用系统的级联排队模型

　　下面描述图2模型的服务规则.在S₁中完成服务的客户进入Q₂中等待离去，直到S₂中的客户完成服务离去时，它才能随之离去.当服务器S₁中的一个客户完成服务并且队列Q₂排满时，该客户滞留在S₁中，使其它客户也无法进入S₁接受服务，S₁进入阻塞状态.当S₂中的客户完成服务离开系统时，在Q₂中等待的所有客户也立即离开系统.如果此时S₁处于阻塞状态，那么S₁中已完成服务并等待离开的客户也同时离开系统.如果S₁中有客户正在接受服务，由前面的服务器动态对应方法，S₁对应的链路此刻改为S₂，其中的客户照常接受服务.对应于前述的合用系统，收端收到的分组先被存入同步缓冲区Q₂，如果它不是系统中最早到达(序号最小)的分组，那么它就会滞留在Q₂中等待离去，直到系统中的最早到达的分组离开系统时.如果它就是系统中的最早到达的分组，那么它将立即离开系统，同时，在Q₂中的其它分组也将同时离开.此刻，如果另一条链路处于阻塞状态，即在该链路的接口中暂存了一个接收的分组，该分组也会立即离开系统，同时利用信令通知发送端继续发送分组，将链路恢复到正常状态.
　　下面描述该模型的客户到达过程和服务过程.出于简化理论分析的原因，迄今为止的许多论文经常假设分组按泊松过程到达.其长度也假设为指数分布.但最新的研究成果表明，分组的到达具有很强的突发性，其长度也不一定服从指数分布^［5，6］.为了使本文的结果更具有普遍性和实用性，我们假设分组的到达过程为位相型马尔可夫更新过程PH-MRP:phase-type Markov renewal process^［7］，其长度则服从位相型概率分布(PH:phase-type distribution)^［8］.PH型分布是一个非常具有一般性的概率分布，r阶PH分布可以用(β,S,S⁰)来表示，其中，β是一个r代表横向量，S是一个r×r维方矩阵S⁰是一个r维纵向量.它包含几乎所用的实用型概率分布^［8］.PH-MRP是在PH型分布的基础上派生出来的，也可用一组矩阵(α,T,T⁰)来表示.但此时α、T和T⁰均为方矩阵，它也非常具有普遍性，泊松过程，间歇泊松过程(IPP：interrupted Poisson process),以及马尔可夫调制泊松过程(MMPP：Markov modulated Poisson Process)^［6］等均可视为其特殊情况.实际上，迄今为止已有许多论文应用这两者解决了实际问题^［9～12］.
　　具体地讲，我们假设分组到达过程为一个r阶PH-MRP，用(α,T,T⁰)表示；其在服务器S₁和S₂中的服务时间分别为r₁阶和r₂阶PH型概率分布，分别用(β₁,S₁,S⁰₁)和(β₂,S₂,S⁰₂)表示.于是，分组的平均到达率和在S₁与S₂中的平均服务率分别为=θT⁰e,₁=₁S⁰₁e和₂=₂S⁰₂e.其中，θ,₁和₂分别是T+T⁰α、S₁+S⁰₁β₁和S₂+S⁰₂β₂的稳态概率分布.另外，用a₁和a₂表示两条链路的归一化速率(即a₁+a₂=1)，定义ρ=/(₁+₂)为归一化到达率.

三、级联排队模型的矩阵几何解
　　根据矩阵几何解析法(matrix-geometric solution)的思想，图2的级联排队模型可以构成一个准生灭过程(quasi-birth-and-death process)，它的状态空间是：
E={(0,j,k,h):0j2n+4,1kr₁;1hr₂}∪
　{(i,j,k,h):i＞0,1j2n+4,1kr₁;1hr₂}
其中：k表示PH-MRP型到达过程的相位；h表示PH型服务过程的相位；i表示在服务器S₁和队列Q₁中的客户数目；j表示在服务器S₂、队列Q₂以及可能滞留于阻塞的S₁中的客户数目；∪为集合或运算记号.当1jn+2时，说明S₂对应于传输速率高的链路；当n+3j2n+4时，说明S₁对应于传输速率高的链路.这两种情况下，在S₂、Q₂以及可能滞留于阻塞的S₁中的客户总数分别为j和j-n-2.
　　于是，该准生灭过程的无限小生成矩阵Q满足：
　　　　　　 23.3.gif (1300 bytes)
其中：
23.4.gif (3561 bytes) 23.5.gif (3368 bytes)
23.6.gif (3519 bytes)
23.7.gif (2157 bytes)
23.8.gif (1873 bytes)
23.9.gif (2445 bytes)
23.10.gif (4672 bytes)
以上矩阵中，运算符和分别表示矩阵的Kronecker乘运算与和运算，矩阵I_m表示一个m×m单位矩阵(所有对角元素为1，非对角元素为0).
　　定义排队模型的稳态概率分布为
　　　　　　　x_ijkh=P［N₁=i,N₂=j,K=k,H=h］,
其中，N₁表示在服务器S₁和队列Q₁中的客户数目；N₂表示在服务器S₂、队列Q₂以及可能滞留于阻塞的S₁中的客户数据目；K和H分别为达到过程和服务过程的相位
　　并定义如下概率向量
　　　　x=(x₀,x₁,x₂,……)，
　　　　x₀=(x₀₀,x₀₁,x₀₂,…,x_0,2n+4),
　　　　x_i=(x_i1,x_i2,…,x_i,2n+4),
　　　　x_ij=(x_ij11,…,x_ij1h,…,x_ijk1,…,x_ijkh).
通过解联立方程式xQ=0和xe=1得
　　　　x_i=x₁R^i-1,i1　　　　　　　　(2)
其中，矩阵R是下面方程式的最小非负解：
　　　　A₀+RA₁+R²A₂=0　　　　　　　　(3)
　　边界概率向量(x₀,x₁)可以从下面联立方程式中解得：
23.11.gif (1759 bytes)
由Little公式，可以得到客户在排队模型中的平均等待时间：
23.12.gif (3495 bytes)
其中，矩阵Λ可表示为：
23.13.gif (3218 bytes) 　　
同时，也易得到两条链路各自的平均利用率
　　
　　 23.22.gif (660 bytes) 　　　(9)
四、数值分析结果与讨论
1.平均传输时间与系统负载、同步缓冲器长度的关系
　　图3中，给出了第三节中的同类合用系统的平均传输时间与系统负载以及同步缓冲器长度n的关系.同时，还给出了三种对照模型的性能比较.它们是：服务率分别为μ、2μ情况下的M/M/1排队系统和服务率为μ的M/M/2排队系统.这三种模型依次相当于：仅有一条链路的传输系统A、两倍于单链路传输速率的理想链路传输系统B和不需要同步机制的两条链路传输系统C.
　　首先，随着系统中同步缓冲器长度n的增加，在相同的系统负载条件下，合用系统的平均传输时间逐渐减小.当n增加到一定程度后，平均传输时间趋向于一个极限值.该极限值始终与系统B和系统C的平均传输时间相差一段时间，这段时间是由于合用系统中的同步机制造成的，无法通过增加同步缓冲器的长度来消除.
　　其次，可以对照系统A、B和C，比较合用系统的性能.在相同的系统负载条件下，合用系统的平均传输时间始终小于系统A，而大于系统B与系统C，这是与实际情况相符的.同时，这也说明了：在同样的平均传输时间要求下，利用合用系统，可以比系统A处理更大的到达业务量，但是无法达到系统B的业务量处理能力.

23.15.gif (8466 bytes)

图3　平均传输时间与系统负载，同步缓冲器长度的关系

2.业务突发性对平均传输时间的影响
　　图4中给出了同类链路系统中，指数长度分布的分组，依据马尔科夫调制泊松过程到达系统后的平均传输时间，另外，图中还给出了同样的分组依据泊松过程达到系统后的平均传输时间作为参照.图中到达过程MMPP的表示为^［6］
　　　　　　
式中参数^［11］：λ₁=1.5399754；λ₂=0.2877169；r₁=0.0742993；r₂=0.0980084.即MMPP的均方差系数的平方是C²_a=2.25，协方差系数为θ=0.2.
　　与泊松到达的情况相对比，可以看出，在相同的系统归一化到达率情况下，MMPP的到达流造成了平均传输时间的增大，如果系统设计时仅考虑泊松过程的业务到达，那么设计的系统就无法满足预定的设计要求，造成不必要的损失.

23.17.gif (8242 bytes)

图4　平均传输时间与归一化到达率、同步缓冲器大小的关系

3.异类链路的不同速率对链路平均利用率的影响
　　在图5中，给出了n=2和n=20的异类链路合用系统，在几种不同链路速率比情况下，系统两条链路的平均利用率与归一化到达率的关系.
　　当链路速率比是1：1时，高速链路的利用率始终较大，但是，随着链路速率比的增加，在系统的归一化到达率较大的区域，低速链路的利用率反而高出高速链路.这种情况并不是设计所希望的，因为充分地利用高速链路会对整个系统性能更加有利.那么是什么原因导致了这种情况的发生呢?产生这种情况的原因是低速链路传输速度慢，经常导致同步缓冲器被填满，使高速链路处于阻塞状态，这虽然提高了高速链路的利用率，但是高速链路在阻塞状态并不传输分组，使高速链路的实际处理能力下降，而系统的业务量与处理能力在系统最大利用率以内是保持平衡的，所以低速链路要负担一部分由于高速链路阻塞而未处理的业务量，导致低速链路也相应地提高了它的链路利用率.当负担较重时，就会出现低速链路的平均利用率高于高速链路的情况.为了避免这种不利情况的发生，可以采用不同的发送端分组分配方法，例如对系统状态进行预测后，再决定分组是否利用低速链路传输，以保证分组能够最快地送到接收端.这些方法还有待进一步研究.
　　此外，同步缓冲器长度越大，两条链路的实际利用率越大.当异类链路合用系统的同步缓冲器长度较小(n=2)时，同步造成的链路阻塞状态的概率会增加，由于链路阻塞也相当于链路被占用，所以链路的平均利用率增加，从而导致了系统最大利用率下降，反映在图中就是在归一化到达率接近系统的最大利用率时，两条链路的平均利用率与归一化到达率的曲线斜率较大.当同步缓冲器长度较大(n=20)时，同样到达率条件下曲线斜率接近于1.这就说明同步缓冲器长度对于链路的平均利用率的影响是造成系统最大利用率限制的因素.

23.18.gif (3596 bytes)
23.19.gif (4236 bytes)
23.21.gif (3609 bytes)
23.20.gif (4400 bytes)

图5　异类链路的平均链路利用率与两条链路速率比及同步缓冲器长度n的关系

五、结　　论
　　本文提出一种独特的级联排队模型对两路合用系统进行了系统建模和性能分析，推导出了分组平均传输时间和两条链路的平均利用率这两个重要的性能指标.利用计算结果，着重讨论了系统的两条链路的速率差异、同步缓冲器的长度、系统的归一化到达率和业务到达的突发性对于这些性能指标的影响.主要结论是：
^.系统同步缓冲器长度的增加会使系统的最大利用率增加、分组平均传输时间减小；
^.到达率固定时，系统的分组平均传输时间随着同步缓冲器长度的增加达到一个极小值
^.业务突发性的增加和两条链路的速率差异增大，都会降低系统的最大利用率，并增加分组平均传输时间
^.不同速率的两条链路合用系统中，低速链路会导致高速链路较为频繁的阻塞，从而使系统性能下降.
这些结论说明了这种两路合用系统的性能与系统参数间的主要关系，对合用系统的设计与实现具有重要作用.
　　本文只讨论了两路合用系统的性能问题，对于多于两路的合用系统的性能分析有待进一步研究.但如果将多条链路虚拟地视作一条虚拟链路，本文的分析结果也将能发挥作用.至少可以作为进一步研究的参考和理论基础.

*国家自然科学基金资助课题(编号69572018)

作者简介:牛志升　1985年毕业于北方交通大学通信与控制系，1989年和1992年先后获得日本丰桥技术科学大学的硕士和博士学位.1992～1994年就职于日本富士通研究所，1994年回清华大学任教至今.现为清华大学微波与数字通信国家重点实验室副教授.此间，1995年10月至1996年3月先后受日本邮政省通信放送协会(TAO)和日本科学技术厅(STA)的邀请访问日本邮政省通信综合研究所(CRL)，1997年2月至1998年2月做为客座教授访问日本日立公司中央研究所.主要研究方向：通信话务理论和排队论，ATM网络流量控制技术，无线ATM网络技术的研究.IEEE高级会员，电子学会高级会员，中国运筹学会会员.
　　　　　刘　宇　1993年毕业于西安电子科技大学，1996年获清华大学硕士学位.
　　　　　林孝康　1970年毕业于清华大学无线电电子学系.现为清华大学微波与数字通信国家重点实验室教授，通信教研室主任.1988～1989年德国斯图加特大学访问学者.现主要从事SDH传输技术和无线ATM技术的研究.
作者单位:清华大学电子工程系，北京 100084

参考文献
［1］　Traw,C.B.S.and Smith,J.M..Striping within the network subsystem.IEEE Network,July/August 1995,22～32
［2］　Duncanson,J.,Inverse multiplexing.IEEE Commun.Mag.,April 1994,34～41
［3］　E.Gustafsson and G.Karlsson.A literature survey on traffic dispersion.IEEE Network,Mar/Apr 1997
［4］　M.Schwartz.Telecommunications Networks:protocol,modeling and analysis.1987
［5］　Paxson,V.and Floyd,S.Wide area traffic:The failure of Poisson modeling.IEEE/ACM Trans.Networking,June 1995,3(3):226～244
［6］　Heffes,H.and Lucantoni,D.M..A Markov modulated characterization of packetized voice and Data traffic and related statistical multiplexer performance,Sept.1986,SAC-4(6):856～868
［7］　Machihara,F..Completion time of service unit interrupted by PH-Markov renewal customers and its applications.12th International Teletraffic Congress,5.4B.5,Torino,1988
［8］　Neuts,M.F..Matrix-geometric solutions in the stochastic models:An algorithm approach.Baltimore,MD:The Johns Hopking University Press,1981
［9］　Niu,Z.and Akimaru,H.Studies on Mixed Delay and Nondelay Systems in ATM Networks.Teletrafic and Datatrafic in a Period of Changes,Elsevier Sci.Publishers,B.V.(North-Holland),1991,515～520
［10］　Niu,Z.,Akimaru.Analysis of statistical multiplexer with selective cell discarding control in ATM networks.IEICE Trans.Commun.,74(12),1991
［11］　Niu,Z.,Kawai,T.,Akimaru,H.and Tadokoro,Y.A unified solution to mixed loss and delay systems with partial preemptive priority.Electronic & Commun.in Japan,Part 1,78(8):57～65,1995
［12］　Niu,Z.,Akimaru,H.,Kokubugata,T..A priority buffer management scheme for ATM and its performance evaluation.4th International Conference on Communication Technology (ICCT′94),Shanghai,China,1994
［13］　刘宇.综合话音数据的交换技术研究.清华大学硕士论文，1996

1997年12月收到,1998年10月定稿.