Service function chaining (SFC), consisting of a sequence of virtual network functions (VNFs), is the de-facto service provisioning mechanism in VNF-enabled data centers (VDCs). However, for the SFC, the dynamic and diverse virtual machine (VM) traffic must traverse a sequence of VNFs possibly installed at different locations at VDCs, resulting in prolonged network delay, redundant network traffic, and large consumption of cloud resources (e.g., bandwidth and energy). Such adverse effects of the SFC, which we refer to as SFC traffic storm, significantly impede its efficiency and practical implementation.In this paper, we solve the SFC traffic storm problem by proposing AggVNF, a framework wherein the VNFs of an SFC are implemented into one aggregate VNF while multiple instances of aggregate VNFs are available in the VDC. AggVNF adaptively allocates and migrates aggregate VNFs to optimize cloud resources in dynamic VDCs while achieving the load balance of VNFs. At the core of the AggVNF are two graph-theoretical problems that have not been adequately studied. We solve both problems by proposing optimal, approximate, and heuristic algorithms. Using real traffic patterns in Facebook data centers, we show that a) our VNF allocation algorithms yield traffic costs 56.3% smaller than the latest research using the SFC design, b) our VNF migration algorithms yield 84.2% less traffic than the latest research using the SFC design, and c) VNF migration is an effective technique in mitigating dynamic traffic in VDCs, reducing the total traffic cost by up to 24.8%.

We study a new variation of the Traveling Salesman Problem (TSP) called the Budget-Constrained Traveling Salesman Problem (BC-TSP). BC-TSP is inspired by a few emerging network applications, such as robotic sensor networks. We design a prize-driven multi-agent reinforcement learning (MARL) framework to solve the BC-TSP. The main novelty of the framework, named P-MARL, is that it makes a connection between the prize maximization in BC-TSP and the cumulative reward maximization in reinforcement learning (RL) to design a more efficient MARL algorithm. In particular, P-MARL integrates the prizes available at nodes into the reward model of the MARL to guide the cooperative effort of multiple learning agents. Via extensive simulations using synthetic data of state capital cities of the U.S., we show that a) the P-MARL outperforms the existing prize-oblivious MARL work by collecting 28.8 % of more prizes under the same budget constraints, b) it takes two orders of magnitudes of shorter training time than the state-of-the-art deep reinforcement learning-based approach while collecting 45.3 % more prizes under the same budgets, and c) P-MARL collects prizes at least 91.9% of optimal obtained by the Integer Linear Programming (ILP) under different network parameters.

We aim to preserve a large amount of data generated inside base station-less sensor networks (BSNs) while considering that sensor nodes are selfish. BSNs refer to emerging sensing applications deployed in challenging and inhospitable environments (e.g., underwater exploration); as such, there do not exist data-collecting base stations in the BSN to collect the data. Consequently, the generated data has to be stored inside the BSN before uploading opportunities become available. Our goal is to preserve the data inside the BSN with minimum energy cost by incentivizing the storage- and energy-constrained sensor nodes to participate in the data preservation process. We refer to the problem as DPP: d ata p reservation p roblem in the BSN. Previous research assumes that all the sensor nodes are cooperative and that sensors have infinite battery power and design a minimum-cost flow-based data preservation solution. However, in a distributed setting and under different control, the resource-constrained sensor nodes could behave selfishly only to conserve their resources and maximize their benefit. In this article, we first solve DPP by designing an integer linear programming (ILP)-based optimal solution without considering selfishness. We then establish a game-theoretical framework that achieves provably truthful and optimal data preservation in BSNs. For a special case of DPP wherein nodes are not energy-constrained, referred to as DPP-W, we design a data preservation game DPG-1 that integrates algorithmic mechanism design (AMD) and a more efficient minimum cost flow-based data preservation solution. We show that DPG-1 yields dominant strategies for sensor nodes and delivers truthful and optimal data preservation. For the general case of DPP (wherein nodes are energy-constrained), however, DPG-1 fails to achieve truthful and optimal data preservation. Utilizing packet-level flow observation of sensor node behaviors computed by minimum cost flow and ILP, we uncover the cause of the failure of the DPG-1. It is due to the packet dropping by the selfish nodes that manipulate the AMD technique. We then design a data preservation game DPG-2 for DPP that traces and punishes manipulative nodes in the BSN. We show that DPG-2 delivers dominant strategies for truth-telling nodes and achieves provably optimal data preservation with cheat-proof guarantees. Via extensive simulations under different network parameters and dynamics, we show that our games achieve system-wide data preservation solutions with optimal energy cost while enforcing truth-telling of sensor nodes about their private cost types. One salient feature of our work is its integrated game theory and network flows approach. With the observation of flow level sensor node behaviors provided by the network flows, our proposed games can synthesize “microscopic” (i.e., selfish and local) behaviors of sensor nodes and yield targeted “macroscopic” (i.e., optimal and global) network performance of data preservation in the BSN.

Service function chaining (SFC), consisting of a sequence of virtual network functions (VNFs), provides effective and flexible network service management in a cloud computing environment. Due to the vulnerabilities of software-implemented VNFs, existing research has introduced VNF backup servers to achieve the fault-tolerance of VNFs and improve the availability of SFCs. However, they either do not consider the failures of backup servers or do not aim to maximize the availability of the entire SFC. In this paper, we study how to maximize the availability of an SFC, considering that both VNFs and backup servers can fail. We refer to the problem as SAM: service function chaining availability maximization problem. Given an SFC and a set of backup servers placed inside a cloud data center network, the failure probabilities of the VNFs and the backup servers, the goal of SAM is to assign backup servers to VNFs to maximize the availability of the SFC while satisfying the backup capacity constraint of the servers. We design a suite of optimal and efficient algorithms to solve SAM. Via extensive simulations with different network parameters, we show that our work outperforms the existing research by up to 21.7% in SFC availability, demonstrating the effectiveness of our algorithms in achieving high fault tolerance of SFC in cloud data centers.

Prize-Collecting Traveling Salesman Problem (PC-TSP) is a new variation of TSP and is defined as follows. Given a weighted complete graph$G(V, E)$where node$i\in V$has an available prize of$p_{i}$, and two nodes$s, t\in V$, the goal of the traveling salesman is to find a route from$s$to$t$such that the sum of the prizes of all the nodes visited along the route reaches a pre-set quota while the distance along the route is minimized. In this paper, we propose a multi-agent reinforcement learning (MARL) framework for the PC-TSP. Our novel observation is that prize-collecting in PC-TSP is intrinsically related to cumulative reward maximization in reinforcement learning (RL). By integrating the prizes in PC-TSP into the reward model in RL, we design an efficient and effective MARL algorithm to solve the PC-TSP. Via extensive simulations under different network and RL parameters, we show that our learning algorithm delivers an average of 65.6% of less traveling distance compared to one existing handcrafted greedy algorithm. When changing the number of agents$m$from 1 to 5, our algorithm reduces the prize-collecting learning time by up to 66.9%, demonstrating the effectiveness of multi-agent collaboration in reducing the prize-collecting learning time in PC-TSP.

Many emerging sensor network applications operate in challenging environments wherein the base station is unavailable. Data generated from such intermittently connected sensor networks (ICSNs) must be stored inside the network for some unpredictable time before uploading opportunities become available. Consequently, sensory data could overflow the limited storage capacity available in the entire network, making discarding valuable data inevitable. To overcome such overall storage overflow in ICSNs, we propose and study a new algorithmic framework calleddataaggregation foroverall storageoverflow ($\text {DAO}^{2}$). Utilizing spatial data correlation that commonly exists among sensory data,$\text {DAO}^{2}$employs data aggregation techniques to reduce the overflow data size while minimizing the total energy consumption in data aggregation. At the core of our framework are two new graph theoretical problems that have not been studied. We refer to them astravelingsalesmenplacementproblem ($\text {TSP}^{2}$) and quota traveling salesmen placement problem (Q-$\text {TSP}^{2}$). Different from the well-known multiple traveling salesman problem (mTSP) and its variants, which mainly focus on the routing of multiple salesmen initially located at fixed locations,$\text {TSP}^{2}$and Q-$\text {TSP}^{2}$must decide the placement as well as the routing of the traveling salesmen. We prove that both problems are NP-hard and design approximation, heuristic, and distributed algorithms. Our algorithms outperform the state-of-the-art data aggregation work with base stations by up to 71.8% in energy consumption.

Virtual Network Functions (VNFs) are software implementation of middleboxes (MBs) (e.g., firewalls and proxy servers) that provide performance and security guarantees for virtual machine (VM) cloud applications. In this paper, we study a new VM flow migration problem for dynamic VNF-enabled cloud data centers (VDCs). The goal is to migrate the VM flows in the dynamic VDCs to minimize the total network traffic while load-balancing VNFs with limited processing capabilities. We refer to the problem as FMDV: flow migration in dynamic VDCs. We propose an optimal and efficient minimum cost flow-based flow migration algorithm and two benefit-based efficient heuristic algorithms to solve the FMDV. Via extensive simulations, we show that our algorithms are effective in mitigating dynamic cloud traffic while achieving load balance among VNFs. In particular, all our algorithms reduce dynamic network traffic in all cases and our optimal algorithm always achieves the best traffic-mitigation effect, reducing the network traffic by up to 28% compared to the case without flow migration.

As software programs, Virtual Network Functions (VNFs) introduce new challenges to network availability due to their potential software failures. Existing models on the availability of VNF networks did not consider all the possible hardware and software failures, making them incapable of analyzing the end-to-end availability of a path. Furthermore, they did not capture the correlation between repeating nodes and links in the path, resulting in inaccurate analytical results. In this paper, we propose a new analytical model, which considers all hardware and software failures as well as the effect of repeating components, to effectively analyze the end-to-end availability of a flow path in VNF networks. On top of the analytical model, we formulate the Highest Availability Path (HAP) problem that finds the flow path with the highest end-to-end availability, and prove its NP-hardness by reduction from the Node-Weighted Steiner Tree problem. Next, we propose two algorithms for HAP: the first one based on a Steiner Tree approximation algorithm, having high time complexity and serving as a performance benchmark; the second one using a dynamic programming approach to search a multi-layer graph in polynomial time. Finally, we present extensive evaluation data to demonstrate the effectiveness of the Layered Search algorithm, which achieves comparable performance as that of the Steiner Tree based algorithm and runs faster by four orders of magnitude.

We propose a new algorithmic framework for traffic-optimal virtual network function (VNF) placement and migration for policy-preserving data centers (PPDCs). As dynamic virtual machine (VM) traffic must traverse a sequence of VNFs in PPDCs, it generates more network traffic, consumes higher bandwidth, and causes additional traffic delays than a traditional data center. We design optimal, approximation, and heuristic traffic-aware VNF placement and migration algorithms to minimize the total network traffic in the PPDC. In particular, we propose the first traffic-aware constant-factor approximation algorithm for VNF placement, a Pareto-optimal solution for VNF migration, and a suite of efficient dynamic-programming (DP)-based heuristics that further improves the approximation solution. At the core of our framework are two new graph-theoretical problems that have not been studied. Using flow characteristics found in production data centers and realistic traffic patterns, we show that a) our VNF migration techniques are effective in mitigating dynamic traffic in PPDCs, reducing the total traffic cost by up to 73%, b) our VNF placement algorithms yield traffic costs 56% to 64% smaller than those by existing techniques, and c) our VNF migration algorithms outperform the state-of-the-art VM migration algorithms by up to 63% in reducing dynamic network traffic.

In this paper we study a new algorithmic problem that maximizes the throughput of virtual machine (VM) communication in bandwidth-constrained data centers. Given a set of VM pairs with different bandwidth demands that are already placed inside cloud data centers, we study how to allocate the network bandwidth to the VM pairs to accommodate maximum number of VM communication while considering that cloud data centers have limited bandwidths. We refer to this throughput maximization problem as VMB. Due to the massive growth of cloud communication traffic in recent years and that service providers attempt to accommodate as many VM applications as possible in order to maximize their profits, VMB is an important problem to study. First we prove that VMB is NP-hard. Then we propose a suite of algorithms to solve VMB. In particular, we propose an approximation algorithm that achieves approximation ratio of$1 /\left(2 \cdot\left\lceil\frac{B}{b}\right\rceil \cdot\vert E\vert^{1 /\left(\left\lceil\frac{B}{b}\right\rceil+1\right)}+1\right)$, where$\vert E\vert$is the number of edges in the data center network,$B$is the average bandwidth capacity on edges, and$b$is the average bandwidth demand of each request. We show through simulations that our algorithms are effective in accommodating large number of VM communications under different network parameters. In particular, our approximation algorithm accommodates more than 60% of total VM communications, and up to 38% more VM pairs compared to existing research.

