Remote driving, orteleoperating AutonomousVehicles (AVs), is a key application that emerging 5G networks aim to support. In this paper, we conduct a systematic feasibility study of AV teleoperation over commercial 5G networks from bothcross-layerandend-to-end (E2E)perspectives. Given the critical importance oftimely delivery of sensor data, such as camera and LiDAR data, for AV teleoperation, we focus in particular on the performance of uplink sensor data delivery. We analyze the impact of Physical Layer (PHY layer) 5G radio network factors, including channel conditions, radio resource allocation, and Handovers (HOs), on E2E latency performance. We also examine the impact of 5G networks on the performance of upper-layer protocols and E2E application Quality-of-Experience (QoE) of the adaptation mechanisms used for real-time sensor data delivery, such as Real-Time Streaming Protocol (RTSP) and Web Real Time Communication (WebRTC). Our study reveals the challenges posed by today’s 5G networks and the limitations of existing sensor data streaming mechanisms. The insights gained will help inform the co-design of future-generation wireless networks, edge cloud systems, and applications to overcome the low-latency barriers in AV teleoperation.

Recent years have witnessed a rapid growth of both 5G coverage and 5G users, attracting several measurement studies on its coverage, reliability and quality of service. However, the capabilities and potential impacts of 5G, especially Standalone (SA) 5G, still remain to be fully understood from a content provider (CP)’s perspective. This paper fills this gap by studying 5G networks used by over 23 million users in one year in Kuaishou, a popular crowdsourced live streaming platform. With passive and active measurements, we have the following key findings: i) SA 5G generally provides end-to-end performance improvements compared to 4G or Non-Standalone (NSA) 5G, but its advantage depends on both the number of cellular users and CP-level configurations. ii) In the radio access networks, SA 5G is more sensitive to access density, but has better handover tolerance. iii) Controlled experiments with 29 mobile device models on energy consumption refute some “conventional wisdom,” including the notion that 5G always consumes more power. iv) Traceroute-based active experiments in over 300 cities show that although users are “closer” to the internet in SA 5G due to the control and user plane separation, whether end-to-end latency benefits from that partly depends on the routing policy at the gateways. Furthermore, we propose a 5G-aware rebuffer strategy tested by 9 million viewers in Kuaishou, showing a 7% reduction in rebuffer proportion. Finally, we also provide new design space for other 5G participants.

The evolving network infrastructure, particularly the 5G core network, is increasingly adopting cloud technologies. This shift brings to the forefront the challenge of meeting the demanding per-packet processing requirements posed by multi-hundred Gbps Ethernet NICs (network interface cards). While traditional NFV (network function virtualization) platforms are effective on older hardware, the per-packet run-to-completion (RTC) execution model for per-packet processing suffers from stalling on state access due to L1/L2 cache misses. Although previous work applying software prefetching can mitigate the issues, their applications are fundamentally limited by the nature of a single execution stream, hence limiting them to batch lookups, suffering from control-flow divergence, and requiring manual tuning. To address the limitations, we introduce a novel interleaved function stream execution model that exploits the function-level parallelism through memory-level parallelism, targeting feature-rich network functions such as 5G Core. To provide the visibility into network functions, we introduce a novel programming model based on the principle of Granular Decomposition, which provides deep visibility into the state access by decoupling the state in a more fine-grained manner compared to traditional modular approaches. We integrate these two innovative designs into a new open-source NF platform, which we refer to as GuNFu. We have tested GuNFu on widely deployed network functions such as 5G UPF (User Plane Function), 5G AMF (Access Management Function), NAT (Network Address Translator) and others. Extensive evaluations reveal that GuNFu can achieve throughput ranging from 1.5 to 6 times over the traditional modular approach.

Roaming provides users with voice and data connectivity when traveling abroad. This is particularly the case in Europe where the "Roam like Home" policy established by the European Union in 2017 has made roaming affordable. Nonetheless, due to various policies employed by operators, roaming can incur considerable performance penalties as shown in past studies of 3G/4G networks. As 5G provides significantly higher bandwidth, how does roaming affect user-perceived performance? We present, to the best of our knowledge, the first comprehensive and comparative measurement study of commercial 5G in four European countries.Our measurement study is unique in the way it makes it possible to link key 5G mid-band channels and configuration parameters ("policies") used by various operators in these countries with their effect on the observed 5G performance from the network (in particular, the physical and MAC layers) and applications perspectives. Our measurement study not only portrays users’ observed quality of experience when roaming, but also provides guidance to optimize the network configuration and to users and application developers in choosing mobile operators. Moreover, our contribution provides the research community with the largest cross-country roaming 5G dataset to stimulate further research.

Neural-enhanced video streaming (e.g., super-resolution) is an ongoing revolution which can provide extremely high-quality video streaming services breaking the restriction of bandwidth. However, such enhancements require intense computation power that is not affordable for a single mobile device, which hinders their real-world deployment. To address the limitation, we propose OASIS, the first system that facilitates multiple users in close proximity to execute intense neural-enhanced video streaming in realtime. To this end, OASIS intelligently distributes computation tasks among multiple mobile devices, selects appropriate video bitrates and super-resolution models, and optimizes video chunk delivery. As a result, the expensive neural-enhanced streaming is done through distributed collaboration, achieving optimal quality of experience (QoE). We implement and evaluate OASIS on commodity smartphones from different vendors, under various network and computation conditions. Extensive experiments demonstrate the high efficiency of OASIS: it improves the video streaming QoE by 40%-200% and reduces each participant's energy consumption by 60% when the system scales up from a single device to six devices.

By aggregating multiple channels, Carrier Aggregation (CA) is an important technology for boosting cellular network bandwidth. Given diverse radio bands made available in 5G networks, CA plays a particularly critical role in achieving the goal of multi-Gbps throughput performance. In this paper, we carry out a timely comprehensive measurement study of CA deployment in commercial 5G networks (as well as 4G networks). We identify the key factors that influence whether CA is deployed and when, as well as which band combinations are used. Thus, we reveal the challenges posed by CA in 5G performance analysis and prediction as well as their implications in application quality-of-experience (QoE). We argue for and develop a novel CA-aware deep learning framework, dubbed Prism5G, which explicitly accounts for the complexity introduced by CA to more effectively predict 5G network throughput performance. Through extensive evaluations, we demonstrate the superiority of Prism5G over existing throughput prediction algorithms. Prism5G improves 5G throughput prediction accuracy by over 14% on average and a maximum of 22%. Using two use cases as examples, we further illustrate how Prism5G can aid applications in optimizing QoE performance.

5G in mid-bands has become the dominant deployment of choice in the world. We present - to the best of our knowledge - the first comprehensive and comparative cross-country measurement study of commercial mid-band 5G deployments in Europe and the U.S., filling a gap in the existing 5G measurement studies. We unveil the key 5G mid-band channels and configuration parameters used by various operators in these countries, and identify the major factors that impact the observed 5G performance both from the network (physical layer) perspective as well as the application perspective. We characterize and compare 5G mid-band throughput and latency performance by dissecting the 5G configurations, lower-layer parameters as well as deployment settings. By cross-correlating 5G parameters with the application decision process, we demonstrate how 5G parameters affect application QoE metrics and suggest a simple approach for QoE enhancement. Our study sheds light on how to better configure and optimize 5G mid-band networks, and provides guidance to users and application developers on operator choices and application QoE tuning. We released the datasets and artifacts at https://github.com/SIGCOMM24-5GinMidBands/artifacts.

QUIC is expected to be a game-changer in improving web application performance. In this paper, we conduct a systematic examination of QUIC's performance over high-speed networks. We find that over fast Internet, the UDP+QUIC+HTTP/3 stack suffers a data rate reduction of up to 45.2% compared to the TCP+TLS+HTTP/2 counterpart. Moreover, the performance gap between QUIC and HTTP/2 grows as the underlying bandwidth increases. We observe this issue on lightweight data transfer clients and major web browsers (Chrome, Edge, Firefox, Opera), on different hosts (desktop, mobile), and over diverse networks (wired broadband, cellular). It affects not only file transfers, but also various applications such as video streaming (up to 9.8% video bitrate reduction) and web browsing. Through rigorous packet trace analysis and kernel- and user-space profiling, we identify the root cause to be high receiver-side processing overhead, in particular, excessive data packets and QUIC's user-space ACKs. We make concrete recommendations for mitigating the observed performance issues.

The advent of diverse frequency bands in 5G networks has promoted measurement studies focused on 5G signal propagation, aiming to understand its pathloss, coverage, and channel quality characteristics. Nonetheless, conducting a thorough 5G measurement campaign is markedly laborious given the large number of samples that must be collected. To alleviate this burden, the present contribution leverages principled active learning (AL) methods to prudently select only a few, yet most informative locations to collect samples. The core idea is to rely on a Gaussian Process (GP) model to efficiently extrapolate measurements throughout the coverage area. Specifically, an ensemble (E) of GP models is adopted that not only provides a rich learning function space, but also quantifies uncertainty, and can offer accurate predictions. Building on this EGP model, a suite of acquisition functions (AFs) are advocated to query new locations on-the-fly. To account for realistic scenaria, the proposed AFs are augmented with a novel distance-based AL rule that selects informative samples, while penalizing queries at long distances. Numerical tests on 5G data generated by the Sionna simulator and on real urban and suburban datasets, showcase the merits of the novel EGP-AL approaches.

The two leading solution paradigms for imitation learning (IL), BC and GAIL, each suffers from notable drawbacks. BC, a supervised learning approach to mimic expert actions, is vulnerable to covariate shift. GAIL applies adversarial training to minimize the discrepancy between expert and learner behaviors, which is prone to unstable training and mode collapse. In this work, we propose DC – Distributional Cloning – a novel IL approach for addressing the covariate shift and mode collapse problems simultaneously. DC directly maximizes the likelihood of observed expert and learner demonstrations, and gradually encourages the learner to evolve towards expert behaviors based on an averaging effect. The DC solution framework contains two stages in each training loop, where in stage one the mixed expert and learner state distribution is estimated via SoftFlow, and in stage two the learner policy is trained to match both the expert’s policy and state distribution via ADMM. Experimental evaluation of DC compared with several baselines in 10 different physics-based control tasks reveal superior results in learner policy performance, training stability, and mode distribution preservation.

QUIC is a multiplexed transport-layer protocol over UDP and comes with enforced encryption. It is expected to be a game-changer in improving web application performance. Together with the network layer and layers below, UDP, QUIC, and HTTP/3 form a new protocol stack for future network communication, whose current counterpart is TCP, TLS, and HTTP/2. In this study, to understand QUIC's performance over high-speed networks and its potential to replace the TCP stack, we carry out a series of experiments to compare the UDP+QUIC+HTTP/3 (QUIC) stack and the TCP+TLS+HTTP/2 (HTTP/2) stack. Preliminary measurements on file download reveal that QUIC suffers from a data rate reduction compared to HTTP/2 across different hosts.

A key challenge with supervised learning (e.g., image classification) is the shift of data distribution and domain from training to testing datasets, so-called “domain shift” (or “distribution shift”), which usually leads to a reduction of model accuracy. Various meta-learning approaches have been proposed to prevent the accuracy loss by learning an adaptable model with training data, and adapting it to test time data from a new data domain. However, when the domain shift occurs in multiple domain dimensions (e.g., images may be transformed by rotations, transitions, and expansions), the average predictive power of the adapted model will deteriorate. To tackle this problem, we propose a domain disentangled meta-learning (DDML) framework. DDML disentangles the data domain by dimensions, learns the representations of domain dimensions independently, and adapts to the domain of test time data. We evaluate our DDML on image classification problems using three datasets with distribution shifts over multiple domain dimensions. Comparing to various baselines in meta-learning and empirical risk minimization, our DDML approach achieves consistently higher classification accuracy with the test time data. These results demonstrate that domain disentanglement reduces the complexity of the model adaptation, thus increases the model generalizability, and prevents it from overfitting.

Performance of caching algorithms not only determines the quality of experience for users, but also affects the operating and capital expenditures for cloud service providers. Today's production systems rely on heuristics such as LRU (least recently used) and its variants, which work well for certain types of workloads, and cannot effectively cope with diverse and time-varying workload characteristics. While learning-based caching algorithms have been proposed to deal with these challenges, they still impose assumptions about workload characteristics and often suffer poor generalizability.

Unlike previous generation cellular technologies, 5G networks support diverse radio bands from low-band, mid-band to (mmWave) high-band, and offer a wide variety of new and enhanced features. In particular, 3GPP 5G standards adopt a flow-based 5G Quality-of-Service (QoS) framework that allows more flexibility in mapping QoS "flows" to data radio bearers. Nonetheless, the 5G QoS classes are pre-defined and QoS treatment is limited to the "flow" level. As we will argue in an earlier paper, the 5G QoS framework cannot fully and intelligently utilize the diversity of 5G radio bands and other capabilities to cope with fast varying channel conditions, and is therefore inadequate in meeting the quality-of-experience (QoE) requirements of many emerging applications such as augmented/virtual realities (AR/VR) and connected and autonomous vehicles (CAV). This has led us to advance a novel software-defined, fine-grained QoS framework for 5G/NextG networks.In this "work in progress" paper, we share our initial experience in prototyping the proposed fine-grained QoS framework. Our framework extends both the 5G core network and 5G radio access network (RAN) functionality to enable intelligent control of radio resources in a fashion that exploits application semantics to improve user QoE. We discuss in detail about the changes in different systems and its individual components, share the current state of implementation progress (work completed and in-progress) and finally our evaluation plan to validate the framework when the implementation is complete.

5G-NR is beginning to be widely deployed in the mmWave frequencies in urban areas in the US and around the world. Due to the directional nature of mmWave signal propagation, improving performance of such deployments heavily relies on beam management and deployment configurations. We perform detailed measurements of mmWave 5G deployments by two major commercial 5G operators in the US in two diverse environments: an open field with a baseball park (BP) and a downtown urban canyon region (DT), using smartphone-based tools that collect detailed measurements across several layers (PHY, MAC and up) such as beam-specific metrics like signal strength, beam switch times, and throughput per beam. Our measurement analysis shows that the parameters of the two deployments differ in a number of aspects: number of beams used, number of channels aggregated, and density of deployments, which reflect on the throughput performance. Our measurement-driven propagation analysis demonstrates that narrower beams experience a lower path-loss exponent than wider beams, which combined with up to eight frequency channels aggregated on up to eight beams can deliver a peak throughput of 1.2 Gbps at distances greater than 100m.

The ability to dynamically scale in/out network functions (NFs) on multiple cores/servers to meet traffic demands is a key benefit of network function virtualization (NFV). The stateful NF operations make NFV scaling a challenging task: if care is not taken, NFV scaling can lead to incorrect operations and poor performance. We advocate two general abstractions, NFlow and Match-Value Table (MVT), for NFV packet processing pipelines. We present formal definitions of the abstractions and discuss how they can facilitate NFV scaling by minimizing or eliminating shared states. Using NFs implemented with the proposed abstractions, we conduct extensive experiments and demonstrate their efficacy in terms of correctness and performance of NFV scaling.

The emerging volumetric videos offer a fully immersive, six degrees of freedom (6DoF) viewing experience, at the cost of extremely high bandwidth demand. In this paper, we design, implement, and evaluate Vues, an edge-assisted transcoding system that delivers high-quality volumetric videos with low bandwidth requirement, low decoding overhead, and high quality of experience (QoE) on mobile devices. Through an IRB-approved user study, we build a first-of-its-kind QoE model to quantify the impact of various factors introduced by transcoding volumetric content into 2D videos. Motivated by the key observations from this user study, Vues employs a novel multiview approach with the overarching goal of boosting QoE. The Vues edge server adaptively transcodes a volumetric video frame into multiple 2D views with the help of a few lightweight machine learning models and strategically balances the extra bandwidth consumption of additional views and the improved QoE, indicated by our QoE model. The client selects the view that optimizes the QoE among the delivered candidates for display. Comprehensive evaluations using a prototype implementation indicate that Vues dramatically outperforms existing approaches. On average, it improves the QoE by 35% (up to 85%), compared to single-view transcoding schemes, and reduces the bandwidth consumption by 95%, compared to the state-of-the-art that directly streams volumetric videos.

With 5G's support for diverse radio bands and different deployment modes, e.g., standalone (SA) vs. non-standalone (NSA), mobility management - especially the handover process - becomes far more complex. Measurement studies have shown that frequent handovers cause wild fluctuations in 5G throughput, and worst, service outages. Through a cross-country (6,200 km+) driving trip, we conduct in-depth measurements to study the current 5G mobility management practices adopted by three major U.S. carriers. Using this rich dataset, we carry out a systematic analysis to uncover the handover mechanisms employed by 5G carriers, and compare them along several dimensions such as (4G vs. 5G) radio technologies, radio (low-, mid- & high-)bands, and deployment (SA vs. NSA) modes. We further quantify the impact of mobility on application performance, power consumption, and signaling overheads. We identify key challenges facing today's NSA 5G deployments which result in unnecessary handovers and reduced coverage. Finally, we design a holistic handover prediction system Prognos and demonstrate its ability to improve QoE for two 5G applications 16K panoramic VoD and realtime volumetric video streaming. We have released the artifacts of our study at https://github.com/SIGCOMM22-5GMobility/artifact.

5G has seen rapid growth recently, attracting several measurement studies on its coverage, connectivity and quality of service. However, there is still a lack of understanding of 5G's capabilities and potential impacts from a content provider (CP)'s perspective. This paper fills in this gap by studying 5G networks used by over 23 million users in one year in Kuaishou, a popular crowdsourced live streaming platform. Our measurements provide the following discoveries. i) Standalone (SA) 5G generally provides end-to-end performance improvement as compared with 4G or non-SA (NSA) 5G, but its advantage depends on both the number of cellular users and CP-level configurations. ii) In the radio access network, SA 5G is more sensitive to access density but has better handover tolerance. iii) Controlled experiments with 29 mobile device models on energy consumption refute some "conventional wisdom," including that 5G always consumes more power. iv) Traceroute-based active experiments in over 300 cities show that although users are "closer" to the internet in SA 5G, their end-to-end latency may not benefit from that. Furthermore, we show new design space for 5G participants and provide a 5G-aware rebuffer strategy tested by 9 million viewers in Kuaishou, with a 7% reduction in rebuffer proportion.

Emergence of autonomous vehicles (AVs) offers the potential to fundamentally transform the way how urban transport systems be designed and deployed, and alter the way we view private car ownership. In this article we advocate a forward-looking, ambitious and disruptivesmart cloud commuting system(SCCS) for future smart cities based on shared AVs. Employing giant pools of AVs of varying sizes, SCCS seeks to supplant and integrate various modes of transport – most of personal vehicles, low ridership public buses, and taxis used in today’s private and public transport systems – in a unified, on-demand fashion, and provides passengers with a fast, convenient, and low cost transport service for theirdaily commutingneeds. To explore feasibility and efficiency gains of the proposed SCCS, we model SCCS as a queueing system with passengers’ trip demands (as jobs) being served by the AVs (as servers). Using a 1-year real trip dataset from Shenzhen China, we quantify (i) how design choices, such as the numbers of depots and AVs, affect the passenger waiting time and vehicle utilization; and (ii) how much efficiency gains (i.e., reducing the number of service vehicles, and improving the vehicle utilization) can be obtained by SCCS comparing to the current taxi system. Our results demonstrate that the proposed SCCS framework can serve the trip demands with 22 percent fewer vehicles and 37 percent more vehicle utilization, which shed lights on the design feasibility of future smart transportation systems.

Urban traffic status (e.g., traffic speed and volume) is highly dynamic in nature, namely, varying across space and evolving over time. Thus, predicting such traffic dynamics is of great importance to urban development and transportation management. However, it is very challenging to solve this problem due to spatial-temporal dependencies and traffic uncertainties. In this article, we solve the traffic dynamics prediction problem from Bayesian meta-learning perspective and propose a novel continuous spatial-temporal meta-learner (cST-ML), which is trained on a distribution of traffic prediction tasks segmented by historical traffic data with the goal of learning a strategy that can be quickly adapted to related but unseen traffic prediction tasks. cST-ML tackles the traffic dynamics prediction challenges by advancing the Bayesian black-box meta-learning framework through the following new points: (1) cST-ML captures the dynamics of traffic prediction tasks using variational inference, and to better capture the temporal uncertainties within tasks, cST-ML performs as a rolling window within each task; (2) cST-ML has novel designs in architecture, where CNN and LSTM are embedded to capture the spatial-temporal dependencies between traffic status and traffic-related features; (3) novel training and testing algorithms for cST-ML are designed. We also conduct experiments on two real-world traffic datasets (taxi inflow and traffic speed) to evaluate our proposed cST-ML. The experimental results verify that cST-ML can significantly improve the urban traffic prediction performance and outperform all baseline models especially when obvious traffic dynamics and temporal uncertainties are presented.

Providing resilient network control is a critical concern for deploying Software-Defined Networking (SDN) into Wide-Area Networks (WANs). For performance reasons, a Software-Defined WAN is divided into multiple domains controlled by multiple controllers with a logically centralized view. Under controller failures, we need to remap the control of offline switches from failed controllers to other active controllers. Existing solutions have three limitations: (1) the least flow programmability (e.g., the ability to change paths of flows) cannot be maintained; (2) active controllers could be overloaded, interrupting their normal operations; (3) network performance could be degraded because of the increasing controller-switch communication overhead. In this paper, we propose RetroFlow+ to recover the flow programmability and achieve low communication overhead during controller failures. By intelligently configuring a set of selected offline switches working under the legacy routing mode and several active controllers releasing a few control resources, RetroFlow+ enables active controllers to use the minimum control resource to sustain the flow programmability. RetroFlow+ also smartly transfers the control of offline switches with the SDN routing mode to active controllers to minimize the communication overhead from these offline switches to the active controllers. Simulation results show that RetroFlow+ realizes low communication overhead, recovers all offline flows under one and two controller failures, and improves the flow recovery percentage up to 70% under three controller failures, compared with the state-of-the-art solution.

As mobile networks proliferate, we are experiencing a strong diversification of services, which requires greater flexibility from the existing network. Network slicing is proposed as a promising solution for resource utilization in 5G and future networks to address this dire need. In network slicing, dynamic resource orchestration and network slice management are crucial for maximizing resource utilization. Unfortunately, this process is too complex for traditional approaches to be effective due to a lack of accurate models and dynamic hidden structures. We formulate the problem as a Constrained Markov Decision Process (CMDP) without knowing models and hidden structures. Additionally, we propose to solve the problem using CLARA, a Constrained reinforcement LeArning based Resource Allocation algorithm. In particular, we analyze cumulative and instantaneous constraints using adaptive interior-point policy optimization and projection layer, respectively. Evaluations show that CLARA clearly outperforms baselines in resource allocation with service demand guarantees.

As the plethora of Internet of Things (IoT) devices gradually make their way into our lives, several Cloud Service Providers (CSPs) have developed IoT gateway platforms (SDKs) that solely connects IoT devices to their respective cloud. Such gateways have 1) cumbersome IoT device configuration; 2) inflexible IoT data managements; and 3) support no/little cross-vendor edge computation and cloud analytics. We term these commercial gateway SDKs as cloud-centric. In this paper, we study the state-of-the-art vendor-locked IoT Gateway solutions and approaches and propose an edge-centric paradigm through an evolutionary framework, dubbed VeerEdge for developing IoT gateways. We leverage computing and storage capabilities at the network edge for edge-based device & IoT service management and data processing. We exploit availability of multiple cloud services for "best" IoT data analytics. Evaluation results show that VeerEdge achieves this with negligible overhead in terms of latency, CPU and RAM usage when compared to state-of-the-art industrial IoT gateways.

Motivated by the rapid deployment of 5G, we carry out an in-depth measurement study of the performance, power consumption, and application quality-of-experience (QoE) of commercial 5G networks in the wild. We examine different 5G carriers, deployment schemes (Non-Standalone, NSA vs. Standalone, SA), radio bands (mmWave and sub 6-GHz), protocol configurations (_e.g._ Radio Resource Control state transitions), mobility patterns (stationary, walking, driving), client devices (_i.e._ User Equipment), and upper-layer applications (file download, video streaming, and web browsing). Our findings reveal key characteristics of commercial 5G in terms of throughput, latency, handover behaviors, radio state transitions, and radio power consumption under the above diverse scenarios, with detailed comparisons to 4G/LTE networks. Furthermore, our study provides key insights into how upper-layer applications should best utilize 5G by balancing the critical tradeoff between performance and energy consumption, as well as by taking into account the availability of both network and computation resources. We have released the datasets and tools of our study at https://github.com/SIGCOMM21-5G/artifact.

Content Delivery Networks (CDNs) are critical for providing good user experience of cloud services. CDN providers typically collect various multivariate Key Performance Indicators (KPIs) time series to monitor and diagnose system performance. State-of-the-art anomaly detection methods mostly use deep learning to extract the normal patterns of data, due to its superior performance. However, KPI data usually exhibit non-additive Gaussian noise, which makes it difficult for deep learning models to learn the normal patterns, resulting in degraded performance in anomaly detection. In this paper, we propose a robust and noise-resilient anomaly detection mechanism using multivariate KPIs. Our key insight is that different KPIs are constrained by certain time-invariant characteristics of the underlying system, and that explicitly modelling such invariance may help resist noise in the data. We thus propose a novel anomaly detection method called SDFVAE, short for Static and Dynamic Factorized VAE, that learns the representations of KPIs by explicitly factorizing the latent variables into dynamic and static parts. Extensive experiments using real-world data show that SDFVAE achieves a F1-score ranging from 0.92 to 0.99 on both regular and noisy dataset, outperforming state-of-the-art methods by a large margin.

Demands for wide-area connectivity between enterprise site-edge networks and central office core networks/cloud data centers have grown rapidly. Various software defined wide area network (SD-WAN) solutions have been developed with the primary aim of improving WAN link utilization. However, mechanisms used by existing SD-WAN solutions fail to provide high reliability and performance required by today's edge to cloud applications. In this article, we present WAN-aware MPTCP which seamlessly aggregates multiple WAN links into a “big pipe” for better WAN resilience thus minimizing application performance degradation under WAN link failures. We leverage the congestion control of MPTCP to balance traffic across multiple WAN links. The key innovation is to combine LAN virtualization at end systems with WAN virtualization at SD-WAN gateways. Through evaluation in both emulated testbeds and real-world deployment, we demonstrate the performance gain of WAN-aware MPTCP in terms of resilience and throughput over existing SD-WAN solutions.

Power-efficient Data Center Networks (DCNs) have been proposed to save power of DCNs using OpenFlow. In these DCNs, the OpenFlow controller adaptively turns on/off links and OpenFlow switches to form a minimum-power subnet that satisfies the traffic demand. As the subnet changes, flows are dynamically routed and rerouted to the routes composed of active switches and links. However, existing flow scheduling schemes could cause undesired results: (1) power inefficiency: due to unbalanced traffic allocation on active routes, extra switches and links may be activated to cater to bursty traffic surges on congested routes, and (2) Quality of Service (QoS) fluctuation: because of the limited flow entry processing ability, switches may not be able to timely install/delete/update flow entries to properly route/reroute flows. In this paper, we propose AggreFlow, a dynamic flow scheduling scheme that achieves power efficiency and QoS improvement using three techniques: Flow-set Routing, Lazy Rerouting, and Adaptive Rerouting. Flow-set Routing achieves load balancing with a small number of flow entry operations by routing flows in a coarse-grained flow-set fashion. Lazy Rerouting spreads rerouting operations over a relatively long period of time, reducing the burstiness of entry operation on switches. Adaptive Rerouting selectively reroutes flow-sets to maintain load balancing. We built an NS3 based fat-tree network simulation platform to evaluate AggreFlow's performance. The simulation results show that AggreFlow reduces power consumption by about 18%, yet achieving load balancing and improved QoS (low packet loss rate and reducing the number of processing entries for flow scheduling by 98%), compared with baseline schemes.

In recent years, the effort of promoting versatile, easy to manage routing schemes, as a replacement to OSPF has gathered momentum particularly in the context of large-scale enterprise networks, data center networks and software-defined wide area networks (SD-WANs). Such routing schemes rely on embedding the network into a geometric/topological space (e.g. a binary tree) to facilitate multi-path routing with reduced state maintenance and quick recovery in localized failure scenarios. In this work, we propose a systematic framework to embed the network topology into a hierarchical binary virtual-identityspace that is particularly amenable to multi-path routing. Our methodology firstly involves a relaxed form of the connected graph bi-partitioning problem that exploits a geometric embedding of the network in an n-dimensional Euclidean space (n being the number of hosts in the network) based on the Moore-Penrose pseudo inverse of the Laplacian for the graph associated with the network. The edges of the network are mapped to a weight distribution that helps construct a spanning tree from the core of the network towards the periphery, thereby providing a point of symmetry in the network to facilitate balanced bipartitions. This, in turn, yields a (nearly) full balanced binary tree embedding of the network and consequently a good virtual-id space. We also explore the binary identity assignment problem in another point of view by using bi-connected graph as the input graph to introduce a recursive bipartition algorithm. Through rigorous theoretical analysis and experimentation, we demonstrate that our methods perform well within reasonable bounds of computational complexity.

There is a growing demand for real-time analysis of network data streams. In recent years, Model Driven Telemetry (MDT) has been developed - in place of conventional methods such as Simple Network Management Protocol (SNMP), Syslog and CLI commands - to provide a fine-grain holistic view of a network at the control, data and management planes. High-frequency MDT data streams generated from network devices enable new ways of designing Network Operation and Management (OAM) solutions, laying the foundation for future "self-driving" networks.In this paper we study anomaly detection using MDT data streams in a data center environment. In many commercial data centers, BGP is re-purposed for (policy-driven, path-based) intra-routing (as opposed to inter-domain routing that it was originally designed for) to take advantage of rich path diversity. Several vendors have developed MDT data models using YANG that allow routers/switches to express and stream various BGP features for (centralized) network OAM operations. We develop a systematic MDT data processing and feature selection framework that is portable to multiple MDT vendors. Furthermore, we advance NetCorDenstream that builds and improves upon OutlierDenStream proposed in [10] for real-time detection of streamed anomalous MDT data. We show that NetCorDenstream achieves a 59% reduction in alarms raised when compared with OutlierDenStream, thereby reducing the (attention) burden placed on network operators. In particular, it increases alarm detection precision significantly while decreasing false alarms at the expense of a slightly delayed response time.

The emerging 5G services offer numerous new opportunities for networked applications. In this study, we seek to answer two key questions: i) is the throughput of mmWave 5G predictable, and ii) can we build "good" machine learning models for 5G throughput prediction? To this end, we conduct a measurement study of commercial mmWave 5G services in a major U.S. city, focusing on the throughput as perceived by applications running on user equipment (UE). Through extensive experiments and statistical analysis, we identify key UE-side factors that affect 5G performance and quantify to what extent the 5G throughput can be predicted. We then propose Lumos5G -- a composable machine learning (ML) framework that judiciously considers features and their combinations, and apply state-of-the-art ML techniques for making context-aware 5G throughput predictions. We demonstrate that our framework is able to achieve 1.37X to 4.84X reduction in prediction error compared to existing models. Our work can be viewed as a feasibility study for building what we envisage as a dynamic 5G throughput map (akin to Google traffic map). We believe this approach provides opportunities and challenges in building future 5G-aware apps.

Imitation learning (IL) aims to learn a policy from expert demonstrations that minimizes the discrepancy between the learner and expert behaviors. Various imitation learning algorithms have been proposed with different pre-determined divergences to quantify the discrepancy. This naturally gives rise to the following question: Given a set of expert demonstrations, which divergence can recover the expert policy more accurately with higher data efficiency? In this work, we propose f-GAIL – a new generative adversarial imitation learning model – that automatically learns a discrepancy measure from the f-divergence family as well as a policy capable of producing expert-like behaviors. Compared with IL baselines with various predefined divergence measures, f-GAIL learns better policies with higher data efficiency in six physics-based control tasks.

RDMA communication in virtual private cloud (VPC) networks is still a challenging job due to the difficulty in fulfilling all virtualization requirements without sacrificing RDMA communication performance. To address this problem, this paper proposes a software-defined solution, namely, MasQ, which is short for "queue masquerade". The core insight of MasQ is that all RDMA communications should associate with at least one queue pair (QP). Thus, the requirements of virtualization, such as network isolation and the application of security rules, can be easily fulfilled if QP's behavior is properly defined. In particular, MasQ exploits the virtio-based paravirtualization technique to realize the control path. Moreover, to avoid performance overhead, MasQ leaves all data path operations, such as sending and receiving, to the hardware. We have implemented MasQ in the OpenFabrics Enterprise Distribution (OFED) framework and proved its scalability and performance efficiency by evaluating it against typical applications. The results demonstrate that MasQ achieves almost the same performance as bare-metal RDMA for data communication.

Next-basket recommendation (NBR) is prevalent in e-commerce and retail industry. In this scenario, a user purchases a set of items (a basket) at a time. NBR performs sequential modeling and recommendation based on a sequence of baskets. NBR is in general more complex than the widely studied sequential (session-based) recommendation which recommends the next item based on a sequence of items. Recurrent neural network (RNN) has proved to be very effective for sequential modeling, and thus been adapted for NBR. However, we argue that existing RNNs cannot directly capture item frequency information in the recommendation scenario.

We conduct to our knowledge a first measurement study of commercial 5G performance on smartphones by closely examining 5G networks of three carriers (two mmWave carriers, one mid-band carrier) in three U.S. cities. We conduct extensive field tests on 5G performance in diverse urban environments. We systematically analyze the handoff mechanisms in 5G and their impact on network performance. We explore the feasibility of using location and possibly other environmental information to predict the network performance. We also study the app performance (web browsing and HTTP download) over 5G. Our study consumes more than 15 TB of cellular data. Conducted when 5G just made its debut, it provides a “baseline” for studying how 5G performance evolves, and identifies key research directions on improving 5G users’ experience in a cross-layer manner. We have released the data collected from our study (referred to as 5Gophers) at https://fivegophers.umn.edu/www20.

It is well-known that online services resort to various cookies to track users through users' online service identifiers (IDs) - in other words, when users access online services, various “fingerprints” are left behind in the cyberspace. As they roam around in the physical world while accessing online services via mobile devices, users also leave a series of “footprints” - i.e., hints about their physical locations - in the physical world. This poses a potent new threat to user privacy: one can potentially correlate the “fingerprints” left by the users in the cyberspace with “footprints” left in the physical world to infer and reveal leakage of user physical world privacy, such as frequent user locations or mobility trajectories in the physical world - we refer to this problem as user physical world privacy leakage via user cyberspace privacy leakage. In this paper we address the following fundamental question: what kind - and how much - of user physical world privacy might be leaked if we could get hold of such diverse network datasets even without any physical location information. In order to conduct an in-depth investigation of these questions, we utilize the network data collected via a DPI system at the routers within one of the largest Internet operator in Shanghai, China over a duration of one month. We decompose the fundamental question into the three problems: i) linkage of various online user IDs belonging to the same person via mobility pattern mining; ii) physical location classification via aggregate user mobility patterns over time; and iii) tracking user physical mobility. By developing novel and effective methods for solving each of these problems, we demonstrate that the question of user physical world privacy leakage via user cyberspace privacy leakage is not hypothetical, but indeed poses a real potent threat to user privacy.

Network Function Virtualization (NFV) advocates running service function chains (SFCs) on commodity servers as software, thereby providing a new level of flexibility to the deployment and management of network services. However, as we move from 10/40 Gbps to 100/400 Gbps line rates, it is challenging to build an NF execution framework that can deliver high performance at the maximum line speed using commodity servers, while providing scalability and flexibility afforded by software. In this paper, we investigate a fundamental problem of any NFV framework, i.e. how to execute SFCs on commodity servers by examining and comparing the performance of two execution models: the pipeline and run-to-completion models. In particular, we investigate how the multi-core server architecture affects the performance of SFC execution models by conducting extensive experiments on a testbed and shed new insights on the design and optimization of SFC execution models.

In this paper, we develop an optimization decomposition framework for cache management under “BIG” cache abstraction which fully utilizes the cache resources in a cache network. We assign a utility function to each content, and formulate a joint optimization problem to maximize the overall utility of a cache network. We show that this global network utility maximization problem can be decomposed into two sub-problems, the cache allotment problem and object placement problem, which can be solved separately and iteratively. This decoupling enables us to separately optimize the performance objectives from the perspectives of content providers, cache network operators, and users. We provide exact solution to the object placement problem with Poisson and Pareto request interarrival distributions. We also devise a primal-dual algorithm for online content management. We conduct extensive numerical analysis and simulations to evaluate the performance of our optimization decomposition framework, and study the impact of various key factors such as hazard rate functions of the request interarrival distributions and object popularities. We show that our optimization decomposition framework outperform existing heuristic methods.

Providing resilient network control is a critical concern for deploying Software-Defined Networking (SDN) into Wide-Area Networks (WANs). For performance reasons, a Software-Defined WAN is divided into multiple domains controlled by multiple controllers with a logically centralized view. Under controller failures, we need to remap the control of offline switches from failed controllers to other active controllers. Existing solutions could either overload active controllers to interrupt their normal operations or degrade network performance because of increasing the controller-switch communication overhead. In this paper, we propose RetroFlow to achieve low communication overhead without interrupting the normal processing of active controllers during controller failures. By intelligently configuring a set of selected offline switches working under the legacy routing mode, RetroFlow relieves the active controllers from controlling the selected offline switches while maintaining the flow programmability (e.g., the ability to change paths of flows) of SDN. RetroFlow also smartly transfers the control of offline switches with the SDN routing mode to active controllers to minimize the communication overhead from these offline switches to the active controllers. Simulation results show that compared with the baseline algorithm, RetroFlow can reduce the communication overhead up to 52.6% during a moderate controller failure by recovering 100% flows from offline switches and can reduce the communication overhead up to 61.2% during a serious controller failure by setting to recover 90% of flows from offline switches.

Inspired by convolutional neural networks on 1D and 2D data, graph convolutional neural networks (GCNNs) have been developed for various learning tasks on graph data, and have shown superior performance on real-world datasets. Despite their success, there is a dearth of theoretical explorations of GCNN models such as their generalization properties. In this paper, we take a first step towards developing a deeper theoretical understanding of GCNN models by analyzing the stability of single-layer GCNN models and deriving their generalization guarantees in a semi-supervised graph learning setting. In particular, we show that the algorithmic stability of a GCNN model depends upon the largest absolute eigenvalue of its graph convolution filter. Moreover, to ensure the uniform stability needed to provide strong generalization guarantees, the largest absolute eigenvalue must be independent of the graph size. Our results shed new insights on the design of new & improved graph convolution filters with guaranteed algorithmic stability. We evaluate the generalization gap and stability on various real-world graph datasets and show that the empirical results indeed support our theoretical findings. To the best of our knowledge, we are the first to study stability bounds on graph learning in a semi-supervised setting and derive generalization bounds for GCNN models.

