Back to search

University of Nevada - Reno

A Graph Theoretic Perspective on Internet Topology Mapping

Abstract

dc:description.abstract

Understanding the topological characteristics of the Internet is an important research issue as the Internet grows with no central authority. Internet topology mapping studies help better understand the structure and dynamics of the Internet backbone. Knowing the underlying topology, researchers can better develop new protocols and services or fine-tune existing ones. Subnet-level Internet topology measurement studies involve three stages: topology collection, topology construction, and topology analysis. Each of these stages contains challenging tasks, especially when large-scale backbone topologies of millions of nodes are studied. In this dissertation, I first discuss issues in subnet-level Internet topology mapping and review state-of-the-art approaches to handle them. I propose a novel graph data indexing approach to to efficiently process large scale topology data. I then conduct an experimental study to understand how the responsiveness of routers has changed over the last decade and how it differs based on the probing mechanism. I then propose an efficient unresponsive resolution approach by incorporating our structural graph indexing technique. Finally, I introduce Cheleby, an integrated Internet topology mapping system. Cheleby first dynamically probes observed subnetworks using a team of PlanetLab nodes around the world to obtain comprehensive backbone topologies. Then, it utilizes efficient algorithms to resolve subnets, IP aliases, and unresponsive routers in the collected data sets to construct comprehensive subnet-level topologies. Sample topologies are provided at http://cheleby.cse.unr.edu.

Degree

thesis:*
Level thesis:degree_level
Doctorate Degree
Department thesis:degree_department
Computer Science and Engineering
Year dc:date.issued
2012

Author and committee

dc:creator, dc:contributor.*
Author dc:creator
  • Kardes, Hakan
Advisor dc:contributor.advisor
  • Gunes, Mehmet H.
Committee members dc:contributor.committeemember
  • Folmer, Eelke
  • Yuksel, Murat
  • Dascalu, Sergiu
  • Evrensel, Cahit A

Rights

dc:rights
Statement dc:rights
  • In Copyright(All Rights Reserved)
  • Author(s)

Identifiers

dc:identifier.*
Handle dc:identifier.uri
http://hdl.handle.net/11714/3756

Chain of custody

source
Harvested from
University of Nevada - Reno
Base URL
scholarwolf.unr.edu/server/oai/request
Last updated
2026-11-19
Source record
OAI-PMH GetRecord
related terms
citation

Kardes, Hakan. A Graph Theoretic Perspective on Internet Topology Mapping. Doctorate Degree thesis, 2012. http://hdl.handle.net/11714/3756