Accurate measurement of mobile network performance is crucial for optimizing user experience and ensuring regulatory compliance. Traditional methods like crowdsourcing approaches, though effective, depend heavily on user participation and extensive infrastructure. In this paper, we introduce adNPM, a novel technique for measuring download speed by embedded measurement code in ads displayed across web browsers and mobile apps, without requiring user participation. Through controlled lab tests and real-world deployments in 15 countries, we demonstrate that adNPM achieves accuracy comparable to well-established tools like Speedtest by Ookla and Opensignal while significantly reducing data consumption.

As increasingly complex and dynamic volumetric DDoS attacks continue to wreak havoc on edge networks, two recent developments promise to bolster DDoS defense at the edge. First, programmable switches have emerged as promising means for achieving scalable and cost-effective attack signature detection. However, their practical application in edge networks remains a challenging open problem. Second, machine learning (ML)-based solutions have demonstrated potential in accurately detecting attack signatures based on per-flow traffic features. Yet, their inability to effectively scale to the traffic volumes and number of flows in actual production edge networks has largely excluded them from practical considerations.In this paper, we introduce ZAPDOS, a novel approach to accurately, quickly, and scalably detect volumetric DDoS attack signatures at the source prefix level. ZAPDOS is the first to utilize a key characteristic of the observed structure of measured attack and benign source prefixes (i.e., a pronounced cluster-within-cluster property) and effectively apply it in practice against modern attacks. ZAPDOS operates by monitoring aggregate prefix-level features in switch hardware, employing a learning model to identify prefixes suspected of containing attack sources, and using several innovative algorithmic methods to pinpoint attack sources efficiently. We have built a hardware prototype of ZAPDOS and a packet-level software simulator which achieve comparable accuracy results. Since existing datasets are inadequate for training and evaluating prefix-level models, we have developed a new data-fusion methodology for training and evaluating ZAPDOS. We use our prototype and simulator to show that ZAPDOS can detect volumetric DDoS attack signatures with orders of magnitude lower error rates than state-of-the-art under comparable monitoring resource budgets and for a range of different attack scenarios.

Network telemetry systems provide critical visibility into the state of network traffic. By leveraging modern programmable switch hardware, significant progress has been made to scale these systems to production network traffic workloads. Less attention has been paid towards efficiently utilizing these hardware targets’ limited resources in the face of dynamics such as the composition of the traffic workload as well as the number and types of queries running at any given point in time. However, both of these dynamics have implications on resource requirements and query accuracy. Building on our prior work DynATOS, which argues that this dynamics problem motivates reframing telemetry systems as resource schedulers, we present in this paper the design, implementation, and evaluation of DynATOS+. DynATOS+ relies on the same efficient time-division approximation and scheduling algorithm that DynATOS uses and that allows for user-defined query accuracy and latency specifications that are intended to result in tradeoffs with respect to query execution to reduce hardware resource usage. However, unlike DynATOS, DynATOS+ significantly reduces the burden on end users to express their queries by allowing them to use simple-to-state accuracy goals. For example, the method for specifying per-query accuracy goals in DynATOS+ no longer requires end users to either know the average range of query results in advance or to submit multiple trial queries to tune their accuracy goal specifications. We perform extensive simulation-based evaluations that (i) show that this new functionality of DynATOS+ works in practice, (ii) illustrate in detail the tradeoffs that result with respect to query execution and hardware resource usage for a wide range of systems parameters, and (iii) allow for an assessment of system performance under changing query workloads on top of changes in the composition of traffic workloads that has eluded previous work in this area.

Modern enterprises are increasingly adopting multicloud strategies (i.e. connecting islands of resources from disparate public cloud providers, or CPs for short) due to benefits such as competitive pricing, global expansion, or improved reliability. While these benefits are compelling in their own right, what is critically lacking is a framework for establishing optimized multi-cloud overlays atop individual CP backbones in a performance- and cost-aware manner. A key challenge is that we have little understanding of the performance characteristics of CPs' private backbones in light of multi-cloud overlays. To address this challenge, we present a third-party, cloud-centric study to understand and examine the path, delay, and traffic-cost characteristics of CP backbones by deploying VMs in three global-scale CPs (i.e. AWS, Azure, and GCP). Our measurements reveal new insights including the “optimal backbone of cloud backbones” and a lack of path and delay asymmetries in it. Next, we report on several instances where performance-awareness of multi-cloud paths offer better latency reductions than default paths provided by CPs. While these results make a strong case for performance-aware multi-cloud overlays, the problem is further complicated by the varying transit costs/pricing models of CPs across different geographic regions. Based on our findings, we propose a research agenda for creating performance- and cost-aware multi-cloud overlays that deals with issues such as egress costs, considering IXPs as relays, using cloud auctions for transit cost pricing, and improving the performance of cloud-native applications.

