、，01．35
Supplement
蛐ar司andLaserEngineeri
红外与激光工程
2006年10月
ng()ct．2006
以太无源光网络动态带宽分配算法研究
刘
武，刘德明，朱光喜，胡保民
(华中科技大学光电子科学与工程学院，湖北武汉430074)
摘要：动态带宽分配是以太无源光网络的重点研究领域之一，其中光网络单元(oM7)内的带宽分配影响到用户的服务质量。文中在分析已有算法的基础上，提出了一种用于ONu内带宽分配的改进令牌桶算法，即每个分配周期中累积的令牌数取决于ONu分配的带宽，而不是ONU的基本带宽。给出了该算法详细的代码描述，并通过在模拟流量下的仿真，证明了该算法能保证不同类型数据的优先顺序，并能保证各种负载条件下带宽分配的公平性，因此相对于已有算法有更好的适用性。
关键词：以太无源光网络；中圈分类号：TN915
动态带宽分配；文l-I标识码l
A
服务质量；
文章编号l
自相似性
1007—2276(2006)增D一0137．05
BAinethernetpassiVorksInVestigationofDeopticalnetw
ao—IIlinuallg-xi，HUBLⅣWU，LⅣDe—IIling，ZHUG
(Sch∞l
of
ol，tod∞咖Ⅱc
Sci．＆Engg．，Hu配hongUniV．ofSci．&rIkh．，wuh柚4300r74。a血a)
Abst船ct：Dyn锄ic
Opdcal
b觚dwid吐l
alloc撕on(DBA)is锄ong吐le
mainresea∞chfieldsofEI，oN饵ⅡlemetPassive
eiIl昀一0NUNe铆orl@)，aIldm
on
DBA砌uences
ofme
meQmoSofeIldusers．A
iInproVed蜘bucket
illcodeorder0f
alg嘶Ⅱ姗
eaIldm
(hnproVedTB)isproposedbased
tIlefonI】ler
b锄dwidm
alloc删for
u咖g
alg嘶thIns．ThetokensizeiIlcreasedineachcycledependson吐le
each
oM，，i11stead
s伽c
gu砌teedbaIldwidm．Descri皿on
caIl
is百Ven
siInul撕onTesults锄dit
caIl
atsynth酣c仃amcco面妇lm
BhIlprovedT
gu娥IIneeme砸odty
Quality
di】匿酥蚍缸amcs，
also
gua啪tE圮Ⅱle翻-nlessof
SemsiInil撕t)r
alloc撕oncomime虹stiI培bandwparedwid吐l
DynaInic
allocationscheIne．
of
ords：EtllemetKeywPON(既℃N)；b觚dwidtllallocation(DBA)；
service(QoS)；
O引言
以太无源光网络(EPO№作为一种非常有希望的接入方式在近年得到迅猛发展。基于802．3ah工作组提出的多点控制协议(MPcP)【11，EPON在以太网技术基础上实现了高带宽和多业务接入，提供了一种很有竞争力
的接入解决方案。
坟■日期l
2006-08．14
t盒项目t国家科技部创新基金资助项目(04C262142lcr710)
作者■介l刘武(1978．)，男，湖北随州人，博士后，主要从事光同络技术及系统应用等
面的研究．
红外与激光工程：光电信息处理技术
笫35卷
EPON中上行带宽的动态带宽分配是EPON系统的重点研究领域之一，主要解决如何公平有效的分配带宽的问题。根据调度的位置不同，动态带宽分配(DBA)可分为两类：ONu间的带宽分配和0Nu内的带宽分配。在ONU间的带宽分配中，由局端的光线路终端(OLT)根据设定的用户等级协定(SLA)决定各ONU如何轮流分时传输。在ONU内的带宽分配中，由0NU选择内部的各数据队列进行传输【2J。总体而言，ONu间的带宽分配更关注各ONu间带宽分配的效率和公平性，而ONu内的带宽分配则更关注用户的QoS(服务质量)，这也是以太网需要关注的问题之一。目前的研究中已提出了很多ONu内的带宽分配算法，但现有算法普遍较复杂，难以保证业务的整体性能均衡，带宽分配也存在很多不公平性。本文在分析已有算法的基础上，提出了一种用于oNu内带宽分配的改进令牌桶(Improved
Token
Bucket)算法，该算法简单易行，能保证不同优
先级数据的优先顺序，同时保证各种负载条件下带宽分配的公平性，具有广泛的适用性。
1
ImprovedTB算法
目前使用和研究较多的ONu内动态带宽分配算法有sP算法和M—TB算法。严格优先序(SP)算法是指
ONu内严格按数据包优先级高低调度传输，高优先级的数据传输完了后才传输低优先级数据(如图1(a)所示)。SP算法简单而易于实现，能保证优先级顺序，因此符合业务的区分服务要求。但在sP算法中，低优先的队列由于获得调度的机会较少，因而传输迟延较大，丢包率也较高，不能保证调度的公平性。
常见的TB算法(令牌桶)常被作为一种简单的流量整形和QoS调节机制，也常被用于避免某种类型的流量超过预设值。为了在保证优先级顺序同时也能获得较好的QoS，文献f31提出了一种修改过的token算法(M．TB)。M．TB算法分两阶段调度传输(如图1(b)所示)：在第一阶段，ONu根据各队列的令牌数量为各队列分配传输窗口，在第二阶段，剩余的传输窗口按照严格优先级顺序分配到各队列。M．TB中各队列token的数目根据ONu的基本带宽分配得到，一定量的token保证了低优先级的数据得到基本的调度机会，同时也适当限制了过大的流量。
但是该算法中token的大小取决于预定义的基本带宽，难以适应各种负载条件。例如，当token的大小远小于队列长度时，所有的队列将进入第二阶段按优先级顺序进行的分配，总体看来这样M—TB分配的结果将
与SP算法一样(如图1(a)、(b)其中Q，代表各队列，∥代表某个周期各队列总共分配的带宽)。因此M．，IB
在负载大于基本带宽时会表现出SP算法的缺点，即低优先级的数据难以传送。
圆
a
缓
量不再根
黧霾搦玎
(a)
bII
第二阶段
第一阶段
惑鋈了
黝黝黝黝H
(b)
冀
图1
Fig．1
sP和M．TB算法的示意图
Sketchm—TBalgorimapofSPalgori吐lmandMm
为此我们对M—TB算法进一步改进，提出了一种IIIlprovedTB的算法。ImprovedTB的首要改进在于tok饥
预定义的用户基本带宽确定，而是根
每周期ONu分配的带宽进行按比例的动态分配，这样可
量可以累积，也就是未
以改变固定的token大小不能适应负载变化的缺点。ImprovedTB中同时使token的用完的token可以继续用于下一周期，这样真正发挥了其用于流量整形的作用。
增刊刘
武等：以太无源光网络动态带宽分配算法研究
139
Nu图2显示了ImprovedTB算法如何在某个周期分两阶段为ONuf中的各队列分配带宽。假设0LT为O
f分配了带宽掣，oNuf中有肘个输入队列(对应M个优先级)。对于第_『个队列，用乃表示第J个队列的允
许负载在总负荷中的比重，％表示其累积的token数量，彰表示其分配的带宽。显然，oNuf所分配的总共
带宽为群7=∑彰。其中岛表示第_，个队列中排在队首的数据包的长度。首先根据该周期分配的传输窗口大
J．1
小调整t01(en的大小，也就是累加token数目。在第一阶段的带宽分配中，第j个队列分配到的带宽取决于其
令牌数量％的大小，这样过大的流量会受到token数量的限制。在第二阶段分配中，剩余的带宽按严格的优
先级顺序被分配，使高优先级的流量一定程度上优先传输。
．缸毽=l：j《嗣电l+’￥{
玉12
bf÷B-’～：
，
办她|l
掣锄
细‘Q=l：i(-甜：j++’{
8：-o：
wh湘程B；+L。‘=bt)硎f掣+L．t：驿)硎嘞j扛删哪嘞)f
Ht)1．p￡Ic蛔醇qIl蕊谵j讧幽呼嘲痢壤'ds翻l：
B：=B：+LI：
鹫=霹+k：
，，
矗跏辟2
移《鹫‘B：I》{
如O=l：j《=M：j++){
掰程B：÷LI《2bI)删e咖ji5not霸删》f
．眦脚珂驴锹j虹卸删硎s酬：
B：=B：+L-：
酵=鹫÷k：
图2
Fig．2
脚sedImproved
Ir叩fovedTB算法的C代码描述
TB
alg嘶tllm(inCcode)
2算法仿真
算法中不同优先级流量的优先顺序以及带宽分配的公平性。参照互联网工程任务组(㈣的区分服务模型，
—TB算法，通过各种流量在实验中的时延和吞吐量，分析了两种本节比较了hprovedTB算法与旧的M
我们将业务流量分为三种类型：快速转发(ED，保证转发(AF)，尽力转发(BE)。其中与EF类型优先级最高，
140
红外与激光工程：光电信息处理技术
第35卷
对应于语音等时延敏感的业务；AF类型次之，对应于高速视频等；BE类型最低，对应于一般的文件传送等。为了尽量接近真实应用，在仿真中我们采用不同方法模拟产生各种数据流：EF数据流为固定包长(70bit)，到达时问服从指数分布；AF和BE类型流量的包长为64—1518，具有固定字节速率。为了验证该算法的实用性，也在具有自相似性的流量下进行了同样的试验‘41。
因为主要关注ONu内的带宽分配，实验中选取限制服务【51作为ONU间的带宽分配方法，最大传输窗口(MTw)尺寸为15
500
1．2
字节，0Nu间传输的保护间隙为1¨s。假设一个EPON系统中有16个ONU，每个ONI，的设定参数和加的负载都一样，可以算得每个ONU能分得的最大带宽约为62Mbps。
U给首先评价IlIlprovedTB算法保证优先级顺序的能力。oN定的负载为50Mbps，将其中固定的20％(10Mbps)分给EF类型的流量，其余的80％(40Mbps)按不同的比例分给AF和BE流量。图3显示了不同比例下，各种不同优先级的数据包的平均时延。可以看出，高优先级的流量(如EF类型)时延更小，体现出的优先算法符合mTF对不顺序依次为EF、AF、BE，因此IIIlprovedTB同类型流量优先顺序的要求。
Fig．3
矗
捌
管
霸鼬
O．2
5：l
4：l
3：l
2：I
l：l
l：2
l：3
l：4
l：5
AF流餐和B蹴匿的比例
图3
算法下各种优先级流量的ImpmvedTB数据包平均延时
AVeragepacketdelayfbfdiI琵rentqmucs
under
Balg耐mII叩∞VedTm
为了说明IInprovedTB算法相对旧的M—TB算法的改进，还进行了带宽挤占实验，通过观察AF流量递增对其他类型流量的影响，比较各算法分配带宽的优先级情况。设定所有0NU的设定和负载都一致，各ONU
中EF和BE的负载分别固定在0．1和0．2(即lOMpbs、20Mbps)，将AF流量的负载从O．06增至O．3(即6—30Mbps)。
对于M．TB算法，各优先级的队列分配带宽的权重为1：2：2，但基本带宽的设置分为两种：第一个实验中基本带宽设为60Mbps，大体覆盖了负载变动的范围。第二个实验中基本带宽设为20Mbps，负载增大后超过
算法实了给定基本带宽，这样每个周期内，0NU各队列的数据长度将大于对应的token数量。hIlprovedTB
算法中不使用基本带宽作参数(参见图2)，因此基本带宽的设置对试验结果没验条件同上，因为IrnprovedTB
有影响，不需再设置不同的基本带宽进行试验。
图4(a)、(d)显示了M．TB在实验1中(基本带宽为60Mbps时)各类流量的迟延和吞吐量，可以看出，EF和BE流量的延时和吞吐量始终保持稳定，而AF流量增长到一定程度后迟延加大，吞吐量也被限制，因此这是很理想的结果。图4(b)、(e)显示了M．TB在实验2中(基本带宽为20Mbps时)各类流量的迟延和吞吐量，可以看到EF流量的延时和吞吐量保持稳定，而BE流量随着AF流量增大而迟延加大，吞吐量减小，AF流量挤占了BE流量的合理带宽，因而不符合带宽分配的公平性原则。这是因为给定的token数量小于队列长度时，带宽分配的结果与按严格优先级方法分配一样，减少了低优先级队列的传输机会。该实验结果证明了前面对M．TB算法缺点的分析，因此M—TB算法不能保证在各种负载条件下都能公平分配带宽。
算法同样能限制AF图4(c)、(D显示了ImprovedTB算法在挤占试验中的性能。可以看出，ImprovedTB过大的流量，迟延和吞吐量都接近M．TB算法在实验1中的表现，而且因为IInpfovedTB算法不受负载水平的影响，显然具有更广泛的适应性。
3结论
本文分析了已有的oNu内动态带宽分配算法，并在此基础上进行改进提出了ImprovedTB算法。该真，证明了该算法在时延、吞吐量等各面都能取得很好的性能，相对于其他算法具有一定的优势。
法
能保证ONu内各队列传输的优先顺序，并通过动态分配令牌保证各种负载下带宽分配的公平性。通过流量仿
增刊刘武等：以太无源光网络动态带宽分配算法研究
141
∞
∞lOO
们】00
童
g
星
茗茗潮冒lO霹氧．
薹融
嚣m
*
l
串
1
O．10．1
O
O05
0．15
O．25
O．30
O．05
O．15
O．25
O．30
AF负载的流量／100Mbps
AF流量的负载／lOOMbpsAF流量的负载／100Mbps
(a)
(b)
(c)
O
O
O
OO
O
如筋加”旧∞；簪
05
l-———，————，——，—，—．——，—一
O．15
O．25
O．30
O．05
O．15
O．25
O．30
O．05
O．15
O．25O．30
AF负载的流量／100MbpsAF流量的负载／lOOMbps
AF流量的负载／lOOMbps
(d)(e)
(f)
图4
M-TB和ImpmvedTB
算法下各种优先级队列的数据包平均延时Fig．4
Avcragepacket
delayofdi侬IrentqueuesllnderM—TBalgodⅡlm弛dImp∞VedTB
alg鲥ttlm
l】I哪802．3aIl
taskfbrcehomepage(online)．Av枷ableat：http：，，www．ieee802．or∥3／efm
2】
殂皿NGJ，MoIJFTAHHT．Mema
access
conⅡ．ol
fbr副1eI删p鹬sive
op雠al
n咖od【s锄overview【J】．m】巳EC鲫脚吼Mag，
2005，43：145．150．
】
C砥NJ，c瓶N
B，皿s．Anovel
a190riⅡ皿f；orin昀一。肌b柚dw
idthallocati吼inem咖et
p髓sive
o咄aln咖叫【s叨．琚EE
Commun
Lett，2005，9：
850．852．
4】
U三LANDw．G()nmesemsi血lar
nanJre
of
，Mul(HEIUl狙B，PESAVen舱唧mGet．妇姒mcCT(ex．锄a1ded
dynamversion)ic咖【lJ】．删ACM恤lsNct，1994，2：1．15．
5】
KRAMER
for
aIl
Eth咖etPoN(EPON)【J】．m髓Co咖啪
Ma叠，V
2002，40：7牟80．●
参考文献：
【【[3【【
因篇幅问题不能全部显示，请点此查看更多更全内容