长距离无源光网络中自适应多线程轮询算法

张清玲，何荣希（大连海事大学信息科学技术学院，辽宁 大连116026）



中文核心期刊

长距离无源光网络中自适应多线程轮询算法

张清玲，何荣希
（大连海事大学信息科学技术学院，辽宁 大连116026）

摘要：针对长距离无源光网络覆盖范围广、传播时延大的特点，提出一种基于上行数据包时延的自适应多线程轮询算法（A M TP）。该算法中O LT依据上行数据包时延状况动态调整轮询周期内对O N U的带宽授权次数。仿真结果表明：与已有算法相比，A M TP算法具有较高的信道利用率、较低的上行数据包平均时延和时延抖动值。

关键词：长距离无源光网络；动态带宽分配；自适应；多线程轮询

0　引言

长距离无源光网络（LR-PON）将OLT与ONU之间距离扩展到100km甚至更远，导致往返时延高达1ms［1］，因此，在设计动态带宽分配算法（DBA）时应充分考虑传播时延的影响，尽可能减少信道空闲时间，以提高信道利用率［1，2］。

多线程轮询算法（MTP）［3，4］是针对LR-PON设计的经典DBA算法，其通过在OLT与ONU之间建立多个平行进程进行通信，可以提高信道利用率。固定线程数目的MTP无法很好适应网络负载变化，文献［5］提出一种根据网络负载动态改变轮询周期内对ONU授权次数的AMGAV算法，可以提高信道利用率。但是，AMGAV未考虑OLT收到Report消息至ONU收到Gate消息这段时间内可能有数据包到达ONU的情况。为此，文献［6］引入带宽预测机制，提出S-AMGAV算法，有利于尽快上传新到达ONU的数据包。但是该算法一个周期内ONU授权次数高达十几次，大大增加了控制开销。上述算法依据网络负载来调整轮询周期内使用线程数目，但是，网络负载仅反映一段时间内用户产生数据的平均情况，未能很好反映网络实时状况。考虑到网络数据流量的突发性，即使在高负载情况下也可能会有一些ONU处于轻负载状态。同样地，在低负载条件下也可能存在重负载ONU。上行数据包时延能较好反映网络中产生以及缓存数据包的情况。基于此，本文在继承上述算法优点基础上，进一步考虑突发业务特点以及网络负载分布不均和动态变化等特征，提出一种基于数据包时延的自适应多线程轮询算法（AMTP）。该算法在OLT端依据实时数据包时延动态改变轮询周期内线程数目，既能避免使用过多线程，减少控制开销，又能减少上行信道空闲时间，提高信道利用率。

1　算法描述

由于网络数据流量的突发性，网络中各个时刻产生数据包的数量是变化的。数据包产生速率越大，ONU缓存数据越多，上行数据包平均时延越大。为了改善时延性能，相应地需要增加线程数目。因此，可以根据上行数据包时延情况来动态改变轮询周期内为各个ONU进行带宽授权的次数。在AMTP算法中，OLT依据ONU上行数据包的平均时延值来动态调整每个轮询周期的线程数目，使用尽量少的线程来保证上行数据包平均时延维持在一个较低水平。在具体描述所提算法前，引入以下符号：N：ONU的个数；BWi，j：ONUi在线程j的带宽请求；B0：各个ONU的最小保证带宽；BWj：线程j所有ONU的带宽请求之和；Thnum：轮询过程中所使用的线程数目；Bscarity，j：线程j所有轻负载ONU节省带宽的总和；BW0：为各个ONU分配的初始化带宽；Bexces，j：线程j所有重负载ONU不足带宽的总和；R：上下行链路的传输速率；TG，j：OLT为线程j所有ONU进行带宽授权的时刻；Tth：线程融合阈值门限；TR，j：OLT收到线程j所有ONU的Report消息时刻；Gi，j：OLT在线程j为ONUi分配的带宽；Tg：连续两个ONU上行数据传输保护时间间隔。

算法具体描述如下：

算法首先为各个ONU的各个线程进行初始化带宽分配，分配的带宽为：

系统进入正常通信状态后，为防止重负载ONU独占上行信道，设置各个ONU的最大保证带宽B0= 15500字节［7］。将带宽请求小于等于、大于B0的ONU分别称为轻、重负载ONU，并将轻负载ONU节省下来的带宽按比例分配给重负载ONU［8］。线程j授权ONUi的带宽为：

