In real-world decision-making, uncertainty is important yet difficult to handle. Stochastic dominance provides a theoretically sound approach to comparing uncertain quantities, but optimization with stochastic dominance constraints is often computationally expensive, which limits practical applicability. In this paper, we develop a simple yet efficient approach for the problem, Light Stochastic Dominance Solver (light-SD), by leveraging properties of the Lagrangian. We recast the inner optimization in the Lagrangian as a learning problem for surrogate approximation, which bypasses the intractability and leads to tractable updates or even closed-form solutions for gradient calculations. We prove convergence of the algorithm and test it empirically. The proposed light-SD demonstrates superior performance on several representative problems ranging from finance to supply chain management.

Distributions over discrete sets capture the essential statistics including the high-order correlation among elements. Such information provides powerful insight for decision making across various application domains, e.g., product assortment based on product distribution in shopping carts. While deep generative models trained on pre-collected data can capture existing distributions, such pre-trained models are usually not capable of aligning with a target domain in the presence of distribution shift due to reasons such as temporal shift or the change in the population mix. We develop a general framework to adapt a generative model subject to a (possibly counterfactual) target data distribution with both sampling and computation efficiency. Concretely, instead of re-training a full model from scratch, we reuse the learned modules to preserve the correlations between set elements, while only adjusting corresponding components to align with target marginal constraints. We instantiate the approach for three commonly used forms of discrete set distribution—latent variable, autoregressive, and energy based models—and provide efficient solutions for marginal-constrained optimization in either primal or dual forms. Experiments on both synthetic and real-world e-commerce and EHR datasets show that the proposed framework is able to practically align a generative model to match marginal constraints under distribution shift.

Access control is an extremely important and error-prone practice during web application. The emergence of NoSQL databases and the flexible data models they bring impose new challenges on the implementation of access control within web applications. This paper presents Scout, a novel methodology for discovering access control vulnerabilities in existing web applications. Meanwhile (1) features of NoSQL database can be addressed and (2) neither application source code nor server-side session information from the developers is required. This paper implements a prototype of Scout, which targets MongoDB backend web applications. By automatically discovering the protocol layer in the web application stack, Scout introduces a data access operation model precisely representing the MongoDB actions performed in the web application, as well as inferring the access control policies. The prototype is shown to be able to identify comprehensive access control vulnerabilities in MongoDB backend web applications, and generate detailed report as the facilitator to manually fix the identified vulnerabilities.

Interactive ad hoc data query over massive datasets has recently gained significant traction. Massively parallel data query and analysis frameworks (e.g., Dremel, Impala) are built and deployed to support SQL-like queries over distributed and partitioned data in a clustering environment. As a result, the execution of each query is converted into a set of coordinated tasks including data retrieval, intermediate result computation and transfer, and result aggregation. To support high request rate of concurrent interactive queries, coordinated management of multiple resources (e.g., bandwidth, CPU, memory) of the cluster environment is critical. In this paper, we investigate this resource management problem using an utility-based optimization framework. Our goal is to optimize the resource utilization, and maintain fairness among different types of queries. We present a price-based algorithm which achieves this optimization objective. We implement our algorithm in the open source Impala system and conduct a set of experiments in a clustering environment using the TPC-DS workload. Experimental results show that our coordinated resource management solution can increase the aggregate utility by at least 15.4% compared with simple fair resource share mechanism, and 63.5% compared with the FIFO resource management mechanism.

Access control vulnerabilities within web applications pose serious security threats to the sensitive information stored at back-end databases. Existing approaches are limited from several aspects, including the coarse granularity at which the access control is modeled, the incapability of handling complex relationship between data entities and the requirement of source code and the specific application platform. In this paper, we present an automated black-box technique for identifying a broad range of access control vulnerabilities, which can be applied to applications that are developed using different languages and platforms. We model the access control policy based on a novel virtual SQL query concept, which captures both the database access operations (i.e., through SQL queries) and the post-processing filters within the web application. We leverage a crawler to automatically explore the application and collect execution traces. From the traces, we identify the set of database access operations that are allowed for each role (i.e., role-level policy inference) and extract the constraints over the operation parameters to characterize the relationship between the users and the accessed data (i.e., user-level policy inference). Based on the inferred policy, we construct test inputs to exploit the application for potential access control flaws. We implement a prototype system BATMAN and evaluate it over a set of PHP and JSP web applications. The experiment results demonstrate the effectiveness and accuracy of our approach.

), however, when databases are maintained by disparate organizations, the disclosure of such information can breach the privacy of the corresponding individuals. Various private record linkage (PRL) methods have been developed to obscure such identifiers, but they vary widely in their ability to balance competing goals of accuracy, efficiency and security. The tokenization and hashing of field values into Bloom filters (BF) enables greater linkage accuracy and efficiency than other PRL methods, but the encodings may be compromised through frequency-based cryptanalysis. Our objective is to adapt a BF encoding technique to mitigate such attacks with minimal sacrifices in accuracy and efficiency. To accomplish these goals, we introduce a statistically-informed method to generate BF encodings that integrate bits from multiple fields, the frequencies of which are provably associated with a minimum number of fields. Our method enables a user-specified tradeoff between security and accuracy. We compare our encoding method with other techniques using a public dataset of voter registration records and demonstrate that the increases in security come with only minor losses to accuracy.

Joint congestion control and link scheduling has been proposed as an approach to fair resource allocation in wireless networks. Existing solutions usually favor a distributed cross-layer deployment that requires timely communications among network components in seeking system stability and global optimum. However, this is unrealistic with feedback delay and channel capacity perturbation. The stability and efficiency of these algorithms face significant challenges. In this paper, we present a robust joint congestion control and scheduling algorithm, i.e., ROCS, for time-varying multi-hop mesh wireless networks with feedback delay, to bridge the gap between the existing approaches and the reality of wireless networks. The fundamental idea behind ROCS is capacity space projection, which combines the slow time scale part of the channel capacity and a margin estimated from the fast time scale part, to form a new capacity space. The resource allocation problem is formulated into a utility maximization framework over the newly generated capacity space. The problem is solved by a control algorithm consisting of link scheduling and congestion control. Link scheduling coordinates wireless link utilization, and congestion control allocates flow rates according to feedback information. Experiments conducted over simulated and real-world traces demonstrate that ROCS substantially achieves robustness and efficiency.

