Designing effective reasoning-capable LLMs typically requires training using Reinforcement Learning with Verifiable Rewards (RLVR) or distillation with carefully curated Long Chain of Thoughts (CoT), both of which depend heavily on extensive training data.This creates a major challenge when the amount of quality training data is scarce.We propose a sampleefficient, two-stage training strategy to develop reasoning LLMs under limited supervision.In the first stage, we "warm up" the model by distilling Long CoTs from a toy domain, namely, Knights & Knaves (K&K) logic puzzles to acquire general reasoning skills.In the second stage, we apply RLVR to the warmed-up model using a limited set of target-domain examples.Our experiments demonstrate that this two-phase approach offers several benefits: (i) the warmup phase alone facilitates generalized reasoning, leading to performance improvements across a range of tasks, including MATH, HumanEval + , and MMLU-Pro; (ii) When both the base model and the warmed-up model are RLVR trained on the same small dataset (≤ 100 examples), the warmed-up model consistently outperforms the base model; (iii) Warming up before RLVR training allows a model to maintain cross-domain generalizability even after training on a specific domain; (iv) Introducing warmup in the pipeline improves not only accuracy but also overall sample efficiency during RLVR training.The results in this paper highlight the promise of warmup for building robust reasoning LLMs in data-scarce environments.

Recently, it has been shown that for offline deep reinforcement learning (DRL), pre-training Decision Transformer with a large language corpus can improve downstream performance (Reid et al., 2022). A natural question to ask is whether this performance gain can only be achieved with language pre-training, or can be achieved with simpler pre-training schemes which do not involve language. In this paper, we first show that language is not essential for improved performance, and indeed pre-training with synthetic IID data for a small number of updates can match the performance gains from pre-training with a large language corpus; moreover, pre-training with data generated by a one-step Markov chain can further improve the performance. Inspired by these experimental results, we then consider pre-training Conservative Q-Learning (CQL), a popular offline DRL algorithm, which is Q-learning-based and typically employs a Multi-Layer Perceptron (MLP) backbone. Surprisingly, pre-training with simple synthetic data for a small number of updates can also improve CQL, providing consistent performance improvement on D4RL Gym locomotion datasets. The results of this paper not only illustrate the importance of pre-training for offline DRL but also show that the pre-training data can be synthetic and generated with remarkably simple mechanisms.

Recently it has been observed that neural networks exhibit Neural Collapse (NC) during the final stage of training for the classification problem. We empirically show that multivariate regression, as employed in imitation learning and other applications, exhibits Neural Regression Collapse (NRC), a new form of neural collapse: (NRC1) The last-layer feature vectors collapse to the subspace spanned by the $n$ principal components of the feature vectors, where $n$ is the dimension of the targets (for univariate regression, $n=1$); (NRC2) The last-layer feature vectors also collapse to the subspace spanned by the last-layer weight vectors; (NRC3) The Gram matrix for the weight vectors converges to a specific functional form that depends on the covariance matrix of the targets. After empirically establishing the prevalence of (NRC1)-(NRC3) for a variety of datasets and network architectures, we provide an explanation of these phenomena by modeling the regression task in the context of the Unconstrained Feature Model (UFM), in which the last layer feature vectors are treated as free variables when minimizing the loss function. We show that when the regularization parameters in the UFM model are strictly positive, then (NRC1)-(NRC3) also emerge as solutions in the UFM optimization problem. We also show that if the regularization parameters are equal to zero, then there is no collapse. To our knowledge, this is the first empirical and theoretical study of neural collapse in the context of regression. This extension is significant not only because it broadens the applicability of neural collapse to a new category of problems but also because it suggests that the phenomena of neural collapse could be a universal behavior in deep learning.

We propose VRL3, a powerful data-driven framework with a simple design for solving challenging visual deep reinforcement learning (DRL) tasks. We analyze a number of major obstacles in taking a data-driven approach, and present a suite of design principles, novel findings, and critical insights about data-driven visual DRL. Our framework has three stages: in stage 1, we leverage non-RL datasets (e.g. ImageNet) to learn task-agnostic visual representations; in stage 2, we use offline RL data (e.g. a limited number of expert demonstrations) to convert the task-agnostic representations into more powerful task-specific representations; in stage 3, we fine-tune the agent with online RL. On a set of challenging hand manipulation tasks with sparse reward and realistic visual inputs, compared to the previous SOTA, VRL3 achieves an average of 780% better sample efficiency. And on the hardest task, VRL3 is 1220% more sample efficient (2440% when using a wider encoder) and solves the task with only 10% of the computation. These significant results clearly demonstrate the great potential of data-driven deep reinforcement learning.

We develop theory and algorithms for average-reward on-policy Reinforcement Learning (RL). We first consider bounding the difference of the long-term average reward for two policies. We show that previous work based on the discounted return (Schulman et al. 2015, Achiam et al. 2017) results in a non-meaningful lower bound in the average reward setting. By addressing the average-reward criterion directly, we then derive a novel bound which depends on the average divergence between the policies and on Kemeny’s constant. Based on this bound, we develop an iterative procedure which produces a sequence of monotonically improved policies for the average reward criterion. This iterative procedure can then be combined with classic Deep Reinforcement Learning (DRL) methods, resulting in practical DRL algorithms that target the long-run average reward criterion. In particular, we demonstrate that Average-Reward TRPO (ATRPO), which adapts the on-policy TRPO algorithm to the average-reward criterion, significantly outperforms TRPO in the most challenging MuJuCo environments.

We aim to develop off-policy DRL algorithms that not only exceed state-of-the-art performance but are also simple and minimalistic. For standard continuous control benchmarks, Soft Actor-Critic (SAC), which employs entropy maximization, currently provides state-of-the-art performance. We first demonstrate that the entropy term in SAC addresses action saturation due to the bounded nature of the action spaces, with this insight, we propose a streamlined algorithm with a simple normalization scheme or with inverted gradients. We show that both approaches can match SAC’s sample efficiency performance without the need of entropy maximization, we then propose a simple non-uniform sampling method for selecting transitions from the replay buffer during training. Extensive experimental results demonstrate that our proposed sampling scheme leads to state of the art sample efficiency on challenging continuous control tasks. We combine all of our findings into one simple algorithm, which we call Streamlined Off Policy with Emphasizing Recent Experience, for which we provide robust public-domain code.

In reinforcement learning, an agent attempts to learn high-performing behaviors through interacting with the environment, such behaviors are often quantified in the form of a reward function. However some aspects of behavior—such as ones which are deemed unsafe and to be avoided—are best captured through constraints. We propose a novel approach called First Order Constrained Optimization in Policy Space (FOCOPS) which maximizes an agent's overall reward while ensuring the agent satisfies a set of cost constraints. Using data generated from the current policy, FOCOPS first finds the optimal update policy by solving a constrained optimization problem in the nonparameterized policy space. FOCOPS then projects the update policy back into the parametric policy space. Our approach has an approximate upper bound for worst-case constraint violation throughout training and is first-order in nature therefore simple to implement. We provide empirical evidence that our simple approach achieves better performance on a set of constrained robotics locomotive tasks.

There has recently been a surge in research in batch Deep Reinforcement Learning (DRL), which aims for learning a high-performing policy from a given dataset without additional interactions with the environment. We propose a new algorithm, Best-Action Imitation Learning (BAIL), which strives for both simplicity and performance. BAIL learns a V function, uses the V function to select actions it believes to be high-performing, and then uses those actions to train a policy network using imitation learning. For the MuJoCo benchmark, we provide a comprehensive experimental study of BAIL, comparing its performance to four other batch Q-learning and imitation-learning schemes for a large variety of batch datasets. Our experiments show that BAIL's performance is much higher than the other schemes, and is also computationally much faster than the batch Q-learning schemes.

We deploy GPS hacking in conjunction with location-based mobile apps to passively survey users in targeted geographical regions. Specifically, we investigate surveying students at different college campuses with Yik Yak, an anonymous mobile app that is popular on US college campuses. In addition to being campus centric, Yik Yak’s anonymity allows students to express themselves candidly without self-censorship. We collect nearly 1.6 million Yik Yak messages (“yaks”) from a diverse set of 45 college campuses in the United States. We use natural language processing to determine the sentiment (positive, negative, or neutral) of all of the yaks. We employ supervised machine learning to predict the gender of the authors of the yaks and then analyze how sentiment differs among the two genders on college campuses. We also use supervised machine learning to classify all the yaks into nine topics and then investigate which topics are most popular throughout the US and how topic popularity varies on the different campuses. The results in this article provide significant insight into how campus culture and student’s thinking varies among US colleges and universities.

