Silent packet drops and packet corruptions, which are caused by faulty network elements and hurt performances of cloud applications, are common in data centers but hard to detect and localize. Existing solutions based on active probes introduce additional probe traffic and are constrained by probe rate, while solutions based on passive traffic monitoring measure the entire network traffic, and are generally unable to pinpoint the locations where packet losses happen. In this paper, we presentCanary, a system for detecting and localizing network faults with partial traffic monitoring. Canary employs a lightweight and adaptive mechanism to detect packet losses by monitoring a small set of large-sized network flows, and it ensures that on each network path, a sufficient number of packets are monitored by upstream and downstream switches. In addition, Canary encodes information of the path that a packet travels along within its header, and by leveraging path information of the lost packets, Canary is capable to localize network faults with high accuracy. We theoretically prove the effectiveness of our proposed method, and prototype Canary with P4 on commodity hardware programmable switches. Results from extensive experiments driven by real-world traffic show that Canary is lightweight regarding measurement overhead, robust under traffic dynamics, and is accurate in detecting and localizing faulty network links. In particular, comparing with the state-of-the-art solutions, Canary reduces the memory overhead by over 97% under$10^{-2}$link loss rate, and increases the F1-score in localizing the faulty links by over 20% on a$k=8$fat-tree data center network.

Abstract A sketch-based method is promising for traffic monitoring in data center networks. Existing data plane programming model (e.g. P4) assumes target switch as one single pipeline, while state-of-the-art programmable switches actually contain multiple independent pipelines. The status quo approach for deploying a sketch-based measurement application on a multi-pipeline switch is to deploy a sketch instance in each pipeline individually. However, under multi-path routing, such a naive approach leads to poor accuracy. To overcome this problem, in this paper, we present Confluence, a sketch-based network measurement system for multi-pipeline switches. For monitoring network flows that have packets arrived in bursts and spread over multiple pipelines, Confluence introduces novel data structures to collect short-term traffic statistics in ingress pipelines, and converge the measurement data to egress pipelines. Confluence is carefully designed under the switch hardware constraints, and in particular, to resolve the circular dependency in querying and updating a flow’s measurement data from sketch buckets, we propose a novel algorithm and theoretically prove its effectiveness. Both theoretical analysis and experiments driven by real-world traffic traces show that Confluence delivers higher measurement accuracies than existing solutions, especially in the critical task of detecting heavy hitters. Assessment on hardware switch suggests that Confluence is practical for real-world deployment.

To overcome the inherent limitation of the optical circuit switch (OCS) while utilizing its high bandwidth, circuit/packet hybrid networks are widely proposed for modern data centers. However, as today’s OCS has reduced the reconfiguration delay to microseconds, the circuit from a source rack to a destination rack typically lasts fewer than 10 RTTs. Such a short circuit time brings a critical challenge to TCP, as it is difficult for a TCP sender to sufficiently grow its congestion window (CWND) and utilize the optical bandwidth. To address this problem, in this work, we presentAccelToR, a top-of-rack switch for improving TCP performance in circuit/packet hybrid data center networks. AccelToR leverages end-host congestion control to “accelerate” a blocked TCP flow by temporarily scheduling its packets to be transferred through the packet network a few RTTs before its circuit is established, and after enlarging the flow’s CWND with the acceleration, the switch buffers the last window of packets. During the circuit time, the switch sends out the buffered packets, and the accelerated flows, which have their CWNDs already grown large, continue to send packets at high rates to achieve a high optical bandwidth utilization. Experiment results show that AccelToR achieves high throughputs for elephant flows and utilizes over$\mathbf {90\%}$of the optical bandwidth, and it preserves short flow completion times for mice flows at the same time. In addition, AccelToR is robust under unexpected packet losses, and can benefit a wide range of TCP congestion control algorithms.

Large spread and high persistence are widely observed in malicious activities such as botnets and DDoS attacks in high-speed networks, while how to identify persistent-spreaders is still a challenging issue. In this work, we presentPS-Sketch, a system for estimating persistent-spreads of network flows and detecting persistent-spreaders in network data streams. PS-Sketch is based on our definitions of persistence and persistent-spread, which overcome the limitations of the conventional definitions by better capturing network flows’ behaviors, and being difficult for attackers to bypass. Within a switch’s pipeline, PS-Sketch processes packets with two adjacent sketch data structures, namely the P-sketch and the S-sketch. In the P-sketch, we employ low-pass filter (LPF) to trace an element’s persistence that incorporates occurrences in its entire history, and in the S-sketch, we extend the HyperLogLog (HLL) algorithm, and integrate an element’s persistence to the spread estimation of the flow that the element belongs to, for estimating the flow’s persistent-spread. We present theoretical analysis on the error bound of PS-Sketch. Trace-driven evaluation shows that PS-Sketch achieves high accuracy in estimating network flows’ persistent-spreads, and outperforms the existing solutions in detecting persistent-spreaders. We further prototype PS-Sketch in P4 and show that the system is deployable on commodity hardware switches.

Weighted fair queueing (WFQ) is an essential strategy for enforcing bandwidth guarantee and isolation in high-speed networks. Unfortunately, implementing the original WFQ packet scheduling algorithm on today’s commodity switch hardware is challenging due to the prohibitive complexity. Approximate WFQ packet schedulers, which work with the cheap and widely available First-In First-Out (FIFO) queues, have been proposed as an alternative in recent years. In this paper, we show that both the ideal and the approximate WFQ packet schedulers are unable to allocate bandwidths to TCP flows fairly, because of the bursty nature of the TCP traffic. Furthermore, we find that the representative approximate WFQ schedulers further degrade the scheduling fairness, due to their excessive packet drops. To address these issues, we present novel approximate WFQ packet scheduling algorithms in this paper. Our initial design, namely SQ-WFQ, imposes the minimum hardware requirement by using one single FIFO queue, and effectively reduces the excessive packet drops. Extended from SQ-WFQ, we propose the SQ-EWFQ packet scheduling algorithm. SQ-EWFQ inherits all the merits of SQ-WFQ, and is adaptive to the bursty TCP traffic by tolerating short-term packet bursts, while enforcing a long-term fairness among the TCP flows. We have implemented our proposed schedulers on commodity hardware programmable switches, and achieve line rate packet scheduling with them. Experiment results from a real-world testbed and large-scale simulations show that SQ-WFQ and SQ-EWFQ outperform the state-of-the-art approximate schedulers regarding the scheduling fairness, and SQ-EWFQ allocates bandwidths to TCP flows more fairly than SQ-WFQ and other existing solutions.

Sketch-based method has emerged as a promising direction for per-flow measurement in data center networks. Usually in such a measurement system, a sketch data structure is placed as a whole at one switch for counting all passing packets, but when summarizing measurement results from multiple switches, the overall accuracy is generally constrained by a few individual switches with small-sized sketches due to their limited memory resources. To address this problem, in this paper, we present Distributed Sketch, a new method for per-flow network measurement in data center networks. In Distributed Sketch, each network path is associated with a logical sketch, whose data structure is collectively maintained by all the switches along the path; meanwhile, each switch multiplexes its physical sketch to the constructions of the logical sketches of all the paths it belongs to. With Distributed Sketch, switches collaborate to measure network flows, and the network-wide measurement workload is fairly distributed among all the switches in the network. We implement Distributed Sketch with P4 on commodity hardware programmable switch, and in particular, to overcome the limitation that hardware switches do not support float-point computation, we present an optimal approximation method that involves only integer operations. We also propose an In-band Network Telemetry (INT) based method for addressing the challenges in deploying Distributed Sketch in large-scale data centers. Experiment results and theoretical analysis show that our proposed method is lightweight regarding measurement overhead, and by aggregating and making fair uses of resources from all the switches in the network, Distributed Sketch achieves a higher measurement accuracy compared with the state-of-the-art solutions.

Cloud computing is critical for today's information society. In this paper, we shed light on two radically different cloud design philosophies: theDC-cloudbuilt around massive data centers, and theISP-cloudbuilt upon a large ISP. With extensive measurements on Alibaba, Tencent, and CTYun, we find that both designs have strengths and weaknesses: the ISP-cloud of CTYun has less inflated paths to users within the same ISP, but its paths to external users are more inflated comparing with the DC-clouds of Alibaba and Tencent. By analyzing the clouds’ routing policies, we reveal the reasons behind the path inflations: Alibaba and Tencent adopt anearly-exitpolicy to use more inflated public Internet paths as early as possible; while CTYun follows aglobal and location-agnosticpolicy to detour traffic to remote PoPs, leading to highly inflated paths. Based on the insights, we suggest alternative policies and averagely reduce 11.0% latency to 30.5% destinations for Alibaba, 9.8% latency to 18.6% destinations for Tencent, and 54.1% latency to external destinations for CTYun. The results suggest that both cloud designs have rooms for improvement, and an ISP-cloud has the potential to achieve a superior performance, thanks to its inherited advantages from the ISP infrastructure.