The growing demand for an ever-increasing number of cloud services is profoundly transforming the Internet's interconnection or peering ecosystem, and one example is the emergence of "virtual private interconnections (VPIs)". However, due to the underlying technologies, these VPIs are not publicly visible and traffic traversing them remains largely hidden as it bypasses the public Internet. In particular, existing techniques for inferring Internet interconnections are unable to detect these VPIs and are also incapable of mapping them to the physical facility or geographic region where they are established.

Internet interconnections are the means by which networks exchange traffic between one another. These interconnections are typically established in facilities that have known geographic locations, and are owned and operated by so-called colocation and interconnection services providers (e.g., Equinix, CoreSite, and EdgeConneX). These previously under-studied colocation facilities and the critical role they play in solving the notoriously difficult problem of obtaining a comprehensive view of the structure and evolution of the interconnections in today's Internet are the focus of this paper. We present mi2, a new approach for mapping Internet interconnections inside a given colocation facility.1We infer the existence of interconnections from localized traceroutes and use the Belief Propagation algorithm on a specially defined Markov Random Field graphical model to geolocate them to a target colocation facility. We evaluate mi2by applying it initially to a small set of US-based colocation facilities. In the process, we compare our results against those obtained by two recently developed related techniques and discuss observed discrepancies that derive from how the different techniques determine the ownership of border routers. As part of our validation approach, we also identify drastic changes in today's Internet interconnection ecosystem (e.g., new infrastructures in the form of “cloud exchanges” that offer new types of interconnections called “virtual private interconnections”), and discuss their wide-ranging implications for obtaining an accurate and comprehensive map of the Internet's interconnection fabric.

During the past few years, sellers have increasingly offered discounted or free products to selected reviewers of e-commerce platforms in exchange for their reviews. Such incentivized (and often very positive) reviews can improve the rating of a product which in turn sways other users' opinions about the product. Despite their importance, the prevalence, characteristics, and the influence of incentivized reviews in a major e-commerce platform have not been systematically and quantitatively studied. This paper examines the problem of detecting and characterizing incentivized reviews in two primary categories of Amazon products. We describe a new method to identify Explicitly Incentivized Reviews (EIRs) and then collect a few datasets to capture an extensive collection of EIRs along with their associated products and reviewers. We show that the key features of EIRs and normal reviews exhibit different characteristics. Furthermore, we illustrate how the prevalence of EIRs has evolved and been affected by Amazon's ban. Our examination of the temporal pattern of submitted reviews for sample products reveals promotional campaigns by the corresponding sellers and their effectiveness in attracting other users. Finally, we demonstrate that a classifier that is trained by EIRs (without explicit keywords) and normal reviews can accurately detect other EIRs as well as implicitly incentivized reviews. Overall, this analysis sheds an insightful light on the impact of EIRs on Amazon products and users.

The most-followed Twitter users and their pairwise relationships form a sub-graph of all Twitter users that we call the Twitter elite network. The connectivity patterns and influence (in terms of reply and retweet activity) among these elite users illustrate how the “important” users connect and interact with one another on Twitter. Such an elite-focused view also provides valuable information about the structure of the Twitter network as a whole. This paper presents the first detailed characterization of the top-10K Twitter elite network. We describe a new technique to efficiently and accurately capture the Twitter elite network along with social attributes of individual elite accounts. We show that a sufficiently large elite network is typically composed of 15-20 resilient and socially cohesive communities representing “socially meaningful” components of the elite network. We then characterize the community-level structure of the elite network in terms of bias in directed pairwise connectivity and relative reachability. We demonstrate that both the retweet and reply activity between elite users are effectively contained within individual elite communities. Finally, we illustrate that a majority of the elite friends of regular Twitter users tend to belong to a single elite community. This finding offers a promising criterion to group regular users into “shadow partitions” based on their association with elite communities. We show that the level of overall inter-connectivity between shadow partitions mirrors the inter-connectivity of the elite communities. This suggests that these shadow partitions can be viewed as extensions of their corresponding elite communities.

