As video traffic dominates the Internet, it is important for operators to detect video quality of experience (QoE) to ensure adequate support for video traffic. With wide deployment of end-to-end encryption, traditional deep packet inspection--based traffic monitoring approaches are becoming ineffective. This poses a challenge for network operators to monitor user QoE and improve upon their experience. To resolve this issue, we develop and present a system for RE al-time QU ality of experience metric detection for E ncrypted T raffic— Requet —which is suitable for network middlebox deployment. Requet uses a detection algorithm that we develop to identify video and audio chunks from the IP headers of encrypted traffic. Features extracted from the chunk statistics are used as input to a machine learning algorithm to predict QoE metrics, specifically buffer warning (low buffer, high buffer), video state (buffer increase, buffer decay, steady, stall), and video resolution. We collect a large YouTube dataset consisting of diverse video assets delivered over various WiFi and LTE network conditions to evaluate the performance. We compare Requet with a baseline system based on previous work and show that Requet outperforms the baseline system in accuracy of predicting buffer low warning, video state, and video resolution by 1.12×, 1.53×, and 3.14×, respectively.

As video traffic dominates the Internet, it is important for operators to detect video Quality of Experience (QoE) in order to ensure adequate support for video traffic. With wide deployment of end-to-end encryption, traditional deep packet inspection based traffic monitoring approaches are becoming ineffective. This poses a challenge for network operators to monitor user QoE and improve upon their experience. To resolve this issue, we develop and present a system for REal-time QUality of experience metric detection for Encrypted Traffic, Requet. Requet uses a detection algorithm we develop to identify video and audio chunks from the IP headers of encrypted traffic. Features extracted from the chunk statistics are used as input to a Machine Learning (ML) algorithm to predict QoE metrics, specifically, buffer warning (low buffer, high buffer), video state (buffer increase, buffer decay, steady, stall), and video resolution. We collect a large YouTube dataset consisting of diverse video assets delivered over various WiFi network conditions to evaluate the performance. We compare Requet with a baseline system based on previous work and show that Requet outperforms the baseline system in accuracy of predicting buffer low warning, video state, and video resolution by 1.12X, 1.53X, and 3.14X, respectively.

Recognition and perception based mobile applications, such as image recognition, are on the rise. These applications recognize the user's surroundings and augment it with information and/or media. These applications are latency-sensitive. They have a soft-realtime nature - late results are potentially meaningless. On the one hand, given the compute-intensive nature of the tasks performed by such applications, execution is typically offloaded to the cloud. On the other hand, offloading such applications to the cloud incurs network latency, which can increase the user-perceived latency. Consequently, edge computing has been proposed to let devices offload intensive tasks to edge servers instead of the cloud, to reduce latency. In this paper, we propose a different model for using edge servers. We propose to use the edge as a specialized cache for recognition applications and formulate the expected latency for such a cache. We show that using an edge server like a typical web cache, for recognition applications, can lead to higher latencies. We propose Cachier, a system that uses the caching model along with novel optimizations to minimize latency by adaptively balancing load between the edge and the cloud, by leveraging spatiotemporal locality of requests, using offline analysis of applications, and online estimates of network conditions. We evaluate Cachier for image-recognition applications and show that our techniques yield 3x speedup in responsiveness, and perform accurately over a range of operating conditions. To the best of our knowledge, this is the first work that models edge servers as caches for compute-intensive recognition applications, and Cachier is the first system that uses this model to minimize latency for these applications.

WiFi networks have been globally deployed and most mobile devices are currently WiFi-enabled. While WiFi has been proposed for multimedia content distribution, its lack of adequate support for multicast services hinders its ability to provide multimedia content distribution to a large number of devices. In this paper, we present the AMuSe system, whose objective is to enable scalable and adaptive WiFi multicast services. AMuSe is based on accurate receiver feedback and incurs a small control overhead. In particular, we develop an algorithm for dynamic selection of a subset of the multicast receivers as feedback nodes, which periodically send information about the channel quality to the multicast sender. This feedback information can be used by the multicast sender to optimize multicast service quality, e.g., by dynamically adjusting transmission bitrate. AMuSe does not require any changes to the standards or any modifications to the WiFi devices. We implemented AMuSe on the ORBIT testbed and evaluated its performance in large groups with approximately 200 WiFi devices, both with and without interference sources. Our extensive experiments demonstrate that AMuSe can provide accurate feedback in a dense multicast environment. It outperforms several alternatives even in the case of external interference and changing network conditions.

