支持QoS的两种新型带宽分配算法

支持QoS的两种新型带宽分配算法
文献[1]中提出的间插轮询算法采用了可变的授权周期，因此不适合对延时和延时抖动敏感的实时业务。为了解决此类问题，文献[2]中提到了一种固定时隙分配 (Fixed Slot Allocation, FSA)算法，然而固定时隙分配带来的弊端是：轻负载时大部分光网络单元(Optical Network Unit, ONU)的带宽浪费明显，上行信道利用率很低。而在重负载时ONU之间又不能形成带宽共享，给高优先级业务的时延和各业务优先级的队列带来消极影响。鉴于此，本文在对间插轮循算法做出相应改进的基础上，提出了两种全新的支持多业务服务质量(Quality of Service, QoS)的EPON上行信道动态带宽分配算法：单级授权混合发送算法(Single-level Grant Merged Transmission Allocation, SGMTA) 和多级授权分离发送算法(Multiple-level Grant Separated Transmission Allocation, MGSTA)。
1.1 帧结构
考虑到EPON对IEEE802.3所定义的以太帧结构的兼容性，所设计的两种算法共涉及到三种类型的帧：数据帧(DATA)，授权帧(GRANT)和请求帧(REQUEST)。其中数据帧仍然沿用IEEE802.3中的帧结构，不做任何改变。而对于授权帧和请求帧，为了节约下行链路的带宽，决定采用64 B的最小以太帧，具体格式分别如图1和图2所示，从图中看出，Preamble为前导码，SFD为定界符，DA为目的地址，SA为原地址，Type表示以太网类型域。从Subtype开始，请求帧各字段定义如下：Subtype 用于区分数据帧，授权帧和请求帧；Timestamp 用于光线路终端(Optical Line Termination, OLT)和各ONU之间往返时间值的测定；Req_EF和Req_BE分别用于各ONU向OLT请求高优先级业务EF和低优先级业务BE的授权；Reserved/Data字段保留作为以后多优先级业务的扩展或附带传送数据；FCS为校验字段。授权帧的Sendtime_BE字段为授权ONU的低优先级业务BE发送时间，Grant_EF和Grant_BE 分别为OLT向授权ONU分配的高优先级业务EF和低优先级业务BE的传送窗口。

图2 授权帧格式
1.2 SGMTA带宽动态分配算法
SGMTA算法是一种主要基于ONU端设计的多优先级动态带宽分配方案。其步骤如下：
1) OLT依据授权表向各ONU发送带宽授权。授权主要包括两部分信息：所授权ONU的标识和授权窗口的大小。此处的授权窗口是指ONU请求的各优先级窗口大小之和。
2) ONU在用户数据到来时按照ONU端的优先级处理策略先将数据按其优先级缓存在相应的队列中，并为高优先级队列中的数据进一步设置子优先级：sub_priority=(t_wait+t_service)/t_service, 其中t_wait为该数据包在队列中已等待的时间，t_service为该数据包所要求的传送时延。所有数据等到授权到来时再统一发送。
3) OLT的授权帧到达ONU后，ONU读取授权窗口，并根据窗口大小立即发送数据。发送策略为：先发送高优先级的EF数据，发送时按照其子优先级的大小依次发送。当高优先级队列为空或是已发数据等于上轮申请的窗口时，停止发送。接着ONU利用授权中的剩余带宽继续发送低优先级业务，直到授权窗口用完为止。发完数据后，ONU附带发送请求帧，其内容包括当前各优先级的队列情况以及相应的Timestamp值。
4) OLT在向ONU发送授权的同时接受ONU的数据和请求。数据交上层处理，请求则根据其内容更新授权表。为进一步增加位于上轮请求和本轮授权之间到达的高优先级业务的发送机会，可在当前高优先级业务的授权窗口上附加一个补充窗口(supply_window)，作为下轮高优先级业务的带宽预分配。同时为保证公平性，OLT为各ONU设置相应的最大授权窗口Wmax。
5) 完成本轮轮询和收到各ONU请求的基础上，OLT根据更新后的授权表开始新一轮轮询。通过分析，发现了SGMTA算法在继承了光线路终端(Optical Line Termination, OLT)算法充分利用上行信道和避免同步与测距威廉希尔官方网站 等优点的同时，对高优先级的EF业务采取了“一有授权，优先发送”，“预先分配附加窗口”和“细分子优先级”等策略，使得高优先级业务在SGMTA算法中享有较好的时延特性，同时对于低优先级BE业务，也会保证其申请的传输带宽，避免其发送机会被EF业务强行占用，进而导致其缓冲队列的不稳定增长。
1.3 MGSTA带宽动态分配算法
MGSTA算法是一种主要基于OLT端设计的多优先级动态带宽分配方案。在阐明这一算法之前，先来分析一下SGMTA算法中存在的两点不足：1) 在SGMTA中各ONU的高优先级业务(EF)是间隔在不同ONU低优先级业务(BE)之间进行传送的。这样当各ONU的BE业务比较繁忙时，SGMTA的整个轮询周期就会加大，各ONU的EF业务的发送间隔也会相应的增长。2) 由于请求帧是在低优先级业务发送完毕时附带发送的，因此当OLT开始下一次轮询时，距离上轮第一个被轮询到的ONU所报告带宽请求时刻已经相隔了较长的一段时间。而在这段时间内达到的EF业务数据在本轮授权中并没有被申请，其发送机会仅依赖于OLT端根据预测分配的附加窗口，其准确程度有限。
为了解决以上问题，在SGMTA算法改进的基础上提出了MGSTA动态带宽分配方案，其主要改动部分如下：
1) 整个轮询周期根据业务的优先级划分为多个轮询子周期。各轮询子周期的安排顺序遵照其对应的业务优先级高低，高优先级业务先轮询，低优先级业务后轮询。
2) 对OLT的授权机制进一步细分，由SGMTA算法中的整体授权改为针对不同优先级的分级授权。
3) 考虑到节约下行链路带宽，OLT对ONU的多优先级业务授权仍封装在一个授权帧中。各ONU接收到授权后，立即发送高优先级业务，同时获取下一个低优先级业务的发送时间。
4) 在低优先级的发送窗口内增加“带内开窗”机制，为高优先级业务在同一轮询周期内提供多次发送机会。同时, 请求帧仍然附加在最后一个优先级业务发送完成之后进行。