We consider the practical problem of video surveillance in public transport systems, where security videos are stored onboard, and a central operator occasionally needs to access portions of the recordings. When this happens, the selected video must be uploaded within a deadline, possibly using multiple parallel wireless interfaces. Interfaces have different associated costs, related to tariffs charged by Mobile Network Operators (MNOs), energy consumption, data quotas, system load. Our goal is to choose which interfaces to use, and when, so as to minimize the cost of the upload while meeting the deadline, despite the unknown short-term variations in throughput. To achieve this goal, we first collect real traces of mobile uploads from vehicles for different MNOs. Examination of these traces confirms the unpredictability of the short-term throughput of wireless connections, and motivates the adoption of adaptive schedulers with limited a-priori knowledge of the system status. To effectively solve our problem, we devised a family of adaptive algorithms, that we thoroughly evaluated using a trace-driven approach. Results show that our adaptive approach can effectively leverage the fundamental tradeoff between the total cost and the delivery time of content upload, despite unknown short-term variations in throughput.

In the era when Facebook and Twitter dominate the market for social media, Google has introduced Google+ (G+) and reported a significant growth in its size while others called it a ghost town. This begs the question of whether G+ can really attract a significant number of connected and active users despite the dominance of Facebook and Twitter. This paper presents a detailed longitudinal characterization of G+ based on large-scale measurements. We identify the main components of G+ structure and characterize the key feature of their users and their evolution over time. We then conduct detailed analysis on the evolution of connectivity and activity among users in the largest connected component (LCC) of G+ structure, and compare their characteristics to other major online social networks (OSNs). We show that despite the dramatic growth in the size of G+, the relative size of the LCC has been decreasing and its connectivity has become less clustered. While the aggregate user activity has gradually increased, only a very small fraction of users exhibit any type of activity, and an even smaller fraction of these users attracts any reaction. The identity of users with most followers and reactions reveal that most of them are related to high-tech industry. To our knowledge, this study offers the most comprehensive characterization of G+ based on the largest collected datasets.

Swarm-based peer-to-peer streaming (SPS) mechanisms tend to generate a significant amount of costly inter-ISP traffic. Localization of overlay connectivity reduces inter-ISP traffic. However, it can adversely affect the delivered quality. In this paper, we systematically examine the performance of SPS for live video over localized overlays. We identify and discuss the fundamental bottlenecks limiting the stream quality and present OLIVES, an ISP-friendly P2P streaming mechanism for live video. OLIVES maintains a fully localized overlay to reduce the volume of inter-ISP traffic and incorporates a two-tier inter-ISP and intra-ISP scheduling scheme to maximize the delivered quality to individual peers. One important design choice is to perform basic scheduling at a substream level and to use implicit coordination among peers. This allows OLIVES to efficiently detect missing blocks and pull them into the ISP in a timely manner with a minimum in coordination overhead. Furthermore, OLIVES incorporates a shortcutting technique that limits the buffer requirements for each participating peer and effectively reduced the playout latency. Through analysis and extensive simulations, we demonstrate the ability of OLIVES to deliver high-quality streams over localized overlays in various realistic scenarios.

During recent years, a few countries have put in place online antipiracy laws and there has been some major enforcement actions against violators. This raises the question that to what extent antipiracy actions have been effective in deterring online piracy? This is a challenging issue to explore because of the difficulty to capture user behavior, and to identify the subtle effect of various underlying (and potentially opposing) causes. In this paper, we tackle this question by examining the impact of two major antipiracy actions, the closure of Megaupload and the implementation of the French antipiracy law, on publishers in the largest BitTorrent portal who are major providers of copyrighted content online. We capture snapshots of BitTorrent publishers at proper times relative to the targeted antipiracy event and use the trends in the number and the level of activity of these publishers to assess their reaction to these events. Our investigation illustrates the importance of examining the impact of antipiracy events on different groups of publishers and provides valuable insights on the effect of selected major antipiracy actions on publishers' behavior.

In the era when Facebook and Twitter dominate the market for social media, Google has introduced Google+ (G+) and reported a significant growth in its size while others called it a ghost town. This begs the question that "whether G+ can really attract a significant number of connected and active users despite the dominance of Facebook and Twitter?".

BitTorrent is the most popular peer-to-peer (P2P) content delivery application where individual users share various types of content with tens of thousands of other users. The growing popularity of BitTorrent is primarily due to the availability of valuable content without any cost for the consumers. However, apart from the required resources, publishing valuable (and often copyrighted) content has serious legal implications for the users who publish the material. This raises the question that whether (at least major) content publishers behave in an altruistic fashion or have other motives such as financial incentives. In this paper, we identify the content publishers of more than 55 K torrents in two major BitTorrent portals and examine their characteristics. We discover that around 100 publishers are responsible for publishing 67% of the content, which corresponds to 75% of the downloads. Our investigation reveals several key insights about major publishers. First, antipiracy agencies and malicious users publish “fake” files to protect copyrighted content and spread malware, respectively. Second, excluding the fake publishers, content publishing in major BitTorrent portals appears to be largely driven by companies that try to attract consumers to their own Web sites for financial gain. Finally, we demonstrate that profit-driven publishers attract more loyal consumers than altruistic top publishers, whereas the latter have a larger fraction of loyal consumers with a higher degree of loyalty than the former.

