# IoT-B&B: Edge-Based NFV for IoT Devices with CPE Crowdsourcing

Authors: He Zhu; Changcheng Huang
Journal: Wireless Communications and Mobile Computing
 (2018)

---

## Abstract

For embracing the ubiquitous Internet-of-Things (IoT) devices, edge computing and Network Function Virtualization (NFV) have been enabled in branch offices and homes in the form of virtual Customer-Premises Equipment (vCPE). A Service Provider (SP) deploys vCPE instances as Virtual Network Functions (VNFs) on top of generic physical Customer-Premises Equipment (pCPE) to ease administration. Upon a usage surge of IoT devices at a certain part of the network, vCPU, memory, and other resource limitations of a single pCPE node make it difficult to add new services handling the high demand. In this paper, we present IoT-B&B, a novel architecture featuring resource sharing of pCPE nodes. When a pCPE node has sharable resources available, the SP will utilize its free resources as a “bed-and-breakfast” place to deploy vCPE instances in need. A placement algorithm is also presented to assign vCPE instances to a cost-efficient pCPE node. By keeping vCPE instances at the network edge, their costs of hosting are reduced. Meanwhile, the transmission latencies are maintained at acceptable levels for processing real-time data burst from IoT devices. The traffic load to the remote, centralized cloud can be substantially reduced.


---

## Body

## 1. Introduction

Customer-premises equipment (CPE) devices, such as routers, switches, residential gateways, and set-top boxes, have been deployed at the subscriber’s premises to originate, route, and terminate communications between the customer premises and the central office [1]. In the wake of cloud computing and Network Function Virtualization (NFV) [2, 3], Service Providers (SPs) leverage virtual Customer-Premises Equipment (vCPE) as Virtual Network Function (VNF) instances on top of generic physical Customer-Premises Equipment (pCPE), in search of rebuilding a dynamic revenue stream [4]. There can be enough resources for pCPE to deploy VNFs locally [5], while pCPE can also coordinate with the cloud if VNF scale-out is needed to accommodate heavier usage.Taking advantage of centralized cloud services in the core networks has benefits [6] because of scalable and flexible computing capabilities. However, large-number deployments of Internet-of-Things (IoT) devices bring challenges to VNFs running in a centralized cloud, as the network traffic load would be drastically increased by transmitting data between the core and the edge of the network. Such traffic overhead can become unacceptable with excessive data transmission, causing high processing delay or even service outage due to the congestion of the network. Meanwhile, high usage of the cloud networks would jack up the price per usage, resulting in a higher-than-expected operating expense (OPEX).Recent research has been aware of the explosive growth of devices in the edge of the networks. The concepts of fog computing [7] and edge computing [8] were proposed to move the initial handling of raw data to the edge for IoT devices. Although the fog can mitigate the load of the core network, the power of the Customer Edge (CE), namely, the computational capabilities of CPE, is buried. While a single pCPE node has limited resources and typically serves a designated location, the aggregated computing capabilities of pCPE nodes across the edge of a network can be powerful: pCPE nodes have time-varying resource usage that does not always reach full workloads. For instance, the home gateways typically have significantly lower usage in business hours as their users leave for work, while office gateways become idle after hours. If the spare resources of pCPE can be shared within the network edge, VNFs will be able to roam around the edge. Both SP and users will benefit from the considerable capabilities of the sharable resources. Meanwhile, the VNFs deployed on the pCPE nodes keep most traffic within the edge and reduce the traffic to the core network.It certainly sounds interesting to utilize the time-varying computational resources. However, CPE resource sharing faces challenges:(i)
It is unclear how much SP can benefit from spare resources of pCPE nodes compared to traditional virtualization without resource sharing.(ii)
Service availability becomes a concern. A pCPE node’s availability can be jeopardized if it no longer has enough resources to host VNFs. It can also be down due to power outages or user pulling the plugs. The availability of offloaded VNFs must be ensured by enforcing proper redundancy.(iii)
The users need to be motivated to consent to contributing their pCPE nodes for resource sharing. They would not do so without incentives or discounts. Incentives returned to users are required in order to benefit both the SP and its end users.In this paper, we propose an architecture to allow sharing resources of pCPE within the network edge, namely, IoT-B&B. We discuss the scenario that SP deploys VNFs, which are vCPE instances, to both the cloud and the available pCPE nodes participating in the resource sharing program. As Figure1 shows, when a sharable pCPE node is not actively used by its owner, it will be treated as a “bed-and-breakfast” place for vCPE instances to “stay.” SP will have the permission to utilize free resources through the resource manager to deploy VNFs of other users from the same edge network. The following contributions are made for enabling crowdsourcing at the network edge by utilizing resources of pCPE nodes:(i)
We propose an architecture extended from ETSI NFV architecture and interfaces [9] to support resource sharing of pCPE nodes. The pCPE nodes at the network edge are treated as compute hosts which can have VNF instances deployed. They are grouped together and abstracted into the NFV Infrastructure (NFVI) layer. A resource manager is embedded in the NFVI and can leverage placement algorithms to make placement decisions.(ii)
A model is presented to evaluate the cost of assigning a VNF instance to a pCPE node and to the remote cloud. Multiple factors are considered to determine the cost, including remaining resources, network transmission delay, and availability requirements.(iii)
A placement algorithm called “IoT-B&B Algorithm” is also presented to assign vCPE instances to pCPE nodes with the goal of finding a cost-efficient pCPE node for each VNF.(iv)
We implement a system with the IoT-B&B architecture with steps to set up the NFVI and the system’s life cycle. Numerical results are shown to demonstrate the placement algorithm’s effectiveness.Figure 1
The system architecture is extended from ETSI NFV architecture and interfaces [9]. It has a resource manager integrated with NFVI to schedule VNF placement, leveraging the VNF-B&B algorithm. The architecture enables pCPE resources to be part of the NFVI along with cloud host servers, where each pCPE node can have VNFs deployed for multiple users in the edge network. For instance, when pCPE-B needs more VNFs to handle its overloaded use, they can be deployed on both pCPE-A (VNF-B3) and the cloud (VNF-B4).We divide the contents into the following sections. Section2 formulates the problem. Section 3 proposes the IoT-B&B Algorithm based on the problem formulation. Then, Section 4 is presented, covering the actual implementation of the system, followed by the numerical results in Section 5. The related work is illustrated in Section 6. Section 7 concludes the paper and lists future work items.


## 2. Problem Formulation

In this section, we formulate the problem by modeling the resource properties and constraints of the network edge. The resource types we discuss are limited to CPU, memory, and network bandwidth. We believe these three types of the resources are most representative for cost estimation and optimization. Adding consideration of more resource types will not necessarily change the optimization model. Then, the properties of the VNF instances are defined and annotated. All notations defined and used are also summarized in the Notations Used in Problem Formulation. Note that the terms “VNF”; “VNF instance”; and “vCPE instance” in this paper are interchangeable.


### 2.1. Connected pCPE at Network Edge

We discuss one particular network edge, which includes all pCPE nodes under it. A network edge is defined as the networks connecting all pCPE nodes under it. We model a network edge to have a topology such that each pCPE node within it can communicate with another. An example with two network edges can be found in Figure2. The nodes of pCPE 1A, 1B, and 1C group as one network edge connected to each other via Edge Network 1, while the other one consists of the nodes 2A, 2B, and 2C, connected by Edge Network 2.Figure 2
Topologies at network edges. All pCPE nodes can communicate with each other if they are within the same network edge.Based on the definition above, the pCPE nodes and their links at the network edge can be modeled as a directed graphG=(V,L). Set V represents all pCPE nodes at the network edge, while L is the set of all connected links from one vCPE node to another. A pCPE node in V is denoted by v, and there is v∈V. Define the total number of pCPE nodes to be nV. Let vi be a specific pCPE node in V, such that(1)vi∈V,∀i∈1⋯nV. Since all pCPE nodes are connected to each other, G is strongly connected. For any data transmitted from one node vi to another node vj in V, there exists a link lij, such that(2)lij∈L,∀i,j∈1⋯nV,i≠j. The network edge is connected to the core network via a logical link, denoted by lc. The capacity of lc is limited due to budget reasons: the network edge has a certain bandwidth quota. The total bandwidth to the cloud must be kept within the quota. In reality, lc can be a group of links connecting the remote cloud.


### 2.2. VNF Types and Resource Requirement Profiles (Flavors)

The network functions serving the IoT networks have been encapsulated into various types of VNFs. Each type provides a user with a specific service. When the demand increases for a certain type of VNF to a certain level that it exceeds the maximum capacity of current VNF instances, the VNF scales out by increasing the number of Virtual Machine (VM) instances, so that more requests can be processed at the same time. Depending on the purpose, different types of VNF have different resource requirements. The term “flavor” is used to describe the resource requirements profile of an instance of the VNF, including the number of vCPUs, the amount of memory, the size of the disk. We usef to define a VNF instance.Assigna to identify a specific type of network function and na to be the number of network function types. A VNF instance with type “a” can then be represented by f(a). The CPU, memory, and bandwidth requirements of f(a) are then denoted by U(f(a)), M(f(a)), and B(f(a)).


### 2.3. The User of a VNF Instance

Another property of a VNF instance is the user who owns and uses it. Suppose each pCPE node has one unique owner. This is a valid assumption as the actual device on customer premise is typically not shared and belongs to the entity who pays for the service. For a pCPE nodev, its owner u uses a set of VNF instances to satisfy its needs, regardless of where the instances are deployed. When referring to a specific node vi,i∈1⋯nV, we represent the node’s owner by ui, where i∈1⋯nV.Figure3 illustrates an example of VNF instances grouped by the user u1. There is 1 instance of f(a1) and 5 instances of f(a1). The only instance of f(a1), denoted by f1(a1), is on v1, along with f1(a2). Instances f2(a2) and f3(a2) are on v2. Instances f4(a2) and f5(a2) are on v3. The numbers and types of VNF instances grouped by their users are determined by user activities and can change dynamically according to user demands.Figure 3
An example of VNF instances grouped byu1.Based on the user of VNF instances, the annotation off can be extended from f(a) to f(a,u), where u is the user who owns and uses f.


### 2.4. Places to Deploy VNF Instances

Placement decisions are made based on the flavors, which are the resource requirement profiles, of VNF instances and the resource capacities of pCPE nodes. A VNF instance of a certain userui, denoted by f(a,ui), can be deployed at either of the locations below.


#### 2.4.1. B&B Deployment