This paper considers a hybrid cellular architecture in which mobiles can communicate with others in their vicinity, e.g. using 802.11 interface, in addition to the base stations of the cellular network. Such an architecture can aid device-to-device communication as well as assist critical tasks of cellular networks such as mobility management, content caching and relaying. In order to enable these capabilities, base stations need to have sufficient knowledge of the underlying network topology induced by the 802.11 links of the mobiles. Due to the dynamic nature of this network, a compressed snapshot of its topology should be collected within a very short time duration and with minimal communication among mobiles. Addressing this need, we propose a compact topology representation that is suitable for a number of applications. We utilize the broadcast nature of wireless channels to design an efficient topology detection algorithm that acquires a compact representation of the underlying network (at most 3N links and a low `stretch' factor for the N mobiles) within a short duration (10s of ms). Our scheme does not have collision resolution, backoffs or any of the other MAC layer inefficiencies.

Today's cloud storage services must offer storage reliability and fast data retrieval for large amount of data without sacrificing storage cost. We present SEARS, a cloud-based storage system which integrates erasure coding and data deduplication to support efficient and reliable data storage with fast user response time. With proper association of data to storage server clusters, SEARS provides flexible mixing of different configurations, suitable for real-time and archival applications. Our prototype implementation of SEARS over Amazon EC2 shows that it outperforms existing storage systems in storage efficiency and file retrieval time. For 3 MB files, SEARS delivers retrieval time of 2.5 s compared to 7 s with existing systems.

IEEE 802.11-based wireless local area networks, referred to as WiFi, have been globally deployed and the vast majority of mobile devices are currently WiFi-enabled. While WiFi has been proposed for multimedia content distribution, its lack of adequate support for multicast services hinders its ability to provide multimedia content distribution to a large number of devices. We propose AMuSe, a scalable and adaptive interference mitigation solution for WiFi multicast services which is based on accurate receiver feedback and that incurs a small control overhead. Specifically, we develop a scheme for dynamic selection of a subset of the multicast receivers as feedback nodes, which periodically send information, such as channel quality or received packet statistics, to the multicast sender. This feedback information is used by the multicast sender to optimize the multicast service quality, e.g., by dynamically adjusting the transmission bit-rate. Our proposed solution does not require any changes to the standards or any modifications to the WiFi devices. We have implemented the proposed solution in the ORBIT testbed and evaluated its performance in large groups with approximately 250 receivers, both with and without interference sources. Our online experiments demonstrate that our system provides practical multicast services that can accommodate hundreds of receivers.

Content distribution networks (CDNs) using storage clouds have recently started to emerge. Compared to traditional CDNs, storage cloud-based CDNs have the advantage of cost effectively offering hosting services to Web content providers without owning infrastructure. However, existing work on replica placement in CDNs does not readily apply in the cloud. In this paper, we investigated the joint problem of building distribution paths and placing Web server replicas in cloud CDNs to minimize the cost incurred on the CDN providers while satisfying QoS requirements for user requests. We formulate the cost optimization problem with accurate cost models and QoS requirements and show that the monthly cost can be as low as 2.62 US Dollars for a small Web site. We develop a suite of offline, online-static and online-dynamic heuristic algorithms that take as input network topology and work load information such as user location and request rates. We then evaluate the heuristics via Web trace-based simulation, and show that our heuristics behave very close to optimal under various network conditions.

Network load is reduced upon elimination of redundant data transfer. Redundancy elimination (RE) techniques can be applied on a per-packet basis, and provide benefit regardless of application. While it is straightforward to apply RE on a perlink basis, network cost can be further reduced by applying RE network-wide: by routing potentially redundant packets (identified using a redundancy profile) onto common links. Constructing redundancy-aware routes is challenging: it might not be economically viable to deploy RE over every link. Also, to preserve end-to-end performance and control signaling cost, routes cannot be determined on a per packet basis. We propose a redundancy-aware routing algorithm. Our approach can cope with limited resources (in terms of number of routers that can support RE ) and is feasible (not requiring for per-packet routing decisions). We evaluate our algorithm using detailed simulations, based on both synthetic traffic and trace captured from large enterprise networks. Unlike previous studies, our studies consider data from multiple sources. Our results show that a small number of RE equipped routers, coupled with our routing algorithm, are sufficient to achieve reduction in network load close to the unreachable upper bound.

Network-level redundancy elimination (RE) algorithms reduce traffic volume on bandwidth-constrained network paths by avoiding the transmission of repeated byte sequences. Previous work shows that RE can suppress the transmission of 20-50% bytes when deployed at ISP access links or between routers. In this paper, we focus on the challenges of deploying RE in cellular networks. The potential benefifit is substantial, since cellular networks have a growing subscriber base and network links, including wired backhaul, are often oversubscribed. Using three large traces captured at two North American and one European wireless network providers, we show that RE can reduce the bandwidth consumption of the majority of mobile users by at least 10%.

Multicast is an efficient means of transmitting the same content to multiple receivers while minimizing network resource usage. Applications that can benefit from multicast such as multimedia streaming and download, are now being deployed over 3G wireless data networks. Existing multicast schemes transmit data at a fixed rate that can accommodate the farthest located users in a cell. However, users belonging to the same multicast group can have widely different channel conditions. Thus existing schemes are too conservative by limiting the throughput of users close to the base station. We propose two proportional fair multicast scheduling algorithms that can adapt to dynamic channel states in cellular data networks that use time division multiplexing: inter-group proportional fairness (IPF) and multicast proportional fairness (MPF). These scheduling algorithms take into account (1) reported data rate requests from users which dynamically change to match their link states to the base station, and (2) the average received throughput of each user inside its cell. This information is used by the base station to select an appropriate data rate for each group. We prove that IPF and MPF achieve proportional fairness among groups and among all users inside a cell respectively. Through extensive packet-level simulations, we demonstrate that these algorithms achieve good balance between throughput and fairness among users and groups.

Multicast is an efficient means of transmitting the same content to multiple receivers while minimizing network resource usage. Applications that can benefit from multicast such as multimedia streaming and download, are now being deployed over 3G wireless data networks. Existing multicast schemes transmit data at a fixed rate that can accommodate the farthest located users in a cell. However, users belonging to the same multicast group can have widely different channel conditions. Thus existing schemes are too conservative by limiting the throughput of users close to the base station. We propose two proportional fair multicast scheduling algorithms that can adapt to dynamic channel states in cellular data networks that use time division multiplexing: Inter-group Proportional Fairness (IPF) and multicast proportional fairness (MPF). These scheduling algorithms take into account (1) reported data rate requests from users which dynamically change to match their link states to the base station, and (2) the average received throughput of each user inside its cell. This information is used by the base station to select an appropriate data rate for each group. We prove that IPF and MPF achieve proportional fairness among groups and among all users in a group inside a cell respectively. Through extensive packet-level simulations, we demonstrate that these algorithms achieve good balance between throughput and fairness among users and groups.

In current CDMA2000 standard, a packet data serving node (PDSN) acts as an IP gateway to the Internet. Mobile nodes (MN) connect to a PDSN using a point-to-point (PPP) session and IP packets are tunneled over the PPP session from the client to the PDSN which then routes the packets onto a packet network. A CDMA2000 network is a hierarchical network where packets from an MN to the PDSN are transported over a radio-access network (RAN). An MN could move from one RAN to another and still be anchored under the same PDSN; it is also possible that when an MN moves from one RAN to another, the anchor PDSN itself becomes different. In the latter case, there are two ways to handle mobility: (i) tear down the PPP session from the MN to the old PDSN and establish a new PPP session from the MN to the new PDSN, and (ii) use the fast-handoff mechanism as specified in the CDMA2000 standard where a P-P (PDSN to PDSN) tunnel is established to tunnel PPP frames from the old PDSN to the new PDSN and then to the MN. In this paper, we present a better approach to handling mobility than either of the above two techniques. The method is to migrate the PPP state from the old PDSN to the new PDSN transparent to the MN; once the PPP state migration is completed, the new PDSN will serve as the IP gateway to the MN. We have implemented the PPP migration technique and through experimental measurements show its benefits.

The emerging multiprotocol label switching (MPLS) networks enable network service providers to route bandwidth guaranteed paths between customer sites. This basic label switched path (LSP) routing is often enhanced using restoration routing which sets up alternate LSPs to guarantee uninterrupted connectivity in case network links or nodes along primary path fail. We address the problem of distributed routing of restoration paths, which can be defined as follows: given a request for a bandwidth guaranteed LSP between two nodes, find a primary LSP, and a set of backup LSPs that protect the links along the primary LSP. A routing algorithm that computes these paths must optimize the restoration latency and the amount of bandwidth used. We introduce the concept of "backtracking" to bound the restoration latency. We consider three different cases characterized by a parameter called backtracking distance D: 1) no backtracking (D=0); 2) limited backtracking (D=k); and 3) unlimited backtracking (D=/spl infin/). We use a link cost model that captures bandwidth sharing among links using various types of aggregate link-state information. We first show that joint optimization of primary and backup paths is NP-hard in all cases. We then consider algorithms that compute primary and backup paths in two separate steps. Using link cost metrics that capture bandwidth sharing, we devise heuristics for each case. Our simulation study shows that these algorithms offer a way to tradeoff bandwidth to meet a range of restoration latency requirements.

A virtual private network (VPN) is an overlay network that uses the public network to carry data traffic between corporate sites and users, maintaining privacy through the use of tunnelling protocols and security procedures. In the network-based model, VPN-aware network elements are placed within the network to set up concatenated tunnels between the user/site and enterprise resources to offer intranet VPN and remote access VPN. This paper identifies the important differences between a traditional VPN and the mobile VPN and proposes a hierarchical network architecture to efficiently realize network-based mobile VPNs. We address the problem of optimally provisioning VPN-aware devices, called IP service gateways (IPSGs), in the hierarchical network architecture for mobile VPNs, while taking into account of (1) the cost of links over which VPN tunnels are established, (2) the cost of provisioning a VPN customer on an IPSG, and (3) redundancy in IPSG provisioning for fault tolerance. We develop generic yet powerful problem formulations for different scenarios described above while considering practical requirements of the network elements and business requirements of the VPN service provider. The formulation becomes a set of integer programming problems. We solve several instances of the problem for a few practical cases and discuss their applications in the overall network design.

The emerging multi-protocol label switching (MPLS) networks enable network service providers to route bandwidth guaranteed paths between customer sites (see Davie, B. and Rekhter, Y., 2000; Awduche, D. et. al., 1999; Sharma, V. et al., 2002; Jamoussi et al., 2002). This basic label switched path (LSP) routing is often enhanced using restoration routing which sets up alternate LSPs to guarantee uninterrupted connectivity in case network links or nodes along the primary path fail. We address the problem of distributed routing of restoration paths, defined as follows: given a request for a bandwidth guaranteed LSP between two nodes, find a primary LSP and a set of backup LSPs that protect the links along the primary LSP. A routing algorithm that computes these paths must optimize the restoration latency and the amount of bandwidth used. We introduce the concept of "backtracking" to bound the restoration latency. We consider three different cases characterized by a parameter called backtracking distance, D: (1) no backtracking (D=0); (2) limited backtracking (D=k); (3) unlimited backtracking (D=/spl infin/). We use a link cost model that captures bandwidth sharing among links using various types of aggregate link state information. We first show that joint optimization of primary and backup paths is NP-hard in all cases. We then consider algorithms that compute primary and backup paths in two separate steps. Using link cost metrics that capture bandwidth sharing, we devise heuristics for each case. Our simulation study shows that these algorithms offer a way to tradeoff bandwidth to meet a range of restoration latency requirements.

Real-time online multi-player games are becoming increasingly popular due to advances in game design and the proliferation of broadband Internet access. However, fairness remains a major challenge when players over large geographic areas participate in a client-server based game together. The paper proposes a game-independent, network-based service, called Sync-MS, that balances the trade-off between response time and fairness. Sync-MS uses two mechanisms, sync-out and sync-in, to address state update fairness and player action fairness, respectively. Two metrics, ahead and behind, measured against the fair order, are defined to-evaluate Sync-MS's fairness performance. Simulation results show that Sync-MS dramatically improves player action fairness for all players while it slightly increases the average response time for players with shorter network delay to the game server.

In the current Internet, Web content is increasingly being cached closer to the end user to reduce network and Web server load and improve performance. Existing Web caching systems typically cache entire Web documents and attempt to keep them consistent with the origin server. This approach works well for text and images; for bandwidth intensive multimedia data such as audio and video, caching entire documents is not cost effective and does not scale. An alternative approach is to cache parts of the multimedia stream on different caches in the network and coordinate stream playback from these independent caches. From the perspective of the clients, the collection of cooperating distributed caches acts as a single fault tolerant, scalable cache. In this paper, we focus on data placement and replacement techniques for such co-operating distributed caches. Specifically, we propose the following new schemes that work together. 1) A family of distributed layouts, consisting of two layouts, namely RCache and Silo. The RCache layout is a simple, randomized, easy-to-implement layout that distributes constant length segments of a clip among caches and provides modest storage efficiency. The Silo scheme improves upon RCache; it accounts for long term clip popularity and intraclip segment popularity metrics and provides parameters to tune storage efficiency, server load, and playback switch-overs. 2) Rainbow, a local data replacement scheme based on the concept of segment access potential that accurately captures the popularity metrics. 3) Caching Token, a dynamic global data replacement or redistribution scheme that exploits existing data in distributed caches to minimize data distribution overhead. Our schemes optimize storage space, startup latency, server load, network bandwidth usage, and overhead from playback switch-overs. Our analytical and simulation results show that the silo scheme provides three to eight times higher cache hit ratio than a comparable traditional Web caching system that has the same amount of storage space.

This paper proposes to use a logical hypercube structure for detecting message stability in distributed systems. In particular, a stability detection protocol that uses such a superimposed logical structure is presented, and its scalability is compared with other known stability detection protocols. The main benefits of the logical hypercube approach are scalability, fault-tolerance, and refraining from overloading a single node or link in the system. These benefits become evident both by an analytical comparison and by simulations. Another important feature of the logical hypercube approach is that the performance of the protocol is in general not sensitive to the topology of the underlying physical network.

This paper presents a closed-loop (demand-driven) approach towards VoD services, called multicast with caching (Mcache). Servers use multicast to reduce bandwidth usage by serving multiple requests using a single data stream. However, this requires clients to delay receiving the movie until the multicast starts. Using regional cache servers, Mcache removes initial playout delays at the clients, because the clients can receive the prefix of a requested clip from regional caches while waiting for the multicast to start. In addition, the multicast containing the later portion of the movie can wait until the prefix is played out. While this use of caches has been proposed before, the novelty of our scheme lies in that the requests coming after the multicast starts can still be batched together to be served by multicast patches without any playout delays. The use of patches has been proposed to be used either with unicast or with playout delays. Mcache effectively hires the idea of a multicast patch with caches to provide a truly adaptive VoD service whose bandwidth usage is up to par with the best known open-loop schemes under high request rates while using only minimal bandwidth under low request rates. In addition, efficient use of multicast and caches removes the need for a priori knowledge of client request rates and client disk storage requirements which some of the existing schemes assume. This makes Mcache ideal for the current heterogeneous Internet environments where those parameters are hard to predict.

Group communication, providing virtual synchrony semantics, is a powerful paradigm for building distributed applications. For applications that require a large number of groups, significant performance gains can be attained if these groups share the resources required to provide virtual synchrony. A service that maps multiple user groups onto a small number of instances of a virtually synchronous implementation is called a Light-Weight Group Service. The paper describes the design of a light-weight group service able to operate in partitionable networks. Partitions pose challenges to the design of this service, in particular because inconsistent mapping decisions can be made when the system is partitioned. The paper focuses on the design of reconciliation mechanisms needed when a partition is healed.

Many scalable reliable multicast protocols use the local repair scheme where certain receivers retransmit packets by other receivers. Such schemes need a mechanism, called message stability, to ensure reliable delivery to all members of a multicast group and to delete those packets received by all members from the buffers of the local repairers. We propose a new protocol for message stability based on random gossiping. The protocol offers scalabilty and fault-tolerance by limiting each of its message transmissions only to a constant number of randomly chosen group members, hence eliminating message implosion and single point failure through the diffusion of responsibility. Both statistical analysis and simulation study indicate that our gossip-style message stability protocol can be highly effective for large-scale reliable multicast.

This paper proposes to use a logical hypercube structure for detecting message stability in distributed systems. In particular, a stability detection protocol that uses such a superimposed logical structure is presented, and its scalability is compared with other known stability detection protocols. The main benefits of the logical hypercube approach are scalability, fault-tolerance, and refraining from overloading a single node or link in the system. These benefits become evident both by an analytical comparison and by simulations. Another important feature of the logical hypercube approach is that the performance of the protocol is in general not sensitive to the topology of the underlying physical network.

The virtual synchrony model for group communication has proven to be a powerful paradigm for building distributed applications. In applications that use a large number of groups, significant performance gains can be attained if these groups share the resources required to provide virtual synchrony. A service that maps user groups onto instances of a virtually synchronous implementation is called a Light-Weight Group Service. This paper discusses the Light-Weight Group protocols in dynamic environments, where mappings cannot be defined a priori and may change over time. We show that it is possible to establish mappings that promote sharing and, at the same time, minimize interference. These mappings can be established in an automated manner using heuristics applied locally at each node. Experiments using an implementation in the Horus system show that significant performance improvements can be achieved with this approach.

The virtual synchrony model for group communication has proven to be a powerful paradigm for building distributed applications. Implementations of virtual synchrony usually require the use of failure detectors and failure recovery protocols. In applications that require the use of a large number of groups, significant performance gains can be attained if these groups share the resources required to provide virtual synchrony. A service that maps user groups onto instances of a virtually synchronous implementation is called a light-weight group service. This paper proposes a new design for the light-weight group protocols that enables the usage of this service in a transparent manner as a test case, the new design was implemented in the Horus system, although the underlying principles can be applied to other architectures as well. The paper also presents performance results from this implementation.