Fast and efficient recovery from node failure, with minimal disruption of routes and the consequent traffic loss is of the utmost importance for any routing protocol. Link-state protocols, albeit preferred to distance vector ones because of faster convergence, still suffer from a trade-off between control message overhead and performance. This work formalizes the routes' disruption following a node failure as an optimization problem depending on the nodes' centrality in the topology, constrained to a constant signaling overhead. Next, it shows that the solution can be found using Lagrange Multipliers. The solution complexity is low enough to be computed on-line on the network routers, thus obtaining the optimal setting of control message timers that minimize the traffic loss following a node failure. The gain obtained is quantified in power-law synthetic topologies, and it is also tested on real network topologies extending the OLSR protocol to use the modified timers, showing that the inevitable approximations introduced in the analysis do not hamper the very good results achievable through this novel approach. The technique can be applied to any link state protocol, including OSPF, and improves route convergence not only upon failures but on every topology modification.

Pop-Routing: Centrality-based Tuning of Control Messages for Faster Route Convergence

Maccari, Leonardo;
2016

Abstract

Fast and efficient recovery from node failure, with minimal disruption of routes and the consequent traffic loss is of the utmost importance for any routing protocol. Link-state protocols, albeit preferred to distance vector ones because of faster convergence, still suffer from a trade-off between control message overhead and performance. This work formalizes the routes' disruption following a node failure as an optimization problem depending on the nodes' centrality in the topology, constrained to a constant signaling overhead. Next, it shows that the solution can be found using Lagrange Multipliers. The solution complexity is low enough to be computed on-line on the network routers, thus obtaining the optimal setting of control message timers that minimize the traffic loss following a node failure. The gain obtained is quantified in power-law synthetic topologies, and it is also tested on real network topologies extending the OLSR protocol to use the modified timers, showing that the inevitable approximations introduced in the analysis do not hamper the very good results achievable through this novel approach. The technique can be applied to any link state protocol, including OSPF, and improves route convergence not only upon failures but on every topology modification.
35th Annual IEEE International Conference on Computer Communications (INFOCOM)
File in questo prodotto:
File Dimensione Formato  
CR_Maccari_1580.pdf

accesso aperto

Tipologia: Documento in Post-print
Licenza: Accesso chiuso-personale
Dimensione 281.73 kB
Formato Adobe PDF
281.73 kB Adobe PDF Visualizza/Apri
07524407.pdf

non disponibili

Tipologia: Versione dell'editore
Licenza: Accesso chiuso-personale
Dimensione 312.72 kB
Formato Adobe PDF
312.72 kB Adobe PDF   Visualizza/Apri

I documenti in ARCA sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: http://hdl.handle.net/10278/3717590
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 15
  • ???jsp.display-item.citation.isi??? 4
social impact