与MTP算法［4］一样，AMTP算法可能也会出现线程融合问题［9］。为了克服线程融合问题，可以减少当前线程的部分带宽，然后将这部分带宽分配给下一线程中的ONU。即当BWjBWj+1≥Tth时，可将线程j中部分带宽分配给线程j+1的ONU。同时，若OLT对于线程j的带宽授权消息没有发送出去而线程j+1的带宽请求消息已到达OLT（即TG，j≥TR，j+1），并且BWj+1与BWj之和小于B0时，则将线程j+1的带宽请求在线程j进行带宽授权。这样在线程j+1报告的缓存数据在线程j就上传，可以降低这部分缓存数据的上行时延，全网数据包平均时延也会在一定程度上降低［9］。

国际电信联盟规定在100km范围内的接入网中，要使语音信息无失真地传给用户，需要保证其传输时延不超过1.5ms［7］。由文献［9］可知，即使是在高负载条件下，如果线程间采用合适的调度算法和适当的线程数目，仍然能保证网络中上行数据包时延低于1.5ms。在所提出的AMTP算法中，为了减少算法的复杂度，同时使用尽量少的控制信息以提高上行信道传输效率，算法规定每个轮询周期中最多使用3个线程。

在AMTP算法中，如果在一个最小保证带宽的时间范围内，收到的上行数据包时延都高于1.5ms，此时如果当前网络负载低于0.8且线程数目低于3，则可以继续增加轮询周期使用的线程数目（加1）；如果网络负载高于0.8，而且线程数目大于1，则应减少轮询周期使用的线程数目（减1）。另外，如果在一个最小保证带宽时间范围内，收到的所有上行数据包时延都低于1.5ms，同时所使用线程数目大于1，此时应减少使用的线程数目（减1）以减少控制开销，进一步提高上行信道利用率。

AMTP算法动态改变线程数目后，在下一轮询周期将按照更新后的线程数目为各个ONU进行带宽授权，并重复执行上述步骤。

2　计算机仿真及数据分析

本节利用OPNET软件搭建LR-PON仿真平台，对提出的AMTP算法进行仿真分析，并与MTP［4］、AMGAV［5］和S-AMGAV［6］三种算法进行比较。仿真网络包括1个OLT、1个光分路器和16个ONU，ONU到OLT的距离为100km左右，AMTP的初始线程数为1，各线程初始化带宽授权时间为0.3ms［4］，MTP算法的线程数固定为2，这是文献［4］综合考虑计算复杂度和数据包时延情况给出的最佳线程数。网络用户产生的上行数据业务服从H参数为 0.8的 Pareto分布，帧长为560bits，R=1Gb/s，Tg=5μs，Tth=5。仿真性能指标包括轮询周期内平均使用线程数、上行数据包平均时延、上行信道利用率和上行数据包时延抖动。

图1　轮询周期内平均使用线程数

图1给出了不同算法在一个轮询周期内平均使用的线程数随相对网络负载（网络中每秒产生数据的总比特数与R的比值［7］）变化的情况，可以看出：S-AMGAV算法的平均线程数随网络负载的增加逐渐减少，AMGAV和AMTP算法变化不大。AMGAV算法的平均线程数维持在7左右，而AMTP算法较小，平均线程数在1～2之间。这是因为：在S-AMGAV算法中，单位周期的线程数与网络中ONU的数目成反比，并且随着网络负载的增加逐渐减少。当网络中只有16个ONU且负载较低时，线程数接近20个。在AMGAV算法中，单位周期内OLT为各个ONU的授权次数（线程数）与各个ONU的带宽请求之和成反比，且不能超过8。因为授权次数为8的时间较多，所以AMGAV算法中不同负载下对各个ONU进行带宽授权的次数变化不大。在AMTP算法中，最大轮询线程数目设定为3，并且依据上行数据包时延动态调整，网络中线程数目为1和2的时间相对较多，平均授权次数在1～2之间，授权次数最少。

图2　不同算法上行数据包平均时延比较