To improve traffic management ability, Internet Service Providers (ISPs) are gradually upgrading legacy network devices to programmable devices that support Software-Defined Networking (SDN). The coexistence of legacy and SDN devices gives rise to a hybrid SDN. Existing hybrid SDNs do not consider the potential performance issues introduced by a centralized SDN controller: flow requests processed by a highly loaded controller may experience long-tail processing delay; inappropriate multi-controller deployment could increase the propagation delay of flow requests. In this paper, we propose to jointly consider the deployment of SDN switches and their controllers for hybrid SDNs. We formulate the joint problem as an optimization problem that maximizes the number of flows that can be controlled and managed by the SDN and minimizes the propagation delay of flow requests between SDN controllers and switches under a given upgrade budget constraint. We show this problem is NP-hard. To efficiently solve the problem, we propose some techniques (e.g., strengthening the constraints and adding additional valid inequalities) to accelerate the global optimization solver for solving the problem for small networks and an efficient heuristic algorithm for solving it for large networks. The simulation results from real network topologies illustrate the effectiveness of the proposed techniques and show that our proposed heuristic algorithm uses a small number of controllers to manage a high amount of flows with good performance.

Internet of Things (IoT) envisions an intelligent infrastructure of networked smart devices offering task-specific monitoring and control services. The unique features of IoT include extreme heterogeneity, massive number of devices, and unpredictable dynamics partially due to human interaction. These call for foundational innovations in network design and management. Ideally, it should allow efficient adaptation to changing environments, and low-cost implementation scalable to a massive number of devices, subject to stringent latency constraints. To this end, the overarching goal of this paper is to outline a unified framework for online learning and management policies in IoT through joint advances in communication, networking, learning, and optimization. From the network architecture vantage point, the unified framework leverages a promising fog architecture that enables smart devices to have proximity access to cloud functionalities at the network edge, along the cloud-to-things continuum. From the algorithmic perspective, key innovations target online approaches adaptive to different degrees of nonstationarity in IoT dynamics, and their scalable model-free implementation under limited feedback that motivates blind or bandit approaches. The proposed framework aspires to offer a stepping stone that leads to systematic designs and analysis of task-specific learning and management schemes for IoT, along with a host of new research directions to build on.

Rapid urbanization has posed significant burden on urban transportation infrastructures. In today's cities, both private and public transits have clear limitations to fulfill passengers' needs for quality of experience (QoE): Public transits operate along fixed routes with long wait time and total transit time; Private transits, such as taxis, private shuttles and ride-hailing services, provide point-to-point transits with high trip fare. In this paper, we propose CityLines, a transformative urban transit system, employing hybrid hub-and-spoke transit model with shared shuttles. Analogous to Airlines services, the proposed CityLines system routes urban trips among spokes through a few hubs or direct paths, with travel time as short as private transits and fare as low as public transits. CityLines allows both point-to-point connection to improve the passenger QoE, and hub-and-spoke connection to reduce the system operation cost. To evaluate the performance of CityLines, we conduct extensive data-driven experiments using one-month real-world trip demand data (from taxis, buses and subway trains) collected from Shenzhen, China. The results demonstrate that CityLines reduces 12.5-44 percent average travel time, and aggregates 8.5-32.6 percent more trips with ride-sharing over other implementation baselines.

In this paper, we consider the problem of allocating cache resources among multiple content providers. The cache can be partitioned into slices and each partition can be dedicated to a particular content provider or shared among a number of them. It is assumed that each partition employs the least recently used policy for managing content. We propose utility-driven partitioning, where we associate with each content provide a utility that is a function of the hit rate observed by the content provider. We consider two scenarios: (1) content providers serve disjoint sets of files and (2) there is some overlap in the content served by multiple content providers. In the first case, we prove that cache partitioning outperforms cache sharing as cache size and a number of contents served by providers go to infinity. In the second case, it can be beneficial to have separate partitions for overlapped content. In the case of two providers, it is usually always beneficial to allocate a cache partition to serve all overlapped content and separate partitions to serve the non-overlapped contents of both providers. We establish conditions when this is true asymptotically but also present an example where it is not true asymptotically. We develop online algorithms that dynamically adjust partition sizes in order to maximize the overall utility and prove that they converge to optimal solutions, and through numerical evaluations we show they are effective.

Website fingerprinting attacks can reveal the receiver in anonymous networks and cause a potential threat to users' privacy. Previous studies focus more on identifying individual webpages. They also neglect the hyperlink transition information, because it induces extra “noise” to classify the original webpage. However, it is a common scenario that the users surf a website by clicking hyperlinks on the webpage. In this paper, we propose a website modeling method based on profile hidden Markov model (PHMM) which is widely used in bioinformatics for DNA sequencing analysis. Our technique explicitly accounts for possible hyperlink transitions made by users when fingerprinting a target website, and therefore can work in a more realistic environment than existing methods. Using SSH and Shadowsocks, we collect various data sets and conduct extensive evaluations. We also show that our approach could work both in webpage and website identification in a closed world setting. The experimental results demonstrate that our website fingerprinting is more accurate and robust than existing methods.

In SDN, the logically centralized control plane ("network OS") is often realized via multiple SDN controllers for scalability and reliability. ONOS is such an example, where it employs Raft -- a new consensus protocol developed recently -- for state replication and consistency among the distributed SDN controllers. The reliance of network OS on consensus protocols to maintain consistent network state introduces an intricate inter-dependency between the network OS and the network under its control, thereby creating new kinds of fault scenarios or instabilities. In this paper, we use Raft to illustrate the problems that this inter-dependency may introduce in the design of distributed SDN controllers and discuss possible solutions to circumvent these issues.

It is well-known that online services resort to various cookies to track users through users' online service identifiers (IDs) - in other words, when users access online services, various "fingerprints" are left behind in the cyberspace. As they roam around in the physical world while accessing online services via mobile devices, users also leave a series of "footprints" -- i.e., hints about their physical locations - in the physical world. This poses a potent new threat to user privacy: one can potentially correlate the "fingerprints" left by the users in the cyberspace with "footprints" left in the physical world to infer and reveal leakage of user physical world privacy, such as frequent user locations or mobility trajectories in the physical world - we refer to this problem as user physical world privacy leakage via user cyberspace privacy leakage. In this paper we address the following fundamental question: what kind - and how much - of user physical world privacy might be leaked if we could get hold of such diverse network datasets even without any physical location information. In order to conduct an in-depth investigation of these questions, we utilize the network data collected via a DPI system at the routers within one of the largest Internet operator in Shanghai, China over a duration of one month. We decompose the fundamental question into the three problems: i) linkage of various online user IDs belonging to the same person via mobility pattern mining; ii) physical location classification via aggregate user mobility patterns over time; and iii) tracking user physical mobility. By developing novel and effective methods for solving each of these problems, we demonstrate that the question of user physical world privacy leakage via user cyberspace privacy leakage is not hypothetical, but indeed poses a real potent threat to user privacy.

Rapid urbanization has posed significant burden on urban transportation infrastructures. In today's cities, both private and public transits have clear limitations to fulfill passengers' needs for quality of experience (QoE): Public transits operate along fixed routes with long wait time and total transit time; Private transits, such as taxis, private shuttles and ride-hailing services, provide point-to-point transits with high trip fare. In this paper, we propose CityLines, a transformative urban transit system, employing hybrid hub-and-spoke transit model with shared shuttles. Analogous to Airlines services, the proposed CityLines system routes urban trips among spokes through a few hubs or direct paths, with travel time as short as private transits and fare as low as public transits. CityLines allows both point-to-point connection to improve the passenger QoE, and hub-and-spoke connection to reduce the system operation cost. Our evaluation results show that CityLines framework can achieve both short travel time and high ride-sharing ratio.

In this paper, we advocate the notion of "BIG" cache as an innovative abstraction for effectively utilizing the distributed storage and processing capacities of all servers in a cache network. The "BIG" cache abstraction is proposed to partly address the problem of (cascade) thrashing in a hierarchical network of cache servers, where it has been known that cache resources at intermediate servers are poorly utilized, especially under classical cache replacement policies such as LRU. We lay out the advantages of "BIG" cache abstraction and make a strong case both from a theoretical standpoint as well as through simulation analysis. We also develop the dCLIMB cache algorithm to minimize the overheads of moving objects across distributed cache boundaries and present a simple yet effective heuristic for addressing the cache allotment problem in the design of "BIG" cache abstraction.

Software Defined Networking (SDN) can benefit a Network Function Virtualization solution by chaining a set of network functions (NF) to create a network service. Currently, control on NFs is isolated from the SDN, which creates routing inflexibility, flow imbalance and choke points in the network as the controller remains oblivious to the number, capacity and placement of NFs. Moreover, a NF may modify packets in the middle, which makes flow identification at a SDN switch challenging. In this paper, we postulate native NFs within the SDN data plane, where the same logical controller controls both network services and routing. This is enabled by extending SDN to support stateful flow handling based on higher layers in the packet beyond layers 2-4. As a result, NF instances can be chained on demand, directly on the data plane. We present an implementation of this architecture based on Open vSwitch, and show that it enables popular NFs effectively using detailed evaluation and comparison with other alternative solutions.

For the purpose of learning on graphs, we hunt for a graph feature representation that exhibit certain uniqueness, stability and sparsity properties while also being amenable to fast computation. This leads to the discovery of family of graph spectral distances (denoted as FGSD) and their based graph feature representations, which we prove to possess most of these desired properties. To both evaluate the quality of graph features produced by FGSD and demonstrate their utility, we apply them to the graph classification problem. Through extensive experiments, we show that a simple SVM based classification algorithm, driven with our powerful FGSD based graph features, significantly outperforms all the more sophisticated state-of-art algorithms on the unlabeled node datasets in terms of both accuracy and speed; it also yields very competitive results on the labeled datasets - despite the fact it does not utilize any node label information.

In this paper we present a simple and reliable authentication method for mobile devices equipped with multi-touch screens such as smart phones, tablets and laptops. Users are authenticated by performing specially designed multi-touch gestures with one swipe on the touchscreen. During this process, both hand geometry and behavioral characteristics are recorded in the multi-touch traces and used for authentication. By combining both geometry information and behavioral characteristics, we overcome the problem of behavioral variability plaguing many behavior based authentication techniques - which often leads to less accurate authentication or poor user experience - while also ensuring the discernibility of different users with possibly similar handshapes. We evaluate the design of the proposed authentication method thoroughly using a large multi-touch dataset collected from 161 subjects with an elaborately designed procedure to capture behavior variability. The results demonstrate that the fusion of behavioral information with hand geometry features produces effective resistance to behavioral variability over time while at the same time retains discernibility. Our approach achieves EER of 5.84% with only 5 training samples and the performance is further improved to EER of 1.88% with enough training. Security analyses are also conducted to demonstrate that the proposed method is resilient against common smartphone authentication threats such as smudge attack, shoulder surfing attack and statistical attack. Finally, user acceptance of the method is illustrated via a usability study.

We conduct a detailed analysis of cellular communication patterns using (voice/text based) call detail records (CDR) dataset from a nationwide cellular network. We analyze a 5-month large dataset containing over hundreds of millions of CDRs with a user population of over 5 million to dissect meaningful communication patterns, with the goal to understand their impact on - and better manage - cellular network resources. What makes this dataset interesting is that we have both location and timestamp information of the caller and the callee. This allows us to associate communication patterns of users with geographic locations. The enormous size and diversity inherent in the (big)data set, however, makes extracting communication patterns a challenging task. We illustrate this diversity by analyzing tower-level activities and communication patterns between towers and find certain patterns emerging. However, due to the complex structure of the data, extracting them becomes non-trivial. By providing structures to the data in the form of matrices, we adopt machine learning techniques to extract "latent" patterns from the data, while accounting for the inherent non-linearity and skewed data distributions. Our main results reveal the existence of interesting regional communication patterns of varying localities and sizes, out of which one pattern scatters across the entire nation.

To ensure security, cloud service providers employ security groups as a key tool for cloud tenants to protect their virtual machines (VMs) from attacks. However, security groups can be complex and often hard to configure, which may result in security vulnerabilities that impact the entire cloud platform. The goal of this paper is to investigate and understand how cloud tenants configure security groups and to assist them in designing better security groups. We first conduct a measurement-based analysis of security group configuration and usage by tenants in an IaaS cloud. We then propose and develop a tool called Socrates, which enables tenants to visualize and hence understand the static and dynamic access relations among VMs. Socrates also helps diagnose potential misconfigurations and provides suggestions to refine security group configurations based on observed traffic traversing tenants' VMs. Applying Socrates to all tenants hosted on the IaaS cloud, we analyze the common usage (“good” as well as “bad” practices) of cloud security groups and report the key lessons learned in our study. To the best of our knowledge, our work is the first to analyze cloud security group usage based on real-world datasets, and to develop a system to help cloud tenants understand, diagnose and better refine their security group configurations.

Multipath TCP (MPTCP) is a promising technique for boosting application throughput while using well-known and versatile network socket interfaces. Recently, many interesting applications of MPTCP in various environments such as wireless networks and data centers have been proposed, but little work has been done to investigate the impact of this protocol on conventional network devices. For example, MPTCP throughput advantage can be better achieved if all MPTCP subflows are routed on disjoint paths, but this is currently not feasible since routers are not designed to recognize the membership of MPTCP subflows. In this paper, we take a first step to address this issue by proposing SAMPO, an online algorithm to detect and associate MPTCP subflows in network. The main challenge is that sampling techniques and network dynamics may cause a network device to only obtain partial flow records. SAMPO takes advantage of both protocol information and statistical characteristics of MPTCP data sequence number to overcome the challenge in network. Through analysis and experimentation, we show that SAMPO is able to detect and associate MPTCP subflows with high accuracy even when a small portion of the entire flow records are available.

The increasing prevalence of sensors and mobile devices has led to an explosive increase of the scale of spatio-temporal data in the form of trajectories. A trajectory aggregate query, as a fundamental functionality for measuring trajectory data, aims to retrieve the statistics of trajectories passing a user-specified spatio-temporal region. A large-scale spatio-temporal database with big disk-resident data takes very long time to produce exact answers to such queries. Hence, approximate query processing with a guaranteed error bound is a promising solution in many scenarios with stringent response-time requirements. In this paper, we study the problem of approximate query processing for trajectory aggregate queries. We show that it boils down to the distinct value estimation problem, which has been proven to be very hard with powerful negative results given that no index is built. By utilizing the well-established spatio-temporal index and introducing an inverted index to trajectory data, we are able to design random index sampling (RIS) algorithm to estimate the answers with a guaranteed error bound. To further improve system scalability, we extend RIS algorithm to concurrent random index sampling (CRIS) algorithm to process a number of trajectory aggregate queries arriving concurrently with overlapping spatio-temporal query regions. To demonstrate the efficacy and efficiency of our sampling and estimation methods, we applied them in a real large-scale user trajectory database collected from a cellular service provider in China. Our extensive evaluation results indicate that both RIS and CRIS outperform exhaustive search for single and concurrent trajectory aggregate queries by two orders of magnitude in terms of the query processing time, while preserving a relative error ratio lower than 10\%, with only 1% search cost of the exhaustive search method.

Transoceanic video telephony (TVT) over the Internet is challenging due to 1) longer round-trip delay, 2) larger number of relay hops, and 3) higher packet loss rate. Real-world measurements of Skype, Face time, and QQ confirm that their TVT service quality is mostly unsatisfactory. Recently, when using We Chat to make transoceanic video calls, we are fortunate to find that it achieves stably smooth TVT. To explore how this is possible, we conduct in-depth measurements of We Chat data flow. In particular, we discover that the service provider of We Chat deploys a novel, specially designed "twin clouds" based architecture to deliver transoceanic (UDP) packets. Thus, data delivery between two callers is no longer point-to-point (used by Skype, Face time, and QQ) over the best-effort Internet. Instead, transoceanic video packets are delivered through the privileged backbone formed by twin clouds, which greatly reduces the round-trip delay, number of relay hops, and packet loss rate. Besides, whenever a packet is found lost, multiple duplicate packets are instantly sent to aggressively make up for the loss. On the other hand, we notice two-fold shortcomings of twin clouds. First, due to the sophisticated resource provisioning inside the twin clouds, the video start up time is considerably extended. Second, due to the high cost of deploying twin clouds, the capacity of the privileged backbone is limited and sometimes in shortage, and thus We Chat has to deliver data via a detour path with degraded performance. Ultimately, we believe that the twin clouds based data delivery solution will arouse a new direction of Internet video telephony research while still deserves optimization efforts.

Directed links -- representing asymmetric social ties or interactions (e.g., "follower-followee") -- arise naturally in many social networks and other complex networks, giving rise to directed graphs (or digraphs) as basic topological models for these networks. Reciprocity, defined for a digraph as the percentage of edges with a reciprocal edge, is a key metric that has been used in the literature to compare different directed networks and provide "hints" about their structural properties: for example, are reciprocal edges generated randomly by chance or are there other processes driving their generation? In this paper we study the problem of maximizing achievable reciprocity for an ensemble of digraphs with the same prescribed in- and out-degree sequences. We show that the maximum reciprocity hinges crucially on the in- and out-degree sequences, which may be intuitively interpreted as constraints on some "social capacities" of nodes and impose fundamental limits on achievable reciprocity. We show that it is NP-complete to decide the achievability of a simple upper bound on maximum reciprocity, and provide conditions for achieving it. We demonstrate that many real networks exhibit reciprocities surprisingly close to the upper bound, which implies that users in these social networks are in a sense more "social" than suggested by the empirical reciprocity alone in that they are more willing to reciprocate, subject to their "social capacity" constraints. We find some surprising linear relationships between empirical reciprocity and the bound. We also show that a particular type of small network motifs that we call 3-paths are the major source of loss in reciprocity for real networks.

In content-centric networks, it is challenging how to optimally provision in-network storage to cache contents, to balance the tradeoffs between the network performance and the provisioning cost. To address this problem, we first propose a holistic model for intradomain networks to characterize the network performance of routing contents to clients and the network cost incurred by globally coordinating the in-network storage capability. We then derive the optimal strategy for provisioning the storage capability that optimizes the overall network performance and cost, and analyze the performance gains via numerical evaluations on real network topologies. Our results reveal interesting phenomena; for instance, different ranges of the Zipf exponent can lead to opposite optimal strategies, and the tradeoffs between the network performance and the provisioning cost have great impacts on the stability of the optimal strategy. We also demonstrate that the optimal strategy can achieve significant gain on both the load reduction at origin servers and the improvement on the routing performance. Moreover, given an optimal coordination level ℓ*, we design a routing-aware content placement (RACP) algorithm that runs on a centralized server. The algorithm computes and assigns contents to each CCN router to store, which can minimize the overall routing cost, e.g., transmission delay or hop counts, to deliver contents to clients. By conducting extensive simulations using a large-scale trace dataset collected from a commercial 3G network in China, our results demonstrate that our caching scheme can achieve 4% to 22% latency reduction on average over the state-of-the-art caching mechanisms.

