Approximation and Online Algorithms for NFV-Enabled Multicasting in SDNs

Zichuan Xu, Weifa Liang, Meitian Huang, Mike Jia, Song Guo, Alex Galis

Research output: Chapter in book / Conference proceedingConference article published in proceeding or bookAcademic researchpeer-review

53 Citations (Scopus)


Multicasting is a fundamental functionality of networks for many applications including online conferencing, event monitoring, video streaming, and system monitoring in data centers. To ensure multicasting reliable, secure and scalable, a service chain consisting of network functions (e.g., firewalls, Intrusion Detection Systems (IDSs), and transcoders) usually is associated with each multicast request. Such a multicast request is referred to as an NFV-enabled multicast request. In this paper we study NFV-enabled multicasting in a Software-Defined Network (SDN) with the aims to minimize the implementation cost of each NFV-enabled multicast request or maximize the network throughput for a sequence of NFV-enabled requests, subject to network resource capacity constraints. We first formulate novel NFV-enabled multicasting and online NFV-enabled multicasting problems. We then devise the very first approximation algorithm with an approximation ratio of 2K for the NFV-enabled multicasting problem if the number of servers for implementing the network functions of each request is no more than a constant K (1). We also study dynamic admissions of NFV-enabled multicast requests without the knowledge of future request arrivals with the objective to maximize the network throughput, for which we propose an online algorithm with a competitive ratio of O(log n) when K = 1, where n is the number of nodes in the network. We finally evaluate the performance of the proposed algorithms through experimental simulations. Experimental results demonstrate that the proposed algorithms outperform other existing heuristics.

Original languageEnglish
Title of host publicationProceedings - IEEE 37th International Conference on Distributed Computing Systems, ICDCS 2017
EditorsKisung Lee, Ling Liu
PublisherInstitute of Electrical and Electronics Engineers Inc.
Number of pages10
ISBN (Electronic)9781538617915
Publication statusPublished - 13 Jul 2017
Event37th IEEE International Conference on Distributed Computing Systems, ICDCS 2017 - J.W. Marriott Hotel, Atlanta, United States
Duration: 5 Jun 20178 Jun 2017

Publication series

NameProceedings - International Conference on Distributed Computing Systems


Conference37th IEEE International Conference on Distributed Computing Systems, ICDCS 2017
Country/TerritoryUnited States


  • Approximation and online algorithms
  • Multicasting
  • Network function virtualization
  • NFV-enabled multicasting
  • Service chains
  • Software-defined networks
  • Virtualized network functions

ASJC Scopus subject areas

  • Software
  • Hardware and Architecture
  • Computer Networks and Communications


Dive into the research topics of 'Approximation and Online Algorithms for NFV-Enabled Multicasting in SDNs'. Together they form a unique fingerprint.

Cite this