Column generation algorithms for virtual network embedding in flexi-grid optical networks.

Area of Science:

• Computer Science
• Telecommunications Engineering
• Network Engineering

Background:

• Network virtualization enables efficient resource management by overlaying multiple virtual networks (VNs) on a shared substrate network.
• Virtual Network Embedding (VNE) is crucial for optimizing resource allocation and ensuring performance requirements for VNs.
• Flexi-grid optical networks present unique challenges for VNE due to their granular spectrum allocation.

Purpose of the Study:

• To develop and evaluate novel VNE algorithms for efficient resource management in flexi-grid optical networks.
• To minimize the total embedding cost, considering both spectrum and computation costs for VN requests.
• To ensure scalability and high performance in dynamic traffic environments.

Main Methods:

• An exact algorithm was developed to minimize embedding cost for single VN requests.
• A scalable heuristic algorithm was designed for dynamic VNE scenarios.
• Simulations were conducted on a six-node network and a realistic USnet topology to evaluate algorithm performance.

Main Results:

• The heuristic algorithm achieved blocking probabilities very close to the exact algorithm (0.2% higher) in simulations.
• For the USnet topology, the new heuristic algorithm demonstrated a blocking probability approximately one order of magnitude lower than a simpler existing heuristic.
• Both algorithms were applied to a dynamic traffic scenario with sequential VN requests.

Conclusions:

• The proposed heuristic VNE algorithm offers a scalable and efficient solution for managing flexi-grid optical networks.
• The algorithm significantly improves performance by reducing blocking probability compared to existing methods.
• This work contributes to the advancement of resource optimization in virtualized optical network infrastructures.