Neural networks (NNs) have emerged as promising tools for solving constrained optimization problems in real-time. However, ensuring constraint satisfaction for NN-generated solutions remains challenging due to prediction errors. Existing methods to ensure NN feasibility either suffer from high computational complexity or are limited to specific constraint types. We present Bisection Projection, an efficient approach to ensure NN solution feasibility for optimization over general compact sets with non-empty interiors. Our method comprises two key components: (i) a dedicated NN (called IPNN) that predicts interior points (IPs) with low eccentricity, which naturally accounts for approximation errors; (ii) a bisection algorithm that leverages these IPs to recover solution feasibility when initial NN solutions violate constraints. We establish theoretical guarantees by providing sufficient conditions for IPNN feasibility and proving bounded optimality loss of the bisection operation under IP predictions. Extensive evaluations on real-world non-convex problems demonstrate that Bisection Projection achieves superior feasibility and computational efficiency compared to existing methods, while maintaining comparable optimality gaps.

Projection-free first-order methods, e.g., the celebrated Frank-Wolfe (FW) algorithms, have emerged as powerful tools for optimization over simple convex sets such as polyhedra, because of their scalability, fast convergence, and iteration-wise feasibility without costly projections. However, extending these methods effectively to general compact convex sets remains challenging and largely open, as FW methods rely on expensive linear optimization oracles (LOO), while penalty-based methods often struggle with poor feasibility. We tackle this open challenge by presenting **Hom-PGD**, a novel projection-free method without expensive (optimization) oracles. Our method constructs a homeomorphism between the convex constraint set and a unit ball, transforming the original problem into an equivalent ball-constrained formulation, thus enabling efficient gradient-based optimization while preserving the original problem structure. We prove that Hom-PGD attains *optimal* convergence rates matching gradient descent with constant step-size to find an $\epsilon$-approximate (stationary) solution: $\mathcal{O}(\log (1/\epsilon))$ for strongly convex objectives, $\mathcal{O}(\epsilon^{-1})$ for convex objectives, and $\mathcal{O}(\epsilon^{-2})$ for non-convex objectives. Meanwhile, Hom-PGD enjoys a low per-iteration complexity of $\mathcal{O}(n^2)$, without expensive oracles like LOO or projection, where $n$ is the input size. Our framework further extends to certain non-convex sets, broadening its applicability in practical optimization scenarios with complex constraints. Extensive numerical experiments demonstrate that Hom-PGD achieves comparable convergence rates to state-of-the-art projection-free methods, while significantly reducing per-iteration runtime (up to 5 orders of magnitude faster) and thus the total problem-solving time.

We consider the problem of exploring travel demand statistics to optimize ride-sharing routing, which is to determine a route to transport multiple customers with similar itineraries and schedules in a cost-effective and timely manner. This problem is important for unleashing the economic and societal benefits of ride-sharing. Meanwhile, it is challenging due to the need to (i) meet the travel delay requirements of customers and (ii) make online decisions without knowing the exact travel demands beforehand. We present a general framework for exploring the new design space enabled by the demand-aware approach. We show that demand-aware ride-sharing routing is fundamentally a two-stage stochastic optimization problem. While the problem is combinatorial in nature and challenging, we exploit the two-stage structure to design an optimal solution that maximizes the expected reward of the route with polynomial time complexity, which makes it amenable to practical implementation. Our approach can be applied to optimize a variety of objectives in a ride-sharing trip, including revenue, driver’s profit, and total travel time reduction compared to serving customers individually. We carry out extensive simulations based on real-world travel demand traces in Manhattan. Simulation results show that applying our demand-aware solution increases the revenue by 26% against conceivable alternatives. As compared to the case without ride-sharing, our ride-sharing solution increases the driver’s profit per slot by 12% and decreases the total vehicle travel time (an indicator of greenhouse gas emission) by 16%.

We consider the problem of minimizing emission of a heavy-duty truck transporting freight between two locations subject to a hard deadline constraint. The truck is equipped with a multi-speed transmission and a modern combustion engine that intelligently switches among multiple fuel injection strategies at certain engine speeds (called switching speeds) to achieve lower emission profiles. Our objective is to minimize the emission by optimizing both path and speed planning for heavy-duty trucks with multi-speed transmission and multiple injection strategies in the engine. This emission minimization problem, while pervasive in practice, has two challenges: i) the emission rate function is discontinuous and non-convex due to switching of the fuel injections and gear ratios, which makes the common practice of driving at a constant speed on a road segment not eco-friendly; ii) the problem is NP-hard due to the combinatorial nature of the simultaneous path and speed planning. We tackle the first challenge by considering the case where the truck can travel at a heterogeneous speed profile over a road segment and then formulate the speed planning problem as a convex problem. We further identify special structures in this problem and provide an efficient method for computing the optimal speed profile. We then tackle the second challenge by developing an efficient heuristic for both path planning and speed planning to solve the emission minimization problem on the scale of national highway systems. Our extensive simulations on the US highway system show that our solution reduces up to 46% NOx emission as compared to the commonly-adopted fastest path approach. We also find that optimizing heterogeneous speed profiles reduce up to 32% emission as compared to their homogeneous counterpart, thus are necessary to be considered in eco-friendly truck operations.

We consider the scenario where an energy harvesting source sends its updates to a receiver. The source optimizes its energy allocation over a decision period to maximize a sum of time-varying functions of the age of information (AoI), representing the value of providing timely information. In a practical online setting, we need to make irrevocable energy allocation decisions at each time while the time-varying functions and the energy arrivals are only revealed sequentially. The problem is then challenging as 1) we are facing uncertain energy harvesting arrivals and time-varying functions, and 2) the energy allocation decisions and the energy harvesting process are coupled due to the capacity-limited battery. In this paper, we develop an optimal online algorithm$\textsf {CR-RePursuit}$and show it achieves$(\ln \theta +1)$-competitiveness, where$\theta $is a parameter representing the level of uncertainty of the time-varying functions. It is the optimal competitive ratio among all deterministic and randomized online algorithms. We also introduce an adaptive variant of the algorithm, +, that further exploits the revealed information to obtain significantly improved empirical performance. We conduct simulations based on real-world traces and compare our algorithms with conceivable alternatives. The results show that our algorithms achieve 15% performance improvement as compared to the state-of-the-art baseline.

Limited data availability poses a major obstacle in training deep learning models for financial applications. Synthesizing financial time series to augment real-world data is challenging due to the irregular and scale-invariant patterns uniquely associated with financial time series - temporal dynamics that repeat with varying duration and magnitude. Such dynamics cannot be captured by existing approaches, which often assume regularity and uniformity in the underlying data. We develop a novel generative framework called FTS-Diffusion to model irregular and scale-invariant patterns that consists of three modules. First, we develop a scale-invariant pattern recognition algorithm to extract recurring patterns that vary in duration and magnitude. Second, we construct a diffusion-based generative network to synthesize segments of patterns. Third, we model the temporal transition of patterns in order to aggregate the generated segments. Extensive experiments show that FTS-Diffusion generates synthetic financial time series highly resembling observed data, outperforming state-of-the-art alternatives. Two downstream experiments demonstrate that augmenting real-world data with synthetic data generated by FTS-Diffusion reduces the error of stock market prediction by up to 17.9%. To the best of our knowledge, this is the first work on generating intricate time series with irregular and scale-invariant patterns, addressing data limitation issues in finance.

By employing neural networks (NN) to learn input-solution mappings and passing a new input through the learned mapping to obtain a solution instantly, recent studies have shown remarkable speed improvements over iterative algorithms for solving optimization problems. Meanwhile, they also highlight methodological challenges to be addressed. In particular, general non-convex problems often present multiple optimal solutions for identical inputs, signifying a complex, multi-valued input-solution mapping. Conventional learning techniques, primarily tailored to learn single-valued mappings, struggle to train NNs to accurately decipher multi-valued ones, leading to inferior solutions. We address this fundamental issue by developing a generative learning approach using a rectified flow (RectFlow) model built upon ordinary differential equations. In contrast to learning input-solution mapping, we learn the mapping from input to solution distribution, exploiting the universal approximation capability of the RectFlow model. Upon receiving a new input, we employ the trained RectFlow model to sample high-quality solutions from the input-dependent distribution it has learned. Our approach outperforms conceivable GAN and Diffusion models in terms of training stability and run-time complexity. We provide a detailed characterization of the optimality loss and runtime complexity associated with our generative approach. Simulation results for solving non-convex problems show that our method achieves significantly better solution optimality than recent NN schemes, with comparable feasibility and speedup performance.

Since its debut in 2016, ResNet has become arguably the most favorable architecture in deep neural network (DNN) design. It effectively addresses the gradient vanishing/exploding issue in DNN training, allowing engineers to fully unleash DNN's potential in tackling challenging problems in various domains. Despite its practical success, an essential theoretical question remains largely open: how well/best can ResNet approximate functions? In this paper, we answer this question for several important function classes, including polynomials and smooth functions. In particular, we show that ResNet with constant width can approximate Lipschitz continuous function with a Lipschitz constant $\mu$ using $\mathcal{O}(c(d)(\varepsilon/\mu)^{-d/2})$ tunable weights, where $c(d)$ is a constant depending on the input dimension $d$ and $\epsilon>0$ is the target approximation error. Further, we extend such a result to Lebesgue-integrable functions with the upper bound characterized by the modulus of continuity. These results indicate a factor of $d$ reduction in the number of tunable weights compared with the classical results for ReLU networks. Our results are also order-optimal in $\varepsilon$, thus achieving optimal approximation rate, as they match a generalized lower bound derived in this paper. This work adds to the theoretical justifications for ResNet's stellar practical performance.

We consider the scenario where an energy harvesting source sends its updates to a receiver. The source optimizes its energy allocation over a decision period to maximize a sum of time-varying functions of the age of information (AoI), representing the value of providing timely information. In a practical online setting, we need to make irrevocable energy allocation decisions at each time while the time-varying functions and the energy arrivals are only revealed sequentially. The problem is then challenging as 1) we are facing uncertain energy harvesting arrivals and time-varying functions, and 2) the energy allocation decisions and the energy harvesting process are coupled due to the capacity-limited battery. In this paper, we develop an optimal online algorithm CR-Reserve and show it achieves (lnθ + 1)-competitive, where θ is a parameter representing the level of uncertainty of the time-varying functions. It is the optimal competitive ratio among all deterministic and randomized online algorithms. We conduct simulations based on real-world traces and compare our algorithms with conceivable alternatives. The results show that our algorithms achieve 12% performance improvement as compared to the state-of-the-art baseline.

There has been growing interest in employing neural networks (NNs) to directly solve constrained optimization problems with low run-time complexity. However, it is non-trivial to ensure NN solutions strictly satisfy problem constraints due to inherent NN prediction errors. Existing feasibility-ensuring methods are either computationally expensive or lack performance guarantee. In this paper, we propose Homeomorphic Projection as a low-complexity scheme to guarantee NN solution feasibility for optimization over a general set homeomorphic to a unit ball, covering all compact convex sets and certain classes of non-convex sets. The idea is to (i) learn a minimum distortion homeomorphic mapping between the constraint set and a unit ball using a bi-Lipschitz invertible NN (INN), and then (ii) perform a simple bisection operation concerning the unit ball such that the INN-mapped final solution is feasible with respect to the constraint set with minor distortion-induced optimality loss. We prove the feasibility guarantee and bounded optimality loss under mild conditions. Simulation results, including those for non-convex AC-OPF problems in power grid operation, show that homeomorphic projection outperforms existing methods in solution feasibility and run-time complexity while achieving similar optimality loss.

There has been growing interest in employing neural network (NN) to directly solve constrained optimization problems with low run-time complexity. However, it is non-trivial to ensure NN solutions strictly satisfying problem constraints due to inherent NN prediction errors. Existing feasibility-ensuring methods either are computationally expensive or lack performance guarantee. In this paper, we propose homeomorphic projection as a low-complexity scheme to guarantee NN solution feasibility for optimization over a general set homeomorphic to a unit ball, covering all compact convex sets and certain classes of nonconvex sets. The idea is to (i) learn a minimum distortion homeomorphic mapping between the constraint set and a unit ball using an invertible NN (INN), and then (ii) perform a simple bisection operation concerning the unit ball so that the INN-mapped final solution is feasible with respect to the constraint set with minor distortion-induced optimality loss. We prove the feasibility guarantee and bound the optimality loss under mild conditions. Simulation results, including those for non-convex AC-OPF problems in power grid operation, show that homeomorphic projection outperforms existing methods in solution feasibility and run-time complexity, while achieving similar optimality loss.

We study a transportation problem where two heavy-duty trucks travel across the national highway from separate origins to destinations, subject to individual deadline constraints. Our objective is to minimize their total fuel consumption by jointly optimizing path planning, speed planning, and platooning configuration. Such a two-truck platooning problem is pervasive in practice yet challenging to solve due to hard deadline constraints and enormous platooning configurations to consider. We first leverage a unique problem structure to significantly simplify platooning optimization and present a novel formulation. We prove that the two-truck platooning problem is weakly NP-hard and admits a Fully Polynomial Time Approximation Scheme (FPTAS). The FPTAS can achieve a fuel consumption within a ratio of$(1+\epsilon)$to the optimal (for any$\epsilon >0$) with a time complexity polynomial in the size of the transportation network and$1/\epsilon $. These results are in sharp contrast to the general multi-truck platooning problem, which is known to be APX-hard and repels any FPTAS. As the FPTAS still incurs excessive running time for large-scale cases, we design an efficient dual-subgradient algorithm for solving large-/national- scale instances. It is an iterative algorithm that always converges. We prove that each iteration only incurs polynomial-time complexity, albeit it requires solving an integer linear programming problem optimally. We characterize a condition under which the algorithm generates an optimal solution and derive a posterior performance bound when the condition is not met. Extensive simulations based on real-world traces show that our joint solution of path planning, speed planning, and platooning saves up to 24% fuel as compared to baseline alternatives.

We study the problem of minimizing fuel consumption of a heavy-duty truck traveling across the national highway network subject to a hard deadline. We focus on a real-world setting that traversing a road segment is subject to variable speed ranges due to dynamic traffic conditions. The consideration of dynamic traffic conditions not only differentiates our work from existing ones but also allows us to leverage opportunistic driving to improve fuel efficiency. The idea is for the truck to strategically wait (e.g., at highway rest areas) for benign traffic conditions, so as to traverse subsequent road segments at favorable speeds for saving fuel. We observe that traffic conditions and thus speed ranges are mostly stationary within certain duration of the day, and we term them as phases. We formulate the fuel consumption minimization problem under phased speed ranges, considering path planning, speed planning, and opportunistic driving. We prove that the problem is NP-hard, and develop a dual-subgradient algorithm for large-/national- scale instances. We characterize conditions under which the algorithm generates an optimal solution. We carry out simulations based on real-world traces over the US highway system. The results show that our scheme saves up to 20% fuel than a shortest-path based alternative, of which opportunistic driving contributes 13%. Meanwhile, opportunistic driving also reduces driving time by 6% as compared to only optimizing path planning and speed planning. As such, it offers a desirable design option to simultaneously reduce fuel consumption and hours of driving. Last but not least, our results highlight a perhaps surprising observation that dynamic traffic conditions can be exploited to achieve fuel savings even larger than those under stationary traffic conditions.

