计算机科学 ›› 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: Mapping, Network function virtual, Service deploy, Service function chain, Software define network

中图分类号: 

  • 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] 冷佳旭, 谭明圮, 胡波, 高新波.
基于隐式视角转换的视频异常检测
Video Anomaly Detection Based on Implicit View Transformation
计算机科学, 2022, 49(2): 142-148. https://doi.org/10.11896/jsjkx.210900266
[2] 耿海军, 王威, 尹霞.
基于混合软件定义网络的单节点故障保护方法
Single Node Failure Routing Protection Algorithm Based on Hybrid Software Defined Networks
计算机科学, 2022, 49(2): 329-335. https://doi.org/10.11896/jsjkx.210100051
[3] 张赛男, 李千目.
一种基于Logistic-Sine-Cosine映射的彩色图像加密算法
Color Image Encryption Algorithm Based on Logistic-Sine-Cosine Mapping
计算机科学, 2022, 49(1): 353-358. https://doi.org/10.11896/jsjkx.201000041
[4] 杨萍, 舒辉, 康绯, 卜文娟, 黄宇垚.
一种基于语义分析的恶意代码攻击图生成方法
Generating Malicious Code Attack Graph Using Semantic Analysis
计算机科学, 2021, 48(6A): 448-458. https://doi.org/10.11896/jsjkx.201100074
[5] 董仕.
软件定义网络安全问题研究综述
Survey on Software Defined Networks Security
计算机科学, 2021, 48(3): 295-306. https://doi.org/10.11896/jsjkx.200300119
[6] 刘奇, 陈红梅, 罗川.
基于改进的蝗虫优化算法的红细胞供应预测方法
Method for Prediction of Red Blood Cells Supply Based on Improved Grasshopper Optimization Algorithm
计算机科学, 2021, 48(2): 224-230. https://doi.org/10.11896/jsjkx.200600016
[7] 王珂, 曲桦, 赵季红.
多域SFC部署中基于强化学习的多目标优化方法
Multi-objective Optimization Method Based on Reinforcement Learning in Multi-domain SFC Deployment
计算机科学, 2021, 48(12): 324-330. https://doi.org/10.11896/jsjkx.201100159
[8] 叶松涛, 周扬正, 范红杰, 陈正雷.
融合因果关系和时空图卷积网络的人体动作识别
Joint Learning of Causality and Spatio-Temporal Graph Convolutional Network for Skeleton- based Action Recognition
计算机科学, 2021, 48(11A): 130-135. https://doi.org/10.11896/jsjkx.201200205
[9] 高雅卓, 刘亚群, 张国敏, 邢长友, 王秀磊.
基于多阶段博弈的虚拟化蜜罐动态部署机制
Multi-stage Game Based Dynamic Deployment Mechanism of Virtualized Honeypots
计算机科学, 2021, 48(10): 294-300. https://doi.org/10.11896/jsjkx.210500071
[10] 余雪勇, 陈涛.
边缘计算场景中基于虚拟映射的隐私保护卸载算法
Privacy Protection Offloading Algorithm Based on Virtual Mapping in Edge Computing Scene
计算机科学, 2021, 48(1): 65-71. https://doi.org/10.11896/jsjkx.200500098
[11] 苏畅, 张定权, 谢显中, 谭娅.
面向5G通信网络的NFV内存资源管理方法
NFV Memory Resource Management in 5G Communication Network
计算机科学, 2020, 47(9): 246-251. https://doi.org/10.11896/jsjkx.190800008
[12] 朱国晖, 张茵, 刘秀霞, 孙天骜.
节点拓扑感知的高效节能虚拟网络映射算法
Energy Efficient Virtual Network Mapping Algorithms Based on Node Topology Awareness
计算机科学, 2020, 47(9): 270-274. https://doi.org/10.11896/jsjkx.190700162
[13] 高方远, 王秀美.
一种基于块对角表示和近邻约束的子空间聚类方法
Subspace Clustering Method Based on Block Diagonal Representation and Neighbor Constraint
计算机科学, 2020, 47(7): 66-70. https://doi.org/10.11896/jsjkx.190600155
[14] 贾吾财, 吕光宏, 王桂芝, 宋元隆.
SDN多控制器放置问题研究综述
Review on Placement of Multiple Controllers in SDN
计算机科学, 2020, 47(7): 206-212. https://doi.org/10.11896/jsjkx.200200075
[15] 史朝卫, 孟相如, 马志强, 韩晓阳.
拓扑综合评估与权值自适应的虚拟网络映射算法
Virtual Network Embedding Algorithm Based on Topology Comprehensive Evaluation and Weight Adaptation
计算机科学, 2020, 47(7): 236-242. https://doi.org/10.11896/jsjkx.190600022
Viewed
Full text


Abstract

Cited

  Shared   
  Discussed   
No Suggested Reading articles found!