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



ATMлڡתǿȡԪо
̶ꡡ
ժҪԪǻATMӵЧ֮һеԪԾδԪԴ֮ĹϵµԪʱҵԴʺԪʧʵָ궼ϲ.ڴԪһATMʱѺķԴԴСһּڿ˷ͳԪȱݵ²ԣڡתǿȡԪԣԸòԺеֵԪMarkovΪ߷ԴʺԪʧָ꣬ѡԴСԪжòܹ߶ԴʣԪʧʣͬʱԪɵԪطӶջӵ̶ȼСٶӵĿ.
ؼʡ첽תģʽ(ATM)(QoS), Ԫ, Ԫʧ(CLR), Ԫȼ(CLP)
ͼšTP393
STUDY OF THE FORWARDING-STRENGTH BASED CELL
DISCARD STRATEGY IN ATM NETWORKS
CHENG Dong-Nian and LIU Zeng-Ji
(State Key Laboratory on Theory and Chief Technology of Integrated Services Networks, Xidian University, Xi'an710071)
AbstractA cell discard scheme serves as an effective method in either alleviating or eliminating network congestion in ATM network nodes. Existing cell discard strategies, however,do not consider the relationship between cell discarding and network utilization. Consequently, they lead to poor measures of both the average network utilization and the cell loss ratio concerning user services sensitive to semantics. From the viewpoint of the relative volume of network resources having been consumed by a cell arriving at a certain ATM network node, a new cell discard strategy, the forwarding-strength-based one, is proposed in the paper here, with removal of the above defects as its objective. By using the Markov model, the average network utilization and the cell loss ratio are analyzed with respect to the proposed cell discard strategy and the two classical ones available. The results show that by discarding cells having consumed minimal network resources, this new strategy can improve network performance through increasing the network utilization ratio, decreasing the cell loss ratio and cell retransmission volumes, alleviating network congestion, and reducing the possibility of recongestion in ATM network nodes.
Key wordsasynchronous transfer mode(ATM),quality of service (QoS),cell discard,cell loss ratio (CLR),cell loss priority (CLP)
1
ûṩȷķ(quality of service,QoS)첽תģʽ(asynchronous transfer mode,ATM)Ҫ֮һ.ͬ͵ûҵͨڲͬ͸ԶҪͬȼQoS磺ʵʱͺͷʵʱûҵڷֱڴʱӺʼԪʧʶֱҪʱ͸Ժ͸.͸ԵһҪQoSԪʧ(cell loss ratio, CLR).ĿǰоԱѶԪģ͡ƣCLRĶ̬͹ƶ๤磬Pushout Expelling(ſʽ)Ԫԣ12ݡGeom/Geom/1/KŶģ͵CLRƣ3ݡڳص̵CLRŻƼ4ݡڳ̵ֲָCLR5ݼAALݵԪβ鶪ڷ鶪6ݵ.(Pushout)ſʽֵ͵ԪԶԣڶԪʱֻǸԪCLPλǷΪ1CLP=1ԪӦVCC뱾ĹϵӦԴʺԪʧʵָ궼ϲ().ע⵽ǡǡֹϵӳ˲ͬг̵ԪķԴĲͬ仰˵ܻѡضԪиߵԴʺܣԴʵֿɸCLRʱӵָ.ԪѺķԴһʽԪѾġг̡ģԽ󣬱ԪѺķԴԽͬʱҲյԾԽ.Ԫڻӵ710ݣȴǷΪԪṩĸַ(Դķ䡢ռã1112)ΪԪṩЩֿԽͨ·(VCC)QoSΪۻ.ȻԪǶЩӴ۵ķ.⣬ЧԪӦʹԪ˫ط񶨵ĲӰС.оĿǣԪг̡ĸг̵̡ԪԴʣСԱԪӦϢط(ٶ)ӵĿԣӶЧ֧QoS.Ͽǳ˻ڡתǿȡԪ.MarkovֻܷҪϿɵòԾԴʺƽԪʧſʽԪ.
2ڡתǿȡԪģ
ȸתǿȵԪ(¼ƦĲ)3֧ŻģͣVCC·תǿȺVCCԪУȻĲԵ.
(1) VCC·VCC
һͨ·VCCJһ˵Ns˳򾭹DN1,N2,,Nr,,NDһ˵Nd,ǸVCCһ䷽ÿмӵNrŶ.¼Ǻţ
QiNrеĵi·Ӧ(r=1,2,,D)
iQiԪռʱ(CLP=1)Ԫ
iNrQiӵʱQiжԪ(i=1).
(2) תǿ
1. DJΪһVCCJġVCC롱DJ(1)VCCJVCCмӵ.
2. һVCCJVCCмӵΪN1,N2,Nr,NDJƦJΪVCCJһNr(r=1,2,,DJ)QiԪתǿȣ
(1)
ЦJNrԦJĵڲΪ1.򵥵ʽתǿȦJȻҲʽʽ

Щʽͼͼ1ʾ.ͬתǿȶΪͬQoSھвͬԪнûҵ.


ͼ1תǿȵĲͬ(DJ=20)
ɶ֪תǿȦıԪĳһVCCʱ߹г̣ͬһԪгǡǡǸԺķҿɱȵԴӶ˦ĲԵԪ׼.Ϊ֧֦ĲԽԪATMҪžÿVCCڸýתǿ.һVCCĳתǿֵȷ(̬)ʿڸVCCĽ׶̽VCC뼰м(VPI/VCI)ɸӦתǿֵ.
(3) Ŷģ
Ĳ[3]ġGeom/Geom/1/KģΪVCCJһмӵNrһԪQiŶģͣԪĵͷ໥BernoullịһԪʱ϶ڵԪ뿪QiĸʷֱǦ˺ͦͣQiΪKԪ.ԪĵʱTaȥʱTb໥ҶӼηֲTaG()TbG().ʱԪʧCLRһԪQiʱQiԪλñռĸʣ3ݣ
(2)
(4) Ԫģ
㲻ıԪCLPλҦi>1.ڡGeom/Geom/1/KŶģ£ĿſպͦԪ.һԪʱQiɽУ
 ʽԪQiѡһCLP=1ԪԶ
 ſʽԪQiͷCLP=1ԪQiͷCLP=1ԪQiѡһCLP=1ԪԶ
 תǿȦĵԪQiЦiCLP=1ԪѡСתǿֵһԪԶ.
3ܷ
ڽֱ𿼲ſպͦĲԸԵԴʺԪʧ.NrQiӵڼ䣬QiصĸVCC״̬仯(½ҲޱVCC).
(1) Դ
һԪӦͨ··(VCL)ʵʾƽVCLһǶȿһVCCԴ.
3. ƦJΪVCCJԴʡ:
(3)
Ц0,DJ+1ΪһԪVCCJԴ㵽ĿĽƽʱ(ƽVCL).ϵͳ״̬XVCCJһԪVCC,ǰXֵǰһʱXֵأǣXͼ2ʾ״̬,,״̬r(r=1,2,,DJ)״̬0תζNrԪĶ.ǵʵһVCCJ;мͬʱӵĿԽС,ʼһ㷢ӵ,,rʣ1,2,DJ}:



