Research Activities

My recent research activities focus on the following key areas:

• Routing
• Network Design
• Offline design of physical networks,
• Virtual network design (mapping virtual networks onto a substrate network),
• Placement and chaining of virtualized network functions (VNF) or Service Function Chain (SFC) provisioning,
• Coverage in networks (e.g., drones or sensors).
• Network Robustness
• Impact of resource-sharing strategies on the efficiency of protection,
• Local protection of virtual networks,
• End-to-end protection of service chains.
• Metaheuristics and Combinatorial Optimization

In my research, I address various NP-complete problems related to these areas. Key contributions include:

• Transformation of the VNF (Virtual Network Function) placement and chaining problem into a constrained routing problem in a multipartite graph: This work represents a major breakthrough, providing for the first time an exact solution to the problem without relying on Integer Linear Programming (ILP). Constrained routing, which is widely studied and well-documented in the literature, facilitates the development of efficient heuristics for solving this problem. Additionally, both the complexity and approximability of the problem have been established, enabling deeper insights into the mechanisms underlying network function placement and chaining.

To address this problem, we proposed a heuristic based on Dijkstra's algorithm, where up to k paths are stored at each node in the substrate network. Simulations revealed that increasing the value of k yields diminishing returns, suggesting that small values of k provide a high probability of achieving solutions close to the optimum. These findings underscore the effectiveness of our approach in tackling this complex challenge. More details on this contribution can be found in our publication: link.

• Placement of VNFs in a substrate network with abundant bandwidth: This problem was reformulated as a quadratic multiple knapsack problem. The constraints align with those of bin packing, while the objective corresponds to that of the multiple knapsack problem. To solve this challenge, we employed genetic algorithms renowned for their efficiency in addressing knapsack problem variants. More details on this contribution are available here: link.

• Protection of virtual networks against single failures: We demonstrated that, in overprovisioned networks, the local protection problem for virtual networks can be reduced to constructing a Steiner tree, a well-known NP-hard problem. For substrate networks with limited resources, we proposed a heuristic based on Kou-Markowsky-Berman trees. Further information on this work can be found here: link.

• Service Function Chain (SFC) Protection: I demonstrated that the problem of end-to-end protection for service function chains is NP-complete, even in the absence of resource constraints, a critical result for service providers and operators, as it rules out network overprovisioning as a viable workaround. To tackle this challenge, I developed an original heuristic inspired by the “leave room” principle from set cover problems, which maximizes the disjointness between primary and backup walks while optimizing resource usage. This solution delivers a robust and efficient approach, representing a significant advancement in the field.

• Complexity analysis of various problems: We showed that in overprovisioned networks, the problem of VNF (Virtual Network Function) placement and chaining can be reduced to a shortest path problem solvable in polynomial time. However, we also established that the generic version of this problem is NP-complete, even for fixed-size Service Function Chains (SFCs) or fixed substrate network topologies. These results, along with other contributions, can be accessed here: link.

• Additional research topics: Other areas explored include virtual network mapping in interdomain environments, physical network design, and drone network protection. Detailed descriptions of these topics are available here: link.

The complete list of my publications can be found here: link.