杨 臻，程红霞，邱保志

(1.郑州师范学院 信息科学与技术学院，河南 郑州 450044；2.郑州大学 信息工程学院，河南 郑州 450002)

0 引 言

随着互联网和计算机技术的飞速发展，用户对带宽的需求越来越高。虽然主干网和局域网的基础设施也有非常快的发展(如10Gbit以太LAN)，但随着大量用户访问远程资源，接入网就降低了用户总的网络容量[1]。在早期的互联网中，业务流量主要是由纯文本网页和图片构成，只需有限的带宽容量就可完成。然而，现在大多数通过互联网传输的流量是由点对点文件、视频共享、在线实时游戏、视频流、视频点播、教育、IP电话和IPTV等构成。这些应用在接入网侧需要更多的带宽，而且某些应用在包时延变化(packet delay variation，PDV)、丢包率和端到端时延等服务质量方面还有要求。为了满足这些应用在服务质量方面的要求，服务提供商也在研究并不断推出新的接入网技术，如提出了光纤到户(fiber-to-the-home，FTTH)体系结构[2]。最受欢迎的FTTH体系结构便是无源光网络(passive optical network，PON)结构，由于其底层设施中只有无源光单元，能够实现低成本、高带宽数据传输和远程接入等，因此它在光纤接入构架中具有最好的经济性。在PON的下行方向，数据包在PON的中心局侧广播，即光线路终端(optical line terminal，OLT)；在用户侧，即光网络单元(optical network unit，ONU)收集数据包并发送给用户；在上行方向，由于众多ONU通过单一光纤线路连接到OLT，故必须采用多址接入技术来克服拥塞状况。在PON中，主要采用两种多址接入技术：时分多址(time division multiple access，TDMA)和波分多址(wavelength division multiple access，WDMA)；在TDMA技术中，在网络侧有两个主要的标准。一个是吉比特PON(gigabit PON，GPON)，由ITU-T制定；另一个是以太PON(ethernet passive optical network，EPON)，由IEEE 802.3ah工作组制定。

较易实现和低成本使得EPON比GPON在学术研究领域和工业界更受欢迎，所以关于提高EPON的性能如接入容量和服务质量的研究引起了人们的广泛关注，如EPON中的带宽分配就是其中重要的研究方向之一。

EPON中的带宽分配算法包括静态的和动态的。在静态分配算法中，OLT把固定大小不变的传输窗口分配给每个ONU，无需考虑每个ONU的流量要求；而在动态分配算法中，把大小可变的传输窗口动态地分配给不同的ONU，需要考虑每个ONU的流量要求。OLT和ONU之间的通信是通过多点控制协议(multipoint-control protocol，MPCP)来完成的。

针对EPON已提出了多种动态带宽算法(dynamic bandwidth allocation，DBA)。早期的动态带宽分配解决方案是由Kramer G.等提出的“具有自适应周期时间的交叉轮询”(interleaved polling with adaptive cycle time，IPACT)算法[3]，也称为在线DBA，IPACT算法的最好变体就是采用最大窗口限制技术。在IPACT算法中，OLT以交叉方式逐个地发送GATE消息给ONU，无需等待其它ONU的下一个REPORT消息的到达。如果增加最大窗口尺寸，就可能导致ONU本地缓存器中数据包更长的等待时间；相反，如果减小窗口尺寸，又会导致更多的GATE和REPORT被传输，从而给系统带来额外开销；针对高负载ONU的公平带宽分配，文献[3]提出了另一种DBA算法，即基于交叉轮询停止(interleaved polling with stop，IPS)的DBA，也称为离线DBA。在该算法中，OLT在开始发送GATE消息给下一个周期的ONU之前，要等待来自全部ONU在每个周期的REPORT消息。这样，OLT在开始为ONU分配带宽之前，就可以知道全部ONU的总带宽请求。因此，OLT就可以在高负载ONU之间公平地分配剩余带宽。然而，离线DBA在上行信道插入了一个空闲时间Ttidle，Ttidle由算法的计算时间和OLT与ONU之间的往返时间(round trip time，RTT)(假设全部ONU有相同的RTT)构成。

(1)

