The user demands to delay-sensitive applications have put forward new requirements for the mobile networks. Edge caching as a promising way is proposed to enhance the Quality of Service (QoS) for end users at the network edge. Given the widely distributed edge nodes, the content providers (CPs) usually prefer to integrate them with cooperative caching services, by forming a cache coalition. Although such a coalition could be beneficial as a whole, it neglects the profits of individual members, which is one major concern in forming the coalition itself. Besides, due to the poor scalability, the conventional cooperation scheme, which only considers fixed edge nodes, cannot adapt to the spatial and temporal imbalance of user requests. In this article, we tackle the problems of coalition establishment and profit allocation among the coalition members. Particularly, by adopting both fixed edge nodes and mobile vehicles as caching nodes, we propose a hybrid service provisioning framework and cooperative service caching and workload scheduling methods. To maximize the profits in managing the caching resources in the established coalition, we devise an optimization model with a mixed-integer programming (MIP), in which the QoS requirements of end users and caching capacities of each coalition member are also considered as constraints. In addition, based on the Hedonic game theory, we propose a dynamic coalition algorithm to guide each member to join or leave the coalition at each time slot out of its own profits. The experimental results demonstrate that compared to the cases only considering fixed caching nodes, our hybrid caching scheme can improve: 1) the overall profit of the coalition by 53% and 2) the average profit of individual participants by 42%, respectively.

Many hardware-based security middleboxes have been deployed in the networks to defend against different threats. However, these hardware middleboxes are hard to upgrade or migrate. The emergence of network functions virtualization (NFV), which realizes various security functions in the form of virtual network functions (VNFs), brings many benefits to network security. To improve the security level further, several VNFs are coordinated in a pre-defined order to form service function chains (SFCs). It is expected that the SFCs are embedded properly with low cost, including the VNF setup cost and the flow routing cost. In this paper, we find that when an SFC is required by multiple flows for the identical network security threats, the total cost could be reduced by embedding an aggregated service function tree (ASFT) instead of multiple independent SFCs. We formally characterize the integer programming model of this problem and prove that it is NP-hard. Then we propose a performance-guaranteed approximation algorithm and prove that the algorithm could find the optimal solution in a special case. Extensive experiments indicate that our method can reduce the total cost by$22.0\%$and$24.1\%$against two compared algorithms, respectively.

A large number of servers are interconnected using a specific datacenter network to deliver the infrastructure as a service (IaaS). Multicast can jointly utilize the network resources and further reduce the consumption of network bandwidth more than individual unicast. The source of a multicast service, however, does not need to be in a specific location as long as certain constraints are satisfied. This means the multicast can have uncertain sources, which could reduce the network resource consumption more than a traditional multicast service and further improve the quality of service. In this paper, we propose a novel reliable multicast service with uncertain sources named ReMUS. The goal is to minimize the sum of the transfer cost and the recovery cost, although finding such a ReMUS is very challenging. Thus, we design a source-based multicast method to solve this problem by exploiting the flexibility of sources when no recovery nodes exist in the network. Furthermore, we design a general multicast method to jointly exploit the benefits of uncertain sources and recovery nodes to minimize the total cost of ReMUS. We conduct extensive evaluations under Internet2 and datacenter networks. The results indicate that our methods can efficiently realize the reliable and scalable multicast with uncertain sources, irrespective of the settings of networks and multicasts. To the best of our knowledge, we are the first to study the reliable multicast service under uncertain sources.

Multicast can jointly utilize the network resources when delivering the same content to a set of destinations; hence, it can effectively reduce the consumption of network resources more than individual unicast. The source of a multicast, however, does not need to be in a specific location as long as certain constraints are satisfied. This means the multicast can have uncertain sources, which could reduce the network bandwidth consumption more than a traditional multicast. Meanwhile, a reliable multicast becomes crucial in providing reliable services for many important applications. However, a prior minimal cost forest (MCF) for such a new multicast is not designed to support reliable transmissions. In this paper, we propose a novel reliable multicast routing with uncertain sources named ReMUS. To the best of our knowledge, we are the first to study the reliable multicast under uncertain sources. The goal is to minimize the sum of the transfer cost and the recovery cost, although finding such a ReMUS is very challenging. Thus, we design a sourcebased multicast method to solve this problem by exploiting the flexibility of uncertain sources when no recovery nodes exist in the network. Furthermore, we design a general multicast method to jointly exploit the benefits of uncertain sources and recovery nodes to minimize the total cost of ReMUS. We conduct extensive evaluations based on the real topology of Internet2. The results indicate that our methods can efficiently realize the reliable and bandwidth-efficient multicast with uncertain sources, irrespective of the settings of networks and multicasts.

