# QoS-Based Multicast Routing in Network Function Virtualization-Enabled Software-Defined Mobile Edge Computing Networks

Authors: Shimin Sun; Xinchao Zhang; Wentian Huang; Aixin Xu; Xiaofan Wang; Li Han
Journal: Mobile Information Systems
 (2021)

---

## Abstract

Mobile Edge Computing (MEC) technology brings the unprecedented computing capacity to the edge of mobile network. It provides the cloud and end user swift high-quality services with seamless integration of mobile network and Internet. With powerful capability, virtualized network functions can be allocated to MEC. In this paper, we study QoS guaranteed multicasting routing with Network Function Virtualization (NFV) in MEC. Specifically, data should pass through a service function chain before reaching destinations along a multicast tree with minimal computational cost and meeting QoS requirements. Furthermore, to overcome the problems of traditional IP multicast and software-defined multicasting approaches, we propose an implementable multicast mechanism that delivers data along multicast tree but uses unicast sessions. We finally evaluate the performance of the proposed mechanism based on experimental simulations. The results show that our mechanism outperforms others reported in the literature.


---

## Body

## 1. Introduction

In recent years, social networking and personal entertainment have made great success. In many popular scenarios, concurrent subscribers receive data from single or multiple servers, such as remote video conference, online education, and interactive gaming. This paradigm is deemed to be multicasting. Nevertheless, data from most current applications are distributed in a multicast pattern but use unicast sessions in practice. The replicated data put huge traffic pressure on server-side and backbone networks. Meanwhile, with specific requirements, data needs to pass various network functions before reaching destinations, such as Encoder, Network Address Translation (NAT), firewall, Intrusion Detection Systems (IDS), and proxies. The implementation of those functions using a software instance is called Network Function Virtualization (NFV) [1]. As a core functionality of Software-Defined Networking (SDN), NFV is a promising technique to replace the hardware network middle box. It implements network functions in software-based Virtual Machine (VM) instances. Each network function, named Virtual Network Function (VNF), can be deployed on commodity server and further on Mobile Edge Cloud (Computing) (MEC) [2, 3].With the explosive growth of mobile terminals and application markets, application technology is progressing by leaps [4, 5]. The demands of computational resource on terminals promote the rapid development of MEC technology. MEC has emerged as the light cloud computing distributed at the edge of core network. It realizes data processing and storage capability in the vicinity of terminal devices. Allocating at the edge, MEC significantly reduces the response delay in some situations and enhances the capabilities of mobile users with ever-growing resource demands [6, 7].A sequenced chain of VNFs comprises a service function chain. A service function chain can be flexibly composed of a series of heterogeneous VNF nodes from different MECs to process massive data flows. Different types of multicast services may require different combination and order of VNFs. To improve the efficiency of resource utilization of MECs, VNFs can be placed on different cloudlets. The implementation of NFV is usually combined with SDN [8], because SDN enables flexible management of VNF placement.Provisioning multicasting service with a specific network function chain in software-defined MEC is a promising technique and poses many challenges. Firstly, most of the studies on multicasting in MEC or SDN are based on classic IP multicast [9–12], which is not negligible to face those basic issues [13]. The applicability is necessary to be concerned before designing multicasting mechanism. Secondly, comparing with self-contained centralized cloud networks, the computing and storage resource at cloudlets and link capacity is limited to accommodate VM-based VNFs. There should be a consultation mechanism on how to efficiently apply existing or create new VNF instances to minimize the operational cost and meanwhile satisfy the QoS requirements of applications [14]. Further, how to steer data traffic to pass a specific sequence of network functions within a reasonable cost should be deliberated [15].In this paper, we address the aforementioned challenges by presenting an implementable multicast mechanism in software-defined hybrid MEC network, including cost modelling, data processing mechanism, and tree construction algorithm. The novelties and contributions of this paper are as follows:(a)
We present an implementable multicast mechanism using the SDN technique to overcome the dilemma of traditional IP multicast. Based on our mechanisms, legacy network devices and terminal users are unnecessarily aware of data distribution pattern. The server sends data in unicast sessions (not tunnelling) to each destination. Therefore, the presented mechanisms are not only limited to apply to MEC networks but also suitable for SDN/Internet hybrid networks.(b)
We study the problems of NFV-enabled QoS multicasting in MEC networks, exploring VNF instance placement and resource sharing. We strive for the minimum of accumulative computational cost while meeting the QoS requirements of applications. We further present an NFV-enabled QoS guaranteed multicast tree construction algorithm.(c)
We evaluate the performance of the proposed algorithms through experimental simulations. The results demonstrate that the proposed algorithms are promising and outperform compared algorithms.The remainder of this paper is organized as follows. Section2 reviews the related work. Section 3 introduces the system model, notions and notations, and problem definitions. Section 4 develops an implementable SDN-based NFV-enabled QoS multicasting mechanism. Section 5 elaborates the detailed multicast tree maintenance algorithms. Section 6 evaluates the proposed algorithms empirically, and Section 7 concludes the paper.


## 2. Related Work

Network traffic engineering has regained much attention due to the opportunities introduced by SDN [9, 16, 17]. Many studies are devoted to finding the optimal placement of VNFs [14, 15, 18, 19]. However, most of them were primarily applied to unicast communication scenarios. For example, Golkarifard et al. [14] presented a dynamic VNF placement algorithm in 5G environment. Yu et al. [19] address the VNF placement to minimize cost and meet the delay demand of each unicast session.Recently, many studies focus on multicast mechanisms in SDN [9, 20] and NFV-enabled multicasting [10, 21]. For instance, Chiang et al. [9] proposed a dynamic group management approach, Online Branch-aware Steiner Tree (OBST). OBST considers bandwidth utilization, tree scalability, and rerouting overhead. Alhussein et al. [21] presented a multicast service orchestration framework to deal with joint routing and VNF placement problem, while maximizing the throughput of the physical substrate and minimizing the provisioning cost. He et al. [10] took into account QoS constraints to build a reliable multicast tree with recovery nodes and passing a service chain. The overhead could be large for data recovery using response messages if the network is unstable. However, those proposals did not take into account the computation capacity of edge cloudlets, as well as the applicability in real hybrid Internet/MEC networks.There are rare studies on multicasting in NFV-enabled MEC networks [11, 12]. Ma et al. [11] focused on the maximization of throughput. To minimize the cost, they presented an approximation algorithm and an online throughput maximization algorithm. Ren et al. [12] proposed a delay-aware NFV-enabled multicasting mechanism. They presented an approximation algorithm and a heuristic algorithm with and without delay constraint. Although those NFV-enabled multicasting algorithms aimed to minimize resource expense, they did not involve the combined constraints of QoS demands and computing capacity of cloudlets. Most of the above researches did not consider the basic implementation method of data distribution. Thus, it is an urgent problem to design an implementable multicasting approach before putting into effect the aforementioned algorithms.For the deployment of multicasting in SDN, most of the studies endeavoured to implement or amend IP multicast mechanisms. That is, data dissemination is still based on multicast IP addresses and inevitably suffers from most of IP multicast problems. For instance, MultiFlow [22] developed an approach to parse IGMP messages by OpenFlow switches (OFSs), in order to perform group member management. OFM [23] developed multicast services from a clean-slate perspective. The limitation of MultiFlow and OFM is that OFSs need to have the capability of parsing group joining and departure messages. Locality-Aware Multicast Approach (LAMA) [24] reduced the computation cost of multicast tree construction by designing an election algorithm of Rendezvous Point (RP). The algorithm calculates the distances from RP to all sources and generates a minimum tree. The problem is that RP election algorithm requires additional message exchanging, which causes packet overhead and challenges the capacity of flow table. SDM [25] attempted to slice multicast tree by designing SDM domain consisting of pure SDN devices to distribute traffic using multicast address. A flow table entry was required for each group. Specific messages were elaborated to realize the functions of network entities, such as NL-SDM and Virtual Peer Instance. In brief, all those proposals use IP multicast mechanism or design new protocols to manage groups and parse multicast traffic.