Virtual machine (VM) replication is an effective technique in cloud data centers to achieve fault-tolerance, load-balance, and quick-responsiveness to user requests. In this paper we study a new fault-tolerant VM placement problem referred to as FT-VMP. Given that different VM has different fault-tolerance requirement (i.e., difference VM requires different number of replica copies) and compatibility requirement (i.e., some VMs and their replicas cannot be placed into some physical machines (PMs) due to software or platform incompatibility), FT-VMP studies how to place VM replica copies inside cloud data centers in order to minimize the number of PMs storing VM replicas, under the constraints that i) for fault-tolerant purpose, replica copies of the same VM cannot be placed inside the same PM and ii) each PM has a limited amount of storage capacity. We first prove that FT-VMP is NP-hard. We then design an integer linear programming (ILP)-based algorithm to solve it optimally. As ILP takes time to compute thus is not suitable for large scale cloud data centers, we design a suite of efficient and scalable heuristic fault-tolerant VM placement algorithms. We show that a) ILP-based algorithm outperforms the state-of-the-art VM replica placement in a wide range of network dynamics and b) that all our fault-tolerant VM placement algorithms are able to turn off significant number of PMs to save energy in cloud data centers. In particular, we show that our algorithms can consolidate (i.e., turn off) around 100 PMs in a small data center of 256 PMs and 700 PMs in a large data center of 1028PMs.

We focus on policy-aware data centers (PADCs), wherein virtual machine (VM) traffic traverses a sequence of middleboxes (MBs) for security and performance purposes, and propose two new VM placement and migration problems. We first study PAL: policy-aware virtual machine placement. Given a PADC with a data center policy that communicating VM pairs must satisfy, the goal of PAL is to place the VMs into the PADC to minimize their total communication cost. Due to dynamic traffic loads in PADCs, however, above VM placement may no longer be optimal after some time. We thus study PAM: policy-aware virtual machine migration. Given an existing VM placement in the PADC and dynamic traffic rates among communicating VMs, PAM migrates VMs in order to minimize the total cost of migration and communication of the VM pairs. We design optimal, approximation, and heuristic policyaware VM placement and migration algorithms. Our experiments show that i) VM migration is an effective technique, reducing total communication cost of VM pairs by 25%, ii) our PAL algorithms outperform state-of-the-art VM placement algorithm that is oblivious to data center policies by 40-50%, and iii) our PAM algorithms outperform the only existing policy-aware VM migration scheme by 30%.

We focus on sensor networks that are deployed in challenging environments, wherein sensors do not always have connected paths to a base station, and propose a new data resilience problem. We refer to it as DRE2: data resiliency in extreme environments. As there are no connected paths between sensors and the base station, the goal of DRE2 is to maximize data resilience by preserving the overflow data inside the network for maximum amount of time, considering that sensor nodes have limited storage capacity and unreplenishable battery power. We propose a quadratic programming-based algorithm to solve DRE2 optimally. As quadratic programming is NP-hard thus not scalable, we design two time efficient heuristics based on different network metrics. We show via extensive experiments that all algorithms can achieve high data resiliences, while a minimum cost flow-based is most energy-efficient. Our algorithms tolerate node failures and network partitions caused by energy depletion of sensor nodes. Underlying our algorithms are flow networks that generalize the edge capacity constraint well-accepted in traditional network flow theory.

Many emerging sensor network applications operate in challenging environments wherein sensor nodes do not always have connected paths to the base station. Data generated from such intermittently connected sensor networks therefore must be stored inside the network for some unpredictable period of time before uploading opportunities become available. Consequently, sensory data could overflow limited storage capacity available in the entire network, making discarding valuable data inevitable. To overcome such overall storage overflow in intermittently connected sensor networks, we propose and study a new algorithmic problem called data aggregation for overall storage overflow (DA02). Utilizing spatial data correlation that commonly exists among sensory data, DAO2employs data aggregation techniques to reduce the overflow data size while minimizing the total energy consumption. To solve DAO2, we uncover a new graph theoretic problem called multiple traveling salesman walks (MTSW), and show that with proper graph transformation, the DAO2is equivalent to the MTSW. We prove that MTSW is NP-hard and design a (2-1.)-approximation q algorithm, where q is the number of nodes to visit (i.e., the number of sensor nodes that aggregate their overflow data). The approximation algorithm is based on a novel routing structure called minimum q-edge forest that accurately captures information needed for energy-efficient data aggregation. We further put forward a heuristic algorithm and empirically show that it constantly outperforms the approximation algorithm by 15% -30% in energy consumption. Finally, we propose a distributed data aggregation algorithm that can achieve the same approximation ratio as the centralized algorithm under some condition, while incurring comparable energy consumption.

