Search

Network coding (NC), when combined with multipath routing, enables a linear programming (LP) formulation for a multi-source multicast with intra-session network coding (MISNC) problem. However, it is still hard to solve using conventional methods due to the enormous scale of variables or constraints. In this paper, we try to solve this problem in terms of throughput maximization from an algorithmic perspective. We propose a novel formulation based on the extreme flow decomposition technique, which facilitates the design and analysis of approximation and online algorithms. For the offline scenario, we develop a fully polynomial time approximation scheme (FPTAS) which can find a (1 + ω) -approximation solution for any specified ω > 0. For the online scenario, we develop an online primal-dual algorithm which proves O (1) -competitive and violates link capacities by a factor of O (log ⁡ m) , where m is the link number. The proposed algorithms share an elegant primal-dual form and thereby have inherent advantages of simplicity, efficiency, and scalability. To better understand the proposed approach, we devise delicate numerical examples on an extended butterfly network to validate the effects of algorithmic parameters and make an interesting comparison between the offline and online cases. We also perform large-scale simulations on real networks to validate the effectiveness of the proposed FPTAS and online algorithm. • Extreme flow decomposition technique for intra-session network coding. • Offline FPTAS with provable approximation ratio. • Online primal-dual algorithm with provable competitive ratio. • Large-scale experiments using public datasets. [ABSTRACT FROM AUTHOR]

