题目：面向大规模IP网络流量矩阵推断算法研究

网络流量矩阵(Traffic Matrix) 描述了网络源-目的节点对之间的流量状况。较普通的网络链路流量监控，流量矩阵更细致地反映网络承载应用的实际流量需求和运行状况。网络流量矩阵在网络规划、流量工程、网络可靠性分析等很多方面都具有重要价值，获取流量矩阵至今一直是一个热点研究内容。随着网络技术发展和基于网络的大规模应用的推广深入，越来越多的实用大规模IP网络不断涌现，这类网络具有规模大，设备构成复杂，网络出口多等不同于一般局域网络和广域网骨干网络的特点。由于大规模IP网络特殊性，在这种网络中获取流量矩阵成为一个困难的问题。获取网络流量矩阵可分为两类方法：通过直接测量获取和依据间接测量数据推断。直接测量获取流量矩阵主要通过当前业界的Flow技术(例如Netflow，sFlow和NetStream 等) 实现。由于网络规模大和设备构成复杂等原因，通过直接测量获取流量矩阵的方法无法真正实用。而基于间接测量数据推断流量矩阵的方法虽然不如直接测量获取精确但具有数据易获取，容易在实际网络中应用的优势。然而考察当前已发表的基于间接测量的推断算法，它们都是一次推断完整网络完整流量矩阵，在网络规模变大，出口众多的情况下这类算法仍然很难实用，且此时推断所需的部分流量矩阵元素――流量分量往往足以满足应用和管理要求。因此本文研究目标是：面向大规模IP网络依据网络设备接口流量数据推断指定流量分量。围绕该研究目标，本文重点研究了三个问题，并取得成果：(1)提出了基于网络流量线性相关的网络物理拓扑发现算法。本文研究的流量矩阵推断算法面向大规模IP网络的物理层实现，这需要准确的网络物理拓扑数据支持进一步的推断算法。而由于大规模IP网络构成复杂，已有的根据地址转发表等发现网络拓扑的方法不易获得准确的物理拓扑数据。因此本文提出基于网络流量线性相关性的拓扑发现算法。本文证明了物理直连的两个网络设备接口流量具有最强的线性相关度，并基于此统计特性提出完整的物理拓扑发现算法。(2)依据ON/OFF模型推导出理论的网络流量期望方差关系。网络流量矩阵推断算法通常依赖一个重要的统计假设，即网络流量期望和方差之间的函数关系。该关系的存在性被广泛认可，且通过观测的方法流量期望方差关系被广泛接受为幂律形式，即流量随时间变化的随机过程方差与其期望的c次幂成正比。但幂指数c 的取值当前仍在争论中。由于该关系完全由经验观测获得，因此它尚没有理论的依据和解释，同理依据该关系的算法同样缺乏理论依据的支持。通过理论推导本文依据ON/OFF 模型得到新的流量期望方差关系。ON/OFF模型是一种对网络自相似特征物理成因解释的模型，因此使用该模型推导流量期望方差关系可保证得到的函数关系与网络自相似行为特性一致。进一步，本文解释了经验获得的幂律形式期望方差关系的合理性，提出了幂指数c的准确定义；最后本文利用实际网络流量对新的流量期望方差关系进行了验证，证明了理论的流量期望方差关系比原经验获得的关系能够更好地刻画实际网络流量。(3)提出了面向大规模IP网络的网络流量分量推断算法。本文提出的算法可一次推断流动方向相反的两个流量分量。算法首先依据准确的物理拓扑数据划分待求流量分量相关的子网络拓扑并将其映射成等价的三出口网络，然后依据理网络流量期望方差关系和多元线性回归法提出完整的面向大规模IP网络的网络流量分量推断算法。最后，本文结合Netflow技术在实验室网络中搭建了测试环境，通过实际网络流量观测实验验证了算法具有较好的推断效果。