基于Round-Robin的光突发交换混合门限组装算法

1）星载光交换组装算法设计时考虑的问题

星载光交换组装算法设计时主要考虑的问题有：①业务种类多，QoS要求不一致。有的业务对时延敏感，有的对丢包率敏感，针对这些需求，在设计系统时需要系统地、折中地考虑交换和调度方法。②星上资源有限，算法复杂度不能太高，否则会耗费大量能源，导致卫星寿命降低。③通信时间受限，对通信链路的利用率要求较高。卫星光网络的通信时间由于受到卫星间相对运动的影响不能随时建立连接，通信时间受到一定的限制；且卫星间距离遥远，通信质量受到影响，这就对通信期间光链路的利用率要求较高。④光纤延迟线缓存时间有限，性能有限，故星上不可能携带大量光纤延迟线。综上，组装算法设计时要考虑卫星光网络的多种局限和要求，比较之后选用混合门限方式。

下面研究组装时间，设端到端时延为T ETE，则其包括入口节点处理时延T ingress，偏置时延T off、中间节点处理时延T inter、出口节点处理时延T outgress和传播时延T prop。假设T th为平均组装时间，则边缘节点的BDP输出率为1／T th，假设k为流经每个核心节点的平均数据流，核心节点的服务速率为μ，则其处理1个BCP的时间为1／μs。如果流经核心节点的K个数据流独立同分布，把输入核心节点的数据量作归一化处理，其上限为（0＜k＜1）。由突发数据包输出速率必须小于控制面最大处理速率，可得

控制平面对BCP采用存储转发方式，通过M／G／1或M／D／1模型可计算突发停留平均时间W（λc），其中λc为核心节点控制平面的背景流量，则有T th≥W（λc）。由此可得组装时间门限的下限为

组装算法时间门限处于一个区间中，即

同理，长度门限也处于一个区间中：

式中，R为数据信道速率，Erlb（.）为通过爱尔兰B公式得到的最大突发持续时间，L th为门限长度，λ为Gamma分布参数，W为系统容量，T oxc为光交叉连接器两次使用间隔配置时间，η为数据信道负载率下限。

通过图8-15可以表示时间门限和长度门限可以取值的范围。只要组装时间和组装门限处于上述两公式规定的范围内就可以了。

图8-15　混合组装门限取值范围

2）星载光交换组装算法

结合卫星光网络的特点，对基于Round-Robin的组装算法进行改进：LEO（相当于边缘节点）把来自各个传感器的数据分别按照数据的优先级（QoS）和目的地址存储到不同的缓存中，每个缓存队列都配置一个组装器，如图8-16所示。

图8-16　星载光交换网络边缘节点的组成结构及传输链路

组装步骤为：①每个组装器首先填入本队列中的数据。②high priority数据队列中的数据如果组装时间下限T min结束仍然填不满最短突发长度L min，则按照异步的方式进行轮询和混合组装，即当high priority数据在T min内填不满最短BDP时，才填入其他优先级数据，直到达到时间门限的最大值T max；在轮询期间，每个队列不相互等待，本队列只要满足组装条件，即可产生一个BDP。③若high priority数据在时间T min内能够填满L min，则此突发包只传输high priority数据，否则BDP中是混合数据。④若在T max到达时且low priority数据填入后仍然不能填满BDP，则填入空闲数据。⑤low priority数据队列的组装基于最大时间和最小长度门限方法，high priority数据队列组装基于最小时间和最大长度门限；高低优先级数据混合组装时使用最大时间最大长度门限。

混合组装的前提条件是：①只有目的地址相同的数据分组才能混装在一个BDP中。②只有high priority分组队列的组装才能去轮询low priority数据队列，low priority分组队列不能轮询high priority队列，low priority队列数据量不够时只能填入空闲数据，以提供high priority数据所需的QoS性能。

突发包中各优先级数据长度由BCP中length字段标出。假设有N个优先级，则控制包中的长度字段至少为N-1个，这样在目的端可区分出不同的IP包。high priority队列的组装器从low priority队列的头部取数据进行填充。可以看出，low priority数据相当于“搭顺路车”，既减少了组装等待时间，同时也提高了星间光链路的利用率。

3）算法理论模型

（1）空闲比特填充率。

这里通过推导空闲比特填充概率模型讨论FZTFR算法。假定系统有N个不同优先级的BDP、P个目的地址，则需要NP个数据队列。这些队列可认为是M／M／NP／L排队系统，此处节点服务时间以M表示，服从指数分布，NP表示系统中服务员的个数，即组装器的个数，L表示系统的容量，即突发包的最大长度。