We consider an increasingly popular demand-response scenario where a home user schedules the flexible electric vehicle (EV) charging load in response to real-time electricity prices. The objective is to minimize the total charging cost with user dissatisfaction taken into account. We focus on the online setting where neither accurate prediction nor distribution of future real-time prices is available to the user when making irrevocable charging decisions in each time slot. The emphasis on considering user dissatisfaction and achieving optimal competitive ratio differentiates our work from existing ones and makes our study uniquely challenging. Our key contribution is two simple online algorithms with the optimal competitive ratio among all deterministic algorithms. The optimal competitive ratio is upper-bounded by$\min \left \{{ \sqrt {\alpha /p_{\min }},p_{\max }/p_{\min }}\right \} $and the bound is asymptotically tight with respect to$\alpha $, where$p_{\max }$and$p_{\min }$are the upper and lower bounds of real-time prices and$\alpha \geq p_{\min }$captures the consideration of user dissatisfaction. The bounds with respect to small and large values of$\alpha $suggest the fundamental difference of the problems with and without considering user dissatisfaction. We also extend the algorithms to take minimum charging requirement and short-term prediction into account. Simulation results based on real-world traces corroborate our theoretical findings and show that the empirical performance of our algorithms can be substantially better than the theoretical worst-case guarantees. Our algorithms also achieve notable performance gains under diverse settings as compared to conceivable alternatives.

We consider a single-unicast networking scenario where a sender periodically sends a batch of data to a receiver over a multi-hop network, possibly using multiple paths. We study problems of minimizing peak/average Age-of-Information (AoI) subject to throughput requirements based on a stylized deterministic model in this scenario. The consideration of batch generation and multi-path communication differentiates ourAoIstudy from existing ones. We first show that ourAoIminimization problems are NP-hard, but only in the weak sense, as we develop an optimal algorithm with a pseudo-polynomial time complexity. We then prove that minimizingAoIand minimizing maximum delay are “roughly” equivalent, in the sense that any optimal solution of the latter is an approximate solution of the former with bounded optimality loss. We leverage this understanding to design a general approximation framework for our problems. It can build upon any$\alpha $-approximation algorithm of the maximum delay minimization problem to construct an$(\alpha +\mathsf {c})$-approximate solution for minimizingAoI. Here$\mathsf {c}$is a constant depending on the throughput requirements. Furthermore, we show that our results can be extended to the multiple-unicast setting. Simulations over various network topologies validate the effectiveness of our approach. Our results make a major advance to optimizingAoIin multi-path communication, and hence can be of broad interest to the networking research community.

The papers in this special section focus on the intersection of computing and communication technologies with energy systems. Computing and communication technologies impact energy systems in two distinct ways. The exponential growth of these technologies has made them large energy consumers. Therefore, new architectures, technologies and systems are being developed and deployed to make computing and networked systems more energy efficient. Additionally, these technologies will play a central role in the ongoing transformation of our energy systems. They help measure, monitor and control energy resources, inform and shape human demand, and determine how utilities, generators, regulators, and consumers interact. Recently, there have been vibrant developments in the research community at the intersection of computing and communication technologies with energy systems. Diverse applications of computing and networked systems have made legacy systems more energy-efficient, as well as improved the design, analysis, and development of innovative new energy systems.

We consider the scenario where a sender streams a flow at a fixed rate to a receiver across a multi-hop network, possibly using multiple paths. Data transmission over a link incurs a cost and a delay, both of which are traffic-dependent. We study the problem of minimizing network transmission cost subject to a maximum delay constraint and a throughput requirement. The problem is important for leveraging edge-cloud computing platforms to support computationally intensive IoT applications, which are sensitive to three critical performance metrics, i.e., cost, maximum delay, and throughput. Our problem jointly considers the three metrics, while existing ones only account for one or two of them. We first show that our problem is uniquely challenging, as (i) it is NP-complete even to find a feasible solution satisfying all constraints, and (ii) directly extending existing solutions to our problem results in problem-dependent maximum delay violations that can be unbounded. We then design both an approximation algorithm and an efficient heuristic. For any feasible instance, our approximation algorithm will achieve a cost no worse than the optimal, while violating the maximum delay constraint and the throughput requirement only by constant ratios. Meanwhile, our heuristic will construct feasible solutions for a large portion (over 60% empirically) of feasible instances, strictly satisfying the maximum delay constraint and the throughput requirement. We further characterize a condition under which the cost of our heuristic must be within a problem-dependent-ratio gap to the optimal. We simulate representative edge computing platforms, and observe that (i) when sacrificing 3% throughput, our approximation algorithm reduces 32% cost as compared to a greedy baseline, and satisfies the maximum delay constraint for 56% simulated instances; (ii) our heuristic solves 62% of feasible instances, and reduces 24% cost as compared to the baseline while strictly satisfying all constraints.

Driving while distracted or losing alertness significantly increases the risk of traffic accident. The emerging Internet of Things (IoT) systems for smart driving hold the promise of significantly reducing road accidents. In particular, detecting unsafe hand motions and warning the driver using smart sensors can improve the driver’s alertness and skill. However, due to the impact of the vehicle’s movement and the significant variation across different driving environments, detecting the position of the driver’s hand is challenging. This article presents SafeWatch—a system based on smartwatches and smartphones that detects the driver’s unsafe behaviors in a real-time manner. SafeWatch infers driver’s hand position based on several important features, such as the posture of the driver’s forearm and the vibration on the smartwatch. SafeWatch employs a novel adaptive training algorithm that keeps updating the training data set at run-time based on inferred hand positions in certain driving conditions. The evaluation with 75 real driving trips from six subjects shows that SafeWatch has a high accuracy over 97.0% for both recall and precision in detection of the unsafe hand positions when the condition lasts for more than 6.0 s , as well as over 97.1% recall and over 91.0% precision in detection of the unsafe hand movements when it lasts for more than 2.5 s . The relative position of the hand to the steering wheel also reveals some detailed driving habits, like the type of steering method.

We consider a common truck operation scenario, where a long-haul heavy-duty truck drives across a national highway system to fulfill multiple geographically-dispersed tasks in a specific order. The objective is to minimize the total fuel consumption subject to the pickup and delivery time window constraints of individual tasks, by jointly optimizing task execution times, path planning, and speed planning. The need to coordinate execution times for multiple tasks differentiates our study from existing ones on single task. We first prove that our problem is NP-hard. Moreover, it is uniquely challenging to solve our problem, as we further show that optimizing task execution times is a non-convex puzzle. We then exploit the problem structure to develop (i) a Fully-Polynomial-Time Approximation Scheme (FPTAS), and (ii) a fast and efficient heuristic algorithm, called SPEED (Sub-gradient-based Price-driven Energy-Efficient Delivery). We characterize sufficient conditions under which SPEED generates an optimal solution, and derive an optimality gap for SPEED when the conditions are not satisfied. We evaluate the practical performances of our solutions using real-world traces over the US national highway. We observe that our solutions can save up to 22% fuel as compared to the fastest-/shortest- path baselines, and up to 10% fuel than a conceivable alternative generalized from the state-of-the-art single-task algorithm. The fuel saving is robust to the number of tasks to be fulfilled. Simulations also show that our algorithms always obtain close-to-optimal solutions and meet time window constraints for all feasible problem instances. In comparison, the conceivable alternative fails to meet time window constraints for up to 45% of the instances.

We consider a single-unicast networking scenario where a sender streams a flow at a fixed rate to a receiver across a multi-hop network, possibly using multiple paths. Transmission over a link incurs a traffic-dependent link delay. We optimize network delay concerning two popular metrics, namely maximum delay and average delay. Well-known pessimistic results state that a flow cannot simultaneously achieve a maximum delay and an average delay both within bounded-ratio gaps to optimal. Instead, we pose an optimistic note on the fundamental compatibility of the two delay metrics. Specifically, we design two polynomial-time solutions each of which can deliver (1 - ϵ)-fraction of the flow with maximum delay and average delay simultaneously within (1/ϵ)-ratio gap to optimal, for any ϵ ∈ (0, 1). We prove that the ratio (1/ϵ) is at least near-tight. Moreover, our solutions can be extended to the multiple-unicast setting. In this setting, the two delay metrics of our solutions are both within a boundedratio gap of (R/(Rmin · ϵ)) to optimal, where R (resp. Rmin) is the aggregate (resp. minimum) flow rate requirement of all sender-receiver pairs. Hence we pose a similar optimistic note. Simulations based on real-world continent-scale network topology show that the empirical delay gaps observed under practical settings can be much smaller than their theoretical counterparts. In addition, our solutions can achieve over 10% reduction on the maximum delay and average delay simultaneously, only in the cost of losing 3% traffic, as compared to a conceivable delay-aware baseline without traffic loss. Our results can be of particular interest to delay-centric networking applications that can tolerate a small fraction of traffic loss, including cloud video conferencing that recently attracts substantial attention.

We consider a multi-path routing problem of maximizing the aggregate user utility over a multi-hop network, subject to link capacity constraints, maximum end-to-end delay constraints, and user throughput requirements. A user's utility is a concave function of the achieved throughput or the experienced maximum delay. The problem is important for supporting real-time multimedia traffic and is uniquely challenging due to the need of simultaneously considering maximum delay constraints and throughput requirements. In this paper, we first show that it is NP-complete either (i) to construct a feasible solution strictly meeting all constraints, or (ii) to obtain an optimal solution after relaxing either the maximum delay constraints or the throughput requirements. We then develop a polynomial-time approximation algorithm named PASS. The design of PASS leverages a novel understanding between non-convex maximum-delay-aware problems and their convex average-delay-aware counterparts, which can be of independent interest and suggests a new avenue for solving maximum-delay-aware network optimization problems. We prove that PASS always obtains approximate solutions (i.e., with theoretical performance guarantees), at the cost of violating both the maximum delay constraints and the throughput requirements by up to constant ratios. We also develop two variants of PASS, named PASS-M and PASS-T, to generate approximate solutions at the cost of violating either the maximum delay constraints or the throughput requirements by up to problem-dependent ratios. We evaluate our solutions using extensive simulations on Amazon EC2 datacenters supporting video-conferencing traffic. Compared to the existing algorithms and a conceivable baseline, our solutions obtain up to 100% improvement of utilities, by meeting the throughput requirements but relaxing the maximum delay constraints to the extent acceptable for practical video conferencing applications.

Mobile Instant Messaging (IM) apps, such as WhatsApp and WeChat, frequently send heartbeat messages to remote servers to maintain their always-online status. Periodic heartbeat messages are small in size, but their transmissions incur heavy signaling traffic due to frequently establishing and releasing communication channels between Base Stations (BSs) and smartphones, known as the signaling storm. Meanwhile, smartphones also need to activate the cellular data communication module frequently for transmitting short heartbeat messages, resulting in substantial energy consumption. To address these issues, we present eDirect, an energy-efficient D2D-assIsted Relaying framEwork for Cellular signaling reducTion. eDirect selects active smartphones as relays to opportunistically collect heartbeat messages from nearby smartphones using energy-efficient D2D communication. The collected heartbeat messages are transmitted to the BS in an aggregated manner to reduce cellular signaling traffic. Based on the beating frequencies and deadlines of the collected heartbeat messages, eDirect schedules transmissions of the collected heartbeat messages to minimize signaling overhead and energy consumption while meeting the deadline constraints. We implement and evaluate our solution on Android smartphones. The results from real-world experiments show that our solution reduces signaling traffic by at least 50% and energy consumption by up to 36%.

We consider an increasingly popular demand-response scenario where a user schedules the flexible electric vehicle (EV) charging load in response to real-time electricity prices. The objective is to minimize the total charging cost with user dissatisfaction taken into account. We focus on the online setting where neither accurate prediction nor distribution of future real-time prices is available to the user when making irrevocable charging decision in each time slot. The emphasis on considering user dissatisfaction and achieving optimal competitive ratio differentiates our work from existing ones and makes our study uniquely challenging. Our key contribution is two simple online algorithms with the best possible competitive ratio among all deterministic algorithms. The optimal competitive ratio is upper-bounded by min {√α/pmin, pmax/pmin} and the bound is asymptotically tight with respect to α, where pmaxand pminare the upper and lower bounds of real-time prices and α ≥ pmincaptures the consideration of user dissatisfaction. The bounds under small and large values of α suggest the fundamental difference of the problems with and without considering user dissatisfaction. Simulation results based on real-world traces corroborate our theoretical findings and show that the empirical performance of our algorithms can be substantially better than its theoretical worst-case guarantee. Moreover, our algorithms achieve large performance gains as compared to conceivable alternatives. The results also suggest that increasing EV charging rate limit decreases overall cost almost linearly.

Ride-sharing is a modern urban-mobility paradigm with tremendous potential in reducing congestion and pollution. Demand-aware design is a promising avenue for addressing a critical challenge in ridesharing systems, namely joint optimization of request-vehicle assignment and routing for a fleet of vehicles. In this paper, we develop a probabilistic demand-aware framework to tackle the challenge. We focus on maximizing the expected number of passenger pickups, given the probability distributions of future demands. The key idea of our approach is to assign requests to vehicles in a probabilistic manner. It differentiates our work from existing ones and allows us to explore a richer design space to tackle the request-vehicle assignment puzzle with a performance guarantee but still keeping the final solution practically implementable. The optimization problem is non-convex, combinatorial, and NP-hard in nature. As a key contribution, we explore the problem structure and propose an elegant approximation of the objective function to develop a dual-subgradient heuristic. We characterize a condition under which the heuristic generates a (1 -- 1/e) approximation solution. Our solution is simple and scalable, amendable for practical implementation. Results of numerical experiments based on real-world traces in Manhattan show that, as compared to a conventional demand-oblivious scheme, our demand-aware solution improves the passenger pickups by up to 46%. The results also show that joint optimization at the fleet level leads to 19% more pickups than that by separate optimizations at individual vehicles.

We consider the scenario where a sender periodically sends a batch of data to a receiver over a multi-hop network, possibly using multiple paths. Our objective is to minimize peak/average Age-of-Information (AoI) subject to throughput requirements. The consideration of batch generation and multi-path communication differentiates our AoI study from existing ones. We first show that our AoI minimization problems are NP-hard, but only in the weak sense, as we develop an optimal algorithm with a pseudo-polynomial time complexity. We then prove that minimizing AoI and minimizing maximum delay are "roughly" equivalent, in the sense that any optimal solution of the latter is an approximate solution of the former with bounded optimality loss. We leverage this understanding to design a general approximation framework for our problems. It can build upon any α-approximation algorithm of the maximum delay minimization problem, e.g., the algorithm in [13] with α = 1 + ϵ given any user-defined ϵ > 0, to construct an (α + c)-approximate solution for minimizing AoI. Here c is a constant depending on the throughput requirements. Simulations over various network topologies validate the effectiveness of our approach.

We consider a multiple-unicast network flow problem of maximizing aggregate user utilities under link capacity constraints, maximum delay constraints, and user throughput requirements. A user's utility is a concave function of the achieved throughput or the experienced maximum delay. We first prove that it is NP-complete either (i) to construct a feasible solution meeting all constraints, or (ii) to obtain an optimal solution after we relax maximum delay constraints or throughput requirements. We then leverage a novel understanding between nonconvex maximum-delay-aware problems and their convex average-delay-aware counterparts, and design a polynomial-time approximation algorithm named PASS. PASS achieves constant or problem-dependent approximation ratios, at the cost of violating maximum delay constraints or throughput requirements by up to constant or problem-dependent ratios, under realistic conditions. We empirically evaluate our solutions using simulations of supporting video-conferencing traffic across Amazon EC2 datacenters. Compared to conceivable baselines, PASS obtains up to 100% improvement of utilities, meeting throughput requirements but relaxing maximum delay constraints that are acceptable for video conferencing applications.

Small-cell architecture is widely adopted by cellular network operators to increase spectral spatial efficiency. However, this approach suffers from low spectrum temporal efficiency. When a cell becomes smaller and covers fewer users, its total traffic fluctuates significantly due to insufficient traffic aggregation and exhibits a large “peak-to-mean” ratio. As operators customarily provision spectrum for peak traffic, large traffic temporal fluctuation inevitably leads to low spectrum temporal efficiency. To address this issue, in this paper, we advocate device-to-device (D2D) load-balancing as a useful mechanism. The idea is to shift traffic from a congested cell to its adjacent under-utilized cells by leveraging inter-cell D2D communication, so that the traffic can be served without using extra spectrum, effectively improving the spectrum temporal efficiency. We provide theoretical modeling and analysis to characterize the benefit of D2D load balancing, in terms of total spectrum requirements and the corresponding cost, in terms of incurred D2D traffic overhead. We carry out empirical evaluations based on real-world 4G data traces and show that D2D load balancing can reduce the spectrum requirement by 25% as compared to the standard scenario without D2D load balancing, at the expense of negligible 0.7% D2D traffic overhead.

