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/Report/Conference proceedingConference contributionpeer-review

    55 Citations (Scopus)

    Abstract

    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.
    Pages625-634
    Number of pages10
    ISBN (Electronic)9781538617915
    DOIs
    Publication statusPublished - 13 Jul 2017
    Event37th IEEE International Conference on Distributed Computing Systems, ICDCS 2017 - Atlanta, United States
    Duration: 5 Jun 20178 Jun 2017

    Publication series

    NameProceedings - International Conference on Distributed Computing Systems

    Conference

    Conference37th IEEE International Conference on Distributed Computing Systems, ICDCS 2017
    Country/TerritoryUnited States
    CityAtlanta
    Period5/06/178/06/17

    Fingerprint

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

    Cite this