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 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 Fast-rtd, such as more than 45% memory reduction, 3% to 15% pruning rate increase, and up to 25% speed improvement.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Chen, A., Chan, E., Luo, X., Fok, W., Chang, R.: An efficient approach to multi-level route analytics. In: Proc. IFIP/IEEE IM (2013)
Schwartz, Y., Shavitt, Y., Weinsberg, U.: On the diversity, stability and symmetry of end-to-end Internet routes. In: Proc. IEEE GI Symposium (2010)
Logg, C., Cottrell, L., Navratil, J.: Experiences in traceroute and available bandwidth change analysis. In: Proc. ACM SIGCOMM Workshop on Network Troubleshooting (2004)
Chan, E.W.W., Luo, X., Fok, W.W.T., Li, W., Chang, R.K.C.: Non-cooperative diagnosis of submarine cable faults. In: Spring, N., Riley, G.F. (eds.) PAM 2011. LNCS, vol. 6579, pp. 224–234. Springer, Heidelberg (2011)
Fok, W., Luo, X., Mok, R., Li, W., Liu, Y., Chan, E., Chang, R.: Monoscope: Automating network faults diagnosis based on active measurements. In: Proc, IFIP/IEEE IM (2013)
Liu, Y., Luo, X., Chang, R., Su, J.: Characterizing inter-domain rerouting by betweenness centrality after disruptive events. IEEE JSAC 31(6) (2013)
Pucha, H., Zhang, Y., Mao, Z., Hu, Y.: Understanding network delay changes caused by routing events. In: Proc. ACM SIGMETRICS (2007)
Pathak, A., Pucha, H., Zhang, Y., Hu, Y.C., Mao, Z.M.: A measurement study of Internet delay asymmetry. In: Claypool, M., Uhlig, S. (eds.) PAM 2008. LNCS, vol. 4979, pp. 182–191. Springer, Heidelberg (2008)
He, Y., Faloutsos, M., Krishnamurthy, S.: Quantifying routing asymmetry in the Internet at the AS level. In: Proc. IEEE GLOBECOM (2004)
Han, J., Watson, D., Jahanian, F.: An experimental study of Internet path diversity. IEEE Trans. Dependable and Secure Computing (2006)
Beverly, R., Berger, A., Xie, G.: Primitives for active Internet topology mapping: Toward high-frequency characterization. In: Proc, ACM/USENIX IMC (2010)
Hyun, Y.: Archipelago measurement infrastructure. http://www.caida.org/projects/ark/
Chen, Y., Wan, A., Liu, W.: A fast parallel algorithm for finding the longest common sequence of multiple biosequences. BMC Bioinformatics 7(S4) (2006)
Wang, Q., Korkin, D., Shang. Y.: A fast multiple longest common subsequence (MLCS) algorithm. IEEE TKDE 23(3) (2011)
Madhyastha, H., Isdal, T., Piatek, M., Dixon, C., Anderson, T.: iPlane: An information plane for distributed services. In: Proc, USENIX OSDI (2006)
Augustin, B., Cuvellier, X., Orgogozo, B., Viger, F., Friedman, T., Latapy, M., Magnien, C., Teixeira, R.: Avoiding traceroute anomalies with Paris traceroute. In: Proc. ACM/USENIX IMC (2006)
Team Cymru. IP to ASN service. http://www.team-cymru.org/Services/ip-to-asn.html
Schwartz, Y., Shavitt, Y., Weinsberg, U.: A measurement study of the origins of end-to-end delay variations. In: Krishnamurthy, A., Plattner, B. (eds.) PAM 2010. LNCS, vol. 6032, pp. 21–30. Springer, Heidelberg (2010)
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2014 Institute for Computer Sciences, Social Informatics and Telecommunications Engineering
About this paper
Cite this paper
Tu, P., Luo, X., Wu, W., Tang, Y. (2014). Speeding Up Multi-level Route Analysis Through Improved Multi-LCS Algorithm. In: Leung, V., Chen, M., Wan, J., Zhang, Y. (eds) Testbeds and Research Infrastructure: Development of Networks and Communities. TridentCom 2014. Lecture Notes of the Institute for Computer Sciences, Social Informatics and Telecommunications Engineering, vol 137. Springer, Cham. https://doi.org/10.1007/978-3-319-13326-3_31
Download citation
DOI: https://doi.org/10.1007/978-3-319-13326-3_31
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-319-13325-6
Online ISBN: 978-3-319-13326-3
eBook Packages: Computer ScienceComputer Science (R0)