We consider the problem of exploring travel demand statistics to optimize ride-sharing routing, in which the driver of a vehicle determines a route to transport multiple customers with similar itineraries and schedules in a cost-effective and timely manner. This problem is important for unleashing economical and societal benefits of ride-sharing. Meanwhile, it is challenging due to the need of (i) meeting travel delay requirements of customers, and (ii) making online decisions without knowing the exact travel demands beforehand. We present a general framework for exploring the new design space enabled by the demand-aware approach. We show that the demand-aware ride-sharing routing is fundamentally a two-stage stochastic optimization problem. We show that the problem is NP-Complete in the weak sense. We exploit the two-stage structure to design an optimal solution with pseudo-polynomial time complexity, which makes it amenable for practical implementation. We carry out extensive simulations based on real-world travel demand traces of Manhattan. The results show that using our demand-aware solution instead of the conventional greedy-routing scheme increases the driver's revenue by 10%. The results further show that as compared to the case without ride-sharing, our ride-sharing solution reduces the customers' payment by 9% and the total vehicle travel time (indicator of greenhouse gas emission) by 17%. The driver can also get 26% extra revenues per slot by participating in ride-sharing.

We consider the scenario where a source streams a flow at fixed rate to a receiver across a network, possibly using multiple paths. Transmission over a link incurs a delay modeled as a non-negative, non-decreasing and differentiable function of the link aggregated transmission rate. This setting models various practical network communication scenarios. We study network delay optimization concerning two popular metrics, namely maximum delay and average delay experienced by the flow. A well-known pessimistic result says that a flow cannot simultaneously achieve optimal maximum delay and optimal average delay, or even within constant-ratio gaps to the two optimums. In this paper, we pose an optimistic note on the fundamental compatibility of the two delay metrics. Specifically, we design two polynomial-time solutions to deliver (1 -ε) fraction of the flow with maximum delay and average delay simultaneously within 1/ε to the optimums for any ε ∈ (0,1). Hence, the two delay metrics are “largely” compatible. The ratio 1/ε is independent to the network size and link delay function, and we show that it is tight or near-tight. Simulations based on real-world continent-scale network topology verify our theoretical findings. Note that the proposed delay gap 1/ε, upon sacrificing ε fraction of the flow rate, is guaranteed even under the worst theoretical case setting. Our simulation results show that the empirical delay gaps observed under practical settings can be much smaller than 1/ε. Our results are of particular interest to delay-centric networking applications that can tolerate a small fraction of traffic loss, including cloud video conferencing that recently attracts substantial attention.

The uncertainty and variability of renewable generation pose significant challenges to reliable power-grid operations. This paper designs robust online strategies for jointly operating energy storage units and fossil-fuel generators to achieve provably reliable grid operations at all times under high renewable uncertainty, without the need of renewable curtailment. In particular, we jointly consider two power system operations, namely day-ahead reliability assessment commitment (RAC) and real-time dispatch. We first extend the concept of “safe-dispatch sets” to our setting. While finding such safe-dispatch sets and checking their non-emptiness provide crucial answers to both RAC and real-time dispatch, their computation incurs high complexity in general. To develop computationally-efficient solutions, we first study a single-bus case with one generator-storage pair, where we derive necessary conditions and sufficient conditions for the safe-dispatch sets. Our results reveal fundamental trade-offs between storage capacity and generator ramp-up/-down limits to ensure grid reliability. Then, for the more general multi-bus scenario, we split the net-demand among virtual generator-storage pairs (VGSPs) and apply our single-bus decision strategy to each VGSP. Simulation results on an IEEE 30-bus system show that, compared with state-of-art solutions, our scheme requires significantly less storage to ensure reliable grid operation without any renewable curtailment.

We consider a timely transportation problem where a heavy-duty truck travels between two locations across the national highway system, subject to a hard deadline constraint. Our objective is to minimize the total fuel consumption of the truck, by optimizing both route planning and speed planning. The problem is important for cost-effective and environment-friendly truck operation, and it is uniquely challenging due to its combinatorial nature as well as the need of considering hard deadline constraint. We first show that the problem is NP-complete; thus exact solution is computational prohibited unless P = NP. We then design a fully polynomial time approximation scheme (FPTAS) to solve it. While achieving highly-preferred theoretical performance guarantee, the proposed FPTAS still suffers from long running time when applying to national-wide highway systems with tens of thousands of nodes and edges. Leveraging elegant insights from studying the dual of the original problem, we design a heuristic with much lower complexity. The proposed heuristic allows us to tackle the energy-efficient timely transportation problem on large-scale national highway systems. We further characterize a condition under which our heuristic generates an optimal solution. We observe that the condition holds in most of practical instances in numerical experiments, justifying the superior empirical performance of our heuristic. We carry out extensive numerical experiments using real-world truck data over the actual U.S. highway network. The results show that our proposed solutions achieve 17% (resp. 14%) fuel consumption reduction, as compared with a fastest path (resp. shortest path) algorithm adapted from common practice.

Mobile Instant Messaging (IM) apps, such as WhatsApp and WeChat, frequently send heartbeat messages to remote servers to maintain always-online status. Periodic heartbeat messages are small in size, but their transmissions incur heavy signaling traffic to frequently establish and release communication channels between base stations and smartphones, known as signaling storm. Meanwhile, smartphones also need to activate cellular data communication module frequently for transmitting short heartbeat messages, resulting in substantial energy consumption. To address these issues, we propose a Device-to-Device (D2D) based heartbeat relaying framework, in order to reduce signaling traffic and energy consumption in heartbeat transmission. The framework selects the smartphones as relays to opportunistically collect heartbeat messages from nearby smartphones using energy-efficient D2D communication. The collected heartbeat messages are transmitted to the BS in an aggregated manner to reduce cellular signaling traffic. Based on the periods and the expiration time of the collected heartbeat messages, the framework schedules the transmissions of collected heartbeat messages to minimize signaling and energy consumption while satisfying time constrains. We implement and evaluate our solution on Android smartphones. The results from real-world experiments show that our solution achieves more than 50% signaling traffic reduction and up to 36% energy saving.

Today's internet has witnessed a fast growth of mobile video streaming. Different from traditional PC/laptop-based video streaming, mobile video streaming relies on the usage of mobile devices and wireless networks, allowing people to receive video content on the move. The change has challenged traditional video content delivery, which uses centralized infrastructure (e.g., CDN) inside the network for content distribution, in a sense that mobile users (connected to Wi-Fi or cellular networks) encounter large delay and small download speed. One promising solution is to prefetch content in the edge of the network, e.g., on access points (APs). However, it faces the great challenges: 1) It is difficult to prefetch content in such edge APs with limited storage capacity; 2) Users' mobility cross APs affects the content delivery; 3) Popularity of content may change significantly across APs. Previous approaches make mobile video content delivery inefficient without jointly considering these problems. In this paper, we propose an AP-assisted mobile video delivery framework to solve these problems. First, using large-scale measurement studies of users' trajectories and preferences of videos, we reveal that both users' mobility patterns and their intrinsic preferences are important for AP-assisted content delivery. Second, we formulate the AP content prefetching as an optimization problem, and develop an online solution, APRank, to solve it. Third, we evaluate the effectiveness of our design, compared with four baselines, random-based, popularity-based, preference-based and offline prefetching.

We consider the scenario where a cloud service provider (CSP) operates multiple geo-distributed datacenters to provide Internet-scale service. Our objective is to minimize the total electricity and bandwidth cost by jointly optimizing electricity procurement from wholesale markets and geographical load balancing (GLB), i.e., dynamically routing workloads to locations with cheaper electricity. Under the ideal setting where exact values of market prices and workloads are given, this problem reduces to a simple LP and is easy to solve. However, under the realistic setting where only distributions of these variables are available, the problem unfolds into a non-convex infinite-dimensional one and is challenging to solve. Our main contribution is to develop an algorithm that is proven to solve the challenging problem optimally and efficiently, by exploring the full design space of strategic bidding. Trace-driven evaluations corroborate our theoretical results, demonstrate fast convergence of our algorithm, and show that it can reduce the cost for the CSP by up to 20% as compared to baseline alternatives. Our study highlights the intriguing role of uncertainty. While variability in workloads deteriorates the cost-saving performance of joint electricity procurement and GLB, counter-intuitively, variability in market prices can be exploited to achieve a cost reduction even larger than the setting without price variability.

We study a delay-sensitive information flow problem where a source streams information to a sink over a directed graph G = (V, E) at a fixed rate R possibly using multiple paths to minimize the maximum end-to-end delay, denoted as the Min-Max-Delay problem. Transmission over an edge incurs a constant delay within the capacity. We prove that Min-Max-Delay is weakly NP-complete, and demonstrate that it becomes strongly NP-complete if we require integer flow solution. We propose an optimal pseudo-polynomial time algorithm for Min-Max-Delay, with time complexity O(log(Ndmax)(N5dmax2.5)(log R + N2dmaxlog(N2dmax))), where N =△max{|V|, |E|} and dmaxis the maximum edge delay. Besides, we show that the integrality gap, which is defined as the ratio of the maximum delay of an optimal integer flow to the maximum delay of an optimal fractional flow, could be arbitrarily large.

We investigate the problem of stochastic network optimization in the presence of imperfect state prediction and non-stationarity. Based on a novel distribution-accuracy curve prediction model, we develop the predictive learning-aided control (PLC) algorithm, which jointly utilizes historic and predicted network state information for decision making. PLC is an online algorithm that requires zero a-prior system statistical information, and consists of three key components, namely sequential distribution estimation and change detection, dual learning, and online queue-based control.

The device-to-device load balancing (D2D-LB) paradigm has been advocated in recent small-cell architecture design for cellular networks. The idea is to exploit inter-cell D2D communication and dynamically relay traffic of a busy cell to adjacent under-utilized cells to improve spectrum temporal efficiency, addressing a fundamental drawback of small-cell architecture. Technical challenges of D2D-LB have been studied in previous works. The potential of D2D-LB, however, cannot be fully realized without providing proper incentive mechanism for device participation. In this paper, we address this economical challenge using an online procurement auction framework. In our design, multiple sellers (devices) submit bids to participate in D2D-LB and the auctioneer (cellular service provider) evaluates all the bids and decides to purchase a subset of them to fulfill load balancing requirement with the minimum social cost. Different from similar auction design studies for cellular offloading, battery limit of relaying devices imposes a time-coupled capacity constraint that turns the underlying problem into a challenging multi-slot one. Furthermore, the dynamics in the input to the multi-slot auction problem emphasize the need for online algorithm design. We first tackle the single-slot version of the problem, show that it is NP-hard, and design a polynomial-time offline algorithm with a small approximation ratio. Building upon the single-slot results, we design an online algorithm for the multi-slot problem with sound competitive ratio. Our auction algorithm design ensures that truthful bidding is a dominant strategy for devices. Extensive experiments using real-world traces demonstrate that our proposed solution achieves near offline-optimum and reduces the cost by 45% compared with an alternative heuristic.

Today's Internet has witnessed an increase in the popularity of mobile video streaming, which is expected to exceed 3/4 of the global mobile data traffic by 2019. To satisfy the considerable amount of mobile video requests, video service providers have been pushing their content delivery infrastructure to edge networks-from regional content delivery network (CDN) servers to peer CDN servers (e.g., smartrouters in users' homes)-to cache content and serve users with storage and network resources nearby. Among the edge network content caching paradigms, Wi-Fi access point caching and cellular base station caching have become two mainstream solutions. Thus, understanding the effectiveness and performance of these solutions for large-scale mobile video delivery is important. However, the characteristics and request patterns of mobile video streaming are unclear in practical wireless network. In this paper, we use real-world data sets containing 50 million trace items of nearly 2 million users viewing more than 0.3 million unique videos using mobile devices in a metropolis in China over two weeks, not only to understand the request patterns and user behaviors in mobile video streaming, but also to evaluate the effectiveness of Wi-Fi and cellular-based edge content caching solutions. To understand the performance of edge content caching for mobile video streaming, we first present temporal and spatial video request patterns, and we analyze their impacts on caching performance using frequency-domain and entropy analysis approaches. We then study the behaviors of mobile video users, including their mobility and geographical migration behaviors, which determine the request patterns. Using trace-driven experiments, we compare strategies for edge content caching, including least recently used (LRU) and least frequently used (LFU), in terms of supporting mobile video requests. We reveal that content, location, and mobility factors all affect edge content caching performance. Moreover, we design an efficient caching strategy based on the measurement insights and experimentally evaluate its performance. The results show that our design significantly improves the cache hit rate by up to 30% compared with LRU/LFU.

It is a promising vision to exploit white spaces , that is, vacant VHF and UHF TV channels, to meet the rapidly growing demand for wireless data services in both outdoor and indoor scenarios. While most prior works have focused on outdoor white space, the indoor story is largely open for investigation. Motivated by this observation and discovering that 70% of the spectrum demand comes from indoor environment, we carry out a comprehensive study to explore indoor white spaces. We first conduct a large-scale measurement study and compare outdoor and indoor TV spectrum occupancy at 30+ diverse locations in a typical metropolis—Hong Kong. Our results show that abundant white spaces are available in different areas in Hong Kong, which account for more than 50% and 70% of the entire TV spectrum in outdoor and indoor scenarios, respectively. Although there are substantially more white spaces indoors than outdoors, there have been very few solutions for identifying indoor white space. To fill in this gap, we develop the first data-driven, low-cost indoor white space identification system for White-space Indoor Spectrum EnhanceR (WISER), to allow secondary users to identify white spaces for communication without sensing the spectrum themselves. We design the architecture and algorithms to address the inherent challenges. We build a WISER prototype and carry out real-world experiments to evaluate its performance. Our results show that WISER can identify 30%--40% more indoor white spaces with negligible false alarms, as compared to alternative baseline approaches.

This paper considers network communications under a hard timeliness constraint, where a source node streams perishable information to a destination node over a directed acyclic graph subject to a hard delay constraint. Transmission along any edge incurs unit delay, and it is required that every information bit generated at the source at the beginning of time t to be received and recovered by the destination at the end of time t + D - 1, where D > 0 is the maximum allowed end-to-end delay. We study the corresponding delay-constrained unicast capacity problem. This paper presents the first example showing that network coding (NC) can achieve strictly higher delay-constrained throughput than routing even for the single unicast setting and the NC gain can be arbitrarily close to 2 in some instances. This is in sharp contrast to the delay-unconstrained (D = ∞) single-unicast case where the classic min-cut/max-flow theorem implies that coding cannot improve throughput over routing. Motivated by the above findings, a series of investigation on the delay-constrained capacity problem is also made, including: 1) an equivalent multiple-unicast representation based on a time-expanded graph approach; 2) a new delay-constrained capacity upper bound and its connections to the existing routing-based results [Ying et al. 2011]; 3) an example showing that the penalty of using random linear NC can be unbounded; and 4) a counter example of the tree-packing Edmonds' theorem in the new delay-constrained setting. Built upon the time-expanded graph approach, we also discuss how our results can be readily extended to cyclic networks. Overall, our results suggest that delay-constrained communication is fundamentally different from the well-understood delay-unconstrained one and call for investigation participation.