BitTorrent is the most popular P2P content delivery application where individual users share various type of content with tens of thousands of other users. The growing popularity of BitTorrent is primarily due to the availability of valuable content without any cost for the consumers. However, apart from required resources, publishing (sharing) valuable (and often copyrighted) content has serious legal implications for users who publish the material (or publishers). This raises a question that whether (at least major) content publishers behave in an altruistic fashion or have other incentives such as financial. In this study, we identify the content publishers of more than 55K torrents in two major BitTorrent portals and examine their behavior. We demonstrate that a small fraction of publishers is responsible for 67 % of the published content and 75 % of the downloads. Our investigations reveal that these major publishers respond to two different profiles. On the one hand, antipiracy agencies and malicious publishers publish a large amount of fake files to protect copyrighted content and spread malware respectively. On the other hand, content publishing in BitTorrent is largely driven by companies with financial incentives. Therefore, if these companies lose their interest or are unable to publish content, BitTorrent traffic/portals may disappear or at least their associated traffic will be significantly reduced.

This paper presents a new approach to determine the geographical footprint of individual Autonomous Systems that directly provide service to end-users, i.e., eyeball ASes. The key idea is to leverage the geo-location of end-users associated with an eyeball AS to identify its geographical footprint. We leverage the kernel density estimation method to estimate the density of users across individual eyeball ASes. This method enables us to cope with the potential error associated with the location of individual end-users while controlling the level of aggregation among data points to capture a geo-footprint at the desired resolution. We use the resulting geo-footprint of individual eyeball ASes to identify their likely Point-of-Presence (PoP) locations. To demonstrate our proposed technique, we use the inferred geo-locations of 48 million users from three popular P2P applications and assess the geo- and PoP-level footprints of 1233 eyeball ASes. The validation of the identified PoP locations by our technique against online information and prior results by a commonly-used technique based on traceroute shows a very high accuracy. Leveraging the acquired PoP locations, we examine the implications of geo-footprint of eyeball ASes on their connectivity to the rest of the Internet. In particular, we present a case study that reveals a much more complex picture of AS-level connectivity as compared to what the more traditional but geography-agnostic BGP- or traceroute-based approaches depict.

This paper presents Respondent-Driven Sampling (RDS) as a promising technique to derive unbiased estimates of node properties in unstructured overlay networks such as Gnutella. Using RDS and a previously proposed technique, namely Metropolized Random Walk (MRW) sampling, we examine the efficiency of estimating node properties in unstructured overlays and identify some of the key factors that determine the accuracy of sampling techniques. We evaluate the RDS and MRW techniques using simulation over a wide range of static and dynamic graphs as well as experiments over a widely deployed Gnutella network. Our study sheds light on how the connectivity structure among nodes and its dynamics affect the accuracy and efficiency of the two sampling techniques. Both techniques exhibit a rather similar performance over a wide range of scenarios. However, RDS significantly outperforms MRW when the overlay structure exhibits a combination of highly skewed node degrees and highly skewed (local) clustering coefficients.

In Swarm-based Peer-to-Peer Streaming (SPS) mechanisms, par-ticipating peers form a randomly connected mesh over which they incorporate swarm-like content delivery. In practice, a subset of participating peers may form clusters in the overlay due to vari-ous reasons such as localization of connectivity within edge ISPs. Despite the commonly held assumptions, the appearance of such clusters could significantly degrade the delivered quality to partici-pating peers in SPS mechanisms. This paper examines the effect of overlay clustering on the per-formance of SPS mechanisms for live content. Leveraging the no-tion of two-phase content delivery in SPS mechanisms, we illus-trate the effect of overlay clustering on content delivery. We pro-pose the Overlay Monitoring and Repair (OMR) mechanism as a distributed and scalable approach to maintain proper overlay con-nectivity in SPS mechanisms. The key idea is to use delivered quality to individual peers as an indication of poor connectivity from other regions of the overlay. OMR employs a probabilistic ap-proach to ensure an adequate number of properly-positioned peers reacts to detected clustering in the overlay without any coordina-tion. Reacting peers rewire a small number of carefully-selected connections in the overlay to significantly improve the performance of content delivery. Our preliminary evaluations demonstrate that OMR mechanism can achieve its goals.

