We present a novel technique for modulating the appearance frequency of a few tokens within a dataset for encoding an invisible watermark that can be used to protect ownership rights upon data. We develop optimal as well as fast heuristic algorithms for creating and verifying such watermarks. We also demonstrate the robustness of our technique against various attacks and derive analytical bounds for the false positive probability of erroneously “detecting” a watermark on a dataset that does not carry it. Our technique is applicable to both single dimensional and multidimensional datasets, is independent of token type, allows for a fine control of the introduced distortion, and can be used in a variety of use cases that involve buying and selling data in contemporary data marketplaces.

In light of the growing impact of disinformation on social, economic, and political landscapes, accurate and efficient identification methods are increasingly critical. This paper introduces HyperGraphDis, a novel approach for detecting disinformation on Twitter that employs a hypergraph-based representation to capture (i) the intricate social structures arising from retweet cascades, (ii) relational features among users, and (iii) semantic and topical nuances. Evaluated on four Twitter datasets -- focusing on the 2016 U.S. presidential election and the COVID-19 pandemic -- HyperGraphDis outperforms existing methods in both accuracy and computational efficiency, underscoring its effectiveness and scalability for tackling the challenges posed by disinformation dissemination. HyperGraphDis displays exceptional performance on a COVID-19-related dataset, achieving an impressive F1 score (weighted) of approximately 89.5%. This result represents a notable improvement of around 4% compared to the other state-of-the-art methods. Additionally, significant enhancements in computation time are observed for both model training and inference. In terms of model training, completion times are accelerated by a factor ranging from 2.3 to 7.6 compared to the second-best method across the four datasets. Similarly, during inference, computation times are 1.3 to 6.8 times faster than the state-of-the-art.

A large number of Data Marketplaces (DMs) have appeared in the last few years to help owners monetize their data, and data buyers optimize their marketing campaigns, train their ML models, and facilitate other data-driven decision processes. In this paper, we present a first of its kind measurement study of the growing DM ecosystem, focused on understanding which features of data are actually driving their prices in the market. We show that data products listed in commercial DMs may cost from few to hundreds of thousands of US dollars. We analyze the prices of different categories of data and show that products about telecommunications, manufacturing, automotive, and gaming command the highest prices. We also develop classifiers for comparing data products across different DMs, as well as a regression analysis for revealing features that correlate with data product prices of specific categories, such as update rate or history for financial data, and volume and geographical scope for marketing data.

Spatio-temporal information is used for driving a plethora of intelligent transportation, smart-city and crowd-sensing applications. Data is now a valuable production factor and data marketplaces have appeared to help individuals and enterprises bring it to market and the ever-growing demand. Such marketplaces are able to combine data from different sources to meet the requirements of different applications. In this paper we study the problem of estimating the relative value of spatio-temporal datasets combined in marketplaces for predicting transportation demand and travel time in metropolitan areas. Using large datasets of taxi rides from Chicago, Porto and New York we show that simplistic but popular approaches for estimating the relative value of data, such as splitting it equally among the data sources, more complex ones based on volume or the "leave-one-out" heuristic, are inaccurate. Instead, more complex notions of value from economics and game-theory, such as the Shapley value, need to be employed if one wishes to capture the complex effects of mixing different datasets on the accuracy of forecasting algorithms. This does not seem to be a coincidental observation related to a particular use case but rather a general trend across different use cases with different objective functions.

In this paper we propose a method for using mobile network data to detect potential COVID-19 hospitalizations and derive corresponding epidemic risk maps. We apply our methods to a dataset from more than 2 million cellphones, collected by a mobile network provider located in London, UK. The approach yields a 98.6% agreement with released public records of patients admitted to NHS hospitals. Analyzing the mobility pattern of these individuals prior to their potential hospitalization, we present a series of risk maps. Compared with census-based maps, our risk maps indicate that the areas of highest risk are not necessarily the most densely populated ones and may change from day to day. Finally, we observe that hospitalized individuals tended to have a higher average mobility than non-hospitalized ones.

Several data protection laws include special provisions for protecting personal data relating to religion, health, sexual orientation, and other sensitive categories. Having a well-defined list of sensitive categories is sufficient for filing complaints manually, conducting investigations, and prosecuting cases in courts of law. Data protection laws, however, do not define explicitly what type of content falls under each sensitive category. Therefore, it is unclear how to implement proactive measures such as informing users, blocking trackers, and filing complaints automatically when users visit sensitive domains. To empower such use cases we turn to the Curlie.org crowdsourced taxonomy project for drawing training data to build a text classifier for sensitive URLs. We demonstrate that our classifier can identify sensitive URLs with accuracy above 88%, and even recognize specific sensitive categories with accuracy above 90%. We then use our classifier to search for sensitive URLs in a corpus of 1 Billion URLs collected by the Common Crawl project. We identify more than 155 millions sensitive URLs in more than 4 million domains. Despite their sensitive nature, more than 30% of these URLs belong to domains that fail to use HTTPS. Also, in sensitive web pages with third-party cookies, 87% of the third-parties set at least one persistent cookie.

Being able to check whether an online advertisement has been targeted is essential for resolving privacy controversies and implementing in practice data protection regulations like GDPR, CCPA, and COPPA. In this paper we describe the design, implementation, and deployment of an advertisement auditing system called eyeWnder that uses crowdsourcing to reveal in real time whether a display advertisement has been targeted or not. Crowdsourcing simplifies the detection of targeted advertising, but requires reporting to a central repository the impressions seen by different users, thereby jeopardizing their privacy. We break this deadlock with a privacy preserving data sharing protocol that allows eyeWnder to compute global statistics required to detect targeting, while keeping the advertisements seen by individual users and their browsing history private. We conduct a simulation study to explore the effect of different parameters and a live validation to demonstrate the accuracy of our approach. Unlike previous solutions, eyeWnder can even detect indirect targeting, i.e. , marketing campaigns that promote a product or service whose description bears no semantic overlap with its targeted audience.

The question of “how far” technologies and business models of the web should go into collecting personal data of unassuming, or at best moderately informed citizens, appears to be one of the most timely questions of our times. Indeed, whenever we read a news article, “like” a page on a social network, or “check in” to a popular spot, our digital trace collected, processed, fused, and traded among myriads of tracking, analytics, advertising, and marketing companies becomes an ever more accurate descriptor of our lives, our beliefs, our desires, our likes and dislikes. The resulting revenue from marketing and advertising activities driven by the digital traces of millions of people is what funds the free online services we have come to rely upon.

