Modern communication networks employ local fast failover mechanisms in the data plane, swiftly reacting to link failures through pre-installed rerouting rules. This paper investigates resilient routing schemes that guarantee packet delivery under up to k link failures, provided the source and destination remain connected in the degraded network. While prior theoretical studies have mainly addressed static failures, where multiple links fail simultaneously and permanently, real networks often experience dynamic failures, such as transient link flapping caused by short-lived faults. We study the limits of basic and source-matched failover routing with packet-header rewriting against dynamic failures in general graphs. In basic routing, forwarding depends only on active links, incoming ports, and the destination, whereas source-matched routing additionally incorporates the source, requiring more memory (and logic) at the router. The 2-resilient source-matched routing for static failures is shown to fail under permanent but non-simultaneous failures. Moreover, even with source matching, we prove that in planar graphs k ≥ 2 resilience is impossible without bit rewriting, and in general graphs, perfect k-resilience is unachievable by only rewriting O(log k) bits. For planar graphs, we introduce ear-decomposition into basic routing and develop novel local rerouting mechanisms that tolerate dynamic failures. These yield tight 2-resilient basic routing by rewriting only one or two bits, closing the gap between lower bounds and practical routing scheme.

Escaping the station during the golden time is the main reference for managers to develop optimization strategies under floods. However, regular evacuation drills often fail to incorporate the impact of flood evolution and involve ethical considerations. The evacuation time obtained from microscopic simulations makes it difficult to meet real-time requirements, which is time-consuming and labor-intensive. To address this issue, this paper proposes a flood-induced evacuation time prediction model for metro stations, with high accuracy and strong real-time performance. The hydrodynamic model and passenger dynamics model for the metro station are built based on the Fluent and the PathFinder software, to obtain the evacuation time corresponding to different scene parameters and evacuation scales. The flood invasion speed and gate availability parameters in the scene parameters, as well as the number of passengers and the proportion of passengers with different attributes, are used as inputs to the prediction model, and the evacuation time is used as the output. The accuracy of the constructed time prediction model is mainly concentrated between 0.85 and 1.00, with a high fit between the predicted values and the actual values. An evacuation path optimization strategy is further provided to reduce evacuation time and improve evacuation safety. Taking evacuation time, evacuation path length, and human stability risk as optimization objectives, the optimal path decision under a multi-objective game is obtained. Results show that adopting an optimization strategy significantly reduces evacuation time and increases the maximum passenger capacity threshold allowed by the platform during the golden evacuation time. The proposed method provides feasible suggestions for the rapid evaluation of station evacuation efficiency and improvement of escape strategies under flood conditions.

Emerging reconfigurable optical communication technologies allow to enhance datacenter topologies with demand-aware links optimized towards traffic patterns. This paper studies the algorithmic problem of jointly optimizing topology and routing in such demand-aware networks to minimize congestion, along two dimensions: (1) splittable or unsplittable flows, and (2) whether routing is segregated, i.e., whether routes can or cannot combine both demand-aware and demand-oblivious (static) links.For splittable and segregated routing, we show that the problem is generally 2-approximable, but APX-hard even for uniform demands induced by a bipartite demand graph. For unsplittable and segregated routing, we establish upper and lower bounds of O (log m/ log log m) and Ω (log m/ log log m), respectively, for polynomial-time approximation algorithms, where m is the number of static links. We further reveal that under un-/splittable and non-segregated routing, even for demands of a single source (resp., d estina tion), the problem cannot be approximated better than $\Omega \left({\frac{{{c_{\max }}}}{{{c_{\min }}}}}\right)$ unless P=NP, where cmax(resp., cmin) denotes the maximum (resp., minimum) capacity. It remains NP-hard for uniform capacities, but is tractable for a single commodity and uniform capacities.Our trace-driven simulations show a significant reduction in network congestion compared to existing solutions.

To achieve fast recovery from link failures, most modern communication networks feature local fast failover mechanisms in the data plane. These failover mechanisms typically rely on pre-installed static rerouting rules which can depend only on local failure information. The locally limited failure information renders the problem of providing a high resilience algorithmically challenging. In this paper, we are interested in algorithms which tolerate a maximal number of k simultaneous link failures to guarantee packet delivery, as long as source and destination remain connected afterwards. Prior work showed that k=1 link failure can always be tolerated in general networks, but already the question of k=2 remained an unresolved problem.

The performance of more and more cloud-based applications critically depends on the performance of the interconnecting datacenter network. Emerging reconfigurable datacenter networks have the potential to provide an unprecedented throughput by dynamically reconfiguring their topology in a demand-aware manner. This paper studies the algorithmic problem of how to design low-degree and hence scalable datacenter networks that are optimized toward the current traffic they serve. Our main contribution is a novel network design which provides asymptotically minimal route lengths and congestion. In comparison to prior work, our design reduces the degree requirements by a factor of four for sparse demand matrices. We further show that the problem is already NP-hard for tree-shaped demands, but permits a 2-approximation on the route lengths and a 6-approximation for congestion. We further report on a small empirical study on Facebook traces.

Recently, many algorithms are proposed to find a communication flow that is robust against k-edges failures. That flow can be weaker, if attackers can obtain forwarding information in each router. In this paper, we propose an algorithm that find a forwarding algorithm maximizing the remaining flow in that situation. We show that Kishimoto's multiroute flow is a (k + 1)-approximation algorithm for the problem, when the route number is k + 1. When the route number is optimally chosen, we show that the multiroute flow is a 2-approximation algorithm for most of randomly generated graphs. Our experimental results show that our algorithm has 15%-37% better performance than max-flow algorithm.