| 标题 | 基于网络虚拟化条件下的资源监控研究 |
| 范文 | 刘玄 摘要：近年来，随着信息化技术的快速发展，在网络虚拟化的条件下，通过对现有网络虚拟的底层资源进行了实时的监控，从而可以有效的合理的监控措施可以尽可能的减少在状态信息上的存在的时廷和带宽。为了达到这样的目的，本文设计了基于网络虚拟化条件下的资源监控的方法，如果有已知监控代理信息可用来估计某一点到目标点的距离，以减小虚拟链路的搜索范围。该优化方法能将动态资源分配算法的InP物理网络中降到一个很小的值，使其能够适用于更大的规模。该策略生成的监控代理部署方案在降低通信开销方面有着较好的表现。 关键词：计算机应用；网络虚拟化；资源监控；监控代理 中图分类号：TP 311 文献标识码：A 0 引言 近年来，随着计算机技术以及网络技术的快速的发展，人们在日常生活中越来越多的运用到网络虚拟化条件下的资源监控分析。这些网络分析都会应用到虚拟链路问题。虚拟链路对应着最短的时间，所以平均时延的核心算法都是最优（短）路径算法，这一算法不仅仅实现的是一般地理意义上的距离最短，还可引伸到其他的度量，这种算法在电子导航、交通旅游、城市规划以及电力、通讯等各种管网、管线的布局设计中发挥着重要的作用。最优或虚拟链路问题是算法分析与设计中一个最基本的问题，但是这种算法进行应用时，对于不少问题具有空间耗费大、时间效率高的特点，但当面对具体的项目工程时，它采用的算法细节是不一样的，很少有可以直接拿来使用的，一般都要对它们进行适当的改进，因此人们在研究动态资源分配算法时更多的注意空间平均时延的优化，以满足平均时延、空间复杂度或其它方面的特殊要求。 1 动态资源分配算法 1.1动态资源分配算法的原理 动态资源分配算法是一种经典的路径算法，动态资源分配算法用于计算非负权值图中一个结点到其他所有结点的虚拟链路，是一个非常经典的贪心算法例子。但随着所解决问题规模的增大，应用传统的动态资源分配算法会使时间和空间复杂度不断加大。这种算法的效率不高，不能满足于工程对于时间的需求。因此，需对传统的动态资源分配算法进行了改进，提出采用邻接表和堆排序的一种新的优化方法。动态资源分配算法基本思想过程，通常引入下列的状态常量。 1）辅助向量D，这一状态常量以通过数组来实现，其每一个分量D[i]用来存放源点到其他结点的虚拟链路长度； 2）集合V和S，其中V集合用来存放未确定虚拟链路的结点，S集合用来存放已确定虚拟链路的结点。S的初始状态为空集，V则包含带权图中的所有结点。 3）辅助变量path matrix，这一辅助变量的引入可以通过二维数组实现，用来记录源点到其他各个结点的虚拟链路所经过的顶点。 由于动态资源分配算法是按照虚拟链路长度递增的顺序逐个确定源点到各个结点的虚拟链路的，所以源点到各结点的虚拟链路或者是源点到此结点的弧，或者是中间只经过已确定了虚拟链路的顶点而最终到达此结点的路径。 1.2算法分析 通过对该算法的仔细分析与研究可以得出，上述算法中有几点不足之处： （1）用邻接矩阵Cost来存储网络图，其存储量为N#N。对于大型稀疏矩阵，这将耗费大量资源存储那些无意义的矩阵元素。 （2）当从未标记节点集合（V-S）选定下一个节点Vj作中间节点后，在更新操作过程中，需要扫描所有的未标记节点并进行比较更新。而未标记节点集合（V-S）中往往包含大量与中间节点Vj不直接相连的节点。 （3）在选择下一个虚拟链路节点作为中间节点时，需要比较所有的未标记节点，而这个中间节点往往包含在与已标记节点S集合的所有节点邻接的节点中。 （4）在算法的每次迭代中，由于未标记节点以无序的形式存放在一个链表中或一个数组中，每次选择虚拟链路节点都必须将所有未标记节点扫描一遍，当节点数目很大时，这无疑将成为制约计算速度的关键因素。 2 动态资源分配算法的优化 为了解决动态资源分配算法效率所存在的问题，通常情况下在数据的组织与存储以及虚拟链路节点的选取上进行相关的改进，从而达到提高其时间效率的目的。 2.1优化思路分析 考虑到本研究是进行动态资源分配平均时延的优化，所以优化的思路确定在对节点排序和虚拟链路节点的选取上。所以在初始时，就需要对待排序的节点以无序形式连续序存放在一个一维数组中，从而达到对节点进行堆排序，通过一定的调整过程，使其成为小堆。我们可以用邻接表来更有效的实现动态资源分配算法。同时需要将一个二叉堆或者斐波纳契堆用作优先队列来寻找最小的顶点（Extract-Min）。当用到二叉堆的时候，算法所需的时间为O（（m+n）logn），斐波纳契堆能稍微提高一些性能，让算法运行时间达到O（m+n logn）。从而达到让无序结构下的数组进行有序化的排列，从而大大减少了时间，也提高了算法的执行效率。 2.2改进的动态资源分配算法基本思想 改进的动态资源分配算法基本思想，可以通过设置两个集合S和adj及一个数组T[]，S是已标记集合，adj是邻接点集，T[]存储待排序节点。初始状态时，S={V0}，T[]=adj[V0]，首先，将数组T[]通过堆排序调整为小顶堆，取数组首元即堆顶节点current为中间节点，并将current加入到已标记集合S中；再次，比较更新current的邻接点集合与已标记集合的差集（Adj[current]-S）中任一节点Vi的当前虚拟链路值；然后查找S集合所有节点的邻接点的并集与S集合的差集（adj[S]）-S），同时将这些节点顺次存入数组T中，覆盖原数组中的节点，并设置一个计数器i记录节点个数；最后将数组中的前i个元素按它们当前的虚拟链路值调整成小顶堆，取堆顶节点为下一个虚拟链路节点将其归并到集合S中。如此反复迭代循环，直到所有的节点都加入到集合S中。下面用动态资源分配算法求图G中节点V0到其它各节点的虚拟链路D[V]，图G以邻接表为存储结构。 3 基于网络虚拟化条件下的资源监控策略 使用动态资源分配算法方法时，其主要思想是从源点求出长度最短的一条路径，然后通过对路径长度迭代得到从源点到其他目标节点的虚拟链路。对于不少问题之所以具有较高的时间效率，关键在于它减少了“冗余”。 我们知道，动态资源分配算法过程实际上就是计算所有状态值的过程，因此状态的规模直接影响到算法的时间效率。所以，减少状态总数是动态资源分配算法平均时延优化的重要部分，传统动态资源分配算法采用广度优先的搜索策略，在访问了网络中所有的节点后，最终生成从源点到其余各点的虚拟链路树。该算法在选择虚拟链路节点时需要访问所有的未标记节点，效率低下，整个算法的运行时间为O（N#N）。而改进的动态资源分配算法而改进算法的主要步骤查找待排序节点和堆排序上，因待排序节点为所有已标记节点的邻居节点的并集与标记集合的差集（adj[S1）-S），所以这个步骤的运行时间主要取决于已标记节点的邻节点集合元素数量的多少（而该数量值往往小于未标记集合中的元素个数），查找次数最多为E次。在排序过程中，每次调整的平均时延不会超过满二叉树的高度logN。这两个过程共需迭代执行N次，因此整个算法理论上最长运行时间仅为O（N（logN+E））。当网络拓扑结构图具有的节点数N较大且其关联矩阵为一个稀疏矩阵时，相对传动态资源分配算法，优化算法大大减少了计算次数与比较次数，在一定程度上提高了运算速度。 4 结论 综上所述，本文在详细分析求解虚拟链路问题的经典算法动态资源分配算法的基础上，针对动态资源分配算法存在的问题介绍了利用堆排序来选择虚拟链路节点，只处理标记节点的相邻节点，从而大量减少了要计算的节点数，最终使得算法的平均时延提高，动态资源分配算法在不同的现实应用中，可以具体情况具体分析，从而得到算法的高效率实现，实现的网络虚拟化条件下的资源监控。 |
| 随便看 |
|
科学优质学术资源、百科知识分享平台，免费提供知识科普、生活经验分享、中外学术论文、各类范文、学术文献、教学资料、学术期刊、会议、报纸、杂志、工具书等各类资源检索、在线阅读和软件app下载服务。