计算机工程 ›› 2018, Vol. 44 ›› Issue (5): 146-154.doi: 10.19678/j.issn.1000-3428.0048549

• 人工智能及识别技术 • 上一篇    下一篇

基于k最短路径算法优化与负载均衡的虚拟网络映射机制

高斐 1,陈德礼 1,洪家军 1,于智 2,田甜 3   

  1. 1.莆田学院 信息工程学院,福建 莆田 351100; 2.浙江大学 计算机科学与技术学院,杭州 310027; 3.审计署驻上海特派员办事处,上海 200051
  • 收稿日期:2017-09-05 出版日期:2018-05-15 发布日期:2018-05-15
  • 作者简介:高斐(1982—),女,讲师、硕士,主研方向为数据挖掘、人工智能;陈德礼、洪家军,副教授、硕士;于智,博士;田甜,硕士。
  • 基金项目:
    国家自然科学基金(61502417);福建省自然科学基金(2016J01759)。

Virtual Network Mapping Mechanism Based on k Shortest Path Algorithm Optimization and Load Balance

GAO Fei  1,CHEN Deli  1,HONG Jiajun  1,YU Zhi  2,TIAN Tian  3   

  1. 1.College of Information Engineering,Putian University,Putian,Fujian 351100,China; 2.College of Computer Science and Technology,Zhejiang University,Hangzhou 310027,China; 3.Shanghai Agency of National Audit Office,Shanghai 200051,China
  • Received:2017-09-05 Online:2018-05-15 Published:2018-05-15

摘要: 针对当前虚拟网络映射存在局部区域的节点和链路负载压力过大、节点和相邻链路传输时产生报文抖动和资源浪费等问题,设计一种基于全网负载均衡的虚拟网络映射算法。将节点和相邻链路资源差异性考虑到节点映射中,对k最短路径算法的邻接矩阵进行优化,将矩阵转换成反映链路负载均衡的映射矩阵。通过对节点和链路资源的动态调整,分析虚拟网络映射时出现的瓶颈问题。实验结果表明,与随机算法和贪婪算法相比,该算法具有更好的虚拟网络映射率和网络负载均衡性。

关键词: 虚拟网络映射, 负载均衡, 抖动, 网络瓶颈, k最短路径算法

Abstract: As the existing nodes and links of local areas are overweight,the phenomenon of packet jitter and resource waste generates when packets transmits between nodes and adjacent links.A virtual network embedding algorithm is designed for load balancing of the whole network in this paper.It considers the differences of nodes and adjacent links resources and put the differences into the node embedding process.The k shortest path algorithm of the adjacency matrix is optimized.The matrix is transformed into the new matrix which could reflect link load balancing.Finally,it analyzes the bottleneck problem of virtual network embedding by dynamically adjusting the resources of nodes and links.Experimental results show that the method could achieve better virtual network embedding ratio and network load balancing than randomized algorithm and greedy algorithm.

Key words: virtual network mapping, load balance, jitter, network bottleneck, k shortest path algorithm

中图分类号: