VNF Deployment and Flow Scheduling in Geo-distributed Data Centers

Abstract

NFV可降低網路營運上的設備採購以及維護成本，透過NFV可將網路功能與物理基礎設施進行解耦合。
並在通用硬體上運行虛擬網路功能(VNF)，NFV可使網路更加靈活可控，但仍然存在各種技術挑戰
像是如何在不同地理位置上有效部屬VNFs，以及在不同地理位址的資料中心調度網路流量。

本篇論文中研究此議題並最大縣動減少部屬以及通訊成本，此問題被轉換成混合整數線性規劃問題(mixed-integer linear programming)，本論文提出一種基於放鬆的演算法(relaxtion-based algorithm)來解決它的計算複雜度，最後通過實驗結果表明，該演算法可有效降低部屬與通訊成本。

Ch1-Introduction

傳統資料中心或雲端運算網路架構仰賴特定硬體來提供特定網路服務，像是防火牆、入侵偵測系統。
這些造成硬體成本過高。而NFV的出現取代了這種往賴特定硬體的網路架構。

藉由NFV，網路功能可能被虛擬化成基於軟體的VNF並運行在一般COTS服器上。

而為了提供網路服務，網路流需要流經過一連串以排序之網路功能的集合

然而要實際應用NFV技術，必須考量到VNF要如何串接成一串服務鏈(service chains)以降低成本
以往這部分的研究都僅僅關注於部屬成本，旨在減少資料中心的資源消耗，像是CPU、記憶體、儲存空間等，或是單獨著重於通訊成本，像是最大限度減少點對點的延遲等
但幾乎沒有考量到若作為VNF部屬的通訊成本。

在服務鏈上每個鏈結上的網路功能都是有序的，每個鏈結也都有自己的流速，同時在不同VNF部屬在地域分布的資料中心的不同VNF，將導致不同的通訊成本。這代表部屬成本與通訊成本之間的關係不疼夠被忽視，此外舊有研究也很少考慮NFV服務中的流量平衡問題，以前的研究通常會假設VNF流不能夠被分配到同一類的多個VNF Instance上，或是其分散式流量率(distributed flow rate)是預先定義好的，這對於大規模網路中的私有NFV服務來說是不限實也沒效率的，本篇論文認為VNF instance的數量和相應的網路流量應該根據當前網路狀態進行調整。

本篇論文，考量到有序服務鏈在不同地理分布資料中心下的部屬成本以及通訊成本間的權衡問題，並且我們允許一種 NF 具有多個 VNF 實例。

本文主要貢獻：

本文將綜合考量網絡拓撲、VNF的數量和部署以及流量調度，來將VNF部屬以及流量調度問題轉換為混和整數線性規劃問題(mixed integer linear programming, MILP)，，以降低部署成本和通訊成本。
在該MILP方程式的基礎上設計一種低複雜度的基於鬆弛的演算法，並進行大量實驗來說明此演算法相較現有演算法的優勢，結果表明本研究提出的演算法可有效降低部屬成本以及通訊成本。

Ch2-System Model

A. DCs Topology

由於資料中心分布在世界各地，不同資料中心間所傳輸的網路流量會有著不同的成本(cost)
這裡透過無向圖(indirected graph) 來代表資料中心的網路拓圖 $G_{d}=(D,E_{d})$
$D$ 為資料中心 $E_{d}$ 代表網路邊緣
$H_{dp}$ 為 edge $e_{dp} \in E_{d}$的權重(weight) 其中 $d,p \in D$
(上面就代表，D和P是資料中心，而H是DP這之間網路連接的Weight，所代表的是這兩資料中心之間的傳輸成本)
而這裡須注意，個別資料中心自己到自己之間沒有傳輸成本 $H_{dd}=0$

B. Chain Set

有一組鏈 $C={c1,c2,…}$ 被部屬到資料中心，若將服務鏈中$c_{i} \in C$來源節點(source)與目的節點(destination)分別以 $o_{i}$ 以及 $t_{i}$ 表示。
每個服務鏈 $c_{i}$中都有一組以排序之網路功能 $c_{i}={s_{i,1},s_{i,2},….s_{i,j},…}$ 來以速率 $R_{i}$處理網路流量
我們定義 $|c_{i}|$ 為服務鏈 $c_{i}$的長度，並且定義 $n(s_{i,j})$ 來表示𝑠𝑖,𝑗的網絡功能的類型
舉例來說如圖

