OPT-AG-VMTE: Integer Linear Programming-Optimized Augmented Graph Approach for Virtual Multicast Tree Embedding in Software Defined Networks

Abstract

Network virtualization enables multiple Virtual Networks (VNs) to share the same physical infrastructure, improving resource utilization. A key challenge is efficiently mapping these VNs onto the Substrate Network (SN), a process known as Virtual Network Embedding (VNE). Traditional VNE focuses on one-to-one (unicast) communication. This research addresses the efficient mapping of VNs with one-to-many (multicast) interactions, represented as Virtual Multicast Trees (VMTs), onto a shared SN. We introduce a Virtual Multicast Tree Embedding (VMTE) approach that leverages Integer Linear Programming (ILP) and employs IBM CPLEX and Gurobi solvers. This VMTE-ILP method aims to minimize substrate network resource consumption (i.e., bandwidth) while meeting virtual node computing requirements and reducing redun-dant link usage. We evaluate the performance of the proposed VMTE-ILP approach across various network topologies, comparing CPLEX and Gurobi solver performance and analyzing the impact of different topologies on bandwidth consumption and redundant multicast transmission. This work provides a comparative analysis of ILP-based VMTE solutions using different solvers, focusing on minimizing resource consumption and optimizing multicast communication in virtualized networks. © 2025 IEEE.