For a VNF instancef(a,ui), any pCPE node within the same network edge can be considered as a candidate place to deploy, also known as B&B deployments. A B&B deployment is performed when f(a,ui) is deployed on a pCPE node vj. For a B&B deployment of f(a,ui), its notation can be extended to f(a,ui,vj), where vj is the place to deploy f. We use the set Fv to define all VNF instances deployed on the pCPE node v.Particularly, when there are enough resources on the pCPE nodevi of ui, f(a,ui) can be deployed on vi locally. For a local deployment of f(a,ui), its notation becomes f(a,ui,vi), where vi is the place to deploy f.


#### 2.4.2. Cloud Deployment

Besides B&B deployments, the remote cloud can be chosen as an alternative place to deploy VNF instances. For a cloud deployment off(a,ui), its notation can be extended to f(a,ui,c), where c is the place to deploy f, and c stands for the remote cloud location. We use the set Fc to define all VNF instances deployed on the cloud.


### 2.5. Factors to Impact Placement Decisions

The following factors will impact the placement decisions.


#### 2.5.1. pCPE Resource Capacity

Every pCPE nodev has its own resource capacity to host a limited number of VNF instances. As a compute node, the resources for VNF instances are as follows: virtual CPUs (vCPUs) and memory. We assume that there is a plenty of disk space on each pCPE node for any virtual instances deployed. Therefore, the disk space of the pCPE nodes is not in the scope of discussion. Let U(v) denote the number of vCPUs v can provide. Let M(v) be the total amount of memory for VNF instances from v. Figure 4 provides an example of the resource capacity for a pCPE node with 20 vCPUs and 10 GB memory in total. There are currently 2 instances of VNF f(a1) and 3 instances of f(a2) deployed on it.Figure 4
Capacities of the number of vCPUs and the amount of memory of a pCPE node. At the moment, there are 2 instances of VNFf(a1) and 3 instances of VNF f(a2).


#### 2.5.2. Edge Network Transmission Delay

Comparing with the core network transmission delay to be discussed in the next section, the transmission delay between pCPE nodes at the network edge can be ignored as the bandwidth between edge nodes is considered plenty and the transmission delay is small enough to be ignored in the discussion.


#### 2.5.3. Core Network Transmission Delay

The core network transmission delay of a VNF instancef offloaded to the cloud is defined as the time consumed by offloading the VNF instance to the cloud and is denoted by t(f), while Tmax(f) is the maximum allowed network delay for a specific network function instance. The actual delay must not exceed this limit, or the requests would eventually overflow the buffer and cause malfunction of the VNF.There are many factors that may affect the core network transmission delay. As stated in [10], the transmission delay to the cloud can be calculated by(3)Transmission  delay=Message  sizeNetwork  bandwidth. For the same message, the less available bandwidth left from the network edge to the cloud, the longer transmission delay will be. During the peak hours, more VNF instances are requested by users concurrently across the network and would congest lc. The severity of direct oversubscription is reflected by the residue bandwidth of the link from the edge switch to the cloud, denoted by R(lc), which is the link’s total bandwidth B(lc) less the mean bandwidth usage for all remote VNF instances. The smaller residue bandwidth R(lc) there is, the bigger core network transmission delay t(lc) we should expect.Because all network function instances offloaded to a remote cloud share the same linklc that connects the edge network to the remote cloud and the same cloud environment, we assume the core network transmission delay is the same for all offloaded network function instances to simplify the modeling process. Let B(lc) be the total bandwidth of lc and t(lc) be the transmission delay of lc. VNF instances take up the bandwidth of lc to communicate with the pCPE nodes. The latency of the core network is therefore highly correlated to the bandwidth consumption of lc.LetFc denote the set of VNF instances deployed in the remote cloud. R(lc) can be calculated by(4)Rlc=Blc-∑f∈FcBf,∀f∈Fc.Even iflc is not congested, the remote cloud environment may be degraded by other sources. For example, overloaded VNFs from other users or applications of a shared cloud could affect other VNFs on the same host because of overcommitting. To better utilize the resources on a host, overcommitting is enabled by default [11]. However, the performance could be jeopardized if some VNFs are taking up most of the resource [12]. We define the delay not directly caused by the network edge as a Td, where the value of Td changes according to the load of the cloud environment.Oversubscription will result in a higher core network delayt(lc). For all VNF instances offloaded to the cloud, there must be(5)tlc≤Tmaxf,∀f∈Fc.The equation above ensures the functionality of all VNFs offloaded to the cloud with the existence oft(lc). It draws a limit of how much VNF offloading can be done, since an oversubscribed cloud environment would increase t(lc). Based on the calculation of transmission delay, we further model t(lc) to be inversely proportional to R(lc)+b and proportional to Td with b as a constant scoping the maximum core network delay when the bandwidth of lc is depleted:(6)tlc=TdRlc+b,0≤Rlc≤Blc.Combining (5) with (6), we have(7)TdRlc+b≤Tmaxf,∀f∈Fc.WhenTd gets higher or R(lc) becomes lower, the value of t(lc) would exceed Tmax(f) of one or more offloaded VNF instances.


### 2.6. Cost of Offloading to Edge Network

By enabling the resource sharing of pCPE nodes across the network edge, SP benefits from extended containers hosting the VNFs. The costs of leveraging these resources include the following.


#### 2.6.1. Incentives Returned to End Users

By encouraging the users to participate in the resource sharing program and to consent to share, it is necessary to give incentives to the users based on the amount of resource shared. We denote the unit incentive of CPU, memory, and bandwidth usage for pCPE nodev as wU(v), wM(v), and wB(v), respectively. One exception is that when the pCPE node is hosting VNF instances used by its own user, the incentives do not apply.


#### 2.6.2. Extra Redundancy

Since the availability of the pCPE nodes is lower than the cloud, more standby VNF instances are needed. We define the redundancy factorγ to be the mean number of standby VNF instances needed for one VNF instance on B&B nodes.Based on the two factors above, the cost of offloading a VNF instancef to any of the pCPE nodes, denoted by S(f,v), is calculated as below:(8)Sf,v=1+γwUvUf+wMvMf+wBvBf.


### 2.7. Cost of Offloading to Cloud

As defined earlier, we usec to represent the remote cloud in general to deploy VNF instances, to make it distinct from B&B deployments. Although the resources in the cloud, especially in the public cloud, can be considered infinite [13] due to the elasticity of the amount of resources available, for a specific edge network, there are budgets for resources assigned to it. Therefore, resources in the cloud to an edge network are limited when we model them.The total amounts of vCPUs, memory, and network bandwidth assigned to the edge network we discuss in the cloud are denoted byU(c), M(c), and B(c), respectively. The cost of offloading to the cloud depends on its usage. In general, the less resources left in the cloud for the edge network, the higher unit price our model gives, because the cloud needs to be available as an alternative place to host vCPE instances. Allowing the cloud resources to be drained too early will jeopardize the flexibility of placement and do harm to the service availability.LetwU(c) stand for the unit cost for consuming the cloud’s CPU resource. We model wU(c) to be inversely proportional to the cloud’s remaining vCPUs with the constant of proportionality WU. The remaining number of vCPUs is denoted by RU(c). The total cost of vCPUs for a VNF instance f to be offloaded to the cloud, denoted by SU(f,c), is then(9)SUf,c=wUcUf=WURUc+δUf=WUUfUc-∑f′∈FcUf′+δ.In (9), δ is a small positive number to avoid dividing by zero.Also, letwM(c) represent the unit cost of the memory resource in the cloud. Like vCPUs, wM(c) is modeled to be inversely proportional to the cloud’s residue memory with the constant of proportionality WM. The residue memory resource of the cloud is denoted by RM(c). Similar to the induction of (9), we have the total cost of cloud memory for a VNF instance f denoted by SM(f,c), where δ is a small positive number to avoid dividing by zero:(10)SMf,c=wMcMf=WMRMc+δMf=WMMfMc-∑f′∈FcMf′+δ.LetwB(c) denote the unit cost of the remote cloud’s network bandwidth. The variable wB(c) is defined to be proportional to the core network delay t(lc) with the constant of proportionality WB. We define the total cost of bandwidth used between the VNF instance f and the cloud as SB(f,c). As defined previously, b is a constant representing the maximum core network delay when the bandwidth of lc is depleted. Then we have(11)SBf,c=wBcBf=WBtlcBf=WBTdRlc+bBf=WBTdBfBlc-∑f′∈FcBf′+b.From (9), (10), and (11), the cost of offloading a VNF instance f to the cloud, denoted by S(f,c), is then calculated as(12)Sf,c=SUf,c+SMf,c+SBf,c=WUUfUc-∑f′∈FcUf′+δ+WMMfMc-∑f′∈FcMf′+δ+WBTdBfBlc-∑f′∈FcBf′+b.


### 2.8. Objective and 0-1 Integer Programming Formulation

SP would like to reduce the total cost of deploying and running VNF instances for all users across the network edge. The VNF instances can be deployed either to the remote cloud locationc or to the pCPE location v. Based on where the VNF instances are offloaded, we identify two portions of costs offloading the VNF instances: (1) to the cloud and (2) to B&B nodes. The objective of the optimization is to minimize the total offloading cost of the SP.Variables
(i)
X
(
f
,
v
): a group of Boolean variables representing if each VNF instance f is deployed on the B&B node v.
(ii)
X
(
f
,
c
): a group of Boolean variables representing if each VNF instance f is deployed on the remote cloud c(13)Xf,v=0,fnot  deployed  onv;1,fdeployed  onv.Xf,c=0,fnot  deployed  on  cloud;1,fdeployed  on  cloud.Objective
(14)
Minimize
∑
f
∈
F
∑
v
∈
V
S
f
,
c
X
f
,
c
+
S
f
,
v
X
f
,
vConstraints
(15)
X
f
,
c
+
∑
v
∈
V
X
f
,
v
=
1
,
∀
f
∈
F
,
(16)
U
c
-
∑
f
∈
F
c
U
f
≥
0
,
(17)
M
c
-
∑
f
∈
F
c
M
f
≥
0
,
(18)
T
d
R
l
c
+
b
≤
T
m
a
x
f
,
∀
f
∈
F
c
,
(19)
U
v
-
∑
f
∈
F
v
U
f
≥
0
,
∀
v
∈
V
,
(20)
M
v
-
∑
f
∈
F
v
M
f
≥
0
,
∀
v
∈
V
.Remarks
(i)
Function (14) is the objective function. It minimizes the total cost of offloading VNFs instances to the cloud and to B&B nodes.
(ii)
Constraint (15) ensures that every VNF instance f∈F is only deployed at one place.
(iii)
Constraints (16) and (17) are the capacity bounds of the CPU and memory of the cloud. Each type of the three resources leveraged by all VNF instances offloaded to the cloud must not exceed the cloud’s allocated resource capacity for the network edge.
(iv)
Constraint (18) sets the bottom line of the residue bandwidth for lc between the network edge and the cloud, which is essentially setting a limit for the number of VNFs offloaded to the cloud.
(v)
Constraints (19) and (20) are the capacity bounds for CPU and memory of every pCPE node. Each type of the resources used by all VNFs offloaded to the vCPEs must not exceed these bounds.


