Asynchronous Convergence of Policy-Rich Distributed Bellman-Ford Routing Protocols
View / Open Files
Authors
Griffin, TG
Daggitt, Matthew
Gurney, Alexander
Publication Date
2018-08-07Journal Title
SIGCOMM 2018 - Proceedings of the 2018 Conference of the ACM Special Interest Group on Data Communication
Conference Name
ACM SIGCOMM 2018
ISBN
9781450355674
Publisher
Association for Computing Machinery
Pages
103-116
Type
Conference Object
This Version
AM
Metadata
Show full item recordCitation
Griffin, T., Daggitt, M., & Gurney, A. (2018). Asynchronous Convergence of Policy-Rich Distributed Bellman-Ford Routing Protocols. SIGCOMM 2018 - Proceedings of the 2018 Conference of the ACM Special Interest Group on Data Communication, 103-116. https://doi.org/10.1145/3230543.3230561
Abstract
We present new results in the theory of asynchronous convergence for the Distributed Bellman-Ford (DBF) family of routing protocols which includes distance-vector protocols (e.g. RIP) and path-vector protocols (e.g. BGP). We take the \emph{strictly increasing} conditions of Sobrinho and make three main new contributions.
First, we show that the conditions are sufficient to guarantee that the protocols will converge to a \emph{unique} solution, preventing the possibility of BGP wedgies.
Second, we decouple the computation from the asynchronous context in which it occurs, allowing us to reason about a more relaxed model of asynchronous computation in which routing messages can be lost, reordered, and duplicated.
Third, our theory and results have been fully formalised in the Agda theorem prover and the resulting library is publicly available for others to use and extend.
This is in line with the increasing emphasis on
formal verification of software for critical infrastructure.
Sponsorship
EPSRC (1642042)
Identifiers
External DOI: https://doi.org/10.1145/3230543.3230561
This record's URL: https://www.repository.cam.ac.uk/handle/1810/287727
Rights
Licence:
http://www.rioxx.net/licenses/all-rights-reserved
Statistics
Total file downloads (since January 2020). For more information on metrics see the
IRUS guide.
Recommended or similar items
The current recommendation prototype on the Apollo Repository will be turned off on 03 February 2023. Although the pilot has been fruitful for both parties, the service provider IKVA is focusing on horizon scanning products and so the recommender service can no longer be supported. We recognise the importance of recommender services in supporting research discovery and are evaluating offerings from other service providers. If you would like to offer feedback on this decision please contact us on: support@repository.cam.ac.uk