论文部分内容阅读
随着计算机技术的快速发展,计算机网络也随之大规模的飞速发展。在大规模网络中,网络的性能状况越来越被引起重视,如果对网络进行全网测量来获得网络性能状态,一方面会给网络带来额外的负担,影响本身的网络环境,另外一方面,对大规模网络进行全网测量消耗的时间会很长,使得很难快速掌握全网状况。基于稀疏表征的填充技术利用网络本身有的冗余性,使得仅仅需要通过测量部分数据,就能推断出全网数据。本文基于稀疏表征技术,从精度和速度两方面来解决通过少部分已知数据来获得全网数据的问题,主要的研究成果为:1、基于GPU的网络测量数据的并行矩阵填充方法在网络中,全面了解端到端网络性能对于网络的管理和以及网络服务都十分重要。在端到端的网络中通常需要对路径进行主动探测,主动探测会使得开销随着网络节点数量的增加而成倍增加。为了减少测量开销,最近一些研究提出了利用矩阵填充技术来获得全网数据,即仅通过测量一小部分路径来预测所有节点对之间的端到端网络性能。尽管矩阵填充技术十分有效,但用矩阵填充来恢复丢失的数据时,往往恢复精度不高而且恢复时间长。为了解决这些问题,本文提出基于GPU的并行矩阵填充方法（MC-GPU）,利用GPU来实现并行矩阵分解,以实现高速和高精度的矩阵填充,从而获得全网数据。为了充分利用GPU的特殊体系结构,使得并行执行时在任务和数据方面都没有冲突,MC-GPU方法主要包括下面几个方面:利用局部敏感哈希函数将相似的OD（原始节点-目标节点）对进行重新排序;平衡的矩阵划分方法;并行矩阵填充。本文在GPU平台上实现了MC-GPU,并使用真实的数据集来对性能进行评估,通过实验结果表明MC-GPU可以在提高的数据恢复精度的同时提高计算速度。2、基于GPU的网络测量数据的并行张量填充方法由于网络数据的本身应该是有多维属性的,而矩阵无法充分表达出网络的高维信息,从而丢失了数据中蕴含的内部结构信息。因此,张量填充能够利用多维度的数据信息,从而能够更准确的恢复出缺失的数据。然后,由于维度的增多,使得数据的计算复开销增大,这在大量数据的存在下阻止了常规张量填充算法在实际中的应用。本文主要将算法在GPU上进行执行,以实现高速和高精度的张量填充的方法。提出了基于GPU加速的并行张量填充方法（GPU-TC）,用于准确,快速地恢复丢失的数据。在方法中,为了提高数据的恢复准确性和速度,通过三个方法来将GPU与张量分解的过程结合:基于网格的张量分区;基于洗牌算法的独立任务分配;基于球形的内存调度策略。将算法在真是数据集上进行试验,并将GPU-TC与经典的张量填充算法以及矩阵填充算法进行了比较。实验结果表明,GPU-TC在错误率指标和计算时间方法都有显著的提高。3、基于相似度敏感的子张量填充方法张量填充可以用于恢复丢失的数据,这对于许多数据不完整的数据应用程序都是有用的。为了推断丢失的数据,现有的张量填充算法通常假定张量数据具有全局低秩结构,并通过全局优化应用单个模型来拟合整体观测数据。但是,数据之间往往存在不同的相关级别,因此某些子张量的秩甚至可能比大张量的秩更低。将单个模型拟合到所有数据将损害数据恢复的精度。为了提高丢失数据恢复的准确性,提出局部张量填充方法（Local-TC）,从子张量中恢复数据,每个子张量都包含相关性更高的数据。由于张量数据仅是按逻辑顺序存放的,因此很难一目了然的确定数据之间的关系。利用局部敏感哈希函数（LSH）快速重新组织张量数据,提取子张量,并利用投影数据来执行相似性敏感数据融合。通过实验来说明Local-TC的效果,使用两个真实流量数据集Abilene和G`EANT来比较Local-TC和几种经典的张量填充算法（CP-als,CP-opt,CP-wopt以及TK als）的效果。实验结果表明,Local-TC在提高恢复精度方面非常有效,且在张量框架下是一种通用的算法。4、基于负载均衡的局部并行子张量填充算法现在越来越多的应用使用张量填充来对缺失的数据进行恢复。但是现存的一些技术往往都忽略了张量内部的局部相似性,张量内部的局部子张量有更强的相关性,对局部子张量填充,会使得张量填充的效果更加好。针对局部子张量,每个子张量都能够单独的进行各自的计算,可以进行并行计算。但是当张量被分割成一个个小的局部子张量之后,现有算法往往没有考虑计算的负载均衡问题,使得并行计算不能最有效的进行。为了提高缺失数据的的恢复准确性,以及计算时间,提出了一种新的并行局部张量填充算法Local-TCP。本方法首先使用局部敏感哈希函数将张量进行三个维度的切分,使得形成有局部相似性的子张量,然后使用热导流的数据平衡方法,将每个子张量中的计算任务都进行有效的均衡,使得算法能够更有效的进行并行计算,进行完子张量数据平衡后,将算法扩展到GPU上进行计算,得到最终的填充结果。将算法与经典的CP-als,CP-opt,CP-wopt和TK-als在网络流量数据集（Abilene,G`EANT）上进行比较,从实验结果可以得到,在数据集上,算法Local-TCP无论在精确度还是在计算时间上都有所提高。