Abstract Due to the recent “Right to be Forgotten” (RTBF) ruling, for queries about an individual, Google and other search engines now delist links to web pages that contain “inadequate, irrelevant or no longer relevant, or excessive” information about that individual. In this paper we take a data-driven approach to study the RTBF in the traditional media outlets, its consequences, and its susceptibility to inference attacks. First, we do a content analysis on 283 known delisted UK media pages, using both manual investigation and Latent Dirichlet Allocation (LDA). We find that the strongest topic themes are violent crime, road accidents, drugs, murder, prostitution, financial misconduct, and sexual assault. Informed by this content analysis, we then show how a third party can discover delisted URLs along with the requesters’ names, thereby putting the efficacy of the RTBF for delisted media links in question. As a proof of concept, we perform an experiment that discovers two previously-unknown delisted URLs and their corresponding requesters. We also determine 80 requesters for the 283 known delisted media pages, and examine whether they suffer from the “Streisand effect,” a phenomenon whereby an attempt to hide a piece of information has the unintended consequence of publicizing the information more widely. To measure the presence (or lack of presence) of a Streisand effect, we develop novel metrics and methodology based on Google Trends and Twitter data. Finally, we carry out a demographic analysis of the 80 known requesters. We hope the results and observations in this paper can inform lawmakers as they refine RTBF laws in the future.

Abstract Location‐based social discovery (LBSD) services enable users to discover their geographic neighborhoods to make new friends. Original LBSD services were designed to provide the exact distances to nearby users. It has been shown that it is easy to pinpoint any target user's location by using trilateration based on the exact distances from three fake Global Positioning System locations to the target user. To defend against the trilateration attack, contemporary LBSD services then began to report distances of nearby users in concentric bands, for example, bands of 100 meters, rather than exact distances. In this paper, we investigate the user location privacy leakage problem in LBSD services reporting distances in discrete bands. Using number theory, we analytically show that by strategically placing multiple virtual probes with fake Global Positioning System locations, one can nevertheless localize user locations in band‐based LBSD. Our methodology is guaranteed to localize any reported user within a circle of radius no greater than one meter, even for LBSD services using large bands (such as 100 m as used by WeChat). Eventually, countermeasures are proposed to reduce location privacy leakage to the very minimum. To the best of our knowledge, this is the first work that explicitly exploits and quantifies user location privacy leakage in band‐based LBSD services. We expect our study to draw more public attention to this serious privacy issue and expectantly motivate better privacy preserving LBSD designs. Copyright © 2016 John Wiley & Sons, Ltd.

Children's online privacy has garnered much attention in media, legislation, and industry. Adults are concerned that children may not adequately protect themselves online. However, relatively little discussion has focused on the privacy breaches that may occur to children at the hands of others, namely, their parents and relatives. When adults post information online, they may reveal personal information about their children to other people, online services, data brokers, or surveillant authorities. This information can be gathered in an automated fashion and then linked with other online and offline sources, creating detailed profiles which can be continually enhanced throughout the children's lives.

These keynote discusses the following: Big Data Science and Social Networks - Accelerating Insights and Building Value; Sampling Theory of Large Networks; Mining Online Social Networks: Opportunities and Privacy Issues.

Lawmakers, children's advocacy groups and modern society at large recognize the importance of protecting the Internet privacy of minors (under 18 years of age). Online Social Networks, in particular, take precautions to prevent third parties from using their services to discover and profile minors. These precautions include displaying only minimal information in registered minors' public profiles, not listing minors when searching for users by high school or city, and banning young children from joining altogether. In this paper we show how an attacker can circumvent these precautions. We develop efficient crawling and data mining methodologies to discover and profile most of the high school students in a targeted high school. In particular, using Facebook and for a given target high school, the methodology finds most of the students in the school, and for each discovered student infers a profile that includes significantly more information than is available in a registered minor's public profile. Such profiles can be used for many nefarious purposes, including selling the profiles to data brokers, large-scale automated spear-phishing attacks on minors, as well as physical safety attacks such as stalking, kidnapping and arranging meetings for sexual abuse. Ironically, the Children's Online Privacy Protection Act (COPPA), a law designed to protect the privacy of children, indirectly facilitates the approach. In order to bypass restrictions put in place due to the COPPA law, some children lie about their ages when registering, which not only increases the exposure for themselves but also for their non-lying friends. Our analysis strongly suggests there would be significantly less privacy leakage if Facebook did not have age restrictions.

In dynamic streaming, a user can dynamically choose from different versions of the same video. In P2P dynamic streaming, there is one P2P swarm for each version, and within a swarm, peers can share video chunks with each other, thereby reducing the server's bandwidth cost. Due to economy of scale, cooperation among peers can also reduce the per-peer content price. In this paper, we use cooperative game theory to dynamically assign each peer to a version. To maximally incentivize peer cooperation, we use mechanism design to develop pricing schemes that reflect content and bandwidth cost savings derived from peer cooperation. With this approach, each peer is assigned to a swarm that is commensurate with its upload contribution and the price it is willing to pay. We also develop and simulate a distributed dynamic P2P streaming algorithm, consisting of chunk scheduling, token-based accounting, and video version switching, to dynamically adjust each peer's video version based on the collaborative behaviors of all peers.

Adaptive streaming, such as Dynamic Adaptive Streaming over HTTP (DASH), has been widely deployed to provide uninterrupted video streaming service to users with dynamic network conditions. In this paper, we analytically study the potential of using P2P in conjunction with adaptive streaming. We first study the capacity of P2P adaptive streaming by developing utility maximization models that take into account peer heterogeneity, taxation-based incentives, multi-version videos at discrete rates. We further develop stochastic models to study the performance of P2P adaptive streaming in face of bandwidth variations and peer churn. Through analysis and simulations, we demonstrate that incentive-compatible video sharing between peers can be easily achieved with simple video coding and distribution designs. P2P adaptive streaming not only significantly reduces the load on the servers, but also improves the stability of user-perceived video quality in the face of dynamic bandwidth changes.

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 study to quantify just how severe the privacy leakage problem is in Facebook. As a case study, we focus on estimating birth year, which is a fundamental human attribute and, for many people, a private one. Specifically, we attempt to estimate the birth year of over 1 million Facebook users in New York City. We examine the accuracy of estimation procedures for several classes of users: (i) highly private users, who do not make their friend lists public; (ii) users who hide their birth years but make their friend lists public. To estimate Facebook users' ages, we exploit the underlying social network structure to design an iterative algorithm, which derives age estimates based on friends' ages, friends of friends' ages, and so on. We find that for most users, including highly private users who hide their friend lists, it is possible to estimate ages with an error of only a few years. We also make a specific suggestion to Facebook which, if implemented, would greatly reduce privacy leakages in its service.

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.

This paper explores the incentive schemes that have been used by cyberlockers, and examines to what extent they have helped to foster the current environment. This short paper also presents a preliminary economic analysis of incentives in cyberlockers based on measurement results from three different types of sites related to cyberlockers- a search engine, a discussion forum, and a popular cyberlocker site.

User Generated Content (UGC) video applications, such as YouTube, are enormously popular. UGC systems can potentially reduce their distribution costs by allowing peers to store and redistribute the videos that they have seen in the past. We study peer-assisted UGC from three perspectives. First, we undertake a measurement study of the peer-assisted distribution system of Tudou (a popular UGC network in China), revealing several fundamental characteristics that models need to take into account. Second, we develop analytical models for peer-assisted distribution of UGC. Our models capture essential aspects of peer-assisted UGC systems, including system size, peer bandwidth heterogeneity, limited peer storage, and video characteristics. We apply these models to numerically study YouTube-like UGC services. And third, we develop analytical models to understand the rate at which users would install P2P client applications to make peer-assisted UGC a success. Our results provide a comprehensive study of peer-assisted UGC distribution, exposing its fundamental characteristics and limitations.

