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

《ISP拓扑测量中的源点部署方法》由会员分享，可在线阅读，更多相关《ISP拓扑测量中的源点部署方法（8页珍藏版）》请在装配图网上搜索。

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

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

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

4、所获取的树状拓扑以形成较完整的拓扑。实际测量通常采用如下策略：选择一个合适的完备目标集合或尽可能地增加目标节点，分布式部署有限数量的测量源点。直观上，上述方案能够发现待测网络中的核心节点和链路，然而仍没有充足证据来证实已测拓扑数据的完整性(特别是链路完整性)。(3) 测量的权限出于安全考虑，一部分路由器限制响应由traceroute发出的ICMP探测报文，这直接阻碍了获取完整的拓扑数据。如果网络中相当多的节点不响应探测报文，无论怎样选择目标和源点都不可能获取完整的拓扑数据。本文假设大部分节点都能响应探测报文。上述讨论表明，ISP拓扑测量的主要问题是如何选择测量源点和目标节点以保证节点和链路的完

5、整性。理论上，节点完整性较之链路完整性更易实现，对于一个待测网络，若目标节点选择得足够多，所有网络节点(不包括终端主机节点)都能被发现，尽管需要进行大量测量。然而，对于多点测量，即使采用一个完备的目标节点集合仍无法保证链路完整性。增加源点数量能改善这种情况，但遗憾的是不知道增加多少源点才能保证这种完整性。重要的是，通常情况下多点测量中源点的数量是非常有限的，远小于目标节点的数量。增加源点的代价远远大于增加目标节点，因而不可能大量地增加源点。如何合理地部署或选择源点以确保链路完整性是多点测量的难点，因此深入研究上述问题对于提高拓扑测量的完整性有重要意义。2相关工作一般将路由器级拓扑表示为一个连通

6、无向图G=(V, E)，其中V表示路由器节点集合，E表示路由器之间的链路集合。测量源点的放置问题就是选择一个节点数量最少的节点集合P，以P中的节点为测量源点通过(k,m)-tr测量能够发现G的所有边。现有研究都基于拓扑结构已知的前提。Bejerano等人在静态路由和对称路由的假设下，将源点的放置问题定义为一个链路监测(link monitoring，LM)问题，证明了LM问题是NP-难问题，并利用贪心算法求解该问题3。Horton等人假设测量源点可以指定从哪条邻接链路发出探测报文，在此基础上定义了源点放置(beacon placement,BP)问题，证明了BP问题是NP-完全问题，并利用SC

7、问题求解算法来求解BP问题，其结论是在最坏情况下最少需要(|V|-1)/3个测量源点，最多需要(|V|+1)/3个测量源点4。路由策略对拓扑测量也具有一定影响，在不同的路由策略配置下，有可能得到大小不同的最小测量源点集合。如果一个测量源点在所有可能的路由配置情况下都能监测某条边eE，则称边e为该测量源点的一条确定的可监测边。一个测量源点的确定的可监测边集(deterministically monitorable edge set ，DMES)就是该源点的所有确定的可监测边组成的集合。Kumar等人5定义了任意路由配置条件下基于DMES的源点放置问题，即Beacon最小化问题( beacon

8、minimization problem，BMP)，并证明BMP是NP-完全问题，实际上该问题就是最小集合覆盖(minimum set cover，MSC)问题。同样可使用贪心算法求解BMP问题。上述研究皆假设拓扑结构已知，但在实际的测量中并不知道待测网络的确切拓扑结构，因此无法应用上述研究成果来确定最小源点集合。实践中典型的多点测量工作有： Spring N.等人开发的Rocketfuel引擎针对美国大型ISP采用公共traceroute服务器从其外部进行拓扑测量6，其特点是根据BGP路由表信息减少了不必要的测量；互联网数据分析合作协会 (cooperative association fo

9、r Internet data analysis，CAIDA)的大规模拓扑测量项目通过部署在亚洲、欧洲和北美的17个监测服务器，利用基于traceroute机制的skitter工具，针对全球97万个目标地址每天进行测量以获取全球拓扑7。其测量数据具有代表性，被广泛应用于互联网拓扑研究领域之中。然而，尽管使用了分布式的多点测量，但上述工作的源点部署是被动的或是经验性的，并没有论证其部署的合理性。上述讨论表明，在拓扑未知的情况下无法找到一个精确的源点部署方法来确保整个ISP网络的链路完整性，但可以找到一个能保证骨干链路完整性的部署方法。3“城市覆盖”的源点部署方法数以万计的ISP网络组成了互联网，