## 2.1. Connected pCPE at Network Edge

We discuss one particular network edge, which includes all pCPE nodes under it. A network edge is defined as the networks connecting all pCPE nodes under it. We model a network edge to have a topology such that each pCPE node within it can communicate with another. An example with two network edges can be found in Figure2. The nodes of pCPE 1A, 1B, and 1C group as one network edge connected to each other via Edge Network 1, while the other one consists of the nodes 2A, 2B, and 2C, connected by Edge Network 2.Figure 2
Topologies at network edges. All pCPE nodes can communicate with each other if they are within the same network edge.Based on the definition above, the pCPE nodes and their links at the network edge can be modeled as a directed graphG=(V,L). Set V represents all pCPE nodes at the network edge, while L is the set of all connected links from one vCPE node to another. A pCPE node in V is denoted by v, and there is v∈V. Define the total number of pCPE nodes to be nV. Let vi be a specific pCPE node in V, such that(1)vi∈V,∀i∈1⋯nV. Since all pCPE nodes are connected to each other, G is strongly connected. For any data transmitted from one node vi to another node vj in V, there exists a link lij, such that(2)lij∈L,∀i,j∈1⋯nV,i≠j. The network edge is connected to the core network via a logical link, denoted by lc. The capacity of lc is limited due to budget reasons: the network edge has a certain bandwidth quota. The total bandwidth to the cloud must be kept within the quota. In reality, lc can be a group of links connecting the remote cloud.


## 2.2. VNF Types and Resource Requirement Profiles (Flavors)

The network functions serving the IoT networks have been encapsulated into various types of VNFs. Each type provides a user with a specific service. When the demand increases for a certain type of VNF to a certain level that it exceeds the maximum capacity of current VNF instances, the VNF scales out by increasing the number of Virtual Machine (VM) instances, so that more requests can be processed at the same time. Depending on the purpose, different types of VNF have different resource requirements. The term “flavor” is used to describe the resource requirements profile of an instance of the VNF, including the number of vCPUs, the amount of memory, the size of the disk. We usef to define a VNF instance.Assigna to identify a specific type of network function and na to be the number of network function types. A VNF instance with type “a” can then be represented by f(a). The CPU, memory, and bandwidth requirements of f(a) are then denoted by U(f(a)), M(f(a)), and B(f(a)).


## 2.3. The User of a VNF Instance

Another property of a VNF instance is the user who owns and uses it. Suppose each pCPE node has one unique owner. This is a valid assumption as the actual device on customer premise is typically not shared and belongs to the entity who pays for the service. For a pCPE nodev, its owner u uses a set of VNF instances to satisfy its needs, regardless of where the instances are deployed. When referring to a specific node vi,i∈1⋯nV, we represent the node’s owner by ui, where i∈1⋯nV.Figure3 illustrates an example of VNF instances grouped by the user u1. There is 1 instance of f(a1) and 5 instances of f(a1). The only instance of f(a1), denoted by f1(a1), is on v1, along with f1(a2). Instances f2(a2) and f3(a2) are on v2. Instances f4(a2) and f5(a2) are on v3. The numbers and types of VNF instances grouped by their users are determined by user activities and can change dynamically according to user demands.Figure 3
An example of VNF instances grouped byu1.Based on the user of VNF instances, the annotation off can be extended from f(a) to f(a,u), where u is the user who owns and uses f.


## 2.4. Places to Deploy VNF Instances

Placement decisions are made based on the flavors, which are the resource requirement profiles, of VNF instances and the resource capacities of pCPE nodes. A VNF instance of a certain userui, denoted by f(a,ui), can be deployed at either of the locations below.


### 2.4.1. B&B Deployment

For a VNF instancef(a,ui), any pCPE node within the same network edge can be considered as a candidate place to deploy, also known as B&B deployments. A B&B deployment is performed when f(a,ui) is deployed on a pCPE node vj. For a B&B deployment of f(a,ui), its notation can be extended to f(a,ui,vj), where vj is the place to deploy f. We use the set Fv to define all VNF instances deployed on the pCPE node v.Particularly, when there are enough resources on the pCPE nodevi of ui, f(a,ui) can be deployed on vi locally. For a local deployment of f(a,ui), its notation becomes f(a,ui,vi), where vi is the place to deploy f.


### 2.4.2. Cloud Deployment

Besides B&B deployments, the remote cloud can be chosen as an alternative place to deploy VNF instances. For a cloud deployment off(a,ui), its notation can be extended to f(a,ui,c), where c is the place to deploy f, and c stands for the remote cloud location. We use the set Fc to define all VNF instances deployed on the cloud.


## 2.4.1. B&B Deployment

For a VNF instancef(a,ui), any pCPE node within the same network edge can be considered as a candidate place to deploy, also known as B&B deployments. A B&B deployment is performed when f(a,ui) is deployed on a pCPE node vj. For a B&B deployment of f(a,ui), its notation can be extended to f(a,ui,vj), where vj is the place to deploy f. We use the set Fv to define all VNF instances deployed on the pCPE node v.Particularly, when there are enough resources on the pCPE nodevi of ui, f(a,ui) can be deployed on vi locally. For a local deployment of f(a,ui), its notation becomes f(a,ui,vi), where vi is the place to deploy f.


## 2.4.2. Cloud Deployment

Besides B&B deployments, the remote cloud can be chosen as an alternative place to deploy VNF instances. For a cloud deployment off(a,ui), its notation can be extended to f(a,ui,c), where c is the place to deploy f, and c stands for the remote cloud location. We use the set Fc to define all VNF instances deployed on the cloud.


## 2.5. Factors to Impact Placement Decisions

The following factors will impact the placement decisions.


### 2.5.1. pCPE Resource Capacity

Every pCPE nodev has its own resource capacity to host a limited number of VNF instances. As a compute node, the resources for VNF instances are as follows: virtual CPUs (vCPUs) and memory. We assume that there is a plenty of disk space on each pCPE node for any virtual instances deployed. Therefore, the disk space of the pCPE nodes is not in the scope of discussion. Let U(v) denote the number of vCPUs v can provide. Let M(v) be the total amount of memory for VNF instances from v. Figure 4 provides an example of the resource capacity for a pCPE node with 20 vCPUs and 10 GB memory in total. There are currently 2 instances of VNF f(a1) and 3 instances of f(a2) deployed on it.Figure 4
Capacities of the number of vCPUs and the amount of memory of a pCPE node. At the moment, there are 2 instances of VNFf(a1) and 3 instances of VNF f(a2).


### 2.5.2. Edge Network Transmission Delay

Comparing with the core network transmission delay to be discussed in the next section, the transmission delay between pCPE nodes at the network edge can be ignored as the bandwidth between edge nodes is considered plenty and the transmission delay is small enough to be ignored in the discussion.


### 2.5.3. Core Network Transmission Delay

The core network transmission delay of a VNF instancef offloaded to the cloud is defined as the time consumed by offloading the VNF instance to the cloud and is denoted by t(f), while Tmax(f) is the maximum allowed network delay for a specific network function instance. The actual delay must not exceed this limit, or the requests would eventually overflow the buffer and cause malfunction of the VNF.There are many factors that may affect the core network transmission delay. As stated in [10], the transmission delay to the cloud can be calculated by(3)Transmission  delay=Message  sizeNetwork  bandwidth. For the same message, the less available bandwidth left from the network edge to the cloud, the longer transmission delay will be. During the peak hours, more VNF instances are requested by users concurrently across the network and would congest lc. The severity of direct oversubscription is reflected by the residue bandwidth of the link from the edge switch to the cloud, denoted by R(lc), which is the link’s total bandwidth B(lc) less the mean bandwidth usage for all remote VNF instances. The smaller residue bandwidth R(lc) there is, the bigger core network transmission delay t(lc) we should expect.Because all network function instances offloaded to a remote cloud share the same linklc that connects the edge network to the remote cloud and the same cloud environment, we assume the core network transmission delay is the same for all offloaded network function instances to simplify the modeling process. Let B(lc) be the total bandwidth of lc and t(lc) be the transmission delay of lc. VNF instances take up the bandwidth of lc to communicate with the pCPE nodes. The latency of the core network is therefore highly correlated to the bandwidth consumption of lc.LetFc denote the set of VNF instances deployed in the remote cloud. R(lc) can be calculated by(4)Rlc=Blc-∑f∈FcBf,∀f∈Fc.Even iflc is not congested, the remote cloud environment may be degraded by other sources. For example, overloaded VNFs from other users or applications of a shared cloud could affect other VNFs on the same host because of overcommitting. To better utilize the resources on a host, overcommitting is enabled by default [11]. However, the performance could be jeopardized if some VNFs are taking up most of the resource [12]. We define the delay not directly caused by the network edge as a Td, where the value of Td changes according to the load of the cloud environment.Oversubscription will result in a higher core network delayt(lc). For all VNF instances offloaded to the cloud, there must be(5)tlc≤Tmaxf,∀f∈Fc.The equation above ensures the functionality of all VNFs offloaded to the cloud with the existence oft(lc). It draws a limit of how much VNF offloading can be done, since an oversubscribed cloud environment would increase t(lc). Based on the calculation of transmission delay, we further model t(lc) to be inversely proportional to R(lc)+b and proportional to Td with b as a constant scoping the maximum core network delay when the bandwidth of lc is depleted:(6)tlc=TdRlc+b,0≤Rlc≤Blc.Combining (5) with (6), we have(7)TdRlc+b≤Tmaxf,∀f∈Fc.WhenTd gets higher or R(lc) becomes lower, the value of t(lc) would exceed Tmax(f) of one or more offloaded VNF instances.


## 2.5.1. pCPE Resource Capacity

