Efficient Recovery from False State in Distributed Routing Algorithms

Abstract : Malicious and misconfigured nodes can inject incorrect state into a distributed system, which can then be propagated system-wide as a result of normal network operation. Such false state can degrade the performance of a distributed system or render it unusable. For example, in the case of network routing algorithms, false state corresponding to a node incorrectly declaring a cost of 0 to all destinations (maliciously or due to misconfiguration) can quickly spread through the network. This causes other nodes to (incorrectly) route via the misconfigured node, resulting in suboptimal routing and network congestion. We propose three algorithms for efficient recovery in such scenarios and prove the correctness of each of these algorithms. Through simulation, we evaluate our algorithms - in terms of message and time overhead - when applied to removing false state in distance vector routing. Our analysis shows that over topologies where link costs remain fixed and for the same topologies where link costs change, a recovery algorithm based on system-wide checkpoints and a rollback mechanism yields superior performance when using the poison reverse optimization.
Type de document :
Communication dans un congrès
Mark Crovella; Laura Marie Feeney; Dan Rubenstein; S. V. Raghavan. 9th International IFIP TC 6 Networking Conference (NETWORKING), May 2010, Chennai, India. Springer, Lecture Notes in Computer Science, LNCS-6091, pp.198-212, 2010, NETWORKING 2010. 〈10.1007/978-3-642-12963-6_16〉
Liste complète des métadonnées

Littérature citée [17 références]  Voir  Masquer  Télécharger

https://hal.inria.fr/hal-01056312
Contributeur : Hal Ifip <>
Soumis le : lundi 18 août 2014 - 15:45:12
Dernière modification le : vendredi 11 août 2017 - 15:25:03
Document(s) archivé(s) le : jeudi 27 novembre 2014 - 05:31:19

Fichier

main.pdf
Fichiers produits par l'(les) auteur(s)

Licence


Distributed under a Creative Commons Paternité 4.0 International License

Identifiants

Citation

Daniel Gyllstrom, Sudarshan Vasudevan, Jim Kurose, Gerome Miklau. Efficient Recovery from False State in Distributed Routing Algorithms. Mark Crovella; Laura Marie Feeney; Dan Rubenstein; S. V. Raghavan. 9th International IFIP TC 6 Networking Conference (NETWORKING), May 2010, Chennai, India. Springer, Lecture Notes in Computer Science, LNCS-6091, pp.198-212, 2010, NETWORKING 2010. 〈10.1007/978-3-642-12963-6_16〉. 〈hal-01056312〉

Partager

Métriques

Consultations de la notice

321

Téléchargements de fichiers

114