微信服务号

微信订阅号

2025-6-5- 19
Home > Archive>Volume 19, Issue 6, 2008 >1452-1464
PDF HTML XML Export Cite reminder
Scalable Router
Author:
Affiliation:

  • Article
    • | |
  • Metrics
    • |
  • Reference [89]
    • |
  • Related [20]
    • |
  • Cited by [2]
    • | |
  • Comments
    Abstract:

    This paper presents a survey on the study of the scalable router and proposes a hierarchical model based on the study of the architecture and models of the scalable router. The model splits the scalable router into six layers from bottom to top, which are interconnection network and data switching layer, routing lookup layer, standard interface layer, distributed operating system layer, distributed routing behavior layer and single image management layer. The paper provides surveys on the research of each layer, and finally concludes and analyses the difficulties of current development of the scalable router.

    Reference
    [1]Xu K,Wu JP,Xu MW.Advanced Computer Networks:Architecture,Protocol Mechanism,Algorithm Design And Router Technology.Beijing:Mechanism Industry Press,2005.496-500 (in Chinese).
    [2]Iyer S,McKeown NW.Analysis of the parallel packet switch architecture.IEEE/ACM Trans.on Networking,2003,11(2):314-324.
    [3]Gupta P.Algorithms for routing lookups and packet classification[Ph.D.Thesis].Stanford:Department of Computer Science,Stanford University,2000.
    [4]Keslassy I,Chuang ST,Yu K,Miller D,Horowitz M,Solgaard O,McKeown N.Scaling Internet routers using optics.In:Proc.of the 2003 Conf.on Applications,Technologies,Architectures,and Protocols for Computer Communications.New York:ACM Press,2003.189-200.http://tiny-tera.stanford.edu/～nickm/papers/sigcomm2003.pdf
    [5]T640 Routing Node and TX Matrix(tm) Platform:Architecture.White Paper.http://www.juniper.net
    [6]Cisco CRS-1 series carrier routing system getting started guide.http://www.cisco.com
    [7]The Avici TSR:Cornerstone of the multi-terabit core.http://www.avici.com
    [8]Kohler E.The Click modular router[Ph.D.Thesis].Department of Electrical Engineering and Computer Science,MIT University,2001.
    [9]Montz AB,Mosberger D,O'Malley SW,Peterson LL,Proebsting TA.Scout:A communications-oriented operating system.In:Proc.of the 5th Workshop on Hot Topics in Operating Systems (HotOS-V).1995.58-61.http://lahtermaher.org/pub/plan/xkernel/Papers/ scout_hotos.ps
    [10]Decasper D,Dittia Z,Parulkar G,Plattner B.Router plugins:A software architecture for next generation routers.IEEE/ACM Trans.on Networking,2000,8(1):2-15.
    [11]Gottlieb Y,Peterson L.A comparative study of extensible routers.In:Proc.of the 2002 IEEE Open Architectures and Network Programming Conf.New York:IEEE Press,2002.51-62.http://www.cs.princeton.edu/nsg/papers/routerstudy_openarch_02/ routerstudy-openarch.pdf
    [12]Karlin S,Peterson L.VERA:An extensible router architecture.In:Proc.of the 4th Int'l Conf.on Open Architectures and Network Programming (OPENARCH).2001.3-14.http://www.cs.princeton.edu/nsg/papers/vera_cn_02/vera-cn.pdf
    [13]Handley M,Hodson O,Kohler E.Xorp:An open platform for network research.ACM SIGCOMM Computer Communication Review,2003,33(1):53-57.
    [14]Welling G,Ott M,Mathur S.CLARA:A cluster-based active router architecture.IEEE Micro,2001,21(1):16-25.
    [15]Ott M,Welling G,Mathur S,Reininger D,Izmailov R.The JOURNEY active network model.IEEE Journal on Selected Areas in Communications,2001,19(3):527-537.
    [16]Guo JN,Chen F,Bhuyan L,Kumar R.A cluster-based active router architecture supporting video/audio stream trans-coding service.In:Proc.of the Int'l Parallel and Distributed Processing Symp.2003.8-15.http://www-lih.univ-lehavre.fr/Intranet/proceedings/ IPDPS2003/DATA/11_02_059.PDF
    [17]Yu X.Research on the key technologies of cluster based router[Ph.D.Thesis].Wuhan:Huazhong University of Science and Technology.2005 (in Chinese with English abstract).
    [18]Kuhns F,DeHart J,Kantawala A,Keller R,Lockwood J,Pappu P,Richards D,Taylor D,Parwatikar J,Spitznagel E,Turner J,Wong K.Design of a high performance dynamically extensible router.In:Proc.of the DARPA Active Networks Conf.and Exposition (DANCE).2002.http://www.arl.wustl.edu/projects/fpx/references/dance02.pdf
    [19]Chiueh TC,Pradhan P.Suez:A cluster-based scalable real-time packet router.In:Proc.of the 20th Int'l Conf.on Distributed Computing Systems.2000.136-144.http://academic.csuohio.edu/yuc/perf-00/References/ICDCS00-suez.ps
    [20]Pluris massively parallel routing.White Paper.http://www.kotovnik.com/~avg/pluris/wp/
    [21]Fan XB,Lin C,Wu JP,Xu L.Performance model and analysis of a distributed router.Chinese Journal of Computers,1999,22(11):1223-1227 (in Chinese with English abstract).
    [22]Guan JB.Research on the architecture and key technologies of cluster-based routers[Ph.D.Thesis].Changsha:National University of Defense Technology,2005 (in Chinese with English abstract).
    [23]Wang BS.Research and implementation on a new router architecture[Ph.D.Thesis].Changsha:National University of Defense Technology,2005 (in Chinese with English abstract).
    [24]Gong ZH,Fu B,Lu ZX.Research on the architecture of software-based cluster routers.Journal of National University of Defense Technology,2006,8(3):40-43 (in Chinese with English abstract).
    [25]Doria A,Hellstrand F,Sundell K,Worster T.General switch management protocol (GSMP) V3.RFC3292,2002.
    [26]Biswas J,Lazar AA,Huard JF,Lim K,Pau LF,Torstensson S,Wang WG,Weinstein S.The IEEE P1520 standards Initiative for programmable network interfaces.IEEE Communications Special Issue on Programmable Networks,1998,36(10):64-70.
    [27]Doria A.ForCES Protocol Specification.IETF draft.2007.
    [28]Bergen C,Lynch J.Streaming interface (NPSI) implementation agreement.White Paper,Network Processing Forum Hardware Working Group,2002.http://www.npforum.org/techinfo/HWStreamingIA.pdf
    [29]Anderson TE,Owicki SS,Saxes JB,Thacker CP.High speed switch scheduling for local area networks.ACM Trans.on Computer Systems,1993,11(4):319-352.
    [30]McKeown N.The iSLIP scheduling algorithm for input-queued switches.IEEE/ACM Trans.on Networking,1999,7(2):188-201.
    [31]Rojas-Cessa R,Oki E,Chao HJ.On the combined input-crosspoint buffered switch with round-robin arbitration.IEEE Trans.on Communications,2005,53(11):1945-1951.
    [32]Chang CS,Lee DS,Jou YS.Load balanced Birkhoff-von Neumann switches,part I:One-stage buffering.Computer Communications,2002,25(6):611-622.
    [33]Yue ZH,Zhao YJ,Wu JP,Zhang XP.Designing scalable routers with a new switching architecture.In:Proc.of Autonomic and Autonomous Systems and Int'l Conf.on Networking and Services.2005.
    [34]Narasimha MJ.The Batcher-Banyan self-routing network:universality and simplification.IEEE Trans.on Communications,1988,36(10):1175-1178.
    [35]Lawrie DH.Access and alignment of data in an array processor.IEEE Trans.on Computers,1975,24(12):175-189.
    [36]Wu CL,Feng TY.On a class of multi-stage interconnection networks.IEEE Trans.on Computers,1980,29(8):649-702.
    [37]Patel JH.Performance of processor-memory interconnection for multiprocessors.IEEE Trans.on Computers,1981,30(10):771-780.
    [38]Batcher KE.Sorting networks and their applications.In:Proc.of the AFIPS Spring Joint Computer Conf.1968.307-314.http://www.cs.kent.edu/～potter/research/papers/sort.pdf
    [39]M Pease.The indirect binary n-cube microprocessor array.IEEE Trans.on Computers,1977,6(5):250-265.
    [40]Jajszczyk A.Nonblocking,repackable,and rearrangeable Clos networks:Fifty years of the theory evolution.IEEE Communications Magazine,2003,41(10):28-33.
    [41]Sapountzis G,Katevenis M.Benes switching fabrics with O(N)-complexity internal backpressure.IEEE Communications Magazine,2005,43(1):88-94.
    [42]Tzeng NF.Multistage-Based switching fabrics for scalable routers.IEEE Trans.on Parallel and Distributed Systems,2004,15:304-318.
    [43]Tzeng NF,Mandviwalla M.Cost-Effective switching fabrics with distributed control for scalable routers.In:Proc.of the ICDCS.2002.65-73.
    [44]Fuller V,Li T,Yu J,Varadhan K.Classless inter-domain routing (CIDR):An address assignment and aggregation strategy.RFC1519,1993.
    [45]Xu K,Xu MW,Wu JP,Wu J.Survey on routing lookup algorithms.Journal of Software,2002,13(1):42-50 (in Chinese with English abstarct).http://www.jos.org.cn/1000-9825/12/42.pdf
    [46]Morrison DR.PATRICIA:Practical algorithm to retrieve information coded in alphanumeric.Journal of the ACM,1968,15(14):514-534.
    [47]Srinivasan V,Varghese G.Fast address lookups using controlled prefix expansion.ACM Trans.on Computer Systems,1999,17(1):1-40.
    [48]Nilsson S,Karlsson G.IP-Address lookup using LC-Tries.IEEE Journal on Selected Areas in Communications,1999,17(6):1083-1092.
    [49]Waldvogel M,Varghese G,Turner J,Plattner B.Scalable high speed IP routing lookups.In:Proc.of the ACM SIGCOMM'97.1997.25-36.http://sigcomm.org/sigcomm97/papers/p182.pdf
    [50]Degermark M,Brodnik A,Carlsson S,Pink S.Small forwarding tables for fast routing lookups.In:Proc.of the ACM SIGCOMM'97.1997.3-14.http://www.cs.ust.hk/~hamdi/Class/CSIT560/Reading/Lookup1.pdf
    [51]Mehrotra P,Franzon PD.Binary search schemes for fast IP lookups.In:Proc.of the Global Telecommunications Conf.(GLOBECOM 2002),Vol.2.2002.2005-2009.http://ants.iis.sinica.edu.tw/presents/Binary%20search%20schemes%20for%20fast% 20IP%20lookups.pdf
    [52]Berger,M.IP lookup with low memory requirement and fast update.In:Proc.of the High Performance Switching and Routing,HPSR 2003.2003.287-291.
    [53]Lim H,Lee B,Kim WJ.Binary searches on multiple small trees for IP address lookup.Communications Letters,2005,9(1):75-77.
    [54]Chiueh TC,Pradhan P.High-Performance IP routing table lookup using CPU caching.In:Proc.of the IEEE INFOCOMM'99.1999.1421-1428.http://citeseer.ist.psu.edu/131258.html
    [55]Song YL,Aboelela E.A parallel IP-address forwarding approach based on partitioned lookup table techniques.In:Proc.of the 29th Annual IEEE Int'l Conf.on Local Computer Networks (LCN 2004).2004.425-426.
    [56]Wang ZX,Wang HM,Sun YM,Zhang YX,Wu JX.High-Performance IPv4/IPv6 dual-stack routing lookup.In:Proc.of the 18th Int'l Conf.on Advanced Information Networking and Applications (AINA 2004).2004.476-481.
    [57]Lim H,Jung Y.A parallel multiple hashing architecture for IP address lookup.In:Proc.of the Workshop on High Performance Switching and Routing (HPSR 2004).2004.91-95.
    [58]Dally WJ.Performance analysis of k-ary n-cube Interconnection networks.IEEE Trans.on Computers,1990,39(6):775-785.
    [59]Zheng K,Hu CC,Lu HB,Liu B.A TCAM-based distributed parallel ip lookup scheme and performance analysis.IEEE/ACM Trans.on Networking,2006,14(4):863-875.
    [60]Deering S,Hinden R.Internet protocol version 6 (IPv6) specification.RFC1883,1998.
    [61]Zebra.Zebra Protocol.2001.http://manticore.2y.net/doc/zebra
    [62]Zheng K,Liu Z,Liu B.A scalable IPv6 lookup scheme via dynamic variable-stride bitmap compression.Computer Communications,2006,29(16):3037-3050.
    [63]Xu K,Wu JP,Yu ZC,Xu MW.HEROS:Router-Oriented distributed real-time operating system.Journal of Tsinghua University (Sci & Tech),2002,42(1):52-55 (in Chinese with English abstract).
    [64]Fan XB,Lin C,Wu JP,Xu K.Performance model and analysis of a distributed router.Chinese Journal of Computers,1999,22(11):1223-1227 (in Chinese with English abstract).
    [65]Levy E,Silberschatz A.Distributed file systems:Concepts and examples.ACM Computing Surveys,1990,22(4):321-374.
    [66]Denys G,Piessens F,Matthijs F.A survey of customizability in operating systems research.2002.
    [67]Pradhan P,Chiueh TC.Operating systems support for programmable cluster-based internet routers.In:Proc.of the Workshop on Hot Topics in Operating Systems.1999.76-81.http://citeseer.ist.psu.edu/27538.html
    [68]Wu K.Research on Software architecture for extensible router[Ph.D.Thesis].Beijing:Tsinghua University,2006 (in Chinese with English abstract).
    [69]Chan HCB,Alnuweiri HM,Leung VCM.A framework for optimizing the cost and performance of next-generation IP routers.IEEE Journal on Selected Areas in Communications,1999,17(6):1013-1029.
    [70]Liang ZY,Xu K,Wu JP,Xu MW.Routing management model in distributed routers.Journal of Tsinghua University (Sci & Tech),2003,43(4):503-506 (in Chinese with English abstract).
    [71]Zhang XZ,Lu XC,Zhu PD,Peng W.A synchronization framework and critical algorithm maintaining single image of ip forwarding tables among cluster router's nodes.Journal of Software,2006,17(3):445-453 (in Chinese with English abstract).http://www.jos.org.cn/1000-9825/17/445.htm
    [72]Basu A,Riecke JG.Stability issues in OSPF routing.In:Proc.of the ACM SIGCOMM 2001.2001.http://www.sigcomm.org/ sigcomm2001/p18-basu.pdf
    [73]Zhu S,Huang GM.A new parallel and distributed shortest path algorithm for hierarchically clustered data networks.IEEE Trans.on Parallel and Distributed Systems,1998,9(9):841-855.
    [74]Antonio JK,Huang GM,Tsai WK.A fast distributed shortest path algorithm for a class of hierarchically clustered data networks.IEEE Trans.on Computers,1992,41(6):710-724.
    [75]Cohen E.Efficient parallel shortest-paths in digraphs with a separator decomposition.In:Proc.of the 5th Annual ACM Symp.on Parallel Algorithms and Architectures.1993.57-67.http://akpublic.research.att.com/～edith/Papers/separator.ps.gz
    [76]Romeijn HE,Smithy RL.Parallel algorithms for solving aggregated shortest path problems.Computers & Operations Research,1999,26(10-11):941-953.
    [77]Zhang XP,Wu JP,Zhang N,Zhao YJ.BPA-A parallel shortest path algorithm for cluster-router.In:Proc.of the PDCS 2006.
    [78]Geoff Huston.Internet BGP Table.http://www.potaroo.net/
    [79]Labovitz C,Malan GR,Jahanian F.Internet routing instability.In:Proc.of the ACM SIGCOMM'97.1997.http://www.cdt.luth.se/ net/courses/99-00/smd076/articles00/internet-routing-instability.pdf
    [80]Ge ZH,Figueiredo DR,Jaiswal S,Gao LX.On the hierarchical structure of the logical Internet graph.In:Proc.of the SPIE ITCom.2001.208-222.http://routeviews.org/papers/hier.ps
    [81]CIDR REPORT.http://www.cidr-report.org
    [82]Rekhter Y,Li T,Hares S.A Border Gateway Protocol 4 (BGP-4).IETF RFC 4271,2006.
    [83]Huston G.Analyzing the Internet's BGP routing table.Cisco Internet Protocol Journal.2001,4(1).http://www.potaroo.net/papers/ ipj/2001-v4-n1-bgp/bgp.pdf
    [84]Xu K,Wu JP.Design and implementation of border gateway protocol BGP-4 based on event-driven programming.Journal of Software,2000,11(11):1516-1521 (in Chinese with English abstract).
    [85]Zhang XZ,Zhu PD,Lu XC.Fully-Distributed and highly-parallelized implementation model of bgp4 based on clustered routers.In:Proc.of the 4th Int'l Conf.on Networking (ICN 2005).2005.433-441.
    [86]Zhang XZ.Research on parallel processing of routing protocols[Ph.D.Thesis].Changsha:National University of Defense Technology,2005 (in Chinese with English abstract).
    [87]Goscinski A,Hobbs M,Silcock J.GENESIS:An efficient,transparent and easy to use cluster operating system.Elsevier Science,2002.557-605.
    [88]Cisco craft works interface configuration applications reference guide,release 3.2.Technical Report,Cisco Systems,Inc.,2005.http://www.cisco.com/
    [89]Garey MR,Johnson DS.Computers and Intractability:A Guide to the Theory of NP-Completeness.Greeman,1979.
    Comments
    Comments
    分享到微博
    Submit
Get Citation

张小平,刘振华,赵有健,关洪涛.可扩展路由器.软件学报,2008,19(6):1452-1464

Copy
Share
Article Metrics
  • Abstract:
  • PDF:
  • HTML:
  • Cited by:
History
  • Received:August 02,2007
  • Revised:January 24,2008
Links:Institute of Software, CASChina Computer FederationCASNSFC
You are the firstVisitors
Copyright: Institute of Software, Chinese Academy of Sciences Beijing ICP No. 05046678-4
Address：4# South Fourth Street, Zhong Guan Cun, Beijing 100190,Postal Code：100190
Phone：010-62562563 Fax：010-62562533 Email：jos@iscas.ac.cn
Technical Support：Beijing Qinyun Technology Development Co., Ltd.

Beijing Public Network Security No. 11040202500063