Collecter un nombre inconnu de coupons

Résumé : Dans les algorithmes de cartographie d'Internet, l'un des problèmes clés à résoudre est celui de la découverte des différentes interfaces de sortie d'un routeur en cas d'équilibrage de charge: combien de sondes doit-on envoyer tester la connexion pour être raisonnablement certain d'avoir découvert toutes les interfaces ? Une des solutions existantes est une variante du problème du collecteur de coupons, qui consiste à associer à chaque nombre d'interfaces découvertes un nombre de sondes au-delà duquel on considère que l'on peut s'arrêter. Dans cet article, nous donnons une formule close pour l'association et prouvons sa quasi-optimalité.ne formule close pour l'association et prouvons sa quasi-optimalité.
Document type :
Conference papers
Liste complète des métadonnées

https://hal.inria.fr/hal-01787252
Contributor : Fabien Mathieu <>
Submitted on : Monday, May 7, 2018 - 2:17:56 PM
Last modification on : Tuesday, April 2, 2019 - 2:38:17 AM
Document(s) archivé(s) le : Tuesday, September 25, 2018 - 7:40:01 PM

File

Coupons_CoRes.pdf
Files produced by the author(s)

Identifiers

  • HAL Id : hal-01787252, version 1

Citation

Philippe Jacquet, Mohamed Lamali, Fabien Mathieu. Collecter un nombre inconnu de coupons. CORES 2018 - Rencontres Francophones sur la Conception de Protocoles, l’Évaluation de Performance et l’Expérimentation des Réseaux de Communication, May 2018, Roscoff, France. pp.1-4. ⟨hal-01787252⟩

Share

Metrics

Record views

176

Files downloads

57