基于网络优化的云数据传输的最大收益问题

张源境 东北大学 王浩栋 宋晓可 山东科技大学 李艺帆 西安电子科技大学

基于网络优化的云数据传输的最大收益问题

张源境 东北大学 王浩栋 宋晓可 山东科技大学 李艺帆 西安电子科技大学

云数据传输问题是研究文件的传输顺序，使传输总时间最短的问题，属于“时间表问题”的一种。而时间表问题属于离散最优化领域。我们构造顶点矩阵a，得到饱和顶点并传输其最大边，对最大权匹配思想进行变异，得出所有顶点的最短传输时间，其中的最大值即为问题的最优解。部分节点的传输能力变为大于1的值，所以可将这部分节点的最大值与次大值同时传输，以保证结果最优。由于虚拟机内存容量以及虚拟机迁移的影响，使问题变得复杂，不能简单地通过求饱和点的方法来求解。

网络优化问题 饱和点 最大边

1 问题描述

已知所有机器之间的联系情况，有联系的计算机之间传输文件的时间，可以将实际问题抽象为一个对称矩阵a，行数和列数表示对应的节点Vy的值，对应元素a（i，j）即为文件从计算机i到计算机j（计算机j到计算机i）之间的传输时间。将同时与三台其他计算机相联系的计算机抽象为饱和点，连接两个饱和点的边抽象为饱和边。易知，只要求解出所有点传输完成所有边的总时间，再比较出各个点传输完边所用的时间，就可以确定完成所有过程所需的总时间。只要对这一求解过程进行优化，避免不必要的等待和错误的传输顺序，就可以得到最短的传输时间。由于饱和点和饱和边处的复杂程度在图形中占主要位置，并且饱和点所连的边数大于非饱和点所连的边数，且可以保证在大多数情况下饱和点的相连的三条边的总传输时间大于非饱和点的总传输时间，故只需考虑饱和点的传输总时间即可。将部分饱和点的传输能力改变为2或者3，并且一部分数据变为未知。先将所有顶点的传输能力均视为1，即为第一步中得到的解法。之后筛选出实际传输能力不为1的顶点，对这部分顶点的传输时间进一步压缩优化，即可得到传输问题的最短时间。对于未知量N的问题，可以从“已知到未知求解”的角度出发，先用已知值替换，之后改变该替换值，从中发现替换规律，得到最优解以及N值的影响。

2 问题求解

Step1：求解饱和顶点；Step2：对饱和顶点的相关边比较，寻找饱和顶点之间相连的最大边；Step3：最大边传输完成；继续进行比较算法，求出饱和顶点的实际次大边和最小边；Step4：循环计算，依次得到所有饱和顶点的传输时间；饱和顶点传输完成，循环结束。

当顶点的传输能力变化时，真正对传输时间产生影响的只有饱和顶点。可以先将所有顶点传输能力全部看做1，通过上述方法求解出三条边传输过程中的实际传输时间。此时需要注意，对于传输能力为2的点，其次大边的传输可以与最大边同时进行以得到传输最短时间；对于传输能力为3的点，可以使3条边的传输同时进行以保证传输时间。

Step1：求解饱和顶点；Step2：对饱和顶点的相关边比较，寻找饱和顶点最大边；Step3：求解传输能力为2的点，让这类点在可能的情况下传输剩下的边；Step4：求解传输能力为3的点，让这类点在可能的情况下传输与之相邻的所有边；Step5：传输剩下的所有边；Step6：计算传输时间。于未知量N的求解，最直观的办法是对N进行赋值，在合理区间内为N赋值，通过改变N，观察结果中产生的影响。

如果该服务器为不可靠类，则交换机需时刻准备将请求转移至传输完成的出错率最低的较可靠类机器。传输消耗的时间由所给无向图决定。当传输尚未完成而又有新的可靠度高于原转移目标的服务器空闲，且道路中的服务器尚未被占用时，交换机根据期望值的大小决定转移是否至新的可靠服务器。显然，即便在高故障率的服务器上，当任务快要完成时在选择迁移是不划算的。

[1]图论（第四版）---[德]Reinhard Diestel著，北京，高等教育出版社

[2]基于云计算的网络操作系统中虚拟机动态迁移的研究与实现---邹超，陆月明

第一作者：张源境（1997—），女，汉族，辽宁省沈阳市，本科生，东北大学，研究方向为云计算与大数据。第二作者：王浩栋（1997—），男，汉族，山东省威海市。大学本科在校生，山东科技大学矿业与安全工程学院采矿工程16级，研究方向为采矿工程。第三作者：宋晓可（1996—），女，汉族，山东省聊城市。本科，山东科技大学数学与系统科学学院统计学2014级，研究方向为统计学。李艺帆（1996—），性别：女，民族：汉，籍贯：陕西西安。职务/职称：无，学历：大学本科，单位：西安电子科技大学，研究方向：云计算。