Novelty is a critical attribute in academic publishing, guiding researchers toward genuinely groundbreaking contributions and shaping influential research trajectories. Motivated by the need to better quantify novelty, this paper presents an analysis of research novelty and impact in scholarly work. We develop a quantitative metric that considers both the originality and influence of research work to measure the contributions of each publication to novelty within the constructed citation network and perform a content similarity analysis to assess how closely each work builds upon its predecessors. As a preliminary study, we apply this methodology to a set of seminal publications in the domain of artificial intelligence, tracking their current citation outcomes. Results show that the inaugural work exhibits the highest novelty and garners the most citations, whereas later, more incremental works achieve varied levels of influence. We also observe that content similarity between a citing work and the work it references tends to be inversely related to novelty, reflecting whether the new work represents a significant departure or a refinement of prior research. This combined analysis offers insights into the relationship between novelty and impact in the evolution of research publications.

This study examines the factors that influence the adoption of in-home respite services by family caregivers in Hong Kong, with the aim of addressing the societal challenge of an aging population. The research employs data science techniques on a large-scale community project to identify patterns that impact caregivers’ decisions. The findings can inform future policies on caregiver support, enabling the Hong Kong government to design more precise services for family caregivers. The research combines data science with social science, demonstrating the value of an interdisciplinary approach to address complex societal challenges and to make the results more transparent and explainable.

As online video service continues to grow in popularity, video content providers compete hard for more eyeball engagement. Some users visit multiple video sites to enjoy videos of their interest while some visit exclusively one site. However, due to the isolation of data, mining and exploiting user behaviors in multiple video websites remain unexplored so far. In this work, we try to model user preferences in six popular video websites with user viewing records obtained from a large ISP in China. The empirical study shows that users exhibit both consistent cross-site interests as well as site-specific interests. To represent this dichotomous pattern of user preferences, we propose a generative model of Multi-site Probabilistic Factorization (MPF) to capture both the cross-site as well as site-specific preferences. Besides, we discuss the design principle of our model by analyzing the sources of the observed site-specific user preferences, namely, site peculiarity and data sparsity. Through conducting extensive recommendation validation, we show that our MPF model achieves the best results compared to several other state-of-the-art factorization models with significant improvements of F-measure by 12.96, 8.24 and 6.88 percent, respectively. Our findings provide insights on the value of integrating user data from multiple sites, which stimulates collaboration between video service providers.

Recent years have witnessed the rapidly-growing business of ride-on-demand (RoD) services such as Uber, Lyft and Didi. Unlike taxi services, these emerging transportation services use dynamic pricing to manipulate the supply and demand, and to improve service responsiveness and quality. Despite this, on the drivers' side, dynamic pricing creates a new problem: how to seek for passengers in order to earn more under the new pricing scheme. Seeking strategies have been studied extensively in traditional taxi service, but in RoD service such studies are still rare and require the consideration of more factors such as dynamic prices, the status of other transportation services, etc. In this paper, we develop ROD-Revenue, aiming to mine the relationship between driver revenue and factors relevant to seeking strategies, and to predict driver revenue given features extracted from multi-source urban data. We extract basic features from multiple datasets, including RoD service, taxi service, POI information, and the availability of public transportation services, and then construct composite features from basic features in a product-form. The desired relationship is learned from a linear regression model with basic features and high-dimensional composite features. The linear model is chosen for its interpretability-to quantitatively explain the desired relationship. Finally, we evaluate our model by predicting drivers' revenue. We hope that ROD-Revenue not only serves as an initial analysis of seeking strategies in RoD service, but also helps increasing drivers' revenue by offering useful guidance.

Ride-on-demand (RoD) services such as Uber and Didi (in China) are becoming increasingly popular, and in these services dynamic price plays an important role in balancing the supply (i.e., the number of cars) and demand (i.e., the number of passenger requests) to benefit both drivers and passengers. However, the dynamic price also creates concerns for passengers: the "unpredictable" prices sometimes prevent them from making quick decisions at ease. One may wonder if it is possible to get a lower price if s/he chooses to wait a while. Giving passengers more information helps to tackle this concern, and predicting the prices is a possible solution.

All large-scale online video systems, for example, Netflix and Youku, make a significant investment on video recommendations that can dramatically affect video information diffusion processes among users. However, there is a lack of efficient methodology to interpret how various recommendation mechanisms affect information diffusion processes resulting in the difficulty to evaluate video recommendation efficiency. In this paper, we propose to quantify and explain video recommendation mechanisms by using epidemic models to mine video view count traces. It is well known that an epidemic model is an efficient approach to model information diffusion processes; while view count traces can be viewed as the results of video information diffusion driven by video recommendations. Thus, we propose a framework based on extended epidemic models to quantify and interpret two recommendation mechanisms, that is, direct and word-of-mouth (WOM) recommendations, by fitting video view count traces collected from Tencent Video, a large-scale online video system in China. Our approach is a novel methodology to evaluate video recommendation mechanisms, and a new perspective to interpret how recommendation mechanisms drive view count evolution.

Smart-home is becoming increasingly popular in recent years, and it introduces a new content retrieval paradigm - delay-insensitive downloading. In this new paradigm, users do not require the content retrieval task to finish as soon as possible, but only set a deadline for it. We study the role of this paradigm in the traffic engineering of a chunk-based cloud storage service. We propose that it could help to reduce the high intra-datacenter traffic at peak resulting from the chunk-based architecture, by delaying users' content requests when necessary. Because of the introduction of the new paradigm, we consider the co- existence of three applications (downloading, streaming, delay-insensitive downloading) in the service, and try to understand the best way to delay users' requests. We conduct an incentive-based study for the evaluation of schemes of delaying users' requests: the service provider pays incentives to users to promote this new paradigm. The incentive, as well as users' application-specific QoE on the service, is modelled, and a framework for the evaluation is presented. We then apply our framework to study several proposed delay schemes and present both quantitative and qualitative results.

In emerging ride-on-demand (RoD) services such as Uber or Didi (in China), dynamic pricing plays an important role in regulating supply and demand, trying to make such service, to some extent, more convenient for passengers. Despite the convenience, dynamic pricing also exerts mental burden on passengers: they wonder whether the current price is low enough to accept, or if it is not, what they could do to get a lower price. Without extra information, passengers sometimes feel anxious and lose satisfaction. It is thus necessary to provide more information to relieve the anxiety, and price prediction is one of the solutions.

As online video service continues to grow in popularity, video content providers compete hard for more eyeball engagement. Some users visit multiple video sites to enjoy videos of their interest while some visit exclusively one site. However, due to the isolation of data, mining and exploiting user behaviors in multiple video websites remain unexplored so far. In this work, we try to model user preferences in six popular video websites with user viewing records obtained from a large ISP in China. The empirical study shows that users exhibit both consistent cross-site interests as well as site-specific interests. To represent this dichotomous pattern of user preferences, we propose a generative model of Multi-site Probabilistic Factorization (MPF) to capture both the cross-site as well as site-specific preferences. Besides, we discuss the design principle of our model by analyzing the sources of the observed site-specific user preferences, namely, site peculiarity and data sparsity. Through conducting extensive recommendation validation, we show that our MPF model achieves the best results compared to several other state-of-the-art factorization models with significant improvements of F-measure by 12.96%, 8.24% and 6.88%, respectively. Our findings provide insights on the value of integrating user data from multiple sites, which stimulates collaboration between video service providers.

The net neutrality debate has been centered on the question: should Internet service providers (ISPs) be allowed to differentiate services for Internet content traffic? The concern is that the differentiation imposed by selfish ISPs might discriminate content providers (CPs) and harm social welfare. Although market competition among ISPs would alleviate the problem and moderate the necessity for net neutrality regulations, the problem remains in monopolistic access markets. We focus on such a market and study paid prioritization where CPs voluntarily pay for prioritizing their traffic under shared capacity. We study an ISP's pricing strategy, CPs' choices of priority, and the resulting system equilibrium, based on which we derive the utility of the ISP and CPs as well as social welfare. This paper shows that: 1) an ISP's optimal pricing leads to an efficient differentiation among CPs, such that social welfare is close to its maximum; 2) although ISPs might inhibit capacity deployment in the short run, price regulation could solve this issue; and 3) under medium system scale and capacity cost, ISPs would have strong incentives to expand capacity under paid prioritization. From a welfare perspective, our results suggest that paid prioritization could be superior to the imposition of net neutrality regulations.

