Sökning: onr:"swepub:oai:DiVA.org:kth-228142" >
Stochastic Online S...
Stochastic Online Shortest Path Routing : The Value of Feedback
-
- Talebi Mazraeh Shahi, Mohammad Sadegh, 1982- (författare)
- KTH,ACCESS Linnaeus Centre
-
- Zou, Zhenhua (författare)
- Ericsson Res, SE-16483 Stockholm, Sweden.
-
- Combes, Richard (författare)
- Cent Supelec L2S, Telecommun Dept, F-91192 Gif Sur Yvette, France.
-
visa fler...
-
- Proutiere, Alexandre (författare)
- KTH,ACCESS Linnaeus Centre
-
- Johansson, Mikael (författare)
- KTH,ACCESS Linnaeus Centre
-
visa färre...
-
(creator_code:org_t)
- Institute of Electrical and Electronics Engineers (IEEE), 2018
- 2018
- Engelska.
-
Ingår i: IEEE Transactions on Automatic Control. - : Institute of Electrical and Electronics Engineers (IEEE). - 0018-9286 .- 1558-2523. ; 63:4, s. 915-930
- Relaterad länk:
-
https://urn.kb.se/re...
-
visa fler...
-
https://doi.org/10.1...
-
visa färre...
Abstract
Ämnesord
Stäng
- 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.
Ämnesord
- TEKNIK OCH TEKNOLOGIER -- Elektroteknik och elektronik -- Kommunikationssystem (hsv//swe)
- ENGINEERING AND TECHNOLOGY -- Electrical Engineering, Electronic Engineering, Information Engineering -- Communication Systems (hsv//eng)
Nyckelord
- Online combinatorial optimization
- shortest path routing
- stochastic multiarmed bandits (MAB)
Publikations- och innehållstyp
- ref (ämneskategori)
- art (ämneskategori)
Hitta via bibliotek
Till lärosätets databas