Methods and Tools to Infer Aspects of the AS-level Internet: Gonca Gursun, PhD proposal

Starts:
10:00 am on Monday, October 29, 2012
Ends:
11:00 am on Monday, October 29, 2012
Location:
MCS 148
Abstract: Knowledge about the global behavior of AS-level Internet is vital for many networking problems such as traffic engineering, network management, security, and business intelligence. However, given its distributed architecture, the global behavior of AS-level Internet is hard to come by. For instance, there is no single vantage point to measure all Internet traffic. Individual ASes can only observe a small portion of the whole set of flows, i.e. their visibility is limited. In this thesis, we study the ability of individual ASes to extend their visibility of the AS-level Internet. We define two types of visibility: 1) the visibility of interdomain traffic volumes which corresponds to the knowledge about the amount of traffic exchanged between ASes, and 2) the visibility of interdomain routing state which corresponds to the knowledge about the set of routes that passes through an AS. In the first part of this thesis, we study the ability of ASes infer the volume of traffic that does not pass through their networks. We seek to understand which ASes are likely to perform such inference successfully and which flows they can readily recover. In the second part, we study the ability of ASes identify which paths flow through their network. We show that this problem is equivalent to inferring which source-destination pairs that are not communicating at a given time. Answering this question prompts us to look for ways to identify sets of source-destination paths that are routed similarly in a particular region of the Internet. To do that, we define a metric called Routing State Distance (RSD) to compute the distance between any given two prefixes. In the third part of the thesis, we study the properties of this new metric in detail and show how to use it as a tool for characterizing BGP paths. We show that such characterization uncovers some suprising patterns in the interdomain routing system. Committee: Mark Crovella (advisor - first reader) Evimaria Terzi (second reader) John Byers Azer Bestavros