The convergence of games and online social platforms is an exploding phenomena. The continued success of social games hinges critically on the ability to deliver smooth and highly-interactive experiences to end-users. However, it is extremely challenging to satisfy the stringent performance requirements of online social games.

We study a natural and potentially devastating attack against BitTorrent, namely, attacking the initial seed in a torrent's early stages. The goal of this attack is to diminish the seed's ability to upload blocks. If the attacker can discover and react quickly enough to the new torrent, it can possibly "nip the torrent in its bud," preventing all of the leechers from obtaining the entire file. We consider two natural seed attacks: the bandwidth attack and the connection attack. We take a three-prong approach to analyze these attacks. First, we actually launch and measure the attacks using popular BitTorrent seeds (Azureus, uTorrent, and BitTornado). To this end, because we do not want to interfere with torrents in the wild, we have created our own private torrents within PlanetLab. Second, to gain insight into our empirical results, we carefully analyze the connection management and seeding algorithms in open-source BitTorrent seeds. Third, we construct a simple fluid model which provides additional insights into the empirical results. We have discovered that the three BitTorrent seeds investigated are quite resilient to such an attack. The observations and conclusions in this paper can help P2P developers design highly-resilient P2P systems.

YouTube uploaders are the central agents in the YouTube phenomenon. We conduct extensive measurement and analysis of YouTube uploaders. We estimate YouTube scale and examine the uploading behavior of YouTube users. We demonstrate the positive reinforcement between on-line social behavior and uploading behavior. Furthermore, we examine whether YouTube users are truly broadcasting themselves, via characterizing and classifying videos as either user generated or user copied.

In this paper, we show how to exploit real-time communication applications to determine the IP address of a targeted user. We focus our study on Skype, although other real-time communication applications may have similar privacy issues. We first design a scheme that calls an identified-targeted user inconspicuously to find his IP address, which can be done even if he is behind a NAT. By calling the user periodically, we can then observe the mobility of the user. We show how to scale the scheme to observe the mobility patterns of tens of thousands of users. We also consider the linkability threat, in which the identified user is linked to his Internet usage. We illustrate this threat by combining Skype and BitTorrent to show that it is possible to determine the filesharing usage of identified users. We devise a scheme based on the identification field of the IP datagrams to verify with high accuracy whether the identified user is participating in specific torrents. We conclude that any Internet user can leverage Skype, and potentially other real-time communication systems, to observe the mobility and filesharing usage of tens of millions of identified users.

To optimize network performance, cloud service providers have a number of options available to them, including co-locating production servers in well-connected Internet eXchange (IX) points, deploying data centers in additional locations, or contracting with external Content Distribution Networks (CDNs). Some of these options can be very costly, and some may or may not improve performance significantly. Cloud service providers would clearly like to be able to estimate a priori performance gain of the various options before sinking significant capital expenditures into major infrastructure changes. In this paper we take a measurement-oriented approach and develop methodologies that accurately predict the performance improvement for making major infrastructure changes. Our methodologies leverage active web content, existing large-scale CDN infrastructures, and the SpeedTest network. We then apply our methodologies and a CloudBeacon tool to the problem of locating satellite data centers throughout the world. The results show that for North America, a deployment limited to 11 locations will be sufficient. However, in order to provide good latency and throughput performance on a global scale, somewhere between a total of 36 and 72 cloud-service locations with good peering connections is most likely needed.

BitTorrent is the most successful open Internet application for content distribution. Despite its importance, both in terms of its footprint in the Internet and the influence it has on emerging P2P applications, the BitTorrent Ecosystem is only partially understood. We seek to provide a nearly complete picture of the entire public BitTorrent Ecosystem. To this end, we crawl five of the most popular torrent-discovery sites over a ine-month period, identifying all of 4.6 million and 38,996 trackers that the sites reference. We also develop a high-performance tracker crawler, and over a narrow window of 12 hours, crawl essentially all of the public Ecosystem's trackers, obtaining peer lists for all referenced torrents. Complementing the torrent-discovery site and tracker crawling, we further crawl Azureus and Mainline DHTs for a random sample of torrents. Our resulting measurement data are more than an order of magnitude larger (in terms of number of torrents, trackers, or peers) than any earlier study. Using this extensive data set, we study in-depth the Ecosystem's torrent-discovery, tracker, peer, user behavior, and content landscapes. For peer statistics, the analysis is based on one typical snapshot obtained over 12 hours. We further analyze the fragility of the Ecosystem upon the removal of its most important tracker service.

Incentive mechanisms play a critical role in P2P systems. Private BitTorrent sites use a novel incentive paradigm, where the sites record upload and download amounts of users and require each user to maintain its upload-to-download ratio above a specified threshold. This paper explores in-depth incentives in private P2P file-sharing systems. Our contributions are threefold. We first conduct a measurement study on a representative private BitTorrent site, examining how incentives influence user behavior. Our measurement study shows that, as compared with public torrents, a private BitTorrent site provides more incentive for users to contribute and seed. Second, we develop a game theoretic model and analytically show that the ratio mechanism indeed provides effective incentives. But existing ratio incentives in private BitTorrent sites are vulnerable to collusions. Third, to prevent collusion, we propose an upload entropy scheme, and show through analysis and experiment that the entropy scheme successfully limits colluding, while rarely affecting normal users who do not collude.

The success of future P2P applications ultimately depends on whether users will contribute their bandwidth, CPU and storage resources to a larger community. In this paper, we propose a new incentive paradigm, Networked Asynchronous Bilateral Trading (NABT), which can be applied to a broad range of P2P applications. In NABT, peers belong to an underlying social network, and each pair of friends keeps track of a credit balance between them. When user Alice provides a service (a file, storage space, computation and so on) to her friend Bob, she charges Bob credits. Thus, in NABT, there is no global currency; instead, there are only credit balances maintained between pairs of friends. NABT allows peers to supply each other asynchronously and further allows peers to trade with remote peers through intermediaries. We theoretically show that NABT is perfectly efficient with balanced demands and supports "networked tit-for-tat". The efficiency of NABT with unbalanced demands is determined by the min-cut of credit limits of the underlying social network. Using simulations driven by MySpace traces, we demonstrate that a simple two-hop NABT design can have high trading efficiency, provide service differentiation, exploit trading intermediaries, and discourage free-riders.

A private BitTorrent site (also known as a "Bit Torrent darknet") is a collection of torrents that can only be accessed by members of the darknet community. The private BitTorrent sites also have incentive policies which encourage users to continue to seed files after completing downloading. Although there are at least 800 independent BitTorrent darknets in the Internet, they have received little attention in the research community to date. We examine BitTorrent darknets from macroscopic, medium-scopic and microscopic perspectives. For the macroscopic analysis, we consider 800+ private sites to obtain a broad picture of the darknet landscape, and obtain a rough estimate of the total number of files, accounts, and simultaneous peers within the entire darknet landscape. Although the size of each private site is relatively small, we find the aggregate size of the darknet landscape to be surprisingly large. For the medium-scopic analysis, we investigate content overlap between four private sites and the public BitTorrent ecosystem. For the microscopic analysis, we explore in-depth one private site and examine its user behavior. We observe that the seed-to-leecher ratios and upload-to-download ratios are much higher than in the public ecosystem. The macroscopic, medium-scopic and microscopic analyses when combined provide a vivid picture of the darknet landscape, and provide insight into how the darknet landscape differs from the public BitTorrent ecosystem.

Although Tor is the most widely used overlay for providing anonymity services, its users often experience very high delays. Because much of Tor usage is for Web applications, which are sensitive to latency, it is critical to reduce delays in Tor. To take an important step in this direction, we seek an in-depth understanding of delays in Tor. By taking snapshots of the entire Tor network within a short time window, we are able to study the delay distribution of the entire router population. We also monitor delays introduced by individual Tor routers over extended periods of time. Our results indicate that apart from delays introduced by routers, overlay network latency also plays a significant role in delays in Tor. We have also observed that at any time, there exist huge differences in the delays introduced by different routers. Our results reveal key performance characteristics of Tor system behavior and provide valuable insights for improving the Tor performance.

