网络拓扑图划分算法研究

发布时间：2019-04-01 14:18

【摘要】：许多基于互联网的研究,以及对认知网络的研究,均涉及用高速群集计算机系统并行模拟或处理大规模网络的问题。而网络拓扑图划分是处理相应计算任务分配的一种有效的技术手段。基于图划分的应用不断深入与扩展的形势,为保证划分质量的需要,对网络拓扑图划分算法进行了深入研究。本文研究工作主要包括四个方面:网络拓扑图划分的求解模式、网络模拟图的划分算法、CDN缓存服务器放置问题的图划分算法和网络拓扑图划分质量的评价方法。具体研究内容如下:第一,为了规范网络拓扑图划分问题的求解过程,从内在机制上做到保证划分质量,探索并构建一种具有循环优化调节环节的网络拓扑图划分的求解模式。该模式包含三部分内容:一是图的预处理,即权重估算,约束条件和优化目标的确定;二是图的划分,包括粗化压缩、初始划分和细化还原三个阶段;三是划分质量评价和运行参数循环优化调节。同时,为了满足图划分应用领域不断扩展的需要,在网络拓扑图划分一般定义的基础上,给出了最大化边切割的概念和网络拓扑图划分的四个扩展定义,打破了传统的图划分只为求最小化边切割,不能最大化边切割的束缚。第二,根据网络拓扑图划分求解模式,提出一种具有循环优化调节环节的网络模拟图多层k路划分算法,达到了保证划分质量的目的。在传统算法的基础上,增加预处理环节,进行权重估算,根据任务要求和实际掌握的数据情况,确定优化目标和约束条件。阐述了粗化阶段的有选择的轻点匹配算法,解决了轻点匹配算法原设计中有的较重节点被压缩的问题;阐述了初始划分阶段的有选择的图增长划分算法和有选择的贪心图增长划分算法,解决了原算法因初始点不同而影响边切割大小的敏感性问题。设计了运行参数循环优化调节的具体过程,给出循环变量的具体选择与调节方法。采用有选择的轻点匹配算法并对照轻点匹配算法和有选择的重边匹配算法进行网络模拟图划分对比实验,实验数据表明,有选择的轻点匹配算法在边切割和均衡度两方面都比对照算法更好,证明有选择的轻点匹配算法比对照算法更适于网络模拟图的划分。第三,为了解决CDN缓存服务器放置问题,提出一种用最大化边切割算法对CDN图进行划分的新方法。给出CDN图划分应满足的条件和CDN图划分的定义,确定CDN图划分的权重抽象规则。实现用单次边压缩算法和有选择的轻点压缩算法进行CDN图划分粗化压缩,用单次轻边压缩k路划分法进行初始划分,并改造KL/FM算法实现了CDN图划分的细化还原。CDN图划分实验数据证实有选择的轻点压缩算法和单次轻边压缩算法是解决CDN图划分问题的有效方法。第四,为了比较不同划分算法的划分性能和验证图划分的效果,提出一种网络拓扑图划分质量综合评价指标法。定义了多项网络拓扑图划分的基本评价参数,构建了网络拓扑图划分质量评价的基本方法,包括割衡积Q、网络模拟图划分质量相对评价指数J和无量纲评价指数C的概念。设计了网络模拟图划分质量的综合评价指标法和完成任务花费时间指标法。分别给出用J值法和C值法对网络模拟图划分质量进行综合评价的示例,实验数据分析表明,评价结果反映了用不同评价指标联合评价划分质量的综合效果,说明综合评价法具有理论意义和实际应用价值。制定了 CDN图划分质量的评价指标,包括割衡商R和CDN图划分相对评价指数L等概念。给出CDN图划分质量的L值法评价示例,对有选择的轻点压缩算法、单次轻边压缩算法和轻边匹配算法的实验数据进行对比分析,证明有选择的轻点压缩算法和单次轻边压缩算法具有优势,效果较好。
[Abstract]:Many Internet-based studies, as well as research on cognitive networks, involve the use of high-speed cluster computer systems to simulate or process large-scale networks in parallel. The division of network topology is an effective way to deal with the task assignment. Based on the application of graph division and the situation of extension, the network topology graph partitioning algorithm is deeply studied in order to guarantee the need of the division quality. The research work in this paper mainly includes four aspects: the solution mode of the network topology graph division, the partitioning algorithm of the network simulation graph, the graph partitioning algorithm of the CDN cache server placement problem and the evaluation method of the network topology graph division quality. The specific research contents are as follows: First, in order to standardize the solution process of the network topology graph division problem, the partition quality is guaranteed from the internal mechanism, and the solution mode of the network topology graph partition with the loop optimization adjustment link is explored and constructed. The model includes three parts: one is the pretreatment of the graph, namely the weight estimation, the constraint condition and the determination of the optimization target; the second is the division of the graph, including three stages of coarsening, compression, initial division and refinement; thirdly, the quality evaluation and the operation parameter circulation optimization adjustment are divided. At the same time, in order to meet the need of the continuous extension of the application field of the graph, on the basis of the general definition of the network topology graph, the concept of maximum edge cutting and the four extension definitions of the network topology diagram are given, and the traditional graph division is broken only to minimize edge cutting, It is not possible to maximize the binding of the edge cut. Secondly, according to the network topology graph partition solution mode, a network simulation graph multi-layer k-way partitioning algorithm with a loop optimization adjusting link is proposed, and the purpose of ensuring the division quality is achieved. On the basis of the traditional algorithm, the preprocessing link is added, the weight estimation is carried out, and the optimization objective and the constraint condition are determined according to the task requirements and the actual data conditions. This paper describes the selection of the light-point matching algorithm in the coarsening stage, and solves the problem that the heavy-node is compressed in the original design of the light-point matching algorithm. The sensitivity of the original algorithm to the size of the edge cutting due to different initial points is solved. In this paper, the specific process of the optimization and adjustment of the running parameters is designed, and the specific selection and adjustment method of the cycle variable are given. By using the selected light-point matching algorithm and the comparison experiment of the network simulation graph with the light-point matching algorithm and the selected heavy-edge matching algorithm, the experimental data show that the selected light-point matching algorithm is better than the control algorithm in terms of the edge cutting and the balance degree, It is proved that the selected light-point matching algorithm is more suitable for the division of the network simulation graph than the control algorithm. Third, in order to solve the problem of CDN cache server placement, a new method for dividing the CDN image with the maximum edge cutting algorithm is proposed. The conditions and the definition of the CDN graph division are given, and the weight abstract rules of the CDN graph division are determined. In this paper, a single-edge compression algorithm and a selected light-point compression algorithm are used to divide the CDN image into coarsened compression, and the initial division is carried out by a single-edge compression k-way division method and the KL/ FM algorithm is modified to realize the refinement and reduction of the CDN graph division. The experimental data of the CDN graph prove that the selected light-point compression algorithm and the single-edge compression algorithm are an effective way to solve the problem of the CDN graph division. Fourth, in order to compare the division performance of the different partitioning algorithm and the effect of the verification graph, a comprehensive evaluation index method of network topology is proposed. The basic evaluation parameters of network topology graph division are defined, and the basic method of network topology graph division quality evaluation is constructed, including the concept of the division of the balance product Q, the division quality of the network simulation graph and the dimensionless evaluation index C. The comprehensive evaluation index method of network simulation graph division quality and the time index method to complete the task are designed. The paper gives an example of the comprehensive evaluation of the division quality of the network simulation graph by the J value method and the C value method, and the experimental data analysis shows that the evaluation result reflects the comprehensive effect of the joint evaluation of the division quality with different evaluation indexes, and the comprehensive evaluation method has both theoretical and practical application values. The evaluation index of the division quality of the CDN (CDN) graph is developed, including the concept of the relative evaluation index (L), such as the scale quotient (R) and the CDN (CDN) graph. In this paper, an example of an L value method for the quality of the CDN graph division is given, and the experimental data of the selected light point compression algorithm, the single light edge compression algorithm and the light edge matching algorithm are compared and analyzed to prove that the selected light point compression algorithm and the single-edge compression algorithm have the advantages of good effect and good effect.
【学位授予单位】：哈尔滨工程大学
【学位级别】：博士
【学位授予年份】：2014
【分类号】：TP393.02

【相似文献】