Testbeds and Research Infrastructure: Development of Networks and Communities. 9th International ICST Conference, TridentCom 2014, Guangzhou, China, May 5-7, 2014, Revised Selected Papers

Research Article

Speeding Up Multi-level Route Analysis Through Improved Multi-LCS Algorithm

Download
490 downloads
  • @INPROCEEDINGS{10.1007/978-3-319-13326-3_31,
        author={Pei Tu and Xiapu Luo and Weigang Wu and Yajuan Tang},
        title={Speeding Up Multi-level Route Analysis Through Improved Multi-LCS Algorithm},
        proceedings={Testbeds and Research Infrastructure: Development of Networks and Communities. 9th International ICST Conference, TridentCom 2014, Guangzhou, China, May 5-7, 2014, Revised Selected Papers},
        proceedings_a={TRIDENTCOM},
        year={2014},
        month={11},
        keywords={Multi-level route analysis Multiple LCS BGP},
        doi={10.1007/978-3-319-13326-3_31}
    }
    
  • Pei Tu
    Xiapu Luo
    Weigang Wu
    Yajuan Tang
    Year: 2014
    Speeding Up Multi-level Route Analysis Through Improved Multi-LCS Algorithm
    TRIDENTCOM
    Springer
    DOI: 10.1007/978-3-319-13326-3_31
Pei Tu1,*, Xiapu Luo,*, Weigang Wu1,*, Yajuan Tang2,*
  • 1: Sun Yat-Sen University
  • 2: Shantou University
*Contact email: tuwantpkyj@hotmail.com, csxluo@comp.polyu.edu.hk, wuweig@mail.sysu.edu.cn, yjtang@stu.edu.cn

Abstract

Although the multi-level route analysis (e.g., AS, subnet, IP levels) is very useful to many applications (e.g. profiling route changes, designing efficient route-tracing algorithms, etc.), few research investigates how to conduct such analysis efficiently. Regarding routes as sequences, current approaches only handle two routes at a time and they just apply algorithms designed for general sequence comparison. In this paper, we propose and implement a new approach named that contrasts multiple routes simultaneously and exploits the unique features of Internet routes to decrease the computational complexity in terms of time and memory. Our extensive evaluations on real traceroute data demonstrate the efficiency of , such as more than 45% memory reduction, 3% to 15% pruning rate increase, and up to 25% speed improvement.