NMRG P. Martinez-Julia, Ed.
Internet-Draft NICT
Intended status: Informational D. Lopez
Expires: January 10, 2022 TID
July 09, 2021
VEGA: A Genetic Method for Planning Virtual Network Embedding
Configurations
draft-pedro-nmrg-vega-network-embedding-00
Abstract
The number of elements composing virtual networks (VN), together with
the number of elements in the substrate networks (SN), makes
unfeasible to obtain in a short time an optimum configuration for the
assignation of elements from the VN to the SN. Here we present VEGA,
standing for Virtual network Embedding method based on a Genetic
Algorithm. It defines a particular strategy and heuristic to provide
configurations for network embedding that are close to the optimum in
a short time.
Status of This Memo
This Internet-Draft is submitted in full conformance with the
provisions of BCP 78 and BCP 79.
Internet-Drafts are working documents of the Internet Engineering
Task Force (IETF). Note that other groups may also distribute
working documents as Internet-Drafts. The list of current Internet-
Drafts is at https://datatracker.ietf.org/drafts/current/.
Internet-Drafts are draft documents valid for a maximum of six months
and may be updated, replaced, or obsoleted by other documents at any
time. It is inappropriate to use Internet-Drafts as reference
material or to cite them other than as "work in progress."
This Internet-Draft will expire on January 10, 2022.
Copyright Notice
Copyright (c) 2021 IETF Trust and the persons identified as the
document authors. All rights reserved.
This document is subject to BCP 78 and the IETF Trust's Legal
Provisions Relating to IETF Documents
(https://trustee.ietf.org/license-info) in effect on the date of
publication of this document. Please review these documents
Martinez-Julia & Lopez Expires January 10, 2022 [Page 1]
Internet-Draft Planning Virtual Network Embedding July 2021
carefully, as they describe your rights and restrictions with respect
to this document. Code Components extracted from this document must
include Simplified BSD License text as described in Section 4.e of
the Trust Legal Provisions and are provided without warranty as
described in the Simplified BSD License.
Table of Contents
1. Introduction . . . . . . . . . . . . . . . . . . . . . . . . 2
2. Terminology . . . . . . . . . . . . . . . . . . . . . . . . . 3
3. Background . . . . . . . . . . . . . . . . . . . . . . . . . 3
3.1. Virtual Computer and Network Systems . . . . . . . . . . 3
3.2. SDN and NFV . . . . . . . . . . . . . . . . . . . . . . . 3
3.3. Management and Control . . . . . . . . . . . . . . . . . 4
3.4. Virtual Network Embedding Problem . . . . . . . . . . . . 5
4. Genetic Method for Finding Network Embedding Configurations . 5
4.1. Resolving the VNEP . . . . . . . . . . . . . . . . . . . 5
4.2. Using VEGA to Get a Configuration Close to the Optimum . 5
4.3. Building an Embedding Configuration . . . . . . . . . . . 7
4.4. Basic Heuristic Function . . . . . . . . . . . . . . . . 8
4.5. Incremental Heuristic Function . . . . . . . . . . . . . 8
5. Relation to Other IETF/IRTF Initiatives . . . . . . . . . . . 9
6. IANA Considerations . . . . . . . . . . . . . . . . . . . . . 9
7. Security Considerations . . . . . . . . . . . . . . . . . . . 10
8. Acknowledgements . . . . . . . . . . . . . . . . . . . . . . 10
9. References . . . . . . . . . . . . . . . . . . . . . . . . . 10
9.1. Normative References . . . . . . . . . . . . . . . . . . 10
9.2. Informative References . . . . . . . . . . . . . . . . . 10
Appendix A. Appendix 1 . . . . . . . . . . . . . . . . . . . . . 11
Authors' Addresses . . . . . . . . . . . . . . . . . . . . . . . 11
1. Introduction
In this document we describe VEGA, which stands for Virtual network
Embedding method based on a Genetic Algorithm. It, therefore, is a
method for finding configurations for embedding the elements of a
Virtual Network (VN) in the elements of a Substrate Network (SN) by
using an algorithm following the Genetic Programming (GP)
methodology. This is needed because the number of combinations of
elements from the VN and SN is so big that it is unfeasible to obtain
the optimum configuration in a short time.
This limitation is resolved by using some suboptimal method for
searching the solution, as it is the case of an algorithm based on
GP. However, a particular strategy and heuristic should be used to
ensure that provided configurations are close to the optimum within a
short time. Therefore, the time boundaries for the method presented
here are low and the quality of the configurations is high. This
Martinez-Julia & Lopez Expires January 10, 2022 [Page 2]
Internet-Draft Planning Virtual Network Embedding July 2021
quality is required for the correct operation of current and future
networks, particularly those that must be adapted to dynamic needs.
2. Terminology
The key words "MUST", "MUST NOT", "REQUIRED", "SHALL", "SHALL NOT",
"SHOULD", "SHOULD NOT", "RECOMMENDED", "MAY", and "OPTIONAL" in this
document are to be interpreted as described in [RFC2119].
3. Background
3.1. Virtual Computer and Network Systems
The continuous search for efficiency and cost reduction to get the
most optimum exploitation of available resources (e.g. CPU power and
electricity) has conducted current physical infrastructures to move
towards virtualization infrastructures. Also, this trend enables end
systems to be centralized and/or distributed, so that they are
deployed to best accomplish customer requirements in terms of
resources and qualities.
One of the key functional requirements imposed to computer and
network virtualization is a high degree of flexibility and
reliability. Both qualities are subject to the underlying
technologies but, while the latter has been always enforced to
computer and network systems, flexibility is a relatively new
requirement, which would not have been imposed without the backing of
virtualization and cloud technologies. Such flexibility is exploited
by allowing management systems, such as presented in "Anticipating
minimum resources needed to avoid service disruption of emergency
support systems [ICIN-2018]," to configure the computer and network
systems.
3.2. SDN and NFV
SDN and NFV are conceived to bring high degree of flexibility and
conceptual centralization qualities to the network. On the one hand,
with SDN, the network can be programmed to implement a dynamic
behavior that changes its topology and overall qualities. Moreover,
with NFV the functions that are typically provided by physical
network equipment are now implemented as virtual appliances that can
be deployed and linked together to provide customized network
services. SDN and NFV complements to each other to actually
implement the network aspect of the aforementioned virtual computer
and network systems.
Although centralization can lead us to think on the single-point-of-
failure concept, it is not the case for these technologies.
Martinez-Julia & Lopez Expires January 10, 2022 [Page 3]
Internet-Draft Planning Virtual Network Embedding July 2021
Conceptual centralization highly differs from centralized deployment.
It brings all benefits from having a single point of decision but
retaining the benefits from distributed systems. For instance,
control decisions in SDN can be centralized while the mechanisms that
enforce such decisions into the network (SDN controllers) can be
implemented as highly distributed systems. The same approach can be
applied to NFV. Network functions can be implemented in a central
computing facility, but they can also take advantage of several
replication and distribution techniques to achieve the properties of
distributed systems. Nevertheless, NFV also allows the deployment of
functions on top of distributed systems, so they benefit from both
distribution alternatives at the same time.
3.3. Management and Control
The introduction of virtualization into the computer and network
system landscape has increased the complexity of both underlying and
overlying systems. On the one hand, virtualizing underlying systems
adds extra functions that must be managed properly to ensure the
correct operation of the whole system, which not just encompasses
underlying elements but also the virtual elements running on top of
them. Such functions are used to actually host the overlying virtual
elements, so there is an indirect management operation that involves
virtual systems. Moreover, such complexities are inherited by final
systems that get virtualized and deployed on top of those
virtualization infrastructures. A key to address them, from the
architecture point of view, is to define a whole architecture, such
as [ETSI-NFV-MANO], and complement it with required protocols,
interfaces, and algorithms, such as the algorithm defined here, to
ensure widespread of management techniques and qualities.
In parallel, virtual systems are empowered with additional, and
widely exploited, functionality that must be managed correctly. It
is the case of the dynamic adaptation of virtual resources to the
specific needs of their operation environments, or even the
composition of distributed elements across heterogeneous underlying
infrastructures, and probably providers. Taking both complex
functions into account, either separately or jointly, makes clear
that management requirements have greatly surpassed the limits of
humans, so automation has become essential to accomplish most common
tasks. In addition, getting and analyzing telemetry
[I-D.ietf-opsawg-ntf] gains a key relevancy in the management and
control planes.
Martinez-Julia & Lopez Expires January 10, 2022 [Page 4]
Internet-Draft Planning Virtual Network Embedding July 2021
3.4. Virtual Network Embedding Problem
The Virtual Network Embedding Problem (VNEP) targets the construction
of a configuration that assigns nodes from the SN (NSNs) to a VN. A
configuration is, therefore, a map from VNF instances to NSNs. It
must ensure that all nodes and links from the VN are embedded onto
the SN. These solutions must ensure that the goals set by the
tenants of both the VN and the SN are respected. However, it is well
known that conventional methods to resolve the VNEP cannot be both
subject to find the optimum and resolved in polynomial time, as
discussed in "Automation and Multi-Objective Optimization of Virtual
Network Embedding [IEEE-IM-2021]". The algorithm presented here
provides a solution to the VNEP that is close to the optimum.
4. Genetic Method for Finding Network Embedding Configurations
4.1. Resolving the VNEP
In this section we describe VEGA, a method to get a solution to the
VNEP that is close to the optimum. To do so, it incorporates a new
algorithm, which has been designed using the GP methodology. It uses
a particular heuristic and overall strategy to provide the resulting
method with the ability to find a basic configuration and improve it,
incrementally and iteratively, until some stop condition is met,
generally after a number of iterations.
4.2. Using VEGA to Get a Configuration Close to the Optimum
By using an heuristically driven search approach, with most
heuristics, an algorithm can be stuck into a local optimum. Although
most of the time such kind of optimums are good enough for most VN
embeddings, they can provide some disparate configurations. To
prevent such situation, GP focuses on the iterative generation of
configurations which have some degree of randomness from one
iteration to the next, so disparate solutions are also considered,
breaking any local optimum barrier.
VEGA exploits the benefits of such randomness by including the
creation method of generating new solutions, as detailed below. This
extends the search space beyond the path guided by the heuristic
function and allows the algorithm to find better optimal
configurations, closer to the global optimum. Moreover, the
algorithm builds the configurations incrementally, following DP
methodology, so the most relevant partial configurations are cached
for allowing the find procedure to avoid re-calculating all of them
when exploring different paths.
Martinez-Julia & Lopez Expires January 10, 2022 [Page 5]
Internet-Draft Planning Virtual Network Embedding July 2021
procedure VEGA
C0 = MakeConf (Empty, F, S)
Gi = [C0]
while N > 0 do
Gjm = Mutate (Gi, L)
Gjb = Breed (Gi, L)
Gjc = Create (Gi, L)
Gj = (Gjm union Gjb union Gjc) - Gi
SortByH (Gj)
PickHomo (Gj, L)
Gi = Gi union Gj
N = N - 1
end while
SortByH (Gi)
return First (Gi)
end procedure
Main algorithm of VEGA.
This algorithm relies on an inner algorithm, MakeConf, to build a
basic configuration. As described below, it provides a configuration
that accomplishes the overall objectives but, as it is greedy, it is
most probably stuck in a local optimum. At first, VEGA begins
building a basic configuration for the current set of VN elements (F)
and SN elements (S), specifying that the base configuration is empty.
This configuration is considered to be a local optimum. To go beyond
it, VEGA uses three functions to generate new configurations to
consider. They are Mutate, Breed, and Create.
Mutate gets each configuration from the input and changes some
assignation of F to S randomly. Breed gets pairs of configurations
from the input and creates a new configuration for each pair by
including the odd or even assignations from the "parents" into the
"child" configurations. Finally, Create builds new configurations by
randomly assigning elements of F to elements of S. Each function
generates, at most, the amount of new configurations specified (L).
All new and old configurations are unified together in a set and the
previously considered configurations are removed from it. Then, the
set is sorted by incremental value of the heuristic function (H) and
a subset is picked by choosing L configurations homogeneously,
although ensuring that the first (best configuration, according to H)
is included. The new set is unified with the set of configurations
previously generated and a new loop is done. After N iterations the
loop exits. The resulting set of configurations is sorted by H and
the first configuration (best) is returned.
Martinez-Julia & Lopez Expires January 10, 2022 [Page 6]
Internet-Draft Planning Virtual Network Embedding July 2021
4.3. Building an Embedding Configuration
A typical algorithm for implementing the inner function of finding
associations of VN elements to SN elements, viz. configurations,
would loop among all of them and generate all possible
configurations. However, it is not just unpractical and generally
unfeasible to be accomplished on polynomial time for bigger networks,
but also inefficient because there would be a lot of configurations
that are irrelevant and/or totally deviated from the objective.
Instead, VEGA relies on a greedy version of such exploration
algorithm. Although the search is not exhaustive, each iteration of
this algorithm chooses the best alternative, so it quickly finds some
local optimum.
procedure MakeConf (Ci, F, S)
Cj = Ci
C = Empty
for all fi in F do
for all si in S do
C = C union [Cj union (fi, si)]
end for
SortByH (C)
Cj = First (C)
end for
return Cj
end procedure
Algorithm for building a configuration, viz. a set of assignations of
VN elements to SN elements.
This algorithm works as follows. First, the provided base
configuration is considered, although it can be the empty
configuration. Then, a new set of configurations is generated by
assigning each element of F to every element of S. This set is
sorted by H and the first configuration (best) is chosen to be used
for attaching the next assignation of F to S in the next iteration.
This highly reduces the complexity of this algorithm, in terms of
number of instructions. It does not provide the optimum, not even
close local optimum, but it is oriented by H, so when combined with
the overall procedure of VEGA, as described above, a configuration
that is very close to, or equal to, the global optimum can be
reached. After all elements of F have been assigned, the resulting
configuration is returned.
Martinez-Julia & Lopez Expires January 10, 2022 [Page 7]
Internet-Draft Planning Virtual Network Embedding July 2021
4.4. Basic Heuristic Function
The heuristic used in the method is a key aspect since it determines
how efficient and fast is the method iterating towards a solution
that is as close as possible to the optimum. There are two
definitions for the heuristic. The first, presented here, is in the
general form, as follows:
function H (c)
result = 0
for all (_, si) in c do
result = result + PathLenTo (si)
end for
for all sj in S do
q = 0
for all (_, sk) in c do
if sk == sj then
q = q + 1
end if
end for
result = result + Z ^ q
end for
return result
end function
Iterative function to calculate the heuristic value of a
configuration.
A value is assigned to a configuration in base of the placement of
VNF instances, depending on the co-location of several instances on
the same node of the SN and the length of the path from the gateway
to the node of the SN where certain VNF instance has been placed. It
is calculated by adding the length of all paths from the gateway to
the node from S that is included in a configuration, and
exponentiating a value (Z) to the amount of elements that are co-
located in the same substrate node.
4.5. Incremental Heuristic Function
A new heuristic is derived form the basic heuristic to meet the
requirements of the incremental strategy used by the algorithm. It,
therefore, defines a value for a configuration by re-using the value
obtained from a previous configuration. Therefore, the definition of
the heuristic function is as follows:
Martinez-Julia & Lopez Expires January 10, 2022 [Page 8]
Internet-Draft Planning Virtual Network Embedding July 2021
function H (Cj)
Ci = Cj - (fj, sj)
result = H (Ci)
q = 0
for all (_, sk) in Ci do
if sk == sj then
q = q + 1
end if
end for
result = result - Z ^ q
result = result + PathLenTo (sj)
r = 0
for all (_, sk) in Cj do
if sk == sj then
r = r + 1
end if
end for
result = result + Z ^ r
return result
end function
Recursive function to calculate the heuristic value of a
configuration.
It has the same considerations but relies on calculations already
done and stored in a table, following the Dynamic Programming (DP)
methodology. The addition of the cost derived from the new paths is
straightforward, but the addition of the cost of co-locating VNF
instances is not and must be calculated by subtracting first the
previous value. Therefore, the function begins with the value of H
for the previous configuration (Ci), which is equivalent to the new
configuration (Cj) after removing the last element ((fj, sj)). Then,
it calculates the amount of co-located elements in Ci and subtracts
it to the result. Then, it acts as a single iteration in the
previous definition of H to add the values of the new elements ((fj,
sj)). Finally, it returns the result.
5. Relation to Other IETF/IRTF Initiatives
TBD.
6. IANA Considerations
This memo includes no request to IANA.
Martinez-Julia & Lopez Expires January 10, 2022 [Page 9]
Internet-Draft Planning Virtual Network Embedding July 2021
7. Security Considerations
The main security consideration is tied to the source of the data
provided to the algorithm for both knowing the functions forming the
VN and the nodes forming the SN. It is up to the administration
endpoint to ensure such information is addressed securely.
8. Acknowledgements
TBD.
9. References
9.1. Normative References
[RFC2119] Bradner, S., "Key words for use in RFCs to Indicate
Requirement Levels", BCP 14, RFC 2119,
DOI 10.17487/RFC2119, March 1997,
<https://www.rfc-editor.org/info/rfc2119>.
9.2. Informative References
[ETSI-NFV-MANO]
ETSI NFV GS NFV-MAN 001, "Network Functions Virtualisation
(NFV); Management and Orchestration", 2014.
[I-D.ietf-opsawg-ntf]
Song, H., Qin, F., Martinez-Julia, P., Ciavaglia, L., and
A. Wang, "Network Telemetry Framework", draft-ietf-opsawg-
ntf-07 (work in progress), February 2021.
[ICIN-2018]
P. Martinez-Julia, V. P. Kafle, and H. Harai,
"Anticipating minimum resources needed to avoid service
disruption of emergency support systems, in Proceedings of
the 21th ICIN Conference (Innovations in Clouds, Internet
and Networks, ICIN 2018). Washington, DC, USA: IEEE, 2018,
pp. 1--8", 2018.
[IEEE-IM-2021]
P. Martinez-Julia, V. P. Kafle, and H. Asaeda, "Automation
and Multi-Objective Optimization of Virtual Network
Embedding, in Proceedings of the IFIP/IEEE International
Symposium on Integrated Network Management", May 2021.
Martinez-Julia & Lopez Expires January 10, 2022 [Page 10]
Internet-Draft Planning Virtual Network Embedding July 2021
Appendix A. Appendix 1
TBD.
Authors' Addresses
Pedro Martinez-Julia (editor)
NICT
4-2-1, Nukui-Kitamachi, Koganei
Tokyo 184-8795
Japan
Phone: +81 42 327 7293
Email: pedro@nict.go.jp
Diego R. Lopez
Telefonica I+D
Don Ramon de la Cruz, 82
Madrid 28006
Spain
Email: diego.r.lopez@telefonica.com
Martinez-Julia & Lopez Expires January 10, 2022 [Page 11]