假设class1拥有最高的priority，而class N拥有最低priority。任一类别i的突发包单独到时的指数分布率为λi，它的平均传输时间为t i，因此类别i突发包的流量密度为ρi=λit i／K，K为用于传输突发数据包的波长数目。IP数据包的服务时间服从参数为μ的指数分布。

假设突发组装长度门限下限为L min，上限为L max，组装时间的门限分别为T min和T max。则在T min时间内到达k个分组的概率为k=0，1，2，…，则在T min时间内IP分组队列长度B的概率密度函数为：f B（x）=（N=k）f（x｜k），其中f（x｜k）为有k个分组时到达队列长度的条件概率。由于IP分组长度服从负指数分布，k个分组到达队列时队列长度为一个k阶爱尔兰分布，则f（x｜k）可由下式给出

从而可得T min时间内IP分组队列长度B的概率密度函数为

若高等级IP包不能在时间门限下限T min到来时达到最短突发包长，则会从低等级队列中拿出一些数据填入，使之能达到最短突发门限长度。这些低等级数据也是在T min时间内到达的，则在T min时间内可能到达（L min-k）个低等级分组的概率为

则在时间T内填满突发包最短包长的概率为

则系统的空闲填充率为

f B（x）可以用一个n阶一般爱尔兰分布来近似，表达式为

式中，μ1为爱尔兰分布均值。

通过以上公式，就可以计算出突发包的空闲比特填充率。

（2）链路利用率。

在考虑保护时间的条件下，卫星光突发交换网络总的链路利用率为

式中，T bs为数据突发传输时间，T oxc为设备倒换时间，ρb为单波长信道的业务量强度。从式（8-9）可以看出，在选取组装算法参数时，为保证较高的链路利用率，必须要求　足够大，即突发传输时间与倒换时间相比要足够大。因此，在考虑QoS情况下，时间门限和长度门限还必须满足以下条件：

式中，Q为系统的QoS等级数，D为目的地址数，λ为IP分组以Possion过程到达时的参数，1／μ为IP分组长度的平均值，。此处T bs=T ass+T sch+T tri+T del，T ass为边缘节点组装时间，T sch为调度时间，T tri为链路传输时间，T del为总的等待时延（包括组装时延，调度时延，交换时延等）。此处假定T oxc，T sch，T tri，T del为固定值，则当采用FZTFR算法时，组装时间必须比T min要大。在低负载率情况下尤其比使用固定门限算法的组装时间要长，所以其链路利用率有了较大的提高。

（3）突发包丢失率。

当类别n的突发包被其他类别突发包阻塞而不是被比它优先级低的突发包阻塞时，其突发包丢失率就是最小突发包丢失率。类别n突发包的最低丢失率可表示为

（4）算法复杂度。

网络负荷较大时，某一队列中的数据可在最短时间内填满最短长度的突发包，不需要填充入其他队列的数据，此时算法复杂度比Round-Robin轮询算法还简单，所需的存储空间未增加。在最坏情况下，即某一队列的数据很少，在最短时间门限到来时仍不能填满最短突发包长，则在（T max-T min）内轮询其他队列，插入其他队列的数据包，此时复杂度与Round-Robin轮询算法相当。所以FZTFR算法简单可行，易于实现，较为适合星上光突发交换网络。

（5）组装时延。

为简单分析起见，此处假设只有2个优先级，分别为0和1，0代表高优先级，1代表低优先级，它们的分组到达率分别为λ0和λ1。

（A）完全由高优先级数据分组组成的数据突发包中第i个分组的时延。

高优先级突发包的组装门限是T min，L max，只要达到其中一个条件就可以产生一个BDP。则依据部分混合组装算法时延分析可知高优先级突发包中的分组时延由2部分组成：达到长度门限和达到时间门限的时延的和，即时延的概率密度函数为

（B）完全由低优先级数据分组组成的数据突发包中第i个分组的时延。

低优先级数据队列的组装基于最大时间T max和最小长度门限方法L min，达到其中一个条件就可以生成突发包，则依据部分混合组装算法时延分析可知，低优先级突发包中的分组时延由2部分组成：达到长度门限和达到时间门限的时延的和，则时延的概率密度函数为

（C）由高优先级分组和低优先级分组共同组成的数据突发包中第i个分组时延。

