Speeding up multi-level route analysis through improved multi-lcs algorithm

Pei Tu, Weigang Wu, Xiapu Luo, Xiapu Luo, Yajuan Tang

Research output: Chapter in book / Conference proceedingConference article published in proceeding or bookAcademic researchpeer-review

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 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.
Original languageEnglish
Title of host publicationTestbeds and Research Infrastructure
Subtitle of host publicationDevelopment of Networks and Communities - 9th International ICST Conference, TridentCom 2014, Revised Selected Papers
PublisherSpringer Verlag
Pages327-337
Number of pages11
ISBN (Electronic)9783319133256
DOIs
Publication statusPublished - 1 Jan 2014
Event9th International ICST Conference on Testbeds and Research Infrastructures for the Development of Networks and Communities, TridentCom 2014 - Guangzhou, China
Duration: 5 May 20147 May 2014

Publication series

NameLecture Notes of the Institute for Computer Sciences, Social-Informatics and Telecommunications Engineering, LNICST
Volume137
ISSN (Print)1867-8211

Conference

Conference9th International ICST Conference on Testbeds and Research Infrastructures for the Development of Networks and Communities, TridentCom 2014
Country/TerritoryChina
CityGuangzhou
Period5/05/147/05/14

Keywords

  • BGP
  • Multi-level route analysis
  • Multiple LCS

ASJC Scopus subject areas

  • Computer Networks and Communications

Cite this