10、这些ISP网络以AS号标识并形成一个等级结构。一个ISP网络由多个POP(point of presence)及ISP骨干链路组成。一个POP就是某ISP网络在一个特定位置所拥有的一个路由器组。POP通常位于某个城市的一座建筑中，若一个ISP网络跨越多个城市，则其网络内存在多个POP，每个POP网络代表了此ISP覆盖该城市的网络。一个ISP网络中不同POP之间的链路称为骨干链路(backbone link)或核心链路。骨干链路上的路由器称为骨干或核心路由器。POP与那些不隶属同一AS的邻居网络之间的链路称为接入链路(access link)，接入链路上的路由器称为接入路由器。接入链路既可以连接

11、另一个ISP网络，也可以连接一个非ISP网络，即不具备AS号的接入网，例如企业网或校园网。图1显示了一个ISP网络的内部组成。基于ISP网络结构特点，提出一种较规范化的源点部署方法，利用该部署方法并选择合适的目标节点可以实现下列目标：确保ISP网络骨干链路的测量完整性并尽量发现更多的POP内部链路。该源点部署方法的基本思想是“城市覆盖”：在一个ISP网络所覆盖的每个城市中，至少选择一个符合如下条件的测量服务器：（1）IP地址隶属该AS；（2）IP地址隶属某个与该AS直接相连的校园网或企业网。实践中，有些城市可不部署测量服务器，例如国内大型ISP所设置的海外POP，这些POP一般只与国内少量作为

12、国际出口的POP直连，无需单独设置测量服务器。假设待测网络的最小用户地址分配单位前缀为p，按参考文献1提出的“桩网络完全覆盖”方法选择目标地址：首先从Whois数据库获得待测网络所拥有的全部IP地址块，将这些地址块进一步分割，形成一个前缀长度为p的地址块列表，然后从每个p地址块中随机选择一个地址形成待测的IP地址列表。上述过程在每个测量服务器上独立进行，因此不同测量源点的目标地址列表是不同的。选取的目标集合是完备的，能有效覆盖所有可能的桩网络地址块。图2显示了基于城市的源点部署方法的一个示例。AS X由3个POP组成，分别位于城市A、B和C。在3个城市中分别部署测量服务器S(a)、S(b)和S

13、(c)。测量服务器的地址隶属某校园网或企业网，通过接入链路与该AS直接相连(图中省略了校园网或企业网的接入路由器)。B(1)和B(2)分别表示城市B连接城市A和C的骨干路由器。下面以图2为例，讨论上述测量方案的链路完整性。（1）骨干链路完整性考察城市A和B之间的骨干链路。对于城市A中的测量服务器S(a)，其测量目标涵盖了城市B中的桩网络，同样地，对于城市B中的测量服务器S(b)，其测量目标涵盖了城市A中的桩网络，测量是双向的，因此即使A和B之间存在配置负载均衡的多条骨干链路，仍能被上述测量所发现。同理，因为在每个城市都设置测量服务器，所以通过选择合适的目标集合，上述测量方法理论上能够保证城市之