Modern parallel computing systems, such as MapReduce, often assume data values are uniformly distributed. However, in the real world, data is often highly skewed, which may cause workload imbalance among parallel running tasks. In this paper, we study the reduce-phase skew problem in MapReduce, where reduce tasks are often assgined imbalance load (in terms of key groups). We introduce a sketch-based data structure for capturing MapReduce key group size statistics and present an optimal packing algorithm which assigns the key groups to the reducers in a load balancing manner. We perform an empirical evaluation with several real and synthetic datasets over two distinct types of applications. The results show that our load balancing algorithm can strongly mitigate the reduce-phase skew. It can decrease the overall job completion time by 45.5% of the default settings in Hadoop and by 38.3% in comparison to the state-of-the-art solution.

Logic flaws are an important class of vulnerabilities within web applications, which allow sensitive information and restrictive operations to be accessed at inappropriate application states. In this paper, we take a first step towards a systematic black-box approach to identifying logic vulnerabilities within web applications. We first construct a partial FSM over the expected input domain by collecting and analyzing the execution traces when users follow the navigation paths within the web application. Then, we test the application at each state by constructing unexpected input vectors and evaluating corresponding web responses. We implement a prototype system LogicScope and demonstrate its effectiveness using a set of real world web applications.

Probability of successful delivery under deadline constraints is one of the most important performance measures in a wireless real-time multihop control and sensor network. In this paper we approach the problem of determining the probability of successful packet delivery by calculating the per-link outage probability for different fading channel models. We provide easily computable results for the end-to-end reliability for two different physical layer designs. Furthermore, we show that incorporating physical layer information into routing and scheduling decisions can result in significant performance improvements when strict deadlines are imposed on the system.

Recent research has introduced load balancing schemes that are aware of the input data distribution (i.e., data profile) to mitigate data skew and fully exploit the parallel capability of the MapReduce framework to support record linkage. However, existing solutions face a significant scalability issue when applied to massive data sets with millions or billions of blocks (a basic unit in record linkage) because their data profiles can not be maintained precisely in an efficient manner. The goal of this paper is to introduce a profiling method based on the notion of a sketch, which allows for a compact scalable solution for maintaining block size statistics. In addition, we propose two load balancing algorithms to work over sketch-based profiles while solving the data skew problem associated with record linkage. We provide an analytical analysis and extensive experiments (using Hadoop), with real and controlled synthetic data sets, to illustrate the effectiveness of our solution. The experimental results show that our load balancing algorithms can decrease the overall job completion time by 71.56% and 70.73% of the default settings in Hadoop using a set of DBLP data sets, which have 2.5 to 50.4 million records.

Logic flaws within web applications allow the attackers to disclose or tamper sensitive information stored in back-end databases, since the web application usually acts as the single trusted user that interacts with the database. In this paper, we model the web application as an extended finite state machine and present a black-box approach for deriving the application specification and detecting malicious SQL queries that violate the specification. Several challenges arise, such as how to extract persistent state information in the database and infer data constraints. We systematically extract a set of invariants from observed SQL queries and responses, as well as session variables, as the application specification. Any suspicious SQL queries that violate corresponding invariants are identified as potential attacks. We implement a prototype detection system SENTINEL (SEcuriNg daTabase from logIc flaws iN wEb appLication) and evaluate it using a set of real-world web applications. The experiment results demonstrate the effectiveness of our approach and show that acceptable performance overhead is incurred by our implementation.

This paper presents the Networked Control Systems Windtunnel (NCSWT), an integrated modeling and simulation tool for the evaluation of networked control systems (NCS). NCSWT integrates Matlab/Simulink and ns-2 using the High Level Architecture (HLA). Our implementation of the NCSWT based on HLA guarantees accurate time synchronization and data communication in heterogenous simulations. NCSWT uses the Model Integrated Computing (MIC) techniques to define HLA-based model constructs such as federates representing the simulators and interactions between the simulators. NCSWT also uses MIC techniques to define models representing the control system and network dynamics for the rapid synthesis of simulations.

This paper investigates the optimal rate allocation problem with end-to-end delay constraints in multi-hop wireless networks. We introduce Virtual Link Capacity Margin (VLCM), which is the gap between the schedulable link capacity and the maximum allowable flow rate over a link, for link delay control. We formulate the problem as a utility maximization framework with two sets of constraints: 1) capacity and schedulability constraints and 2) end-to-end delay constraints. By dual decomposition of the original optimization problem, we present a control algorithm that jointly tunes the flow rates and VLCMs, through a double-price scheme derived with regard to the constraints: the link congestion price reflecting the traffic load of a link, and the flow delay price reflecting the margin between the average packet delay and the delay requirement of a flow. We prove that the algorithm converges to a global optimum where the aggregate network utility defined over the flow rate set is maximized, while the delay constraints are satisfied. A key feature of our algorithm is it does not rely on a specific traffic model. The algorithm is implemented distributedly via joint wireless link scheduling and congestion control. Simulation results show that our algorithm outperforms heuristic rate allocation algorithms while satisfying the end-to-end delay constraints.

