One of the key features of a routing protocol is its ability to recover from link or node failures, recomputing routes efficiently without creating temporary loops. Indeed, in real conditions, there is always a trade-off between the overhead due to the periodic generation of control messages and route convergence time. This paper formalizes the problem of the choice of timers for control message generation as an optimization problem that minimizes the route convergence time, constrained to a constant signaling overhead. The solution requires the knowledge of nodes' centrality in the topology and can be obtained with a computational complexity low enough to allow on-line computation of the timers. Results on both synthetic and real topologies show a significant decrease of the transient duration with the consequent performance gain in terms of reduced number of unreachable destinations and routing loops. Our proposal is general and it can he applied to enhance any link-state routing protocol, albeit it is more suited for wireless networks. As a concrete example, we present the extension of OLSRv2 with our proposal, named Pop-Routing, and discuss its performance and the stability of centrality metrics in three large-scale real wireless mesh networks. This exhaustive analysis on traces of the topology evolution of real networks for one entire week shows that pop-routing outperforms the non-enhanced protocol in every situation, even when it runs with sub-optimal timers due to centrality computation on stale information.

Improving routing convergence with centrality: Theory and implementation of pop-routing

Maccari, Leonardo;
2018-01-01

Abstract

One of the key features of a routing protocol is its ability to recover from link or node failures, recomputing routes efficiently without creating temporary loops. Indeed, in real conditions, there is always a trade-off between the overhead due to the periodic generation of control messages and route convergence time. This paper formalizes the problem of the choice of timers for control message generation as an optimization problem that minimizes the route convergence time, constrained to a constant signaling overhead. The solution requires the knowledge of nodes' centrality in the topology and can be obtained with a computational complexity low enough to allow on-line computation of the timers. Results on both synthetic and real topologies show a significant decrease of the transient duration with the consequent performance gain in terms of reduced number of unreachable destinations and routing loops. Our proposal is general and it can he applied to enhance any link-state routing protocol, albeit it is more suited for wireless networks. As a concrete example, we present the extension of OLSRv2 with our proposal, named Pop-Routing, and discuss its performance and the stability of centrality metrics in three large-scale real wireless mesh networks. This exhaustive analysis on traces of the topology evolution of real networks for one entire week shows that pop-routing outperforms the non-enhanced protocol in every situation, even when it runs with sub-optimal timers due to centrality computation on stale information.
File in questo prodotto:
File Dimensione Formato  
main.pdf

accesso aperto

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

non disponibili

Tipologia: Versione dell'editore
Licenza: Accesso chiuso-personale
Dimensione 2.53 MB
Formato Adobe PDF
2.53 MB 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: https://hdl.handle.net/10278/3717579
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 9
  • ???jsp.display-item.citation.isi??? 8
social impact