(2)

式中：Ri为第i个ONU请求的带宽。之后，把在当前周期里还没有分配的剩余带宽公平地在全部高负载ONU之间进行分配。

文献[3]针对EPON提出了一种基于动态带宽分配的智能模糊逻辑的延迟性能(intelligent fuzzy logic based dynamic bandwidth allocation，IFLDBA)算法，并从仿真的角度将IFLDBA与其它一些著名的算法的时延和带宽利用率进行了比较。评估结果表明，IFLDBA能显著改善数据包延迟和带宽利用率。文献[4]提出了一种高效节能的DBA算法，同时保证基于上游和下游方向的带宽请求的网络性能。文献[5]针对EPON提出了一种DBA，如果在当前周期中没有轻负载存在，就可以通过选择一个高负载ONU来提高空闲时间的利用，而且算法根据ONU的流量负载将轻负载ONU置入睡眠模式，以使高负载ONU充分利用其空闲时间。文献[4,5]的算法都是基于解决离线DBA中的空闲时间问题而提出，但算法改变了ONU服务顺序，从而可能导致PDV。同时算法要发送额外控制消息，这又会造成额外的开销，用来减小ONU本地缓冲器中的包时延算法是队列大小预测算法[6,7]。如果一个ONU能够预测它在下一个周期的缓冲器大小，则它就请求必需的带宽而无需等待一个周期时间。然而，本地流量源的突发性以及不准确的队列大小预测也会造成带宽浪费。文献[8]针对目前WDM-EPON中带宽分配和接入存在的问题，提出了一种低成本保护结构及动态资源分配算法，目的是降低WDM-EPON的接入成本和提高传输效率。文献[9]研究了多信道波分复用/时分复用混合以太网无源光网络系统的上行波长带宽分配算法，将问题映射到调度理论中的并行多处理器模型进行分析，考虑了实际网络中传播时延的多样性对波分复用以太网无源光网络带宽分配的影响，提出了支持抢先机制的基于最短传播时延/最长剩余处理时间混合调度策略的改进调度算法，提高了信道资源的利用率。文献[10]提出了一种适用于多业务EPON的上行带宽分配算法——周期和准周期结合的动态带宽分配算法，算法针对以太网业务和话音业务的特性，分别采取准周期同步轮询动态带宽分配和周期固定带宽分配机制，算法提高了系统带宽利用率和带宽分配的公平性。

通过以上关于EPON的动态带宽算法的分析，本文提出了一种介于在线DBA和离线DBA算法之间的中间算法。算法基于交叉轮询停止并对上行信道中的传输采用不同的周期定时控制，即根据上行信道负载情况工作在两种模式：在低负载时，算法切换到在线DBA模式，类似于IPACT算法；在高负载时，切换到离线DBA模式，这样既能消除离线DBA算法中存在的空闲时间，同时又能实现剩余带宽公平地在全部高负载ONU之间的分配，从而最大限度地提高带宽利用率。工作模式的切换分别根据传入给OLT的上行带宽请求。

1 本文提出的DBA算法

1.1 算法原理

如果在空闲周期开始时间与空闲周期长度Tidle(Tcomputation+RTT)同步之前，OLT能够知道来自于全部ONU的带宽需求，则在上行信道中就可以发送GATE消息而没有任何空闲时间。为了发送GATE消息，如果超过一半的ONU在最后一个门控ONU之后报告它们的带宽请求，则OLT计算出分配给一半ONU的带宽数量，而不是轮询表中的全部ONU；否则，OLT直接发送一个GATE消息给轮询表中的下一个ONU，这时OLT处于在线DBA模式，直到报告的ONU数量超过总数的一半。当报告的ONU数量超过总数的一半时，OLT开始启动离线DBA模式，并在ONU之间公平分配带宽；当OLT不能收集到足够的REPORT信息时，算法切换到在线DBA模式。如果ONU的时隙时间很短，则上行信道就是低负载的。因此在在线模式下，不必考虑公平分配，因为系统有一个周期时间小于所需的周期时间限制。

1.2 算法实现