Netflix and Hulu are leading Over-the-Top (OTT) content service providers in the US and Canada. Netflix alone accounts for 29.7% of the peak downstream traffic in the US in 2011. Understanding the system architectures and performance of Netflix and Hulu can shed light on the design of such large-scale video streaming platforms, and help improving the design of future systems. In this paper, we perform extensive measurement study to uncover their architectures and service strategies. Netflix and Hulu bear many similarities. Both Netflix and Hulu video streaming platforms rely heavily on the third-party infrastructures, with Netflix migrating that majority of its functions to the Amazon cloud, while Hulu hosts its services out of Akamai. Both service providers employ the same set of three content distribution networks (CDNs) in delivering the video contents. Using active measurement study, we dissect several key aspects of OTT streaming platforms of Netflix and Hulu, e.g., employed streaming protocols, CDN selection strategy, user experience reporting, etc. We discover that both platforms assign the CDN to a video request without considering the network conditions and optimizing the user-perceived video quality. We further conduct the performance measurement studies of the three CDNs employed by Netflix and Hulu. We show that the available bandwidths on all three CDNs vary significantly over the time and over the geographic locations. We propose a measurement-based adaptive CDN selection strategy and a multiple-CDN-based video delivery strategy that can significantly increase users' average available bandwidth.

Malware families classification has been studied extensively in the literature. Machine learning based identification techniques rely on building a classification model for the malware traffic, and then the model is used for labeling unseen observations. In practice, malware traffic (malware signal) is mixed with other legitimate traffic (background signal). Consequently, the classifier's effectiveness may be hindered, since the observed traffic is mixed. We propose to apply signal decomposition in order to decompose the observed traffic into two components, malware traffic and background traffic, and then classification techniques are applied effectively on the malware traffic after removing the background attributes. Our preliminary results show the effectiveness of the proposed approach.

In this paper, we describe our experience in implementing a non-IP routing protocol - Virtual Id Routing (VIRO) - using the OVS-SDN platform in GENI. As a novel, "plug-&-play", routing paradigm for future dynamic networks, VIRO decouples routing/forwarding from addressing by introducing a topology-aware, structured virtual id layer to encode the locations of switches and devices in the physical topology for scalable and resilient routing. Despite its general "match-action" forwarding function, the existing OVS-SDN platform is closely tied to the conventional Ethernet/IP/TCP header formats, and cannot be directly used to implement the new VIRO routing/forwarding paradigm. As a result, we repurpose the Ethernet MAC address to represent VIRO virtual id, modify and extend the OVS (both within the user space and the kernel space) to implement the VIRO forwarding functions. We also utilize a set of local POX controllers (one per VIRO switch) to emulate the VIRO distributed control plane and one global POX controller to realize the VIRO (centralized) management plane. We evaluate our prototype implementation through the Mininet emulation and GENI deployment test and discuss some lessons learned using the test-bed.

To ensure security, cloud service providers employ security groups as a key tool for cloud tenants to protect their virtual machines from unwanted traffic. However, security groups can be complex and often hard to configure, which may result in security vulnerabilities that impact the entire cloud platform. To assist tenants in designing better security groups, in this paper, we propose and develop a system called Secgras. Secgras enables tenants to visualize and hence to understand the static and dynamic access relations among virtual machine (VM) instances. Secgras also helps diagnose potential misconfigurations and provides suggestions to refine security group configurations based on real traffic traversing tenants VMs.

Cloud storage services such as Dropbox, Google Drive, and Microsoft OneDrive provide users with a convenient and reliable way to store and share data from anywhere, on any device, and at any time. The cornerstone of these services is the data synchronization (sync) operation which automatically maps the changes in users' local filesystems to the cloud via a series of network communications in a timely manner. If not designed properly, however, the tremendous amount of data sync traffic can potentially cause (financial) pains to both service providers and users.

The web has become a platform that attackers exploit to infect vulnerable hosts, or deceive victims into buying rogue software. To accomplish this, attackers either inject malicious scripts into popular web sites or manipulate content delivered by servers to exploit vulnerabilities in users' browsers. To hide malware distribution servers, attackers employ HTTP redirections, which automatically redirect users' requests through a series of intermediate web sites, before landing on the final distribution site. In this paper, we develop a methodology to identify malicious chains of HTTP redirections. We build per-user chains from passively collected traffic and extract novel statistical features from them, which capture inherent characteristics from malicious redirection cases. Then, we apply a supervised decision tree classifier to identify malicious chains. Using a large ISP dataset, with more than 15K clients, we demonstrate that our methodology is very effective in accurately identifying malicious chains, with recall and precision values over 90% and up to 98%.

As a crucial operation, routing plays an important role in various communication networks. In the context of data and sensor networks, routing strategies such as shortest-path, multi-path and potential-based (“all-path”) routing have been developed. Existing results in the literature show that the shortest path and all-path routing can be obtained from$L_{1}$and$L_{2}$flow optimization, respectively. Based on this connection between routing and flow optimization in a network, in this paper we develop a unifying theoretical framework by considering flow optimization with mixed (weighted)$L_{1}/L_{2}$-norms. We obtain a surprising result: as we vary the trade-off parameter$\theta$, the routing graphs induced by the optimal flow solutions span from shortest-path to multi-path to all-path routing—this entire sequence of routing graphs is referred to as the routing continuum. We also develop an efficient iterative algorithm for computing the entire routing continuum. Several generalizations are also considered, with applications to traffic engineering, wireless sensor networks, and network robustness analysis.

In-network content storage has become an inherent capability of routers in the content-centric networking architecture. This raises new challenges in utilizing and provisioning the in-network caching capability, namely, how to optimally provision individual routers' storage to cache contents, so as to balance the trade-offs between the network performance and the provisioning cost. To address this problem, we first propose a holistic model to characterize the network performance of routing contents to clients and the network cost incurred by globally coordinating the in-network storage capability. We then derive the optimal strategy for provisioning the storage capability that optimizes the overall network performance and cost, and analyze the performance gains via numerical evaluations on real network topologies. Our results reveal interesting phenomena; for instance, different ranges of the Zipf exponent can lead to opposite optimal strategies, and the trade-offs between the network performance and the provisioning cost have great impacts on the stability of the optimal strategy. We also demonstrate that the optimal strategy can achieve significant gain on both the load reduction at origin servers and the improvement on the routing performance.

We were able to put together an excellent technical program for ICNP 2013, thanks to the joint efforts by our authors, TPC members, and technical area leads. We received 251 submissions to the main conference this year, the highest number in ICNP's 21-year history. Each paper received at least three reviews, and the 66 technical program committee members produced 765 paper reviews. The 11 area chairs ensured review quality and consistency between reviewers. The final papers for the main conference were selected during a TPC meeting in July. To accommodate for the larger number of submissions, we decided to shorten paper presentations slightly. Overall, 46 papers were accepted for presentation at the conference, which corresponds to an acceptance rate of 18.3%.

In this paper, we provide a detailed analysis on the venue popularity in Foursquare, a leading location-based social network. By collecting 2.4 million venues from 14 geographic regions all over the world, we study the common characteristics of popular venues, and make the following observations. First, venues with more complete profile information are more likely to be popular. Second, venues in the Food category attract the most (43%) public tips (comments) by users, and the Travel & Transport category is the most popular category with the highest per venue check-ins, i.e., each venue in this category attracts on average 376 check-ins. Moreover, the stickiness of users checking in venues in the residence, office, and school categories is higher than in other categories. Last but not least, in general, old venues created at the early stage of Foursquare are more popular than new venues. Our results help to understand the factors that cause venues to become popular, and have applications in venue recommendations and advertisement in location based social networks.

Using a large Web search service as a case study, we highlight the challenges that modern Web services face in understanding and diagnosing the response time experienced by users. We show that search response time (SRT) varies widely over time and also exhibits counter-intuitive behavior. It is actually higher during off-peak hours, when the query load is lower, than during peak hours. To resolve this paradox and explain SRT variations in general, we develop an analysis framework that separates systemic variations due to periodic changes in service usage and anomalous variations due to unanticipated events such as failures and denial-of-service attacks. We find that systemic SRT variations are primarily caused by systemic changes in aggregate network characteristics, nature of user queries, and browser types. For instance, one reason for higher SRTs during off-peak hours is that during those hours a greater fraction of queries come from slower, mainly-residential networks. We also develop a technique that, by factoring out the impact of such variations, robustly detects and diagnoses performance anomalies in SRT. Deployment experience shows that our technique detects three times more true (operator-verified) anomalies than existing techniques.

With the proliferation of online social networking (OSN) and mobile devices, preserving user privacy has become a great challenge. While prior studies have directly focused on OSN services, we call attention to the privacy leakage in mobile network data. This concern is motivated by two factors. First, the prevalence of OSN usage leaves identifiable digital footprints that can be traced back to users in the real-world. Second, the association between users and their mobile devices makes it easier to associate traffic to its owners. These pose a serious threat to user privacy as they enable an adversary to attribute significant portions of data traffic including the ones with NO identity leaks to network users' true identities. To demonstrate its feasibility, we develop the Tessellation methodology. By applying Tessellation on traffic from a cellular service provider (CSP), we show that up to 50% of the traffic can be attributed to the names of users. In addition to revealing the user identity, the reconstructed profile, dubbed as "mosaic," associates personal information such as political views, browsing habits, and favorite apps to the users. We conclude by discussing approaches for preventing and mitigating the alarming leakage of sensitive user information.

In this paper, we conduct a comprehensive study of SMS spam in a large cellular network in the US. Using one year of user reported spam messages to the network carrier, we devise text clustering techniques to group associated spam messages in order to identify SMS spam campaigns and spam activities. Our analysis shows that spam campaigns can last for months and have a wide impact on the cellular network. Combining with SMS network records collected during the same time, we find that spam numbers within the same activity often exhibit strong similarity in terms of their sending patterns, tenure and geolocations. Our analysis sheds light on the intentions and strategies of SMS spammers and provides unique insights in developing better method for detecting SMS spam.

Influence diffusion and influence maximization in large-scale online social networks (OSNs) have been extensively studied because of their impacts on enabling effective online viral marketing. Existing studies focus on social networks with only friendship relations, whereas the foe or enemy relations that commonly exist in many OSNs, e.g., Epinions and Slashdot, are completely ignored. In this paper, we make the first attempt to investigate the influence diffusion and influence maximization in OSNs with both friend and foe relations, which are modeled using positive and negative edges on signed networks. In particular, we extend the classic voter model to signed networks and analyze the dynamics of influence diffusion of two opposite opinions. We first provide systematic characterization of both short-term and long-term dynamics of influence diffusion in this model, and illustrate that the steady state behaviors of the dynamics depend on three types of graph structures, which we refer to as balanced graphs, anti-balanced graphs, and strictly unbalanced graphs. We then apply our results to solve the influence maximization problem and develop efficient algorithms to select initial seeds of one opinion that maximize either its short-term influence coverage or long-term steady state influence coverage. Extensive simulation results on both synthetic and real-world networks, such as Epinions and Slashdot, confirm our theoretical analysis on influence diffusion dynamics, and demonstrate that our influence maximization algorithms perform consistently better than other heuristic algorithms.

Various applications in wireless networks, such as routing and query processing, can be formulated as random walks on graphs. Many results have been obtained for such applications by utilizing the theory of random walks (or spectral graph theory), which is mostly developed for undirected graphs. However, this formalism neglects the fact that the underlying (wireless) networks in practice contain asymmetric links, which are best characterized by directed graphs (digraphs). Therefore, random walk on digraphs is a more appropriate model to consider for such networks. In this paper, by generalizing the random walk theory (or spectral graph theory) that has been primarily developed for undirected graphs to digraphs, we show how various transmission costs in wireless networks can be formulated in terms of hitting times and cover times of random walks on digraphs. Using these results, we develop a unified theoretical framework for estimating various transmission costs in wireless networks. Our framework can be applied to random walk query processing strategy and the three routing paradigms—best path routing, opportunistic routing, and stateless routing—to which nearly all existing routing protocols belong. Extensive simulations demonstrate that the proposed digraph-based analytical model can achieve more accurate transmission cost estimation over existing methods.

Although existing flooding protocols can provide efficient and reliable communication in wireless sensor networks on some level, further performance improvement has been hampered by the assumption of link independence, which requires costly acknowledgments (ACKs) from every receiver. In this paper, we present collective flooding (CF), which exploits the link correlation to achieve flooding reliability using the concept of collective ACKs. CF requires only 1-hop information at each node, making the design highly distributed and scalable with low complexity. We evaluate CF extensively in real-world settings, using three different types of testbeds: a single-hop network with 20 MICAz nodes, a multihop network with 37 nodes, and a linear outdoor network with 48 nodes along a 326-m-long bridge. System evaluation and extensive simulation show that CF achieves the same reliability as state-of-the-art solutions while reducing the total number of packet transmission and the dissemination delay by 30%-50% and 35%-50%, respectively.

Most IP-geolocation mapping schemes [14], [16], [17], [18] take delay-measurement approach, based on the assumption of a strong correlation between networking delay and geographical distance between the targeted client and the landmarks. In this paper, however, we investigate a large region of moderately connected Internet and find the delay-distance correlation is weak. But we discover a more probable rule - with high probability the shortest delay comes from the closest distance. Based on this closest-shortest rule, we develop a simple and novel IP-geolocation mapping scheme for moderately connected Internet regions, called GeoGet. In GeoGet, we take a large number of webservers as passive landmarks and map a targeted client to the geolocation of the landmark that has the shortest delay. We further use JavaScript at targeted clients to generate HTTP/Get probing for delay measurement. To control the measurement cost, we adopt a multistep probing method to refine the geolocation of a targeted client, finally to city level. The evaluation results show that when probing about 100 landmarks, GeoGet correctly maps 35.4 percent clients to city level, which outperforms current schemes such as GeoLim [16] and GeoPing [14] by 270 and 239 percent, respectively, and the median error distance in GeoGet is around 120 km, outperforming GeoLim and GeoPing by 37 and 70 percent, respectively.

Content distribution on today's Internet operates primarily in two modes: server-based and peer-to-peer (P2P). To leverage the advantages of both modes while circumventing their key limitations, a third mode: peer-to-server/peer (P2SP) has emerged in recent years. Although P2SP can provide efficient hybrid server-P2P content distribution, P2SP generally works in a closed manner by only utilizing its private owned servers to accelerate its private organized peer swarms. Consequently, P2SP still has its limitations in both content abundance and server bandwidth. To this end, the fourth mode (or says a generalized mode of P2SP) has appeared as "open-P2SP" that integrates various third-party servers, contents, and data transfer protocols all over the Internet into a large, open, and federated P2SP platform. In this paper, based on a large-scale commercial open-P2SP system named "QQXuanfeng" , we investigate the key challenging problems, practical designs and real-world performances of open-P2SP. Such "white-box" study of open-P2SP provides solid experiences and helpful heuristics to the designers of similar systems.

Netflix is the leading provider of on-demand Internet video streaming in the US and Canada, accounting for 29.7% of the peak downstream traffic in US. Understanding the Netflix architecture and its performance can shed light on how to best optimize its design as well as on the design of similar on-demand streaming services. In this paper, we perform a measurement study of Netflix to uncover its architecture and service strategy. We find that Netflix employs a blend of data centers and Content Delivery Networks (CDNs) for content distribution. We also perform active measurements of the three CDNs employed by Netflix to quantify the video delivery bandwidth available to users across the US. Finally, as improvements to Netflix's current CDN assignment strategy, we propose a measurement-based adaptive CDN selection strategy and a multiple-CDN-based video delivery strategy, and demonstrate their potentials in significantly increasing user's average bandwidth.

We deduce key design features behind the YouTube video delivery system by building a distributed active measurement infrastructure, and collecting and analyzing a large volume of video playback logs, DNS mappings and latency data. We find that the design of YouTube video delivery system consists of three major components: a “flat” video id space, multiple DNS namespaces reflecting a multi-layered logical organization of video servers, and a 3-tier physical cache hierarchy. We also uncover that YouTube employs a set of sophisticated mechanisms to handle video delivery dynamics such as cache misses and load sharing among its distributed cache locations and data centers.

Hybrid cloud-P2P content distribution (“CloudP2P”) provides a promising alternative to the conventional cloud-based or peer-to-peer (P2P)-based large-scale content distribution. It addresses the potential limitations of these two conventional approaches while inheriting their advantages. A key strength of CloudP2P lies in the so-called bandwidth multiplier effect: by appropriately allocating a small portion of cloud (server) bandwidth Sito a peer swarm i (consisting of users interested in the same content) to seed the content, the users in the peer swarm - with an aggregate download bandwidth Di- can then distribute the content among themselves; we refer to the ratio Di/Sias the bandwidth multiplier (for peer swarm i). A major problem in the design of a CloudP2P content distribution system is therefore how to allocate cloud (server) bandwidth to peer swarms so as to maximize the overall bandwidth multiplier effect of the system. In this paper, using real-world measurements, we identify the key factors that affect the bandwidth multipliers of peer swarms and thus construct a fine-grained performance model for addressing the optimal bandwidth allocation problem (OBAP). Then we develop a fast-convergent iterative algorithm to solve OBAP. Both trace-driven simulations and prototype implementation confirm the efficacy of our solution.

With widespread adoption and growing sophistication of mobile devices, fraudsters have turned their attention from landlines and wired networks to cellular networks. While security threats to wireless data channels and applications have attracted the most attention, voice-related fraud activities also represent a serious threat to mobile users. In particular, we have seen increasing numbers of incidents where fraudsters deploy malicious apps, e.g., disguised as gaming apps to entice users to download; when invoked, these apps automatically - and without users' knowledge - dial certain (international) phone numbers which charge exorbitantly high fees. Fraudsters also frequently utilize social engineering (e.g., SMS or email spam, Facebook postings) to trick users into dialing these exorbitant fee-charging numbers.

Despite the increasing popularity, Internet video streaming to mobile devices is still challenging. In particular, there has been a format and resolution "gap" between Internet videos and mobile devices, so mobile users have high demand on video transcoding to facilitate their specific devices. However, as a computation-intensive work, video transcoding is greatly challenged by the limited battery capacity of mobile devices. In this paper we propose and implement "Cloud Transcoder", which utilizes an intermediate cloud platform to bridge the "gap" via its special and practical designs. Specifically, Cloud Transcoder only requires the user to upload a video request rather than the video content. After getting the video request, Cloud Transcoder downloads the original video from the Internet, transcodes it on the user's demand, and transfers the transcoded video back to the user with a high data rate via the intra-cloud data transfer acceleration. Therefore, the mobile device only consumes energy in the last step - fast retrieving the transcoded video from the cloud. Running logs of our real-deployed system confirm the efficacy of Cloud Transcoder.