2 仿真结果和性能分析
为了验证SGMTA算法和MGSTA算法的可行性，进行了仿真实验。实验中所用到仿真参数设置如下(FSA, SGMTA和MGSTA算法的仿真参数相同)：ONU的个数：16；优先级的设置：高优先级：EF，低优先级：BE；OLT到ONU的距离：10～20 kｍ；上下行链路速率：1 Gbps；业务源：Paerto和Poisson；帧长：64～1518 B；保护时间：1 μs；ONU最大分配窗口：15 000 B。
为了更好地interwetten与威廉的赔率体系 实际EPON中的数据源，在仿真中采用了具有自相似性(self-similarity)和长相关性的突发数据源和具有泊松(Poisson)分布的数据源叠加而成。其中高优先级业务占整个网路负载的20％，低优先级业务占80％。整个仿真模型考虑了数据的排队延时Tq，发送延时Ts和链路传播延时Tp。
图3为测定了高优先级业务EF在FSA，SGMTA和MGSTA三种算法下端到端时延d随网络负载l改变的情况。所不同的是：图3a为在高优先级业务源负载恒定的情况下测出的，图3b中的EF业务源则随着网络负载增加而增加，但与低优先级业务比例始终维持一定。通过比较，发现在两种测试条件下，MGSTA和SGMTA分配算法均比FSA算法体现出更小的时延以及更平稳的时延变化。在满负载或超负载时，FSA的EF时延约为MGSTA的2.5～3倍, SGMTA的1.2～1.5倍。 这是由于MGSTA和SGMTA算法在设计的思想中分别采用了“多级授权，分离发送”，“预分带宽，带内开窗”和“细分子优先级”等机制为高优先级业务尽可能多的提供了发送机会。
图4为FSA，SGMTA和MGSTA算法下ONU处的队列尺度b改变的情况，图4a给出了两种算法相对于FSA算法的高优先级业务的队列尺度b，可以看到其变化趋势与各自算法的时延特性基本一致。MGSTA算法中高优先级业务的及时传递，必将导致相同负载下其较小的队列长度和较稳定的增长变化。图4b则表明了ONU处所需的缓冲区大小，发现即使在MGSTA算法允许高优先级业务抢占低优先级业务发送带宽的情况下，其总共所需的缓冲空间仍小于SGMTA算法。原因为：1) MGSTA算法中为各ONU预先分配了一个附加窗口，使高优先级业务不会耗尽低优先级业务的发送带宽。2) 在允许高优先级抢占低优先级带宽的同时，也允许低优先级在没有高优先级业务时利用附加窗口发送，使得带宽分配更为灵活。

(a) 高优先级业务EF的平均队列尺度 (b) ONU的缓冲区大小
图4 FSA, SGMTA和MGSTA算法下ONU处的队列情况

支持QoS的EPON上行动态带宽分配算法设计