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 be 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. This situation must be taken into account, as, albeit computationally light weight, the optimization cannot run in real-time on wireless routers.

Improving routing convergence with centrality: Theory and implementation of pop-routing / Maccari, Leonardo; Lo Cigno, Renato. - In: IEEE-ACM TRANSACTIONS ON NETWORKING. - ISSN 1063-6692. - 26:5(2018), pp. 2216-2229. [10.1109/TNET.2018.2865886]

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

Maccari, Leonardo;Lo Cigno, Renato
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 be 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. This situation must be taken into account, as, albeit computationally light weight, the optimization cannot run in real-time on wireless routers.
2018
5
Maccari, Leonardo; Lo Cigno, Renato
Improving routing convergence with centrality: Theory and implementation of pop-routing / Maccari, Leonardo; Lo Cigno, Renato. - In: IEEE-ACM TRANSACTIONS ON NETWORKING. - ISSN 1063-6692. - 26:5(2018), pp. 2216-2229. [10.1109/TNET.2018.2865886]
File in questo prodotto:
File Dimensione Formato  
main.pdf

Open Access dal 01/01/2021

Tipologia: Post-print referato (Refereed author’s manuscript)
Licenza: Tutti i diritti riservati (All rights reserved)
Dimensione 988.57 kB
Formato Adobe PDF
988.57 kB Adobe PDF Visualizza/Apri
08457534.pdf

Solo gestori archivio

Tipologia: Versione editoriale (Publisher’s layout)
Licenza: Tutti i diritti riservati (All rights reserved)
Dimensione 2.53 MB
Formato Adobe PDF
2.53 MB Adobe PDF   Visualizza/Apri

I documenti in IRIS 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/11572/232208
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 9
  • ???jsp.display-item.citation.isi??? 7
social impact