圖中三個服務鏈的長度分別為2,3,3 (注意:，不同的服務鏈可能需要一種網絡功能)
舉例來說，$c1$ $c2$ $c3$ 可能都共同包含網路功能 $f1$，即 $n(s_{1,1})=n(s_{2,2})=n(s_{3,2})=f_{1}$

C. NFs Graph

基於上述的鏈集合(Chain Set)，我們可以建構網路功能圖 $G_{n}$
此網路功能圖為有向非循環圖(directed acyclic graph, DAG)
$G_{n}=(V_{n},E_{n})$，且$V_{n}$ 可被歸納為三個種類:

sources $O$
network function $N$
destinations $T$
而每個edge $e_{m,n} \in E_{n}$ 代表網路功能$m$與$n$之間的網路流量
對於鏈 $c_{i}$ 中的每個服務對(service pair) $(s_{i,j},s_{i,j+1})$，在$G_{n}$中存在一個網路功能對(network function pair)
$(m,n)$，存在從$m$到$n$的有向鏈結，其中 $n(s_{i,j})=m$ , $n(s_{i,j+1})=n$

如同剛剛提及，不同網路功能可能會由不同服務鏈以不同的網量速率來共享功能
對於每個edge $e_{m,n} \in E_{n}$，我們定義一個集合 $U_{m,n} = { i : c_{i} \in C, n(s_{i,j})=m,n(s_{i,j+1})=n}$ 來記錄具有網路功能對($m$,$n$)的服務鏈

存在具有不同流量要求的不同網路流量在edge $e_{m,n}$ 上傳輸，表示為 $R_{i}$, $\forall i \in U_{m,n}$
舉例來說，來自服務鏈 $c1$ 和 $c2$ 的網路流量在 edge $e_{f_{1},f_{2}}$上傳輸，如下圖所示

速率分別是 2與1

D. VNFs Graph

我們的目標是要以VNF instance形式來在圖 $G_{n}$ 之中部屬所有網路功能
$G_{n}$中每個網路功能n可能會有多個VNF Instances 在不同資料中心
舉例來說如下圖

網路功能 $f1$可能會有兩個VNF Instance分別位於資料中心 $d1$以及 $d2$

注意，每個網絡功能 $n$ 在所有 $|D|$ 數據中心中可能最多有 $|D|$ 可能的Instance，
並且 $G_{n}$ 中的每一對 $(m,n)$ 也可能相應地在它們之間最多有 $|D|^{2}$ 個鏈接。

因此，在VNF圖 $G_{v}=(V_{v},E_{v})$，節點集合 $V_{v}$ 包括 $|V_{n}| \cdot |D|$ instances 表示為集合 $V$、sources集合 $O$以及目標節點集合 $T$，而 $E_{v}$ 表示他們之間的鏈結。
對於每個edge $e_{u,v} \in E_{v}$，讓 $f^{i}{uv}$ 註記為服務鏈 $C{i}$中 instance $u$,$v$ 間的流量速率。

舉例來說，我們考慮圖 $G_{n}$ 中的兩個網路功能 $(f1,f2)$ 以及edge $e_{f_{1},f_{2}}$，對應的 $G_{v}$ 在下圖中顯示，有 2 個資料中心

$f1,f2$的Instance分別是 $v1$ $v2$ 以及 $v3$ $v4$，並且j我們可以觀察到，網路功能 $f1$ $f2$共有4個edge，而𝑓1和𝑓2之間的網絡流量可以在這四個edge之間自由分佈

於任何實例$v \in V$，我們使用$d(v)$ 和$n(v)$分別表示其資料中心位置和網絡功能類型。例如，$d(v_{1})=d1$，$n(v_{1})=f1$

