论文部分内容阅读
随着互联网的飞速发展,网络在网络结构、数据流量和商用用途等方面变得越来越复杂。管理这样的的网络是非常困难的。网络测量作为认知、监控网络的主要手段就显得尤为重要。网络断层扫描技术是一种高效的利用端到端的信息计算和推测网络内部状态的网络测量方法。其通过部署监测节点,利用监测节点发送探测包,得到端到端路径指标的观测值,从而推测链路指标,具有较低的测量开销。如何部署监测节点使得网络中链路可测的问题引起了国内外学者的广泛关注,很多工作研究了网络拓扑与链路可测性的关系,考虑如何部署监测节点使得网络可测。但这些工作均假设网络是可靠的,没有考虑链路失效会对网络测量的影响,而链路失效是网络中很常见的。本文主要研究了链路在网络中任意k条链路失效时仍可测的拓扑条件,并据此设计了监测节点部署算法,使得在网络中存在失效链路时,网络中尽可能多的链路仍可通过端到端的测量路径推测出。 本研究主要内容包括:⑴提出了k可测这一新颖的概念,即链路在网络中任意其他k(k≥0)条链路失效仍可测,来描述断层扫描的鲁棒性,应对链路失效对断层扫描技术带来的影响。⑵研究了链路可测性与网络拓扑结构之间的关系,提出并证明了链路k可测充分必要的拓扑条件,回答了在给定监测节点部署下网络中哪些链路是k可测这一问题。⑶提出了有效的多项式复杂度的监测节点部署算法。在监测节点个数一定的情况下,该算法能求出使得网络中k可测链路数目最多的监测节点部署方案。同时,本文利用真实的网络拓扑,进行了大量实验,验证了该算法的有效性。