混合突发包的组装基于最大时间T max和最大长度门限L max，达到任一条件即可生成突发包。这种BDP由高优先级分组和其他优先级分组共同组成，计算第i个分组的时延时分为2种情况：①第i个分组属于高优先级分组，则其时延分为2部分：一部分是高优先级分组基于T min和L min门限的组装，此时由于时间达到了T min，但长度未达到L min，则这部分时延的概率密度可表示为基于时间门限T min组装算法的概率密度：

高优先级队列中数据量不能达到L min时轮询开始并组装低优先级分组，为了能达到最大长度门限或最大时间门限，假设此时队列中高优先级分组长度达到L，则剩下的组装可认为是长度门限为L max-L、时间门限为T max-T min的混合门限组装。若最后是先到达时间门限T max-T min，则其剩余的时延就是剩余的组装时间T max-T min；若是先到达长度门限，则其突发包中轮询得到的第j个分组时延的概率密度可表示基于长度门限为L max-L min的组装算法的概率密度：

最终平均组装时延可通过分段积分得到。②第i个分组属于低优先级分组，其到达率为λ1，则其组装过程类似于长度门限为L max-L、时间门限为T max-T min的混合门限组装，其时延的概率密度可以套用混合门限组装算法的概率密度公式，结果为

4）仿真验证结果

以其中任一边缘节点作为组装算法仿真对象。对3种不同的组装汇聚方法进行仿真。图8-17是不同组装算法下的空闲比特填充率比较，可以看出：FZTFR算法相比于PBRA算法，填充率在高负载情况下相差不大，而在中低负载下填充率降低较多，这也证明了FZTFR算法对降低填充率有很明显的作用，尤其是负载为0.35时，其空闲填充率比超前汇聚算法降低了4.51倍，比PBRA算法降低了4.72倍。

图8-17　不同组装算法下的空闲比特填充率比较

图8-18比较了FZTFR算法下不同优先级数据丢包率，可得出高优先级数据的服务质量得到了有效的保证。负载较低时，高优先级突发包单个队列数据在最短时间门限内达不到最短长度门限，所以轮询插入了低优先级数据，故而此时低优先级数据的丢包率与高优先级比较接近；随着负载的增加，高、低优先级之间的丢包率差异逐渐明显。

图8-19比较了FZTFR算法与其他算法的丢包率，可以看出由于采用了先进的轮询填充手段，低优先级的数据可以“搭乘”高优先级数据的“车”，这样在分配数据信道时，可以有优先权，丢包率得到了较大的改善。负载为0.35时，FZTFR算法的丢包率比超前汇聚和PBRA算法的丢包率低2个数量级，差距明显，随着负载的逐渐上升，差距逐渐缩小。超前汇聚算法由于类似于固定时间门限算法，其丢包率在低负载时与PBRA算法接近，但从0.35开始其丢包率上升很快，原因在于其突发包生成时间接近，易于造成突发发送时间重叠，引起资源竞争，所以丢包率较高。

图8-18　FZTFR算法不同优先级数据丢包率比较

图8-19　不同组装算法下的类别1丢包率比较

图8-20比较了FZTFR算法与PBRA算法下类别1突发数据的组装时延比较，可以发现在单位负载较小时FZTFR的性能较为突出，在负载为0.3时FZTFR组装时延比PBRA性能提高18.7%左右，与超前汇聚算法持平。原因在于FZTFR算法时间门限有最长、最短2个门限，长度门限也有2个门限，门限较为灵活，而PBRA时间门限和长度门限都只有1个。随着负载逐渐增大，两种算法的组装时延逐渐接近，原因为两者都是混合门限算法，在负载较大时数据量都能很快到达长度门限，所以组装时延逐渐趋同。

图8-20　不同组装算法下的类别1组装时延比较

综合以上分析，可以得出结论：①FZTFR算法有效地降低了突发包的空闲比特填充率，提高了卫星光交换网络链路的利用率。②相比Round-Robin、PBRA和超前汇聚算法，使用了FZTFR算法后，提高了数据丢失率，而计算复杂度并没有因此增加。③相比PBRA算法，组装时延在低负载下更小，高负载下类似于PBRA算法，远小于超前汇聚算法。④相比超前汇聚算法能支持QoS要求。

综上，FZTFR算法达到了卫星光网络通信的需求。不足之处是如果在低优先级的队列快达到组装门限时，而高优先级的数据包恰好缺少几个IP包，希望从中“拿走”几个时，存在着能不能拿走的问题，即低优先级队列中的数据在达到多长时可以被拿走，这是一个值得研究的问题，否则即使强行拿走也可能得不偿失，反而会导致低优先级数据时延加大，链路利用率反而降低。