Peer Exchange (PEX), in which peers directly exchange with each other lists of active peers in the torrent, has been widely implemented in modern BitTorrent clients for decentralized peer discovery. However, there is little knowledge about the behavior of PEX in operational systems. In this paper, we perform both passive measurements and Planetlab experiments to study the impact and properties of BitTorrent PEX. We first study the impact of PEX on the download efficiency of BitTorrent. We observe that PEX can significantly reduce the download time for some torrents. We then analyze the freshness, redundancy and spread speed of PEX messages. Finally, we also conduct large- scale Planetlab experiments to understand the impact of PEX on the overlay properties of BitTorrent.

When a host discovers that it has a software vulnerability that is susceptible to an attack, the host needs to obtain and install a patch. Because centralized distribution of patches may not scale well, peer-to-peer (P2P) approaches have recently been suggested. There is, however, a serious privacy problem with peer-assisted patch distribution: when a peer A requests a patch from another peer B, it announces to B its vulnerability, which B can exploit instead of providing the patch. Through analytical modeling and simulation, we show that a large majority of vulnerable hosts will typically become compromised with a basic design for peer- assisted patch distribution. We then study the effectiveness of two different approaches in countering this privacy problem. The first approach utilizes special-purpose peer nodes, referred to as honeypots, that discover and blacklist malicious peers listening for patch requests from susceptible hosts. In the second approach, the patches are requested through an anonymizing network, hiding the identities of susceptible hosts from malicious peers. Using analytical models and simulation, we show that, honeypots do not completely solve the privacy problem; in contrast, an anonymizing network turns out to be more suitable for security patch distribution.

In recent years, there have been several large-scale deployments of P2P live video systems. Existing and future P2P live video systems will offer a large number of channels, with users switching frequently among the channels. In this paper, we develop infinite-server queueing network models to analytically study the performance of multichannel P2P live video systems. Our models capture essential aspects of multichannel video systems, including peer channel switching, peer churn, peer bandwidth heterogeneity, and Zipf-like channel popularity. We apply the queueing network models to two P2P streaming designs: the isolated channel design (ISO) and the View-Upload Decoupling (VUD) design. For both of these designs, we develop efficient algorithms to calculate critical performance measures, develop an asymptotic theory to provide closed-form results when the number of peers approaches infinity, and derive near-optimal provisioning rules for assigning peers to groups in VUD. We use the analytical results to compare VUD with ISO. We show that VUD design generally performs significantly better, particularly for systems with heterogeneous channel popularities and streaming rates.

In recent years, peer-to-peer (P2P) technology has been demonstrated tremendously effective in delivering large-scale video streaming services. Although P2P streaming is scalable and robust, the network-oblivious peering and scheduling in the current designs impede the further improvement in streaming quality and the efficient usage of network resources. New P2P streaming systems exploit network information provided by Internet service providers (ISPs) to achieve a higher level of application performance and generate lower traffic stress. In this paper, utilizing information from ISPs, we investigate the strategies on the topology construction and maintenance of multi-tree based P2P streaming systems. We study topology optimization to minimize the average height of sub-stream trees and the average propagation latency in each tree. We first present the optimization formulations, and then propose a set of heuristic algorithms for the construction and dynamic management of the multiple sub-stream trees for practical implementation. Through numerical comparison study, we show that our algorithms can significantly improve the delay performance of existing P2P streaming systems.

In current multi-channel live P2P video systems, there are several fundamental performance problems including exceedingly-large channel switching delays, long playback lags, and poor performance for less popular channels. These performance problems primarily stem from two intrinsic characteristics of multi-channel P2P video systems: channel churn and channel- resource imbalance. In this paper, we propose a radically different cross-channel P2P streaming framework, called view-upload decoupling (VUD). VUD strictly decouples peer downloading from uploading, bringing stability to multichannel systems and enabling cross-channel resource sharing. We propose a set of peer assignment and bandwidth allocation algorithms to properly provision bandwidth among channels, and introduce substream swarming to reduce the bandwidth overhead. We evaluate the performance of VUD via extensive simulations as well with a PlanetLab implementation. Our simulation and PlanetLab results show that VUD is resilient to channel churn, and achieves lower switching delay and better streaming quality. In particular, the streaming quality of small channels is greatly improved.

In recent years there have been several large-scale deployments of P2P live video systems. Existing and future P2P live video systems will offer a large number of channels, with users switching frequently among the channels. In this paper, we develop infinite-server queueing network models to analytically study the performance of multi-channel P2P streaming systems. Our models capture essential aspects of multi-channel video systems, including peer channel switching, peer churn, peer bandwidth heterogeneity, and Zipf-like channel popularity. We apply the queueing network models to two P2P streaming designs: the isolated channel design (ISO) and the View-Upload Decoupling (VUD) design. For both of these designs, we develop efficient algorithms to calculate critical performance measures, develop an asymptotic theory to provide closed-form results when the number of peers approaches infinity, and derive near- optimal provisioning rules for assigning peers to groups in VUD. We use the analytical results to compare VUD with ISO. We show that VUD design generally performs significantly better, particularly for systems with heterogeneous channel popularities and streaming rates.

Although there are several successful commercial deployments of live P2P streaming systems, the current designs 1) lack incentives for users to contribute bandwidth resources, 2) lack adaptation to aggregate bandwidth availability, and 3) exhibit poor video quality when bandwidth availability falls below bandwidth supply. In this paper, we propose, prototype, deploy, and validateLayerP2P, a P2P live streaming system that addresses all three of these problems. LayerP2P combines layered video, mesh P2P distribution, and a tit-for-tat-like algorithm, in a manner such that a peer contributing more upload bandwidth receives more layers and consequently better video quality. We implement LayerP2P (including seeds, clients, trackers, and layered codecs), deploy the prototype in PlanetLab, and perform extensive experiments. We also examine a wide range of scenarios using trace-driven simulations. The results show that LayerP2P has high efficiency, provides differentiated service, adapts to bandwidth deficient scenarios, and provides protection against free-riders.

This article characterizes video-based interactions that emerge from YouTube's video response feature, which allows users to discuss themes and to provide reviews for products or places using much richer media than text. Based on crawled data covering a representative subset of videos and users, we present a characterization from two perspectives: the video response view and the interaction network view. In addition to providing valuable statistical models for various characteristics, our study uncovers typical user behavioral patterns in video-based environments and shows evidence of opportunistic behavior.

We consider the design of an open P2P live-video streaming system. When designing a live video system that is both open and P2P, the system must include mechanisms that incentivize peers to contribute upload capacity. We advocate an incentive principle for live P2P streaming: a peer’s video quality is commensurate with its upload rate. We propose Substream Trading, a new P2P streaming design which not only enables differentiated video quality commensurate with a peer’s upload contribution but can also accommodate different video coding schemes, including single-layer coding, layered coding, and multiple description coding. Extensive trace-driven simulations show that substream trading has high efficiency, provides differentiated service, low start-up latency, synergies among peers with different Internet access rates, and protection against free-riders.

This paper seeks understanding the user behavior in a social network created essentially by video interactions. We present a characterization of a social network created by the video interactions among users on YouTube, a popular social networking video sharing system. Our results uncover typical user behavioral patterns as well as show evidences of anti-social behavior such as self-promotion and other types of content pollution.

In this paper, we quantify the potential gains of hybrid CDN-P2P for two of the leading CDN companies, Akamai and Limelight. We first develop novel measurement methodology for mapping the topologies of CDN networks. We then consider ISP-friendly P2P distribution schemes which work in conjunction with the CDNs to localize traffic within regions of ISPs. To evaluate these schemes, we use two recent, real-world traces: a video-on-demand trace and a large-scale software update trace. We find that hybrid CDN-P2P can significantly reduce the cost of content distribution, even when peer sharing is localized within ISPs and further localized within regions of ISPs. We conclude that hybrid CDN-P2P distribution can economically satisfy the exponential growth of Internet video content without placing an unacceptable burden on regional ISPs.

Peer-to-peer overlays can be used for service discovery over a global network fabric. We describe and evaluate a new service indexing mechanism for in-band streaming services such as application relays, mixers, and media transcoders. For this type of service, the location of the service in the network and service admission status are key attributes. We describe and analyze a service indexing mechanism which uses network position-based advertisement. We show that this mechanism gives good service selection, provides a close to uniform advertisement distribution in the overlay, reduces message overhead, and exhibits acceptable stability and setup delay.

