In this paper we understand BitTorrent protocol from a Markov approximation perspective. We show that together with the underlying rate control algorithm, the rarest first algorithm and choking algorithm in BitTorrent protocol implicitly solve a cooperative combinatorial network utility maximization problem in a distributed manner. This understanding allows us to access properties of BitTorrent from a fresh perspective, including performance optimality, convergence and impacts of design parameters. Our numerical evaluations validate the analytical results.

In this paper, we quantify how much codes can reduce the data retrieval latency in storage systems. By combining a simple linear code with a novel request scheduling algorithm, which we call Blocking-one Scheduling (BoS), we show analytically that it is possible to use codes to reduce data retrieval delay by up to 17% over currently popular replication-based strategies. Although in this work we focus on a simplified setting where the storage system stores a single content, the methodology developed can be applied to more general settings with multiple contents. The results also offer insightful guidance to the design of storage systems in data centers and content distribution networks.

We introduce video-sync (VSYNC), a video file synchronization system that efficiently uses a bidirectional communications link to maintain up-to-date video sources at remote ends to a desired resolution and distortion level. By automatically detecting and transmitting only the differences between video files, VSYNC is able to avoid unnecessary re-transmission of the entire video when there are only minor differences between video copies. A hierarchical hashing scheme is designed to allow synchronization to within some user-defined distortion, white being rate-efficient and computationally tractable. Distributed video coding is used to realize further rate savings when transmitting video updates. VSYNC is bandwidth-efficient and is useful in many scenarios including video backup, video sharing, and video authentication applications. Experimental results show that rate-savings ranging from 2× to 10× can be obtained by VSYNC with about 10% of the frames being edited, compared to re- transmitting the compressed video or using a file synchronization utility such as rsync.

We study the problem of neighbor selection in BitTorrent-like peer-to-peer (P2P) systems, and propose a "soft-worst-neighbor-choking" algorithm that is provably optimal. In practical P2P systems, peers often keep a large set of potential neighbors, but only simultaneously upload/download to/from a small subset of them, which we call active neighbors, to avoid excessive connection overhead. A natural question to ask is: which active neighbor set should each peer choose to maximize the global system performance? The combinatorial nature of the problem makes it especially challenging. In this paper, we formulate an optimization problem and derive a distributed algorithm. We remark that our solution has a similar favor compared to the worst neighbor choking and optimistic unchoking neighbor selection algorithms that are implemented by BitTorrent. However, it encourages peers to stick to better performing neighbors for longer time and is provably globally optimal. Our proposed solution is easy to implement: each peer periodically waits for a constant period of time that depends on the size of the potential neighbor set and the aggregated utility of the active neighbors, chokes (drops) one of its current active neighbors with probability proportional to an exponential weight on the utility of the corresponding link, and randomly unchokes (adds) a new neighbor from its potential neighbor set. Our theoretical findings provide insightful guidelines to designing practical P2P systems. Simulation results corroborate our proposed solution.

We investigate the design of a frame-bufferless and low-latency video communication system, where the encoder has no access to any previous frames and only one use of feedback communication from the decoder to the encoder is allowed in encoding each frame. This strict requirement on encoder complexity and system latency is of critical importance in designing low complexity realtime video communication systems, where the encoder is limited in storage and computing resources and the use of the feedback channel must not incur accumulated receiver playback delay. We propose a simple online statistical model that captures the time-varying video process and develop a general framework that explores how to best utilize the feedback and distributed source coding mechanisms to minimize the overall communication rate. Our analysis and experimental results validate the efficiency of the proposed system and highlight its potential in practical system design.

We investigate a practical approach to solving one instantiation of a distributed hypothesis testing problem under severe rate constraints that shows up in a wide variety of applications such as camera calibration, biometric authentication and video hashing: given two distributed continuous-valued random sources, determine if they satisfy a certain Euclidean distance criterion. We show a way to convert the problem from continuous-valued to binary-valued using binarized random projections and obtain rate savings by applying a linear syndrome code. In finding visual correspondences, our approach uses just 49% of the rate of scalar quantization to achieve the same level of retrieval performance. To perform video hashing, our approach requires only a hash rate of 0.0142 bpp to identify corresponding groups of pictures correctly.

Video file synchronization between remote users is an important task in many applications. Re-transmission of a video that has been only slightly modified is expensive, wasteful and avoidable. We propose a scheme that automatically detects and sends only modified content according to some user defined distortion constraint to enable rate savings under a wide range of video edits. Through the use of a low-rate hierarchical hashing scheme, we can detect modifications with some spatial granularity. We also apply distributed source coding techniques to exploit correlation between remote copies for a further rate rebate. Experimental results show that the proposed approach achieves up to 7times rate reduction when compared to re-transmitting.

The throughput of Peer-to-Peer (P2P) Video-on-Demand (VoD) systems is typically capped by the users' aggregate upload bandwidth [1]. The drastic increase in the popularity of VoD and the demand of higher quality content has thus placed substantial burden on the content servers. We investigate a novel P2P VoD architecture that leverages idle Internet resources, which we call helpers, to provide a scalable solution to P2P VoD systems. Helpers are volatile in nature, and can be individually unreliable. However, we investigate the statistical aggregation of a large number of helpers to guarantee quality of service. Since helpers do not come with ¿free¿ preloaded content, trade-offs between how much a helper should download and how much it can aid the system need to be explored. In this paper, the optimal steady-state design parameters are derived to maximize the helpers' upload bandwidth utilization. Packet level simulations have verified the efficiency of the system. In a typical scenario of 240 users and a required theoretical minimum of 120 helpers with an average upload bandwidth of 256 kbps, a streaming rate of 384 kbps can be sustained with < 2% relative server load. Results also show that the system is robust to helper churn.

We propose a decentralized Peer-to-Peer (P2P) Video-on-Demand (VoD) system. The traditional data center architecture is eliminated and is replaced by a large set of distributed, dynamic and individually unreliable helpers. The system leverages the strength of numbers to effect reliable cooperative content distribution, removing the drawbacks of conventional data center architectures including complexity of maintenance, high power consumption and lack of scalability. In the proposed VoD system, users and helper ldquoserveletsrdquo cooperate in a P2P manner to deliver the video stream. Helpers are preloaded with only a small fraction of parity coded video data packets, and form into swarms each serving partial video content. The total number of helpers is optimized to guarantee high quality of service. In cases of helper churn, the helper network is also able to regenerate itself by users and helpers working cooperatively to repair the lost data, which yields a highly reliable system. Analysis and simulation results corroborate the feasibility and effectiveness of the proposed architecture.

VSYNC is a novel incremental video file synchronization system that efficiently synchronizes two video files at remote ends through a bi-directional communications link. Retransmission of a video file that has been modified only slightly, for the purpose of synchronization with a remote-end copy, is extremely expensive but avoidable. VSYNC is a bi-directional algorithm designed to automatically detect and transmit changes in the modified video file without the knowledge of what was changed. Another feature of VSYNC is that it allows synchronization to within some user defined distortion constraint. A hierarchical hashing scheme is designed to compare video chunks, converting the high-level content information to a low-level hash stream that is more amenable to the tools of coding theory. Our approach shows impressive gains in transmission rate-savings. In a typical example of two 12 sec video files with about 10% of the frames being edited, transmission savings of 44% to 87% can be obtained compared to directly sending the updated video files using H.264 and rsync [1].