Nextgeneration optical metroaccess networks are
expected to support endtoend virtual network slices for critical
5G services. However, disasters affecting physical infrastructures
upon which network slices are mapped can cause significant
disruption in these services. Operators can deploy recovery units
or trucks to restore services based on slice requirements. In
this study, we investigate the problem of sliceaware service
restoration in metroaccess networks with specialized recovery
trucks to restore services after a disaster failure. We model
the problem based on classical vehiclerouting problem to find
optimal routes for recovery trucks to failure sites to provide
temporary backup service until the network components are repaired.
Our proposed sliceaware servicerestoration approach is
formulated as a mixed integer linear program with the objective
to minimize penalty of service disruption across different network
slices.We compare our sliceaware approach with a sliceunaware
approach and show that our proposed approach can achieve
significant reduction in servicedisruption penalty
more »
« less
PopulationAware Relay Placement for Wireless MultiHop Based Network Disaster Recovery
Network disaster recovery is one of the greatest concerns for Mobile Network Operators (MNOs) and first responders during largescale natural disasters such as earth quakes. In many recent studies, wireless multihop networking has been demonstrated as an effective technique to quickly and efficiently extend the network coverage during disasters. In this paper, we specifically address the network deployment problem by proposing the PopulationAware Relay Placement (PARP) solution, which seeks the efficient deployment of a limited number of relays such that population coverage is maximized in the scenario of network disaster recovery. We provide a graphbased modeling and prove its NPhardness accordingly. In order to efficiently solve this problem, we propose a heuristic solution, which is constructed in two steps. We first design a simple algorithm based on a disk graph to determine the Steiner locations, which is the biggest challenge in this problem. Then, we formulate the problem as an integer programming problem, which is inspired by the formulation of PrizeCollecting Steiner Tree (PCST). Thus, the integer problem is solved by exploring the similarity of the existing algorithm for PCST. To evaluate the proposed solution extensively, we present numerical results on both realworld and random scenarios, which validate the effectiveness of the proposed solution and show substantial improvement by comparing to the previous one.
more »
« less
 Award ID(s):
 1461886
 NSFPAR ID:
 10098763
 Date Published:
 Journal Name:
 GLOBECOM 2017  2017 IEEE Global Communications Conference
 Page Range / eLocation ID:
 1 to 6
 Format(s):
 Medium: X
 Sponsoring Org:
 National Science Foundation
More Like this


We study the multilevel Steiner tree problem: a generalization of the Steiner tree problem in graphs where terminals T require varying priority, level, or quality of service. In this problem, we seek to find a minimum cost tree containing edges of varying rates such that any two terminals u, v with priorities P(u), P(v) are connected using edges of rate min{P(u),P(v)} or better. The case where edge costs are proportional to their rate is approximable to within a constant factor of the optimal solution. For the more general case of nonproportional costs, this problem is hard to approximate with ratio c log log n, where n is the number of vertices in the graph. A simple greedy algorithm by Charikar et al., however, provides a min{2(ln T  + 1), lρ}approximation in this setting, where ρ is an approximation ratio for a heuristic solver for the Steiner tree problem and l is the number of priorities or levels (Byrka et al. give a Steiner tree algorithm with ρ ≈ 1.39, for example). In this paper, we describe a natural generalization to the multilevel case of the classical (singlelevel) Steiner tree approximation algorithm based on Kruskal’s minimum spanning tree algorithm. We prove that this algorithm achieves an approximation ratio at least as good as Charikar et al., and experimentally performs better with respect to the optimum solution. We develop an integer linear programming formulation to compute an exact solution for the multilevel Steiner tree problem with nonproportional edge costs and use it to evaluate the performance of our algorithm on both random graphs and multilevel instances derived from SteinLib.more » « less

In the classical Steiner tree problem, given an undirected, connected graph G=(V,E) with nonnegative edge costs and a set of terminals T⊆V, the objective is to find a minimumcost tree E′⊆E that spans the terminals. The problem is APXhard; the best known approximation algorithm has a ratio of ρ=ln(4)+ε<1.39. In this paper, we study a natural generalization, the multilevel Steiner tree (MLST) problem: given a nested sequence of terminals Tℓ⊂⋯⊂T1⊆V, compute nested trees Eℓ⊆⋯⊆E1⊆E that span the corresponding terminal sets with minimum total cost. The MLST problem and variants thereof have been studied under various names including Multilevel Network Design, QualityofService Multicast tree, GradeofService Steiner tree, and MultiTier tree. Several approximation results are known. We first present two simple O(ℓ)approximation heuristics. Based on these, we introduce a rudimentary composite algorithm that generalizes the above heuristics, and determine its approximation ratio by solving a linear program. We then present a method that guarantees the same approximation ratio using at most 2ℓ Steiner tree computations. We compare these heuristics experimentally on various instances of up to 500 vertices using three different network generation models. We also present various integer linear programming (ILP) formulations for the MLST problem, and compare their running times on these instances. To our knowledge, the composite algorithm achieves the best approximation ratio for up to ℓ=100 levels, which is sufficient for most applications such as network visualization or designing multilevel infrastructure.more » « less

null (Ed.)In the classical Steiner tree problem, given an undirected, connected graph G =( V , E ) with nonnegative edge costs and a set of terminals T ⊆ V , the objective is to find a minimumcost tree E &prime ⊆ E that spans the terminals. The problem is APXhard; the bestknown approximation algorithm has a ratio of ρ = ln (4)+ε < 1.39. In this article, we study a natural generalization, the multilevel Steiner tree (MLST) problem: Given a nested sequence of terminals T ℓ ⊂ … ⊂ T 1 ⊆ V , compute nested trees E ℓ ⊆ … ⊆ E 1 ⊆ E that span the corresponding terminal sets with minimum total cost. The MLST problem and variants thereof have been studied under various names, including Multilevel Network Design, QualityofService Multicast tree, GradeofService Steiner tree, and Multitier tree. Several approximation results are known. We first present two simple O (ℓ)approximation heuristics. Based on these, we introduce a rudimentary composite algorithm that generalizes the above heuristics, and determine its approximation ratio by solving a linear program. We then present a method that guarantees the same approximation ratio using at most 2ℓ Steiner tree computations. We compare these heuristics experimentally on various instances of up to 500 vertices using three different network generation models. We also present several integer linear programming formulations for the MLST problem and compare their running times on these instances. To our knowledge, the composite algorithm achieves the best approximation ratio for up to ℓ = 100 levels, which is sufficient for most applications, such as network visualization or designing multilevel infrastructure.more » « less

Natural disasters can result in severe damage to communication infrastructure, which leads to further chaos to the damaged area. After the disaster strikes, most of the victims would gather at the evacuation sites for food supplies and other necessities. Having a good communication network is very important to help the victims. In this paper, we aim at recovering the network from the stillalive mobile base stations to the outofservice evacuation sites by using multihop relaying technique. We propose to reconstruct the postdisaster network in a capacityaware way based on prize collecting Steiner tree. The purpose of the proposed scheme is to achieve high capacity connectivity ratio in a cost efficient way. To provide more accurate evaluation results, we evaluate the proposed scheme by using the real evacuation site and base station data in Tokyo area, and utilizing the big data analysis based postdisaster service availability model.more » « less