Online unicasting and multicasting in software-defined networks

Meitian Huang, Weifa Liang, Zichuan Xu, Wenzheng Xu, Song Guo, Yinlong Xu

Research output: Journal article publicationJournal articleAcademic researchpeer-review

5 Citations (Scopus)

Abstract

Software-Defined Networking (SDN) has emerged as the paradigm of the next-generation networking through separating the control plane from the data plane. In a software-defined network, the forwarding table at each switch node usually is implemented by expensive and power-hungry Ternary Content Addressable Memory (TCAM) that only has limited numbers of entries. In addition, the bandwidth capacity at each link is limited as well. Provisioning quality services to users by admitting their requests subject to such critical network resource constraints is a fundamental problem, and very little attention has been paid. In this paper, we study online unicasting and multicasting in SDNs with an objective of maximizing the network throughput under network resource constraints, for which we first propose a novel cost model to accurately capture the usages of network resources at switch nodes and links. We then devise two online algorithms with competitive ratios O(log n) and O(Kϵlog n) for online unicasting and multicasting, respectively, where n is the network size, K is the maximum number of destinations in any multicast request, and ϵ is a constant with 0 < ϵ ≤ 1. We finally evaluate the proposed algorithms empirically through simulations. The simulation results demonstrate that the proposed algorithms are very promising.

Original languageEnglish
Pages (from-to)26-39
Number of pages14
JournalComputer Networks
Volume132
DOIs
Publication statusPublished - 26 Feb 2018

Keywords

  • Combinatorial optimization
  • Competitive ratio analysis
  • Dynamic unicast and multicast request admissions
  • Network resource allocation
  • Online algorithms
  • Software-defined networks
  • Ternary content addressable memory (TCAM)

ASJC Scopus subject areas

  • Computer Networks and Communications

Cite this