Network Topology Inference with End-to-End Unicast Measurements

  • Author / Creator
    Malekzadeh, Amir
  • Network tomography is the problem of discovering the delay and loss rate of the internal links of a network, assuming the internal nodes are not cooperating. The first step to solving this problem is finding network topology. Well-known tools such as traceroute solve this problem, however they depend on cooperation by the internal nodes. This thesis studies the problem of topology identification without relying on the cooperation of the internal nodes of the network. Our work is based on a probing method called the sandwich method. We suggest a novel probing scheme called TSP which is based on end-to-end unicast delay measurements and combines the ideas of sandwich and traceroute. We also develop two topology inference algorithm to find the topology of the network. One of the algorithms uses sandwich data and the other uses TSP. Our simulation-based experiments show that TSP improves the topology identification process substantially compared to previous methods.

  • Subjects / Keywords
  • Graduation date
  • Type of Item
  • Degree
    Master of Science
  • DOI
  • License
    This thesis is made available by the University of Alberta Libraries with permission of the copyright owner solely for non-commercial purposes. This thesis, or any portion thereof, may not otherwise be copied or reproduced without the written consent of the copyright owner, except to the extent permitted by Canadian copyright law.
  • Language
  • Institution
    University of Alberta
  • Degree level
  • Department
    • Department of Computing Science
  • Supervisor / co-supervisor and their department(s)
    • MacGregor, Mike H (Computing Science)
  • Examining committee members and their departments
    • Tellambura, Chintha (Electrical and Computer Engineering)
    • Harms, Janelle (Computing Science)