Fair resource allocation for end-to-end flows is an important yet challenging problem in multi-hop wireless networks. Recent research on fair resource allocation is mainly based on the assumption of convex resource regions, which has been theoretically proven untrue. Thus, the definition of fairness in IEEE 802.11 is intriguing for two reasons: non-convexity of the IEEE 802.11, and the intrinsically deficient MAC scheduling. Two key questions that emerge unanswered are 1) How to define end-to-end fairness under IEEE 802.11. 2) How to achieve end-to-end fairness. In this paper, we present a new fairness model for IEEE 802.11 wireless network where the capacity region is non-convex. To characterize the desired fairness property, we adopt an axiomatic approach based on the game theoretic framework. Our new fairness model grounds on the Nash Extension Solution (NES), which is shown to be consistent with the concept of proportional fairness under the convex cases and approximate it under the non-convex cases. We further present an efficiency enhanced version of Nash extension solution, which pushes the NES to the strong Pareto frontier. Based on the construction method of NES and its extension solution, we present a time-decomposed price-based rate allocation algorithm and prove its stability. The simulation study over a variety of topologies (e. g., random and dynamic) validates the performance of our algorithms and demonstrates this theoretically sound new fairness model for IEEE 802.11 networks.

Joint congestion control and scheduling has been widely applied to resource allocation in multi-hop wireless networks. Existing algorithms usually rely on seamless cooperation between network components to seek the optimal solution. However, this is unrealistic considering the presence of time delay and channel capacity perturbation in real wireless environments. The stability and efficiency of these cross-layer control algorithms face significant challenges. In this paper we present ROCS: a robust joint congestion control and scheduling algorithm for time-varying multihop wireless networks with time delay, to bridge the gap between the existing results and the reality of wireless networks. The fundamental idea behind ROCS is Capacity Space Mapping, which combines the slow time scale part of the original channel capacity and a margin estimated from the fast time scale part, to form a new capacity space. The cross-layer resource allocation problem is formulated into a utility maximization framework over the newly generated capacity space. The problem is solved by a control algorithm which contains two closely coupled components: Link Scheduling and Congestion Control. Link Scheduling coordinates wireless link utilization on a maximum weight basis, and Congestion Control allocates flow rates according to congestion feedback information. We further derive the sufficient conditions for the Lyapunov stability of the control algorithm with time delay, following the Razumikhin theorem. We demonstrate via extensive experiments conducted over simulated and real world wireless traces that ROCS substantially achieves robustness and efficiency.

Web applications are increasingly used as portals to interact with back-end database systems and support business processes. This type of data-centric workflow-driven web application is vulnerable to two types of security threats. The first is an request integrity attack, which stems from the vulnerabilities in the implementation of business logic within web applications. The second is guideline violation, which stems from privilege misuse in scenarios where business logic and policies are too complex to be accurately defined and enforced. Both threats can lead to sequences of web requests that deviate from typical user behaviors. The objective of this paper is to detect anomalous user behaviors based on the sequence of their requests within a web session. We first decompose web sessions into workflows based on their data objects. In doing so, the detection of anomalous sessions is reduced to detection of anomalous workflows. Next, we apply a hidden Markov model (HMM) to characterize workflows on a per-object basis. In this model, the implicit business logic involved in this object defines the unobserved states of the Markov process, where the web requests are observations. To derive more robust HMMs, we extend the object-specific approach to an object-cluster approach, where objects with similar workflows are clustered and HMM models are derived on a per-cluster basis. We evaluate our models using two real systems, including an open source web application and a large web-based electronic medical record system. The results show that our approach can detect anomalous web sessions and lend evidence to suggest that the clustering approach can achieve relatively low false positive rates while maintaining its detection accuracy.

State violation attacks towards web applications exploit logic flaws and allow restrictive functions and sensitive information to be accessed at inappropriate states. Since application logic flaws are specific to the intended functionality of a particular web application, it is difficult to develop a general approach that addresses state violation attacks. To date, existing approaches all require web application source code for analysis or instrumentation in order to detect state violations.

The goal of this paper is to minimize service disruption, a unique phenomenon in peer-to-peer (P2P) streaming system and the major contributing factor to degrade user experience. In order to improve its streaming quality and stability, a P2P system should select peers with abundant bandwidth resource and prospect longevity as the parents of other peers. Towards this end, we propose PRW (peer resilient weight), a metric to evaluate a peer's healthiness regarding these two aspects. The theoretical background of PRW originates from the optimization framework based on the generalized flow theory. To show PRW's applicability to a wide variety of P2P streaming solutions, we propose several parent selection algorithms guided by PRW under the single-tree, multi-tree, and mesh structures. Using MSN and PPLive traces, we find our algorithms to be able to achieve lower service disruption and lower peer rejection, compared to several existing heuristics and algorithms.

The benefits and importance of electronic medical record (EMR) systems have been well recognized in the healthcare industry. Yet, their wide adoption still face significant barriers in providing on-demand secure medical information access while preserving patients' privacy. Understanding the usage pattern of an EMR system is the first essential step towards building such environment. This paper conducts an in-depth trace analysis of a large-scale EMR system that has been in operation for more than a decade at the Vanderbilt Medical Center. Our study demonstrates several important characteristics of EMR system usage from the perspective of user-initiated sessions. First, the workload of the EMR system is highly stable and consistent with a weekly pattern. Second, EMR behavior varies between users, but each user's behavior tends to be consistent with a slow rate of migration across sessions. Finally, the degree of access between users and medical records is sparse, echoing the limits of patient-caregiver relationships that manifest in real healthcare operations. We believe these observations can assist in the development of system security measures, such as EMR-specific anomaly detection systems, and facilitate system performance optimization.

Peer-to-peer (P2P) traffic is arguably the biggest contributor to today's Internet traffic. So far, very limited effort has been paid to theoretically analyze the effect of bringing locality-awareness into P2P applications. In this paper, we analyze three locality-awareness policies for BitTorrent-like system: tracker locality(neighbor selection), choker locality(choking and unchoking) and picker locality(piece picking). Based on an H-sphere model which captures the essential property of Internet topology, we analyze how much network load saving can be expected for these locality policies, as well as their impact to the downloading efficiency of the system. Through analytical study and simulation, we have the following findings. First, when the system enters the steady state, the locality policies proposed in this paper can achieve the same downloading efficiency as the standard BitTorrent system. Second, these locality policies can significantly alleviate the traffic load on the Internet. Finally, we find that there exists no all-around winner. Instead, each policy performs the best under different system configuration parameters, such as number of unchoked peers.