从算法原理可见，算法需要前一个周期的请求和带宽分配信息，对最后一个门控ONU和最后一个报告的ONU都必须即时监测。由于算法对一个周期中的ONU服务顺序不会改变，因此，最后一个门控ONU和最后一个报告的ONU可以简单地通过轮询表来监测。在线和离线模式之间的切换根据GATE定时器失效时来自于最后一个门控ONU所报告的ONU数量。这个参数与周期时间、请求的窗口尺寸和ONU的RTT有关。如果有一半的ONU的窗口尺寸非常小，则它们的服务时间就可能小于RTT。这样，当GATE定时器失效时，如果分配的总窗口尺寸不大于数据包的RTT，则OLT就无法收集到足够的REPORT来计算新的半周期。

现在需要考虑的是离线模式下的EBD。本文采用类似于离线DBA算法中的EBD，但OLT仅用K个REPORT消息而不是全部N个REPORT消息，对于(N-K)个节点，OLT还没有接收到其带宽请求。在EBD算法中，把ONU分为2组：已报告的和未报告的，算法需要全部ONU的请求来公平地分配带宽。对于那些报告还没有到达OLT的ONU，所需信息将基于其先前周期生成。

本文采用的剩余带宽计算与离线DBA算法不同。我们把要研究的一个周期分为两个半周期。在半周期中，可用剩余带宽不能仅用当前半个周期中的ONU的请求来测量。为了把剩余带宽公平地分配给全部ONU，OLT也要考虑在前半个周期被服务的ONU的带宽请求。来自于最后报告信息的K个ONU的剩余带宽由式(3)计算，N-K个ONU的剩余带宽，即来自于保存在轮询表中先前报告信息的N-K个ONU的未使用的带宽由式(4)计算

(3)

(4)

(5)

如果K个节点中每个节点的剩余带宽数量小于K个节点总的剩余带宽，算法就把K个ONU的总的剩余带宽标记为可用，反之，则意味着在前半个周期中的ONU是过载的。在这种情况下，算法将考虑PON中全部ONU的总需求，把可分配的剩余带宽分配给当前半个周期，以使前一个周期中的ONU在下一个周期有更多的剩余带宽；此外，如果来自于前半个周期的N/2个ONU有未使用的剩余带宽，则把这个未使用的剩余带宽值也加到剩余带宽中。这样，算法就可以在每个半周期里确保公平分配。

(6)

2 算法性能评价

为了表明本文所提出的DBA算法的性能，考虑一个由16个ONU通过一个无源耦合器连接到一个OLT构成的EPON接入网，耦合器和OLT之间、以及ONU和耦合器之间的距离大约为10 km。然后来比较3种算法在1Gbps和10Gbps的EPON上行信道两种情况下单业务流量源和多业务流量时的字节丢失率和平均接入时延性能；单业务流量源采用恒定比特率(constant bit rates，CBR)的单一流量源，多业务流量源采用泊松帕累托突发过程(Poisson Pareto burst process，PPBP)的多业务流量源，即Pareto分布ON-OFF流量源；仿真在离散事件网络仿真工具NS2中进行。

图1为字节丢失率比较曲线。从图1(a)可见，在单

图1 3种算法的字节丢失率比较

业务流量源时，只有离线DBA算法在流量负荷超过0.9时存在字节丢失，而本文提出的DBA算法和IPACT算法均不存在字节丢失。这说明离线DBA算法相比于本文提出的DBA算法和IPACT算法有更差的带宽利用率；从图1(b)可见，在多业务流量源时，3种算法在1Gbps时均存在字节丢失，但在相同大小负荷情况下，本文提出的DBA算法的字节丢失率最低，而且出现在流量负荷超过0.8以后，而离线DBA算法在流量负荷为0.7以后就出现字节丢失，而从图1(c)可见，3种算法在10Gbps时只有离线DBA算法和IPACT算法存在字节丢失，而本文提出的DBA算法无论流量负荷多大时都不存在字节丢失，说明本文提出的DBA算法在字节丢失率方面有最好的性能。

图2为1 Gbps和10 Gbps时单业务流量源时的平均接入时延。可以看出，本文提出的DBA算法和IPACT算法要优于离线DBA算法；而且对于3种算法，在低负荷时的平均接入时延都小于1 ms。当负荷增加时，平均接入时延也增大，但本文提出的DBA算法仍能得到更好的平均接入时延性能。

