8481 articles  [english version]

hal-00683827, version 2

CCN Interest Forwarding Strategy as Multi-Armed Bandit Model with Delays

Konstantin Avrachenkov (, http://www-sop.inria.fr/mistral/personnel/K.Avrachenkov/me.html) 1, Peter Jacko () a, 2

N° RR-7917 (2012)

Résumé : We consider Content Centric Network (CCN) interest forwarding problem as a Multi-Armed Bandit (MAB) problem with delays. We investigate the transient behaviour of the $\eps$-greedy, tuned $\eps$-greedy and Upper Confidence Bound (UCB) interest forwarding policies. Surprisingly, for all the three policies very short initial exploratory phase is needed. We demonstrate that the tuned $\eps$-greedy algorithm is nearly as good as the UCB algorithm, the best currently available algorithm. We prove the uniform logarithmic bound for the tuned $\eps$-greedy algorithm. In addition to its immediate application to CCN interest forwarding, the new theoretical results for MAB problem with delays represent significant theoretical advances in machine learning discipline.

  • a –  BCAM -- Basque Center for Applied Mathematics
  • 1 :  MAESTRO (INRIA Sophia Antipolis)
  • INRIA – Université Montpellier II - Sciences et techniques
  • 2 :  Basque Center for Applied Mathematics (BCAM)
  • Basque Center for Applied Mathematics
  • Domaine : Informatique/Réseaux et télécommunications
  • Mots-clés : Information Centric Networks – Content Centric Networks – Interest Forwarding – Multi-Armed Model with Delays
  • Référence interne : RR-7917
  • Versions disponibles :  v1 (31-03-2012) v2 (02-04-2012)
 
  • hal-00683827, version 2
  • http://hal.inria.fr/hal-00683827
  • oai:hal.inria.fr:hal-00683827
  • Contributeur : Konstantin Avrachenkov <>
  • Soumis le : Dimanche 1 Avril 2012, 23:08:42
  • Dernière modification le : Lundi 2 Avril 2012, 16:25:54