With the growing need for a robust network backbone to ensure uninterrupted connectivity in the face of large-scale natural disasters, we introduce the Risk Zone-Diversified Network Design (RZDD) problem. This problem requires diverse paths between source-destination pairs to be risk zone-disjoint, preventing any single disaster from disrupting overall network connectivity. Unlike previous research, we propose an innovative cost framework that considers geographically overlapping links and long-term maintenance costs, providing a comprehensive approach to cost analysis. We prove the intractability of the RZDD problem and present the Risk Zone-Diversified Network Design Algorithm (RZDD-Algorithm). In small-scale networks with a single source-destination pair, our algorithm achieves optimal outcomes. Comparative analysis shows that our method reduces costs by an average of 24% compared to an SRLG algorithm that does not consider the preference of geographically overlapping links. For multiple pairs, our approach maintains a gap ratio within 4% and 7% of optimal solutions. Furthermore, experimental evaluations on large networks demonstrate reductions of 26% and 31% compared to the SRLG baseline for single pairs. We also showcase the efficiency of our method in designing large-scale networks with multiple pairs.

Since the inception of networking technology, network topology design has been a fundamental step for any interconnected system. This classical problem has diverse forms due to various design criteria. One special criterion, the ease of monitoring the network (termed as monitorability of the network), has recently attracted much attention in the era of Industry 4.0 when many complex private networks need to be built for new industrial services. This paper extends a quantitative measure of network monitorability, k-identifiability, based on which a new form of network topology design problem is formulated. We prove that this network design problem is intractable. To solve it, we systematically analyze the topological features that are helpful for reducing the complexity of network construction. Based on the analysis, we propose a dual-heuristic method that runs two heuristics in parallel and selects the better topology as the preliminary design result. Moreover, we design an integrated algorithm that reduces unnecessary edges as the final design result. We compare our dual-heuristic algorithm with the theoretical optimal solution in small-scale networks where the brute-force search is feasible. The results demonstrate the near-optimality of our method. We also illustrate the capability of our method in designing large-scale networks.