2008-09-04 Readings - Interdomain Routing

ON INFERRING AUTONOMOUS SYSTEM RELATIONSHIPS IN THE INTERNET,

Lixin Gao

Summary: A study to infer the AS topology of the internet using BGP routing tables. Obtains BGP routing tables from publicly available Route Views router in Oregon (limited number of such routers). Classifies AS relationships into provider-customer (I route for you type), siblings (I route for you and you route for me), and peers (we don't route for each other). Uses notions such as uphill path and downhill path; transit relationship exist going uphill and going downhill. Identify top provider by AS size, given by AS degree (level of connectivity to other AS). Sibling relationship exist if mutual transit. Peering relationship exists if two AS are at top of the AS path, and their degrees differ by no more than a factor R. Results verified close to 100% by AT&T internal AS info; WHOIS lookup services further confirms sibling-sibling relationships. Sibling relationship inference the weakest.

Background required: BGP, which is presented in the other reading.

Criticism and discussion points: The R parameter in peering inference is really ugly and somewhat haphazard. The author acknowledged such. Still, would be good to have somewhat sound logic behind it. Did not explain why sibling inference so inaccurate even though the logic seems air-tight. The results are pretty convincing, but if the assumption that each AS path should have only one peering relationship is wrong, then their peering inference would be totally messed up. The usual inference evaluations would have a training set data to tune their R and a test set. Their dataset and the nature of their experiment prevents this.

I wonder if ISP has done similar work to infer AS relationships using their own routing tables and data.

Just had a mischievous insight ... Suppose the ISP want to keep their peering/sibling/customer info secrete ... and WHOIS is public ... and their method is published ... and their method is scientifically sound ... the black hats can do a lot of crap with this info. I wonder what Vern Paxson would think of this ...


INTERDOMAIN INTERNET ROUTING,

Hari Balakrishnan, Nick Feamster

Summary: Explains BGP in most of its gory detail ... Include notes on AS, route export/import, design goals, AS relationships, eBGP/iBGP, attributes, multi-homing issues, convergence problems, etc. Descriptive textbook reading.

Background required: Need to know Intra-AS routing etc.

Criticisms and discussion points: Textbook material ... the technology is what it is ... not much to say here ... Talk about multi-homing issues perhaps? It's real enough ...