Multiparty cloud video conferencing architecture has been recently advocated to exploit rich computing and bandwidth resources in the cloud to effectively improve video conferencing performance. As a typical design in this architecture, multiple agents, i.e., virtual machines, are deployed in different cloud sites, and users are assigned to the agents. Then, the users communicate through the agents, and the agents might transcode the recorded videos given the heterogeneities among devices in terms of hardware specification and connectivity. In this architecture, two critical and nontrivial challenges are: 1) assigning users to agents to reduce the operational cost and the user-to-user conferencing delay and 2) identifying best agents to perform transcoding tasks, taking into account the heterogeneous bandwidth and processing availabilities. To address these challenges, we cast a joint problem of user-to-agent assignment and transcoding-agent selection. The ultimate objective is to simultaneously minimize the cost of the service provider and the conferencing delay. The problem is combinatorial in nature, which belongs to the NP-hard node assignment problems. We leverage the Markov approximation framework and devise an adaptive parallel algorithm that finds a close-to-optimal solution to our problem with a bounded performance guarantee. To evaluate the performance of our solution, we implement a prototype video conferencing system and carry out trace-driven experiments. In a set of largescale experiments using PlanetLab traces, our solution decreases the operational cost by 77% and simultaneously yields lower conferencing delay compared with an existing alternative.

Most existing wireless networking solutions are best-effort and do not provide any delay guarantee required by important applications, such as mobile multimedia conferencing and real-time control of cyber-physical systems. Recently, Hou and Kumar provided a novel framework for analyzing and designing delay-guaranteed wireless networking solutions. While inspiring, their idle-time-based analysis applies only to flows with a special traffic pattern called the frame-synchronized setting. The problem remains largely open for general traffic patterns. This paper addresses this challenge by proposing a general framework that characterizes and achieves the complete delay-constrained capacity region with general traffic patterns in single-hop downlink access-point wireless networks. We first show that the timely wireless flow problem is fundamentally an infinite-horizon Markov decision process (MDP). Then, we judiciously combine different simplification methods to prove that the timely capacity region can be characterized by a finite-size convex polygon. This for the first time allows us to characterize the timely capacity region of wireless flows with general traffic patterns. We then design three scheduling policies to optimize network utility and/or support feasible timely throughput vectors for general traffic patterns. The first policy achieves the optimal network utility and supports any feasible timely throughput vector but suffers from the curse of dimensionality. The second and third policies are inspired by our MDP framework and are of much lower complexity. Simulation results show that both achieve near-optimal performance and outperform other existing alternatives.

In online service systems, the delay experienced by users from service request to service completion is one of the most critical performance metrics. To improve user delay experience, recent industrial practices suggest a modern system design mechanism: proactive serving, where the service system predicts future user requests and allocates its capacity to serve these upcoming requests proactively. This approach complements the conventional mechanism of capability boosting. In this paper, we propose queuing models for online service systems with proactive serving capability and characterize the user delay reduction by proactive serving. In particular, we show that proactive serving decreases average delay exponentially (as a function of the prediction window size) in the cases where service time follows light-tailed distributions. Furthermore, the exponential decrease in user delay is robust against prediction errors (in terms of miss detection and false alarm) and user demand fluctuation. Compared with the conventional mechanism of capability boosting, proactive serving is more effective in decreasing delay when the system is in the light-load regime. Our trace-driven evaluations demonstrate the practical power of proactive serving: for example, for the data trace of light-tailed YouTube videos, the average user delay decreases by 50% when the system predicts 60 s ahead. Our results provide, from a queuing-theoretical perspective, justifications for the practical application of proactive serving in online service systems.

Most existing wireless networking solutions are best-effort and do not provide any delay guarantee required by important applications such as the control traffic of cyber-physical systems. Recently, Hou and Kumar provided the first framework for analyzing and designing delay-guaranteed network solutions. While inspiring, their idle-time-based analysis appears to apply only to flows with a special traffic (arrival and expiration) pattern, and the problem remains largely open for general traffic patterns. This paper addresses this challenge by proposing a new framework that characterizes and achieves the complete delay-constrained capacity region with general traffic patterns in single-hop downlink access-point wireless networks. We first formulate the timely capacity problem as an infinite-horizon Markov Decision Process (MDP) and then judiciously combine different simplification methods to convert it to an equivalent finite-size linear program (LP). This allows us to characterize the timely capacity region of flows with general traffic patterns for the first time in the literature. We then design three timely-flow scheduling algorithms for general traffic patterns. The first algorithm achieves the optimal utility but suffers from the curse of dimensionality. The second and third algorithms are inspired by our MDP framework and are of polynomial-time complexity. Simulation results show that both achieve near-optimal performance and outperform other existing alternatives.

In this paper, we are interested in online multistage decisions to ensure robust power grid operations under high renewable uncertainty. We jointly consider both the reliability assessment commitment (RAC) and the real-time dispatch problems. We first focus on the real-time dispatch problem and define “maximally robust algorithms,” which can provably ensure grid safety whenever there exists any other algorithm that can ensure grid safety under the same level of future uncertainty. We characterize a class of maximally robust algorithms using the concept of “safe dispatch set,” which also provides conditions for verifying grid safety for RAC. However, in general such safe dispatch sets may be difficult to compute. We then develop efficient computational algorithms for characterizing the safe dispatch sets. Specifically, for a simpler single-bus two-generator case, we show that the safe dispatch sets can be exactly characterized by a polynomial number of convex constraints. Then, based on this two-generator characterization, we develop a new solution for the multi-bus multi-generator case using the idea of virtual demand splitting (VDS), which can effectively compute a suitable subset of the safe-dispatch set. Our numerical results demonstrate that a VDS-based economic dispatch algorithm outperforms the standard economic dispatch algorithm in terms of robustness, without sacrificing economy.

Recently, Wang and Chen [1] showed that network coding (NC) can double the throughput as compared to routing in delay-constrained single-unicast communication. This is in sharp contrast to its delay-unconstrained counterpart where coding has no throughput gain. The result reveals that the landscape of delay-constrained communication is fundamentally different from the well-understood delay-unconstrained one and calls for investigation participation. In this paper, we generalize the Koetter-Medard algebraic approach [2] for delay-unconstrained network coding to the delay-constrained setting. The generalized approach allows us to systematically model deadline-induced interference, which is the unique challenge in studying network coding for delay-constrained communication. Using this algebraic approach, we characterize the coding capacity for single-source unicast and multicast, as the rank difference between an information space and a deadline-induced interference space. The results allow us to numerically compute the NC capacity for any given graph, serving as a benchmark for existing and future solutions on improving delay-constrained throughput.

Suppose x is any exactly k-sparse vector in Rn. We present a class of sparse matrices A, and a corresponding algorithm that we call short and fast1 (SHO-FA) that, with high probability over A, can reconstruct x from Ax. The SHO-FA algorithm is related to the invertible bloom lookup tables recently introduced by Goodrich et al., with two important distinctions- SHO-FA relies on linear measurements, and is robust to noise. The SHO-FA algorithm is the first to simultaneously have the following properties: 1) it requires only O(k) measurements; 2) the bit precision of each measurement and each arithmetic operation is O (log(n) + P) (here, 2-Pcorresponds to the desired relative error in the reconstruction of x); 3) the computational complexity of decoding is O(k) arithmetic operations and that of encoding is O(n) arithmetic operations; and 4) if the reconstruction goal is simply to recover a single component of x instead of all of x, with significant probability over A, this can be done in constant time. All the above constants are independent of all problem parameters other than the desired probability of success. For a wide range of parameters, these properties are informationtheoretically order-optimal. In addition, our SHO-FA algorithm works over fairly general ensembles of sparse random matrices, and is robust to random noise and (random) approximate sparsity for a large range of k. In particular, suppose the measured vector equals A(x + z) + e, where z and e correspond to the source tail and measurement noise, respectively. Under reasonable statistical assumptions on z and e, our decoding algorithm reconstructs x with an estimation error of O(||z||2 + ||e||2). The SHO-FA algorithm works with high probability over A, z, and e, and still requires only O(k) steps and O(k) measurements over O(log(n))-bit numbers. This is in contrast to most existing algorithms that focus on the worst case z model, where it is known that Ω(k log(n/k)) measurements over O(log(n))-bit numbers are necessary. Our algorithm has good empirical performance, as validated by simulations.

In distributed storage systems, regenerating codes can achieve the optimal tradeoff between storage capacity and repair bandwidth. However, a critical drawback of existing regenerating codes, in general, is the high coding and repair complexity, since the coding and repair processes involve expensive multiplication operations in finite field. In this paper, we present a design framework of regenerating codes, which employ binary addition and bitwise cyclic shift as the elemental operations, named BASIC regenerating codes. The proposed BASIC regenerating codes can be regarded as a concatenated code with the outer code being a binary parity-check code, and the inner code being a regenerating code utilizing the binary parity-check code as the alphabet. We show that the proposed functional-repair BASIC regenerating codes can achieve the fundamental tradeoff curve between the storage and repair bandwidth asymptotically of functional-repair regenerating codes with less computational complexity. Furthermore, we demonstrate that the existing exact-repair product-matrix construction of regenerating codes can be modified to exact-repair BASIC product-matrix regenerating codes with much less encoding, repair, and decoding complexity from the theoretical analysis, and with less encoding time, repair time, and decoding time from the implementation results.

Motivated by the increasing popularity of learning and predicting human user behavior in communication and computing systems, in this paper, we investigate the fundamental benefit of predictive scheduling, i.e., predicting and pre-serving arrivals, in controlled queueing systems. Based on a lookahead-window prediction model, we first establish a novel queue-equivalence between the predictive queueing system with a fully efficient scheduling scheme and an equivalent queueing system without prediction. This result allows us to analytically demonstrate that predictive scheduling necessarily improves system delay performance and drives it to zero with increasing prediction power. It also enables us to exactly determine the required prediction power for different systems and study its impact on tail delay. We then propose the Predictive Backpressure (PBP) algorithm for achieving optimal utility performance in such predictive systems. PBP efficiently incorporates prediction into stochastic system control and avoids the great complication due to the exponential state space growth in the prediction window size. We show that PBP achieves a utility performance that is within O(ε) of the optimal, for any ε > 0, while guaranteeing that the system delay distribution is a shifted-to-the-left version of that under the original Backpressure algorithm. Hence, the average delay under PBP is strictly better than that under Backpressure, and vanishes with increasing prediction window size. This implies that the resulting utility-delay tradeoff with predictive scheduling can beat the known optimal [O(ε),O(log(1/ε))] tradeoff for systems without prediction. We also develop the Predictable-Only PBP (POPBP) algorithm and show that it effectively reduces packet delay in systems where traffic can only be predicted but not pre-served.

Live media streaming has become one of the most popular applications over the Internet. We have witnessed the successful deployment of commercial systems with content delivery network (CDN)- or peer-to-peer-based engines. While each being effective in certain aspects, having an all-round scalable, reliable, responsive, and cost-effective solution remains an illusive goal. Moreover, today's live streaming services have become highly globalized, with subscribers from all over the world. Such a globalization makes user behaviors and demands even more diverse and dynamic, further challenging state-of-the-art system designs. The emergence of cloud computing, however, sheds new light into this dilemma. Leveraging the elastic resource provisioning from the cloud, we present Cloud-Assisted Live Media Streaming (CALMS), a generic framework that facilitates a migration to the cloud. CALMS adaptively leases and adjusts cloud server resources in a fine granularity to accommodate temporal and spatial dynamics of demands from live streaming users. We present optimal solutions to deal with cloud servers with diverse capacities and lease prices, as well as the potential latencies in initiating and terminating leases in real-world cloud platforms. Our solution well accommodates location heterogeneity, mitigating the impact from user globalization. It also enables seamless migration for existing streaming systems, e.g., peer-to-peer, and fully explores their potentials. Simulations with data traces from both cloud service providers (Amazon EC2 and SpotCloud) and a live streaming service provider (PPTV) demonstrate that CALMS effectively mitigates the overall system deployment costs and yet provides users with satisfactory streaming latency and rate.

The cloud computing paradigm has been advocated in recent video conferencing system design, which exploits the rich on-demand resources spanning multiple geographic regions of a distributed cloud, for better conferencing experience. A typical architectural design in cloud environment is to create video conferencing agents, i.e., Virtual machines, in each cloud site, assign users to the agents, and enable inter-user communication through the agents. Given the diversity of devices and network connectivities of the users, the agents may also transcode the conferencing streams to the best formats and bitrates. In this architecture, two key issues exist on how to effectively assign users to agents and how to identify the best agent to perform a Transco ding task, which are nontrivial due to the following: (1) the existing proximity-based assignment may not be optimal in terms of inter-user delay, which fails to consider the whereabouts of the other users in a conferencing session, (2) the agents may have heterogeneous bandwidth and processing availability, such that the best Transco ding agents should be carefully identified, for cost minimization while best serving all the users requiring the transcoded streams. To address these challenges, we formulate the user-to-agent assignment and Transco ding-agent selection problems, which targets at minimizing the operational cost of the conferencing provider while keeping the conferencing delay low. The optimization problem is combinatorial in nature and difficult to solve. Using Markov approximation framework, we design a decentralized algorithm that provably converges to a bounded neighborhood of the optimal solution. An agent ranking scheme is also proposed to properly initialize our algorithm so as to improve its convergence. The results from a prototype system implementation show that our design in a set of Internet-scale scenarios reduces the operational cost by 77% as compared to a commonly-adopted alternative, while simultaneously yielding lower conferencing delays.

The Federal Communications Commission (FCC) released the final rule to approve of TV white spaces (TVWS), i.e., locally vacant TV channels, for unlicensed use in 2010. This TV spectrum will mitigate the shortage of wireless spectrum resources and provide opportunities for new applications. TVWS differ from the conventional Wi-Fi spectrum in three aspects: spectrum fragmentation, spatial variation, and temporal variation. These differences make the network design over TVWS challenging and fundamentally different from Wi-Fi networks. While most prior works on TVWS network design focused on outdoor large-area scenario, the important indoor scenario is largely open for investigation. In this paper, we present WINET (for White-space Indoor NETwork), the first design framework for indoor multi-AP white space network. We optimize AP placement, spectrum allocation, and AP association. Spectrum fragmentation, spatial variation, and temporal variation are all tackled in our network design. We build a test-bed and conduct extensive measurements inside an office building across four months to obtain real-world traces. Experimental results show that WINET can increase AP coverage area by an average of 62.2% and obtain 67.9% higher system throughput while achieving fairness among users as compared to alternative approaches.

We study competitive online algorithms for EV (electrical vehicle) charging under the scenario of an aggregator serving a large number of EVs together with its background load, using both its own renewable energy (for free) and the energy procured from the external grid. The goal of the aggregator is to minimize its peak procurement from the grid, subject to the constraint that each EV has to be fully charged before its deadline. Further, the aggregator can predict the future demand and the renewable energy supply with some levels of uncertainty. The key challenge here is how to develop a model that captures the prior knowledge from such prediction, and how to best utilize this prior knowledge to reduce the peak under future uncertainty. In this paper, we first propose a 2-level increasing precision model (2-IPM), to capture the system uncertainty. We develop a powerful computation approach that can compute the optimal competitive ratio under 2-IPM over any online algorithm, and also online algorithms that can achieve the optimal competitive ratio. A dilemma for online algorithm design is that an online algorithm with good competitive ratio may exhibit poor average-case performance. We then propose a new Algorithm-Robustification procedure that can convert an online algorithm with reasonable average-case performance to one with both the optimal competitive ratio and good average-case performance. The robustified version of a well-known heuristic algorithm, Receding Horizon Control (RHC), is found to demonstrate superior performance via trace-based simulations.

