2024/2/16

Outline• Introduction

Adaptive Network Slicing Control Method
for Unpredictable Network Variations
using Quality-Diversity Algorithms• Evaluation• Background• Problems• Purpose and method• Method• The formulation of VNE Problem• The details of MAP-Elites• The design of feature space• The encoding of solutions• The definition of fitness

Amato Otsuki
Graduate School of Information Science and Technology,
Osaka University Osaka, Japana-otsuki@ist.osaka-u.ac.jp• Evaluation method• Algorithms used for comparison• Purpose and method• Results• Discussion• Conclusion and future work2112Background• The spread of various internet services• Growing need to provide a flexible network
Network Slices (Virtual Networks)• Network slicing• Construction multiple virtual networks (VNs)
on a substrate network (SN)Introduction• Virtual Networking Embedding (VNE)

Substrate Network• The resource allocation problem todetermine the mapping between elementsof SN and VNs
Fig. The model of network slicing

43

3

4ProblemsPurpose and method• VNE problem is NP-hard• Solving VNE adaptively to environmental change• It is difficult to derive the optimal solutionin the modern huge network• Many heuristics have been proposed

Morebandwidth• Utilizing the previous solutions
to develop a new solution immediately

More CPU• Genetic algorithm (GA)• Dynamic environment in practical use• Based on a model of organism evolution• Conventional GAs tend to decrease diversity• Changes of network condition, user request, …

• Need to solve VNE adaptively• To derive a feasible solution after such changes
utilizing previous solutions

Throughput
degradation• Quality-Diversity (QD) algorithm

Servererror

Previous solutions

Selection
CrossoverMutationNext solutions• The methods proposed to generate
diverse and superior solutions• We focused on one of them, MAP-Elites

Fig. Changes of VNE environment

Fig. Genetic algorithm
55661

2024/2/16

The formulation of VNE Problem• SN and VN are modeled as undirected graphs• SN: 𝐺𝑆 = 𝑁𝑆 , 𝐿𝑆 , 𝑅𝑆𝑛 , 𝑅𝑆𝑙• VN: 𝐺𝑉 = 𝑁𝑉 , 𝐿𝑉 , 𝑅𝑉𝑛 , 𝑅𝑉𝑙• A solution of VNE is mapping 𝑀• 𝑀: 𝑁𝑉 , 𝐿𝑉 → 𝑁𝑆′ , 𝑃𝑆′ , 𝑁𝑆′ ⊂ 𝑁𝑆
• 𝑃𝑆′ is a subset of substrate paths• Resource requirements must be satisfiedMethod• e.g. 𝑅𝑉𝑛 𝑛1𝑉 < 𝑅𝑆𝑛 (𝑛4𝑆 )• 𝐺𝑉 and 𝑁𝑆′ , 𝑃𝑆′ must have the same topology

Fig. Example of VNE

8778

The details of MAP-Elites

The design of feature space

1.
2.
3.
4.
5.

Generate an initial population at random
Select an individual from population at random
Mutate a copy of the selected individual
Evaluate fitness and features of a new individual
It compete with the existing individual in the cell(return to 2)

Feature 1• The feature space consists of user-designed variables
and is divided into cells at a certain granularity• Output the best solution within each cell

• The algorithm is below:• Important to search for solutions efficiently

Feature 2

4.

• The dimension of feature space is lower than that of problem space• Diverse feasible solutions should be spread in feature space
2.

Feature 2• Features we designed are below:

5.

• Feature 1: The total amount of substrate node resources
allocated to virtual nodes• Feature 2: The total hops of the substrate paths
assigned to virtual links

0100101010010101
3.

Feature 1• Search for diverse solutions in a feature space

Fig. Feature space• We also intend to separate the node and path selections
into each feature

0100101011010101
Fig. MAP-Elites algorithm
991010The encoding of solutions

The definition of fitness• Encode a mapping into a genotype• The population evolves so that its fitness becomes higher• Encode the correspondences between
elements of SN and VN directly• Define fitness to direct the evolution appropriately

𝑅𝑉𝑛 𝑛2𝑉 = 3.0• Fitness: 𝐹 𝑀 = 𝑅 𝑀 − 𝜆𝑃 𝑀

• Limit the search space

violation• 𝑅 𝑀 : total amount of residual resources• To make it possible to encode a mappingwith a finite fixed gene length• A substrate path is selected from only
the k-shortest paths• Evolve to decrease usage of substrate resources• 𝑃 𝑀 : penalty term
• The difference between resource requirements
and resource allocated actually• Evolve to satisfy resource requirements(𝜆 is set adequately large)

𝑅𝑆𝑛 𝑛2𝑆 = 2.6

𝑃 𝑀 = 3.0 − 2.6
Fig. Resource requirement violation

Fig. Encoded solution

111112122

2024/2/16

Evaluation method• We conducted computer simulations of dynamic VNE problem• Examine the effect of using QD algorithm

VN• Compare MAP-Elites with conventional GAs and another QD algorithm• Embed a single VN into a SN in each simulation

SN• A specific substrate node failure happens at a certain time

100 pairs of30 times for each pair

• Simulations are performed 30 times for 100 different settings

Evaluation• Compare the means of the metrics below
after the environmental change

embedSimulation duration
Node failure• Acceptance rate: the percentage of cases
Acceptance rate
where a feasible solution is found in the duration
Immediate acceptance rate
• Immediate acceptance rate: the percentage of cases
where a feasible solution exists in the population at the environmental change
1413

13

14

Algorithms used for comparisonResults• The algorithms we used for comparison are below:• Acceptance rate

• Elitism-based GA (EGA)• Immediate acceptance rate

• No major difference• Only SSGA is lower because of
the decrease of diversity• A basic GA that carries over the best individual to the next population for its steady evolution• Steady State GA (SSGA)• A variant of GA that replaces the worst individual with a new individual in the population• Not generating a new population so that there is no generation gap• This characteristic is in common with MAP-Elites• The QD algorithms are superior tothe others• No major difference between the twometrics in QD algorithms• Novelty Search and Local Competition(NSLC)• One of the QD Algorithms• Multi-objective optimization for novelty and local competitiveness• Novelty: the average Euclidean distance to the k nearest neighbors on the feature space• Local competitiveness: the relative fitness in the k nearest neighbors• SSGA is used for optimization in this simulation

15151616Discussion

Conclusion and future work

• Solution diversity is effective for dynamic VNE• We proposed the method of dynamic VNE using MAP-Elites• The difference of acceptance rates
between EGA and QD algorithms is small• The diverse and superior solutions foundby QD algorithms make possible to adapt
for environmental changes more rapidly• The mechanism of evolution enables to adapt to environmental changes• The solution diversity of QD algorithms leads to immediate adaptation• The failure tolerance due to finding solutions independent of important nodes• Future works• Tolerance of methods using QD algorithms• Better design of feature space to search for solutions more efficiently• Developing the method assuming more practical scenario• The extent of performance degradation in the casewhen the substrate nodes with larger resources become
unavailable is small in QD algorithms• Solutions independent of substrate nodes
with larger resources are found in QD algorithms
171718183