View in EDS

Loop-Free Route Updates for Software-Defined Networks.

Saved in:
Bibliographic Details
Title: Loop-Free Route Updates for Software-Defined Networks.
Authors: Foerster, Klaus-Tycho1, Ludwig, Arne2, Marcinkowski, Jan3, Schmid, Stefan4
Source: IEEE/ACM Transactions on Networking. Feb2018, Vol. 26 Issue 1, p328-341. 14p.
Subjects: Graph algorithms, Traffic engineering software, IP networks, Loop tiling (Computer science), Integer programming
Abstract: We consider the fundamental problem of updating arbitrary routes in a software-defined network in a (transiently) loop-free manner. Our objective is to compute fast network update schedules which minimize the number of interactions (i.e., rounds) between the controller and the network nodes. We first prove that this problem is difficult in general: The problem of deciding whether a $k$ -round update schedule exists is NP-complete already for $k=3$ , and there are problem instances requiring $\Omega (n)$ rounds, where $n$ is the network size. Given these negative results, we introduce an attractive, relaxed notion of loop-freedom. We show that relaxed loop-freedom admits for much shorter update schedules (up to a factor $\Omega (n)$ in the best case), and present a scheduling algorithm which requires at most $\Theta (\log n)$ rounds. [ABSTRACT FROM AUTHOR]
Copyright of IEEE/ACM Transactions on Networking 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: 128054283
AccessLevel: 6
PubType: Academic Journal
PubTypeId: academicJournal
PreciseRelevancyScore: 0
IllustrationInfo
Items – Name: Title
  Label: Title
  Group: Ti
  Data: Loop-Free Route Updates for Software-Defined Networks.
– Name: Author
  Label: Authors
  Group: Au
  Data: <searchLink fieldCode="AR" term="%22Foerster%2C+Klaus-Tycho%22">Foerster, Klaus-Tycho</searchLink><relatesTo>1</relatesTo><br /><searchLink fieldCode="AR" term="%22Ludwig%2C+Arne%22">Ludwig, Arne</searchLink><relatesTo>2</relatesTo><br /><searchLink fieldCode="AR" term="%22Marcinkowski%2C+Jan%22">Marcinkowski, Jan</searchLink><relatesTo>3</relatesTo><br /><searchLink fieldCode="AR" term="%22Schmid%2C+Stefan%22">Schmid, Stefan</searchLink><relatesTo>4</relatesTo>
– Name: TitleSource
  Label: Source
  Group: Src
  Data: <searchLink fieldCode="JN" term="%22IEEE%2FACM+Transactions+on+Networking%22">IEEE/ACM Transactions on Networking</searchLink>. Feb2018, Vol. 26 Issue 1, p328-341. 14p.
– Name: Subject
  Label: Subjects
  Group: Su
  Data: <searchLink fieldCode="DE" term="%22Graph+algorithms%22">Graph algorithms</searchLink><br /><searchLink fieldCode="DE" term="%22Traffic+engineering+software%22">Traffic engineering software</searchLink><br /><searchLink fieldCode="DE" term="%22IP+networks%22">IP networks</searchLink><br /><searchLink fieldCode="DE" term="%22Loop+tiling+%28Computer+science%29%22">Loop tiling (Computer science)</searchLink><br /><searchLink fieldCode="DE" term="%22Integer+programming%22">Integer programming</searchLink>
– Name: Abstract
  Label: Abstract
  Group: Ab
  Data: We consider the fundamental problem of updating arbitrary routes in a software-defined network in a (transiently) loop-free manner. Our objective is to compute fast network update schedules which minimize the number of interactions (i.e., rounds) between the controller and the network nodes. We first prove that this problem is difficult in general: The problem of deciding whether a $k$ -round update schedule exists is NP-complete already for $k=3$ , and there are problem instances requiring $\Omega (n)$ rounds, where $n$ is the network size. Given these negative results, we introduce an attractive, relaxed notion of loop-freedom. We show that relaxed loop-freedom admits for much shorter update schedules (up to a factor $\Omega (n)$ in the best case), and present a scheduling algorithm which requires at most $\Theta (\log n)$ rounds. [ABSTRACT FROM AUTHOR]
– Name: AbstractSuppliedCopyright
  Label:
  Group: Ab
  Data: <i>Copyright of IEEE/ACM Transactions on Networking 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=128054283
RecordInfo BibRecord:
  BibEntity:
    Identifiers:
      – Type: doi
        Value: 10.1109/TNET.2017.2778426
    Languages:
      – Code: eng
        Text: English
    PhysicalDescription:
      Pagination:
        PageCount: 14
        StartPage: 328
    Subjects:
      – SubjectFull: Graph algorithms
        Type: general
      – SubjectFull: Traffic engineering software
        Type: general
      – SubjectFull: IP networks
        Type: general
      – SubjectFull: Loop tiling (Computer science)
        Type: general
      – SubjectFull: Integer programming
        Type: general
    Titles:
      – TitleFull: Loop-Free Route Updates for Software-Defined Networks.
        Type: main
  BibRelationships:
    HasContributorRelationships:
      – PersonEntity:
          Name:
            NameFull: Foerster, Klaus-Tycho
      – PersonEntity:
          Name:
            NameFull: Ludwig, Arne
      – PersonEntity:
          Name:
            NameFull: Marcinkowski, Jan
      – PersonEntity:
          Name:
            NameFull: Schmid, Stefan
    IsPartOfRelationships:
      – BibEntity:
          Dates:
            – D: 01
              M: 02
              Text: Feb2018
              Type: published
              Y: 2018
          Identifiers:
            – Type: issn-print
              Value: 10636692
          Numbering:
            – Type: volume
              Value: 26
            – Type: issue
              Value: 1
          Titles:
            – TitleFull: IEEE/ACM Transactions on Networking
              Type: main
ResultId 1