Small-cell architecture is widely adopted by cellular network operators to increase network capacity. By reducing the size of cells, operators can pack more (low-power) base stations in an area to better serve the growing demands, without causing extra interference. However, this approach suffers from low spectrum temporal efficiency. When a cell becomes smaller and covers fewer users, its total traffic fluctuates significantly due to insufficient traffic aggregation and exhibiting a large "peak to-mean" ratio. As operators customarily provision spectrum for peak traffic, large traffic temporal fluctuation inevitably leads to low spectrum temporal efficiency. In this work, we first carryout a case-study based on real-world 3G data traffic traces and confirm that 90% of the cells in a metropolitan district are less than 40% utilized. Our study also reveals that peak traffic of adjacent cells are highly asynchronous. Motivated by these observations, we advocate device-to-device (D2D) load-balancing as a useful mechanism to address the fundamental drawback of small-cell architecture. The idea is to shift traffic from a congested cell to its adjacent under-utilized cells by leveraging inter-cell D2D communication, so that the traffic can be served without using extra spectrum, effectively improving the spectrum temporal efficiency. We provide theoretical modeling and analysis to characterize the benefit of D2D load balancing, in terms of sum peak traffic reduction of individual cells. We also derive the corresponding cost, in terms of incurred D2D traffic overhead. We carry out empirical evaluations based on real-world 3G data traces to gauge the benefit and cost of D2D load balancing under practical settings. The results show that D2D load balancing can reduce the sum peak traffic of individual cells by 35% as compared to the standard scenario without D2D load balancing, at the expense of 45% D2D traffic overhead.

The smart grid is a modern power grid that achieves high efficiency and robustness through sophisticated information and communications technology. Demand response has great potential in helping balance demand and supply in a smart grid, cutting generation cost and carbon footprint, and improving system stability. Auctions represent a natural and efficient approach for carrying out demand response between the power grid and large electricity users, microgrids, and electricity storage devices. This work explores the modeling and design space of demand response auctions, targeting expressive power, truthful information revelation, computational efficiency, and economic efficiency. We present a randomized auction that explores the underlying problem structure of demand response, and prove that it is truthful, runs in polynomial time, and achieves (1 + ϵ)-optimal social cost for an arbitrarily small constant ϵ. The key technique lies in the marriage of smoothed analysis and randomized reduction, which makes its debut in this work among literature on mechanism design, and can be applied to problems where social welfare optimization is NP-hard but admits a smoothed polynomial-time algorithm.

Idling, or running the engine when the vehicle is not moving, accounts for 13%-23% of vehicle driving time and costs billions of gallons of fuel each year. In this paper, we consider the problem of idling reduction under the uncertainty of vehicle stop time. We abstract it as a classic ski rental problem, and propose a constrained version with two statistics μB- and qB+, the expected length of short stops and the probability of long stops. We develop two online algorithms, a suboptimal closed-form algorithm and an optimal numerical solution, that combine the best of the well-known deterministic and randomized schemes to minimize the worst case competitive ratio. We demonstrate the algorithms perform better than existing solutions in terms of both worst case guarantee and average case performance using simulation and real-world driving data.

There is an unprecedented trend that content providers (CPs) are building their own content delivery networks (CDNs) to provide a variety of content services to their users. By exploiting powerful CP-level information in content distribution, these CP-built CDNs open up a whole new design space and are changing the content delivery landscape. In this paper, we adopt a measurement-based approach to understanding why, how, and how much CP-level intelligences can help content delivery. We first present a measurement study of the CDN built by Tencent, a largest content provider based in China. We observe new characteristics and trends in content delivery which pose great challenges to the conventional content delivery paradigm and motivate the proposal of CPCDN, a CDN powered by CP-aware information. We then reveal the benefits obtained by exploiting two indispensable CP-level intelligences, namely context intelligence and user intelligence, in content delivery. Inspired by the insights learnt from the measurement studies, we systematically explore the design space of CPCDN and present the novel architecture and algorithms to address the new content delivery challenges that have arisen. Our results not only demonstrate the potential of CPCDN in pushing content delivery performance to the next level, but also identify new research problems calling for further investigation.

Idling, or running the engine when the vehicle is not moving, accounts for 13% - 23% of vehicle driving time and costs billions of gallons of fuel each year. In this paper, we consider the problem of idling reduction under the uncertainty of vehicle stop time. We abstract it as a classic ski rental problem, and propose a constrained version with two statistics μB− and qB+, the expectation of short stops' lengths and the probability of long stops. We develop an online algorithm that combines the best of the well-known deterministic and randomized schemes to minimize the worst case competitive ratio. We demonstrate the robustness of the algorithm in terms of both worst case guarantee and average case performance using simulation and real-world driving data.

We present a new family of maximal-distance separable (MDS) array codes which can tolerate five disk failures. The encoding is based on bit-wise exclusive OR (XOR) and bit-wise cyclic shifts, and hence is amenable to practical implementation. Efficient repair method for correcting up to two disk failures is also given. The proposed coding scheme provides a larger spectrum of parameters, with comparable encoding and repairing complexities in compare with existing MDS array codes, such as the row-diagonal parity (RDP) code and the EVENODD code.

This work studies how to minimize the bandwidth cost for uploading deferral big data to a cloud computing platform, for processing by a MapReduce framework, assuming the Internet service provider (ISP) adopts the MAX contract pricing scheme. We first analyze the single ISP case and then generalize to the MapReduce framework over a cloud platform. In the former, we design a Heuristic Smoothing algorithm whose worst-case competitive ratio is proved to fall between 2−1/(D+1) and 2(1 − 1/e), where D is the maximum tolerable delay. In the latter, we employ the Heuristic Smoothing algorithm as a building block, and design an efficient distributed randomized online algorithm, achieving a constant expected competitive ratio. The Heuristic Smoothing algorithm is shown to outperform the best known algorithm in the literature through both theoretical analysis and empirical studies. The efficacy of the randomized online algorithm is also verified through simulation studies.

Compressive phase retrieval algorithms attempt to reconstruct a “sparse high-dimensional vector” from its “low-dimensional intensity measurements”. Suppose x is any length-n input vector over ℂ with exactly k non-zero entries, and A is an m × n (k1x|, ..., |Amx|) (corresponding to component-wise absolute values of the linear measurement Ax) - here Ai's correspond to the rows of the measurement matrix A. In this work, we present a class of measurement matrices A, and a corresponding decoding algorithm that we call SUPER, which can reconstruct x up to a global phase from intensity measurements. The SUPER algorithm is the first to simultaneously have the following properties: (a) it requires only O(k) (order-optimal) measurements, (b) the computational complexity of decoding is O(k log k) (near order-optimal) arithmetic operations, (c) it succeeds with high probability over the design of A. Our results hold for all k ∈ {1, 2, ..., n}.

We present a design framework of regenerating codes for distributed storage systems which employ binary additions and bit-wise cyclic shifts as the basic operations. The proposed coding method can be regarded as a concatenation coding scheme with the outer code being a binary cyclic code, and the inner code a regenerating code utilizing the binary cyclic code as the alphabet set. The advantage of this approach is that encoding and repair of failed node can be done with low computational complexity. It is proved that the proposed coding method can achieve the fundamental tradeoff curve between the storage and repair bandwidth asymptotically when the size of the data file is large.

We consider a delay-constrained unicast scenario, where a source node streams perishable information to a destination node over a directed acyclic graph subject to a delay constraint. Transmission along any edge incurs unit delay, and we require that every information bit generated at the source in the beginning of time t to be received and recovered by the destination in the end of time t + D - 1 where D > 0 is the maximum allowed communication delay. We study the corresponding delay-constrained (d-cn) unicast capacity problem. When only routing is allowed, [Ying, et al. 2011] showed that the aforementioned d-cn unicast routing capacity can be characterized and computed efficiently. However, the d-cn capacity problem changes completely when network coding (NC) is allowed. In this work, we construct the first example showing that NC can achieve strictly higher d-cn throughput than routing even for the single unicast setting and the NC gain can be arbitrarily close to 2 in some instances. This is in sharp contrast to the delay-unconstrained (D → ∞) single-unicast case where the classic min-cut/max-flow theorem implies that coding cannot improve throughput over routing. Finally, we propose a new upper bound on the d-cn unicast NC capacity and elaborate its connections to the existing routing-based results [Ying, et al. 2011]. Overall, our results suggest that d-cn communication is fundamentally different from the well-understood delay-unconstrained one and call for investigation participation.

Motivated by the increasing popularity of learning and predicting human user behavior in communication and computing systems, in this paper, we investigate the fundamental benefit of predictive scheduling, i.e., predicting and pre-serving arrivals, in controlled queueing systems. Based on a lookahead-window prediction model, we first establish a novel queue-equivalence between the predictive queueing system with a fully-efficient scheduling scheme and an equivalent queueing system without prediction. This result allows us to analytically demonstrate that predictive scheduling necessarily improves system delay performance and drives it to zero with increasing prediction power. It also enables us to exactly determine the required prediction power for different systems and study its impact on tail delay. We then propose the Predictive, Backpressure, (PBP) algorithm for achieving optimal utility performance in such predictive systems. PBP efficiently incorporates prediction into stochastic system control and avoids the great complication due to the exponential state space growth in the prediction window size. We show that PBP achieves a utility performance that is within O(ε) of the optimal, for any ε>0, while guaranteeing that the system delay distribution is a shifted-to-the-left version of that under the original Backpressure algorithm. Hence, the average delay under PBP is strictly better than that under Backpressure, and vanishes with increasing prediction window size. This implies that the resulting utility-delay tradeoff with predictive scheduling can beat the known optimal [O(ε), O(log(1/ε))] tradeoff for systems without prediction.

Most mobile devices today come with multiple access interfaces, \emph{e.g.}, 4G and WiFi. Multipath TCP (MP-TCP) can greatly improve network performance by exploiting the connection diversity of multiple access interfaces, at the expense of higher energy consumption. In this paper, we design MP-TCP algorithms for mobile devices by jointly considering the performance and energy consumption. We consider two main types of mobile applications: realtime applications that have a fixed duration and file transfer applications that have a fixed data size. For each type of applications, we propose a two-timescale algorithm with theoretical guarantee on the performance. We present simulation results that show that our algorithms can reduce energy consumption by up to 22$\%$ without sacrificing throughput compared to a baseline MP-TCP algorithm.

In online service systems, delay experienced by a user from the service request to the service completion is one of the most critical performance metrics. To improve user delay experience, in this paper, we investigate a novel aspect of system design: proactive serving, where the system can predict future user request arrivals and allocate its capacity to serve these upcoming requests proactively. In particular, we investigate the average user delay under proactive serving from a queuing theory perspective. We show that proactive serving reduces the average user delay exponentially (as a function of the prediction window size) under M/M/1 queueing models. Our simulation results show that, for G/G/1 queueing models, the average user delay also decreases significantly under proactive serving.

We study the problem of maximizing the broadcast rate in peer-to-peer (P2P) systems under node degree bounds, i.e., the number of neighbors a node can simultaneously connect to is upper-bounded. The problem is critical for supporting high-quality video streaming in P2P systems and is challenging due to its combinatorial nature. In this paper, we address this problem by providing the first distributed solution that achieves near-optimal broadcast rate under arbitrary node degree bounds and over arbitrary overlay graph. It runs on individual nodes and utilizes only the measurement from their one-hop neighbors, making the solution easy to implement and adaptable to peer churn and network dynamics. Our solution consists of two distributed algorithms proposed in this paper that can be of independent interests: a network-coding-based broadcasting algorithm that optimizes the broadcast rate given a topology, and a Markov-chain guided topology hopping algorithm that optimizes the topology. Our distributed broadcasting algorithm achieves the optimal broadcast rate over arbitrary P2P topology, while previously proposed distributed algorithms obtain optimality only for P2P complete graphs. We prove the optimality of our solution and its convergence to a neighborhood around the optimal equilibrium under noisy measurements or without time-scale separation assumptions. We demonstrate the effectiveness of our solution in simulations using uplink bandwidth statistics of Internet hosts.

Today's data centers are shared among multiple tenants running a wide range of applications. These applications require a network with a scalable and robust layer-2 network management solution that enables load-balancing and QoS provisioning. Ensemble routing was proposed to achieve management scalability and robustness by using Virtual Local Area Networks (VLANs) and operating on the granularity of flow ensembles, i.e. group of flows. The key challenge of intra-data-center traffic engineering with ensemble routing is the combinatorial optimization of VLAN assignment, i.e., optimally assigning flow ensembles to VLANs to achieve load balancing and low network costs. Based on the Markov approximation framework, we solve the VLAN assignment problem with a general objective function and arbitrary network topologies by designing approximation algorithms with close-to-optimal performance guarantees. We study several properties of our algorithms, including performance optimality, perturbation bound, convergence of algorithms and impacts of algorithmic parameter choices. Then we extend these results to variants of VLAN assignment problem, including interaction with TCP congestion and QoS considerations. We validate our analytical results by conducting extensive numerical experiments. The results show that our algorithms can be tuned to meet different temporal constraints, incorporate fine-grained traffic management, overcome traffic measurement limitations, and tolerate imprecise and incomplete traffic matrices.

Cloud computing, rapidly emerging as a new computation paradigm, provides agile and scalable resource access in a utility-like fashion, especially for the processing of big data. An important open issue here is how to efficiently move the data, from different geographical locations over time, into a cloud for effective processing. The de facto approach of hard drive shipping is not flexible, nor secure. This work studies timely, cost-minimizing upload of massive, dynamically-generated, geodispersed data into the cloud, for processing using a MapReducelike framework. Targeting at a cloud encompassing disparate data centers, we model a cost-minimizing data migration problem, and propose two online algorithms, for optimizing at any given time the choice of the data center for data aggregation and processing, as well as the routes for transmitting data there. The first is an online lazy migration (OLM) algorithm achieving a competitive ratio of as low as 2.55, under typical system settings. The second is a randomized fixed horizon control (RFHC) algorithm achieving a competitive ratio of 1+ 1/l+λ κ/λ with a lookahead window of l, where κ and λ are system parameters of similar magnitude.

Regenerating code is a class of storage codes that achieve the optimal trade-off between storage capacity and repair bandwidth, which are two important performance metrics in data storage systems. However, existing constructions of regenerating codes rely on expensive computational operations such as finite field multiplication. The high coding and repair complexity limit their applications in large-scale practical storage systems. In this paper, we show that it is possible to achieve the full potential of regenerating codes with low computational complexity. In particular, we propose a new class of regenerating codes, called BASIC codes, that can achieve two specific points (i.e., minimum-bandwidth and minimum-storage regenerating points) on the storage and repair bandwidth trade-off curve, using only binary addition and shift operations in the coding and repair processes. Although in this paper we focus on constructing and analyzing BASIC codes for two specific exact-repair settings, our framework can be generalized to develop BASIC codes for more general exact- and functional-repair regenerating codes.

Broadcasting systems such as P2P streaming systems represent important network applications that support up to millions of online users. An efficient broadcasting mechanism is at the core of the system design. Despite substantial efforts on developing efficient broadcasting algorithms, the following important question remains open: How to achieve the maximum broadcast rate in a distributed manner with each user maintaining information queues only for its direct neighbors? In this work, we first derive an innovative formulation of the problem over acyclic overlay networks with arbitrary underlay capacity constraints. Then, based on the formulation, we develop a distributed algorithm to achieve the maximum broadcast rate and every user only maintains one queue per-neighbor. Due to its lightweight nature, our algorithm scales very well with the network size and remains robust against high system dynamics. Finally, by conducting simulations we validate the optimality of our algorithm under different network capacity models. Simulation results further indicate that the convergence time of our algorithm grows linearly with the network size, which suggests an interesting direction for future investigation.