Video popularity (measured by view count) over time is an essential reference for both online video providers and users. According to state-of-the-art works, video popularity is useful for system optimization, load generation, video caching, and video recommendation. Thus, deeper understanding of video popularity evolution is very helpful for improving video service quality and providers' operating efficiency. The core question to be explored in this paper is what key factors govern online video popularity evolution? Through collaboration with our industry partner, Tencent Video, we obtain historical data of video view counts over a period of time, and observe their patterns. We then propose a stochastic fluid model, named as EvoModel, which captures two processes giving rise to different evolution patterns of a given video: (a) the information spreading process and (b) the user reaction process. The driving forces for process (a) can be either via recommendation from the system directly, or word-of-mouth; the extent of the spread is governed by the intrinsic popularity of the video. The factor affecting the second process can be modeled by a user reaction rate. These processes together determine different video popularity evolution patterns. We validate our model by fitting the historical data obtained from a real-world system. Furthermore, we discuss the feasibility of estimating model parameters and predicting popularity.

We study the problem of how to manage the high intra-datacenter traffic in a chunk-based public cloud storage service serving primarily smart home devices. The large volume of traffic is introduced by delivering very large content during busy hours in the cloud. Measurement of a commercial cloud service shows that the peak traffic volume (at its edge servers) overwhelms the network interface cards (NICs), resulting in serious congestion and packet losses. Since it can be expected the large content downloading requests in smart home environment could be delay-insensitive, we propose DST to keep the peak load under a specified upper bound, by delaying users' requests when necessary. By modelling DST as a queueing system, we derive the relation between the mean delay and the traffic upper bound. With trace-driven simulations, we evaluate the system performance and validate the analysis results. For the commercial cloud service we study, we show that it is possible to keep the traffic upper bound to about 80% of peak traffic rate by introducing a mean delay of around 48 minutes.

Large-scale Internet VoD services often adopt a hybrid overlay approach using both P2P and CDN to stream video content. When the underlay ISP network interconnection is weak, as the situation is found in China, it is important to provision the CDN bandwidth carefully in different ISP networks. Through measurement studies using real world data (from Tencent Video), it is found that users in large ISP networks can leverage more on P2P service, compared to the case for smaller ISP networks, and this is especially true during heavy load periods. We study systematic strategies for allocating CDN bandwidth given fixed total bandwidth purchasing budget, and the influence of P2P factor. We show that a more optimal strategy would bias towards allocating proportionally more CDN bandwidth to smaller ISP networks. This result from our model and analysis is validated by simulation. This problem has not been considered by past works and has practical implications for improving the operation of real-world VoD service providers.

Large Internet video delivery systems serve millions of videos to tens of millions of users on daily basis, via Video-on-Demand (VoD) and live streaming. Video popularity (measured by view count) evolves over time. It represents the workload, as well as business value, of the video to the overall system. The ability to predict video popularity is very helpful for improving service quality and operating efficiency. Previous studies adopted simple (usually static) models for video popularity, or directly adopted patterns from measurement studies. In this paper, we develop a fluid model that tries to capture two hidden processes that give rise to different patterns of a given video's popularity evolution: (a) the information spreading process, and (b) the user reaction process. Specifically, these processes model how the video is recommended to the users, the video's inherent attractiveness, and users' reaction rate; and yield different popularity evolution patterns. We validate our model by fitting the data obtained from a large content provider in China. This model gives us the insight to explain the common and different video popularity evolution patterns and why.

Crowdsourcing-based video service systems, e.g., Thunder Crystal, are novel content distribution platforms composed by a large number of agent devices, acting like miniservers. Most agents are normal Internet users who would like to earn rewarded cash by uploading content through their devices. Compared with CDN, the bandwidth cost is much cheaper; while compared with Peer-to-Peer(P2P), the bandwidth supply is more stable. In this work, we create a stochastic model to analyze the live and VoD streaming performance in such crowdsourcingbased video service systems. Simulation is conducted to validate the accuracy of our analytical results.

There are two types of P2P systems satisfying two different user demands: 1) file downloading and 2) video-on-demand (VoD) streaming. An example of file downloading is the original BitTorrent, and examples for VoD streaming include various commercial P2P-based VoD streaming systems such as that offered by PPLive. We have a hypothesis - by combining a type: 1) system and 2) system as a single P2P system, both the file downloading users and the streaming users of the same video will benefit in performance. The reasoning is that at any moment, only a subset of the file downloading peers can provide good service to VoD streaming peers and the VoD streaming peers are only good at providing service to a different subset of the file downloading peers. The former subset is the set of peers close to completing the downloading of the video file; whereas the latter subset is the set of peers starting to download a video. In this paper, we propose a novel design for a mesh-based video distribution system without depending on video replication on streaming peers. We produce simple back-of-the-envelop analysis to show its effectiveness. Then, we further validate our design and compare it with other designs through simulation and experiments in practical networking environment by implementing a prototype.

Bandwidth cost is a significant concern for online video service providers. Today's video streaming systems mostly use HTTP streaming, with users accessing video segments as HTTP requests. A frequently used strategy is to serve all user requests as fast as possible, as if the user is downloading a file. The downloading rate can often far exceed the playback rate, when the system is below the peak load. This is known as progressive downloading. Since users may quit before viewing the complete video, however, much of the downloaded video can be “wasted.” By studying and exploiting the predictability of users' departure behavior , the authors developed a smart streaming strategy that can significantly improve overall streaming service quality under given server bandwidth. The improvement is achieved by avoiding the waste based on predicted user departure behavior. The proposed smart streaming technique is evaluated by modeling, analysis, and simulation, as well as experimentation using a prototype implementation.

Popular online video-on-demand (VoD) services all maintain a large catalog of videos for their users to access. The knowledge of video popularity is very important for system operation , such as video caching on content distribution network (CDN) servers. The video popularity distribution at a given time is quite well understood. We study how the video popularity changes with time, for different types of videos, and apply the results to design video caching strategies. Our study is based on analyzing the video access levels over time, based on data provided by a large video service provider. Our main finding is, while there are variations, the glory days of a video’s popularity typically pass by quickly and the probability of replaying a video by the same user is low. The reason appears to be due to fairly regular number of users and view time per day for each user, and continuous arrival of new videos. All these facts will affect how video popularity changes, hence also affect the optimal video caching strategy. Based on the observation from our measurement study, we propose a mixed replication strategy (of LFU and FIFO) that can handle different kinds of videos. Offline strategy assuming tomorrow’s video popularity is known in advance is used as a performance benchmark. Through trace-driven simulation, we show that the caching performance achieved by the mixed strategy is very close to the performance achieved by the offline strategy.

Online video-on-demand(VoD) services invariably maintain a view count for each video they serve, and it has become an important currency for various stakeholders, from viewers, to content owners, advertizers, and the online service providers themselves. There is often significant financial incentive to use a robot (or a botnet) to artificially create fake views. How can we detect fake views? Can we detect them (and stop them) efficiently? What is the extent of fake views with current VoD service providers? These are the questions we study in this article. We develop some algorithms and show that they are quite effective for this problem.

We consider a peer-to-peer (P2P)-assisted video-on-demand (VoD) system where each peer can store a relatively small number of movies to offload the server when these movies are requested. User requests are stochastic based on some movie popularity distribution. The problem is how to replicate (or place) content at peer storage to minimize the server load. Several variations of this replication problem have been studied recently with somewhat different conclusions. In this paper, we first point out and explain that the main difference between these studies is in how they model the scheduling of peers to serve user requests, and show that these different scheduling assumptions will lead to different “optimal” replication strategies. We then propose a unifying request scheduling model, parameterized by the maximum number of peers that can be used to serve a single request. This scheduling is called Fair Sharing with Bounded Degree (FSBD). Based on this unifying model, we can compare the different replication strategies for different degree bounds and see how and why different replication strategies are favored depending on the degree. We also propose a simple (primarily) distributed replication algorithm and show that this algorithm is able to adapt itself to work well for different degrees in scheduling.

Popular online Video-on-Demand (VoD) services all maintain a large catalog of videos for their users to access. The number of servers assigned to serve each video is directly related to the relative popularity of the video. The distribution of popularity at a given time is quite well understood. We study how the video popularity changes over its lifetime, for different types of videos. Our study is based on analyzing the video access levels over time, based on data provided by a large video service provider. Our main finding is, while there are variations, the glory days of a video typically pass by quickly and probability of replaying a video by the same user is low. The reason appears to be due to fairly regular number of users and view time per day for each user, and continuous arrival of new videos. We then discuss the implication of our findings for video replication and recommendation.

Rapid growth in users of smartphones and other mobile devices is increasing the demand for online video service to these mobile devices. The mobile video on demand (VoD) service is almost exclusively provided by content delivery network (CDN) servers since mobile devices are not powerful enough to provide any peer-to-peer (P2P) service. However, in a mixed VoD system with both non-mobile and mobile peers, an interesting question is to ask whether we can leverage non-mobile peers to provide better support for VoD. In this paper, we try to answer this question by a measurement study on Tencent's existing VoD systems. Our measurement results show various interesting characteristics and potential benefits of leveraging non-mobile users. Such results will guide us towards a practical system design and implementation in the near future.

