Research Article
Speeding Up Multi-level Route Analysis Through Improved Multi-LCS Algorithm
@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
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.