14、间骨干链路的测量完整性。（2）POP内部链路完整性考察城市B的内部链路。S(a)、S(b)和S(c)都对城市B的抽样目标地址进行测量，S(a)的探测报文经骨干路由器B(1)进入B，S(c)的探测报文经骨干路由器B(2)进入B，因此对于城市B中内部链路而言，可以认为存在3个本地测量源点进行测量。虽然无法保证全部链路的完整性，但是因为城市内部的拓扑规模比整个ISP拓扑要小得多，因此上述测量方案在经验上能够保证大部分POP内部链路被测量到。上述讨论表明，尽管无法保证所有链路的完整性，但仍能找到一个较规范化的源点部署方法，配合有效的目标选择方法，就可保证ISP网络骨干链路的测量完整性，而在POP内部链

15、路的测量上也可预期有较好的效果。4实验分析利用上述源点部署方法，笔者对中国电信骨干网Chinanet(AS4134)进行了相关测量，并与CAIDA组织提供的skitter数据进行了对比。Chinanet是覆盖全国的大规模网络，为简化讨论，只测量省会城市及直辖市(共31个城市)之间的骨干链路。4.1测量Chinanet骨干链路利用国内5个traceroute服务器8来实现Chinanet骨干链路的测量。其中位于上海、中山和成都的服务器都隶属电信，尽管中山不在讨论的城市范围，但它所有的出省路径皆经由省会广州，因此可替代广州节点进行测量；而位于北京和郑州的服务器隶属中国互联网发展中心CNNIC，虽不

16、是电信地址，但其大部分测量路径都位于电信网络内，可以采用。对每个测量服务器而言，其测量目标是其他30个城市的政府网站地址或当地电信公司网站地址。位于城市A的源点向位于城市B的目标节点发送探测报文，有可能中途经由第3方城市。因此只有对测量路径中的IP地址进行地理定位才能获取城市之间准确的骨干链路信息。IP地址定位是相当困难的，但由于只评估省会城市及直辖市之间的骨干链路，因此在某些情况下并不需要准确地定位每个IP地址，这一定程度上减少了定位的难度。本文综合采用参考文献911中的技术来定位有关IP地址。若IP路径中存在关键地址不能定位，则无法从该路径中提取正确的城市连接关系，这样的路径在评估完整性时

17、将被忽略。测量服务器及其测量信息如表1所示。其中有效路径数是指被确认有效的测量路径数量。一条测量路径若出现以下情况被认为无效：路径中地址没有全部位于AS4134之内，例如出现网通地址；路径中关键地址未能有效判别其地理位置。表1中的骨干链路数表示该服务器通过测量发现的不同骨干链路的数量。图3显示了5个源点所获取的AS4134骨干链路的连接。4.2与skitter数据的比较作为对比，本文检索了skitter数据中所含有的AS4134骨干链路信息。数据集取自CAIDA在05/10/2007到05/15/2007之间所测量的IP路径数据。根据ICANN的地址分配信息(取自05/15/2007) 12，

18、从skitter数据中截取位于中国大陆境内的IP路径信息(不含主机节点)；根据RouteViews提供的BGP路由表数据(取自05/15/2007) 13，从中获得AS4134所拥有的前缀信息，进而从skitter数据中截取位于AS4134的IP路径信息。表2列举了中国大陆以及AS4134拓扑基本数据。表2中显示skitter发现路由器地址28 827个，涵盖了中国大陆72个ISP网络，说明skitter通过大规模测量能获取较丰富的拓扑数据。上述地址中隶属AS4134的地址有14 368个，显示出Chinanet确实是国内最重要的ISP网络之一。图4显示了skitter数据所展现的AS4134

19、骨干链路的连接。与图3相比，存在以下差异。(1) 北方城市覆盖率较低。图3中AS4134覆盖了全国31个省会城市及直辖市，而图4显示skitter数据只涵盖了其中23个直辖市及省会城市，北方城市覆盖较少，这是因为现有Chinanet主服务区域为南方21省市，北方各省市是中国联通的主服务区域，因此skitter在北方省市的测量目标大部分经由联通网络而非Chinanet。(2) 城市之间的骨干链路较少。大部分骨干链路以北京和上海为中心成星形结构。这是因为大部分skitter测量服务器位于国外，其测量路径都经由北京和上海两个国际接入点进入Chinanet，因此位于AS4134内的路径都以北京和上海为

