Filling in the Blanks of Internet Topology

Discovering the Internet’s router-level topology is a compelling objective with applications in the areas of network management, operations, and security. Prior work on Internet topology discovery have mainly focused on the engineering problems associated with extensively probing the Internet using high network load probes, and then aggregating the vast quantities of data returned. Unfortunately, the size of the Internet, coupled with service providers frequent attempts to thwart structure discovery, often renders standard topology discovery tools ineffective due to missing measurement data.

In this talk, I will discuss how to discover Internet topology characteristics using incomplete network measurements. We will discuss two case studies. First, topological characteristics of the network will be inferred from passively observed traffic in the network. We show how inherently incomplete observations of network traffic allow for accurate clustering of end hosts and shared path estimation in the Internet. The second study presents a novel network tomography methodology that targets a non-exhaustive number of pair wise probes to resolve the logical network topology. Experiments performed on both real world and synthetic Internet topologies show significant improvements in both topology reconstruction accuracy and probing complexity over prior results.

Brian Eriksson is currently a postdoctoral research associate at Boston University in the Department of Computer Science. He received his Ph.D. in Electrical Engineering at the University of Wisconsin advised by Robert Nowak (Department of Electrical and Computer Engineering) and Paul Barford (Computer Science) in August 2010. He received his B.S. in Computer Engineering from the University of Wisconsin in 2004 with distinction, and his M.S. in Electrical Engineering from the University of Wisconsin in 2006. He is a recipient of the Claude and Dora Richardson Memorial Scholarship and the Frank Roger Bacon Graduate Fellowship.