The net neutrality debate has been centered at the question: whether price and service differentiation should be allowed for the Internet? We focus on a monopoly market, where regulation is often required, and study the type of service differentiation where an option of paid prioritization is provided for the Content Providers (CPs) by an Internet Service Provider (ISP). We study the ISP's pricing strategy and the corresponding CPs' responses. Based on the higher level CPs' choices of service classes and the lower level traffic equilibrium, we analyze the utility of the ISP and the CPs as well as the social welfare. By comparing the induced social welfare under different settings, we find that ISP's optimal pricing leads to an efficient differentiation among the CPs such that the social welfare is highly optimized. We also identify the conditions under which the ISP would have a strong incentive to expand its capacity when the market grows. In conclusion, our results support the use of priority-based pricing and service differentiation rather than imposing net neutrality regulations.

Online video-on-demand (VoD) services invariably maintain a view count for each video they serve, and it has become an important currency for various stakeholders, from viewers, to content owners, advertizers, and the online service providers themselves. There is often significant financial incentive to use a robot (or a botnet) to artificially create fake views. How can we detect the fake views? Can we detect them (and stop them) efficiently? What is the extent of fake views with current VoD service providers? These are the questions we study in this paper. We develop some algorithms and show their effectiveness for this problem.

Video streaming service in wireless networks is increasingly using dynamic selection of video bit-rates to provide a high quality of user experience (QoE). The bit-rate switching mechanism, performed at client side, plays a key role in determining QoE metrics. In this paper, we present the first analytical framework to compute starvation probability of playout buffer, continuous playback time and mean video quality, given the bit-rate switching logics. Wireless channel is modeled as a continuous time Markov process, and playout buffer is modeled as a fluid queue with Markov modulated fluid arrival. We construct a set of ordinary differential equations (ODEs) to characterize the dynamics of starvation probability and expected continuous playback time with regard to buffer length, and simple models to analyze mean bit-rate for different bit-rate switching algorithms. Our framework is very general in that by adding appropriate parameters, it can be utilized to predict the QoE metrics of dynamic adaptive streaming with a variety of features: i) buffer-aware bit-rate switching ii) (im)patience of the user, and iii) receiver-side flow control.

P2P systems require neighbor peers to frequently exchange buffer-map (BM) messages for efficient content sharing and distribution, which, however, can result in considerable communication overhead. A big problem in the BMs exchanged between neighbor peers is that a lot of information in them is redundant. To reduce the redundancy, some P2P systems have adopted certain block-level compression schemes (e.g., Huffman encoding) to compress each BM in isolation. However, these schemes simply treat each BM separately and as a single block of data, which largely affects their compression efficiency. In this paper, we propose a novel relevant-window-based (RW) compression framework, which takes advantage of the correlation between sequentially exchanged BMs between neighbor peers and thus can greatly remove the redundancy in them. We accordingly design a RW-based distributed compression scheme, which can work alone or co-work well with an existing block-level compression scheme for higher compression efficiency. We prove the correctness of our scheme and derive tight upper bound on average length of compressed bitmaps by our scheme via mathematical modeling. Numerical results demonstrate that our scheme alone can achieve compression efficiency of 96.6%, which can be further increased to up to 97.1% when jointly working with a block-level compression scheme.

Nowadays digital services, such as cloud computing and network access services, allow dynamic resource allocation and virtual resource isolation. This trend can create a new paradigm of flexible pricing schemes. A simple pricing scheme is to allocate multiple isolated service classes with differentiated prices, namely Paris Metro Pricing (PMP). The benefits of PMP are its simplicity and applicability to a wide variety of general digital services, without considering specific performance guarantees for different service classes. The central issue of our study is whether PMP is economically viable, namely whether it will produce more profit for the service provider and whether it will achieve more social welfare. Prior studies had only considered specific models and arrived at conflicting conclusions. In this article, we identify unifying principles in a general setting and derive general sufficient conditions that can guarantee the viability of PMP. We further apply the results to analyze various examples of digital services.

A peer-to-peer (P2P) live streaming system faces a big challenge under flash crowds. When a flash crowd occurs, the sudden arrival of numerous peers may starve the upload capacity of the system, hurt its quality of service, and even cause system collapse. This paper provides a comprehensive study on the performance of P2P live streaming systems under flash crowds. By modeling the systems using a fluid model, we study the system capacity, peer startup latency, and system recovery time of systems with and without admission control for flash crowds, respectively. Our study demonstrates that, without admission control, a P2P live streaming system has limited capacity to handle flash crowds. We quantify this capacity by the largest flash crowd (measured in shock level) that the system can handle, and further find this capacity is independent of system initial state while decreasing as departure rate of stable peer increases, in a power-law relationship. We also establish the mathematical relationship of flash crowd size to the worst-case peer startup latency and system recovery time. For a system with admission control, we prove that it can recover stability under flash crowds of any sizes. Moreover, its worst-case peer startup latency and system recovery time increase logarithmically with the flash crowd size. Based on the analytical results, we present detailed flash crowd handling strategies, which can be used to achieve satisfying peer startup performance while keeping system stability in the presence of flash crowds under different circumstances .

A big portion of Internet traffic nowadays is video. A good understanding of user behavior in online VoD systems can help us design, configure and manage video content distribution. With the help of a major video on demand (VoD) service provider, we conduct a detailed study of user behavior watching streamed videos over the Internet. We engineered the video player at the client side to collect user behavior reports for over 540 million sessions.In order to isolate the possible effect of session quality of experience (QoE) on user behavior, we focus on the sessions with perfect QoE, and leave out those sessions with QoE impairments (such as freezes).Our main finding is that users spend a lot of time browsing: viewing part of one video after another, and only occasionally (around 20% of the time) watching a video to its completion. We consider seek (jump to a new position of the video) as a special form of browsing - repeating partial viewing of the same video. Our analysis leads towards a user behavior model in which a user transitions through a random number of short views before a longer view, and repeats the process a random number of times. A purely abstract version of such user behavior model was proposed by Wu et al [1] as a closed queueing network formulation. Our study uncovers the parameters and distributions of such a stochastic behavior model based on observations in practice.

Video content downloading using the P2P approach is scalable, but does not always give good performance. Recently, subscription-based premium services have emerged, referred to as cloud downloading. In this service, the cloud storage and server caches user-interested content and updates the cache based on user downloading requests. If a requested video is not in the cache, the request is held in a waiting state until the cache is updated. We call this design server mode. An alternative design is to let the cloud server serve all downloading requests as soon as they arrive, behaving as a helper peer. We call this design helper mode. Our model and analysis show that both these designs are useful for certain operating regimes. The helper mode is good at handling a high request rate, while the server mode is good at scaling with video population size. We design an adaptive algorithm (AMS) to select the service mode automatically. Intuitively, AMS switches service mode from server mode to helper mode when too many peers request blocked movies, and vice versa. The ability of AMS to achieve good performance in different operating regimes is validated by simulation .

Traditional video-on-demand (VoD) systems rely purely on servers to stream video content to clients, which does not scale. In recent years, peer-to-peer assisted VoD (P2P VoD) has proven to be practical and effective. In P2P VoD, each peer contributes some storage to store videos (or segments of videos) to help the video server. Assuming peers have sufficient bandwidth for the given video playback rate, a fundamental question is what is the relationship between the storage capacity (at each peer), the number of videos, the number of peers, and the resultant off-loading of video server bandwidth. In this paper, we use a simple statistical model to derive this relationship. We propose and analyze a generic replication algorithm Random with Load Balancing (RLB) that balances the service to all movies for both deterministic and random (but stationary) demand models and both homogeneous and heterogeneous peers (in upload bandwidth). We use simulation to validate our results for sensitivity analysis and for comparisons to other popular replication algorithms. This study leads to several fundamental insights for P2P VoD system design in practice.

We consider a P2P-assisted Video-on-Demand (VoD) system where each peer can store a relatively small number of movies to offload the server when these movies are requested. User requests are stochastic based on some movie popularity distribution. The problem is how to replicate (or place) content at peer storage to minimize the server load. Several variation of this replication problem have been studied recently with somewhat different conclusions. In this paper, we first point out that the main difference between these studies is in how they model the scheduling of peers to serve user requests, and show that these different scheduling assumptions will lead to different “optimal” replication strategies. We then propose a unifying request scheduling model, parameterized by the maximum number of peers that can be used to serve a single request. This scheduling is called Fair Sharing with Bounded Out-Degree (FSBD). Based on this unifying model, we can compare the different replication strategies for different out-degree bounds and see how and why different replication strategies are favored depending on the out-degree. We also propose a new simple, adaptive, and essentially distributed replication algorithm, and show that this algorithm is able to adapt itself to work well for different out-degree in scheduling.