In this paper, we consider applying multiple description coding in mesh-pull P2P live streaming networks to provide incentives for redistribution. In our system, a video is encoded into multiple descriptions with each description having equal importance. We consider a heterogeneous system with peers having different uplink bandwidths. We design a distributed protocol in which a peer contributing more uplink bandwidth receives more descriptions and consequently better video quality. Previous approaches consider single-layer video, where each peer receives the same video quality no matter how much bandwidth it contributes to the system. The simulation results show that our approach can provide differentiated video quality commensurate with a peer's contribution to other peers.

A fundamental paradigm in peer-to-peer (P2P) content distribution is that of a large community of intermittently-connected nodes that cooperate to share files. Because nodes are intermittently connected, the P2P community must replicate and replace files as a function of their popularity to achieve satisfactory performance. In this paper, we develop an analytical optimization theory for benchmarking the performance of replication/replacement algorithms, including algorithms that employ erasure codes. We also consider a content management algorithm, the Top-K Most Frequently Requested algorithm, and show that in most cases this algorithm converges to an optimal replica profile. Finally, we present two approaches for achieving an evenly balanced load over all the peers in the community.

We develop a simple stochastic fluid model that seeks to expose the fundamental characteristics and limitations of P2P streaming systems. This model accounts for many of the essential features of a P2P streaming system, including the peers' realtime demand for content, peer churn (peers joining and leaving), peers with heterogeneous upload capacity, limited infrastructure capacity, and peer buffering and playback delay. The model is tractable, providing closed-form expressions which can be used to shed insight on the fundamental behavior of P2P streaming systems. The model shows that performance is largely determined by a critical value. When the system is of moderate-to-large size, if a certain ratio of traffic loads exceeds the critical value, the system performs well; otherwise, the system performs poorly. Furthermore, large systems have better performance than small systems since they are more resilient to bandwidth fluctuations caused by peer churn. Finally, buffering can dramatically improve performance in the critical region, for both small and large systems. In particular, buffering can bring more improvement than can additional infrastructure bandwidth.

Video-on-demand in the Internet has become an immensely popular service in recent years. But due to its high bandwidth requirements and popularity, it is also a costly service to provide. We consider the design and potential benefits of peer-assisted video-on-demand, in which participating peers assist the server in delivering VoD content. The assistance is done in such a way that it provides the same user quality experience as pure client-server distribution. We focus on the single-video approach, whereby a peer only redistributes a video that it is currently watching.

This paper explores how to remotely monitor network-wide quality in mesh-pull P2P live streaming systems. Peers in such systems advertise to each other buffer maps which summarize the chunks of the video stream that they currently have cached and make available for sharing. We demonstrate how buffer maps can be exploited to monitor network-wide quality. We show that the information provided in a peer's advertised buffer map correlates with that peer's viewing-continuity and startup latency. Given this correlation, we remotely harvest buffer maps from many peers and then process these buffer maps to estimate the video playback quality. We apply this methodology to a popular P2P live streaming system, namely, PPLive. To harvest buffer maps, we build a buffer-map crawler and also deploy passive sniffing nodes. We process the harvested buffer maps and present results for network-wide playback continuity, startup latency, playback lags among peers, and chunk propagation patterns. The results show that this methodology can provide reasonably accurate estimates of ongoing video playback quality throughout the network.

The eleven papers in this special issue are devoted to advancements in peer-to-peer streaming systems.

An emerging Internet application, IPTV, has the potential to flood Internet access and backbone ISPs with massive amounts of new traffic. Although many architectures are possible for IPTV video distribution, several mesh-pull P2P architectures have been successfully deployed on the Internet. In order to gain insights into mesh-pull P2P IPTV systems and the traffic loads they place on ISPs, we have undertaken an in-depth measurement study of one of the most popular IPTV systems, namely, PPLive. We have developed a dedicated PPLive crawler, which enables us to study the global characteristics of the mesh-pull PPLive system. We have also collected extensive packet traces for various different measurement scenarios, including both campus access networks and residential access networks. The measurement results obtained through these platforms bring important insights into P2P IPTV systems. Specifically, our results show the following. 1) P2P IPTV users have the similar viewing behaviors as regular TV users. 2) During its session, a peer exchanges video data dynamically with a large number of peers. 3) A small set of super peers act as video proxy and contribute significantly to video data uploading. 4) Users in the measured P2P IPTV system still suffer from long start-up delays and playback lags, ranging from several seconds to a couple of minutes. Insights obtained in this study will be valuable for the development and deployment of future P2P IPTV systems.

In this paper, we examine the prefetching strategies in a peer-driven video on-demand system. In our design, each video is encoded into multiple low bit-rate substreams and copies of the substreams are distributed to the participating peers. When a peer streams in a substream of rate r, it instead streams at rate rcirc, where r>rcirc. In this manner, if one of the peer's suppliers disconnects, the client peer can tap the reservoir of prefetched bits while searching for a replacement server, thereby avoiding any glitches or reduced visual quality. We examine how to assign prefetching rates to each of substreams as a function of their importance. Our studies show that appropriate prefetching strategies can bring significant performance improvements for both multiple description and layered videos

Abstract — P2P file-sharing systems have indexes, which users search to find locations of desired titles. In the index poisoning attack, the attacker inserts massive numbers of bogus records into the index for a set of targeted titles. As a result, when a user searches for a targeted title, the index returns bogus results, such as bogus file identifiers, bogus IP addresses, or bogus port numbers. In this paper we first show that both structured and unstructured P2P file-sharing systems are highly vulnerable to the index poisoning attack. We then develop a novel and efficient methodology for estimating index poisoning levels and pollution levels in file-sharing systems. The methodology is efficient in that involves neither the downloading nor the analysis of binary content files. We deploy data-harvesting platforms for FastTrack, an unstructured file-sharing system, and Overnet, a DHT-based file-sharing system. Applying our methodology to harvested data, we find that index poisoning is pervasive in both systems. We also outline a distributed blacklisting procedure for countering the index poisoning and pollution attacks. I.

Peer-to-peer video streaming has emerged as an important means to transport stored video. The peers are less costly and more scalable than an infrastructure-based video streaming network which deploys a dedicated set of servers to store and distribute videos to clients. In this paper, we investigate streaming layered encoded video using peers. Each video is encoded into hierarchical layers which are stored on different peers. The system serves a client request by streaming multiple layers of the requested video from separate peers. The system provides unequal error protection for different layers by varying the number of copies stored for each layer according to its importance. We evaluate the performance of our proposed system with different copy number allocation schemes through extensive simulations. Finally, we compare the performance of layered coding with multiple description coding.

In a P2P system, a client peer may select one or more server peers to download a specific file. In a P2P resource economy, the server peers charge the client for the downloading. A server peer's price would naturally depend on the specific object being downloaded, the duration of the download, and the rate at which the download is to occur. The optimal peer selection problem is to select, from the set of peers that have the desired object, the subset of peers and download rates that minimizes cost. In this paper we examine a number of natural peer selection problems for both P2P downloading and P2P streaming. For downloading, we obtain the optimal solution for minimizing the download delay subject to a budget constraint, as well as the corresponding Nash equilibrium. For the streaming problem, we obtain a solution that minimizes cost subject to continuous playback while allowing for one or more server peers to fail during the streaming process. The methodologies developed in this paper are applicable to a variety of P2P resource economy problems.

One way to combat P2P file sharing of copyrighted content is to deposit into the file sharing systems large volumes of polluted files. Without taking sides in the file sharing debate, in this paper we undertake a measurement study of the nature and magnitude of pollution in the FastTrack P2P network, currently the most popular P2P file sharing system. We develop a crawling platform which crawls the majority of the FastTrack Network's 20,000+ supernodes in less than 60 minutes. From the raw data gathered by the crawler for popular audio content, we obtain statistics on the number of unique versions and copies available in a 24-hour period. We develop an automated procedure to detect whether a given version is polluted or not, and we show that the probabilities of false positives and negatives of the detection procedure are very small. We use the data from the crawler and our pollution detection algorithm to determine the fraction of versions and fraction of copies that are polluted for several recent and old songs. We observe that pollution is pervasive for recent popular songs. We also identify and describe a number of anti-pollution mechanisms.

