о뷢չ
JOURNAL OF COMPUTER RESEARCH AND DEVELOPMENT
1999 36 9 Vol.36 No.9 1999



״̬Ԥǰ
¬ǡධ
ժҪĴӳٳ˻ʹڴͳƵABRԶԸ߿ɱVBRӦʵĲƥ.Ϊ߷ƷЧԣøȼVBRҵʣĿôԤǰģʽABRԴĲͬӳٶδʱVBRռôԤ⣬δABRôֵΪӦABRʷ䣬Ӷʵʵľȷƥ.VBRҵǿʹԾȷʱԤΪܣʹͨõԤⷽVBRҵʵʱԤ⣻ҵԤRTTԸݵǰ(LF)ʵERֵԲ.ǰģʽЧԺ͹ƽͨʾԵõֱ۵ʶ㷨Եһ֤Ҳи.
ؼʡҵͻԣƥ䣬ҵԤ⣬ǰƣҵԣԤ⣬ƽ
ͼšTP393.2
PROACTIVE CONTROL BASED ON NETWORK STATE PREDICTION
LU XiCheng and ZHU Pei-Dong
(Department of Computer Science, National University of Defense Technology, Changsha 410073)
AbstractThe large bandwidthdelay product of high speed networks(HSNs) makes the conventional feedbackbased mechanisms unsuitable for ABR to fast respond to high bursty VBR traffic, and results in a significant rate mismatch . In order to increase the efficiency of feedbackbased control and acquire full access to leftover bandwidth by high priority traffic, a predictionbased proactive control scheme is proposed, which predicts future VBR bandwidth occupancy respectively for different feedback delays of ABRs, and assigns the corresponding ABR sources a rate on the basis of the estimate of total ABR capacity. Strong dependency of VBR traffic in HSNs makes possible the relatively exact prediction of time series, and we can take advantage of the existing generalpurpose linear prediction methods to get realtime results online. The current value of load factor(LF) can be used to adjust ER feedback , thus compensating the forecasting variance and RTT estimate error. The efficiency (i.e., exact rate match achieved) and fairness of the proactive scheme can be seen intuitively from an example, while their general description and simple proof are also presented.
Key wordstraffic burstiness, rate match, traffic prediction, proactive control, traffic dependence, linear prediction, error compensation, fairness
1
1.1ABRʿƿ
ABR(available bit rate)ATMһҪķͣҪܹøȼCBR(constant bit rate)VBR(variable bit rate)ʣֽСԪʧʣҪABRԴ״̬ı仯Ӧ.
ATM TM4.01ݶ˻ʵABRƿܣȷ涨Դϵͳ(SES)޶ϵͳ(DES)ľΪصʽ(ER)ܣERļ㷽ҵʵ.SESÿNrmԪһ RMԪ(ǰRM: FRM)ЯǰԪ(CCR)(ERֵ)ؽдERͨRM(BRM)ͻSESSESµERԼԪ(ACR).
Ӱ췴ЧԵʱ䲿RTT:Դ޵ӳ٣͡Ŷӳ٣FD(feedback delay):ظĸصصӳ٣FD(SFD)Դ֮䴫ͷӳٵ.IRCT(interRM cell time):ƻķNrm(1/ACR)нСIRCTԴÿ;AI(averaging interval)ֳƲ(measurement period)صĿ(control cycle)ؼERǰزʱAIԽСER仯ԽƵSES ABRʱ仯ԽࣻAIʱȶ; VBR仯Ƶʵ.
1.2ERЧ
ӳٳ˻ĸ練ӳٺܴʹABRӦVBRĿٱ仯ʱصĴƥɹ(overload)Ƿ(underload)·.
Ϊ˱ڷͼ1ʾĻṹȿһABRһVBR.ͼABRԴVBRԴƿSwitchCABRԶӳΪd.DESϽӳ٣RTT=FDݲǷŶӳ٣FD =2d.ABRVBRʹòͬ.

ͼ1ABRƷģ
ABRΪԴʼݷͣABR SESԪacr(t)ΪطER(ݲǸӵԴ).Ŀ·100Ԫʧ(CLR)С.£tʱؿɼABRsw-acr(t)VBRsw-vbr(t)swacr(t)=C-swvbr(t)ABRʺͿôȫƥ.ҪSES ABRacr(t-d)=Csw-vbr(t).
ʱtʱܲõsw-vbr(t)ϢϢt+dʱ﷢SESѾһBDP(ӳٻֵΪacr(t)d) ݷt+dʱacr(t+d)=Cswvbr(t)t+2dʱʵݲŵأswacr(t+2d)Cswvbr(t)2d֮ʲźswvbr(t)ƥ䣬2BDPķûܽܿƣtʱΪt+2dʱűֳͼ2ʾ.
봫ͳ粻ͬǸBDPǳô10MbpsRTT=40msNrm=32IRCT=1.4msSESԼ30RMԪ֮ܵõҪ״ֻ̬ڵȴԼ30RMԪ֮󾭹ƵABRҵŵƵЧԷǳ.ϼVBRʸıʱBRMͬʱER㣬ЩʱأƵЧԽһ.
⣬صVBRsw-vbr(t+2d)ѷܴ仯ABRswacr(t+2d) swvbr(t+2d)Ȼƥ.ͼ3ʾVBRı仯С2d.ͳƽ2dԽͼ2ͼ3ʾʲƥԽأɵıĶʧԽ࣬ҲԽ.

ͼ2ջƵʲƥ(ӳ)

ͼ3ջƵʲƥ(VBRٱ仯)
2ER㷨Ŭ
͵ABR㷨EPRCA2, ERICA3ݺERICA+4, CAPC25ݣPhantom6, NIST ER7ݵ.ER㷨Ƹ׷õ̬ܣABRôĸ߿ɱȱ.ʹΪõ㷨ﵽյʷʱҲҪʮRTTʱ.ERICA+4100·ΪĿ꣬ΪӦɱVBRȡһЩʩûɹеķӳ٣ͼ2ͼ3ʾABR㷨ĵЧ޷.
SP-EPRCA8ʹSmithԤӳٴӿƻ·ɾҪԴרõĹʽERABRʿƵı׼ܲ.ף9ݶVBR仯ʱԤ⣬ڱ仯ǰ2d֪ͨԴͨRMԪƽӵ״̬ERABRʿƱ׼ܣԤVBR仯ʹüٶֲ(ֲ)ľֵǰƵЧԣҲʵãûпǶABRVBR.(עͼ2ף9ͼ1.)
3Ԥǰ
ABRƿǶ-˱ջƣʹôͳʷģʽ޷BDPزƥ⣬ABRVBRı仯ԿӦ.㷨ǿƻĹؼƣΪˣڷABRʿƱ׼ܵǰ£ԤǰģʽزԤ⼼ͨԤδVBRʣδABRʣǰABRӶȷABRVBRʵȫƥ.
3.1һABRµERǰǰ
ʹtʱصABRʺͿôȫƥ䣬swacr(t)=C-swvbr(t)ҪSESABRacr(t-d)=C-swvbr(t).ERؼģȻ󾭹ʱd͸SESر뼰ʱABRĿ.Ϊ˷ABRʣҪȷVBRʵʹõĴ.Ԥswvbr(t)swacr(t)=C-swvbr(t)swacr(t).swvbr(t)Ԥֵswvbr(t)õABRôΪswacr(t).
RMԪERϢSESABRʵĵΪIRCTABRt-dʱյBRMµãʵЧSESΪ(t-d),(t-d)+IRCTݣʵЧΪt,t+IRCT.صĿ(AI)ҲIRCTt-2dʱԤ⣬Ԥǣt,t+IRCTؿɼVBR.޷֪VBRҵľȷģͣͨԤt,t+IRCTVBRԪпƣҲҵģʽԤ.
3.2ԤⴰںԤȷ
ʵʵпжABRأػ֪ܵABRô֮ҪͳһԸABRʷ.NABRΪABRi,iʣ1,N.ABRiķӳFDiRMԪΪIRCTi.BDP磬IRCTi<AI FDiAI.
㷨ȷΪ׶ΣԤ׶κͷ׶.Ԥ׶ΣÿAIʼʱVBRԤ⡢δABRԼABRƽ(fair share)㣻׶ΣAIڵBRMʱERļ.Ԥ׶ο㹻̵ʱɣȻͬһAIʣʱڣABRBRMأERʼSES.
FDIRCTȫһµĸABRΪͬԴ.صABRͬΪ˾ȷƥ䣬ӦtʱʱڵVBRۼҵԤ.Ԥʱθһıʾǣ(t+D),(t+D)+PW.DΪԤ룬ԤеʱԤ俪ʼʱ֮ľ룻PWԤĳȣΪԤⴰڣԽṹӦÿѡȡһʱṹƵÿ֡ʱ(frame time).
(1) Ԥⴰڵȷ
PWAIôSESӦñֵһAIʼ.ȻģΪʹһER㷨УһAIڶͬһԴķҲɲ䣬ͬһABRĶBRMЯͬERֵ.
(2) Ԥȷ
 ABRķӳͬi,jʣ1,N,FDi=FDj=FD,D=FD;
 ABRķӳСAIi,jʣ1,N,FDi-FDjAI.IRCTi<AIһAIABRBRMأʹ÷ӳٵľֵD=FDt/N.
 ,iʣ1,N.kiMֵͬΪKl, lʣ1,M.һAIڣҪMԤֱԤ⣬Dt=KlAIԤֵVBR Capacityt(t+Dl)(t+Dl)+PWݣlʣ1,MݣȥAIѾԤ⣬AIڿʹô洢ԤֵýСԤⲽ½Ԥ.ڸABRki=kj=KlABRiABRjʹͬԤֵ.Ȼǰͳһַ.
3.3Ԥǰ㷨
ÿAIʼʱԤ⣬ԤʱΪt;ABRiBRMʱERi.VBR CapacityΪVBRռôԤֵTotal ABR CapacityΪԤABRô.PWAIԾĿֲ. 
㷨1.ǰģʽػ㷨
(1) ݷӳ٣ԾABRӻΪMӼAl,lʣ1,M;ABRi,ABRjAl iff
(2) Ԥ׶Σѭ l=1 to M
 Ԥ(t+Dl),(t+Dl)+PWʱVBRռôVBR Capacityl;
 Total ABR CapacitylLink Capacity-VBR Capacityl;
 FairSharel
(3) ׶ΣABRiAlERiFairSharel.
3.4 㷨ʾ
صAI=4msN12ABRԾӣݷӳٻΪM=3ӼA1A2A3.ʱΪt0MԤ1ʾ.·C=100MbpsԤȫ׼ȷ.2гԤVBRռôABRôʱtı仯УABRERֵԼʧԤǰƷ봫ͳıȽ.
1ABRӦԤ

lAlиABRFD(ms)KlDl(ms)Ԥ(ms)
121,22,23,24624t0+24, t0+28
2 25,26,27,28728t0+28,t0+32
329,30,31,32832t0+32,t0+36

2Уʱa-bʾt0+a, t0+bݣTotal ABR CapacityΪӦʱIABRôԤֵERl ʾIڼAlABRķ.ʧ(LB)ΪABRܵĿôȥABRصʵ.ͳֵڱ2߿г.
2Ԥ㷨봫ͳƷʱбȽ 
ʱI044881212161620202424
2828
3232
3636
40
VBR Capacity
VBR Capacity䡡
Total ABR Capacity䡡24366012
ER1, ER2, ER32,3,53,5,15,1,X1,X,X
صABRʡ2,X,X3,3,X5,5,51,1,1
ʧ(LB)YYYYYYYY000
Total ABR Capacity12482460
ER1, ER2, ER31,1,14,4,42,2,25,5,5
صABRʡ1,X,X4,1,X2,4,15,2,4
ʧ(LB)ZZZZZZZZ32-32
˵ЩδΪ˼п㷨нϴӰ򣻢ڱеXʾиЩ޷õֵYZĺ˵ʻλMbps. 
ɱ2ɼʹûԤǰƣt0+32,t0+36Ժʱڣʵ־ȷƥ.ͳķABRʱVBRʣĿôַ˱仯t0+32, t0+36LBΪֵABRĴʵͣΪ28/60=46.7%t0+36, t0+40LBΪֵ·أ32Mbps4ms=128KbitۻصABRУɶʧ.ִƥͼ3.
ABRFDֵFDmaxΪ32ms2YZעʱڵĴʧ.t0㷨ĵһִʱ(t0=0)ԤƵABRҵûȫأYֵȷǷΪ0.Ԥ㷨Ѿ(t0>0)ӽt0+32, t0+36ݵʱYֵͻΪ0t0>FDmaxYȫΪ0.ʱ2,X,X=2,2,2,3,3,X=3,3,3.ͳƣFDmaxZֵȷǷΪ0ؿ㷨ʱͽ״̬޹. Ĵƥͼ2.
4VBRҵԤ
ǰƿƥ侫ȷԵľԤ׼ȷԣֺVBRҵеĿԤԼԤ㷨.
ֻҪԤδĳʱ(PW)ڵԪĿVBR Cells䣬VBR Capacity=VBR Cells/PWVBRռôõϵͳģ.жVBRͨأԤVBRۼҵ(aggregate traffic). VBRԴONOFF״̬֮лVBRۼҵڸʱ߶(time scale)϶ֳǳǿͻԣҵзǳǿԣ10ݣδҵԤ. 
ʱVBRۼҵ񹹳ʱ.Ϊ˼СۣʹԻع鷽ʷݵϽԤ.LMS(least mean square)ӦҪ˽ʱеؽṹЧҵʵʱԤȡñȽĽ1112.LMSԤģʽĵ㷨11ݣ
(1) xn=W\+TnXn-1
(2) n=xn-xn
(3) Wn+1=Wn+2̦nXn
УxnΪԤֵX\+Tn-1=xn-1,,xn-Pǹȥʵʲҵ.WnΪnڵӦ˲ϵnΪԤΪӦ泣Ӧ㷨ٶȺȶ.LMSʱԤϵԤ˲ϵӶС.
5㷨
5.1ģʽ
2ͨ㷨ıȽϣԶԤ㷨ıһֱ۵ʶ.ԤƷERʱFD֮ABRôʷ䣬ͬFDABRʲͬǵFDmaxABRҵ񵽴ʱABRͬ.ʵִȫƥ䣬ʵ˴ĹƽĹƽָABRôƽ(equal share). 
ͳȫ෴ERڵǰôABRֵͬǵҵ񵽴صʱ䲻ͬ.ؿABR޷ƽôܵĴռúVBRʣҲƥ.ϣFDmax֮ʵִƥ䣬ҪFDmaxڼFDmax֮VBRռõĴ.VBRÿһα仯һҪ󣬲ʵִƥ.
Nͬʱݴ䣬ԤĿ㷨FDmax֮ʵֲִȫƥ䣬ضԻҪСгȺŶӳСԪʧ.
5.2ģʽԵһ֤
ABR㷨Ч빫ƽԿһ 
㷨ʱtFDmaxABRi,iʣ1,N,swacri(t)=Total ABR capacity(t)/N.swacri(t)ΪtʱABRiصҵʣTotal ABR capacity(t)ΪtʱABRܵĿô.
򵥵֤.tFDmaxswacri(t)t-FDiʱؽERʣԸ㷨1swacri(t)=Total ABR Capacityl/N.Ԥȫ׼ȷôԤABRôΪTotal ABR Capacityl=Total ABR capacity((t-FDi)+FDi)=Total ABR Capacity(t).
֤.
5.3 㷨
VBRҵԤFDƶƥ̶ܵӰ.Ϊ˷ֹۻ(buildup)Ըݵǰ(LF)ʵERֵ.VBR CapacityABR Input RateһAIڵĲֵ.㷨1ķ׶θΪ
Total ABR CapacityLink Capacity-VBR Capacity;

ABRiAl
6 
øVBRҵǿԤԣABRԴĲͬӳٶδʱVBRռôԤ⣬ݴΪӦABRʷ.ԶԸ߿ɱVBRӦʵʵľȷƥ䣬ʵִĹƽ.ҵԤ㷨һĸԣרӲʵֲ㷨ҲҪ϶ĿռԴ洢״̬Ϣ.
עõҡ߼ƻ(Ŀ306ZD07022).
߼飺¬ǣУ194611ڣʿʦҪоΪܼȽ缼ֲ.
ධУ19715ʿоҪоΪЭ.
ߵλѧѧѧϵɳ410073
ο
1Traffic Management Technical Working Group. Traffic management 4.0. ATM Forum,Tech Rep:aftm0056.000,1996
2Roberts L. Enhanced proportional rate control algorithm. ATM Forum,Tech Rep:940735R1, 1994 
3Jain R, Kalyanaraman S, Viswanathan R. The OSU scheme for congestion avoidance in ATM networks:lessons learnt and extensions. Performance Evaluation, 1997,31(1-2): 6788 
4Jain R, Kalyanaraman S et al. ERICA+: Extensions to the ERICA switch algorithm.ATM Forum, Tech Rep: 95-1346,1995
5Barnhar A W. An example switch algorithm for section 5.4 of TM spec. ATM Forum, Tech Rep: 950195, 1995
6Afek Y,Mansour Y, Ostfeld Z. Phantom: a simple and efficient flow control scheme. ACM Computer Communications Review,1996,26(4):169182
7Golmie N, Chang Y, Su D. NIST ER switch mechanism(an example). ATM Forum, Tech Rep: 950695, 1995
8Mascolo S, Cavendish D, Gerla M. ATM rate based congestion control using a smith predictor: An EPRCA implementation.In: Proc of IEEE INFOCOM '96, San Fransisco, CA, 1996. 569576
9Dag T, Stavrakakis I. A proactive feedback based flow control scheme for ABR services. In: 3rd AsiaPacific Conference on Communications (APCC'97) , Australia, 1997. 116122
10 Feldmann A, Gilbert A C, Willinger W, Kurtz T G. The changing nature of network traffic: Scaling phenomena. ACM Computer Communications Review, 1998, 28(2): 529
11 Chiruvolu G, Sankar R, Ranganathan N. Adaptive VBR traffic management for higher utilization of ATM networks. ACM Comupter Communications Review, 1998, 28(3): 2740
12 Adas A. Using adaptive linear prediction to support realtime VBR video under RCBR network service model. IEEE Transactions on Networking, 1998, 6(5): 635644
ԭյڣ1998-11-26޸ĸյڣ1999-04-07.
