Back to Search
Start Over
Router dans Internet avec quinze entrées
- Source :
- ALGOTEL 2015 — 17èmes Rencontres Francophones sur les Aspects Algorithmiques des Télécommunications, ALGOTEL 2015 — 17èmes Rencontres Francophones sur les Aspects Algorithmiques des Télécommunications, Jun 2015, Beaune, France
- Publication Year :
- 2015
- Publisher :
- HAL CCSD, 2015.
-
Abstract
- International audience; Cet article étudie les schémas de routage compacts qui sont très efficaces en termes de mémoires utilisées pour le stockage des tables de routage dans les graphes de type Internet. Nous proposons un nouveau schéma de routage compact avec indépendance des noms, dont la mémoire moyenne par noeud est prouvée comme étant bornée par √n, et pour lequel l'étirement maximum de toute route est au plus 7. Ces bornes sont données pour la classe RPLG (Random Power Low Graphs) et sont vraies avec forte probabilité. De plus, nous montrons expérimentalement que notre schéma est tr es efficace en termes d'étirement et de mémoire dans les graphes de type Internet (CAIDA et d'autres cartes). Nous complétons cette étude en comparant nos résultats analytiques et expérimentaux a plusieurs schémas de routage compact. En particulier, nous montrons que les besoins moyens en mémoire de notre schéma sont meilleurs que les schémas précédents d'au moins un ordre de grandeur pour des cartes CAIDA de 16K noeuds.
- Subjects :
- graphes en loi de puissance
[INFO.INFO-NI]Computer Science [cs]/Networking and Internet Architecture [cs.NI]
[INFO.INFO-NI] Computer Science [cs]/Networking and Internet Architecture [cs.NI]
schéma de routage
[INFO.INFO-DS]Computer Science [cs]/Data Structures and Algorithms [cs.DS]
[INFO.INFO-DS] Computer Science [cs]/Data Structures and Algorithms [cs.DS]
routage compact
Subjects
Details
- Language :
- English
- Database :
- OpenAIRE
- Journal :
- ALGOTEL 2015 — 17èmes Rencontres Francophones sur les Aspects Algorithmiques des Télécommunications, ALGOTEL 2015 — 17èmes Rencontres Francophones sur les Aspects Algorithmiques des Télécommunications, Jun 2015, Beaune, France
- Accession number :
- edsair.dedup.wf.001..bac5318019970935a10034f5b61fcd3e