We consider a P2P-assisted content storage and delivery system to support a streaming Video-on-Demand (VoD) service. In this system, the peers are part of the service provider (e.g. set-top boxes) with limited storage space. Servers with ample storage and bandwidth are deployed to guarantee the availability and quality, but it is desirable to minimize the server utilization to reduce costs. Based on experience of implementing a deployed P2P VoD system, it was suggested in [1] that a movie's availability should be proportional to the movie's popularity. Based on further refinement, it is observed [2] that performance can be further improved by more (than proportional) availability for cold movies in P2P system. In this paper, we show that as the number of movies becomes large and there is some skewness in movie popularity, then one cannot expect the P2P part of the system to reduce server load as well as provide availability to all movies at the same time. It is a trade-off between coverage of movies and streaming throughput provided by the P2P system. If the goal is to minimize server load, under some reasonable conditions, we show that it is best to store and replicate only the hottest K* movies in the P2P part of the system. We also study the relationship between the skewness of the movie popularity distribution, P2P resources and the value of K*. Finally, we use simulation to validate our results.

Content distribution via network coding has received a lot of attention lately. However, direct application of network coding may be insecure. In particular, attackers can inject "bogus” data to corrupt the content distribution process so as to hinder the information dispersal or even deplete the network resource. Therefore, content verification is an important and practical issue when network coding is employed. When random linear network coding is used, it is infeasible for the source of the content to sign all the data, and hence, the traditional "hash-and-sign” methods are no longer applicable. Recently, a new on-the-fly verification technique has been proposed by Krohn et al. (IEEE S&P '04), which employs a classical homomorphic hash function. However, this technique is difficult to be applied to network coding because of high computational and communication overhead. We explore this issue further by carefully analyzing different types of overhead, and propose methods to help reducing both the computational and communication cost, and provide provable security at the same time.

Routing failures are common on the Internet and routing protocols can not always react fast enough to recover from them, which usually cause packet delivery failures. To address the problem, fast reroute solutions have been proposed to guarantee reroute path availability and to avoid high packet loss after network failures. However, existing solutions are often specific to single type of routing protocol. It is hard to deploy these solutions together to protect Internet routing including both intra- and inter-domain routing protocols because of their individual computational and storage complexity. Moreover, most of them can not provide effective protection for traffic over failed links, especially for the bi-directional traffic. In this paper, we propose a unified fast reroute solution for routing protection under network failures. Our solution leverages identifier based direct forwarding to guarantee the effectiveness of routing protection and supports incremental deployment. In particular, enhanced protection cycle (e-cycle) is proposed to construct rerouting paths and to provide node and link protection for both intra- and inter-domain routing protocols. We evaluate our solution by simulations, and the results show that the solution provides 100% failure coverage for all end-to-end routing paths with approximately two extra Forwarding Information Base (FIB) entries. Furthermore, we report an experimental evaluation of the proposed solution in operational networks. Our results show that the proposed solution effective provides failure recovery and does not introduce processing overhead to packet forwarding.

In peer-to-peer (P2P) networks, incentive protocol is used to encourage cooperation among end-nodes so as to deliver a scalable and robust service. However, the design and analysis of incentive protocols have been ad hoc and heuristic at best. The objective of this paper is to provide a simple yet general framework to analyze and design incentive protocols. We consider a class of incentive protocols that can learn and adapt to other end-nodes' strategies. Based on our analytical framework, one can evaluate the expected performance gain and, more importantly, the system robustness of a given incentive protocol. To illustrate the framework, we present two adaptive learning models and three incentive policies and show the conditions in which the P2P networks may collapse and the conditions in which the P2P networks can guarantee a high degree of cooperation. We also show the connection between evaluating incentive protocol and evolutionary game theory so one can easily identify robustness characteristics of a given policy. Using our framework, one can gain the understanding on the price of altruism and system stability, as well as the correctness of the adaptive incentive policy.

The information of temporal correlations among network-wide data flows is crucial to a wide range of network management applications, such as root-cause analysis, threat monitoring, and traffic profiling. While several prior work had only studied the centralized and offline computation of flow correlations, we present DisTrack, a space-efficient network management mechanism for online tracking of network-wide temporal flow correlations. The major benefits of DisTrack include low space complexity, high processing speed, and ease of distributed deployment. This paper presents its randomized data structures, with theoretical analysis on the trade-off between space complexity and accuracy. We further provide extensive empirical evaluations on real network traces.

Traditional Video-on-Demand (VoD) systems reply purely on servers to stream video content to clients, which does not scale. In recent years, Peer-to-peer assisted VoD (P2P VoD) has proven to be practical and effective. In P2P VoD, each peer contributes some storage to store videos (or segments of videos) to help the video server. Assuming peers have sufficient bandwidth for the given video playback rate, a fundamental question is what is the relationship between the storage capacity (at each peer), the number of videos, the number of peers and the resultant off-loading of video server bandwidth. In this paper, we use a simple statistical model to derive this relationship. We propose and analyze a generic replication algorithm RLB which balances the service to all movies, for both deterministic and random demand models, and both homogeneous and heterogeneous peers (in upload bandwidth). We use simulation to validate our results, for sensitivity analysis and for comparisons with other popular replication algorithms. This study leads to several fundamental insights for design P2P VoD systems in practice.

In this paper, we study the impact of the image quality (hence, the video streaming bit-rate) and the chunk-level impairment (hence the playback discontinuity) on the perceptual assessment of the viewing experience of P2P layered video streaming services. Through subjective QoE experiments, we have obtained several interesting findings and useful insights. The results clearly reveal the tradeoffs between streaming bit-rate (B) and discontinuity (D) on the MOS under certain network condition. It is also showed that B-D tradeoff pattern is video content dependant. Based on these observations, a heuristic model is proposed to derive a group of MOS contours. This type of contours have practical usage and can help selecting suitable video streaming bit-rate (layer) for playback so as to maximize the perceptual QoE of the end users.

Internet service providers (ISPs) depend on one another to provide global network services. However, the profit-seeking nature of the ISPs leads to selfish behaviors that result in inefficiencies and disputes in the network. This concern is at the heart of the “network neutrality” debate, which also asks for an appropriate compensation structure that satisfies all types of ISPs. Our previous work showed in a general network model that the Shapley value has several desirable properties, and that if applied as the profit model, selfish ISPs would yield globally optimal routing and interconnecting decisions. In this paper, we use a more detailed and realistic network model with three classes of ISPs: content, transit, and eyeball. This additional detail enables us to delve much deeper into the implications of a Shapley settlement mechanism. We derive closed-form Shapley values for more structured ISP topologies and develop a dynamic programming procedure to compute the Shapley values under more diverse Internet topologies. We also identify the implications on the bilateral compensation between ISPs and the pricing structures for differentiated services. In practice, these results provide guidelines for solving disputes between ISPs and for establishing regulatory protocols for differentiated services and the industry.

Peer-to-peer (P2P) streaming tries to achieve scalability (like P2P file distribution) and at the same time meet real-time playback requirements. It is a challenging problem still not well understood. In this paper, we describe a simple stochastic model that can be used to compare different downloading strategies to random peer selection. Based on this model, we study the tradeoffs between supported peer population, buffer size, and playback continuity. We first study two simple strategies: Rarest First (RF) and Greedy. The former is a well-known strategy for P2P file sharing that gives good scalability by trying to propagate the chunks of a file to as many peers as quickly as possible. The latter is an intuitively reasonable strategy to get urgent chunks first to maximize playback continuity from a peer's local perspective. Yet in reality, both scalability and urgency should be taken care of. With this insight, we propose a Mixed strategy that achieves the best of both worlds. Furthermore, the Mixed strategy comes with an adaptive algorithm that can adapt its buffer setting to dynamic peer population. We validate our analytical model with simulation. Finally, we also discuss the modeling assumptions and the model's sensitivity to different parameters and show that our model is robust.

Routing failures are common on the Internet and routing protocols can not always react fast enough to recover from them, which usually causes packet delivery failures. To address the problem, fast reroute solutions have been proposed to guarantee reroute path availability and to avoid high packet loss after network failures. However, existing solutions are often specific to single type of routing protocol. It is hard to deploy these solutions together to protect Internet routing including intra- and inter-domain routing because of their individual computational and storage complexity. Moreover, most of them can not provide effective protection for traffic over failed links, especially for the bi-directional traffic. In this paper, we propose a unified fast reroute solution for routing protection under network failures. Our solution leverages identifier based direct forwarding to guarantee the effectiveness of routing protection and supports incremental deployment. In particular, enhanced protection cycle (e-cycle) is proposed to construct rerouting paths and to provide node and link protection for both intra- and inter-domain routing. We evaluate our solution by simulations, and the results show that the solution provides 100% failure coverage for all end-to-end routing paths with approximately two extra Forwarding Information Base (FIB) entries.

Paris Metro Pricing (PMP) is a simple multi-class flat-rate pricing scheme already practiced by transport systems, specifically by the Paris Metro at one time. The name is coined after Andrew Odlyzko proposed it for the Internet as a simple way to provide differentiated services. Subsequently, there were several analytical studies of this promising idea. The central issue of these studies is whether PMP is viable, namely, whether it will produce more profit for the service provider, or whether it will achieve more social welfare. The previous studies considered similar models, but arrived at different conclusions. In this paper, we point out that the key is how the users react to the congestion externality of the underlying system. We derive sufficient conditions of congestion functions that can guarantee the viability of PMP, and provide the relevant physical meanings of these conditions.

Quality of Experience (QoE) refers to subjective criteria for evaluating multimedia content. Methods have been devised to study the design of Voice over IP systems and video codecs. In recent years, due to more abundant network bandwidth, it has become quite popular to watch video streamed over the Internet, whether by clientserver method or through a peer-to-peer (P2P) network. In this paper, we describe our experience in conducting QoE studies of P2P streaming using a chunk-level model. Instead of considering fine-grained network service impairments such as bit errors, packet losses or delays, we focus on chunk level delays. We carry out some preliminary QoE experiments on low-bit rate, low-frame rate and low-resolution video (3L-video) sequences. We apply the chunk-level model to help improve the design of the P2P streaming algorithms, and the design of video players that playback network streamed video.

Recently, there has been a growing interest of using network coding to improve the performance of wireless networks, for example, authors of proposed the practical wireless network coding system called COPE, which demonstrated the throughput gain achieved by network coding. However, COPE has two fundamental limitations: (1) the coding opportunity is crucially dependent on the established routes and (2) the coding structure in COPE is limited within a two-hop region only. The aim of this paper is to overcome these limitations. In particular, we propose DCAR, the distributed coding-aware routing mechanism which enables: (1) the discovery for available paths between a given source and destination and (2) the detection for potential network coding opportunities over much wider network region. One interesting result is that DCAR has the capability to discover high throughput paths with coding opportunities, while conventional wireless network routing protocols fail to do so. In addition, DCAR can detect coding opportunities on the entire path, thus eliminating the ¿two-hop¿ coding limitation in COPE. We also propose a novel routing metric called coding-aware routing metric (CRM) which facilitates the performance comparison between ¿coding-possible¿ and "coding-impossible¿ paths. We implement the DCAR system in ns-2 and carry out extensive evaluation. We show that when comparing to the coding mechanism in, DCAR can achieve much higher throughput gain.

Network coding is an attracting technology that has been shown to be able to improve the throughput of wireless networks. However, there still lacks fundamental understanding on how network coding works under realistic scenarios. In this paper, we examine the performance of a recently proposed network coding system under a realistic wireless physical layer and practical random access mechanisms. We propose a key performance measure called “encoding number”-the number of packets that can be encoded via network coding in each transmission. We provide an upper bound on the encoding number for the general coding topology, and derive the average encoding number and system throughput for a general class of random access mechanisms. Based on the practical coding system, we also derive a tighter upper bound on the throughput gain for a general wireless network. Our results are of fundamental value for coding-related MAC/Routing protocol design and analysis.

Within the current Internet, autonomous ISPs implement bilateral agreements, with each ISP establishing agreements that suit its own local objective to maximize its profit. Peering agreements based on local views and bilateral settlements, while expedient, encourage selfish routing strategies and discriminatory interconnections. From a more global perspective, such settlements reduce aggregate profits, limit the stability of routes, and discourage potentially useful peering/connectivity arrangements, thereby unnecessarily balkanizing the Internet. We show that if the distribution of profits is enforced at a global level, then there exist profit-sharing mechanisms derived from the coalition games concept ofShapley valueand its extensions that will encourage these selfish ISPs who seek to maximize their own profits to converge to a Nash equilibrium. We show that these profit-sharing schemes exhibit several fairness properties that support the argument that this distribution of profits is desirable. In addition, at the Nash equilibrium point, the routing and connecting/peering strategies maximize aggregate network profits and encourage ISP connectivity so as to limit balkanization.

In the past few years, P2P file distribution applications (e.g., BitTorrent) are becoming so popular that they are the dominating source of Internet traffic. This creates significant problems to Internet Service Providers (ISPs), not only because of the added complexity in traffic engineering, but the increase of traffic, in particular on the cross-ISP links, implies congestion and a higher operating cost. In this paper, we consider an ISP-friendly file distribution protocol which uses the “exploiting-the-locality principle” (ELP) to reduce the cross-ISP traffic. To show its benefit, we derive an upper and lower bound of cross-ISP traffic for the protocols which rely on ELP and show that the cross-ISP traffic can be reduced significantly when the number of peers within an ISP increases. To carry out realistic study, we design and implement our ISP-friendly protocol (which is compatible with the current BitTorrent protocol) and carry out large scale experiments on PlanetLab to measure the reduction of the cross ISP-traffic and the file downloading time. More important, we also show how the proposed ISP-friendly protocol can handle the “black-hole” security attack. This paper sheds light on the merits and design direction of ISP-friendly content distribution protocols.

Incentive protocols play a crucial role to encourage cooperation among nodes in networking applications. The aim of this paper is to provide a general analytical framework to analyze and design a large family of incentive protocols. We consider a class of incentive protocols wherein peers can distributively learn and adapt their actions. Using our analytical framework, one can evaluate the expected performance gain and system robustness of a given incentive protocol. To illustrate the framework, we present three incentive policies and two learning (or adaptive) models. We show under what conditions the network may collapse (e.g., no cooperation in the system) or the incentive protocol can guarantee a high degree of cooperation. In particular, we formally show the connection between evaluating incentive protocols and evolutionary game theory so to identify robustness characteristics of an incentive policy.

Data-driven P2P streaming systems can potentially provide good playback rate to a large number of viewers. One important design problem in such P2P systems is to determine the optimal chunk selection policy that provides high continuity playback under the server's upload capacity constraint. We present a general and unified mathematical framework to analyze a large class of chunk selection policies. The analytical framework is asymptotically exact when the number of viewers is large. More importantly, we provide some interesting observations on the optimal chunk selection policy: it is of shaped and becomesmore greedy as the upload capacity of the server increases. This insight helps content providers to deploy large scale streaming systems with a QoS-guarantee under a given cost constraint.

Recent works show conflicting results: network capacity may increase or decrease with higher transmission power under different scenarios. In this work, we want to understand this paradox. Specifically, we address the following questions: (1)Theoretically, should we increase or decrease transmission power to maximize network capacity? (2) Theoretically, how much network capacity gain can we achieve by power control? (3) Under realistic situations, how do power control, link scheduling and routing interact with each other? Under which scenarios can we expect a large capacity gain by using higher transmission power? To answer these questions, firstly, we prove that the optimal network capacity is a non-decreasing function of transmission power. Secondly, we prove that the optimal network capacity can be increased unlimitedly by higher transmission power in some network configurations. However, when nodes are distributed uniformly, the gain of optimal network capacity by higher transmission power is upper-bounded by a positive constant. Thirdly, we discuss why network capacity may increase or decrease with higher transmission power under different scenarios using carrier sensing and the minimum hop-count routing. Extensive simulations verify our analysis.

Abstract Stream control (SC) has recently attracted attentions in the research of multiple input multiple output (MIMO) wireless networks as a potential way to improve network capacity. However, inappropriate use of SC may significantly degrade network capacity as well. In this paper, we provide the first formal study on SC scheduling in MIMO wireless mesh networks (WMNs). We derive the theoretical upper bound on network capacity gain of SC scheduling. We also provide an efficient scheduling algorithm and show that its achieved network capacity gain is close to its theoretical upper bound. Moreover, we point out the poor performance of a previous SC scheduling algorithm SCMA under the general settings of WMNs. This formal characterization provides a deeper understanding of steam control scheduling in MIMO WMNs. Copyright © 2008 John Wiley & Sons, Ltd.

Internet service providers (ISPs) depend on one another to provide global network services. However, the profit-seeking nature of the ISPs leads to selfish behaviors that result in inefficiencies and disputes in the network. This concern is at the heart of the "network neutrality" debate, which also asks for an appropriate compensation structure that satisfies all types of ISPs. Our previous work showed in a general network model that the Shapley value has several desirable properties, and that if applied as the revenue model, selfish ISPs would yield globally optimal routing and interconnecting decisions.

The Internet includes thousands of Internet service providers (ISPs) which are interconnected to provide connectivity and service for end-users. Traditionally, the settlement between the ISPs are determined based on bilateral agreements that result from pair-wise negotiations. Although this settlement mechanism is intuitive and easy to implement, it does not encourage network- wide cooperation, as the bilateral charges typically do not lead to a fair division of revenue among all ISPs that are involved in carrying the same flows of traffic. This problem is getting more severe with various emerging new Internet business models. In this paper, we try to determine the existence and realizability of bilateral prices that can achieve fair revenue division among ISPs. In particular, we use Shapley value as the basis for deriving fair prices. Under a quite general topology and traffic model, we find that there exists prices that make the revenue division under bilateral settlement equal to that calculated under Shapley value. The corresponding "fair price" exhibits several nice and desirable characteristics. Moreover, it could be realized approximately.

The practical network coding system proposed in (S. Katti et al., 2006) has two fundamental limitations: 1) the coding opportunity is crucially dependent on the established routes; 2) the coding structure is limited within a two-hop region. To overcome these limitations, we propose DCAR, the first distributed coding-aware routing mechanism which combines (a) the discovery for available paths between a given source and destination, and (b) the detection for potential network coding opportunities. DCAR has the potential to find high throughput paths with coding opportunities while conventional routing fails to do so. In addition, DCAR can detect coding opportunities on the entire path, thus eliminating the "two-hop" coding limitation in (S. Katti et al., 2006). We also propose a novel routing metric called "CRM" (coding-aware routing metric) which facilitates the comparison between coding-possible and coding-impossible paths. We implement the DCAR system in NS-2 and conduct extensive evaluation, which shows that DCAR achieves 7% to 20% throughput gain over the coding system in [1].

