TY - GEN
T1 - Speeding up multi-level route analysis through improved multi-lcs algorithm
AU - Tu, Pei
AU - Wu, Weigang
AU - Luo, Xiapu
AU - Luo, Xiapu
AU - Tang, Yajuan
PY - 2014/1/1
Y1 - 2014/1/1
N2 - 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 Fast-rtd that contrastsmultiple routes simultaneously andexploits 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 Fast-rtd, suchasmore than45%memoryreduction, 3% to 15% pruning rate increase, and up to 25% speed improvement.
AB - 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 Fast-rtd that contrastsmultiple routes simultaneously andexploits 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 Fast-rtd, suchasmore than45%memoryreduction, 3% to 15% pruning rate increase, and up to 25% speed improvement.
KW - BGP
KW - Multi-level route analysis
KW - Multiple LCS
UR - https://www.scopus.com/pages/publications/84916206399
U2 - 10.1007/978-3-319-13326-3_31
DO - 10.1007/978-3-319-13326-3_31
M3 - Conference article published in proceeding or book
T3 - Lecture Notes of the Institute for Computer Sciences, Social-Informatics and Telecommunications Engineering, LNICST
SP - 327
EP - 337
BT - Testbeds and Research Infrastructure
PB - Springer Verlag
T2 - 9th International ICST Conference on Testbeds and Research Infrastructures for the Development of Networks and Communities, TridentCom 2014
Y2 - 5 May 2014 through 7 May 2014
ER -