This paper addresses the problem of optimal rate allocation for video stream in peer-to-peer networks. We present a distributed rate allocation algorithm with the goal of minimizing the total video distortion among peers receiving the same video. The scheme assumes that video streams can be transcoded/re- quantized at intermediate peers. We deploy a double pricing solution that simultaneously incorporates the network and the relay constraints in the peer-to-peer network and compare it with a single pricing solution where the relay constraint is applied only after all the communicating peers converge to optimality. We combine our solution with two video adaptation techniques: transcoding using times 264 and scalable coding using H.264 SVC (scalable video coding) extension. Our experiment shows that the double pricing solution consistently achieves a smaller aggregate distortion for all peers over the single pricing solution.

Peer-to-peer (P2P) is a powerful platform for a variety of multimedia streaming applications over the Internet such as video-on-demand, video conferencing, live broadcasting, etc. A P2P system is extremely cost-effective since it utilizes the resources (CPU cycles, storage space, and uplink bandwidth) of peer machines.The decentralized and shared bandwidth nature of a P2P network, therefore, makes it an effective choice for implementing video conferencing applications. In this work, Vanets is presented , a P2P based video conferencing system that takes advantage of transcoding to optimally allocate streaming rates for all participating peers. The solution presented in this paper distinguishes between active and passive participants and enhances the video quality of the active participant.

The use of wireless sensor networks as a means for providing remote healthcare provides a unique opportunity to reduce the healthcare cost through more efficient use of clinical resources and earlier detection of medical conditions. Despite the initial promising results, there remain significant obstacles to apply this technology to the practical medical care context. In this paper, we investigate one of the critical issues-how to assure the timely and reliable delivery of life-critical medical data in the pervasive patient monitoring networks. In this paper, our study is based on the remote health monitoring system CareNet which is built on top of a two-tier wireless sensor networks. In particular, we present an integrated admission control and routing solution to ensure the quality of admitted sensor delivery services. Using an optimization-based approach, our solution can maximally utilize the scarce wireless resource and satisfy the monitoring service requirements from the most number of patients. The novelty of our approach come from its patient activity awareness, which is used to provide more accurate estimation of the network capacity and worst-case assurance of the service quality under all patient movement scenarios. Extensive experiment and simulation results are presented to validate our proposed solution.

This paper addresses the problem of optimal rate allocation for video streaming in a multi-path peer-to-peer mesh network. We present a distributed rate allocation algorithm that minimizes the total rate distortion among receiving peers. The scheme assumes that video streams can be transcoded/re-quantized at intermediate peers. We deploy a double pricing solution that simultaneously incorporates both the network and the relay constraints. We compare it with a single pricing solution where the relay constraint is applied only after all the communicating peers have converged. Our simulation shows that the double pricing solution consistently achieves a smaller aggregate distortion for all peers in comparison to the single pricing solution and thus achieves higher video quality.

Layered streaming is an effective solution to address receiver heterogeneity in a peer-to-peer (P2P) network. This paper addresses the problem of rate allocation for layered video stream in p2p mesh networks. We present a distributed rate allocation algorithm that achieves close to optimal layer allocation among peers receiving the same video. We use load balancing technique that evenly distributes layer requests to a parent peer. Weight based layer allocation technique ensures that a child peer with higher children receives higher priority in servicing layer allocation request from its parents. Results show that for up to seven layers streamed by a server, the algorithm maintains a layer delivery ratio of 88% or more among all peers in a network.

Recent advances in wireless sensor technology facilitate the development of remote healthcare systems, which can significantly reduce the healthcare cost. Despite the initial promising results, there remain many obstacles to apply this technology to the practical medical care context. One of the critical issues is to assure the timely and robust delivery of the life-critical medical data in the resource-constrained wireless sensor networking environment. This paper addresses this issue and presents a quality of service (QoS) support mechanism for wireless remote healthcare system, which integrates XML-based QoS specification, patient admission policy, and differentiated scheduling and queue management. The proposed QoS support mechanism is implemented in CareNet, our wireless sensor system for remote healthcare. Extensive performance study is presented to validate and evaluate our solution.

This paper presents the measurement study of locality-aware P2P solutions over real-world Internet autonomous systems (AS) topology. By using the accesses of nodes of PlanetLab testbed, we create a detailed AS-level map including the end-to-end path of all nodes, as well as the relationship of all involved ASes. Based on this map, we evaluate the performance of a set of locality-aware P2P solutions, including an optimal solution guaranteeing the minimum AS hop count, as well as modified BitTorrent system with locality-awareness built into its neighbor selection, peer choking/unchoking, and piece selection processes. Our findings suggest that locality-awareness can help existing P2P solution to significantly decrease load on Internet, and achieve shorter downloading time. By comparing the performance of different kinds of locality-aware and traditional BitTorrent systems, we also point out the necessity to tradeoff between the goals of optimizing AS-related performance and achieving fairness among peers such as intra-AS traffic and peer burden fairness.

A unique challenge in P2P network is that the peer dynamics (departure or failure) cause unavoidable disruption to the downstream peers. While many works have been dedicated to consider fault resilience in peer selection, little understanding is achieved regarding the solvability and solution complexity of this problem from the optimization perspective. To this end, we propose an optimization framework based on the generalized flow theory. Key concepts introduced by this framework include resilience factor, resilience index, and generalized throughput, which collectively model the peer resilience in a probabilistic measure. Under this framework, we divide the domain of optimal peer selection along several dimensions including network topology, overlay organization, and the definition of resilience factor and generalized flow. Within each subproblem, we focus on studying the problem complexity and finding optimal solutions. Simulation study is also performed to evaluate the effectiveness of our model and performance of the proposed algorithms.