While the practical coding scheme has been shown to be able to improve throughput of wireless networks, there still lacks fundamental understanding on how the coding scheme works under realistic settings, namely, when it operates on a realistic physical layer and the medium access is controlled by some random access methods. In this paper, we provide a formal analysis on the performance of the practical coding scheme under such realistic settings. The key performance measure is the encoding number, i.e., the number of packets that can be encoded by a coding node in each transmission. We provide an upper bound on the encoding number for the general coding topology, and derive the average encoding number and system throughput for a general class of random access mechanisms. Based on the practical coding scheme, we also derive a tighter upper bound on the throughput gain for a general wireless network. Our results can be particularly useful for coding-related MAC/Routing protocol design and analysis.

Accurate identification of network applications is important to many network activities. Traditional port-based technique has become much less effective since many new applications no longer use well-known port numbers. In this paper, we propose a novel profile-based approach to identify traffic flows belonging to the target application. In contrast to classifying traffic based on statistics of individual flows in previous studies, we build behavioral profiles of the target application, which describe dominant patterns of the application. Based on the behavioral profiles, a two-level matching is used in identifying new traffic. We first determine if a host participates in the application by comparing its behavior with the profiles. Subsequently, for each flow of the host we compare if it matches with the patterns in the profiles to determine which flows belong to this application. We demonstrate the effectiveness of our method on campus traffic traces. Our results show that one can identify the popular P2P applications with very high accuracy.

The "tracker" of a P2P system is used to lookup which peers hold (or partially hold) a given object. There are various designs for the tracker function, from a single-server tracker, to multiple-server tracker system, to DHT-based serverless systems. In this paper, we classify the different designs, discuss the different considerations for these designs, and simple models to evaluate the reliability of these designs.

P2P file downloading and streaming have already become very popular Internet applications. These systems dramatically reduce the server loading, and provide a platform for scalable content distribution, as long as there is interest for the content. P2P-based video-on-demand (P2P-VoD) is a new challenge for the P2P technology. Unlike streaming live content, P2P-VoD has less synchrony in the users sharing video content, therefore it is much more difficult to alleviate the server loading and at the same time maintaining the streaming performance. To compensate, a small storage is contributed by every peer, and new mechanisms for coordinating content replication, content discovery, and peer scheduling are carefully designed. In this paper, we describe and discuss the challenges and the architectural design issues of a large-scale P2P-VoD system based on the experiences of a real system deployed by PPLive. The system is also designed and instrumented with monitoring capability to measure both system and component specific performance metrics (for design improvements) as well as user satisfaction. After analyzing a large amount of collected data, we present a number of results on user behavior, various system performance metrics, including user satisfaction, and discuss what we observe based on the system design. The study of a real life system provides valuable insights for the future development of P2P-VoD technology.

The Internet is a hierarchical architecture comprising heterogeneous entities of privately owned infrastructures, where higher level Internet service providers (ISPs) supply connectivity to the local ISPs and charge the local ISPs for the transit services. One of the challenging problems facing service providers today is how the profitability can be increased while maintaining good service qualities as the network scales up. In this work, we seek to understand the fundamental issues on the "interplay" (or interaction) between ISPs at different tiers. Although the local ISPs (which we term peers) can communicate with each other by purchasing the connectivity from transit ISPs, there stands an opportunity for them to set up private peering relationships. Under this competitive framework, we explore the issues on 1) the impact of peering relationship; 2) resource distribution; 3) revenue maximization; and 4) condition for network upgrade. First, a generalized model is presented to characterize the behaviors of peers and the transit ISP, in which their economic interests are reflected. We study how a peer can distributively determine its optimal peering strategy. Furthermore, we show how a transit ISP is able to utilize the available information to infer its optimal pricing strategy, under which a revenue maximization is achieved. Two distributed algorithms are proposed to help ISPs to provide a fair and efficient bandwidth allocation to peers, avoiding a resource monopolization of the market. Last, we investigate the above issues in a "many-peers region," that is, when we scale up the network. We provide insightful evidence to show that the ISPs can still gain profits as they upgrade the network infrastructures. Extensive simulations are carried out to support our theoretical claims.

Within the current Internet, autonomous ISPs implement bilateral agreements, with each ISP establishing agreements that suit its own local objective to maximize its profit. Peering agreements based on local views and bilateral settlements, while expedient, encourage selfish routing strategies and discriminatory interconnections. From a more global perspective, such settlements reduce aggregate profits, limit the stability of routes, and discourage potentially useful peering/connectivity arrangements, thereby unnecessarily balkanizing the Internet. We show that if the distribution of profits is enforced at a global level, then there exist profit-sharing mechanisms derived from the coalition games concept of Shapley value and its extensions that will encourage these selfish ISPs who seek to maximize their own profits to converge to a Nash equilibrium. We show that these profit sharing schemes exhibit several fairness properties that support the argument that this distribution of profits is desirable. In addition, at the Nash equilibrium point, the routing and connecting/peering strategies maximize aggregate network profits, encourage ISP connectivity so as to limit balkanization.

Network coding has been shown to be able to improve the throughput of wireless networks. The authors have established fundamental understanding on how the coding scheme works under a realistic physical layer and practical link-scheduling algorithms. In the future, they aim at a complete system solution to incorporate network coding into the MAC and routing protocols, which can achieve higher efficiency in using potential coding opportunities and provide higher throughput. The results can serve as the prototype for future design of wireless networks embracing the network coding technology.

P2P streaming tries to achieve scalability (like P2P file distribution) and at the same time meet real-time playback requirements. It is a challenging problem still not well understood. In this paper, we describe a simple stochastic model that can be used to compare different data-driven downloading strategies based on two performance metrics: continuity (probability of continuous playback), and startup latency (expected time to start playback). We first study two simple strategies: rarest first and greedy. The former is a well-known strategy for P2P file sharing that gives good scalability, whereas the latter an intuitively reasonable strategy to optimize continuity and startup latency from a single peer's viewpoint. Greedy, while achieving low startup latency, fares poorly in continuity by failing to maximize P2P sharing; whereas rarest first is the opposite. This highlights the trade-off between startup latency and continuity, and how system scalability improves continuity. Based on this insight, we propose a mixed strategy that can be used to achieve the best of both worlds. Our algorithm dynamically adapts to the peer population size to ensure scalability; at the same time, it reserves part of a peer's effort to the immediate playback requirements to ensure low startup latency.

There is an increasing number of group-based multimedia applications over the Internet, for example, voice conference or multi-player games. For these applications, it is often necessary to select a strategy to distribute the multimedia streams or mixing the multimedia stream data so as to provide better quality of service (QoS) guarantees. However, there is no appropriate metrics to evaluate the QoS of a group multimedia session, despite abundant literature on how to evaluate the QoS for two-party communication (e.g. MOS, E-Model). In this paper, we propose a new measure which is called the group mean opinion score (GMOS). To leverage on existing work, our definition of GMOS is based on two-party MOS, hence, it can be estimated via measurement of network parameters and fitting these data into the E-Model. We conduct large scale experiments using the latest SKYPE conference software. We first calibrate the GMOS based on the subjective scores of our experiments, then for individual conference sessions, we check whether our approach can pick a server configuration strategy to achieve the best GMOS. The study shows our proposed methodology is very promising and the potential of applying to other group-based applications.

Being autonomous and scalable, peer-to-peer systems provide a paradigm for sharing files in the Internet. However, different from conventional structured replication systems like content distribution networks (CDN), peers in an unstructured P2P system may have different, sometimes low, online availability, and usually get only partial information about the resources of the system. Therefore, how to achieve good system level file availability by autonomous peers is an important goal in P2P replication systems. In this paper, we investigate decentralized and cooperative resource allocation algorithms in a class of P2P systems that provide replication service. We formulate this replication problem as an optimization problem, and propose several heuristic algorithms respectively. They include (a) a random algorithm, (b) a group partition algorithm that relies on peers' forming groups, and (c) a greedy search algorithm based on an estimated system-level file availability target. We compare and evaluate these algorithms by simulations, and observe that each of them has advantages depending on the system parameters.

