概要

• 論文連結，2017 ICC
• Notion 筆記

為了解決網路負載，挑選好地方置放 Servcie Function Chain (SFC) 是個難題。

因為 VNFs 只能放在資料中心，因此使用較小的 cluster server 以縮短使用者到達資料中心的距離會是較佳的方式，但資源利用率是個問題。

編按：不只能放在資料中心吧？

作者設計並比較三種 allocation & replication 的方法：

1. Linear Programming (LP)
2. Genetic Algorithm (GA)
3. Random Fit Placement Algorithm (RFPA)

同時也提出 GA heuristics 演算法，結果顯示最佳化的 placement & replication 可以大幅地改善負載平衡。

介紹

VNF 置放地點的選擇可依數量分成兩種：

• 少而集中
  • 硬體設備不用買那麼多
  • 距離遠，傳輸成本增加
• 多而分散
  • 需買較多硬體，且需計算利用率
  • 距離近，傳輸成本低

為了找到最佳化的置放位置，作者將問題定為 Mixed Integer Programming (MIP)

編按：文末「整數規劃」有 MIP 介紹

參考架構

NFV 資源分配問題可以分成三種步驟：

1. VNFs Chain Composition (VNFs-CC)
   • 在 data center 跟 mobile network 尤其重要
   • IETF Network and Service Chaining Working Groups 有在貢獻
2. VFN Forwarding Graph Embedding (VNF-FGE)
   • 根據需求尋找VNF 置放位置
     • 計算資源
     • 能源資源
     • 網路負載平衡
   • 也被叫做 VNF placement problem
3. NFs Scheduling ( VNFs-SCH)
   • 對 VNF 的執行做排程
   • 以降低整體運行時間

SFC in Mobile Core Network

S-GW, P-GW 對應到 VNF1，這兩個都是 non-replicable 的，後面的設備如防火牆與 NAT 都是 replicable。

作者這份研究是針對 mobile network 後面那些 replicable 的 VNF 做擺放位置的最佳化，因此會決定出擺在哪、擺多少。

知道了需要擺多少的 VNF 以維持良好的網路負載平衡，就可以知道要佈建多少台 Server。

Network Traffic Model

作者假定有兩種網路流量：

1. background traffic
   • 從每個核心節點（core node）產生的流量，會流到其他節點
   • 使用傳統網路核心協定（traditional network core protocol）
2. data center traffic
   • 從 data center 產生，座落在不同的網路部分，導向到 Internet gateway
   • 由終端用戶產生，通常是 TCP
   • 在接上網際網路前會經過一連串的 network function

最佳化模型

此章節將 TE、RA 描述為具有 objective function 的最佳化問題，能夠最小化所有 link 的開銷：

$$Minimize: \sum_{\ell \in \overrightarrow{L}}{K_\ell}$$

每條 link 的線性 cost function: $y_{i}\left(U_\ell\right) = a \cdot U_\ell - b$，其中 $U_\ell$ 是 link utilization，也就是下圖括號中的部分：

$$K_{\ell} \geq y_{i}\left(\sum_{s \in \vec{S}} \sum_{p \in \vec{P}} \sum_{\lambda \in \vec{\Lambda}{b g \mid s}} \frac{\lambda \cdot\left(R{p}^{\lambda} \mid R_{p, s}^{\lambda}\right) \cdot t_{p}^{\ell}}{c_{\ell}}\right)$$

其中：

• $R^{\lambda}_{p}$ 是用在 TE 的情況
• $R^{\lambda}_{p, s}$ 是用在 RA 的情況

而作者假設所有 link 的 utilization 在 60% 以下的開銷都是 0，60% 以上的開銷成指數成長。

Routing constrain:

for TE: $\forall \lambda \in \overrightarrow{\Lambda_{b g}}: \sum_{p \in \vec{P}} R_{p}^{\lambda}=1$

for RA: $\forall \lambda \in \vec{\Lambda_{s}}: \sum_{s \in \vec{S}} \sum_{p \in \vec{P}} R_{p, s}^{\lambda}=1$

上面這兩個例子都是每個 traffic demand 都只能用在一條路徑上

其中第二個是因為可能有不同的 SFC 用了同個 path

---

接著這邊都是給 RA 的限制了

traffic demand 只能在 service chain 使用時而存在

$$\forall p \in \vec{P}, \forall s \in \vec{S}, \forall \lambda \in \vec{\Lambda_{s}}: R_{p, s}^{\lambda} \leq R_{p, s}$$

這 $\leq$ 代表 SFC 有用這 path 但不一定有 traffic demand

在 [0, 1, 2, … r] replicas 的情況下，SFC 可以使用的 path 數量

$$\forall s \in \vec{S}: 1 \leq \sum_{p \in \vec{P}} R_{p, s} \leq r_{m a x}+1$$

SFC 中所有的 VNF 都有分配到 path 上的 node

$$\forall p \in \vec{P}, \forall s \in \vec{S}, \forall v \in \vec{V_{s}}: R_{p, s} \leq \sum_{n \in p} F_{s, v}^{n}$$

也就是 p 上至少有 1 個 node 被 s 中的 VNF 使用

但這似乎沒有確保分配完 VNF

同一個 SFC 中的兩條 path 不會挑選同個 node 去部署相同的 VNF

$$\begin{array}{c}\forall s \in \vec{S}, \forall p_{1} \in \vec{P}, \forall p_{2} \in \vec{P}, \forall v \in \vec{V_{s}}, \forall n \in p_{1}, p_{2}: R_{p_{1}, s}+R_{p_{2}, s}+2 F_{s, v}^{n} \cdot r_{v} \leq 3\end{array}$$

也就是說 $R_{p_1}= F_{s, v}^{n} = 1$ 時成立；當 $R_{p_1}= R_{p_2} = 1$ 時 $F_{s, v}^{n}$ 已經是 1 因此不能繼續放。

這條件應是在置放前的 if 判斷式

編按：但是不同的 SFC 然後相同的 VNF 呢？

確保 VNF 的順序性

在 path $p$ 中 function $v$ 不能被分配到 node $n$ 除非前一個 function $v-1$ 已經被分配到前一個節點上

$$\left(\sum_{m=0}^{n-1} F_{s, v-1}^{m}\right)-F_{s, v}^{n} \geq R_{p, s}-1$$

節點上放置 VNF 的上限

$$\forall n \in \vec{N}: \sum_{s \in \vec{S}} \sum_{v \in \vec{V}{s}} F{s, v}^{n} \leq 1$$

這在說此節點上只能放置一個 VNF

replicable function 的數量上限

$$\sum_{n}^{N} F_{s, v}^{n} \leq 1+r_{m a x} \cdot r_{v}$$

啟發式演算法

VNF allocation 已經被知道是 NP-hard 問題，linear programming model 只能用在小型網路當中，大型網路必須要用啟發式演算法。

作者根據上面的最佳化模型提出 Genetic Algorithm 來解決此問題，此外還提出 Random Fit Placement Algorithm（RFPA）來驗證作者的 GA 有效解決負載平衡問題，RFPA 其實就是隨便擺。

Genetic Algorithm (Algorithm 1)

拆成三部分：

1. Traffic Engineering (TE-GA)
   • 從輸入參數挑選一些有資格的 path
   • 計算網路開銷
   • 輸出 path 將作為 RA-GA 的輸入
2. Resource Allocation (RA-GA)
   • 負責 VNF 的分配
   • 選擇節點
     • 根據 data center 流量的網路開銷
     • 根據 TE-GA 給的 path
     • 選到的節點將會作為「尋找替代路徑」的參數
   • 選擇的節點將作為 RR-GA 的輸入
3. Resource Replication (RR-GA)
   • 負責分配 replica
     • 根據上限值
   • 一直分配 replica 直到所增加的 replica 無法改善 cost

Random-Fit Placement Algorithm

• 隨機擺放 VNF
• 依照正確順序尋找可行的 path，越多 replica 越好
• 對於每個 traffic deman，只會隨機選擇一條 path
• 輸出結果會是 total network cost、被選擇的節點

效能評估

作者比較了：

1. Genetic Algorithm (作者提出的）
2. Gurobi Optimizer (Linear Programming solver)
3. Random Allocation Approach

下面是從 SNDLib 網站挑選的拓樸測資： 參數有，nodes/links 的數量、connection 數量、Data Center 頻寬、Background 頻寬

為了使結果可以在不同的拓樸中比較，data center （例如 S-GW, P-GW function）的數量固定為 2，最大 link 負載為 2.5 Gbps。

Background traffic 隨機產生，間隔為 background bandwidth，並且確保 TE model 的開銷永遠小於 1，也就是不會有瓶頸的產生。

Service chain 的長度為兩個 end-point (例如 S-GW, P-GW datacenter & border gateway)、與一個位於中間的 VNF。

作者假設 border gateway 的位置是 random fixed parameter；而 S-GW/P-GW 和 VNF 的位置都是根據最佳化而不同。

Link utilization 結果

Nobel-us

Janos-us

Network cost & # of replicas

Computation Time

名詞解釋

整數規劃 (Integer Programming)

整數規劃是指一類要求問題中的全部或一部分變數為整數的數學規劃。是近三十年來發展起來的、規劃論的一個分支. 整數規劃問題是要求決策變數取整數值的線性規劃或非線性規劃問題。

整數規劃的種類

1. 純整數規劃：所有決策變數均要求為整數的整數規劃
2. 混合整數規劃 (Mixed Integer Programming, MIP)：部分決策變數均要求為整數的整數規劃
3. 純0－1整數規劃：所有決策變數均要求為0－1的整數規劃
4. 混合0－1規劃：部分決策變數均要求為0－1的整數規劃

整數規劃與線性規劃不同這處只在於增加了整數約束。不考慮整數約束所得到的線性規劃稱為整數規劃的線性鬆弛模型。

參考來源：MBA智庫

SAE 結構體系

System Architecture Evolution 是 3GPP 所制定的 LTE 無線通信核心網路標準，傳輸全使用 IP 網路，從而支援系統的 control plane 與 data plane 分離。

其核心為 EPC (Evolved Packet Core)，包含 MME, S-GW, P-GW 等等。

MME

移動性管理實體（MME，Mobility Management Entity）：MME是LTE接入網絡的關鍵控制節點。它負責空閒模式UE（用戶設備）跟蹤和尋呼控制。這些內容也包括UE的註冊與註銷過程，同時幫助UE 選擇 S-GW，以完成LTE系統內核網路（CN）節點切換。

通過與用戶歸屬伺服器（HSS）的信息交流，MME 完成用戶驗證功能。MME 是非接入層（NAS）信令的終結點，它負責生成和分配 UE 的臨時 ID。它通過鑒權，決定 UE 是否能享受本服務提供商的服務，並對 UE 做漫遊限制。MME 是為 NAS 信令提供加密/完整性保護的網絡節點，並且負責安全密鑰管理。MME 也支持對信令的合法監聽。

S-GW

服務網關（SGW，Serving Gateway）：S-GW 負責用戶數據包的路由和轉發。當 UE 在 eNodeB 之間中繼（handover）或在LTE與其他3GPP無線技術（RAT，Radio Access Technology）之間移動時，SGW 是其用戶面數據的錨點，它通過 S4 接口與 2G/3G 系統的SGSN通信。

對於空閒狀態的UE，SGW是下行數據路徑的終點，在下行數據到達時觸發對UE的尋呼。SGW 管理和存儲 UE 的上下文（context），其內容包括為 UE 提供的 IP 承載（bearer）的參數、網絡內部的路由訊息等。如果使用合法監聽功能，它還對用戶所傳輸的數據進行複製。

P-GW

PDN 閘道器（PGW，PDN Gateway）：PDN 閘道器作為連線點， 為 UE 提供與 公共資料網 （PDN）之間的傳輸 。一個 UE 可以同時透過多個 PGW 訪問多個 PDN。PGW 實現控制策略的實施、針對使用者的資料包過濾、計費、 合法監聽 與資料包篩選。 PGW 的另一個關鍵作用的是作為 3GPP 和非 3GPP 網路（例如 WiMAX 和 3GPP2 的 CDMA 1X 和 EvDO）之間的移動性管理錨點。

HSS

歸屬用戶伺服器（HSS，Home Subscriber Server）：HSS是一個中央資料庫，包含與用戶信息和所訂閱的服務的信息。HSS的功能包括:移動性管理，呼叫和會話建立的支持，用戶認證（authentication）和訪問授權（authorization）。 HSS的功能是2G、3G核心網的歸屬位置暫存器（HLR）和認證中心（AuC）的擴展。

參考來源：維基百科

SNDLib

一個網路設計的測試函式庫，裡面有多種測資。

What is SNDlib?

SNDlib is a library of test instances for Survivable fixed telecommunication Network Design. Its purpose is

• to make realistic network design test instances available to the research community,
• to serve as a standardized benchmark for testing, evaluating, and comparing network design models and algorithms,
• to be a source of information and resources related to fixed network design, and
• to provide a contact platform for researchers and practitioners working in this field.

Why SNDlib?

In the field of telecommunication network design problems, proposed solution approaches range from LP-/IP-based models and algorithms such as branch-and-bound, row and column generation, or Lagrangian relaxation to meta-heuristics such as evolutionary algorithms, simulated annealing and tabu search.

---

• ← Previous Post
• Next Post →

comments powered by Disqus