Tomography-based Overlay Network MonitoringYan Chen, David Bindel, Randy H. KatzComputer Science DivisionUniversity of California at BerkeleyBerkeley, CA 94720-1776, USA{yanchen, dbindel, randy}@cs.berkeley.eduABSTRACTOverlay network monitoring enables distributed Internet ap-plications to detect and recover from path outages and peri-ods of degraded performance within seconds. For an overlaynetwork with n end hosts, existing systems either requireO(n2) measurements, and thus lack scalability, or can onlyestimate the latency but not congestion or failures. Unlikeother network tomography systems, we characterize end-to-end losses (this extends to any additive metrics, includinglatency) rather than individual link losses. We find a mini-mal basis set of k linearly independent paths that can fullydescribe all the O (n2) paths. We selectively monitor andmeasure the loss rates of these paths, then apply them to es-timate the loss rates of all other paths. By extensively study-ing synthetic and real topologies, we find that for reasonablylarge n (e.g., 100), k is only in the range of O(n log n).Thisis explained by the moderately hierarchical nature of Inter-net routing.Our scheme only assumes the knowledge of underlying IPtopology, and any link can become lossy or return to normal.In addition, our technique is tolerant to topology measure-ment inaccuracies, and is adaptive to topology changes.Categories and Subject DescriptorsC.2.3 [Network Operations]: Network monitoringGeneral TermsMeasurement, AlgorithmsKeywordsOverlay networks, Network measurement and monitoring,Network tomography, Numerical linear algebra1. INTRODUCTIONWith the rapid growth of the Internet, new large-scaleglobally distributed network services and applications havePermission 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.emerged, such as overlay routing and location systems, application-level multicast, and peer-to-peer file sharing. As these sys-tems have flexibility in choosing their communication pathsand targets, they can benefit significantly from dynamic net-work distance prediction (e.g., latency and loss rate).Existing network distance estimation systems can be groupedinto two categories: static estimation [18, 23] and dynamicmonitoring [13, 8, 3]. Previous static estimation systems,such as Global Network Positioning (GNP) [18], achieve ahigh level of accuracy, but also incur high overhead for con-tinuously updating the estimates.Dynamic monitoring can detect path outages and periodsof degraded performance within seconds. However, existingschemes either require pair-wise measurements for all endhosts, and thus lack scalability [3]; or they can only esti-mate latency, but not congestion or failures [13, 8]. Existingscalable systems, such as [13, 8], cluster end hosts based ontheir network proximity or latency similarity under normalconditions. However, end hosts in the same cluster may nothave similar losses, especially when the losses happen in thelast mile.In this paper, we describe a scalable overlay network con-gestion/failure monitoring system which is highly accurateand incrementally deployable. Consider an overlay networkof n end hosts; we define a path to be a routing path be-tween a pair of end hosts, and a link to be an IP link betweenrouters. A path is a concatenation of links. There are O(n2)paths among the n end hosts, and we wish to select a min-imal subset of paths to monitor so that the loss rates andlatencies of all other paths can be inferred. The loss ratesare used to estimate the congestion/failures on the overlaypaths.To this end, we propose a tomography-based overlay net-work monitoring system in which we selectively monitor abasis set of k paths (typically k n2). Any end-to-end pathcan be written as a unique linear combination of paths inthe basis set. Consequently, by monitoring loss rates for thepaths in the basis set, we infer loss rates for all end-to-endpaths. This can also be extended to other additive met-rics, such as latency. The end-to-end path loss rates can becomputed even when the paths contain unidentifiable linksfor which loss rates cannot be computed. We provide anintuitive picture of this characterization process in terms ofvirtual links.Although congestion outbursts within seconds are hard todetect and bypass, the delay in Internet inter-domain pathfailovers averages over three minutes [16]. Our loss rateestimation will filter out measurement noise with smoothing216techniques, such as exponentially-weighted moving average(EWMA), and detect these path failovers quickly to haveapplications circumvent them.Our key observation is that k grows relatively slowly as afunction of n. The dimension k is bounded by the numberof links in the subgraph induced by the routing paths. Inan Internet-like topology with a power-law degree distribu-tion, there are O(N) links, where N is the total number ofend hosts in the network. This is because a small number ofnodes have high degree and the links between them are heav-ily used [12]. Consequently, if n = O(N),thenk<O(n).However, even when n N, the moderately hierarchicalstructure of the network causes many routing paths to over-lap [26], so that the number of links in the routing path sub-graph grows much slower than O (n2). Our extensive studyof both synthetic and real Internet topologies suggests thatfor a randomly selected subset of n end hosts, k grows likeO(n log n) when n is sufficiently large (say 100).Furthermore, our technique is tolerant to topology mea-surement inaccuracies, and is adaptive to topology changes.Besides simulating our system with various synthetic andreal topologies, we implemented our system on the Planet-Lab testbed [22]. We deployed it on 51 global hosts (eachfrom a different organization) and ran the experiments overfour weekdays with a total of 76.5M UDP packets. Bothsimulation and implementation results show we achieve highaccuracy when estimating path loss rates with k measure-ments. For example, the average absolute error of loss
View Full Document
Unlocking...