Many of the applications running in cloud data center are data intensive, processing large amount of data inside the data center. File replication, which brings data files closer to the computing virtual machines (VMs), is an effective strategy that reduces data access latencies and bandwidth consumption, thus saving energy in data centers. In this paper, we formulate and study the file replication problem (FRP) in data center, with the goal of minimizing the total energy consumption of data file access inside data centers. In contrast to all the existing work of data replication in data centers, which are mainly heuristic based, we design a time-efficient approximation algorithm with performance guarantee for energy consumption in file replication. In particular, our file replication algorithm is based on a novel concept called “profit”, and optimizes over a submodular function that can be computed efficiently. Our algorithm yields the total profit of file replication at least half of what is achieved by an optimal replication solution. We also design two energy- and time-efficient heuristic file replication algorithms. Via extensive simulations using CloudSim, a popular simulation framework for cloud computing, we compare all the algorithms under different network scenarios. We show that the approximation algorithm outperforms the other two under different network parameters, while all three effectively reducing the total energy consumptions of data access in data centers.

By replicating virtual machines (VMs) and placing replica copies into data centers, not only does it distribute the requests to virtual machines into different physical machines, thus reducing server load, but also it achieves fault tolerance in risks of server failures by placing multiple copies of a VM on different servers. This paper studies the virtual machine replication problem (VMR) in data centers, with the goal of minimizing the total power consumption in this process. To guarantee that each VM is available in the event of server failure, it replicates R copies of each VM and place them into different physical machines (PMs) in the data centers, where R depends upon the server failure probability. We show that VMR is equivalent to the minimum cost flow problem, which can be solved efficiently and optimally. We further reduce the power consumption in the data center by consolidating PMs that store VM replicas and turning off inactive ones. In addition, we design two time-efficient heuristic algorithms to solve VMR. Via extensive simulations and analysis, we compare the VM replication algorithms under different data center scenarios, and show that our consolidation algorithm could further consolidate 50 PMs upon the VM replication algorithm in a data center of 1028 PMs.

We study overall storage overflow problem in sensor networks, wherein data-collecting base station is not available while more data is generated than available storage spaces in the entire network. Existing research designs a two-stage solution to solve this problem. It first aggregates overflow data to the size that can be accommodated by the available storage capacity in the network, and then offloads the aggregated data into the network to be stored. We refer to this naive two-stage solution as DAO-N. In this paper, we demonstrate that this approach does not necessarily achieve good performance. We propose a more unified method that is based upon data replication techniques, referred to as DAO-R, in order to improve the performance of DAO-N. Specifically, we design two energy-efficient data replication algorithms to integrate data aggregation and data offloading in DAO-N. We show via extensive simulations that DAO-R outperforms DAO-N by around 30% in terms of energy consumption under different network parameters.

We consider the problem of preserving data in intermittently connected sensor networks wherein sensor nodes do not always have connected paths to the base stations. The generated data is first stored inside the network before being uploaded to the base station when uploading opportunities arise. Each node has both limited energy level and limited storage space, and is associated with a probability of failure. To guarantee that at any moment, each generated data item is available for being uploaded in the presence of node failure, we propose to replicate K copies of each data item in the network, where K depends upon the node failure probability. We refer to the problem as Data K-Availability Problem (DKAP). DKAP is naturally divided into two phases: K-Availability creation and K-Availability maintenance. For K-Availability creation, we show that the problem is NP-hard for arbitrary data sizes, and that it is equivalent to minimum cost flow problem for unit data sizes. For K-Availability maintenance, we show that it is NP-hard even for unit data sizes and design a centralized greedy heuristic. We further design an efficient and low-overhead distributed algorithm, which is applicable to both phases, and show using extensive simulations that it performs close to the heuristic.

We study an energy-efficient routing problem in static ad hoc networks. The problem, referred to as maxR, is to maximize the number of routing requests that can be satisfied in the network, under the constraint that each node has finite battery power. The online version of the problem, where the sequence of messages that has to be routed over the network is not known ahead of time, has been studied extensively. In this paper, we study the offline version of the problem where the sequence of requests is pre-known. As far as we know, the offline maxR problem, its hardness and approximability have not been well studied. We show that after appropriate transformation, offline maxR is equivalent to the well-known maximum disjoint path problem, which is NP-hard. We propose a greedy algorithm called GDP that has a constant approximation ratio to the optimal algorithm. GDP can be used as a benchmark to evaluate the performance of online algorithms as it is known that the best offline algorithm performs better than any online algorithm. We then put forward a new online algorithm called MECBE to solve the online maxR problem. Simulation results show that GDP outperforms MECBE, which outperforms the state-of-the-art online algorithm OML, in terms of the number of satisfiable requests, the average energy consumption per request, and the number of energy-depleted nodes.