Peer-to-peer distributed hash table (DHT) systems make it simple to discover specific data when their complete identifiers - or keys - are known in advance. In practice, however, users looking up resources stored in peer-to-peer systems often have only partial information for identifying these resources. We describe techniques for indexing data stored in peer-to-peer DHT networks, and discovering the resources that match a given user query. Our system creates multiple indexes, organized hierarchically, which permit users to locate data even using scarce information, although at the price of a higher lookup cost. The data itself is stored on only one (or few) of the nodes. Experimental evaluation demonstrates the effectiveness of our indexing techniques on a distributed peer-to-peer bibliographic database with realistic user query workloads.

We study the problem of how to stream layered video (live and stored) over a lossy packet network in order to optimize the video quality that is rendered at the receiver. We present a unified framework that combines scheduling, FEC error protection, and decoder error concealment. In the context of the unified framework, we study both the case of a channel with perfect state information and the case of a channel with imperfect state information (delayed or lost feedback). We adapt the theory of infinite-horizon, average-reward Markov decision processes (MDPs) with average-cost constraints to the problem. Based on simulations with MPEG-4 FGS video, we show that (1) optimizing together scheduling, FEC error correction and error concealment improves performance significantly and (2) policies with static error protection give near-optimal performance. We also find that degradations in quality for a channel with imperfect state information are small; thus our MDP approach is suitable for networks with long end-to-end delays.

We consider streaming layered video (live and stored) over a lossy packet network in order to maximize the video quality that is rendered at the receiver. We propose a framework, called joint scheduling and error concealment (Joint S+EC), in which packet scheduling decisions at the sender explicitly account for the error concealment mechanism at the receiver. We show how the theory of infinite--horizon, average--reward Markov decision processes (MDPs) with average--cost constraints can be applied to the joint scheduling and error concealment problem for low--delay transmission channels. The formulation allows for a wide variety of performance metrics, including metrics that take quality variation into account. We demonstrate the framework and MDP solution procedure using MPEG--4 FGS video traces. The main conclusions are (1) Joint S+EC optimal policies perform better than Disjoint S+EC optimal policies, and (2) the performance of the optimal Disjoint S+EC policy is not significantly better than very simple static policies.

E-mail is a mission-critical communication function for virtually all institutions. Modern e-mail employs a server-centric design, in which the user is critically dependent on her mail server. We present a peer-to-peer (P2P) email architecture that eliminates the need to rely on a single server and boosts the resilience of email against any kinds of attacks. Our architecture also provides confidential communications for all users. We present how the basic mechanisms of sending and reading email are implemented in our architecture. We also consider additional schemes to improve anonymity in our architecture. We present our prototype implementation and discuss the future of P2P communication architectures.

This paper presents an implementation of an end-to-end application for streaming stored MPEG-4 fine-grained scalable (FGS) videos over the best-effort Internet. Our current implementation runs over TCP but can also be run over TCP-friendly RTP/UDP with an error recovery mechanism. Our scheme adapts the coding rate of the streaming video to the variations of the available bandwidth for the connection, while smoothing changes in image quality between consecutive video scenes. We justify our design choices and present the results of the simulations obtained from our testbed. Our combined use of FGS-encoded video with a simple network-adaptation heuristic gives a system of low complexity, which is suitable for high performing video servers.

Because Internet access rates are highly heterogeneous, many video content providers today make available different versions of the videos, with each version encoded at a different rate. Multiple video versions, however, require more server storage and may also dramatically impact cache performance in a traditional cache or in a CDN server. An alternative to versions is layered encoding, which can also provide multiple quality levels. Layered encoding requires less server storage capacity and may be more suitable for caching; but it typically increases transmission bandwidth due to encoding overhead. In this paper we compare video streaming of multiple versions with that of multiple layers in a caching environment. We examine caching and distribution strategies that use both versions and layers. Our analytical results indicate that mixed distribution/caching strategies provide the best overall performance.

fine-grained scalable video over a TCP-friendly connection. The goal is to develop low-complexity yet high-performing schemes that adequately adapt to the short- and long-term variations in available bandwidth. We first present a novel framework for low-complexity streaming of fine-grained scalable video over a TCP-friendly connection. In the context of this scheme, and under the assumption of complete knowledge of bandwidth evolution, we derive an optimal policy for a criterion that involves both image quality and quality variability during playback. Based on this ideal optimal policy, we develop a real-time heuristic to stream fine-grained scalable video over the Internet, and we study its performance using real Internet traces. We find that our heuristic policy performs almost as well as the ideal optimal policy for a wide-range of bandwidth scenarios and when run over ordinary TCP the policy is essentially as good as when running the policy over popular TCP-friendly algorithms.

The efficient distribution of stored information has become a major concern in the Internet which has increasingly become a vehicle for the transport of stored video. Because of the highly heterogeneous access to the Internet, researchers and engineers have argued for layered encoded video. We investigate delivering layered encoded video using caches. Based on the stochastic knapsack theory, we develop a model for the layered video caching problem. We propose heuristics to determine which videos and which layers in the videos should be cached in order to maximize the revenue from the streaming service. We evaluate the performance of our heuristics through extensive numerical experiments. We find that, for typical scenarios, the revenue increases nearly logarithmically with the cache size and linearly with the link bandwidth that connects the cache to the origin servers. We also consider service models with request queuing and negotiations about the delivered stream quality and find that both extensions provide only small revenue increases.

Continuous-media traffic (i.e., audio and video) can tolerate some loss but have rigid delay constraints. A natural QoS requirement for a continuous-media connection is a prescribed limit on the fraction of traffic that exceeds an end-to-end delay constraint. We propose and analyze a framework that provides such a statistical QoS guarantee to traffic in a packet-switched network. Providing statistical guarantees in a network is a notoriously difficult problem because traffic flows lose their original statistical characterizations at the outputs of queues. Our scheme uses bufferless statistical multiplexing combined with cascaded leaky buckets for smoothing and traffic contracting. This scheme along with a novel method for bounding the loss probability gives a tractable framework for providing end-to-end statistical QoS. Using MPEG video traces, we present numerical results that compare the connection-carrying capacity of our scheme with that of guaranteed service schemes (i.e., no loss) using GPS and RCS. Our numerical work indicates that our scheme can support significantly more connections without introducing significant traffic loss.

The efficient distribution of stored information has become a major concern in the Internet which has increasingly become a vehicle for the transport of stored video. Because of the highly heterogeneous access to the Internet, researchers and engineers have argued for layered encoded video. We investigate delivering layered encoded video using caches. Based on a stochastic knapsack model we develop a model for the layered video caching problem. We propose heuristics to determine which videos and which layers in the videos should be cached. We evaluate the performance of our heuristics through extensive numerical experiments. We also consider two intuitive extensions to the initial problem.

We propose a new design for the Domain Name System (DNS) that takes advantage of recent advances in disk storage and multicast distribution technology. In essence, our design consists of geographically distributed servers, called replicated servers, each of which has a complete and up-to-date copy of the entire DNS database. To keep the replicated servers up-to-date, they distribute new resource records over a satellite channel or over terrestrial multicast. The design allows Web sites to dynamically wander and replicate themselves without having to change their URL. The design can also significantly improve the Web surfing experience since it significantly reduces the DNS lookup delay.

This paper presents a model and theory for streaming layered video. We model the bandwidth available to the streaming application as a stochastic process whose statistical characteristics are unknown a priori. The random bandwidth models short-term variations due to congestion control (such as TCP-friendly conformance). We suppose that the video has been encoded into a base and an enhancement layer, and that to decode the enhancement layer the base layer has to be available to the client. We make the natural assumption that the client has abundant local storage and attempts to prefetch as much of the video as possible during playback. At any instant of time, starvation or partial starvation can occur at the client in either of the two layers. During periods of starvation, the client applies video error concealment to hide the loss. We study the dynamic allocation of the available bandwidth to the two layers in order to minimize the impact pact of client starvation. For the case of an infinitely-long video, we find that the optimal policy takes on a surprisingly simple and static form. For finite-length videos, the optimal policy is a simple static policy when the enhancement layer is deemed at least as important as the base layer. When the base layer is more important, we design a threshold policy heuristic which switches between two static policies. We provide numerical results that compare the performance of no-prefetching, static and threshold policies.

