View in EDS

Stochastic Online Shortest Path Routing: The Value of Feedback.

Saved in:
Bibliographic Details
Title: Stochastic Online Shortest Path Routing: The Value of Feedback.
Authors: Talebi, Mohammad Sadegh1, Proutiere, Alexandre1, Johansson, Mikael1, Zou, Zhenhua2, Combes, Richard3
Source: IEEE Transactions on Automatic Control. Apr2018, Vol. 63 Issue 4, p915-930. 16p.
Subjects: Stochastic analysis, Random operators, Matrix analytic methods, Combinatorial optimization, Routing (Computer network management)
Abstract: 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. [ABSTRACT FROM PUBLISHER]
Copyright of IEEE Transactions on Automatic Control is the property of IEEE and its content may not be copied or emailed to multiple sites without the copyright holder's express written permission. Additionally, content may not be used with any artificial intelligence tools or machine learning technologies. However, users may print, download, or email articles for individual use. This abstract may be abridged. No warranty is given about the accuracy of the copy. Users should refer to the original published version of the material for the full abstract. (Copyright applies to all Abstracts.)
Database: Engineering Source
FullText Text:
  Availability: 0
Header DbId: egs
DbLabel: Engineering Source
An: 128843712
AccessLevel: 6
PubType: Periodical
PubTypeId: serialPeriodical
PreciseRelevancyScore: 0
IllustrationInfo
Items – Name: Title
  Label: Title
  Group: Ti
  Data: Stochastic Online Shortest Path Routing: The Value of Feedback.
– Name: Author
  Label: Authors
  Group: Au
  Data: <searchLink fieldCode="AR" term="%22Talebi%2C+Mohammad+Sadegh%22">Talebi, Mohammad Sadegh</searchLink><relatesTo>1</relatesTo><br /><searchLink fieldCode="AR" term="%22Proutiere%2C+Alexandre%22">Proutiere, Alexandre</searchLink><relatesTo>1</relatesTo><br /><searchLink fieldCode="AR" term="%22Johansson%2C+Mikael%22">Johansson, Mikael</searchLink><relatesTo>1</relatesTo><br /><searchLink fieldCode="AR" term="%22Zou%2C+Zhenhua%22">Zou, Zhenhua</searchLink><relatesTo>2</relatesTo><br /><searchLink fieldCode="AR" term="%22Combes%2C+Richard%22">Combes, Richard</searchLink><relatesTo>3</relatesTo>
– Name: TitleSource
  Label: Source
  Group: Src
  Data: <searchLink fieldCode="JN" term="%22IEEE+Transactions+on+Automatic+Control%22">IEEE Transactions on Automatic Control</searchLink>. Apr2018, Vol. 63 Issue 4, p915-930. 16p.
– Name: Subject
  Label: Subjects
  Group: Su
  Data: <searchLink fieldCode="DE" term="%22Stochastic+analysis%22">Stochastic analysis</searchLink><br /><searchLink fieldCode="DE" term="%22Random+operators%22">Random operators</searchLink><br /><searchLink fieldCode="DE" term="%22Matrix+analytic+methods%22">Matrix analytic methods</searchLink><br /><searchLink fieldCode="DE" term="%22Combinatorial+optimization%22">Combinatorial optimization</searchLink><br /><searchLink fieldCode="DE" term="%22Routing+%28Computer+network+management%29%22">Routing (Computer network management)</searchLink>
– Name: Abstract
  Label: Abstract
  Group: Ab
  Data: 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. [ABSTRACT FROM PUBLISHER]
– Name: AbstractSuppliedCopyright
  Label:
  Group: Ab
  Data: <i>Copyright of IEEE Transactions on Automatic Control is the property of IEEE and its content may not be copied or emailed to multiple sites without the copyright holder's express written permission. Additionally, content may not be used with any artificial intelligence tools or machine learning technologies. However, users may print, download, or email articles for individual use. This abstract may be abridged. No warranty is given about the accuracy of the copy. Users should refer to the original published version of the material for the full abstract.</i> (Copyright applies to all Abstracts.)
PLink https://search.ebscohost.com/login.aspx?direct=true&site=eds-live&db=egs&AN=128843712
RecordInfo BibRecord:
  BibEntity:
    Identifiers:
      – Type: doi
        Value: 10.1109/TAC.2017.2747409
    Languages:
      – Code: eng
        Text: English
    PhysicalDescription:
      Pagination:
        PageCount: 16
        StartPage: 915
    Subjects:
      – SubjectFull: Stochastic analysis
        Type: general
      – SubjectFull: Random operators
        Type: general
      – SubjectFull: Matrix analytic methods
        Type: general
      – SubjectFull: Combinatorial optimization
        Type: general
      – SubjectFull: Routing (Computer network management)
        Type: general
    Titles:
      – TitleFull: Stochastic Online Shortest Path Routing: The Value of Feedback.
        Type: main
  BibRelationships:
    HasContributorRelationships:
      – PersonEntity:
          Name:
            NameFull: Talebi, Mohammad Sadegh
      – PersonEntity:
          Name:
            NameFull: Proutiere, Alexandre
      – PersonEntity:
          Name:
            NameFull: Johansson, Mikael
      – PersonEntity:
          Name:
            NameFull: Zou, Zhenhua
      – PersonEntity:
          Name:
            NameFull: Combes, Richard
    IsPartOfRelationships:
      – BibEntity:
          Dates:
            – D: 01
              M: 04
              Text: Apr2018
              Type: published
              Y: 2018
          Identifiers:
            – Type: issn-print
              Value: 00189286
          Numbering:
            – Type: volume
              Value: 63
            – Type: issue
              Value: 4
          Titles:
            – TitleFull: IEEE Transactions on Automatic Control
              Type: main
ResultId 1