Recent results have made a promising case for offering oversubscribed wired data center networks (DCN) with extreme costs. Inter-rack wireless networks are drawing intensive attention to augment such wired DCNs with a few wireless links. Inspired by the promise of easy deployment and plug-and-play, we present VLCcube, a novel inter-rack wireless solution that extends the design of wireless DCN into three further dimensions: (1) all inter-rack links are wireless; (2) there is no imposition of any infrastructure-level alteration on wired production data centers; and (3) it should be plug-and-play, without any need of additional mechanical or electronic control operations. This vision, if realized, will lead to increased flexibility, reduced reconstructing cost, simplified configuration and usage, and outstanding compatibility with existing wired DCNs. Previous proposals, however, are opposed to the last two design rationales. To achieve this vision, the proposed VLCcube augments Fat-Tree, a representative DCN in production data centers, by organizing all racks into a wireless Torus structure via the emerging visible light links. We further present the topology design, hybrid routing, and flow scheduling schemes for VLCcube. Extensive evaluations indicate that VLCcube outperforms Fat-Tree significantly under the existing ECMP flow scheduling scheme, irrespective of the undergoing traffic pattern. Moreover, the performance of VLCcube can be significantly promoted by our congestion-aware flow scheduling scheme. More precisely, compared to ECMP, our flow scheduling scheme makes VLCcube achieve$\times 1.50$throughput under batched flows,$\mathrm{\times}2.21$and$\times 2.59$throughput under two different kinds of online flows.

Data sharing among multiple sampling tasks significantly reduces energy consumption and communication cost in low-power wireless sensor networks (WSNs). Conventional proposals have already scheduled the discrete point sampling tasks to decrease the amount of sampled data. However, less effort has been expended for applications that generate continuous interval sampling tasks. Moreover, most pioneering work limits its view to schedule sampling intervals of tasks on a single sensor node and neglects the process of task allocation in WSNs. Therefore, the gained efforts in prior work cannot benefit a large-scale WSN because the performance of a scheduling method is sensitive to the strategy of task allocation. Broadening the scope to an entire network, this article is the first work to maximize data sharing among continuous interval sampling tasks by jointly optimizing task allocation and scheduling of sampling intervals in WSNs. First, we formalize the joint optimization problem and prove it NP-hard. Second, we present the COMBINE operation, which is the crucial ingredient of our solution. COMBINE is a 2-factor approximate algorithm for maximizing data sharing among overlapping tasks. Furthermore, our heuristic named CATS is proposed. CATS is 2-factor approximate algorithm for jointly allocating tasks and scheduling sampling intervals so as to maximize data sharing in the entire network. Extensive empirical study is conducted on a testbed of 50 sensor nodes to evaluate the effectiveness of our methods. In addition, the scalability of our methods is verified by utilizing TOSSIM, a widely used simulation tool. The experimental results indicate that our methods successfully reduce the volume of sampled data and decrease energy consumption significantly.

Localization is an enabling technique for many sensor network applications. Real-world deployments demonstrate that, in practice, a network is not always entirely localizable, leaving a certain number of theoretically nonlocalizable nodes. Previous studies mainly focus on how to tune network settings to make a network localizable. However, the existing methods are considered to be coarse-grained, since they equally deal with localizable and nonlocalizable nodes. Ignoring localizability induces unnecessary adjustments and accompanying costs. In this study, we propose a fine-grained approach, localizability-aided localization (LAL), which basically consists of three phases: node localizability testing, structure analysis, and network adjustment. LAL triggers a single round adjustment, after which some popular localization methods can be successfully carried out. Being aware of node localizability, all network adjustments made by LAL are purposefully selected. Experiment and simulation results show that LAL effectively guides the adjustment while makes it efficient in terms of the number of added edges and affected nodes.

A fundamental goal of data center networking is to efficiently interconnect a large number of servers with the low equipment cost. Several server-centric network structures for data centers have been proposed. They, however, are not truly expandable and suffer a low degree of regularity and symmetry. Inspired by the commodity servers in today's data centers that come with dual port, we consider how to build expandable and cost-effective structures without expensive high-end switches and additional hardware on servers except the two NIC ports. In this paper, two such network structures, called HCN and BCN, are designed, both of which are of server degree 2. We also develop the low overhead and robust routing mechanisms for HCN and BCN. Although the server degree is only 2, HCN can be expanded very easily to encompass hundreds of thousands servers with the low diameter and high bisection width. Additionally, HCN offers a high degree of regularity, scalability, and symmetry, which conform to the modular designs of data centers. BCN is the largest known network structure for data centers with the server degree 2 and network diameter 7. Furthermore, BCN has many attractive features, including the low diameter, high bisection width, large number of node-disjoint paths for the one-to-one traffic, and good fault-tolerant ability. Mathematical analysis and comprehensive simulations show that HCN and BCN possess excellent topological properties and are viable network structures for data centers.

Query processing over uncertain data streams, in particular top-$(k)$ query processing, has become increasingly important due to its wide application in many fields such as sensor network monitoring and internet traffic control. In many real applications, multiple top-$(k)$ queries are registered in the system. Sharing the results of these queries is a key factor in saving the computation cost and providing real-time response. However, due to the complex semantics of uncertain top-$(k)$ query processing, it is nontrivial to implement sharing among different top-$(k)$ queries and few works have addressed the sharing issue. In this paper, we formulate various types of sharing among multiple top-$(k)$ queries over uncertain data streams based on the frequency upper bound of each top-$(k)$ query. We present an optimal dynamic programming solution as well as a more efficient (in terms of time and space complexity) greedy algorithm to compute the execution plan of executing queries for saving the computation cost between them. Experiments have demonstrated that the greedy algorithm can find the optimal solution in most cases, and it can almost achieve the same performance (in terms of latency and throughput) as the dynamic programming approach.

Recent work has demonstrated that path diversity is an effective way to improve the end-to-end performance of network applications. For every node pair in a full-mesh network with $(n)$ nodes, this paper presents a family of new approaches that efficiently identify an acceptable indirect path that has a similar to or even better performance than the direct path, hence considerably scaling the network at the cost of low per-node traffic overhead. In prior techniques, every node frequently incurs $(O(n^{1.5}))$ traffic overhead to probe the links from itself to all other nodes and to broadcast its probing results to a small set of nodes. In contrast, in our approaches, each node measures its links to only $(O(\sqrt{n}))$ other nodes and transmits the measuring results to $(O(\sqrt{n}))$ other nodes, where the two node sets of size $(O(\sqrt{n}))$ are determined by the partial sampling schemes presented in this paper. Mathematical analyses and trace-driven simulations show that our approaches dramatically reduce the per-node traffic overhead to $(O (n))$ while maintaining an acceptable backup path for each node pair with high probability. More precisely, our approaches, which are based on enhanced and rotational partial sampling schemes, are capable of increasing said probability to about 65 and 85 percent, respectively. For many network applications, this is sufficiently high such that the increased scalability outweighs such a drawback. In addition, it is not desirable to identify an outstanding backup path for every node pair in reality, due to the variable link quality.

Localization is an enabling technique for many sensor and ad-hoc network applications. Real-world deployments demonstrate that, in practice, a network is not always entirely localizable, leaving a certain number of theoretically non-localizable nodes. Previous studies mainly focus on how to tune network settings to make a network localizable; however, they are considered to be coarse-grained, since they equally deal with localizable and non-localizable nodes. Ignoring localizability induces unnecessary adjustments and accompanying costs. In this study, we propose a fine-grained approach, Localizability-aided Localization (LAL), which basically consists of three phases: node localizability testing, component tree construction, and network adjustment. LAL triggers a single round adjustment, after which some popular localization methods can be successfully carried out. Being aware of node localizability, all adjustments made by LAL are purposefully selected. Simulation results show that LAL effectively guides the adjustment.

A fundamental challenge in data centers is how to design networking structures for efficiently interconnecting a large number of servers. Several server-centric structures have been proposed, but are not truly expansible and suffer low degree of regularity and symmetry. To address this issue, we propose two novel structures called HCN and BCN, which utilize hierarchical compound graphs to interconnect large population of servers each with two ports only. They own two topological advantages, i.e., the expansibility and equal degree. In addition, HCN offers high degree of regularity, scalability and symmetry, which well conform to the modular design of data centers. Moreover, a BCN of level one in each dimension involves more servers than FiConn with server degree 2 and diameter 7, and is large enough for a single data center. Mathematical analysis and comprehensive simulations show that BCN possesses excellent topology properties and is a viable network structure for data centers.