Every pCPE nodev has its own resource capacity to host a limited number of VNF instances. As a compute node, the resources for VNF instances are as follows: virtual CPUs (vCPUs) and memory. We assume that there is a plenty of disk space on each pCPE node for any virtual instances deployed. Therefore, the disk space of the pCPE nodes is not in the scope of discussion. Let U(v) denote the number of vCPUs v can provide. Let M(v) be the total amount of memory for VNF instances from v. Figure 4 provides an example of the resource capacity for a pCPE node with 20 vCPUs and 10 GB memory in total. There are currently 2 instances of VNF f(a1) and 3 instances of f(a2) deployed on it.Figure 4
Capacities of the number of vCPUs and the amount of memory of a pCPE node. At the moment, there are 2 instances of VNFf(a1) and 3 instances of VNF f(a2).


## 2.5.2. Edge Network Transmission Delay

Comparing with the core network transmission delay to be discussed in the next section, the transmission delay between pCPE nodes at the network edge can be ignored as the bandwidth between edge nodes is considered plenty and the transmission delay is small enough to be ignored in the discussion.


## 2.5.3. Core Network Transmission Delay

The core network transmission delay of a VNF instancef offloaded to the cloud is defined as the time consumed by offloading the VNF instance to the cloud and is denoted by t(f), while Tmax(f) is the maximum allowed network delay for a specific network function instance. The actual delay must not exceed this limit, or the requests would eventually overflow the buffer and cause malfunction of the VNF.There are many factors that may affect the core network transmission delay. As stated in [10], the transmission delay to the cloud can be calculated by(3)Transmission  delay=Message  sizeNetwork  bandwidth. For the same message, the less available bandwidth left from the network edge to the cloud, the longer transmission delay will be. During the peak hours, more VNF instances are requested by users concurrently across the network and would congest lc. The severity of direct oversubscription is reflected by the residue bandwidth of the link from the edge switch to the cloud, denoted by R(lc), which is the link’s total bandwidth B(lc) less the mean bandwidth usage for all remote VNF instances. The smaller residue bandwidth R(lc) there is, the bigger core network transmission delay t(lc) we should expect.Because all network function instances offloaded to a remote cloud share the same linklc that connects the edge network to the remote cloud and the same cloud environment, we assume the core network transmission delay is the same for all offloaded network function instances to simplify the modeling process. Let B(lc) be the total bandwidth of lc and t(lc) be the transmission delay of lc. VNF instances take up the bandwidth of lc to communicate with the pCPE nodes. The latency of the core network is therefore highly correlated to the bandwidth consumption of lc.LetFc denote the set of VNF instances deployed in the remote cloud. R(lc) can be calculated by(4)Rlc=Blc-∑f∈FcBf,∀f∈Fc.Even iflc is not congested, the remote cloud environment may be degraded by other sources. For example, overloaded VNFs from other users or applications of a shared cloud could affect other VNFs on the same host because of overcommitting. To better utilize the resources on a host, overcommitting is enabled by default [11]. However, the performance could be jeopardized if some VNFs are taking up most of the resource [12]. We define the delay not directly caused by the network edge as a Td, where the value of Td changes according to the load of the cloud environment.Oversubscription will result in a higher core network delayt(lc). For all VNF instances offloaded to the cloud, there must be(5)tlc≤Tmaxf,∀f∈Fc.The equation above ensures the functionality of all VNFs offloaded to the cloud with the existence oft(lc). It draws a limit of how much VNF offloading can be done, since an oversubscribed cloud environment would increase t(lc). Based on the calculation of transmission delay, we further model t(lc) to be inversely proportional to R(lc)+b and proportional to Td with b as a constant scoping the maximum core network delay when the bandwidth of lc is depleted:(6)tlc=TdRlc+b,0≤Rlc≤Blc.Combining (5) with (6), we have(7)TdRlc+b≤Tmaxf,∀f∈Fc.WhenTd gets higher or R(lc) becomes lower, the value of t(lc) would exceed Tmax(f) of one or more offloaded VNF instances.


## 2.6. Cost of Offloading to Edge Network

By enabling the resource sharing of pCPE nodes across the network edge, SP benefits from extended containers hosting the VNFs. The costs of leveraging these resources include the following.


### 2.6.1. Incentives Returned to End Users

By encouraging the users to participate in the resource sharing program and to consent to share, it is necessary to give incentives to the users based on the amount of resource shared. We denote the unit incentive of CPU, memory, and bandwidth usage for pCPE nodev as wU(v), wM(v), and wB(v), respectively. One exception is that when the pCPE node is hosting VNF instances used by its own user, the incentives do not apply.


### 2.6.2. Extra Redundancy

Since the availability of the pCPE nodes is lower than the cloud, more standby VNF instances are needed. We define the redundancy factorγ to be the mean number of standby VNF instances needed for one VNF instance on B&B nodes.Based on the two factors above, the cost of offloading a VNF instancef to any of the pCPE nodes, denoted by S(f,v), is calculated as below:(8)Sf,v=1+γwUvUf+wMvMf+wBvBf.


## 2.6.1. Incentives Returned to End Users

By encouraging the users to participate in the resource sharing program and to consent to share, it is necessary to give incentives to the users based on the amount of resource shared. We denote the unit incentive of CPU, memory, and bandwidth usage for pCPE nodev as wU(v), wM(v), and wB(v), respectively. One exception is that when the pCPE node is hosting VNF instances used by its own user, the incentives do not apply.


## 2.6.2. Extra Redundancy

Since the availability of the pCPE nodes is lower than the cloud, more standby VNF instances are needed. We define the redundancy factorγ to be the mean number of standby VNF instances needed for one VNF instance on B&B nodes.Based on the two factors above, the cost of offloading a VNF instancef to any of the pCPE nodes, denoted by S(f,v), is calculated as below:(8)Sf,v=1+γwUvUf+wMvMf+wBvBf.


## 2.7. Cost of Offloading to Cloud

As defined earlier, we usec to represent the remote cloud in general to deploy VNF instances, to make it distinct from B&B deployments. Although the resources in the cloud, especially in the public cloud, can be considered infinite [13] due to the elasticity of the amount of resources available, for a specific edge network, there are budgets for resources assigned to it. Therefore, resources in the cloud to an edge network are limited when we model them.The total amounts of vCPUs, memory, and network bandwidth assigned to the edge network we discuss in the cloud are denoted byU(c), M(c), and B(c), respectively. The cost of offloading to the cloud depends on its usage. In general, the less resources left in the cloud for the edge network, the higher unit price our model gives, because the cloud needs to be available as an alternative place to host vCPE instances. Allowing the cloud resources to be drained too early will jeopardize the flexibility of placement and do harm to the service availability.LetwU(c) stand for the unit cost for consuming the cloud’s CPU resource. We model wU(c) to be inversely proportional to the cloud’s remaining vCPUs with the constant of proportionality WU. The remaining number of vCPUs is denoted by RU(c). The total cost of vCPUs for a VNF instance f to be offloaded to the cloud, denoted by SU(f,c), is then(9)SUf,c=wUcUf=WURUc+δUf=WUUfUc-∑f′∈FcUf′+δ.In (9), δ is a small positive number to avoid dividing by zero.Also, letwM(c) represent the unit cost of the memory resource in the cloud. Like vCPUs, wM(c) is modeled to be inversely proportional to the cloud’s residue memory with the constant of proportionality WM. The residue memory resource of the cloud is denoted by RM(c). Similar to the induction of (9), we have the total cost of cloud memory for a VNF instance f denoted by SM(f,c), where δ is a small positive number to avoid dividing by zero:(10)SMf,c=wMcMf=WMRMc+δMf=WMMfMc-∑f′∈FcMf′+δ.LetwB(c) denote the unit cost of the remote cloud’s network bandwidth. The variable wB(c) is defined to be proportional to the core network delay t(lc) with the constant of proportionality WB. We define the total cost of bandwidth used between the VNF instance f and the cloud as SB(f,c). As defined previously, b is a constant representing the maximum core network delay when the bandwidth of lc is depleted. Then we have(11)SBf,c=wBcBf=WBtlcBf=WBTdRlc+bBf=WBTdBfBlc-∑f′∈FcBf′+b.From (9), (10), and (11), the cost of offloading a VNF instance f to the cloud, denoted by S(f,c), is then calculated as(12)Sf,c=SUf,c+SMf,c+SBf,c=WUUfUc-∑f′∈FcUf′+δ+WMMfMc-∑f′∈FcMf′+δ+WBTdBfBlc-∑f′∈FcBf′+b.


## 2.8. Objective and 0-1 Integer Programming Formulation

SP would like to reduce the total cost of deploying and running VNF instances for all users across the network edge. The VNF instances can be deployed either to the remote cloud locationc or to the pCPE location v. Based on where the VNF instances are offloaded, we identify two portions of costs offloading the VNF instances: (1) to the cloud and (2) to B&B nodes. The objective of the optimization is to minimize the total offloading cost of the SP.Variables
(i)
X
(
f
,
v
): a group of Boolean variables representing if each VNF instance f is deployed on the B&B node v.
(ii)
X
(
f
,
c
): a group of Boolean variables representing if each VNF instance f is deployed on the remote cloud c(13)Xf,v=0,fnot  deployed  onv;1,fdeployed  onv.Xf,c=0,fnot  deployed  on  cloud;1,fdeployed  on  cloud.Objective
(14)
Minimize
∑
f
∈
F
∑
v
∈
V
S
f
,
c
X
f
,
c
+
S
f
,
v
X
f
,
vConstraints
(15)
X
f
,
c
+
∑
v
∈
V
X
f
,
v
=
1
,
∀
f
∈
F
,
(16)
U
c
-
∑
f
∈
F
c
U
f
≥
0
,
(17)
M
c
-
∑
f
∈
F
c
M
f
≥
0
,
(18)
T
d
R
l
c
+
b
≤
T
m
a
x
f
,
∀
f
∈
F
c
,
(19)
U
v
-
∑
f
∈
F
v
U
f
≥
0
,
∀
v
∈
V
,
(20)
M
v
-
∑
f
∈
F
v
M
f
≥
0
,
∀
v
∈
V
.Remarks
(i)
Function (14) is the objective function. It minimizes the total cost of offloading VNFs instances to the cloud and to B&B nodes.
(ii)
Constraint (15) ensures that every VNF instance f∈F is only deployed at one place.
(iii)
Constraints (16) and (17) are the capacity bounds of the CPU and memory of the cloud. Each type of the three resources leveraged by all VNF instances offloaded to the cloud must not exceed the cloud’s allocated resource capacity for the network edge.
(iv)
Constraint (18) sets the bottom line of the residue bandwidth for lc between the network edge and the cloud, which is essentially setting a limit for the number of VNFs offloaded to the cloud.
(v)
Constraints (19) and (20) are the capacity bounds for CPU and memory of every pCPE node. Each type of the resources used by all VNFs offloaded to the vCPEs must not exceed these bounds.


## 3. IoT-B&B Heuristic Placement Algorithm

From the 0-1 integer programming in the previous section, we design a heuristic algorithm to achieve a lower cost by choosing the first valid candidate place to deploy new VNF instances, after the candidate places are sorted by the remaining resources.


### 3.1. Preliminary Resource Check

For every request of deploying a new VNF instance, we first use Algorithm1 to check the placement eligibility of every pCPE node, as well as the remote cloud. If the place does not meet the resource constraints of the instance, it will be excluded from the list of candidate places. By calling the function GetCandidates(f), a list of candidate places will be returned from the input of a specific VNF instance f and the current resource level. The list will be sorted by considering the lowest percentage of remaining resource type, in a descending order. For example, if a pCPE node has 90% of vCPU left but only 20% of memory left, then the remaining memory will be used for sorting.Algorithm 1:IoT-B&B resource eligibility check algorithm.
(
1
)     function  GetSortedCandidates(f)
(
2
)     create an empty list  candidates
(
3
)   for all  v∈V  do
(
4
)      if  IsResourceEnough(v,f)  then
(
5
)         add v to  candidates
(
6
)      end if
(
7
)   end for
(
8
)   sort  candidates  by remaining resources descending
(
9
)   if  IsResourceEnough(c,f)  then
(
10
)     add c to  candidates
(
11
)     end if
(
12
)     return  candidates
(
13
)  end function
(
14
)  function  IsResourceEnough(v,f)
(
15
)     if  v is c  then  ⊳ Check delay for cloud
(
16
)       link_bw_left  ←B(lc)+b
(
17
)       for all  f′∈Fc  do
(
18
)         link_bw_left  ←  link_bw_left  −  B(f′)
(
19
)       end for
(
20
)       delay  ←Td/  link_bw_left
(
21
)       if  delay  <Tmax(f)  then
(
22
)          return  false  ⊳ Too much delay
(
23
)       end if
(
24
)     end if
(
25
)     if  RU(v)<U(f)  then
(
26
)        return  false  ⊳ vCPU not enough
(
27
)     end if
(
28
)     if  RM(v)<M(f)  then
(
29
)        return  false  ⊳ memory not enough
(
30
)     end if
(
31
)     if  RB(v)<B(f)  then
(
32
)        return  false  ⊳ bandwidth not enough
(
33
)     end if
(
34
)     return  true  ⊳ validation passes
(
35
)  end function


### 3.2. Cost Estimation

With the list of eligible candidate places for a VNF instancef, we can further estimate the cost of f deployed at each place. Algorithms 2 and 3 provide implementation of the cost model from Section 2. Algorithm 3 defines the function to choose the place for VNF instance f at the lowest cost, namely, ChoosePlace(f). The function first calls GetCandidates(f) in Algorithm 1 to get the places eligible for deploying f. Then, for each eligible place, the cost is checked based on the type of the place based on Algorithm 2. If the place is the cloud, CloudCost(f) is invoked for cost; if the place is a pCPE node, the function BnbCost(f,v) is called instead. After iterating all eligible places, the place with the lowest cost is selected and returned.Algorithm 2:IoT-B&B cost estimation algorithm.
(
1
)    function  CloudCost(f)
(
2
)     cpu_left  ←  U(c)+δ
(
3
)     memory_left  ←  M(c)+δ
(
4
)     link_bw_left  ←  B(lc)+b
(
5
)     cost  ←  0
(
6
)     for all  f′∈Fc  do
(
7
)      cpu_left  ←  cpu_left  −  U(f′)
(
8
)      memory_left  ←  memory_left  −  M(f′)
(
9
)      link_bw_left  ←  link_bw_left  −  B(f′)
(
10
)      end for
(
11
)      cost  ←  cost  +  WUU(f)/cpu_left
(
12
)      cost  ←  cost  +  WMM(f)/memory_left
(
13
)      cost  ←  cost  +  WBTdB(f)/link_bw_left
(
14
)      return  cost
(
15
)  end function
(
16
)  function  BnbCost(f,v)
(
17
)     cost  ←  0
(
18
)     if  user of f does not own v  then
(
19
)      cost  ←  cost  +  wU(v)U(f)
(
20
)      cost  ←  cost  +  wM(v)M(f)
(
21
)      cost  ←  cost  +  wB(v)B(f)
(
22
)      cost  ←  cost  ×  (1+γ)
(
23
)     end if
(
24
)     return  cost
(
25
)  end functionAlgorithm 3:IoT-B&B place selection algorithm.
(
1
)     function  ChoosePlace(f)
(
2
)      candidates  ←  GetSortedCandidates(f)
(
3
)      for all  candidate  in  candidates  do
(
4
)      if  candidate  is c  then
(
5
)        current_cost  ←  CloudCost(f)
(
6
)      else
(
7
)        current_cost  ←  BnbCost(f,  candidate)
(
8
)      end if
(
9
)      if  current_cost  <  cost  then
(
10
)        return  place
(
11
)   end if
(
12
)   end for
(
13
)   return  none
(
14
)   end function


### 3.3. Time Complexity

Algorithm1 has the time complexity of O(nlog⁡(n)) because of sorting the pCPE nodes by remaining resources (assuming merge sort is used). Algorithm 2 has time complexity of O(1). Algorithm 3 will always compare the first candidate pCPE node with the cloud and choose the destination with the lower cost, which has the time complexity of O(1). Combining the three algorithms, the time complexity of IoT-B&B Algorithm is O(nlog⁡(n)).If the exhaustive algorithm is used, which does not sort the candidate pCPE nodes, it would have to check all candidates and find out the one with the lowest cost. Such algorithm would increase the time complexity toO(n2). Figure 5 shows the time consumed using the two different algorithms (Algorithms 2 and 3) with up to 50 pCPE nodes. From the results, we can see that VNF-B&B algorithm scales well compared to the exhaustive algorithm, where the time consumed is less than 1000 ms for 50 nodes, while the exhaustive algorithm takes more than 9000 ms.Figure 5
Time complexity comparison between IoT-B&B heuristic algorithm and the exhaustive algorithm checking all pCPE candidate nodes.


### 3.4. Access to IoT-B&B Algorithms

We have implemented the Java version of the IoT-B&B Algorithm library. The library source code is published under the MIT License and is downloadable from the following URL:https://github.com/zhuheec/iot-bnb.


## 3.1. Preliminary Resource Check

For every request of deploying a new VNF instance, we first use Algorithm1 to check the placement eligibility of every pCPE node, as well as the remote cloud. If the place does not meet the resource constraints of the instance, it will be excluded from the list of candidate places. By calling the function GetCandidates(f), a list of candidate places will be returned from the input of a specific VNF instance f and the current resource level. The list will be sorted by considering the lowest percentage of remaining resource type, in a descending order. For example, if a pCPE node has 90% of vCPU left but only 20% of memory left, then the remaining memory will be used for sorting.Algorithm 1:IoT-B&B resource eligibility check algorithm.
(
1
)     function  GetSortedCandidates(f)
(
2
)     create an empty list  candidates
(
3
)   for all  v∈V  do
(
4
)      if  IsResourceEnough(v,f)  then
(
5
)         add v to  candidates
(
6
)      end if
(
7
)   end for
(
8
)   sort  candidates  by remaining resources descending
(
9
)   if  IsResourceEnough(c,f)  then
(
10
)     add c to  candidates
(
11
)     end if
(
12
)     return  candidates
(
13
)  end function
(
14
)  function  IsResourceEnough(v,f)
(
15
)     if  v is c  then  ⊳ Check delay for cloud
(
16
)       link_bw_left  ←B(lc)+b
(
17
)       for all  f′∈Fc  do
(
18
)         link_bw_left  ←  link_bw_left  −  B(f′)
(
19
)       end for
(
20
)       delay  ←Td/  link_bw_left
(
21
)       if  delay  <Tmax(f)  then
(
22
)          return  false  ⊳ Too much delay
(
23
)       end if
(
24
)     end if
(
25
)     if  RU(v)<U(f)  then
(
26
)        return  false  ⊳ vCPU not enough
(
27
)     end if
(
28
)     if  RM(v)<M(f)  then
(
29
)        return  false  ⊳ memory not enough
(
30
)     end if
(
31
)     if  RB(v)<B(f)  then
(
32
)        return  false  ⊳ bandwidth not enough
(
33
)     end if
(
34
)     return  true  ⊳ validation passes
(
35
)  end function


## 3.2. Cost Estimation

With the list of eligible candidate places for a VNF instancef, we can further estimate the cost of f deployed at each place. Algorithms 2 and 3 provide implementation of the cost model from Section 2. Algorithm 3 defines the function to choose the place for VNF instance f at the lowest cost, namely, ChoosePlace(f). The function first calls GetCandidates(f) in Algorithm 1 to get the places eligible for deploying f. Then, for each eligible place, the cost is checked based on the type of the place based on Algorithm 2. If the place is the cloud, CloudCost(f) is invoked for cost; if the place is a pCPE node, the function BnbCost(f,v) is called instead. After iterating all eligible places, the place with the lowest cost is selected and returned.Algorithm 2:IoT-B&B cost estimation algorithm.
(
1
)    function  CloudCost(f)
(
2
)     cpu_left  ←  U(c)+δ
(
3
)     memory_left  ←  M(c)+δ
(
4
)     link_bw_left  ←  B(lc)+b
(
5
)     cost  ←  0
(
6
)     for all  f′∈Fc  do
(
7
)      cpu_left  ←  cpu_left  −  U(f′)
(
8
)      memory_left  ←  memory_left  −  M(f′)
(
9
)      link_bw_left  ←  link_bw_left  −  B(f′)
(
10
)      end for
(
11
)      cost  ←  cost  +  WUU(f)/cpu_left
(
12
)      cost  ←  cost  +  WMM(f)/memory_left
(
13
)      cost  ←  cost  +  WBTdB(f)/link_bw_left
(
14
)      return  cost
(
15
)  end function
(
16
)  function  BnbCost(f,v)
(
17
)     cost  ←  0
(
18
)     if  user of f does not own v  then
(
19
)      cost  ←  cost  +  wU(v)U(f)
(
20
)      cost  ←  cost  +  wM(v)M(f)
(
21
)      cost  ←  cost  +  wB(v)B(f)
(
22
)      cost  ←  cost  ×  (1+γ)
(
23
)     end if
(
24
)     return  cost
(
25
)  end functionAlgorithm 3:IoT-B&B place selection algorithm.
(
1
)     function  ChoosePlace(f)
(
2
)      candidates  ←  GetSortedCandidates(f)
(
3
)      for all  candidate  in  candidates  do
(
4
)      if  candidate  is c  then
(
5
)        current_cost  ←  CloudCost(f)
(
6
)      else
(
7
)        current_cost  ←  BnbCost(f,  candidate)
(
8
)      end if
(
9
)      if  current_cost  <  cost  then
(
10
)        return  place
(
11
)   end if
(
12
)   end for
(
13
)   return  none
(
14
)   end function


## 3.3. Time Complexity

Algorithm1 has the time complexity of O(nlog⁡(n)) because of sorting the pCPE nodes by remaining resources (assuming merge sort is used). Algorithm 2 has time complexity of O(1). Algorithm 3 will always compare the first candidate pCPE node with the cloud and choose the destination with the lower cost, which has the time complexity of O(1). Combining the three algorithms, the time complexity of IoT-B&B Algorithm is O(nlog⁡(n)).If the exhaustive algorithm is used, which does not sort the candidate pCPE nodes, it would have to check all candidates and find out the one with the lowest cost. Such algorithm would increase the time complexity toO(n2). Figure 5 shows the time consumed using the two different algorithms (Algorithms 2 and 3) with up to 50 pCPE nodes. From the results, we can see that VNF-B&B algorithm scales well compared to the exhaustive algorithm, where the time consumed is less than 1000 ms for 50 nodes, while the exhaustive algorithm takes more than 9000 ms.Figure 5
Time complexity comparison between IoT-B&B heuristic algorithm and the exhaustive algorithm checking all pCPE candidate nodes.


## 3.4. Access to IoT-B&B Algorithms

We have implemented the Java version of the IoT-B&B Algorithm library. The library source code is published under the MIT License and is downloadable from the following URL:https://github.com/zhuheec/iot-bnb.


## 4. System Implementation

We have implemented a system following the architecture illustrated in the previous section. The system provides a platform to practice and evaluate the IoT-B&B algorithm.


### 4.1. Hardware Configuration of pCPE Nodes

For flexibility and scalability, we use VMs instead of bare metal machines as pCPE nodes. Up to 99 VMs are deployed, and each acts as a pCPE node with 8 Cores of CPU, 16 GB of memory, and 40 GB of disk space. Every pCPE node can communicate with any other one via a private virtual network, to mimic that these pCPE nodes are at the same network edge.


### 4.2. NFVI Setup

Each pCPE node has CentOS 7 [14] installed as its operating system. It has its essential functionalities running as CPE. We use the OpenStack Kolla Project [15] to deploy OpenStack services across multiple pCPE nodes as well as PE, such that(a)
the OpenStack services on a pCPE node runs as Docker containers. They can be spun up and torn down with minimal overhead;(b)
with container-based OpenStack services, a pCPE node can be converted into an OpenStack compute node and then register to the controller to be one of the available hosts;(c)
when the pCPE is no longer available to be a compute node due to high usage, the OpenStack services on it can be stopped to free up resources.Figure6 reflects the architecture we use to provision IoT-B&B service upon container-based OpenStack.Figure 6
IoT-B&B service backed by container-based OpenStack.


### 4.3. IoT-B&B Algorithm as Filter Scheduler

To leverage the proposed IoT-B&B algorithm in the system, we implement it as afilter scheduler used by nova service, with the name VnfBnbFilter. The IoT-B&B algorithm matches the filtering-weighting mechanism of thefilter scheduler.Figure7 shows how IoT-B&B algorithm works as a filter scheduler to rank places to deploy. Suppose there are four places to choose: v1, v2, v3, and c. Algorithm 1 is first invoked to filter out ineligible places that do not have enough resources. In the example, v2 is filtered out as a result of resource shortage. Then, Algorithms 2 and 3 are used to rank the places according to the cost to deploy the VNF instance. They determine that v3 has the lowest cost to deploy the instance.Figure 7
IoT-B&B algorithm in OpenStack as afilter scheduler.


### 4.4. System Life Cycle

We define a set of system states and events for IoT-B&B. The system transitions its state based on the events according to the actual demand, in order to adjust the scaling of the VNF. As Figure8 shows, the states and events are listed as follows.Figure 8
IoT-B&B service system life cycle.


#### 4.4.1. Up State

The state indicates the system is up and running as expected. System load level is acceptable to satisfy the needs. The system is expected to stay in this state if it runs properly.


#### 4.4.2. Load Check Event

This is the event to update the system load level. If the updated load level triggers a change, the system may enter Overloaded or Underloaded state or remain in Up state, depending on the threshold to determine them.


#### 4.4.3. Overloaded State

The state indicates the system is overloaded by a higher volume of requests. A scale-out is pending. The placement scheduler will be invoked to determine the place to scale out: B&B or the cloud and then triggers the actual event to scale out.


#### 4.4.4. Scale-out to B&B Event

This is the event to trigger a new VM to be deployed on a B&B, that is, a CPE deployment.


#### 4.4.5. Scale-out to Cloud Event

This is the event to trigger a new VM to be scaled out in the remote cloud environment.


#### 4.4.6. Underloaded State

The state indicates the system is underloaded because of a lower volume of requests. A scale-in is pending. If the number of the VMs has already reached the minimum number required, then the system would not enter this state.


#### 4.4.7. Scale-in Event

This is the event to trigger an existing VM to be scaled in from either the B&B or the remote cloud.


#### 4.4.8. Migration Event

This is the event that is triggered by pCPE availability changes. When a pCPE is no longer capable of hosting a VM because of higher usage from its user, it will cease to be a B&B and be removed from the list of available hosts. Meanwhile, the migration event will be added to the system to move the existing VMs deployed.


### 4.5. Typical Use Cases

With the definition of the system life cycle, we describe typical uses cases leveraging the IoT-B&B algorithm.


#### 4.5.1. Launch of New Application

The dynamic nature of IoT-based services allows the user to launch new applications which are processed by new VNF instances. A new VNF instance does not automatically get deployed on-site, that is, the pCPE node of its user. The reason can range from lack of enough resources to higher cost being deployed on-site. The IoT-B&B algorithm will be called to determine the place to deploy the new VNF instances.


#### 4.5.2. Scaling out due to Higher Load

When the user applications have more significant activities, resulting in a higher load of the existing instances, the system’s periodical load check daemon will detect the load increase. If the load is above the threshold raising flags of performance, extra VNF instances are needed for processing the larger amount of requests. The IoT-B&B algorithm will be called to determine the place to scale out new VNF instances.


#### 4.5.3. Migration for Lower Cost

The VNF instances in the cloud may start with low cost. However, it does not last forever. As more VNF instances are deployed to the remote cloud, fewer resources are available and the unit resource becomes more expensive. At some point, a migration from the cloud to B&B nodes, or vice versa, is reasonable to lower considerable cost.


## 4.1. Hardware Configuration of pCPE Nodes

For flexibility and scalability, we use VMs instead of bare metal machines as pCPE nodes. Up to 99 VMs are deployed, and each acts as a pCPE node with 8 Cores of CPU, 16 GB of memory, and 40 GB of disk space. Every pCPE node can communicate with any other one via a private virtual network, to mimic that these pCPE nodes are at the same network edge.


## 4.2. NFVI Setup

Each pCPE node has CentOS 7 [14] installed as its operating system. It has its essential functionalities running as CPE. We use the OpenStack Kolla Project [15] to deploy OpenStack services across multiple pCPE nodes as well as PE, such that(a)
the OpenStack services on a pCPE node runs as Docker containers. They can be spun up and torn down with minimal overhead;(b)
with container-based OpenStack services, a pCPE node can be converted into an OpenStack compute node and then register to the controller to be one of the available hosts;(c)
when the pCPE is no longer available to be a compute node due to high usage, the OpenStack services on it can be stopped to free up resources.Figure6 reflects the architecture we use to provision IoT-B&B service upon container-based OpenStack.Figure 6
IoT-B&B service backed by container-based OpenStack.


## 4.3. IoT-B&B Algorithm as Filter Scheduler

To leverage the proposed IoT-B&B algorithm in the system, we implement it as afilter scheduler used by nova service, with the name VnfBnbFilter. The IoT-B&B algorithm matches the filtering-weighting mechanism of thefilter scheduler.Figure7 shows how IoT-B&B algorithm works as a filter scheduler to rank places to deploy. Suppose there are four places to choose: v1, v2, v3, and c. Algorithm 1 is first invoked to filter out ineligible places that do not have enough resources. In the example, v2 is filtered out as a result of resource shortage. Then, Algorithms 2 and 3 are used to rank the places according to the cost to deploy the VNF instance. They determine that v3 has the lowest cost to deploy the instance.Figure 7
IoT-B&B algorithm in OpenStack as afilter scheduler.


## 4.4. System Life Cycle

We define a set of system states and events for IoT-B&B. The system transitions its state based on the events according to the actual demand, in order to adjust the scaling of the VNF. As Figure8 shows, the states and events are listed as follows.Figure 8
IoT-B&B service system life cycle.


### 4.4.1. Up State

The state indicates the system is up and running as expected. System load level is acceptable to satisfy the needs. The system is expected to stay in this state if it runs properly.


### 4.4.2. Load Check Event

This is the event to update the system load level. If the updated load level triggers a change, the system may enter Overloaded or Underloaded state or remain in Up state, depending on the threshold to determine them.


### 4.4.3. Overloaded State

The state indicates the system is overloaded by a higher volume of requests. A scale-out is pending. The placement scheduler will be invoked to determine the place to scale out: B&B or the cloud and then triggers the actual event to scale out.


### 4.4.4. Scale-out to B&B Event

This is the event to trigger a new VM to be deployed on a B&B, that is, a CPE deployment.


### 4.4.5. Scale-out to Cloud Event

This is the event to trigger a new VM to be scaled out in the remote cloud environment.


### 4.4.6. Underloaded State

The state indicates the system is underloaded because of a lower volume of requests. A scale-in is pending. If the number of the VMs has already reached the minimum number required, then the system would not enter this state.


### 4.4.7. Scale-in Event

This is the event to trigger an existing VM to be scaled in from either the B&B or the remote cloud.


