微信服务号

微信订阅号

2025-4-5- 13
Home > Archive>Volume 22, Issue 1, 2011 >84-100. DOI:10.3724/SP.J.1001.2011.03935
PDF HTML XML Export Cite reminder
Scalability of Internet Inter-Domain Routing
Author:
Affiliation:

  • Article
    • | |
  • Metrics
    • |
  • Reference [44]
    • |
  • Related [20]
    • | | |
  • Comments
    Abstract:

    The problem of the scalability of inter-domain routing is of the main issues in the design of Next Generation Internet (NGI). This paper addresses the intrinsic essences of the problems created by the scalability of Internet routing by introducing the entropy routing information concept. Based on the theoretical model of entropy in routing information, potential solutions to the routing scalability problems are discussed, which focus on three different aspects with their respective benefits and limitations and their architectural evaluations on typical proposals. In the end, a conclusion on the challenges of the Internet routing scalability problem is drawn, and the direction of further research on this problem is explored.

    Reference
    [1] Doria A, Davies E, Kastenholz F. A set of possible requirements for a future routing architecture. RFC 5772, 2010.
    [2] Davies E, Doria A. Analysis of inter-domain routing requirements and history. RFC 5773, 2010.
    [3] Meyer D, Zhang L, Fall K. Report from the IAB workshop on routing and addressing. RFC 4984, 2007.
    [4] Krioukov D, Fall K, Yang X. Compact routing on Internet-like graphs. In: Proc. of the IEEE INFOCOM 2004. Piscataway: IEEE, 2004. 209-219 .
    [5] Li T, ed. Design goals for scalable internet routing. Internet-Draft, 2007.
    [6] Zhang LM. Complex network and compact routing. ZTE Communications, 2009,15(6):5-8 (in Chinese with English abstract).
    [7] Cui Y. IETF highly concerns routing scalability problems. China Educational Network, 2007 (in Chinese with English abstract). http://www.cnki.com.cn/Article/CJFDTOTAL-JYWL200704022.htm
    [8] Zhan FB, Xu MW, Wu JP, Survey on host identity protocol (HIP). Journal of Chinese Computer Systems, 2007,28(2):224-228 (in Chinese with English abstract).
    [9] Yu SP. Study on the locator/identifier separation. Computer Technology and Development, 2007,19(7):95-97 (in Chinese with English abstract).
    [10] Xu XH, Guo DY, Gao XS, Cao W, Li HJ. Discussion on Internet scalability problems. Telecommunications Network Technology, 2009,4:6-11 (in Chinese with English abstract).
    [11] Li JR. Scalability of Internet. Science and Technology Information, 2009,21:65-66 (in Chinese with English abstract).
    [12] Shannon CE. A mathematical theory of communication. Bell System Technical Journal, 1948,27:379-423 , 623-656 .
    [13] Faloutsos M, Faloutsos P, Faloutsos C. On power-law relationships of the Internet topology. In: Proc. of the Conf. on Applications, Technologies, Architectures, and Protocols for Computer Communication. New York: ACM, 1999. 251-262 .
    [14] Massey D, Wang L, Zhang B, Zhang L. A scalable routing system design for future Internet. In: Proc. of the ACM SIGCOMM Workshop on IPv6. Kyoto: ACM, 2007. http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.120.218&rep=rep1&type=pdf
    [15] Subramanian L, Caesar M, Cheng TE, Handley M, Mao M, Shenker S, Stoica I. HLP: A next generation inter-domain routing protocol. Computer Communication Review, 2005,35(4):13-24 .
    [16] Farinacci D, Fuller V, Meyer D, Lewis D. Locator/ID separation protocol (LISP). Internet-Draft, 2009. http://tools.ietf.org/html/ draft-ietf-lisp-08.txt
    [17] Whittle R. Ivip (Internet vastly improved plumbing) architecture. Internet-Draft, 2010. http://tools.ietf.org/html/draft-whittle-iviparch- 04
    [18] Jen D, Meisel M, Massey D, Wang L, Zhang B, Zhang LX. APT: A practical transit mapping service. Internet-Draft, 2007. http://tools.ietf.org/html/draft-jen-apt-01
    [19] Adan JJ. Tunneled inter-domain routing (TIDR). Internet-Draft, 2006. http://tools.ietf.org/html/draft-adan-idr-tidr-00
    [20] Templin F, ed. The IPvLX architecture. Internet-Draft, 2007. http://tools.ietf.org/id/draft-templin-ipvlx-08.txt
    [21] Zhang B, Zhang L, Wang L. Evolution towards global routing scalability. Internet-Draft, 2009. http://tools.ietf.org/html/draftzhang- evolution-02
    [22] Zhang B, Wang L, Zhao X, Liu Y, Zhang L. FIB aggregation. Internet-Draft, 2009. http://tools.ietf.org/html/draft-zhangfibaggregation- 02
    [23] Ballani H, Francis P, Cao T, Wang J. Making routers last longer with ViAggre. In: Proc. of the 6th USENIX Symp. on Networked Systems Design and Implementation. Berkeley: USENIX Association, 2009. 453-466 .
    [24] Zhang XY, Francis P, Wang J, Yoshida K. Scaling IP routing with the core router-integrated overlay. In: Proc. of the 2006 IEEE Int’l Conf. on Network Protocols. Washington: IEEE Computer Society, 2006. 147-156 .
    [25] Kleinrock L, Kamoun F. Hierarchical routing for large networks: Performance evaluation and optimization. Computer Networks, 1997,1(3):155-174 .
    [26] Castineyra I, Chiappa N, Steenstrup M. The nimrod routing architecture. RFC 1992, 1996. http://tools.ietf.org/html/rfc1992
    [27] Kastenholz F. ISLAY: A new routing and addressing architecture. Internet-Draft, 2002. http://tools.ietf.org/all-ids/draft-irtfrouting- islay-00.txt
    [28] Krioukov D, Claffy K, Fall K, Brady A. On compact routing for the Internet. Computer Communication Review, 2007,37(3):41-52 .
    [29] Nordmark E, Bagnulo M. Shim6: Level 3 multihoming shim protocol for IPv6. RFC 5533, 2009. http://tools.ietf.org/html/rfc5533
    [30] Vogt C. Six/One router: A scalable and backwards compatible solution for provider-independent addressing. In: Proc. of the 3rd Int’l Workshop on Mobility in the Evolving Internet Architecture. Seattle: ACM, 2008. 13-18 .
    [31] 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]
    [32] Atkinson R. ILNP concept of operations. Internet-Draft, 2010. http://ilnp.cs.st-andrews.ac.uk/docs/id/draft-rja-ilnp-intro-03.txt
    [33] Menth M, Hartmann M, Klein D. Global locator, local locator, and identifier split (GLI-Split). Report No.470, University of Wurzburg Institute of Computer Science Research Report Series. Wurzburg: University of Wurzburg, 2010. http://www3. informatik.uni-wuerzburg.de/~menth/Publications/papers/Menth-GLI-Split.pdf
    [34] Moskowitz R, Nikander P. Host identity protocol (HIP) architecture. RFC 4423, http://tools.ietf.org/html/rfc4423
    [35] Frejborg P. Hierarchical IPv4 framework. Internet-Draft, http://tools.ietf.org/html/draft-frejborg-hipv4-08
    [36] Feldmann A, Cittadini L, Mühlbauer W, Bush R, Maennel O. HAIR: Hierarchical architecture for Internet routing. In: Proc. of the 2009 Workshop on Re-Architecting the Internet. New York: ACM, 2009. 43-48 .
    [37] Kuhn F, Wattenhofer R, Zhang Y, Zollinger A. Geometric ad-hoc routing: Of theory and practice. In: Proc. of the 22nd Annual Symp. on Principles of Distributed Computing. New York: ACM, 2003. 63-72 .
    [38] Serrano MA, Krioukov D, Boguna M. Self-Similarity of complex networks and hidden metric spaces. Physical Review Letters, 2008,100(7):078701-1. [doi: 10.1103/PhysRevLett.100.078701]
    [39] Boguna M, Krioukov D, Claffy K. Navigability of complex networks. Nature Physics, 2009,5:74-80 . [doi: 10.1038/nphys1130]
    [40] Shavitt Y, Tankel T. Hyperbolic embedding of Internet graph for distance estimation and overlay construction. IEEE/ACM Trans. on Networking, 2008,16(1):25-36 . [doi: 10.1109/TNET.2007.899021]
    [41] Kleinberg R. Geographic routing using hyperbolic space. In: Proc. of the 26th IEEE Int’l Conf. on Computer Communications (IEEE INFOCOM 2007). Piscataway: IEEE, 2007. 1902-1909 . [doi: 10.1109/INFCOM.2007.221]
    [42] Caesar M, Condie T, Kannan J, Lakshminarayanan K, Stoica I, Shenker S. ROFL: Routing on flat labels. In: Proc. of the SIGCOMM 2006. New York: ACM, 2006. 363-374 .
    [43] Koponen T, Chawla M, Chun B, Ermolinskiy A, Kim KH, Shenker S, Stoica I. A data-oriented (and beyond) network architecture. In: Proc. of the SIGCOMM 2007. New York: ACM, 2007. 181-192 .
    [44] Jacobson V, Smetters D, Thornton J, Plass M, Briggs N, Braynard R. Networking named content. In: Proc. of the CoNEXT 2009. New York: ACM, 2009. 1-12 .
    Cited by
    Comments
    Comments
    分享到微博
    Submit
Get Citation

张威,毕军,吴建平.互联网域间路由可扩展性.软件学报,2011,22(1):84-100

Copy
Share
Article Metrics
  • Abstract:8881
  • PDF: 11461
  • HTML: 0
  • Cited by: 0
History
  • Received:June 24,2010
  • Revised:August 27,2010
Links:Institute of Software, CASChina Computer FederationCASNSFC
You are the first2033169Visitors
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