Data generated in sensor networks may have different importance and priority. Different types of data contribute differently for scientists to analyze the physical environment. In a challenging environment, wherein sensor nodes do not always have connected paths to the base station, and not all the data can be preserved inside the network due to severe energy constraints and storage constraints at sensor nodes, how to preserve data with maximum priority is a new and challenging problem. In this paper, we study how to preserve data that yield maximum total priorities, under the constraints that each sensor node has limited energy level and storage capacity. We design an efficient optimal algorithm and prove its optimality. The core of the problem is a maximum weighted flow problem, which is to maximize the total weight of flow in the network considering different flows have different weights. Maximum weighted flow is a generalization of the classic maximum flow problem, wherein each unit of flow has the same weight. To the best of our knowledge, our work is the first to study and solve the maximum weighted flow problem. We propose a more time efficient heuristic algorithm. Via simulation, we show that it performs comparably to the optimal algorithm and performs better than the classic maximum flow algorithm, which does not consider data priority. Finally we design a distributed data preservation algorithm based on push-relabel algorithm, analyze its time and message complexities, and empirically show that it outperforms the push-relabel distributed maximum flow algorithm in terms of the total preserved priorities.

We address the energy-efficient data redistribution problem in data-intensive sensor networks (DISNs). In a DISN, a large volume of data gets generated, which is first stored in the network and is later collected for further analysis when the next uploading opportunity arises. The key concern in DISNs is to be able to redistribute the data from data-generating nodes into the network under limited storage and energy constraints at the sensor nodes. We formulate the data redistribution problem where the objective is to minimize the total energy consumption during this process while guaranteeing full utilization of the distributed storage capacity in the DISNs. We show that the problem is APX-hard for arbitrary data sizes; therefore, a polynomial time approximation algorithm is unlikely. For unit data sizes, we show that the problem is equivalent to the minimum cost flow problem, which can be solved optimally. However, the optimal solution's centralized nature makes it unsuitable for large-scale distributed sensor networks. Thus, we design a distributed algorithm for the data redistribution problem which performs very close to the optimal, and compare its performance with various intuitive heuristics. The distributed algorithm relies on potential function-based computations, incurs limited message and computational overhead at both the sensor nodes and data generator nodes, and is easily implementable in a distributed manner. We analytically study the convergence and performance of the proposed algorithm and demonstrate its near-optimal performance and scalability under various network scenarios. In addition, we implement the distributed algorithm in TinyOS, evaluate it using TOSSIM simulator, and show that it outperforms EnviroStore, the only existing scheme for data redistribution in sensor networks, in both solution quality and message overhead. Finally, we extend the proposed algorithm to avoid disproportionate energy consumption at different sensor nodes without compromising the solution quality.

In intermittently connected sensor networks, wherein sensor nodes do not always have connected paths to the base station, preserving generated data inside the network is a new and challenging problem. We propose to preserve the data items by distributing them from storage-depleted data generating nodes to sensor nodes with available storage space and high battery energy, under the constraints that each node has limited storage capacity and battery power. The goal is to maximize the minimum remaining energy among the nodes storing the data items, in order to preserve them for maximum amount of time until next uploading opportunity arises. We first give feasibility condition of this problem by proposing and applying a Modified Edmonds-Karp Algorithm (MEA) on an appropriately transformed flow network. We then show that when feasible solutions exist, finding the optimal solution is NP-hard. We develop a sufficient condition to solve the problem optimally. We then design a centralized greedy heuristic with less time complexity than that of the optimal, which also works when feasibility can not be satisfied and network partitions arise. Via extensive simulations, we show that the heuristic performs comparably to optimal.

The benefits of caching for reducing access time to frequently needed data, in order to improve system performance, are already well-known. In this paper, a proposal for employing data caching for increasing the level of anonymity provided by an anonymity system is presented. This technique is especially effective for user sessions containing bidirectional communication, such as anonymous web browsing. A framework is first constructed for capturing the effect of attacks on anonymity systems that have the ability to serve some incoming user requests from their cache. A system-wide metric is then presented for measuring the anonymity provided by such systems. It is shown that the anonymity level of such systems rises with the amount of data caching performed by them. This behavior is illustrated in an example threshold mix network.

Data replication has been well adopted in data intensive scientific applications to reduce data file transfer time and bandwidth consumption. However, the problem of data replication in Data Grids, an enabling technology for data intensive applications, has proven to be NP-hard and even non approximable, making this problem difficult to solve. Meanwhile, most of the previous research in this field is either theoretical investigation without practical consideration, or heuristics-based with little or no theoretical performance guarantee. In this paper, we propose a data replication algorithm that not only has a provable theoretical performance guarantee, but also can be implemented in a distributed and practical manner. Specifically, we design a polynomial time centralized replication algorithm that reduces the total data file access delay by at least half of that reduced by the optimal replication solution. Based on this centralized algorithm, we also design a distributed caching algorithm, which can be easily adopted in a distributed environment such as Data Grids. Extensive simulations are performed to validate the efficiency of our proposed algorithms. Using our own simulator, we show that our centralized replication algorithm performs comparably to the optimal algorithm and other intuitive heuristics under different network parameters. Using GridSim, a popular distributed Grid simulator, we demonstrate that the distributed caching technique significantly outperforms an existing popular file caching technique in Data Grids, and it is more scalable and adaptive to the dynamic change of file access patterns in Data Grids.

The Statistical Disclosure Attack against a particular user of an anonymity system is known to be very effective in determining, after long-term observation of the system, the set of receivers that user sends messages to. This paper first presents an improvement over this attack that, by employing a weighted mean of the observed relative receiver popularity, is more accurate than the original one based upon arithmetic mean. Second, a mathematical analysis is presented of this attack on a model, in which senders blend dummy messages with real ones. It is shown that despite such sender-generated dummy cover traffic, the attack can proceed almost unhindered. The analysis substantiates earlier empirical indications of the ineffectiveness of this countermeasure.

Internet-based data intensive sensor networks (DISNs) are sensor networks wherein large volume of different types of sensory data are sensed and generated from the physical world, and queried by multiple users simultaneously. One critical issue in Internet-based DISNs is how to support multiple user queries simultaneously in an efficient manner, in terms of query response time, query loss ratio and sensor node energy consumption. In this paper, we formulate and study multi-user data query problem in DISNs and present our solution. Specifically, we present our design, implementation, and evaluation of LiteWS, a web service system aiming to enhance multi-user queries in Internet-based DISNs. We propose a simple caching technique and give an analytical model of how to reduce query loss ratio in our system. Through extensive experiments based on Crossbow IRIS motes, we evaluate the system performance of LiteWS under both correlated and uncorrelated query traffic. We show the performance with data caching is much better than the one without; particularly, the average query response time of LiteWS is improved 5 to 10 times and the query loss rate is improved 2 times.

We address the energy-efficient data redistribution problem in data intensive sensor networks (DISNs). The key question in sensor networks with large volumes of sensory data is how to redistribute the data efficiently under limited storage and energy constraints at the sensor nodes. The goal of the redistribution scheme is to minimize the energy consumption during the process, while guaranteeing full utilization of the distributed storage capacity in the DISNs. We formulate this problem as a minimum cost flow problem, which can be solved optimally. However, the optimal solution's centralized nature makes it unsuitable for large-scale distributed sensor networks. We thus design a distributed algorithm for the data redistribution problem which performs very close to the optimal, and compare its performance with various intuitive heuristics. Our proposed algorithm relies on potential function based computations, incurs limited message and computational overhead at both the sensor nodes and data generator nodes, and is easily implementable in a distributed manner. We analytically show the convergence of our algorithm, and demonstrate its near-optimal performance and scalability under various network scenarios considered. Finally, we implement our distributed algorithm in TinyOS and evaluate it using TOSSIM simulator, and show that it outperforms EnviroStore, the only existing scheme for data redistribution in sensor networks, in both solution quality and overhead messages.

We study the localization problem in sensor networks by using local angle measurement. Localization using local angle information was recently proposed as an effective localization technique, which can be used for geographical routing with guaranteed delivery. However, the existing approach is based on linear programming (LP) and can not be implemented distributedly. We propose, design, and evaluate DAL: a purely distributed localization protocol in sensor networks using local angle measurement. Localization with local angle poses unique challenge in sensor networks due to information uncertainties identified in this paper. DAL specifically addresses these challenges. Via extensive simulations using ns2 and our own simulator, we show that the performance of DAL is comparable with that of the centralized LP approach in most cases. Our preliminary results with noisy angle measurement show that DAL keeps the global geometry of the sensor network fairly well.

