基于時頻聯(lián)合碎片感知的資源均衡虛擬光網(wǎng)絡映射算法
doi: 10.11999/JEIT171208
-
1.
重慶郵電大學重慶市光纖通信技術與網(wǎng)絡重點實驗室 重慶 400065
-
2.
重慶郵電大學自動化學院 重慶 400065
-
3.
國網(wǎng)冀北電力有限公司信息通信分公司 北京 100053
基金項目: 國家自然科學基金(61275077)，重慶市基礎與前沿研究項目(2015jcyjA40024)，國家電網(wǎng)公司科學技術項目
Resources Balancing Algorithm Based on the Time-frequency Fragment Awareness for Virtual Optical Network Mapping
-
1.
Key Laboratory of Optical Communications and Networks, Chongqing University of Posts and Telecommunications, Chongqing 400065, China
-
2.
School of Automation, Chongqing University of Posts and Telecommunications, Chongqing 400065, China
-
3.
Information & Telecommunication Company, State Grid Jibei Electric Power CLP, Beijing 100053, China
Funds: The National Natural Science Foundation of China (61275077), The Basic and Frontier Research Program of Chongqing (2015jcyjA40024), The National Electric Net Ltd. Technology Project
-
摘要: 為了解決虛擬光網(wǎng)絡映射中帶寬阻塞率較高以及底層資源消耗不均勻問題，論文提出一種基于時間域-頻譜域碎片感知的虛擬網(wǎng)絡映射(FA-VNM)算法。該文綜合考慮頻隙在時間域和頻譜域上的碎片問題，設計時頻聯(lián)合碎片公式最小化分配過程中的頻譜碎片。進一步，為了均衡網(wǎng)絡中的資源消耗，在FA-VNM算法基礎上提出基于節(jié)點度數(shù)的負載均衡感知虛擬網(wǎng)絡映射(LB-VNM)算法，設計物理節(jié)點平均資源承載能力的公式，優(yōu)先映射物理節(jié)點平均資源承載能力大的節(jié)點；為了均衡路徑上資源使用，考慮路徑權重值，并根據(jù)每條路徑的權重值對虛擬鏈路進行映射，從而降低阻塞率。仿真結果表明，所提算法能有效降低阻塞率，提高資源利用率。
-
關鍵詞:
- 彈性光網(wǎng)絡 /
- 網(wǎng)絡虛擬化 /
- 時頻聯(lián)合碎片感知 /
- 負載均衡
Abstract: In order to address the problems of the high bandwidth blocking probability and imbalance resources consumption in physical network during virtual optical network mapping, Fragmentation-Aware based on time and spectrum domain of Virtual Network Mapping (FA-VNM) algorithm is proposed. In the FA-VNM algorithm, the fragments problem in the time domain and the spectrum domain is considered. Fragment formula jointly considering the time fragment and spectrum fragment is devised to minimize the spectrum fragments. Further, in order to balance the network resources consumption, based on the FA-VNM, Load Balancing based on degree of Virtual Network Mapping (LB-VNM) algorithm is proposed. In the stage of node mapping, physical node average resource carrying capacity is introduced and the physical node with larger average resources carrying capacity is mapped first. In order to balance the resource consumption in physical path, weight value of physical path is calculated in the stage of link mapping. Then, according to the weight value of each physical path, virtual links are mapped to achieve the purpose of load balancing for reduce the blocking rate. Simulation results show that the algorithms can effectively reduce the blocking rate and improve the resources utilization. -
表 1 參數(shù)對照表
參數(shù) 參數(shù)表達的含義 參數(shù) 參數(shù)表達的含義 $\vartheta _f^l$ 
二進制變量，如果鏈路l上第f個頻譜的使用情況，空
閑則為1，否則為0${\varphi _{e^{\rm{r}}},{p^{\rm{{s}}}}$ 
二進制變量，如果虛擬鏈路 ${e^{\rm{r}}}$ 映射在物理光路
${p^{\rm{s}}}$ 上，則為1，否則為0
${\xi _{{i^{\rm{r}}},{j^{\rm{s}}}}}$ 
二進制變量，如果虛擬節(jié)點 ${i^{\rm{r}}}$ 映射在物理節(jié)點
${j^{\rm{s}}}$ 則為1，否則為0
${\sigma _{e_1^{\rm{r}},e_2^{\rm{r}}}}$ 
二進制變量，如果虛擬鏈路 $e_1^{\rm{r}}$ 和虛擬鏈路
$e_2^{\rm{r}}$ 使用相同的物理鏈路則為1，否則為0
$C_i^{\rm{r}}$ 
虛擬節(jié)點 i 請求的計算資源 ${W_{{e^{\rm{r}}}}}$ 
整型變量，分配給虛擬鏈路 ${e^{\rm{r}}}$ 的連續(xù)頻譜塊的開始索引值
$C_j^{\rm{s}}$ 
物理節(jié)點 j 具有的計算資源 ${{{P}}^{{s}}}$ 
物理拓撲圖中預先計算的路徑集合 ${Z_{{e^{\rm{r}}}}}$ 
整型變量，分配給虛擬鏈路 ${e^{\rm{r}}}$ 的連續(xù)頻譜塊的結束索
引值${\rho _{e_1^{\rm{r}},e_2^{\rm{r}}}}$ 
二進制變量，如果分配給虛擬鏈路 $e_1^{\rm{r}}$ 的連續(xù)頻譜塊的開始索引值小于分配給虛擬鏈路
$e_2^{\rm{r}}$ 則為1，否則為0
下載: 導出CSV
表 2 FA-VNM算法
步驟1 虛擬業(yè)務到來，記錄虛擬鏈路數(shù)L，令l表示第l條虛擬鏈路，l初始值為1，并按照每個虛擬節(jié)點所請求的計算資源 $C_i^{\rm{r}}$ 將節(jié)點降序排
序VR={vr1,vr2,···,vrn},vri表示第i個虛擬節(jié)點，i初始值為1；步驟2 根據(jù)式(10)計算物理節(jié)點的資源可用性排序，并將物理節(jié)點按照降序排序，記為集合VS={vs1,vs2,···,vsn},vsi表示第i個物理節(jié)
點，i初始值為1；步驟3 判斷物理節(jié)點vsi可用計算資源是否大于等于虛擬節(jié)點vri請求的計算資源，如大于等于則將vri映射在vsi上，轉(zhuǎn)至步驟4；否則標記
業(yè)務阻塞；步驟4 將vri從集合VR刪除，判斷VR是否為空，若是，則轉(zhuǎn)至步驟5，否則將i+1，轉(zhuǎn)至步驟3； 步驟5 對第l虛擬鏈路(其中，l $\in$ [1, L])，根據(jù)虛擬節(jié)點映射的情況，根據(jù)Dijkstra算法計算找到對應映射的物理節(jié)點對之間的K條最短路
徑，令k表示第k條傳輸路徑，k初始值取1，轉(zhuǎn)步驟6；步驟6 若k>K，標記業(yè)務阻塞轉(zhuǎn)至步驟1；否則轉(zhuǎn)至步驟7； 步驟7 檢查第k條(k $\in$ [1, K])光路上各鏈路頻譜資源使用情況，根據(jù)業(yè)務所需頻隙數(shù)選出大小等于業(yè)務所需頻隙數(shù)的空閑頻譜塊作為可用
頻譜塊，加入可用頻譜塊集合${{ASB}}_k^{} = \left\{ {{\rm{as}}{{\rm}_{\rm{1}}},{\rm{ as}}{{\rm}_{\rm{2}}},·\!··,{\rm{ as}}{{\rm}_n}} \right\}$ ，表示第k條路徑上的可用頻譜資源集合，asbm(m
$\in$ [1, n])表示集合中
m第個可用頻譜塊，調(diào)用式(14)計算連續(xù)被占用的頻譜塊的剩余時間方差，選擇剩余時間方差小的頻譜塊asbm分配業(yè)務，若${{ASB}}_k^{}$ 
為空，轉(zhuǎn)步驟8；步驟8 檢查第k條 (其中，k $\in$ [1, K])光路上各鏈路的頻譜資源使用情況，再根據(jù)業(yè)務所需的頻隙數(shù)，選出大小大于業(yè)務所需頻隙數(shù)的空閑
頻譜塊，作為可用頻譜塊，加入到可用頻譜塊集合中，記作${{BSB}}_k^{}{\rm{ = }}\left\{ {{\rm{bs}}{{\rm}_{\rm{1}}},{\rm{ bs}} {{\rm}_{\rm{2}}},·\!·\!·,{\rm{ bs}}{{\rm}_n}} \right\}$ ，表示第k條路徑上的可用頻譜資源集合，
bsbm(m$\in$ [1, n])表示集合中第m個可用頻譜塊，并調(diào)用式(17)計算路徑上的頻譜碎片差值，選擇聚頻譜碎片差值小的頻譜塊bsbm分
配該虛擬鏈路，若集合ASBk和BSBk都為空，將k加1，轉(zhuǎn)至步驟6；否則轉(zhuǎn)至步驟9；步驟9 判斷l是否等于L，若等于則標記業(yè)務成功傳輸，轉(zhuǎn)至步驟1；否則將l加1，轉(zhuǎn)至步驟5。
下載: 導出CSV
表 3 LB-VNM算法
步驟1 虛擬業(yè)務到來，記錄虛擬鏈路數(shù)L，令l表示第l條虛擬鏈路，l初始值為1，并按照每個虛擬節(jié)點所請求的計算資源將節(jié)點降序排序
VR={vr1,vr2,···,vrn},vri表示第i個虛擬節(jié)點，i初始值為1；步驟2 調(diào)用式(18)計算每個物理節(jié)點的資源可用性AvRank，并將物理節(jié)點按照降序排序，記為集合Vs={vs1,vs2,···,vsn},vsi表示第i個虛
擬節(jié)點，i初始值為1；步驟3 判斷物理節(jié)點vsi可用計算資源是否大于等于虛擬節(jié)點vri請求的計算資源，如大于等于則將vri映射在vsi上，轉(zhuǎn)至步驟4；否則標記
業(yè)務阻塞；步驟4 將vri從VR刪除，判斷集合VR是否為空，若是，則轉(zhuǎn)至步驟5，否則將i+1，轉(zhuǎn)至步驟3； 步驟5 對第l虛擬鏈路，l $ \in $ [1, L]，根據(jù)虛擬節(jié)點映射的情況，根據(jù)Dijkstra算法計算找到對應映射的物理節(jié)點對之間的K條最短路徑，調(diào)
用式(19)分別計算K條路徑的平均聚合程度${\rm{avc}}(p)$ ，按照路徑的平均聚合程度avc(p)對k條候選路徑進行降序排序，令k表示第k條傳
輸路徑，k初始值取1，轉(zhuǎn)至步驟6；步驟6 若k>K，標記業(yè)務阻塞轉(zhuǎn)至步驟1；否則轉(zhuǎn)至步驟7； 步驟7 檢查第k條 (其中，k $\in$ [1, K])光路上各鏈路的頻譜資源使用情況，再根據(jù)業(yè)務所需的頻隙數(shù)，選出等于業(yè)務所需頻隙數(shù)的空閑頻譜
塊，作為可用頻譜塊，加入到可用頻譜塊集合中，記作${{CSB}}_k^{} = \left\{ {{\rm{cs}}{{\rm}_{\rm{1}}},{\rm{ cs}}{{\rm}_{\rm{2}}},·\!··,{\rm{ cs}}{{\rm}_n}} \right\}$ ，表示第k條路徑上的可用頻譜資源集合，csbm
(m$\in$ [1, n])表示集合中第m個可用頻譜塊，并調(diào)用式(14)計算連續(xù)被占用的頻譜塊的剩余時間方差，選擇剩余時間方差小的頻譜塊
csbm分配業(yè)務，若集合CSB為空，轉(zhuǎn)至步驟8；步驟8 檢查第k條 (其中，k $\in$ [1, K])光路上各鏈路的頻譜資源使用情況，再根據(jù)業(yè)務所需的頻隙數(shù)，選出大于業(yè)務所需頻隙數(shù)的空閑頻譜
塊，作為可用頻譜塊，加入到可用頻譜塊集合中，記作${{DSB}}_k^{} \!=\! \left\{ {{\rm{ds}}{{\rm}_{\rm{1}}},{\rm{ ds}}{{\rm}_{\rm{2}}},·\!··,{\rm{ ds}}{{\rm}_n}} \right\}$ ，表示第k條路徑上的可用頻譜資源集合，dsbm
(m$\in$ [1, n])表示集合中第m個可用頻譜塊，若集合CSB和DSB為空，將k加1，轉(zhuǎn)至步驟6，否則轉(zhuǎn)至步驟9；
步驟9 記錄所選擇的傳輸路徑k，并按頻譜索引值從小到大的順序，選擇第1個可用的頻譜塊dfsm進行頻譜分配，轉(zhuǎn)至步驟10； 步驟10 判斷l是否等于L，若等于則標記業(yè)務成功傳輸，轉(zhuǎn)至步驟1；否則將l加1，轉(zhuǎn)至步驟5。
下載: 導出CSV
-
劉煥淋, 歲蒙, 徐一帆, 等. 基于距離自適應和有效共享路徑感知的光疏導方法[J]. 電子與信息學報, 2015, 37(8): 1955–1970 doi: 10.11999/JEIT141442LIU Huanlin, SUI Meng, XU Yifang, et al. Method of optical grooming for distance-adaptive and effective sharing path-aware[J]. Journal of Electronics&Information Technology, 2015, 37(8): 1955–1970 doi: 10.11999/JEIT141442 劉煥淋, 李瑞艷, 孔德謙, 等. 基于多目標遺傳算法優(yōu)化彈性光網(wǎng)絡的多路徑保護機制[J]. 電子與信息學報, 2016, 38(9): 2261–2267 doi: 10.11999/JEIT151384LIU Huanlin, LI Ruiyan, KONG Deqian, et al. Optimization survivable multipath provisioning based on NSGA-II algorithm for elastic optical networks[J]. Journal of Electronics&Information Technology, 2016, 38(9): 2261–2267 doi: 10.11999/JEIT151384 PAOLUCCI F, CUGINI F, FRESI F, et al. Super filter technique in SDN-controlled elastic optical networks[Invited][J].Journal of Optical Communications and Networking, 2015, 7(2): A285–A292 doi: 10.1364/JOCN.7.00A285 WANG Yan, JIN Yaohui, GUO Wei, et al. Virtualized optical network services across multiple domains for grid applications[J]. IEEE Communications Magazine, 2011, 49(5): 92–101 doi: 10.1109/MCOM.2011.5762804 YE Zelong, ZHU Yuqing, JI P N, et al. Virtual infrastructure mapping in software-defined elastic optical networks[J]. Photonic Network Communications, 2016, 34(1): 1–11 doi: 10.1007/s11107-016-0678-4 DUBOIS D J and CALSE G. Autonomic provisioning and application mapping on spot cloud resource[C]. International Conference on Cloud and Autonomic Computing, Boston, USA, 2015: 57–68. CHEN Bowen, ZHANG Jie, XIE Weisheng, et al. Cost-effective survivable virtual optical network mapping in flexible bandwidth optical networks[J]. Journal of Lightwave Technology, 2016, 34(10): 2398–2412 doi: 10.1109/JLT.2016.2530846 GAO Xiujiao, YE Zelong, ZHONG Weida, et al. Multicast service-oriented virtual network mapping over elastic optical networks[C]. IEEE International Conference on Communications, London, UK, 2015: 5174–5179 WANG Hongxiang, ZHAO Jingxi, LI Hui, et al. Opaque virtual optical network mapping algorithms based on available spectrum adjacency for elastic optical networks[J]. Science China Information Sciences, 2016, 59(4): 1–11 doi: 10.1107/s11432-016-5525-9 GONG Long and ZHU Zuqing. Virtual Optical Network Embedding (VONE) over elastic optical networks[J]. Journal of Lightwave Technology, 2014, 32(3): 450–460 doi: 10.1109/JLT.2013.2294389 WANGH Hongxiong, XIN Xin, ZHANG Jiawei, et al. Dynamic virtual optical network mapping based on switching capability and spectrum fragmentation in elastic optical networks[C]. Optoelectronics and Communications Conference, Niigata, Japan, 2016: 3–7. -
圖(6) / 表(3)
計量
- 文章訪問數(shù): 2247
- HTML全文瀏覽量: 487
- PDF下載量: 49
- 被引次數(shù): 0
下載:
