Improved Compact Routing Schemes for Power-Law Networks

Abstract : Compact routing intends to achieve good tradeoff between the routing path length and the memory overhead, and is recently considered as a main alternative to overcome the fundamental scaling problems of the Internet routing system. Plenty of studies have been conducted on compact routing, and quite a few universal compact routing schemes have been designed for arbitrary network topologies. However, it is generally believed that specialized compact routing schemes for peculiar network topologies can have better performance than universal ones. Complex network research has uncovered that most real-world networks have degree distributions exhibiting power law tails, i.e., a few nodes have very high degrees while many other nodes have low degrees. High-degree nodes play a crucial role of hubs in communication and networking. Based on this fact, we put forward two highest-degree landmark based compact routing schemes, namely HDLR and HDLR + . Theoretical analysis on random power law graphs shows our schemes can achieve a better space-stretch trade-off than prior compact routing schemes. Simulations conducted on random power law graphs and real-world AS-level Internet graph validate the effectivity of our schemes.
Type de document :
Communication dans un congrès
Erik Altman; Weisong Shi. 8th Network and Parallel Computing (NPC), Oct 2011, Changsha,, China. Springer, Lecture Notes in Computer Science, LNCS-6985, pp.44-58, 2011, Network and Parallel Computing. 〈10.1007/978-3-642-24403-2_4〉
Liste complète des métadonnées

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

https://hal.inria.fr/hal-01593024
Contributeur : Hal Ifip <>
Soumis le : lundi 25 septembre 2017 - 16:33:55
Dernière modification le : vendredi 1 décembre 2017 - 01:09:45
Document(s) archivé(s) le : mardi 26 décembre 2017 - 14:40:33

Fichier

978-3-642-24403-2_4_Chapter.pd...
Fichiers produits par l'(les) auteur(s)

Licence


Distributed under a Creative Commons Paternité 4.0 International License

Identifiants

Citation

Mingdong Tang, Jianxun Liu, Guoqing Zhang. Improved Compact Routing Schemes for Power-Law Networks. Erik Altman; Weisong Shi. 8th Network and Parallel Computing (NPC), Oct 2011, Changsha,, China. Springer, Lecture Notes in Computer Science, LNCS-6985, pp.44-58, 2011, Network and Parallel Computing. 〈10.1007/978-3-642-24403-2_4〉. 〈hal-01593024〉

Partager

Métriques

Consultations de la notice

42

Téléchargements de fichiers

4