微信服务号

微信订阅号

2025年7月30日 20:51 星期三
首页 > 过刊浏览>2010年第21卷第10期 >2524-2541
PDF HTML阅读 XML下载 导出引用 引用提醒
互联网可扩展路由
作者:
基金项目:

Supported by the National Natural Science Foundation of China under Grant Nos.60673168, 90818004 (国家自然科学基金)

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

    全球路由表的高速膨胀,使互联网路由系统的可扩展性面临着严峻的挑战.为了缩减路由表,很多研究提出了新的路由解决方案.在介绍了互联网路由系统现状之后,从较高层次上将存在的解决方案分为短期方案、路由架构和可扩展路由算法3部分.着重介绍了路由算法和路由架构这两类工作,对经典的可扩展路由算法和路由架构进行了深入的分析和比较.最后讨论了有待解决的关键问题和未来的研究方向.

    Abstract:

    The Internet routing system is facing a serious scaling challenge due to the rapid growth of the global routing table. For the purpose of reducing routing table size, many studies have developed a lot of new routing solutions. After the paper introduces the background of the Internet routing system, a classification of new routing solutions is presented. Then, a typical scalable routing algorithms and architectures become the focus, and their basic ideas and characteristics are deeply analyzed and compared. Finally, some key issues and ideas for future research are discussed.

    参考文献
    [1] Meyer D, Zhang L, Fall K. Report from the IAB workshop on routing and addressing. RFC 4984, 2007.
    [2] Menth M, Hartmann M, Tran-Gia P, Klein D. Future Internet routing-motivation and design issues. Information Technology, Special Issue on Next Generation Internet, 2008,50(6):1?8.
    [3] Wu JP, Wu Q, Xu K. Research and exploration of next-generation Internet architecture. Chinese Journal of Computers, 2008,31(9): 1537?1548 (in Chinese with English abstract).
    [4] Narten T. Routing and addressing problem statement. Draft-narten-radir-problem-statement-02.txt, 2008.
    [5] Huston G. BGP routing table analysis reports. 2009. http://bgp.potaroo.net/
    [6] Tu R, Su JS, Peng W. Survey of naming and addressing architecture based on locator/identifier split. Journal of Computer Research and Development, 2009,46(11):1777?1786 (in Chinese with English abstract).
    [7] Hou J, Liu YP, Gong ZH. Key techniques of identifier-based routing. Journal of Software, 2010,21(6):1326?1340 (in Chinese with English abstract). http://www.jos.org.cn/1000-9825/3797.htm [doi: 10.3724/SP.J.1001.2010.03797]
    [8] Fuller V, Li T, Yu J, Varadhan K. Classless inter-domain routing (CIDR): An address assignment and aggregation strategy. RFC 1519, 1993.
    [9] Karpilovsky E, Rexford J. Using forgetful routing to control BGP table size. In: Proc. of the CoNEXT. Lisboa: ACM Press, 2006. http://www.cs.princeton.edu/~jrex/papers/forgetfulrouter.pdf
    [10] Internet research task force. http://www.irtf.org/
    [11] Kleinrock L, Kamoun F. Hierarchical routing for large networks: Performance evaluation and optimization. Computer Networks, 1977,1(3):155?174.
    [12] Massey D, Wang L, Zhang B, Zhang L. A proposal for scalable Internet routing and addressing. Internet Draft, draft-wang-ietf-efit- 00.txt, 2007.
    [13] Wang N, Ma HL, Cheng DN, Wang BQ. Hidra: A hierarchical inter-domain routing architecture. Chinese Journal of Computers, 2009,32(3):377?390 (in Chinese with English abstract).
    [14] Tsuchiya PF. The landmark hierarchy: A new hierarchy for routing in very large networks. ACM SIGCOMM Computer Communication Review, 1988,18(4):35?42. [doi: 10.1145/52325.52329]
    [15] Stoica I, Morris R, Karger D, Kaashoek MF, Balakrishnan H. Chord: A scalable peer-to-peer lookup service for Internet applications. In: Proc. of the ACM SIGCOMM. San Diego: ACM Press, 2001. 149?160. http://pdos.csail.mit.edu/papers/chord: sigcomm01/chord_sigcomm.pdf
    [16] Plaxton CG, Rajaraman R, Richa AW. Accessing nearby copies of replicated objects in a distributed environment. In: Proc. of the 9th Annual ACM Symp. on Parallel Algorithms and Architectures. Newport: ACM Press, 1997. 311?320. http://citeseerx.ist. psu.edu/viewdoc/download?doi=10.1.1.38.1850&rep=rep1&type=pdf
    [17] Caesar M, Castro M, Nightingale E, O’Shea G, Rowstron A. Virtual ring routing: network routing inspired by DHTs. In: Proc. of the ACM SIGCOMM. Pisa: ACM Press, 2006. 351?362. http://research.microsoft.com/en-us/um/people/antr/MS/vrr_sigcomm.pdf
    [18] Kim C, Caesar M, Rexford J. Floodless in SEATTLE: A scalable Ethernet architecture for large enterprises. In: Proc. of the ACM SIGCOMM. Seattle: ACM Press, 2008. 3?14. http://www.cs.princeton.edu/~chkim/Research/SEATTLE/seattle.pdf
    [19] Caesar M, Condie T, Kannan J, Lakshminarayanan K, Stoica I, Shenker S. ROFL: Routing on flat labels. In: Proc. of the ACM SIGCOMM. Pisa: ACM Press, 2006. 363?374. http://www.cs.uiuc.edu/~caesar/papers/rofl.pdf
    [20] Cowen L. Compact routing with minimum stretch. Journal of Algorithms, 2001,38(1):170?183. [doi: 10.1006/jagm.2000.1134]
    [21] Thorup M, Zwick U. Compact routing schemes. In: Proc. of the ACM Symp. on Parallel Algorithms and Architecture (SPAA). Heraklion: ACM Press, 2001. 1?10. http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.4.4139&rep=rep1&type=pdf
    [22] Arias M, Cowen L, Laing KA, Rajaraman R, Taka O. Compact routing with name independence. In: Proc. of the ACM Symp. on Parallel Algorithms and Architecture (SPAA). San Diego: ACM Press, 2003. 184?192. http://citeseerx.ist.psu.edu/viewdoc/ download?doi=10.1.1.127.524&rep=rep1&type=pdf
    [23] Abraham I, Gavoille C, Malkhi D, Nisan N, Thorup M. Compact name-independent routing with minimum stretch. In: Proc. of the ACM Symp. on Parallel Algorithms and Architecture (SPAA). Barcelona: ACM Press, 2004. 20?24. http://www.cs.huji.ac.il/ ~ittaia/papers/AGMNT04.pdf
    [24] Gavoille C, Gengler M. Space-Efficiency for routing schemes of stretch Factor three. Journal of Parallel and Distributed Computing, 2001,61(5):679?687. [doi: 10.1006/jpdc.2000.1705]
    [25] Faloutsos M, Faloutsos P, Faloutsos C. On power-law relationships of the Internet topology. ACM SIGCOMM Computer Communications Review, 1999,29(4):251?262. [doi: 10.1145/316194.316229]
    [26] Dorogovtsev SN. Clustering of correlated networks. Physical Review E, 2004,69(027104).
    [27] Zhou S, Mondragon RJ. Accurately modeling the Internet topology. Physical Review E, 2004,70(066108).
    [28] Zhou S, Zhang GQ, Zhang GQ. Chinese Internet AS-level topology. IET Communications, 2007,1(2):209?214. [doi: 10.1049/ iet-com:20060518]
    [29] Zhang GQ, Zhang GQ, Yang QF, Cheng SQ, Zhou T. Evolution of the Internet and its cores. New Journal of Physics, 2008, 10(123027).
    [30] Krioukov D, Fall K, Yang X. Compact routing on Internet-like graphs. In: Proc. of the IEEE INFOCOM 2004. Hong Kong: IEEE Press, 2004. 209?219. http://www.ieee-infocom.org/2004/Papers/05_4.PDF
    [31] Brady A, Cowen L. Compact routing on power-law graphs with additive stretch. In: Proc. of the 8th Workshop on Algorithm Engineering and Experiments. SIAM, 2006. 119?128. http://www.siam.org/meetings/alenex06/
    [32] Tang MD, Zhang GQ, Yang J, Zhang GQ. A compact routing scheme for scale-free networks, Journal of Software, 2010,21(7): 1732?1743 (in Chinese with English abstract). http://www.jos.org.cn/1000-9825/3582.htm [doi: 10.3724/SP.J.1001.2010.03582]
    [33] Enachescu M, Wang M, Goel A. Reducing maximum stretch in compact routing. In: Proc. of the IEEE INFOCOM. Phoenix: IEEE Press, 2008. 977?985. http://www-cs-students.stanford.edu/~mihaela/pdfs/cr_infocom.pdf
    [34] Carmi S, Cohen R, Dolev D. Searching complex networks efficiently with minimal information. Europhysics Letters, 2006,74(6): 1102?1108. [doi: 10.1209/epl/i2006-10049-1]
    [35] Abraham I, Malkhi D. Name independent routing for growth bounded networks. In: Proc. of the 17th Annual ACM Symp. on Parallelism in Algorithms and Architectures. 2005. 49?55. http://www.cs.huji.ac.il/~ittaia/papers/AM-SPAA05.pdf
    [36] Lu H. Improved compact routing tables for planar networks via orderly spanning trees. In: Proc. of the 8th Int’l Conf. on Computing and Combinatorics. LNCS 2387, Berlin: Springer-Verlag, 2002. 57?66. http://citeseerx.ist.psu.edu/viewdoc/download? doi=10.1.1.7.1903&rep=rep1&type=pdf
    [37] Flury R, Pemmaraju SV, Wattenhofer R. Greedy routing with bounded stretch. In: Proc. of the IEEE INFOCOM. Rio de Janerio: IEEE Press, 2009. 1737?1745. http://www.disco.ethz.ch/publications/infocom09routing.pdf
    [38] Tang MD, Yang J, Zhang GQ. Compact routing on random power law graphs. In: Proc. of the IEEE Int’l Conf. on Dependable, Autonomic, and Secure Computing. Chengdu: IEEE Press, 2009. 575?578. http://doi.ieeecomputersociety.org/10.1109/ DASC.2009.133
    [39] Chen W, Sommer C, Teng SH, Wang Y. Compact routing in power-law graphs. In: Proc. of the DISC. Elche: Springer-Verlag, 2009. 379?391. http://research.microsoft.com/en-us/people/yajunw/disc2009sp.pdf
    [40] Krioukov D, Claffy KC, Fall K, Brady A. On compact routing for the Internet. ACM SIGCOMM Computer Communication Review, 2007,37(7):43?52. [doi: 10.1145/1198255.1198262]
    [41] Karp B, Kung HT. Gpsr: Greedy perimeter stateless routing for wireless networks. In: Proc. of the 6th Annual MOBICOM. Boston: ACM Press, 2000. 243?254. http://www.eecs.harvard.edu/~htk/publication/2000-mobi-karp-kung.pdf
    [42] Finn G. Routing and addressing problems in large metropolitan-scale Internet-works. Technical Report, ISI/RR-87-180, ISI, University of Southern California, 1987.
    [43] Francis P. Comparison of geographical and provider-rooted Internet addressing. Computer Networks and ISDN Systems, 1994, 27(3):437?448. [doi: 10.1016/0169-7552(94)90118-X]
    [44] Hain T. An IPv6 provider-independent global unicast address format. Internet Draft, draft-hain-ipv6-pi-addr-10, 2006.
    [45] Oliveira R, Lad M, Zhang B, Zhang L. Geographically informed inter-Domain routing. In: Proc. of the ICNP. Beijing: IEEE Press, 2007. 103?112. http://www.cs.ucla.edu/~lixia/papers/07SIGPoster_giro.pdf
    [46] Cao Q, Abdelzaher T. A scalable logical coordinates framework for routing in wireless sensor networks. ACM Trans. on Sensor Networks, 2006,2(4):557?593. [doi: 10.1145/1218556.1218561]
    [47] Fonseca R, Ratnasamy S, Zhao J, Ee CT, Culler D, Shenker S, Stoica I. Beacon vector routing: Scalable point to point routing in wireless sensornets. In: Proc. of the 2nd USENIX/ACM Symp. on Networked Systems Design and Implementation (NSDI). Boston: ACM Press, 2005. 329?342. http://berkeley.intel-research.net/sylvia/bvr.pdf
    [48] Papadimitriou C, Ratajczak D. On a conjecture related to geometric routing. Theoretical Computer Science, 2005,344(1):3?14. [doi: 10.1016/j.tcs.2005.06.022]
    [49] Kleinberg R. Geographic routing using hyperbolic space. In: Proc. of the IEEE INFOCOM. Anchorage: IEEE Press, 2007. 1902?1909. http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.93.2848&rep=rep1&type=pdf
    [50] Westphal C, Pei G. Scalable routing via greedy embedding. In: Proc. of the IEEE INFOCOM. Rio de Janerio: IEEE Press, 2009. 2826?2830. http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.160.6328&rep=rep1&type=pdf
    [51] Zhang GQ, Zhang GQ. Research on Internet correlation. Journal of Software, 2006,17(3):490?497 (in Chinese with English abstract). http://www.jos.org.cn/1000-9825/17/490.htm. [doi: 10.1360/jos170490]
    [52] Zhang GQ, Zhang GQ. Exploring the local connectivity preference of the Internet AS-level topology. In: Proc. of the IEEE Int’l Conf. on Communications (ICC). Glasgow: IEEE Press, 2007. 6439?6445. http://sourcedb.ict.cas.cn/cn/ictthesis/200907/ P020090722624457401017.pdf
    [53] Krioukov D, Papadopoulos F, Boguna M, Vahdat A. Greedy forwarding in scale-free networks embedded in hyperbolic metric spaces. ACM SIGMETRICS Performance Evaluation Review, 2009,37(2):15?17. [doi: 10.1145/1639562.1639568]
    [54] Tang MD, Zhang GQ, Yang J. Graph embedding based scalable routing in large networks. Journal of Computer Research and Development, 2010,47(7):1225?1233 (in Chinese with English abstract).
    [55] Subramanian L, Caesar M, Ee CT, Handley M, Mao M, Shenker S, Stoica I. HLP: A next generation inter-domain routing protocol. SIGCOMM Computer Communication Review, 2005,35(4):13?24. [doi: 10.1145/1090191.1080095]
    [56] Verkaik P, Broido A, Claffy KC, Gao R, Hyun Y, van der PR. Beyond CIDR aggregation. Technical Report, TR-2004-1, CAIDA, 2004.
    [57] Castineyra I, Chiappa N, Steenstrup M. The nimrod routing architecture. RFC 1992, IETF, 1996.
    [58] Zhang X, Francis P, Wang J, Yoshida K. Scaling IP routing with the core router-integrated overlay. In: Proc. of the IEEE Int’l Conf. on Network Protocols (ICNP). Santa Barbara: IEEE Press, 2006. 147?156. http://citeseerx.ist.psu.edu/viewdoc/download?doi= 10.1.1.88.9844&rep=rep1&type=pdf
    [59] Kastenholz F. ISLAY: A new routing and addressing architecture. Internet Draft, irtf-routing-islay-00.txt, 2002.
    [60] Farinacci D, Fuller V, Oran D, Meyer D. Locator/ID separation protocol (LISP). Internet Draft, draft-farinacci-lisp-05.txt, 2007.
    [61] Whittle R. Internet vastly improved plumbing architecture (Ivip). Internet Draft, draft-whittle-ivip-arch-01.txt, 2008.
    [62] Adan JJ. Tunneled Inter-Domain Routing (TIDR). Internet Draft, draft-adan-idr-tidr-01.txt, 2006.
    [63] Herrin W. Tunneling route reduction protocol (TRRP). 2008. http://bill.herrin.us/network/trrp.html
    [64] Jen D, Meisel M, Massey D, Wang L, Zhang B, Zhang L. APT: A practical transit mapping service. Internet Draft, Draft-jen-apt- 01.txt, 2007.
    [65] Templin F. The IPvLX architecture. Internet Draft, draft-templin-ipvlx-08.txt, 2007.
    [66] O’Dell M. GSE—An alternate addressing architecture for IPv6. Internet Draft, draft-ietf-ipngwg-gseaddr-00, 1997.
    [67] Vogt C. Six/One: A solution for routing and addressing in IPv6. Internet Draft, draft-vogt-rrg-six-one-02, 2007.
    [68] Vogt C. Six/One router: A scalable and backwards-compatible solution for provider-Independent addressing. In: Proc. of the ACM SIGCOMM MobiArch Workshop. Seattle: ACM Press, 2008. 13?18. http://citeseerx.ist.psu.edu/viewdoc/download?doi= 10.1.1.151.729&rep=rep1&type=pdf
    [69] Moskowitz R, Nikander P. Host identity protocol (HIP) architecture. RFC 4423, 2006.
    [70] Nordmark E, Bagnulo M. Shim6: Level 3 multihoming shim protocol for IPv6. Internet Draft, draft-ietf-shim6-proto-09, 2007.
    [71] Lear E. NERD: A not-so-novel EID to RLOC database. Internet Draft, draft-lear-lisp-nerd-04, 2008.
    [72] Mathy L, Lancaster U. LISP-DHT: Towards a DHT to map identifiers onto locators. In: Proc. of the Re-Architecting the Internet Conf (ReArch 2008). Madrid: ACM Press, 2008. 7?12. http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.139.735&rep= rep1&type=pdf
    [73] Luo H, Qin Y, Zhang H. A DHT-based identifier-to-locator mapping approach for a scalable Internet. IEEE Trans. on Parallel and Distributed Systems, 2009,20(10):1790?1802. [doi: 10.1109/TPDS.2009.30]
    [74] Brim S, Chiappa N, Farinacci D, Fuller V, Lewis D, Meyer D. LISP-CONS: A content distribution overlay network service for LISP. Internet Draft, draft-meyer-lisp-cons-04, 2008.
    [75] Farinacci D, Fuller V, Meyer D. LISP alternative topology (LISP-ALT). Internet Draft, draft-fuller-lisp-alt-02, 2008.
    [76] Yang X, Clark D, Berger AW. NIRA: A new inter-domain routing architecture. IEEE/ACM Trans. on Networking, 2007,15(4): 775?788. [doi: 10.1109/TNET.2007.893888]
    [77] Godfrey PB, Ganichev I, Shenker S, Stoica I. Pathlet routing. In: Proc. of the ACM SIGCOMM. Barcelona: ACM Press, 2009. 111?122. http://conferences.sigcomm.org/hotnets/2008/papers/17.pdf
    附中文参考文献: [3] 吴建平,吴茜,徐恪.下一代互联网体系结构基础研究及探索.计算机学报,2008,31(9):1537?1548.
    [6] 涂睿,苏金树,彭伟.位置与标识分离的命名和寻址体系结构研究综述.计算机研究与发展,2009,46(11):1777?1786.
    [7] 侯婕,刘亚萍,龚正虎.标识路由关键技术.软件学报,2010,21(6):1326?1340. http://www.jos.org.cn/1000-9825/3797.htm [doi: 10.3724/SP.J.1001.2010.03797]
    [13] 王娜,马海龙,程东年,汪斌强.Hidra:一个分级域间路由架构.计算机学报,2009,32(3):377?390.
    [32] 唐明董,张国清,杨景,张国强.针对无标度网络的紧凑路由方法.软件学报,2010,21(7):1732?1743. http://www.jos.org.cn/1000- 9825/3582.htm [doi: 10.3724/SP.J.1001.2010.03582]
    [51] 张国强,张国清.Internet网络的关联性研究.软件学报,2006,17(3):490?497. http://www.jos.org.cn/1000-9825/17/490.htm [doi: 10.1360/jos170490]
    [54] 唐明董,张国清,杨景.大规模网络上基于图嵌入的可扩展路由方法研究.计算机研究与发展,2010,47(7):1225?1233.
    引证文献
    引证文献 [0]
    [1]唐明董,刘建勋,张国清.紧凑路由研究[J].计算机科学与探索,2011,5(3):193-207.
    网友评论
    网友评论
    分享到微博
    发 布
引用本文

唐明董,张国清,杨景,张国强.互联网可扩展路由.软件学报,2010,21(10):2524-2541

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

京公网安备 11040202500063号