计算机科学 ›› 2021, Vol. 48 ›› Issue (11A): 476-480.doi: 10.11896/jsjkx.201200216

• 网络& 通信 • 上一篇    下一篇

基于加权图的链路映射算法

高明, 周慧颖, 焦海, 应丽莉   

  1. 浙江工商大学信息与电子工程学院 杭州310018
  • 出版日期:2021-11-10 发布日期:2021-11-12
  • 通讯作者: 周慧颖(1435561370@qq.com)
  • 作者简介:gaoming@zjgsu.edu.cn
  • 基金资助:
    浙江省基础公益研究计划(LGG20F010005);国家重点研发计划基金(2017YFB0803202);国家自然科学基金(61871468);浙江省重点研发计划基金(2019C01056)

Link Mapping Algorithm Based on Weighted Graph

GAO Ming, ZHOU Hui-ying, JIAO Hai, YING Li-li   

  1. School of Information and Electronic Engineering,Zhejiang Gongshang University,Hangzhou 310018,China
  • Online:2021-11-10 Published:2021-11-12
  • About author:GAO Ming,born in 1979,associate professor.His main research interests include new network architecture and industrial Internet.
    ZHOU Hui-ying,born in 1997,postgraduate.Her main research interests include new network architecture and industrial Internet.
  • Supported by:
    Research Plan of Basic Welfare of Zhejiang Province,China(LGG20F010005),National Research Plan Foundation of China(2017YFB0803202),National Natural Science Foundation of China(61871468) and Research Plan Foundation of Zhejiang Province,China(2019C01056).

摘要: 服务功能链(Service Function Chain,SFC)作为一种服务部署概念,为网络提供了更高的灵活性。文中研究服务功能部署中的映射问题,针对服务功能链的业务编排平面部署提出一种基于加权图的链路映射算法,来平衡功能服务节点部署到物理节点上的负载要求。给出了一种服务功能虚拟链路的映射算法,即先进行服务功能组合,随后针对实际的链路情况进行建模分析,利用效率矩阵求解初值,最后利用启发式算法对前者进行纠正。通过建模分析,并与降低链路带宽需求的图匹配策略的特征向量分解算法进行对比,该算法可以在链路节点负载和链路带宽均衡的情况下完成服务请求,并且在服务链长度不断增长和流量数增加的过程中,算法对于吞吐量的变化更加稳定,可以降低对于现有物理网络进行映射的代价。

关键词: 网络功能虚拟化, 软件定义网络, 服务功能链, 服务部署, 映射

Abstract: Service function chain (SFC),as a concept of service deployment,provides a higher flexibility for network.This paper studies the mapping problem in the service function deployment,and proposes a link mapping algorithm based on weighted graph for the service function chain's business choreography plane deployment,so as to balance the load requirements of the functional service nodes deployed to the physical nodes.And this paper presents a mapping algorithm for virtual link of service function,that is,the combination of service function is first carried out,and then the actual link situation is modeled and analyzed,the initial va-lue is obtained by using efficiency matrix,and finally the former is corrected by using heuristic algorithm.Through the modeling analysis and comparison with Eigen decomposition of adjacency matrices (Eigen) of map matching strategy which reduces the link bandwidth demand,the algorithm can complete the service request under the condition of balanced link node load and link bandwidth,and in the growing service chain length and flow,the algorithm is more stable to changes in throughput and can reduce the cost of mapping for existing physical network.

Key words: Network function virtual, Software define network, Service function chain, Service deploy, Mapping

中图分类号: 

  • TP393