It is a promising vision to utilize white spaces, i.e., vacant VHF and UHF TV channels, to satisfy skyrocketing wireless data demand in both outdoor and indoor scenarios. While most prior works have focused on exploring outdoor white spaces, the indoor story is largely open for investigation. Motivated by this observation and that 70% of the spectrum demand comes from indoor environments, we carry out a comprehensive study of exploring indoor white spaces. We first present a large-scale measurement of outdoor and indoor TV spectrum occupancy in 30+ diverse locations in a typical metropolis Hong Kong. Our measurement results confirm abundant white spaces available for exploration in a wide range of areas in metropolises. In particular, more than 50% and 70% of the TV spectrum are white spaces in outdoor and indoor scenarios, respectively. While there are substantially more white spaces in indoor scenarios than in outdoor scenarios, there is no effective solution for identifying indoor white spaces. To fill in this gap, we propose the first system WISER (for White-space Indoor Spectrum EnhanceR), to identify and track indoor white spaces in a building, without requiring user devices to sense the spectrum. We discuss the design space of such system and justify our design choices using intensive real-world measurements. We design the architecture and algorithms to address the inherent challenges. We build a WISER prototype and carry out real-world experiments to evaluate its performance. Our results show that WISER can identify 30%-50% more indoor white spaces with negligible false alarms, as compared to alternative baseline approaches.

Microgrids represent an emerging paradigm of future electric power systems that can utilize both distributed and centralized generations. Two recent trends in microgrids are the integration of local renewable energy sources (such as wind farms) and the use of co-generation (i.e., to supply both electricity and heat). However, these trends also bring unprecedented challenges to the design of intelligent control strategies for microgrids. Traditional generation scheduling paradigms rely on perfect prediction of future electricity supply and demand. They are no longer applicable to microgrids with unpredictable renewable energy supply and with co-generation (that needs to consider both electricity and heat demand). In this paper, we study online algorithms for the microgrid generation scheduling problem with intermittent renewable energy sources and co-generation, with the goal of maximizing the cost-savings with local generation. Based on the insights from the structure of the offline optimal solution, we propose a class of competitive online algorithms, called CHASE (Competitive Heuristic Algorithm for Scheduling Energy-generation), that track the offline optimal in an online fashion. Under typical settings, we show that CHASE achieves the best competitive ratio among all deterministic online algorithms, and the ratio is no larger than a small constant 3. We also extend our algorithms to intelligently leverage on limited prediction of the future, such as near-term demand or wind forecast. By extensive empirical evaluations using real-world traces, we show that our proposed algorithms can achieve near offline-optimal performance. In a representative scenario, CHASE leads to around 20% cost reduction with no future look-ahead, and the cost reduction increases with the future look-ahead window.

Different from a large body of research on social networks that has focused almost exclusively on positive relationships, we study signed social networks with both positive and negative links. Specifically, we focus on how to reliably and effectively predict the signs of links in a newly formed signed social network (called a target network). Since usually only a very small amount of edge sign information is available in such newly formed networks, this small quantity is not adequate to train a good classifier. To address this challenge, we need assistance from an existing, mature signed network (called a source network) which has abundant edge sign information. We adopt the transfer learning approach to leverage the edge sign information from the source network, which may have a different yet related joint distribution of the edge instances and their class labels.

In this paper, we revisit the problem of multi-party conferencing from a practical perspective, and to rethink the design space involved in this problem. We believe that an emphasis on low end-to-end delays between any two parties in the conference is a must, and the source sending rate in a session should adapt to bandwidth availability and congestion. We present Celerity, a multi-party conferencing solution specifically designed to achieve our objectives. It is entirely Peer-to-Peer (P2P), and as such eliminating the cost of maintaining centrally administered servers. It is designed to deliver video with low end-to-end delays, at quality levels commensurate with available network resources over arbitrary network topologies where bottlenecks can be anywhere in the network. This is in contrast to commonly assumed P2P scenarios where bandwidth bottlenecks reside only at the edge of the network. The highlight in our design is a distributed and adaptive rate control protocol, that can discover and adapt to arbitrary topologies and network conditions quickly, converging to efficient link rate allocations allowed by the underlying network. In accordance with adaptive link rate control, source video encoding rates are also dynamically controlled to optimize video quality in arbitrary and unpredictable network conditions. We have implemented Celerity in a prototype system, and demonstrate its superior performance over existing solutions in a local experimental testbed and over the Internet.

Cloud computing, rapidly emerging as a new computation paradigm, provides agile and scalable resource access in a utility-like fashion, especially for the processing of big data. An important open issue here is to efficiently move the data, from different geographical locations over time, into a cloud for effective processing. The de facto approach of hard drive shipping is not flexible or secure. This work studies timely, cost-minimizing upload of massive, dynamically-generated, geo-dispersed data into the cloud, for processing using a MapReduce-like framework. Targeting at a cloud encompassing disparate data centers, we model a cost-minimizing data migration problem, and propose two online algorithms: an online lazy migration (OLM) algorithm and a randomized fixed horizon control (RFHC) algorithm , for optimizing at any given time the choice of the data center for data aggregation and processing, as well as the routes for transmitting data there. Careful comparisons among these online and offline algorithms in realistic settings are conducted through extensive experiments, which demonstrate close-to-offline-optimum performance of the online algorithms.

Many important network design problems are fundamentally combinatorial optimization problems. A large number of such problems, however, cannot readily be tackled by distributed algorithms. The Markov approximation framework studied in this paper is a general technique for synthesizing distributed algorithms. We show that when using the log-sum-exp function to approximate the optimal value of any combinatorial problem, we end up with a solution that can be interpreted as the stationary probability distribution of a class of time-reversible Markov chains. Selected Markov chains among this class yield distributed algorithms that solve the log-sum-exp approximated combinatorial network optimization problem. By examining three applications, we illustrate that the Markov approximation technique not only provides fresh perspectives to existing distributed solutions, but also provides clues leading to the construction of new distributed algorithms in various domains with provable performance. We believe the Markov approximation techniques will find applications in many other network optimization problems.

Online social networks have reshaped how multimedia contents are generated, distributed, and consumed on today's Internet. Given the massive number of user-generated contents shared in online social networks, users are moving to directly access these contents in their preferred social network services. It is intriguing to study the service provision of social contents for global users with satisfactory quality of experience. In this article, we conduct large-scale measurement of a real-world online social network system to study the social content propagation. We have observed important propagation patterns, including social locality, geographical locality, and temporal locality. Motivated by the measurement insights, we propose a propagation-based social-aware delivery framework using a hybrid edge-cloud and peer-assisted architecture. We also design replication strategies for the architecture based on three propagation predictors designed by jointly considering user, content, and context information. In particular, we design a propagation region predictor and a global audience predictor to guide how the edge-cloud servers backup the contents, and a local audience predictor to guide how peers cache the contents for their friends. Our trace-driven experiments further demonstrate the effectiveness and superiority of our design.

We design flexible schemes to explore the tradeoffs between storage space and access efficiency in reliable data storage systems. Aiming at this goal, two new classes of erasure-resilient codes are introduced -- Basic Pyramid Codes (BPC) and Generalized Pyramid Codes (GPC). Both schemes require slightly more storage space than conventional schemes, but significantly improve the critical performance of read during failures and unavailability. As a by-product, we establish a necessary matching condition to characterize the limit of failure recovery, that is, unless the matching condition is satisfied, a failure case is impossible to recover. In addition, we define a maximally recoverable (MR) property. For all ERC schemes holding the MR property, the matching condition becomes sufficient, that is, all failure cases satisfying the matching condition are indeed recoverable. We show that GPC is the first class of non-MDS schemes holding the MR property.

Energy consumption represents a significant cost in data center operation. A large fraction of the energy, however, is used to power idle servers when the workload is low. Dynamic provisioning techniques aim at saving this portion of the energy, by turning off unnecessary servers. In this paper, we explore how much gain knowing future workload information can bring to dynamic provisioning. In particular, we develop online dynamic provisioning solutions with and without future workload information available. We first reveal an elegant structure of the offline dynamic provisioning problem, which allows us to characterize the optimal solution in a “divide-andconquer” manner. We then exploit this insight to design two online algorithms with competitive ratios 2 - α and e/(e - 1 + α), respectively, where 0 ≤ α ≤ 1 is the normalized size of a look-ahead window in which future workload information is available. A fundamental observation is that future workload information beyond the full-size look-ahead window (corresponding to α = 1) will not improve dynamic provisioning performance. Our algorithms are decentralized and easy to implement. We demonstrate their effectiveness in simulations using real-world traces.

Mobile broadband networks using 3G and 4G technologies (such as EV-DO, HSPA, WiMAX, LTE) are rapidly becoming one of the prominent means to access the Internet. Multimedia consumption - requiring low delay, high bandwidth, or a combination of both - is projected to become a large portion of bandwidth utilization in mobile broadband networks. In this paper, we study the fundamental problem of how packet loss and delay vary as a function of the transmission rate over these networks. With extensive real-world measurement studies, we analyze the performance of a number of rate control algorithms commonly used in media transmission. We show that the variable nature of congestion signals (loss and delay) on these networks leads to an ultimate failure of existing rate control strategies to deliver adequate performance for multimedia applications. In addition, we show how a rate control algorithm derived from the utility maximization framework - which uses queuing delay as the primary congestion signal - can be modified to solve the challenging issues we have observed. By using a variable threshold to define when the network is congested, our proposed solution is able to achieve a significant improvement over algorithms that use fixed definitions of congestion.

Today's data centers need efficient traffic management to improve resource utilization in their networks. In this work, we study a joint tenant (e.g., server or virtual machine) placement and routing problem to minimize traffic costs. These two complementary degrees of freedom—placement and routing—are mutually-dependent, however, are often optimized separately in today's data centers. Leveraging and expanding the technique of Markov approximation, we propose an efficient online algorithm in a dynamic environment under changing traffic loads. The algorithm requires a very small number of virtual machine migrations and is easy to implement in practice. Performance evaluation that employs the real data center traffic traces under a spectrum of elephant and mice flows, demonstrates a consistent and significant improvement over the benchmark achieved by common heuristics.

In this paper we understand BitTorrent protocol from a Markov approximation perspective. We show that together with the underlying rate control algorithm, the rarest first algorithm and choking algorithm in BitTorrent protocol implicitly solve a cooperative combinatorial network utility maximization problem in a distributed manner. This understanding allows us to access properties of BitTorrent from a fresh perspective, including performance optimality, convergence and impacts of design parameters. Our numerical evaluations validate the analytical results.

Live media streaming has become one of the most popular applications over the Internet. We have witnessed the successful deployment of commercial systems with CDN- or peer-to-peer based engines. While each being effective in certain aspects, having an all-round scalable, reliable, responsive and cost-effective solution remains an illusive goal. Moreover, today's live streaming services have become highly globalized, with subscribers from all over the world. Such a globalization makes user behaviors and demands even more diverse and dynamic, further challenging state-of-the-art system designs. The emergence of cloud computing however sheds new lights into this dilemma. Leveraging the elastic resource provisioning from cloud, we present CALMS (Cloud-Assisted Live Media Streaming), a generic framework that facilitates a migration to the cloud. CALMS adaptively leases and adjusts cloud server resources in a fine granularity to accommodate temporal and spatial dynamics of demands from live streaming users. We present optimal solutions to deal with cloud servers with diverse capacities and lease prices, as well as the potential latencies in initiating and terminating leases in real world cloud platforms. Our solution well accommodates location heterogeneity, mitigating the impact from user globalization. It also enables seamless migration for existing streaming systems, e.g., peer-to-peer, and fully explores their potentials. Simulations with data traces from both cloud service provider (Amazon EC2) and live media streaming service provider (PPTV) demonstrate that CALMS effectively mitigates the overall system deployment costs and yet provides users with satisfactory streaming latency and rate.

The problem of maximum rate achievable with analog network coding for a unicast communication over a layered wireless relay network with directed links is considered. A relay node performing analog network coding scales and forwards the signals received at its input. Recently this problem has been considered under two assumptions: (A) each relay node scales its received signal to the upper bound of its transmit power constraint, (B) the relay nodes in specific subsets of the network operate in the high-SNR regime. We establish that assumption (A), in general, leads to suboptimal end-to-end rate. We also characterize the performance of analog network coding in a class of symmetric layered networks without assumption (B). The key contribution of this work is a lemma that states that in a layered relay network a globally optimal set of scaling factors for the nodes that maximizes the end-to-end rate can be computed layer-by-layer. Specifically, a rate-optimal set of scaling factors for the nodes in a layer is the one that maximizes the sum-rate of the nodes in the next layer. This critical insight allows us to characterize analog network coding performance in network scenarios beyond those that can be analyzed using the existing approaches. We illustrate this by computing the maximum rate achievable with analog network coding in one particular layered network, in various communication scenarios.

Mixing time is a fundamental property for a number of transient behaviors of stochastic processes, particularly, random access in CSMA networks. We use mixing time to characterize temporal starvation, which is a transient phenomenon where links can starve for prolonged periods indefinitely often despite having good stationary throughput. Considering a general CSMA network, we study a fundamental setting with multiple frequency agility, such that more than one frequency channel is available, and a link can transmit on at most one of the frequency channels not occupied by its neighbors. The characterization of throughput in such a setting is challenging, involving a hidden Markov chain of the associated stochastic process. This paper develops new results based on the mixing time of hidden Markov chains to shed light on the temporal starvation. Our analytical results quantify the effect of the number of frequency channels on temporal starvation. We provide sufficient and necessary conditions for fast mixing time of the corresponding hidden Markov chain.

A communication scenario where a source communicates with a destination over a directed layered relay network is considered. Each relay performs analog network coding where it scales and forwards the signals received at its input. In this scenario, we address the question: What portion of the maximum end-to-end achievable rate can be maintained if only a fraction of relay nodes available at each layer are used? We consider, in particular, the Gaussian diamond network and a class of symmetric layered networks. For these networks we provide upper bounds on additive and multiplicative gaps between the optimal analog network coding performance when all N relays in each layer are used and when only k such relays are are used, k <; N (network simplification). We show that asymptotically (in source power), the additive gap increases at most logarithmically with ratio N/k and the number of layers, and the corresponding multiplicative gap increases at most linearly with ratio N/k and is independent of the number of layers in the layered network. To the best of our knowledge, this work offers the first characterization of the performance of network simplification in general layered amplify-and-forward relay networks. Further, unlike most of the current approximation results that attempt to bound optimal rates either within an additive gap or a multiplicative gap, our results suggest a new rate approximation scheme that allows for the simultaneous computation of additive and multiplicative gaps.

Online social network has reshaped the way how video contents are generated, distributed and consumed on today's Internet. Given the massive number of videos generated and shared in online social networks, it has been popular for users to directly access video contents in their preferred social network services. It is intriguing to study the service provision of social video contents for global users with satisfactory quality-of-experience. In this paper, we conduct large-scale measurement of a real-world online social network system to study the propagation of the social video contents. We have summarized important characteristics from the video propagation patterns, including social locality, geographical locality and temporal locality. Motivated by the measurement insights, we propose a propagation-based social-aware replication framework using a hybrid edge-cloud and peer-assisted architecture, namely PSAR, to serve the social video contents. Our replication strategies in PSAR are based on the design of three propagation-based replication indices, including a geographic influence index and a content propagation index to guide how the edge-cloud servers backup the videos, and a social influence index to guide how peers cache the videos for their friends. By incorporating these replication indices into our system design, PSAR has significantly improved the replication performance and the video service quality. Our trace-driven experiments further demonstrate the effectiveness and superiority of PSAR, which improves the local download ratio in the edge-cloud replication by 30%, and the local cache hit ratio in the peer-assisted replication by 40%, against traditional approaches.