### 4.4.8. Migration Event

This is the event that is triggered by pCPE availability changes. When a pCPE is no longer capable of hosting a VM because of higher usage from its user, it will cease to be a B&B and be removed from the list of available hosts. Meanwhile, the migration event will be added to the system to move the existing VMs deployed.


## 4.4.1. Up State

The state indicates the system is up and running as expected. System load level is acceptable to satisfy the needs. The system is expected to stay in this state if it runs properly.


## 4.4.2. Load Check Event

This is the event to update the system load level. If the updated load level triggers a change, the system may enter Overloaded or Underloaded state or remain in Up state, depending on the threshold to determine them.


## 4.4.3. Overloaded State

The state indicates the system is overloaded by a higher volume of requests. A scale-out is pending. The placement scheduler will be invoked to determine the place to scale out: B&B or the cloud and then triggers the actual event to scale out.


## 4.4.4. Scale-out to B&B Event

This is the event to trigger a new VM to be deployed on a B&B, that is, a CPE deployment.


## 4.4.5. Scale-out to Cloud Event

This is the event to trigger a new VM to be scaled out in the remote cloud environment.


## 4.4.6. Underloaded State

The state indicates the system is underloaded because of a lower volume of requests. A scale-in is pending. If the number of the VMs has already reached the minimum number required, then the system would not enter this state.


## 4.4.7. Scale-in Event

This is the event to trigger an existing VM to be scaled in from either the B&B or the remote cloud.


## 4.4.8. Migration Event

This is the event that is triggered by pCPE availability changes. When a pCPE is no longer capable of hosting a VM because of higher usage from its user, it will cease to be a B&B and be removed from the list of available hosts. Meanwhile, the migration event will be added to the system to move the existing VMs deployed.


## 4.5. Typical Use Cases

With the definition of the system life cycle, we describe typical uses cases leveraging the IoT-B&B algorithm.


### 4.5.1. Launch of New Application

The dynamic nature of IoT-based services allows the user to launch new applications which are processed by new VNF instances. A new VNF instance does not automatically get deployed on-site, that is, the pCPE node of its user. The reason can range from lack of enough resources to higher cost being deployed on-site. The IoT-B&B algorithm will be called to determine the place to deploy the new VNF instances.


### 4.5.2. Scaling out due to Higher Load

When the user applications have more significant activities, resulting in a higher load of the existing instances, the system’s periodical load check daemon will detect the load increase. If the load is above the threshold raising flags of performance, extra VNF instances are needed for processing the larger amount of requests. The IoT-B&B algorithm will be called to determine the place to scale out new VNF instances.


### 4.5.3. Migration for Lower Cost

The VNF instances in the cloud may start with low cost. However, it does not last forever. As more VNF instances are deployed to the remote cloud, fewer resources are available and the unit resource becomes more expensive. At some point, a migration from the cloud to B&B nodes, or vice versa, is reasonable to lower considerable cost.


## 4.5.1. Launch of New Application

The dynamic nature of IoT-based services allows the user to launch new applications which are processed by new VNF instances. A new VNF instance does not automatically get deployed on-site, that is, the pCPE node of its user. The reason can range from lack of enough resources to higher cost being deployed on-site. The IoT-B&B algorithm will be called to determine the place to deploy the new VNF instances.


## 4.5.2. Scaling out due to Higher Load

When the user applications have more significant activities, resulting in a higher load of the existing instances, the system’s periodical load check daemon will detect the load increase. If the load is above the threshold raising flags of performance, extra VNF instances are needed for processing the larger amount of requests. The IoT-B&B algorithm will be called to determine the place to scale out new VNF instances.


## 4.5.3. Migration for Lower Cost

The VNF instances in the cloud may start with low cost. However, it does not last forever. As more VNF instances are deployed to the remote cloud, fewer resources are available and the unit resource becomes more expensive. At some point, a migration from the cloud to B&B nodes, or vice versa, is reasonable to lower considerable cost.


## 5. Numerical Results

The numerical results based on simulations are shown in this section. From the numerical results, our goals are to verify the benefits of leveraging B&B nodes, compared to using a centralized cloud alone. Table1 lists the values of the constants used in the algorithms.Table 1
Constant configurations.
Constant
Value
T
d
50000 ms
W
U
1000
W
M
1000
W
B
1000
δ
1
b
1
γ
1


### 5.1. Host Nodes Setup

We create 99 pCPE nodes with random levels of initial resources. As all pCPE nodes and the cloud are used to deploy VNF instances, in our configuration, there is a total of 100 nodes for deployments. As seen in Figure9, the nodes are arranged as a 10 × 10 matrix. Each node is represented by a cell, and is given a horizontal and a vertical coordinate from 1 to 10. The last element, which has the coordinates (10,10), represents the remote cloud. The colors of the cells reflect the remaining resource levels of the nodes. For the ease of demonstration, the CPU, memory, and bandwidth resources are all broken into 20 levels ranging from 1 to 20. Deploying VNF instances on a pCPE node follows the Law of the Minimum [16], meaning that the capacity of a pCPE node to host instances is determined by its scarcest resource. Therefore, we color the cells according to the resource type of the lowest level of a node. For example, if the remaining CPU level of a node is 20, while the memory level is 3, the cell representing the node will be colored at Level 3. From the initial resource levels, it can be learned that the pCPE nodes have various levels of resources available. Meanwhile, the cloud starts with the maximum level of resources for deployment.Figure 9
Initial resource levels of the 100 nodes used for experiments. The nodes are arranged as a 10 × 10 matrix, where the last element represents the cloud.


### 5.2. VNF Resource Requirement Profile (Flavor) Types

We predefine 10 types of VNF resource requirement profiles (flavors), as shown in Table2, with different requirements of resources and max delays allowed. A VNF instance to be deployed will have a flavor from the 10 predefined ones. Templating VNF flavors is based on the real use cases as users will need VNF instances from limited kinds of images for serving known functionalities.Table 2
Predefined flavor types for simulation. Resource requirements in units.
Name
CPU
Memory
Bandwidth
Max delay
F1
1
1
1
1000 ms
F2
2
2
2
100 ms
F3
2
2
2
1000 ms
F4
2
2
2
10000 ms
F5
4
4
4
100 ms
F6
4
4
4
1000 ms
F7
4
4
4
10000 ms
F8
8
8
8
100 ms
F9
8
8
8
1000 ms
F10
8
8
8
10000 ms


### 5.3. Placement Configuration Modes

In order to compare the effectiveness of the IoT-B&B algorithm, we configure the simulated system to keep deploying new VNF instances of a specific flavor with one of the three modes below, until the resources are depleted:(i)
Local mode: deploying only on the pCPE node the user owns. The cloud and B&B nodes are not allowed.(ii)
Local + cloud mode: deploying locally on the pCPE node the user owns, as well as on the remote cloud.(iii)
Local + cloud + B&B mode: local, cloud, and B&B deployments.


### 5.4. Extended VNF Instance Capacity

Figure10 shows the numbers of instances of deploying each of the 10 predefined flavors with the 3 modes. From the results of Figure 10, we learn that the numbers of instances deployed for all 10 flavors have dramatically increased. Taking F3 as an example, inLocal Mode, only 9 instances are deployed. When usingLocal + Cloud Mode, the number jumps to 85. ForLocal + Cloud + B&B Mode, the number skyrockets to 550. Therefore, the most beneficial part of the system is to extend the total capacity of hosting VNF instances. If using the remote cloud alone, the capacity of the cloud for VNF instances is limited by the core network delay, even if other resources are assumed to be unlimited. This bottleneck is greatly relieved by the B&B nodes hosting instances, because the instances on B&B nodes do not put extra traffic to the core network.Figure 10
Total number of VNF instances deployed for the network edge with various flavors and placement configuration modes.


### 5.5. Cost Hike by Cloud Load Increase

We pick the three flavors: F3, F6, and F9, to investigate the trends of cost increase as more VNF instances are deployed in the system. Figures11 and 12 demonstrate the changes of costs to deploy a new VNF instance on the cloud in two different modes, as the numbers of deployed instances go up.Figure 11
Cost hikes when the cloud load increases:Local + Cloud Mode.Figure 12
Cost hikes when the cloud load increases:Local + Cloud + B&B Mode.UsingLocal + Cloud Mode, the cost is first 0 as the instances are deployed on the local pCPE nodes. As the loads increase, the remote cloud starts to be picked and the cost to deploy an instance increases as the numbers of deployed instances climb. For F6 and F9, the numbers of deployed VNF instances stop at 42 and 21, respectively.Comparing Figure12 with Figure 11, inLocal + Cloud + B&B Mode, the costs are lower when deploying the same numbers of instances in the system. For instance, when deploying 20 instances with flavor F9, the cost usingLocal + Cloud Mode is about 140. Meanwhile, when deploying the same number of instances with the same flavor, the cost underLocal + Cloud + B&B Mode is only around 50.The results above have demonstrated the ability of the B&B nodes to redirect the load off the cloud and to reduce the overall cost, even if offering incentives to the users.


### 5.6. Impact from outside the Network Edge

As discussed in Section2, when the cloud load from outside the network edge gets higher, that is, the value of Td is higher, the ability of the cloud hosting VNF instances may be reduced. To verify how much the impact will be, underLocal + Cloud + B&B Mode and for the three flavors F3, F6, and F9, we increase the level of Td by 1 each time and repeat the deployment for 10 times. The numbers of VNF instances deployed are shown in Figure 13. From the results, the capacity of the system is affected by the increase of Td. However, the impact becomes less significant as the level of Td increases. With the considerable buffer of the B&B nodes, the impact from Td is reduced.Figure 13
Cost changes when the cloud load increases due to tasks outside the target network edge.


### 5.7. Remaining Resource Levels

InLocal + Cloud + B&B Mode, all B&B nodes participate in hosting VNF instances. We examine the resource levels after the system resources are depleted. When all VNF instances deployed are of flavor F1, the resource levels after the maximum number of instances is deployed are displayed in Figure 14.Figure 14
Remaining resource levels after all B&B nodes have been used.The dark colors of all cells indicate that the remaining resource levels are low across all pCPE nodes. The cloud resource levels are also low because of the link/delay bottleneck from the network edge to the core network. The results have demonstrated the ability of the IoT-B&B algorithm to extract the resources to deploy more instances following the best-effort basis.


## 5.1. Host Nodes Setup

