Managing a Portfolio of Overlay PathsDaria Antonova∗Arvind Krishnamurthy†Zheng Ma†Ravi Sundaram∗ABSTRACTIn recent years, several architectures have been proposedand developed for supporting streaming applications thattake advantage of multiple paths through the network si-multaneously. We consider the problem of computing a setof paths and the relative amounts of data conveyed throughthem in order to provide the desired level of performance fordata streams. Given the expectation, variance, and covari-ance of an appropriate metric of interest for overlay links, weattempt to solve the underlying resource allocation problemby applying methods used in managing a finance portfolio.We observe that the flow allocation problem requires con-strained application of these methods, and we discuss thetractability of enforcing the constraints. We finally presentsome simulation results to evaluate the effectiveness of ourproposed techniques.Categories and Subject DescriptorsC.2.2 [Computer Communication Networks]: NetworkProtocols—Applications, r outing protocolsGeneral TermsAlgorithms, Performance, Measurement, ExperimentationKeywordsOverlay networks, video streaming1. INTRODUCTIONIn recent years, considerable work has been done in char-acterizing the quality of redundant paths in the Internet.Recent work on overlay networks has allowed various projects∗Department of Computer Science, Northeastern University.Email: {daria,koods}@ccs.neu.edu†Department of Computer Science, Yale University. Sup-ported by NSF grants CCR-9985304, ANI-0207399, andCCR-0209122. Email: {arvind,zhengma}@cs.yale.eduPermission 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.NOSSDAV’04, June 16–18, 2004, Cork, Ireland.Copyright 2004 ACM 1-58113-801-6/04/0006 ...$5.00.to exploit this redundancy to achieve better performanceand higher fault-tolerance. Detour [24], for instance, im-proves routing efficiency by exchanging congestion informa-tion between nodes and adaptively routing through overlaypaths that correspond to better routes. Resilient OverlayNetwork (RON) [1] allows distributed applications to per-form overlay path selection in an application-specific man-ner, detect path failures, and recover by routing data throughother overlay paths. In fact, many high performance stream-ing media systems exploit the redundant paths in a concur-rent manner to provide higher throughput or better qualityof service. CoopNet [20] streams media and employs stripingover multiple overlay trees to enhance both performance andreliability. Splitstream [7], which is built on top of the Pastryoverlay network, also multicasts content over multiple over-lay trees. Byers et al. [6] propose a system for performingmulti-point transfers across richly connected overlays by ju-diciously coordinating delivery of subsets of data in a highlydistributed and concurrent fashion. Cheng et al. [8] addressthe dual problem of collecting data from several hosts bycarefully scheduling the movement of data. Nguyen and Za-khor [19] propose the use of sending redundant data overmultiple paths to minimize packet loss.An important issue that repeatedly shows up in many ofthe above-mentioned efforts is the need to identify a goodset of redundant paths to be used for communication. Inorder to obtain good performance, most systems try to useoverlay paths that correspond to disjoint sets of physicallinks. In situations where completely disjoint paths can notbe identified, these system try to minimize the use of sharedphysical links [19, 31]. Typically, a probing tool, such astraceroute, is used to obtain the characteristics of the over-lay paths, and some simple heuristics are employed to es-timate the disjointness of candidate paths during path se-lection. Nguyen and Zakhor [19] use a metric that countsthe number of shared physical links between two candidatepaths, while Zhang et al. [31] take into account the latency ofthe shared physical links in order to distinguish low-latencyLAN links from high-latency backbone links. Given theirsimplicity and their heuristic nature, these schemes couldfail to recognize that some of the physical links are actuallyhigh-performance, over-provisioned links and would refrainfrom using paths that share them. Splitstream makes anindirect attempt at minimizing the sharing of physical linksby ensuring that each overlay node appears as an interme-diate node at most once in different overlay trees. Manyother user-level multicast proposals [4, 14, 22, 33] recognizethe importance of this issue and evaluate their systems us-30-60%-40%-20%0%20%40%60%80%100%84 86 88 90 92 94 96 98YearReturnExxon Southwest Airlines-60%-40%-20%0%20%40%60%80%100%84 86 88 90 92 94 96 98YearReturnFigure 1: Return profiles for Exxon and Southwest Airlines.ing performance metrics that track the worst case number ofoverlay paths that share some physical link in the network.They do not, however, provide any specific techniques forminimizing this quantity.In this paper, we propose methods for computing a setof paths and the relative amounts of data to be conveyedthrough them for a given pair of source-destination nodes.We require as inputs statistical measures that characterizethe behavior of the overlay links with respect to a predeter-mined performance metric, such as latency, jitter, or loss-rate. The statistical measures used in our approach aretraditional ones such as expectations, variances, and covari-ances. For instance, in one of our target settings, where weare interested in optimizing for user-perceived latency, wetake into account the mean and variance of latency for eachoverlay link as well as the covariance of latency over pairs oflinks. We believe that the complex physical structure of theunderlying network could be captured by these statisticalmeasures. In this respect, we draw inspiration from previ-ous work [3, 12, 23] on shared congestion detection that isbased on the observation that if two flows share a congestedphysical link, then packets from the two flows traversing thecongested link at about the same time are likely to be ei-ther dropped or delayed by similar amounts of time.
View Full Document
Unlocking...