Mathematical Modelling of Network Orchestrators in Distributed Environment A Scientific & Mathematical ApproachToward Managing NFVI and Its Nodes

Mathematical Model Definition & Variables

Let us use Graph theory to solve this issue.Consider the NFVI modelled as a directed graph.

G = (P, E), where P is the NFVI-Point of Presence nodes set.

E is the network edge set linking them, such that E = {(p, q) | p ∈ P, q ∈ P, p 6= q}.

δp, δq represents the network delay of an edge (p, q) ∈ E.

V represents the set of VNF instances in the system.

Location of a VNF instance v ∈ V is defined by lv,p ∈ {0, 1} such that lv, p equals to 1 only when v is placed at p ∈ P.

M represents the set of VNFMs that can be used to manage the xNF instances. ϕ denotes the capacity of a VNFM. It represents the maximum number of xNF instances that a VNFM can manage.

We consider that an NFVO has capacity defined in terms of the maximum number of xNF instances in its domain.

• We employ Φ to refer to this capacity.
• Assume that the DGSMO is deployed at a given NFVI-Point of Presence.

We define wp ∈ {0, 1} to indicate the DGSMO location, such that wp is equal to 1 only if the DGSMO is placed at p ∈ P.

There is an upper bound on the acceptable network delay between various functional blocks to ensure predictable system performance.

We use ψ to denote the maximum acceptable delay between an NFVO at the DGSMO and the VIM on the other hand.

VNFM can manage different VNF types, which can impose different requirements on the network delay over the VNFM reference points.

Define the upper bound on network delay between a VNFM and other functional blocks per VNF instance.

Ωv indicates the maximum acceptable delay between the NFVO and the VNFM assigned to VNF instance v.

Employ ωv to denote the upper bound on the delay between the VNF instance v and its designated VNFM.

Going with our assumptions (2) and (3) of the problem statement, ωv also represents the maximum acceptable delay between the VNFM and the VIM of NFVI-Point of Presence where v is located.

Minimised Objective Function Constraint Defined

The objective function constraints listed are as follows

Constraint - (1)

(Eq.1) seeks to minimize the number of NFVOs and VNFMs as their number is a measure of the operational cost of the NFV management and orchestration.

Constraint - (2)

stipulates that one NFVO is responsible for the resource orchestration of a NFVI-Point of Presence, i.e. a NFVI-Point of Presence belongs exactly to one domain.

Constraint - (3)

ensures that the NFVI-Point of Presence q can be assigned to the NFVO at NFVI-Point of Presence p when there exists an active NFVO at p.

Constraint - (4)

indicates that a NFVO should be placed within its domain boundaries.

Constraint - (5)

ensures that a VNFM can be placed only at one NFVI-Point of Presence.

Constraint - (6)

indicates that each VNF instance should be assigned to one VNFM.

Constraint - (7)

stipulates that a VNF instance can be assigned to VNFM m placed at NFVI-Point of Presence p only when m exists at p.

Constraint - (8)

stipulates that a VNF instance can be assigned to VNFM m placed at NFVI-Point of Presence p only when m exists at p.

We enforce the capacity constraints of NFVO and VNFM by (9) and (10).

Constraint - (11)

ensures that a VNFM is active only when it manages at least one VNF instance.

Constraints - (12)-(15)

enforce the delay limits in the system.

Note that the constraints (8), (9) and (15) are non-linear constraints and can be linearized by replacing them with linear constraints (16)-(21) as follows

Proposed Mathematical Solution

We propose a two-step management algorithm to solve the problem

1. Firstly, decompose the NFVI into one or more domains and place a single NFVO in each domain. This step is performed through a metaheuristic search method employing local search methods used for mathematical optimization search-based algorithm which will be discussed later in section IV-A. However, the algorithm generally aims to minimize the number of NFVOs in the system.

2. It gives the solution of decision variables hp and rq,p that satisfies the model constraints (2)–(4), (12) and (13). Besides, this step disregards the placement of VNFMs themselves. However, we assure that the solution design would allow future VNFM placement to satisfy the VNFM delay constraints, i.e. constraints (14) and (15).

3. To do so, we impose additional constraints on the solution to ensure that

a. ∀v ∈ V, ∃p´ ∈ P such that: lv,q rq,p rp,p ´ δq,p´ ≤ ωv, ∀q, p ∈ P - (22)

b. lv,q rq,p rp,p ´ δp,p ´ ≤ Ωv, ∀q, p ∈ P - (23)

4. The constraints (22) and (23) guarantee that for every VNF instance v, there exists a NFVI-Point of Presence p´ in the same domain where a VNFM can be placed to manage v while fulfilling the delay constraints.

5. After that, in the second step, we place the needed VNFMs for each domain and map the VNF instances onto the VNFMs. We do that by utilizing the VNFM placement algorithm presented in our earlier work [11].

6. This step provides the solution of decision variables xm,p and yv,m,p. The obtained solution satisfies the model constraints (5)–(11), (14) and (15).

7. Use Metaheuristic search method employing local search methods used for mathematical optimization search-based algorithm to place the NFVOs and define the boundaries of their domains.

8. Metaheuristic search method employing local search methods used for mathematical optimization.

9. [12] is a widely adopted meta-heuristic that guides a local search procedure to explore the solution space beyond local optimality. It starts the search process from an initial solution and iteratively explores the neighbour solutions.

10. Each iteration uses movements to produce a set of neighbor solutions and employs an objective function to evaluate them. The search continues till the stop criteria are met.