We create 99 pCPE nodes with random levels of initial resources. As all pCPE nodes and the cloud are used to deploy VNF instances, in our configuration, there is a total of 100 nodes for deployments. As seen in Figure9, the nodes are arranged as a 10 × 10 matrix. Each node is represented by a cell, and is given a horizontal and a vertical coordinate from 1 to 10. The last element, which has the coordinates (10,10), represents the remote cloud. The colors of the cells reflect the remaining resource levels of the nodes. For the ease of demonstration, the CPU, memory, and bandwidth resources are all broken into 20 levels ranging from 1 to 20. Deploying VNF instances on a pCPE node follows the Law of the Minimum [16], meaning that the capacity of a pCPE node to host instances is determined by its scarcest resource. Therefore, we color the cells according to the resource type of the lowest level of a node. For example, if the remaining CPU level of a node is 20, while the memory level is 3, the cell representing the node will be colored at Level 3. From the initial resource levels, it can be learned that the pCPE nodes have various levels of resources available. Meanwhile, the cloud starts with the maximum level of resources for deployment.Figure 9
Initial resource levels of the 100 nodes used for experiments. The nodes are arranged as a 10 × 10 matrix, where the last element represents the cloud.


## 5.2. VNF Resource Requirement Profile (Flavor) Types

We predefine 10 types of VNF resource requirement profiles (flavors), as shown in Table2, with different requirements of resources and max delays allowed. A VNF instance to be deployed will have a flavor from the 10 predefined ones. Templating VNF flavors is based on the real use cases as users will need VNF instances from limited kinds of images for serving known functionalities.Table 2
Predefined flavor types for simulation. Resource requirements in units.
Name
CPU
Memory
Bandwidth
Max delay
F1
1
1
1
1000 ms
F2
2
2
2
100 ms
F3
2
2
2
1000 ms
F4
2
2
2
10000 ms
F5
4
4
4
100 ms
F6
4
4
4
1000 ms
F7
4
4
4
10000 ms
F8
8
8
8
100 ms
F9
8
8
8
1000 ms
F10
8
8
8
10000 ms


## 5.3. Placement Configuration Modes

In order to compare the effectiveness of the IoT-B&B algorithm, we configure the simulated system to keep deploying new VNF instances of a specific flavor with one of the three modes below, until the resources are depleted:(i)
Local mode: deploying only on the pCPE node the user owns. The cloud and B&B nodes are not allowed.(ii)
Local + cloud mode: deploying locally on the pCPE node the user owns, as well as on the remote cloud.(iii)
Local + cloud + B&B mode: local, cloud, and B&B deployments.


## 5.4. Extended VNF Instance Capacity

Figure10 shows the numbers of instances of deploying each of the 10 predefined flavors with the 3 modes. From the results of Figure 10, we learn that the numbers of instances deployed for all 10 flavors have dramatically increased. Taking F3 as an example, inLocal Mode, only 9 instances are deployed. When usingLocal + Cloud Mode, the number jumps to 85. ForLocal + Cloud + B&B Mode, the number skyrockets to 550. Therefore, the most beneficial part of the system is to extend the total capacity of hosting VNF instances. If using the remote cloud alone, the capacity of the cloud for VNF instances is limited by the core network delay, even if other resources are assumed to be unlimited. This bottleneck is greatly relieved by the B&B nodes hosting instances, because the instances on B&B nodes do not put extra traffic to the core network.Figure 10
Total number of VNF instances deployed for the network edge with various flavors and placement configuration modes.


## 5.5. Cost Hike by Cloud Load Increase

We pick the three flavors: F3, F6, and F9, to investigate the trends of cost increase as more VNF instances are deployed in the system. Figures11 and 12 demonstrate the changes of costs to deploy a new VNF instance on the cloud in two different modes, as the numbers of deployed instances go up.Figure 11
Cost hikes when the cloud load increases:Local + Cloud Mode.Figure 12
Cost hikes when the cloud load increases:Local + Cloud + B&B Mode.UsingLocal + Cloud Mode, the cost is first 0 as the instances are deployed on the local pCPE nodes. As the loads increase, the remote cloud starts to be picked and the cost to deploy an instance increases as the numbers of deployed instances climb. For F6 and F9, the numbers of deployed VNF instances stop at 42 and 21, respectively.Comparing Figure12 with Figure 11, inLocal + Cloud + B&B Mode, the costs are lower when deploying the same numbers of instances in the system. For instance, when deploying 20 instances with flavor F9, the cost usingLocal + Cloud Mode is about 140. Meanwhile, when deploying the same number of instances with the same flavor, the cost underLocal + Cloud + B&B Mode is only around 50.The results above have demonstrated the ability of the B&B nodes to redirect the load off the cloud and to reduce the overall cost, even if offering incentives to the users.


## 5.6. Impact from outside the Network Edge

As discussed in Section2, when the cloud load from outside the network edge gets higher, that is, the value of Td is higher, the ability of the cloud hosting VNF instances may be reduced. To verify how much the impact will be, underLocal + Cloud + B&B Mode and for the three flavors F3, F6, and F9, we increase the level of Td by 1 each time and repeat the deployment for 10 times. The numbers of VNF instances deployed are shown in Figure 13. From the results, the capacity of the system is affected by the increase of Td. However, the impact becomes less significant as the level of Td increases. With the considerable buffer of the B&B nodes, the impact from Td is reduced.Figure 13
Cost changes when the cloud load increases due to tasks outside the target network edge.


## 5.7. Remaining Resource Levels

InLocal + Cloud + B&B Mode, all B&B nodes participate in hosting VNF instances. We examine the resource levels after the system resources are depleted. When all VNF instances deployed are of flavor F1, the resource levels after the maximum number of instances is deployed are displayed in Figure 14.Figure 14
Remaining resource levels after all B&B nodes have been used.The dark colors of all cells indicate that the remaining resource levels are low across all pCPE nodes. The cloud resource levels are also low because of the link/delay bottleneck from the network edge to the core network. The results have demonstrated the ability of the IoT-B&B algorithm to extract the resources to deploy more instances following the best-effort basis.


## 6. Related Work

NFV has been a key role to accelerate usage-based changes and to reduce OPEX by both SPs and vendor. Much of the recent NFV research relies on cloud computing as the underlying infrastructure [17].By leveraging generic cloud computing Infrastructure-as-a-Service (IaaS) frameworks, such as OpenStack [18] and VMWare [19], research on cloud-based NFV has been done to ensure that VNFs run at optimum levels in the cloud [20]. Soares et al. presented a platform for VNFs called Cloud4NFV [3], which is compliant with the ETSI [9] NFV architectural specification. Two approaches were discussed to virtualize NF: full virtualization moved all control and user plane functional entities to the cloud, while partial virtualization still forwarded user traffic to physical hardware. With the implementation of service provisioning and end-to-end inventory management, vConductor [21] was presented by Shen et al. that enabled users to plan the virtual network services using its data model. The systems and architectures above focus on deploying VNF instances into the generic cloud infrastructure, rather than the edge of the network.Due to the nature of varying cost of resources in the cloud, cloud-based resource allocation problems have been studied to reduce the cost and to help evenly distribute the workload. We have analyzed vulnerability of mobile apps in [22] to keep sensitive information in local mobile device, while offloading secured computing-intensive modules to the cloud. Xiao et al. [23] presented a system leveraging virtualization to dynamically allocate resources in datacenter and to optimize the number of servers in use. While these solutions did help better use cloud resources, they keep the computing remotely in the cloud and will not move it to the edge of the network.The concept of fog computing was proposed in [7] and was anticipated to become an essential part of cloud computing with the volume of Internet-of-Things (IoT) growing explosively. Vaquero and Rodero-Merino [24] proposed a comprehensive definition of the fog covering its features and impact, including device ubiquity, challenges on service and fog-based network management, levels of device connectivity, and privacy. Edge clouds were presented as entry points for IoT, which could be parts of the Enhanced Packet Core (EPC). The scenarios of fog computing in several domains were discussed in [25], including Smart Grid, IoT, and SDN, with topics about security, privacy, trust, and service migration. The work above has pointed the research direction of leveraging the edge of the network from high levels. Based on fog computing, crowdsourcing becomes an option as fog nodes can be updated dynamically with the participation of the third party. The security and privacy challenges were illustrated in [26], where a general architecture was presented to model crowdsourcing networks, including crowdsourcing sensing and crowdsourcing computing. The security concerns were captured from the characteristics of the architecture.Virtualization in edge networks as a form of fog computing, including NFV, have been given a close look. Manzalini et al. visioned potential value chain shifts and business opportunities in [27] by emerging paradigms such as SDN and NFV. The paper pictured a massive number of virtualized network and service functions running at the edge of the network, making the processing power more distributed globally. The service chaining in the cloud-based edge networks was analyzed in [28] by programming actions into OpenFlow switches to achieve dynamic service chaining. A platform called Network Functions At The Edge (NetFATE) was proposed in [29] as a proof of concept (PoC) of an NFV framework at the edge of a telco operator networks. Each CPE node was realized with a generic-purpose computer installed with a hypervisor and virtual switches. This made the CPE node capable of deploying VNFs on itself. The focus of this paper was to prove that deploying VNFs on the edge of the network is feasible. However, the benefits of resource sharing across different CPE nodes are not mentioned.


## 7. Conclusions

In this paper, we have presented the architecture and the algorithms to share resources of pCPE nodes across the network edge. When a sharable pCPE node has enough resources, SP will utilize its free resources as a bed-and-breakfast place to deploy VNFs of other users from the same network edge for a certain period. The users can get incentives by allowing SP to leverage the free resources.By applying the VNF-B&B architecture, the capacity of VNF instances for the network edge is greatly increased. The cost of offloading to the centralized cloud is reduced. By keeping the VNFs at the network edge, the delay is reduced for better processing of real-time data burst from IoT devices. Meanwhile, the traffic load to the core network is substantially reduced with the same number of VNF instances deployed.Making better use of the network edge is an interesting topic and has a massive potential. While the paper ends here, we are continuing to beef up the architecture, including the following:(i)
Explore the availability to factor in the service up and down of B&B nodes. This paper has used a constant factor to model the backup VNF instances. The modeling can be improved so that it is closer to the real-world scenario.(ii)
Consider more factors impacting the deployment placement besides vCPUs, memory, and network bandwidth. Also, consider detailed factors that can indirectly impact the cost and the core network delay of the remote cloud.Future work of this paper will consider the items listed above with the aim of obtaining a practical and effective framework of virtualizing and utilizing the network edge.



---

*Source: 3027269-2018-02-04.xml*