Let $N(n)$ 代表提供網路功能 $n$的VNF集合，例如在上圖中，我們有 $v1$以及 $v2$ 來提供網路功能 $f1$，即 $N(f1)={ v1,v2 }$，對於每個 VNF Instance Pair $(u,v)$，可以透過 $f_{uv}^{i}$ 來表示流經邊緣的網路流量速率。
其中對於鏈 $c_{i}$ 上的邊緣滿足 $e_{u,v}\in E_{v}$
且在圖 $G_{v}$中，$\forall i\in U_{n(u),n(v)}$

Ch3-Problem Formulation

基於上一章的系統模型，我們可以公式化VNF部屬以及流量調度問題，轉換成混合整數線性規劃問題
(MILP)，且目標是要最小化所有VNF Pairs之間的部屬以及通訊總成本

VNF Instance Placement

如圖$G_{v}$所示，每個網絡功能可以由所有資料中心託管，每個資料中心可以託管所有類型的網絡功能，因此我們定義了二進位的變數 $x_{v}$ 來表示 在資料中心 $d(v) 中負責提供的網路功能 $n(v)$ 的VNF Instance 是否被實際部屬

Flow requirement constraints

對於每個服務鏈 $c_{i}$ 所需要的流量，可被分配到所有它的VNF Instance上
例如，鏈 $c_{i}$中的網絡功能pair $m$、$n$ 之間的網絡流率 $R_{i}$ 將分佈到$G_{v}$中Instance $v$、$u$ 之間的所有邊上，其中$n(u)=m$，$n(v)=n$

對於來源節點與目標節點，可以列出以下等式

VNF flow constraint

對於每個VNF Instance，輸入流量是源自輸入instance $i(v)$來處理
然後分散到輸出instance $o(v)$

其中 $\alpha_{n(v)}$ 是由網路功能來決定的擴展因子(scaling factor)

The relationship between $x_{v}$ and $f^{i}_{uv}$

只要有流量通過 VNF 實例 $v$，二進位變數應設定為 1 以提供網絡功能$n(v)$，並且此 VNF 實例應部署在$d(v)$ 中。這可以描述為

A Joint MILP Formulation

若把上述總結，可以得到以下的 Cost-min 問題

Cost-Min

係數 $\gamma$ 和 $\delta$ 由用戶定義，以平衡部署成本和通訊成本，並可根據不同的 QoS 要求進行調整。

Ch4-Relaxation-Based Algorithm

因為有整數變數 $x_{v}$ ，計算上來解決 Cost-Min問題是被禁止的，特別規模大的網路中。
此章節中，我們會提出基於鬆散的方式，來解決Cost-min問題。

首先我們將 $x_{v}$ 鬆弛為[0,1]範圍內的實數，以降低計算複雜度。經過鬆弛後，我們的模型被簡化為線性規劃(LP)問題，如演算法中第1行，這可以透過Matlab輕鬆解決。

我們對 $x_{v}$ 做遞增排序，如演算法表中第2行，

並將每個非零 $x_{v}$ 的值設為1，如演算法表中第5行，

在這種情況下，我們以整數 $x_{v}^{*}$ 形式獲得一個新的 VNF 部署解決方案，

並將每個網絡功能的 VNF Instance 數量記錄為 $count_{n(v)}$，如演算法表中第6行，
我們將整數solution $ x_{v}^{*} $ 作為輸入並計算流量調度的解答 $ f_{uv}^{*j} $ ，且總成本 $cost’$

我們將整數解 $x_{v}^{*}$ 作為輸入，通過在第 11 行再次求解 Cost-Min-LP 問題來計算流量調度解 $f_{uv}^{*j}$ 和總成本 $cost’$

請注意，放寬可能會導致更多 VNF 實例，因此我們下一步將嘗試進一步減少實例數量以及部署成本，同時確保從第 12 行到第 22 行間的通訊成本接近最佳化。
我們從非零 $x_{v}$ 的最小值內的實例 $v$ 開始。
請注意，如果$v$是網絡中唯一提供網絡功能$n(v)$的VNF實例，即$count_{n(v)}$ == 1，則必須部署$v$，並且跳到下一個Instance
否則，若網路中存在提供相同網路功能 $n(v)$的VNF Instance(見14行)，則我們$x_{v}^{*}$ 設為0，並重新計算流量調度解 $f_{uv}^{*i}$ 和新的總成本 $cost’$

只有當新成本低於當前的 $minCost$時，才會更新NFV部屬解 $x_{v}^{*}$、流量調度解 $f_{uv}^{*j}$ 以及總成本 $minCost$，然後更新網路功能 $n(v)$的Instance數量 (見18、19行)

另一方面，如果總成本沒有降低，我們將 $x_{v}^{*}$ 的值設置回 1 並移動到下一個實例，直到我們遍歷 $V$ 中的所有 VNF 實例（第 25 行）

最終我們會返回 NFV部屬解 $x_{v}^{*}$、流量調度解 $f_{uv}^{*j}$ 以及總成本 $minCost$ 作為演算法的輸出。

Ch5-Performance Evaluation

在本節中，我們通過將基於鬆弛的算法 (“RLX”) 與 Cost-Min 的最佳結果 (“OPT”) 和最短路徑算法 (“SP”) 進行比較來評估它
實驗設置：

網絡中有∣𝐷∣ = 20 個資料中心。 $H_{dp}$ 隨機設置在 [1,20] 的範圍內，表示DC之間的跳躍數
共有 20 條服務鏈，多條鏈共享 15 種不同類型的網絡功能
服務鏈的流量設置在 [1, 10] 的範圍內
係數 $\gamma$ 設置為 10，$\delta$ 設置為 1
我們使用商業求解器 Gurobi 來解決我們的 Cost-Min 和 Cost-Min-LP 問題
本研究通過在不同場景中改變參數提供了廣泛的實驗

The value of 𝛾

首先，我們調查𝛾和𝛿的影響。我們設置 𝛿 = 1，並將 𝛾 的值從 5 變為 50。結果如圖 4 所示
圖 4 中的結果表明，三種算法的所有成本都隨著 𝛾 的增加而增長。原因是，𝛾的增加會導致更高的 VNF 部署成本。
得注意的是，SP 的增長率遠大於其他兩種算法，因為 SP 主要通過減少每個網絡流的路徑長度來關注通信成本，而忽略了部署成本。
因此，當部署成本成為主導部分時，SP 顯示的優勢較小
例如，當𝛾 = 10 時，RLX 算法的部署成本佔總成本的比例為 57%，OPT 為 35%，SP 為 82%。

The effect of number of hops

我們通過將跳數的上限從 2 變為 20 來研究不同網絡拓撲的 OPT、RLX 和 SP 的總成本
從圖 5 可以看出，OPT 和 RLX 的成本隨著跳數的增加而略有增長，因為跳數的增加可能會增加通信成本。

然而，SP卻呈現出下降的趨勢。主要原因是當不同數據中心之間的跳數都很小時，SP可以找到很多最短路徑並在這些路徑上部署VNF實例，而某些網絡功能可能有多個實例，導致部署成本較高。
當跳數增加時，SP 只會找到更少的最短路徑，從而導致 VNF 實例更少，部署成本更低。因此，總成本降低。

The effect of rate

同樣，我們將 20 條鏈的速率要求上限從 3 更改為 30，以顯示流量要求的影響。
圖 6 顯示，當速率上限增加時，所有三種算法的總成本也會增加。
這是因為增加流量會導致更高的通信成本以及總成本。

The effect of the number of chains

在這一部分，我們討論了鏈數從 5 到 50 的影響，並比較了三種算法的結果。
所有三種算法的上升趨勢都可以在圖 7 中觀察到。
原因是更多的服務鏈帶來了更多的網絡功能部署在數據中心，更多的網絡流分佈到 VNF 實例。
這將導致更高的部署成本和通信成本，因此所有三種算法的總成本都會上升

The effect of the number of NFs

最後，圖 8 顯示了所有三種算法的結果，網絡功能的數量從 10 到 55 不等
可以得出，成本也上升了。這是因為所有算法都需要在數據中心放置更多的 VNF 實例，從而導致部署成本的增加。同時，不同數據中心的網絡功能之間更多的網絡流量也會導致通信成本的增加。因此，總成本呈上升趨勢。
儘管如此，我們的RLX 的優勢始終可以在任何設置下觀察到，因為它優於SP 並接近OPT