Traffic routing plays a critical role in determining the performance of a wireless mesh network. To investigate the best solution, existing work proposes to formulate the mesh network routing problem as an optimization problem. In this problem formulation, traffic demand is usually implicitly assumed as static and known a priori. Contradictorily, recent studies of wireless network traces show that the traffic demand, even being aggregated at access points, is highly dynamic and hard to estimate. Thus, in order to apply the optimization-based routing solution into practice, one must take into account the dynamic and unpredictable nature of wireless traffic demand. This paper presents an integrated framework for network routing in multi-radio multi-channel wireless mesh networks under dynamic traffic demand. This framework consists of two important components: traffic estimation and routing optimization. By analyzing the traces collected at wireless access points, the traffic estimation component predicts future traffic demand based on its historical value using time-series analysis, and represents the prediction result in two forms - mean value and statistical distribution. The optimal mesh network routing strategies then take these two forms of traffic demand estimations as inputs. In particular, two routing algorithms are proposed based on linear programming which consider the mean value and the statistical distribution of the predicted traffic demands, respectively. The trace-driven simulation study demonstrates that our integrated traffic estimation and routing optimization framework can effectively incorporate traffic dynamics in mesh network routing, where both algorithms outperform the shortest path algorithm in about 80% of the test cases.

Recent theoretical and simulation-based studies have confirmed the tremendous benefit of peer-to-peer (P2P)communication at reducing the cost of running a VoD service.To date, very limited effort has been paid to validate the concept of peer-assisted VoD service, especially in terms of system implementation and service deployment. In this paper, we present the case study of a peer-assisted video-on-demand (VoD) system. We designed and developed Bit-Tube, a BitTorrent-compliant VoD system. By combining client/server and P2P downloading, it supports seamless transition across the spectrum from pure client-server mode to BitTorrent mode. Within this framework, we experiment with a series of piece picking policies to enhance BitTubepsilas support to video streaming and promote locality-aware P2P downloading. We evaluate our system over PlanetLab,which hosts the user-side component of the BitTube system and emulates the global-scale user requests to the VoD service.

Traffic routing plays a critical role in determining the performance of a wireless mesh network. To investigate the best solution, existing work proposes to formulate the mesh network routing problem as an optimization problem. In this problem formulation, traffic demand is usually implicitly assumed as static and known a priori. Contradictorily, recent studies of wireless network traces show that the traffic demand, even being aggregated at access points, is highly dynamic and hard to estimate. Thus, in order to apply the optimization-based routing solution in practice, one must take into account the dynamic and uncertain nature of wireless traffic demand. There are two basic approaches to address the traffic uncertainty in network routing: (1) predictive routing which infers the traffic demand with maximum possibility based in its history and optimizes the routing strategy based on the predicted traffic demand and (2) oblivious routing which considers all the possible traffic demands and selects the routing strategy where the worst-case network performance could be optimized. This paper conducts a systematic comparison study of these two approaches based on the extensive simulation study over a variety of network and traffic scenarios. It identifies the key factors of the network topology and traffic profile that affect the performance of each routing strategy and provides guidelines towards the strategy selection in mesh network routing under uncertain traffic demands.

This paper considers two important issues for video sensor networks: (1) timely delivery of captured video stream and (2) energy-efficient network design. Based on network calculus, it presents a unified analytical framework that is able to quantitatively weigh the tradeoff between these two factors. In particular, it derives the service curve, buffer and delay bound under single-hop and multi-hop scenarios for video sensor networks under power management. To the best of our knowledge, this is the first work that extends the network calculus theory to the domain of wireless network with the consideration of power management and wireless interference. Our analysis has been validated through experiments conducted on a video sensor network testbed.

High-throughput P2P streaming relies on peer selection, the strategy a peer uses to select other peer(s) as its parent(s) of streaming. Although this problem has been thoroughly investigated in the classical optimization framework, it still remains unaddressed as how to sustain throughput competitive to the optimum under highly dynamic peer churning. We propose an online distributed peer selection algorithm based on "shortest- path" routing where the overlay edge length is an asymptotic function of its traffic load. This basic algorithm is further extended under practical settings such as multi-parent streaming, admission control, delay constraint, and simplified topology. In all above settings, we prove approximation bound of our algorithm to the optimal throughput. Through evaluation under different topological setups and peer churning sequences, we show our solution to consistently deliver competitive throughput, which greatly outperform its theoretical bound.

Multicast is an important communication paradigm, also a problem well known for its difficulty (NP-completeness) to achieve certain optimization goals, such as minimum network delay. Recent advances in network coding has shed a new light onto this problem. In network coding, forwarding nodes can perform arbitrary operations on data received, other than forwarding or replicating, to enhance throughput of a multicast session. In this paper, we show that with the aid of network coding, the once intractable optimal multicast routing problem becomes tractable. In this problem, given a set of multicast sessions and their traffic demands, one tries to route the multicast traffic regarding various objectives, such as to minimize overall delay, or to maximize the battery life of each node. We further show that his problem can be solved in a distributed fashion: each node akes its own routing decisions based on periodic updating information from neighboring nodes. We prove that starting from any initial routing assignment, the proposed distributed routing algorithm is able to converge to the point where the value of the objective function is optimized. Our solution can be fit into a variety of networks to achieve different optimization goals. The example in this paper is maximum lifetime routing in multi-hop wireless network.

Layered streaming is an effective solution to address the receiver heterogeneity in peer-to-peer (P2P) multimedia distribution. This paper targets a fundamental challenge in this application, i.e., how to find optimal routing structure maximizing receiver throughput and achieving intra-layer and inter-layer fairness. We formulate the problem using the multicommodity flow theory, and propose a series of routing algorithms that fully explore the tradeoff between theoretical optimality and practicability. For each algorithm, we have proved its optimality to achieve maximum throughput under fairness constraint, or approximation bound to the optimal rate. Experimental results confirm our algorithms to greatly outperform their theoretical bounds.