Online advertising is progressively moving towards a programmatic model in which ads are matched to actual interests of individuals collected as they browse the web. Letting the huge debate around privacy aside, a very important question in this area, for which little is known, is: How much do advertisers pay to reach an individual?

We present the design, implementation, validation, and deployment of the Price Sheriff, a highly distributed system for detecting various types of online price discrimination in e-commerce. The Price Sheriff uses a peer-to-peer architecture, sandboxing, and secure multiparty computation to allow users to tunnel price check requests through the browsers of other peers without tainting their local or server-side browsing history and state. Having operated the Price Sheriff for several months with approximately one thousand real users, we identify several instances of cross-border price discrimination based on the country of origin. Even within national borders, we identify several retailers that return different prices for the same product to different users. We examine whether the observed differences are due to personal-data-induced discrimination or A/B testing, and conclude that it is the latter.

We have developed a novel methodology for deriving bandwidth prices for premium direct peering between Access ISPs (A-ISPs) and Content and Service Providers (CSPs) that want to deliver content and services in premium quality. Our methodology establishes a direct link between service profitability, for example, from advertising, user and subscriber loyalty, interconnection costs, and finally bandwidth price for peering. Unlike existing work in both the networking and economics literature, our resulting computational model, built around Nash bargaining, can be used for deriving quantitative results comparable to actual market prices. We analyze the U.S. market and derive prices for video, that compare favorably with existing prices for transit and paid peering. We also observe that the fair prices returned by the model for high-profit/low-volume services such as search, are orders of magnitude higher than current bandwidth prices. This implies that resolving existing (fierce) interconnection tussles may require per service, instead of wholesale, peering between A-ISPs and CSPs. Our model can be used for deriving initial benchmark prices for such negotiations.

Online Behavioural targeted Advertising (OBA) has risen in prominence as a method to increase the effectiveness of online advertising. OBA operates by associating tags or labels to users based on their online activity and then using these labels to target them. This rise has been accompanied by privacy concerns from researchers, regulators and the press. In this paper, we present a novel methodology for measuring and understanding OBA in the online advertising market. We rely on training artificial online personas representing behavioural traits like 'cooking', 'movies', 'motor sports', etc. and build a measurement system that is automated, scalable and supports testing of multiple configurations. We observe that OBA is a frequent practice and notice that categories valued more by advertisers are more intensely targeted. In addition, we provide evidences showing that the advertising market targets sensitive topics (e.g, religion or health) despite the existence of regulation that bans such practices. We also compare the volume of OBA advertising for our personas in two different geographical locations (US and Spain) and see little geographic bias in terms of intensity of OBA targeting. Finally, we check for targeting with do-not-track (DNT) enabled and discover that DNT is not yet enforced in the web.

Ride-sharing systems have the potential to match travelers with similar itineraries and time schedules, and to bring significant benefits to individual users and the city as a whole. However, this is a challenging task, since users' requests are not known in advance and they become available a few minutes before departure. In this paper, we design an online ride sharing system, where drivers and passengers send their requests for a ride in advance, possibly on a short notice. Our design is efficient and optimal. This is achieved by dividing the system into two components: the constraint satisfier and the matching module. The constraint satisfier takes as input the spatio-temporal constraints of drivers and passengers and provides feasible (driver, passenger) pairs in real time, and the matching module takes as input the feasible pairs and provides a maximum cardinality matching of drivers and passengers. Our preliminary evaluation shows that the constraint satisfier can resolve the most expensive queries (matching of passenger to en-route drivers) in 2 seconds (on average), while the matching module can achieve a matching ratio of 78% when the offline upper-bound is 80%.

Online Behavioral Advertising (OBA) is an important revenue source for online publishers and content providers. However, the extensive user tracking required to enable OBA raises valid privacy concerns. Existing and proposed solutions either block all tracking, therefore breaking OBA entirely, or require significant changes on the current advertising infrastructure, making adoption hard. We propose Web Identity Translator (WIT), a new privacy service running as a proxy or middlebox. WIT stops the original tracking cookies from being set on the browser of users and instead substitutes them by private cookies it controls. Manipulating the mapping between tracking and private cookies WIT maintains permits transparent OBA to continue while simultaneously protecting the identity of users from attacks based on behavioral analysis of browsing patterns.

Peering in the Internet interdomain network has long been considered a “black art”, understood in-depth only by a select few peering experts while the majority of the network operator community only scratches the surface employing conventional rules-of-thumb to form peering links through ad hoc personal interactions. Why is peering considered a black art? What are the main sources of complexity in identifying potential peers, negotiating a stable peering relationship, and utility optimization through peering? How do contemporary operational practices approach these problems? In this work we address these questions for Tier-2 Network Service Providers. We identify and explore three major sources of complexity in peering: (a) inability to predict traffic flows prior to link formation (b) inability to predict economic utility owing to a complex transit and peering pricing structure (c) computational infeasibility of identifying the optimal set of peers because of the network structure. We show that framing optimal peer selection as a formal optimization problem and solving it is rendered infeasible by the nature of these problems. Our results for traffic complexity show that 15% NSPs lose some fraction of customer traffic after peering. Additionally, our results for economic complexity show that 15% NSPs lose utility after peering, approximately, 50% NSPs end up with higher cumulative costs with peering than transit only, and only 10% NSPs get paid-peering customers.

Distributing long-tail content is a difficult task due to the low amortization of bandwidth transfer costs as such content has limited number of views. Two recent trends are making this problem harder. First, the increasing popularity of user-generated content and online social networks create and reinforce such popularity distributions. Second, the recent trend of geo-replicating content across multiple points of presence spread around the world, done for improving quality of experience (QoE) for users. In this paper, we analyze and explore the tradeoff involving the “freshness” of the information available to the users and WAN bandwidth costs, and we propose ways to reduce the latter through smart update propagation scheduling, by leveraging on the knowledge of the mapping between social relationships and geographic location, the timing regularities and time differences in end user activity. We first assess the potential of our approach by implementing a simple social-aware scheduling algorithm that operates under bandwidth budget constraints and by quantifying its benefits through a trace-driven analysis. We show that it can reduce WAN traffic by up to 55 percent compared to an immediate update of all replicas, with a minimal effect on information freshness and latency. Second, we build TailGate, a practical system that implements our social-aware scheduling approach, which distributes on the fly long-tail content across PoPs at reduced bandwidth costs by flattening the traffic. We evaluate TailGate by using traces from an OSN and show that it can decrease WAN bandwidth costs by as much as 80 percent and improve QoE. We deploy TailGate on PlanetLab and show that even in the case when imprecise social information is available, it can still decrease by a factor of 2 the latency for accessing long-tail YouTube videos.

