isp拓扑测量中的源点部署方法

《isp拓扑测量中的源点部署方法》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、ISP拓扑测量中的源点部署方法*魏镇韩，陈鸣(解放军理工大学指挥自动化学院南京210007)摘　要ISP拓扑测量中合理部署测量源点对于获取完整的网络拓扑有重要意义。现有研究主要基于拓扑已知的假设来讨论该问题，然而在拓扑未知情况下如何部署测量源点尚缺乏深入研究。本文通过分析ISP网络组成特点，提出了“城市覆盖”的源点部署方法。配合适当的目标集合，该方法能从理论上保证ISP拓扑中骨干链路的完整性。实验结果表明，这种源点部署方法在发现ISP骨干链路方面是有效的。关键词　IP网络；拓扑测量；源点部署1　引言了解互联网的拓扑对于研究网络结构的演化规律、分

2、析选路协议的动态性质、协议的设计等方面都具有重要意义。通常ISP不会公布其内部详细的网络拓扑，因此需要通过测量来获取相关拓扑数据。具体方法是，首先基于traceroute测量工具获取IP转发路径，继而通过聚合IP转发路径形成路由器级拓扑。目前的测量方式主要是采用多点测量，参考文献[1]称之为(k,m)-tr测量，即从k个不同的源点分别向m个不同的目标利用traceroute工具进行测量。ISP拓扑测量的目标是尽可能地获取完整的节点和链路数据。节点完整性指真实拓扑中所有节点都能通过测量被发现；链路完整性指真实拓扑中所有链路都能通过测量被发现。影响

3、拓扑测量完整性的因素主要有3个。(1)目标节点的选择参考文献[2]表明，在多点测量中增加目标节点比增加测量源点更重要，因为可以发现更多的边缘节点和链路。事实上，在测量一个ISP网络时，往往能够找到一个完备的目标节点集合，例如选择待测网络中所有可能的IP地址，在这种情况下，即使是单点测量也能确保发现所有活动的节点(这里假设所有活动节点都会响应探测报文)。参考文献[1]提出了一种完备目标集合的选择方法。(2)测量源点的选择尽管能够选择一个完备目标集合，单点测量只能获取真实拓扑结构的一个生成树。一般地，在最短选路、链路权重满足三角不等式以及没有负载均

4、衡等条件下，若想发现网络中一个回路(最小的回路是三角形)中的所有边，至少需要2个测量源点。为发现更多的链路，实际测量主要采用多点策略，通过合并每个源点所获取的树状拓扑以形成较完整的拓扑。实际测量通常采用如下策略：选择一个合适的完备目标集合或尽可能地增加目标节点，分布式部署有限数量的测量源点。直观上，上述方案能够发现待测网络中的核心节点和链路，然而仍没有充足证据来证实已测拓扑数据的完整性(特别是链路完整性)。(3)测量的权限出于安全考虑，一部分路由器限制响应由traceroute发出的ICMP探测报文，这直接阻碍了获取完整的拓扑数据。如果网络中相

5、当多的节点不响应探测报文，无论怎样选择目标和源点都不可能获取完整的拓扑数据。本文假设大部分节点都能响应探测报文。上述讨论表明，ISP拓扑测量的主要问题是如何选择测量源点和目标节点以保证节点和链路的完整性。理论上，节点完整性较之链路完整性更易实现，对于一个待测网络，若目标节点选择得足够多，所有网络节点(不包括终端主机节点)都能被发现，尽管需要进行大量测量。然而，对于多点测量，即使采用一个完备的目标节点集合仍无法保证链路完整性。增加源点数量能改善这种情况，但遗憾的是不知道增加多少源点才能保证这种完整性。重要的是，通常情况下多点测量中源点的数量是非常

6、有限的，远小于目标节点的数量。增加源点的代价远远大于增加目标节点，因而不可能大量地增加源点。如何合理地部署或选择源点以确保链路完整性是多点测量的难点，因此深入研究上述问题对于提高拓扑测量的完整性有重要意义。2　相关工作一般将路由器级拓扑表示为一个连通无向图G=(V,E)，其中V表示路由器节点集合，E表示路由器之间的链路集合。测量源点的放置问题就是选择一个节点数量最少的节点集合P，以P中的节点为测量源点通过(k,m)-tr测量能够发现G的所有边。现有研究都基于拓扑结构已知的前提。Bejerano等人在静态路由和对称路由的假设下，将源点的放置问题定

7、义为一个链路监测(linkmonitoring，LM)问题，证明了LM问题是NP-难问题，并利用贪心算法求解该问题[3]。Horton等人假设测量源点可以指定从哪条邻接链路发出探测报文，在此基础上定义了源点放置(beaconplacement,BP)问题，证明了BP问题是NP-完全问题，并利用SC问题求解算法来求解BP问题，其结论是在最坏情况下最少需要(

8、V

9、-1)/3个测量源点，最多需要(

10、V

11、+1)/3个测量源点[4]。路由策略对拓扑测量也具有一定影响，在不同的路由策略配置下，有可能得到大小不同的最小测量源点集合。如果一个测量源点在所有可能

12、的路由配置情况下都能监测某条边e∈E，则称边e为该测量源点的一条确定的可监测边。一个测量源点的确定的可监测边集(deterministicallymo