On the Number of Distributed Measurement Points forNetwork TomographyJoseph D. HortonFaculty of Computer ScienceUniversity of New BrunswickFredericton, NB E3B 5A3, [email protected] L ´opez-OrtizSchool of Computer ScienceUniversity of WaterlooWaterloo, Ont. N2L 3G1, [email protected] topology information is only made available in aggregateform by standard routing protocols. Connectivity information andlatency characteristicsmust therefore be inferred using indirect tech-niques. In this paper we consider measurements using a distributedset of measurement points or beacons. We show that computing theminimum number of required beacons on a network under a BGP-like routing policy is NP-hard and at best Ω(log n)-approximable.In the worst case at least (n − 1)/3 and at most (n +1)/3 beaconsare required for a network with n nodes. We then introduce someobservations that allow us to propose a relatively small candidateset of beacons for the current Internet topology. The set proposedhas properties with relevant applications for all-paths routing on thepublic Internet and performance based routing.Categories and Subject DescriptorsC.2.3 [Computer-Communication Networks] Network monitor-ingGeneral TermsTheory, MeasurementsKeywordsNetwork measurements, Internet tomography, topology discovery,NP-hard, approximation algorithms, resilient overlay networks.1. INTRODUCTIONEfficient routing and caching require accurate connectivity infor-mation of the Internet. However, by their very nature, Internet pro-tocols make this task difficult. Routing decisions are made locallyand most often shared across organizations only in aggregate form.Furthermore connectivity changes dynamically due to node or linkfailures and router misconfiguration. At any given time between1.5% and 3.4% of connections suffer a visible pathology [29]. Em-pirically, it has been observed that a few key failures often havesignificant impact on routing decisions.Permission to make digital or hard copies of all or part of this work forpersonal or classroom use is granted without fee provided that copies arenot made or distributed for profit or commercial advantage and that copiesbear this notice and the full citation on the first page. To copy otherwise, torepublish, to post on servers or to redistribute to lists, requires prior specificpermission and/or a fee.IMC’03, October 27–29, 2003, Miami Beach,Florida, USA.Copyright 2003 ACM 1-58113-773-7/03/0010 ...$5.00.Routing decisions and content distribution networks (web caches)require proper connectivity and latency information so as to di-rect traffic in an optimal fashion. The family of internet protocolscollect and distribute only a limited amount of information on thetopology, connectivity and state of the network. Hence the infor-mation of interest, be it latency, topology, or connectivity has to beinferred from experimental measurements. Gathering connectivityinformation through indirect measurements is known as Internettomography [15, 37, 14]. In this work we consider the problem ofdetermining the topology of the Internet under the assumption thata distributed set of measurement points (sometimes called beacons)running special software is deployed at key sites across the entireInternet. This has emerged as one of the strategies of choice formeasuring the state of the Internet (e.g. [33, 7, 3, 36, 18]).1.1 Related WorkThere are two distinctive types of measurements that can be ob-tained through the use of tomography: (1) obtain an accurate mapof the slowly evolving link topology of the network, and (2) de-tect short-lived, transient effects. For the first objective, we can uselong lived processes, spawning perhaps several days, while for thesecond we need a fast and accurate method of detecting changes,with as light a load as possible on the network.Currently there are several efforts in progress to obtain topologyand performance measurements on the Internet [33, 26, 7, 37, 3, 36,18], several of which use some form of measurement points to ex-tract information from the network. In practice these measurementpoints are often placed in universities and other organizations thatare willing to host the software or hardware required. The locationof these measurement devices or beacons is determined accordingto various heuristics [1, 4, 10, 13, 7]Extensive research has taken place over the last few years on de-ploying measurement points and studying their characteristics. Forexample the National Internet Measurement Infrastructure (NIMI)[1, 2, 3, 31, 18] is a concerted effort to deploy general purposebeacons, termed “NIMI probes” with particular focus in scalabil-ity and flexibility. Some other measurement efforts of note are, inno particular order, MINC [12], the Internet Weather Report [33],Cheswick et al. visualization project [13], Claffy et al. efforts oninternet tomography [15, 14], SPAND [35], Malan and Jahandian’sWindmill [27], as well as a set of performance measurements thatrelied implicitly on a distributed measurement architecture (e.g.[16, 21, 22, 29, 30, 20]).While substantial efforts have been directed at the deploymentand use of distributed measurement systems, there has been some-what less research focused on the systematic study of the propertiesrequired for such measurement sets. Jamin et al. propose theoreti-204cal methods as well as ad hoc heuristics for computing the locationof a set of measurement points whose aim is to compute the dis-tance maps on the network [25]. Recently, Barford et al. providedthe first systematic experimental study to validate the empirical ob-servation that a relatively small number of measurement points isgenerally sufficient to obtain an accurate map of the network [8].Lastly, Bu et al. considerthe problem of the effectiveness of tomog-raphy on networks of general topology [11]. While their focus is onthe ability to infer performance data from a set of multicast trees,their systematic study of the abilities of tomography in arbitrarynetworks is germane to our work, as we also consider the place-ment of measurement points both in the current internet topologyand in general networks of arbitrary topology.In this paper we study the optimal and systematic placement ofthese beacons and the properties of a beacon set mapping the net-work both under theoretical and empirical analysis.First we take a theoretical tack and prove in Section 4 that com-puting the minimum number of required beacons
View Full Document
Unlocking...