高级搜索

留言板

尊敬的读者、作者、审稿人, 关于本刊的投稿、审稿、编辑和出版的任何问题, 您可以本页添加留言。我们将尽快给您答复。谢谢您的支持!

姓名
邮箱
手机号码
标题
留言内容
验证码

基于时频联合碎片感知的资源均衡虚拟光网络映射算法

刘焕淋 胡浩 熊翠连 陈勇 向敏 马跃

刘焕淋, 胡浩, 熊翠连, 陈勇, 向敏, 马跃. 基于时频联合碎片感知的资源均衡虚拟光网络映射算法[J]. 电子与信息学报, 2018, 40(10): 2345-2351. doi: 10.11999/JEIT171208
引用本文: 刘焕淋, 胡浩, 熊翠连, 陈勇, 向敏, 马跃. 基于时频联合碎片感知的资源均衡虚拟光网络映射算法[J]. 电子与信息学报, 2018, 40(10): 2345-2351. doi: 10.11999/JEIT171208
Huanlin LIU, Hao HU, Cuilian XIONG, Yong CHEN, Min XIANG, Yue MA. Resources Balancing Algorithm Based on the Time-frequency Fragment Awareness for Virtual Optical Network Mapping[J]. Journal of Electronics & Information Technology, 2018, 40(10): 2345-2351. doi: 10.11999/JEIT171208
Citation: Huanlin LIU, Hao HU, Cuilian XIONG, Yong CHEN, Min XIANG, Yue MA. Resources Balancing Algorithm Based on the Time-frequency Fragment Awareness for Virtual Optical Network Mapping[J]. Journal of Electronics & Information Technology, 2018, 40(10): 2345-2351. doi: 10.11999/JEIT171208

基于时频联合碎片感知的资源均衡虚拟光网络映射算法

doi: 10.11999/JEIT171208
基金项目: 国家自然科学基金(61275077),重庆市基础与前沿研究项目(2015jcyjA40024),国家电网公司科学技术项目
详细信息
    作者简介:

    刘焕淋:女,1970年生,教授,研究方向为光通信技术与未来网络

    胡浩:男,1995年生,硕士生,研究方向为灵活光网络路由

    熊翠连:女,1992年生,硕士生,研究方向为光网络虚拟化技术

    陈勇:男,1963年生,教授,研究方向为光通信技术、传感检测

    向敏:男,1974年生,博士,研究方向为智能电网,工业物联网

    马跃:男,1977年生,高级工程师,研究方向为电力通信

    通讯作者:

    刘焕淋  liuhl2@sina.com

  • 中图分类号: TN929.11