Mobile broadband is predominantly priced following tiered plans that involve a certain prepaid emph{commit volume} and additional metered volume priced at a higher emph{penalty rate}. An individual's demand, however, may vary wildly from month to month and thus users inevitably purchase packages that are either too small or too large for their needs. By collaborating in predefined closed (eg, family) or open groups (eg, through tethering) users can reduce both the amount of paid-but-left-unused capacity or the high penalty rates. In this paper we present a quantitative study of collaborative consumption using data from 40K mobile subscribers and tariffs from ten operators around the world. We show that small 2-person family plans offer modest expected savings in the range of 3% to 14%, whereas getting more substantial savings requires rather impractically large groups of approximately 10 people or more. Going over to open groups, where users can freely trade their data capacity, we characterize the impact of the secondary market price on the user costs and the operator revenues, and show that Telcos might be better off to embrace secondary markets (eg, let them integrate with billing), and thus have some control on, as opposed to letting them operate unsupervised through tethering. The latter may severely harm the revenues of a Telco, in an uncontrolled manner, especially in densely populated areas.

This paper assesses the potential of ride-sharing for reducing traffic in a city -- based on mobility data extracted from 3G Call Description Records (CDRs), for the cities of Madrid and Barcelona (BCN), and from OSNs, such as Twitter and Foursquare (FSQ), collected for the cities of New York (NY) and Los Angeles (LA). First, we analyze these data sets to understand mobility patterns, home and work locations, and social ties between users. Then, we develop an efficient algorithm for matching users with similar mobility patterns, considering a range of constraints, including social distance. The solution provides an upper bound to the potential decrease in the number of cars in a city that can be achieved by ride-sharing. Our results indicate that this decrease can be as high as 31%, when users are willing to ride with friends of friends.

The effectiveness of service provisioning in large-scale networks is highly dependent on the number and location of service facilities deployed at various hosts. The classical, centralized approach to determining the latter would amount to formulating and solving the uncapacitated k-median (UKM) problem (if the requested number of facilities is fixed- k) or the uncapacitated facility location (UFL) problem (if the number of facilities is also to be optimized). Clearly, such centralized approaches require knowledge of global topological and demand information, and thus do not scale and are not practical for large networks. The key question posed and answered in this paper is the following: “How can we determine in a distributed and scalable manner the number and location of service facilities?” In this paper, we develop a scalable and distributed approach that answers our key question through an iterative reoptimization of the location and the number of facilities within network neighborhoods. We propose an innovative approach to migrate, add, or remove servers within limited-scope network neighborhoods by utilizing only local information about the topology and demand. We show that even with limited information about the network topology and demand, within one or two hops, our distributed approach achieves performance, under various synthetic and real Internet topologies and workloads, that is comparable to that of optimal, centralized approaches requiring full topology and demand information. We also show that it is responsive to volatile demand. Our approach leverages recent advances in virtualization technology toward an automated placement of services on the Internet.

A substantial amount of work has recently gone into localizing BitTorrent traffic within an ISP in order to avoid excessive and often times unnecessary transit costs. Several architectures and systems have been proposed and the initial results from specific ISPs and a few torrents have been encouraging. In this work we attempt to deepen and scale our understanding of locality and its potential. Looking at specific ISPs, we consider tens of thousands of concurrent torrents, and thus capture ISP-wide implications that cannot be appreciated by looking at only a handful of torrents. Second, we go beyond individual case studies and present results for few thousands ISPs represented in our data set of up to 40K torrents involving more than 3.9M concurrent peers and more than 20M in the course of a day spread in 11K ASes. Finally, we develop scalable methodologies that allow us to process this huge data set and derive accurate traffic matrices of torrents. Using the previous methods we obtain the following main findings: i) Although there are a large number of very small ISPs without enough resources for localizing traffic, by analyzing the 100 largest ISPs we show that Locality policies are expected to significantly reduce the transit traffic with respect to the default random overlay construction method in these ISPs; ii) contrary to the popular belief, increasing the access speed of the clients of an ISP does not necessarily help to localize more traffic; iii) by studying several real ISPs, we have shown that soft speed-aware locality policies guarantee win-win situations for ISPs and end users. Furthermore, the maximum transit traffic savings that an ISP can achieve without limiting the number of inter-ISP overlay links is bounded by “unlocalizable” torrents with few local clients. The application of restrictions in the number of inter-ISP links leads to a higher transit traffic reduction but the QoS of clients downloading “unlocalizable” torrents would be severely harmed.

After years of speculation, price discrimination in e-commerce driven by the personal information that users leave (involuntarily) online, has started attracting the attention of privacy researchers, regulators, and the press. In our previous work we demonstrated instances of products whose prices varied online depending on the location and the characteristics of prospective online buyers. In an effort to scale up our study we have turned to crowd-sourcing. Using a browser extension we have collected the prices obtained by an initial set of 340 test users as they surf the web for products of their interest. This initial dataset has permitted us to identify a set of online stores where price variation is more pronounced. We have focused on this subset, and performed a systematic crawl of their products and logged the prices obtained from different vantage points and browser configurations. By analyzing this dataset we see that there exist several retailers that return prices for the same product that vary by 10%-30% whereas there also exist isolated cases that may vary up to a multiplicative factor, e.g., x2. To the best of our efforts we could not attribute the observed price gaps to currency, shipping, or taxation differences.

The co-existence of cellular and wired networks has been exploited almost exclusively in the direction of OffLoading traffic from the former onto the latter. In this paper we claim that there exist cases that call for the exact opposite, i.e, use the cellular network to assist a fixed wired network. In particular, we show that by "OnLoading'' traffic from the wired broadband network onto the cellular network we can usefully speedup wired connections, on the downlink or the uplink. We consider the technological challenges pertaining to this idea and implement a prototype 3G OnLoading service that we call 3GOL, that can be deployed by an operator providing both the wired and cellular network services. By strategically OnLoading a fraction of the data transfers to the 3G network, one can significantly enhance the performance of particular applications. In particular we demonstrate non-trivial performance benefits of 3GOL to two widely used applications: video-on-demand and multimedia upload. We also consider the case when the operator that provides wired and cellular services is different, adding the analysis on economic constraints and volume cap on cellular data plans that need to be respected. Simulating 3GOL}over a DSLAM trace we show that 3GOL can reduce video pre-buffering time by at least 20% for 50% of the users while respecting data caps and we design a simple estimator to compute the daily allowance that can be used towards 3GOL while respecting caps. Our prototype is currently being piloted in 30 households in a large European city by a large network provider.

