微信服务号

微信订阅号

2025-4-24- 16
Home > Archive>Volume 21, Issue 10, 2010 >2524-2541
PDF HTML XML Export Cite reminder
Scalable Routing for the Internet
Author:
Affiliation:

  • Article
    • | |
  • Metrics
    • |
  • Reference [84]
    • |
  • Related [20]
    • |
  • Cited by
    • | |
  • Comments
    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.

    Reference
    [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.
    Cited by
    Comments
    Comments
    分享到微博
    Submit
Get Citation

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

Copy
Share
Article Metrics
  • Abstract:
  • PDF:
  • HTML:
  • Cited by:
History
  • Received:December 20,2009
  • Revised:June 28,2010
Links:Institute of Software, CASChina Computer FederationCASNSFC
You are the first2038126Visitors
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