The ability to accurately and scalably classify network traffic is of critical importance to a wide range of management tasks of large networks, such as tier-1 ISP networks and global enterprise networks. Guided by the practical constraints and requirements of traffic classification in large networks, in this article, we explore the design of an accurate and scalable machine learning based flow-level traffic classification system, which is trained on a dataset of flow-level data that has been annotated with application protocol labels by a packet-level classifier. Our system employs a lightweight modular architecture , which combines a series of simple linear binary classifiers, each of which can be efficiently implemented and trained on vast amounts of flow data in parallel, and embraces three key innovative mechanisms, weighted threshold sampling, logistic calibration , and intelligent data partitioning , to achieve scalability while attaining high accuracy. Evaluations using real traffic data from multiple locations in a large ISP show that our system accurately reproduces the labels of the packet level classifier when runs on (unlabeled) flow records, while meeting the scalability and stability requirements of large ISP networks. Using training and test datasets that are two months apart and collected from two different locations, the flow error rates are only 3% for TCP flows and 0.4% for UDP flows. We further show that such error rates can be reduced by combining the information of spatial distributions of flows, or collective traffic statistics , during classification. We propose a novel two-step model, which seamlessly integrates these collective traffic statistics into the existing traffic classification system. Experimental results display performance improvement on all traffic classes and an overall error rate reduction by 15%. In addition to a high accuracy, at runtime, our implementation easily scales to classify traffic on 10Gbps links.

Energy is the most precious resource in sensor networks. The ability to move energy around makes it feasible to build distributed energy storage systems that can robustly extend the lifetime of networked sensor systems. eShare supports the concept of energy sharing among multiple embedded sensor devices by providing designs for energy routers (i.e., energy storage and routing devices) and related energy access and network protocols. In a nutshell, energy routers exchange energy sharing control information using their data network while sharing energy freely among connected embedded sensor devices using their energy network. To improve sharing efficiency subject to energy leakage, we develop an effective energy charging and discharging mechanism using an array of ultra-capacitors as the main component of an energy router. We extensively evaluate our system under seven real-world settings. Results indicate our charging and discharging control can effectively minimize the energy leaked away. Moreover, the energy sharing protocol can quantitatively share 113J energy with 96.82% accuracy in less than 2 seconds.

YouTube is one of the most popular video sharing websites in the world. In order to serve its globally distributed users, it requires a massive-scale video delivery system. A major part of the whole system is to decide exactly what server machine is going to serve a client request at any given time. In this paper, we analyze DNS resolutions and video playback traces collected by playing half a million YouTube videos from geographically distributed PlanetLab nodes to uncover load- balancing and server selection strategies used by YouTube. Our results indicate that YouTube is aggressively deploying cache servers of widely varying sizes at many different locations around the world with several of them located inside other ISPs to reduce cost and improve the end-user performance. We also find that YouTube tries to use local "per-cache" load-sharing before resorting to redirecting a user to bigger/central cache locations.

Routing is a critical operation in networks. In the context of data and sensor networks, routing strategies such as shortest-path, multi-path and potential-based ("all-path") routing have been developed. Based on the connection between routing and flow optimization in a network, in this paper we develop a unifying theoretical framework by considering flow optimization with mixed (weighted) L1/L2-norms. We obtain a surprising result: as we vary the trade-off parameter, the routing graphs induced by the optimal flow solutions span from shortest-path to multi-path to all-path routing - this entire sequence of routing graphs is referred to as the routing continuum. Our theory subsumes the earlier results showing the shortest path and all-path routing can be obtained from L1 and L2 flow optimization, respectively. We also develop an efficient iterative algorithm for computing the entire routing continuum. Several generalizations are also considered, with applications to traffic engineering and wireless sensor networks.

This paper investigates the roles of front-end (proxy) servers in improving user-perceived performance of dynamic content distribution. Using Bing and Google search services as two case studies, we perform extensive network measurement and analysis to understand several key factors that affect the overall user-perceived performance. In particular, we develop a simple model-based inference framework to indirectly measure and quantify the (directly unobservable) "frontend-to-backend fetching time" comprised of the query processing time at back-end data centers and the delivery time between the back-end data centers and front-end servers. We show that this fetching time plays a critical role in the end-to-end performance of dynamic content delivery.

Leveraging the characteristics of YouTube video id space and exploiting a unique property of YouTube search API, in this paper we develop a random prefix sampling method to estimate the total number of videos hosted by YouTube. Through theoretical modeling and analysis, we demonstrate that the estimator based on this method is unbiased, and provide bounds on its variance and confidence interval. These bounds enable us to judiciously select sample sizes to control estimation errors. We evaluate our sampling method and validate the sampling results using two distinct collections of YouTube video id's (namely, treating each collection as if it were the "true" collection of YouTube videos). We then apply our sampling method to the live YouTube system, and estimate that there are a total of roughly 500 millions YouTube videos by May, 2011. Finally, using an unbiased collection of YouTube videos sampled by our method, we show that YouTube video view count statistics collected by prior methods (e.g., through crawling of related video links) are highly skewed, significantly under-estimating the number of videos with very small view counts (<1000); we also shed lights on the bounds for the total storage YouTube must have and the network capacity needed to delivery YouTube videos.

Effectively managing multiple data centers and their traffic dynamics pose many challenges to their operators, as little is known about the characteristics of inter-data center (D2D) traffic. In this paper we present a first study of D2D traffic characteristics using the anonymized NetFlow datasets collected at the border routers of five major Yahoo! data centers. Our contributions are mainly two-fold: i) we develop novel heuristics to infer the Yahoo! IP addresses and localize their locations from the anonymized NetFlow datasets, and ii) we study and analyze both D2D and client traffic characteristics and the correlations between these two types of traffic. Our study reveals that Yahoo! uses a hierarchical way of deploying data centers, with several satellite data centers distributed in other countries and backbone data centers distributed in US locations. For Yahoo! US data centers, we separate the client-triggered D2D traffic and background D2D traffic from the aggregate D2D traffic using port based correlation, and study their respective characteristics. Our findings shed light on the interplay of multiple data centers and their traffic dynamics within a large content provider, and provide insights to data center designers and operators as well as researchers.

In this paper we propose VIRO - a novel, virtual identifier (Id) routing paradigm for future networks. The objective is three-fold. First, VIRO directly addresses the challenges faced by the traditional layer-2 technologies such as Ethernet, while retaining its simplicity feature. Second, it provides a uniform convergence layer that integrates and unifies routing and forwarding performed by the traditional layer-2 and layer-3, as prescribed by the traditional local-area/wide-area network dichotomy. Third and perhaps more importantly, VIRO decouples routing from addressing, and thus is namespace-independent. The key idea in our design is to introduce a topology-aware, structured virtual id (vid) space onto which both physical identifiers as well as higher layer addresses/names are mapped. VIRO completely eliminates network-wide flooding in both the data and control planes, and thus is highly scalable and robust. Furthermore, VIRO effectively localizes failures, and possesses built-in mechanisms for fast rerouting and load-balancing.

Effective management of large-scale cellular data networks is critical to meet customer demands and expectations. Customer calls for technical support provide direct indication as to the problems customers encounter. In this paper, we study the customer tickets - free-text recordings and classifications by customer support agents - collected at a large cellular network provider, with two inter-related goals: i) to characterize and understand the major factors which lead to customers to call and seek support; and ii) to utilize such customer tickets to help identify potential network problems. For this purpose, we develop a novel statistical approach to model customer call rates which account for customer-side factors (e.g., user tenure and handset types) and geo-locations. We show that most calls are due to customer-side factors and can be well captured by the model. Furthermore, we also demonstrate that location-specific deviations from the model provide a good indicator of potential network-side issues.

Despite the rapid growth in cellular data traffic, we know very little about the (operational) cellular data service network (CDSN) infrastructure. A key step in the process of developing any such understanding is to first understand the locations and distribution of the basestations in the CDSN infrastructure that serve as physical access points for end users for communicating with the underlying network. Such knowledge not only can provide critical insight into the the CDSN infrastructure, but can also guide the development of innovative (e.g. location-aware) services and applications. In this paper we propose a novel approach for mapping the CDSN basestation infrastructure via (explicit) user geo-intent. The intuition behind the proposed approach is to exploit specific geo-locations (i.e. geo-intent) contained in user queries to location-based services, and correlate them with basestation id's to geo-map the CDSN infrastructure. To investigate the validity of our approach, we employ data (RADIUS/RADA data sessions and application sessions) collected at the core IP network inside a CDSN. We develop heuristics for identifying user geo-intent and for geo-mapping the CDSN infrastructure - in particular, the basestations - and evaluate their efficacy using a subset of basestations with ground-truth GPS locations.

In this paper we "reverse-engineer" the YouTube video delivery cloud by building a distributed measurement infrastructure. Through extensive data collection and analysis, we deduce the key design features underlying the YouTube video delivery cloud. The design of the YouTube video delivery cloud consists of three major components: a "flat" video id space, multiple DNS namespaces reflecting a multi-layered logical organization of video servers, and a 3-tier physical cache hierarchy. By mapping the video id space to the logical servers via consistent hashing and cleverly leveraging DNS and HTTP re-direction mechanisms, such a design leads to a scalable, robust and flexible content distribution system.

With network components increasingly reliable, routing is playing an ever greater role in determining network reliability. This has spurred much activity in improving routing stability and reaction to failures and rekindled interest in centralized routing solutions, at least within a single routing domain. Centralizing decisions eliminates uncertainty and many inconsistencies and offers added flexibility in computing routes that meet different criteria. However, it also introduces new challenges, especially in reacting to failures where centralization can increase latency. This paper leverages the flexibility afforded by centralized routing to address these challenges. Specifically, we explore when and how standby backup forwarding options can be activated while waiting for an update from the centralized server after the failure of an individual component (link or node). We provide analytical insight into the feasibility of such backups as a function of network structure and quantify their computational complexity. We also develop an efficient heuristic reconciling protectability and performance, and demonstrate its effectiveness in a broad range of scenarios. The results should facilitate deployments of centralized routing solutions.

Traditional DSL troubleshooting solutions are reactive, relying mainly on customers to report problems, and tend to be labor-intensive, time consuming, prone to incorrect resolutions and overall can contribute to increased customer dissatisfaction. In this paper, we propose a proactive approach to facilitate troubleshooting customer edge problems and reducing customer tickets. Our system consists of: i) a ticket predictor which predicts future customer tickets; and ii) a trouble locator which helps technicians accelerate the troubleshooting process during field dispatches. Both components infer future tickets and trouble locations based on existing sparse line measurements, and the inference models are constructed automatically using supervised machine learning techniques. We propose several novel techniques to address the operational constraints in DSL networks and to enhance the accuracy of NEVERMIND. Extensive evaluations using an entire year worth of customer tickets and measurement data from a large network show that our method can predict thousands of future customer tickets per week with high accuracy and signifcantly reduce the time and effort for diagnosing these tickets. This is benefcial as it has the effect of both reducing the number of customer care calls and improving customer satisfaction.

Gaining a better knowledge of one's own network is crucial to effectively manage and secure today's large, diverse campus and enterprise networks. Because of the large number of IP addresses (or hosts) and the prevalent use of dynamic IP addresses, profiling and tracking individual hosts within such large networks may not be effective nor scalable. In this paper, we develop a novel methodology for capturing, characterizing, and tracking network activities at the block-level by carefully selecting a port feature vector and capturing the port activities of individual hosts within a block using a block-wise (host) port activity matrix (BPAM). Applying the SVD low-rank approximation technique, we obtain a low-dimensional subspace representation which captures the significant and typical host activities of the block. Using these subspace representations, we cluster and classify blocks to provide high-level descriptive labels to assist network operators and security analysts to gain insight into the network activities. We also develop novel methods to track and quantify changes in blocks' behaviors over time, and demonstrate how these methods can be utilized to identify major changes and anomalies within the network.

Today's large campus and enterprise networks are characterized by their complexity, i.e. containing thousands of hosts, and diversity, i.e. with various applications and usage patterns. To effectively manage and secure such networks, network operators and system administrators are faced with the challenge of characterizing, profiling and tracking activity patterns passing through their networks. Because of the large number of IP addresses and the prevalence of dynamic IP addresses, profiling and tracking individual hosts may not be effective nor scalable. In this paper, we develop a hierarchical extraction of activity patterns (HEAPs), which is a method for characterizing and profiling activity patterns within subnets. By representing activities within a subnet in a host-port association matrix (HPAM) and applying pLSA, we obtain co-clusters that capture the significant and dominant activity patterns of the subnet. Using these co-clusters, we utilize hierarchical clustering to cluster activity patterns to assist network operators and security analysts gain a ”big-picture” view of the network activity-patterns. We also develop a novel method to track and quantify changes in activity patterns within subnets over time and demonstrate how to utilize this method to identify major changes and anomalies within the network.

As a key approach to securing large networks, existing anomaly detection techniques focus primarily on network traffic data. However, the sheer volume of such data often renders detailed analysis very expensive and reduces the effectiveness of these tools. In this paper, we propose a light-weight anomaly detection approach based on unproductive DNS traffic, namely, the failed DNS queries, with a novel tool - DNS failure graphs. A DNS failure graph captures the interactions between hosts and failed domain names. We apply a graph decomposition algorithm based on the tri-nonnegative matrix factorization technique to iteratively extract coherent co-clusters (dense subgraphs) from DNS failure graphs. By analyzing the co-clusters in the daily DNS failure graphs from a 3-month DNS trace captured at a large campus network, we find these co-clusters represent a variety of anomalous activities, e.g., spamming, trojans, bots, etc.. In addition, these activities often exhibit distinguishable subgraph structures. By exploring the temporal properties of the co-clusters, we show our method can identify new anomalies that likely correspond to unreported domain-flux bots.

In this paper we conduct an extensive and in-depth study of traffic exchanged between YouTube data centers and its users, as seen from the perspective of a tier-1 ISP in Spring 2008 after YouTube was acquired by Google but before Google did any major restructuring of YouTube. Using flow-level data collected at multiple PoPs of the ISP, we first infer where the YouTube data centers are located and where they are connected to the ISP. We then deduce the load balancing strategy used by YouTube to service user requests, and investigate how load balancing strategies and routing policies affect the traffic dynamics across YouTube and the tier-1 ISP.

With network components increasingly reliable, routing is playing an ever greater role in determining network reliability. This has spurred much activity in improving routing stability and reaction to failures, and rekindled interest in centralized routing solutions, at least within a single routing domain. Centralizing decisions eliminates uncertainty and many inconsistencies, and offers added flexibility in computing routes that meet different criteria. However, it also introduces new challenges; especially in reacting to failures where centralization can increase latency. This paper leverages the flexibility afforded by centralized routing to address these challenges. Specifically, we explore when and how standby backup forwarding options can be activated, while waiting for an update from the centralized server after the failure of an individual component (link or node). We provide analytical insight into the feasibility of such backups as a function of network structure, and quantify their computational complexity. We also develop an efficient heuristic reconciling protectability and performance, and demonstrate its effectiveness in a broad range of scenarios. The results should facilitate deployments of centralized routing solutions.

In this paper we develop a unified theoretical framework for estimating various transmission costs of packet forwarding in wireless networks. Our framework can be applied to the three routing paradigms, best path routing, opportunistic routing, and stateless routing, to which nearly all existing routing protocols belong. We illustrate how packet forwarding under each paradigm can be modeled as random walks on directed graphs (digraphs). By generalizing the theory of random walks that has primarily been developed for undirected graphs to digraphs, we show how various transmission costs can be formulated in terms of hitting times and hitting costs of random walks on digraphs. As representative examples, we apply the theory to three specific routing protocols, one under each paradigm. Extensive simulations demonstrate that the proposed digraph based analytical model can achieve more accurate transmission cost estimation over existing methods.

This paper presents a new economic approach for studying competition and innovation in a complex and highly interactive system of network providers, users, and suppliers of digital goods and services (i.e., service providers). It employs Cournot and Bertrand games to model competition among service providers and network providers, respectively, and develops a novel unified model to capture the interaction and competition among these players in a "service-oriented" Internet. Incentives for service and network innovation are studied in this model.

With widespread popularity of smart phones, more and more users are accessing the Internet on the go. Understanding mobile user browsing behavior is of great significance for several reasons. For example, it can help cellular (data) service providers (CSPs) to improve service performance, thus increasing user satisfaction. It can also provide valuable insights about how to enhance mobile user experience by providing dynamic content personalization and recommendation, or location-aware services.

The ability to move energy around makes it feasible to build distributed energy storage systems that can robustly extend the lifetime of networked sensor systems. eShare supports the concept of energy sharing among multiple embedded sensor devices by providing designs for energy routers (i.e., energy storage and routing devices) and related energy access and network protocols. In a nutshell, energy routers exchange energy sharing control information using their data network while sharing energy freely among connected embedded sensor devices using their energy network. To improve sharing efficiency subject to energy leakage, we develop an effective energy charging and discharging mechanism using an array of ultra-capacitors as the main component of an energy router. We extensively evaluate our system under six real-world settings. Results indicate our charging and discharging control can effectively minimize the energy leaked away. Moreover, the energy sharing protocol can quantitatively share 113J energy with 96.82% accuracy in less than 2 seconds.

In this paper, we propose a novel technique for inferring the distribution of application classes present in the aggregated traffic flows between endpoints, which exploits both the statistics of the traffic flows, and the spatial distribution of those flows across the network. Our method employs a two-step supervised model, where the bootstrapping step provides initial (inaccurate) inference on the traffic application classes, and the graph-based calibration step adjusts the initial inference through the collective spatial traffic distribution. In evaluations using real traffic flow measurements from a large ISP, we show how our method can accurately classify application types within aggregate traffic between endpoints, even without the knowledge of ports and other traffic features. While the bootstrap estimate classifies the aggregates with 80% accuracy, incorporating spatial distributions through calibration increases the accuracy to 92%, i.e., roughly halving the number of errors.

Commercial agreements drive the routing policies used in today's Internet. The two most extensively studied commercial agreements are transit and peering; however, they are only two of many diverse and continuously evolving commercial agreements that ISPs enter into. So far, the only known practical safe and robust routing policy is Gao and Rexford's policy guideline, which is applicable to transit and peering agreements only. It is, therefore, of importance to identify routing policies that are safe and robust and, at the same time, capable of accommodating the diverse commercial agreements existing in the Internet. In particular, this paper investigates the extent to which routing policies can be devised to accommodate complex mutual transit agreements. We propose a series of policy guidelines that allow mutual transit agreements with progressively broader semantics to be established. Those policy guidelines guarantee routing safety and robustness as long as the autonomous system (AS) graph satisfies a corresponding set of precise topological constraints. An experimental evaluation of the proposed policy guidelines demonstrates the benefits they would likely afford in terms of routing reliability if adopted in the current Internet.

Supercomputers are prone to frequent faults that adversely affect their performance, reliability and functionality. System logs collected on these systems are a valuable resource of information about their operational status and health. However, their massive size, complexity, and lack of standard format makes it difficult to automatically extract information that can be used to improve system management. In this work we propose a novel method to succinctly represent the contents of supercomputing logs, by using textual clustering to automatically find the syntactic structures of log messages. This information is used to automatically classify messages into semantic groups via an online clustering algorithm. Further, we describe a methodology for using the temporal proximity between groups of log messages to identify correlated events in the system. We apply our proposed methods to two large, publicly available supercomputing logs and show that our technique features nearly perfect accuracy for online log-classification and extracts meaningful structural and temporal message patterns that can be used to improve the accuracy of other log analysis techniques.