In a wireless network, data transmission suffers from varied signal strengths and channel bit error rates. To ensure successful packet reception under different channel conditions, automatic bit rate control schemes are implemented to adjust the transmission bit rates based on the perceived channel conditions. This leads to a wireless network with diverse bit rates. On the other hand, TCP is unaware of such rate diversity when it performs flow rate control in wireless networks. Experiments show that the throughput of flows in a wireless network are driven by the one with the lowest bit rate, (i.e., the one with the worst channel condition). This does not only lead to low channel utilization, but also fluctuated performance for all flows independent of their individual channel conditions. To address this problem, we conduct an optimization-based analytical study of such behavior of TCP. Based on this optimization framework, we present a joint flow control and active queue management solution. The presented channel-aware active queue management (CA-AQM) provides congestion signals for flow control not only based on the queue length but also the channel condition and the transmission bit rate. Theoretical analysis shows that our solution isolates the performance of individual flows with diverse bit rates. Further, it stabilizes the queue lengths and provides a time-fair channel allocation. Test- bed experiments validate our theoretical claims over a multi-rate wireless network testbed.

P2P (peer-to-peer) technology has proved itself an efficient and cost-effective solution to support large-scale multimedia streaming. Different from traditional P2P applications, the quality of P2P streaming is strictly determined by performance metrics such as streaming delay. To meet these requirements, previous studies resorted to intuitions and heuristics to construct peer selection solutions incorporating topology and proximity concerns. However, the impact of proximity-aware methodology and delay tolerance of peers on the scalability of P2P system remains an unanswered question. In this paper, we study this problem via an analytical approach. To address the challenge of incorporating Internet topology into P2P streaming analysis, we construct a H-sphere network model which maps the network topology from the space of discrete graph to the continuous geometric domain, meanwhile capturing the the power-law property of Internet. Based on this model, we analyze a series of peer selection methods by evaluating their performance via key scalability metrics. Our analytical observations are further verified via simulation on Internet topologies.

Wireless mesh networks have attracted increasing attention and deployment as a high-performance and low-cost solution to last-mile broadband Internet access. Network routing plays a critical role in determining the performance of a wireless mesh network. To study the best mesh network routing strategy which can maximize the network throughput while satisfying the fairness constraints, existing research proposes to formulate the mesh network routing problem as an optimization problem. These works usually make ideal assumptions such as known static traffic input. Whether they could be applied for practical use under the highly dynamic and uncertain traffic in wireless mesh network is still an open issue. The main objective of this paper is to understand the effects of traffic uncertainty in wireless mesh networks and consider these effects in throughput maximization routing. It identifies the appropriate optimization framework that could integrate the statistical user traffic demand model into a tractable throughput maximization problem. The trace-driven simulation study demonstrates that our algorithm can effectively incorporate the traffic demand uncertainty in routing optimization, and outperform the throughput maximization routing which only considers static traffic demand.

The dynamic nature of mobile ad hoc networks poses fundamental challenges to the design of service composition schemes that can minimize the effect of service disruptions. Although improving reliability has been a topic of extensive research in mobile ad hoc networks, little work has considered service deliveries spanning multiple components. Moreover, service composition strategies proposed for wireline networks are poorly suited for wireless ad hoc networks due to their highly dynamic nature. This paper proposes a new service composition and recovery framework designed to achieve minimum service disruptions for mobile ad hoc networks. The framework consists of two-tiers: service routing, which selects the service components, and network routing, which finds the network path that connects these service components. Our framework is based on the disruption index, which is a novel construct that characterizes different aspects of service disruptions, including frequency and duration. For ad hoc networks with known mobility plan, we formulate the problem of minimum-disruption service composition and recovery (MDSCR) as a dynamic programming problem and give its optimal solution. Based on the derived analytical insights, we present our MDSCR heuristic algorithm for ad hoc networks with uncertain node mobility. This heuristic algorithm approximates the optimal solution with one-step lookahead prediction, where service link lifetime is predicted using linear regression. We evaluate the performance of our algorithm via simulation study conducted under various network environments.

There is an increasing demand to introduce adaptive capabilities in distributed real-time and embedded (DRE) systems that execute in open environments where system operational conditions, input workload, and resource availability cannot be characterized accurately a priori. To meet these needs, this paper presents the hierarchical distributed resource-management architecture (HiDRA), which provides adaptive resource management using control-the ore tic techniques that adapt to workload fluctuations and resource availability. In contrast to adaptive control techniques that manage only one type of system resource, HiDRA features a hierarchical control scheme that manages both bandwidth and processor utilization simultaneously. This paper presents three contributions to research in adaptive resource management for DRE systems. First, we describe the structure and functionality of HiDRA. Second, we present an analytical model of HiDRA that formalizes its control theoretic behavior and present analytical performance guarantees. Third, we evaluate the performance of HiDRA via experiments on a representative DRE system that performs distributed target tracking in real-time. Our analytical and empirical results indicate that HiDRA yields predictable, stable, and high system performance, even in the face of changing workload.

Video sensor network is evolving from an isolated system to an integral component of the global information infrastructure. In this paper, we argue that when video sensor network becomes a public information source on the Internet, DRM (digital rights management) must be enforced, due to the sensitivity and the privacy natures of sensor content. Moreover, existing DRM solutions do not suffice because the explicit one-to-one mapping between content producer and consumer does not apply in the sensor network domain. We propose a DRM-enabled content service architecture for video sensor network. Within this architecture, we propose a binary-tree-based hierarchical key generation scheme for data encryption, and adopt a label-guided watermarking strategy to address the unique challenges of video sensor content. We present the evaluation results of our solution based on a preliminary video sensor testbed system

In this paper, the traffic confidentiality and study of the traffic pattern concealment problem via routing control is focused. First, the number of nodes in a WMN is limited. Second, traffic forwarding relationship among nodes is strongly dependent on their locations and the network topology, which is static and known a priori in WMN. To better utilize the wireless channel resource and enhance the data delivery performance, a short path is usually selected. In light of these problems, it is aimed to design a light weight traffic privacy preserving mechanism for WMN. The penalty-based routing algorithm is proposed to achieve the goal of hiding traffic pattern by exploiting the richness of available paths between two nodes in WMN. The algorithm operates in three phases, path pool generation, candidate path selection and individual packet routing. These results show that with this algorithm, the destination node is able to consistently limit the proportion of mutual information it shares with the observing nodes.