We present the design and evaluation of ITMgen, a tool for generating synthetic but representative Interdomain Traffic Matrices (ITMs). ITMgen is motivated by the observation that gravity-based models do not reflect application level or regional characteristics of Internet traffic. ITMgen works at the level of connections, taking into account the relative sizes of ASes, their popularity with respect to various applications, and the relation between forward and reverse traffic for different application types. The necessary parameters for integrating application types and the distribution of content popularity can be realistically estimated by combining public sources like Alexa that capture traffic trends at a macro level with local traffic sampling (NetFlow, DPI) for providing an additional enhancement layer at the micro level. Using the above philosophy we demonstrate that we can synthesize ITMs that match real-world measurements closer than the current state of the art. In addition, the modular design philosophy of ITMgen makes it easy to integrate additional enhancement layers that improve the accuracy of our existing implementation.

Fueled by concern over the energy consumption of backbone networks, lot's of work has recently gone into proposals for energy-aware traffic engineering and routing. Local and network-wide policies have been developed for switching off network interfaces and concentrating traffic in as few links as allowed by SLA constraints. In this work we examine empirically the energy saving margins of such policies using extensive data from a national and a pan-European research and academic network. We analyze the dependence of such margins on several parameters, including the level of energy proportionality, QoS constraints and the geographic span of a network. Our findings reveal that with existing devices, smart powering-off can save more than 50% of currently consumed energy, and that energy-aware traffic engineering has still quite away to go before it can be made redundant by improvements in the energy proportionality of devices.

Many emerging scientific and industrial applications require transferring multiple terabytes of data on a daily basis. Examples include pushing scientific data from particle accelerators/colliders to laboratories around the world, synchronizing datacenters across continents, and replicating collections of high-definition videos from events taking place at different time-zones. A key property of all above applications is their ability to tolerate delivery delays ranging from a few hours to a few days. Such delay-tolerant bulk (DTB) data are currently being serviced mostly by the postal system using hard drives and DVDs, or by expensive dedicated networks. In this paper, we propose transmitting such data through commercial ISPs by taking advantage of already-paid-for off-peak bandwidth resulting from diurnal traffic patterns and percentile pricing. We show that between sender-receiver pairs with small time-zone difference, simple source scheduling policies are able to take advantage of most of the existing off-peak capacity. When the time-zone difference increases, taking advantage of the full capacity requires performing store-and-forward through intermediate storage nodes. We present an extensive evaluation of the two options based on traffic data from 200+ links of a large transit provider with points of presence (PoPs) at three continents. Our results indicate that there exists huge potential for performing multiterabyte transfers on a daily basis at little or no additional cost.

Price discrimination, setting the price of a given product for each customer individually according to his valuation for it, can benefit from extensive information collected online on the customers and thus contribute to the profitability of e-commerce services. Another way to discriminate among customers with different willingness to pay is to steer them towards different sets of products when they search within a product category (i.e., search discrimination). Our main contribution in this paper is to empirically demonstrate the existence of signs of both price and search discrimination on the Internet, and to uncover the information vectors used to facilitate them. Supported by our findings, we outline the design of a large-scale, distributed watchdog system that allows users to detect discriminatory practices.

Access link can often be the bottleneck for application performance. In this paper, we propose to augment wired connections using cellular ones, that we term "3G onloading (3GOL)". 3GOL utilizes available mobile devices and already-paid-for data volumes to augment and improve performance of applications on wired network. We motivate 3GOL by understanding bottlenecks present in the wired and the cellular networks. In order to understand the potential benefits of 3GOL, we conduct active experiments using mobile devices. We show that capacity gains can scale linearly with the number of devices on the downlink while also seeing improvements on the uplink. Using real traces we show how video on demand can benefit with 3GOL, even when volume caps are in place. We design 3GOL as an over the top service, and highlight research challenges.

We study the problem of how to share the cost of a backbone network among its customers. A variety of empirical cost-sharing policies are used in practice by backbone network operators but very little ever reaches the research literature about their properties. Motivated by this, we present a systematic study of such policies focusing on the discrepancies between their cost allocations. We aim at quantifying how the selection of a particular policy biases an operator's understanding of cost generation. We identify F-discrepancies due to the specific function used to map traffic into cost (e.g., volume vs. peak rate vs. 95-percentile) and M-discrepancies, which have to do with where traffic is metered (per device vs. ingress metering). We also identify L-discrepancies relating to the liability of individual customers for triggered upgrades and consequent costs (full vs. proportional), and finally, TCO-discrepancies emanating from the fact that the cost of carrying a bit is not uniform across the network (old vs. new equipment, high vs. low energy or real estate costs, etc.). Using extensive traffic, routing, and cost data from a tier-1 network we show that F-discrepancies are large when looking at individual links but cancel out when considering network-wide cost-sharing. Metering at ingress points is convenient but leads to large M-discrepancies, while TCO-discrepancies are huge. Finally, L-discrepancies are intriguing and esoteric but understanding them is central to determining the cost a customer inflicts on the network.

Distributing long-tail content is an inherently difficult task due to the low amortization of bandwidth transfer costs as such content has limited number of views. Two recent trends are making this problem harder. First, the increasing popularity of user-generated content (UGC) and online social networks (OSNs) create and reinforce such popularity distributions. Second, the recent trend of geo-replicating content across multiple PoPs spread around the world, done for improving quality of experience (QoE) for users and for redundancy reasons, can lead to unnecessary bandwidth costs. We build TailGate, a system that exploits social relationships, regularities in read access patterns, and time-zone differences to efficiently and selectively distribute long-tail content across PoPs. We evaluate TailGate using large traces from an OSN and show that it can decrease WAN bandwidth costs by as much as 80% as well as reduce latency, improving QoE. We deploy TailGate on PlanetLab and show that even in the case when imprecise social information is available, TailGate can still decrease the latency for accessing long-tail YouTube videos by a factor of 2.

