
COMPUTER ENGINEERING
1999 25 12 vol.25 No.12 1999



QoS·ؼ
Ⱥᡡнܡ
ΪϢʩѸٷչ·رǹǸ·ƺʵҪսһûӼýӦõĳ֣Ҫ··ӵиߴûӦõҪṩͬķ·Ӧ߱(IETFIntServDiffServ ַ)Ļơ
ͬʱָ֧ߴʹ·(QoS·)ƺʵָΪӡߴҪ·ٵشתÿݰҲҪ·ڲܼ򵥣Ҫ·ڲָ״̬ϢԱ㰴ӻһӷʶݰͷԴʹݰתΪӡΪһìܣͬͳBest-effort·ȣQoS·ҪϵṹԴȷиĽҪصýͲд·ܡ 
1 QoS·ϵṹ
1.1 ·
һͨõ·ṹͼ1ʾ4ɣ˿ڡṹ·ɴ˿ڡ˿·ִ·㹦ܣݰIPַ·ɱȷݰ˿ںһεַ˿·ӣҲִ·㹦ܣ洢ͷݰ·ɴ·Эά·ɱִܡṹ˿ڡ˿ں·ɴԱ˿ڵݰһ˿ڻ·ɴ 


ͼ1 ·
1.2 QoS·߼
QoS·߼ͼ2ʾʵߺ߷ֱʾݰת·Ϳ·ת·ϣQoS·ִ·ɱҡ˿ڵ˿ڽݰ⣬ִݰ࣬øӵĵȺͻӷԴ