图2 单业务流量源时的平均接入时延比较

图3为1 Gbps和10 Gbps时多业务流量时的平均接入时延。可以看到，本文提出的DBA算法和IPACT算法的平均接入时延在所有负荷值时都在1 ms以下，但本文提出的DBA算法仍然比IPACT和离线DBA算法能够获得更好的平均接入时延性能，这是因为如果其它ONU有较低带宽请求而有剩余带宽存在时，本文提出的DBA算法可以提供更多的带宽给高负载的ONU。

图3 多业务流量源时的平均接入时延比较

3 结束语

本文提出了一种介于离线DBA和在线DBA之间的动态带宽分配算法。算法既能消除离线DBA算法中存在的空闲时间问题，同时又能实现离线DBA算法的公平EBD；算法在两个半周期里分配剩余带宽，并根据每个周期时间里的流量负荷切换到在线DBA模式；通过单业务流量源和多业务流量源在1Gbps和10Gbps上行信道带宽速率下的仿真结果表明，本文所提出的DBA算法在字节丢失率和平均接入时延性能方面都有明显提高。

[1]Mercian A,Mcgarry M P,Reisslein M.Impact of report message scheduling (RMS) in 1G/10G EPON and GPON[J].Optical Switching & Networking,2013,12(3):1-13.

[2]Rawshan F,Park Y.Architecture of multi-OLT PON systems and its bandwidth allocation algorithms[J].Photonic Network

Communications,2013,25(2):95-104.

[3]Radzi NAM,Din NM,Al-mansoori MH,et al.Analysis of delay performance on the intelligent fuzzy logic dynamic bandwidth allocation algorithm[J].Arabian Journal for Science and Engineering,2013,38(9):2367-2374.

[4]Li C,Guo W,Hu W,et al.Energy-efficient dynamic bandwidth allocation for EPON networks with sleep mode onus[J].Optical Switching & Networking,2014,15:121-133.

[5]Dixit A,Lannoo B,Colle D,et al.Energy efficient dynamic bandwidth allocation for Ethernet passive optical networks:Overview,challenges,and solutions[J].Optical Switching & Networking,2014,18(2):169-179.

[6]Hedayati AR,Fesharaki MN.Parnian:A two-stage neste-dauction for dynamic bandwidth allocation in Ethernet passive optical networks[J].Iranian Journal of Science & Technology Transaction B Engineering,2011,35:45-61.

[7]Lai chia-lin,Lin hui-tang,Chiang hung-hsin,et al.Design and analysis of a frame-based dynamic bandwidth allocation scheme for fiber-wireless broadband access networks[J].IEEE/OSA Journal of Optical Communications and Networking,2014,6(5):486-500.

[8]ZHAO Haijun,LI Min,CUI Mengtian,et al.A sort of dynamic resource allocation algorithm based on low cost protective framework in WDM-EPON[J].Journal of Yunnan University(Natural Sciences),2012,34(6):658-663(in Chinese).[赵海军,李敏,崔梦天,等.WDM-EPON中基于低成本保护结构的一种动态资源分配算法[J].云南大学学报(自然科学版),2012,34(6):658-663.]

[9]SHUAI Qianjun,ZHU Weijia,YAN Jinyao,et al.Heterogeneous propagation delay of dynamic bandwidth assignment for WDM/TDM EPON[J].Journal of Beijing University of Posts and Telecommunications,2013,36(5):90-95(in Chinese).[帅千钧,朱维嘉,颜金尧,等.WDM/TDM EPON 传播时延的动态带宽分配算法[J].北京邮电大学学报,2013,36(5):90-95.]

[10]ZHANG Yang,CHEN Lei,HUANG Xiang,et al.Multi-services bandwidth assignment algorithm in EPON[J].Journal of Beijing University of Posts and Telecommunications,2013,27(5):90-93(in Chinese).[张洋,陈雷,黄翔,等.多业务EPON动态带宽分配算法[J].北京邮电大学学报,2013,27(5):90-93.]