ͼ2ϵͳ״̬X:״̬
VCCJһNr(rʣ12DJ)ӵʱԸprתVCCJԪԸqr(=1-pr)ԪʱһԪ״̬0(VCCJԴ)״̬DJ+1(VCCJĿĽ)ʵʾƽʱΪ

ʽf(n)0,DJ+1Ϊ״̬0DJ+1n״.


ԡ

(4)
qRr,qEr,qr(r{1,2,DJ})ֱΪNrӵʱſպֲͦ¶VCCJCLP=1ԪĶʣ(4)ʽԵԴʦR,E,Ǧ.ԣ
(5)
ſղԣiK/2ʱͷn(1nܦi)CLP=1Ԫĸ pnͷCLP=1ԪƽmƽԪMһCLP=1ԪĸqErֱΪ

ΪͷCLP=1Ԫĸ.K/2<i<KʱƵУ


(6)
ڦĲ£赱QiӵʱеĦiCLP=1ԪԵתǿȷֱΪ

ӦjΪQiеjVCC(VCCj)תǿȦjNrе㣬ɼÿjӲΪDjɢȷֲj=(1,2,,i)pjk=P{j=k/Dj}=1/Dj(k=1,2,,Dj).Ϊ򻯷ٶst໥(s,t=1,2,i,st)QiЦiCLP=1ԪͬVCCDҶCLP=1ԪCjʱУ,ˣ
(7)
ʽ(5),(6)(7)֪:qRr<qErˣqr<qRrʱЦǦ>R>E.
ڣ 
ԣֻҪĲԾͱſղԾиߵԴ(֤).
(2) Ԫʧ
WΪһVCCӦ͵ԪTǸVCCĳʱ䣬iΪԪʱVCCJÿмNiƽԪʣi=W/T, (i=1,2,,DJ).ԪʱصVCCԴ԰ñԪĸ߲֡ط(ҵ)TʱطζNiԪʵ󣬼ʱĵʦˡiΪ

ˡ䡡iݦi.ԪʵֱӵQiҵ񸺺ɦ(=/)󣬴ӶʹӦCLR.VCCJһм㷢ӵǰ£ϵͳ״̬YΪһԪVCCJԴ㵽ĿĽ񣬼Y=0ʾδY=1ʾ.Yͼ3ʾ״̬


