Metaheuristics as Enablers for VNF Scheduling in the Network Slice Set Up Process

I. INTRODUCTION

THE fifth generation (5G) of mobile networks has brought a new era in telecommunications where new research challenges and business potentials have emerged. The key advances of 5G refer to i) the convergence of telecom sector with the cloud infrastructures, through the virtualisation of the network functions, and ii) the unprecedented performance gains, due to the evolution of the radio access network (RAN) part of the network. Already, a plethora of telecom operators around the globe [1], have integrated 5G compliant equipment in their infrastructures and they have set the scene for providing 5G-enabled services. The research community is also intensively active on 5G-related topics. For instance, 5G PPP projects [2] have provided a plethora of 5G experimentation infrastructures around Europe. Academia has also produced a great number of results in emerging 5G research fields, such as network slicing [3], [4], mobile network openness [5], resource sharing [6], [7], and (radio) access technologies engagement [8], [9].

The goals of 5G networks were set from ITU IMT 2020 [10], and they can be described briefly by the following higher level key performance indicators (KPIs) compared to the previous generation; namely: Increase by 1000 times the wireless area capacity; reduce the average service creation time cycle from 90 hours to 90 minutes; create secure, reliable and dependable internet with a “zero perceived” downtime for services provision; save up to 90% of energy per service provided; support ultra-dense device deployments; and enable advanced user controlled privacy. From the service perspective, one of the ultimate goals of 5G, is to be able to handle heterogenous services, with different, and sometimes competitive requirements over a unified network infrastructure. The three extremes of such services are [11]: i) Enhanced mobile broadband (eMBB) – also called extreme mobile broadband, ii) ultra-reliable and low latency communications (URLLC), and iii) massive machine type communications (mMTC).

Towards the above-mentioned 5G developments and performance gains, a set of technologies have been emerged, including a game changer one; the “network slicing” [12]. The main target of the network slicing concept is to enable the creation of multiple virtual isolated networks on a shared physical infrastructure, so that heterogeneous and conflicting service requirements are fulfilled. A prerequisite for network slicing implementation is the concept of decoupling network functions from dedicated hardware, to make them software functions that can be hosted in/migrated to virtual environments. The network functions softwarization, requires the transformation of physical network functions (PNFs) to virtualised/containerized network functions (VNFs/CNFs). Thus, the network slices are considered sets of VNFs, hosted on several virtual servers of a provider’s network.

In this context, resources of whatever kind (compute, network, storage, etc.) should be allocated efficiently to VNFs, fulfilling functional requirements, such as the network slice set up time. The slice set up process includes the instantiation and the configuration of the VNFs/CNFs that compose a slice; hence it affects a key 5G KPI, the service creation time [13] (referring to the time needed for a network service at the “zero” status to become fully functional).

In this article, the problem of minimising the time needed for instantiation and configuration of VNFs is mapped to the job-shop scheduling problem (JSSP) [14]. To resolve the problem the toolbox provided by the metaheuristic processes is examined. More precisely, we consider a system that receives requests for setting up network slices and provides scheduling decisions based on nature-inspired metaheuristics. Expanding our previous work on metaheuristics [15], the evolution-based and the swarm-based metaheuristic categories are targeted through two key representatives, namely: The genetic algorithm (GA) and the ant colony optimisation (ACO), respectively. For each one of the approaches, we study thoroughly the impact of configuration parameters on their performance in order to select the best-fitting solution for the VNF/CNF scheduling problem. In the following, for simplicity, we use only the term VNFs, and VNF scheduling; however the proposed approach is valid for CNFs, as well.

The remaining of this paper is organised as follows. Section II describes the network slicing concept, as well as related resource allocation techniques for placement and scheduling of VNFs that compose network slices. In Section III, the adopted system model is presented by explaining how the problem of minimizing the slice set up time is mapped to the well-known JSSP. Section IV defines a case study, where metaheuristic algorithms are utilized to solve the target problem. Section V presents performance evaluation results. Finally, in Section VI, conclusions and insights for further study are provided.

II. THE CONCEPT OF NETWORK SLICING

A. Network Slice and VNFs

