Cited By
View all- Maccari LPasserini A(2019)A Big Data and machine learning approach for network monitoring and securitySecurity and Privacy10.1002/spy2.532:1Online publication date: 12-Mar-2019
Improving Routing Convergence With Centrality: Theory and Implementation of Pop-Routing
Pages 2216 - 2229
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.
References
[1]
L. Maccari and R. Lo Cigno, "Pop-routing: Centrality-based tuning of control messages for faster route convergence," in Proc. IEEE Int. Conf. Comput. Commun. (INFOCOM), Apr. 2016, pp. 1-9.
[2]
M. Goyal et al., "Improving convergence speed and scalability in OSPF: A survey," IEEE Commun. Surveys Tuts., vol. 14, no. 2, pp. 443-463, 2nd Quart., 2012.
[3]
F. Clad, P. Mérindol, J.-J. Pansiot, P. Francois, and O. Bonaventure, "Graceful convergence in link-state IP networks: A lightweight algorithm ensuring minimal operational impact," IEEE/ACM Trans. Netw., vol. 22, no. 1, pp. 300-312, Feb. 2014.
[4]
R. Puzis, P. Zilberman, Y. Elovici, S. Dolev, and U. Brandes, "Heuristics for speeding up betweenness centrality computation," in Proc. Int. Conf. Privacy, Secur., Risk Trust Int. Conf. Social Comput., Sep. 2012, pp. 302-311.
[5]
L. Maccari, Q. Nguyen, and R. Lo Cigno, "On the computation of centrality metrics for network security in mesh networks," in Proc. IEEE Global Commun. Conf. (GLOBECOM), Dec. 2016, pp. 1-6.
[6]
C. Gomez, D. Garcia, and J. Paradells, "Improving performance of a real ad-hoc network by tuning OLSR parameters," in Proc. 10th IEEE Symp. Comput. Commun., (ISCC), Jun. 2005, pp. 16-21.
[7]
Y. Huang, S. N. Bhatti, and D. Parker, "Tuning OLSR," in Proc. IEEE 17th Int. Symp. Pers., Indoor Mobile Radio Commun., (PIMRC), Sep. 2006, pp. 1-5.
[8]
J. Toutouh, J. Garcia-Nieto, and E. Alba, "Intelligent OLSR routing protocol optimization for VANETs," IEEE Trans. Veh. Technol., vol. 61, no. 4, pp. 1884-1894, May 2012.
[9]
A. Belghith and M. Abid, "Autonomic self tunable proactive routing in mobile ad hoc networks," in Proc. IEEE Int. Conf. Wireless Mobile Comput., Netw. Commun. (WIMOB), Oct. 2009, pp. 276-281.
[10]
L. Guardalben, L. J. G. Villalba, F. Buiati, J. B. M. Sobral, and E. Camponogara, "Self-configuration and self-optimization process in heterogeneous wireless networks," Sensors, vol. 11, no. 1, pp. 425-454, 2010.
[11]
D. F. H. Sadok, T. G. Rodrigues, R. D. M. Amorim, and J. Kelner, "On the performance of heterogeneous MANETs," Wireless Netw., vol. 21, no. 1, pp. 139-160, 2015.
[12]
J. Yu, N. Wang, G. Wang, and D. Yu, "Connected dominating sets in wireless ad hoc and sensor networks--A comprehensive survey," Comput. Commun., vol. 36, no. 2, pp. 121-134, 2013.
[13]
O. Liang, Y. A. Sekercioglu, and N. Mani, "A survey of multipoint relay based broadcast schemes in wireless ad hoc networks," IEEE Commun. Surveys Tuts., vol. 8, no. 4, pp. 30-46, 4th Quart., 2006.
[14]
L. Maccari and R. Lo Cigno, "How to reduce and stabilize MPR sets in OLSR networks," in Proc. IEEE Int. Conf. Wireless Mobile Comput., Netw. Commun. (WIMOB), Oct. 2012, pp. 373-380.
[15]
J. H. Ahn and T.-J. Lee, "Multipoint relay selection for robust broadcast in ad hoc networks," Ad Hoc Netw., vol. 17, pp. 82-97, Jun. 2014.
[16]
L. Maccari and R. Lo Cigno, "Betweenness estimation in OLSR-based multi-hop networks for distributed filtering," J. Comput. Syst. Sci., vol. 80, no. 3, pp. 670-685, 2014.
[17]
A. Iwata, C.-C. Chiang, G. Pei, M. Gerla, and T.-W. Chen, "Scalable routing strategies for ad hoc wireless networks," IEEE J. Sel. Areas Commun., vol. 17, no. 8, pp. 1369-1379, Aug. 1999.
[18]
C. Adjih, E. Baccelli, T. H. Clausen, P. Jacquet, and G. Rodolakis, "Fish eye OLSR scaling properties," J. Commun. Netw., vol. 6, no. 4, pp. 343-351, Dec. 2004.
[19]
Y. Faheem and J. L. Rougier, "Loop avoidance for fish-eye OLSR in sparse wireless mesh networks," in Proc. 6th IEEE Int. Conf. Wireless On-Demand Netw. Syst. Services (WONS), Feb. 2009, pp. 231-234.
[20]
P. Francois, M. Shand, and O. Bonaventure, "Disruption free topology reconfiguration in OSPF networks," in Proc. IEEE Int. Conf. Comput. Commun. (INFOCOM), May 2007, pp. 89-97.
[21]
L. C. Freeman, "A set of measures of centrality based on betweenness," Sociometry, vol. 40, no. 1, pp. 35-41, Mar. 1977.
[22]
D. Katsaros, N. Dimokas, and L. Tassiulas, "Social network analysis concepts in the design of wireless ad hoc network protocols," IEEE Netw., vol. 24, no. 6, pp. 23-29, Nov./Dec. 2010.
[23]
S. Dolev, Y. Elovici, and R. Puzis, "Routing betweenness centrality," J. ACM, vol. 57, no. 4, 2010, Art. no. 25.
[24]
R. Puzis, M. Tubi, Y. Elovici, C. Glezer, and S. Dolev, "A decision support system for placement of intrusion detection and prevention devices in large-scale networks," ACM Trans. Model. Comput. Simul., vol. 22, no. 1, 2011, Art. no. 5.
[25]
L. Maccari and R. Lo Cigno, "Waterwall: A cooperative, distributed firewall for wireless mesh networks," J. Wireless Commun. Netw., vol. 2013, p. 225, Sep. 2013.
[26]
M. Kas, S. Appala, C. Wang, K. M. Carley, L. R. Carley, and O. K. Tonguz, "What if wireless routers were social? Approaching wireless mesh networks from a social networks perspective," IEEE Wireless Commun., vol. 19, no. 6, pp. 36-43, Dec. 2012.
[27]
A. Vázquez-Rodas and L. J. de la Cruz Llopis, "A centrality-based topology control protocol for wireless mesh networks," Ad Hoc Netw., vol. 24, pp. 34-54, Jan. 2015.
[28]
L. Baldesi, L. Maccari, and R. Lo Cigno, "On the use of eigenvector centrality for cooperative streaming," IEEE Commun. Lett., vol. 21, no. 9, pp. 1953-1956, Sep. 2017.
[29]
U. Brandes, "A faster algorithm for betweenness centrality," J. Math. Sociol., vol. 25, no. 2, pp. 163-177, 2001.
[30]
D. Vega, L. Cerdà-Alabern, L. Navarro, and R. Meseguer, "Topology patterns of a community network: Guifi.net," in Proc. IEEE 8th Int. Conf. Wireless Mobile Comput., Netw. Commun. (WiMob), Oct. 2012, pp. 612-619.
[31]
L. Maccari and R. Lo Cigno, "A week in the life of three large wireless community networks," Ad Hoc Netw., vol. 24, pp. 175-190, Jan. 2015.
[32]
L. Maccari, L. Ghiro, A. Guerrieri, A. Montresor, and R. Lo Cigno, "On the distributed computation of load centrality and its application to DV routing," in Proc. IEEE Int. Conf. Comput. Commun. (INFOCOM), Honolulu, HI, USA, Apr. 2018.
[33]
T. H. Clausen, P. Jacquet, D.-Q. Nguyen, and E. Baccelli, OSPF Multipoint Relay (MPR) Extension for Ad Hoc Networks, document RFC 5449. [Online]. Available: https://tools.ietf.org/html/rfc5449
[34]
B. Milic and M. Malek, "NPART--Node placement algorithm for realistic topologies in wireless multihop network simulation," in Proc. 2nd Int. Conf. Simul. Tools Techn. (SIMUTOOLS), Mar. 2009, Art. no. 9.
[35]
U. Herberg, C. Dearlove, and T. Clausen, Integrity Protection for the Neighborhood Discovery Protocol (NHDP) and Optimized Link State Routing Protocol Version 2 (OLSRv2), document RFC 7183, Internet Engineering Task Force, Apr. 2014.
[36]
U. Herberg, R. Cole, and T. Clausen, Definition of Managed Objects for the Optimized Link State Routing Protocol Version 2, document RFC 7184, Internet Engineering Task Force, Apr. 2014.
[37]
C. Dearlove, T. Clausen, and P. Jacquet, Link Metrics in the Optimized Link State Routing Protocol Version 2 (OLSRv2), document RFC 7185, Internet Engineering Task Force, Apr. 2014.
[38]
C. Dearlove and T. Clausen, Routing Multipoint Relay Optimization for the Optimized Link State Routing Protocol Version 2 (OLSRv2), document RFC 7187, Internet Engineering Task Force, Apr. 2014.
[39]
C. Barz, J. Niewiejska, and H. Rogge, "NHDP and OLSRv2 for community networks," in Proc. IEEE 9th Int. Conf. Wireless Mobile Comput., Netw. Commun. (WiMob), Lyon, France, Oct. 2013, pp. 96-102.
Recommendations
Improving internet-wide routing protocols convergence with MRPC timers
CoNEXT '09: Proceedings of the 5th international conference on Emerging networking experiments and technologiesThe behavior of routing protocols during convergence is critical as it impacts end-to-end performance. Network convergence is particularly important in BGP, the current interdomain routing protocol. In order to decrease the amount of exchanged routing ...
Evaluation of Congestion Aware Social Metrics for Centrality-Based Routing
Opportunistic networks utilize pocket switching for routing where each node forwards its messages to a suitable next node. The selection of the forwarder node is crucial for the efficient performance of a routing protocol. In any opportunistic network, ...
Route flap damping exacerbates internet routing convergence
SIGCOMM '02: Proceedings of the 2002 conference on Applications, technologies, architectures, and protocols for computer communicationsRoute flap damping is considered to be a widely deployed mechanism in core routers that limits the widespread propagation of unstable BGP routing information. Originally designed to suppress route changes caused by link flaps, flap damping attempts to ...
Comments
Please enable JavaScript to view thecomments powered by Disqus.Information & Contributors
Information
Published In
Copyright © 2018.
Publisher
IEEE Press
Publication History
Published: 01 October 2018
Published in TON Volume 26, Issue 5
Qualifiers
- Research-article
Contributors
Other Metrics
Bibliometrics & Citations
Bibliometrics
Article Metrics
- View Citations1Total Citations
- 60Total Downloads
- Downloads (Last 12 months)4
- Downloads (Last 6 weeks)1
Reflects downloads up to 16 Nov 2024
Other Metrics
Citations
Cited By
View all- Maccari LPasserini A(2019)A Big Data and machine learning approach for network monitoring and securitySecurity and Privacy10.1002/spy2.532:1Online publication date: 12-Mar-2019
View Options
Login options
Check if you have access through your login credentials or your institution to get full access on this article.
Sign in