In-band Network Telemetry (INT) is a novel framework for monitoring network health in real-time, and its recent variant, Probabilistic INT (PINT), reduces its bandwidth consumption with a probabilistic approach. However, as we show in this paper, a PINT task can be successfully accomplished only when it is allocated a sufficient number of packets, and if there are many tasks executed in parallel, packets become a scarce resource. Meanwhile, today’s production network generally executes multiple measurement tasks for tracing different network states simultaneously. Therefore, in such a context, scheduling parallel PINT tasks on one single INT flow that has a limited number of packets becomes a critical problem. In this paper, we address this problem for the first time. We propose an algorithm that efficiently schedules multiple parallel PINT tasks on a flow by allocating the flow’s packets to the tasks and showing that the allocation is optimal. We realize the algorithm with a packet processing pipeline and implement it on software and hardware-programmable switches. Comprehensive evaluation on a FatTree testbed shows that at a low scheduling overhead, our algorithm can conduct parallel PINT tasks to detect various network faults in a timely and accurate manner. Additionally, the algorithm accomplishes more PINT tasks with higher quality than the alternative solutions.

Leading e-commerce providers have built large and complicated systems to provide countrywide or even worldwide services. However, there have been few substantive studies on e-commerce systems in real world. In this paper, we investigate the systems of Tmall and JD, the top-two most popular e-commerce websites in China, with a measurement approach. By analyzing traffics from campus network, we present a characterization study that covers several features, including usage patterns and shopping behaviors, of the e-commerce workload; in particular, we characterize the massive flash crowd in the Double-11 Day, which is the biggest online shopping festival in the world. We also reveal Tmall and JD's e-commerce infrastructures, including content delivery networks (CDNs) and clouds, and evaluate their performances under the flash crowd. We find that Tmall's CDN proactively throttles bandwidths for ensuring low but guaranteed throughputs, while JD still follows the best-effort way, leading to poor and unstable performances; both providers do not have sufficient capacities in their private clouds, resulting in extraordinarily long transaction latencies. Based on the insights obtained from measurement, we discuss the design choices of e-commerce CDNs, and investigate the potential benefits brought by incorporating client-side assistances in offloading massive flash crowd of e-commerce workloads.

High-level programming abstraction and large-scale deployment have become two important trends of software-defined networking (SDN) in the past decade. Using high-level program to manage the large-scale network faces more serious control plane extensibility problem due to its complex intermediate representation and protocol-independent feature. To address this problem, we propose SPARC, a programmable and scalable controller architecture, which employs a hybrid hierarchical structure to maximize flexibility with regard to control plane distribution. Our architecture also allows for pushing down control decision making closer to the data plane and localize network event processing to lower the latency of control plane operations while exploiting SDN's global visibility to build optimal policy decisions. Furthermore, we investigate the feasibility of SPARC by exemplifying the case of delivering ICN mobility services and then conduct evaluations to demonstrate the efficacy of our design.

Crowdsourced live video broadcasting services, such as Twitch and YouTube Live, are becoming increasingly popular. In such a service, viewers are allowed to perform rich interactions, such as posting comments and donating monetary virtual gifts, while watching videos. Understanding viewer interactions is essential for people to comprehend the production and consumption of the crowdsourced live video content and improve the service. However, the basic characteristics of the viewer interactions are still unknown. In this paper, we present a comprehensive measurement study of the viewer interactions on Douyu, a popular crowdsourced live video broadcasting website in China. Our measurement spans four months and contains comment posting and virtual gift donating interactions from tens of millions of viewers in hundreds of thousands of channels. Based on the measurement data, we carry out a content analysis on danmu comments and characterize the patterns of the viewer interactions. We build a suite of models for capturing the gift donating process, viewer activity, and channel popularity. We further analyze the influences of the broadcaster's behavioral factors on a channel's popularity and present methodologies for popularity predicting. Our measurement and analysis have important implications on the design and business policy of the crowdsourced live video broadcasting services.