Passive network tomography uses end-to-end observations of network communications to characterize the network, for instance, to estimate the network topology and to localize random or adversarial faults. Under the setting of linear network coding, this work provides a comprehensive study of passive network tomography in the presence of network (random or adversarial) faults. To be concrete, this work is developed along two directions: 1) tomographic upper and lower bounds (i.e., the most adverse conditions in each problem setting under which network tomography is possible, and corresponding schemes (computationally efficient, if possible) that achieve this performance) are presented for random linear network coding (RLNC). We consider RLNC designed with common randomness, i.e., the receiver knows the random codebooks of all intermediate nodes. (To justify this, we show an upper bound for the problem of topology estimation in networks using RLNC without common randomness.) In this setting, we present the first set of algorithms that characterize the network topology exactly. Our algorithm for topology estimation with random network errors has time complexity that is polynomial in network parameters. For the problem of network error localization given the topology information, we present the first computationally tractable algorithm to localize random errors, and prove that it is computationally intractable to localize adversarial errors. 2) New network coding schemes are designed that improve the tomographic performance of RLNC while maintaining the desirable low-complexity, throughput-optimal, distributed linear network coding properties of RLNC. In particular, we design network codes based on Reed–Solomon codes so that a maximal number of adversarial errors can be localized in a computationally efficient manner even without the information of network topology. The tomography schemes proposed in the paper can be used to monitor networks with other faults such as packet losses and link delays, etc.

Privacy Preserving Data Mining (PPDM) addresses the problem of developing accurate models about aggregated data without access to precise information in individual data record. A widely studied perturbation-based PPDM approach introduces random perturbation to individual values to preserve privacy before data are published. Previous solutions of this approach are limited in their tacit assumption of single-level trust on data miners. In this work, we relax this assumption and expand the scope of perturbation-based PPDM to Multilevel Trust (MLT-PPDM). In our setting, the more trusted a data miner is, the less perturbed copy of the data it can access. Under this setting, a malicious data miner may have access to differently perturbed copies of the same data through various means, and may combine these diverse copies to jointly infer additional information about the original data that the data owner does not intend to release. Preventing such diversity attacks is the key challenge of providing MLT-PPDM services. We address this challenge by properly correlating perturbation across copies at different trust levels. We prove that our solution is robust against diversity attacks with respect to our privacy goal. That is, for data miners who have access to an arbitrary collection of the perturbed copies, our solution prevent them from jointly reconstructing the original data more accurately than the best effort using any individual copy in the collection. Our solution allows a data owner to generate perturbed copies of its data for arbitrary trust levels on-demand. This feature offers data owners maximum flexibility.

In this paper, we study the problem of utility maximization in peer-to-peer (P2P) systems, in which aggregate application-specific utilities are maximized by running distributed algorithms on P2P nodes, which are constrained by their uplink capacities. For certain P2P topologies, we show that routing along a linear number of trees per source can achieve the largest rate region that can be possibly obtained by intrasession and intersession network coding. This observation allows us to develop a simple multitree formulation for the problem. For the resulting nonstrictly concave optimization problem, we develop a Primal-dual distributed algorithm and prove its global convergence using our proposed sufficient conditions. These conditions are general and add understanding to the convergence of primal-dual algorithms under nonstrictly concave settings. We implement the proposed distributed algorithm in a peer-assisted multiparty conferencing system by utilizing only end-to-end delay measurements between P2P nodes. We demonstrate its superior performance through actual experiments on a LAN testbed and the Internet.

A general class of wireless relay networks with a single source-destination pair is considered. Intermediate nodes in the network employ an amplify-and-forward scheme to relay their input signals. In this case the overall input-output channel from the source via the relays to the destination effectively behaves as an intersymbol interference channel with colored noise. Unlike previous work we formulate the problem of the maximum achievable rate in this setting as an optimization problem with no assumption on the network size, topology, and signal-to-noise ratio. Previous work considered only scenarios wherein relays use all their power to amplify their received signals. We demonstrate that this may not always maximize the achievable rate in amplify-and-forward relay networks. The proposed formulation allows us to not only recover known results on the performance of the amplify-and-forward schemes for some simple relay networks but also characterize the performance of such schemes in more complex relay networks which cannot be addressed in a straightforward manner with existing approaches. Using cut-set arguments, we derive simple upper bounds on the capacity of general wireless relay networks. Through various examples, we show that a large class of amplify-and-forward relay networks can achieve rates within a constant factor of these upper bounds asymptotically in network parameters.

An interesting distributed throughput-optimal CSMA MAC protocol, called adaptive CSMA, was proposed recently to schedule any strictly feasible rates inside the capacity region. Of particular interest is the fact that the adaptive CSMA can achieve a system utility arbitrarily close to that is achievable under a central scheduler. However, a specially designed transport-layer rate controller is needed for this result. An outstanding question is whether TCP Reno (one of the most mature versions of TCP) is compatible with adaptive CSMA and can achieve the same result. The answer to this question will determine how close to practical deployment adaptive CSMA is. Our answer is yes and no. First, we observe that running TCP Reno directly over adaptive CSMA results in severe starvation problems. Effectively, its performance is no better than that of TCP Reno over legacy CSMA (IEEE 802.11), and the potentials of adaptive CSMA cannot be realized. We then propose a multi connection TCP solution with active queue management and prove that it can work with adaptive CSMA to achieve optimal utility. NS-2 simulations demonstrate that our solution can alleviate starvation and achieve fair and efficient rate allocation. We remark that multi-connection TCP can be implemented at either application or transport layer. Application-layer implementation requires no kernel modification, making the solution readily deployable in networks running adaptive CSMA. Our results show that adaptive CSMA can work well with only light-weight TCP modifications, bringing it a step closer to practicaiity.

In this paper, we attempt to revisit the problem of multi-party conferencing from a practical perspective, and to rethink the design space involved in this problem. We believe that an emphasis on low end-to-end delays between any two parties in the conference is a must, and the source sending rate in a session should adapt to bandwidth availability and congestion. We present Celerity, a multi-party conferencing solution specifically designed to achieve our objectives. It is entirely Peer-to-Peer (P2P), and as such eliminating the cost of maintaining centrally administered servers. It is designed to deliver video with low end-to-end delays, at quality levels commensurate with available network resources over arbitrary network topologies where bottlenecks can be anywhere in the network. This is in contrast to commonly assumed P2P scenarios where bandwidth bottlenecks reside only at the edge of the network. The highlight in our design is a distributed and adaptive rate control protocol, that can discover and adapt to arbitrary topologies and network conditions quickly, converging to efficient link rate allocations allowed by the underlying network. In accordance with adaptive link rate control, source video encoding rates are also dynamically controlled to optimize video quality. We have implemented Celerity in a prototype system, and demonstrate its superior performance over existing solutions in a local experimental testbed and over the Internet.

In this paper, we attempt to revisit the problem of multi-party conferencing from a practical perspective, and to rethink the design space involved in this problem. We believe that an emphasis on low end-to-end delays between any two parties in the conference is a must, and the source sending rate in a session should adapt to bandwidth availability and congestion. We present Celerity, a multi-party conferencing solution specifically designed to achieve our objectives. It is entirely Peer-to-Peer (P2P), and as such eliminating the cost of maintaining centrally administered servers. It is designed to deliver video with low end-to-end delays, at quality levels commensurate with available network resources over arbitrary network topologies where bottlenecks can be anywhere in the network. This is in contrast to commonly assumed P2P scenarios where bandwidth bottlenecks reside only at the edge of the network. The highlight in our design is a distributed and adaptive rate control protocol, that can discover and adapt to arbitrary topologies and network conditions quickly, converging to efficient link rate allocations allowed by the underlying network. In accordance with adaptive link rate control, source video encoding rates are also dynamically controlled to present the best possible video quality in arbitrary and unpredictable network conditions. We have implemented Celerity in a prototype system and demonstrate its superior performance in a local experimental testbed.

We study the problem of neighbor selection in BitTorrent-like peer-to-peer (P2P) systems, and propose a "soft-worst-neighbor-choking" algorithm that is provably optimal. In practical P2P systems, peers often keep a large set of potential neighbors, but only simultaneously upload/download to/from a small subset of them, which we call active neighbors, to avoid excessive connection overhead. A natural question to ask is: which active neighbor set should each peer choose to maximize the global system performance? The combinatorial nature of the problem makes it especially challenging. In this paper, we formulate an optimization problem and derive a distributed algorithm. We remark that our solution has a similar favor compared to the worst neighbor choking and optimistic unchoking neighbor selection algorithms that are implemented by BitTorrent. However, it encourages peers to stick to better performing neighbors for longer time and is provably globally optimal. Our proposed solution is easy to implement: each peer periodically waits for a constant period of time that depends on the size of the potential neighbor set and the aggregated utility of the active neighbors, chokes (drops) one of its current active neighbors with probability proportional to an exponential weight on the utility of the corresponding link, and randomly unchokes (adds) a new neighbor from its potential neighbor set. Our theoretical findings provide insightful guidelines to designing practical P2P systems. Simulation results corroborate our proposed solution.

Peer-to-peer (P2P) systems provide a scalable way to stream content to multiple receivers over the Internet. The maximum rate achievable by all receivers is the capacity of a P2P streaming session. We provide a taxonomy of sixteen problem formulations, depending on whether there is a single P2P session or there are multiple concurrent sessions, whether the given topology is a full mesh graph or an arbitrary graph, whether the number of peers a node can have is bounded or not, and whether there are nonreceiver relay nodes or not. In each formulation, computing P2P streaming capacity requires the computation of an optimal set of multicast trees, with an exponential complexity, except in three simplest formulations that have been recently solved with polynomial time algorithms. These solutions, however, do not extend to the other more general formulations. In this paper, we develop a family of constructive, polynomial-time algorithms that can compute P2P streaming capacity and the associated multicast trees, arbitrarily accurately for seven formulations, to a factor of 4-approximation for two formulations, and to a factor of log of the number of receivers for two formulations. The optimization problem is reformulated in each case so as to convert the combinatorial problem into a linear program with an exponential number of variables. The linear program is then solved using a primal-dual approach. The algorithms combine an outer loop of primal-dual update with an inner loop of smallest price tree construction, driven by the update of dual variables in the outer loop. We show that when the construction of smallest price tree can be carried out arbitrarily accurately in polynomial time, so can the computation of P2P streaming capacity. We also develop several efficient algorithms for smallest price tree construction. Using the developed algorithms, we investigate the impact of several factors on P2P streaming capacity using topologies derived from statistics of uplink capacities of Internet hosts.

Cross-layer optimization is a key step in wireless network design that coordinates the resources allocated to different layers in order to achieve globally optimal network performance. Existing work on cross-layer optimization for wireless networks often adopts simplistic physical-layer models for wireless channels, such as treating interference as noise or interference avoidance. This crude modeling of physical layer often leads to inefficient utilization of resources. In this paper, we adopt a deterministic channel model proposed in,, a simple abstraction of the physical layer that effectively captures the effect of channel strength, broadcast and superposition in wireless channels. This model allows us to go beyond “treating interference as noise” and as a consequence are able to achieve higher throughput and utility. Within the network utility maximization (NUM) framework, we study the cross-layer optimization for wireless networks based on this deterministic channel model. First, we extend the well-studied conflict graph model to capture the flow interactions over the deterministic channels and characterize the feasible rate region. Then we study distributed algorithms for general wireless multi-hop networks with both link-centric formulation and node-centric formulation. The convergence of algorithms is proved by applying Lyapunov stability theorem and stochastic approximation method. Further, we show the convergence to the bounded neighborhood of optimal solutions with probability one under constant step sizes and constant update intervals. Our numerical evaluations validate the analytical results and show the advantage of deterministic channel model over simple physical layer models such as treating interference as noise.

We consider multi-rate peer-to-peer multiparty video conferencing applications, where different receivers in the same group can receive videos at different rates using, for example, scalable layered coding. The quality of video received by each receiver can be modeled as a concave utility function of the video bitrate. We study and address the unique challenges introduced by maximizing utility in the multi-rate setting as compared to the single-rate case. We first determine an optimal set of tree structures for routing multi-rate content using scalable layered coding. We then develop Primal and Primal-dual based distributed algorithms to maximize aggregate utility of all receivers in all groups by multi-tree routing and show their convergence. These algorithms can be easily implemented and deployed on today's Internet. We have built a prototype video conferencing system to show that this approach converges to optimal bitrates to improve user experience and offers automatic adaptation to network conditions and user preferences.

In the literature, asymptotic studies of multihop wireless network capacity often consider only centralized and deterministic time-division multiple-access (TDMA) coordination schemes. There have been fewer studies of the asymptotic capacity of large-scale wireless networks based on carrier-sensing multiple access (CSMA), which schedules transmissions in a distributed and random manner. With the rapid and widespread adoption of CSMA technology, a critical question is whether CSMA networks can be as scalable as TDMA networks. To answer this question and explore the capacity of CSMA networks, we first formulate the models of CSMA protocols to take into account the unique CSMA characteristics not captured by existing interference models in the literature. These CSMA models determine the feasible states, and consequently the capacity of CSMA networks. We then study the throughput efficiency of CSMA scheduling as compared to TDMA. Finally, we tune the CSMA parameters so as to maximize the throughput to the optimal order. As a result, we show that CSMA can achieve throughput as Ω([1/√(n)]), the same order as optimal centralized TDMA, on uniform random networks. Our CSMA scheme makes use of an efficient backbone-peripheral routing scheme and a careful design of dual carrier-sensing and dual channel scheme. We also address implementation issues of our CSMA scheme.

Two of the fundamental problems in peer-to-peer (P2P) streaming are as follows: what is the maximum streaming rate that can be sustained for all receivers, and what peering algorithms can achieve close to this maximum? These problems of computing and approaching the P2P streaming capacity are often challenging because of the constraints imposed on overlay topology. In this paper, we focus on the limit of P2P streaming rate under node degree bound, i.e., the number of connections a node can maintain is upper bounded. We first show that the streaming capacity problem under node degree bound is NP Complete in general. Then, for the case of node out-degree bound, through the construction of a “Bubble algorithm”, we show that the streaming capacity is at least half of that of a much less restrictive and previously studied case, where we bound the node degree in each streaming tree but not the degree across all trees. Then, for the case of node total-degree bound, we develop a “Cluster-Tree algorithm” that provides probabilistic guarantee of achieving a rate close to the maximum rate achieved under no degree bound constraint, when the node degree bound is logarithmic in network size. The effectiveness of these algorithms in approaching the capacity limit is demonstrated in simulations using uplink bandwidth statistics of Internet hosts. Both analysis and numerical experiments show that peering in a locally dense and globally sparse manner achieves near-optimal streaming rate if the degree bound is at least logarithmic in network size.

We study the problem of maximizing the broadcast rate in peer-to-peer (P2P) systems under node degree bounds, i.e., the number of neighbors a node can simultaneously connect to is upper-bounded. The problem is critical for supporting high-quality video streaming in P2P systems, and is challenging due to its combinatorial nature. In this paper, we address this problem by providing the first distributed solution that achieves near-optimal broadcast rate under arbitrary node degree bounds, and over arbitrary overlay graph. It runs on individual nodes and utilizes only the measurement from their one-hop neighbors, making the solution easy to implement and adaptable to peer churn and network dynamics. Our solution consists of two distributed algorithms proposed in this paper that can be of independent interests: a network-coding based broadcasting algorithm that optimizes the broadcast rate given a topology, and a Markov-chain guided topology hopping algorithm that optimizes the topology. Our distributed broadcasting algorithm achieves the optimal broadcast rate over arbitrary P2P topology, while previously proposed distributed algorithms obtain optimality only for P2P complete graphs. We prove the optimality of our solution and its convergence to a neighborhood around the optimal equilibrium under noisy measurements or without timescale separation assumptions. We demonstrate the effectiveness of our solution in simulations using uplink bandwidth statistics of Internet hosts.

Many important network design problems can be formulated as a combinatorial optimization problem. A large number of such problems, however, cannot readily be tackled by distributed algorithms. The Markov approximation framework studied in this paper is a general technique for synthesizing distributed algorithms. We show that when using the log-sum-exp function to approximate the optimal value of any combinatorial problem, we end up with a solution that can be interpreted as the stationary probability distribution of a class of time- reversible Markov chains. Certain carefully designed Markov chains among this class yield distributed algorithms that solve the log-sum-exp approximated combinatorial network optimization problem. By three case studies, we illustrate that Markov approximation technique not only can provide fresh perspective to existing distributed solutions, but also can help us generate new distributed algorithms in various domains with provable performance. We believe the Markov approximation framework will find applications in many network optimization problems, and this paper serves as a call for participation.