20、起点。另外，大部分城市显示出与北京或上海存在直接的路由器级连接，这可能因为POP之间使用了诸如MPLS、ATM等技术来实现互连。skitter共发现AS4134骨干链路22条，而图3中含有骨干链路55条且涵盖所有skitter发现的链路。可以看出，尽管skitter对全球进行了大规模的拓扑测量，但由于部署源点的局限，因此不能很好地反映AS4134骨干链路的分布情况。在ISP拓扑测量中，只有采用“城市覆盖”的源点部署方法才能确保骨干链路的完整性。如果在上述实验中能在其他城市中也部署测量源点，只需少量测量就可获取AS4134全面的骨干链路信息。5结束语合理地部署测量源点对于获取完整的ISP拓扑具有

21、重要意义。现有研究都是基于拓扑已知的假设来讨论源点选择问题，然而在实践中待测网络的拓扑结构往往都是未知的。对于未知的待测网络，不存在精确的源点部署方法发现所有链路。基于ISP网络的组成特点，本文提出一种较规范化的源点部署方法，该方法基于“城市覆盖”的思想，在待测ISP网络所涉及的各城市中设置源点，通过选择合适目标节点，能够实现ISP骨干链路的测量完整性，同时也能保证一定的城市内部链路的完整性。实验表明，因为源点部署的局限，skitter不能很好地反映中国电信骨干网Chinanet的骨干链路数据，同时也说明只有按照“城市覆盖”的思想部署源点才能有效测量ISP拓扑。参考文献1姜誉, 何松. Int

22、ernet路由器级拓扑测量中目标选择方法研究.通信学报, 2006，27（2）2Barford P, Bestavros A, Byers J, et al. On the marginal utility of network topology measurements. In: Proc First ACM SIGCOMM Workshop on Internet Measurement (IMW 2001), San Frandisco, California, USA,20013 Bejerano Y, Rastogi R. Robust monitoring of link dela

23、ys and faults in IP networks. In: Proc IEEE INFOCOM 2003, San Francisco, California, 20034 Horton J D，Lopez-Ortiz. A. On the number of distributed measurement points for network tomography. In: Proc 3rd ACM SIGCOMM Conf on Internet Measurement (IMC 2003), Miami Beach, Florida，USA,20035 Kumar R, Kuma

24、r J. Efficient beacon placement for network tomography. In: Proc 4th ACM SIGCOMM Conf on Internet Measurement (IMC 2004), Taormina, Sicily, Italy, 20046 Spring N, Mahjan R, Wetherall D. Measuring ISP topologies with rocketfuel. ACM SIGCOMM Computer Communication Review, 2002, 32(4)7 Cooperative asso

25、ciation for internet data analysis，http:/www.caida.org8 世界网络， 9 Padmanabhan V N , Subramanian L. An investigation of geographic mapping techniques for Internet host. ACM SIGCOMM Computer Communication Review. 2001, 31(4)10 Subramanian L. On inferring the geographic properties of the Internet.Univers

26、ity of California at Berkley, 200211 姜誉.Internet路由器级拓扑测量与分析技术研究.哈尔滨工业大学博士论文，200512 Internet corporation for assigned names and numbers，http:/www.icann.org/13 MEYER D. University of oregon routeviews project，http:/www.routeviews.org/Vantage Points Deployment Method on ISP Topology MeasurementWei Zhen

27、han, Chen Ming （Institute of Command Automation，PLAUST, Nanjing 210007, China）Abstract The vantage points deployment is important for acquiring complete Internet topologies. In current researches, the issue is discussed under the assumption that the topologys structure is known. However, how to depl

28、oy vantage points under unknown topology is lack of researches. The structure characteristic of ISP topologies is analyzed, and a vantage points deployment method that was described as city coverage is proposed. The method guarantees the completeness of the ISP backbone links theoretically. Experiment results show that vantage points deployment method is efficient on finding ISP network backbone links.Key words IP network，ISP topology，vantage points deployment