## 3. Preliminaries

In this section, we first introduce the system model, notations, and key concepts and then define the problems precisely.


### 3.1. System Model

We consider an MEC network modelled by an undirected graphG=V,E with a set V of OpenFlow-enabled access points (APs), OFSs, cloudlets, and a set E of links in the network. Each cloudlet is colocated with an AP node (or an OFS) vv∈V connected via a high-speed optical cable. Communication delay between cloudlet and directly connected APs is negligible. Cloudlets have the computing and storage capacity to implement various VNFs based on VMs. There is at least one SDN controller taking the role of the brain of the network. SDN controller is responsible for network traffic steering, multicast group management, and placement of VNFs.In Figure1, we present an illustrative example of an NFV-enabled MEC network, in which some of the APs/OFSs are attached to cloudlets, while the rest nodes are not. VNF-enabled APs/OFSs provide VNF support on behalf of multicasting services. SDN controller is responsible for the management of APs/OFSs, while the source node produces streaming and provides the information of group members. All those entities connect to the Internet. All the links could be direct physical links or virtual links.Figure 1
An illustrative example of an MEC network with VNFs and SDN.


### 3.2. Cost Model of NFV-Enabled QoS Multicast Routing

For real-time service, QoS multicast routing is essential to provide high-quality service. In this paper, our study achieves the objective that is constructing multicast tree with NFV support and meeting QoS constraints. For QoS guarantee, we mainly consider the QoS service in two aspects: delay constraints and bandwidth constraints.Delay constraints: it is assumed thatPk is a set of unicast routes from source Sk to destination Dk in the multicast graph. Path pm∈Pk denotes the path from Sk to a destination. The maximal delay is incurred by the largest end-to-end delay of pm. Then, we can define the transmission delay dkt using(1)dkt=maxpm∈Pk∑e∈pmdu,v.Without loss of generality, it is assumed that the processing delay of pathp, denoted bydkp, is proportional to the data rate of the flow. The processing delay may be different, since the computational consumption of each VNF is disparate. Besides, the processing delay of VNF and legacy routers is also discrepant. Generally, the functionality implemented by hardware is much faster than implemented by software. Therefore, dkp can be deduced by the sum of processing delay of each VNF and legacy routers, denoted by(2)dkp=∑fk,i∈SCkαj⋅rk+∑e∈E,e∉SCkβ⋅rk,where αj and β are given proportional factors for each VNF processing delay and legacy network device processing delay, respectively.Finally, we obtain the maximum delaydk of the multicast tree, depicted in equation (3). To meet the delay demand of service k, dk should be lower than delay threshold Dk; that is, dk<Dk.(3)dk=dkt+dkp.Bandwidth constraints: denote bybp the available bandwidth of a path pm∈Pk from source Sk to destination Dk. Denote by bm the minimum bandwidth of a multicast tree. Then, bp and bm can be calculated by equations (4) and (5)(4)bp=mine∈Pmeu,v,(5)bm=minpm∈Pkbp.Demand bandwidthBk should be larger than bm; that is, bm>Bk.Instantiating a new VNF instance consumes both computing and storage resources. The cost of setting up a new VNF is denoted bycinsfk,i,v. Unit data processing cost using an existing instance of function fk in cloudlet v is indicated bycprocfk,i,v. Then, the processing cost of a service with data rate rk is rk⋅cprocfk,i,v. Notice that, the placement of VNFs on different cloudlets may result in different cost. Let nins be the number of newly created instances for fk,i in cloudlet v, while next is the number of existing instances to process data on behalf of fk,i.The total operational cost fork-th multicast service is represented by the sum of the cost of setting up new VNFs and the processing cost of k-th service with data rate rk.The cost of setting up new VNFs for the multicast service is∑fk,i∈SCknins⋅cinsfk,i,v. The processing cost of all VNFs is∑fk,i∈SCknins+next⋅rk⋅cprocfk,i,v.Then, the total cost to implement and run all VNFs can be specified as(6)Ck=∑fk,i∈SCknins⋅cinsfk,i,v+nins+next⋅rk⋅cprocfk,i,v.For a service function chainSCk = fk,1,fk,2,…,fk,Lk with m available cloudlets, the total cost can be represented by a matrix, as shown in equation (7). Where the set (CL1, CL2, …, CLm) is the cloudlets that have sufficient resource to implement VNF instances, the element is the operational cost of a VNF implementing on a cloudlet. Then, the computational cost of each cloudlet is the summation of each row, which has an upper bound threshold depending on the computation capability of each cloudlet.(7)For clarity, the symbols that used in this paper are summarized in Table1.Table 1
Symbols.
SymbolsMeaningG=V,EA software-defined Mobile Edge Cloud network with a setV of OpenFlow switches (OFSs) or APs and a set E of linksv and eAn OFS node or an AP nodevv∈V and a link ee∈ECvThe available computing capacity of the cloudlet attached to nodevMk = Sk,Dk,SCk,bk,dkThek-th multicast service with source node Sk, the set of destinations Dk, the service chain SCk that consists of a sequence of VNFs, bandwidth requirement bk, and delay limitation dkLkThe number of VNFs inSCkSCk = fk,1,fk,2,…,fk,LkA service chain fork-th multicast service consisting of Lk-th functionsfk,1,fk,2,⋯,fk,Lkcf,mComputational cost to implement a VNFf on VM mdu,vDelay of linke(u, v)bu,vAvailable bandwidth of linke(u, v)rkData rate ofk-th multicast servicePkA set of unicast route from sourceSk to each destination from DkpmA route from sourceSk to a destinationdkt and dkpTransmission delay and processing delay, respectivelydkThe maximum delay of the multicast treebp and bmThe minimum bandwidth of a path and a multicast tree, respectivelyDk and BkQoS requirement of delay and bandwidth, respectivelycinsfk,i,vThe cost of instantiating a new VNF instancei on node v for k-th multicast servicecprocfk,i,vThe cost of using an existing VNF instancei on node v for k-th multicast serviceCkThe total operational cost for multicast servicekCL = (CL1, CL2, …, CLm)A set of cloudlets that have sufficient resource to implement VNF instancesVNFL = (VNF1, VNF2, …, VNFn)VNF that exists or can be created for a multicast service


### 3.3. Problem Definitions

Problem 1.
Most of the studies focus on the functional design of multicast routing and ignore the implementation of basic functionalities, in most cases, IP multicast. Because IP multicast is far from being widely deployed in current Internet architecture, puzzled by router capability, scalability, security, economic efficiency, and so on. Therefore, it is difficult to be implemented in large-scale networks.
The first challenge is to design an implementable multicast approach that can be facilely applied to real IP networks. In particular, with the development of new-type network technology, such as SDN and MEC, there emerge new thoughts and innovation opportunities to be put forward to novel multicasting algorithms. Therefore, we attempt to design an implementable multicast mechanism considering NFV and QoS requirements, which is compatible to SDN, MEC, and various Internet hybrid networks.Problem 2.
NFV-enable multicast routing with QoS guarantee problem is NP-hard.Proof.
NFV-enable multicast routing is a special case of classic QoS multicast routing without NFV support. It builds a multicast tree from source to destinations passing by a series of VNFs. For simplicity, we split the process of tree construction into two steps. First, the paths from source to the last VNF of a service chain are sorted by the cost of equation (6). Then, we construct the minimal multicast tree from each last VNF to destinations with QoS guarantees. Finally, the optimal multicast tree is generated with NFV-enabled and meeting QoS requirements. According to literature [11, 13, 26], multicast tree construction problem can be reduced to a Steiner tree problem.Problem 3.
NFV-enable multicast routing problem in MEC network is to route the traffic to each destination bypassing either existing or newly created VNF instances. Such that, it requires that the operational cost is minimum, while satisfying the QoS requirementsDk and Bk, as well as the capacity constraint of each cloudlet. If the computational resource of each cloudlet is sufficient to implement all required VNFs, the problem is simplified into a QoS constraints multicast routing problem that is to find a QoS guaranteed minimal spanning tree, while the VNFs can be placed on any cloudlet on the paths from source to each destination.


## 3.1. System Model

We consider an MEC network modelled by an undirected graphG=V,E with a set V of OpenFlow-enabled access points (APs), OFSs, cloudlets, and a set E of links in the network. Each cloudlet is colocated with an AP node (or an OFS) vv∈V connected via a high-speed optical cable. Communication delay between cloudlet and directly connected APs is negligible. Cloudlets have the computing and storage capacity to implement various VNFs based on VMs. There is at least one SDN controller taking the role of the brain of the network. SDN controller is responsible for network traffic steering, multicast group management, and placement of VNFs.In Figure1, we present an illustrative example of an NFV-enabled MEC network, in which some of the APs/OFSs are attached to cloudlets, while the rest nodes are not. VNF-enabled APs/OFSs provide VNF support on behalf of multicasting services. SDN controller is responsible for the management of APs/OFSs, while the source node produces streaming and provides the information of group members. All those entities connect to the Internet. All the links could be direct physical links or virtual links.Figure 1
An illustrative example of an MEC network with VNFs and SDN.


## 3.2. Cost Model of NFV-Enabled QoS Multicast Routing

For real-time service, QoS multicast routing is essential to provide high-quality service. In this paper, our study achieves the objective that is constructing multicast tree with NFV support and meeting QoS constraints. For QoS guarantee, we mainly consider the QoS service in two aspects: delay constraints and bandwidth constraints.Delay constraints: it is assumed thatPk is a set of unicast routes from source Sk to destination Dk in the multicast graph. Path pm∈Pk denotes the path from Sk to a destination. The maximal delay is incurred by the largest end-to-end delay of pm. Then, we can define the transmission delay dkt using(1)dkt=maxpm∈Pk∑e∈pmdu,v.Without loss of generality, it is assumed that the processing delay of pathp, denoted bydkp, is proportional to the data rate of the flow. The processing delay may be different, since the computational consumption of each VNF is disparate. Besides, the processing delay of VNF and legacy routers is also discrepant. Generally, the functionality implemented by hardware is much faster than implemented by software. Therefore, dkp can be deduced by the sum of processing delay of each VNF and legacy routers, denoted by(2)dkp=∑fk,i∈SCkαj⋅rk+∑e∈E,e∉SCkβ⋅rk,where αj and β are given proportional factors for each VNF processing delay and legacy network device processing delay, respectively.Finally, we obtain the maximum delaydk of the multicast tree, depicted in equation (3). To meet the delay demand of service k, dk should be lower than delay threshold Dk; that is, dk<Dk.(3)dk=dkt+dkp.Bandwidth constraints: denote bybp the available bandwidth of a path pm∈Pk from source Sk to destination Dk. Denote by bm the minimum bandwidth of a multicast tree. Then, bp and bm can be calculated by equations (4) and (5)(4)bp=mine∈Pmeu,v,(5)bm=minpm∈Pkbp.Demand bandwidthBk should be larger than bm; that is, bm>Bk.Instantiating a new VNF instance consumes both computing and storage resources. The cost of setting up a new VNF is denoted bycinsfk,i,v. Unit data processing cost using an existing instance of function fk in cloudlet v is indicated bycprocfk,i,v. Then, the processing cost of a service with data rate rk is rk⋅cprocfk,i,v. Notice that, the placement of VNFs on different cloudlets may result in different cost. Let nins be the number of newly created instances for fk,i in cloudlet v, while next is the number of existing instances to process data on behalf of fk,i.The total operational cost fork-th multicast service is represented by the sum of the cost of setting up new VNFs and the processing cost of k-th service with data rate rk.The cost of setting up new VNFs for the multicast service is∑fk,i∈SCknins⋅cinsfk,i,v. The processing cost of all VNFs is∑fk,i∈SCknins+next⋅rk⋅cprocfk,i,v.Then, the total cost to implement and run all VNFs can be specified as(6)Ck=∑fk,i∈SCknins⋅cinsfk,i,v+nins+next⋅rk⋅cprocfk,i,v.For a service function chainSCk = fk,1,fk,2,…,fk,Lk with m available cloudlets, the total cost can be represented by a matrix, as shown in equation (7). Where the set (CL1, CL2, …, CLm) is the cloudlets that have sufficient resource to implement VNF instances, the element is the operational cost of a VNF implementing on a cloudlet. Then, the computational cost of each cloudlet is the summation of each row, which has an upper bound threshold depending on the computation capability of each cloudlet.(7)For clarity, the symbols that used in this paper are summarized in Table1.Table 1
Symbols.
SymbolsMeaningG=V,EA software-defined Mobile Edge Cloud network with a setV of OpenFlow switches (OFSs) or APs and a set E of linksv and eAn OFS node or an AP nodevv∈V and a link ee∈ECvThe available computing capacity of the cloudlet attached to nodevMk = Sk,Dk,SCk,bk,dkThek-th multicast service with source node Sk, the set of destinations Dk, the service chain SCk that consists of a sequence of VNFs, bandwidth requirement bk, and delay limitation dkLkThe number of VNFs inSCkSCk = fk,1,fk,2,…,fk,LkA service chain fork-th multicast service consisting of Lk-th functionsfk,1,fk,2,⋯,fk,Lkcf,mComputational cost to implement a VNFf on VM mdu,vDelay of linke(u, v)bu,vAvailable bandwidth of linke(u, v)rkData rate ofk-th multicast servicePkA set of unicast route from sourceSk to each destination from DkpmA route from sourceSk to a destinationdkt and dkpTransmission delay and processing delay, respectivelydkThe maximum delay of the multicast treebp and bmThe minimum bandwidth of a path and a multicast tree, respectivelyDk and BkQoS requirement of delay and bandwidth, respectivelycinsfk,i,vThe cost of instantiating a new VNF instancei on node v for k-th multicast servicecprocfk,i,vThe cost of using an existing VNF instancei on node v for k-th multicast serviceCkThe total operational cost for multicast servicekCL = (CL1, CL2, …, CLm)A set of cloudlets that have sufficient resource to implement VNF instancesVNFL = (VNF1, VNF2, …, VNFn)VNF that exists or can be created for a multicast service


## 3.3. Problem Definitions

Problem 1.
Most of the studies focus on the functional design of multicast routing and ignore the implementation of basic functionalities, in most cases, IP multicast. Because IP multicast is far from being widely deployed in current Internet architecture, puzzled by router capability, scalability, security, economic efficiency, and so on. Therefore, it is difficult to be implemented in large-scale networks.
The first challenge is to design an implementable multicast approach that can be facilely applied to real IP networks. In particular, with the development of new-type network technology, such as SDN and MEC, there emerge new thoughts and innovation opportunities to be put forward to novel multicasting algorithms. Therefore, we attempt to design an implementable multicast mechanism considering NFV and QoS requirements, which is compatible to SDN, MEC, and various Internet hybrid networks.Problem 2.
NFV-enable multicast routing with QoS guarantee problem is NP-hard.Proof.
NFV-enable multicast routing is a special case of classic QoS multicast routing without NFV support. It builds a multicast tree from source to destinations passing by a series of VNFs. For simplicity, we split the process of tree construction into two steps. First, the paths from source to the last VNF of a service chain are sorted by the cost of equation (6). Then, we construct the minimal multicast tree from each last VNF to destinations with QoS guarantees. Finally, the optimal multicast tree is generated with NFV-enabled and meeting QoS requirements. According to literature [11, 13, 26], multicast tree construction problem can be reduced to a Steiner tree problem.Problem 3.
NFV-enable multicast routing problem in MEC network is to route the traffic to each destination bypassing either existing or newly created VNF instances. Such that, it requires that the operational cost is minimum, while satisfying the QoS requirementsDk and Bk, as well as the capacity constraint of each cloudlet. If the computational resource of each cloudlet is sufficient to implement all required VNFs, the problem is simplified into a QoS constraints multicast routing problem that is to find a QoS guaranteed minimal spanning tree, while the VNFs can be placed on any cloudlet on the paths from source to each destination.


## 4. Design of Implementable SDN-Based Multicasting Routing Architecture

### 4.1. System Architecture

The proposed mechanism is built on top of overlay SDN architecture with three layered planes. Functionalities are designed as application modules in application plane, routing decision distributed by SDN controller in control plane [27, 28] and executed by OFSs in data plane. Unlike other studies, we involve servers as a participant for multicast group management. Then, it is much easier to manage group members from the point of both source and SDN controller. The roles and responsibilities of the main entities are described as follows. Parts of the content of this section have been presented in our previous work [29].Receiver. End host that initiates service request in a unicast session to a source node. Commonly, it also receives data from this unicast session. Thus, it is transparent to multicast data distribution mechanism.Source. Server that provides data distribution service. In this proposal, it acts not only as a resource server but also as a participant for group management. It is responsible for maintaining the unicast session information with each receiver and meanwhile keeping the information of receivers updated with SDN controller.SDN Controller. The brain of the whole system. It allocates network resource, manages multicast group, constructs and maintains multicast tree, distributes decisions where to place VNFs, and so on.OpenFlow Switch and OpenFlow-enabled AP. In the virtualized overlay network, OFS is the network entities managed and controlled by SDN controller. They connect to cloudlets, Internet, and each other. OFS is the actor of data forwarding strictly following the rules from controllers. More importantly, it monitors the status of direct links and counts the statistics of processed packets.Legacy router. Except OFSs, there are numerous legacy routers in the current dominant Internet. They are lacking programmability and out of the control of controller. They are used to connect OFSs. When building virtualized overlay network, legacy routers are ignored since they do not participate in any multicast-related operation.


### 4.2. Processing of Multicast Service

The procedure of multicast service is illustrated in Figure2. It is assumed that source node S accesses the Internet by an OFS and provides only a single streaming service. Before initiating the steaming, source needs to complete the authentication to controller. A multicast address is assigned to S to indicate the multicast service.Figure 2
Brief illustration of functional flowchart.Initially,S does not stream and waits for service request. After that, host R1 issues the first service request to S. S replies a response message to R1 encapsulating an authentication request. The authentication can be completed based on frequently used password-based authentication, which is out of the scope of this paper and will not be further extended. After achieving authentication, S creates a unicast session with R1. It fetches the session information from the exchanged packets and stores it to the receiver list. Since R1 is the first receiver of the service, S issues data to R1 through the unicast session along the default routing path. OFSs on the path may report the arrival of new packets to the controller and request for admission of access.After that, other hosts may request the service.S maintains the receiver list dynamically and updates synchronously with the controller. As decision-maker, SDN controller constructs and adjusts the multicasts tree along with the joining and departure of receivers. It issues rules to the corresponding OFSs on behalf of data dissemination for each receiver. Data manipulation mechanism will be presented in Section 5.When receiver leaving, the corresponding session will be closed. The information of the receiver is removed from the receiver list. Tree adjustment algorithm initiates if necessary.


## 4.1. System Architecture

The proposed mechanism is built on top of overlay SDN architecture with three layered planes. Functionalities are designed as application modules in application plane, routing decision distributed by SDN controller in control plane [27, 28] and executed by OFSs in data plane. Unlike other studies, we involve servers as a participant for multicast group management. Then, it is much easier to manage group members from the point of both source and SDN controller. The roles and responsibilities of the main entities are described as follows. Parts of the content of this section have been presented in our previous work [29].Receiver. End host that initiates service request in a unicast session to a source node. Commonly, it also receives data from this unicast session. Thus, it is transparent to multicast data distribution mechanism.Source. Server that provides data distribution service. In this proposal, it acts not only as a resource server but also as a participant for group management. It is responsible for maintaining the unicast session information with each receiver and meanwhile keeping the information of receivers updated with SDN controller.SDN Controller. The brain of the whole system. It allocates network resource, manages multicast group, constructs and maintains multicast tree, distributes decisions where to place VNFs, and so on.OpenFlow Switch and OpenFlow-enabled AP. In the virtualized overlay network, OFS is the network entities managed and controlled by SDN controller. They connect to cloudlets, Internet, and each other. OFS is the actor of data forwarding strictly following the rules from controllers. More importantly, it monitors the status of direct links and counts the statistics of processed packets.Legacy router. Except OFSs, there are numerous legacy routers in the current dominant Internet. They are lacking programmability and out of the control of controller. They are used to connect OFSs. When building virtualized overlay network, legacy routers are ignored since they do not participate in any multicast-related operation.


## 4.2. Processing of Multicast Service

The procedure of multicast service is illustrated in Figure2. It is assumed that source node S accesses the Internet by an OFS and provides only a single streaming service. Before initiating the steaming, source needs to complete the authentication to controller. A multicast address is assigned to S to indicate the multicast service.Figure 2
Brief illustration of functional flowchart.Initially,S does not stream and waits for service request. After that, host R1 issues the first service request to S. S replies a response message to R1 encapsulating an authentication request. The authentication can be completed based on frequently used password-based authentication, which is out of the scope of this paper and will not be further extended. After achieving authentication, S creates a unicast session with R1. It fetches the session information from the exchanged packets and stores it to the receiver list. Since R1 is the first receiver of the service, S issues data to R1 through the unicast session along the default routing path. OFSs on the path may report the arrival of new packets to the controller and request for admission of access.After that, other hosts may request the service.S maintains the receiver list dynamically and updates synchronously with the controller. As decision-maker, SDN controller constructs and adjusts the multicasts tree along with the joining and departure of receivers. It issues rules to the corresponding OFSs on behalf of data dissemination for each receiver. Data manipulation mechanism will be presented in Section 5.When receiver leaving, the corresponding session will be closed. The information of the receiver is removed from the receiver list. Tree adjustment algorithm initiates if necessary.


## 5. Joint Unicast and Multicast Routing Algorithm for NFV-Enabled QoS Guaranteed Network

### 5.1. Data Manipulation to Realize Packet Distribution on Multicast Tree

For a better understanding of the proposed mechanism, we first introduce how to steer data delivered along constructed multicast tree ignoring VNFs. To illustrate the basic operation, we present a brief example in Figure3. There, triangle icons denote the server; circular icons and grey squares with sequence numbers inside indicate OFSs and receivers, respectively.Figure 3
Basic operations of multicast data distribution.It is assumed thatR1 is the first host that sends a request to the source. The server sends data packets to R1 directly in unicast session. Afterwards, R2 requests the same source. Now, a branch is necessary to distribute data to R2 with minimum cost. Therefore, an OFS is selected as the operation node for data bifurcation. Following the tree construction mechanism presented in Section 5.2, the fork node selected is OFS4 in common situation. OFS4 replicates the flow and replaces the destination of the replicated flow with the IP/Port pair of R2, which is from <IPR1, PORTR1> to <IPR2, PORTR2>. Similarly, OFS2 is selected as the operation node for R3, which transfers duplicated packets from <IPR1, PORTR1> to <IPR3, PORTR3>.In current networks, there are numerous legacy routers, and some OFSs may be capacity limited to be an operation node. In fact, the operation node is not necessary to be a physically branching node. Wrapping route is allowed to find a usable operation node. For example in Figure3, the desired operation node for R3 is OFS2. However, if OFS2 is unable to serve as the operation node, other OFSs, such as OFS1, OFS3, OFS7, or even OFS4, could undertake the task of data manipulation for R3.In this section, we described how data are distributed along a multicast tree but in unicast sessions, without involving NFV capability, QoS, and MEC capacity constraints. This is the implementable method and can be extensively applied to NFV-enabled SDN MEC networks.


### 5.2. NFV-Enabled QoS Guaranteed Multicast Tree Construction Algorithms

In this section, we elaborate how to solve VNF placement problems during multicast tree construction. Based on the introduction of NFV and notions in Section3.2, we consider the cost matrix defined in equation (7) and aim to calculate the computational cost of each possible route from source to a last VNF in a specific sequence of service chain, that is, with a set VNFL = (VNF1, VNF2, …, VNFn) of VNFs and a service chain SCk = fk,1,fk,2,…,fk,Lk, to find all the paths from source to the node of the last service function fk,Lk passing the service chain of SCk and to calculate the cost using equation (6).After sorting out the paths from the source to the last function nodes, we then construct trees from each last function node to the set of destinations, which is the Steiner tree problem with NP-hard. How to build a Steiner tree will not be extended in this paper; readers can refer to [30, 31] for more information. We calculate the minimal spanning trees meeting QoS constraints. Subsequently, a set of multicast trees are generated from each function node of fk,Lk to the set of destinations.Finally, we get the set of paths from the source to the node of the last service functionfk,Lk and a set of multicast trees from each last function node to the destination set. Based on the information, we can find the optimal multicast tree from the source node to the destination set with minimal cost and meeting the QoS requirements while passing required VNFs. Notice that, the cost of links from the last function node to the set of destinations is ignored, because we hold the opinion that the cost of deploying VNFs is much larger than that of utilizing a link in the case of QoS guaranteed. Algorithm 1 presents the pseudocode of the NFV-enabled QoS guaranteed multicast tree construction algorithm.Algorithm 1:NFV-enabled QoS guaranteed multicast tree construction
Input:G=V,E, Mk, Dk, Bk, cf,m, SCk, CLOutput: A QoS guaranteed multicast tree with minimal cost(1)
Calculate the costCkj of path j from source Si to VNF node v(v ∈ CL) that implementing fk,Lk;(2)
Get a set of path costsCk = (Ck1, Ck2, …, Ckn);(3)
forv ∈ CL, do(4)
Construct a Steiner tree from eachv to destination set;(5)
With QoS requirement constraints, generate a set of multicast treesT;(6)
end(7)
Select the multicast treeTopt with the minimum cost of Ck of v, which meets the QoS requirements(8)
ReturnTopt


## 5.1. Data Manipulation to Realize Packet Distribution on Multicast Tree

For a better understanding of the proposed mechanism, we first introduce how to steer data delivered along constructed multicast tree ignoring VNFs. To illustrate the basic operation, we present a brief example in Figure3. There, triangle icons denote the server; circular icons and grey squares with sequence numbers inside indicate OFSs and receivers, respectively.Figure 3
Basic operations of multicast data distribution.It is assumed thatR1 is the first host that sends a request to the source. The server sends data packets to R1 directly in unicast session. Afterwards, R2 requests the same source. Now, a branch is necessary to distribute data to R2 with minimum cost. Therefore, an OFS is selected as the operation node for data bifurcation. Following the tree construction mechanism presented in Section 5.2, the fork node selected is OFS4 in common situation. OFS4 replicates the flow and replaces the destination of the replicated flow with the IP/Port pair of R2, which is from <IPR1, PORTR1> to <IPR2, PORTR2>. Similarly, OFS2 is selected as the operation node for R3, which transfers duplicated packets from <IPR1, PORTR1> to <IPR3, PORTR3>.In current networks, there are numerous legacy routers, and some OFSs may be capacity limited to be an operation node. In fact, the operation node is not necessary to be a physically branching node. Wrapping route is allowed to find a usable operation node. For example in Figure3, the desired operation node for R3 is OFS2. However, if OFS2 is unable to serve as the operation node, other OFSs, such as OFS1, OFS3, OFS7, or even OFS4, could undertake the task of data manipulation for R3.In this section, we described how data are distributed along a multicast tree but in unicast sessions, without involving NFV capability, QoS, and MEC capacity constraints. This is the implementable method and can be extensively applied to NFV-enabled SDN MEC networks.


## 5.2. NFV-Enabled QoS Guaranteed Multicast Tree Construction Algorithms

In this section, we elaborate how to solve VNF placement problems during multicast tree construction. Based on the introduction of NFV and notions in Section3.2, we consider the cost matrix defined in equation (7) and aim to calculate the computational cost of each possible route from source to a last VNF in a specific sequence of service chain, that is, with a set VNFL = (VNF1, VNF2, …, VNFn) of VNFs and a service chain SCk = fk,1,fk,2,…,fk,Lk, to find all the paths from source to the node of the last service function fk,Lk passing the service chain of SCk and to calculate the cost using equation (6).After sorting out the paths from the source to the last function nodes, we then construct trees from each last function node to the set of destinations, which is the Steiner tree problem with NP-hard. How to build a Steiner tree will not be extended in this paper; readers can refer to [30, 31] for more information. We calculate the minimal spanning trees meeting QoS constraints. Subsequently, a set of multicast trees are generated from each function node of fk,Lk to the set of destinations.Finally, we get the set of paths from the source to the node of the last service functionfk,Lk and a set of multicast trees from each last function node to the destination set. Based on the information, we can find the optimal multicast tree from the source node to the destination set with minimal cost and meeting the QoS requirements while passing required VNFs. Notice that, the cost of links from the last function node to the set of destinations is ignored, because we hold the opinion that the cost of deploying VNFs is much larger than that of utilizing a link in the case of QoS guaranteed. Algorithm 1 presents the pseudocode of the NFV-enabled QoS guaranteed multicast tree construction algorithm.Algorithm 1:NFV-enabled QoS guaranteed multicast tree construction
Input:G=V,E, Mk, Dk, Bk, cf,m, SCk, CLOutput: A QoS guaranteed multicast tree with minimal cost(1)
Calculate the costCkj of path j from source Si to VNF node v(v ∈ CL) that implementing fk,Lk;(2)
Get a set of path costsCk = (Ck1, Ck2, …, Ckn);(3)
forv ∈ CL, do(4)
Construct a Steiner tree from eachv to destination set;(5)
With QoS requirement constraints, generate a set of multicast treesT;(6)
end(7)
Select the multicast treeTopt with the minimum cost of Ck of v, which meets the QoS requirements(8)
ReturnTopt


## 6. Methodology, Implementation, and Evaluation

It is a great challenge to design an SDN/NFV/MEC-enabled multicast routing mechanism. Likewise, it is hard to implement the proposal in a single simulation environment. Therefore, to experiment our proposal, we first set up an SDN environment in Mininet [32], and we use NS2 simulator to build the same network as the comparison. In this section, we evaluate the performance of the proposed mechanism and investigate the impact of the main parameters.We denote our proposal by SDUM. Many of the existing multicast approaches explicitly or implicitly apply or improve IP multicast to suit specific network scenarios. However, the performance of basic data distribution efficiency is commonly no better than native IP multicast. In this paper, we chose SDM [25] and PIM-SM [30] as the comparison. SDM is a pure SDN-based multicast approach, while PIM-SM is a classical IP multicast routing protocol suitable for multicast in sparse networks. Both of them are in line with the cases of our proposal. Multicast tree rooted from the source to destinations was constructed according to Steiner tree algorithm. Thus, the tree topology was the same for all three methods.


