Automatic Inference of BGP Community Semantics

The Border Gateway Protocol (BGP) enables communication between Autonomous Systems (ASes) on the Internet. BGP offers significant flexibility for traffic engineering through BGP communities, which are operator-defined tags that convey information or requests in route announcements. Unfortunately, the absence of standardized semantics or centralized repositories for BGP communities complicates and limits their use, hindering the effective management of interdomain routing. This thesis develops techniques to infer BGP community semantics using public BGP data from routing collectors, overcoming the lack of documentation and providing datasets that can be automatically updated. We first propose a set of techniques to infer location communities, which are communities related to entities or locations traversed by a route. We apply our techniques to billions of routing records from public BGP collectors and show that they produce high precision (ranging from 86% to 93%) and recall (ranging from 72% to 81%). We also design and evaluate algorithms to automatically uncover BGP action communities and ASes that violate standard practices, revealing undocumented relationships between them (e.g., sibling relationships). Our experimental evaluation uncovers previously unknown AS relationships and shows that our algorithm to identify action communities achieves average precision and recall of 92.5% and 86.5%, respectively.