Title

Analysis of large scale traceroute datasets in Internet routing overlays by parallel computation

Authors

Authors

M. Z. Ahmad;R. Guha

Comments

Authors: contact us about adding a copy of your work at STARS@ucf.edu

Abbreviated Journal Title

J. Supercomput.

Keywords

Internet topology; Internet exchange points; GPGPU; CUDA; Data analysis; Parallel computation; SEARCH; GPU; Computer Science, Hardware & Architecture; Computer Science, Theory &; Methods; Engineering, Electrical & Electronic

Abstract

The creation of a routing overlay network on the Internet requires the identification of shorter detour paths between end hosts in comparison to the default path available. These detour paths are typically the edges forming a Triangle Inequality Violation (TIV), an artifact of the Internet delay space where the sum of latencies across an intermediate hop is lesser than the direct latency between the pair of end hosts. These violations are caused mainly due to interdomain routing policies between Autonomous Systems (ASes) and AS peering through Internet eXchange Points (IXPs). Identifying detours for a global overlay network requires large amounts of computational capabilities due to the sheer number of possible paths linking source and destination ASes. In this work, we use parallel programming paradigms to exploit the massively parallel capabilities of analyzing the large network measurement datasets made available to the network research community by CAIDA. We study Internet routes traversing IXPs and measure potential TIVs created by these paths. Large scale analysis of the dataset is carried out by implementing an efficient parallel solution on the CPU and then the general purpose graphics processor unit (GPGPU) as well. Both multicore CPU and GPGPU implementations can be carried out with ease on desktop environments with readily available software. We find both parallel solutions yield high improvements in speedup (2-35x) in comparison to the serial methodologies thereby opening up the possibility of harnessing the power of parallel programming with readily available hardware. The large amount of data analyzed and studied helps draw various inferences for the networking research community in building future scalable Internet routing overlays with greater routing efficiencies.

Journal Title

Journal of Supercomputing

Volume

62

Issue/Number

3

Publication Date

1-1-2012

Document Type

Article

Language

English

First Page

1425

Last Page

1450

WOS Identifier

WOS:000310428700017

ISSN

0920-8542

Share

COinS