Alternative paths computation for congestion mitigation in segment-routing networks

Overview

• This paper explores a promising approach to quickly steer network traffic away from congested links in backbone networks.
• The researchers focus on the path computation problem, aiming to maximize the amount of traffic that can be rerouted and the resilience against 1-link failures.
• They investigate two variants of this problem: one that maximizes the residual flow after failures, and another that maximizes the number of surviving alternative paths.

Plain English Explanation

In backbone networks, it's crucial to quickly protect the quality of service (QoS) when unexpected events, like failures or congestions, occur. Current solutions based on Segment Routing (SR), such as Topology-Independent Loop-Free Alternate (TI-LFA), can handle failures, but there are no distributed solutions for mitigating congestion.

The researchers propose a promising SR-based approach to quickly reroute traffic away from congested links and onto alternative paths. The key challenge is pre-computing these alternative paths efficiently to enable effective congestion mitigation. The researchers explore two variants of this path computation problem:

1. Maximizing Residual Flow: This aims to maximize the amount of traffic that can still flow through the network after any 1-link failure. The researchers show this is a complex, NP-Hard problem and solve it using a Benders decomposition algorithm.

2. Maximizing Surviving Paths: This simpler variant aims to maximize the number of alternative paths that remain available after any 1-link failure. The researchers provide a polynomial-time algorithm to solve this.

Through experiments, the researchers compare these two approaches and demonstrate that both can increase the amount of rerouted traffic and the overall resilience of the network to failures.

Technical Explanation

The researchers propose a Segment Routing (SR)-based approach to quickly steer network traffic away from congested links in backbone networks. They focus on the path computation problem, aiming to maximize both the amount of traffic that can be rerouted and the resilience against 1-link failures.

They investigate two variants of this problem:

1. Maximizing Residual Flow: This first variant seeks to maximize the residual flow (the amount of traffic that can still be transmitted) after all possible 1-link failures. The researchers show this is an NP-Hard problem and solve it using a Benders decomposition algorithm.

2. Maximizing Surviving Paths: This second, relaxed variant aims to maximize the number of alternative paths that remain available after any 1-link failure. The researchers provide a polynomial-time algorithm to solve this problem.

Through numerical experiments, the researchers compare the two approaches. They demonstrate that both variants can significantly increase the amount of rerouted traffic and the overall resilience of the network against 1-link failures.

Critical Analysis

The researchers acknowledge that their work focuses solely on 1-link failures, and that more complex failure scenarios could be considered in future research. Additionally, the performance of their algorithms may degrade as the network size and complexity increase, so further optimization and scalability improvements may be needed.

While the researchers provide promising results, it would be valuable to see the proposed approaches evaluated in real-world network scenarios to further validate their effectiveness. Comparing the performance to other congestion mitigation techniques, such as queue-aware network control algorithms, could also provide additional insights.

Overall, the researchers have presented a thoughtful approach to a critical challenge in backbone network management, and their work lays a solid foundation for continued exploration in this area.

Conclusion

This paper introduces a novel Segment Routing-based approach to quickly reroute network traffic away from congested links in backbone networks. By exploring two variants of the path computation problem - one focused on maximizing residual flow and the other on maximizing the number of surviving alternative paths - the researchers demonstrate that their techniques can significantly improve the ability to mitigate congestion and enhance network resilience against 1-link failures.

While the research has some limitations, the insights and algorithms presented in this work represent an important step forward in addressing the need for distributed and tactical congestion management solutions in modern backbone networks.