The new era of telecommunications brings up plenty of high-performance standards along with heterogeneous requirements set by emerging vertical services (e.g., Internet-ofthings, automotive communication), which cannot be satisfied by the conventional/monolithic network deployments. High data rates, low latency, seamless coverage, and dense connectivity are few of the most important requirements that new generation networks must fulfil. The network’s infrastructure must be able to cope with resource demanding and competitive services simultaneously. The countermeasure to this challenge is the concept of network slicing, chosen to be the main pillar in the new generation of mobile networks that will enable innovative vertical services. Network slicing refers to the process of setting up on demand end-to-end logical networks, that: i) Run on a shared underlying (physical or virtual) network, ii) are mutually isolated, and iii) can have independent control and management planes [16]. The implementation of the network slicing concept is based on two key technologies, namely, the software defined networks (SDN) and the network function virtualisation (NFV).

SDN architecture refers to decoupling routing (control plane) and forwarding (data plane) functions in network nodes, thus enabling the capability of programmable network control and the import of an abstraction level in the underlying infrastructure, suitable for application and network services. SDN purpose is to address the fact that the static architecture of traditional networks was decentralized and complex, making the network unable to keep up to dynamic changes and hard for troubleshooting. By disaggregating control and data plane, SDN attempts to centralise network intelligence in a set of limited network components, thus transforming conventional networks to dynamic, manageable, cost-effective, and adaptable ones. The basic architectural components of SDN are: i) SDN controller, which is the logical centralized entity responsible for every decision in the network, ii) SDN application, which is the software component importing a desired functionality in the network, iii) SDN datapath, which is the logical network device providing the physical network device with SDN capabilities, iv) SDN interfaces, divided in two categories: Control to data-plane interface, between SDN controller and SDN datapath, and northbound interface, between SDN application and SDN controller.

NFV is the concept of virtualising network services, such as firewall, encryption, routing etc., that have traditionally been run on dedicated hardware. These services are packaged as isolated logical entities (virtual machines or containers) on commodity hardware, which allows service providers to run these on standard servers instead of proprietary ones. NFV implementation can improve scalability and agility by allowing service providers to deliver custom network services and applications on demand, minimising the need for additional hardware resources [17]. According to ETSI [18] the NFV framework consists of: i) Virtualized network function (VNF), i.e., the software implementation of a network function, ii) NFV infrastructure, including the resources to be virtualised and iii) NFV management and orchestration (MANO), which is responsible for the orchestration and lifecycle management of physical and logical resources that support infrastructure virtualisation.

Consequently, a “network slice” can be considered as a set of VNFs that are hosted in compute nodes of a network infrastructure to offer isolated and scalable network services to vertical service providers.

B. VNF Placement and Scheduling

The research interest on network slicing lies mainly in the so-called resource management problem (management of the computation power), where two key algorithmic processes are defined; the VNF placement, referring to the placement of VNFs from a set of network slice requests to the physical computing hosts, and the VNF scheduling, referring to the order that the VNF are installed/served by the hosts.

VNF placement. In the literature the algorithmic part of VNF placement is mainly addressed using the integer linear programming (ILP). For instance, in [19], ILP is used to deal with VNF placement problem, targeting at maximising continuous available time of service chain functions (SCFs). ILP is also used to formalise the problem in [20], where the authors study VNF placement and chaining in network slicing considering geographic location of network slice users. The authors in [21] are dealing with VNF placement problem, studying the degree that intra-slice isolation and end-to-end delay restrictions affect resource utilization (CPU and bandwidth). They adopt a MILP approach with AMPL to model the optimization algorithm and CPLEX as MILP solver [22]. The problem is modelled as a MILP in [23] as well, where the authors focus on how to place VNF instances in distributed data centers and schedule the appropriate network flows to minimise the total cost of VNF deployment and flow communication for big data processing.

In addition to the above-mentioned set of approaches, online solutions have been proposed as well. For instance, in [24] the authors propose a mechanism of online placement and reallocation of VNFs between core and edge networks, by using a forwarding graph embedding algorithm, with major objective to maximise the number of served users. Similarly, the research study in [25] introduces an online method to orchestrate VNFs and schedule traffic flow for network utility maximisation, using deep reinforcement learning (DRL) assisted by an optimization model.

