ѧ
JOURN AL OF SOFTWARE
1999ꡡ1010ڡVol.10No.101999




һڲֵнͨ㷨
 Ļ  

ժҪ㷨ͬӦõİ·ϵķ˳,ṩQoSĹؼ.ĸϵͳʱӺʱӲֵнĵ㷨VDBF(virtual clock difference-bounded framework).ڴ˻,ϵͳʱӵķͲʽṹ,˼򵥹ƽĵ㷨DFQR(difference-based fair queueing by re-calibration).˵㷨ӳ١ȹƽԺʵָӶ֮ﵽ˺ܺõ,֤ģʾܵԽ.
ؼʵ㷨,ʱӲֵн,,νṹ.
ͼTP393
A Difference-based Traffic Scheduling Algorithm
SUN Li-min DOU Wen-hua GONG Zheng-hu ZHOU Xing-ming
(Department of Computer Science National University of Defense Techonolgy Changsha 410073)
Abstract Packet scheduling algorithm controls the order of packet service, which is crucial in the design of a QoS network. In this paper, the authors first give a virtualclock difference-bounded framework (VDBF), then present a new scheduling algorithmDFQR (difference-based fair queueing by re-calibration), in which they use a hierarchical structure, recalibrate the system virtual clock periodically, compromise network delay with fairness and implementation complexity. Finally, they demonstrate the performance benefit of DFQR by analysis and simulation.
Key words Scheduling algorithm, virtualclock difference-bounded, recalibrate periodically, hierarchical structure.
㷨ͬӦõİ·ϵķ˳,ṩQoS֤Ĺؼ֮һ[1].ʵõĵ㷨еӳ١õĵȹƽԺ͵ʵָӶȵŵ,ĿǰĴ㷨δͬʱЩŵϼ֮ﵽܺõ[2].ڱϵͳʱӺʱӲֵн㷨VDBF(virtual clock difference-bounded framework)Ļ,ϵͳʱӵķͲʽṹ,˼򵥹ƽĵ㷨DFQR(difference-based fair queueing by re-calibration).ӳ١ȹƽԺʵָӶ֮ﵽ˺ܺõ,нǿʵ.
1ֵнĵ㷨VDBF
1. ϵͳæָһֱڹ״̬ʱ.ϵͳæ,͸ӵİ.
2. ۻָڽаȴʱ.ۻڵӳΪۻ.
3. i (t1,t2]ڼڻõķWi(t1,t2)ԤԼi֮,Ϊi(t1,t2]ڼõĹ񻯷,Wi(t1,t2]ʾ.
VDBF[3]һϵͳʱP(t)ϵͳ״̬,ÿiһʱPi(t)״̬.ģ.
(1) ·ĴΪC,·ӸΪN,iԤԼΪi,Ϊ֤ȶ,ڹϵ.
(2) ÿӵʱtʱӵ״̬,:
(a) ϵͳæʱ,iʱΪ;iۻʱ,iʱӱֲ;
(b) it1ʱ̽ۻʱ,ʱΪPi(t1)=max{P(t1-),P(t1-)};
(c) ۻ(t1,t2]ڼ,it(t1,t2)ʱʱΪPi(t1)=Pi(t1)+Wi(t1,t).
(3) ϵͳʱtʱϵͳ״̬,:
(a) ϵͳæʱ,ϵͳʱΪ;ϵͳæڵ(t1,t2],
P(t2)-P(t1)t2-t1
(b) κʱϵͳʱӶκδۻڵʱ,B(t)ʾtʱ̴ۻڵӼ,ô
P(t)minPi(t),iB(t);
(c) κʱ,ϵͳʱκδۻڵʱ֮н,
Pi(t)P(t)P, PΪ.
(4) ϵͳѡۻӷΪ:ϵͳtʱֻʱСۻӼ,üϸӻõķǵԤԼ.
ģжԲͬʿͬʱ÷,ģʱֻһ÷.VDBFӦİģϵͳ,ÿʱ,ʱǰһλ뿪ģϵͳʱӵʱֵ,ϵͳѡʱСĵ.֤WFQ[4]VC[5]㷨VDBF.
VDBFܹİ㷨ΪPDFQ(packet_by_packet difference_based fair queueing)㷨.PDFQ㷨.
1. PDFQ,Lmaxʾĳ,iĵͨ©Ͱģ(ii),ô,iİӳ.
4(㷨ƽ). ϵͳæ,ʱ(t1,t2)ۻڵij,ij(t1,t2)ڼõĹ񻯷֮н,(FΪ),ô㷨йƽ,FֵԽСƽԾԽ,F.
Liʾi,ʾi(t1,t2]ڼڻõİ.PDFQ㷨ĵȹƽ.
2. PDFQ,ijڦʱ̺һֱۻ,ôڦʱ̺ʱ(t1,t2],ϵ:
.
,Pϵͳʱʱֵ֮.
2DFQR㷨
VDBFܹ涨ϵͳʱӺʱӵԼʱӵļ㷽.VDBFܵĵ㷨ͬĵӳ,ȹƽԴڲ.VDBFܾ幹㷨ĺϵͳʱӵļ,ʹòͬϵͳʱӼ㷽,㷨ʵָӶȺ͵ȹƽԲͬ.㷨ӶҪʱԼѡ.ϵͳʱӵļʱ㸴Ӷ.ʵּ򵥺͵ȹƽ,ǲϵͳʱӵķ.
2.1ϵͳʱӵ
,DǰģʱӲֵСϽ.
ϵͳʱӰʵʱ,ôļܼ,ϵͳʱʱ֮ɴֵɵȹƽԲ.Ϊ˼ϵͳʱӼ򵥺͵ȹƽԺ,ϵͳʱͨʵʱ,ϵͳʱʱ֮һֵʱ,ʱϵͳʱ.ڰģ,öʽ* ϵͳʱʵּ,ϵͳʱӵֻڰ뿪ʱ.
ϵͳʱϵͳæڿʼʱΪ,Ұʵʱ,ʱӵļѡӵķVDBFܹ涨.Ӧİģ,ÿʱģ°һλɷʱӵʱֵ,ѡʱСİ.ڰģ·ɰʱ(ΪTfʱ),p_hʾۻδ÷ʱСİ,Fp_hʾp_hʱ,Ĺϵ.
1. ڰģ,ڷɰTfʱ̴¹ϵʽ:
Pi(Tf)Fp_h-D, iB(Tf).
֤:֤.ۻjʱֵϵʽ,
Pj(Tf)<Fp_h-D, jB(Tf).
Tfʱ,jڽδ÷ȵİΪjĵk,ô,
,
Fk,j<Fp_h.
֪p_hδ÷ʱСì,֤. 
ڰģ,ڷɰʱ(Tf),Fp_hP(Tf-)+D, jB(Tf).(Tfʱ̼ΪTRʱ),ɶ1֪,ۻӵʱֵ(Fp_hD),ϵͳʱP(Tf)С(Fp_hD),ɽϵͳʱΪP(Tf)=Fp_hD.ϵͳʱӵķΪ: 
(1) ϵͳæڿʼ,ϵͳʱΪ;
(2) ÿʱTf ,жϽδСʱǷϵͳʱֵD,Fp_hP(Tf-)D,ϵʽ,ϵͳʱΪP(Tf)Fp_hD,;
(3) ʱP(t)=P(t1)+t-t1,(t1,t]ϵͳæ.
2. ڰģ,ļϵͳʱӷ,ڷɰʱTf,ڹϵ:
Pi(Tf)P(TfD, iB(Tf).
֤:֤.Pj(Tf)P(Tf)+D,jB(Tf),ʱTf,jشһѾɵİ(Ϊk),ʱΪPj(Tf.jkʱt(t<Tf)Ϊp_h,ʱ,
Fp_h=Pj(TfP(Tf)+D.
P(t)P(Tf)(tTf),Fp_hP(t)+D.,tʱҪϵͳʱΪ
P(t)=Fp_h-D=Pj(TfPj(Tf)-D, (tʱ)
 Pj(Tf)=P(t)+D,
,Pj(Tf)P(Tf)+D,P(t)P(Tf).
֪ì,֤. 
ɶ1Ͷ2֪:ڰģ,ļϵͳʱӷ,ôڷɰʱTf,ۻӵʱֵС(P(Tf)+D)Ҷ(Fp_h-D),ϵͳʱʱ֮СڡD.
Ӧģµĵ㷨,ʱСۻͬʱ÷,ۻӵʱֵͬ.ڰģ,󵽴ʱСİܰڷ͵İ;ģ,󵽴()ʱֵСۻӿɰڷ͵.,ʱ,ģСۻʱӲСڰģ¸ӵʱֵ;ģۻʱӲڰģ¸ӵʱֵ;ģۻʱ֮ĲֵڰģС.ΪģTRʱ,ۻӵʱֵС(P(TR)+D)ֵҶ(Fp_h-D)ֵ,,ģTRʱ,ۻӵʱֵҲС(P(TR)+D)ֵҶ(Fp_h-D)ֵ,ʱɽϵͳʱ޸Ϊ(Fp_h-D).޸ϵͳʱ,һVDBFܵ,һ汣ģϵͳʱͬ.
3. ģʽµĵ㷨,VDBFܼʱӼѡӷ,ϵͳʱӼ㷽,ô:
1 ϵͳæڵκ(t1,t2],P(t2)-P(t1)t2-t1;
2 ϵͳæڵʱt,P(t)Pi(t),iB(t);
3 ϵͳæڵʱt,Pi(t)-P(t)D,iB(t);
֤:1 :
(1) (t1,t2]ڼ,ûϵͳʱ,ôP(t2)=P(t1)+t2-t1,ϵʽ.
(2) (t1,t2]ڼ,ʱ̦12mϵͳʱ,Ҳڦk=(k=1,2,...,m)ʱ,P(k)=Fp_h-DP(k-),ôP(t2)=P(m)+t2-mP(m-)+t2-mP(m-1-)+t2-m-1,ƿɵP(t2)P(1-)+t2-t1P(t1)+t2-t1,ϵʽ.
2 ֤.ϵͳæڣʱiB(t),P(t)Pi(t),tʱt-tPi(t-t),i(t-t,t]ڼ䴦ۻ.:
(1) (t-t,t]ڼûϵͳʱֵ.i(t-t,t]ڼʱֵС,÷ʲСڦi,,,,ì,P(t)Pi(t).
(2) tʱϵͳʱ,ڹϵʽ:P(t-)Fp_h-DPi(t-),ϵͳʱΪP(t)=Fp_h-D,Pi(t)=Pi(t-),P(t)Pi(t).
3 ϵͳʱӷ֪:ϵͳʱֵ֮ϵͳʱӵʱ֮ǰ.ʱtϵͳʱֵ,ڹϵʽ:
P(t-)Fp_h-DPi(t-)P(t-)+D, iB(t-),
 Pi(t)-P(t-)D,iB(t),
,ϵͳæڵʱt,Pi(t)=P(t)D,iB(t).
. ģ,ϵͳʱӵķ,VDBFܼʱӼѡӷ,ôõ㷨VDBF,ҡP=D.
2.2 ʽŻ
ÿӶ,հȺ˳,ֻڽδȵİμ.ǲ²ʽ:ÿһȴ,յȺ˳ڸӵİ;ϵͳһȴ,ڽδȵİŵȴ,ǰʱС,,ӶΪO(log2N).ѡ񹫹ȴʱСİ,ͰӦӶа,1ʱ빫ȴ.
2.3 DFQR㷨
ھ㷨֮ǰ,˵¼:pub_queueʾʱСĹȴ;
i_queueʾiյȺĵȴ;Fp_h(t)ʾtʱpub_queueδСʱ;FiʾǰʱiͰʱ,ϵͳæڿʼΪ.
ϵͳʱӼ:
(1) ϵͳæڿʼʱ,ϵͳʱP(t)Ϊ;
(2) ϵͳæڳϵͳʱP(t)ʱ,ϵͳʱP(t)ʵʱ.
뿪㷨: iĵktʱ̷.
(1) ޸ϵͳʱֵ:
if ( pub_queueΪ)
then { P(t)=0;
Fi=0;iC(t),C(t)ǹ·Ӽ
exit() }
else { if (Fp_hP(t)+D)
then P(t)=Fp_h-D
endif }
endif
(2) pub_queuejmʱС,ѡð;
(3) FjFm,j
(4) if ( j_queueǿ)
then {j(m+1)ʱ;
ʱ佫j(m+1)pub_queue}
endif
㷨: i(k+1)tʱ̵.
if ((i_queueΪ) and (pub_queueûiİ))
then {;
ʱ佫ðpub_queue}
else ݵ˳򽫰i_queue
endif
3㷨ıȽģ
3.1 㷨ıȽ
ӱ1ԿDFQR㷨ӳٱ߽WFQͬ,ʵָӶVCͬ,ȹƽҲPFFQ[3]㷨. 
1 㷨ӳ١ƽԺʵָӶȱȽ

㷨ӳٹƽԸӶ
WFQi/i+Lmax/CFi,j(0)O(N)
VCi/i+(Lmax/C)O(logN)
SCFQi/i+Lmax/C(N- 1)Li/i+Lj/jO(logN)
DFQRi/i+Lmax/CFi,j(D)O(logN)
PFFQi/i+Lmax/CFi,j(2.D) O(logN)

 
, 
.
3.2 ģ⹫ƽ
ӳģģΪ8ӹ·,ӵͨON_OFFģͲ©Ͱ.2㷨ڰΪ1(ģATM)ʱӳͳƽ.ӱ2:ӵӳСϵӳٱ߽;ռ50%ϵ1DFQR㷨еӳٽSCFQ(PFFQ)WFQ(VC)֮;ԤԼǿӳٵĹؼ,ͨ΢ӵԤԼͿɸıӵӳ.
2 㷨ӳͳƽ(i=2,Lmax=1)

ԤԼVCֵSCFQֵVCWFQDFQRPFFQSCFQ
10.500 0000.4985111.801.601.804.007.20
20.062 5000.061333920.0018.0023.0022.0023.00
30.062 5000.062333922.0019.0024.0025.0024.00
40.062 5000.062333923.0021.0025.0027.0031.00
50.078 1250.076273312.4012.6016.4018.4017.60
60.078 1250.076273314.8013.2017.8019.4018.60
70.078 1250.076273315.8013.6018.8020.4019.60
80.078 1250.076273319.8015.6019.8021.2021.60

 
ͨȽͬһʱӻõĹ񻯷֮۵㷨Ĺƽ,񻯷ֵ֮ͨӸսۻںʱ.Ϊ˲㷨Ĺƽ,ǽӷΪż,жӦӵԤԼͬ,ӵͨϴԱ֤κʱӶۻ.Ӱt=0ʼ,żӰt=1000ʼ,ͳÿ100ʱ䵥λʱӷͰĸ,12ʱ(700,1800]ڵͳƽͼ1ʾ.ͼʾVCȵĹƽԲ,㷨Ľ.һʵ˵DFQR㷨ĹƽԽPFFQWFQ ֮.

ͼ112ڲͬ㷨·Ͱĸ(ʱ:100s)
4С 
ڲֵнĵ㷨VDBFܻ,ͨϵͳʱ,òʽŻṹ,DFQR㷨.۷ģʾ,DFQR㷨еӳ١ϺõĵȹƽԺʵּ򵥵ŵ,ӳ١ƽԺʵָӶ֮ﵽõ.PFFQ㷨ATMӲʵ.DFQR㷨PFFQ㷨ƽԺ,ʵָΪ,˵DFQR㷨ȫӲʵ,ڸٵĽ,һΪʵõĸܵ㷨.
עͣоõ863߿ƼĿ
߼飺1966,ʿ,ҪоΪټ,ʵʱͨ
Ļ:1946,,ʿʦ, ҪоΪ缼
:1945,,ʿʦ,ҪоΪ绥,QoS
:1938,,ʿʦ,йѧԺԺʿ,ҪоΪܻϵͳṹ,ټ,ֲʽݿ
ߵλѧѧϵ ɳ 410073)
ο
1Zhang Hui. Service disciplines for guaranteed performance service in 
packet-switching networks. Proceedings of IEEE, 1995,83(10):13731396
2Stiliadis D, Varma A. Frame-based fair queueing: a new traffic scheduling 
algorithm for packet-switched networks. Technical Report, UCSC-CRL-95-39, 1995. 
http: //www.cse.ucsc.edu/research/hanlab/publications/
3.нӳʵʱо[ʿѧλ].ѧѧϵ,1998
(Sun Li-min. Real-time networks with bound-delay service guarantees [Ph.D. 
Thesis]. National University of Defense Technology, 1998)
4Parekh A, Gallager R. A generalized processor sharing approach to flow control in
integrated services networks: the single-node case. IEEE/ACM Transactions on 
Networking, 1993,1(3):344357
5Figueira N R, Pasquale J. An upper bound on delay for the virtualclock service 
discipline. IEEE/ACM Transactions on Networking, 1995,3(4):399408
6Golestani S J. Network delay analysis of a class of fair queueing algorithms.  
IEEE Journal on Selected Areas in Communication, 1995,13(8):10571570
ոڣ1998-07-13޸ڣ1998-10-16
