.-lhrrroCt--Peering allowvs service providers to handle trafic surges withbut over-provisioning. reduce the cost of dedicated infrastructure, and leverage the specialization and prices of pariner providers. In this paper. we develop a peering system for multi-provider content delivery based on a cost-optimized peer selection algorithm. We formulate a cost model for evaluating competing peering strategies, and use metasurement data collected from globally distributed nehvork p r o k stations, Iargescnk Web sites, and existing service provider infrashuctures to empirically evaluate propnsed peering strategies. Our analysis shows that our peer selection algorithm is significantly more efficient than greedy alternatirrs, in terms of minimizing senice cnst and respecting nehr-ork delay and server capacity thresholds. nver a brosd range o f real-wnrld scenarios. System design, simulations, network measurements, erprrimentatitm with red networksitestbeds. ISTKODI:CTIOS Delivering largc-scale network services requires a distributed computing and net\\c,rk infr:istructure that provides a consistently high level of pcr1irm1;incc. and reliability in the face of surges in demand, failures, and changes in customer requirements. Service providers who acquire; provision, and manage the s e n i c e infrastructure mnst balance these requirements against the high costs of deploying customerdedicated, over-provisioned resources. Service providers hare addressed this problem to some extent hy using shared .infrastructures to multiplex resources hetween many customers; and thus improve utilization. To lower costs further, however; providers are increasingly interested in leveraging computing or network infrastructure from partners through peering mechanisms that allow provisioning and sharing of computing resources: and settlement and exchange of the resultant revenue. The customer's view remains that of a single provider (who we refer to as the priiiiaiv provider), whicti may in fact consist of pooled resources from several providers distributed over a numher of locations. For In this paper, w e focus on the use of cooperatives for content delivey services. In t h s scenario; the priman. service provider may deplo! a limited content hosting infrastructure in a singlc (or few) data centers, and at the same time. strike agreements with other content distribution senice providers (CDSPs) who agree to s e n e customer content on behalf of the prima? provider for a share of the revenue. As long as the client load can be handled by the prima? provider, reqnests will be sened from the origin since this maximizes revenue for the prima? provider. If the actual or predicted workload exceeds the capacity of the priman's servers, the excess requests are offloaded to the partner seners. The choice of which clients are oftloaded to which partners mav he based on provider cost and capacily, expected performance delivered to the client from a given provider, or policies that prefer one provider o w r another. Figure I shows a simple example of how workload might be managed from the primay provider's seners under normal conditions, and partially offloaded to senice provider to handle surges without over-provisioning, reduce infrastructure costs, and leverage the prices and specialization (e.g., specific geographic regions) i f other providers. While peering for content deliven is appealing for all of these reasons; there are a numher of challenges in designing a ?stem that virtualizes multiple. providers; and directs clients to different providers hased on cost, petfbtmance, and expected load. Our contribution lies in designing and implementing a peering . tem -that minimizes cost while also respecting client 0-7803-8355-9/04/$20.00 02034 IEEE. performance requirements. This is in contrast to pcer selection in traditional peer-to-peer networks where the focus is primarily on efficiently finding a nearby peer with the desired content. W e evaluate our strategy against altcrnative schemes using real trafIic data from large Web sites, request-routing data gathered from measurements of operational CDSPs, and network location d a b collected from a set of globally distributed probe stations. Specilically> we propose solutions for the following key issues: -IP'hen to iffluad? We adopt a proactive approach in n h c h client load is continuously monitored at the priman provider-s servers in order to predict h t u r e demand and trigger offload when load exceeds available capacity. IF/io to offlood? We propose and evaluate a novel client clustming scheme that balances network prosimity and load prediction accuracy. Small clusters enable more accurate estimation of client location, but larger clusters generate more agpegate traffic, thus improving traffic prediction capabilities. IT;l,oni io ofload to'? When choosing a partner provider for a p u p of clients, it is necessary to consider the cost as well as the expected pelformance. This is complicated by separate ndministration and limited information sharing between individual providers. We leverage redirection models developed in [3] to predict performance of partnrrs. How IO offload? Our peering >?stem is hased on DNSbased request-routing, rrhich is the defacto standard used by CDSPs. Domain Name Senice (DNS) provides a relatively transparent way to direct clients between senice providers, and to recover them when appropriate. In evaluating our pcenng strategy we show that our proposed peer selection algorithm is significantly more efficient than geed) alternatives, which average a factor of 1.5 times higher cost. We demonstrate that this performance is consistent over a range of operating environments, including different Web sites; pricing structures, and expected delay thresholds. The remainder of this paper is organized as follows. In the next section we provide background information. In Section 111; we provide a more formal statement of the problem our peering strateeies address. We present our peer selection algoritlun, experimental methodology; and data collection procedures in Sections IV and V. We dctail the results of our analysis in Section VI. We summarize the paper in Section VII. 11. B-\CKGKOL~ND Our peering system uses state of the art techniques to estimate client location and predict performance from partner providers. In this section. we pive a hriel overview of how we leverage existing work in designing our system. In the next section. we provide a more formal statement of the problem addressed in this .paper. using terminology and notation inuoduccd in this section.  . %). is computed as the Euclidean distance between We use this scheme to assign absolute coordinates to thousands of IP addresses. based on measurements from globally distributed probe stations. We can then infer the distance between clients and servers belonging to partner providers to enable the peering tem to direct clients to providers that are expected to meet the performance requirements. We detail the collection of the netvork prohe data, as well as other data sets used in our study, in Section V. Note that while \re limit our attention to distance as the key performance metric (particularly for Web content deliyen) other metrics such as optimizing cache hit rate may also be useful [25]. Large-scale Web sites often senre content from multiple, geographically distributed sener sets that may consist of mirrored servers or be part of a content deliven. network (CDN). The most common approach for directing clients to a specific server is via DNS request routing. DNS-based techniques may also hc used to redirect clients from the priman provider.s hosting infrastructure to 3 partner n h o pelforms its own sener selection [6]. Predicting the performance a panner s e n e r sct will provide to a given client requires some knowledge of how the partner selects servers €or different clients. The actual server selection criteria used in CDNs are generally considered propnetan information, and may he hased on complex and dynamic metrics [5][17], making prediction difficult. 0-7803-8355-9M20.00 02004 LEE. However, a recent measurement-based study [3] of 851 commercial server set deployments showed that, despite the use of a variety of selection criteria, these schemes can be modeled with reasonable accuracy. The study determined that it was possible to predict the distance between clients and the chosen sewer to within 20 ms in 90% of the cases with a few simple models. The study proposed a distance metric that is the average delay from a client to each server in the set, weighted by the probabiliF that the client is directed to 3 particular server. The models developed in the paper included: -ii selecting the closest server to the client in terms of network dela!' (referred to as MIN): iij a uniform choice between the first and second closest (MINZ), iii) load-halancing with uniform server selection (LBP); and iv) a policy in which 80% of the traific is directed to the closest sewer while 20% is uniformly distributed among the remaining servers (WGT). We use information such as the numher of servers; locations of servers, and redirection policies discovered in [3] .to evaluate our peering strategies. Additionally, when inferring the distance between clients and server sets; we use the same weighted average distance metric. . Our peering strategy is described in Section IV and the sewer set data used for its eyaluation is detailed in Section V. - Our goal is to minimize the cost of hosting a workload on a federated infrastructure comprising sets of servers deployed by a priman service provider and its partners. The priman service provider selects amongst p r i m q and partner sen-er sets: each server set provider performs server selection within its own server set. Server sets may be globally or regionally deployed; and server set coverage may be overlapping since multiple providers may deploy sewers in the same network or ,geographical region. Examples of semer sets include surrogate sewers deployed by CDSPs, minored servers deployed hy a content hosting entity, and caching sewers .deployed in access networks. We focus on workloads (such as Web content delive?) where the prima? goal is to service client requests by delivering data to-the client. w e perform our analysis using a fee stmcture representative of the content delivev environment [2 11. Spicifically, the cost of servicing a workload is the sum of the fees charged by the server sets participating in servicing the workload: plus any penalties~ due to violations of specified network delay or capacity thresholds. Server set fees are bandwidth-based, that is; the fee is a charge per megabit of content served per second. Fees are assessed according to the 95*' percentile qf the maximum bandwidth utilized in any measurement period during the service internal. A meaiurement period, for example, might he 60 seconds whereas a service i n t e n d is on the order of 1 month. .denote the senrice interval. Further, let S denote the set of participating server sets where i E S, and K denote the set of clients, k E K . Each sewer set i has a positive fee denoted by Client requests that are directed to an overloaded semer or to a semer for which the network delay exceeds D are said to be rnisdiiructed bv the assignment policv. We use c(.Yf,$) to denote the portion of the workload that is misdirected. A provider incurs a penalty; y,, for workload that is not serviced according to senvice criteria (either because it was not seniced or hecause it was misdirected). Thus, total congestion costs C j for a single provider i are: where flX, is the 95" percentile of a workload X. The terms in the definition of C, represent the cost of offloading traffic t o other providers: (3); the penalties incuned because the resources required to meet the service level objectives were not available when required (4); and the penalties incurred because client requests were incorrectly directed to a server ' In equation (2) we use the notation x ' := max(x, 0; that did not meet the sewice level objectives (5). Note that the cost includes terms related to performance as well as busmessrelated considerations. Our goal is to de\.elop an algorithm capable of finding the assignment 4(r) for all I E T that minimizes the congestion costs (specified ahove in terms (3, 4; 5)) incurred by a single provider I . We do not consider optimizations achieved hy changes in the capacitv (i.e.: the values in I are static), since workload assignment algorithms affect only the effective allocation of the capacity of i and its peers. Also, we assume the wokload ~Y,(r) and the price charged by provider i for sewicing.\;(r) arc not affected by the assignment policy. This allows a simplified cost-based formulation (as opposed to a profit-based formulation). While the solution is deterministic when the workload, S(I), is known, .Y(I) for the full interval T i s not known at the time the selection is made. More importantly, finding the optimal assignment is not computationally feasible (since there are hundreds of thousands of clients in the environment we wish to address). Our goal is not to solve this problem analytically, but instead, to develop a system that uses heuristics to approximate the optimal solution. given the information available at the time of selection. We use the congestion costs defined in this section to compare our stratep to greedy alternatives. We also describe how our algorithm is incorporated into a morc comprehensive peering . tem. capable of managing workload assignments in a largescale commercial website. IV. PEER SELECTIOS ALGORITRSI In this section; we detail our proposed algorithm for costoptimized peering, which ~e refer to as COP. We begin by introducing a norel client clustering technique and then descnhe how COP uses it. We cnntrast our proposal with two alternative p e d y strategies. In later sections; 15-e mill compare the performance of these strategies on workloads generated from two world-wide sporting event Web sites, using sewer sets representative of commercially deployed content deliven infrastructures, and client location data collected from globally distributed network prohe stations. .4. IP .Address Chrsrer?iip COP does not attempt to assi-a individual client IP addresses to sener sets. hut instead operates on clusters of network proximal clients. Workload statistics are tracked and sener set assignments are pelformed on a per-cluster basis. While clustering improves the computational efficiency of thc assignment algorithm, we also use it to mitigate some drawbacks of DNS-hased redirection. DNS redirection is a highly scalable, hut coarse-grained mechanism for directing clients to network senice points. Since DNS responses may be cached a1 clients and local DNS (LDNS) serverx multiple requests from potentially different clients may use the result from a single DNS resolution. Setting the expiration of a DNS response to a small value can limit, but not eliminate, this effect. We propose a traffic clustering technique that enables clients to he grouped fur effective network location and traffic estimation, and thus helps to mitigate some of the issues that arise from the coarsegrained client-to-server assignments common to DNS-based redirection. Our clustering approach combines techniques from network-aware clustering, location inference, and spatial analysis. We use network prohe data described in Section V to assign ahsolute coordinates to IP addresses. IP addresses that differ only by the last octet (i.e.> I24 address subnets) are grouped together and assigned a single set of coordinates. Our decision to group IP addresses according to the I24 address is based on findings in [2] indicating a small variance in delay measurements to IP addresses in the same 124 suhnet. The clustering process hegins by selecting a representative set of station coordinates. a s depicted in Figure 2 ; and assigning IP addresses to the nearest station. The station coordinates; which are the centroids of the coordinates of IP addresses in the cluster; sewe as the location estimate for all IP addresses \rithin the cluster. In Section VI; we provide a comparative evaluation of station selection alternatives, including human population and Web traffic centers. We also evaluate COP over a range of cluster sizes. The COP algorithm functions by accepting three primaninputs: server set data, workload data, and IP address coordinate data. It produces an assignment of client vorkload to different s e n e r sets, including the primae provider. The data for each s e n e r set i; is the contracted capacity. ri, the unit price of service; pi; and the ahsolute coordinates, V(s,); of the IP addresses of each semer se in sewer set I . The senrer set IP addresses could either be provided by the partner or inferred using techniques similar tu those described in [ 3 ] . The workload input is a traffic log in which euch e n t v represents a client request and includes a timestamp: client IP address and number of bytes sent in response to the request. The imrkload; .I'(I)> is tracked for each client cluster in terms of number of requests and number of bytes in the response. The absolute coordinates of each client cluster, V(k), are also computed and stored. The output of COP is an assignment of the percentage of requests from each client cluster that should he assigned to each s e n e r set. The COP algorithm casts the sewer set selection problem as a minimum cost network tlow optimization problem. Mincost flow formulations are a common tool for solving 0-7803-8355-9/04/S20.00 82004 BEE. 853 Sen-cr Sets Figure 3 ; client clusters are connected to sen-er sets in a bipartite graph. An edge connects cluster k to server set i; if the distance hetwen X and i (as defined in Section 11.B) is less than the network delay threshold, D. The costs of all edges are 0. usccpt those leading from.server sets to the si&. These bear the feu associated with the server set. The capacity of the w T c r tct lo sink edges are .set to the ,contracted capacih of the tenur set. .The capacity of edges from source to client clustci-. :in? clicnt cluster to sewer sets is set to the workload gencratcd h! tlic con-cspunding client cluster. COP implements the netirork simplex algorithm [I] to. find the tlo\v values, h, for each (X, ;)-tuple, that meet the min-cost, max-flow objective. At administratively defined intends, COP produces a map, which specifies the fraction of the norkloadfi/.\*(t)~from h-that is to he directed to i in interval 1. The map is stored in an expanded tric data structure designed for fast IP routing table lookups. Our peering DNS protocol engine, pDNS, peiforms a lookup using the client IP address when a client request is received to determine the appropriate sewer set assignment. Although selcction criteria for multi-provider content deliven have been proposed. none address the criteria we wish to evaluate (namely. minimizing service deliver?. costs while respecting service level objectives). For example, the Content Serving Utilit). descrihed in [ I l l allows an administrator to contipre the prima? proaider's authoritative DNS sener to redirect clients to a partner CDN based.on a few static policies, but does not take into account cost or workload. A second example, the CDN Brokering system [6], implements. a DNS-hased request-routing system and an
A peering system for content delivery workloads in a federated, multi-provider infrastructure has been presented in REF , but the peering strategy, resource provisioning and performance guarantees among partnering CDNs is unexplored in this work.
Effective peering for multi-provider content delivery services
IEEE INFOCOM 2004
IEEE INFOCOM 2004
Computer Science