Computer Science

Computer Science ›› 2021, Vol. 48 ›› Issue (11A): 476-480.doi: 10.11896/jsjkx.201200216

• Network & Communication • Previous Articles     Next Articles

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).

PDF (PC)

454

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

CLC Number: 

  • 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] WANG Kun-shu, ZHANG Ze-hui, GAO Tie-gang. Reversible Hidden Algorithm for Remote Sensing Images Based on Hachimoji DNA and QR Decomposition [J]. Computer Science, 2022, 49(8): 127-135.
[2] ZENG Jin, LU Yong-gang, YUE Yang. Finer-grained Mapping for Urban Scenes Based on POI [J]. Computer Science, 2022, 49(4): 9-15.
[3] ZHU Min, LIANG Zhao-hui, YAO Lin, WANG Xiang-kun, CAO Meng-qi. Survey of Visualization Methods on Academic Citation Information [J]. Computer Science, 2022, 49(4): 88-99.
[4] ZHANG Sai-nan, LI Qian-mu. Color Image Encryption Algorithm Based on Logistic-Sine-Cosine Mapping [J]. Computer Science, 2022, 49(1): 353-358.
[5] TIAN Ye, CHEN Hong-wei, WANG Fa-sheng, CHEN Xing-wen. Overview of SLAM Algorithms for Mobile Robots [J]. Computer Science, 2021, 48(9): 223-234.
[6] YANG Ping, SHU Hui, KANG Fei, BU Wen-juan, HUANG Yu-yao. Generating Malicious Code Attack Graph Using Semantic Analysis [J]. Computer Science, 2021, 48(6A): 448-458.
[7] LIU Qi, CHEN Hong-mei, LUO Chuan. Method for Prediction of Red Blood Cells Supply Based on Improved Grasshopper Optimization Algorithm [J]. Computer Science, 2021, 48(2): 224-230.
[8] WANG Ke, QU Hua, ZHAO Ji-hong. Multi-objective Optimization Method Based on Reinforcement Learning in Multi-domain SFC Deployment [J]. Computer Science, 2021, 48(12): 324-330.
[9] YE Song-tao, ZHOU Yang-zheng, FAN Hong-jie, CHEN Zheng-lei. Joint Learning of Causality and Spatio-Temporal Graph Convolutional Network for Skeleton- based Action Recognition [J]. Computer Science, 2021, 48(11A): 130-135.
[10] YU Xue-yong, CHEN Tao. Privacy Protection Offloading Algorithm Based on Virtual Mapping in Edge Computing Scene [J]. Computer Science, 2021, 48(1): 65-71.
[11] QI Shao-hua, XU He-gen, WAN You-wen, FU Hao. Construction of Semantic Mapping in Dynamic Environments [J]. Computer Science, 2020, 47(9): 198-203.
[12] WANG Bing-zhou, WANG Hui-bin, SHEN Jie, ZHANG Li-li. FastSLAM Algorithm Based on Adaptive Fading Unscented Kalman Filter [J]. Computer Science, 2020, 47(9): 213-218.
[13] SU Chang, ZHANG Ding-quan, XIE Xian-zhong, TAN Ya. NFV Memory Resource Management in 5G Communication Network [J]. Computer Science, 2020, 47(9): 246-251.
[14] GAO Fang-yuan, WANG Xiu-mei. Subspace Clustering Method Based on Block Diagonal Representation and Neighbor Constraint [J]. Computer Science, 2020, 47(7): 66-70.
[15] HUANG Mei-gen, WANG Tao, LIU Liang, PANG Rui-qin and DU Huan. Virtual Network Function Deployment Strategy Based on Software Defined Network Resource Optimization [J]. Computer Science, 2020, 47(6A): 404-408.
Viewed
Full text


Abstract

Cited
  Shared   
  Discussed   
No Suggested Reading articles found!
渝ICP备16013121号-4
Add:18# Honghu West Rd., Yubei ,Chongqing,China    Post Code: 401121
Tel: 023-63500828/023-67039612/023-67039623
E-mail: jsjkx12@163.com
Powered by Beijing Magtech Co., Ltd.