The Internet host cardinality, defined as the number of distinct peers that an Internet host communicates with, is an important metric for profiling Internet hosts. Some example applications include behavior based network intrusion detection, p2p hosts identification, and server identification. However, due to the tremendous number of hosts in the Internet and high speed links, tracking the exact cardinality of each host is not feasible due to the limited memory and computation resource. Existing approaches on host cardinality counting have primarily focused on hosts of extremely high cardinalities. These methods do not work well with hosts of moderately large cardinalities that are needed for certain host behavior profiling such as detection of p2p hosts or port scanners. In this paper, we propose an online sampling approach for identifying hosts whose cardinality exceeds some moderate prescribed threshold, e.g. 50, or within specific ranges. The main advantage of our approach is that it can filter out the majority of low cardinality hosts while preserving the hosts of interest, and hence minimize the memory resources wasted by tracking irrelevant hosts. Our approach consists of three components: 1) two-phase filtering for eliminating low cardinality hosts, 2) thresholded bitmap for counting cardinalities, and 3) bias correction. Through both theoretical analysis and experiments using real Internet traces, we demonstrate that our approach requires much less memory than existing approaches do whereas yields more accurate estimates.

Unlike traditional wireless routing protocols which use a single fixed path, opportunistic routing explicitly takes advantage of the broadcast nature of wireless communications by using a set of forwarders to opportunistically perform packet forwarding. A key issue in the design of opportunistic routing protocols is the forwarder list selection problem. In this paper we establish a general theory for analyzing the forwarder list selection problem, and develop an optimal solution, the minimum transmission selection (MTS) algorithm, which minimizes the expected number of transmissions and it can be incorporated into existing opportunistic routing protocols to select optimal forwarder lists. Our theory and algorithm can also be generalized to optimize other routing objectives such as minimizing the expected transmission time or energy consumption in opportunistic routing. Through extensive simulations, we demonstrate that in more than 90% cases the MTS algorithm outperforms the ETX forwarder selection scheme used in existing opportunistic routing protocols such as ExOR and MORE.

To ensure sustainable operations of wireless sensor systems, environmental energy harvesting has been regarded as the right solution for long-term applications. In energy-dynamic environments, energy conservation is no longer considered necessarily beneficial, because energy storage units (e.g., batteries or capacitors) are limited in capacity and leakage-prone. In contrast to legacy energy conservation approaches, we aim at energy synchronization for wireless sensor devices. The starting point of this work is TwinStar, which uses ultra-capacitor as the only energy storage unit. To efficiently use the harvested energy, we design and implement leakage-aware feedback control techniques to match local and network-wide activity of sensor nodes with the dynamic energy supply from environments. We conduct system evaluation under three typical real-world settings - indoor, outdoor, and mobile backpack under a wide range of system settings. Results indicate our leakage-aware control can effectively utilize energy that could otherwise leak away. Nodes running leakage-aware control can enjoy 70% more energy than the ones running non-leakage-aware control and application performance (e.g., event detection) can be improved significantly.

The Internet inter-domain routing protocol, BGP, experiences frequent routing disruptions such as transient routing loops or loss of connectivity. The goal of this paper is to address this issue while preserving BGP's benefits in terms of operational maturity and flexibility in accommodating diverse policies. In realizing this goal, we apply to inter-domain routing a common concept in the design of highly reliable systems, namely, the use of redundancy, which we introduce in a manner that maximizes compatibility with the existing BGP protocol. The basic idea is to run several, mostly unchanged BGP processes that compute complementary routes, so that in the presence of network instabilities a working path remains available to any destination. The paper outlines the design of this approach and compares it to previously proposed alternatives. The benefits of the scheme are demonstrated using actual BGP data and realistic simulations.

In this paper, we propose a method, where the labeling of the data set is carried out in a semi-supervised manner with user-specified guarantees about the quality of the labeling. In our scheme, we assume that for each class, we have some heuristics available, each of which can identify instances of one particular class. The heuristics are assumed to have reasonable performance but they do not need to cover all instances of the class nor do they need to be perfectly reliable. We further assume that we have an infallible expert, who is willing to manually label a few instances. The aim of the algorithm is to exploit the cluster structure of the problem, the predictions by the imperfect heuristics and the limited perfect labels provided by the expert to classify (label) the instances of the data set with guaranteed precision (specificed by the user) with regards to each class. The specified precision is not always attainable, so the algorithm is allowed to classify some instances as dontknow. The algorithm is evaluated by the number of instances labeled by the expert, the number of dontknow instances (global coverage) and the achieved quality of the labeling. On the KDD Cup Network Intrusion data set containing 500,000 instances, we managed to label 96.6% of the instances while guaranteeing a nominal precision of 90% (with 95% confidence) by having the expert label 630 instances; and by having the expert label 1200 instances, we managed to guarantee 95% nominal precision while labeling 96.4% of the data. We also provide a case study of applying our scheme to label the network traffic collected at a large campus network.

Starting from the features and impact of energy leakage in ultra-capacitor powered systems, this demonstration highlights the design of a capacitor-only Twin-Star node, and a leakage-aware energy synchronization methodology.

Today’s Internet contains a large portion of “dynamic ” IP ad-dresses, which are assigned to clients upon request. A signif-icant amount of malicious activities have been reported from dynamic IP space, such as spamming, botnets, etc.. Accurate identification of dynamic IP addresses will help build black-lists of suspicious hosts with more confidence, and help track the sources of different types of anomalous activities. In this paper, we contrast traffic activity patterns between static and dynamic IP addresses in a large campus network, as well as their activity patterns when countering outside scanning traffic. Based on the distinct characteristics observed, we propose a scanning-based technique for identifying dynamic IP addresses in blocks. We conduct an experiment using a month-long data collected from our campus network, and instead of scanning our own network, we utilize identified outside scanning traffic. The experiment results demonstrate a high classification rate with low false positive rate. As an on-going work, we also introduce our design of an online classifier that identifies dynamic IP addresses in any network in real-time. 1.

This paper presents the design and implementation of a real-time behavior profiling system for high-speed Internet links. The profiling system uses flow-level information from continuous packet or flow monitoring systems, and uses data mining and information-theoretic techniques to automatically discover significant events based on the communication patterns of end-hosts. We demonstrate the operational feasibility of the system by implementing it and performing extensive benchmarking of CPU and memory costs using a variety of packet traces from OC-48 links in an Internet backbone network. To improve the robustness of this system against sudden traffic surges such as those caused by denial of service attacks or worm outbreaks, we propose a simple yet effective filtering algorithm. The proposed algorithm successfully reduces the CPU and memory cost while maintaining high profiling accuracy.

The recent advances of distributed hash tables (DHTs) facilitate the development of highly scalable and robust network applications and services. However, with applications and services each employing their own DHTs that perform essentially the same tasks, an open infrastructure providing the core DHT functionalities for these applications and services would represent a cost-effective solution. In this paper we present a generic secure framework for deploying secure overlay-based applications/services. We combine DHTs and identity-based encryption (IBE) to develop a novel architecture that is scalable and robust against man-in-the-middle attacks. We also develop an innovative mechanism called "WheelofTrust" that secures our framework against insider attacks. Based on the proposed architecture, we present some preliminary evaluation results from a prototype implementation.

Estimating the number of false negatives for a classifier when the true outcome of the classification is ascertained only for a limited number of instances is an important problem, with a wide range of applications from epidemiology to computer/network security. The frequently applied method is random sampling. However, when the target (positive) class of the classification is rare, which is often the case with network intrusions and diseases, this simple method results in excessive sampling. In this paper, we propose an approach that exploits the cluster structure of the data to significantly reduce the amount of sampling needed while guaranteeing an estimation accuracy specified by the user. The basic idea is to cluster the data and divide the clusters into a set of “strata”, such that the proportion of positive instances in the stratum is very low, very high or in between, respectively. By taking advantage of the different characteristics of the strata, more efficient estimation strategies can be applied, thereby significantly reducing the amount of required sampling. We also develop a computationally efficient clustering algorithm – referred to as class-focused partitioning – which uses the (imperfect) labels predicted by the classifier as additional guidance. We evaluated our method on the KDDCup network intrusion data set. Our method achieved better precision and accuracy with a 5% sample than the best trial of simple random sampling with 40% samples.

The three papers in this special section were originally presented at the IEEE INFOCOM 2006 conference in Barcelona. The augmented papers, which address issues in wireless networks and mobile computing, represent the high quality of research presented at the conference.

In this paper, we present the challenges in supporting multimedia, in particular, VoIP services over multihop wireless networks using commercial IEEE 802.11 MAC DCF hardware, and propose a novel software solution, called Layer 2.5 SoftMAC. Our proposed SoftMAC resides between the IEEE 802.11 MAC layer and the IP layer to coordinate the real-time (RT) multimedia and best-effort (BE) data packet transmission among neighboring nodes in a multihop wireless network. To effectively ensure acceptable VoIP services, channel busy time and collision rate need to be well controlled below appropriate levels. Targeted at this, our SoftMAC architecture employs three key mechanisms: 1) distributed admission control for regulating the load of RT traffic, 2) rate control for minimizing the impact of BT traffic on RT one, and 3) nonpreemptive priority queuing for providing high priority service to VoIP traffic. To evaluate the efficacy of these mechanisms, extensive simulations are conducted using the network simulator NS2. We also implement our proposed SoftMAC as a Windows network driver interlace specification (NDIS) driver and build a multihop wireless network testbed with 32 wireless nodes equipped with IEEE 802.11 a/b/g combo cards. Our evaluation and testing results demonstrate the effectiveness of our proposed software solution. Our proposed collaborative SoftMAC framework can also provide good support for A/V streaming in home networks where the network consists of hybrid WLAN (wireless LAN) and Ethernet

Binding services are crucial building blocks in networks and networked applications. A binding service (e.g., the domain name system (DNS)) maps certain information, namely, binding keys (e.g., host names), to other information, i.e., binding values (e.g., IP addresses), and answers queries for such key-value bindings. Clearly, building secure binding services that ensure the integrity and authenticity of bindings are vital to the correct operations of many networks and networked applications. In this paper we present a novel approach for building generic secure binding services that allow arbitrary key-value bindings as (trusted) infrastructure services to support a variety of networks and networked applications. We combine the Identity- Based Encryption (IBE) crypto-mechanisms with distributed hash table (DHT) techniques to develop an innovative architecture for building scalable, robust and secure binding services. Using this architecture, we implement a prototype system called Vault and evaluate its performance both in a local testbed and on the PlanetLab.

Large-scale peer-to-peer systems span a wide range of Internet locations. Such diversity can be leveraged to build overlay "detours" to circumvent periods of poor performance on the default path. However, identifying which peers are "good" relay choices in support of such detours is challenging, if one is to avoid incurring an overhead that grows with the size of the peer- to-peer system. This paper proposes and investigates the Earliest Branching Rule (EBR) to perform such a selection. EBR builds on the Earliest Diverging Rule (EDR) that selects relay nodes whose AS path diverges from the default path at the earliest possible point, but calls for monitoring a much smaller number of paths. As a result, it has a much lower overhead. The paper explores the performance and overhead of EBR, and compares them to that of EDR. The results demonstrate that EBR succeeds in selecting good relay nodes with minimum control overhead. Hence, providing a practical solution for dynamically building good overlays in large peer-to-peer systems.

Point-to-point delay is an important network performance measure as well as a key parameter in SLAs. We study how to measure and report delay in a concise and meaningful way for an ISP, and how to monitor it efficiently. We analyze various measurement intervals and potential metric definitions. We find that reporting high quantiles (between 0.95 and 0.99)every 10-30 minutes as the most effective way to summarize the delay in an ISP. We then propose an active probing scheme to estimate a high quantile with bounded error. We show that only a small number of probes are sufficient to provide an accurate estimate. We validate the proposed delay monitoring technique on real data collected on the Sprint IP backbone network.

Slow convergence in the Internet can be directly attributed to the "path exploration" phenomenon, inherent in all path vector protocols. The root cause for path exploration is the dependency among paths propagated through the network. Addressing this problem in BGP is particularly difficult as the AS paths exchanged between BGP routers are highly summarized. In this paper, we describe why path exploration cannot be countered effectively within the existing BGP framework, and propose a simple, novel mechanism - forward edge sequence numbers - to annotate the AS paths with additional "path dependency" information. We then develop an enhanced path vector algorithm, EPIC, shown to limit path exploration and lead to faster convergence. In contrast to other solutions, ours is shown to be correct on a very general model of Internet topology and BGP operation. Using theoretical analysis and simulations, we demonstrate that EPIC can achieve a dramatic improvement in routing convergence, compared to BGP and other existing solutions.

The current best-effort Internet cannot readily provide the service guarantees that VoIP applications often require. Path switching can potentially address this problem without requiring new network mechanisms, simply by leveraging the robustness to performance variations available from connectivity options such as multi-homing and overlays. In this paper, we evaluate the effectiveness and benefits of path switching in improving the quality of VoIP applications, and demonstrate its feasibility through the design and implementation of a prototype gateway. We argue for an application-driven path switching system that accounts for both network path characteristics and application-specific factors (e.g., codec algorithms, playout buffering schemes). We also develop an application path quality estimator based on the ITU-T E-model for voice quality assessment, and an application-driven path switching algorithm that dynamically adapts the time scales over which path switching decisions are made to maximize voice quality. Through network emulation and experiments over a wide-area multi-homed test bed, we show that, with sufficient path diversity, path switching can yield meaningful improvements in voice quality. Hence by exploiting the inherent path diversity of the Internet, application-driven path switching is a viable option in providing quality-of-service to applications.

Abstract — Static broadband wireless networks, due to their ease of deployment, are likely to proliferate in the near future. The major stumbling block, however, is that wireless links are prone to external interference, channel fading, inclement weather, etc. Therefore scalable and reliable routing despite frequent link quality fluctuations is needed for accelerating the growth of these networks. Most of the wireless routing schemes proposed in the literature are less suitable for these networks, as they are designed primarily for mobile ad hoc networks with dynamic and unpredictable topologies. In this paper, we propose a novel link-state-based blacklist-aided forwarding (BAF) approach, that takes advantage of the fact that the nodes and therefore their adjacencies are relatively static, for scalable packet delivery in static wireless networks. Under BAF, each packet carries a blacklist, a minimal set of degraded-quality links encountered along its path, and the next hop is determined based on both its destination and blacklist. BAF provides loop-free delivery of packets to reachable destinations regardless of the number of degraded links in the network. We evaluate the performance of BAF and show that it is not only reliable but also scalable. I.

Abstract- In this paper, we present the challenges in supporting VoIP services over multi-hop wireless networks using commercial IEEE 802.11 MAC DCF hardware, and propose a novel software solution, called Layer 2.5 SoftMAC. Our proposed SoftMAC resides between the 802.11 MAC layer and IP layer to coordinate the real-time and best-effort packet transmission among neighboring nodes in a multi-hop wireless network. To effectively support VoIP services, our SoftMAC architecture employs three key mechanisms: 1) distributed admission control for regulating the load of real time-traffic, 2) rate control for minimizing the impact of best-effort traffic on real-time traffic, and 3) non-preemptive priority queueing for providing high priority service to VoIP traffic. To evaluate the efficacy of these mechanisms, we conduct extensive simulations using the network simulator NS2. We also implement our proposed SoftMAC as a Windows Network Driver Interface Specification (NDIS) driver over Network Interface Card (NIC) driver, and build a multi-hop wireless network testbed with 32 wireless nodes equipped with 802.11 a/b/g combo cards. Our evaluation and testing results demonstrate the effectiveness of our proposed software solution. 1.

Recent spates of cyber-attacks and frequent emergence of applications affecting Internet traffic dynamics have made it imperative to develop effective techniques that can extract, and make sense of, significant communication patterns from Internet traffic data for use in network operations and security management. In this paper, we present a general methodology for building comprehensive behavior profiles of Internet backbone traffic in terms of communication patterns of end-hosts and services. Relying on data mining and information-theoretic techniques, the methodology consists of significant cluster extraction, automatic behavior classification and structural modeling for in-depth interpretive analyses. We validate the methodology using data sets from the core of the Internet. The results demonstrate that it indeed can identify common traffic profiles as well as anomalous behavior patterns that are of interest to network operators and security analysts.

We introduce a methodology to predict when and where link additions/upgrades have to take place in an Internet protocol (IP) backbone network. Using simple network management protocol (SNMP) statistics, collected continuously since 1999, we compute aggregate demand between any two adjacent points of presence (PoPs) and look at its evolution at time scales larger than 1 h. We show that IP backbone traffic exhibits visible long term trends, strong periodicities, and variability at multiple time scales. Our methodology relies on the wavelet multiresolution analysis (MRA) and linear time series models. Using wavelet MRA, we smooth the collected measurements until we identify the overall long-term trend. The fluctuations around the obtained trend are further analyzed at multiple time scales. We show that the largest amount of variability in the original signal is due to its fluctuations at the 12-h time scale. We model inter-PoP aggregate demand as a multiple linear regression model, consisting of the two identified components. We show that this model accounts for 98% of the total energy in the original signal, while explaining 90% of its variance. Weekly approximations of those components can be accurately modeled with low-order autoregressive integrated moving average (ARIMA) models. We show that forecasting the long term trend and the fluctuations of the traffic at the 12-h time scale yields accurate estimates for at least 6 months in the future.

In this paper, we investigate the fundamental trade-offs in aggregate packet scheduling for support of guaranteed delay service. In our study, we consider two classes of aggregate packet scheduling algorithms: the static earliest time first (SETF) and dynamic earliest time first (DETF). Through these two classes of aggregate packet scheduling (and together with the simple FIFO packet scheduling algorithm), we show that, with additional timestamp information encoded in the packet header for scheduling purposes, we can significantly increase the maximum allowable network utilization level, while, at the same time, reducing the worst-case edge-to-edge delay bound. Furthermore, we demonstrate how the number of the bits used to encode the timestamp information affects the trade-off between the maximum allowable network utilization level and the worst-case edge-to-edge delay bound. In addition, the more complex DETF algorithms have far superior performance than the simpler SETF algorithms. These results illustrate the fundamental trade-offs in aggregate packet scheduling algorithms and shed light on their provisioning power in support of guaranteed delay service.

Traffic measurement and monitoring are an important component of network management and traffic engineering. With high-speed Internet backbone links, efficient and effective packet sampling techniques for traffic measurement and monitoring are not only desirable, but also increasingly becoming a necessity. Since the utility of sampling depends on the accuracy and economy of measurement, it is important to control sampling error. In this paper, we propose an adaptive packet sampling technique for flow-level traffic measurement with a stratification approach. We employ and advance sampling theory in order to ensure the accurate estimation of large flows. With real network traces, we demonstrate that the proposed sampling technique provides unbiased estimation of flow size with controllable error bound, in terms of both packet and byte counts for elephant flows, while avoiding excessive oversampling.

This work explores the feasibility of improving the performance of end-to-end data transfers between different sites through path switching. Our study is focused on both the logic that controls path switching decisions and the configurations required to achieve sufficient path diversity. Specifically, we investigate two common approaches offering path diversity multi-homing and overlay networks - and investigate their characteristics in the context of a representative wide-area testbed. We explore the end-to-end delay and loss characteristics of different paths and find that substantial improvements can potentially be achieved by path switching, especially in lowering end-to-end losses. Based on this assessment, we develop a simple path-switching mechanism capable of realizing those performance improvements. Our experimental study demonstrates that substantial performance improvements are indeed achievable using this approach.

Multi-homing is a common practice among many (especially large) customer (or stub) networks. Although the purpose of multi-homing is primarily for enhanced reliability, it has also increasingly been used for load balancing and latency reduction. In this paper, we address the problem of how to perform scalable route selection in a multi-homed stub network to optimize network latency to various destinations as measured by round-trip-time (RTT). A straight forward method is to simply perform RTT measurements (e.g., using ping) to each destination via each provider and select the one with the minimum RTT as the "best" next-hop to the destination. Is there a more.