VNF scheduling. The study in [26] implements Qlearning, a Reinforcement Learning technique, to solve delayguaranteed VNF scheduling. The problem is handled as a timeslot problem, where in each slot a decision on which VNF will be executed is being made. The authors in [27] present a solution for VNF scheduling problem, based on GA, adopting three variations, i) feed the algorithm with deterministic initial population, ii) use an adaptive crossover probability controlled by the fitness value, and iii) apply mutation controlled by simulated annealing. In [28], VNF scheduling with E2E delay requirements among services is formulated first as MILP and then as a Markov decision process (MDP) solved with Qlearning algorithm. In [29], VNF scheduling is formulated as a flexible job-shop scheduling problem, and the authors propose a deep Q-Learning algorithm, named DQS, to solve the problem. They also compare their approach with other four algorithms, a greedy-based, a matching-based, a fair weighted and GA. A metaheuristic approach, on the other hand, is used by [30], developing two novel genetic-based algorithms, which try to optimise VNF scheduling by maximising the number of accepted service requests, and minimising the number of bottleneck links and the overall processing time. An alternative approach is presented by the authors of [31], who propose a matching-based algorithm to solve both offline and online VNF scheduling.

Joint VNF placement and scheduling. The authors in [32] present a two-phase solution for joint optimization of VNF chain placement and request scheduling problem. The authors apply the theory of open Jackson network to model VNF chains, formulate the VNF chain placement problem as a variant of variable-sized bin-packing problem, and propose a priority-driven weighted algorithm best fit decreasing using smallest used nodes (BFDSU) to optimise resource utilization and a heuristic algorithm reverse complete Karmarkar- Karp (RCKK) to minimise response latency. A similar approach for the joint optimisation problem is proposed in [33]. The authors study stateful VNF placement along with routing scheduling, formulate the problem as a Mixed Integer Linear Programming (MILP) and use a two-phase fast algorithm to deploy VNF instances and select appropriate routing paths. The objective of placing and scheduling VNFs in [34] is to minimise cost incurred by the service provider (SP) to lease computing and networking resources. Also, latency requirements of service demands, which arrive dynamically, should be satisfied. Cost-effective placing and scheduling scheme are compared with a low-latency scheme and is formulated with MILP and with a heuristic that consists of three subalgorithms, i.e., optimal zone determination (OZD), latency requirement verification (LRV), and service demand provisioning (SDP). The study in [35] proposes an approach to jointly optimise the processes of VNF placement and VNF scheduling. Authors first solve the optimal VNF placement for all flows to simplify the problem, and then they use Lagrangian multipliers to relax and decompose it into a series of subproblems. A dynamic programming method is designed to solve each subproblem and a heuristic method is presented to construct a feasible solution for it. Finally, the solution is optimised through the subgradient optimisation method. The authors in [36] propose a graph-based algorithm to solve VNF placing and scheduling on demand, taking also some software requirements into consideration. On the other hand, the author in [37] evaluates heuristic, metaheuristic and greedy approaches for the joint optimisation of VNF placement and scheduling.

Overall, the VNF placement problem, in practice, is addressed internally in the platform that implements the virtualisation environment (e.g., a cloud computing platform, such as Kubernetes). Thus, the implementation details can affect the efficiency of the solution. In this view, proof-of-concept solutions have been developed, as for example the one presented in [38], where VNF placement and chaining is concerned for the interactive gaming use case. An implementation for VNF placement is presented in [39] as well. The authors introduce an ETSI NFV compliant, scalable, and distributed architecture, called Megalos, which allocates VNFs via a custom variation on top of the Kubernetes native VNF placement scheme. Thus, the VNF scheduling problem seems to be more attractive, as it is platform independent and, also, more critical, when it comes to time optimization criteria, like the slice set up time. Thus, the target of our work is to study the VNF scheduling problem. The essentials of the proposed approach are presented in the next section.

III. SYSTEM MODEL

A. Problem Statement

As already mentioned, a network slice is comprised of VNFs which are chained in a specific order. We assume that a network slice provider (NSP) is responsible for fulfilling the performance requirements of a requested service, and for providing the service-related network slice(s) ready (up and running) in the shortest possible time.

Considering the ETSI MANO architecture and the 5G service-based architecture (SBA), the responsibility for the end-to-end deployment of a service-related network slice is upon the network slice management function (NSMF), which resides at the NSP [34]. Also, considering the 5G performance targets initially set by ITU IMT 2020 [40], for the network slicing preparation, the NSP targets to reduce the average service creation time from 90 hours to 90 minutes; The service creation time has been defined as the “time required to provision a service, measured since a new service deployment is requested until the overall orchestration system provides a response” [13], and it can be divided into many time-consuming phases, each of them depending on different factors. In the attempt to identify the various phases of service creation, 5G-PPP has reported a collaborative reference timing flow. This timing flow does not only separate the stages in network service creation and activation process, but also defines clear starting and ending time points. A representation of the timing flow is presented in Table I. From the set of phases defined for the service creation procedure, phase 2, (named as instantiate, configure & activate) seems to be the most time-consuming stage in the whole process, since it includes the processes of instantiating, configuring and activating a slice. As a result, the minimisation of the time spent in this phase would have a positive overall effect in the network slice creation process. In this view, our target is to minimise the time needed for instantiation and configuration of a network slice, by studying fast and robust schedulers that are able to schedule resourcecompetitive VNFs of various network slices in a limited set of physical machines (hosts).