Abstract — Peer-to-Peer (P2P) streaming mechanism is a promising approach to offer one-to-many distribution of live streaming content to large number of residential users across the Internet. While a few P2P streaming mechanisms have been recently proposed, the behavior of these mechanisms in sessions where a large fraction of uasers are residential peers have not been examined. Several characteristics of residential users could affect the behavior of P2P streaming sessions including (i) the heterogeneity of access link bandwidth, (ii) the limitation of available resources due to asymmetric nature of access link bandwidth (for DSL and cable modem), and (iii) the participation of free-loaders. In this paper, we examine the effect of these three characteristics of residential users on the performance of P2P streaming mechanisms using ns simulations. We show that these characteristics could adversely affect the performance of P2P streaming mechanisms as follows. First, the delivered quality to individual users is not correlated with their contributed resource to the system. Second, the presence of free-loaders could dramatically degrade the delivered quality to participating peers even when the amount of available resources in the system are adequate. Our findings suggest that P2P streaming has to address these issues in order to be successfully deployed among residential users. I.

During the past few years, Peer-to-Peer (P2P) applications have become increasingly popular over the Internet. In these applications, a large number (e.g., millions) of geographically distributed end-systems (or peers) form an overlay to exchange content and share their resources. Several recent studies have observed the network traffic at one or few vantage points and shown that P2P applications significantly contribute to the overall Internet traffic(e.g., [2]). Given the distributed nature of P2P applications, the observed traffic associated with a P2P application across different regions (i.e., ASes) in the Internet depends on several factors including (i) the location of participating peers, (ii) the connectivity among the peers, and (iii) the BGP routing of traffic among ASes in the underlay. Therefore, the observed traffic for a P2P application at a single (or few) vantage point(s) clearly does not represent the extent of its impact across the network. Capturing an accurate view of the global impact of a P2P application requires access to a large number of vantage points that is prohibitively expensive. To our knowledge, none of the previous empirical studies on P2P systems have characterized the global impact of a P2P application on the AS-level underlay.

The observed performance by individual peers in BitTorrent can be simply measured by their average download rate. While it is often stated that the observed peer-level performance by BitTorrent clients is high, it is difficult to accurately verify this claim due to the large scale, distributed and dynamic nature of this P2P system. To provide a "representative" characterization of peer-level performance in BitTorrent, the following two important questions should be addressed: (i) What is the distribution of observed performance among participating peers in a torrent? (ii) What are the primary peer-or group-level properties that determine observed performance by individual peers? In this paper, we conduct a measurement study to tackle these two questions. Toward this end, we derive observed performance for nearly all participating peers along with their main peer-and (peer-view of) group-level properties in three different torrents. Our results show that the probability of experiencing certain level of performance has a roughly uniform distribution across the entire range of observed values. Furthermore, while the performance of each peer has the highest correlation with its outgoing bandwidth, there is no dominant peer-and group-level property that primarily determines the observed performance by the majority of peers.

The success of swarming content delivery has motivated a new approach to live peer-to-peer (P2P) streaming that we call mesh-based streaming. In this approach, participating peers form a random mesh and incorporate swarming content delivery to stream live content. Despite the growing popularity of this approach, neither the design tradeoffs nor the basic performance bottlenecks in mesh-based P2P streaming are well understood. This paper presents PRIME, the first mesh-based P2P streaming for live content that effectively incorporates swarming content delivery. We identify two performance bottlenecks in a mesh-based P2P streaming, namely bandwidth bottleneck and content bottleneck. We derive proper peer connectivity to minimize bandwidth bottleneck as well as an efficient pattern of delivery for live content over a random mesh to minimize content bottleneck. We show that the pattern of delivery can be divided into diffusion and swarming phases and then identify proper packet scheduling algorithm at individual peers. Using ns simulations, we examine key characteristics, design tradeoffs and the relationship between main system parameters.

Existing approaches to P2P streaming can be divided into two general classes: (i)tree-based approachesuse push-based content delivery over multiple tree-shaped overlays, and (ii)mesh-based approachesuse swarming content delivery over a randomly connected mesh. Previous studies have often focused on a particular P2P streaming mechanism and no comparison between these two classes has been conducted. In this paper, we compare and contrast the performance of representative protocols from each class using simulations. We identify the similarities and differences between these two approaches. Furthermore, we separately examine the behavior of content delivery and overlay construction mechanisms for both approaches in static and dynamic scenarios. Our results indicate that the mesh-based approach consistently exhibits a superior performance over the tree-based approach. We also show that the main factors attributing in the inferior performance of the tree-based approach are (i) the static mapping of content to a particular tree, and (ii) the placement of each peer as an internal node in one tree and as a leaf in all other trees.

The dynamics of peer participation, or churn, are an inherent property of Peer-to-Peer (P2P) systems and critical for design and evaluation. Accurately characterizing churn requires precise and unbiased information about the arrival and departure of peers, which is challenging to acquire. Prior studies show that peer participation is highly dynamic but with conflicting characteristics. Therefore, churn remains poorly understood, despite its significance.In this paper, we identify several common pitfalls that lead to measurement error. We carefully address these difficulties and present a detailed study using three widely-deployed P2P systems: an unstructured file-sharing system (Gnutella), a content-distribution system (BitTorrent), and a Distributed Hash Table (Kad). Our analysis reveals several properties of churn: (i) overall dynamics are surprisingly similar across different systems, (ii) session lengths are not exponential, (iii) a large portion of active peers are highly stable while the remaining peers turn over quickly, and (iv) peer session lengths across consecutive appearances are correlated. In summary, this paper advances our understanding of churn by improving accuracy, comparing different P2P file sharingdistribution systems, and exploring new aspects of churn.

This paper addresses the difficult problem of selecting representative samples of peer properties (eg degree, link bandwidth, number of files shared) in unstructured peer-to-peer systems. Due to the large size and dynamic nature of these systems, measuring the quantities of interest on every peer is often prohibitively expensive, while sampling provides a natural means for estimating system-wide behavior efficiently. However, commonly-used sampling techniques for measuring peer-to-peer systems tend to introduce considerable bias for two reasons. First, the dynamic nature of peers can bias results towards short-lived peers, much as naively sampling flows in a router can lead to bias towards short-lived flows. Second, the heterogeneous nature of the overlay topology can lead to bias towards high-degree peers.We present a detailed examination of the ways that the behavior of peer-to-peer systems can introduce bias and suggest the Metropolized Random Walk with Backtracking (MRWB) as a viable and promising technique for collecting nearly unbiased samples. We conduct an extensive simulation study to demonstrate that the proposed technique works well for a wide variety of common peer-to-peer network conditions. Using the Gnutella network, we empirically show that our implementation of the MRWB technique yields more accurate samples than relying on commonly-used sampling techniques. Furthermore, we provide insights into the causes of the observed differences. The tool we have developed, ion-sampler, selects peer addresses uniformly at random using the MRWB technique. These addresses may then be used as input to another measurement tool to collect data on a particular property.

Peer-to-Peer (P2P) file sharing applications have witnessed a dramatic increase in popularity during the past few years. To accommodate the rapid growth in user population, developers introduced new features in their client software, in particular a two-tier overlay topology. The effect of the two- tier overlay topology in a widely-deployed P2P system primarily depends on the availability and coherency of its implementations among participating clients throughout the system. This paper sheds some light on the long-term evolution of such a two-tier overlay topology in the Gnutella network during a 15-month period over which the system quadrupled in size, exceeding three million concurrent peers. Our results show two interesting phenomena including: (i) During this period, the two- tier overlay has repeatedly begun to lose its balance. However, proper modifications in major client software coupled with the rapid upgrade rate of users, has enabled the developers to maintain the overlay's desired properties, (ii) Despite its random connectivity, the Gnutella overlay exhibits a strong bias towards intra-continent connectivity, especially in continents with smaller user populations, that has not changed as the system scaled.

During recent years, Distributed Hash Tables (DHTs) have been extensively studied through simulation and analysis. However, due to their limited deployment, it has not been possible to observe the behavior of a widely-deployed DHT in practice. Recently, the popular eMule file-sharing software incorporated a Kademlia-based DHT, called Kad, which currently has around one million simultaneous users. In this paper, we empirically study the performance of the key DHT operation, lookup, over Kad. First, we analytically derive the benefits of different ways to increase the richness of routing tables in Kademlia-based DHTs. Second, we empirically characterize two aspects of the accuracy of routing tables in Kad, namely completeness and freshness, and characterize their impact on Kad’s lookup performance. Finally, we investigate how the efficiency and consistency of lookup in Kad can be improved by performing parallel lookup and maintaining multiple replicas, respectively. Our results pinpoint the best operating point for the degree of lookup parallelism and the degree of replication for Kad.

A common approach for measurement-based characterization of peer-to-peer (P2P) systems is to capture overlay snapshots using a crawler. The accuracy of captured snapshots by P2P crawlers directly depends on both the crawling speed and the fraction of unreachable peers. This in turn affects the accuracy of the conducted characterization based on these captured snapshots. Prior studies frequently rely on crawling the network over an hour or more, during which time the overlay may change substantially. Moreover, none of the previous measurement-based studies on P2P systems have examined the accuracy of their captured snapshots or the impact on conducted characterization. In this paper, we present a fast P2P crawler called Cruiser, discuss aspects of its design, and evaluate its accuracy. Cruiser is able to crawl the million-node Gnutella network in around 7 minutes. Having these accurate snapshots enables us to quantify (i) the "relative error" in captured snapshot as a function of crawling speed, (ii) the tradeoff between the completeness and accuracy of captured snapshots, and (iii) the effect of snapshot accuracy on the correctness of characterizations of Gnutella.