The shared-medium multihop nature of wireless ad hoc networks poses fundamental challenges to the design of effective resource allocation algorithms that are optimal with respect to resource utilization and fair across different network flows. None of the existing resource allocation algorithms in wireless ad hoc networks have realistically considered end-to-end flows spanning multiple hops. Moreover, strategies proposed in wireline networks are not applicable in the context of wireless ad hoc networks, due to their unique characteristics of location-dependent contention. In this paper, we propose a new price-based resource allocation framework in wireless ad hoc networks to achieve optimal resource utilization and fairness among competing end-to-end flows. We build our pricing framework on the notion of maximal cliques in wireless ad hoc networks, as compared to individual links in traditional wide-area wireline networks. Based on such a price-based theoretical framework, we present a two-tier iterative algorithm. Distributed across wireless nodes, the algorithm converges to a global network optimum with respect to resource allocations. We further improve the algorithm toward asynchronous network settings and prove its convergence. Extensive simulations under a variety of network environments have been conducted to validate our theoretical claims.

Although initially proposed as the deployable alternative to IP multicast, the overlay network actually revolutionizes the way network applications can be built. In this paper, we study the rate allocation problem in overlay-based multirate multicast, which can be understood as a utility-based resource allocation problem. Each receiver is associated with a utility defined as a function of its streaming rate. Our goal is to maximize the aggregate utility of all receivers, subject to network capacity constraint and data constraint. The latter constraint is unique in overlay multicast, mainly due to the dual role of end hosts as both receivers and senders. We use a price-based approach to address this problem. Two types of prices, network price and data price, are generated with regard to the two constraints of the problem. A distributed algorithm is proposed, where each receiver adjusts its flow rate according to the associated network price and data price. The algorithm is proved to converge to the optimal point, where the aggregate utility of all receivers is maximized. We implement our algorithm using an end-host-based protocol. Our protocol purely relies on the coordination of end hosts to accomplish tasks originally assigned to network routers, which makes it directly deployable to the existing network infrastructure.

Abstract Cooperation in wireless ad hoc networks has twofold implications. First, each wireless node does not excessively and greedily inject traffic to the shared wireless channel. Second, intermediate nodes voluntarily relay traffic for upstream nodes towards the destination at the cost of its own private resource. Such an assumption supports almost all existing research when it comes to protocol design in ad hoc networks. We believe that without appropriate incentive mechanisms, the nodes are inherently selfish (unwilling to contribute its private resource to relay traffic) and greedy (unfairly sharing the wireless channel). In this paper, we present a price pair mechanism to arbitrate resource allocation and to provide incentives simultaneously such that cooperation is promoted and the desired global optimal network operating point is reached by convergence with a fully decentralized self‐optimizing algorithm. Such desired network‐wide global optimum is characterized with the concept of Nash bargaining solution (NBS), which not only provides the Pareto optimal point for the network, but is also consistent with the fairness axioms of game theory. We simulate the price pair mechanism and report encouraging results to support and validate our theoretical claims. Copyright © 2006 John Wiley & Sons, Ltd.

Energy efficient routing is a critical problem in multihop wireless networks due to the severe power constraint of wireless nodes. Despite its importance and many research efforts towards it, a distributed routing algorithm that maximizes network lifetime is still missing. To address this problem, we propose a novel utility-based nonlinear optimization formulation to the maximum lifetime routing problem. Based on this formulation, we further present a fully distributed, localized routing algorithm, which is proved to converge to the optimal point, where the network lifetime is maximized. Solid theoretical analysis and simulation results are presented to validate our solution.

Providing service differentiation in wireless networks has attracted much attention in recent research. Existing studies so far have focused on the design of MAC layer protocols to achieve distributed priority scheduling. While these works have been shown to achieve certain differentiation (higher throughput or lower delay for higher priority packets) at MAC layer, they did not consider the problem of service differentiation from end-to-end perspective. Moreover, these approaches did not present a formalized service differentiation model that quantifies the degree of differentiation, which is critical for service class selection and provision. This paper addresses above problems by introducing a clear service differentiation model, proportional service differentiation, to the domain of wireless network which targets at providing proportional delay differentiation in wireless LAN. Due to the unique characteristic of distributed medium sharing, the scheduling algorithm employed in wireline networks can not be applied directly to the context of the wireless network. We argue that delay differentiation in wireless LAN can be only achieved through a joint packet scheduling at network layer and distributed coordination at MAC layer. Hereby, we present a distributed waiting time priority scheduling (DWTP) algorithm which is deployed on a cross-layer architecture. DWTP consists of two tiers: an intra-node predictive WTP scheduler at network layer and an inter-node priority-based distributed coordination at MAC layer. These two tiers coordinate via cross-layer priority mapping to achieve proportional delay differentiation. Simulation results show that the cross-layer DWTP algorithm can effectively achieve proportional delay differentiation in wireless LAN.

Although initially proposed as the deployable alternative to IP multicast, overlay multicast actually offers us great flexibilities on QoS-aware resource allocation for network applications. For example, in overlay multicast streaming, (1) the streaming rate of each client can be diversified to better accommodate network heterogeneity, through various end-to-end streaming adaptation techniques; and (2) one can freely organize the overlay session by rearranging the multicast tree, for the purpose of better resource utilization and fairness among all clients. The goal of this paper, is to find the max-min rate allocation in overlay multicast, which is pareto-optimal in terms of network resource utilization, and max-min fair. We approach this goal in two steps. First, we present a distributed algorithm, which is able to return the max-min rate allocation for any given overlay multicast tree. Second, we study the problem of finding the optimal tree, whose max-min rate allocation is optimal among all trees. After proving its NP-hardness, we propose a heuristic algorithm of overlay multicast tree construction. A variation of the heuristic is also designed to handle the dynamic client join/departure. Both of them have approximation bound of 1/2 to the optimal value. Experimental results show that they achieve high average throughput, almost saturate link utilization, and consistent min-favorability.

