於軟體定義網路中具服務品質保證之最小成本容量規劃

Abstract

在第五代（5G）與展望第六代（6G）行動通訊網路的發展進程中，網路切片技術已成為實現多元服務品質（QoS）保證的核心基石。然而，如何在確保各類切片嚴格延遲需求的前提下，精準規劃網路容量以最小化基礎設施的建置成本，仍是電信營運商面臨的艱鉅挑戰。本論文針對軟體定義網路（SDN）環境，探討「具 QoS 保證之最小成本容量規劃問題」，將其建構為混合整數非線性規劃（MINLP）模型，並深入剖析「非搶佔式」與「搶佔式」M/G/1 優先權排隊機制在資源配置上的本質差異。

鑑於該問題具有 NP-Hard 複雜度與高度非線性特徵，本研究採用基於拉格朗日鬆弛（Lagrangian Relaxation, LR）的優化框架。透過將原始問題拆解為多個獨立的子問題，並利用次梯度法迭代更新乘數，以獲取高品質的理論下界。為克服對偶問題與原始可行解之間的落差，本研究開發了四種啟發式演算法以建構原始可行解。其中，創新提出的「成本導向離散收縮法（Cost-Guided Discrete Shrinkage, CGDS）」採用了「先寬鬆擴充以確保可行，後精確收縮以優化硬體階層」的雙階段策略，在絕大多數測試場景中展現了絕對的統治力；而基於全域對偶資訊的路由策略（如拉格朗日懲罰引導路由啟發式演算法 （LR Penalty Guided Routing Heuristic, LPGR）則在極端成本差異環境中，展現出避開局部最佳解的獨特價值。

實證結果顯示，CGDS 演算法具備極佳的穩健性，即便在重載流量與高成本變異環境下，仍能將搶佔式模型的最佳性差距（Optimality Gap）逼近至 0.99% 至 1.14% 的理論極限。此外，本研究透過量化分析揭示了兩種服務機制的關鍵權衡：搶佔式模型藉由允許高優先權流量中斷服務，有效免除了為壓低基礎序列化延遲（Serialization Delay）而盲目擴充的容量緩衝，在重載情境下可節省約 33% 的建置成本；惟其嚴謹的邊界方程式導致在極端低延遲（如 0.1 ms）場景下引發數學死鎖（Mathematical Deadlock），表現出極高的結構剛性（Structural Rigidity）。相對而言，非搶佔式模型雖然因需過度配置容量而成本高昂，但在面對物理極限時展現了較大的部署彈性。本研究所提出的優化架構與分析觀點，將可為次世代網路的策略性容量規劃提供具備數學立論基礎與經濟效益的決策參考。

With the evolution of Fifth-Generation (5G) and Sixth-Generation (6G) mobile technologies, network slicing has emerged as a pivotal architecture for supporting diverse Quality of Service (QoS) requirements. Minimizing infrastructure deployment costs while satisfying stringent latency constraints presents a critical challenge for network operators. This thesis addresses the "Minimum Cost Capacity Planning Problem with Guaranteed QoS" within Software-Defined Networks (SDN). The problem is formulated as a Mixed Integer Non-Linear Programming (MINLP) model, incorporating Non-Preemptive and Preemptive M/G/1 priority queueing disciplines to characterize network delay dynamics.

Given the NP-hard nature of the problem, a solution approach based on Lagrangian Relaxation (LR) is developed. The primal problem is decomposed into subproblems, and the Subgradient Method is employed to update multipliers and derive tight theoretical lower bounds. To bridge the integrality gap between the dual solution and a discrete network configuration, four distinct heuristic algorithms are proposed. Among them, the novel Cost-Guided Discrete Shrinkage (CGDS) heuristic, which combines cost-guided primal initialization with a rigorous discrete shrinkage phase, demonstrates absolute dominance across most scenarios. Simultaneously, global dual-guided routing strategies (e.g., LR Penalty Guided Routing Heuristic (LPGR)) prove uniquely valuable in evading economic traps under extreme cost heterogeneity.

Computational experiments indicate that the CGDS algorithm is highly robust, driving the optimality gap down to near-absolute theoretical limits of 0.99% to 1.14% for the Preemptive model under heavy traffic and severe cost variance. Furthermore, this study provides a critical comparative analysis of the two service disciplines: the Preemptive model significantly reduces capital expenditure (saving approximately 33% in heavy load scenarios) by eliminating the need to purchase massive capacity headroom merely to minimize base serialization delays. However, this economic efficiency comes at the cost of structural rigidity, triggering a mathematical deadlock under extreme latency constraints (e.g., 0.1 ms). In contrast, the Non-Preemptive model, while drastically more costly due to brute-force over-provisioning, offers greater feasibility flexibility near physical limits. The proposed framework establishes a mathematically rigorous and cost-effective tool for strategic capacity planning in next-generation networks.