Column Generation Based Service Function Chaining Embedding in Multi-domain Networks

Research output: Journal Publications and Reviews (RGC: 21, 22, 62)21_Publication in refereed journalpeer-review

View graph of relations


  • Rongping Lin
  • Song Yu
  • Shan Luo
  • Xiaoning Zhang
  • Jingyu Wang

Related Research Unit(s)


Original languageEnglish
Journal / PublicationIEEE Transactions on Cloud Computing
Publication statusOnline published - 31 May 2021


Network function virtualization (NFV) achieves cost-effective network service provisioning through exploitation of virtualization and automation by decoupling network functions (software) from dedicated hardware. The software of the various devices can then be hosted by low-cost general computation devices rather than by more expensive dedicated devices. To obtain a specific network service, the traffic flow is steered to go through a specific order of network functions that are hosted by cloud computing, and this network function sequence is known as a service function chaining (SFC). To allocate computation resources for network functions and bandwidth resources between network functions in a physical network is the SFC embedding problem. In this paper, we consider the SFC embedding problem in multi-domain networks, where no domain information, like domain topology and network resource, is disclosed among domains. We propose a new optimization algorithm based on column generation method to solve this problem, which is distributedly computed in each domain. To further improve the scalability, we also provide two heuristic algorithms. We selected two networks one large (158 nodes) and one small (18 nodes) to numerically validate the proposed algorithms and demonstrate that the acceptance ratio obtained by the heuristic algorithms is close (within 5.6%) to that of the optimal algorithm.

Research Area(s)

  • Network function virtualization, service function chaining embedding, multi-domain