針對單一實體設施節點失效之具生存性虛擬網路可擴展映射方法

Abstract

隨著網路基礎設施對於有彈性且高效資源利用的需求日益增長，虛擬網路嵌入（VNE）技術應運而生。虛擬網路（VN）已廣泛應用於雲端計算與軟體定義網路（SDN）等應用中，以滿足這些不同應用或服務需要具有獨立的網路拓撲結構、特殊計算資源、網路頻寬、延遲與可靠性之多樣需求。透過VN 的需求抽象化，網路營運商在無需關注底層實體網路的細節下仍然能夠提供相應之服務，同時透過虛擬網路嵌入（VNE）演算法，營運商可快速將VN對應至實體網路（SN），確保服務品質（QoS）需求得以滿足，同時最大化資源利用率。

在 VNE 研究領域的眾多議題中，本研究聚焦於因實體網路（SN）的失效（尤其是節點失效）時產生的生存性問題，實體網路之失效可能源自於硬體故障、軟體錯誤或網路攻擊，對於關鍵應用與服務而言，此類失效可能嚴重影響使用者滿意度與營運可靠性，因此可生存性成為 VN 設計與管理中不可忽視的議題。

為解決 VNE 的可生存性問題，本研究採用一種解耦方法，也就是將生存性與嵌入問題分開處理 [16][17]，並提出兩項新的設計原則。首先，我們在所謂的增強階段（augmentation phase）處理生存性問題，透過增加備援虛擬節點與相應的備援虛擬連結來「增強」 VN。此研究透過探討各種增強 VN 的策略，識別出一種擁有最大 augmented VN 解空間的增強策略，提高了尋找全域最佳 augmented VN 的可能性。其次，本研究開發了一種名為 Nest-Base 的演算法，以快速識別在放寬限制條件下的全域最佳augmented VN。此外，本研究亦設計了一種嵌入演算法，此演算法確保了增強階段的資源增量與最終嵌入成本之間具有較強的線性關聯性，使得Nest-Base找到的資源增量最小的augmented VN，能夠最終實現最低的嵌入成本。

模擬結果顯示，Nest-Base 在 VN 接受率 (acceptance ratio) 與嵌入成本方面皆優於現有方法，包括 FIP、FDP [16]及 ProRed [17]。在適中負載的網路環境下，Nest-Base 嵌入成本降低幅度 在 小型 SN 中相較於 FIP 降低 11.6% 至 29.2%，相較於 FDP 降低 12.9% 至 31.5%，相較於 ProRed 降低 18.9% 至 25.4%。在 大型 SN 中，嵌入成本的降低幅度分別為 10.0% 至 29.1%（相較於 FIP）、11.7% 至 31.0%（相較於 FDP）、19.5% 至 25.7%（相較於 ProRed）。

在高負載的網路環境下，Nest-Base VN 接受率範圍 在 小型 SN 中為 60% 至 70%，在 大型 SN 中為 85% 至 100%。相較於 FIP、FDP 和 ProRed，Nest-Base 在 小型 SN 的 VN 接受率分別提升 25% 至 35%（相較於 FIP）、30%（相較於 FDP）、10% 至 15%（相較於 ProRed）。在 大型 SN 中，VN 接受率的提升幅度為 25% 至 45%（相較於 FIP 和 FDP）、2% 至 12.5%（相較於 ProRed）。此結果凸顯了本研究方案的實用性，並顯示其在多種實際網路應用場景中的價值。

The growing demand for flexible and efficient resource utilization of network infrastructures has driven the development of Virtual Network Embedding (VNE). Virtual Networks (VNs) are widely used in cloud computing and software-defined networks (SDN), where different applications or services require independent, isolated network topologies with specific requirements in terms of bandwidth, latency, and reliability. The abstraction of VNs allows network operators to provide these services without worrying about the underlying physical network's details. By using VNE algorithms, the VN can be efficiently mapped onto the substrate networks (SNs), ensuring that the QoS requirements are satisfied, and resource utilization is maximized.

Among different issues studied in the field of VNE, we focus on the survivability issue which deal with SNs failure (in particular node failure) due to hardware malfunctions, software bugs, or cyberattacks. For critical applications and services, these failures can severely affect user satisfaction and operational reliability, making survivability an essential consideration in VN design and management.

To address the survivability issue of VNE, we adopted a decoupled approach to tackle survivability and embedding separately [16][17] with two new design principles. First, the survivability issue is handled in the so-called augmentation phase, where backup virtual nodes are added, along with corresponding backup virtual links, to “augment” the VNs. By exploring various augmented VN strategies, this research identifies an augmentation strategy with the largest solution space for augmented VNs, thereby enhancing the likelihood of finding a optimal augmented VN. Second, an algorithm named Nest-Base was developed to quickly identify optimal augmented VNs under the relaxed constraints. Finally, a mapping (embedding) algorithm with a stronger linear correlation between resource increment of the augmentation phase and embedding cost of the mapping (embedding) phase is also developed such that the augmented VN with the minimum resource increment during the augmentation phase will lead to the minimum mapping (embedding) cost during the mapping phase.

The simulation results indicate that Nest-Base provides the lowest embedding cost while accommodating VNs significantly better than other approaches, including FIP, FDP [16], and ProRed [17]. Under moderate-load network conditions, Nest-Base achieves an embedding cost reduction ranging from 11.6% to 29.2% compared to FIP, 12.9% to 31.5% compared to FDP, and 18.9% to 25.4% compared to ProRed in small-scale SNs. In large-scale SNs, the embedding cost reduction reaches 10.0% to 29.1% over FIP, 11.7% to 31.0% over FDP, and 19.5% to 25.7% over ProRed.

Under high-load network conditions, the VN acceptance ratio of Nest-Base remains within 60% to 70% in small-scale SNs and 85% to 100% in large-scale SNs. Compared to FIP, FDP, and ProRed, Nest-Base achieves a VN acceptance ratio improvement ranging from 25% to 35% over FIP, 30% over FDP, and 10% to 15% over ProRed in small-scale SNs. In large-scale SNs, the VN acceptance ratio improvement reaches 25% to 45% over FIP and FDP, and 2% to 12.5% over ProRed.

This highlights the practicality of our solution, underlining its value across a variety of potential networking scenarios.