HTML socket streams, such as XHR-polling and HTML5 websockets, are being rapidly embraced because they operate over HTTP(S) protocols and ports, allowing them to easily traverse security firewalls and HTTP proxies, unlike raw TCP streams. This paper presents an active measurement study of these protocols and compares their performance to raw TCP. Our results indicate that HTML socket streams impose significant performance penalties with respect to protocol overhead (up to 5×), data payload delivery delay (up to 3× more), and throughput (up to 3× less). The performance divide between HTML socket streams and TCP is particularly severe for the more important case of small data payload sizes (100s of bytes). Moreover, our results demonstrate the HTML socket streams introduce higher jitter as compared to TCP streams. Our experiments indicate that the real-time capabilities of HTML socket streams are significantly poorer than TCP streams, particularly over 3G cellular data Internet connections.

We examine the problem of minimizing feedback in reliable wireless broadcasting by pairing rateless coding with extreme value theory. Our key observation is that, in a broadcast environment, this problem resolves into estimating the maximum number of packets dropped among many receivers rather than for each individual receiver. With rateless codes, this estimation relates to the number of redundant transmissions needed at the source in order for all receivers to correctly decode a message with high probability. We develop and analyze two new data dissemination protocols, called Random Sampling (RS) and Full Sampling with Limited Feedback (FSLF), based on the moment and maximum likelihood estimators in extreme value theory. Both protocols rely on a single-round learning phase, requiring the transmission of a few feedback packets from a small subset of receivers. With fixed overhead, we show that FSLF has the desirable property of becoming more accurate as the receivers' population gets larger. Our protocols are channel-agnostic, in that they do not require a priori knowledge of (i.i.d.) packet loss probabilities, which may vary among receivers. We provide simulations and an improved full-scale implementation of the Rateless Deluge over-the-air programming protocol on sensor motes as a demonstration of the practical benefits of our protocols, which translate into about 30% latency and energy consumption savings. Furthermore, we apply our protocols to real-time (RT) oblivious rateless codes in broadcast settings. Through simulations, we demonstrate a 100-fold reduction in the amount of feedback packets while incurring an increase of only 10%–20% in the number of encoded packets transmissions.

We propose a coding-based solution to mitigate the disruption during switching from unicast to broadcast wireless channels while streaming live video to mobile devices. Our solution, based on unequal error protection principles, takes advantage of side information about the switching time available at the encoder. In particular, we present a method to distribute error protection unequally among the input packets based on their temporal position in the video stream and on the switching time distribution. We implement our proposed encoder and decoder in Matlab and compare the proposed scheme to LT codes and to the naive approach of not using coding at all. Our experiments indicate that our approach results in approximately 8% improvement over plain LT coding and about 20% improvement over a no coding approach.

This paper explores the effect of varying peers' local cache sizes on user perceived video quality in Video-on-Demand p2p streaming. First, we ascertain the relationship between the average video distortion on peers and peer cache size. Second, we analyze the aggregate access network usage of uplink bandwidth for different peer cache sizes. Finally, we measure the p2p server bandwidth usage as the peer cache size is changed. After finding analytical fits to these three functions we compute the optimal peer cache size that minimizes the total cost of p2p VoD video streaming. Our extensive simulations highlight the key role peer cache sizes play in the interplay between the video quality delivered to users and the amounts of p2p server and peer bandwidth usage. Subsequent data analysis provided in this work presents a framework for computing an optimum operating point for p2p VoD systems in terms of server and peer bandwidth required.

We examine the problem of minimizing feedbacks in reliable wireless broadcasting, by pairing rateless coding with extreme value theory. Our key observation is that, in a broadcast environment, this problem resolves into estimating the maximum number of packets dropped among many receivers rather than for each individual receiver. With rateless codes, this estimation relates to the number of redundant transmissions needed at the source in order for all receivers to correctly decode a message with high probability. We develop and analyze two new data dissemination protocols, called Random Sampling (RS) and Full Sampling with Limited Feedback (FSLF), based on the moment and maximum likelihood estimators in extreme value theory. Both protocols rely on a single-round learning phase, requiring the transmission of a few feedback packets from a small subset of receivers. With fixed overhead, we show that FSLF has the desirable property of becoming more accurate as the receivers's population gets larger. Our protocols are channel agnostic, in that they do not require a-priori knowledge of (i.i.d.) packet loss probabilities, which may vary among receivers. We provide simulations and an improved full-scale implementation of the Rateless Deluge over-the-air programming protocol on sensor motes as a demonstration of the practical benefits of our protocols, which translate into about 30% latency and energy consumption savings.