### 6.1. Simulation Setup

We implemented SDUM on top of the Ryu controller [33] based on OpenFlow protocol version 1.3. The network topology was constructed using Mininet version 2.2.2. Due to functional limitations, it is difficult to implement the PIM-SM protocol in Mininet. Therefore, we deployed the same network with the exact same link status using NS2, which was able to simulate IP multicast protocols. The testbed was allocated in a desktop PC with Ubuntu Desktop 16.04. Each simulation time was set to 60 seconds for each scenario.We built the networks consisting of 50 to 250 OFSs. Network topology was generated using the tool GT-ITM [34]. Source node was attached to an OFS and generated 1 Mbps constant UDP streaming.


### 6.2. Evaluation and Analysis

Since the examined approaches were all based on the Steiner tree algorithm, they conducted actually the same multicast tree. Therefore, it is meaningless to compare tree construction efficiency, data delivery latency, or bandwidth consumption with each other. Instead, it is significant to evaluate the number of control messages, signalling overhead ratios, and utilization of flow table entries or routing table entries installed to OFSs or routers, respectively, on the multicast tree to enable data transmission. We also evaluated the impact of the number of OFSs in a hybrid network. Finally, we present a qualitative comparison of typical multicast approaches.


#### 6.2.1. Impact of Network Scale

In the experiments, we increased the network scale from 50 nodes to 250 nodes with 30 randomly selected destinations. The results (Figures4(a)–4(c)) show that the total cost on three aspects significantly increased with the growing of network size. It is mainly because that multicast tree grows up along with more links and exchanging control messages when the network is scaling up.Figure 4
The impact of network size on control overhead. (a) The number of control messages. (b) Signalling overhead ratio. (c) The number of flow/routing entries.
(a)(b)(c)The number of control messages reveals the load of protocols or approaches imposed on the network. For PIM-SM, control messages are exchanged among routers to build and maintain multicast tree, such as IGMP and RP election messages. For SDM and SDUM, control messages are mainly OpenFlow messages exchanged among OFSs and controller, includingPacketOut messages for rule installation, PacketIn messages for rule query, and so on. Except OpenFlow messages, SDM generates control messages for domain management, virtual peer operation, host joining and leaving, and so on. From the results in Figure 4(a), we can conclude that SDUM injects much less control messages than SDM and PIM-SM.Signalling overhead ratio denotes the bitrate proportion of multicast-related control messages to the total data rate per link. We emulated a constant 1 Mbps UDP traffic as the streaming. Depending on the basic format of control messages, PIM-SM control messages are around 70 bytes while control messages in SDN are around 200 bytes. The number of the control messages may not reveal the real signalling overhead due to different packet size. We can see that PIM-SM is the overwhelming approach among them, as depicted in Figure4(b).It is also necessary to measure the utilization of flow (routing) table entries, because it is the main reason that limits the globe deployment of IP multicast. Similarly, the volume of flow table is also restricted by the price of memory (TCAM). As a contrast, PIM-SM requires one table entry for each group on every router that may process multicast traffic. For SDM and SDUM, it is necessary to install rules to flow table to realize packet duplication, address translation, and data forwarding. The results in Figure4(c) show that SDM performs worse since the occupation of flow table increase sharply. SDUM incurs a horizontal line, which is because the number of rules installed to OFSs depends on the number of destinations (30), while SDUM and PIM-SM are sensitive to the size of the network and the multicast tree.


#### 6.2.2. Impact of Group Size

We further measured the impact of group size. We set the network size to 200 nodes, with the number of destinations switched from 10 to 90. A constant 1 Mbps UDP traffic was injected as the streaming to the network by source node. Although the number of control messages increases for all three methods, the performance of SDM is close to IP multicast while SDUM consumes much less control messages (Figure5(a)). For signalling overhead (Figure 5(b)), the number of edges of the multicast tree is also rising with the growing of destinations. Therefore, the signalling overhead per link becomes gently with the variation of destinations. In these experiments, the performance of PIM-SM is overwhelmed, because the packet size in PIM-SM is much smaller than OpenFlow messages. For utilization of flow (routing) table entries (Figure 5(c)), SDUM performs outstandingly than both others. The number of flow table entries grows linearly correlated to the number of receivers. For SDM, the number of rules installed greatly relies on network topology and destination location. It is necessary to install rules not only on access OFS of each receiver but also on specific core OFSs. For PIM-SM, only the legacy routers on the multicast tree are required to insert an entry to the routing table, which is necessary for parsing multicast addresses.Figure 5
The impact of group size on control overhead. (a) The number of control messages. (b) Signalling overhead ratio. (c) The number of flow/routing entries.
(a)(b)(c)From the above experiments, we can conclude that SDM shows a worse scalability performance with the growing of network size and the increasing number of destinations. The performance of PIM-SM is more correlated to the size of multicast tree, while SDUM has strong correlation with the number of destinations. Therefore, PIM-SM is suitable for sparse network with limited groups, while SDUM is better to be deployed for large networks with a small quantity of receivers in each group.


#### 6.2.3. Impact of the Number of OFSs in Hybrid Network

As we mentioned, our design is suitable for hybrid networks. The number of OFSs in the network affects the performance of multicast tree construction. In the simulation, we assumed that OFSs distributed in the network randomly. Legacy routers connected with OFSs and formed the network together. Therefore, instead of counting the edges of the virtualized network, we should count the physical edges of the multicast tree including legacy router-connected links. We present the experiments with different number of OFSs from 40 to 200 in networks with a total of 200, 300, and 400 nodes. We counted the number of edges that formed the multicast tree. For the simplicity of the simulation, we assumed that a single OFS at most attaches to one receiver.According to the results demonstrated in Figure6, it is obvious that the number of edges of a multicast tree has a strong correlation with the number of OFSs in hybrid network. With the raising of network size, the number of edges also increases. For a fixed network size, with the increasing of the number of OFSs, the number of edges decreases. That is because, in our mechanism, one receiver corresponds to a specific operation node (OFS). We can conclude that our mechanism can generate minimal multicast tree if most of the network devices are OFSs.Figure 6
The impact of varying number of OpenFlow switches (OFSs) in hybrid network.
(a)(b)(c)


#### 6.2.4. Qualitative Comparison

It is also meaningful to make a qualitative comparison about the classic multicasting approaches. As shown in Table2, the main concern is the incremental implementation, which is essential whether it can be popularized or not. To implement multicasting service, PIM-SM requires all routers support multicasting function, while SDM requires that all devices are OpenFlow enabled in SDM domain. As a comparison, SDUM requires that only the operation nodes are OpenFlow enabled without any other function demands. For scalability consideration, we need concern about how many devices are required to support specific functions. To implement PIM-SM, all routers need to install the multicast protocol. For SDM, pure SDN domain is required and thus inadequate to be applied to hybrid networks. SDUM is suitable for hybrid networks with distributed OFSs in the network and implementable in large complex networks. For ISP control and access control, it is hard to manage group members using IP multicasting protocols due to the distribution management feature of group joining and leaving. However, attribute to the centralized management manner of SDUM, it can easily achieve source, receiver, and on-the-fly data traffic management and control.Table 2
Qualitative comparison.
PIM-SMSDMSDUMIncremental implementationAll routers in the network need to install multicast protocolNo legacy router allowed in SDM domainSupport hybrid networks; only operation nodes are OpenFlow demandScalabilityLow (distributed routers of multiple ISPs result in difficulty to use same multicast mechanism)Low (in the current evolution network, it is hard to build a pure large-scale SDN)High (virtualized network on top of hybrid network is possible)ISP controlLow (distributed legacy routers are hard to be managed)High (centralized control of OFSs in SDM domain)High (centralized control of fork OFSs distributed in the network)Access controlSome specific protocols are necessary, for example, IGMP-AC and SIGMPNo concernSource, receiver, and on-the-fly traffic management and control