We perform a detailed analysis of point-to-point packet delay in an operational tier-1 network. The point-to-point delay is the time between a packet entering a router in one PoP (an ingress point) and its leaving a router in another PoP (an egress point). It measures the one-way delay experienced by packets from an ingress point to an egress point across an ISP's network and provides the most basic information regarding the delay performance of the ISP's network. Using packet traces captured in the operational network, we obtain precise point-to-point packet delay measurements and analyze the various factors affecting them. Through a simple, step-by-step, systematic methodology and careful data analysis, we identify the major network factors that contribute to point-to-point packet delay and characterize their effect on the network delay performance. Our findings are: 1) delay distributions vary greatly in shape, depending on the path and link utilization; 2) after constant factors dependent only on the path and packet size are removed, the 99th percentile variable delay remains under 1 ms over several hops and under link utilization below 90% on a bottleneck; 3) a very small number of packets experience very large delay in short bursts.

Dealing with network failures effectively is a major operational challenge for Internet service providers. Commonly deployed link state routing protocols such as OSPF react to link failures through global (i.e., network-wide) link state advertisements and routing table recomputations, causing significant forwarding discontinuity after a failure. The drawback with these protocols is that they need to trade off routing stability and forwarding continuity. To improve failure resiliency without jeopardizing routing stability, we propose a proactive local rerouting based approach called failure insensitive routing (FIR). The proposed approach prepares for failures using interface-specific forwarding, and upon a failure, suppresses the link state advertisement and instead triggers local rerouting using a backwarding table. In this paper, we prove that when no more than one link failure notification is suppressed, FIR always finds a loop-free path to a destination if one such path exists. We also formally analyze routing stability and network availability under both proactive and reactive approaches, and show that FIR provides better stability and availability than OSPF.

Route flap damping (RFD) is anecdotally considered to be a key contributor in the stability of the inter-domain routing system. It works by suppressing advertisements about persistently flapping routes, which otherwise would propagate throughout the Internet. It was recently shown that relatively stable routes, i.e., routes that fail occasionally, can be incorrectly suppressed by this mechanism for substantially long periods of time. This can be traced back to the complex interaction between BGP path exploration and the mechanism used by RFD to identify route flaps. In this paper we study the distinctive feature that distinguishes the sequence of updates following a single network event from that of persistently unstable routes. Based on this characteristic, we propose a new BGP route flap damping algorithm, RFD+, with the following properties - 1) it can correctly distinguish between route flaps and normal path exploration; 2) it suppresses routes that are frequently and persistently changing; and 3) it does not affect routes that fail occasionally. We present the algorithm and discuss its relevant properties; simulation studies are also conducted to illustrate the performance of our algorithm.

Location-based routing significantly reduces routing overheads in mobile ad hoc networks (MANETs) by utilizing position information of mobile nodes in forwarding decisions. A location service is therefore critical to location-based routing, the scalability of which hinges largely on the overheads of such a service. Although several location service schemes have been proposed, most of them focus only on one or two aspects of scalability in their performance evaluations, and a comprehensive comparative study is missing. We first explore the design space of location services and present a taxonomy of existing schemes. We then propose HIGH-GRADE, a new location service scheme that employs a multilevel hierarchical location server structure and a multi-grained location information organization. We develop a uniform theoretical framework to analyze HIGH-GRADE and four other existing schemes in terms of three metrics: location maintenance cost, location query cost, and storage requirement cost. We show that the design of a location service scheme involves tradeoffs among all three of these kinds of overhead. Further, in our theoretical analysis and simulation experiments, HIGH-GRADE demonstrates superior scalability, especially when a localized data traffic pattern is assumed.

The service overlay network (SON) is an effective means to deliver end-to-end QoS guaranteed applications on the current Internet. Duan et al. (2002) address the bandwidth provisioning problem on a SON, specifically, in determining the appropriate amount of bandwidth capacity to purchase from various autonomous systems so as to satisfy the QoS requirements of the SON's end users and at the same time maximize the total revenue of operating the overlay network. In this paper, we extend the concept of the service overlay network. Since traffic demands are time varying and there may be some unexpected events which can cause a traffic surge, these will significantly increase the probability of QoS violation and will reduce the profit margin of a SON. To overcome these problems, we propose to replicate services on the service gateways so as to dynamically adapt to these traffic surges. We show that the service replication problem, in general, is intractable. We propose an efficient service replication algorithm which replicates services for a subset of traffic flows. Under our replication strategy, one does not need to increase the bandwidth capacity of underlying links and at the same time, be able to increase the average profit for the overlay network. Experiments are carried out to illustrate that replication algorithm provides higher flexibility during traffic fluctuations and can quickly find a near-optimal solution.

No abstract available.

We present a novel bandwidth broker architecture for scalable support of guaranteed services that decouples the QoS control plane from the packet forwarding plane. More specifically, under this architecture, core routers do not maintain any QoS reservation states, whether per-flow or aggregate. Instead, the QoS reservation states are stored at and managed by a bandwidth broker. There are several advantages of such a bandwidth broker architecture. Among others, it avoids the problem of inconsistent QoS states faced by the conventional hop-by-hop, distributed admission control approach. Furthermore, it allows us to design efficient admission control algorithms without incurring any overhead at core routers. The proposed bandwidth broker architecture is designed based on a core stateless virtual time reference system developed recently. This virtual time reference system provides a unifying framework to characterize, in terms of their abilities to support delay guarantees, both the per-hop behaviors of core routers and the end-to-end properties of their concatenation. We focus on the design of efficient admission control algorithms under the proposed bandwidth broker architecture. We consider both per-flow end-to-end guaranteed delay services and class-based guaranteed delay services with flow aggregation. Using our bandwidth broker architecture, we demonstrate how admission control can be done on a per domain basis instead of on a "hop-by-hop" basis. Such an approach may significantly reduce the complexity of the admission control algorithms. In designing class-based admission control algorithms, we investigate the problem of dynamic flow aggregation in providing guaranteed delay services and devise a new apparatus to effectively circumvent this problem. We conduct detailed analyses to provide theoretical underpinning for our schemes as well as to establish their correctness. Simulations are also performed to demonstrate the efficacy of our schemes.

Bandwidth contention is still a challenging problem in providing efficient IP-based video-on-demand (VOD) service on broadband cable networks (BCNs), due to the lack of effective approaches to exploit the unique characteristics of BCNs. To address this issue, we have designed an optimal full-sharing (Dong Y et al., 2003) for VOD service over a single channel, which maximizes the number of simultaneous video sessions on the single channel. In this paper, we further extend our optimal scheduling for VOD service over multiple channels. We first analyze the expected session bandwidth of a video and then develop an efficient video assignment mechanism for maximizing the profit of a VOD system.

Traffic measurement and monitoring is an important component of network QoS management and traffic engineering. With high-speed Internet links, efficient and effective packet sampling techniques for traffic measurement are not only desirable, but increasingly becoming a necessity. In this paper, we propose and analyze an adaptive random packet sampling technique for traffic load measurement. In particular, we address the problem of bounding sampling error within a pre-specified tolerance level. Using real network traffic traces, we show that the proposed adaptive random sampling technique indeed produces the desired accuracy, while also yielding significant reduction in the amount of traffic samples.

We introduce a methodology to predict when and where link additions/upgrades have to take place in an IP backbone network. Using SNMP statistics, collected continuously since 1999, we compute aggregate demand between any two adjacent PoPs and look at its evolution at time scales larger than one hour. We show that IP backbone traffic exhibits visible long term trends, strong periodicities, and variability at multiple time scales. Our methodology relies on the wavelet multiresolution analysis and linear time series models. Using wavelet multiresolution analysis, we smooth the collected measurements until we identify the overall long-term trend. The fluctuations around the obtained trend are further analyzed at multiple time scales. We show that the largest amount of variability in the original signal is due to its fluctuations at the 12 hour time scale. We model inter-PoP aggregate demand as a multiple linear regression model, consisting of the two identified components. We show that this model accounts for 98% of the total energy in the original signal, while explaining 90% of its variance. Weekly approximations of those components can be accurately modeled with low-order autoregressive integrated moving average (ARIMA) models. We show that forecasting the long term trend and the fluctuations of the traffic at the 12 hour time scale yields accurate estimates for at least six months in the future.

The small-time (sub-seconds) scaling behaviors of Internet backbone traffic, based on traces collected from OC3/12/48 links in a tier-1 ISP is studied. We observe that for a majority of these traces, the (second-order) scaling exponents at small time scales (1 ms - 100 ms) are fairly close to 0.5, indicating that traffic fluctuations at these time scales are (nearly) uncorrelated. In addition, the traces manifest mostly monofractal behaviors at small time scales. The objective of the paper is to understand the potential causes or factors that influence the small-time scalings of Internet backbone traffic via empirical data analysis. We analyze the traffic composition of the traces along two dimensions - flow size and flow density. Our study uncovers dense flows (i.e., flows with bursts of densely clustered packets) as the correlation-causing factor in small time scales, and reveals that the traffic composition in terms of proportions of dense vs. sparse flows plays a major role in influencing the small-time scalings of aggregate traffic.

We advocate the notion of service overlay network (SON) as an effective means to address some of the issues, in particular, end-to-end quality of service (QoS), plaguing the current Internet, and to facilitate the creation and deployment of value-added Internet services such as VoIP, Video-on-Demand, and other emerging QoS-sensitive services. The SON purchases bandwidth with certain QoS guarantees from the individual network domains via bilateral service level agreement (SLA) to build a logical end-to-end service delivery infrastructure on top of the existing data transport networks. Via a service contract, users directly pay the SON for using the value-added services provided by the SON. In this paper, we study the bandwidth provisioning problem for a SON which buys bandwidth from the underlying network domains to provide end-to-end value-added QoS sensitive services such as VoIP and Video-on-Demand. A key problem in the SON deployment is the problem of bandwidth provisioning, which is critical to cost recovery in deploying and operating the value-added services over the SON. The paper is devoted to the study of this problem. We formulate the bandwidth provisioning problem mathematically, taking various factors such as SLA, service QoS, traffic demand distributions, and bandwidth costs. Analytical models and approximate solutions are developed for both static and dynamic bandwidth provisioning. Numerical studies are also performed to illustrate the properties of the proposed solutions and demonstrate the effect of traffic demand distributions and bandwidth costs on SON bandwidth provisioning.

We present a proxy-assisted video delivery architecture that can simultaneously reduce the resources requirements at the central server and the service latency experienced by clients (i.e., end users). Under the proposed video delivery architecture, we develop and analyze two novel proxy-assisted video streaming techniques for on-demand delivery of video objects to a large number of clients. By taking advantage of the resources available at the proxy servers, these techniques not only significantly reduce the central server and network resource requirements, but are also capable of providing near-instantaneous service to a large number of clients. We optimize the performance of our video streaming architecture by carefully selecting video delivery techniques for videos of various popularity and intelligently allocating resources between proxy servers and the central server. Through empirical studies, we demonstrate the efficacy of the proposed proxy-assisted video streaming techniques.

Effective service delivery capabilities are critical to the transformation of the Internet into a viable commercial infrastructure. At the same time, there are several design limitations that prevent this. We propose a novel service overlay architecture that serves as a flexible, unifying platform for delivering services over the Internet. We introduce a new addressing scheme and an associated service layer, which enables service-oriented routing and forwarding over the underlying IP network domain. We also describe the functionality of the network elements that are introduced by our architecture, namely service gateway (SG) and service point-of-presence (S-PoP). We also present examples to demonstrate the efficacy of our architecture.

We advocate the notion of service overlay network (SON) as an effective means to address some of the issues, in particular end-to-end QoS, plaguing the current Internet, and to facilitate the creation and deployment of value-added Internet services such as VoIP, video-on-demand, and other emerging QoS-sensitive services. A SON purchases bandwidth with certain QoS guarantees from individual network domains via a bilateral service level agreement (SLA) to build a logical end-to-end service delivery infrastructure on top of existing data transport networks. Via a service contract, users directly pay the SON provider for using the value-added services provided by the SON. We study the bandwidth provisioning problem for a service overlay network which is critical to the cost recovery in deploying and operating value-added services over the SON. We mathematically formulate the bandwidth provisioning problem, taking into account various factors such as SLA, service QoS, traffic demand distributions, and bandwidth costs. Analytical models and approximate solutions are developed for both static and dynamic bandwidth provisioning. Numerical studies are also performed to illustrate the properties of the proposed solutions and demonstrate the effect of traffic demand distributions and bandwidth costs on the bandwidth provisioning of a SON.

In this paper we study the scalability issue in the design of a centralized bandwidth broker model for dynamic control and management of QoS provisioning. We propose and develop a path-oriented, quota-based dynamic bandwidth allocation mechanism for efficient admission control operations under the centralized bandwidth broker model. We demonstrate that this dynamic bandwidth allocation mechanism can significantly reduce the overall number of QoS state accesses/updates, thereby increasing the overall call processing capability of the bandwidth broker. Based on the proposed dynamic bandwidth allocation mechanism, we also extend the centralized architecture with a single bandwidth broker to a hierarchically distributed architecture with multiple bandwidth brokers to further improve its scalability. Our study demonstrates that the bandwidth broker architecture can be designed in such a manner that it scales with the increase in the network capacity.

Timely detection of changes in traffic load is critical for initiating appropriate traffic engineering mechanisms. Accurate measurement of traffic is essential since the efficacy of change detection depends on the accuracy of traffic estimation. However, precise traffic measurement involves inspecting every packet traversing a link, resulting in significant overhead, particularly on high speed links. Sampling techniques for traffic load estimation are proposed as a way to limit the measurement overhead. In this paper, we address the problem of bounding sampling error within a pre-specified tolerance level and propose an adaptive random sampling technique that determines the minimum sampling probability adaptively according to traffic dynamics. Using real network traffic traces, we show that the proposed adaptive random sampling technique indeed produces the desired accuracy, while also yielding significant reduction in the amount of traffic samples. We also investigate the impact of sampling errors on the performance of load change detection.

A set of applications such as Internet video broadcasts, corporate telecasts, and distance learning require the simultaneous streaming of video to a large population of viewers across the Internet. The high bandwidth requirements and the multi-timescale burstiness of compressed video make it a challenging problem to provision network resources for streaming multimedia. For such applications to become affordable and ubiquitous, it is necessary to develop scalable techniques to efficiently stream video to a large number of disparate clients across a heterogeneous Internet. In this paper, we propose to multicast smoothed video over an application-level overlay network of proxies, and to differentially cache the video at the intermediate nodes (proxies) in the distribution tree, in order to reduce the network bandwidth requirements of video dissemination. We formulate the multicast smoothing problem as an optimization problem, and develop an algorithm for computing the set of transmission schedules for the tree that minimize the peak rate and rate variability, given buffer constraints at different nodes in the tree. We also develop an algorithm to compute the minimum buffer allocation in the entire tree, such that feasible transmission to all the clients is possible, when the tree has heterogeneous rate constraints. We show through trace-driven simulations that substantial benefits are possible from multicast smoothing and differential caching, and that these gains can be realized even with modest proxy caches.

We survey advances in theories and models for Internet quality of service (QoS). We start with the theory of network calculus, which lays the foundation for support of deterministic performance guarantees in networks, and illustrate its applications to integrated services, differentiated services, and streaming media playback delays. We also present mechanisms and architecture for scalable support of guaranteed services in the Internet, based on the concept of a stateless core. Methods for scalable control operations are also discussed. We then turn our attention to statistical performance guarantees and describe several new probabilistic results that can be used for a statistical dimensioning of differentiated services. Lastly, we review proposals and results in supporting performance guarantees in a best effort context. These include models for elastic throughput guarantees based on TCP performance modeling, techniques for some QoS differentiation without access control, and methods that allow an application to control the performance it receives, in the absence of network support.

Most of the QoS routing schemes proposed so far require periodic exchange of QoS state information among routers, imposing both communication overhead on the network and processing overhead on core routers. Furthermore, stale QoS state information causes the performance of these QoS routing schemes to degrade drastically. In order to circumvent these problems, we focus on localized QoS routing schemes where the edge routers make routing decisions using only local information and thus reducing the overhead at core routers. We first describe virtual capacity based routing (vcr), a theoretical scheme based on the notion of virtual capacity of a route. We then propose proportional sticky routing, an easily realizable approximation of vcr and analyze its performance. We demonstrate through extensive simulations that adaptive proportional routing is indeed a viable alternative to the global QoS routing approach.

This paper presents architecture and mechanisms to support multiple QoS under the DiffServ paradigm. On the data plane, we present a node architecture based on the virtual time reference system (VTRS), which is a unifying scheduling framework for scalable support of the guaranteed service. The key building block of our node architecture is the core-stateless virtual clock (CSVC) scheduling algorithm, which, in terms of providing delay guarantee, has the same expressive power as a stateful weighted fair queueing (WFQ) scheduler. Based on the CSVC scheduler, we design a node architecture that is capable of supporting integrated transport of the guaranteed service (GS), the premium service (PS), the assured service (AS), and the traditional best-effort (BE) service. On the control plane, we present a BE architecture to provide flexible resource allocation and QoS provisioning. Simulation results demonstrate that our architecture and mechanisms can provide scalable and flexible transport of integrated traffic of the GS, the PS, the AS, and the BE services.

We investigate the fundamental trade-offs in aggregate packet scheduling for the support of guaranteed delay service. Besides the simple FIFO packet scheduling algorithm, we consider two new classes of aggregate packet scheduling algorithms: the static earliest time first (SETF) and dynamic earliest time first (DETF). Through these two classes of aggregate packet scheduling, we show that, with additional time stamp information encoded in the packet header for scheduling purpose, we can significantly increase the maximum allowable network utilization level, while at the same time reducing the worst-case edge-to-edge delay bound. Furthermore, we demonstrate how the number of the bits used to encode the time stamp information affects the trade-off between the maximum allowable network utilization level and the worst-case edge-to-edge delay bound. In addition, the more complex DETF algorithms have far better performance than the simpler SETF algorithms. These results illustrate the fundamental trade-offs in aggregate packet scheduling algorithms and shed light on their provisioning power in support of guaranteed delay service.

IP multicast is an important enabling service for the current and future Internet. With the explosive growth of the Internet, a challenging issue facing IP multicast is scalability, in particular, the problem of multicast forwarding state and control explosion. In this paper, we propose a new methodology to address the multicast scalability problem for backbone domains-multicast tunneling with branch filtering (MTBF). This multicast group aggregation scheme is designed on top of the inter-domain protocol architecture such as MASC/BGMF, and is independent of any underlying intra-domain multicast protocols. It aggregates multicast groups by constructing bolder router (BR)-based multicast routing trees and forwards data by using an encapsulation technique called multicast tunneling (MT). The feasibility and performance of our scheme is demonstrated through analysis and simulations.

This paper presents a network node architecture and several traffic management mechanisms that are capable of achieving QoS provisioning for the guaranteed service (GS), the controlled-load (CL) service, and the best-effort (BE) service under IETF integrated services (IntServ) paradigm. Our architecture offers the attractive feature of in-sequence delivery for all packets, albeit some of which may be out-of-profile. Simulation results show that, once admitted into the network, our architecture and traffic management algorithms provide hard performance guarantees to GS flows under all conditions, consistent (or soft) performance to CL flows under both light load and heavy load conditions, and minimal negative impact to in-profile GS, CL and BE traffic should there be any out-of-profile behavior from some flows.

