Change search
ReferencesLink to record
Permanent link

Direct link
Online shortest path routing: The value of information
KTH, School of Electrical Engineering (EES), Automatic Control.
KTH, School of Electrical Engineering (EES), Automatic Control.
KTH, School of Electrical Engineering (EES), Automatic Control.
2014 (English)Conference paper (Refereed)
Abstract [en]

This paper studies online shortest path routing over dynamic multi-hop networks. Link costs or delays are time-varying and modelled 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 delay difference) 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 decision. For each scenario, we derive the tight asymptotic lower bound on the regret that has to be satisfied by any online routing policy. These bounds help us to understand the performance improvements we can expect when (i) taking routing decisions at each hop rather than at the source only, and (ii) observing per-link costs rather than aggregate path costs. In particular, we show that (i) is of no use while (ii) can have a spectacular impact. Efficient algorithms are proposed and evaluated against the state-of-the a


Place, publisher, year, edition, pages
National Category
Engineering and Technology
URN: urn:nbn:se:kth:diva-153425DOI: 10.1109/ACC.2014.6859133ISI: 000346492602115ScopusID: 2-s2.0-84905676985OAI: diva2:752383
2014 American Control Conference (ACC) June 4-6, 2014. Portland, Oregon, USA

QC 20141006

Available from: 2014-10-03 Created: 2014-10-03 Last updated: 2015-03-27Bibliographically approved

Open Access in DiVA

No full text

Other links

Publisher's full textScopus

Search in DiVA

By author/editor
Zou, ZhenhuaProutiere, AlexandreJohansson, Mikael
By organisation
Automatic Control
Engineering and Technology

Search outside of DiVA

GoogleGoogle Scholar
The number of downloads is the sum of all downloads of full texts. It may include eg previous versions that are now no longer available

Altmetric score

Total: 15 hits
ReferencesLink to record
Permanent link

Direct link