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

Link Mapping Algorithm Based on Weighted Graph

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

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