## 6.1. Simulation Setup

We implemented SDUM on top of the Ryu controller [33] based on OpenFlow protocol version 1.3. The network topology was constructed using Mininet version 2.2.2. Due to functional limitations, it is difficult to implement the PIM-SM protocol in Mininet. Therefore, we deployed the same network with the exact same link status using NS2, which was able to simulate IP multicast protocols. The testbed was allocated in a desktop PC with Ubuntu Desktop 16.04. Each simulation time was set to 60 seconds for each scenario.We built the networks consisting of 50 to 250 OFSs. Network topology was generated using the tool GT-ITM [34]. Source node was attached to an OFS and generated 1 Mbps constant UDP streaming.


## 6.2. Evaluation and Analysis

Since the examined approaches were all based on the Steiner tree algorithm, they conducted actually the same multicast tree. Therefore, it is meaningless to compare tree construction efficiency, data delivery latency, or bandwidth consumption with each other. Instead, it is significant to evaluate the number of control messages, signalling overhead ratios, and utilization of flow table entries or routing table entries installed to OFSs or routers, respectively, on the multicast tree to enable data transmission. We also evaluated the impact of the number of OFSs in a hybrid network. Finally, we present a qualitative comparison of typical multicast approaches.


### 6.2.1. Impact of Network Scale

In the experiments, we increased the network scale from 50 nodes to 250 nodes with 30 randomly selected destinations. The results (Figures4(a)–4(c)) show that the total cost on three aspects significantly increased with the growing of network size. It is mainly because that multicast tree grows up along with more links and exchanging control messages when the network is scaling up.Figure 4
The impact of network size on control overhead. (a) The number of control messages. (b) Signalling overhead ratio. (c) The number of flow/routing entries.
(a)(b)(c)The number of control messages reveals the load of protocols or approaches imposed on the network. For PIM-SM, control messages are exchanged among routers to build and maintain multicast tree, such as IGMP and RP election messages. For SDM and SDUM, control messages are mainly OpenFlow messages exchanged among OFSs and controller, includingPacketOut messages for rule installation, PacketIn messages for rule query, and so on. Except OpenFlow messages, SDM generates control messages for domain management, virtual peer operation, host joining and leaving, and so on. From the results in Figure 4(a), we can conclude that SDUM injects much less control messages than SDM and PIM-SM.Signalling overhead ratio denotes the bitrate proportion of multicast-related control messages to the total data rate per link. We emulated a constant 1 Mbps UDP traffic as the streaming. Depending on the basic format of control messages, PIM-SM control messages are around 70 bytes while control messages in SDN are around 200 bytes. The number of the control messages may not reveal the real signalling overhead due to different packet size. We can see that PIM-SM is the overwhelming approach among them, as depicted in Figure4(b).It is also necessary to measure the utilization of flow (routing) table entries, because it is the main reason that limits the globe deployment of IP multicast. Similarly, the volume of flow table is also restricted by the price of memory (TCAM). As a contrast, PIM-SM requires one table entry for each group on every router that may process multicast traffic. For SDM and SDUM, it is necessary to install rules to flow table to realize packet duplication, address translation, and data forwarding. The results in Figure4(c) show that SDM performs worse since the occupation of flow table increase sharply. SDUM incurs a horizontal line, which is because the number of rules installed to OFSs depends on the number of destinations (30), while SDUM and PIM-SM are sensitive to the size of the network and the multicast tree.


### 6.2.2. Impact of Group Size

We further measured the impact of group size. We set the network size to 200 nodes, with the number of destinations switched from 10 to 90. A constant 1 Mbps UDP traffic was injected as the streaming to the network by source node. Although the number of control messages increases for all three methods, the performance of SDM is close to IP multicast while SDUM consumes much less control messages (Figure5(a)). For signalling overhead (Figure 5(b)), the number of edges of the multicast tree is also rising with the growing of destinations. Therefore, the signalling overhead per link becomes gently with the variation of destinations. In these experiments, the performance of PIM-SM is overwhelmed, because the packet size in PIM-SM is much smaller than OpenFlow messages. For utilization of flow (routing) table entries (Figure 5(c)), SDUM performs outstandingly than both others. The number of flow table entries grows linearly correlated to the number of receivers. For SDM, the number of rules installed greatly relies on network topology and destination location. It is necessary to install rules not only on access OFS of each receiver but also on specific core OFSs. For PIM-SM, only the legacy routers on the multicast tree are required to insert an entry to the routing table, which is necessary for parsing multicast addresses.Figure 5
The impact of group size on control overhead. (a) The number of control messages. (b) Signalling overhead ratio. (c) The number of flow/routing entries.
(a)(b)(c)From the above experiments, we can conclude that SDM shows a worse scalability performance with the growing of network size and the increasing number of destinations. The performance of PIM-SM is more correlated to the size of multicast tree, while SDUM has strong correlation with the number of destinations. Therefore, PIM-SM is suitable for sparse network with limited groups, while SDUM is better to be deployed for large networks with a small quantity of receivers in each group.


### 6.2.3. Impact of the Number of OFSs in Hybrid Network

As we mentioned, our design is suitable for hybrid networks. The number of OFSs in the network affects the performance of multicast tree construction. In the simulation, we assumed that OFSs distributed in the network randomly. Legacy routers connected with OFSs and formed the network together. Therefore, instead of counting the edges of the virtualized network, we should count the physical edges of the multicast tree including legacy router-connected links. We present the experiments with different number of OFSs from 40 to 200 in networks with a total of 200, 300, and 400 nodes. We counted the number of edges that formed the multicast tree. For the simplicity of the simulation, we assumed that a single OFS at most attaches to one receiver.According to the results demonstrated in Figure6, it is obvious that the number of edges of a multicast tree has a strong correlation with the number of OFSs in hybrid network. With the raising of network size, the number of edges also increases. For a fixed network size, with the increasing of the number of OFSs, the number of edges decreases. That is because, in our mechanism, one receiver corresponds to a specific operation node (OFS). We can conclude that our mechanism can generate minimal multicast tree if most of the network devices are OFSs.Figure 6
The impact of varying number of OpenFlow switches (OFSs) in hybrid network.
(a)(b)(c)


### 6.2.4. Qualitative Comparison

It is also meaningful to make a qualitative comparison about the classic multicasting approaches. As shown in Table2, the main concern is the incremental implementation, which is essential whether it can be popularized or not. To implement multicasting service, PIM-SM requires all routers support multicasting function, while SDM requires that all devices are OpenFlow enabled in SDM domain. As a comparison, SDUM requires that only the operation nodes are OpenFlow enabled without any other function demands. For scalability consideration, we need concern about how many devices are required to support specific functions. To implement PIM-SM, all routers need to install the multicast protocol. For SDM, pure SDN domain is required and thus inadequate to be applied to hybrid networks. SDUM is suitable for hybrid networks with distributed OFSs in the network and implementable in large complex networks. For ISP control and access control, it is hard to manage group members using IP multicasting protocols due to the distribution management feature of group joining and leaving. However, attribute to the centralized management manner of SDUM, it can easily achieve source, receiver, and on-the-fly data traffic management and control.Table 2
Qualitative comparison.
PIM-SMSDMSDUMIncremental implementationAll routers in the network need to install multicast protocolNo legacy router allowed in SDM domainSupport hybrid networks; only operation nodes are OpenFlow demandScalabilityLow (distributed routers of multiple ISPs result in difficulty to use same multicast mechanism)Low (in the current evolution network, it is hard to build a pure large-scale SDN)High (virtualized network on top of hybrid network is possible)ISP controlLow (distributed legacy routers are hard to be managed)High (centralized control of OFSs in SDM domain)High (centralized control of fork OFSs distributed in the network)Access controlSome specific protocols are necessary, for example, IGMP-AC and SIGMPNo concernSource, receiver, and on-the-fly traffic management and control