ͼ3ϵͳ״̬Y
״̬
״̬0״̬1ƽʱ0,1ΪVCCJԴ㷢һԪӦƽʵԪNrӵʱQ0=qrP0=prr{1,2,,DJ}.԰NrڵÿνNi(i=1,2,,r)˵У,ڣ,,ǣſպֲͦԸԵԪʷֱΪ

(8)

ˣqr<qRrʱЦ˦i>Ri>Ei(i=1,2,,r).
q=1/i,D=2(4,8,16),i/D=5/4(20/9),K=64(16),=1/9.1,=/,ɵõGeom/Geom/1/KģԪſʽͻתǿȵĶԸԵCLR壬ͼ4ʾ.



ͼ4ԪſʽͻתǿȵĶԵCLR
ӵQiиCLP=1ԪͬVCC£ɵó3ҪۣK,D,ͦiֵα仯ĲԵԪʧʶʼյſʽֲԣ3ֲԵԪʧʾKԼСͬҵ񸺺ɦ£ĲԵԪʧҲKСſʽԣ۵KͦiֵȷDɴСʱſʽԸԵԪʧʼԪʧ֮ı仯󣬵ĲԵԪʧǰֲнԵļСKDֵȷiʱĲԪʧʼСЧǰֲҪ.˵Ԫϴ󡢻CLP=1Ԫ϶CLP=1ԪVCCСʱĲԵԪʧָܽԵſԪ.
⣬ſֲԶԣĲԼСһԪԴ޽ƽҲӦؼСԪƽʱ.
4ᡡ
ԪѾг(תǿ)ĸһֿɻӵӶЧ֧CLR-QoSԪԣڡתǿȡĲԣڸԪתǿȵĶýϼ򵥵ģͷ˦ĲԵԴʺԪʧʣſʽ˱ȽϣڸVCCľͬµõۣʱĲԱʺԪʧʷſʽԣӵԪϴCLP=1Ԫ϶CLP=1ԪVCCСʱĲԵԪʧָܽԵſʽ.⣬ĲԶӦ㷨ҲӣСATM缰㷢һ̶ȵӵʱĲԱſʽԸֹܷӵ̶ȵļأӶܸЧ֧(ȷ)CLR-QoSСATMһӵĳ.
ȻVCCĵڲjãĲԵĹƽֵһо.
õӿѧоԺԤл.
߼飺̶꣬У19577ʿо.Ҫо򣺼ͨۼATMۼ.У193712ڣʿʦصʵ.ҪоΪͨۡۺҵۼؼATMۡӦ.
ߵλӿƼѧۺҵۺ͹ؼصʵҡ710071
ο
1Tassiulas L, Hung Y, Panwar S S. Optimal buffer control during congestion in an ATM network node.In: Proc of IEEE INFOCOM '93. San Francisco, 1993.10591066
2Chao H J, Cheng H. A new QoS-guarantee cell discarding strategy: Self-calibrating pushout.In: Proc of IEEE GLOBECOM '94.San Francisco, 1994. 929934
3Robertazzi T G. Computer Networks and Systems. 2nd ed. New York: Springer-Verlag, 1994
4Zhu H, Forst V S. In-service monitoring for cell loss quality of service violations in ATM networks.IEEE/ACM Trans on Networking, 1996, 4(2): 240248
5Gati D, Pujolle G. Performance managemant issues in ATM networks: Traffic and congestion control. IEEE/ACM Trans on Networking, 1996, 4(2): 249257
6Kawahara K et al. Performance evaluation and selection cell discard schemes in ATM networks. In:Proc of IEEE INFOCOM '96.San Francisco, 1996. 10541061
7Adrian E, Doshi B T, Zoccolillo R. Controlling congestion in B-ISDN/ATM: Issues and strategies. IEEE Commun Magazine, 1991, 29(9): 6470
8Prycker M. Asynchronous Transfer Mode: Solution for Broadband ISDN. Hemel Hempstead:Ellis Horwook, 1993
9B-ISDN ATM Layer Cell Transfer Performance(Rec I 356). Geneva: ITU-T,1993
10Traffic Control and Congestion Control in B-ISDN(Rec I 371). Geneva: ITU-T,1993
11ʱ.ۺҵ.ʵ磬1993
(Cheng Shiduan. Integrated Services Digital Network(in Chinese). Beijing: People's Post and Telecommunications Publishing House, 1993)
12ﺣ٣.ATMԭӦ.ɶӿƼѧ磬1995
(Sun Hairong Li Lemin. ATM Technology: Concepts, Principles and Applications(in Chinese). Chengdu: Press of University of Electronic Science and Technology of China, 1995)
ԭյڣ1998-06-22
޸ĸյڣ1998-12-28