Sensor networks are multihop wireless networks of resource-constrained sensor nodes used to realize high-level collaborative sensing tasks. To query or access data generated by the sensor nodes, the sensor network can be viewed as a distributed database. In this paper, we develop algorithms for communication-efficient implementation of join of multiple (two or more) data streams in a sensor network. The distributed implementation of join in sensor networks is particularly challenging due to unique characteristics of the sensor networks such as limited memory and battery energy on individual nodes, arbitrary and dynamic network topology, multihop communication, and unreliable infrastructure. One of our proposed approaches, viz., the perpendicular approach (PA), is load balanced, and in fact, incurs near-optimal communication cost for the special case of binary joins in grid networks under the assumption of uniform generation of tuples across the network. We compare the performance of our designed approaches through extensive simulations on the ns2 simulator, and show that PA results in substantially prolonging the network lifetime compared to other approaches, especially for joins involving spatial constraints.

Data caching can significantly improve the efficiency of information access in a wireless ad hoc network by reducing the access latency and bandwidth usage. However, designing efficient distributed caching algorithms is nontrivial when network nodes have limited memory. In this article, we consider the cache placement problem of minimizing total data access cost in ad hoc networks with multiple data items and nodes with limited memory capacity. The above optimization problem is known to be NP-hard. Defining benefit as the reduction in total access cost, we present a polynomial-time centralized approximation algorithm that provably delivers a solution whose benefit is at least 1/4 (1/2 for uniform-size data items) of the optimal benefit. The approximation algorithm is amenable to localized distributed implementation, which is shown via simulations to perform close to the approximation algorithm. Our distributed algorithm naturally extends to networks with mobile nodes. We simulate our distributed algorithm using a network simulator (ns2) and demonstrate that it significantly outperforms another existing caching technique (by Yin and Cao [33]) in all important performance metrics. The performance differential is particularly large in more challenging scenarios such as higher access frequency and smaller memory.

Caching can significantly improve the efficiency of information access in networks by reducing the access latency and bandwidth usage. However, excessive caching can lead to prohibitive system cost and performance degradation. In this article, we consider the problem of caching a data item in a network wherein the data item is read as well as updated by other nodes and there is a limit on the number of cache nodes allowed. More formally, given a network graph, the read/write frequencies to the data item by each node, and the cost of caching the data item at each node, the problem addressed in this article is to select a set of P nodes to cache the data item such that the sum of the reading, writing (using an optimal Steiner tree), and storage cost is minimized. For networks with a tree topology, we design an optimal dynamic programming algorithm that runs in O(|V|3P2), where |V| is the size of the network and P is the allowed number of caches. For the general graph topology, where the problem is NP-complete, we present a centralized heuristic and its distributed implementation. Through extensive simulations in general graphs, we show that the centralized heuristic performs very close to the exponential optimal algorithm for small networks, and for larger networks, the distributed implementation and the dynamic programming algorithm on an appropriately extracted tree perform quite close to the centralized heuristic.

Data caching can significantly improve the efficiency of information access in a wireless ad hoc network by reducing the access latency and bandwidth usage. However, designing efficient distributed caching algorithms is non-trivial when network nodes have limited memory. In this article, we consider the cache placement problem of minimizing total data access cost in ad hoc networks with multiple data items and nodes with limited memory capacity. The above optimization problem is known to be NP-hard. Defining benefit as the reduction in total access cost, we present a polynomial-time centralized approximation algorithm that provably delivers a solution whose benefit is at least one-fourth (one-half for uniform-size data items) of the optimal benefit. The approximation algorithm is amenable to localized distributed implementation, which is shown via simulations to perform close to the approximation algorithm. Our distributed algorithm naturally extends to networks with mobile nodes. We simulate our distributed algorithm using a network simulator (ns2), and demonstrate that it significantly outperforms another existing caching technique (by Yin and Cao [30]) in all important performance metrics. The performance differential is particularly large in more challenging scenarios, such as higher access frequency and smaller memory.

P2P file sharing protocol and ad hoc wireless routing protocol share many intriguing similarities even though they are motivated on totally different basis. The goal of P2P file sharing system such as KaZaa is to locate a set of servers that contain a given file and disseminate it efficiently. The key problem of an ad hoc network routing protocol is to determine which route to take to reach a given remote host. P2P file sharing application on mobile ad hoc network (MANET) has gained more momentum as shown in the research of recent years. One natural way is to implement P2P application and ad hoc routing at different layers they belong to. In this paper, we argue that instead of stacking one on the top of the other, more work needs to be done to make both P2P file sharing protocol and MANET routing protocol interact with each other. We extract the commonalities of these two and design a common query/response framework on which ad hoc network routing and P2P file sharing are integrated seamlessly. The extensive experiments show that our strategy performs better than the layered approach in terms of traffic, average delay and packet delivery ratio.