Masters Final Oral: Karthiapil Nikhil

Monday, June 12, 2017 - 9:00am
223 Atanasoff Hall
Event Type: 

Title: Validation of State-of-the-Art Autonomous System Relationship Inference Algorithm
Date/Time: June 12th, 2017 @ 9:00 AM
Place: 223 Atanasoff Hall 
Major Professor: Lu Ruan
Committee Members: Pavankumar Aduri and Wallapak Tavanapong


The study of the relationship between various Autonomous Systems (ASes) is important in understanding the structure of the Internet and its evolution. An AS is a collection of routers managed by a single entity and adheres to a specific routing policy. The routing policy between a pair of ASes is determined by their AS relationship, which can be classified as a peer-peer (pp) relationship or a provider-customer (pc) relationship. There are many algorithms proposed to infer the relationship between a given pair of ASes. The Center for Applied Internet Data Analysis (CAIDA) has developed an algorithm that is claimed to be the most accurate algorithm in this sphere. As a result, it is widely used by Internet researchers. In this paper, we perform an independent validation of CAIDA’s AS relationship inference results. We try to validate CAIDA’s accuracy results for data from April 2012, with the AS 
relationship data published by CAIDA in May 2016, with our own data extracted for May 2016. We find that the accuracy of the algorithm for pc relationship is over 98% and the accuracy for pp relationship is about 94%. The accuracies of both the relationships are very close to the 99.6% and 98.7% accuracies reported in the original paper.