Distributed wireless mesh network technology is ready for public deployment in the near future. However, without an incentive system, one should not assume that private self-interested wireless nodes would participate in such a public network and cooperate in the packet forwarding service. This paper studies the use of pricing as an incentive mechanism for stimulating participation and collaboration in public wireless mesh networks. Our focus is on the "economic behavior" of the network nodes-the pricing and purchasing strategies of the access point, wireless relaying nodes, and clients. We use a "game-theoretic approach" to analyze their interactions from one-hop to multihop networks and when the network has an unlimited or limited channel capacity. The important results that we show are that the access point and relaying wireless nodes will adopt a simple yet optimal fixed-rate pricing strategy in a multihop network with an unlimited capacity. However, the access price grows quickly with the hop distance between a client and the access point, which may limit the "scalability" of the wireless mesh network. In case where the network has limited capacity, the optimal strategy for the access point is to vary the access charge and even interrupt service to connecting clients. To this end, we focus on the access point adopting a non-self-enforcing but more practical "fixed-rate noninterrupted service" model and propose an algorithm based on the Markovian decision theory to devise the optimal pricing strategy. Results show that the scalability of a network with limited capacity is upper bounded by one with an unlimited capacity. We believe that this work will shed light on the deployment and pricing issues of distributed public wireless mesh networks.

AS Path Prepending (ASPP) is a popular method for the inter-AS inbound traffic engineering, which is known to be more difficult than the outbound traffic engineering. Although the ASPP approach has been extensively practised by many ASes, it is surprising that there still lacks a systematic study of this approach and the basic understanding of its effectiveness. In this paper, we introduce the concept, applicability and potential instability problem of the ASPP approach. Some guidelines are given as the first step to study the method to avoid instability problem. Finally, we study the dynamic prepending behavior of ISPs and show a real-world pathologic case of prepending instability based on our measurement study of RouteViews data.

Public-access networks need to handle persistent congestion and overload caused by high bandwidth aggregates that may occur during times of flooding-based DDoS attacks or flash crowds. The often unpredictable nature of these two activities can severely degrade server performance. Legitimate user requests also suffer considerably when traffic from many different sources aggregates inside the network and causes congestion. This paper studies a family of algorithms that "proactively" protect a server from overload by installing rate throttles in a set of upstream routers. Based on an optimal control setting, we propose algorithms that achieve throttling in a distributed and fair manner by taking important performance metrics into consideration, such as minimizing overall load variations. Using ns-2 simulations, we show that our proposed algorithms 1) are highly adaptive by avoiding unnecessary parameter configuration, 2) provide max-min fairness for any number of throttling routers, 3) respond very quickly to network changes, 4) are extremely robust against extrinsic factors beyond the system control, and 5) are stable under given delay bounds.

In this paper, we propose to model the dynamics of BitTorrent (BT) P2P file sharing systems using the stochastic differential equation method. Unlike previous approach, our method can capture more realistic network environment and peers behavior. Closed-form solutions of various performance measures such as the average number of downloaders, seeders, the system throughput and file downloading time are derived. We also validate our mathematical results via simulation and show that not only our mathematical model can closely track the dynamics of BT-like systems, but the model has a much higher accuracy than previous proposed methods. Also, many important properties can be derived from the close-form solution such as performance scalability, sensitivity of the measurements to various system parameters. We believe the proposed method can provide better understanding in the design and analysis of BT-like P2P systems.

TCP Veno was proposed to eliminate TCP performance suffering from wireless links. Real network measurements and live Internet results have validated TCP Veno's significant throughput improvement in wireless networks and its harmonious co-existence with TCP Reno connections in wired networks. In this paper, we develop a simple analytic approach to characterize TCP Veno behavior in both wire and wireless situations. Being different from the equation of TCP Reno, a more general close formula is derived, taking into account of the refined multiplicative decrease algorithm in Veno, to model the throughput for a bulk transfer of TCP Veno flow. Our simulation and experimental results demonstrate that such an equation is able to accurately predict TCP Veno throughput over different network scenarios, ranging from very low lossy links to very heavy lossy links.

This paper studies the use of pricing as an incentive mechanism to encourage private, self-interested nodes to participate in a public wireless mesh network and cooperate in the packet forwarding service. Our focus is on the "economic behavior" of the network nodes the pricing and purchasing strategies of the access point, wireless relaying nodes, and clients. We use a "game theoretic approach" to analyze their interactions from one-hop to multihop network and when the network has an unlimited or limited channel capacity. We show that the access point and relaying wireless nodes will adopt a simple, yet optimal, fixed-rate pricing strategy in a multi-hop network with an unlimited capacity. Yet, the fixed-rate pricing strategy fails to be optimal in the limited capacity case. To this end, we focus on the access point adopting a more practical "fixedrate, non-interrupted service" model and propose an algorithm based on the Markovian decision theory to devise the optimal pricing strategy.

The Internet is a hierarchical architecture comprising heterogeneous entities of privately owned infrastructures, where higher level Internet service providers (ISPs) supply connectivity to the local ISPs and charge the local ISPs for the transit services. One of the challenging problems facing service providers today is how to increase the profitability while maintaining good service qualities. In this work, we seek to understand the fundamental issues on the "interplay" (or interaction) between ISPs at different tiers. While the local ISPs (which we term peers) can communicate with each other by purchasing the connectivity from transit ISPs, there stands an opportunity for them to set up private peering relationships. Under this competitive framework, we explore the issues on (a) impact of peering relationship, (b) resource distribution and (c) revenue maximization. Firstly, a generalized model is presented to characterize the behaviors of peers and the transit ISP, in which their economic interests are reflected. We study how a peer can distributively determine its optimal peering strategy. Furthermore, we show how a transit ISP is able to utilize the available information to infer its optimal pricing strategy, under which a revenue maximization is achieved. A distributed algorithm is proposed to help ISPs to provide a fair and efficient bandwidth allocation to peers, avoiding a resource monopolization of the market. Extensive simulations are carried out to support our claims.

The BitTorrent (BT) file sharing protocol is popular due to its scalability property and the incentive mechanism to reduce free-riding. However, in designing such P2P file sharing protocols, there is a fundamental "tussle" between keeping peers, specially the more resourceful ones, in the system for as long as possible to help the system achieve better performance and allowing peers finish their download as quickly as possible. The current BT protocol represents only "one" possible implementation in this whole design spectrum. In this paper, we characterize the "complete" design space of BT-like protocols. We use fairness index to measure the fairness that incorporates the contribution peers make. We show that there is a wide range of design choices, ranging from optimizing the performance of file download, to optimizing the fairness measure. More importantly, we show that there is a simple and easily implementable design knob which can be used to choose a particular operating point in the design space. We then discuss different algorithms (centralized versus distributed) in realizing the design knob. We also carry out performance evaluation to quantify the merits and properties of the BT-like file sharing protocols.

File distribution via network coding has received a lot of attention lately. However, direct application of network coding may have security problems. In particular, attackers can inject "faked" packets into the file distribution process to slow down the information dispersal or even deplete the network resource. Therefore, content verification is an important and practical issue when network coding is employed. When network coding is used, it is infeasible for the source of the content to provide all the hash values or signatures required for verification, and hence the traditional "hash-and-sign" methods are no longer applicable. Recently, a new on-the-fly verification technique is proposed by Krohn et al. for rateless erasure codes. However, their scheme requires a large number of hash values to be distributed in advance, and all of them are needed to verify even for a single packet. We propose a new batch delivery and verification scheme that is similar to the classical scenario where the authentication information of a message is embedded with the message and is sufficient for the verification purpose. We investigate how our technique can be applied when random linear network coding is employed, and show that both the computational and the bandwidth overhead can be greatly reduced by using a variant of the random network coding. We further show by simulation that this variant is sufficiently effective in practice.

In this paper, we present the mathematical analysis of two important performance measures for a BitTorrent (BT) like P2P file sharing system, namely, average file downloading time and file availability. For the file downloading time, we develop a model using the "stochastic differential equation" approach, which can capture the system more accurately than some previous approach and can capture various network settings and peers behavior. We study the steady-state behavior and obtain the closed-form solutions for performance measures which allow us to carry sensitivity analysis on various performance measures for various system parameters. We then extend this model to consider multiclass peers wherein some peers are behind firewalls which may impede the uploading service. We also present the mathematical model to study the file availability of a BT-like system. The model helps us gain the understanding of why the "rarest-first" chunk selection policy is used in today's BT protocol. We propose a novel chunk selection algorithm to enhance the overall system file availability. Extensive simulations are carried to validate our analysis