Abstract Providing service differentiation in wireless networks has attracted much attention in recent research. Existing studies so far have focused on the design of differentiated media access algorithms. Some quality of service (QoS) metrics, such as queueing delay cannot be completely addressed by these approaches. Moreover, without a formalized service differentiation goal that quantifies the outcome of differentiation, the performance of most of the approaches fluctuates, especially in short time‐scales. This paper addresses above problems by introducing the concept of proportional service differentiation, to the domain of wireless network and focuses on providing proportional delay differentiation in wireless LANs. Due to the unique characteristic of distributed medium sharing, the scheduling algorithm employed in wireline networks can not be applied directly to the context of wireless LANs. We argue that delay differentiation in wireless LAN can only be achieved through a joint packet scheduling at the network layer and distributed coordination at the media access control (MAC) layer. Therefore, we present a cross‐layer waiting time priority (CWTP) scheduling algorithm. CWTP consists of two tiers: an intra‐node waiting time priority (WTP) scheduler at the network layer and an inter‐node distributed coordination function at the MAC layer. These two tiers coordinateviaa mapping function, which maps the normalized waiting time at the network layer to the backoff time at the MAC layer. Two mapping schemes, namely linear mapping and piecewise linear mapping, are presented and evaluated in this paper. Extensive simulation results show that the CWTP algorithm can effectively achieve proportional delay differentiation in wireless LANs. Copyright © 2004 John Wiley & Sons, Ltd.

Improving TCP performance has long been the focus of many research efforts in mobile ad hoc networks (MANET). In this paper, we address one aspect of this endeavor: how to properly set TCP's congestion window limit (CWL) to achieve optimal performance. Past research has shown that using a small CWL improves TCP performance in certain scenarios [M. Gerla et al., Feb. 1999], [Z. Fu et al., Apr. 2003], however, no comprehensive study has been given. To this end, we turn the problem of setting TCP's optimal CWL into identifying the bandwidth-delay product (BDP) of a path in MANET. We first show and prove that, independent of the MAC layer protocol being used, the BDP of a path in MANET cannot exceed the round-trip hop-count (RTHC) of the path. We further refine this upper bound based on the IEEE 802.11 MAC layer protocol, and show that in a chain topology, a tighter upper bound exists, which is approximately 1/5 of the RTHC of the path. Based on this tighter bound, we propose an adaptive CWL setting strategy to dynamically adjust TCP's CWL according to the current RTHC of its path. Using ns-2 simulations, we show that our simple strategy improves TCP performance by 8% to 16% in a dynamic MANET environment.

The paper targets the problem of optimal resource allocation in overlay multicast, which poses both theoretical and practical challenges. Theoretically, resource allocation among overlay flows is not subject to the network capacity constraint but also the data constraint, mainly due to the dual role of end hosts as both receivers and senders. Practically, existing distributed resource allocation schemes assume the network links to be capable of measuring flow rates, calculating and communicating price signals, none of which actually exists in the Internet today. We address these challenges as follows. First, we formalize the problem using nonlinear optimization theory, which incorporates both network constraint and data constraint. Based on our theoretical framework, we propose a distributed algorithm, which is proved to converge to the optimal point, where the aggregate utility of all receivers is maximized. Second, we propose an end-host-based solution, which relies on the coordination of end hosts to accomplish tasks originally assigned to network links. our solution can be directly deployed without any changes to the existing network infrastructure.

The performance of ad hoc routing protocols will significantly degrade, if there are malfunctioned nodes in the network. Fault tolerant routing protocols address this problem by exploring the network redundancy through multipath routing. Designing an effective and efficient fault tolerant routing protocol is inherently hard, because the problem is NP-complete and the precise path information is unavailable. This paper solves this problem by presenting an end-to-end estimation-based fault tolerant routing algorithm E/sup 2/FT. E/sup 2/FT deploys two complementary processes: route estimation and route selection. Through end-to-end performance measurement, the route estimation process gives improving estimation results via iterations. Based on these estimation results, the route selection process decides a multipath route for packet delivery. The route selection is refined progressively with the increasingly accurate estimation result using "confirmation" and "dropping" procedures. Through theoretical analysis and simulation, we show E/sup 2/FT can achieve a high packet delivery rate with acceptable overhead.

In multi-hop wireless ad-hop networks, designing energy-efficient routing protocols is critical since nodes are power-constrained. However, it is also an inherently hard problem due to two important factors: First, the nodes may be mobile, demanding the energy-efficient routing protocol to be fully distributed and adaptive to the current states of nodes; Second, the wireless links may be uni-directional due to asymmetric power configurations of adjacent nodes. In this paper, we propose a location-aided power-aware routing protocol that dynamically makes local routing decisions so that a near-optimal power-efficient end-to-end route is formed for forwarding data packets. The protocol is fully distributed such that only location information of neighboring nodes are exploited in each routing node. Through rigorous theoretical analysis for our distributed protocol based on greedy algorithms, we are able to derive critical global properties with respect to end-to-end energy-efficient routes. Finally, preliminary simulation results are presented to verify the performance of our protocol.

In ad-hoc networks, geographical routing protocols take advantage of location information so that stateless and efficient routing is feasible. However such routing protocols are heavily dependent on the existence of scalable location management services. We present a novel scheme to perform scalable location management. With any location management schemes, a specific node, A, in the network trusts a small subset of nodes, namely its location servers, and periodically updates them with its location. Our approach adopts a similar strategy, but a different and original approach to select such location servers. First, we present a selection algorithm used to designate location servers of a node by its identifier. Second, we propose a hierarchical addressing model for mobile ad-hoc networks, where node locations could be represented at different accuracy levels. With this approach, different location servers may carry location information of different levels of accuracy and only a small set of location servers needs to be updated when the node moves. Through rigorous theoretical analysis, we are able to show that the control message overhead is bounded under our scheme. Finally, simulation results are presented to demonstrate the performance of our location management scheme.