8481 articles  [version française]

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)

Abstract: 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
  • Domain : Computer Science/Networking and Telecommunication
  • Keywords : Information Centric Networks – Content Centric Networks – Interest Forwarding – Multi-Armed Model with Delays
  • Internal note : RR-7917
  • Available versions :  v1 (2012-03-31) v2 (2012-04-02)
 
  • hal-00683827, version 2
  • http://hal.inria.fr/hal-00683827
  • oai:hal.inria.fr:hal-00683827
  • From: Konstantin Avrachenkov <>
  • Submitted on: Sunday, 1 April 2012 23:08:42
  • Updated on: Monday, 2 April 2012 16:25:54