Method for optimizing the quality of network resources and the number of services likely to use said resources

Abstract

The invention relates to a method for optimizing the quantity of network resources and the number of services likely to use said resources in a virtualized telecommunications network comprising the following steps of: evaluating similarities between the services likely to use said resources in terms of the virtual network functions VNFs required for the instantiation of each service, gathering services as a function of their similarities in order to maximize resource sharing, calculating additional resources to accept services awaiting instantiation; running an admission control scheme to accept or reject requests for the instantiation of new services.

Claims

1. A method of optimizing the quantity of network resources and the number of services likely to use said resources in a virtualized telecommunications network characterized by the following steps of: evaluating the similarities between the services likely to use said resources in terms of the virtual network functions (VNF) required for the instantiation of each service, gathering services into network slices according to their similarities in order to maximize resource sharing, calculating additional resources to accept services awaiting instantiation, and, running an admission control scheme to accept or reject requests for the instantiation of new services.

2. The method according to claim 1, wherein each service is instantiated in a logic network slice (NSI) comprising at least two sets of virtual network functions, namely a set of network functions K.sup.R which correspond to a radio access network RAN and a set of network functions K.sup.C which correspond to a core network.

3. The method according to claim 2 further comprising the steps of: defining a set =.sup.R∪.sup.C={NF.sub.1, . . . , NF.sub.K} representing the set of network functions K=(K.sub.R+K.sub.C) likely to be instantiated in the telecommunications network, and, for a given logic service n awaiting instantiation, defining a list D.sub.n containing the network functions required for the instantiation of this service and a description of the interactions between said network functions and parameters describing their respective configurations, defining a set of instantiated network slices comprising network functions shared between at least two network services and network functions specifically dedicated to a network service, comparing the network functions required by the network service awaiting instantiation with those of the set of NSIs likely to serve the service awaiting instantiation with a minimum of additional network resources, evaluating the similarities between the network functions being compared, and, based on the similarities evaluated, selecting the NSI that shares the greatest number of network functions with the service awaiting instantiation, if no NSI shares network functions with the service awaiting instantiation, creating a new NSI, consisting exclusively of network functions specifically dedicated to the service awaiting instantiation.

4. The method according to claim 3, wherein, for each service awaiting instantiation, n∈={0, 1, . . . , N}, N representing an integer N≥0, is defined a subset D.sub.n of the set =.sup.R∪.sup.C={NF.sub.1, . . . , NF.sub.K} containing the network functions required for its instantiation and a set of configuration parameters .sub.n,k for each network function, and, to indicate the network functions that make up the n-th request D.sub.n, is defined (4) the vector λ.sub.n∈{0,1}.sup.K, the k-th input of which is defined by: ${\lambda }_{n,k}=\{,\forall {\mathrm{NF}}_k\in .$ then, for each network function NF.sub.k belonging to D.sub.n, the associated configuration parameters are represented as a set of J binary vectors as follows:
.sub.n,k={l.sub.n,k,1,l.sub.n,k,2, . . . ,l.sub.n,k,J}, then the configuration parameters are mapped with a parameter d.sub.n,k,r representing the quantity of communication resources, a parameter d.sub.n,k,c representing the computing resources of the calculation, and a parameter d.sub.n,k,m representing the cloud storage capacity required by the network function NF.sub.k of the n-th service instantiation request using a template consisting of a static and a dynamic part:
d.sub.n,k,r=ρ.sub.k+f.sub.k,r(.sub.n,k),
d.sub.n,k,c=χ.sub.kf.sub.k,c(.sub.n,k),
d.sub.n,k,m+μ.sub.k+f.sub.k,m(.sub.n,k), where ρ.sub.k, χ.sub.k and μ.sub.k represent the minimum quantity of resources required to activate a given network function NF.sub.k∈D.sub.n, and f.sub.k,m(.sub.n,k), f.sub.k,c(.sub.n,k), and f.sub.km(.sub.n,k) representing the additional quantity of resources required, which depends on the configuration parameters, .sub.n,k of the network function NF.sub.k, and the total request for communication resources, computing resources and cloud storage resources for said n-th request is calculated by the following formula:
T.sub.n=(d.sub.n,r,d.sub.n,c,d.sub.n,m), where d.sub.n,r=Σ.sub.NF.sub.k.sub.∈.sub.nd.sub.n,k,r, d.sub.n,c=Σ.sub.NF.sub.k.sub.∈.sub.nd.sub.n,k,c and d.sub.n,m=Σ.sub.NF.sub.k.sub.∈.sub.nd.sub.n,k,m.

5. The method according to claim 4, wherein evaluating the similarities between the network functions required by a network slice awaiting instantiation and those of the set of NSIs already instantiated is obtained by calculating a Jaccard similarity parameter by the following formula: ${\Lambda }_{i,n}=\frac{{\lambda }_n{\lambda }_i}{||{\lambda }_n||+||{\lambda }_i||-{\lambda }_n{\lambda }_i},i\in ,$ where λ.sub.i indicates the network functions that make up the NSI i∈ already instantiated, and ∥⋅∥ representing a Euclidean norm operator.

6. The method according to claim 5, wherein, if none of the NSIs already instantiated is adapted to the service awaiting instantiation, a new NSI is defined.

7. The method according to claim 5, wherein, on the basis of the similarities calculated, is selected the already instantiated NSI i*∈ which shares the largest number of network functions VNFs with the network service awaiting instantiation n: $i^{*}=\underset{i\in ℬ}{{\mathrm{argmax\Lambda }}_{i,n}.}$ then, n is temporarily added to the list of services related to NSI i*.

8. The method according to claim 7, wherein, for each pair of network services n, n′ ∈R.sub.i*,k, where R.sub.i*,k represents the set of services included in the NSI i*∈ which require the network function NF.sub.k∈.sub.n, the similarity between a first set of configuration parameters .sub.n,k and a second set of configuration parameters .sub.n′,k is defined as follows: $C\left({ℒ}_{n,k},{ℒ}_{n^{\prime },k}\right)=\underset{j=1}{\overset{J}{.Math.}}h\left(l_{n,k,j},l_{n^{\prime },k,j}\right),$ where J is the number of parameters of the network function NF.sub.k and h(⋅) is the cosine similarity function (or cosine metric) which allows calculation of the similarity between two N-dimensional vectors by determining the cosine of the angle between them: $h\left(l_{n,k,j},l_{n^{\prime },k,j}\right)=\frac{l_{n,k,l}{l}_{n^{\prime },k,j}}{||l_{n,k,j}||||l_{n^{\prime },k,j}||}.$

9. The method according to claim 8, wherein for each network function NF.sub.k∈.sub.n, of the service n, the quantity of resources that can be pooled between the different network services instantiated in the NSI i* and the new service n through the parameter σ*.sub.n,k,j are evaluated as follows: ${\sigma }_{n,k,j}^{*}=\underset{n^{\prime }\ne n\in {ℛ}_{i,k}}{\max }C\left({ℒ}_{n,k},{ℒ}_{n^{\prime },k}\right),i\in ,$ where the index j represents either communication resources, computing resources or storage resources.

10. The method according to claim 9, wherein the resources required to instantiate each function of the service n are calculated via the NSI i* using a template consisting of a static and a dynamic part:
d′.sub.n,k,r=ρ.sub.kβ(σ*.sub.n,k,j)+(1−σ*.sub.n,k,j)f.sub.k,r(.sub.n,k),
d′.sub.n,k,c=χ.sub.kβ(σ*.sub.n,k,j)+(1−σ*.sub.n,k,j)f.sub.k,c(.sub.n,k),
d′.sub.n,k,m=μ.sub.kβ(σ*.sub.n,k,j)+(1−σ*.sub.n,k,j)f.sub.k,m(.sub.n,k), where β(x) is the characteristic function, which is equal to 1 if x=0 and is equal to 0 if x≠0 and, the total request for communication resources, computing resources and cloud storage resources for said n-th service instantiation request is calculated as follows:
T′.sub.n=(d′.sub.n,r,d′.sub.n,c,d′.sub.n,m), where d′.sub.n,r=Σ.sub.NF.sub.k.sub.∈.sub.nd′.sub.n,k,r, d′.sub.n,c=Σ.sub.NF.sub.k.sub.∈.sub.nd′.sub.n,k,c and d′.sub.n,m=Σ.sub.NF.sub.k.sub.∈.sub.nd′.sub.n,k,m.

11. The method according to claim 3, wherein the services previously instantiated in the set of NSIs are periodically re-classified, via a normalized spectral classification algorithm, the services being represented as nodes of a connected graph and clusters are found by partitioning this graph according to their spectral decomposition into subgraphs.

12. The method according to claim 11, wherein the set R={1, N.sub.R) of the services already instantiated is defined with requests NF{λ1, . . . , λ.sub.N.sub.R} and an affinity matrix , the elements of which are the Jaccard similarity between two already instantiated services n,n′∈ is periodically calculated (20) as follows: ${n,n^{\prime }}_{}=\{\begin{array}{c}{\Lambda }_{n,n^{\prime }},n\ne n^{\prime }\\ 0,\mathrm{else}\end{array},$ where Λ.sub.n,n′, is calculated by ${\Lambda }_{i,n}=\frac{{\lambda }_n{\lambda }_i}{||{\lambda }_n||+||{\lambda }_i||-{\lambda }_n{\lambda }_i},i\in ,$ then (22) is deduced from the corresponding diagonal matrix the element (n, n) of which is the sum of the n-th row of A, s.sub.n,n=Σ.sub.n′∈.sub.\n Λ.sub.n,n′, and the associated normalized Laplacian matrix as: $ℒ=S^{-\frac{1}{2}}{-\frac{1}{2}}^{},$ And then, the normalized eigenvectors of are calculated and the first k eigenvectors are gathered using K-means, the number of clusters k is obtained such that all the eigenvalues (1, . . . , k) are very small, but the (k+1)-th is relatively large.

13. The method according to claim 10, wherein requests for the instantiation of new network services are ordered as a function of: their waiting time in a queue and then, from the oldest one, requests that can be fulfilled as a function of their request for resources are admitted; or the average quantity of resources requested, then which requests can be fulfilled are checked, starting from the request characterized by the smallest request for network resources.

Description

BRIEF DESCRIPTION OF THE DRAWINGS

(1) Further characteristics and advantages of the invention will appear from the following description, taken as a non-limiting example, with reference to the appended figures in which:

(2) FIG. 1 illustrates the correspondence between new applications and services and the requirements associated with these new applications and services in 5G communication systems,

(3) FIG. 2 schematically illustrates the network slice concept,

(4) FIG. 3 illustrates the correspondence between 3GPP network slices and the concepts of ETSI NFV (European Telecommunication Standard Institute, Network Functions Virtualization),

(5) FIG. 4 shows the correspondence of network services with the required network functions,

(6) FIG. 5 represents an illustration of shared network functions and dedicated network functions in a network slice instance (NSI) that enables the simultaneous implementation of multiple services,

(7) FIG. 6 represents a first flowchart illustrating essential steps of the method according to the invention,

(8) FIG. 7 represents a second flowchart illustrating steps in a particular embodiment of the invention.

DETAILED DISCLOSURE OF SPECIFIC EMBODIMENTS

(9) The method according to the invention will be described within the scope of a cellular network management and orchestration system configured to receive service instantiation requests and to decide to accept or refuse these services according to their types/priorities, resource requirements, the presence of other simultaneous requests and available network capacities (which depend on the network slices already instantiated).

(10) For the sake of clarity, in the following description, the instantiation of a network slice will mean the instantiation of the applications and services likely to be provided in that slice.

(11) It should be remembered that each service is instantiated in a logic network slice comprising at least two sets of virtual network functions (VNF), i.e. a set of network functions K.sup.R which correspond to the radio access network RAN and a set of network functions K.sup.C corresponding to the core network.

(12) The implementation of the method according to the invention will be described in reference to FIG. 6. Beforehand, a set of VNFs =.sup.R∪.sup.C={NF.sub.1, . . . , NF.sub.K} representing all the network functions K=(K.sup.R+K.sup.C) likely to be instantiated in the telecommunications network is defined, and, for a given network service, a subset D.sub.n of the set containing the network functions VNFs required for its instantiation and a description of the interactions between said network functions and parameters describing their respective configurations are defined. Then, to indicate the network functions VNFs required for the instantiation of the service n∈, in step 4 is introduced the vector λ.sub.n∈{0,1}.sup.K, the k-th input of which is defined by:

(13) 0${\lambda }_{n,k}=\{\begin{array}{cc}1,& \mathrm{if}{\mathrm{NF}}_k\in {𝒟}_n\\ 0,& \mathrm{else}\end{array},\forall N{F}_k\in .$

(14) The set of NSIs instantiated is then defined, and, for each element of this set i∈, the subset of the set containing the network functions VNFs instantiated for the NSI i. As for each network service, for each NSI i∈, the vector λ.sub.i is defined to indicate the available network functions VNFs.

(15) A Jaccard similarity parameter is then calculated in step 6 to perform evaluation of the similarities between the network functions required by a service awaiting instantiation. n with those of all NSIs already instantiated.

(16) The Jaccard similarity parameter is defined by the following formula:

(17) ${\Lambda }_{i,n}=\frac{{\lambda }_n{\lambda }_i}{.Math.{\lambda }_n.Math.+.Math.{\lambda }_i.Math.-{\lambda }_n{\lambda }_i},i\in ,$

(18) In step 8, it is checked whether there is i∈, such that Λ.sub.i,n>0.

(19) If yes, on the basis of the similarities calculated, in step 10, the NSI already instantiated i*∈ which shares the largest number of network functions VNFs with the network service awaiting instantiation n is selected:

(20) $i^{*}=\underset{iϵℬ}{\mathrm{argmax}}{\Lambda }_{i,n}.$

(21) After temporarily adding n to the list of services associated with NSI i*∈, for each pair of services n, n′ belonging to R.sub.i*,k where R.sub.i*,k represents the set of services included in the NSI i*which require the network function N F.sub.k ∈.sub.n, in step 12, the similarity between the configuration parameters of the two services .sub.n,k and .sub.n′, k is defined as follows:

(22) $C\left({ℒ}_{n,k},{ℒ}_{n^{\prime },k}\right)=\underset{j=1}{\overset{J}{.Math.}}h\left(l_{n,k,j},l_{n^{\prime },k,j}\right),$
where J is the number of parameters of the network function NF.sub.k.

(23) In step 14, the resources needed to be able to instantiate the service n through the selected NSI i* are determined, and in step 16 it is evaluated whether the resource request associated with this new service n can be accepted.

(24) If there is no i∈ such that Λ.sub.i,n>0, i.e. if none of the NSIs of shares network functions with the network service awaiting instantiation n, in step 18, a new NSI is defined and its request for resources is calculated, and then the admission control process is started to determine whether the service can be instantiated (step 16).

(25) In one particular embodiment of the invention illustrated in FIG. 7, the services previously instantiated in the set of NSIs are periodically re-classified via a normalized spectral classification algorithm, the services being represented as nodes of a connected graph and clusters are found by partitioning this graph according to their spectral decomposition into sub-graphs.

(26) To this end, the set ={1, N.sub.R) of services already instantiated with requests NF {λ.sub.1, . . . , λ.sub.N.sub.R} is defined and in step 20, an affinity matrix , the element .sub.n,n′ of which is the Jaccard similarity between two services n,n′∈ already instantiated, is periodically calculated as follows:

(27) ${n,n^{\prime }}_{}=\{\begin{array}{c}{\Lambda }_{n,n^{\prime }},n\ne n^{\prime }\\ 0,\mathrm{else}\end{array},$
where Λ.sub.n,n′ is calculated by

(28) ${\Lambda }_{i,n}=\frac{{\lambda }_n{\lambda }_i}{||{\lambda }_n||+||{\lambda }_i||-{\lambda }_n{\lambda }_i},i\in .$

(29) Then in step 22, from are deduced the corresponding diagonal matrix S the element (n, n) of which is the sum of the n-th row of A, s.sub.n,n=Λ.sub.n,n′ and the associated normalized Laplacian matrix as:

(30) $ℒ=S^{-\frac{1}{2}}{-\frac{1}{2}}^{},$

(31) Then, in step 24, the normalized eigenvectors of are calculated and the first k eigenvectors are gathered using K-means, the number of clusters k is obtained such that all the eigenvalues (1, . . . , k) are very small, but the (k+1)-th one is relatively large. Other similarity calculation techniques can be alternatively used as described in the papers entitled “Content caching clustering based on piecewise interest similarity,” in Proc. IEEE GLOBECOM, December 2017, pp. 1-6 and “Cache-aided coded multicast for correlated sources,” in Proc. of 9th International Symposium on Turbo Codes and Iterative Information Processing (ISTC), September 2016, pp. 360-364.

(32) Preferably, requests for the instantiation of new network services are ordered according to their waiting time in a queue, and then, based on the oldest one, the NSI capable of instantiating this service and the associated quantity of network resources are determined, and then requests that can be fulfilled according to their request for resources are admitted.

(33) In addition, requests for instantiation of new network services are ranked in relation to the average quantity of resources requested, and then checked to see which requests can be met, starting with the request characterized by the lowest request for network resources.

(34) In one first alternative implementation, in the admission control step for accepting or rejecting requests for instantiation of new services, requests are classified into M classes, each characterized by a gain related to the instantiation acceptance r.sub.m and an instantiation rejection cost I.sub.m, m E M. In addition, each network service request is stored in a queue with a size Q.sub.m dedicated to its class. A new service request is deleted when the corresponding queue is full. The management and orchestration systems perceive a gain related to instantiation acceptance r.sub.n, when a request for a slice of the class m is accepted and an instantiation refusal cost I.sub.m when the request is deleted from its queue. Therefore, at time t, the action a.sub.m(t) of the admission controller can be evaluated through a reward function as follows:

(35) $R\left(t\right)=a_m\left(t\right)r_m-d_m\left(t\right)l_m,$
where d.sub.m (t) indicates the number of requests for service of the class m abandoned at time t, which can be calculated as follows:
d.sub.m(t)=max{s.sub.m(t)−a.sub.m(t)+n.sub.m(t)−Q.sub.m,0},
where s.sub.m (t) and n.sub.m (t) indicate respectively the number of requests for slice of the mth class in the queue and the additional slice requests received at time t.

(36) A first solution is to maximize R (t) at each time interval t.

(37) A second approach is to maximize a long-term reward function as follows:

(38) $\stackrel{\_}{R}=\underset{t=0}{\overset{\infty }{.Math.}}{\gamma }^{t}R\left(t\right)$
where 0<γ<1 is a parameter called a reduction factor, which determines the importance of actions at each time interval on the long-term evaluation function.

(39) Reinforcement learning can be used to optimize the function R=Σ.sub.t=0.sup.∞γ.sup.t R (t). There are many algorithms available for this purpose, such as Q-learning.

(40) In a second alternative of the admission control step for accepting or rejecting requests for instantiation of new services, as in the first alternative, service requests are classified into M classes, each characterized by a gain related to the instantiation acceptance r.sub.m and potentially an instantiation refusal cost I.sub.m, m∈M. Then, a controller momentarily reduces the quantity of resources for some of the services already instantiated, to potentially increase the number of services that can be accepted at a given slot. For example, the controller reduces the resources allocated to lower priority services in order to instantiate higher priority services. This limits the number of abandoned requests for low priority services. As a result, a smart controller can maximize a reward that takes into account the cost of reducing the resources allocated to services instantiated with low priority. In this case, the action a.sub.m(t) of the admission controller can be evaluated as follows:

(41) $R\left(t\right)=a_m\left(t\right)r_m-d_m\left(t\right)l_m-n_{\mathrm{cc},m}\left(t\right)l_{\mathrm{cc},m}$
where n.sub.cc,m(t) is the quantity of resources reduced to the service m∈M and I.sub.cc,m is the cost associated with this action. As in the previous embodiment, it is possible to simply maximize R(t) at each time slice. On the other hand, reinforcement learning algorithms could be used to optimize the long-term instantiation acceptance R.