BGP Tomography

Abstract

The Border Gateway Protocol (BGP) is the glue that binds together the many diverse networks that make up the Internet. It is a routing protocol, that distributes possible routes for subnets of the Internet, but does more than just carry routes -- it is a tool for implementing routing policy --- political and commercial decisions about routing. Given the large scale complex nature of the Internet, it is not surprising that BGP's dynamic behaviour is exceedingly complex, and indeed it displays many of the statistical characteristics that we have come to expect of Internet data (e.g. high variability over many time scales), but what might be surprising is that some measurements of this system can be modelled quite simply. This talk will describe a challenge that we forsee in the future. The challenge of modelling BGP routing, and from this building models for infering the internal state of the Internet via the indirect measurement of BGP routing announcements. The problem has aspects in common with network tomography problems, in which one attempts to infer internal topology or performance of a network from end-to-end probes through the network, and indeed it has commonalities with more general tomography problems. Hence it is to be hoped that some of the techniques used in these problems may be directly applicable to this new problem of BGP tomography.