The difficulty of partitioning social graphs has introduced new system design challenges for scaling of online social networks (OSNs). Vertical scaling by resorting to full replication can be a costly proposition. Scaling horizontally by partitioning and distributing data among multiple servers using, for e.g., distributed hash tables (DHTs), can suffer from expensive interserver communication. Such challenges have often caused costly rearchitecting efforts for popular OSNs like Twitter and Facebook. We design, implement, and evaluate SPAR, a Social Partitioning and Replication middleware that mediates transparently between the application and the database layer of an OSN. SPAR leverages the underlying social graph structure in order to minimize the required replication overhead for ensuring that users have their neighbors' data colocated in the same machine. The gains from this are multifold: Application developers can assume local semantics, i.e., develop as they would for a single machine; scalability is achieved by adding commodity machines with low memory and network I/O requirements; and N+K redundancy is achieved at a fraction of the cost. We provide a complete system design, extensive evaluation based on datasets from Twitter, Orkut, and Facebook, and a working implementation. We show that SPAR incurs minimum overhead, can help a well-known Twitter clone reach Twitter's scale without changing a line of its application logic, and achieves higher throughput than Cassandra, a popular key-value store database.

A substantial amount of work has recently gone into localizing BitTorrent traffic within an ISP in order to avoid excessive and often times unnecessary transit costs. Several architectures and systems have been proposed and the initial results from specific ISPs and a few torrents have been encouraging. In this work we attempt to deepen and scale our understanding of locality and its potential. Looking at specific ISPs, we consider tens of thousands of concurrent torrents, and thus capture ISP-wide implications that cannot be appreciated by looking at only a handful of torrents. Secondly, we go beyond individual case studies and present results for the top 100 ISPs in terms of number of users represented in our dataset of up to 40K torrents involving more than 3.9M concurrent peers and more than 20M in the course of a day spread in 11K ASes. We develop scalable methodologies that allow us to process this huge dataset and get concrete quantitative answers rather than qualitative speculations to questions like: “what is the minimum and the maximum transit traffic reduction across hundreds of ISPs?”, “what are the win-win boundaries for ISPs and their users?”, “what is the maximum amount of transit traffic that can be localized without requiring fine-grained control of inter-AS overlay connections?”.

Large datacenter operators with sites at multiple locations dimension their key resources according to the peak demand of the geographic area that each site covers. The demand of specific areas follows strong diurnal patterns with high peak to valley ratios that result in poor average utilization across a day. In this paper, we show how to rescue unutilized bandwidth across multiple datacenters and backbone networks and use it for non-real-time applications, such as backups, propagation of bulky updates, and migration of data. Achieving the above is non-trivial since leftover bandwidth appears at different times, for different durations, and at different places in the world.

Access networks include modems, home gateways, and DSL Access Multiplexers (DSLAMs), and are responsible for 70-80% of total network-based energy consumption. In this paper, we take an in-depth look at the problem of greening access networks, identify root problems, and propose practical solutions for their user- and ISP-parts. On the user side, the combination of continuous light traffic and lack of alternative paths condemns gateways to being powered most of the time despite having Sleep-on-Idle (SoI) capabilities. To address this, we introduce Broadband Hitch-Hiking (BH2), that takes advantage of the overlap of wireless networks to aggregate user traffic in as few gateways as possible. In current urban settings BH2 can power off 65-90% of gateways. Powering off gateways permits the remaining ones to synchronize at higher speeds due to reduced crosstalk from having fewer active lines. Our tests reveal speedup up to 25%. On the ISP side, we propose introducing simple inexpensive switches at the distribution frame for batching active lines to a subset of cards letting the remaining ones sleep. Overall, our results show an 80% energy savings margin in access networks. The combination of B2 and switching gets close to this margin, saving 66% on average.

A foundational issue underlying many overlay network applications ranging from routing to peer-to-peer file sharing is that of the network formation, i.e., folding new arrivals into an existing overlay, and rewiring to cope with changing network conditions. Previous work has considered the problem from two perspectives: devising practical heuristics for the case of cooperative peers and performing game-theoretic analysis for the case of selfish peers. In this paper, we unify the aforementioned thrusts by defining and studying the selfish neighbor selection (SNS) game and its application to overlay routing. At the heart of SNS stands the restriction that peers are allowed up to a certain number of neighbors. This makes SNS substantially different from existing network formation games that impose no bounds on peer degrees. Having bounded degrees has important practical consequences as it permits the creation of overlay structures that requireO(n) instead ofO(n2) link monitoring overhead. We show that a node's “best response” wiring strategy amounts to solving ak-median problem on asymmetric distance. Best-response wirings have substantial practical utility as they permit selfish nodes to reap substantial performance benefits when connecting to overlays of nonselfish nodes. A more intricate consequence is that even nonselfish nodes can benefit from the existence of some selfish nodes since the latter, via their local optimizations, create a highly optimized backbone, upon which even simple heuristic wirings yield good performance. To capitalize on the above properties, we design, build, and deploy EGOIST, an SNS-inspired prototype overlay routing system for PlanetLab. We demonstrate that EGOIST outperforms existing heuristic overlays on a variety of performance metrics, including delay, available bandwidth, and node utilization, while it remains competitive with an optimal but unscalable full-mesh overlay.

The Internet is witnessing explosive growth in traffic due to bulk content transfers, such as multimedia and software downloads, and online sharing of personal, commercial, and scientific data. Yet bulk data transfers remain very expensive and inefficient. As a result, huge amounts of digital data continue to be delivered outside of the Internet using hard drives, optical media or tapes. Meanwhile, large reserves of spare bandwidth lie unutilized in today's networks, where links are overprovisioned for peak load. We designed NetEx, a bulk transfer system that opportunistically exploits the excess capacities of network links to deliver bulk content cheaply and efficiently. Our results based on data from both a commercial tier-1 ISP and the Abilene network suggest that NetEx can considerably increase the capacity of the network, and at the same time it can provide good average performance to bulk transfers.

Scheduling of delay-tolerant jobs has been proposed as a mechanism to alleviate pressure on congested network resources. However, when multiple competing users share these resources, they may not be willing to reveal how flexible is the schedule for their jobs. This work presents a trading system that enables the users to trade their finite allowances in an scenario where they have fixed-size atomic jobs. The trading system makes it possible that tasks with strict timing requirements are completed on time, and flexibility is rewarded with either a larger share of the off-peak capacity or a lower total cost for their owners. The trading system is proven to always converge. Simulation on real traces show significant reductions on the peak-to-valley ratio on the link utilization.