图2比较了不同相对网络负载下上行数据包平均时延的变化情况，可以看出：无论网络负载如何变化，AMTP算法的上行数据包平均时延都低于另外三种算法。随着网络负载的增加，4种算法的上行数据包平均时延都逐渐增大，而AMTP算法增加较为缓慢。当网络负载低于0.5时，MTP算法的上行数据包平均时延高于S-AMGAV和AMGAV算法；当网络负载高于0.5时，MTP算法的上行数据包时延低于AMGAV算法，但是与S-AMGAV算法比较接近。这是因为AMTP算法采用动态轮询周期时间，轮询周期随着网络负载的变化动态调整，使用的线程数目也随着上行数据包平均时延的变化而动态变化，可以保证上行数据包平均时延维持在低于1.5ms内。在网络负载较低时，SAMGAV和AMGAV算法能够给各个ONU进行更多次授权，各个ONU也有更多机会上传数据，所以时延性能比MTP算法好；当网络负载相对较高时，AMGAV算法给各个ONU的授权次数仍然多于MTP。由于此时ONU缓存的上行数据较多，而授权次数多意味着控制开销大，相应地用于传输数据的带宽较少，可能导致较多数据包不能及时上传，因而AMGAV算法的时延大于轮询次数较少的MTP算法。

图3　不同算法的上行信道利用率比较

图3比较了不同相对网络负载下4种算法上行信道利用率的变化情况，可以看出：不论是高负载还是低负载条件下，AMTP算法的信道利用率都明显高于其它算法。当网络负载低于0.5时，MTP算法的信道利用率稍低于S-AMGAV以及AMGAV算法。当网络负载高于0.5时，结果刚好相反。这是因为：AMTP算法解决了多线程轮询算法存在的线程融合和重复授权问题，同时能够根据网络中上行数据包时延情况动态改变所用线程数目，可以提高上行带宽利用率。MTP算法采用固定的轮询次数，不能根据网络中数据包时延的情况做出调整，尤其是在低负载条件下，各个ONU进行数据上传的机会固定不变，而各个ONU中缓存的数据包数量以及数据包到达ONU的时间不确定，导致ONU内缓存的数据包可能会错过仅有的2次上传机会，上行信道在一段时间内将处于空闲状态，信道利用率降低。虽然当网络负载较大时，MTP算法的信道利用率越来越接近AMTP，但是仍然低于AMTP算法。这是因为：当网络负载较大时，网络中平均每个时刻产生的数据包较多，需要传输的上行数据包也比较多，上行信道可能一直处于传输数据的状态，利用率比较高。虽然如此，MTP算法线程数固定为2，而AMTP算法在负载较高时，所使用线程数目为1的时间较多，控制消息相对较少，所以信道利用率高于MTP算法。当网络负载较低时，MTP算法的信道利用率低于S-AMGAV和AMGAV算法，这是因为在SAMGAV和AMGAV算法中，OLT可以对各个ONU进行更多次授权，各个ONU也有更多的机会进行数据上传。当网络负载增大时，由于MTP算法采用线程数固定为2，而在S-AMGAV和AMGAV算法中，一个周期内OLT对ONU进行带宽授权的次数仍然较多，控制消息的增加会占用更多的信道带宽，造成信道利用率低于MTP算法。

图4　不同算法的上行数据包时延抖动比较

图4比较了不同算法的上行数据包时延抖动随相对网络负载变化的情况。上行数据包时延抖动反映了网络中各个ONU缓存数据包的时延变化情况。从图4可以看出：无论网络负载如何变化，AMTP算法的包时延抖动都低于MTP算法。当网络负载低于0.5时，AMTP算法的包时延抖动大于S-AMGAV和AMGAV算法；当网络负载高于0.5时，AMTP算法的包时延抖动小于S-AMGAV和AMGAV算法。这是因为：在网络负载较低时，ONU中缓存的数据包较少，而S-AMGAV 和AMGAV算法使用的线程数目相对较多，数据包在各个线程内都能被及时发送出去，由此数据包时延差别较小。在网络负载较高时，AMTP中可以根据时延值的变化调整使用的线程数目，使所有数据包平均时延都维持在较低的范围内。MTP使用固定数目的线程，不能根据网络条件的变化做出调整，网络负载大时，ONU中可能缓存了几个周期的数据，也可能存在刚到达的数据，因此，时延抖动较大。S-AMGAV算法随着网络负载的增加，单位周期内对各个ONU授权的次数逐渐减少，在网络负载较大时接近AMTP算法对各个ONU授权的次数，因此，包时延值大小差不多，时延抖动也比较接近。但是在AMGAV算法中，当网络负载较高时，单位周期内OLT对各个ONU进行带宽授权的次数仍然较多，这样会因为控制消息的增多而使传输数据的带宽减少，可能导致ONU内缓存数据包增多，上行数据包平均时延差异大，包时延抖动最大。