Multimedia traffic can typically tolerate some loss but has rigid delay constraints. A natural QoS requirement for a multimedia connection is a prescribed bound on the the fraction of traffic that exceeds an end-to-end delay limit. We propose and analyze a traffic management scheme which guarantees QoS to multimedia traffic while simultaneously allowing for a large connection-carrying capacity. We study our traffic management scheme in the context of a single node. In order for the node to guarantee QoS, each connection's traffic is regulated. In order to support many connections, the link statistically multiplexes the connections' traffic. The scheme consists of (i) cascaded leaky-buckets for traffic regulation, (ii) smoothers at the ingresses, and (iii) bufferless statistical multiplexing within the node. For this scheme we show that loss probabilities are minimized with simple one-buffer smoothers which operate at specific minimum rates. We also show that the worst-case input traffic is extremal on-off traffic for all connections. These two results lead to a straightforward scheme for guaranteeing QoS to regulated traffic. Using MPEG video traces, we present numerical results which demonstrate the methodology. Finally, we compare the bufferless scheme with buffered statistical multiplexing.

We consider designing near video on demand (VoD) systems that minimize start-up latency while maintaining high image quality. Recently non-uniform segmentation has been used to develop periodic broadcasting techniques for near VoD. These techniques give significant reductions in start-up latency as compared with more conventional uniform segmentation. All of these schemes assume, however, that the videos are CBR-encoded. Since a CBR-encoded video has a larger average rate than an open-loop VBR encoding with the same image quality, there is potential to obtain further performance improvements by using VBR video. In this paper we develop a series of multiplexing schemes for the periodic broadcasting of VBR-encoded video, which are based on smoothing, server buffering and client prefetching. Two key but conflicting performance measures exist when using VBR video: latency and packet loss. By introducing small additional delays in our multiplexing schemes, our traced-based numerical work shows that the schemes can achieve nearly 100% link utilization with negligible packet loss. When the ratio of the CBR rate to the VBR average rate is a modest 1.8, start-up latency can be reduced by a factor of four or more for common scenarios.

Article Free Access Share on Optimal streaming of synchronized multimedia presentations Authors: David A. Turner Institut Eurécom, B.P. 193, 06904 Sophia-Antipolis, France Institut Eurécom, B.P. 193, 06904 Sophia-Antipolis, FranceView Profile , Keith W. Ross Institut Eurécom, B.P. 193, 06904 Sophia-Antipolis, France Institut Eurécom, B.P. 193, 06904 Sophia-Antipolis, FranceView Profile Authors Info & Claims MULTIMEDIA '99: Proceedings of the seventh ACM international conference on Multimedia (Part 2)October 1999 Pages 91–93https://doi.org/10.1145/319878.319903Published:01 October 1999Publication History 2citation189DownloadsMetricsTotal Citations2Total Downloads189Last 12 Months4Last 6 weeks0 Get Citation AlertsNew Citation Alert added!This alert has been successfully added and will be sent to:You will be notified whenever a record that you have chosen has been cited.To manage your alert preferences, click on the button below.Manage my AlertsNew Citation Alert!Please log in to your account Save to BinderSave to BinderCreate a New BinderNameCancelCreateExport CitationPublisher SiteeReaderPDF

We consider a finite-buffer packet multiplexer to which traffic arrives from several independent sources. The traffic from each of the sources is regulated, i.e., the amount of traffic that can enter the multiplexer is constrained by known regulator constraints. The regulator constraints depend on, the source and are more general than those resulting from cascaded leaky buckets. We assume that the traffic is adversarial to the extent permitted by the regulators. For lossless multiplexing, we show that if the original multiplexer is lossless it is possible to allocate bandwidth and buffer to the sources so that the resulting segregated systems are lossless. For lossy multiplexing, we use our results for lossless multiplexing to estimate the loss probability of the multiplexer. Our estimate involves transforming the original system into two independent resource systems, and using adversarial sources for the two independent resources to obtain a bound on the loss probabilities for the transformed system. We show that the adversarial sources are not extremal on-off sources, even when the regulator consists of a peak rate controller in series with a leaky bucket. We explicitly characterize the form of the adversarial source for the transformed problem. We also provide numerical results for the case of the simple regulator.

We present a high-performance prefetching protocol for the delivery of prerecorded VBR video from a server across a packet-switched network to a large number of clients. Not only does the protocol give constant perceptual quality and almost 100% link utilization, but it also allows for immediate commencement of the video upon user request and near instantaneous response to pause/resume and temporal jumps. The protocol requires: (1) that each client have a small amount of memory dedicated to the application; (2) that there is one bottleneck shared link between the server and the clients. Our protocol is based on the observation that there are frequent periods of time during which the shared link's bandwidth is under utilized. During these periods the server can prefetch frames from any of the ongoing videos and can send the frames to the buffers in the appropriate clients. The server chooses prefetched frames according to a join-the-shortest-queue policy. We present simulation results of our prefetch policy that are based on MPEG encoded traces.

We develop call admission policies for statistically multiplexing prerecorded sources over a bufferless transmission link. Our model is appropriate for video on demand, as well as other on-demand multimedia applications. In particular, we allow users to specify when the sources begin transmission; we also allow the user to invoke VCR actions such as pause and temporal jumps. We suppose that the quality of service (QoS) requirement allows for a small amount of packet loss. We develop a stochastic model which captures the random phases of the sources. We then apply large deviation theory to our model to develop global admission rules. The accuracy of the large deviation approximation is verified with simulation experiments employing importance sampling techniques. We also propose a refined admission rule which combines the global test and a myopic test. Numerical results are presented for the Star Wars trace; we find that the statistical multiplexing gain is potentially high and often insensitive to the QoS parameter. Finally, we develop efficient schemes for the real-time implementation of our global test. In particular, we demonstrate that the Taylor series expansion of the logarithmic moment generating function of the frame size distribution allows for fast and accurate admission decisions.

We introduce a specific transport and transmission scheme for video-on-demand called constant-rate transmission and transport (CRTT). CRTT establishes a CBR virtual channel between the video provider and the viewer's set-top box, and then transmits cells from the provider into this channel at a constant rate. Since we assume that the number of cells in a frame is variable, CRTT requires that some number of cells be built up in a set-top box buffer before the commencement of playback. The build up, cell transmission rate, and the set-top memory size must be chosen so that there is no starvation or overflow at the set-top box. We develop fundamental relationships between these parameters for viable CRTT. We then apply the theory to an MPEG encoding of Star Wars and find that the minimal set-top box memory for CRTT is 23 Mbytes. We also consider varying the constant rate over a small number of intervals. We find, for example, that for Star Wars approximately 2 Mbytes of set-top memory suffices with 32 constant-rate intervals.

We introduce a specific transport and transmission scheme for video-on-demand (VoD) called constant-rate transmission and transport (CRTT). CRTT establishes a constant bit-rate (CBR) virtual channel between the video provider and the viewer's set-top box (STB) and then transmits cells from the provider into this channel at a constant rate. Since we assume that the number of cells in a frame is variable, CRTT requires that some number of cells be built up in an STB buffer before the commencement of playback. The build up, cell transmission rate, and the set-top memory size must be chosen so that there is no starvation or overflow at the STB. We develop fundamental relationships between these parameters for viable CRTT. We then apply the theory to an MPEG encoding of Star Wars and find that the minimal STB memory far CRTT is 23 Mbytes. We also consider varying the constant rate over a small number of intervals. We find, for example, that for Star Wars approximately 2 Mbytes of set-top memory suffices with 32 constant-rate intervals.

Although many closed multiclass queuing networks have a product-form solution, evaluating their performance measures remains nontrivial due to the presence of a normalization constant. We propose the application of Monte Carlo summation in order to determine the normalization constant, throughputs, and gradients of throughputs. A class of importance-sampling functions leads to a decomposition approach, where separate single-class problems are first solved in a setup module, and then the original problem is solved by aggregating the single-class solutions in an execution model. We also consider Monte Carlo methods for evaluating performance measures based on integral representations of the normalization constant; a theory for optimal importance sampling is developed. Computational examples are given that illustrate that the Monte Carlo methods are robust over a wide range of networks and can rapidly solve networks that cannot be handled by the techniques in the existing literature.

