ѧ
JOURNAL OF SOFTWARE
2000Vol.11No.2P.179-186



IP·ϵṹ
㡡ǿ⽨ƽ
ժҪſĲϷչ,齨·ȻҪǧױϵת,ߺ봦·޷˷ľ,ͶԴͳ·ϵṹϾս.ȫ˽ڿIP(Internet protocol)·о½չ,ϸĿIP·ϵṹ,,ָ˸Ҫһо.
ؼʣ,IP(Internet protocol),·,ϵṹ.
ţTP393
Analysis of Broadband IP Router Architecture
XU KeXIONG Yong-qiangWU Jian-ping
(Department of Computer Science and Technology Tsinghua University Beijing 100084)
AbstractWith the increasing development of broadband technology,the speed of packets forwarding needs to be over gigabits per second for the backbone routers.Traditional routers have some insuperable barriers and can not solve the problem based on shared-bus and central processing unit.It is a great challenge for the future router architecture.In this article,the authors survey the recent advances in the research of broadband IP router,and analyze the architecture design of the fourth generation backbone router in detail.Finally,some challenging open problems are identified.
Key wordsBroadband,IP (Internet protocol),router,architecture.
InternetķٷչͿĲϳ,Internetĺ豸·ҪԽԽ.ͳĻߺ봦ṹ·ϵṹϵľ,Ѿ޷齨.,϶ԿIP·оҲԾ,˼ֲͬо˼·1,2,˼Ҫ4:1 ·棨routing engineת棨forwarding engineֿ,ֲתȫ·ɱж;2 ÿٵӲʵIPĵıͷѰת;3 öֲʽĽӿڵԪģʽȡ봦ӽӿڿģʽ;4 ýṹswitch fabric߸ӿڵԪ֮ͨٶ.о,IP·ɼķչѾͽԼķչлؽһ.ĿǰIP·õҪϵṹ,ϸеļѵӦĽ,˽һķչ.
ĵ1ڷIP·4Ҫϵṹ.2IP·дڵҪ.3˵ǰЩҪķ.4ܽȫ,ָ˽һо.
1 IP·ϵṹ
ϵṹ,IP·˴ӵдӹߵṹķչ.ǿ԰Ϊ4.
ʽϵṹ.ǵ1·Ҫõϵṹ:ڵͨCPU,ʹʵʱϵͳͼ1(a)ʾ.ϵṹҪǿǵЭ龭仯,жЭ·ĳضЭŻ,ʱӵĽ͹ȸתҪ.ϵṹ·ʹͨüʵ,һͨüͬ,жӿڿ,ӿڿ֮ͨϵͳ.ӿڵıȱ͵봦,봦е·һĵַ,͵Ӧӿ.·ЭЭ봦ʵ.
Ȼ,·ҪɹߵʺCPUתĵٶȾ.CPUִжʵʱ,,ϵͳѡ൱Ҫ,ʵʱϵͳҲȽϸ,,ϵṹĿչԣscalabilityȽϲ,ҺӿڿӿʵӦ.
ദʽϵṹ.ڵ1·,е·ɼ㶼봦Ͻ,ڸٺͶ̬仯绷,·ɼԼ·ת.2·ͼ1(b)ʾõĶദʽϵṹ·תֲڸ,ӶЧؽ·ɼ.
ڶദʽϵṹ,ӿڿбصĿٴ͸ٻԼж:ÿӵĵ1͵CPU·Ͻд,·ڵõӿڿĶ˿ں֮,䴫ӿڿ,ӿڿڱظٻһ.,ԺķͿֱӿڿ֮佻پCPU.ֽṹ,·ɼתɸֲʽϵת,,תʹõĸٻƾͱȽϾ.ǿΪÿӽһתone forwarding item per connection,OFIPC,Ҳÿ·ɽһ(one forwarding item per route,OFIPR),OFIPR,ʹǳ,ٻҲ̫.
ϵṹҪǹߵ,ߵֱ·,Ϊϵͳ޷ƿ.һ,ϵṹ·.·кܸߵİתٶ,,ӿڿϵ·һ㲻оֲ.,ӿڿϵĸٻѷ,ҲͺѼCPUĸ.Ϊ˽һ,ÿӿڿ϶·ɱ,Խһǿ·.
ദʽϵṹ.Ϊ˽2·еϵͳƿ,˶ദʽϵṹͼ1(c)ʾ.ϵṹ,2ṹеϵͳ߱ṹ.ṹṩȹ߸ߵöĴ,֧еĸӿ.
ɵ,µ֮.·,ÿĵĴµƿ.Ϊ߱Ĵٶ,µϵṹ.
дʽϵṹ.ף1˲бĴķ,ʹַԼؼӿ챨Ĵٶ.÷Ļ˼¿,һ˵ܳеӿͬʱ,,ͨת·Ķ˿ܶ.ϵṹͼ1(d)ʾ.



