一种改进的基于流量预测的动态带宽分配算法
开篇：润墨网以专业的文秘视角，为您筛选了一篇一种改进的基于流量预测的动态带宽分配算法范文，如需获取更多写作素材，在线客服老师一对一协助。欢迎您的阅读与分享！
摘 要:介绍了一种基于流量预测的上行带宽动态分配算法(PDBA)。PDBA算法根据短相关业务(SRD)和自相似、长相关业务(LRD)的流量特征建立了不同的线性预测模型,并在流量变化较快时放弃预测,以减小带宽浪费;同时,在光网络单元中提出一种配合预测机制的公平调度策略。仿真表明PDBA算法比DBAM算法在端到端延时、丢包率等方面有明显改善。
关键词:以太无源光网络;动态带宽分配;流量预测;服务质量;公平性
中图分类号: TP393
文献标志码:A
Improved DBA algorithm based on traffic prediction
ZHENG Yu,LI Guangjun,QIAN Yuping
School of Communication and Information Engineering, University of Electronic Science and Technology of China, Chengdu Sichuan 610054, China
)
Abstract: PDBA based on traffic prediction was presented, which established different linear prediction models for the ShortRange Dependence (SRD) and SongRange Dependence (LRD) traffic and drop prediction to reduce the bandwidth waste when the variation of traffic was rapid, while Optical Network Unit (ONU) used a new local fair scheduling policy adapted to the prediction strategy. The simulation result shows that endtoend delay, and packet loss rate has been improved obviously, compared with DBAM algorithm.
Key words: Ethernet Passive Optical Network (EPON); Dynamic Bandwidth Allocation (DBA); traffic prediction; Quality of Service (QoS); fairness
0 引言
目前,基于以太网的无源光网络(Ethernet Passive Optical Network,EPON)由于带宽资源丰富、价格低廉、协议简单、实施方便等优点被认为是解决接入网“最后一公里”的重要方案[1]。图1是EPON的典型网络拓扑。
图片
图1 EPON的典型网络拓扑
由图1所示,整个网络由光线路终端(Optical Line Terminal,OLT)、光网络单元(Optical Network Unit,ONU)和光分配网络(Optical Distribution Network,ODN)三部分组成。OLT放在中心局端,提供光/电转换、带宽分配和控制各信道的连接,并有实时监控、管理及维护功能(OAM);ONU位于用户侧,采用以太网协议,实现以太网第二层第三层交换功能。ODN是一个无源光器件,用于广播下行数据和集中上行┦据。
由于ONU共享上行信道,为避免冲突并提高带宽利用率,国内外学术界对动态带宽分配算法(Dynamic Bandwidth Allocation,DBA)展开了大量研究。2002年Kramer等人首先提出可变周期交织轮询算法(IPCAT),轮询ONU缓冲区内待发数据长度,根据一定策略分配上行时间窗口[2-3]。预测各优先级业务的上行流量提前分配带宽,使当前周期(T周期)报告帧以后到达ONU的数据帧能够在下一周期(T+1周期)直接发送,而无需等到T+2周期(T+2排队延时),是一种改善EPON系统QoS的重要手段[4-7]。文献[5]提出了一种基于上述思想的典型算法(DBAM),核心内容是OLT估计每种优先级业务的流量,根据用户等级协议和每种优先级业务对上行延时的不同要求分配上行带宽,Щ航狻T+2”排队延时问题,提高QoS性能。然而,DBAM的缺点是:1)预测方法比较粗糙,没有考虑平稳的短相关业务和突发性很强的长相关业务的流量特征,以提高预测精度。2)在ONU中缺乏相关机制降低预测失准导致的带宽浪费。
本文改进了DBAM的上述缺陷,提出了一种满足QoS要求和公平性的DBA算法(PDBA)。该算法针对各种业务流量的特点采用了比DBAM算法更准确的流量预测方法,并在ONU中使用了更有效的调度策略提高带宽利用率。
1 PDBA算法
1.1 改进的流量预测和带宽分配的数学模型
根据对时延的不同要求,可将业务划分为延时敏感的加速转发型业务(EF),优先级最高;对延时不敏感但需要保证带宽的保证转发型业务(AF),优先级次之;对延时和带宽都无要求的尽力而为业务(BE),优先级最低。
图1中的OLT和ONU通过报告帧(report)和授权帧(grant)完成信息交互,过程如图2所示。
图片
图2 OLT授权帧和ONU报告帧交互
ONUiг谏闲写翱诮崾时将缓冲区内积压的各种业务的数据包长度作为带宽申请值装入报告帧发送给OLT,OLT根据该值和DBA算法计算出下一轮的上传窗口大小和起始时间,Р⒆叭胧谌ㄖ》⑺透ONUi。图2中t1和t3分别是ONUi第n-1轮和第n轮的报告帧发送结束的时刻;t4是ONUi第n+1轮数据帧开始发送的时刻。オ
在DBAM中,гげ獾n轮的等待区间(t3到t4)到达ONUi的数据包长度为Tni,wait•(Qni, j/Tn-1i)。其中,Tni=t4-t2,Tni,wait=t4-t3,j∈{EF,AF,BE},然而Qni, j是ONUi在t3时刻剩余数据包的长度,并非t4到t2之间到达ONUi的数据包的长度,导致了预测偏差。讨论一种新的线性估计方法,设Dn-1i, j是t1到t3到达ONUi的数据包长度。易知:Dn-1i, j+Qn-1i, j-Ani, j=Qni, j+OVni, j。其中,Ani, j是t2到t3之间ONUi实际上传业务j的数据包的长度;OVni, j是t1到t3丢弃的数据包的长度。由于EF和AF业务的优先级较高,网络未满载时丢包较少;因此,当j∈{EF,AF}时,Dn-1i, j≈Qni, j+Ani, j-Qn-1i, j。
BE业务优先级最低,被丢弃的数据包的长度OVni,BEг对洞笥谇傲街忠滴,所以Dn-1i, jР荒茏既凡饬,为降低OLT的资源消耗,直接设Dn-1i,BE≈Qni,BE。
EF业务的流量短时相关(Short Range Dependence,SRD),突发性较弱,近似为恒定速率。Уn轮EF业务的预测值为:オ
P=(Dn-1i,EF/Tn-1i)•Tni,wait(1)
其中Tni,wait=t2-t0。
考虑EF业务的包长固定为Lp个字节,式(1)修正为:
Pni,EF=T(P+0.5•Lp)/Lp•Lp(2)
其中,БT•Т表向下取整。
AF和BE业务流量自相似、长相关,具有较强的突发性,预测失准造成较大的带宽浪费。首先定义第n-1轮到n-M轮ONUi的业务j(j=AF, BE)的流量均值和变化因子分别为:オ
Aven-1i, j=(1/M)•∑n-1k=n-MDki, j/Tki
Varn-1i, j=(1/M)•∑n-1k=n-M|Aven-1i, j-Dki, j/Tki|(3)
预测Tni,wait内到达ONUi的数据包长度为:オ
Pni, j=
Aven-1i, j•Tni,wait,Varn-1i, j≤β•Aven-1i, j
0,Varn-1i, j>β•Aven-1i, j (4)
式(4)的意义是当前M轮的流量变化因子大于平均值的β倍时设置Pni, j为0,即放弃流量估计。
Я髁吭げ夂,ONUi的业务j申请第n+1轮使用的带宽为:
Rn+1i, j=Qni, j+Pni, j; 1≤i≤Nオ
设Si,total为SLA规定的最大授权窗口,满足三种业务QoS要求的带宽分配方案为:
Bn+1i,EF=min(Rn+1i,EF,Si,total)(5)
Bn+1i,AF=min(Rn+1i,AF,max(Si,total-Bn+1i,EF,0))(6)
Bn+1i,BE=min(Rn+1i,BE,max(Si,total-Bn+1i,EF-Bn+1i,AF,0))(7)
┆扑慊应用 ┑30卷
1.2 ONU本地调度策略
AF和BE业务流量的突发性较强,因此预测带宽Pni, jЭ赡艹过或者低于实际需求。以太网数据包的不可分割性会导致大包阻塞[7],降低上行带宽的利用率,增加端到端延时。如果严格按照1.1节划分的时间段上传AF和BE业务数据包会加剧带宽浪费现象。在不影响公平性的前提下,在一定程度共享AF和BE业务的上行带宽,对提高网络接入性能具有积极作用。设业务jв氇j′,满足条件j∪j′={AF,BE},г虮镜氐鞫炔呗匀缦:
1)б滴j队列非空且余下时隙Δni, j不够发送该队列头部长度为Lj,HEAD的数据包。如果业务j′Ф恿型凡砍ざ任Lj′,HEADУ氖据包满足条件Еni, j≥Lj′,HEAD,发送该数据包;如果j′=BE, j=AF且Δni, j+Bni, j′≥Lj′,HEAD,г蚍⑺透檬据包并同时进入业务j′的上行发送时间段,否则等待整个上行发送时段结束。オ
2)б滴j队列为空,且上行时隙剩余Δni, j,У却tjШ竺挥幸滴j的数据包到达。如果业务j′Ф恿型凡康氖据包满足Еni, j-tj≥Lj′,HEAD则发送该数据包,完毕后查看业务j是否有新数据包到达,没有则返回继续执行策略2);如果j=AF,Δni, j-tj
上述调度方法的主要优点是网络负担较轻时,实现了预测带宽Pni, jУ牟糠止蚕;网络负担较重时,减少大包阻塞导致的带宽浪费。
2 仿真性能与分析
EPON系统的仿真平台共有16个ONU,光纤链路的上下行速率为1Gbps,而用户到ONU的接入速率为100Mbps。ONU的缓存区为10Mb,RTT设定为0.000B1~0.000B19s。EF业务数据包长度固定为70Byte,到达间隔服从泊松分布;AF和BE业务数据包长度为64~1B518Byte,服从均匀分布;自相似流量的Hurst参数为0.8。整个网络流量从0.05到1变化,其中20%为EF流量、40%为AF流量、40%为BE流量。本文把文献[5]中的DBAM算法作为参考算法;两种算法的最大授权窗口为6B250Byte。PDBA算法的M为4,β为0.5,tj为0。オ
图3~5是三种业务的端到端延时图。端到端延时指从数据包到达ONU到OLT收到这个数据包的延时。PDBA的端到端延时比DBAM明显下降,主要原因是更准确地预测了三种业务的流量,提高了在下一轮直接发送等待区间内到达的数据包的概率,Т佣降低了“T+2”排队延时;同时,本地调度策略使AF和BE业务带宽在一定程度上共享减少了浪费,提高了上行带宽的利用率。
图片
图3 EF业务端到端延时
图片
图4 AF业务端到端延时
图片
图5 BE业务端到端延时
丢包率指缓冲区已满造成的包丢失数量与网络中数据包总量的比值,由于PDBA算法中数据包被积压在ONU缓冲区的时间减少,增大了可用的存储资源,因此可容纳更多的突发数据包,从而降低了丢包率。带宽利用率指ONU实际使用的带宽与授权带宽的比值,从图7可知PDBA算法的带宽利用率与DBAM相比有明显提高。综上,PDBA算法较好地满足了各业务的QoS(如上行延时等)要求。
3 结语
本文通过改进DBAM算法的两点缺陷,提出了基于流量预测保证不同业务QoS的PDBA算法。本算法对流量平稳的EF业务和突发性较强的AF和BE业务采用不同的预测模型;同时,为减小预测失准导致的带宽浪费,在流量波动较大时段放弃预测。ONU的本地调度策略允许AF和BE业务在一定程度上共享上行带宽从而提高了带宽利用率。仿真结果证明了新算法的有效性。
图片
图6 丢包率
图片
图7 带宽利用率
参考文献:[1] PESSAVENTO G, KELSEY M. PONs for the broadband local loop[J]. Lightwave, 1999, 16(10): 68-74.
[2] KRAMER G, MUKHERJEE B, PESAVENTO G. IPACT: A dynamic protocol for an Ethernet PON[J]. IEEE Communications Magazine, 2002, 40(2): 74-80.
[3] ZHU YONGQING, MA MAODE. IPACT with grant estimation (IPCATGE) scheme for Ethernet passive optical networks[J]. IEEE Journal of Lightwave Technology, 2008, 26(14):2055-2063.
[4] ASSI C M, YE YINGHUA, DIXIT S, et al. Dynamic bandwidth allocation for qualityofservice over Ethernet PONs[J]. IEEE Journal on Selected Areas in Communications, 2003, 21(9): 1467-1477.
[5] LUO Y, ANSARI N. Bandwidth allocation for multiservice access on EPON[J]. IEEE Communications Magazine, 2005, 43(2):16-21.
[6] HWANG I S, SHYU Z D,KE L Y, et al. A novel early DBA mechanism with predictionbased fair excessive bandwidth reallocation scheme in EPON[C]// Proceedings of the 6th International Conference on Networking. Washington, DC: IEEE Computer Society, 2007: 75-81.
[7] KRAMER G, SINGHAL N K, DIXIT S. Fair queueing with service envelopes (FQSE): A cousinfair hierarchical scheduler for subscriber access networks[J]. Optical Society of America, 2003,22(8):1497-1510.