A class of loss networks in which each connection specifies a route and a bandwidth requirement is considered. If sufficient bandwidth is not available in one of the links along the route, the connection is blocked and lost. Three schemes are considered for approximating blocking probabilities in the network. For a specific star topology, two of these schemes give blocking probabilities that are very close to the exact values under light, moderate, and heavy traffic. The approximations are shown to be asymptotically correct in a natural limiting regime. The implied costs and their relation to revenue sensitivity are also determined for the approximation schemes. The approximate revenue sensitivities are again very close to the exact values for the specific star topology.>

A reduced load approximation (also referred to as an Erlang fixed point approximation) for estimating point-to-point blocking probabilities in loss networks (e.g., circuit switched networks) with state-dependent routing is considered. In this approximation scheme, the idle capacity distribution for each link in the network is approximated, assuming that these distributions are independent from link to link. This leads to a set of nonlinear fixed-point equations which can be solved by repeated substitutions. The accuracy and the computational requirements of the approximation procedure for a particular routing scheme, namely least loaded routing, is examined. Numerical results for six-node and 36-node asymmetric networks are given. A novel reduced load approximation for multirate networks with state-dependent routing is also presented.>

The performance of the Fiber Distributed Data Interface (FDDI) under overload is studied. It is well known that, under overload, FDDI can settle into one of many recurrent sets of states. The idea of desirable and undesirable states is introduced. A desirable state is one where users share the capacity more or less equally in each token rotation. It is shown that the response times of interactive users are adversely affected if the system operates in an undesirable set of states. The waiting time of heavy users can be reduced by forcing the system to settle into the desirable states. Simple control mechanisms are proposed to ensure that the system settle into the desirable states.>

An internetwork of LANs is modeled as a graph with LAN segments as edges and transparent bridges and repeaters as nodes. The graph model leads to a simple expression for the effective load on an arbitrary LAN segment, which takes into account the overhead traffic due to the learning mechanism of the transparent bridges. Simplifying assumptions for the operation of the medium access control (MAC) layer protocol lead to a simple expression of the average end-to-end delay in terms of the effective loads on the LAN segments. The problem of optimally locating bridges and repeaters on the nodes in order to minimize the average delay is studied. This problem is equivalent to the set partitioning problem which can be readily solved with state-of-the-art algorithms. Minimizing cost subject to a constraint on average end-to-end delay is discussed. Locating bridges and repeaters on a linear topology, as typically found in an office building with a large number of floors, is also studied.>

A broadcast communication network that interconnects multiple hosts N considered.A job generated by a host is either generic, m which case It can be processed at any of the hosts in the network, or dedicated, m which case it must be processed at the host from which it originates.It is assumed that each host can generate several types of dedicated jobs, where each type imposes a constraint on its average response time.The optimal design objective is twofold: First, to redistribute the generic jobs among the host computers in order to minimize the average response time, which shall be referred to as the load-balancing problem; second, for each host computer, to design a control that schedules the dedicated and the generic Jobs so that the response-time constraints are met for each of the dedicated traffic types.Despite its complexity, the model described above has some attractive features.Specifically, for a given allocation of the generic traffic, the scheduhng problem at each host can be solved as a polymatroid optimization problem.The underlying polymatroid structure leads to an efficient algorithm to determine, as a function of the offered load of generic traffic, the average delay of the generic jobs at any given host.Further analysis reveals that the delay functions at each of the hosts are convex and increasing.Therefore, an allocation algorlthm can be employed to solve the system-level load-balancing problem.An example is provided mdlcating that a substantial improvement m performance can be obtained by incorporating scheduling into the load-balancing procedure.

In a recent paper, Melen and Turner [SIAM J. Comput., 18 (1989), pp. 301–313] determined sufficient conditions for multirate interconnection networks to be strictly nonblocking and rearrangeable. They considered the continuous bandwidth case, which permits the bandwidth of a connection to take an arbitrary value in a given closed interval. In this paper, simple necessary and sufficient conditions for multirate interconnection networks to be strictly nonblocking for both discrete and continuous bandwidth cases are determined. New results for rearrangeable multirate networks with discrete bandwidth requirements are also given.

A circuit-switched network consisting of multiple-access links connected to a common link is considered. Each call requires circuits on one access link and on the common link. The network supports multiple classes of calls where each class specifies a bandwidth requirement, an arrival rate, and a holding-time distribution. Based on a product-form solution for these networks, four algorithms are developed to determine the exact blocking probability for each of the classes. The first two algorithms are based on convolution, the third on the fast Fourier transform, and the fourth on a recursion due to J.S. Kaufman (1981) and to J.W. Roberts (1981). Complexity bounds and numerical results demonstrate that these algorithms can determine blocking probabilities in reasonable CPU time for networks with thousands of circuits.>

A stochastic system is considered in equilibrium with N servers, no waiting room, and K classes of customers. A class-k customer requires b/sub k/ servers and releases them simultaneously after a random period of time. This multiclass blocking system is motivated by loss networks that support a variety of traffic types (e.g. voice, video, facsimile). The effect of increasing the state-dependent arrival rates and the number of servers on the throughputs and blocking probabilities is considered. It is noted that the theory developed can be extended to the case where queueing is permitted in the knapsack.>

The problem of packing a knapsack of integer volume F with objects from K different classes to maximize profit is studied. Optimization is carried out over the class of coordinate convex policies. For the case of K=2, it is shown for a wide range of parameters that the optimal control is of the threshold type. In the case of Poisson arrivals and of knapsack and object volumes being integer multiples of each other, it is shown that the optimal policy is always of the double-threshold type. An O(F) algorithm to determine the revenue of threshold policies is also given. For the general case of K classes, the problem of the optimal static control where for each class a portion of the knapsack is dedicated is considered. An efficient finite-stage dynamic programming algorithm for locating the optimal static control is presented. Furthermore, variants of the optimal static control which allow some sharing among classes are also discussed.>

The problem of determining optimal access policies for circuit-switched networks that support traffic types with varying bandwidth requirements is addressed. The authors suppose that the network supports K classes of calls where each class is determined by a fixed route and a bandwidth requirement. A Markov decision process (MDP) approach is used to obtain optimal access policies for three models: the flexible scheme access-port model where a single link is shared; the contiguous scheme access-port model where wideband calls are required to occupy specific contiguous regions of the TDM frame; and the network-access model where a call holds several channels in different links simultaneously. Both linear programming and value-iteration MDP algorithms are coupled with a novel state descriptor in order to locate the optimal policy for reasonable-size problems (several T1 carriers in parallel for the access-port case, and small networks of T1 carriers for the network-access case).>

Two queues are fed by independent, time-homogeneous Poisson arrival processes. One server is available to handle both. All service durations, in both queues, are drawn independently from the same distribution. A setup time is incurred whenever the server moves (switches) from one queue to the other. We prove that in order to minimize the sum of discounted setup charges and holdings costs, assumed linear in queue length and having the same rate at the two queues, the service at each queue should be exhaustive, A “threshold policy” is defined as a policy under which the server switches (from an empty queue) only when the other reaches a critical size. It is shown to be a likely candidate for the optimal policy, both for the discounted version and for the long-time average criterion. The steady-state performance of this policy (under somewhat more general distributional assumptions) and the optimal thresholds are determined for a number of cases.

Considered are optimal dynamic policies for multiplexing Κ + 1 heterogeneous traffic types onto a single communication channel. The packet types arrive to the channel according to independent Poisson processes. The service requirements are exponential with type dependent means. The optimization criterion is to minimize a linear combination of the average delays for packet types 1 to Κ, while simultaneously subjecting the average delay of type-0 packets to a hard constraint. The optimal multiplexing policy is shown to be a randomized modification of the “μc rule”. The optimization problem is thereby reduced to a problem of finding the optimal randomization factor; an algorithm, which can be implemented in real time, is given to do this for two particular cases.