Resources Balancing Algorithm Based on the Time-frequency Fragment Awareness for Virtual Optical Network Mapping

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
  • 摘要: 为了解决虚拟光网络映射中带宽阻塞率较高以及底层资源消耗不均匀问题,论文提出一种基于时间域-频谱域碎片感知的虚拟网络映射(FA-VNM)算法。该文综合考虑频隙在时间域和频谱域上的碎片问题,设计时频联合碎片公式最小化分配过程中的频谱碎片。进一步,为了均衡网络中的资源消耗,在FA-VNM算法基础上提出基于节点度数的负载均衡感知虚拟网络映射(LB-VNM)算法,设计物理节点平均资源承载能力的公式,优先映射物理节点平均资源承载能力大的节点;为了均衡路径上资源使用,考虑路径权重值,并根据每条路径的权重值对虚拟链路进行映射,从而降低阻塞率。仿真结果表明,所提算法能有效降低阻塞率,提高资源利用率。
  • 图  1  底层网络和虚拟业务模型

    图  2  时间域碎片示意图

    图  3  频谱聚合程度示意图

    图  4  4种算法在不同网络中的带宽阻塞率

    图  5  4种算法在不同网络中的频谱利用率

    图  6  4种算法在不同网络中的业务阻塞率

    表  1  参数对照表

    参数 参数表达的含义 参数 参数表达的含义
    $\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}}}}}$ 二进制变量,如果虚拟节点 ${i^{\rm{r}}}$ 映射在物理节点 ${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}}$ 虚拟节点 i 请求的计算资源 ${W_{{e^{\rm{r}}}}}$ 整型变量,分配给虚拟链路 ${e^{\rm{r}}}$ 的连续频谱块的开始索引值
    $C_j^{\rm{s}}$ 物理节点 j 具有的计算资源 ${{{P}}^{{s}}}$ 物理拓扑图中预先计算的路径集合
    ${Z_{{e^{\rm{r}}}}}$ 整型变量,分配给虚拟链路 ${e^{\rm{r}}}$ 的连续频谱块的结束索
    引值
    ${\rho _{e_1^{\rm{r}},e_2^{\rm{r}}}}$ 二进制变量,如果分配给虚拟链路 $e_1^{\rm{r}}$ 的连续频谱块的开始索引值小于分配给虚拟链路 $e_2^{\rm{r}}$ 则为1,否则为0
    下载: 导出CSV

    表  2  FA-VNM算法

     步骤1 虚拟业务到来,记录虚拟链路数L,令l表示第l条虚拟链路,l初始值为1,并按照每个虚拟节点所请求的计算资源 $C_i^{\rm{r}}$ 将节点降序排
    序VR={vr1,vr2,···,vrn},vri表示第i个虚拟节点,i初始值为1;
     步骤2 根据式(10)计算物理节点的资源可用性排序,并将物理节点按照降序排序,记为集合VS={vs1,vs2,···,vsn},vsi表示第i个物理节
    点,i初始值为1;
     步骤3 判断物理节点vsi可用计算资源是否大于等于虚拟节点vri请求的计算资源,如大于等于则将vri映射在vsi上,转至步骤4;否则标记
    业务阻塞;
     步骤4 将vri从集合VR删除,判断VR是否为空,若是,则转至步骤5,否则将i+1,转至步骤3;
     步骤5 对第l虚拟链路(其中,l $\in$ [1, L]),根据虚拟节点映射的情况,根据Dijkstra算法计算找到对应映射的物理节点对之间的K条最短路
    径,令k表示第k条传输路径,k初始值取1,转步骤6;
     步骤6 若k>K,标记业务阻塞转至步骤1;否则转至步骤7;
     步骤7 检查第k条(k $\in$ [1, K])光路上各链路频谱资源使用情况,根据业务所需频隙数选出大小等于业务所需频隙数的空闲频谱块作为可用
    频谱块,加入可用频谱块集合 ${{ASB}}_k^{} = \left\{ {{\rm{as}}{{\rm{b}}_{\rm{1}}},{\rm{ as}}{{\rm{b}}_{\rm{2}}},·\!··,{\rm{ as}}{{\rm{b}}_n}} \right\}$ ,表示第k条路径上的可用频谱资源集合,asbm(m $\in$ [1, n])表示集合中
    m第个可用频谱块,调用式(14)计算连续被占用的频谱块的剩余时间方差,选择剩余时间方差小的频谱块asbm分配业务,若 ${{ASB}}_k^{}$
    为空,转步骤8;
     步骤8 检查第k条 (其中,k $\in$ [1, K])光路上各链路的频谱资源使用情况,再根据业务所需的频隙数,选出大小大于业务所需频隙数的空闲
    频谱块,作为可用频谱块,加入到可用频谱块集合中,记作 ${{BSB}}_k^{}{\rm{ = }}\left\{ {{\rm{bs}}{{\rm{b}}_{\rm{1}}},{\rm{ bs}} {{\rm{b}}_{\rm{2}}},·\!·\!·,{\rm{ bs}}{{\rm{b}}_n}} \right\}$ ,表示第k条路径上的可用频谱资源集合,
    bsbm(m $\in$ [1, n])表示集合中第m个可用频谱块,并调用式(17)计算路径上的频谱碎片差值,选择聚频谱碎片差值小的频谱块bsbm
    配该虚拟链路,若集合ASBk和BSBk都为空,将k加1,转至步骤6;否则转至步骤9;
     步骤9 判断l是否等于L,若等于则标记业务成功传输,转至步骤1;否则将l加1,转至步骤5。
    下载: 导出CSV

    表  3  LB-VNM算法

     步骤1 虚拟业务到来,记录虚拟链路数L,令l表示第l条虚拟链路,l初始值为1,并按照每个虚拟节点所请求的计算资源将节点降序排序
    VR={vr1,vr2,···,vrn},vri表示第i个虚拟节点,i初始值为1;
     步骤2 调用式(18)计算每个物理节点的资源可用性AvRank,并将物理节点按照降序排序,记为集合Vs={vs1,vs2,···,vsn},vsi表示第i个虚
    拟节点,i初始值为1;
     步骤3 判断物理节点vsi可用计算资源是否大于等于虚拟节点vri请求的计算资源,如大于等于则将vri映射在vsi上,转至步骤4;否则标记
    业务阻塞;
     步骤4 将vri从VR删除,判断集合VR是否为空,若是,则转至步骤5,否则将i+1,转至步骤3;
     步骤5 对第l虚拟链路,l $ \in $ [1, L],根据虚拟节点映射的情况,根据Dijkstra算法计算找到对应映射的物理节点对之间的K条最短路径,调
    用式(19)分别计算K条路径的平均聚合程度 ${\rm{avc}}(p)$ ,按照路径的平均聚合程度avc(p)对k条候选路径进行降序排序,令k表示第k条传
    输路径,k初始值取1,转至步骤6;
     步骤6 若k>K,标记业务阻塞转至步骤1;否则转至步骤7;
     步骤7 检查第k条 (其中,k $\in$ [1, K])光路上各链路的频谱资源使用情况,再根据业务所需的频隙数,选出等于业务所需频隙数的空闲频谱
    块,作为可用频谱块,加入到可用频谱块集合中,记作 ${{CSB}}_k^{} = \left\{ {{\rm{cs}}{{\rm{b}}_{\rm{1}}},{\rm{ cs}}{{\rm{b}}_{\rm{2}}},·\!··,{\rm{ cs}}{{\rm{b}}_n}} \right\}$ ,表示第k条路径上的可用频谱资源集合,csbm
    (m $\in$ [1, n])表示集合中第m个可用频谱块,并调用式(14)计算连续被占用的频谱块的剩余时间方差,选择剩余时间方差小的频谱块
    csbm分配业务,若集合CSB为空,转至步骤8;
     步骤8 检查第k条 (其中,k $\in$ [1, K])光路上各链路的频谱资源使用情况,再根据业务所需的频隙数,选出大于业务所需频隙数的空闲频谱
    块,作为可用频谱块,加入到可用频谱块集合中,记作 ${{DSB}}_k^{} \!=\! \left\{ {{\rm{ds}}{{\rm{b}}_{\rm{1}}},{\rm{ ds}}{{\rm{b}}_{\rm{2}}},·\!··,{\rm{ ds}}{{\rm{b}}_n}} \right\}$ ,表示第k条路径上的可用频谱资源集合,dsbm
    (m $\in$ [1, n])表示集合中第m个可用频谱块,若集合CSB和DSB为空,将k加1,转至步骤6,否则转至步骤9;
     步骤9 记录所选择的传输路径k,并按频谱索引值从小到大的顺序,选择第1个可用的频谱块dfsm进行频谱分配,转至步骤10;
     步骤10 判断l是否等于L,若等于则标记业务成功传输,转至步骤1;否则将l加1,转至步骤5。
    下载: 导出CSV
  • 刘焕淋, 岁蒙, 徐一帆, 等. 基于距离自适应和有效共享路径感知的光疏导方法[J]. 电子与信息学报, 2015, 37(8): 1955–1970 doi: 10.11999/JEIT141442

    LIU 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
    刘焕淋, 李瑞艳, 孔德谦, 等. 基于多目标遗传算法优化弹性光网络的多路径保护机制[J]. 电子与信息学报, 2016, 38(9): 2261–2267 doi: 10.11999/JEIT151384

    LIU 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)
计量
  • 文章访问数:  2215
  • HTML全文浏览量:  469
  • PDF下载量:  49
  • 被引次数: 0
出版历程
  • 收稿日期:  2017-12-21
  • 修回日期:  2018-06-11
  • 网络出版日期:  2018-07-30
  • 刊出日期:  2018-10-01

目录

    /

    返回文章
    返回