3　结束语

MTP算法使用固定的线程数，无法适应网络负载的动态变化，AMGAV和S-AMGAV算法虽然可以依据网络负载动态调整轮询周期内的线程数，但是一个周期内对各个ONU进行带宽授权的次数较多，增加的控制消息和线程切换过程都会延缓上行数据的传输，同时也增加了计算的复杂度。本文提出的AMTP算法根据网络中数据包时延的变化情况，自适应调整轮询周期的线程数目，是一种更灵活和适应性更强的DBA算法。仿真结果表明：与已有算法相比，AMTP算法尽可能减少每个轮询周期内使用的线程数目，能够提高上行信道利用率，降低上行数据包平均时延和数据包时延抖动。

参考文献：

［1］SONG H，KIM B-W，MUKHERJEE B.Long-Reach Optical Access Networks：A Survey of Research Challenges，Demonstrations，and Bandwidth Assignment Mechanisms［J］.IEEE Commun.Surv.Tut.，2010，12（1）：112-123.

［2］KANTARCI B，MOUFTAH H T.Bandwidth Distribution Solutions for Performance Enhancement in Long-Reach Passive Optical Networks［J］，IEEE Commun.Surv.Tut.，2012，14（3）：714-733.

［3］HELMY A，FATHALLAH H，MOUFTAH H.Interleaved Polling Versus Multi-Thread Polling for Bandwidth Allocation in Long-Reach PONs ［J］.IEEE/OSA J Opt.Commun.Netw.，2012，4（3）：210-218.

［4］SONG H，KIM B-W，MUKHERJEE B.Multi-Thread Polling：A Dynamic Bandwidth Distribution Scheme in Long-Reach PON［J］.IEEE JSAC，2009，27（2）：134-142.

［5］DIXIT A，DAS G，LANNOO B，et al.Adaptive multi-gate polling with void filling for long-reach passive optical networks［C］.Intern.Conf.on Transparent Optical Netw.（ICTON），Stockholm，IEEE Press，2011：1-4.

［6］DIXIT A，LANNOO B，COLLE D，et al.Synergized-adaptive multi-gate pollingwithvoidfilling：Overcomingperformancedegradationin LR-PONs［J］.IEEE/OSA J Opt.Commun.Netw.，2015，7（9）：837-850.

［7］KRAMER G，MUKHERJEE B，PESAVENTO G.Interleaved Polling with Adaptive Cycle Time（IPACT）：A Dynamic Bandwidth Distribution Scheme in an Optical Access Network［J］.Photonic.Netw.Commun.，2002，4（1）：89-107.

［8］朱婉莹，何荣希，杨帅.EPON中节能动态带宽分配算法［J］.光通信技术，2014，38（11）：35-38.

［9］AHMED J，CHEN J，WOSINSKA L，et al.Efficient inter-thread scheduling scheme for long-reach passive optical networks［J］.IEEE Commun.Mag.2013，51（2）：35-43.

中图分类号：TN929.18

文献标识码：A

文章编号：1002-5561（2016）06-0021-04

DOI：10.13921/j.cnki.issn1002-5561.2016.06.006

收稿日期：2016-01-22。

基金项目：国家自然科学基金资助项目（61371091）资助。

作者简介：张清玲（1990-），女，硕士生，主要研究方向为光网络。

Adaptive multi-thread polling algorithm for long distance passive optical networks

ZHANG Qing-ling，HE Rong-xi
（College of Information Science and Technology，Dalian Maritime University，Dalian Liaoning 116026，China）

Abstract：In this paper，a packet delay based adaptive multi-thread polling algorithm （AMTP）has been proposed for a long reach passive optical network（LR-PON）which has large coverage and considerable propagation delay.AMTP can adjust the number of polling thread dynamically according to the average delay of the received packets.Simulation results show that the proposed algorithm can achieve higher channel utilization and lower packet delay，as well as decreased packet delay jitter compared with the existing algorithms.

Key words：LR-PON，dynamic bandwidth allocation（DBA），adaptive，multi-thread polling