Title：Approximation and online algorithms for NFV-enabled multicasting in SDNs

时间:12月11日上午10:00

地点：西十二楼S401

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$ ($\geq 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.

Bio:

Prof. Weifa Liang received his PhD degree from the Australian National University in 1998, the Master of Engineering degree from the University of Science and Technology of China in 1989, and the BSc degree from Wuhan University, China in 1984, all in computer science. He is currently a Full Professor in the Research School of Computer Science at the Australian National University. His research interests include design and analysis of energy efficient routing protocols for wireless ad hoc and sensor networks, cloud computing, Virtual Network Function Placement, Software-Defined Networking, graph databases, design and analysis of parallel and distributed algorithms, approximation algorithms, combinatorial optimization, and graph theory. He has published over 200 journal and conference papers in top venues. He is a senior member of the IEEE.