| Abstract: |
Nowadays, the world is experiencing an increase in applications and new technologies while numerous devices and networks will be interconnected and traffic demand will constantly rise. 5G network has arrived to meet this wide variety of needs by its architecture that actually takes into account this diversity. One of the visions of 5G is to have a multi-service network supporting a wide range of verticals with a varied set of performance and service requirements. Network slicing, which consists to slice a single physical network into multiple isolated logical networks has become the key to realize this vision. Each slice is composed of a set of visualized network functions (VNFs). This technology provides flexibility to face changes in the slice topology that can occur due to dynamic changes in the network: creation of new slice, need to increase or reduce resources for an existing slice, incident impacting the performance of a slice, etc.
As an emerging technology, network slicing brings several challenges in network management. The reconfiguration of 5G network slices problem is one of these challenges. Our objective is to schedule different slices and generate a reconfiguration plan to pass rapidly and efficiently from an initial state of our infrastructure where VNFs are not optimally allocated toward a new (optimal) state while minimizing the service interruption. This problem is known as a VNF reconfiguration problem.
The problem of VNF reconfiguration is NP-Hard and it may be formulated as a multi-dimension multiknapsack reconfiguration problem. The multidimensionality stands on the number of resources concerned (i.e., CPU and memory), while the knapsack aspect is captured by the servers, each of them representing a knapsack. From exact solution method point of view, we have formulated and studied the problem as a Mixed Integer Linear Programming. We notice that the problem remains difficult and appropriate solution methods handling integer linear complex formulations should be investigated. This is an important investigation direction. From heuristic perspective, we have started to investigate modeling the problem as a graph one. The origin and destination states are represented by a (migration) graph, where the vertices represent the servers and the arcs represent the migrations of the VNFs. If the resulting graph is acyclic, the solution is feasible in polynomial time. In this case, we apply the topological order to have the reconfiguration plan that contains the list of migrations of VNFs following this order. If the graph is cyclic, one may apply the feedback arc set problem algorithm to render it acyclic, which consists in calculating all the arcs of minimum value that will have to be removed to obtain an acyclic graph. Then, we apply the topological order in order to obtain the migration order of the VNFs. Both exact and heuristic solutions are tested on synthetic datasets for validation. |