Peer-to-peer systems are becoming increasingly popular, with millions of simultaneous users and a wide range of applications. Understanding existing systems and devising new peer-to-peer techniques relies on access to representative models derived from empirical observations. Due to the large and dynamic nature of these systems, directly capturing global behavior is often impractical. Sampling is a natural approach for learning about these systems, and most previous studies rely on it to collect data. This paper addresses the common problem of selecting representative samples of peer properties such as peer degree, link bandwidth, or the number of files shared. A good sampling technique will select any of the peers present with equal probability. However, common sampling techniques introduce bias in two ways. First, the dynamic nature of peers can bias results towards short-lived peers, much as naively sampling flows in a router can lead to bias towards short-lived flows. Second, the heterogeneous overlay topology can lead to bias towards high-degree peers. We present preliminary evidence suggesting that applying a degree-correction method to random walk-based peer selection leads to unbiased sampling, at the expense of a loss of efficiency.

A common approach to peer-to-peer (P2P) streaming is to form a tree-based overlay coupled with push content delivery. This approach cannot effectively utilize the outgoing bandwidth of participating peers, and therefore it is not self-scaling. In contrast, swarm-like content delivery mechanisms exhibit the self-scaling property but incorporating them into live P2P streaming applications are challenging for two reasons: (i) in-time requirement of content delivery and (ii) the limited availability of future content.

A common approach for measurement-based characterization of peer-to-peer (P2P) systems is to capture overlay snapshots using a crawler. The accuracy of captured snapshots by P2P crawlers directly depends on both the crawling speed and the fraction of unreachable peers. This in turn affects the accuracy of the conducted characterization based on these captured snapshots. Prior studies frequently rely on crawling the network over an hour or more, during which time the overlay may change substantially. Moreover, none of the previous measurement-based studies on P2P systems have examined the accuracy of their captured snapshots or the impact on conducted characterization.

Characterizing the properties of peer-to-peer (P2P) overlay topologies in file-sharing applications is essential for understanding their impact on the network, identifying their performance bottlenecks in practice, and evaluating their performance via simulation. Such characterization requires accurate snapshots of the overlay topology which is difficult to capture due to the large size and dynamic nature. Previous studies characterizing overlay topologies not only are outdated but also rely on partial or potentially distorted snapshots. In this extended abstract, we briefly present the first characterization of two-tier Gnutella topologies based on recent and accurate snapshots.

This paper presents a simple and scalable framework for architecting peer-to-peer overlays called Peer-to-peer Receiver-driven Overlay (or PRO). PRO is designed for non-interactive streaming applications and its primary design goal is to maximize delivered bandwidth (and thus delivered quality) to peers with heterogeneous and asymmetric bandwidth. To achieve this goal, PRO adopts a receiver-driven approach where each receiver (or participating peer) (i) independently discovers other peers in the overlay through gossiping, and (ii) selfishly determines the best subset of parent peers through which to connect to the overlay to maximize its own delivered bandwidth. Participating peers form an unstructured overlay which is inherently robust to high churn rate. than structured overlay networks. Furthermore, each receiver leverages congestion controlled bandwidth from its parents as implicit signal to detect and react to long-term changes in network or overlay condition without any explicit coordination with other participating peers. Independent parent selection by individual peers dynamically converge to an efficient overlay structure.

This paper presents a new framework for Peer-to-Peer Adaptive Layered Streaming, called PALS. PALS is a receiver-driven approach for quality adaptive playback of layer encoded streaming media from a group of congestion controlled sender peers to a single receiver peer. Since the effective throughput from each sender is variable and not known a priori, it is challenging to coordinate delivery among active senders. In PALS, the receiver orchestrates coordinated delivery among active senders by adaptively determining: 1) a subset of senders that maximize overall throughput, 2) overall quality (i.e. number of layers) that can be delivered from these senders as well as distribution of overall throughput among active layers, and most importantly 3) required packets to be delivered by each active sender in order to effectively cope with any sudden change in throughput from individual senders. We describe PALS framework, identify key components of the framework and their interesting design challenges, present sample solution for the key components, and present our preliminary results.

