一種基于匹配博弈的服務(wù)鏈協(xié)同映射方法
doi: 10.11999/JEIT180385
-
中國人民解放軍信息工程大學(xué) ??鄭州 ??450001
A Collaborative Mapping Method for Service Chain Based on Matching Game
-
The Information Engineering University of PLA, Zhengzhou 450001, China
-
摘要:
針對軟件定義網(wǎng)絡(luò)(SDN)/網(wǎng)絡(luò)功能虛擬化(NFV)環(huán)境下服務(wù)鏈映射難以兼顧效率與物理資源利用率的問題，該文提出一種基于匹配博弈的服務(wù)鏈協(xié)同映射方法。首先，以最大化網(wǎng)絡(luò)資源效用為目標(biāo)，建立服務(wù)鏈映射模型MUSCM；然后，分虛擬網(wǎng)絡(luò)功能(VNF)部署和組鏈兩個部分解決服務(wù)鏈映射問題，VNF部署部分，設(shè)計基于多對一匹配博弈理論的算法協(xié)同服務(wù)鏈和服務(wù)節(jié)點雙方互相進(jìn)行選擇，有效提升了服務(wù)鏈的映射效率和物理資源的利用率，在此基礎(chǔ)上，設(shè)計基于分段路由策略的算法實現(xiàn)各VNF實例間的流量牽引以完成VNF組鏈，有效降低了鏈路傳輸時延。實驗結(jié)果表明，與經(jīng)典算法相比，該算法在保證映射請求接受率的同時，有效降低了服務(wù)鏈的平均傳輸延時，提升了系統(tǒng)的物理資源利用率。
-
關(guān)鍵詞:
- 軟件定義網(wǎng)絡(luò) /
- 網(wǎng)絡(luò)功能虛擬化 /
- 服務(wù)鏈映射 /
- 匹配博弈 /
- 分段路由
Abstract:Considering that it is difficult to balance efficiency and resource utilization of Service Chain (SC) mapping problem in Software Defined Network (SDN)/Network Function Virtualization (NFV) environment, this paper proposes a collaborative mapping method for SC based on matching game. Firstly, it defines a SC mapping model named MUSCM to maximize the utility of network resources. Secondly, it divides the SC mapping problem into Virtual Network Function (VNF) deployment and connection parts. As for the VNF deployment part, an algorithm is designed to collaborate the selection of the SC and the service node based on many-to-one matching game, improving the mapping efficiency of SC and utilization of physical resource effectively. On the basis of it, an algorithm is designed based on segment routing strategy to accomplish the traffic steering between VNF instances to finish the VNF connection part, reducing the link transmission delay effectively. The experiment result shows that, compared with the classical algorithm, this algorithm ensures the mapping request received rate, and at the same time, it reduces the average transmission delay of the service chain and improves the physical resources utilization of the system effectively.
-
表 1 主要符號列表
符號 描述 $G$ 物理基礎(chǔ)設(shè)施無向圖$G = (N,E)$ $N$ 物理節(jié)點集合，$n \in N$ $E$ 物理鏈路集合，$e\left( {{n_i},{n_j}} \right) \in E$ ${N^F}$ 轉(zhuǎn)發(fā)節(jié)點集合 ${N^S}$ 服務(wù)節(jié)點集合 ${I_k}$ 資源種類，${I_k} = \left\{ {{\rm{CPU}},{\rm{Me}},{\rm{Th}}} \right\}$ ${\rm{vol}}_n^{{I_k}}$ 服務(wù)節(jié)點$n$的${I_k}$類資源的容量 ${\rm{vol}}_{e\left( {{n_i},{n_j}} \right)}^{\rm band}$ 服務(wù)節(jié)點${n_i}$和${n_j}$間物理鏈路的帶寬資源容量 $P$ 網(wǎng)絡(luò)中可提供的所有VNF種類集合 ${F^p}$ 類型為$p$的VNF實例集合，${f^p} \in {F^p}$ ${R^c}$ 構(gòu)成服務(wù)鏈$c$的VNF實例集合 $d_{{f^p}}^{{I_k}}$ VNF實例${f^p}$的${I_k}$類資源需求 $C$ 服務(wù)鏈集合，$c \in C$ $d_c^{{I_k}}$ 服務(wù)鏈$c$的${I_k}$類資源需求 $d_{{f^p},{f^{p'}}}^c$ 服務(wù)鏈$c$中實例${f^p}$和${f^{p'}}$間的帶寬資源需求 $X_{{f^p},n}^c$ 服務(wù)鏈$c$中VNF實例${f^p}$與服務(wù)節(jié)點$n$映射關(guān)系 
下載: 導(dǎo)出CSV
表 2 服務(wù)鏈匹配偏好表構(gòu)建算法
算法1 服務(wù)鏈匹配偏好表構(gòu)建算法 輸入：構(gòu)成服務(wù)鏈$c$的VNF實例集合${R^c}$，服務(wù)節(jié)點集合${N^S}$，物 理基礎(chǔ)設(shè)施圖$G$ 輸出：服務(wù)鏈匹配偏好表${\rm SC}\left( {{N^S}} \right)$ (1) 根據(jù)輸入初始化； (2) for each $n$ in ${N^S}$ do 依據(jù)式(8)計算資源偏差$\Delta R$； 選擇$\Delta R$最小的服務(wù)節(jié)點${n_0}$； ${\rm{SC}}\left( {{N^S}} \right) \leftarrow \left\{ {{n_0}} \right\}$；//將${n_0}$作為起始節(jié)點，并加入偏好表 將${n_0}$標(biāo)記為已讀； end for (3) while ${N^S}$中存在未讀節(jié)點 do 依據(jù)NNA算法尋找圖$G$中距離當(dāng)前節(jié)點最近的且滿足資源 約束條件(式(3)、式(4))的下一服務(wù)節(jié)點${n_w}$； ${\rm{SC}}\left( {{N^S}} \right) \cup \left\{ {{n_w}} \right\}$；//將${n_w}$加入偏好表
將${n_w}$標(biāo)記為已讀；(4) 所有服務(wù)節(jié)點已讀則終止； (5) 返回步驟(3)； (6) 輸出服務(wù)鏈匹配偏好表${\rm{SC}}\left( {{N^S}} \right)$
下載: 導(dǎo)出CSV
表 3 服務(wù)節(jié)點匹配偏好表構(gòu)建算法
算法2 服務(wù)節(jié)點匹配偏好表構(gòu)建算法 輸入：構(gòu)成服務(wù)鏈$c$的VNF實例集合${R^c}$，服務(wù)節(jié)點集合${N^S}$ 輸出：服務(wù)節(jié)點匹配偏好表${N^S}\left( {\rm{SC}} \right)$ (1) 根據(jù)輸入初始化； (2) for each ${f^p}$ in ${R^c}$ do 按資源需求對${f^p}$進(jìn)行排序； //資源需求優(yōu)先級依次為
$\rm{CPU} > \rm{Me} > \rm{Th}$依據(jù)BFA算法選擇剩余資源空間最小的VNF實例${f^p}$； ${N^S}\left( {\rm{SC}} \right) \cup \left\{ {{f^p}} \right\}$； //將${f^p}$加入偏好表
將VNF實例${f^p}$標(biāo)記為已讀；end for (3) 所有VNF實例已讀則終止； (4) 返回步驟(2) (5) 輸出服務(wù)節(jié)點匹配偏好表${N^S}\left( {\rm{SC}} \right)$
下載: 導(dǎo)出CSV
表 4 博弈選擇算法
算法3 博弈選擇算法
輸入：構(gòu)成服務(wù)鏈$c$的VNF實例集合${R^c}$，服務(wù)節(jié)點集合${N^S}$
輸出：服務(wù)鏈和服務(wù)節(jié)點的平穩(wěn)匹配結(jié)果
根據(jù)輸入初始化；
if 服務(wù)鏈$c$是不飽和的 do
for each ${f^p}$ in ${R^c}$ do
$n \leftarrow $get highest rank in ${\rm \rm{SC}}\!\left( {{N^S}} \right)$;
if $\left( {{\rm{vol}}_n^{{I_k}} > d_{{f^p}}^{{I_k}}} \right)\& \& \left( {{f^p} \ \ {\rm in} \ \ {N^S}\left( {\rm{SC}} \right)} \right)$ then
將${f^p}$匹配給$n$；
${\rm{vol}}_n^{{I_k}} = {\rm{vol}}_n^{{I_k}} - d_{{f^p}}^{{I_k}}$;
end
else
找出所有滿足${f^p}\mathop \succ \limits_n {f^{p'}}$的${f^{p'}}$;
拒絕所有${f^{p'}}$并更新服務(wù)節(jié)點$n$的資源；
${\rm{vol}}_n^{{I_k}} = {\rm{vol}}_n^{{I_k}} - d_{{f^p}}^{{I_k}}$;
將${f^{p'}}$從服務(wù)節(jié)點映射偏好表${N^S}\left( {\rm{SC}} \right)$中移除；
將$n$從服務(wù)鏈映射偏好表${\rm{SC}}\left( {{N^S}} \right)$中移除；
end
end for
輸出匹配結(jié)果；
else
return
下載: 導(dǎo)出CSV
表 5 分段路由連接算法
算法4 分段路由連接算法 輸入：VNF實例與服務(wù)節(jié)點間的映射關(guān)系$\varOmega $ 輸出：服務(wù)鏈$c$的路由路徑 根據(jù)輸入初始化； 依據(jù)式(11)表達(dá)$\varOmega $中服務(wù)節(jié)點的分段路徑，構(gòu)成集合$S$ for each ${\rm{FG}}\left( {n_{i - 1}^{ma},n_i^{ma}} \right)$ in $S$ do 利用SPA算法計算連接路徑； end for 輸出計算結(jié)果； return
下載: 導(dǎo)出CSV
表 7 VNF參數(shù)設(shè)置
VNF種類 CPU 內(nèi)存(GB) 吞吐量(Mbps) Firewall 8 4 200 IDS 8 4 80 IPS 4 4 268 WAN-opt 2 2 10
下載: 導(dǎo)出CSV
-
KREUTZ D, RAMOS F M V, VERíSSIMO P E, et al. Software-defined networking: A comprehensive survey[J]. Proceedings of the IEEE, 2015, 103(1): 14–76. doi: 10.1109/JPROC.2014.2371999 MIJUMBI R, SERRAT J, GORRICHO J L, et al. Network function virtualization: State-of-the-art and research challenges[J]. IEEE Communications Surveys and Tutorials, 2017, 18(1): 236–262. doi: 10.1109/COMST.2015.2477041 OCAMPO A F, GIL-HERRERA J, ISOLANI P H, et al. Optimal service function chain composition in network functions virtualization[C]. International Conference on Autonomous Infrastructure, Management and Security, Zurich, Switzerland, 2017: 62–76. LI Yong and CHEN Min. Software-defined network function virtualization: A survey[J]. IEEE Access, 2015, 3: 2542–2553. doi: 10.1109/ACCESS.2015.2499271 BHAMARE D, JAIN R, SAMAKA M, et al. A survey on service function chaining[J]. Journal of Network and Computer Applications, 2016, 75: 138–155. doi: 10.1016/j.jnca.2016.09.001 DWARAKI A and WOLF T. Adaptive service-chain routing for virtual network functions in software-defined networks[C]. The Workshop on Hot Topics in Middleboxes and Network Function Virtualization, Salvador, Brazil, 2016: 32–37. XIONG Gang, HU Yunxiang, LAN Julong, et al. A mechanism for configurable network service chaining and its implementation[J]. KSII Transactions on Internet and Information Systems, 2016, 10(8): 3701–3727. doi: 10.3837/tiis.2016.08.016 SEKAR V, EGI N, RATNASAMY S, et al. Design and implementation of a consolidated middlebox architecture[C]. Usenix Conference on Networked Systems Design and Implementation, Lombard, Italy, 2012: 24–34. KUO Tunwei, LIOU Bangheng, LIN Chingju, et al. Deploying chains of virtualnetwork functions: On the relation between link and server usage[C]. IEEE International Conference on Computer Communications, San Francisco, USA, 2016: 1–9. ZHANG Qixia, XIAO Yikai, LIU Fangming, et al. Joint optimization of chain placement and request scheduling for network function virtualization[C]. IEEE International Conference on Distributed Computing Systems, Atlanta, USA, 2017: 731–741. GALE D and SHAPLEY L S. College admissions and the stability of marriage[J]. American Mathematical Monthly, 1962, 69(1): 9–15. doi: 10.4169/amer.math.monthly.120.05.386 XU Hong and LI Baochun. Anchor: A versatile and efficient framework for resource management in the cloud[J]. IEEE Transactions on Parallel and Distributed Systems, 2013, 24(6): 1066–1076. doi: 10.1109/TPDS.2012.308 ZHANG Yan and ANSARI N. Heterogeneity aware dominant resource assistant heuristics for virtual machine consolidation[C]. Global Communications Conference, Austin, USA, 2014: 1297–1302. CORMEN T T, LEISERSON C E, RIVEST R L, et al. Introduction to Algorithms[M]. McGraw, USA, MIT Press, 2002: 145–167. MANLOVE D. Algorithmics of Matching under Preferences[M]. Glasgow, UK, World Scientific Pub. Co, 2013: 266–278. FILSFILS C, NAINAR N K, PIGNATARO C, et al. The segment routing architecture[C]. Global Communications Conference, San Diego, USA, 2015: 1–6. CALVERT K L and BHATTACHARJEE S. How to model an internetwork[C]. IEEE Conference of Computer Societies, San Francisco, USA, 1996: 594–602. -
計量
- 文章訪問數(shù): 1850
- HTML全文瀏覽量: 759
- PDF下載量: 71
- 被引次數(shù): 0
下載:
