API tools faq
paste
Advertisement
Guest User

code

a guest
Feb 17th, 2020
219
0
Never
Add comment
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 75.65 KB | None | 0 0
raw download clone embed print report
  1. %%
  2. %% Copyright 2007, 2008, 2009 Elsevier Ltd
  3. %%
  4. %% This file is part of the 'Elsarticle Bundle'.
  5. %% ---------------------------------------------
  6. %%
  7. %% It may be distributed under the conditions of the LaTeX Project Public
  8. %% License, either version 1.2 of this license or (at your option) any
  9. %% later version. The latest version of this license is in
  10. %% http://www.latex-project.org/lppl.txt
  11. %% and version 1.2 or later is part of all distributions of LaTeX
  12. %% version 1999/12/01 or later.
  13. %%
  14. %% The list of all files belonging to the 'Elsarticle Bundle' is
  15. %% given in the file `manifest.txt'.
  16. %%
  17.  
  18. %% Template article for Elsevier's document class `elsarticle'
  19. %% with numbered style bibliographic references
  20. %% SP 2008/03/01
  21. %%
  22. %%
  23. %%
  24. %% $Id: elsarticle-template-num.tex 4 2009-10-24 08:22:58Z rishi $
  25. %%
  26. %%
  27. \documentclass[preprint,12pt,3p]{elsarticle}
  28.  
  29. \usepackage{algorithm,algorithmic}
  30. \usepackage{amsmath,amssymb,amsfonts}
  31. \usepackage{algorithmic}
  32. \usepackage{mathtools}
  33. \usepackage{graphicx}
  34. \usepackage{textcomp}
  35. \usepackage{xcolor}
  36. \usepackage{upgreek}
  37. \usepackage{subcaption}
  38. \usepackage{caption}
  39. \usepackage{float}
  40. \usepackage{dblfloatfix}
  41. \usepackage{eucal}
  42. \usepackage{amsthm}
  43. \newtheorem{theorem}{Theorem}
  44. \DeclareMathAlphabet{\mathpzc}{OT1}{pzc}{m}{it}
  45. \DeclareMathOperator*{\argmax}{argmax}
  46.  
  47.  
  48. %% Use the option review to obtain double line spacing
  49. %% \documentclass[preprint,review,12pt]{elsarticle}
  50.  
  51. %% Use the options 1p,twocolumn; 3p; 3p,twocolumn; 5p; or 5p,twocolumn
  52. %% for a journal layout:
  53. %% \documentclass[final,1p,times]{elsarticle}
  54. %% \documentclass[final,1p,times,twocolumn]{elsarticle}
  55. %% \documentclass[final,3p,times]{elsarticle}
  56. %% \documentclass[final,3p,times,twocolumn]{elsarticle}
  57. %% \documentclass[final,5p,times]{elsarticle}
  58. %% \documentclass[final,5p,times,twocolumn]{elsarticle}
  59.  
  60. %% if you use PostScript figures in your article
  61. %% use the graphics package for simple commands
  62. %% \usepackage{graphics}
  63. %% or use the graphicx package for more complicated commands
  64. %% \usepackage{graphicx}
  65. %% or use the epsfig package if you prefer to use the old commands
  66. %% \usepackage{epsfig}
  67.  
  68. %% The amssymb package provides various useful mathematical symbols
  69. \usepackage{amssymb}
  70. %% The amsthm package provides extended theorem environments
  71. %% \usepackage{amsthm}
  72.  
  73. %% The lineno packages adds line numbers. Start line numbering with
  74. %% \begin{linenumbers}, end it with \end{linenumbers}. Or switch it on
  75. %% for the whole article with \linenumbers after \end{frontmatter}.
  76. %% \usepackage{lineno}
  77.  
  78. %% natbib.sty is loaded by default. However, natbib options can be
  79. %% provided with \biboptions{...} command. Following options are
  80. %% valid:
  81.  
  82. %% round - round parentheses are used (default)
  83. %% square - square brackets are used [option]
  84. %% curly - curly braces are used {option}
  85. %% angle - angle brackets are used <option>
  86. %% semicolon - multiple citations separated by semi-colon
  87. %% colon - same as semicolon, an earlier confusion
  88. %% comma - separated by comma
  89. %% numbers- selects numerical citations
  90. %% super - numerical citations as superscripts
  91. %% sort - sorts multiple citations according to order in ref. list
  92. %% sort&compress - like sort, but also compresses numerical citations
  93. %% compress - compresses without sorting
  94. %%
  95. %% \biboptions{comma,round}
  96.  
  97. % \biboptions{}
  98.  
  99.  
  100. \journal{Elesvier Computer Communication}
  101.  
  102. \begin{document}
  103.  
  104. \begin{frontmatter}
  105.  
  106. \title{User Mobility and Quality-of-Experience Aware Placement of Virtual Network Functions in 5G}
  107.  
  108.  
  109.  
  110. \author{Palash Roy$^{a}$, Anika Tahsin$^{a}$, Sujan Sarker$^{b}$, Tamal Adhikary$^{a}$, Md. Abdur Razzaque$^{a,c}$, Mohammad Mehedi Hassan$^{d}$ }
  111. %, \corref{cor1}Md. Abdur Razzaque, Md. Mamun-or-Rashid}
  112. %\author[label1]{Sajeeb Saha, Fernaz Narin Nur}
  113. %\author{\corref{cor1}Md. Abdur Razzaque}
  114. %\author{Md. Mamun-or-Rashid}
  115. \address[label1]{Green Networking Research Group, Department of Computer Science and Engineering, University of Dhaka, Bangladesh}
  116. \address[label3]{Department of Robotics and Mechatronics Engineering, University of Dhaka, Bangladesh}
  117. \address[label3]{Department of Computer Science and Engineering, Green University of Bangladesh}
  118. \address[label3]{Information Systems Department, College of Computer and Information Sciences, King Saud University, Riyadh 11543, Saudi Arabia}
  119.  
  120.  
  121. %\cortext[cor1]{Corresponding author, Email: mmhassan@ksu.edu.sa}
  122.  
  123. \begin{abstract}
  124. Virtual Network Functions (VNFs) in cloud servers of Fifth Generation (5G) network systems are responsible for executing offloaded codes from mobile users. Placement of VNFs in the cloud is very complicated to get on-time execution service due to many reasons including users' mobility and resource heterogeneity, which often cause VNF relocations from one data center to another. Minimizing service delay (i.e., maximizing user Quality-of-Experience) for the user applications and the number of VNF relocations are the two main design goals of VNF placement problem; however, they do oppose each other. In this paper, we have formulated the above problem as a Multi-objective Integer Linear Programming (MILP), which is proven to be an NP-hard one. The proposed optimization framework trades-off between the number of VNF relocations and user Quality-of-Experience. We then develop an Artificial Intelligence based meta-heuristic Ant Colony Optimization (ACO) algorithm to achieve sub-optimal placement of VNFs within polynomial time. The performance analysis results, carried out in Cloudsim, depict that the proposed system outperforms the state-of-the-art works significantly in terms of user satisfaction and VNF relocation overhead.
  125. \end{abstract}
  126.  
  127. \begin{keyword}
  128. 5G, Virtual Network Function, Ant Colony Optimization, Quality-of-Experience, User Mobility
  129. \end{keyword}
  130.  
  131. \end{frontmatter}
  132.  
  133. %%
  134. %% Start line numbering here if you want
  135. %%
  136. % \linenumbers
  137.  
  138. %% main text
  139. \section{Introduction}
  140. The Internet has become an inextricable part of our day-to-day life in recent times. The number of devices connected to the Internet is getting increased rapidly \cite{ref11}. Almost all types of instruments from communication devices to home appliances like TV, washing machine, toaster, etc. have started to be connected to the Internet \cite{Starfish_Journal}\cite{sarker2019optimal}.
  141. The role of Fifth Generation (5G) cellular network is expected to be very promising for accommodating increasing reliability requirements on Internet-centric mobile applications \cite{reviwer2Pap1} \cite{reviwer2pap2} \cite{reviwer2pap4}.
  142. 5G heterogeneous network (HetNet) is anticipated to provide more lucrative features such as higher throughput, lower latency, higher mobility range, massive device connectivity, higher network capacity and energy efficiency. It provides up to 20 times accelerated downloading and uploading speeds than 4G, 10 times lesser round trip latency and bandwidth up to 1 Gbps compared to only 20 Mbps in 4G \cite{5Gfeatures}.
  143. %It provides 1ms round trip latency which is almost 10 times lesser than that of 4G .
  144. \par Software Defined Network (SDN) and Network Function Virtualization (NFV) are the two influential key technologies which contribute significantly for developing the architectural design of 5G heterogeneous network \cite{ref2}\cite{islam2018optimal}. Virtualization is a middle layer technology between hardware and software layers which creates virtual representation of something such as virtual machines, servers, memory, network functions, etc. The NFV offers the advantage of segregating the network functions from
  145. proprietary hardware appliances and executing these functions in software on standardized hardware instead. These decoupled network functions are referred to as Virtual Network Functions (VNFs) \cite{ref23}. %In SDN and NFV, control plane and data plane are decoupled from each other. Due to this feature and limited resources, limited computational power, limited battery life of our mobile devices, high computational demanding task are run on the cloud. So, if we run these applications in the cloud in the form of Virtual Network Functions (VNF), this save us huge amount of battery life of the mobile devices \cite{ref5}.
  146.  
  147.  
  148. \par The NFV offered by Cloud Computing has obtained much popularity as constantly growing number of enterprises and individuals are offloading their workloads to cloud service providers and getting served by them \cite{saha2017tradeoff}. This technology is also being taken into account by 5G mobile operators to deal with the increasing number of data traffics and data intensive applications \cite{ref21}. In Mobile Cloud Computing (MCC), because of mobile devices having low computational power and battery lifespan, most of the applications are executed on various VNFs operating in different high computational data centers (DCs) in the cloud \cite{ref22} \cite{reviwer2pap3}. Fig. \ref{figIntro} shows the basic concept of user services architecture in 5G. The user equipments (UEs) are connected to respective evolved Node-Bs (eNBs) of their service area in the network. The cloud domain comprises a number of data centers that serve the eNBs in executing their user applications. Users of an eNB are served by VNFs of exactly one data center. In Fig. \ref{figIntro}, for example, associated eNBs of the home and university is connected to data center 1 and data center 2, respectively. When any user moves from his/her home to university, the placement of the running VNFs of that user becomes a matter of concern.
  149.  
  150. \begin{figure}[!t]
  151. \centering
  152. \includegraphics[width=0.6\textwidth, trim={0cm 3cm 0cm 0cm},clip]{JournelGraph/IntroPic.pdf}
  153. \caption{User Services Architecture in 5G}\par
  154. \label{figIntro}
  155. \end{figure}
  156.  
  157. \par Resource management in cloud computing has been well studied in many research problems \cite{resource1} \cite{resource2}. However,
  158. because of user mobility, allocation of VNFs for running user applications in different data centers is immensely challenging and difficult task in 5G. Because, for optimal placement of VNFs, various parameters are needed to be considered such as total number of VNF relocation, communication delay as well as response time to get service, its cost, etc. If performance of one parameter is attempted to be improved, performances of some other parameters degrade as a consequence. For example, when users move between two eNBs that are taking services from different DCs, keeping the running VNFs of that user at the previous DC eliminates the need for relocations but requires increased response time to get the services. Therefore, an attempt to minimize the number of VNF relocation results in increased communication delay as well as response time and vice-versa. Because of user mobility, static allocation of the VNFs in the DCs will not meet the demand, degrading user Quality of Experience (QoE). The optimal placement of the running VNFs will change with the respective user movements. Therefore, the optimal allocation of resources in different data centers satisfying all the performance parameters becomes a major challenge.
  159. \par The problem of optimal allocation of the resources from the mobile devices to the DC has been well studied in many papers. However, these existing approaches in the literature encounter several limitations. In \cite{rel5}, the authors have studied the resource allocation problem in the case of static users but the approach cannot be feasibly used when there exists user mobility . For minimizing the load
  160. of the Virtual Machines (VMs), the authors in \cite{ref8} have placed the VNFs efficiently in the DCs but minimizing VNF relocations and service cost have not been considered. However, in A-SGWR \cite{rel4}, minimization of the number of VNF relocations have been taken into account but not the response time for getting the service. In S-PL \cite{rel4}, the authors focused on minimizing the total response time but the total number of relocations and its overhead have been ignored.
  161. \par
  162. %In this paper we propose an optimal placement algorithm that solves the problem of VNF relocation that arises due to user mobility.
  163. The VNF relocation is only necessary in cases when a user moves between two eNBs connected to different data centers. In such case, VNF can be relocated from previous DC to service DC minimizing the communication path between the serving DC and new eNB, which in turn minimize the response time. Alternatively, user can get service from the DC on which VNF was running via the current serving DC. However, this second way causes higher response time. Therefore, minimizing VNF relocations and maximizing QoE are two conflicting objectives. Artificial Intelligence (AI) is a branch of computer science which enables the development of computer programs which possess the ability to make decisions rationally and solve problem by learning from experiences and improving it gradually\cite{ml2}. Due to the success of AI in solving complex control and decision-making problems, it is anticipated to contribute significantly for developing various aspects of 5G network and solving complicated problems. In this paper, our aim is to allocate the VNFs in the DC for the mobile users maintaining a trade-off between VNFs relocation and response time. The main contributions in the paper are summarised as follows:
  164. \begin{itemize}
  165. \item We formulate the problem of allocating the VNFs associated with user mobility as a Multi-objective Integer Linear Programming (MILP) problem.
  166. \item We have brought trade off between minimizing the number of VNF relocations and minimizing the total response time (hereafter, we call our system TradeRC) to get the service ensuring user Quality of Service.
  167. \item Due to the NP-hardness of our proposed MILP system, we develop an Ant Colony Optimization (ACO) meta-heuristic based VNF placement algorithm. The operational principle of the proposed system is driven by learning from the past experiences.
  168. \item We simulate our proposed system TradeRC in CloudSim \cite{cloudsim} and compare it with other state-of-the-art works. The results state that the user QoE in TradeRC has been increased by about 25\% and relocation overhead decreased by about 15\% compared to other state-of-the-art works.
  169.  
  170. \end{itemize}
  171.  
  172. \par
  173. %In MCC, optimal allocation of VNFs has more importance for ensuring QoS because of user mobility. As users move continuously, their VNFs have to be considered for relocation. If users move from an eNB (evolved Node-B, that is mainly base station) to another eNB and these two are connected to the same DC, then we have no headache over this. But if the two eNBs are connected to different DCs, then we have to relocate the respective VNF in order to minimize the communication path length between new eNB and the serving DC. This will minimize the communication delay as well as response time. However, another way is, without relocating the VNF getting service from the DC where the VNF was previously running through a DC to DC communication as relocation incurs big amount of time and overhead. In this case, the disadvantage is that communication path length increases resulting in higher communication delay as well as response time. Therefore, minimizing VNF relocation and minimizing communication delay are two conflicting objectives. Optimal placement of VNFs associated with user mobility is the main focus of this paper bringing trade off between minimizing VNF relocation and minimizing communication delay ensuring QoS. \par
  174. The rest of the paper is organized as follows. Section \ref{sec two} presents some related research works. Sections \ref{sec three} and \ref{sec four} describe system model %A system architecture is provided that can implement the proposed algorithm.
  175. and problem formulation, solution details respectively. In Section \ref{antcolony}, we present ACO-based VNF allocation problem in the data center.
  176. %Section \ref{sec five} demonstrates the performance evaluation of our proposed algorithm and compares it with the state-of-the art works.
  177. Subsequently, section \ref{sec five} demonstrates the performance of the proposed optimization solution and comparison with other state-of-the-art works. Finally, section \ref{sec six} summarizes the paper and outlines of the future work plans.
  178.  
  179. %editing
  180. %\par The eNBs are connected to exactly one DC through serving gateways (S-GW) for getting service from VNFs running on that DC. Due to user mobility issue, the VNFs associated with the users also change their eNBs. If these eNBs are connected to the different DCs then the eNBs have to change or relocate their S-GW for reducing communication path distance between eNBs and their corresponding DCs they are connected to. Minimizing communication path delay between eNBs and their corresponding DCs as well as minimizing the number of VNF relocation are two conflicting objectives. Therefore, trading off between them while ensuring QoS has become a major research challenge.
  181. \section{Related Works}
  182. \label{sec two}
  183. VNF placement is a very emerging research problem in 5G heterogeneous network. The VNF placement problem can be modelled as a type of Virtual Machines (VMs) migration problem since VNFs are run on VM. A wide plethora of research works related to VM migration in distributed cloud or hybrid cloud have been addressed in \cite{rel1,rel2,rel3,relIntro1,relIntro2}.
  184. As NFV integrated with SDN is becoming an emerging technology for development of the 5G network architecture, placement of VNF has gained much attention of many researchers. \par
  185. Many state-of-the-art works have proposed solutions to this problem. To fulfill the Quality-of-Services (QoS) and to increase the Quality-of-Experience (QoE) of the users, heavy computation demanding applications need huge amount of communication and computational resources. For that reason, these applications require large amount of offloading delay to offload the task. The authors in \cite{rel5} have solved the problems for static users only. However, offloading the task in the data centers is very computationally expensive when the user is mobile. Three types of online task migration techniques are proposed in \cite{relTaskMig} including cloud-wide task migration, service-centric task migration and task-centric migration methods. Each migration decision is made after a time interval based on user mobility and task execution time. After this time interval, task is transferred from one DC to another. Subsequently, in order to minimize total resource cost, Zhang et al. \cite{relResource} have proposed a framework for dynamic service placement in multiple data centers. They have only considered total response time between a DC and user location. However, they didn't consider any maximum number of resource allocation under a DC. \par
  186. Several approaches are suitable for handling offloaded task in the DC for mobile users. The first one is to migrate the VNFs to the nearest DC so that users get services within a short amount of time. But the migration of VNFs requires huge amount of time. In \cite{rel6}, the authors have proposed an algorithm for efficiently planning of Serving Gateway (S-GW) relocation where they tried to minimize the UE hand-off between S-GW and minimizing the number of created virtual S-GW instances. The second approach is to get the services from other nearby DCs where the VNF is already running using the concept of cloud confederation via DC to DC communication \cite{cloudConfed}. The user doesn't know from which DC he/she is getting that service. \par
  187. The authors in \cite{ref8} have proposed an algorithm to find dynamic placement of VM in eNBs by efficiently considering the load of the VM due to users mobility. But they didn't consider minimizing the number of the VM relocations. Taleb et al. \cite{rel4} have proposed algorithms to place VNFs optimally of both Packet Data Network Gateway (PDN-GW) and S-GW on federated cloud data centers to create an efficient Virtual Network Infrastructure (VNI)considering user mobility. They have dealt with two conflicting objectives, namely minimizing the path distance between PDN-GW and UE and minimizing the S-GW relocation by providing individual solutions for achieving these two objectives separately. In Shortening Path Length (S-PL) system, they have minimized the path delay between UE and PDN-GW. However, they did not impose any limit on the number of S-GW relocations tolerated in the network. On the other hand, In avoiding S-GW relocation (A-SGWR) system, they have tried to minimize the number of S-GW relocations. However, they did not impose any limitations on the amount of allowable communication delay in this case. Moreover, they have considered infinite capacity of the data centers for placing the VNFs. In \cite{ref8,rel4}, the authors did not consider any service cost to take services from other data centers. \par
  188.  
  189. None of the existing works focus on the mobility aware efficient VNF allocation system considering both minimization of the number of relocations and response time (i.e., increasing QoE). Number of relocations increases as a consequence of concentrating only on minimizing response times. Again, taking service from the previous DC reduces the number of relocations which in turn increases response time. These observations have driven us to make a framework that trades-off between minimizing the number of VNF relocations and increasing the user Quality-of-Experience. .
  190. %In this work, we have provided efficient placement system of VNFs in the DCs.
  191. %Due to users mobility, those users changes their BS whose are connected to different DC we consider those VNFs.
  192. %Due to users mobility, we have considered only those VNFs whose users change their eNBs and go under service of another eNB that is connected to a different DC. We want to bring trade-off between minimizing number of VNF relocations and minimizing communication delay to get that service. We have also considered service cost to get services from other DCs. \par
  193.  
  194. \section{System Model and Assumptions}
  195. \label{sec three}
  196.  
  197. Fig. \ref{sysArchi} represents the system architecture of the network.
  198. The system architecture consists of two domains. One is the cloud domain and another one is the Radio Access Network (RAN) domain.
  199. \begin{figure}[!t]
  200. \centering
  201.  
  202. \includegraphics[width=0.7\textwidth, trim={0cm 0cm 0cm 0cm},clip]{JournelGraph/SystemArchitectureFinal.pdf}
  203. \caption{System Architecture of VNF services in 5G}\par
  204. \label{sysArchi}
  205. \end{figure}
  206. The could domain comprises a set of data centers (DCs), $D$. These data centers have strong wired connection among them and the DCs can take services from one another through exploiting cloud confederation \cite{cloudConfed}.
  207.  
  208.  
  209.  
  210.  
  211. \par
  212. \begin{table}[!t]
  213. \centering
  214. \caption{Notation Table}
  215. \label{notationTable}
  216. \begin{tabular}{|l|l|}
  217. \hline
  218. \multicolumn{1}{|c|}{\textbf{Notation}} & \multicolumn{1}{c|}{\textbf{Description}} \\ \hline
  219. $D$ & \begin{tabular}[c]{@{}l@{}}The set of all data centers in the network\end{tabular} \\
  220. $N$ & \begin{tabular}[c]{@{}l@{}}The set of all eNBs that are connected to the DC where\\ the system is running.\end{tabular} \\
  221. \begin{tabular}[c]{@{}l@{}}$V_{j}$\end{tabular} & \begin{tabular}[c]{@{}l@{}}The set of VNFs of eNB $j \in N$ that need to be considered\\ for relocation\end{tabular} \\
  222. \begin{tabular}[c]{@{}l@{}} $\delta_{worst}$\end{tabular} & \begin{tabular}[c]{@{}l@{}}Maximum communication delay tolerated by the network\end{tabular} \\
  223.  
  224. \begin{tabular}[c]{@{}l@{}} $t_{k}$\end{tabular} & \begin{tabular}[c]{@{}l@{}}The communication delay between DC $k \in D$ and the DC \\ where the system is running\end{tabular}
  225. \\
  226. \begin{tabular}[c]{@{}l@{}} $t_{j}$\end{tabular} & \begin{tabular}[c]{@{}l@{}}The communication delay between eNB $j \in N$ and the DC\\ where the system is running\end{tabular}
  227. \\
  228. \begin{tabular}[c]{@{}l@{}} $S_{f}$\end{tabular} & \begin{tabular}[c]{@{}l@{}}Size of Virtual Network Function VNF $f \in V$\end{tabular}
  229. \\
  230.  
  231. \begin{tabular}[c]{@{}l@{}}$\phi_{k}$\end{tabular} & \begin{tabular}[c]{@{}l@{}} Cost to relocate any VNF to DC $k \in D$\end{tabular}
  232. \\
  233. \begin{tabular}[c]{@{}l@{}} $\sigma_{k}$\end{tabular} & \begin{tabular}[c]{@{}l@{}} Cost of taking service from DC $k \in D$\end{tabular}
  234. \\
  235.  
  236. \begin{tabular}[c]{@{}l@{}} $\zeta_{k}$\end{tabular} & \begin{tabular}[c]{@{}l@{}} VNF holding capacity of DC $k \in D$\end{tabular}
  237. \\
  238.  
  239. \begin{tabular}[c]{@{}l@{}} $\varphi_{f}$\end{tabular} & \begin{tabular}[c]{@{}l@{}} Execution time of VNF
  240. $f \in V$\vspace{0.07cm}\end{tabular}
  241. \\
  242. \begin{tabular}[c]{@{}l@{}} $\gamma$\end{tabular} & \begin{tabular}[c]{@{}l@{}} Priority factor for VNF relocation\vspace{0.07cm}\end{tabular}
  243. \\
  244.  
  245. \begin{tabular}[c]{@{}l@{}} $\uptau_{f}$\end{tabular} & \begin{tabular}[c]{@{}l@{}} Transfer time of VNF $f \in V$\vspace{0.07cm}\end{tabular}
  246. \\
  247. \begin{tabular}[c]{@{}l@{}} $X_{k}$\end{tabular} & \begin{tabular}[c]{@{}l@{}} Number of VNFs currently executing in DC $k \in D$ \vspace{0.1cm}\end{tabular}
  248. \\
  249.  
  250. \begin{tabular}[c]{@{}l@{}} $Y_{k,j}^{f}$\end{tabular} & \begin{tabular}[c]{@{}l@{}} Summation of relocation time, communication time\\ and execution time because of allocating VNF $f \in V_{j}$\\ of eNB $j \in N$ to DC $k \in D$ \vspace{0.07cm}\end{tabular}
  251. \\
  252.  
  253. \begin{tabular}[c]{@{}l@{}} $\CMcal{T}_{o}$\end{tabular} & \begin{tabular}[c]{@{}l@{}} Initial pheromone value\vspace{0.07cm}\end{tabular}
  254.  
  255. \\
  256. \begin{tabular}[c]{@{}l@{}} $\CMcal{T}_{j,f}^{k}$\end{tabular} & \begin{tabular}[c]{@{}l@{}} Pheromone value for placing VNF $f \in V_{j}$ of eNB\\ $j \in N$ to DC $k \in D$\vspace{0.07cm}\end{tabular}
  257. \\
  258. \begin{tabular}[c]{@{}l@{}} $\CMcal{H}_{j,f}^{k}$\end{tabular} & \begin{tabular}[c]{@{}l@{}} Local heuristic value for placing VNF $f \in V_{j}$ of eNB\\ $j \in N$ to DC $k \in D$\vspace{0.07cm}\end{tabular}
  259.  
  260. \\
  261. \begin{tabular}[c]{@{}l@{}} $p_{j,f,k}^{z}$\end{tabular} & \begin{tabular}[c]{@{}l@{}} Probability of choosing DC $k \in D$ for placing VNF\\ $f \in V_{j}$ of eNB $j \in N$ by ant $z$\vspace{0.07cm}\end{tabular}
  262. \\
  263. \begin{tabular}[c]{@{}l@{}} $\rho_{l}$\end{tabular} & \begin{tabular}[c]{@{}l@{}} Weight parameter for local pheromone update \vspace{0.07cm}\end{tabular}
  264. \\
  265. \begin{tabular}[c]{@{}l@{}} $\rho_{g}$\end{tabular} & \begin{tabular}[c]{@{}l@{}} Weight parameter for global pheromone update \vspace{0.07cm}\end{tabular}
  266. \\
  267. \begin{tabular}[c]{@{}l@{}} $\Delta \CMcal{T}_{j,f}^{k}$\end{tabular} & \begin{tabular}[c]{@{}l@{}} Global pheromone value for placing VNF $f \in V_{j}$ of eNB\\ $j \in N$ to DC $k \in D$ in global solution.\vspace{0.07cm}\end{tabular}
  268.  
  269. \\
  270. \begin{tabular}[c]{@{}l@{}} $\alpha$\end{tabular} & \begin{tabular}[c]{@{}l@{}} Weight parameter for pheromone value \vspace{0.07cm}\end{tabular}
  271. \\
  272. \begin{tabular}[c]{@{}l@{}} $\beta$\end{tabular} & \begin{tabular}[c]{@{}l@{}} Weight parameter for local heuristic value \vspace{0.07cm}\end{tabular}
  273. \\
  274. \hline
  275. \end{tabular}
  276. \end{table}
  277. The RAN domain consists of a set of access points, i.e. base stations called evolved Node-B (eNB). Several users can be connected to an eNB through radio signal. A group of eNBs are connected to a base station controller. An eNB is connected to exactly one data center through the Serving Gateway (S-GW) and Packet Data Network Gateway (PDN-GW) of that DC \cite{ref15}. Each DC has multiple number of eNBs connected to them. In some areas (busy areas), DCs serve huge number of eNBs and some areas (lightly loaded) DCs serve a small number of eNBs connected to them \cite{ref14}.
  278.  
  279.  
  280. Different Virtual Network Functions (VNFs) are run on different data centers. Each DC has a fixed capacity of holding application/service oriented VNFs. %If hand off occurs between two eNBs i.e. if any user leaves the service area of an eNB and goes to service area of another eNB and they are connected to the same DC then no VNF relocation is needed at all. If they are connected to the different DC, then the case of VNF relocation is considered.
  281. An eNB gets service from the the data center it is connected to. $N$ is the set of all eNBs that are connected to the DC where the system is running. The data center itself can run the respective VNF of a user under that eNB or it can manage the service from any neighbor data center. The second case incurs extra service cost. $V_{j}$ is the set of all VNFs of eNB $j \in N$ that are needed to be considered for relocation and these VNF requests have been occurred for hand off between eNB $ j \in N$ and any other eNB which is connected to a different DC. The major notations and their descriptions used to design TradeRC are listed in Table. \ref{notationTable}.
  282.  
  283.  
  284.  
  285.  
  286. %In the proposed system model, There has two types domains. One is the cloud domain. This domain consists of multiple DCs. This DCs are distributed over in several geographic locations. Another Domain is Cloud Radio Access Network (C-RAN). This domain consists of multiple number of access points. In 5G network, this access points are called evolved Node-B (eNB). Each DC has multiple number of eNB and one or multiple Serving Gateway (S-GW) connected to them. These eNBs communicate with the DCs through S-GW. In some areas (busy areas), DCs serve huge number of eNBs and some areas (lightly loaded) DCs serve a small number of eNBs. Each DC has fixed capacity of holding application/service oriented Virtual Network Functions (VNFs).
  287. %VMs can be created on demand. If any VM is unused for a long time, there will also be a process to destroy that VM.
  288. %\par There is a base station controller that controls some number of eNBs. This base station controller is connected to Mobile switching Controller (MSC).There are a number of gateways between eNB and DC. One eNB can communicate with the DCs using these gateways. There are multiple paths between one eNB and one DC. So, one eNB can communicate with the DCs using multiple paths.
  289.  
  290.  
  291.  
  292. \section{Design of TradeRC}
  293. \label{sec four}
  294. In this section, we present a optimization framework of our proposed TradeRC system and develop a meta-heuristic AI based Ant Colony Optimization (ACO) algorithm. The main focus of TradeRC system is to provide an optimal placement of the VNFs that are needed to be considered for relocation because of user mobility. The system will run in each DC to manage the VNF requests of the eNBs under it that have been come from other eNBs connected to a different DC because of hand off due to user mobility. Minimizing the number of VNF relocations and maximizing the QoE are the two main design goals for the VNF placement problem. As these two are conflicting objectives, we have brought a trade-off between them using priority factor for both. The priority factor can be changed according to the requirement of the network size and requirement.
  295.  
  296.  
  297. %We considered that the network consists of a set of data centers, $D$. $N$ is the set of all $eNBs$ that are connected to the DC where the system is running. $V_{j}$ is the set of all VNFs of $eNB_{j}$ that are needed to be considered for relocation and these VNF requests have been occurred for hand off between $eNB_{j}$ and any other eNB which is connected to a different DC.
  298.  
  299.  
  300.  
  301. \subsection{Optimal Placement of VNFs}
  302. For placing VNF $f \in V_{j}$ of eNB $j \in N$ to DC $k \in D$, the relocation time, denoted by $R_{k,j}^{f}$, is calculated as follows:
  303. %The relocation time $R_{k,j}^{f}$ of a VNF $j \in V_j$ of a user connected to eNB $j \in N$ of DC $k \in D$, from its previous DC to current one is calculated as:
  304. \begin{equation}
  305. R_{k,j}^{f} = \{(1-p^{f}_{k}) \times b_{k,j}^{f}\} \times H^{f}_{k},
  306. \end{equation}
  307. where, the binary variable $p^{f}_{k}$ contains 1 if the VNF was previously running on data center $k \in D$, otherwise 0. Similarly, the binary variable $b_{k,j}^{f}$ means whether VNF $f \in V_{j}$ of eNB $j \in N$ is to be placed to data center $k \in D$ or not. Its value is 1 if the VNF is placed to DC $k \in D$, otherwise 0. So, if the value of $(1-p^{f}_{k})$ is 1, then we have an option to relocate the respective VNF to DC $k \in D$, otherwise not. $H^{f}_{k}$ represents the relocation cost for placing VNF $f \in V_{j}$ of eNB $j \in N$ to DC $k \in D$. It is calculated as follows,
  308. \begin{equation}
  309. H^{f}_{k} = (1-n^{f}_{k}) \times \uptau_{f}, \end{equation}
  310. where, $n^{f}_{k}$ is a binary variable. If the expected VNF $f \in V_{j}$ is running on DC $k \in D$, then it is 1 otherwise 0. We can get service for VNF $f \in V_{j}$ from that DC without creating any instance for that VNF. On the other hand, if $n^{f}_{k}$ is 0, then there is no running VNF $f \in V_{j}$ on DC $k \in D$. So, we need to transfer that VNF from the previous DC. Therefore, if the value of $(1-n^{f}_{k})$ is 1, then we transfer the VNF from the previous DC otherwise not. If this value is 1, then relocation cost is equal to the transfer time of that VNF. Transfer time of the VNF is calculated as,
  311. \begin{equation}
  312. \uptau_{f} = \frac{S_{f}}{r},
  313. \end{equation}
  314. where, $S_f$ is the size of the VNF and $r$ is achievable data rate to transfer a VNF from one DC to another DC. Communication delay to get service for a VNF is calculated as,
  315. \begin{equation}
  316. C_{k,j}^{f} = b_{k,j}^{f} \times (t_{j}+ t_{k}),
  317. \end{equation}
  318. where, total communication delay is equal to summation of communication delay between $eNB_{j}$ and the DC where the solution is running denoted by $t_{j}$ and communication delay between DC $k \in D$ where we are locating the VNF $f \in V$ and the DC where the solution is running. If we take service from the own DC where the solution is running, then we need to calculate only $t_{j}$. But if we take service from another DC $k \in D$ then we also need to add $t_{k}$ with it. Thus the objective function of our work is formulated as,
  319. \\\\
  320. $Minimize:$
  321. \begin{equation}
  322. \label{objectiveFunc}
  323. W=\sum_{j\in N} \sum_{f\in V_{j}} \sum_{k\in D} \{ \gamma \times R_{k,j}^{f} \times \phi_{k} +(1 -\gamma) \times C_{k,j}^{f} \times \sigma_{k}\}.
  324. \end{equation}
  325. Here, the objective function is formulated as a Multi-objective Integer Linear Programming (MILP) to be solved by Data center (DC). Minimizing total VNF relocation and minimizing total path cost in terms of response time are two conflicting objectives. The objective function is bringing trade-off between relocation and communication (hereafter, we call our proposed system TradeRC) using weight factor $\gamma$. There is some extra cost to get services from the global DC than local DC. That is, if any eNB takes services from the distant DCs other than the DC to which they are directly connected, the sevice cost increases. There is also some cost to relocate VNF to any DC $k \in D$ denoted by $\phi_{k}$ . %from global DC to local DC. %Taking service from global DC higher cost than relocation cost.
  326. Minimizing the overall network cost is our main objective. There are some constraints that need to be satisfied. \\\\
  327. Subject to:
  328.  
  329.  
  330.  
  331. \begin{equation}
  332. \label{con1}
  333. b_{k,j}^{f} = \{0,1\},\hspace{0.2cm} \forall j\in N, \hspace{0.2cm} \forall f\in V_{j}, \hspace{0.2cm} \forall k\in D
  334. \end{equation}
  335.  
  336.  
  337. \begin{equation}
  338. \label{constraint2}
  339. \sum_{k\in D}b_{k,j}^{f} = 1, \hspace{0.2cm} \forall j\in N,\hspace{0.2cm} \forall f\in V_{j}
  340. \end{equation}
  341.  
  342. \begin{equation}
  343. \label{con4}
  344. \sum_{f\in V_{j}}\sum_{k\in D}b_{k,j}^{f} = |V_{j}|,\hspace{0.2cm} \forall j\in N
  345. \end{equation}
  346. \begin{equation}
  347. \label{con5}
  348. \sum_{k\in D}( R_{k,j}^{f} + C_{k,j}^{f} + \varphi_{f}) \leq \delta_{worst}, \hspace{0.2cm}\forall j\in N, \hspace{0.2cm}\forall f\in V_{j}
  349. \end{equation}
  350. \begin{equation}
  351. \label{constraint6}
  352. \sum_{j\in N}\sum_{f\in V_{j}} b_{k,j}^{f} \leq \zeta_{k}, \hspace{0.2cm}\forall k\in D
  353. \end{equation}
  354.  
  355. \par
  356.  
  357. Constraint in Eq. \ref{con1} is a binary constraint. If VNF $f \in V_{j}$ for eNB $j \in N$ is located in DC $k \in D$, then it is 1; otherwise 0.
  358. Constraint in Eq. \ref{constraint2} is an atomicity constraint. It ensures that every VNF $f \in V_{j}$ for every eNB $j \in N$ exists exactly in only one data center $k \in D$.
  359. Constraint in Eq. \ref{con4} is the allocation constraint. It ensures that, all VNF $f \in V_{j}$ that comes from an eNB $j \in N$ should be allocated to some data centers. No VNF can be stayed unallocated to any DC.
  360. The QoS constraint in Eq. \ref{con5} ensures that, summation of communication delay, execution time and relocation time must be less than the maximum allowable application deadline. The allowable delay can vary from application to application. Execution time is calculated as;
  361. \begin{equation}
  362. \varphi_{f} = \frac{I_{f}}{MIPS_{k}}, \forall k \in D
  363. \end{equation} \par
  364.  
  365. The capacity constraint in Eq. \ref{constraint6} ensures that, total number of the VNFs of a DC can't be more than the maximum capacity of the DC. \par
  366. \begin{theorem}
  367. VNF placement problem in TradeRC, formulated in Eq. \ref{objectiveFunc}, is NP-hard.
  368. \end{theorem}
  369. \begin{proof}
  370. The above optimization formulation is a Multi-objective Linear Optimization having two conflicting objectives, i.e, minimizing number of VNF relocations and resonse time (i.e., maximizing QoE). Such problem is NP-hard and can not provide solutions in polynomial time for increasing number of VNFs and eNBs.
  371. The optimization problem can be reduced to a Generalized Assignment Problem (GAP) which is NP-Complete \cite{np}. The Generalized Assignment Problem has the following components,
  372. \begin{enumerate}
  373. \item A set $ T =\{ 1,....n\}$ of tasks.
  374. \item A set $ M = \{ 1,....m\}$ of agents.
  375. \item A cost function, $C$, giving the cost of assigning a task to an agent.
  376. \item A capacity function, $A$, giving the capacity used when a task is assigned to an agent.
  377. \item A available capacity function, $B$, giving the available capacity of an agent.
  378. \end{enumerate}
  379. \par The problem tries to minimize overall cost of performing the tasks which is given as,\\\\\\
  380. $Minimize:$
  381.  
  382. \begin{equation}
  383. \label{e1}
  384. \sum_{i \in T}\sum_{j \in M} C_{ij}X_{ij}
  385. \end{equation}
  386. Subject to:\\
  387. \begin{equation}
  388. \label{e2}
  389. \sum_{j \in N} A_{ij}X_{ij}< B_{i},\hspace{0.5cm} \forall i \in M
  390. \end{equation}
  391. \begin{equation}
  392. \label{e2}
  393. \sum_{i \in M} X_{ij}=1,\hspace{0.5cm} \forall j \in T
  394. \end{equation}
  395. \begin{equation}
  396. \label{e2}
  397. X_{ij} \in \{0,1\},\hspace{0.5cm} \forall i \in M, \hspace{0.9mm}\forall j \in T
  398. \end{equation}
  399. \par The optimal VNF allocation problem can be reduced to Generalized Assignment Problem (GAP) by leveraging constraints and considering the problem for a single eNB. Let, $Z_{kf} = H_{k}^{f}(1-p_{k}^{f})\times \gamma \times \phi_{k}$. Considering only relocation part, the optimization problem takes the form,\\\\
  400. $Minimize:$
  401.  
  402.  
  403.  
  404. \begin{equation}
  405. \label{e1}
  406. \sum_{f \in V_{j}}\sum_{k \in D} Z_{kf}b_{k}^{f}
  407. \end{equation}
  408. Subject to:\\
  409. \begin{equation}
  410. \label{con6}
  411. \sum_{f\in V_{j}} b_{k}^{f} \leq \zeta_{k}, \hspace{0.2cm}\forall k\in D
  412. \end{equation}
  413. \begin{equation}
  414. \label{con2}
  415. \sum_{k\in D}b_{k}^{f} = 1, \hspace{0.2cm} \hspace{0.2cm} \forall f\in V_{j}
  416. \end{equation}
  417. \begin{equation}
  418. \label{e2}
  419. b_{k}^{f} \in \{0,1\},\hspace{0.5cm} \forall f \in V_{j}, \hspace{0.9mm}\forall k \in D
  420. \end{equation}
  421. \par As we can reduce the problem into GAP, it can be safely ensured that the proposed formulation is at least as hard as GAP and no optimal solution is found in polynomial time for large networks.
  422.  
  423. \end{proof}
  424.  
  425. \begin{figure}[!ht]
  426. \centering
  427. \captionsetup{justification=centering}
  428. \includegraphics[width=0.6\textwidth, trim={0.3cm 0cm 1.3cm 1.3cm},clip]{JournelGraph/NPHard.eps}
  429. \caption{Impacts of number of VNFs movement per eNB on running time}\par
  430. \label{figNp}
  431. \end{figure}
  432. In support of evidence, we have carried out a simulation experiment. Fig. \ref{figNp} shows the impact of the number of VNFs movement per eNB due to user mobility on running time. To find the boundary values of the number of the eNBs per DC and number of VNFs movement per eNB in the environment, we simulate the objective function in Eq. \ref{objectiveFunc} in the NEOS optimization server \cite{WinNT}. The result shows that, 10ms to 100ms are required for 10 to 15 eNBs with increased number of VNFs movement. As the number of eNBs and VNFs movement increases, algorithm running time increases exponentially. For 30 eNBs under a DC and 300 VNFs movement from an eNB, running time is on an average 4000 ms to 5000 ms which is not practical in real life to get a service.
  433.  
  434. %In literature this problem is known as a 0-1 knapsack problem, where DCs are represented as knapsack and VNFs are known as items. We need to fill the knapsack with the items such that total weight of each item must be less than or equal to a given limit. In our problem, we also keep the VNFs in the DCs in such a way that the total number of VNFs must be less than the capacity of the DCs. Thus it becomes a NP-hard problem.
  435. %\subsection{Algorithm Triggering Criterion}
  436.  
  437. \subsection{Meta-Heuristic VNFs Placement}
  438. \label{antcolony}
  439. Due to the NP-hardness of the above optimization problem, we have provided meta-heuristic Ant Colony Optimization (ACO) based placement algorithm for VNFs to solve this problem. The reason behind choosing meta-heuristic algorithm is that it refers to the master strategy helping us to modify other heuristics to generate solutions. Heuristics are problem dependent and meta-heuristics are problem independent methods. Meta-heuristic does not guarantee to find an optimal solution. However, it can efficiently search the space to find a sub-optimal solution that is close to the optimal one and can solve a problem within polynomial time.
  440. \par
  441. The ACO problem is an Artificial Intelligence (AI) based meta-heuristic algorithm that takes inspiration from the behaviour of real ant colonies. In this problem, a set of agents (virtual ants) are created. These ants have small memory. Each ant tries to build its solution using heuristic value. After that, these ants improve their solutions by exchanging information via pheromones. Each ant updates its local pheromone trail after building local optimal solution. Finally, all ants combine their local optimal solution to build a global optimal solution in distributed manner.
  442. \par
  443. The proposed Ant Colony Optimization Algorithm for VNF placement has been presented in Algorithm \ref{algo1}. At first, various system parameters and ants set have been initialized in lines 1 and 2. Then we generate initial solution set using algorithm \ref{algoFF} in line 3 and calculate the initial pheromone value, $\CMcal{ T}_{o}$, in line 4. Then we produce different solution sets of placing VNFs of all eNBs to suitable DCs for each ant based on pheromone values and local heuristic values in lines 7 to 12. Each time we get a local solution for an ant, we reduce the pheromone values for each element of that solution by local pheromone update in lines 13 to 15, so that variety of solution is generated by the ants. After this is done for all the ants of the ant set, we take the best solution set among the local ones as global solution and update the global pheromone value in line 17.
  444. \begin{algorithm}[!t]
  445.  
  446. \caption{Ant Colony Based VNF Allocation at each data center $k \in D$}
  447. \label{algo1}
  448.  
  449. \begin{algorithmic}[1]
  450.  
  451. \renewcommand{\algorithmicrequire}{\textbf{Input:}}
  452. \renewcommand{\algorithmicensure}{\textbf{Output:}}
  453. \REQUIRE eNB set $N$, VNF set $V_{j}$ for each eNB $j \in N $ and data center set $D$.
  454. \ENSURE VNF-DC pair for each eNB
  455. \STATE Initialize system parameters $\alpha$, $\beta$, $\rho_{l}$, $\rho_{g}$
  456. \STATE Initialize ants set $A$
  457. \STATE Generate initial solution using Algorithm \ref{algoFF}
  458. \STATE Calculate initial pheromone value $\CMcal{T}_{o}$ using Eq. \ref{InitPheromone}
  459. \STATE Set maximum iteration MAX-IT
  460. \WHILE{($iteration$ $\leq$ MAX-IT)}
  461. \FORALL {ant $a \in A$}
  462. \FORALL{eNB $j \in N$}
  463. \FORALL{VNF $f \in V_j$}
  464. \STATE Assign VNF $f \in V_j$ for eNB $j \in N$ to DC $k \in D$ using Eq. \ref{antEqu}
  465. \ENDFOR
  466. \ENDFOR
  467. \FORALL{VNF $f \in V_j$}
  468. \STATE Update the local pheromone value using Eq. \ref{localPh}
  469. \ENDFOR
  470. \ENDFOR
  471. \STATE Update the global pheromone value using Eq. \ref{globalPh}
  472. \STATE $iteration = iteration + 1$
  473. \ENDWHILE
  474.  
  475. \RETURN VNF-DC pairs for each eNB
  476. \end{algorithmic}
  477. \end{algorithm}
  478. \subsubsection{Initial Pheromone Calculation}
  479. When an ant moves from one place to another, it leaves a chemical, pheromone. This pheromone is used to mark these paths and helps the following ants to find their team members. In VNF allocation problem, pheromone represents the possibility of keeping a VNF in a DC. Each ant starts with an initial pheromone value for each VNF to DC pair.
  480. The initial solution is generated using First-Fit VNF (FF-VNF) allocation algorithm approach, which is listed in Algorithm \ref{algoFF}. In this algorithm, we form an initial solution set, $\CMcal{S}_{o}$, by placing the VNFs of all the eNBs to the DCs based on capacity of the DCs and satisfying application deadline on a First-Fit basis from line 2 to 12. Finally, this algorithm returns the initial soution set, $\CMcal{S}_{o}$.
  481. \begin{algorithm}
  482. \caption{First-Fit VNF Allocation at each data center $k \in D$}
  483. \label{algoFF}
  484. \begin{algorithmic}[1]
  485. \renewcommand{\algorithmicrequire}{\textbf{Input:}}
  486. \renewcommand{\algorithmicensure}{\textbf{Output:}}
  487. \REQUIRE eNB set N, VNF set $V_{j}$ for each eNB $j \in N$ and data center set D
  488. \ENSURE Set of VNF-DC pair for each eNB in the initial solution $\CMcal{S}_{0}$
  489. \STATE $\CMcal{S}_{0} \gets \emptyset$
  490. \FORALL {eNB $j \in N$}
  491. \FORALL{VNF $f \in V_j$}
  492. \FORALL{DC $k \in D$}
  493. \IF {($X_{k} < \zeta_{k}$ \&\& $Y_{k,j}^{f} \leq \delta_{worst}$)}
  494. \STATE$\CMcal{S}_{0} \gets \CMcal{S}_{0} \bigcup \{(j,f,k)\} $
  495. \STATE$X_{k}= X_{k}+1$
  496. \STATE Break
  497. \ENDIF
  498. \ENDFOR
  499. \ENDFOR
  500. \ENDFOR
  501. \RETURN $\CMcal{S}_{0}$
  502. \end{algorithmic}
  503. \end{algorithm}
  504.  
  505. \par
  506. The initial pheromone value is calculated by summing the total relocation time and total communication delay of the system and taking the inverse of that value. Initial pheromone value is calculated as follows,
  507. \begin{equation}
  508. \label{InitPheromone}
  509. \CMcal{T}_{o} = \sum_{j\in N} \sum_{f\in V_{j}} \sum_{k\in D} {\frac{1}{R_{k,j}^{f}+C_{k,j}^{f}}} \times \CMcal{Y}_{j,f}^{k}
  510. \end{equation}
  511. where $\CMcal{Y}_{j,f}^{k}$ is a binary variable. It is defined as,
  512. \begin{equation}
  513. \CMcal{Y}_{j,f}^{k}= \begin{cases}
  514. 1, &\text{if $(j,f,k) \in \CMcal{S}_0$}\\
  515. 0, &\text{otherwise}
  516. \end{cases}
  517. \end{equation}
  518. where, $\CMcal{S}_0$ is the initial solution set. If VNF $f \in V_{j}$ of eNB $j \in N$ is placed to DC $k \in D$ in $\CMcal{S}_0$, then the value is 1, otherwise 0.
  519. \par The rationale behind the choice is that, we want to provide more pheromone on the path where relocation and communication occur in the initial solution. The main reason to do inverse operation is that, the lower the value of the summation of relocation time and communication delay, we give more pheromone on that path and vice-versa.
  520.  
  521. \subsubsection{Determining Heuristic Value}
  522. For building solution in Ant Colony Optimization, each ant takes the decision of placing a VNF to a data center combinedly based on pheromone values and local heuristic value. This heuristic value is influential as it contributes to the selection of data center to place a VNF for constructing solution. As our goal is to minimize the total number of VNF relocation and minimize communication delay as well as response time, i.e, bringing trade off between the two conflicting objectives, we have determined our heuristic value in such a way that these two objectives are satisfied. Our local heuristic is defined as,
  523. \begin{equation}
  524. \label{heu}
  525. \CMcal{H}_{j,f}^{k} = \frac{1}{\gamma \times R_{k,j}^{f}\times \phi_{k}+ (1-\gamma)\times C_{k,j}^{f} \times \sigma_{k}}
  526. \end{equation}
  527. The heuristic value for placing VNF $f \in V_{j}$ of eNB $j \in N$ to data center
  528. $k \in D $ is thus determined by Eq. \ref{heu}. As mentioned earlier, $\gamma$ is the priority factor given to VNF relocation and $(1- \gamma)$ to communication time. From Eq. \ref{heu}, it can be ensured that the lesser the weighted sum of communication and relocation cost for placing a VNF to a data center, the higher will be the value of heuristic. And the favorability of choosing that data center to place a VNF by an ant will be increased.
  529. \subsubsection{Selection of Data Center}
  530. Each ant $a \in A$ selects the best suitable DC $k \in D_{c}$ to place VNF $f \in V_{j}$ of eNB $j \in N$ using the following rule, which is called pseudo-random-proportional action rule. Here, $D_{c}$ is the set of candidate DCs which have capacity available to place that VNF and $D_{c}\displaystyle \subseteq D $. The pseudo-random-proportional action rule can be defined as,
  531. \begin{equation}
  532. \label{antEqu}
  533. s =
  534. \begin{dcases}
  535. \argmax_{k \in D_{c}} \left(\left[ \CMcal{T}_{j,f}^{k}\right]^{\alpha} \times \left[ \CMcal{H}_{j,f}^{k}\right]^{\beta}\right), \hspace{0.1cm}$if q \leq q_{0}$ (exploitation)\\
  536. S, \hspace{3.8cm} ${otherwise (exploration)}$ \\
  537. \end{dcases}
  538. \end{equation}
  539. where. $q_{0}$ is a system parameter on the range [0,1] and $q$ is a random variable that is uniformly distributed in [0,1]. $\CMcal{T}_{j,f}^{k}$ is the pheromone value for allocating VNF $f \in V_{j}$ for eNB $j \in N$ to DC $k \in D_{c}$. According to the rule, an ant chooses the most suitable DC $k \in D_{c}$ to place a VNF $f \in V_{j}$ of eNB $j \in N$ in terms of heuristic value and pheromone trail value with $q$ probability. Here, $\alpha$ and $\beta$ denote the relative importance of pheromone value and heuristic value, respectively. Therefore, when $q \leq q_{0}$, an ant selects a DC $k \in D_{c}$ for VNF $f \in V_{j}$, where the quantity of $\left[ \CMcal{T}_{j,f}^{k}\right]^{\alpha} \times \left[ \CMcal{H}_{j,f}^{k}\right]^{\beta}$ gives the highest value among all possible data centers. On the other hand, in case of exploration of an ant $z$ chooses DC $k \in D_{c}$ to place a VNF $f \in V_{j}$ of eNB $j \in N$ with the following probability \cite{ant}.
  540.  
  541. \begin{equation}
  542. \label{prob}
  543. p_{j,f,k}^{z} =
  544. \begin{dcases}
  545. \frac{ \left(\left[ \CMcal{T}_{j,f}^{k}\right]^{\alpha} \times \left[ \CMcal{H}_{j,f}^{k}\right]^{\beta}\right)}{\sum_{d \in D_{c}}\left(\left[ \CMcal{T}_{j,f}^{d}\right]^{\alpha} \times \left[ \CMcal{H}_{j,f}^{d}\right]^{\beta}\right)}, \hspace{0.4cm} ${if k \in D_{c} }$\\
  546. 0, \hspace{4.2cm} ${otherwise}$ \\
  547. \end{dcases}
  548. \end{equation}
  549. \par This probability indicates that the DC $k \in D_{c}$ that gives us highest probability among all candidate DC $d \in D_{c}$, we place the VNF $f \in V_{j}$ in that DC.
  550. \subsubsection{Pheromone Update}
  551. The process of updating pheromone values locally and globally are presented below:
  552.  
  553. \paragraph{Local Update}
  554. When an ant places a VNF in DC $k \in D$, it instantly updates the pheromone trail. Local pheromone value is updated with respect to initial pheromone value. It is updated by each ant as follows,
  555. \begin{equation}
  556. \label{localPh}
  557. \CMcal{T}_{j,f}^{k}(t+1) = \rho_l \times \CMcal{T}_{0} + (1- \rho_l) \times \CMcal{T}_{j,f}^{k}(t),
  558. \end{equation}
  559. where, $\rho_l$ is a system parameter indicating the relative importance of historical pheromone value and current pheromone value. By local pheromone update, every time an ant allocates a VNF in a specific DC, its pheromone trail is decreased. As a result it becomes less desirable for other ants of the colony. It encourages exploration and helps to increase variety of solutions constructed by the colony.
  560. \paragraph{Global Update}
  561. Global pheromone value is updated when all ants construct their local optimal solutions and then they update the global one. The global optima is formed by selecting the best one among the local solutions produced by all the ants. Let, the global solution set is $\CMcal{G}$. Global pheromone value is updated as the following equation,
  562. \begin{equation}
  563. \label{globalPh}
  564. \CMcal{T}_{j,f}^{k}(t+1) = \rho_g \times \Delta \CMcal{T}_{j,f}^{k}
  565. + (1- \rho_g) \times \CMcal{T}_{j,f}^{k}(t),
  566. \end{equation}
  567. where, $\rho_g$ is a system parameter which indicates the relative importance of $\Delta \CMcal{T}_{j,f}^{k}$ and $\CMcal{T}_{j,f}^{k}(t)$ in Eq. \ref{globalPh}. $\Delta \CMcal{T}_{j,f}^{k}$ is the global pheromone value for updated global solution $\CMcal{G}$. The value of $\Delta \CMcal{T}_{j,f}^{k}$ is determined by,
  568.  
  569.  
  570. \begin{equation}
  571. \Delta \CMcal{T}_{j,f}^{k}= \begin{cases}
  572. \CMcal{T}_{j,f}^{k}, &\text{if $(j,f,k) \in \CMcal{G} $}\\
  573. 0, &\text{otherwise}
  574. \end{cases}
  575. \end{equation}
  576.  
  577. If VNF $f \in V_{j}$ of eNB $j \in N$ is placed to DC $k \in D$ in global solution $\CMcal{G}$, then the value of $\Delta \CMcal{T}_{j,f}^{k}$ will be $\CMcal{T}_{j,f}^{k}$, otherwise 0.
  578. \par In brief, ACO meta-heuristic algorithm optimally selects a DC for a VNF from the past learning experience of the ants using pheromone value. After completing one iteration, all ants update their pheromone value. In the next iteration, they use their historical information. After successful completion of the algorithm, all of the VNFs places in the data centers optimally.
  579.  
  580. \subsection{Determination of Weight Parameter}
  581. In this subsection, we discuss on the chosen values of the weight parameters- $\gamma$, $\alpha$, $\beta$, $\rho_l$, $\rho_g$ and the number of ants.
  582. This research is a first step insight on trading-off between VNF relocation overhead and user QoE. Formulating a mathematical model for weight parameter $\gamma$ in real-time might help us to increase the performance of the system. However, it requires extensive analysis on the depending parameters including network size, the service arrival rate, time-deadline of applications, etc., which demands a separate research work.
  583. \par
  584. Similarly for determining the values of $\alpha$, $\beta$, $\rho_l$, $\rho_g$ and the number of ants, we depend on the numerous simulation experimental results and find that the following values give us better results for the given network. We set $\alpha$ = 5, $\beta$ = 1, $\rho_l$ = 0.3, $\rho_g$ = 0.4, $\gamma$ = 0.7 and number of ants = 20 for all experiments. \\
  585.  
  586.  
  587. % \par The complexity of Algorithm \ref{algoFF} is analyzed as follows. In Lines 2-11, there are 3 loops. Line-2 is enclosed in a loop that iterates at most $|N|$ times. Line 3 and Line 4 are also enclosed in a loop that iterate at most $|V_{j}|$ times and $|D|$ times respectively. Line 6 is a Union operation. It takes a constant time. So the total run time complexity of running the Algorithm \ref{algoFF} is required $O(|N| \times |V_{j}| \times |D|)$.
  588.  
  589. %\par
  590. %The complexity of algorithm \ref{algo1} is analyzed further. In line 6, there is an outer loop that iterates MAX-IT times. As MAX-IT is a constant number, it takes a constant time no matter how large the amount of data in the set. So, the complexity of this single loop is considered $O(1)$. Inside this loop, we have a second loop in line 7 that iterates number of ants times. Again number of ants is constant. So, the complexity of this single loop is also $O(1)$. Further, inside this loop, we have a third loop in line 8 that iterates $|N|$ times. Again, inside this third loop, we have a fourth loop in line 9 that iterates $|V_{j}|$ times. Inside this fourth loop, we have to use equation \ref{antEqu}. In this equation, there is a loop running at most $|D|$ times. There is another loop inside the second loop in line 13 which iterates $|V_{j}|$ times. Finally, it can be observed that, the total complexity of algorithm \ref{algo1} is also $O(|N| \times |V_{j}| \times |D|) $.
  591.  
  592.  
  593. \section{Performance Evaluation}
  594. \label{sec five}
  595.  
  596. In this section, we implement the proposed TradeRC system and compare its performance with the state-of-the-art works: A-SGWR\cite{rel4} and S-PL\cite{rel4} systems. We also compare our system with the baseline greedy based FF-VNF method. To solve the VNF allocation optimization problem, we use CPLEX solver at NEOS optimization server \cite{WinNT} (2x Intel Xeon E5-2698 @ 2.3-GHz
  597. 569 CPU and 92-GB RAM). To simulate our ACO base VNF allocation approach, we use Cloudsim \cite{cloudsim}.
  598. \begin{table}[!b]
  599.  
  600. \caption{Simulation Environment}
  601. \centering
  602. \begin{tabular}{|l|l|}
  603.  
  604. \hline
  605. \textbf{Parameter} & \textbf{Value} \\ \hline
  606. Simulation area & 2000 \times 2000 $ m^{2}$ \\ \hline
  607. Number of Data-Centers (DC) & 12 \\ \hline
  608. Number of eNBs under a DC & 4 - 25 \\ \hline
  609. Number of VNFs under an eNB & 500 - 2000 \\ \hline
  610. Communication delay between DCs & 10 - 200 msec \\ \hline
  611. Communication delay between DC and eNB & 2 - 5 msec \\ \hline
  612. Date rate to transfer VNF between DCs & 1 - 50 Mbps \\ \hline
  613. Size of each Virtual Network Functions (VNFs) & 100 - 300 KB \\ \hline
  614. Weight factor ($\gamma$) & 0.7\\ \hline
  615. Importance of pheromone value ($\alpha$) & 5\\ \hline
  616. Importance of heuristic value ($\beta$) & 1\\ \hline
  617. Local pheromone constant ($\rho_{l}$) & 0.3\\ \hline
  618. Global pheromone constant ($\rho_{g}$) & 0.4\\ \hline
  619. Number of ants & 20\\ \hline
  620. Maximum Iteration MAX-IT & 200\\ \hline
  621. \end{tabular}
  622. \label{table: 2}
  623. \end{table}
  624. \subsection{Simulation Environment}
  625. We consider a network consisting of 12 data centers. Each DC has primary memory between 2 to 16 GB and storage between 2 to 16 TB. Each DC has 200 - 400 VMs. These VMs are heterogeneous in size and capacity. There are several numbers of VNFs under a VM. Each VM has RAM between 512MB - 1024MB having clock speed 2.50GHz - 3GHz. Therefore, the processing power of a VM is 500 - 1000 instructions per second. Achievable data rate of a transmission link is randomly chosen with exponential distribution. We choose the range 1Mbps - 50Mbps for assigning data rates to individual links. The average of the results got from 50 simulation runs is used to plot the graph data points. For each of the simulation run, we have used different random seeds. Performance parameter values and ranges are summarized in Table \ref{table: 2}.
  626. \subsection{Performance Metrics}
  627. We have compared the performance of the studied systems on the following metrics:
  628. \begin{itemize}
  629.  
  630. \item Quality of Experience (QoE): QoE is defined as the inverse of average normalized response time to get service for a VNF from a particular DC. It helps us to quantify how fast an algorithm can extend services to the users.
  631. \item Number of relocations of the VNFs: VNF relocation is defined as the total number of migrations required to transfer a VNF from one DC to another. This metric has direct impact on the overall performances of the network. Lower the value, higher is the user performance.
  632. \item User satisfaction is defined as the integrated metric in terms of the number of VNF relocations and user Quality-of-Experience. It is computed as the sum of the inverse of the normalized value of the number of relocations and the normalized value of QoE. This represents overall performance of the studied algorithms.
  633. \item VNF Relocation Overhead: Relocating a VNF from one DC to another requires extra cost related to time and resources. VNF relocation overhead is defined as the extra cost that is required to transfer a VNF from a DC to another and the corresponding service cost. It is measured as the extra cost divided by the total cost of the system.
  634. \end{itemize}
  635.  
  636.  
  637.  
  638. \subsection{Simulation Result}
  639.  
  640.  
  641.  
  642.  
  643. Here we have studied the performance of our proposed TradeRC system by varying the number of eNBs under a DC, number of VNFs movement under an eNB and capacity of different data centers.
  644. \subsubsection{Impacts of Number of VNFs Movement per eNB}
  645. In this experiment, we vary the number of VNF movements per eNB keeping the number of data centers under a network, number of eNBs under a DC and DC's VNFs holding capacity fixed at 12, 20 and 600, respectively.
  646. \begin{figure*}[!t]
  647. \centering
  648. \captionsetup{justification=centering}
  649. \begin{subfigure}[H]{.49\textwidth}
  650. \centering
  651. \includegraphics[width=.9\textwidth, trim={0.3cm 0cm 1.3cm 1.3cm},clip]{JournelGraph/VNFResTime.eps}
  652.  
  653. \caption{Quality-of-Experience (QoE)}
  654. \label{graph:VNFone}
  655. \end{subfigure}
  656. \hfill
  657. \begin{subfigure}[H]{.49\textwidth}
  658. \centering
  659. \includegraphics[width=0.9\textwidth, trim={0.3cm 0cm 1.3cm 1.3cm},clip]{JournelGraph/VNFRel.eps}
  660. \caption{Number of VNF relocations}
  661. \label{graph:VNFtwo}
  662. \end{subfigure}
  663. \hfill
  664. \vspace{0.4cm}
  665. \begin{subfigure}[H]{.49\textwidth}
  666. \centering
  667. \includegraphics[width=0.9\textwidth, trim={0.3cm 0cm 1.3cm 1.3cm},clip]{JournelGraph/VNFSat.eps}
  668. \caption{User satisfaction}
  669. \label{graph:VNFthree}
  670. \end{subfigure}
  671. \hfill
  672. \begin{subfigure}[H]{.49\textwidth}
  673. \centering
  674. \includegraphics[width=0.9\textwidth, trim={0.3cm 0cm 0cm 0cm},clip]{JournelGraph/VNFoverhead.eps}
  675. \caption{VNF relocation overhead}
  676. \label{graph:VNFfour}
  677. \end{subfigure}
  678. \caption{Impacts of varying number of VNFs movement per eNB}
  679. \label{figVNF}
  680. \end{figure*}
  681. \par Fig. \ref{figVNF}(\subref{graph:VNFone})
  682. shows that, increasing the number of VNFs movement from an eNB QoE is decreased. In S-PL and in our TradeRC, Quality-of-Experience is very higher than A-SGWR and FF-VNF methods and perform close to each other. But in A-SGWR, response time is increased by huge amount after increasing the number of VNFs movement. This is because, A-SGWR considered only minimizing number of VNFs relocation. However, it didn't consider response time for a service. For that reason, QoE is very low in A-SGWR than S-PL and TradeRC methods. In A-SGWR, maximum amount of response time can be infinity which is not applicable in real-life scenario. Therefore, S-PL and TradeRC performs better in terms of QoE. \par
  683. Fig. \ref{figVNF}(\subref{graph:VNFtwo}) shows that, as the number of VNFs movement from an eNB is increased, the number of relocation percentage is also enhanced. From the graph, we see that, for small networks number of relocation in S-PL and TradeRC is near to each other. But for large networks, number of relocation in TradeRC is much less compared to S-PL solution. This is because, S-PL solution considered only minimizing response time. However, they didn't consider total number of relocation. In that system, maximum number of relocations can be infinity which is not practical. On the other hand, FF-VNF greedy method doesn't try to minimize the number of relocations and response time. For that reason, FF-VNF performs the worst than TradeRC in terms of number of relocations and QoE. \par
  684.  
  685. \par Fig. \ref{figVNF}(\subref{graph:VNFthree})
  686. indicates overall users' satisfaction is increased by increasing the number of VNFs movement from an eNB. For small types of networks, A-SGWR, S-PL and TradeRC perform near to each others. However, for increasing number of VNFs movement, user satisfaction in TradeRC is higher than other methods. In A-SGWR and S-PL, the authors have considered to improve only one parameter. However, for the other parameters they have not considered any requirement. In FF-VNF method, none of these two parameters are considered to be improved. Our system TradeRC works optimally for both of those parameters jointly. For that reason, user satisfaction is high in TradeRC.
  687. \par Fig. \ref{figVNF}(\subref{graph:VNFfour}) indicates that, with increasing number of VNFs movement, VNFs relocation overhead is also raised. This is because, we need to relocate higher number of VNFs from one DC to another DC with increasing number of VNFs movement. Our proposed TradeRC works better than other methods. This is caused by the fact that, in A-SGWR the authors tried to place all VNFs in one DC where the algorithm is running. So we need extra cost to get service from that DC. On the other hand, in S-PL, the number of relocations is very much higher than TradeRC and A-SGWR. For that reason, relocation cost is very much higher in S-PL. In greedy based FF-VNF method, we place the VNF in that DC where the capacity is available. We don't consider minimization of any parameter. For that reason, our proposed TradeRC system works better than other methods in terms of VNFs migration overhead cost.
  688.  
  689. \begin{figure*}[!t]
  690. \centering
  691. \captionsetup{justification=centering}
  692. \begin{subfigure}[H]{.49\textwidth}
  693. \centering
  694. \includegraphics[width=0.9\textwidth, trim={0.3cm 0cm 1.3cm 1.3cm},clip]{JournelGraph/BSResTime.eps}
  695.  
  696. \caption{Quality-of-Experience (QoE)}
  697. \label{graph:BSone}
  698. \end{subfigure}
  699. \hfill
  700. \begin{subfigure}[H]{.49\textwidth}
  701. \centering
  702. \includegraphics[width=0.9\textwidth, trim={0.3cm 0cm 1.3cm 1.3cm},clip]{JournelGraph/BSRel.eps}
  703. \caption{Number of VNF relocations}
  704. \label{graph:BStwo}
  705. \end{subfigure}
  706. \hfill
  707. \vspace{0.4cm}
  708. \begin{subfigure}[H]{.49\textwidth}
  709. \centering
  710. \includegraphics[width=0.9\textwidth, trim={0.3cm 0cm 1.3cm 1.3cm},clip]{JournelGraph/BSsat.eps}
  711. \caption{User satisfaction}
  712. \label{graph:BSthree}
  713. \end{subfigure}
  714. \hfill
  715. \begin{subfigure}[H]{.49\textwidth}
  716. \centering
  717. \includegraphics[width=0.9\textwidth, trim={0.3cm 0cm 0cm 0cm},clip]{JournelGraph/BSOberhead.eps}
  718. \caption{VNF relocation overhead}
  719. \label{graph:BSfour}
  720. \end{subfigure}
  721. \caption{Impacts of varying number of eNBs per DC }
  722. \label{figBS}
  723. \end{figure*}
  724. \subsubsection{Impacts of Number of eNBs per DC}
  725. In this experiment, we vary the number of eNBs under a DC keeping the number of data centers under a network, number of VNFs movement per eNB and DC's VNFs holding capacity fixed at 12, 250 and 600, respectively.\par
  726. Fig. \ref{figBS}(\subref{graph:BSone})
  727. shows that, QoE is decreased with increased number of eNBs under a DC. In S-PL and our TradeRC systems, QoE is close to each other. However, response time is less in S-PL than TradeRC because it's main target is to minimize response time. For that reason QoE is very high in that approach. On the other hand, response time is very higher in A-SGWR and FF-VNF methods than other two systems. Because, A-SGWR considers only minimizing the number of VNF relocations. However, they didn't consider minimizing response time to get a service from a DC. In their system, response time can be infinity which is not feasible in real life. In FF-VNF greedy solution, we have not considered to minimize the number of VNF relocations. If we have capacity in the DC, we place that VNF greedily in that DC. Therefore, QoE is very low in A-SGWR and FF-VNF methods.
  728. \par Fig. \ref{figBS}(\subref{graph:BStwo})
  729. depicts that, number of VNF relocations is enhanced with the higher number of eNBs under a DC. As the number of eNBs is raised, the number of VNF relocations is also increased. In A-SGWR and TradeRC system, the number of VNF relocations is less than S-PL and FF-VNF approach and they perform close to each other. A-SGWR performs better than TradeRC because, it only considered to minimize the number of VNF relocations. In S-PL, number of relocations is very much higher. This is because, they have only considered to minimize the response time. In that system, number of relocations can be infinity which is not real life scenario. In FF-VNF greedy method, we have not consider to minimize the response time. For that reason, response time is higher in FF-VNF.
  730. \par
  731. From Fig. \ref{figBS}(\subref{graph:BSthree}), we observe that user satisfaction is decreased with the increased number of eNBs per DC. For small types of networks, all methods perform near to each other. However, for large networks user satisfaction is higher in TradeRC than other approaches. In A-SGWR and S-PL, the authors have considered to improve only one parameters. However, for the other parameters, they have not considered any requirement. The other parameter value can be infinity in that systems. For that reasons, user satisfaction is less in that systems. Our system TradeRC works optimally for both of those parameters jointly.
  732. \par Fig. \ref{figBS}(\subref{graph:BSfour})
  733. indicates VNF relocation overhead by increasing number of eNBs under a DC. Although relocations overhead in TradeRC method increases with higher number of eNBs per DC, it performs better compared to other systems. This is because, in A-SGWR all VNFs are tried to migrate to that DC where the algorithm in running. In that system, relocation cost is very low but extra service cost is required to get service from that DC. In S-PL, the number of relocation is very much higher. For this reason, relocation cost is very higher in that system. Due to this reasons, VNF relocation overhead is higher than our TradeRC system. On the other hand, in FF-VNF greedy approach, we have not considered minimizing the number relocations and response time. For that reasons, migration overhead is very much higher in FF-VNF method than other approaches.
  734. \begin{figure*}[!t]
  735. \centering
  736. \captionsetup{justification=centering}
  737. \begin{subfigure}[H]{.49\textwidth}
  738. \centering
  739. \includegraphics[width=0.9\textwidth, trim={0.3cm 0cm 1.1cm 1.3cm},clip]{JournelGraph/CapResTime.eps}
  740.  
  741. \caption{Quality-of-Experience (QoE)}
  742. \label{graph:Capone}
  743. \end{subfigure}
  744. \hfill
  745. \begin{subfigure}[H]{.49\textwidth}
  746. \centering
  747. \includegraphics[width=0.9\textwidth, trim={0.3cm 0cm 1.1cm 1.3cm},clip]{JournelGraph/CapRel.eps}
  748. \caption{Number of VNF relocations}
  749. \label{graph:Captwo}
  750. \end{subfigure}
  751. \hfill
  752. \vspace{0.4cm}
  753. \begin{subfigure}[H]{.49\textwidth}
  754. \centering
  755. \includegraphics[width=0.9\textwidth, trim={0.1cm 0cm 1.1cm 1.3cm},clip]{JournelGraph/CapSat.eps}
  756. \caption{User satisfaction}
  757. \label{graph:Capthree}
  758. \end{subfigure}
  759. \hfill
  760. \begin{subfigure}[H]{.49\textwidth}
  761. \centering
  762. \includegraphics[width=0.9\textwidth, trim={0.3cm 0cm 0cm 0cm},clip]{JournelGraph/CapOverhead.eps}
  763. \caption{VNF relocation overhead}
  764. \label{graph:Capfour}
  765. \end{subfigure}
  766. \caption{Impacts of varying number of VNF holding capacity of DC }
  767. \label{figCap}
  768. \end{figure*}
  769. \subsubsection{Impacts of VNF holding capacity of DC}
  770. In this experiment, we measure the impact of DC's VNFs holding capacity by varying the capacity of DC keeping the number of data centers under a network, number of eNBs under a DC and number of VNFs movement per eNB fixed at 12, 20 and 250, respectively.
  771. \par Fig. \ref{figCap}(\subref{graph:Capone})
  772. depicts that, by increasing the capacity of DC, QoE is increased. TradeRC and S-PL perform close to each other in terms of QoE. In S-PL, their main objective was to minimize response time. For that reason, S-PL performs better than other methods in terms of QoE. Again, TradeRC performs better than A-SGWR and FF-VNF method because in TradeRC, we try to bring trade off between response time and the number of relocations. On the other hand, response time can be infinite in A-SGWR system which is not practical. For that reason, QoE is very low in A-SGWR and FF-VNF methods. Therefore, S-PL and TradeRC perform better with respect to QoE than other two methods.
  773. \par
  774. From Fig. \ref{figCap}(\subref{graph:Captwo})
  775. we see that, number of relocations is decreased with increasing the capacity of the DC. This is because, by increasing capacity, it means that DC has enough capacity and particular type of VNFs is available in that DC. So we don't need to relocate VNFs to get that particular type of service from another DC. A-SGWR and TradeRC perform better than other two approaches and A-SGWR perform better than TradeRC because in A-SGWR, it tried to minimize the number of relocations only. On the other hand, S-PL performs the worst because in S-PL the authors tried to minimize response time allowing infinite number of relocations in their system which is not feasible in real life. In FF-VNF, we don't consider to minimize the number of relocation. For that reason, the number of relocations is very much higher in FF-VNF method.
  776. \par user satisfaction is improved with the increasing capacity of the DC which is depicted in Fig. \ref{figCap}(\subref{graph:Capthree}). user satisfaction is also high in our proposed TradeRC system in that case. This is because, TradeRC brings trade-off between the two conflicting objectives and works optimally for both of those two parameters jointly. On the other hand, A-SGWR and S-PL tried to improve only one parameter value. In these systems, other parameter value can be infinity. For that reason, user satisfaction is less in A-SGWR and S-PL than TradeRC.
  777. \par Fig. \ref{figCap}(\subref{graph:Capfour}) shows that, VNF relocation overhead decreases with increased capacity of the DC. This is because, with increasing number of DC's capacity, number of reloactions decreases. In FF-VNF greedy method, extra service cost and relocations cost are huge. Because, in that method, the number of relocations is not minimized. In A-SGWR, all VNFs were tried to be placed in one DC so that the number of relocations is reduced. In that system, extra service costs are required to get service where the algorithm is running. On the other hand, In S-PL, the number of relocations can be infinite. For that reason, relocations cost are huge in that system. Therefore, migration overhead cost is higher in S-PL, A-SGWR and FF-VNF systems than our proposed TradeRC system.
  778.  
  779.  
  780. \section{Conclusion and Future Work}
  781. \label{sec six}
  782.  
  783. This paper introduced a framework for optimal placement of VNFs in 5G data centers. Decreasing the response time for user code execution in VNFs of 5G data centers can be achieved by enabling VNF relocations; however, excessive migration causes communication and computation overhead. This work explored optimal trading-off approach in between two conflicting objectives- maximizing Quality-of-Experience and minimizing number of VNF relocations. For large networks, this placement problem was proven to be an NP-hard problem. Our proposed AI based ACO solution maximized Quality-of-Experience and minimized relocation overhead, increasing user satisfaction. The experimental results showed significant performance improvement in terms of user satisfaction and relocation overhead as high as 25\% and 15\%, respectively.
  784. \par In the future, we want to develop mathematical modeling and analysis for determining the values of the system parameters dynamically so as to further enhance the performances.
  785. \section*{Acknowledgment}
  786. The authors are grateful to King Saud University, Riyadh, Saudi Arabia for funding this work through Researchers Supporting Project number RSP-2019/18
  787.  
  788.  
  789.  
  790.  
  791.  
  792. %% References
  793. %%
  794. %% Following citation commands can be used in the body text:
  795. %% Usage of \cite is as follows:
  796. %% \cite{key} ==>> [#]
  797. %% \cite[chap. 2]{key} ==>> [#, chap. 2]
  798. %%
  799.  
  800. %% References with bibTeX database:
  801. \nocite{*}
  802. %\bibliographystyle{elsarticle-num}
  803. % \bibliographystyle{elsarticle-harv}
  804. % \bibliographystyle{elsarticle-num-names}
  805. % \bibliographystyle{model1a-num-names}
  806. % \bibliographystyle{model1b-num-names}
  807. % \bibliographystyle{model1c-num-names}
  808. % \bibliographystyle{model1-num-names}
  809. % \bibliographystyle{model2-names}
  810. % \bibliographystyle{model3a-num-names}
  811. % \bibliographystyle{model3-num-names}
  812. % \bibliographystyle{model4-names}
  813. % \bibliographystyle{model5-names}
  814. % \bibliographystyle{model6-num-names}
  815. \bibliographystyle{unsrt}
  816. \bibliography{sample}
  817. \end{document}
  818.  
  819. %%
  820. %% End of file `elsarticle-template-num.tex'.
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement
Public Pastes
Advertisement
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy.  OK, I Understand
Not a member of Pastebin yet?
Sign Up, it unlocks many cool features!