论文部分内容阅读
网络层析成像是一种网络测量技术,能够在目标网络不提供测量协作的情况下,通过端到端测量的方式推断出链路时延分布等目标网络参数。网络层析成像不仅适用于普通网络用户,对于网络管理者而言,也是一种重要的网络性能监控措施。然而,随着互联网规模的快速增长以及大量新技术的开发和应用,互联网的一些特征正逐渐发生着变化。一种典型的情况是网络流量均衡技术会在网络中引入多径路由,使得在端节点间可存在多条可用路径,在改变传统单源网络树型拓扑结构的同时,也对网络层析成像等网络测量技术提出新的要求。本文针对多径路由网络这种新网络场景,在多径路由网络识别、多径路由网络端到端测量路径定位、多径路由网络拓扑推断、多径路由网络拥塞链路诊断等四个主要方面开展多径路由网络层析成像方法研究,并取得如下相应成果:<1>.针对多径路由网络识别问题,首先通过对端到端报文到达顺序进行概率建模,在理论上证明报文无乱序传输概率具有路由区分性,即单径路由情形下的报文无乱序传输概率对多径路由情形表现出一致的大小关系。然后基于网络端到端报文到达顺序测量,提出一种既能够分辨多径路由网络又能够用于识别多径路由类型的探测方案。理论分析结果表明,所提多径路由网络识别方案能够取得非常低的检测失效概率。实验结果验证所提方案的有效性;<2>.针对多径路由网络测量路径定位问题,提出一种定位端节点对间探测流测量路径的网络层析成像方案。对于一个给定的单源多径路由网络,所提方案首先计算并在端节点对间部署使路径测量覆盖失败概率不高于给定门限时所需最少数量的探测流。然后,根据探测流路径时延性能相似性识别出处于同一测量路径上的探测流。最后,提出并证明探测流测量路径能够被唯一定位时目标拓扑所需要满足的一个充分条件。实验结果表明所提方案对探测流测量路径的定位效果良好;<3>.针对多径路由网络拓扑推断问题,首先利用图割的方法在理论上证明单源多径路由网络拓扑所对应的非树型拓扑能够被分解为一个树型拓扑和一个多源单径路由拓扑,并以此说明单源多径路由网络拓扑的可辨识性。其次通过网络端到端报文到达顺序测量方式,提出一种能够检测路径间共享割边情况的探测方案。然后基于该端到端探测方案,进一步提出用于单源多径路由网络拓扑各子拓扑端到端路径识别算法。实验结果证实所提方案具有良好的识别性能;<4>.针对多径路由网络拥塞链路诊断问题,首先理论证明单源多径路由网络链路时延方差具有可识别性。然后基于从网络端到端测量数据中提取的额外时延性能约束信息以及额外路径拥塞程度差异性量化信息,将单源多径路由网络拥塞链路识别问题归纳为约束最优化问题,并提出一系列相应的求解算法。由于从测量数据中提取更多的有用信息量以及合理地利用单源多径路由网络拓扑结构特点,实验结果表明,所提相关算法具有比现有方法更好的拥塞链路检测性能。通过解决上述问题,本文将网络层析成像的应用范围扩展到多径路由网络环境。所取得的相关成果,不仅能直接用于多径路由网络环境层析成像方法的实际测量部署,而且还能为非平稳网络等复杂网络环境层析成像方法提供借鉴,有力增强网络层析成像方法的实用性。