In recent years there has been renewed interest in the problem of transferring bulk data (terabytes) utilizing commercial ISPs. The need to transfer bulk data arises in various scientific and industrial applications. Today, this data is moved using postal service in conjunction with hard drives and DVDs or special high performance dedicated networks. The key insight underlying the recent work was that many of the applications are delay- tolerant and hence the bulk data can be transferred at minimal cost, utilizing already paid-for off-peak bandwidth resulting from diurnal traffic patterns, using store-and-forward through intermediate storage nodes. In this paper we expand on this theme and consider the computational complexity of transferring data over a network whose links have time-varying capacities. We show that the general problem of finding a cost-optimal transfer of the bulk data can be solved in polynomial-time using minimum cost flow algorithms on a time-expanded version of the underlying network. Our solution involves graph transformations. We present additional transformations that enable the handling of half-duplex links (e.g. fiber-optic links) as well as node processing constraints (e.g. limitations on the processing power available for filtering or archiving). An important characteristic of our solution is the ability to handle nodes with storage. We consider nodes with storage that varies over time in terms of both capacity and cost. We show that our approach provably extends to cover the case of linear costs, providing polynomial- time algorithms. However, the flat-fee storage model is NP- complete and hence unlikely to be tractable in polynomial-time. Interestingly, with constrained storage, the optimal solutions may involve loops, i.e. the data may pass through the same node more than once on its way from the destination to the source along the optimal route. We use data from one of the world's leading ISPs and perform a comprehensive evaluation of our algorithm. We show that there exists a huge potential for cost savings in real-world networks with time-varying costs for both link capacities and node storage.

Cost control for the Internet access providers (AP) influences not only the nominal speeds offered to the customers, but also other, more controversial, policies related to traffic shaping and discrimination. Given that the cost for the AP is determined by the peak-hour traffic (e.g. through the 95th-percentile), the individual user contribution towards the aggregate cost is not a linear function of its byte usage. In this paper we propose a metric for evaluating the contribution each individual user has on the peak demand, that is based on Shapley value, a well known game-theoretic concept. Given the computational complexity of calculating the Shapley value, we use a Monte Carlo method for approximating it with reasonable accuracy. We employ our methodology to study a dataset that logs per-subscriber temporal usage patterns over one month period for 10K broadband subscribers of a European AP and report observed results.

The difficulty of scaling Online Social Networks (OSNs) has introduced new system design challenges that has often caused costly re-architecting for services like Twitter and Facebook. The complexity of interconnection of users in social networks has introduced new scalability challenges. Conventional vertical scaling by resorting to full replication can be a costly proposition. Horizontal scaling by partitioning and distributing data among multiples servers - e.g. using DHTs - can lead to costly inter-server communication.

A substantial amount of work has recently gone into localizing BitTorrent traffic within an ISP in order to avoid excessive and often times unnecessary transit costs. In this work we aim to answer yet unanswered questions such as: what is the minimum and the maximum transit traffic reduction across hundreds of ISPs?, what are the win-win boundaries for ISPs and their users?, what is the maximum amount of transit traffic that can be localized without requiring fine-grained control of inter-AS overlay connections?, what is the impact to transit traffic from upgrades of residential broadband speeds?.

In an n-way broadcast application, each one of n overlay nodes wants to push its own distinct large data file to all other n-1 destinations as well as download their respective data files. BitTorrent-like swarming protocols are ideal choices for handling such massive data volume transfers. The original BitTorrent targets one-to-many broadcasts of a single file to a very large number of receivers, and thus, by necessity, employs a suboptimized overlay topology. n-way broadcast applications, on the other hand, owing to their inherent complexity, are realizable only in small to medium scale networks. In this paper, we show that we can leverage this scale constraint to construct optimized overlay topologies that take into consideration the end-to-end characteristics of the network and as a consequence deliver far superior performance compared to random and myopic (greedy) approaches. We present the Max-Min and Max-Sum peer-selection policies used by individual nodes to select their neighbors. The first one strives to maximize the available bandwidth to the slowest destination, while the second maximizes the aggregate output rate. We design a swarming protocol suitable for n-way broadcast and operate it on top of overlay graphs formed by nodes that employ Max-Min or Max-Sum policies. Using measurements from a PlanetLab prototype implementation and trace-driven simulations, we demonstrate that the performance of swarming protocols on top of our constructed topologies is far superior to the performance of random and myopic overlays.

Motivated by increased concern over energy consumption in moderndatacenters,wepropose anew,distributedcomputingplatform calledNanoDataCenters(NaDa). NaDausesISP-controlledhome gateways to provide computing and storage services and adopts a managed peer-to-peer model to form a distributed data center infrastructure. To evaluate the potential for energy savings in NaDa platform we pick Video-on-Demand (VoD) services. We develop an energy consumption model for VoD in traditional and in NaDa data centers and evaluate this model using a large set of empirical VoD access data. We find that even under the most pessimistic scenarios, NaDa saves at least 20 % to 30 % of the energy compared to traditional data centers. These savings stem from energypreserving properties inherent to NaDa such as the reuse of already committed baseline power on underutilized gateways, the avoidance of cooling costs, and the reduction of network energy consumption as a result of demand and service co-localization in NaDa. Categories andSubject Descriptors

Motivated by emerging cooperative P2P applications we study new uplink allocation algorithms for substituting the rate-based choke/unchoke algorithm of BitTorrent which was developed for non-cooperative environments. Our goal is to shorten the download times by improving the uplink utilization of nodes. We develop a new family of uplink allocation algorithms which we call BitMax, to stress the fact that they allocate to each unchoked node the maximum rate it can sustain, instead of an 1/(k + 1) equal share as done in the existing BitTorrent. BitMax computes in each interval the number of nodes to be unchoked, and the corresponding allocations, and thus does not require any empirically preset parameters like k. We demonstrate experimentally that Bit-Max can reduce significantly the download times in a typical reference scenario involving mostly ADSL nodes. We also consider scenarios involving network bottlenecks caused by filtering of P2P traffic at ISP peering points and show that BitMax retains its gains also in these cases.

A foundational issue underlying many overlay network applications ranging from routing to peer-to-peer file sharing is that of connectivity management, i.e., folding new arrivals into an existing overlay, and re-wiring to cope with changing network conditions. Previous work has considered the problem from two perspectives: devising practical heuristics for specific applications designed to work well in real deployments, and providing abstractions for the underlying problem that are analytically tractable, especially via game-theoretic analysis. In this paper, we unify these two thrusts by using insights gleaned from novel, realistic theoretic models in the design of EGOIST -- a distributed overlay routing system that we implemented, deployed, and evaluated on PlanetLab. Using extensive measurements of paths between nodes, we demonstrate that EGOIST'S neighbor selection primitives significantly outperform existing heuristics on a variety of performance metrics, including delay, available bandwidth, and node utilization. Moreover, we demonstrate that EGOIST is competitive with an optimal, but unscalable full-mesh approach, remains highly effective under significant churn, is robust to cheating, and incurs minimal overhead. Finally, we use a multiplayer peer-to-peer game to demonstrate the value of EGOIST to end-user applications.