## 6.2.1. Impact of Network Scale

In the experiments, we increased the network scale from 50 nodes to 250 nodes with 30 randomly selected destinations. The results (Figures4(a)–4(c)) show that the total cost on three aspects significantly increased with the growing of network size. It is mainly because that multicast tree grows up along with more links and exchanging control messages when the network is scaling up.Figure 4
The impact of network size on control overhead. (a) The number of control messages. (b) Signalling overhead ratio. (c) The number of flow/routing entries.
(a)(b)(c)The number of control messages reveals the load of protocols or approaches imposed on the network. For PIM-SM, control messages are exchanged among routers to build and maintain multicast tree, such as IGMP and RP election messages. For SDM and SDUM, control messages are mainly OpenFlow messages exchanged among OFSs and controller, includingPacketOut messages for rule installation, PacketIn messages for rule query, and so on. Except OpenFlow messages, SDM generates control messages for domain management, virtual peer operation, host joining and leaving, and so on. From the results in Figure 4(a), we can conclude that SDUM injects much less control messages than SDM and PIM-SM.Signalling overhead ratio denotes the bitrate proportion of multicast-related control messages to the total data rate per link. We emulated a constant 1 Mbps UDP traffic as the streaming. Depending on the basic format of control messages, PIM-SM control messages are around 70 bytes while control messages in SDN are around 200 bytes. The number of the control messages may not reveal the real signalling overhead due to different packet size. We can see that PIM-SM is the overwhelming approach among them, as depicted in Figure4(b).It is also necessary to measure the utilization of flow (routing) table entries, because it is the main reason that limits the globe deployment of IP multicast. Similarly, the volume of flow table is also restricted by the price of memory (TCAM). As a contrast, PIM-SM requires one table entry for each group on every router that may process multicast traffic. For SDM and SDUM, it is necessary to install rules to flow table to realize packet duplication, address translation, and data forwarding. The results in Figure4(c) show that SDM performs worse since the occupation of flow table increase sharply. SDUM incurs a horizontal line, which is because the number of rules installed to OFSs depends on the number of destinations (30), while SDUM and PIM-SM are sensitive to the size of the network and the multicast tree.


## 6.2.2. Impact of Group Size

We further measured the impact of group size. We set the network size to 200 nodes, with the number of destinations switched from 10 to 90. A constant 1 Mbps UDP traffic was injected as the streaming to the network by source node. Although the number of control messages increases for all three methods, the performance of SDM is close to IP multicast while SDUM consumes much less control messages (Figure5(a)). For signalling overhead (Figure 5(b)), the number of edges of the multicast tree is also rising with the growing of destinations. Therefore, the signalling overhead per link becomes gently with the variation of destinations. In these experiments, the performance of PIM-SM is overwhelmed, because the packet size in PIM-SM is much smaller than OpenFlow messages. For utilization of flow (routing) table entries (Figure 5(c)), SDUM performs outstandingly than both others. The number of flow table entries grows linearly correlated to the number of receivers. For SDM, the number of rules installed greatly relies on network topology and destination location. It is necessary to install rules not only on access OFS of each receiver but also on specific core OFSs. For PIM-SM, only the legacy routers on the multicast tree are required to insert an entry to the routing table, which is necessary for parsing multicast addresses.Figure 5
The impact of group size on control overhead. (a) The number of control messages. (b) Signalling overhead ratio. (c) The number of flow/routing entries.
(a)(b)(c)From the above experiments, we can conclude that SDM shows a worse scalability performance with the growing of network size and the increasing number of destinations. The performance of PIM-SM is more correlated to the size of multicast tree, while SDUM has strong correlation with the number of destinations. Therefore, PIM-SM is suitable for sparse network with limited groups, while SDUM is better to be deployed for large networks with a small quantity of receivers in each group.


## 6.2.3. Impact of the Number of OFSs in Hybrid Network

As we mentioned, our design is suitable for hybrid networks. The number of OFSs in the network affects the performance of multicast tree construction. In the simulation, we assumed that OFSs distributed in the network randomly. Legacy routers connected with OFSs and formed the network together. Therefore, instead of counting the edges of the virtualized network, we should count the physical edges of the multicast tree including legacy router-connected links. We present the experiments with different number of OFSs from 40 to 200 in networks with a total of 200, 300, and 400 nodes. We counted the number of edges that formed the multicast tree. For the simplicity of the simulation, we assumed that a single OFS at most attaches to one receiver.According to the results demonstrated in Figure6, it is obvious that the number of edges of a multicast tree has a strong correlation with the number of OFSs in hybrid network. With the raising of network size, the number of edges also increases. For a fixed network size, with the increasing of the number of OFSs, the number of edges decreases. That is because, in our mechanism, one receiver corresponds to a specific operation node (OFS). We can conclude that our mechanism can generate minimal multicast tree if most of the network devices are OFSs.Figure 6
The impact of varying number of OpenFlow switches (OFSs) in hybrid network.
(a)(b)(c)


## 6.2.4. Qualitative Comparison

It is also meaningful to make a qualitative comparison about the classic multicasting approaches. As shown in Table2, the main concern is the incremental implementation, which is essential whether it can be popularized or not. To implement multicasting service, PIM-SM requires all routers support multicasting function, while SDM requires that all devices are OpenFlow enabled in SDM domain. As a comparison, SDUM requires that only the operation nodes are OpenFlow enabled without any other function demands. For scalability consideration, we need concern about how many devices are required to support specific functions. To implement PIM-SM, all routers need to install the multicast protocol. For SDM, pure SDN domain is required and thus inadequate to be applied to hybrid networks. SDUM is suitable for hybrid networks with distributed OFSs in the network and implementable in large complex networks. For ISP control and access control, it is hard to manage group members using IP multicasting protocols due to the distribution management feature of group joining and leaving. However, attribute to the centralized management manner of SDUM, it can easily achieve source, receiver, and on-the-fly data traffic management and control.Table 2
Qualitative comparison.
PIM-SMSDMSDUMIncremental implementationAll routers in the network need to install multicast protocolNo legacy router allowed in SDM domainSupport hybrid networks; only operation nodes are OpenFlow demandScalabilityLow (distributed routers of multiple ISPs result in difficulty to use same multicast mechanism)Low (in the current evolution network, it is hard to build a pure large-scale SDN)High (virtualized network on top of hybrid network is possible)ISP controlLow (distributed legacy routers are hard to be managed)High (centralized control of OFSs in SDM domain)High (centralized control of fork OFSs distributed in the network)Access controlSome specific protocols are necessary, for example, IGMP-AC and SIGMPNo concernSource, receiver, and on-the-fly traffic management and control


## 7. Conclusion

In this paper, we presented an implementable multicast routing mechanism for NFV-enabled software-defined MEC networks. We first investigated the system mode with problem statements and analysed the capacity constraints of cloudlets and QoS constraints of service. Then, we proposed an implementable unicast and multicast jointed routing mechanism, which enabled us to deliver data in unicast sessions along a minimal multicast tree. Thus, it can provide a generic multicast service in network layer for SDN-based MEC networks. The evaluation results indicate an evident improvement in terms of control message and signalling overhead ratio, utilization of flow/routing table, number of OFSs in hybrid network, and qualitative comparison. For future work, we will focus on mechanism optimization and experiments in various scenarios.



---

*Source: 5590963-2021-04-15.xml*