In this context, let the NSP manage several processing machines, located in multiple compute centers (at network core, edge etc.) on which VNFs can be hosted. We assume the following:

Chunks of requests for deployment of network slices are periodically received by the NSP.

Each request includes the required execution plan (VNF order) for each slice.

The NSP, based on i) monitoring of past set-ups, ii) knowledge of the capabilities of the available processing machines and iii) network constrains and delays, estimates the time needed for setting-up each specific VNF and assigns it in the most suitable machine.

An optimization algorithm is applied to schedule a chunk of requests, taking all constrains into account. The algorithm exports the total VNF execution plan.

To select the optimisation algorithm for the scheduling of network slice chunks, the problem is mapped to JSSP, as explained below.

B. Mapping VNF Scheduling to JSSP

In the literature, the scheduling problem mainly refers to the challenge of selecting time slots for performing a set of activities, with respect to a given set of constrains (such as resources limitations or precedence order among the activities), targeting at optimising a performance metric [41]. In most of the network related scheduling approaches, the optimisation metric is either the total processing time of the activities (i.e., the minimisation of makespan [42]) or the amount of processing resources allocated to run the activities. At the dawn of the slice-enabled networks, scheduling procedures fit well to procedures needed in sliced networks for allocating VNFs to available processing resources. This mapping is clear since every network service is modelled as a service chain, i.e., a set of network functionalities, implemented as VNFs, in a specific order [43].

A well-studied example of scheduling problem is the Job- Shop Scheduling Problem. The JSSP sets a combinatorial problem, where its solving has been used widely in literature to address resource allocation and scheduling problems [44]–[48]. Here we assume the JSSP with the following characteristics:

Let a set of n jobs, denoted as [TeX:] $$J_1, J_2, \cdots, J_n;$$

Within each job there is a set of operations [TeX:] $$O_1, O_2, \cdots, O_i,$$ of varying processing times;

Each operation of every job must be executed is a specific machine, among a set of m machines, denoted as [TeX:] $$M_1, M_2, \cdots, M_m,$$ according to initial plan;

Each machine can process one operation at a time and when an operation is assigned to a machine, the machine can not interrupt its execution.

The objective is to find an execution plan of the activities, w.r.t., precedence and resource constraints of the system, that minimises the time in which all operations will be executed (i.e., to find the minimum makespan). To formulate the VNF scheduling, the following mapping is assumed:

JSSP machines are mapped to network provider’s machines that host VNFs;

Jobs correspond to network slicing requests;

Operations are mapped to VNFs.

More specifically, based on this mapping, we use the following notation:

𝑠 for the 𝑠th network slice, where [TeX:] $$s \in[1,|S|];$$

[TeX:] $$F_S$$ for the set of VNFs of slice 𝑠;

[TeX:] $$f_{s j}$$ for the 𝑗th VNF of the 𝑠th slice, where [TeX:] $$s \in[1,|S|]] \ \text { and } j \in\left[1,\left|F_s\right|\right];$$

𝐻 for the set of hosts; and ℎ for the ℎth host, where [TeX:] $$h \in[1,|H|];$$

[TeX:] $$h_{S, j}$$ for the host where the 𝑗th VNF of the 𝑠th slice is deployed, [TeX:] $$h_{s, j} \in[1,|H|];$$

[TeX:] $$t_{s, j}$$ for the starting time of the 𝑗th VNF of the 𝑠th slice;

[TeX:] $$T_{s, j}$$ for the deployment time of the 𝑗th VNF of the 𝑠th slice.

The constrains of this problem can be formalised as follows:

[TeX:] $$t_{s, j+1}-t_{s, j} \geq T_{s, j+1},$$ representing that each VNF must be installed after the completion of the previous VNF of the same network slice;