Real-time media flow protocol (RTMFP) is a protocol developed by Adobe for multimedia delivery under both client-server and peer-to-peer (P2P) paradigms. Currently, major Internet video service providers, such as PPTV and iQIYI, have already built their Web-based video streaming systems with RTMFP. In such a system, a user only needs to install a Flash Player plug-in on his Web browser, and can stream videos in a peer-assisted way. Despite its wide usage, RTMFP has received little attention from the measurement community. In this paper, we select PPTV as an example and study the RTMFP video streaming technology with a measurement approach. We reveal the architecture of PPTV's RTMFP streaming system and show that, compared with proprietary P2P networks, the RTMFP network has a different content distribution policy, and exhibits different features on peers' streaming behaviors, potential system bottleneck, and network dynamics. We also study RTMFP's video transmission and find that the protocol's selective retransmission scheme can effectively overcome packet losses and improve the video playback quality; however, the TCP-like congestion control mechanism of RTMFP does not lead to fairness between RTMFP and Transmission Control Protocol (TCP) traffics, due to the mismatch between the inherited pull-based video segment distribution model of the P2P streaming application and the protocol's built-in congestion control mechanism. This paper provides insights into the RTMFP-based video streaming technology and is helpful for people to construct better peer-assisted video systems with RTMFP.

With information becoming a first-class citizen on the Internet, information-centric networking (ICN) is considered as a promising direction for the future Internet. Named data networking (NDN) is a prominent example of emerging ICN architectures. Unfortunately, NDN is vulnerable to various attacks targeting its in-network caching mechanism. In this paper, we focus on the false-locality pollution attack, in which an adversary repeatedly requests a number of unpopular data objects to waste the precious cache space on the NDN router and to reduce normal users' hit ratios. With simulation experiments, we show that such an attack can cause considerable damage to the NDN network. To detect and mitigate such an attack, we introduce an algorithm that exploits the diversity of the Interest traversing paths within an Internet service provider's point-of-presence network. We also propose inexpensive methodologies based on the probabilistic counting and Bloom filter techniques to implement the algorithm on an NDN router. The experimental results indicate that our proposed algorithm is effective in thwarting false-locality pollution. We also experiment with strategies that the adversary may utilize against our antipollution algorithm and demonstrate that such strategies are either ineffective or impractical in the real world.

Information-centric networking (ICN) is one promising direction for the future Internet, and how to manage the in-network caching resources is a fundamental problem in ICN. In this paper, we address the problem by proposing a utility-based caching mechanism. In the mechanism, network nodes track the utilities of the contents that they have ever cached, and en-route nodes cooperate to make the caching decisions. For enabling the utility tracking, we introduce a novel component named Tracking Store in ICN routers, and develop two methodologies for implementing this component based on dynamic LRU queue and time-decaying Bloom filter (TBF). Through analysis and extensive simulations using real-world topologies, we show that at a sustainable router overhead, our proposed mechanism, with both of its implementations, achieves a superior caching performance than existing solutions under various content popularity scenarios.We also explore the inherent tradeoff of the mechanism, and provide guideline for its realworld deployment.

Crowdsourcing services have emerged and become popular on the Internet in recent years. However, evidence shows that crowdsourcing can be maliciously manipulated. In this paper, we focus on the “dark side” of the crowdsourcing services. More specifically, we investigate the spam campaigns that are originated and orchestrated on a large Chinese-based crowdsourcing website, namely ZhuBaJie.com, and track the crowd workers to their spamming behaviors on Baidu Zhidao, the largest community-based question answering (QA) site in China. By linking the spam campaigns, workers, spammer accounts, and spamming behaviors together, we are able to reveal the entire ecosystem that underlies the crowdsourcing spam attacks. We present a comprehensive and insightful analysis of the ecosystem from multiple perspectives, including the scale and scope of the spam attacks, Sybil accounts and colluding strategy employed by the spammers, workers' efforts and monetary rewards, and quality control performed by the spam campaigners, etc. We also analyze the behavioral discrepancies between the spammer accounts and the legitimate users in community QA, and present methodologies for detecting the spammers based on our understandings on the crowdsourcing spam ecosystem.

With the increasing popularity of the Internet video streaming services (e.g. YouTube and Netflix), content delivery networks (CDNs) are heavily used to stream video contents to users, and consume more and more power and bandwidths in recent years. In this paper, we investigate the problem of saving a video streaming CDN's operating expense, including both its energy cost and the traffic cost. From our measurement study on the CDN infrastructure of Youku, which is the largest video site in China, we find that there exists an inherent conflict between improving a video streaming CDN's energy efficiency for power saving, and maintaining the CDN's ISP-friendly server selection policy. To address this problem, we propose a cost-aware capacity provisioning algorithm, which dynamically plans the service capacities of a CDN's server clusters in numerous ISPs, and optimizes its overall operating cost regarding both the energy consumptions and the cross-ISP traffics. By using the workload derived from real-world measurement and applying actual power and bandwidth price parameters, we show with experiments that our approach can significantly reduce a video streaming CDN's overall operating cost, and avoid frequent server switches effectively. To our best knowledge, this work is the first one that identifies and resolves the inherent conflict between a CDN's energy efficiency and its ISP-friendly policy.

Reliable Group Data Delivery (RGDD) is a pervasive traffic pattern in data centers. In an RGDD group, a sender needs to reliably deliver a copy of data to all the receivers. Existing solutions either do not scale due to the large number of RGDD groups (e.g., IP multicast) or cannot efficiently use network bandwidth (e.g., end-host overlays). Motivated by recent advances on data center network topology designs (multiple edge-disjoint Steiner trees for RGDD) and innovations on network devices (practical in-network packet caching), we propose Datacast for RGDD. Datacast explores two design spaces: 1) Datacast uses multiple edge-disjoint Steiner trees for data delivery acceleration. 2) Datacast leverages in-network packet caching and introduces a simple soft-state based congestion control algorithm to address the scalability and efficiency issues of RGDD. Our analysis reveals that Datacast congestion control works well with small cache sizes (e.g., 125KB) and causes few duplicate data transmissions (e.g., 1.19%). Both simulations and experiments confirm our theoretical analysis. We also use experiments to compare the performance of Datacast and BitTorrent. In a BCube(4, 1) with 1Gbps links, we use both Datacast and BitTorrent to transmit 4GB data. The link stress of Datacast is 1.01, while it is 1.39 for BitTorrent. By using two Steiner trees, Datacast finishes the transmission in 16.9s, while BitTorrent uses 52s.

We perform a large-scale topology mapping and geolocation study for China's Internet. To overcome the limited number of Chinese PlanetLab nodes and looking glass servers, we leverage unique features in China's Internet, including the hierarchical structure of the major ISPs and the abundance of IDC data centers. Using only 15 vantage points, we design a traceroute scheme that finds significantly more interfaces and links than iPlane with significantly fewer traceroute probes. We then consider the problem of geolocating router interfaces and end hosts in China. When examining three well-known Chinese geoIP databases, we observe frequent occurrences of null replies and erroneous entries, suggesting that there is significant room for improvement. We develop a heuristic for clustering the interface topology of a hierarchical ISP, and then apply the heuristic to the major Chinese ISPs. We show that the clustering heuristic can geolocate router interfaces with significantly more detail and consistency than can the existing geoIP databases in isolation. We show that the resulting clusters expose several characteristics of the Chinese Internet, including the major ISPs' provincial structure and the centralized interconnections among the ISPs. Finally, using the clustering heuristic, we propose a methodology for improving commercial geoIP databases and evaluate using IDC data center landmarks.

We perform a large-scale topology mapping and geolocation study for China's Internet. To overcome the limited number of Chinese PlanetLab nodes and looking glass servers, we leverage several unique features in China's Internet, including the hierarchical structure of the major ISPs and the abundance of IDCs. Using only 15 vantage points, we design a traceroute scheme that finds significantly more interfaces and links than iPlane with significantly fewer traceroute probes. We then consider the problem of geolocating router interfaces and end hosts in China. We develop a heuristic for clustering the interface topology of a hierarchical ISP, and then apply the heuristic to the major Chinese ISPs. We show that the clustering heuristic can geolocate router interfaces with significantly more detail and accuracy than can the existing geoIP databases in isolation, and the resulting clusters expose the major ISPs' provincial structure. Finally, using the clustering heuristic, we propose a methodology for improving commercial geoIP databases.