In an n-way broadcast application each one of n overlay nodes wants to push its own distinct large data file to all other n-1 destinations as well as download their respective data files. BitTorrent-like swarming protocols are ideal choices for handling such massive data volume transfers. The original BitTorrent targets one-to-many broadcasts of a single file to a very large number of receivers and thus, by necessity, employs an almost random overlay topology, n-way broadcast applications on the other hand, owing to their inherent n-squared nature, are realizable only in small to medium scale networks. In this paper, we show that we can leverage this scale constraint to construct optimized overlay topologies that take into consideration the end-to-end characteristics of the network and as a consequence deliver far superior performance compared to random and myopic (local) approaches. We present the Max-Min and Max- Sum peer-selection policies used by individual nodes to select their neighbors. The first one strives to maximize the available bandwidth to the slowest destination, while the second maximizes the aggregate output rate. We design a swarming protocol suitable for n-way broadcast and operate it on top of overlay graphs formed by nodes that employ Max-Min or Max-Sum policies. Using trace-driven simulation and measurements from a PlanetLab prototype implementation, we demonstrate that the performance of swarming on top of our constructed topologies is far superior to the performance of random and myopic overlays. Moreover, we show how to modify our swarming protocol to allow it to accommodate selfish nodes.

Motivated by applications in social networks, peer-to-peer and overlay networks, we define and study the Bounded Budget Connection (BBC) game- we have a collection of n players or nodes each of whom has a budget for purchasing links; each link has a cost as well as a length and each node has a set of preference weights for each of the remaining nodes; the objective of each node is to use its budget to buy a set of outgoing links so as to minimize its sum of preference-weighted distances to the remaining nodes. We study the structural and complexity-theoretic properties of pure Nash equilibria in BBC games. We show that determining the existence of a pure Nash equilibrium in general BBC games is NP-hard. We counterbalance this result by considering a natural variant, fractional BBC games- where it is permitted to buy fractions of links- and show that a pure Nash equilibrium always exists in such games. A major focus is the study of (n, k)-uniform BBC games- those in which all link costs, link lengths and preference weights are equal (to 1) and all budgets are equal (to k). We show that a pure Nash equilibrium or stable graph exists for all (n, k)-uniform BBC games and that all stable graphs are essentially fair (i.e. all nodes have similar costs). We provide an explicit construction of a family of stable graphs that spans the spectrum from minimum total social cost to maximum total social cost. To be precise we show that that the price of stability is Θ(1) and the price of anarchy is Ω( n/k) and O( logk n

In a typical overlay network for routing or content sharing, each node must select a fixed number of immediate overlay neighbors for routing traffic or content queries. A selfish node entering such a network would select neighbors so as to minimize the weighted sum of expected access costs to all its destinations. Previous work on selfish neighbor selection has built intuition with simple models where edges are undirected, access costs are modeled by hop-counts, and nodes have potentially unbounded degrees. However, in practice, important constraints not captured by these models lead to richer games with substantively and fundamentally different outcomes. Our work models neighbor selection as a game involving directed links, constraints on the number of allowed neighbors, and costs reflecting both network latency and node preference. We express a node's "best response" wiring strategy as a k-median problem on asymmetric distance, and use this formulation to obtain pure Nash equilibria. We experimentally examine the properties of such stable wirings on synthetic topologies, as well as on real topologies and maps constructed from PlanetLab and AS-level Internet measurements. Our results indicate that selfish nodes can reap substantial performance benefits when connecting to overlay networks constructed by naive nodes. On the other hand, in overlays that are dominated by selfish nodes, the resulting stable wirings are optimized to such great extent that even uninformed newcomers can extract near-optimal performance through naive wiring strategies.

The effectiveness of service provisioning in large-scale networks is highly dependent on the number and location of service facilities deployed at various hosts. The classical, centralized approach to determining the latter would amount to formulating and solving theuncapacitated k-median(UKM) problem (if the requested number of facilities is fixed), or theuncapacitated facility location(UFL) problem (if the number of facilities is also to be optimized). Clearly, such centralized approaches require knowledge of global topological and demand information, and thus do not scale and are not practical for large networks. The key question posed and answered in this paper is the following: "How can we determine in a distributed and scalable manner thenumberandlocationof service facilities?" We propose an innovative approach in which topology and demand information is limited to neighborhoods, or balls of small radius around selected facilities, whereas demand information is captured implicitly for the remaining (remote) clients outside these neighborhoods, by mapping them to clients on the edge of the neighborhood; the ball radius regulates the trade-off between scalability and performance. We develop a scalable, distributed approach that answers our key question through an iterative re-optimization of the location and the number of facilities within such balls. We show that even for small values of the radius (1 or 2), our distributed approach achieves performance under various synthetic and real Internet topologies that is comparable to that of optimal, centralized approaches requiring full topology and demand information.

In many networked applications, independent caching agents cooperate by servicing each other's miss streams, without revealing the operational details of the caching mechanisms they employ. Inference of such details could be instrumental for many other processes. For example, it could be used for optimized forwarding (or routing) of one's own miss stream (or content) to available proxy caches, or for making cache-aware resource management decisions. In this paper, we introduce the cache inference problem (CIP) as that of inferring the characteristics of a caching agent, given the miss stream of that agent. While CIP is insolvable in its most general form, there are special cases of practical importance in which it is, including when the request stream follows an independent reference model (IRM) with generalized power-law (GPL) demand distribution. To that end, we design two basic "litmus" tests that are able to detect the LFU and LRU replacement policies, the effective size of the cache and of the object universe, and the skewness of the GPL demand for objects. Using extensive experiments under synthetic as well as real traces, we show that our methods infer such characteristics accurately and quite efficiently, and that they remain robust even when the IRM/GPL assumptions do not hold, and even when the underlying replacement policies are not "pure" LFU or LRU. We demonstrate the value of our inference framework by considering example applications.

Although cooperation generally increases the amount of resources available to a community of nodes, thus improving individual and collective performance, it also allows for the appearance of potential mistreatment problems through the exposition of one node's resources to others. We study such concerns by considering a group of independent, rational, self-aware nodes that cooperate using online caching algorithms, where the exposed resource is the storage at each node. Motivated by content networking applications - including Web caching, content delivery networks (CDNs), and peer-to-peer (P2P) - this paper extends our previous work on the offline version of the problem, which was conducted under a game-theoretic framework and limited to object replication. We identify and investigate two causes of mistreatment: 1) cache state interactions (due to the cooperative servicing of requests) and 2) the adoption of a common scheme for cache management policies. Using analytic models, numerical solutions of these models, and simulation experiments, we show that online cooperation schemes using caching are fairly robust to mistreatment caused by state interactions. To appear in a substantial manner, the interaction through the exchange of miss streams has to be very intense, making it feasible for the mistreated nodes to detect and react to exploitation. This robustness ceases to exist when nodes fetch and store objects in response to remote requests, that is, when they operate as level-2 caches (or proxies) for other nodes. Regarding mistreatment due to a common scheme, we show that this can easily take place when the "outlier" characteristics of some of the nodes get overlooked. This finding underscores the importance of allowing cooperative caching nodes the flexibility of choosing from a diverse set of schemes to fit the peculiarities of individual nodes. To that end, we outline an emulation-based framework for the development of mistreatment-resilient distributed selfish caching schemes.

In this paper we examine the impact of the adopted playout policy on the overall performance of a P2P streaming system. It is argued and showed that adopting (popular) playout policies that result in a divergence of the playout points drastically deteriorates the performance of P2P streaming and that policies that keep these points near-in-time should be adopted.

Today's nanometer technology trends have a very negative impact on the reliability of semiconductor products. Intermittent faults constitute the largest part of reliability failures that are manifested in the field during the semiconductor product operation. Since software-based self-test (SBST) has been proposed as an effective strategy for on-line testing of processors integrated in non-safety critical low-cost embedded system applications, optimal test period specification is becoming increasingly challenging. In this paper we first introduce a reliability analysis for optimal periodic testing of intermittent faults that minimizes the test cost incurred based on a two-state Markov model for the probabilistic modeling of intermittent faults. Then, we present for the first time an enhanced SBST strategy for on-line testing of complex pipelined embedded processors. Finally, we demonstrate the effectiveness of the proposed optimal periodic SBST strategy by applying it to a fully-pipelined RISC embedded processor and providing experimental results

Abstract — Although cooperation generally increases the amount of resources available to a community of nodes, thus improving individual and collective performance, it also allows for the appearance of potential mistreatment problems through the exposition of one node’s resources to others. We study such concerns by considering a group of independent, rational, self-aware nodes that cooperate using on-line caching algorithms, where the exposed resource is the storage of each node. Motivated by content networking applications – including web caching, CDNs, and P2P – this paper extends our previous work on the off-line version of the problem, which was limited to object replication and was conducted under a game-theoretic framework. We identify and investigate two causes of mistreatment: (1) cache state interactions (due to the cooperative servicing of requests) and (2) the adoption of a common scheme for cache replacement/redirection/admission policies. Using analytic models, numerical solutions of these models, as well as simulation experiments, we show that online cooperation schemes using caching are fairly robust to mistreatment caused by state interactions. When this becomes possible, the interaction through the exchange of miss-streams has to be very intense, making it feasible for the mistreated nodes to detect and react to the exploitation. This robustness ceases to exist when nodes fetch and store objects in response to remote requests, i.e., when they operate as Level-2 caches (or proxies) for other nodes. Regarding mistreatment due to a common scheme, we show that this can easily take place when the “outlier ” characteristics of some of the nodes get overlooked. This finding underscores the importance of allowing cooperative caching nodes the flexibility of choosing from a diverse set of schemes to fit the peculiarities of individual nodes. To that end, we outline an emulation-based framework for the development of mistreatment-resilient distributed selfish caching schemes.

A commonly employed abstraction for studying the object placement problem for the purpose of Internet content distribution is that of a distributed replication group. In this work, the initial model of the distributed replication group of Leff et al. [CHECK END OF SENTENCE] is extended to the case that individual nodes act selfishly, i.e., cater to the optimization of their individual local utilities. Our main contribution is the derivation of equilibrium object placement strategies that 1) can guarantee improved local utilities for all nodes concurrently as compared to the corresponding local utilities under greedy local object placement, 2) do not suffer from potential mistreatment problems, inherent to centralized strategies that aim at optimizing the social utility, and 3) do not require the existence of complete information at all nodes. We develop a baseline computationally efficient algorithm for obtaining the aforementioned equilibrium strategies and then extend it to improve its performance with respect to fairness. Both algorithms are realizable, in practice, through a distributed protocol that requires only a limited exchange of information.

