Search

Network update enables Software-Defined Networks (SDNs) to optimize the data plane performance. The single update focuses on processing one update event at a time, i.e., updating a set of flows from their initial routes to target routes, but it fails to handle continuously arriving update events in time incurred by high-frequency network changes. On the contrary, the continuous update proposed in “Update Algebra” can handle multiple update events concurrently and respond to the network condition changes at all times. However, “Update Algebra” only guarantees the blackhole-free and loop-free update. The congestion-free property cannot be respected. In this paper, we propose Coeus to achieve the continuous update while maintaining consistency, i.e., ensuring the blackhole-free, loop-free, and congestion-free properties simultaneously. Firstly, we establish the continuous update model based on the update operations in update events. With the update model, we dynamically reconstruct the operation dependency graph (ODG) to capture the relationship between update operations and link utilization variations. Then, we develop a composition algorithm to eliminate redundant operations in update events. To further speed up the update procedure, we present a partition algorithm to split the operation nodes of the ODG into a series of suboperation nodes that can be executed independently. The partition algorithm is proven to be optimal. Finally, extensive evaluations show that Coeus can improve the update speed by at least 179% and reduce redundant operations by at least 52% compared with state-of-the-art approaches when the arrival rate of update events equals three times per second. [ABSTRACT FROM AUTHOR]