Reliability of tree-like multicast overlays caused by nodes' abrupt failures is considered as one of the major problems for the Internet application-layer media streaming service. In this paper, we address this problem by designing a distributed and light-weighted protocol named the instantaneous reliability oriented protocol (IRP). Unlike most of existing empirical solutions, we first define the overlay reliability problem formally, and propose a protocol containing a node joining algorithm (IRP-Join), a node preemption algorithm (IRP-Preempt), and a node switching algorithm (IRP-Switch) for reactively constructing and repairing the overlay, as well as proactively maintaining the overlay. With the formal problem presentation, we set up a paradigm for solving the overlay reliability problem by theoretically proving the effectiveness of our algorithms. Moreover, by comparing IRP with existing solutions via simulation-based experiments and real-world deployment, we show that IRP achieves a better reliability, while incurs fewer structural adjustments on the multicast overlay, thus, providing a superior overall performance.

In recent years, many distributed rating systems have been proposed against the increasing misbehaviors of peers in peer-to-peer (P2P) networks. However, the low accuracy, long-response time and vulnerabilities under the adversary attacks of P2P rating systems have long been criticized and hindering the practical deployment of such a mechanism. There is also a lack of systematic analysis and evaluation for understanding the systems. In this paper, we first present a framework of stochastic analytical model for evaluating P2P rating systems. The performances of two representative designs, namely the unstructured self-managing rating (UMR) system and the structured supervising rating (SSR) system, are then studied with our model. We identify the positive features as well as the negative ones of the two designs with different design choices and under various network environments and adversary attacks. We also propose a configurable loosely supervising rating system, and show that this system works inexpensively, and could make trade-off between the false rating attack resistance of the UMR system and the accuracy, responsiveness, whitewashing attack resistance as well as a failure resilience of the SSR system, thus providing a better overall performance according to the application context.

