Scheduling congestion-and loop-free network update in timed SDNs

Jiaqi Zheng, Guihai Chen*, Stefan Schmid, Haipeng Dai, Jie Wu, Qiang Ni

*Corresponding author for this work

Research output: Contribution to journalJournal articleResearchpeer-review

22 Citations (Scopus)

Abstract

Software-defined networks (SDNs) introduce interesting new opportunities in how network routes can be defined, verified, and changed over time. Despite the logically-centralized perspective offered, however, an SDN still needs to be considered a distributed system: rule updates communicated from the controller to the individual switches traverse an asynchronous network and may arrive out-of-order. This can lead to (temporary or permanent) inconsistencies and triggered much research over the last years. We, in this paper, initiate the study of algorithms for consistent network updates in 'timed SDNs'-SDNs in which individual node updates can be scheduled at specific times. While technology enabling tightly synchronized SDNs is emerging, the resulting algorithmic problems have not been studied yet. This paper presents, implements and evaluates Chronus, a system which provides provably congestion-and loop-free network updates, while avoiding the flow table space headroom required by existing two-phase update approaches. We formulate the minimum update time problem as an optimization program and propose two polynomial-time algorithms which lie at the heart of Chronus: a decision algorithm to check feasibility and a greedy algorithm to find a good update sequence. Extensive experiments on Mininet and numerical simulations show that Chronus can substantially reduce transient congestion and save over 60% of the rules compared with the state of the art.

Original languageEnglish
Article number8058446
JournalIEEE Journal on Selected Areas in Communications
Volume35
Issue number11
Pages (from-to)2542-2552
Number of pages11
ISSN0733-8716
DOIs
Publication statusPublished - 1 Nov 2017

Keywords

  • Clock synchronization
  • Congestion-free
  • Loop-free
  • Network updates
  • SDN

Fingerprint

Dive into the research topics of 'Scheduling congestion-and loop-free network update in timed SDNs'. Together they form a unique fingerprint.

Cite this