A majority of localization approaches of wireless sensor networks rely on the measurements of inter-node distance. Errors are inevitable in distance measurements and we observe that a small number of outliers can degrade localization accuracy drastically. To deal with noisy and outlier ranging results, a straight-forward method, triangle inequality, is often employed in previous studies. However, triangle inequality has its own limitations that make itself far from accurate and reliable. In this study, we first analyze how much information are needed to identify outlier measurements. Applying rigidity theory, we propose the concept of verifiable edges and derive the conditions of an edge being verifiable. On this basis, we design a localization approach with outlier detection, which explicitly eliminates the rangings with large errors before location computation. Considering entire networks, we define verifiable graphs in which all edges are verifiable. If a wireless network meets the requirements of graph verifiability, it is not only localizable, but also outlier-resistant. Extensive simulations are conducted to examine the effectiveness of the proposed approach. The results show the remarkable improvements of location accuracy by sifting outliers.

We consider deterministic feasibility and time complexity of two fundamental tasks in distributed computing: consensus and mutual exclusion. Processes have different labels and communicate through a multiple access channel. The adversary wakes up some processes in possibly different rounds. In any round, every awake process either listens or transmits. The message of a process i is heard by all other awake processes, if i is the only process to transmit in a given round. If more than one process transmits simultaneously, there is a collision and no message is heard. We consider three characteristics that may or may not exist in the channel: collision detection (listening processes can distinguish collision from silence), the availability of a global clock showing the round number, and the knowledge of the number n of all processes. If none of the above three characteristics is available in the channel, we prove that consensus and mutual exclusion are infeasible; if at least one of them is available, both tasks are feasible, and we study their time complexity. Collision detection is shown to cause an exponential gap in complexity: if it is available, both tasks can be performed in time logarithmic in n, which is optimal, and without collision detection both tasks require linear time. We then investigate both consensus and mutual exclusion in the absence of collision detection, but under alternative presence of the two other features. With global clock, we give an algorithm whose time complexity linearly depends on n and on the wake-up time, and an algorithm whose complexity does not depend on the wake-up time and differs from the linear lower bound only by a factor O(\log^2 n). If n is known, we also show an algorithm whose complexity differs from the linear lower bound only by a factor O(\log^2 n).

With the wide applications of data streams in many fields, such as sensor network monitoring and internet traffic control, query processing over data streams has become increasingly important. In these applications, multiple aggregate queries are registered in the system, and have different sliding window sizes and different frequency upper bounds. How to share the results of these queries is a challenge. Prior work studies how to detect common tasks of these queries and share the results by computing the common tasks only once. Hybrid scheduling first addressed this problem and used the earliest-deadline-first (EDF) method. However, this work did not present a method for computing the scheduling. We formulate the scheduling problem among multiple aggregate queries with different sliding window sizes and different frequency upper bounds over data streams and propose a combination rule to classify these queries. Then, we present an efficient scheduling algorithm to decide whether a query should be executed more often than necessary, as long as the interval between two consecutive executions is less than the frequency upper bound. We also combine our scheduling algorithm with EDF to handle under loaded and overloaded situations. An experimental study shows that our scheduling algorithms are more efficient than no scheduling and EDF in terms of the number of scanned tuples, the throughput and the latency.

The ever-growing creation of data requires large-scale network storage systems. One of the key issues related such systems is how to place several petabytes of data among large number of devices. Itpsilas necessary to design a reliable, fair, adaptable data placement algorithm. All proposed approaches are oblivious to the reliability-based requirements of data in such systems. In this paper, we present a reliability-aware data placement algorithm for large-scale network storage systems. With considering the reliability-aware differences of storage devices and the reliability-based requirement of data, we formulate the problem as an integer programming to minimize the reliability cost and propose a polynomial-time algorithm to solve the problem. For each reliability level, we use a fair and adaptive data placement to distribute data. It can support arbitrary heterogeneous storage systems, distribute data in a fair way and allow an efficient adaptation to a changing set of devices. The theoretical analysis as well as the experimental study show that the approach can meet the reliability-based requirements of data, distribute data evenly among devices, and adapt well to the changes of devices.

There is a growing need for enabling reprogramming in a working sensor network. We prefer to meet the requirements remotely instead of collecting all deployed sensors. Identifying the version difference of data items, having the same key, could significantly reduce the communication overhead, because only those out-of-date items should be updated at each sensor. Previous protocols need to exchange multiple messages to identify a version difference between two items with the same key. In this paper, we propose a reliable and energy efficient data dissemination protocol (BDP) with less propagation delay. BDP uses Bloom filters to identify a version difference between two items with the same key, and find the new one between two items having the same key but different versions. Through comprehensive simulations, we show that BDP outperforms previous work in terms of energy cost and propagation delay of updating new items with high reliability