[TeX:] $$t_{s, j} \geq t_{s^{\prime}, j^{\prime}}+T_{s^{\prime}, j^{\prime}} \text { or } t_{s^{\prime}, j^{\prime}} \geq t_{s, j}+T_{s, j} \text { for } h_{s, j}=h_{s^{\prime}, j^{\prime}},$$ representing that a host cannot process two or more VNFs simultaneously.

Thus, the minimisation of makespan is defined as:

where the quantity [TeX:] $$\max \left[t_{s, j}+T_{s, j}\right]$$ defines the completion time of the last VNF among all network slices.

C. Metaheuristics as a Candidate Solver

Based on the mapping presented in the previous section, a solution of the VNF scheduling problem can be provided by resolving the related JSSP [49]. The JSSP is known as an NP-hard problem, meaning it cannot be solved in polynomial time [50]. Thus, it makes ineffective the use of exact methods (such as the dynamic programming, the branch & bound, etc.) since they search exhaustively to the space of all the potential solutions to find the optimal one.

Also, it is worth noted that the execution time (complexity) of the optimisation algorithm to be used affects the overall slice set-up time as well. In other words, the response time of the algorithm that performs the scheduling must be negligible, compared to the other procedures needed for setting the slice up.

Based on the above observations, heuristic methods fit well to the JSSP, as they can provide a near-optimal solution by constructing solutions according to greedy decisions [51]. Heuristics have some remarkably interesting advantages. To name some, they work well for dynamic problem sizes [52]; they find a solution in reasonable time [44]; and they can be combined with other methods [53]. However, the ‘greedy’ nature of heuristics is not always preferable when the problem size increases, and the near-optimal solution they provide tends to be worse, or the algorithm may stick on local minima or maxima. To compensate with the greediness of the heuristic methods, metaheuristic methods have emerged.

The metaheuristic category of algorithms refers to high-level heuristics that mimics the biological or physical phenomena. Metaheuristics are refined scientifically to find near-optimal solutions in reasonable computing time, and bring some additional advantages compared with heuristics: i) Simple and easy implementation, ii) avoiding stucking on local optima, and iii) tunning of the execution time through execution parameters that can change based on the input size [54]. Another unique feature that metaheuristics apply is the different search process. As it is analyzed in [55], these algorithms apply two phases of search: intensification and diversification. The intensification phase finds the local best solution within its adjacent location, called as local search. The diversification phase starts the search process globally in the provided search space which intend to attain the global solution, called as global search. The most challenging task in the development of any metaheuristic algorithm is to find a suitable balance between intensification and diversification.

IV. SELECTED METAHEURISTIC ALGORITHMS

Digging into the plethora of metaheuristic methods, there is a set of algorithms called ‘nature-inspired’. The natureinspired methods, as their name implies, adopt their behavior from various nature functionalities and have been extensively used in the last decade to solve various optimisation problems in many research fields such as cloud computing [52], power consumption [53] and data-mining [54]. According to [51], nature-based methods can be classified into four divisions: Evolution-based, inspired by the theory of natural evolution, Physics-based, mimicking physical rules in the universe, Swarm-based, mimicking the social behavior of groups of animals, and Human-based, inspired by the advancement in level of searching strategy. In this study, we focus on the most efficient metaheuristic algorithms of the Evolution-based and the Swarm-based categories, namely the genetic algorithm and ant colony optimisation.

A. Genetic Algorithm (GA)

The GA is a genetic or evolution-based method to solve combinatorial optimisation problems such as the one studied in this paper. The block diagram of the adopted method is depicted in Fig. 1, while each one of the blocks is explained below.

1) Encoding: The encoding process refers to the process of representing a set of initial (randomly selected) solutions to arrays of VNFs with specific order. Using genetic-based terminology, each VNF is a gene, and a solution (series of VNFs) is a chromosome, as depicted in the example that follows:

2) Crossover: Crossover is a genetic operator analogous to biological reproduction, and it aims at breeding new acceptable solutions from existing ones. This procedure requires two VNF chains (chromosomes) referred to as “parents”. First, from both the parent chromosomes, a portion of the same lengh is selected. Then this portion is exchanged between the chromosomes to create two new chromosomes (children), as depicted in Table II. A portion is valid for exchange, only if duplications and invalid crossovers are avoided.

3) Mutation: Mutation is the genetic operator that preserves the genetic diversity from one generation to the next. This is succeeded by changing randomly the order of the VNFs in the chain. However, a mutation can also produce unacceptable solutions that violate constrains. To prevent this, in our implementation, the randomness of mutation is restricted to chromosome areas that the constrains are not violated.

