Change search
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • harvard1
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf
Stochastic Online Shortest Path Routing: The Value of Feedback
KTH, School of Electrical Engineering and Computer Science (EECS), Centres, ACCESS Linnaeus Centre.ORCID iD: 0000-0002-1934-7421
Ericsson Res, SE-16483 Stockholm, Sweden..
Cent Supelec L2S, Telecommun Dept, F-91192 Gif Sur Yvette, France..
KTH, School of Electrical Engineering and Computer Science (EECS), Centres, ACCESS Linnaeus Centre.
Show others and affiliations
2018 (English)In: IEEE Transactions on Automatic Control, ISSN 0018-9286, E-ISSN 1558-2523, Vol. 63, no 4, p. 915-930Article in journal (Refereed) Published
Abstract [en]

This paper studies online shortest path routing over multihop networks. Link costs or delays are time varying and modeled by independent and identically distributed random processes, whose parameters are initially unknown. The parameters, and hence the optimal path, can only be estimated by routing packets through the network and observing the realized delays. Our aim is to find a routing policy that minimizes the regret (the cumulative difference of expected delay) between the path chosen by the policy and the unknown optimal path. We formulate the problem as a combinatorial bandit optimization problem and consider several scenarios that differ in where routing decisions are made and in the information available when making the decisions. For each scenario, we derive a tight asymptotic lower bound on the regret that has to be satisfied by any online routing policy. Three algorithms, with a tradeoff between computational complexity and performance, are proposed. The regret upper bounds of these algorithms improve over those of the existing algorithms. We also assess numerically the performance of the proposed algorithms and compare it to that of existing algorithms.

Place, publisher, year, edition, pages
Institute of Electrical and Electronics Engineers (IEEE), 2018. Vol. 63, no 4, p. 915-930
Keywords [en]
Online combinatorial optimization, shortest path routing, stochastic multiarmed bandits (MAB)
National Category
Communication Systems
Identifiers
URN: urn:nbn:se:kth:diva-228142DOI: 10.1109/TAC.2017.2747409ISI: 000429056000001Scopus ID: 2-s2.0-85028716123OAI: oai:DiVA.org:kth-228142DiVA, id: diva2:1207065
Note

QC 20180518

Available from: 2018-05-18 Created: 2018-05-18 Last updated: 2018-05-23Bibliographically approved

Open Access in DiVA

No full text in DiVA

Other links

Publisher's full textScopus

Authority records BETA

Talebi Mazraeh Shahi, Mohammad SadeghProutiere, AlexandreJohansson, Mikael

Search in DiVA

By author/editor
Talebi Mazraeh Shahi, Mohammad SadeghProutiere, AlexandreJohansson, Mikael
By organisation
ACCESS Linnaeus Centre
In the same journal
IEEE Transactions on Automatic Control
Communication Systems

Search outside of DiVA

GoogleGoogle Scholar

doi
urn-nbn

Altmetric score

doi
urn-nbn
Total: 35 hits
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • harvard1
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf