An Approach to Network Service Placement Reconciling Optimality and Scalability

Masoud Taghavian (1, 2) , Yassine Hadjadj-Aoul (3, 2) , Géraldine Texier (4, 1, 2) , Nicolas Huin (1, 4) , Philippe Bertin (2)

1 ADOPNET - Advanced technologies for operated networks
2 IRT b-com - Institut de Recherche Technologique b-com
3 ERMINE - mEasuRing and ManagIng Network operation and Economic
4 IMT Atlantique - SRCD - Département Systèmes Réseaux, Cybersécurité et Droit du numérique

The inevitable transition from physical dedicated hardware devices towards lightweight containerized reusable software modules with Network Function Virtualization (NFV) introduces countless opportunities while presenting several unprecedented challenges. Satisfying NFV expectations in post-5G networks heavily depends on the efficient placement of network services. In this paper, after modeling the placement problem and proposing the exact resolutions using Integer Linear Programming (ILP) and Column Generation (CG), we propose our deterministic placement solution, capable of obtaining optimal results with the scalability of a heuristic-grade approach. Our method is organized as a Branch and Bound (BnB) structure, applying Artificial Intelligence (AI) search strategies (especially A*) to address the problem of network service placement. We believe that it is suitable for a range of applications in online placement scenarios, whether we concentrate on the quality of the results or on the strict time constraints. We are interested in the popular objective of Service Acceptance (SA) maximization and have carried out several extensive evaluations. The obtained results confirm the effectiveness of our solution.

Keywords: Network Function Virtualization; Network Service Placement; Branch and Bound; Artificial Intelligence

Domains: Networking and Internet Architecture [cs.NI]

Masoud Taghavian, Yassine Hadjadj-Aoul, Géraldine Texier, Nicolas Huin, Philippe Bertin. An Approach to Network Service Placement Reconciling Optimality and Scalability. IEEE Transactions on Network and Service Management, 2023, 20 (3), pp.2218-2229. ⟨10.1109/tnsm.2023.3284602⟩. ⟨hal-04367850⟩