Fig.1The architectures of four kinds of principal routers
ͼ14ֵ͵·ϵṹ
ͼ1(d)ʾϵṹ,תֻһַ,ҵһַ,͸ӿڿ,,ӿڿͿֱӰѺ̵ıͽӿ.Ҫע,ֻҪѱĵͷͽת.ԼٻṹϲҪıĴ为.ֻڽӿڿ֮䴫.
ϵṹ,ֻҪ㹻ת,Ϳʹ·߱Ҫת.ʹϵṹΪһתû㹻еӿڿͻԵĴ.Ҫڶӿڿ֮乲ת.
˵,תȿԺӿڿһ,Ҳ໥.תǶĲ,ôͨתӿڿıͿ߼ٰת,ף3۵50GbIP·ʹַ.,תӿڿֿṹĸ,ڶת֮仹Ҫʹøƽ.,ҲеƷӿڿת漯һ,NetStar˾GigaRouter4.ַ,ת治еӿڿ֮乲,ÿӿڿһת.ʵ,ϵṹǶദʽϵṹ.ʹϵṹ뱣֤תܹӿڿͻԵĴ.
2 IP·еҪ
ĿǰĿIP·Ҫõ1ᵽĵ3ֺ͵4ϵṹ.,ǽҪϵṹ·.
ڿIP·,ܵϵͳƿ:һǱĵת.ڹʽĽṹ,ϵͳҪƿ.ڽʽṹ,ڽṹĴܸ,תϵͳҪƿ.һǱĵ·,תҲΪ·ɱв·.һĵʱ,·ĿĵַתвĿĶ˿ں.һ˵,תµʽ·:Ŀַ/,߼˿ںš;ܵĿĵַΪAıʱ,˿ڽת,ʹA,Ӧַһ,ö˿ھͳΪѡ˿֮һ.ѡĶ˿ڽкѡ˿ӦĶ˿,ⱻΪǰ׺ƥ䣨the longest prefix match.˵,һ̨··ɱ3:166.111.1.5/16,1,166.111.225.0/18,3,128.0.0.0/8,5.ô,һĿĵַΪ166.111.195.1ıĽͬʱƥǰ.ڶ˿3Ӧ·ɱ,,ñĵĿĶ˿ӦǶ˿3.
пԿ,Ч·ɱ൱ѵ.,··ɱһ͵ֵ15K·ɱ,˳,Чʽǳ.Ϊ˾·ٶ,Ǳ뾡ܼ·ɲҵʱ.,һĿܻͬʱƥ·ɱ,Ǳ·ɱѰƥ.ǰҲᵽ,,ʹ·ɱٻ沢·ɱҵٶ.,ǻҪʹµķ·ɱĲٶ.
/˿ںͽṹٶȵĲͬ,IP·ԷֳŶӵģinput-queuedŶӵģoutput-queued·.ṹĴе˿ڵĴܺ,ôľֻ˿Ŷ,·ΪŶӵ·.,ľͻŶ,·ͱΪŶӵ·.
Ŷӵ·Ŷӵ··ɲҵƿ,֮,ǸԻԼеƿ.Ŷӵ·еıĶ˿ڵĻŶ,˿ڻĴȡٶ̬ܶ洢;̬洢ķʱƵ.սŶ·.ô,еĶжŵһ,أ,Ҫٲṹ֮ľ,һٶƽٲ൱ѵģ5,6.
3 ҪĽ
ڽϽڿIP·оȡõ½չν2ᵽļҪ.
3.1 Ч·ɱ
ڵ2Ѿᵽ,ʹýʽṹĿIP·,Ҫƿ·ɱв뵽ﱨĵĿĵַƥǰ׺·.֪,·ɱҵٶɲʱҪڴĴڴٶȹͬ.,һ㷨Ҫִ8ڴ,ÿڴʵʱ60ns,ôһ·ɵʱ480ns,Ҳ˵ÿִдԼ200·ɲ.ʹͬ㷨,ʹ÷ٶΪ10nsڴ,ôÿʹԼִ1250·ɲ.
·ɱ㷨ʱҪǵһ·ɱ޸.о,·ɱı仯ǱȽ,ԼֻҪÿӸһΣ7,ʹñȽϸӵݽṹ߲ٶ,Ĵ޸·ɱҪʱ.
ı·ɱݽṹ,,ÿӸڵ㵽Ҷӽڵ·ͶӦ·ɱеһ.,Ѱǰ׺תΪѰ·8.һ˵,㷨ĸڵ㿪ʼ,ʹĿĵַеλƥ䵱ǰڵӽڵ,ֱҵһƥΪֹ.,²·ɱѵʱҵǰ׺ƥĳȳ.㷨Ҫ˼ǴڵֻҪٵӽڵñпֵܵ.㷨Լڴ,ĴҪиεڴ.ڴ۸½,ƷѾԽԽ.
·ɱܵķж,ǿ԰Ƿֳ3:
(1) Ӳļ
õĻӲļʹ洢content-addressable memories͸ٻ߲ٶ.ּ·ɱı仯չ,˲Ҫʹô·ɱ·.,оԱĻӲĲ԰ڴ߼ɵһоƬ,Լؼڴʱ.
2ֻӲļͨʹõڴ洢·ɱ,ͨռ任ȡʱ.ף9һַ,ʹ33Mڴ·ɱ.ﵽڶ,ֻҪһ·ɱͿԵõĿĶ˿,,ҲֻҪ·ɱ.ͨʹһЩŻ,԰ڴʹ9M,Ӧʱͻ3ڴʱ.÷Ļ˼:32λĿĵֳַ,ǰ24λһ,8λһ.ʹǰ24λΪֱַӲ·ɱ,Ŀĵַ·ɳС24λ,һڴʱڲҵĿĶ˿.Ŀĵַ·ɳȴ24λ,·ɱӦλûõһֵ,øֵĿĵַ8λΪַȥһ洢,,,ҲֻҪڴ.÷ĺ˼ǰ·ɱɢ,,1166.111.0.0/16,1·ɽ·ɱռݴӵַ166,111,0,0ʼ256.Ȼ·ɱĲٶ,ȴ·ɱµĲ.1·ɵĸıҪ´·ɱ.,Ϊ߸µٶ,ף9ӦĽ.
(2) 
10ʹøӵǽݽṹ·ɱ.,·ɱͿԷڴĵ1ٻ.ַ֧ǧױʵ·ɱ.ʹף10ݽṹ,԰Ѿ40000·ɵ·ɱѹֻ150Kֽ.
(3) ϣ
ϣҲ·ɱ.Ѱǰ׺ƥ˹ϣʹ.ʵʹ,ǲ֪һĿĵַӦǰ׺ƥǶ೤.һķǳԲͬȵ,ѡƥ.ѡȿʹõʽ,Ҳʹòηʽ,ʹõַǰλָһǰ׺б.,ЩĿչԶܲ.
ף11һֿչĻڹϣĲ㷨,㷨nλַǰ׺ƥĲΪO(logn).㷨ÿֳȵǰ׺ʹһĹϣ,ʱǴǰ׺ʼ,Ǹǰ׺ִ۰.Ϊִܹ۰,Ҫϣֶ,ֶָʧʱ,ǵȸıв,ǵСһЩıв.,ף11ݻӦļٱֶεĴ洢ռ.㷨ԱȽ׵չIP v6.
3.2 ٵıת
ṹǿIP·еĹؼ,ǽٱתҪʽ,ֱӾ·.ṹһԲý濪غ͹ڴַʽʵ.濪صٶܵ,ڴٶڴٶȵ.Cisco˾Ƴĸ߶·GSR12000ϵ,ʹ˽濪Ϊṹ12,Juniper˾Ƴ·Juniper M40ʹ˹ڴΪṹ13.濪غ͹ڴ涼ܹﵽȽϸߵ,ܹﵽÿ40Gbps8OC-48·ӿڿʱϵ.ڴصʵּ,ҲܴﵽȽϸߵ,ܵĽһ߽ܵڴʵ,չԱȽϲ,·ӿڿ϶ʱ,ܽܵһӰ.濪ܹﵽȽϸߵ,չԺ,ҪƵĵ㷨øӲʵֵ.ǶԽ濪ص㷨о,ѾƲʵáʵּ򵥵ĵ㷨,,ĿǰIP·ʹý濪Ϊṹ,ǽص۽濪صʵ.
ʹý濪ҪµĿ:,濪ؿӿڿ֮佨㵽,ζӿڿ֮Ըٴ.Ŀǰ,òƷ,оƬоƬ·ٶѾԴﵽ1Gb/s,ʵѾԴﵽ410Gb/s.,濪ؿͬʱṩ·,ֻҪԴĿĵزͻ,Ϳͬʱ,ԼӴ.
ʹý濪ʱ,Ҫѱıɶķ.ʹöķʱ,ԸݷĴСʱƬ,ʱƬһһش.ʹñ䳤ķ,ôͨ濪صʱ,ͱ֪״̬,ʹ൱,Һƽ.
ʹý濪ʱ,Ҫ¼Ҫ.
3.2.1 
ʹý濪Ϊṹʱ,ܻ3.
1·ͷ.˿ڵȴķ鶼ʹһŶ,ͻ·ͷ.˵,ͷķҪȥĶ˿æ,ô˷ֻڶеȴ.ʱʹķҪȥĶ˿ǿе,Ҳûлᷢ.Ἣؽͽ濪ص.ף14һֳΪУvirtual output queuing,VOQĻ·ͷ.˼·:ϵͳn˿ںn˿,ôÿ˿ڶnзֱӦÿ˿.,һ˿ڷ˿ڲӰ.Ȼ,ʵʱ,ÿ˿ֻӦڽ濪еһ,˳֮Ϊ.
2.жӦĽ濪صֻ1,,ÿֻܽһ.жʱ,òĶͷʹ״̬.Ӱ콻濪ص,ֻķӳ.
3.˿ڵķ鶼Ҫȥͬһ˿,ͻᷢ.һ,Ӱ콻濪ص,ֻķӳԽ.ף12ֽ.1,ȼ.ÿл4ȼ,ӦҲͱ4,ȼķȷ.ַȫ,ȼͬķ֮仹,Ա֤ȼķӳٱȽС.2,ӿ콻濪صĽٶ.濪صĽٶǶ˿ٶȵ,ô,ڶ˿˵,濪ܹһν.˵,n˿ںn˿,ô濪صٶȱǶ˿ٶȵnܱ֤û.ף12ָ,ʵʹ,ֻҪ濪صٶǶ˿ٶȵ,ͿԻ֤.
3.2.2 㷨
濪صһҪǵ㷨.㷨ƵĻҪ:
(1) Чʸ.Чʵĵ㷨Ӧܹͬʱƥ価ܶ.һ˵,ʹӲѿټƥ,,һƵ㷨ʱǾѰҴŵ㷨.
(2) ȶ.е,㷨ӦѸҵеĵ.
(3) ĳЩԶòӦ.
(4) .㷨ִ,򽫻濪شĴ.
(5) ʵ.㷨ӦӲʵ.ʵֵĸ԰ά״̬,Щ״̬ߵ߼ĸӶȺ޸״̬ʱͨſ.
㷨ԷֳŶӵĵ㷨Ŷӵĵ㷨.,һֱΪŶӵĵ㷨ܱȽϲ,Ŷӵĵ㷨˴о1517.,Ŷӵĵ㷨Ҫ˵Ľӿ˵NNǶ˿,ͻִ.˿ٶȵĲߺ˿,Ŷӵĵ㷨Ѿٽ濪صҪ.,оԱ°עеŶӵĵ㷨.
ף18һŶӵĳΪiSLIPiterative round-robin matching with SLIPĽ濪ص㷨.㷨һ򵥵ѭ㷨,ÿѭһ뵽Ϊֹ,ֱпܵΪֹ,Ȼͬʱ.ÿѭֳ3,1;2ÿеѡȼߵĽлӦ;3ÿ˴ӿܵĶӦѡȼߵĽ.Ϊ˱֤ƽ,ʹȼת.Ϊܹಥ,ף18ݰiSLIP㷨չɿֶ֧ಥESLIPextended SLIP12.㷨ԭ,Ӳʵ,Ҿкܺõܣ5.Cisco˾Ƴĸ߶·GSR12000ϵеĽ濪ص㷨ͲiSLIPESLIP.
㷨ĽһоṩԷQoSquality of service֧.ף19һֽ롢ŶӵĽṹCIOQcombined input/output queuing,ɵ㷨,ýṹܹڱ֤߷齻ʵͬʱṩ֧,ýṹļٱΪ2.ף20,ŶӵĽṹķֽ֧о,˼ԸҲҪٱȵĵ㷨.λַ֧ĵȽǵ㷨Ľһо.
3.3 ܵʵʱ·ϵͳ
ǰ·ϵͳһ㶼һ򵥵ں,ṩķԭ.ЭĲϷչ,·ϵͳҪҲԽԽ,·ϵͳҪܹ֧·Эĸִܵ,ҪܹϲЭĶ̬.Ҫһָܵġģ黯ġչĲϵͳ֧.
ף21˻plugin·ϵͳϵṹ,ڸϵṹ,ϲЭΪplugin̬صϵͳںִ,Իøܺ͸߿չ.ף21ݸݴϵṹһչļɷ·.
ַʽһ˾磨active network,,ͨ·װЭ22.ַʽ˺ܴİȫ,ܷȡúܺõЧдڽһо.
4  
ż绥ģĲ,·ҪԽԽ.˽ڿIP·оȡõ½չ.缼ķչ,ǱоȨĿIP·.ڹҡ塱滮ڼ,廪ѧѧ뼼ϵƺͿܳCisco˾7000ϵ·ĸ·23,ΪһоõĻ.ڸٿIP·,Ҫһо:
(1) ֧ʶ.һʱڴĳԴַĳĿĵַı.һTCPӷ͵ı,ҲеUDPuser datagram protocol.ͨ,ŻԴʹ,ٻ.ڱʶʱҪʹ÷㷨.ǰ۵ĸ·㷨ѱ޸ĳɷ㷨.ĿǰȱͨöЧ.ЩҪнһо.
(2) ֧ԴԤ.InternetԴԤֺ֧,Ǿ··ǿIP·õĶǾͻ,֧ȼ.Ӧõķչ,ǶķQoSҪԽԽ,Ϊַ֧Ҫ,Ҫ·֧ԴԤ.֧ԴԤҪᵽʶ,ʶĻ,ҪʵͨõĵȺͻ㷨,ַ֧ĽṹЧ.
(3) Чʵ·ϵͳ.ǰ·תIPӲ豸.,·ϵͳܺ,һ㶼ṩӦñ̽ӿAPIapplication programming interface.Ӧõķչ,ûԱԽԽҪ̬·мģṩǽȻ.Ҫ·ϵͳܹṩһġЧʵĻ֧Ӧ.
ĿоõȻѧ(No69682002,69725003)͹ҡ塱Ƽ
Ŀ
߼飺㡣1974ʿҪоΪϵṹϵͳ
ۡ
ǿ,1974,ʿ,ҪоΪϵṹ,簲ȫ.
⽨ƽ,1953,ʿ,,ʿʦ,ҪоΪϵṹ,
Э.
ߵλ(廪ѧѧ뼼ϵ100084)
ǿ(廪ѧѧ뼼ϵ100084)
⽨ƽ(廪ѧѧ뼼ϵ100084)
οף
1Asthana A,Delhp S,Jagdish H et al.Design of a Gigabit IP Router.Technical Report,11251-911105-09TM,AT&T Bell Laboratorys,1991
2Asthana A,Delhp S,Jagdish H et al.Towards a gigabit IP router.Journal of High-Speed Networks,1992,1(4):281288
3Partidge C,Carvey P P,Burgess E et al.A 50Gb/s IP router.IEEE Transactions on Networking,1998,6(3):237248
4Kachelmeyer D.A New Router Architecture for Tomorrow's Internet.NetStar,Inc.,http://www.netstar.com
5McKeown N.Scheduling algorithms for input-queued cell switchs Ph.D.Thesis.Berkeley,CA:University of California,1995
6McKeown N,Anantharam V,Walrand J.Achieving 100% throughput in an input-queued switch.In:Toshiharu Hasegawa,Pickholtz R L eds.Proceedings of the IEEE INFOCOM'96.San Francisco,CA:IEEE Computer Society Press,1996.296302
7Labovitz C,Malan G R,Jahanian F.Internet routing instability.ACM Computer Communication Review,1997,27(4):115126
8Stevens W R.TCP/IP Illustrated,Vol.2.MA:Addison-Wesley,1995.220223
9Gupta P,Lin S,McKeown N.Routing lookups in hardware at memory access speeds.In:Guerin R ed.Proceedings of the IEEE INFOCOM'98.San Francisco,CA:IEEE Computer Society Press,1998.12401247
10Brodnik A,Carlsson S,Degermark M et al.Small forwarding tables for fast route lookups.ACM Computer Communication Review,1997,27(4):314
11Waldvogel M,Turner J,Plattner B.Scalable high speed IP routing lookups.ACM Computer Communication Review,1997,27(4):2536
12McKeown N.Fast Switched Backplane for a Gigabit Switched Router.White Paper,http://www.cisco.com
13Semeria C.Internet Backbone Routers and Evolving Internet Design.White Paper,http://www.juniper.com
14Mekkittikul A,McKeown N.Practical scheduling algorithm to achieve 100% throughput in input-queued switches.In:Guerin R ed.Proceedings of the IEEE INFOCOM'98.San Francisco,CA:IEEE Computer Society Press,1998.792799
15Kelly.Effective bandwidths at multiclass queues.Queuing Systems Theory and Applications,1991,9(1-2):515
16Keshav S.An efficient implementation of fair queuing.Internetworking:Research and Experience,1991,2(3):157173
17Kesidis G,Walrand J,Chang C.Effective bandwidths for multiclass Markov fluidsand other ATM sources.IEEE/ACM Transactions on Networking,1993,1(4):424428
18McKeown N,Izzard M,Mekkittikul A et al.Tiny Tera:a packet switch core.IEEE Micro,1997,17(1):2633
19Shang-Tse Chuang et al.Matching output queuing with a combined input/output-queued switch.IEEE Journal on Selected Areas in Communications,1999,17(6):10301039
20Anthony C K,Siu Kai-yeung.Linear-complexity algorithms for QoS support in input-queued switches with no speedup.IEEE Journal on Selected Areas in Communications,1999,17(6):10401056
21Decasper D,Plattner B,Parulkar G M et al.Scalable high-performance active network node.IEEE Network,1999,13(1):819
22Alexander D S,Shaw M,Nettles S M et al.Active bridging.ACM Computer Communication Review,1997,27(4):101111
23Fan Xiao-bo,Lin Chuang,Wu Jian-ping et al.Performance model and analysis of a distributed router.Chinese Journal of Computers,1999,22(11):15
(,ִ,⽨ƽ.ֲʽ·ģ.ѧ,1999,22(11):15)
ոڣ1999-07-01
޸ڣ1999-09-28
