Time-Expanded Graph-Based Virtual Network Embedding Algorithm for Diverse Virtual Networks: Balancing Delay-Sensitive and Tolerant Services
Jingyu Miao, Limin Zhang, Zhichao Ma, Bin Liu · 2024
In the satellite-terrestrial network (STN), network virtualization (NV) enables efficient resource sharing among diverse virtual networks (VN s) with varying quintessence and accords. The primary challenge in NV is the precise mapping of each VN's demand for definite nodes and links in the SN, a process known as virtual network embedding (VNE). Existing VNE manners often overlook the multiplicity and dynamics inherent in both VN requests (VNRs) and STN resources. This paper introduces an innovative temporal graph-based online algorithm to tackle VNE challenges for both delay-susceptible and patient services. Initially, a time-expanded graph (TEG) is utilized to represent STN resources in both spatial and temporal dimensions. Differentiated services are modeled as two ways of time-related VNRs. The proposed TEG-based online VNE algorithm (TEG- VNE) is designed to maximize the number of successfully embedded VNRs while optimizing STN resource utilization through the joint scheduling and embedding of these differentiated VNRs. The effectiveness of the proposed VNE- TEG approach is demonstrated through comprehensive numerical simulations.