Search

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 recent years emerging ride-on-demand services (eg., Uber or Didi) are penetrating into the market of traditional taxi service. In these new services mobile devices are a key enabler: they serve as the intermediary between passengers/drivers and the service provider, tracking the locations and behavior of both passengers and drivers. On the other hand, the use of mobile devices also help us to capture huge amount of data for analysis. Through collaboration with a leading service provider in China, we collect vast amount of accurate data and analyze, in this paper, passenger reaction to dynamic prices in such a service. We consider the analysis as an important step towards making the service more efficient and more attractive to the passengers. We present the patterns of passengers' reaction, and discuss if it is useful to estimate the trip fare for multiple times in order to get a lower price. Our findings pave the way for future study on system optimization and policy considerations.

Emerging ride-on-demand services (e.g., Uber or Uber-like) are vying to penetrate into the market of traditional taxi service, and they are ubiquitous in the nature, by using smart mobile devices like on-car GPS and mobile phone. These ubiquitous services are also beneficial for the environment by increasing the utilization of cars and improving travel efficiency. Through collaboration with a leading service provider in China, we are able to collect vast amount of accurate data and analyze the nature of the demand and dynamic pricing mechanisms that match the supply with demand. We consider the analysis as an important step towards making the ubiquitous service more efficient and beneficial to the sustainability of future smart cities. We collect datasets of passengers' orders and payment information, and focus on the analysis of demand and dynamic pricing. In demand analysis, we discuss its general characteristics, passenger grouping and demand clustering; in dynamic pricing analysis, we discuss the pattern and determination of dynamic pricing multipliers. Our findings pave the way for future study on system optimization, dynamic pricing and policy considerations.

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.

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. Refereed/Peer-reviewed

There is an increasing demand for mobile video streaming. In order to improve the QoE of mobile video streaming, it is important to understand the user interest, user behavior, and current QoE achieved in mobile video streaming systems. Past studies have compared mobile video streaming with that for non-mobile end systems (PCs). In this paper, we report the differences in user interest, user behavior and QoE for different mobile device types (phone versus tablets, and Android versus iOS). Our study is based on a large data set collected from a real world mobile video streaming service operated by our collaborator. Besides reporting the differences for these device types, we also report the extent the streamed video is wasted (not viewed). It shows that there is a lot of room for improving the service QoE and efficiency.

Welcome to COMSNETS 2015! The final technical program this year consists of 35 regular papers and 10 invited presentations. We received 163 paper submissions from authors in 11 countries.

We study the problem of managing high intradatacenter traffic in a chunk-based public cloud storage service. The high traffic volume is introduced by aggregating very large files from multiple chunk servers in a single edge server. We measure a commercial cloud storage service system, and observe that peak traffic volume overwhelms the network interface cards (NICs) significantly. In the scenario of delivering content based on Smart Home network, it can be expected the file downloading service could be delay-insensitive. Thus, we propose “Batching Smooth intra-datacenter Traffic” (BST) scheme to reduce the peak load to a specified upper bound by batching and delaying users' requests. We resort to a mathematical model to understand the necessity of batching strategy. To evaluate BST's effects, we implement trace-driven simulations with different scheduling policies. In the commercial cloud storage service system, we show that BST is capable of keeping the upper bound to approximately 75% of the original peak traffic by trading off an average delay of 8 minutes.

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. Refereed/Peer-reviewed

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. Refereed/Peer-reviewed

Keywords of academic papers are jargons shared within a research domain as well as a summary of the contents. However, the increasing popularity of the interdisciplinary research in academia in recent years opened a possibility that the choice of keywords would be no longer confined by the traditional domain boundaries. In order to investigate the evolutionary trends of keyword-sharing groups in academic publications, we applied three types of Social Network Analysis methods on the papers in the Computer Science domain collected from the Libra database. Particularly, papers published in 5 different time periods from 1970 to 2010 were targeted to show the change of keyword networks over time. The analysis results confirmed the increasing tendency in the keyword network to be absorbed by one big agglomerated cluster over time. As a result, the gatekeeper- or liaison keywords seldom exist in later times but coordinator keywords became majority.

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. Refereed/Peer-reviewed

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 bitrate (B) and discontinuity (D) on the MOS under ceratin 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.

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 [1]. 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. Refereed/Peer-reviewed

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.

In this paper, we focus on the perceptual quality assessment of network streamed video via P2P networks. In these systems, the most noticeable impairments are not bit-level distortions, nor packet losses (as they get repaired), but video chunk or frame level delays. A key module in a video player is the video playback controller that decides whether to wait for delayed frames (hence freezing the playback), or try to playback by concealing the missing data. A good design should be based on how users react to different frame delay scenarios and playback decisions. We carefully designed a set of subjective tests to sample user reactions, and discuss how our results can be used in the design of playback controllers.

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 intraand 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 intraand inter-domain routing. We evaluate our solution by simulations, and the results show that the solution provides 100% failure coverage for all endto-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.

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.

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.