This paper considers the fundamental problem of deployment of Unmanned Aerial VehIcles for aniSotropic monItoring Tasks (VISIT), that is, given a set of objects with determined coordinates and directions in 2D area, deploy a fixed number of UAVs by adjusting their coordinates and orientations such that the overall monitoring utility for all objects is maximized. We develop a theoretical framework to address VISIT problem. First, we establish monitoring model whose quality of monitoring (QoM is anisotropic with monitoring angle and varying with various monitoring distance. To the best of our knowledge, we are the first considering the anisotropy of monitoring angle. Then, we propose a framework consisting of area discretization and Monitoring Dominating Set (MDS) extraction to reduce the infinite solution space of VISIT to a limited one with performance bound. Finally, we model the reformulated problem as maximizing a monotone submodular function subject to a matroid constraint, and present a greedy algorithm with $1-1/e-\epsilon$ 1 - 1 / e - ε approximation ratio. We conduct both simulations and field experiments to evaluate our framework, and the results show that our algorithm outperforms comparison algorithms by at least 41.3 percent. [ABSTRACT FROM AUTHOR]

This paper studies the problem of cHarging tAsk Scheduling for direcTional wireless chargEr networks (HASTE), i.e., given a set of rotatable directional wireless chargers on a 2D area and a series of offline (online) charging tasks, scheduling the orientations of all the chargers with time in a centralized offline (distributed online) fashion to maximize the overall charging utility for all the tasks. We prove that HASTE is NP-hard. Then, we prove that a relaxed version of HASTE falls within the realm of maximizing a submodular function subject to a partition matroid constraint, and propose a centralized offline algorithm that achieves $(1-\rho)(1-\frac{1}{e})$ (1 - ρ) (1 - 1 e) approximation ratio to address HASTE where $\rho$ ρ is the switching delay of chargers. Further, we propose a distributed online algorithm and prove it achieves $\frac{1}{2}(1-\rho)(1-\frac{1}{e})$ 1 2 (1 - ρ) (1 - 1 e) competitive ratio. We conduct simulations and field experiments on a testbed consisting of eight off-the-shelf power transmitters and 8 rechargeable sensor nodes. The results show that our distributed online algorithm achieves 92.97 percent of the optimal charging utility, and outperforms the comparison algorithms by up to 15.28 percent in terms of charging utility. [ABSTRACT FROM AUTHOR]

Although the logically-centralized perspective is offered in Software-Defined Networking (SDN), the data plane is still distributed. Update commands sent by the centralized controller are executed asynchronously and independently in each switch. The timed SDN enables synchronous and coordinated update operations as each update command can be triggered by a pre-defined timestamp. Prior work on timed update mainly focuses on producing a congestion-free update sequence, whereas finding a congestion-free timed update sequence may prolong the update time. Even worse, such an update order may not exist. In this paper, we propose Chronus+, a novel timed update system that utilizes the switch buffer to shorten the update time while minimizing the switch buffer during updates. First, we formulate the Minimum Switch Buffer Problem (MSBP) as an integer linear programming and show its hardness. Then, we propose a set of efficient algorithms to solve the problem in polynomial time. Extensive evaluations in Mininet and large-scale simulations show that Chronus+ can reduce the update time by at least 17% and the switch buffer size by at least 27% compared with state-of-the-art approaches. [ABSTRACT FROM AUTHOR]

Due to the distributed and asynchronous nature in data plane, the packets can be forwarded into a loop during routing updates. Software-Defined Networks (SDNs) enable a controller to schedule the update operations of routing rules in a loop-free manner. However, the existing rule replacement mechanism cannot give an efficient solution for large-scale update scenarios. In this paper, we make use of the ingress port field in forwarding rules to design a loop-free update scheme, Inport-Matching Update (IMU), for per-flow and destination-based unicast, which significantly improves efficiency of solving update scenarios and reduces update rounds. In both our proposed and previous mechanisms, a subproblem called Rule Replacement Scheduling (RRS) problem needs to be solved and we prove that the scale of RRS problem can be reduced at least by half. Moreover, we use the inclusion-exclusion principle to rigorously prove that the probability that an RRS problem under IMU has a trivial solution, i.e., one round, is always higher than 83.7%, given a random per-flow unicast update scenario with ingress port rules. Experimental results show that our proposed Inport-Matching Update mechanism remarkably reduces the average number of rounds and runtime for solving the RRS problem compared to the existing rule replacement mechanism. [ABSTRACT FROM AUTHOR]

This paper considers the problem of practical Heterogeneous wIreless charger Placement with Obstacles (HIPO), i.e., given a number of heterogeneous rechargeable devices distributed on a 2D plane where obstacles of arbitrary shapes exist, deploying heterogeneous chargers with a given cardinality of each type, i.e., determining their positions and orientations, the combination of which we name as strategies, on the plane such that the rechargeable devices achieve maximized charging utility. After presenting our practical directional charging model, we first propose to use a piecewise constant function to approximate the nonlinear charging power, and divide the whole area into multi-feasible geometric areas in which a certain type of chargers have constant approximated charging power. Next, we propose the Practical Dominating Coverage Set extraction algorithm to reduce the unlimited solution space to a limited one by exacting a finite set of candidate strategies for all multi-feasible geometric areas. Finally, we prove the problem falls in the realm of maximizing a monotone submodular function subject to a partition matroid constraint, which allows a greedy algorithm to solve with approximation ratio of $\frac{1}{2} - \epsilon$ 1 2 - ε . We conduct experiments to evaluate the performance. Results show that our algorithm outperforms the comparison algorithms by at least 33.49 percent on average. [ABSTRACT FROM AUTHOR]

In memory computing and high-end distributed storage demand low latency, high throughput, and zero data loss simultaneously from datacenter networks. Existing reactive congestion control approaches cannot both minimize queuing latency and ensure zero data loss. A token-oriented proactive approach can achieve them together by controlling congestion even before sending data packets. However, state-of-the-art token-oriented approaches only strive to optimize network-level metrics: maximizing throughput while achieving flow-level fairness. This article answers the question of how to support objective-aware traffic scheduling in token-oriented approaches. The novelty of Token-Oriented in-network Prioritization (TOP) is that it prioritizes tokens instead of data packets. We make three contributions. Via simulations over a hypothetical TOP system, our first contribution is demonstrating the potential performance gain that can be brought by TOP. Second, we investigate the applicability of TOP. Although the overhead of enabling necessary TOP features in switches is trivial, we find that mainstream commodity datacenter switches do not support them. We hence propose a readily-deployable remedy to achieve in-network prioritization by pushing both switch and end-host hardware capacity to an extreme end. Lastly, we implement a running TOP system with Linux hosts and commodity switches, and evaluate TOP in testbeds and with large-scale simulations for various scenarios. [ABSTRACT FROM AUTHOR]

This paper concerns the problem of finding persistent items in distributed datasets, which has many applications such as port scanning and intrusion detection. To the best of our knowledge, there is no existing solution for finding persistent items in distributed datasets. In this paper, we propose DISPERSE, a probabilistic algorithm that can find persistent items in distributed datasets without collecting all the datasets. Our basic idea is that each monitor compresses each item ID in its dataset in a lossy fashion, sends the set of lossily compressed item IDs to the server, then the server recovers the IDs of the persistent items. We design the lossy compression so that given one lossily compressed item ID, the server cannot recover the item ID, but when the number of lossily compressed versions of the same item ID exceeds a threshold, which means that such items are persistent ones, the server can recover the item ID with a high probability. This threshold is exactly the threshold in the definition of persistent items. We implemented DISPERSE and evaluated its performance. In comparison with the straightforward solution, DISPERSE achieves a compression ratio of 26.5% with FNR=3.5% and FPR=0. In comparison with a developed Bloom filter based scheme and the adapted kBF and IBF schemes, our scheme can achieve 7.9, 5.7, and 6.6 times performance gains, respectively, in terms of compression ratio. [ABSTRACT FROM AUTHOR]

Today’s cellular core relies on a few expensive and dedicated hardware racks to connect the radio access network and the egress point to the Internet, which are geographically placed at fixed locations and use the specific routing policies. This inelastic architecture fundamentally leads to increased capital and operating expenses, poor application performance and slow evolution. The emerging paradigm of Network Function Virtualization (NFV) and Software Defined Networking (SDN) bring new opportunities for cellular networks, which makes it possible to flexibly deploy service chains on commodity servers and fine-grained control the routing policies in a centralized way. We present a two-stage optimization framework Plutus. The network-level optimization aims to minimize the service chain deployment cost, while the server-level optimization requires to determine which Virtualized Network Function (VNF) should be deployed onto which CPU core to balance the CPU processing capability. We formulate these two problems as two optimization programs and prove their hardness. Based on parallel multi-block ADMM, we propose a $(\delta, 2)$ -bicriteria approximation algorithm and a learning-based algorithm to address two cases whether the flow information and the resource consumption can be known as a priori, respectively. Large-scale simulations and DPDK-based OpenNetVM platform show that Plutus can reduce the capital cost by 84% and increase the throughput by 36% on average. [ABSTRACT FROM AUTHOR]