A transcoder design is proposed in which the transcoder loads the pre-encoded embedded wavelet coefficients and computes the DCT coefficients. The resulting DCT coefficients are quantized and sorted by multi-grid embedded coding to output a compressed DCT bitstream. This transcoder has two operational modes: open-loop and closed-loop. The open-loop scheme is designed for direct transcoding, targeted to applications in which receivers are connected to the transcoder through a fast network and demand the same rate. In contrast, the closed-loop scheme is designed for fully progressive transcoding, targeted to receivers which are connected to the transcoder through a slow network connection, and may demand heterogeneous rates. The performance of the transcoder is evaluated in both open-loop mode and close-loop mode.

Many emerging applications involve real-time packet video transmission over noisy wireless networks. To ensure reliable video transmission, an automatic repeat request (ARQ) scheme is used for repairing packet loss over a channel by retransmitting corrupted packets. However, an ARQ resolves the problem of packet loss at the expense of varying an effective channel rate as well as introducing extra latency. These properties increase the difficulty of rate control for real-time wireless video when the buffer overflow and underflow are taken into account. Therefore, we propose a novel ARQ-based rate control scheme, called "channel condition ARQ rate control" by using embedded coding to design an efficient retransmission policy for wireless video. This scheme achieves both maximal channel utilization and smooth video quality perceived at an end-host, which has a low implementation complexity under buffer constraints. We have conducted extensive simulations to verify the efficiency and robustness of the proposed scheme.

Most of the QoS routing schemes proposed so far require periodic exchange of QoS state information among routers, imposing both communication overhead on the network and processing overhead on core routers. Furthermore, stale QoS state information causes the performance of these QoS routing schemes to degrade drastically. In order to circumvent these problems, we focus on localized QoS routing schemes where the edge routers make routing decisions using only "local" information and thus reducing the overhead at core routers. We first describe virtual capacity-based routing (VCR), a theoretical scheme based on the notion of virtual capacity of a route. We then propose proportional sticky routing (PSR), an easily realizable approximation of VCR and analyze its performance. We demonstrate through extensive simulations that adaptive proportional routing is indeed a viable alternative to the global QoS routing approach.

For scalable support of guaranteed services that decouples the QoS control plane from the packet forwarding plane. More specifically, under this architecture, core routers do not maintain any QoS reservation states, whether per-flow or aggregate. Instead, QoS reservation states are stored at and managed by bandwidth broker(s). There are several advantages of such a bandwidth broker architecture. Among others, it relieves core routers of QoS control functions such as admission control and QoS state management, and thus enables a network service provider to introduce new (guaranteed) services without necessarily requiring software/hardware upgrades at core routers. Furthermore, it allows us to design efficient admission control algorithms without incurring any overhead at core routers. The proposed bandwidth broker architecture is designed based on a core stateless virtual time reference system developed in [20].

We propose and develop a novel virtual time reference system as a unifying scheduling framework to provide scalable support for guaranteed services. This virtual time reference system is designed as a conceptual framework upon which guaranteed services can be implemented in a scalable manner using the DiffServ paradigm. The key construct in the proposed virtual time reference system is the notion of packet virtual time stamps, whose computation is core stateless, i.e., no per-flow states are required for its computation. We lay the theoretical foundation for the definition and construction of packet virtual time stamps. We describe how per-hop behavior of a core router (or rather its scheduling mechanism) can be characterized via packet virtual time stamps, and based on this characterization establish end-to-end per-flow delay bounds. Consequently, we demonstrate that, in terms of its ability to support guaranteed services, the proposed virtual time reference system has the same expressive power and generality as the IntServ model. Furthermore, we show that the notion of packet virtual time stamps leads to the design of new core stateless scheduling algorithms, especially work-conserving ones. In addition, our framework does not exclude the use of existing scheduling algorithms such as stateful fair queuing algorithms to support guaranteed services.

Real-time distribution of stored video over wide-area networks (WANs) is a crucial component of many emerging distributed multimedia applications. The heterogeneity in the underlying network environments is an important factor that must be taken into consideration when designing an end-to-end video delivery system. We present a novel approach to the problem of end-to-end video delivery over WANs using proxy servers situated between local-area networks (LANs) and a backbone WAN. A major objective of our approach is to reduce the backbone WAN bandwidth requirement. Toward this end, we develop an effective video delivery technique called video staging via intelligent utilization of the disk bandwidth and storage space available at proxy servers. Using this video staging technique, only part of a video stream is retrieved directly from the central video server across the backbone WAN whereas the rest of the video stream is delivered to users locally from proxy servers attached to the LANs. In this manner, the WAN bandwidth requirement can be significantly reduced, particularly when a large number of users from the same LAN access the video data. We design several video staging methods and evaluate their effectiveness in trading the disk bandwidth of a proxy server for the backbone WAN bandwidth. We also develop two heuristic algorithms to solve the problem of designing a multiple video staging scheme for a proxy server with a given video access profile of a LAN. Our results demonstrate that the proposed proxy-server-based approach provides an effective and scalable solution to the problem of the end-to-end video delivery over WANs.

This paper presents an implementation architecture based on per flow queueing that is capable of achieving QoS provisioning for future integrated services networks consisting of the guaranteed service (GS), the controlled-load (CL), and the best-effort (BE) service classes. We propose several novel traffic management mechanisms, including adaptive rate allocation for controlled-load (ARC), a hybrid model-based and measurement-based admission control algorithm for GS and CL flows, and a quasi-pushout plus (QPO+) packet discarding mechanism. Simulation results show that our architecture and algorithms provide hard QoS guarantees to GS flows under all conditions, consistent (soft) QoS to CL flows under both light and heavy load conditions, and effective control of negative impact from non-conforming CL flows. Our architecture and algorithms also resolve several issues associated with the traditional class-based approach.

In this paper, we propose a novel proxy-based hierarchical gateway scheme to optimize receiver adaptation layered video transmission in multicast scenarios. The proxies within networks are defined as transport layer gateways to coordinate senders and receivers. By using the proxies, the receiver adaptation for diverse bandwidth networks is synchronized. Additionally, we also incorporate embedded codecs into the structure of layers to perform hybrid scalable video coding. From cooperation between transport layer proxies and application layer hybrid codecs, the proxy scheme improves the scalability of the network and provides a solution to heterogeneous video requirements among receivers.

Receiver adaptation layered multicast video has been proposed to address the issue of network bandwidth heterogeneity in multiparty video communication over networks. An important issue in this approach is how to conduct layer adaptation to achieve the "optimal level" of subscription to maximize the perceived video quality at receivers while utilizing bandwidth efficiently. In the paper, optimal layers are typically determined by congestion signals fed back from networks. This approach implies that instantaneous congestion is a key parameter; however, in random traffic, such an implication somewhat under-estimates other parameters. In order to investigate the performance of "layer adaptation" in random traffic for improving the network based multi party video communication system, in this paper we present an analytical studying of the issue of receiver layer adaptation for layered video transmission. In this work, we use the notion of congestion probability as a partial and indirect measure of the perceived layered video quality at a receiver. The system's efficiency under a given receiver layer adaptation scheme is also defined and used as a metric to study the performance of a receiver layer adaptation scheme. Through the analysis, we determine the optimal receiver layer adaptation scheme, which maximizes the system efficiency while providing best sustainable video quality to a receiver. We show that the greedy receiver layer adaptation scheme is indeed optimal if the traffic generated by various layers of a layered video as well as the cross traffic are constant. However, in a more realistic setting where layered video traffic or the cross traffic varies over the time, the greedy receiver layer adaptation scheme is in general not optimal. To verify our theory, we conduct simulations.

A number of applications such as internet video broadcasts, corporate telecasts, distance learning etc. require transmission of streaming video to multiple simultaneous users across an internetwork. The high bandwidth requirements coupled with the multi-timescale burstiness of compressed video make it a challenging problem to provision network resources for transmitting streaming multimedia. For such applications to become affordable and ubiquitous, it is necessary to develop scalable techniques which can efficiently deliver streaming video to multiple heterogeneous clients across a heterogeneous internetwork. We propose using multicasting of smoothed video and differential caching of the video at intermediate nodes in the distribution tree, as techniques for reducing the network bandwidth requirements of such dissemination. We formulate the multicast smoothing problem, and develop an algorithm for computing the set of optimally smoothed transmission schedules for the tree (such that the transmission schedule along each link in the tree has the lowest peak rate and rate variability for any feasible transmission schedule for that link) given a buffer allocation to the different nodes in the tree. We also develop an algorithm to compute the minimum total buffer allocation to the entire tree and the corresponding allocation to each node, such that feasible transmission is possible to all the clients, when the tree has heterogeneous rate constraints. MPEG-2 trace-driven performance evaluations indicate that there are substantial benefits from multicast smoothing and differential caching. For example, the optimal multicast smoothing can reduce the total transmission bandwidth requirements in the distribution tree by more than a factor of 3 as compared to multicasting the unsmoothed stream.

Video delivery from a server to a client across a network is an important component of many multimedia applications. While delivering a video stream across a resource constrained network, loss of frames may be unavoidable. Under such circumstances, it is desirable to find a server transmission schedule that can efficiently utilize the network resources while maximizing the perceived quality-of-service (QoS) at the client. To address this issue, we introduce the notion of selective frame discard at the server and formulate the optimal selective frame discard problem using a QoS based cost function. Given network bandwidth and client buffer constraints, we develop an O(N log N) algorithm to find the minimum number of frames that must be discarded in order to meet these constraints. The correctness of the algorithm is also formally established. Since the computational complexity of the optimal algorithm for solving the optimal selective frame discard problem is prohibitively high in general, we also develop several efficient heuristic algorithms for selective frame discard. These algorithms are evaluated using JPEG video traces.

IP Multicast is an important enabling service for the current and future Internet. With the explosive, growth of the Internet, a challenging issue facing IP multicast is scalability, in particular, the problem of multicast forwarding state and control explosion. In this paper, we propose a new methodology to address the multicast scalability problem for backbone domains Multicast Tunneling with Branch Filtering (MTBF). This multicast group aggregation scheme is designed on top of the inter-domain protocol architecture such as MASC/BGMP, and is independent of any underlying intra-domain multicast protocols. It aggregates multicast groups by constructing Border Router (BR)-based multicast routing trees and forwards data by using an encapsulation technique called Multicast Tunneling (MT). To minimize excess traffic due to aggregate multicast address based data forwarding, an efficient Dynamic Filtering Point Selection (DFPS) algorithm is used. The feasibility and performance of our scheme is demonstrated through analysis and simulations.

We present a novel video streaming technique called catching for on-demand delivery of “hot” (i.e., frequently accessed) video objects to a large number of clients. This technique not only significantly reduces the server and network resource requirements but also is capable of providing near-instantaneous service to a large number of clients. By combining this technique for delivery of “hot” video objects with controlled multicast [4] for delivery of “cold” video objects, we design an efficient video delivery scheme referred to as selective catching. Through empirical studies, we demonstrate the efficacy of the proposed video delivery schemes.

We study the problem of resource allocation and control for a network node with regulated traffic. Both guaranteed lossless service and statistical service with small loss probability are considered. We investigate the relationship between source characteristics and the buffer/bandwidth tradeoff under both services. Our contributions are the following. For guaranteed lossless service, we find that the optimal resource allocation scheme suggests that sources sharing a network node with finite bandwidth and buffer space divide into groups according to time scales defined by their leaky-bucket parameters. This time-scale separation determines the manner by which the buffer and bandwidth resources at the network node are shared among the sources. For statistical service with a small loss probability, we present a new approach for estimating the loss probability in a shared buffer multiplexer using the "extremal" on-off, periodic sources. Under this approach, the optimal resource allocation for statistical service is achieved by maximizing both the benefits of buffering sharing and bandwidth sharing. The optimal buffer/bandwidth tradeoff is again determined by a time-scale separation.

In this paper we present a novel network-conscious approach to the problem of end-to-end video delivery over wide-area networks using proxy servers situated between local-area networks (LANs) and a backbone wide-area network (WAN). We develop a novel and effective video delivery technique called video staging via intelligent utilization of the disk bandwidth and storage space available at proxy servers. We also design several video staging methods and evaluate their effectiveness in reducing the backbone WAN bandwidth requirement. Our results demonstrate that the proposed proxy-server-based, network-conscious approach provides an effective and scalable solution to the problem of the end-to-end video delivery over wide-area networks.

Variable-bit-rate (VBR) compressed video can exhibit significant multiple-time-scale bit-rate variability. In this paper we consider the transmission of stored video from a server to a client across a network, and explore how the client buffer space can be used most effectively toward reducing the variability of the transmitted bit rate. Two basic results are presented. First, we show how to achieve the greatest possible reduction in rate variability when sending stored video to a client with given buffer size. We formally establish the optimality of our approach and illustrate its performance over a set of long MPEG-1 encoded video traces. Second, we evaluate the impact of optimal smoothing on the network resources needed for video transport, under two network service models: deterministic guaranteed service (Chang 1994; Wrege et al. 1996) and renegotiated constant-bit-rate (RCBR) service (Grossglauser et al. 1997). Under both models, the impact of optimal smoothing is dramatic.

In this paper we study the problem of resource allocation and control for an ATM node with regulated traffic. Both guaranteed lossless service and statistical service with small loss probability are considered. We investigate the relationship between source characteristics and the buffer/bandwidth trade-off under both services. Our contributions are the following. For guaranteed lossless service, we find that the optimal resource allocation scheme suggests a time scale separation of sources sharing an ATM node with finite bandwidth and buffer space, and the optimal buffer/bandwidth trade-off is determined by the sources' time scale. For statistical service with a small loss probability, we present a new approach for estimating the loss probability in a shared buffer multiplexor with the so called "extremal" on-off periodic sources. Under this approach, the optimal resource allocation for statistical service is achieved by maximizing both the benefits of buffering sharing and bandwidth sharing. The optimal buffer/bandwidth trade-off is again determined by time scale separation.

Variable bit-rate (VBR) compressed video is known to exhibit significant, multiple-time-scale rate variability. A number of researchers have considered transmitting stored video from server to a client using smoothing algorithms to reduce this rate variability. These algorithms exploit client buffering capabilities and determine a "smooth" rate transmission schedule, while ensuring that a client buffer neither overflows nor underflows. We investigate how video smoothing impacts the statistical multiplexing gains available with such traffic, and we show that a significant amount of statistical multiplexing gains can still be achieved. We then examine the implication of these results on network resource management and call admission control when transmitting smoothed stored video using VBR service with statistical quality-of-service (QoS) guarantees. Specifically, we present a uniform call admission control scheme based on a Chernoff bound method that uses a simple, novel traffic model requiring only a few parameters. This scheme provides an easy and flexible mechanism for supporting multiple VBR service classes with different QoS requirements. We evaluate the efficacy of the call admission control scheme over a set of MPEG-1 coded video tracts.

We study the performance of a multiplexer using the generalized processor sharing (GPS) scheduling to serve Markov modulated fluid sources (MMFSs). We focus on a two-queue GPS system serving two classes of sources. By using a bounding approach combined with an approximation approach and by taking advantage of the specific structure of MMFSs, we are able to derive a lower bound and an upper bound approximation on queue length distributions for each class of the GPS system. Numerical investigations show that the lower bound and the upper bound approximation are very accurate. Hence our work greatly improves the earlier results on GPS scheduling which are obtained for a more general stochastic model. Application of our performance bounds to call admission control and bandwidth sharing is also illustrated, and a comparison with FIFO and strict priority in different scenarios is presented. We show that the flexibility provided by GPS does not provide much better performance than FIFO and priority when the classes only have loss requirements. However, this flexibility provides better performance when the classes exhibit delay requirements as well as loss requirements.

VBR compressed video is known to exhibit significant, multiple-time-scale bit rate variability. In this paper, we consider the transmission of stored video from a server to a client across a high speed network, and explore how the client buffer space can be used most effectively toward reducing the variability of the transmitted bit rate.We present two basic results. First, we present an optimal smoothing algorithm for achieving the greatest possible reduction in rate variability when transmitting stored video to a client with given buffer size. We provide a formal proof of optimality, and demonstrate the performance of the algorithm on a set of long MPEG-1 encoded video traces. Second, we evaluate the impact of optimal smoothing on the network resources needed for video transport, under two network service models: Deterministic Guaranteed service [1, 9] and Renegotiated CBR (RCBR) service [8, 7]. Under both models, we find the impact of optimal smoothing to be dramatic.

We develop bounds on the individual session backlog and delay distribution under the generalized processor sharing (GPS) scheduling discipline. This work is motivated by, and is an extension of, Parekh and Gallager's (see IEEE/ACM Trans. Networking, vol.1, no.6, p.344-357, 1993, and vol. 2, no.4, p.137-150, 1994) deterministic study of the GPS scheduling discipline with leaky-bucket token controlled sessions. Using the exponentially bounded burstiness (EBB) process model introduced by Yaron and Sidi (see IEEE/ACM Trans. Networking, vol.1, p.372-385, 1993) as a source traffic characterization, we establish results that extend the deterministic study of GPS. For a single GPS server in isolation, we present statistical bounds on the distributions of backlog and delay for each session. In the network setting, we show that networks belonging to a broad class of GPS assignments, the so-called consistent relative session treatment (CRST) GPS assignments, are stable in a stochastic sense. In particular, we establish simple bounds on the distribution of backlog and delay for each session in a rate proportional processor sharing (RPPS) GPS network with arbitrary topology.>

In this paper, we consider the problem of providing statistical guarantees (for example, on the tail distribution of delay) under the Generalized Processor Sharing (GPS) scheduling discipline. This work is motivated by, and is an extension of, Parekh and Gallager's deterministic study of GPS scheduling discipline with leaky-bucket token controlled sessions [PG93a,b, Parekh92]. Using the exponentially bounded burstiness (E.B.B.) process model introduced in [YaSi93a] as a source traffic characterization, we establish results that extend the deterministic study of GPS: for a single GPS server in isolation, we present statistical bounds on the tail distributions of backlog and delay for each session. In the network setting, we show that networks belonging to a broad class of GPS assignments, the so-called Consistent Relative Session Treatment (CRST) GPS assignments, are stable in a stochastic sense. In particular, we establish simple bounds on the tail distribution of backlog and delay for each session in a Rate Proportional Processor Sharing (RPPS) GPS network with arbitrary topology.

Let K be any field, and let F: K/sup n/ to K/sup n/ be a bijection with the property that both F and F/sup -1/ are computable using only arithmetic operations from K. Motivated by cryptographic considerations, the authors concern themselves with the relationship between the arithmetic complexity of F and the arithmetic complexity of F/sup -1/. They give strong relations between the complexity of F and F/sup -1/ when F is an automorphism in the sense of algebraic geometry (i.e. a formal bijection defined by n polynomials in n variables with a formal inverse of the same form). These constitute all such bijections in the case in which K is infinite. The authors show that at polynomially bounded degree, if an automorphism F has a polynomial-size arithmetic circuit, then F/sup -1/ has a polynomial-size arithmetic circuit. Furthermore, this result is uniform in the sense that there is an efficient algorithm for finding such a circuit for F/sup -1/, given such a circuit for F. This algorithm can also be used to check whether a circuit defines an automorphism F. If K is the Boolean field GF(2), then a circuit defining a bijection does not necessarily define an automorphism. However, it is shown in this case that, given any K/sup n/ to K/sup n/ bijection, there always exists an automorphism defining that bijection. This is not generally true for an arbitrary finite field.>