We analyze two commercial peer-to-peer (P2P) video streaming systems via active measurements: a tree-based overlay multicast and a mesh-based overlay. Our controlled IP test-bed allows us to reproduce near-identical network conditions for both the systems and to test them under varying network conditions and peer behavior. We report on the bandwidth efficiency of these P2P video streaming systems under different network conditions and on how these systems adapt to heterogeneous networks and peer behavior. Our results include quality-of-service information in terms of the fraction of the total video stream received by each peer for live playback. We also report the server bandwidth versus P2P bandwidth consumed by the system under different conditions. The dynamic behavior of the P2P video streaming systems is captured via measuring the size of interactions (bytes downloaded) among peers. Finally we report the correlation between the underlying traffic-shaped bandwidth assigned to a peer and the actual amount of P2P data uploaded by the peer. Our analysis shows that the mesh-based overlay mimics the underlying IP network more closely than the tree-based overlay, indicating that the former is more network aware. On the other hand, the tree-based system is more efficient in bandwidth usage.

The erasure resilience of rateless codes, such as Luby-Transform (LT) codes, makes them particularly suitable to a wide variety of loss-prone wireless and sensor network applications, ranging from digital video broadcast to software updates. Yet, traditional rateless codes usually make no use of a feedback communication channel, a feature available in many wireless settings. As such, we generalize LT codes to situations where receiver(s) provide feedback to the broadcaster. Our approach, referred to as Shifted LT (SLT) code, modifies the robust soliton distribution of LT codes at the broadcaster, based on the number of input symbols already decoded at the receivers. While implementing this modification entails little change to the LT encoder and decoder, we show both analytically and through real experiments, that it achieves significant savings in communication complexity, memory usage, and overall energy consumption. Furthermore, we show that significant savings can be even achieved with a low number of feedback messages (on the order of the square root of the total number of input symbols) transmitted at a uniform rate. The practical benefits of Shifted LT codes are demonstrated through the implementation of a real over-the-air programming application for sensor networks, based on the Deluge protocol.

We design a test methodology to analyze in detail the video quality received at each peer in a peer-to-peer (P2P) video streaming system. The metrics that we employ at each peer include video PSNR, statistical analysis of frame-freeze events, the amount of time to wait before video playback starts, nature of the data-paths established to serve the peer, protocol overhead and duplicate data received. These metrics are estimated by analyzing the packet reception times at each peer and utilizing information about the original uncompressed video as well as the encoded video. We use this framework to compare the performance of three P2P video streaming systems by deploying them on our controlled traffic-shaped network test-bed. We can emulate the same network conditions and peer behavior for testing different systems and ensure that the experiments are repeatable. These measurements highlight the differences between systems based upon their underlying implementation, overlay architecture, and choice of protocols. This measurement study helps to gauge the performance of currently available P2P video streaming systems and points out desirable performance improvements.

We evaluate the performance of a large-scale live P2P video multicast session comprising more than 120, 000 peers on the Internet. Our analysis highlights P2P video multicast characteristics such as high bandwidth requirements, high peer churn, low peer persistence in the P2P multicast system, significant variance in the media stream quality delivered to peers, relatively large channel start times, and flash crowd effects of popular video content. Our analysis also indicates that peers are widely spread across the IP address space, spanning dozens of countries and hundreds of ISPs and Internet ASes. As part of the P2P multicast evaluation several QoS measures such as fraction of stream blocks correctly received, number of consecutive stream blocks lost, and channel startup time across peers. We correlate the observed quality with the underlying network and with peer behavior, suggesting several avenues for optimization and research in P2P video multicast systems.

We consider the problem of efficiently broadcasting incremental updates to multiple terminals that contain outdated (and possibly different) initial copies of the data. This situation occurs, for example, with the broadcast of Short Messaging Service [SMS] or Multimedia Messaging Service [MMS] cellphone messages to various clients whose phones are sometimes unavailable. We propose an efficient protocol for effecting such broadcast based on a novel combination of recent work on rate less coding and set reconciliation. Our approach is non-interactive, in that terminal nodes need not send any messages to the source, and stateless, in that the source need not know (or store) any information about the terminals. It also minimizes communication complexity and energy expenditure at the terminal nodes, at the expense of added computation. In support of our work, we provide several energy usage measurements on MICA2 sensor motes that clearly highlight the advantages of random linear decoding over wholesale data transfer.

This paper presents an expert peering system for information exchange in the knowledge society. Our system realizes an intelligent, real-time search engine for enterprise Intranets or online communities that automatically relays user queries to knowledgable specialists. According to its very nature, the system requires a sound integration of concepts drawn from various areas of Computer Science. In addition to our solutions to problems in scalable processing, data transfer, and networking, we also address issues of interface design and usability, as well as aspects of machine intelligence. Results obtained from extensive experiments demonstrate the efficiency and robustness of our system and convey its potential for next generation web services.

We propose a peer-to-peer architecture designed to overcome asymmetries in upload/download speeds that are typical in end-user dialup, broadband and cellular wireless Internet connections. Our approach allows users at remote locations to access information stored on their home computers at rates often exceeding their home connection’s upload capacity. The key to this approach is to share file data when communications are idle using random linear coding, so that, when needed, an end-user can download a file from several sources at a higher data rate than his home computer’s upload capacity. We prove that our proposed system is asymptotically fair, in that (even malicious) users are proportionally assigned idle bandwidth depending on how much bandwidth they contribute, and that there is a natural incentive to join and cooperate fairly in the system. In addition, our approach provides cryptographic security and geographic data robustness to the participating peers.

Peer-to-peer (P2P) systems are becoming a popular means of streaming audio and video content but they are prone to bandwidth starvation if selfish peers do not contribute bandwidth to other peers. We prove that an incentive mechanism can be created for a live streaming P2P protocol while preserving the asymptotic properties of randomized gossip based streaming without any incentives. In order to show the utility of our result, we adopt a distributed incentive scheme from P2P file storage literature to the live streaming scenario. We provide simulation results that confirm the ability to achieve a constant download rate (in time, per peer) that is needed for streaming applications on peers. The incentive scheme fairly differentiates peers' download rates according to how much useful bandwidth they contribute back to the P2P system, thus creating a powerful quality of service incentive for peers to contribute bandwidth to other peers. In addition we provide preliminary data from a real implementation of a gossip based streaming application

We consider the problem of approximating the number of differences between sets held on remote hosts using minimum communication. Efficient solutions to this problem are important for streamlining a variety of communication sensitive network applications, including data synchronization in mobile networks, gossip protocols and content delivery networks. Using tools from the field of interactive communication, we show that this problem requires about as much communication as the problem of exactly determining such differences. As a result, we propose a heuristic solution based on the counting Bloom filter. We provide analytic bounds on the expected performance of our protocol and also experimental evidence that they can outperform existing difference approximation techniques.

Of considerable interest in recent years has been the problem of exchanging correlated data with minimum communication. We thus consider the problem of exchanging two similar strings held by different hosts. Our approach involves transforming a string into a multiset of substrings that are reconciled efficiently using known multiset reconciliation algorithms, and then put back together on a remote host using tools from graph theory. We present analyses, experiments, and results to show that the communication complexity of our approach for high-entropy data compares favorably to existing algorithms including rsync, a widely-used string reconciliation engine. We also quantify the trade-off between communication and the computation complexity of our approach

Modern personal digital assistant (PDA) architectures often utilize a wholesale data transfer protocol known as "slow sync" for synchronizing PDAs with personal computers (PCs). This approach is markedly inefficient with respect to bandwidth usage, latency, and energy consumption since the PDA and PC typically share many common records. We propose, analyze, and implement a novel PDA synchronization scheme (CPIsync) predicated upon previous information-theoretic research. The salient property of this scheme is that its communication complexity depends on the number of differences between the PDA and PC, and is essentially independent of the overall number of records. Moreover, our implementation shows that the computational complexity and energy consumption of CPIsync is practical and that the-overall latency is typically much smaller than that of slow sync or alternative synchronization approaches based on Bloom (1970) filters. Thus, CPIsync has potential for significantly improving synchronization protocols for PDAs and, more generally, for heterogeneous networks of many machines.

Modern personal digital assistant (PDA) architectures often utilize a wholesale data transfer protocol known as "slow sync" for synchronizing PDAs with personal computers (PCs). This approach is markedly inefficient with respect to bandwidth usage and latency, since the PDA and PC typically share many common records. We propose, analyze, and implement a novel PDA synchronization scheme (CPIsync - characteristic polynomial interpolation-based synchronization) predicated upon recent information-theoretic research. The salient property of this scheme is that its communication complexity depends on the number of differences between the PDA and PC, and is essentially independent of the overall number of records. Moreover, our implementation shows that the computational complexity of CPIsync is practical, and that the overall latency is typically much smaller than that of slow sync. Thus, CPIsync has potential for significantly improving synchronization protocols for PDAs and, more generally, for heterogeneous networks of many machines.