Abstract In this paper, we present a simple mathematical model for studying the performance of the BitTorrent ( http://www.bittorrent.com ) file sharing system. We are especially interested in the distribution of peers in different states of the download job progress. With the model we find that the distribution of the download peers follows an asymmetric U‐shaped curve under the stable state, due to BitTorrent's unchoking strategies. In addition, we find that the seeds' departure rate and the download peers' abort rate will influence the peer distribution in different ways notably. We also analyze the content availability under the dying process of the BitTorrent file sharing system. We find that the system's stability deteriorates with decreasing and unevenly distributed online peers, and BitTorrent's built‐in ‘tit‐for‐tat’ unchoking strategy could not help to preserve the integrity of the file among the download peers. We propose an innovative ‘tit‐for‐tat’ unchoking strategy which enables more peers to finish the download job and prolongs the system's lifetime. By playing our innovative strategy, download peers could cooperate to improve the stability of the system by making a trade‐off between the current downloading rate and the future service availability. Finally, experimental results are presented to validate our analytical results and support our proposals. Copyright © 2007 John Wiley & Sons, Ltd.

Abstract The phenomenon of system churn degrades the lookup performance of distributed hash table (DHT) systems greatly. To handle the churn, a number of approaches have been proposed to date. However, there is a lack of theoretical analysis to direct how to make design choices under different churn rates and how to configure their parameters optimally. In this paper, we analytically study three important aspects on optimizing DHT lookup performance under churn, i.e. lookup strategy, lookup parallelism and lookup key replication. Our objective is to build a theoretical basis for designers to make better design choices in the future. We first compare the performance of two representative lookup strategies—recursive routing and iterative routing—and explore the existence of better alternatives. Then we study the effectiveness of lookup parallelism in systems with different churn rates and show how to select the optimal degree of parallelism. Owing to the importance of key replication on lookup performance, we also analyze the reliability of the replicated key under two different replication policies, and show how to perform proper configuration. Besides the analytical study, our results are also validated by simulation, and Kad is taken as a case to show the meaningfulness of our analysis. Copyright © 2007 John Wiley & Sons, Ltd.

As a fundamental problem in DHT-based P2P systems, load balancing is important to avoid performance degradation and guarantee system fairness. In this paper, to get a better understanding about the effectiveness of migration-based load balancing approaches in DHT systems, we analytically study two representative migration-based load balancing strategies: rendezvous directory strategy (RDS) and independent searching strategy (ISS). They differ in load information management and decision making in the process of load balancing. We analyze their performance in terms of efficiency, scalability and robustness, and explore the impact of their parameter settings. Based on the analysis results, we also propose a gossip-based strategy (GBS) for load balancing in DHT systems, which attempts to achieve the benefits of both RDS and ISS. Later, the effectiveness of GBS is evaluated by simulation under different workload and churn.

Previous studies show that more than 85% of the peers have joined multiple torrents in BitTorrent, but theoretical work on multiple files BitTorrent downloading is rare. In this paper, we first consider the scenario of multi-torrent downloading. We present a fluid-model based analysis on the multi-torrent concurrent downloading scheme, which is implicitly adopted in practical applications, and quantitatively compare its performance with an alternative scheme of multi-torrent sequential downloading. We also consider the scenario of multi-file torrent downloading (e.g. multiple files shared within a single torrent), and find that the scheme of multi-file torrent concurrent downloading, which is explicitly engaged in practical applications, is inefficient. A new scheme named collaborative multi-file torrent sequential downloading is proposed, and we show via numerical analysis that the download performance could be improved by collaboration among the peers in different subtorrents. Finally, we propose a self-adaptive mechanism for practically deploying our multi-file torrent downloading scheme in a distributed fashion under situations when correlation among the files and majority peers' behaviors are unknown

Abstract — In this paper, a simple mathematical model is presented for studying the performance of the BitTorrent [1] file sharing system. We are especially interested in the distribution of the peers with different states of the download job completedness. With the model we find that in the stable state the distribution of the download peers follows a U-shaped curve, and the parameters such as the departure rate of the seeds and the abort rate of the download peers will influence the peer distribution in different ways notably. We also analyze the file availability and the dying process of the BitTorrent file sharing system. We find that the system’s stability deteriorates with the clustering of the peers, and BitTorrent’s built-in “tit-for-tat ” unchoking strategy could not help to preserve the integrity of the file among the download peers when the size of the community is small. An innovative peer selection strategy which enables more peers to finish the download job and prolongs the system’s lifetime is proposed, in which the peers cooperate to improve the stability of the system by making a tradeoff between the current download rate and the future service availability. Finally, experimental results are presented to validate our analysis and findings. I.

In DHT-based P2P systems, the technique of "virtual server" is widely used to achieve load balance. To efficiently handle the workload skewness , "virtual servers" are allowed to migrate between nodes. Among existing migration-based load balancing strategies, there are two main categories: (I) rendezvous directory strategy (RDS) and (2) independent searching strategy (ISS). However, none of them can achieve resilience and efficiency at the same time. In this paper, we propose a gossip dissemination strategy (GDS) for load balancing in DHT systems, which attempts to achieve the benefits of both RDS and ISS. GDS doesn't rely on a few static rendezvous directories to perform load balancing. Instead, load information is disseminated within the formed groups via a gossip protocol, and each peer has enough information to act as the rendezvous directory and perform load balancing within its group. Besides intra-group balancing, inter-group balancing and emergent balancing are also supported by GDS. To further improve system resilience, the position of the rendezvous directory is randomized in each round. For a better understanding, we also perform analytical studies on GDS in terms of its scalability and efficiency under churn. Finally, the effectiveness of GDS is evaluated by extensive simulation under different workload and churn levels

The phenomenon of churn degrades the lookup performance of DHT-based P2P systems greatly. To date, a number of approaches have been proposed to handle it from both the system side and the client side. However, there lacks theoretical analysis to direct how to make design choices under different churn levels and how to configure their parameters optimally. In this paper, we analytically study three important aspects on improving DHT lookup performance under churn, i.e., lookup strategy, lookup parallelism and lookup key replication. Our objective is to build a theoretical basis for DHT designers to make better design choices in the future. We first compare the performance of two representative lookup strategies - recursive routing and iterative routing, and explore the existence of better alternatives. Then we show the effectiveness of parallel lookup in systems with different churn levels and how to select the optimal degree of parallelism. Due to the importance of key replication on lookup performance, we also analyze the reliability of replicated keys under two different replication policies, and discuss how to make configuration in different environments. Besides analytical study, our results are also validated by simulation, and Kad is taken as a case to show the meaningfulness of our analysis