4) Evaluation (Fitness function): The process of evaluation or fitness function is used on evaluating the solutions produced from genetic operations. This evaluation happens by calculating for every solution the objective value, that is [TeX:] $$\max \left[t_{s, j}+T_{s, j}\right]$$as defined in the objective function (1).

5) Selection: The selection mechanism is used for keeping the most “genetically robust” children of a generation, thus the solutions with the optimal service creation time. The selected children serve as parents in the next generation.

B. Ant Colony Optimisation (ACO)

In the swarm-based metaheuristic category, the ACO is the most representative paradigm. Marco Dorigo was the first to introduce ACO in his PhD thesis in 1992 [56]. The idea behind the algorithm was inspired by the foraging process of ants. When an ant of a colony searches for food, it deposits a special substance on every path that walks called pheromone. The shorter the path, the bigger the portion of pheromone in the path. Ants coming later, choose with greater probability the path with increased amount of pheromone previously deposited by other ants, thus a shorter path. As a result, ants succeed to find the shortest path to the food source. The block diagram of the algorithm is depicted in Fig. 2.

1) Encoding to graph: The problem must first be encoded as graph where:

Each VNF is represented by a node.

VNFs belonging to the same network slice request are connected with unidirectional edges, respecting the order of processing.

The rest of the VNFs are connected with bidirectional edges.

The cost of its edge is an ant-inspired parameter [TeX:] $$\tau_{j_1} \rightarrow j_2,$$ called pheromone concentration. The pheromone concentration quantity refers to the amount of pheromone deposited by each ant for transition from VNF/node [TeX:] $$j_1$$ to VNF/node [TeX:] $$j_2.$$ The contribution of each ant m that has passed from the VNF/node [TeX:] $$j_1$$ to VNF/node [TeX:] $$j_2$$ is given by the following quantity:

where Q is a constant, selected to tune the size of the ratio [TeX:] $$Q /\left(t_{s, j_2}+T_{s, j_2}\right),$$ based on the volumes of the denominator (i.e., is a problem specific quantity). Thus, the [TeX:] $$\tau_{j_1} \rightarrow j_2$$ is updated as follows:

where [TeX:] $$\tau_{j_1} \rightarrow j_2$$ current value and [TeX:] $$\tau_{j_1}^{\prime} \rightarrow j_2$$ the updated one. Also, [TeX:] $$\rho$$ is the pheromone evaporation coefficient, M is the number of ants, and the sum [TeX:] $$\sum_m^M \Delta \tau_{j_1 \rightarrow j_2}^m$$ is the contribution of the ants that passed from the representing edge, as defined in (2).

2) Initialise ants: In this stage, the number of the ants (usually being equal to the number of network slice requests) is defined. For our analysis, we denote by M the number of ants/agents in the system. For each ant, m, the number of iterations is also defined, i.e., the number of times that an ant is going to run through the graph (apply a local search as explained below).

3) Local search: The local search refers to the path followed by an ant in the graph. Each ant, starting from a VNF/node [TeX:] $$j_1$$ of the graph, moves to the adjacent node [TeX:] $$j_2$$ with probability:

where,

Attractiveness [TeX:] $$\eta_{s, j},$$ represents a heuristic value of the cost of selecting the move, and it is equal to the reverse of the duration of VNF deployment, i.e., [TeX:] $$1 / T_{s, j}.$$

[TeX:] $$\sum_{l \in \text { AllowedTransitions }{ }_{j_1}}\left[\tau_{j_1 \rightarrow l}\right]^\alpha\left[\eta_{s, l}\right]^\beta$$ is the cumulative product of pheromone concentration and heuristic value for all possible node transitions from [TeX:] $$j_1 \text {. }$$

[TeX:] $$\alpha \text { and } \beta$$ parameters, are arbitrary values, [TeX:] $$\alpha \in[0, \infty),\beta \in[1, \infty],$$ that determine the degree of influence from the heuristic and pheromone values, respectively.

4) Global search: When the ants finish their job and produce their solutions, that is a valid sequence of VNFs, the algorithm keeps the solution with the best makespan. Then the pheromone trails in each edge are globally updated as defined in (3). When one of the stopping criteria is met, then the output of the algorithm is the VNF sequence with the best makespan until that time.

V. PERFORMANCE EVALUATION

