微信服务号

微信订阅号

2025年3月24日 17:36 星期一
首页 > 过刊浏览>2008年第19卷第6期 >1452-1464
PDF HTML阅读 XML下载 导出引用 引用提醒
可扩展路由器
作者:
基金项目:

Supported by the National Natural Science Foundation of China under Grant Nos.90604029, 60773150 (国家自然科学基金); the National High-Tech Research and Development Plan of China under Grant No.2077AA01Z219 (国家高技术研究发展计划(863))

  • 摘要
    • | |
  • 访问统计
    • |
  • 参考文献 [89]
    • |
  • 相似文献 [20]
    • |
  • 引证文献
    • | |
  • 文章评论
    摘要:

    对可扩展路由器的研究现状进行了综述,并在可扩展路由器体系结构和模型研究的基础上提出其分层模型,将可扩展路由器"自底向顶"地划分为互连结构和数据交换层,路由查找层、标准接口层、分布式操作系统层、分布式路由行为层和单映像管理层6层,并综述了每层的研究进展.最后进行了总结并分析了当前可扩展路由器发展的难点.

    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.

    参考文献
    [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.
    网友评论
    网友评论
    分享到微博
    发 布
引用本文

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

复制
分享
文章指标
  • 点击次数:8467
  • 下载次数: 10403
  • HTML阅读次数: 0
  • 引用次数: 0
历史
  • 收稿日期:2007-08-02
  • 最后修改日期:2008-01-24
文章二维码
友情链接:中国科学院软件研究所中国计算机学会中国科学院国家自然科学基金委员会CCF数字图书馆Int'l J of Softw Info计算机系统应用
您是第19728431位访问者
版权所有：中国科学院软件研究所 京ICP备05046678号-3
地址：北京市海淀区中关村南四街4号,邮政编码：100190
电话：010-62562563 传真：010-62562533 Email：jos@iscas.ac.cn
技术支持：北京勤云科技发展有限公司

京公网安备 11040202500063号