Enregistré dans:
| Auteurs principaux: | , , |
|---|---|
| Format: | Preprint |
| Publié: |
2026
|
| Sujets: | |
| Accès en ligne: | https://arxiv.org/abs/2603.03638 |
| Tags: |
Ajouter un tag
Pas de tags, Soyez le premier à ajouter un tag!
|
| _version_ | 1866914379484626944 |
|---|---|
| author | Yang, Shunyu Wang, Dan Zhang, Peng |
| author_facet | Yang, Shunyu Wang, Dan Zhang, Peng |
| contents | Due to the policy-rich BGP, multiple stable forwarding states might exist for the same network topology and configuration, rendering the network convergence non-deterministic. This paper proves that any network with multiple converged states possesses a specific set of critical links which, when flipped (disconnect then reconnect), shifts the network between different stable states. We establish this result under the Stable Path Problem (SPP) framework, and also examine a real-world corner case where SPP doesn't apply.
Building on this theoretical foundation, we propose a tentative theoretical verification method for non-determinism with $O(n)$ complexity, where $n$ is the number of edges in a network. Specifically, we separately flip each link in the network and observe whether new converged states emerge. If no new states are discovered, the network is guaranteed to be free of non-determinism. This approach is proved correct when the set of critical links reduces to a single link -- usually the case in the real-world deployments. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2603_03638 |
| institution | arXiv |
| publishDate | 2026 |
| record_format | arxiv |
| spellingShingle | Exploring Multiple Converged States of Network Configurations Yang, Shunyu Wang, Dan Zhang, Peng Networking and Internet Architecture Due to the policy-rich BGP, multiple stable forwarding states might exist for the same network topology and configuration, rendering the network convergence non-deterministic. This paper proves that any network with multiple converged states possesses a specific set of critical links which, when flipped (disconnect then reconnect), shifts the network between different stable states. We establish this result under the Stable Path Problem (SPP) framework, and also examine a real-world corner case where SPP doesn't apply. Building on this theoretical foundation, we propose a tentative theoretical verification method for non-determinism with $O(n)$ complexity, where $n$ is the number of edges in a network. Specifically, we separately flip each link in the network and observe whether new converged states emerge. If no new states are discovered, the network is guaranteed to be free of non-determinism. This approach is proved correct when the set of critical links reduces to a single link -- usually the case in the real-world deployments. |
| title | Exploring Multiple Converged States of Network Configurations |
| topic | Networking and Internet Architecture |
| url | https://arxiv.org/abs/2603.03638 |