雲霧端網路中的延遲感知虛擬網路嵌入問題

Abstract

霧運算是一個將雲端的運算負載分佈到網路邊緣的一個全新 的概念，並可用來滿足逐漸興起的嶄新應用(像是擴充/虛擬實境 和車聯網)在低延遲上的需求，為了能夠實現霧運算的概念，網路 功能虛擬化是其中一個關鍵的技術，令服務(像是網路功能或第三 方應用)能夠被配置在網路中的任何地方。 因為網路功能虛擬化的興起，如何根據應用的各種需求來決定 將它們佈建在網路中的哪個地方是未來一個很重要的議題，至今 已經有多種不同方面的研究在這個議題上，其中一種研究是虛擬 網路嵌入問題，它是一個探討在網路營運者所管控的實體網路中， 在能夠滿足虛擬網路請求的前提下，來決定服務端點配置的地方 和端點間資料傳輸路徑的資源分配策略。因為虛擬網路嵌入問題 的相關研究在延遲方面的領域還不夠成熟，所以在這個碩士論文 中我們主要探討這個問題，並定義了一個延遲感知虛擬網路嵌入 最佳化問題，目標是在能夠滿足應用的延遲需求的前提下，去最小 化因配置這個應用所花費的成本。 因為虛擬網路嵌入問題的複雜度相當高，我們提出了一個命名 為 CN-based LA-VNE 的啟發式演算法，這個演算法充分的利用了 雲霧端網路中在實際情況下佈建運算節點的性質，其性質是指越 遠的運算節點會擁有越強的運算能力。在這個演算法中，我們會將 這些運算節點以階層式的分成多個群集，並用這些群集來初步評 估延遲和成本，根據這個初步評估的結果，我們可預判哪些區域可 能有較好的解，並在這些區域中使用粒子群最佳化演算法來找可 行解。如此一來，我們的演算法能夠有效率地在較小規模且包含較 好可行解的搜尋空間中去尋找次解，來改善可擴充性的問題。 我們將所提出的演算法和窮舉法以及現有的粒子群最佳化演 算法來去比較成本、接受率和搜尋時間等效能，結果呈現出在小規 模網路下我們的方法能夠趨近於最佳解，而在大規模網路下我們 的方法於成本(約 33%)、接受率(約 7%)和執行時間(約 37%) 都優於現有的粒子群最佳化演算法。

Fog computing is a promising solution to meet the increasing demand for low latency ap- plications (such as augmented reality (AR), virtual reality (VR), and vehicle networks) by distributing some computing loads from the cloud to the network edge. In the implementation of fog computing, network function virtualization (NFV) is an important enabler. NFV enables services (such as network functions and third party applications) to be deployed anywhere by using virtualization techniques. Due to the emergence of NFV, how to deploy applications based on application demands becomes an important issue. There have been many researches on the issue, and one of them is the virtual network embedding (VNE). VNE is a type of allocation strategies on how to select serving nodes and data paths on the underlying substrate network based on the demands of virtual network requests (VNRs). Since research on VNE with is still immature, we focus on this problem in this thesis, In particular, we define a latency-aware optimization problem for minimizing the total cost while satisfying the latency demand of applications. Since the VNE problem is complex, we propose a heuristic algorithm that is called the CN-based LA-VNE algorithm. It fully takes advantage of the realistic property that far away computing nodes in fog-cloud networks have more powerful computing capabilities than ones near to the edge node. In our algorithm, we group these computing nodes into multiple clusters in the hierarchy, and preliminarily evaluate performance in terms of cost and latency by em- bedding VNRs onto these clusters. According to the evaluation, we could estimate potentially better solutions, and find feasible solutions by using the particle swarm optimization (PSO) algorithm. By doing so, our solution could efficiently find sub-optimal solutions in the smaller search space including better feasible solutions and improve the scalability problem. We compare our solution with the exhaustive search and the existing PSO algorithm in terms of cost, acceptance ratio and searching time. The evaluation results show that our so- lution has near-optimal performance in small networks, and has a substantial improvement by 33% in terms of cost, 7% in terms of acceptance ratio, and 37% in terms of searching time over the existing PSO in large networks.