Volume 22 Issue 1
Turn off MathJax
Article Contents
Abstract
References
QIN Donghong, YANG Jiahai, WANG Hui. Experimental Study on Diversity and Novelty of Interdomain Paths[J]. Chinese Journal of Electronics, 2013, 22(1): 160-166.
Citation: QIN Donghong, YANG Jiahai, WANG Hui. Experimental Study on Diversity and Novelty of Interdomain Paths[J]. Chinese Journal of Electronics, 2013, 22(1): 160-166.
shu

Experimental Study on Diversity and Novelty of Interdomain Paths

  • 1.

    Department of Computer Science and Technology, Tsinghua University, Beijing 100084, China;

  • 2.

    Network Research Center, Tsinghua University, Beijing 100084, China;

  • 3.

    Tsinghua National Laboratory for Information Science and Technology, Beijing 100084, China

Funds: This work is supported by the National Basic Research Program of China (973 Program) (No.2009CB320505), the National Science and Technology Supporting Plan of China (No.2008BAH37B05), the National Natural Science Foundation of China (No.61170211), the Specialized Research Fund for the Doctoral Program of Higher Education (No.20110002110056), and the National High Technology Research and Development Program (863 Program) (No.2008AA01A303, No.2009AA01Z251).
More Information
  • Received Date: December 31, 2011
  • Revised Date: February 29, 2012
  • Published Date: January 04, 2013
    Graphical Abstract
    • Abstract
  • Exploiting Internet path diversity to enhance communication reliability and performance is an important research field. Although the Internet has enormous physical diversity in the underlaying infrastructure, inter-domain routing protocol and routing policies highly limit this path diversity in the Internet. In order to investigate the effects of routing policies on inter-domain paths, we develop a measurement study framework to characterize and classify inter-domain paths. In this framework, we define the concepts of the transit strategy and the valley and valley-free paths, and give a formal model of strategylabeled inter-domain paths. Then we develop three associated algorithms: Topology extraction (TE), Multi-path computation algorithm (MCA) and Classification of path pattern (CPP), which are used to compute and classify inter-domain paths. Experimental results show two useful and important observations that valley paths have averagely more than 73% in all inter-domain paths, and Class 1 paths account for 64.6% of all valley paths. The observations may guide the design of inter-domain routing protocol, especially the design of multi-path routing, to achieve higher performance and reliability.
    • FullText(HTML)
    • References (23)
  • Y. Rekhter, T. Li, “ A Border Gateway Protocol 4 (BGP-4)”,RFC4271, 2006.
    M. Yannuzzi and X. Masip-Bruin, “Open issues in interdomainrouting: a survey”, IEEE Network, Vol.19, No.6, pp.49-56,2009.
    N. Feamster, H. Balakrishnan, J. Rexford, “Some foundationalproblems in interdomain routing”, Proc. of ACM SIGCOMMWorkshop on Hot Topics in Networks, San Diego, California,USA, pp.41-46, 2004.
    C. Labovitz, S. Iekel-Johnson, et al. “Internet inter-domaintraffic”, SIGCOMM Computer Communication Review, Vol.40,No.4, pp.75-86, 2010.
    J. He, J. Rexford, “Toward internet-wide multipath routing”,IEEE Network, Vol.22, No.2, pp.16-21, 2008.
    R. Teixeira, “Characterizing and measuring path diversity ofinternet topologies”, Proc. of ACM SIGMETRICS, New York,NY, USA, 2003.
    S. Savage, et al., “The end-to-end effects of internet path selection”,Proc. of ACM SIGCOMM, Cambridge, Massachusetts,USA, 1999.
    D. Qin, J. Yang, et al., “AMIR: Another multipath interdomainrouting”, Proc. of IEEE International Conference on AdvancedInformation, Fukuoka, Japan, pp.113-120, 2012.
    D. Qin, J. Yang, Z. Liu, et al., “Multipath interdomain routingvia deviation from primary path”, Proc. of The 26th ofthe International Conference on Information Networking, Bali,Indonesia, pp.222-227, 2012.
    L. Gao, “On inferring autonomous system relationships in theInternet”, IEEE/ACM Trans. on Networking, Vol.9, No.6,pp.733-745, 2001.
    B. Quoitin, S. Uhlig, “Modeling the routing of an autonomoussystem with C-BGP”, IEEE Network, Vol.19, No.6, pp.12-19,2005.
    M. Xiong, C. Zhang, X. Qiu, T. Ma and H. Wang, “Towardsautonomous system topology aware relay service scheme”, Proc.of The 6th International Conference on Wireless CommunicationsNetworking and Mobile Computing (WiCOM), Chengdu,China, pp.1-4, 2010.
    L. Subramanian, S. Agarwal, J. Rexford and R. Katz, “Characterizingthe internet hierarchy from multiple vantage points”,Proc. of IEEE INFOCOM, Gosier, Guadeloupe, pp.618-627,2002.
    H. Tangmunarunkit et al., “The impact of routing policy on internetpaths”, Proc. of IEEE Infocomm, Anchorage, AK, USA,pp.736-742, 2001.
    G. Huston, “Interconnection, peering and settlements”, InternetProtocol Journal, Vol.2, No.2, pp.2-23, 1999.
    P. Baake, T. Wichmann, “On the economics of internet peering”,Netnomics, Vol.1, No.1, pp.89-105, 1998.
    The CAIDA AS Relationships Dataset, http://www.caida.org/data/active/asrelationships/, 2006-2010.
    J. Han, F. Jahanian, “Impact of path diversity on multi-homedand overlay networks”, Proc. of International Conference onDependable Systems and Networks, Florence, Italy, pp.29-38,2008.
    Z. Liu, Y. Sun, Y. Liu, “Routing differentiated services in theInternet“, Chinese Journal of Electronics, Vol.11, No.1, pp.83-88, 2002.
    B. Zhang, E. Liu, D. D. Massey, and L. Zhang, “Collecting thenternet AS-level topology”, ACM SIGCOMM Computer CommunicationReview, Vol.35, No.1, pp.53-61, 2009.
    C. Shi, J. Hu, M. Chang, “An integrated metric based hierarchicalrouting algorithm in broadband communication system”,Chinese Journal of Electronics, Vol.10, No.4, pp.520-523, 2001.
    A. R. Curtis, R. M. McConnell, D. Massey, “Efficient algorithmsfor optimizing policy-constrained routing”, Proc. of FifteenthIEEE International Workshop on Quality of Service, Evanston,Illinois, USA, pp.113-116, 2007.
    S. Nomoto, K. Fukuda, M. Uehara and H. Mori, “A visualizationof internet as topology with valley-free rules”, Proc. ofInternational Conference on Complex, Intelligent and SoftwareIntensive Systems, Fukuoka, Japan, pp.279-286, 2009.
    • Related Articles

Catalog

    Get Citation
    PDF
    XML

    Article Metrics

    Article views (790) PDF downloads (1683) Cited by()
    Related

    Links

    IEEE CJE Homepage CNKI Chinese Institute of Electronics Journal of Semiconductors
    E-mail Alert RSS

    Chinese Journal of Electronics

    (Bimonthly)

    ISSN    1022-4653CN  10-1284/TN

    eISSN  2075-5597CODEN CHJEEW

    CJE QR CODE

    CIE QR CODE

    Copyright © Editorial Office of Chinese Journal of Electronics | 京ICP备12041980号-1 | Supported by: Beijing Renhe Information Technology Co., Ltd.  Baidu Analytics

    /

    DownLoad:  Full-Size Img  PowerPoint
    Return
    Return