High Arity Nodes, Routing and Internet Tomography
Loading...
Files
Date
Authors
Journal Title
Journal ISSN
Volume Title
Publisher
Abstract
Internet topology information is only made available in aggregate form by standing routing protocols. Connectivity information and latency characteristics must therefore be inferred using indirect techniques. In this paper we consider measurement techniques using strategically place nodes called beacons. We show that computing the minimum number of required beacons on a network under a BGP-like routing policy is NP-complete and at best U(log n)-approximable. In the worst case at least n/4 and at most (n+1)/3 beacons are required for a network with n nodes. We then introduce some results and observations that allow us to propose a relatively small candidate set of beacons for the current Internet topology. The set proposed has properties with relevant applications for all paths routing on the public Internet as well as interesting economic settlement properties for public peering.