Broker-Coordinated Conflict-Based Search for Multi-Domain Virtual Network Embedding

Abstract

Network virtualization enables multiple virtual networks to share physical network resources efficiently and flexibly. Realizing this capability requires solving the Virtual Network Embedding (VNE) problem, the task of assigning Virtual Network Requests (VNRs) to physical network resources while satisfying resource allocation constraints. Although VNE has been extensively studied in single-domain settings, practical deployments may span multiple administrative domains operated by independent Infrastructure Providers (InPs) that do not disclose their internal topologies or resource availability. In this paper, we study the multi-domain VNE problem and propose B-iVNE-CBS, a broker-coordinated framework that uses iVNE-CBS, an improved Conflict-Based Search (CBS) solver for VNE, to compute local embeddings within each InP. The broker assigns VNR vertices to suitable InPs based on InP-reported embedding costs and an abstract view of the inter-domain connectivity. Each InP computes its local embedding using iVNE-CBS and reports only the information required for coordination. When a local embedding fails or the resulting local embeddings cannot be combined into a feasible inter-domain embedding, the broker introduces constraints and revises the affected assignments through a CBS-style search. This design preserves the autonomy of each InP while limiting the disclosure of private network information. Experimental results show that, despite limited information disclosure, B-iVNE-CBS achieves the highest acceptance ratios for large multi-domain VNE instances, favorable cost/revenue ratios, and low runtimes compared with the evaluated baseline methods.