Large scale hierarchical caches for Web content have been deployed widely in an attempt to reduce delivery delays and bandwidth consumption and also to improve the scalability of content dissemination through the World Wide Web. Irrespective of the specific replacement algorithm employed in each cache, a de facto characteristic of contemporary hierarchical caches is that a hit for a document at an l-level cache leads to the caching of the document in all intermediate caches (levels l-1,..., 1) on the path towards the leaf cache that received the initial request. This paper presents various algorithms that revises this standard behavior and attempts to be more selective in choosing the caches that gets to store a local copy of the requested document. As these algorithms operate independently of the actual replacement algorithm running in each individual cache, they are referred to as meta algorithms. Three new meta algorithms are proposed and compared against the de facto one and a recently proposed one by means of synthetic and trace-driven simulations. The best of the new meta algorithms appears to be leading to improved performance under most simulated scenarios, especially under a low availability of storage. The latter observation makes the presented meta algorithms particularly favorable for the handling of large data objects such as stored music files or short video clips. Additionally, a simple load balancing algorithm that is based on the concept of meta algorithms is proposed and evaluated. The algorithm is shown to be able to provide for an effective balancing of load thus possibly addressing the recently discovered "filtering-effect" in hierarchical Web caches.

Due to random delay variations in current best effort networks, packet video applications rely on end-system buffering and playout adaptation to reduce the effects of disruptions on the required smooth stream presentation. To study the effect of buffering and playout adaptation, we present an analytical model based on the M/G/1 queueing system with finite buffer capacity, and traffic intensity equal to or greater than unity. This model fits well a range of new applications that have limited buffer resources for the reception of incoming frames. We introduce the variance of distortion of playout (VDoP), a new metric that accounts for the overall presentation disruption caused by buffer underflows, intentionally introduced gaps during slowdown periods and data loss from overflows. VDoP is an elegant and fair metric for the estimation of playout quality and will hopefully assist the development of better adaptation algorithms. Furthermore, the effect of finite buffer capacity is examined in relation to stream continuity revealing a system behavior not previously accounted for. The sensitivity of the system to the variance of the arrival process is also examined by means of simulation. Finally, an online algorithm is presented for the exploitation of our study on implemented systems.