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.

Experimental Study on Diversity and Novelty of Interdomain Paths

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).
  • Received Date: 2012-01-01
  • Rev Recd Date: 2012-03-01
  • Publish Date: 2013-01-05
  • 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.
  • loading
  • 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.
  • 加载中


    通讯作者: 陈斌, bchen63@163.com
    • 1. 

      沈阳化工大学材料科学与工程学院 沈阳 110142

    1. 本站搜索
    2. 百度学术搜索
    3. 万方数据库搜索
    4. CNKI搜索

    Article Metrics

    Article views (416) PDF downloads(1679) Cited by()
    Proportional views


    DownLoad:  Full-Size Img  PowerPoint