Admission control has been shown to be a preferred alternative to TCP-friendly congestion control for inelastic flows in heterogeneous networks shared by elastic and inelastic traffic [1]. However, it is possible for an inelastic flow to adopt different level of aggressiveness in implementing the admission control. How these different levels of aggressiveness affect the system performance remains an open issue. In this paper, we evaluate a full spectrum of (abstract) admission control algorithms in terms of their aggressiveness towards elastic flows. A totally aggressive version would admit an inelastic flow even if this means elastic flows' fair bandwidth share is reduced to close to zero. In the other extreme, a TCP-friendly version would only admit an inelastic flow if its desired rate is no higher than what the elastic flows will receive after its arrival. We show that the performance of inelastic flows is asymptotically insensitive to their aggressiveness without strong assumptions about flow file size or holding time distributions. This makes a strong case for adopting a less aggressive, yet TCP-friendly admission control in a heterogeneous network. Extensive simulations are carried out to validate the performance, stability and asymptotic behavior the the proposed TCP-friendly admission control policy.

The connectivity between millions of nodes on the Internet is provided by the interconnection of many ISPs' networks. These ISPs, in their decisions to peer with each other, define a set of transit relationships. These transit relationships are the primary factors that dictate how traffic flows through the Internet. BGP-based inter-domain routing that implements these transit relationships can be considered economically efficient. The advent of peer-to-peer (P2P) applications and overlay networks, however, changes the rules by providing traffic routing favoring the applications' needs. This can lead to reduced economic efficiency and upset the ISPs' business model. In this paper, we propose simple models to represent P2P traffic demand, peering and routing in a market place of two competing ISPs to illustrate this tussle of the Internet. Based on these models, we also propose and investigate alternative peering and provisioning strategies available to the ISPs and analyze their effectiveness

Flow-level traffic measurement is required for a wide range of applications including accounting, network planning and security management. A key design challenge is how to gracefully deal with traffic surges that exhaust the resources (memory, export bandwidth or CPU) of the flow monitor. A standard solution is to do sampling (look at one out of every n packets). This is implemented in Cisco’s Netflow, a popular platform. Setting the sampling rate according to the normal traffic, however, cannot avoid overrunning available memory for flow records during abnormal situations, such as when there is a DoS attack or other security breaches. Currently available countermeasures have their own problems: (1) reject new flows when the cache is full - some legitimate new flows will not be counted; (2) export not-terminated flows to make room for new ones - this will exhaust the export bandwidth; (3) adapt the sampling rate to traffic rate - this will reduce the overall accuracy of accounting, including legitimate flows. In this paper, we propose a new counter-measure to deal with abnormal traffic conditions - adaptive flow aggregation. Often the reason for abnormal traffic conditions is due to security attacks. Fortunately, such attacks usually have some common patterns. For example, packets of DoS attacks have the same destination IP address, while traffic for worm spreading has the same source IP address. Our flow monitoring algorithm identifies these traffic clusters in real-time and aggregates these large amount of short flows into a few flows.

High-bandwidth traffic aggregates may occur during times of flooding-based distributed denial-of-service attacks or flash crowds. Congestion control of these traffic aggregates is important to avoid congestion collapse of network services. This paper presents a class of feedback-control algorithms that proactively protect a network server from overload by installing rate throttles in a set of upstream routers. A control-theoretical framework is proposed to optimize the control setting such that throttling can be achieved in a distributed and fair manner. We develop control-theoretic algorithms that (1) are highly adaptive by avoiding the configuration of unnecessary control parameters, (2) provide max-min fairness for any number of throttling routers, (3) respond very quickly to network changes, (4) are extremely robust against extrinsic factors beyond the system control, and (5) are stable under given delay bounds.

In wireless networks, it is well understood what throughput can be achieved by nodes who can hear each other (i.e. nodes within a single cell). The effects of nodes beyond the sensing range (known as hidden nodes) on a sender are complicated and difficult to analyze. Consequently, how to analytically model multi-hop ad-hoc networks, specially networks based on the popular IEEE 802.11 standards remains largely open. In a recent paper, the throughput of a particular wireless network topology (linear network with a given number of hidden nodes) has been derived analytically. In this paper, we unify previous results on single-cell models, and results characterizing different types of hidden node interference and the analysis of C. Ng et al., (2004), to derive a general solution for throughput given a linear network of arbitrary density and transmission distance between source and destination nodes. An important insight from our model is that there is a certain transmission distance, which is less than the maximum transmission distance, that optimizes throughput in such networks. This result is verified using ns-2 simulation with both single as well as multiple flows.

Opinion polls can be used as a means to reach weak agreement, an idea introduced by the LOCKSS system. We investigate a set of protocols based on those of LOCKSS that achieve data resilience for the long-term using a peer-to-peer network, where mutually untrusted peers are loosely organized. Peers use opinion polls to correct corrupted copies of data items instead of conventional methods that use consensus algorithms or cryptography to sign data. We give an overview of how LOCKSS performs opinion polls. We improve the current algorithms and evaluate our protocols in terms of their performance and security against adversary attacks. Finally we investigate the dynamics and steady state of the system.

This paper proposes a simple mechanism to allow reliability to be traded off against performance and scalability in a reliable multicast transport protocol. A reliability window is used in the data packet header to indicate which packets are useful to recover if lost. In addition, we describe a simple API that allows applications to set the reliability window in a way meaningful to the application. The usefulness of the trade-off is demonstrated using experimental results from a test network. We expect this mechanism to be useful for large-scale content distribution where the content ages over time.

This paper contains a detailed description of the congestion control algorithm of TRAM, a tree-based reliable multicast protocol. This algorithm takes advantage of regular acknowledgements from the receivers that propagate back to the sender via the repair tree. This scalable feedback mechanism is used to collect receiver credits. Complementing the windowing mechanism, packet transmission is smoothed by using a data rate commensurate with the window size. Additional details, such as how to prune slow receivers, and how to implement the rate scheduler on non-real-time systems are also discussed. The performance of the congestion control algorithm is then evaluated in extended LANs, and wide area networks. The fairness of bandwidth-sharing with other (TCP) traffic is also evaluated.

This paper describes a new class of deadlock-free routing algorithms for irregular networks based on ordered links. In this case, the links are ordered by partitioning them into a set of layers, each layer containing a spanning tree (when possible). Deadlock free routes can then be derived by using links with non-decreasing order. The deadlock-freedom property is proved. Two different implementations of the routing algorithm are studied. The resultant performance of these algorithms is then compared to other known algorithms: the shortest-path algorithm (which may result in deadlocks) and the up*/down* algorithm. Various performance metrics are considered, including path-length, network capacity, fault tolerance and time of computation. We argue that network capacity is the most important metric to optimize. It is shown that the proposed algorithms are promising since they usually achieve higher network capacity than up*/down*, while they perform only slightly worse than up*/down* in other metrics.

This paper reviews the engineering solutions and economic models for fair allocation of network bandwidth to elastic flows. Using examples, it gives insight to proportional fairness, and how it compares to the fairness achieved by TCP. The second topic is a discussion of fair bandwidth allocation between multicast and unicast flows. By separating the discussion into economic and engineering viewpoints, this paper discusses ideal solutions and suggests practical approaches to achieving reasonable fairness.

A traffic shaper regulates the transmission of packets according to a pre-determined rate, seemingly a straightforward program. A frequently used technique to achieve the prescribed rate is to interleave packet transmissions with sleeps, an operating system function. If the sleep duration cannot be accurately controlled, it can adversely impact the performance of the traffic shaper. We describe the problem caused by an inaccurate sleep, various algorithms for compensating for the inaccuracy, and how to accommodate intermittent data arrival streams at the same time. The objective is to produce an accurate, yet simple, robust, and efficient traffic shaper.

Abstract This paper describes the design of a network monitor that captures connections information in a network. The real‐time performance requirement makes the design significantly more challenging than that of a simple monitor that only counts packet types. Although we developed the monitor for DECnet, most of the lessons we learned are protocol‐independent and are thus applicable to designing such a monitor for a different protocol. In addition to reviewing the functionality, we report a first‐cut performance evaluation of the monitor software. We also describe some of our early experiences in using the monitor and review some current applications of the monitor in the areas of network configuration planning and performance management.

This paper is a study based on measurements of network activities of a major site of Digital's world-wide corporate network. The study yields two kinds of results: (1) DECnet protocol performance information and (2) DECnet session statistics. Protocol performance is measured in terms of the various network overhead (non-data) packets in routing, transport and session layers. From these protocol performance data, we are able to review how effective various network protocol optimizations are; for example the on/off flow control scheme and the delayed acknowledgement scheme in the transport protocol. DECnet session statistics characterizes the workload in such a large network. The attributes of a session include the user who started it, the application invoked, the distance between the user and the application, the time span, the number of packets and bytes in each direction, and the various reasons if a session is not successfully established. Based on a large sample of such sessions, we generate distributions based on various attributes of sessions; for example the application mix, the visit count distribution and various packet number and size distributions.