Increasingly, a computer network administrator's job is pre-occupied with user behavioral problems rather than physical failures of network and system components. A small number of malicious users can cause problems that affect a large number of users; more often, by not following proper procedures a user may let his/her system be used by malicious users; and there are various other misuses that all leave the network in a state of the tragedy of the commons. In this paper, we introduce the concept of credit-based networking - borrowing ideas from financial management and adapting them to network management. We first focus on a campus network by studying concrete scenarios of how credit-based network management can be applied. We then discuss how the concept is generally applicable to managing network behaviors as well by applying it to managing ISP peering relationships. We argue that the cascading effect of credit-based network management can enhance network management efficiency and improve the global network environment we all live in.

In recent years, BitTorrent-like file-swarming applications are becoming so popular that they contribute to a large percentage of the current Internet traffic. Internet service providers (ISPs) not only need to cope with this traffic engineering problem, e.g., when and how to increase their network capacity, but more importantly, these P2P applications also increase their operating cost since large amount of the traffic has to go through the cross-ISP links. In this paper, we consider the design and analysis of an ISP-friendly file swarming protocol so as to reduce the cross-ISP traffic. We analytically show that the conventional P2P file-swarming protocols consume significant bandwidth on the cross-ISP links. We also derive an upper and lower bound for the cross-ISP traffic for ISP-friendly protocols which exploit the data locality property. We propose and implement an ISP-friendly protocol and carried out large scale experiments on the PlanetLab. Experimental results indicate that our protocol can significantly reduce the cross ISP-traffic and provide a reasonable file downloading time.

The Internet is composed of thousand of autonomous Internet Service Providers (ISPs). On the one hand, they cooperate with one another to provide services for their customers; on the other hand, they compete with each other by using selfish routing and interconnecting strategies to maximize their own profits. Currently, ISPs use bilateral settlements to decide the financial compensation one ISP pays to another. However, without an appropriate settlement model, ISPs disputes might lead to disgraceful consequences. For example, Level 3 unilaterally terminated its ldquosettlement freerdquo peering relationship with Cogent on October 5, 2005. This disruption resulted in at least 15% of the Internet to be unreachable for the users who utilized either Level 3 or Cogent for Internet access. Although both companies restored peering connections several days later with a new ongoing negotiation, Level 3's move against Cogent exhibited an escalation of the tension that necessitates a new settlement for ISPs.

In unstructured P2P content distribution systems, the most important algorithms to ensure optimal flow of content along multiple dynamically created distribution trees are piece selection algorithms and load balancing algorithms. This paper models practical load balancing algorithms and derives a number of insights.

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.

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.

In recent years, the upgrade of access networks to broadband networks together with the P2P technology has brought many new applications to the Internet. P2P applications have quickly become the biggest consumer of network resources. ISPs of access networks as well as backbone networks are all wondering how to better manage their network resources. We explore the idea of uplink pricing as a way to provide differential pricing to P2P and regular users. In particular, we formulate a simple economic model to analyze under what scenarios uplink pricing will be adopted by all ISPs in a competitive market.

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.

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.

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.

Analyzing transport layer operation and enhancing its performance over multihop ad hoc networks have attracted a lot of attentions. Although the fundamental reasons for the performance degradation of TCP have been studied for many years, the tight coupling between transport layer and the wireless MAC layer is still not well understood. In this paper, we focus on the interactions between the hidden nodes and network congestion. By modeling the frame loss ratios of competing flows, a novel index is presented to measure congestion and fairness of these interfered links simultaneously. We formulate a practical optimization framework for TCP flows, and propose a distributed algorithm to improve the end-to-end throughput, and at the same time, provide per-flow fairness by exploiting cross-layer information. In the link layer, each node uses a proportional controller to determine the ECN marking probability for the purpose of notifying incipient congestion. Then the rate based TCP sender adjusts its sending rate according to the feedbacks from the link layer. Compared with standard TCP/802.11 as well as recent wireless TCP enhancements, our method substantially improves both long-term fairness and short-term fairness without sacrificing the aggregate end-to-end throughput. For some topologies with long hops, the throughputs of our proposed algorithm even outperform basic TCP/802.11 by over 100%.

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 [1]. 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 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.

Current peer-to-peer (P2P) file-sharing systems are mostly optimized for file availability. This paper investigates P2P architecture for video streaming in general, and the performance impact of data redundancy schemes in particular. In particular, this work show that maximizing file availability is not the best strategy for video streaming as another constraint-peers' streaming bandwidth, comes into play. To address this limitation, a request-rate minimization policy is developed and evaluated using simulation. The resultant optimized replication strategy is then compared to data redundancy scheme based on erasure-correction coding. Simulation results show that with sufficient peer storage and a low erasure coding overhead, erasure-correction coding can achieve substantially better streaming performance than replication-based strategies

In this paper, we compare the maximum achieveable throughput using network coding with routing in P2P networks. Our analysis is based on a simple star network where there is no multicast and network coding can only be applied at the peers. Under the idealized assumption that there is perfect information to realize optimal routing, this model captures the essential elements of a P2P network, yet allows simple analysis for what can be achieved by network coding and by routing respectively. The conclusion is that there is no coding advantage. We then discuss the applicability of this result to a real P2P content distribution system which may operate at lower throughput due to various other factors. Finally, in addition to yielding insights to the present case of P2P networks, we believe this type of non-multicast network models can lead to other new results for network coding in general.

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.

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.

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.

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 [17] 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.

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.

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.

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 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 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.