Multimedia proxy caching is a client-oriented solution for large-scale delivery of high quality streams over heterogeneous networks such as the Internet. Existing solutions for multimedia proxy caching are unable to adjust quality of cached streams. Thus these solutions either can not maximize delivered quality or exhibit poor caching efficiency. This paper presents the design and implementation ofMocha, a quality adaptive multimedia proxy cache for layered encoded streams. The main contribution of Mocha is its ability to adjust quality of cached streams based on their popularity and on the available bandwidth between proxy and interested clients. Thus Mocha can significantly improve caching efficiency without compromising delivered quality. To perform quality adaptive caching, Mocha implementsfine-grained replacementandfine-grained prefetchingmechanisms. We describe our prototype implementation of Mocha on top of Squid and address various design challenges such as managing partially cached streams. Finally, we validate our implementation and present some of our preliminary results.

The Internet has witnessed a rapid growth in deployment of Web-based streaming applications during recent years. In these applications, the server should be able to perform end-to-end congestion control and quality adaptation to match the delivered stream quality to the average available bandwidth. Thus the delivered quality is limited by the bottleneck bandwidth on the path to the client. This paper proposes a proxy caching mechanism for layered-encoded multimedia streams in the Internet to maximize the delivered quality of popular streams to interested clients. The main challenge is to replay a quality-variable cached stream while performing quality adaptation effectively in response to the variations in available bandwidth. We present a prefetching mechanism to support higher quality cached streams during subsequent playbacks and improve the quality of the cached stream with its popularity. We exploit inherent properties of multimedia streams to extend the semantics of popularity and capture both level of interest among clients and usefulness of a layer in the cache. We devise a fine-grain replacement algorithm suited for layered-encoded streams. Our simulation results show that the interaction between the replacement algorithm and prefetching mechanism causes the state of the cache to converge to an efficient state such that the quality of a cached stream is proportional to its popularity, and the variations in quality of a cached stream are inversely proportional to its popularity. This implies that after serving several requests for a stream, the proxy can effectively hide low bandwidth paths to the original server from interested clients.

Streaming audio and video applications are becoming increasingly popular on the Internet, and the lack of effective congestion control in such applications is now a cause for significant concern. The problem is one of adapting the compression without requiring video servers to reencode the data, and fitting the resulting stream into the rapidly varying available bandwidth. At the same time, rapid fluctuations in quality will be disturbing to the users and should be avoided. We present a mechanism for using layered video in the context of unicast congestion control. This quality adaptation mechanism adds and drops layers of the video stream to perform long-term coarse-grain adaptation, while using a TCP-friendly congestion control mechanism to react to congestion on very short timescales. The mismatches between the two timescales are absorbed using buffering at the receiver. We present an efficient scheme for the distribution of available bandwidth among the active layers. Our scheme allows the server to trade short-term improvement for long-term smoothing of quality. We discuss the issues involved in implementing and tuning such a mechanism, and present our simulation results.

End-to-end congestion control mechanisms have been critical to the robustness and stability of the Internet. Most of today's Internet traffic is TCP, and we expect this to remain so in the future. Thus, having "TCP-friendly" behavior is crucial for new applications. However, the emergence of non-congestion-controlled realtime applications threatens unfairness to competing TCP traffic and possible congestion collapse. We present an end-to-end TCP-friendly rate adaptation protocol (RAP), which employs an additive-increase, multiplicative-decrease (AIMD) algorithm. It is well suited for unicast playback of realtime streams and other semi-reliable rate-based applications. Its primary goal is to be fair and TCP-friendly while separating network congestion control from application-level reliability. We evaluate RAP through extensive simulation, and conclude that bandwidth is usually evenly shared between TCP and RAP traffic. Unfairness to TCP traffic is directly determined by how TCP diverges from the AIMD algorithm. Basic RAP behaves in a TCP-friendly fashion in a wide range of likely conditions, but we also devised a fine-grain rate adaptation mechanism to extend this range further. Finally, we show that deploying RED queue management can result in an ideal fairness between TCP and RAP traffic.

Streaming audio and video applications are becoming increasingly popular on the Internet, and the lack of effective congestion control in such applications is now a cause for significant concern. The problem is one of adapting the compression without requiring video-servers to re-encode the data, and fitting the resulting stream into the rapidly varying available bandwidth. At the same time, rapid fluctuations in quality will be disturbing to the users and should be avoided.In this paper we present a mechanism for using layered video in the context of unicast congestion control. This quality adaptation mechanism adds and drops layers of the video stream to perform long-term coarse-grain adaptation, while using a TCP-friendly congestion control mechanism to react to congestion on very short timescales. The mismatches between the two timescales are absorbed using buffering at the receiver. We present an efficient-scheme for the distribution of buffering among the active layers. Our scheme allows the server to trade short-term improvement for long-term smoothing of quality. We discuss the issues involved in implementing and tuning such a mechanism, and present our simulation results.