By allowing routers to randomly mix the information content in packets before forwarding them, network coding can maximize network throughput in a distributed manner with low complexity. However, such mixing also renders the transmission vulnerable to pollution attacks, where a malicious node injects corrupted packets into the information flow. In a worst case scenario, a single corrupted packet can end up corrupting all the information reaching a destination. In this paper, we propose RIPPLE, a symmetric key based in-network scheme for network coding authentication. RIPPLE allows a node to efficiently detect corrupted packets and encode only the authenticated ones. Despite using symmetric key based homomorphic Message Authentication Code (MAC) algorithms, RIPPLE achieves asymmetry by delayed disclosure of the MAC keys. Our work is the first symmetric key based solution to allow arbitrary collusion among adversaries. It is also the first to consider tag pollution attacks, where a single corrupted MAC tag can cause numerous packets to fail authentication farther down the stream, effectively emulating a successful pollution attack.

Existing work on cross-layer optimization for wireless networks adopts simple physical-layer models, i.e., treating interference as noise. In this paper, we adopt a deterministic channel model proposed in, a simple abstraction of the physical layer that effectively captures the effect of channel strength, broadcast and superposition in wireless channels. Within the Network Utility Maximization (NUM) framework, we study the cross-layer optimization for wireless networks based on this deterministic channel model. First, we extend the well-applied conflict graph model to capture the flow interactions over the deterministic channels and characterize the feasible rate region. Then we study distributed algorithms for general wireless multi-hop networks. The convergence of algorithms is proved by Lyapunov stability theorem and stochastic approximation method. Further, we show the convergence to the bounded neighborhood of optimal solutions with probability one under constant steps and constant update intervals. Our numerical evaluation validates the analytical results.

Network Tomography (or network monitoring) uses end-to-end measurements to characterize the network, such as estimating the network topology and localizing random or adversarial glitches. Under the setting that all nodes in the network perform random linear network coding, this work provides a comprehensive study of passive network tomography in the presence of network failures, in particular adversarial/random errors and adversarial/random erasures. Our results are categorized into two classes: 1. Topology Estimation. In the presence of both adversarial/random failures, we prove it is both necessary and sufficient for all nodes in the network to share common randomness, i.e., the receiver knows the random code-books of other nodes. Without such common randomness, we prove that in the presence of adversarial or random failures it is either theoretically impossible or computationally intractable to estimate topology accurately. With common randomness, we present the first set of algorithms for characterizing topology exactly. Our algorithms for topology estimation in the presence of random errors/erasures have polynomial-time complexity. 2. Failure Localization. Given the topology, we present the first polynomial time algorithms to localize random errors and adversarial erasures. For the problem of locating adversarial errors, we prove that it is intractable.

Two questions on the theory of content distribution capacity are addressed in this paper: What is the worst user delay performance bound in a chunk-based P2P streaming systems under peer fanout degree constraint? Can we achieve both the minimum delay and the maximum streaming rate simultaneously? In the homogeneous user scenario, we propose a tree-based algorithm called Inverse Waterfilling, which schedules the chunk transmission following an optimal transmitting structure, under fanout degree bound. We show that the algorithm guarantees the delay bound for each chunk of the stream and maintains the maximum streaming rate at the same time.

The throughput of Peer-to-Peer (P2P) Video-on-Demand (VoD) systems is typically capped by the users' aggregate upload bandwidth [1]. The drastic increase in the popularity of VoD and the demand of higher quality content has thus placed substantial burden on the content servers. We investigate a novel P2P VoD architecture that leverages idle Internet resources, which we call helpers, to provide a scalable solution to P2P VoD systems. Helpers are volatile in nature, and can be individually unreliable. However, we investigate the statistical aggregation of a large number of helpers to guarantee quality of service. Since helpers do not come with ¿free¿ preloaded content, trade-offs between how much a helper should download and how much it can aid the system need to be explored. In this paper, the optimal steady-state design parameters are derived to maximize the helpers' upload bandwidth utilization. Packet level simulations have verified the efficiency of the system. In a typical scenario of 240 users and a required theoretical minimum of 120 helpers with an average upload bandwidth of 256 kbps, a streaming rate of 384 kbps can be sustained with < 2% relative server load. Results also show that the system is robust to helper churn.

We consider multi-rate peer-to-peer multi-party conferencing applications, where different receivers in the same group can receive videos at different rates using, for example, scalable layered coding. The quality of video received by each receiver can be modeled as a concave utility function of the video rate. We study and address the unique challenges introduced by multi-rate setting as compared to the single-rate case. We first determine an optimal set of tree structures for routing multi-rate content using scalable layered coding. We then develop primal and primal-dual based distributed algorithms to maximize aggregate utility of all receivers in all groups by multi-tree routing and show their convergence. These algorithms can be easily implemented and deployed on today's Internet. We have built a prototype video conferencing system to show that this approach offers low end-to-end delay, low complexity and high throughput, along with automatic adaptation to network conditions and user preferences.

In the literature, asymptotic studies of multi-hop wireless network capacity often consider only centralized and deterministic TDMA (time-division multi-access) coordination schemes. There have been fewer studies of the asymptotic capacity of large-scale wireless networks based on CSMA (carrier-sensing multi-access), which schedules transmissions in a distributed and random manner. With the rapid and widespread adoption of CSMA technology, a critical question is that whether CSMA networks can be as scalable as TDMA networks. To answer this question and explore the capacity of CSMA networks, we first formulate the models of CSMA protocols to take into account the unique CSMA characteristics, not captured by existing interference models in the literature. These CSMA models determine the feasible states, and consequently the capacity of CSMA networks. %and are functions of various CSMA parameters. We then study the throughput efficiency of CSMA scheduling as compared to TDMA. Finally, we tune the CSMA parameters so as to maximize the throughput to the optimal order. As a result, we show that CSMA can achieve throughput as Ω(1/√n), the same order as optimal centralized TDMA, on uniform random networks. Our CSMA scheme makes use of an efficient backbone-peripheral routing scheme and a careful design of dual carrier-sensing and dual channel scheme. We also address practical implementation issues of our capacity-optimal CSMA scheme.

Random perturbation is a popular method of computing anonymized data for privacy preserving data mining. It is simple to apply, ensures strong privacy protection, and permits effective mining of a large variety of data patterns. However, all the existing studies with good privacy guarantees focus on perturbation at a single privacy level . Namely, a fixed degree of privacy protection is imposed on all anonymized data released by the data holder. This drawback seriously limits the applicability of random perturbation in scenarios where the holder has numerous recipients to which different privacy levels apply. Motivated by this, we study the problem of multi-level perturbation , whose objective is to release multiple versions of a dataset anonymized at different privacy levels. The challenge is that various recipients may collude by sharing their data to infer privacy beyond their permitted levels. Our solution overcomes this obstacle, and achieves two crucial properties. First, collusion is useless, meaning that the colluding recipients cannot learn anything more than what the most trustable recipient (among the colluding recipients) already knows alone . Second, the data each recipient receives can be regarded (and hence, analyzed in the same way) as the output of conventional uniform perturbation. Besides its solid theoretical foundation, the proposed technique is both space economical and computationally efficient. It requires O (n+m) expected space, and produces a new anonymized version in O ( n + log m ) expected time, where n is the cardinality of the original dataset, and m the number of versions released previously. Both bounds are optimal under the realistic assumption that n » m .

In this paper, we design a system for mutually distrustful entities to perform privacy preserving joins, leveraging the power of a memory-limited secure coprocessor. Under this setting, we critique a questionable assumption in a previous privacy definition [1] that leads to unnecessary information leakage. We then remove the assumption and propose a new definition. Based on this definition, we propose three correct and provable secure algorithms to compute general joins of arbitrary predicates, by utilizing available cryptographic tools in a nontrivial way. We discuss different memory requirements of our proposed algorithms, and explore how to trade little privacy with significant performance improvement. In [2], we evaluate the performance of our algorithms by numerical examples. We also show the performance superiority of our approach over secure multi-party computation in [2].

We consider multi-source multicast communication scenarios in which each node has an aggregate outbound traffic capacity and can directly communicate with any other node. This is motivated by peer-to-peer (P2P) information dissemination applications on the Internet in which the uplink capacity of nodes is usually the bottleneck, being several times smaller than the downlink capacity. We also allow the communication in a group to be helped by non-receiver nodes (with respect to that group) as relays. Extending an earlier result for the single source case, we show that when coding is not allowed across sources, routing is optimal. Also, as a rather surprising discovery, we show that when all groups have pairwise identical or disjoint receivers, routing is optimal even when coding across sources is allowed. Moreover, routing along a linear number of trees per source is sufficient to achieve this. The latter scenario is common in multiparty conferencing systems, hence our results have interesting practical applications in the design of infrastructure-less P2P multiparty conferencing systems.

In this paper, we study the problem of utility maximization in P2P systems, in which aggregate application-specific utilities are maximized by running distributed algorithms on P2P nodes, which are constrained by their uplink capacities. This may be understood as extending Kelly's seminal framework from single-path unicast over general topology to multi-path multicast over P2P topology, with network coding allowed. For certain classes of popular P2P topologies, we show that routing along a linear number of trees per source can achieve the largest rate region that can be possibly obtained by (multi-source) network coding. This simplification result allows us to develop a new multi-tree routing formulation for the problem. Despite of the negative results in literature on applying Primal-dual algorithms to maximize utility under multi-path settings, we have been able to develop a Primal-dual distributed algorithm to maximize the aggregate utility under the multi-path routing environments. Utilizing our proposed sufficient condition, we show global exponential convergence of the Primal-dual algorithm to the optimal solution under different P2P communication scenarios we study. The algorithm can be implemented by utilizing only end-to-end delay measurements between P2P nodes; hence, it can be readily deployed on today's Internet. To support this claim, we have implemented the Primal-dual algorithm for use in a peer-assisted multi-party conferencing system and evaluated its performance through actual experiments on a LAN testbed and the Internet.

In this paper, we study the maximally recoverable (MR) property for multi-protection group (MPG) codes. MPG codes with MR property achieve the best erasure recoverability given configurations, where a configuration represents the structural relationship between data and parity symbols. We present construction and decoding algorithms for MPG codes with MR property. We show that both recoverability and minimum decoding overhead of any MPG code with MR property depend only on the configuration, where decoding overhead is defined as the additional number of symbols to access, in order to decode the lost data symbols.

To flexibly explore the trade-offs between storage space and access efficiency in reliable data storage systems, we describe two classes of erasure resilient coding schemes: basic and generalized pyramid codes. The basic pyramid codes can be simply derived from any existing codes, and thus all known efficient encoding/decoding techniques directly apply. The generalized pyramid codes are radically advanced new codes, which can further improve access efficiency and/or reliability upon the basic pyramid codes. We also establish a necessary condition for any failure pattern to be ever recoverable, and show that the generalized pyramid codes are optimal in failure recovery (i.e., the necessary condition is also sufficient, and any failure pattern that is ever recoverable can indeed be recovered).

Abstract — Flow control, including congestion control for data transmission, and rate control for multimedia streaming, is an important issue in information transmission in both wireline and wireless networks. Widely accepted flow control methods in wireline networks are TCP [1] for data, and TCP Friendly Rate Control (TFRC) [2] for multimedia. Kelly [3] [4] has laid down theoretical framework for TCP in wireline networks demonstrating its optimality, fairness, and stability. However, TCP and TFRC both assume that packet loss in wireline networks is primarily due to congestion, and as such, are not applicable to wireless networks in which the bulk of packet loss is due to errors at the physical layer. In this paper we first show flow control in the wireless networks can be formulated as the same concave optimization problem Kelly defined in the wireline networks. TCP and TFRC in the wireless networks pursue the optimal solution using inaccurate feedback. All existing approaches to this TCP/TFRC over wireless problem correct the inaccurate feedback by casting modifications to existing protocols, such as TCP, or infrastructure elements such as routers, thereby making them hard to deploy in practice. In this paper, we formulate the problem as another concave optimization problem with a different utility function, and propose a new class of solutions. Our approach is end-to-end, and achieves reasonable performance by adjusting the number of connections of a user according to a properly selected control law. The control law is based on only one bit of information, which can be reliably measured at the application layer. We show that the control system has a unique stable equilibrium that solves the concave optimization problem, implying scalability and optimality of the solution. We apply our results to design a practical rate control scheme for data transmission over wireless networks, and characterize its performance using NS-2 simulations and actual experiments over Verizon Wireless 1xRTT data network. Analysis and simulation results also indicate our scheme is applicable to both wireline and wireless scenarios. I.

Rate control is an important issue in video streaming applications for both wired and wireless networks. A widely accepted rate control method in wired networks is equation based rate control , in which the TCP friendly rate is determined as a function of packet loss rate, round trip time and packet size. This approach, also known as TCP friendly rate control (TFRC), assumes that packet loss in wired networks is primarily due to congestion, and as such is not applicable to wireless networks in which the bulk of packet loss is due to error at the physical layer. In this paper, we propose multiple TFRC connections as an end-to-end rate control solution for wireless video streaming. We show that this approach not only avoids modifications to the network infrastructure or network protocol, but also results in full utilization of the wireless channel. NS-2 simulations, actual experiments over 1$times$RTT CDMA wireless data network, and and video streaming simulations using traces from the actual experiments, are carried out to validate, and characterize the performance of our proposed approach.

This paper proposes a detailed framework of storing privacy information in surveillance video as a watermark. Authorized personnel is not only removed from the surveillance video as in J. Wickramasuriya et al. (2004) but also embedded into the video itself, which can only be retrieved with a secrete key. A perceptual-model-based compressed domain video watermarking scheme is proposed to deal with the huge payload problem in the proposed surveillance system. A signature is also embedded into the header of the video as in M. Pramateftakis et al. (2004) for authentication. Simulation results have shown that the proposed algorithm can embed all the privacy information into the video without affecting its visual quality. As a result, the proposed video surveillance system can monitor the unauthorized persons in a restricted environment, protect the privacy of the authorized persons but, at the same time, allow the privacy information to be revealed in a secure and reliable way.

In video communications over error-prone channels, compressed video streams are extremely sensitive to bit errors. Often random and burst bit errors impede correct decoding of parts of a received bitstream. Video decoders normally utilize error concealment techniques to repair a damaged decoded frame, but the effectiveness of these error concealment schemes relies heavily on correctly locating errors in the bitstream. In this paper, we propose a fragile watermark-based error detection and localization scheme called "force even watermarking (FEW)". A fragile watermark is forced onto quantized DCT coefficients at the encoder. If at the decoder side the watermark is no longer intact, errors exist in the bitstream associated with a particular macro-block (MB). Thanks to the watermark, bitstream errors can accurately be located at MB level, which facilitates proper error concealment. This paper describes the algorithm, model and analysis of the watermarking procedure. Our simulation results show that compared to the syntax-based error detection schemes, the proposed FEW scheme significantly improves the error detection capabilities of the video decoder, while the peak signal-to-noise ratio loss and additional computational costs due to watermark embedding and extraction are small.

Rate control is an important issue in video streaming applications for both wired and wireless networks. A widely accepted rate control method in wired networks is equation based rate control (Sally Floyd et al., Aug. 2000), in which the TCP friendly rate is determined as a function of packet loss rate, round trip time and packet size. This approach, also known as TFRC, assumes that packet loss in wired networks is primarily due to congestion, and as such is not applicable to wireless networks in which the bulk of packet loss is due to error at the physical layer. We propose multiple TFRC connections as an end-to-end rate control solution for wireless video streaming. We show that this approach not only avoids modifications to the network infrastructure or network protocol, hut also results in full utilization of the wireless channel. NS-2 simulations and experiments over 1/spl times/RTT CDMA wireless data network are carried out to validate, and characterize the performance of our proposed approach.