Scheduling independent tasks on a parallel platform is a widely-studied problem, in particular when the goal is to minimize the total execution time, or makespan (P | | C max problem in Graham's notations). Also, many applications do not consist of sequential tasks, but rather parallel tasks, either rigid, with a fixed degree of parallelism, or moldable, with a variable degree of parallelism (i.e., for which we can decide at the execution on how many processors they are executed). Furthermore, since the energy consumption of data centers is a growing concern, both from an environmental and economical point of view, minimizing the energy consumption of a schedule is a main challenge to be addressed. One can then decide, for each task, on how many processors it is executed, and at which speed the processors are operated, with the goal to minimize the total energy consumption. We further focus on co-schedules, where tasks are partitioned into shelves, and we prove that the problem of minimizing the energy consumption remains NP-complete when static energy is consumed during the whole duration of the application. We are however able to provide an optimal algorithm for the schedule within one shelf, i.e., for a set of tasks that start at the same time. Several approximation results are derived, both with discrete and continuous speed models, and extensive simulations are performed to show the performance of the proposed algorithms. • A model for a theoretical analysis of the energy consumption of a schedule for moldable and rigid tasks. • Most presented scheduling problems are NP-complete. • There exist approximation algorithms for the presented problems (from 1.59 to 3 depending on the problem). • An experimental study of the trade-off between the time complexity of the scheduler and the energy consumed by the schedule. [ABSTRACT FROM AUTHOR]

• Improved distributed approximation for Steiner tree. • Approximation algorithms for Steiner tree in the CONGEST model of distributed computing. • Steiner tree problem in network optimization. In this paper we present two deterministic distributed algorithms for the Steiner tree (ST) problem in the CONGEST model. The first algorithm computes a 2 (1 − 1 / ℓ) -approximate ST using O (S + n log ⁎ ⁡ n) rounds and O (m S + n 3 / 2) messages for a graph of n nodes and m edges, where S is the shortest path diameter of the graph and ℓ is the number of leaf nodes in the optimal ST. It improves the round complexity of the best distributed ST algorithm known so far, which is O ˜ (S + min { S t , n }) [34] , where t is the number of terminal nodes. The second algorithm improves the message complexity of the first one by dropping the additive term of O (n 3 / 2) at the expense of a logarithmic multiplicative factor in the round complexity. We also show that for graphs with S = O (log ⁡ n) , a 2 (1 − 1 / ℓ) -approximate ST can be deterministically computed using O ˜ (n) rounds and O ˜ (m) messages and these complexities almost coincide with the results of some of the singularly-optimal minimum spanning tree (MST) algorithms proposed in [15,22,37]. [ABSTRACT FROM AUTHOR]

• The placement of data and the scheduling of request are studied in edge caching. • Network unreliability and limited storage and bandwidth resources are considered. • Two algorithms with different computation complexity and cache efficiency are developed. • The experiments are conducted to evaluate the performance of proposed caching strategies. Edge caching is a prevailing media delivery technology where data is hosted at the edge nodes with computing and storage capability in close proximity to users, in order to expand the backhaul network capacity and enhance users' quality of experience (QoE). The existing work in this area often neglects the fact that large-scale distributed cache networks are not particularly reliable and many edge nodes are prone to failure. In this paper we investigate and develop a novel, cooperative caching mechanism for content placement and request routing. We aim to minimize the content access delay and achieve the optimization in polynomial time, taking into account failures in an unreliable network environment with limited edge storage and bandwidth. We introduce two optimization algorithms: 1) a primal-dual algorithm that is based on the Lagrangian dual decomposition and subgradient method, and 2) a greedy-based approximation algorithm with a proven approximation ratio. Numerical results show that the proposed algorithms outperform other comparative approaches in synthetic and real network environments, and the approximation algorithm is particularly suitable for networking scenarios with sparse node connectivity and resources in short supply. [ABSTRACT FROM AUTHOR]

Coflow is a network abstraction used to represent communication patterns in data centers. The coflow scheduling problem encountered in large data centers is a challenging NP -hard problem. Many previous studies on coflow scheduling mainly focus on the single-core model. However, with the growth of data centers, this single-core model is no longer sufficient. This paper addresses the coflow scheduling problem within heterogeneous parallel networks, which feature an architecture consisting of multiple network cores running in parallel. In this paper, two polynomial-time approximation algorithms are developed for the flow-level scheduling problem and the coflow-level scheduling problem in heterogeneous parallel networks, respectively. For the flow-level scheduling problem, the proposed algorithm achieves an approximation ratio of O (log ⁡ m / log ⁡ log ⁡ m) when all coflows are released at arbitrary times, where m represents the number of network cores. On the other hand, in the coflow-level scheduling problem, the proposed algorithm achieves an approximation ratio of O (m (log ⁡ m / log ⁡ log ⁡ m) 2) when all coflows are released at arbitrary times. Moreover, we propose a heuristic algorithm for the flow-level scheduling problem. Simulation results using synthetic traffic traces validate the performance of our algorithms and show improvements over the previous algorithm. • Algorithm achieves O (log ⁡ m / log ⁡ log ⁡ m) approximation ratio for flow-level scheduling, where m is network cores. • For coflow-level scheduling, algorithm achieves O (m (log ⁡ m / log ⁡ log ⁡ m) 2) approximation ratio. • Moreover, this paper proposes a heuristic algorithm for the flow-level scheduling problem. [ABSTRACT FROM AUTHOR]

Fog computing is an emerging paradigm that brings computing capabilities closer to distributed IoT devices, which provides networking services between end devices and traditional cloud data centers. One important mission is to further reduce the monetary cost of fog resources while meeting the ever-growing demands of multiple users. In this paper, we focus on minimizing the total cost for multiple mobile users to provide an efficient resource provisioning scheme in fog computing. The total cost includes two aspects: the replication cost and the transmission cost. We consider three cases for the resource provision problem by focusing on different cost models. First, one simple case where users can only upload one replication is discussed, and an optimal solution is proposed by converting the original problem into a bipartite graph matching. Then we consider a more complicated case in which each user can upload multiple replications on fog nodes in the resource provisioning. Specifically, two models are discussed: the 0–1 transmission cost model and the different transmission cost model. For the 0–1 transmission cost model, each user can upload multiple replications with a constant transmission cost, and one optimal greedy solution is proposed. For the different transmission cost model, the transmission cost is related to the distance of each pair of fog nodes. This problem is proven to be NP-hard. We first propose a non-adaptive algorithm which is proved to be bounded by 2 3 W + 1 3 O P T. Another 3 + ϵ -approximation algorithm is proposed based on local search, which has better performance with higher complexity. Extensive simulations also prove the efficiency of our schemes. • We consider the resource provision problem for users with cost minimization and model the identified problem by considering two types of cost: replication cost and transmission cost. We first discuss a simple case, and one optimal solution is proposed. We then consider a more complicated case in which each user can upload multiple replications on fog nodes in the provisioning process. Two models are discussed: the 0–1 transmission cost model and the different transmission cost model. • We propose an optimal solution for the 0–1 transmission cost model. Then we prove that the problem under the different transmission cost model is NP-hard. We first propose a non-adaptive algorithm which is proved to be bounded by 2 3 W + 1 3 O P T. Another 3 + ϵ -approximation algorithm is proposed based on local search, which has better performance with higher complexity. • Various simulations were conducted to compare our joint optimization methods with several state-of-the-art ones based on two real datasets: the Mobike dataset and the Microsoft GPS trajectory dataset. The results are shown from different perspectives to provide conclusions. [ABSTRACT FROM AUTHOR]

Approximation algorithms for scheduling parallel machines have been studied for decades, leading to significant progress in terms of their approximation guarantees. The algorithms that provide near optimal performance are not feasible to use in practice due to their huge execution time requirements, thus underscoring the importance of developing efficient parallel approximation algorithms with near-optimal performance guarantees that are suitable for execution on current parallel systems, such as multi-core systems. We present the design and analysis of a parallel approximation algorithm for the problem of scheduling jobs on parallel identical machines to minimize makespan. The design of the parallel approximation algorithm is based on the best existing polynomial-time approximation scheme (PTAS) for the problem. To the best of our knowledge, this is the first practical parallel approximation algorithm for the minimum makespan scheduling problem that maintains the approximation guarantees of the sequential PTAS and it is specifically designed for execution on shared-memory parallel machines. We implement and run the algorithm on a large multi-core system and perform an extensive experimental analysis on data generated from realistic probability distributions. The results show that our proposed parallel approximation algorithm achieves significant speedup with respect to both the sequential PTAS and the CPLEX-based solver that solves the mixed integer program formulation of the problem. • A parallel approximation algorithm for scheduling parallel identical machines is proposed. • The proposed algorithm has the same approximation guarantees as the sequential PTAS. • The proposed algorithm is suitable for implementation on multi-core systems. [ABSTRACT FROM AUTHOR]

We study the multi-budgeted version of the metric Survivable Network Design Problem (SND) (Jain, 2001), also known as Steiner Network problem, where besides the usual connectivity requirements (i.e., lower bound on the number edge-disjoint paths) between pre-specified pairs of points, we are also asked to satisfy a set of extra linear constraints (the budgets). Based on combinatorial properties of extreme point solutions of the natural LP relaxation of the problem and using the iterative method, we design new approximation algorithms with the following performance guarantee: if any edge participates in at most f ∈ N budgets, then we show how we can device an ( f + 2 , f + 2 ) bi-criteria approximation algorithm in polynomial time i.e., return a solution with cost at most ( 2 + f ) times the optimal one with a potential budget overflow bounded from above by the same factor. In other words, the approximation and budget violation guarantee we achieve is a linear function of the maximum frequency among all the edges in the budgets, as opposed to a function of the number of budgets themselves and this constitutes a strict improvement over the previous approaches. Our approach is flexible enough and we demonstrate how it can be used to provide a ( 4 , 4 ) bi-criteria algorithm for the Minimum Weighted Bounded Degree version of the SND problem in which we have the standard SND connectivity constraints and, additionally, for every vertex v in the graph we have an upper bound on the sum of the weights of the edges incident to that edge in any feasible solution. These problems, besides their obvious theoretical interest, have numerous real life applications from Cloud Computing to Optical Networking systems. [ABSTRACT FROM AUTHOR]

Let G = ( V , E ) be a unit disk graph corresponding to a given set P of n points in R 2 . We propose a distributed approximation algorithm to find a minimum connected dominating set of G . The maintenance of the connected dominating set constructed is fully localized. Our algorithm produces a connected dominating set of size ( 104 o p t + 52 ) , where o p t is the size of a minimum connected dominating set. The time and message complexities of our algorithm are O ( Δ ) and O ( n ) respectively, where Δ and n are the maximum node degree and number of nodes in G respectively. Our distributed approximation algorithm outperforms existing algorithms in terms of its time and message complexities. We also propose a scheduling scheme that obtains O ( Δ ) conflict-free time slots to deal with interference. [ABSTRACT FROM AUTHOR]

Peer-to-Peer systems have been introduced as an alternative to the traditional client–server scheme. Distributed Hash Tables, a type of structured Peer-to-Peer system, have been designed for massive storage purposes. In this work we model the behavior of a DHT based system, Cassandra, with focus on its fault tolerance capabilities, and more specifically, on its availability when facing two different situations: (1) transient failures, those in which a node goes off-line for a while and returns on-line maintaining its data, and (2) memory-less failures, those in which a node goes off-line and returns with no data. First, we introduce two analytical models (one for each scenario) that provide approximations to the behavior of Cassandra under different configurations, and secondly, in order to validate our models, we complete a set of experiments over a real Cassandra cluster. Experimental results confirm the validity of the proposed models of the availability of Cassandra. We also provide some examples of how these models can be used to optimize the availability configuration of Cassandra-based applications. [ABSTRACT FROM AUTHOR]

Broadcast is a fundamental operation in Wireless Sensor Networks (WSNs) and plays an important role in a communication protocol design. In duty-cycled scenarios, a sensor node can receive a message only in its active time slot, which makes it more difficult to design collision-free scheduling for broadcast operations. Recent studies in this area have focused on minimizing broadcast latency and guaranteeing that all nodes receive a broadcast message. This paper investigates the problem of Minimum Latency Broadcast Scheduling in Duty-Cycled (MLBSDC) WSNs. By using special geometric properties of independent sets of a broadcast tree, we reduce the number of transmissions, consequently reducing the possibility of collision. Allowing multiple transmissions in one working period, our proposed Latency Aware Broadcast Scheduling (LABS) scheme provides a latency-efficient broadcast schedule. Theoretical analysis proves that the scheme has the same approximation ratio and complexity as the previous best algorithm for the MLBSDC problem. Moreover, simulation shows that the new scheme achieves up to 34%, 37%, and 21% performance improvement over previous schemes, in terms of latency, number of transmissions, and energy consumption, respectively. [ABSTRACT FROM AUTHOR]

Abstract: Periodic monitoring is sufficient for sweep coverage with a small number of mobile sensor nodes, whereas a continuous monitoring with static sensor nodes is required for the coverage problem in wireless sensor networks. Finding the minimum number of mobile sensor nodes with a uniform speed to guarantee sweep coverage is NP-hard and it cannot be approximated within a factor of 2 (Li et al., 2011). In this paper we have proposed a 2-approximation algorithm for solving the sweep coverage for a given set of points of interest (PoIs). The best known approximation factor is 3 for this problem (Li et al., 2011). Modification of the algorithm is also proposed for extending lifetime of the mobile sensors, sweep coverage in the presence of obstacles and failure of mobile sensors. When all PoIs are static sensor nodes, we have proposed a distributed approximation algorithm with approximation ratio 2, where the static sensor nodes compute the number of mobile sensor nodes and their positions. We have introduced sweep coverage for a given area of interest (AoI) and proved that the problem is NP-complete. A -approximation algorithm is designed in order to solve the problem for a square region. An improvement over the approximation factor is designed for any rectangular region. Based on our simulation study we have shown that less number mobile sensor nodes are required for our point sweep coverage algorithm compared to the algorithm proposed in Du et al. (2010). [Copyright &y& Elsevier]

Abstract: The Malleable Parallel Task Scheduling problem (MPTS) is an extension of one of the most classic scheduling problems (P∥Cmax). The only difference is that for MPTS, each task can be processed simultaneously by more than one processor. Such flexibility could dramatically reduce the makespan, but greatly increase the difficulty for solving the problem. By carefully analyzing some existing algorithms for MPTS, we find each of them suitable for some specific cases, but none is effective enough for all cases. Based on such observations, we introduce some optimization algorithms and improving techniques for MPTS, with their performance analyzed in theory. Combining these optimization algorithms and improving techniques gives rise to our novel scheduling algorithm OCM (Optimizations Combined for MPTS), a 2-approximation algorithm for MPTS. Extensive simulations on random datasets and SPLASH-2 benchmark reveal that for all cases, schedules produced by OCM have smaller makespans, compared with other existing algorithms. [Copyright &y& Elsevier]

Abstract: Fischer proposes in [T. Fischer, Optimizing the degree of minimum weight spanning trees, Technical Report 93–1338, Department of Computer Science, Cornell University, Ithaca, NY, USA, 1993] a sequential algorithm to compute a minimum weight spanning tree of maximum degree at most in time for any constant , where is the maximum degree value of an optimal solution and n is the number of nodes in the network. In the present paper, we propose a distributed version of Fischer''s sequential algorithm with time complexity , requiring messages and space per node, where is the maximum degree of an initial minimum weight spanning tree. [Copyright &y& Elsevier]

Abstract: We study the problem of scheduling unit size jobs on n processors connected by a ring. We show a distributed algorithm for this problem with an approximation ratio of . [Copyright &y& Elsevier]

Abstract: We present provably efficient parallel algorithms for sweep scheduling, which is a commonly used technique in radiation transport problems, and involves inverting an operator by iteratively sweeping across a mesh from multiple directions. Each sweep involves solving the operator locally at each cell. However, each direction induces a partial order in which this computation can proceed. On a distributed computing system, the goal is to schedule the computation, so that the length of the schedule is minimized. Due to efficiency and coupling considerations, we have an additional constraint, namely, a mesh cell must be processed on the same processor along each direction. Problems similar in nature to sweep scheduling arise in several other applications, and here we formulate a combinatorial generalization of this problem that captures the sweep scheduling constraints,and call it the generalized sweep scheduling problem. Several heuristics have been proposed for this problem; see [S. Pautz, An algorithm for parallel sweeps on unstructured meshes, Nucl. Sci. Eng. 140 (2002) 111–136; S. Plimpton, B. Hendrickson, S. Burns, W. McLendon, Parallel algorithms for radiation transport on unstructured grids, Super Comput. (2001)] and the references therein; but none of these have provable worst case performance guarantees. Here we present a simple, almost linear time randomized algorithm for the generalized sweep scheduling problem that (provably) gives a schedule of length at most times the optimal schedule for instances with n cells, when the communication cost is not considered, and a slight variant, which coupled with a much more careful analysis, gives a schedule of (expected) length times the optimal schedule for m processors. These are the first such provable guarantees for this problem. The algorithm can be extended with an additional multiplicative factor in the case when we have inter-processor communication latency, in the models of Rayward-Smith [UET scheduling with inter-processor communication delays, Discrete Appl. Math. 18 (1) (1987) 55–71] and Hwang et al. [Scheduling precedence graphs in systems with inter-processor communication times, SIAM J. Comput. 18(2) (1989) 244–257]. Our algorithms are extremely simple, and use no geometric information about the mesh; therefore, these techniques are likely to be applicable in more general settings. We also design a priority based list schedule using these ideas, with the same theoretical guarantee, but much better performance in practice; combining this algorithm with a simple block decomposition also lowers the overall communication cost significantly. Finally, we perform a detailed experimental analysis of our algorithm. Our results indicate that the algorithm compares favorably with the length of the schedule produced by other natural and efficient parallel algorithms proposed in the literature [S. Pautz, An Algorithm for parallel sweeps on unstructured meshes, Nucl. Sci. Eng. 140 (2002) 111–136; S. Plimpton, B. Hendrickson, S. Burns, W. McLendon, Parallel algorithms for radiation transport on unstructured grids, Super Comput. (2001)]. [Copyright &y& Elsevier]

Abstract: The server allocation with bounded simultaneous requests problem arises in isolated infostations, where mobile users going through the coverage area require immediate high-bit rate communications such as web surfing, file transferring, voice messaging, email and fax. Given a set of service requests, each characterized by a temporal interval and a category, an integer k, and an integer for each category c, the problem consists in assigning a server to each request in such a way that at most k mutually simultaneous requests are assigned to the same server at the same time, out of which at most are of category c, and the minimum number of servers is used. Since this problem is computationally intractable, a 2-approximation on-line algorithm is exhibited which asymptotically gives a -approximation, where . Generalizations of the problem are considered, where each request r is also characterized by a bandwidth rate , and the sum of the bandwidth rates of the simultaneous requests assigned to the same server at the same time is bounded, and where each request is characterized also by a gender bandwidth. Such generalizations contain bin-packing, multiprocessor task scheduling, and interval graph coloring as special cases, and they admit on-line algorithms providing constant approximations. [Copyright &y& Elsevier]