ͼ2 ȽBest Effort·QoS·
ڿ·ϣQoS·ά·ɱִ⣬RSVPЭִн[1]RSVPЭͽڸӱԴת·ڿԴ״̬Ϣ͡ȼȡ 
2 QoS·Ĺؼ
QoS·ܵĹؼת·ܣ߹ת·ĸ·ƣṹݰࡢ·ɱҺԴĴ
2.1 ṹ
ṹ·ĺģߡڴͽ濪3߽͡ṹָ·ĸ˿ں˿ڶͬṹ򵥣ʵ߽֡ṹ˿ڼÿֻһݰͬʱٲýṹʵָӣӶߴߡ߽ṹֻڷ·ҵ·
ڴṹ·ѽյݰ洢ڹڴ棬˿ڼֻ轻ݰָ追ݰЧ߽ṹʡ洢ȡٶƣҲ·
濪N˿ںN˿ڼ佨Nߡ˿ͨݰߴһĽ濪شڵһǣ˿HOLʹʵ͡һڲ٣ʹ濪صڲ·ܺͣ˿ͬʱն˿ڵݰŶӷʽŵݰֻŶʱӣȱչԽϲһŶӡ濪ÿ˿ڶӦһ˿άһFIFOСģͽַ֤ʽɻȡ100%ֻڲٱΪ2ɻͬڲٱNƵǿչġ濪һǲÿɱ䳤Ƚ̶Ƚÿɱ䳤Ƚߴʣ䳤߼ʮָӣǲù̶Ƚ·ѿɱ䳤ȵIPݰֶԪñǼԪ˿ڣIPݰ
2.2 IPݰ
IPݰݰࡢ·ɱҺһԴ籨ͷУ顢޸ıͷIPַ֤IPѡȡУ·ɱҺݰΪӡ
(1)·ɱ㷨 InternetCIDR(Classless Inter-Domain Routing)ַṹ·յÿݰҾ(ƥǰ׺)·ɱݰת·ɱָ˿ڡƥǰ׺ʹôͳȫƥ䷽ȫϣƲҡ׼洢ֱӦ·ɱҡ⣬һ·ɱһǧ·ɱͬʱݰȺ̣ܶʹ·ɱʵֱѡ·ɱӰ·һҪء
ֿЧĽ·ɲܵ㷨ЩĽ㷨ɷΪ(1)Ӳ(2)ѹ(3)ϣͳӲʹ洢(Content Addressable Memories)͸ٻ(Cache)洢·ɱַչԲִ֧·ɱĸ·һָĽǰ߼·ʹ洢һʹ洢ܻԼߴ洢ٶȡһָĽô洢ռ洢洢·ɱרӲ޸·ɱ˷·ɱ޸ѵȱ㡣
ѹ·ɱϡԹһӺͽյ·ɱԱܰ·ɱ·ɴһٻڣʵָ·ɱҡ
һָĽϣǶһIPַѭѡȡͬǰ׺ʽֱϣֵַչԲһֿչϣ㷨ǶһNλַֻO(logN)ʱǰ׺ƥ䡣㷨Ϊÿܵǰ׺ƥһĹϣǰ׺ﳤʹöƲ㷨Ǵӿǰ׺ʽʼҡ⣬㷨ҪΪÿϣ洢ڲǣϣʧʱָһ׺ʽĹϣһ·ɱڲѹʽ洢Чٱ洢ռҪԤһ16ǰ׺ʽԤһ·ɱϣԿٸıϣɽһƽ洢ʱΪ2
(2)ݰ㷨 ݰ֧һҪơQoS·ʶһӻһӷ͵ݰԱҪԴûҪ󡣰ӷݰQoS·ҪÿݰIPĿĵַһԴַӵҲģǰЭ͡ͺTCP/UDP˿ںڹ˿һƥݰIPv4ԴĿĵַ֮Ϊ64λЭ͡ͺTCP/UDP˿ںֶΣ䳤֮Ϊ104λǸ·Ĺ˿һ㺬дķ(1k10k)£Ҫʵֿݰʵֿ·ɱҸΪѡһЩ·ɱ㷨ʵְٲ32λַЩ㷨ܱ޸Ķڿݰࡣ
ݰһЩʵַһQoS·ͨĿġԴIPַݰһgrid-of-triesŻ㷨ͬʱ԰ĿġԴַͶ˿ںŵȶάռзݰһcross-producting㷨㷨Ҫ8δ洢ʺ11δ洢ʡһǻӲĲз෽ʵ֡÷·ĿġԴַͶ˿ںŵȷݰһ㻯Ϊάռ⣬÷ֽⷽѶάռΪʽ⣬ʽ
ӷʵ񣬷ǳڹǸ·ԣʵְӷǳѣչԲˣԺչԼԣǸ·þۺϵķʵַ񡣶ÿݰ·ֻ谴࣬ڸʵ֡
(3)ֲд ·ɲӲͨIP IPӦأṹɻΪкͷֲʽ֡ʽṹǲһתתܶһĴִС
ֲʽṹǲһЩܴòдIPͬʽṹȣֲʽṹչԺãƸӸӡȣ·þʹƸԷֹݰһЩǰŶӶһЩеȴΣ·άȫһ·ɱΪý⣬ɲһֹרûķֲʽṹ·IP̷ֳΪִضܽ׶ΣÿIPִֻһרݰһԪһԪɼ򻯸Ԫƣͬʱʹͨſӡ
(4) Ž ·IPһַ·ñŽŽͬڴͳ·ɽ˼·һӵݰһţһ·ݰȫƥ䷽ʽת͵ȴӵڶʼݰ·ɱҺݰ⣬·ATMݰתٶȡŽҪ·ʵֱŷЭ飬⽫شı䵱ǰInternetṹ⣬ʹ·е·ݴԽ͡
2.3 Դ
·Դ·ռǰ۵ݰ㷨ÿݰһӻһӷ࣬ݰȺͻ㷨һӻһӷ·ͻ壬ӵķҪ
2.3.1 㷨
㷨ȷŶݰ·˿ڵķ˳򡣵㷨ȷͳȼԼӵļȨƽŶӺͷֲ·㷨ȷ㷨ʵּ򵥣ȷȱǲܿƷܱ֤һЩӱȱӾиСĶ˵ʱӣԼֹһЩӲϷݰʹӲܹƽʹԴ
ȨƽŶ㷨һĵ㷨ÿȨֵ·ȨֵɱʾΪw1, w2,,wnЦwi=1Ŷkпɱ֤wk*R/wiRΪ·ˣȨƽŶ㷨ɱ͸ӣƽʣӷ©Ͱ㷨Ӿһɱ֤Ķ˵ʱޡȨƽŶ㷨ȱҪÿŶ״̬ϢݰʱӲҰȼŶӣչԲ
ֲ·ָ֯һ·ӣ·ڲԵظÿ·ֲ·Ҫʵ¼Ŀ꣺һ㹻Ӧ֤СһʣӦֵ֤๫ƽʹЩʣڣ֧ʵʱȼ񡣶ЩĿ꣬ʱǳͻģ㷨ӦʵӦĳЩĿҪڷֲ·ĵ㷨ҪŶ(Class Based Queueing)[4]ֲȨƽŶ㷨(Hierarchical Packet Fair Queueing)ͷֲ㷨(Hierarchical Fair Service Curve)Уֲ㷨ʱӺʹص㣬ɸЧôԴ
2.3.2 
ӷ仺ͻʱζݰͬ㷨ȣ㷨ֻݹ̶״̬ϢرһЩȫ״̬ϢһЩض״̬Ϣջݰڸʵ֡
㷨Ҫβǰ(Random Early Detection)[5]Ľ㷨ͳ·һβ㷨β㷨ڻʱݰʵãҪ⣺һǲƽռû壬TCPӿռô壬ֹӹƽʹԴһǹռû壬·ڻʱ׶ͻIPʹһЩTCPͬٷʹڣ·ʡ
RED㷨һŶӹ㷨β㷨ͬRED·ڻǰݰʽӵָʾǰ֪ͨTCPӽݰʡʹָȨƶƽͨ˲ƽгȡ·ƽгȺߡޱȽϡƽгСڵʱ·κݰݰͷӵʶƽгȴڸʱ·ÿݰͷӵšƽгڸߡ֮䣬·ԸpaÿµIPͷӵʶpaƽгȱRED·άһԶ̵ƽŶӳȣɼݰŶʱӣͬʱݰʳɱݰɱ֤һĹƽԺͷֹͬؽ
REDĽ㷨FRED(Flow Random Early Detection)RIO(Red with In/Out)FREDͬRED㷨ȣɸõر֤TCPӹƽʹôFREDҪӷݰRIO㷨RED㷨Ӧݰвͬȼ˼ǵ·ӵʱ߸ʵضȼݰʵһֵʹơ
3 
QoS·ṹ·ڲƣṹݰࡢݰȺͻʵ㷨ЩʵַһWFQкܺõԣҪ󣬵չԽϲʵָԸߣһRIO㷨кܺõչԺ͵͵ʵָӶȣ֧ԲθĽЩ㷨ͬʱԡչԺʵָҪ󣬻Ҫһо
ߵλϺͨѧӹ,Ϻ200030
ο
1 Clark D D,Shenker S,Zhang L.Supporting Real-time Applications in an Integrated Services Packet Network:Architecture and Mechanism.SIGCOMM'92,1992-08 14-16
2 Degermark M,Brodnik A,Carlsson S et al.Small Forwarding Tables for Fast Routing Lookups.SIGCOMM'97,19973-14
3 Srinivasan V,Varghese G,Suri S et al.Fast and Scalable Layer Four Switching.SIGCOMM'98,1998-08-31191-202 
4 Floyd S.Jacobson V.Linking-sharing and Resource Management Models for Packet Networks.IEEE/ACM Transactions on Networking,1995,3(4)1240
5 Floyd S,Jacobson V.Random Early Detection Gateways for Congestion Avoidance.IEEE/ACM Transactions on Networking, 19931(4)127