The two algorithms were tested for a wide range of values for their configurable parameters, while a numerous set of runs has been executed to extract each evaluation result. To evaluate the algorithms, we adopted a [TeX:] $$10 \times 10$$ (i.e., #slices [TeX:] $$|S|=10,$$ and [TeX:] $$\text { \#VNFs }\left|F_s\right|=10 \text { per slice) and a } 20 \times 5$$ dataset (i.e., #slices [TeX:] $$|S|=20, \text { and \#VNFs }\left|F_s\right|=5$$ per slice), named “orb04” and “ft20” (from [57]), with known minimum makespans equal to 1005 and 1165 time-units, respectively. We also assume known deployment times and machines for the input, i.e., known values for the [TeX:] $$T_{s, j}, \text { and } h_{s, j},$$ parameters. More precisely, the format of every dataset follows the rules listed below (we use a [TeX:] $$6 \times 6$$ example for convenience):

The first row defines the number of network slices requests and number of VNF hosts for the specific instance, e.g.: “6 6”, “10 10” or “20 5”.

Each row contains a set of pairs whose number is equal to the number of VNFs of each network slice.

Each pair of numbers describes a specific VNF by defining the machine hosting the operation and the duration of executing the operation in time units estimated by the NSP e.g. “2 1” means that the VNF is hosted by machine 2 and its execution will last 1 time-unit.

A. Numerical Results

The performance of the GA is tightly correlated with its tunning parameters, namely, the number of generations, the population size, the crossover and the mutation probability. We first study the impact of crossover and the mutation probabilities on the achievable makespan. The actions of crossover and mutation help the algorithm to overcome the problem of stucking on local optima by changing the order of the VNFs. As it is depicted on Fig. 4, for 40 generations and population size equal to 100, the performance of the algorithm is improved as more crossover and mutation actions are operated. However, for probabilities higher than 0.6, the slope of the performance remains rather stable. In order to define more exactly the best values for these parameters, we conducted another experiment, shown at Fig. 5. In this experiment we tried to clarify which is the best combination of the two parameters. According to the graph, the algorithm performs better when the number of crossovers and mutations tends to be equal. It can be observed in Fig. 5 that the mutation action results in reduced makespan compared to crossover, thus having a greater impact on the overall algorithm. As a result, for the rest of the experiments, we choose to set the values of crossover and mutation equal to 0.7.

The next parameters we examined on the GA were the number of generations and the population size. These parameters define the extend that the algorithm is going to search for a near-optimal solution. As their number increases, a wider part of the solution space is searched, and therefore, the probability of finding a better solution is also increasing. However, increasing recklessly the number of these parameters cannot be considered as a viable strategy, because it leads to enormous and unacceptable execution time. Hence it is important to choose the referred parameters in a way that both quality and acceptable time are satisfied. According to the results depicted in Fig. 6, the increase in the number of population and generations is indeed helping the performance, though it can be observed that makespan is minimised for population and generation values between 150 and 200, respectively.

ACO on the other hand, as we have already mentioned in the previous section, follows a swarm-based strategy, comprised of many agents trying to find the optimal execution order of VNFs. The most important factors in the specific algorithm are the number of iterations, that is how many times the agents will run, and the pheromone decay rate, which defines the rate of system memory for previous runs of the agents. In order to examine the impact of the above parameters on the overall performance, we run the algorithm for multiple iterations and for specific decay rates (0, 0.3, 0.7, 1) covering its whole value space. According to the results presented in Fig. 7, decay rate plays an especially important role on the performance of the algorithm. More specifically, better results seem to come out when rate is close to 0.7, while at the same time, both full-memory (rate equal to 0) and no-memory (rate equal to 1) schemes downgrade the performance. Concerning the number of iterations, it can be deducted from the graph that their increment improves the results. However, makespan seems to stabilize after 4500 iterations. As a result, keeping the iterations around 4500 guarantees satisfying results at acceptable time.

A factor we had not included in our previous work [15], was whether the characteristics of the problem play some role in choosing the best parameters in each algorithm. To fill that blank, we run GA and ACO for a [TeX:] $$20 \times 5$$ JSS problem. The [TeX:] $$20 \times 5$$ problem is consisted of 20 slice requests, with 5 VNFs each, that must be allocated in 5 hosts. While the number of different VNFs is the same as the [TeX:] $$10 \times 10$$ problem, however, the distribution of VNFs to hosts has changed. Following the same approach with the previous series of experiments, we first examine the impact of GA’s probability parameters on the makespan. The results in Fig. 8, show a small difference compared to the corresponding graph in [TeX:] $$10 \times 10.$$ While the increment in mutation probability improves the performance, crossover probability does not influence the results that much. The above can be observed in Fig. 9 as well, where the change in crossover probability (blue line) does not have any crucial effect on the makespan. Due to this fact, as it is also depicted in Fig. 9, the total absence of crossover probability (green line) is close to the condition that crossover and mutation probabilities are equal (red line).

Generation and population parameters seem to follow the same pattern in [TeX:] $$20 \times 5$$ problem as in [TeX:] $$10 \times 10.$$ However, it can be observed in Fig. 10 that the threshold defining the result stabilization has been slightly increased to 200 generations while the population parameter seems to have less effect on the makespan than in the [TeX:] $$10 \times 10$$ problem.

The execution of ACO for [TeX:] $$20 \times 5$$ problem brought up an interesting result, shown in Fig. 11. While in the [TeX:] $$10 \times 10$$ problem, the performance improved when the decay rate was between 0.3 and 0.7, in [TeX:] $$20 \times 5$$ the situation has been inverted. The total absence of decay seems to minimise the makespan, which means that for a limited number of machines it is better to keep a full-memory strategy among run of the agents.

B. Overall Assessment and Insights

To assess which metaheuristic approach fits better to this kind of scheduling problems, Table IV depicts the optimal makespan for three sizes of the target problem [TeX:] $$(10 \times 10, 20 \times 5, \text { and } 20 \times 20 \text { ) }.$$ Those optimal values are compared to the actual makespan values for the two target algorithms. Both approaches seem to achieve near-optimal results. The deviation between the optimal and the actual results of the algorithms is related to the number of slice requests. As it can be observed, for the [TeX:] $$10 \times 10$$ problem, both GA and ACO, can achieve a close to optimal makespan. According to the experiments, GA leads to slightly better results than ACO. Specifically, GA offers approximately an 8% performance improvement but with longer execution times in exchange.

Based in the theoretical study and the performance evaluation results:

While both evaluation-based and swarm-based algorithms perform well on small and medium problems (less than 100 VNFs), they are inappropriate for bigger problems (more than 100 VNFs) due to the high increase of their execution time. As a countermeasure, ACO, due to its agent-based architecture, can be efficiently implemented as a distributed /multi-threaded application to reduce the execution time.

The number of slice requests plays more crucial role on the algorithms’ performance than the number of machines used to host the VNFs. This observation reveals the critical role of the way that the requests for network service deployment are organized for feeding the scheduling process. In other words, the performance can be increased if we split the input pool of requests and address them in small groups rather by adding more hosts in the system.

ACO approach can be easily adapted to function on dynamic arrival of network slice requests, in contrast to GA. This is because the GA approach starts from a random solution from a given number of requests, while the ACO progressively builds a result, which allows the addition of more requests by dynamically expanding the representation graph that is used for the ants’ local search.

In terms of complexity, the nature of metaheuristic algorithms does not facilitate an absolute way of comparing them. Indeed the complexity in both the selected algorithms is affected by their tuning parameters. As such, the GA’s complexity could be expressed as:

and ACO’s as:

To better reflect the relation between complexity and efficiency for the selected metaheuristic algorithms, Table IV includes the tuning parameters used for each experiment.

VI. CONCLUSION

Service creation time is one of the fundamental KPIs in 5G systems, since it can have a great impact on the overall system performance, and eventually to the quality of the services that an operator provides to vertical industries. The optimisation of the service creation time is a challenging task, as it can be affected by multiple parameters that reside at the implementation choices, as well as at the management methods (algorithmic processes) that are used. In this context, we examined metaheuristic methods as enablers for resolving the VNF scheduling under various service requests in a 5G system. The evaluation process revealed that metaheuristic algorithms can efficiently contribute towards the minimization of service creation time. From the various categories of metaheuristic algorithms, the evolution-based approach (in our case the GA) provides an overall better performance than the swarmbased one (in our case the ACO). However, considering that the slice set-up process is be real-time process, swarm-based algorithms, such as the ACO, have the advantage of short execution time, compared to the evolution-based ones.

Although metaheuristics seem to be an efficient solution for VNF scheduling problem, the analysis revealed some drawbacks, such as their low-fitting to dynamic scheduling (on-line) problems (that is the case when new network slice requests arrive and have to be scheduled on-line). Building on top of this study, we plan to relax the assumption on the way that the slice requests arrive and examine machine learning approaches toward an automated alignment of the scheduling to the dynamically changing input.