[1]HUANG M G,WANG T,LIU L,et al.Virtual network function deployment strategy based on software defined network resource optimization[J].Computer Science,2020,47(S1):404-408.
[2]DING W,QI W,WANG J,et al.OpenSCaaS:an open service chain as a service platform toward the integration of SDN and NFV[J].Network IEEE,2015,29(3):30-35.
[3]JIANG J C,ZHU K J,ZHANG Y F,et al.Joint Decision Algorithm for DASH Video Transmission Routing and Bitrate Adjustment in Software-Defined Networking[J].Journal of Chinese Computer Systems,2017.
[4]LIU Y C,LUY,WANG S,et al.An Optimal Deployment Mechanism of Service Function Chain Based on Software Defined Network[J].Computer application research,2019,36(10):3089-3093.
[5]BREMLER-BARR A,HARCHOL Y,HAY D.OpenBox:ASoftware-Defined Framework for Developing,Deploying,and Managing Network Functions[C]//Conference on AcmSigcomm Conference.ACM,2016.
[6]LI X,QIAN C.The virtual network function placement problem[C]//Computer Communications Workshops.IEEE,2015:69-70.
[7]MCGEER R,ANDERSEN D G,SCHWAB S.The NetworkTestbed Mapping Problem[C]//Testbeds & Research Infrastructures Development of Networks & Communities-international Icst Conference.Springer Berlin Heidelberg,2010.
[8]WEN T,YU H,SUN G,et al.Network function consolidation in service function chaining orchestration[C]//IEEE International Conference on Communications.IEEE,2016.
[9]LI X,QIA N C.The virtual network function placement problem[C]//Computer Communications Workshops.IEEE,2015:69-70.
[10]LIU L,YU H F.Service chain mapping algorithm of virtual network function based on resource splitting[J].Computer application research,2016,33(8):2440-2445.
[11]LI D,LAN J L,WANG P,et al.Service function chain deployment method based on optimal weighted graph matching[J].Journal of Communication,2019,40(3):10-18.
[12]UMEYAMA S.An eigendecomposition approach to weightedgraphmatching problems[J].IEEE Transactions on Pattern Analysis & Machine Intelligence,1988,10(5):695-703.
[13]ZHAI D,MENG X R,KANG Q Y.Delay and Reliability Optimization Oriented Service Function Chain Deployment Method[J].Journal of Electronics and Information,2020,42(10):2386-2393.
[14]GHRIBI C,ZEGHLACHE D.A scalable algorithm for theplacement of service function chains[J].IEEE Transactions on Network and Service Management,2016,13(3):533-546.
[15]MALIS A,BRYANT S,HALPERN J,et al.MPLS TransportEncapsulation for the Service Function Chaining (SFC) Network Service Header (NSH)[OL].https://www.rfc-editor.org/info/rfc8596.
[16]RAO L L,ZHANG D Z.Solving the 3-SAT problem based on genetic and simulated annealing algorithms[J].Modern Compu-ter(Professional),2012(10):14-16,36.
[1] 杨萍, 舒辉, 康绯, 卜文娟, 黄宇垚. 一种基于语义分析的恶意代码攻击图生成方法[J]. 计算机科学, 2021, 48(6A): 448-458.
[2] 董仕. 软件定义网络安全问题研究综述[J]. 计算机科学, 2021, 48(3): 295-306.
[3] 刘奇, 陈红梅, 罗川. 基于改进的蝗虫优化算法的红细胞供应预测方法[J]. 计算机科学, 2021, 48(2): 224-230.
[4] 叶松涛, 周扬正, 范红杰, 陈正雷. 融合因果关系和时空图卷积网络的人体动作识别[J]. 计算机科学, 2021, 48(11A): 130-135.
[5] 高雅卓, 刘亚群, 张国敏, 邢长友, 王秀磊. 基于多阶段博弈的虚拟化蜜罐动态部署机制[J]. 计算机科学, 2021, 48(10): 294-300.
[6] 余雪勇, 陈涛. 边缘计算场景中基于虚拟映射的隐私保护卸载算法[J]. 计算机科学, 2021, 48(1): 65-71.
[7] 苏畅, 张定权, 谢显中, 谭娅. 面向5G通信网络的NFV内存资源管理方法[J]. 计算机科学, 2020, 47(9): 246-251.
[8] 朱国晖, 张茵, 刘秀霞, 孙天骜. 节点拓扑感知的高效节能虚拟网络映射算法[J]. 计算机科学, 2020, 47(9): 270-274.
[9] 高方远, 王秀美. 一种基于块对角表示和近邻约束的子空间聚类方法[J]. 计算机科学, 2020, 47(7): 66-70.
[10] 贾吾财, 吕光宏, 王桂芝, 宋元隆. SDN多控制器放置问题研究综述[J]. 计算机科学, 2020, 47(7): 206-212.
[11] 史朝卫, 孟相如, 马志强, 韩晓阳. 拓扑综合评估与权值自适应的虚拟网络映射算法[J]. 计算机科学, 2020, 47(7): 236-242.
[12] 黄梅根, 汪涛, 刘亮, 庞瑞琴, 杜欢. 基于软件定义网络资源优化的虚拟网络功能部署策略[J]. 计算机科学, 2020, 47(6A): 404-408.
[13] 张举, 王浩, 罗舒婷, 耿海军, 尹霞. 基于遗传算法的混合软件定义网络路由节能算法[J]. 计算机科学, 2020, 47(6): 236-241.
[14] 张浩, 蔡英, 夏红科. VANET中基于RSU辅助签名环形成的方案[J]. 计算机科学, 2020, 47(5): 301-305.
[15] 谢英英, 石涧, 黄硕康, 雷凯. 面向5G的命名数据网络物联网研究综述[J]. 计算机科学, 2020, 47(4): 217-225.
Viewed
Full text


Abstract

Cited

  Shared   
  Discussed   
[1] 姜新文. 哈密顿图判定问题的多项式时间算法[J]. 计算机科学, 2020, 47(7): 8 -20 .
[2] 冯芙蓉, 张兆功. 目标轮廓检测技术新进展[J]. 计算机科学, 2021, 48(6A): 1 -9 .
[3] 孙正, 张小雪. 生物光声成像中声反射伪影抑制方法的研究进展[J]. 计算机科学, 2021, 48(6A): 10 -14 .
[4] 周欣, 刘硕迪, 潘薇, 陈媛媛. 自然交通场景中的车辆颜色识别[J]. 计算机科学, 2021, 48(6A): 15 -20 .
[5] 黄雪冰, 魏佳艺, 沈文宇, 凌力. 基于自适应加权重复值滤波和同态滤波的MR图像增强[J]. 计算机科学, 2021, 48(6A): 21 -27 .
[6] 江妍, 马瑜, 梁远哲, 王原, 李光昊, 马鼎. 基于分数阶麻雀搜索优化OTSU肺组织分割算法[J]. 计算机科学, 2021, 48(6A): 28 -32 .
[7] 冯霞, 胡志毅, 刘才华. 跨模态检索研究进展综述[J]. 计算机科学, 2021, 48(8): 13 -23 .
[8] 周文辉, 石敏, 朱登明, 周军. 基于残差注意力网络的地震数据超分辨率方法[J]. 计算机科学, 2021, 48(8): 24 -31 .
[9] 朝乐门, 尹显龙. 人工智能治理理论及系统的现状与趋势[J]. 计算机科学, 2021, 48(9): 1 -8 .
[10] 雷羽潇, 段玉聪. 面向跨模态隐私保护的AI治理法律技术化框架[J]. 计算机科学, 2021, 48(9): 9 -20 .