中国IP级网络拓扑测量与分析.doc

第12期张宇等：中国IP级网络拓扑测量与分析101中国IP级网络拓扑测量与分析张宇，方滨兴，张宏莉（哈尔滨工业大学 计算机网络与信息安全技术研究中心，黑龙江 哈尔滨 150001）摘 要：以建立中国IP级网络拓扑图景为目标，首先评价了传统的目标抽样法，提出了3项改进技术，并测量了中国网络，然后运用复杂网络研究方法提取并比较分析了拓扑特征，最后采用IP2AS技术统计了自治域规模。结果表明，传统目标抽样法将丢失大量信息，改进技术在保持完整性的同时降低约一半负载。获得新的中国拓扑规模5倍于CAIDA的skitter。新拓扑与skitter拓扑相比，呈现更显著的非相称性、更弱的聚集、更短的距离、更不均衡的节点流量分布。发现了中国自治域规模的重尾分布。关键词：拓扑测量；拓扑建模；复杂网络；自治域规模中图分类号：TP393 文献标识码：A 文章编号：1000-436X(2007)12-0096-06Chinese IP-level network topology measurement and analysisZHANG Yu, FANG Bin-xing, ZHANG Hong-li(Research Center of Computer Network and Information Security Technology, Harbin Institute of Technology, Harbin 150001, China)Abstract: To build the prospect of Chinese IP-level topology, the traditional destination sampling method was evaluated; three new improved techniques were developed; and Chinese network was measured. With the methodology of complex network, the topology characteristics were extracted and compared. The sizes of autonomous systems (AS) were investigated with the IP2AS technique. The results showe that lots of information is missed by the traditional method; the load is reduced to about a half by the new techniques while the completeness is retained; and the size of new discovered Chinese topology is 5 times as many as that discovered by CAIDAs skitter. Compared to skitters topology, the more complete topology showe more observable dissortativity, weaker clustering, shorter distance and more disequilibrium of node traffic distribution. The heavy-tailed distribution of AS sizes is discovered.Key words: topology measurement; topology modeling; complex network; autonomous system size1 引言收稿日期：2007-09-23；修回日期：2007-12-03基金项目：国家自然科学基金资助项目（60203021）Foundation Item: The National Natural Science Foundation of China (60203021)测量Internet已成为研究其复杂性的基本手段之一。IP级(也称接口级)网络拓扑以路由器的接口为节点，相邻接口为链接。对其测量采用基于traceroute技术，发现从监测点(或称探测源)到目标之间前向路径上，一组顺序相连路由器的接口IP地址。以CAIDA的skitter为代表的测量实践13，为网络拓扑建模411提供了有力的数据支持，促进了学术界向洞察网络本质的方向迈进。本文以初步建立中国IP级网络拓扑图景为目标。截止2004年8月31日，中国IPv4地址空间约为21.8万个/24前缀，自治域（AS）号约180个。国内ISP之间互联互通，作为一个整体无需经过国外ISP的传输流量，因此，本文研究对象具有典型性。与以往工作相比，本文意义在于：一方面，采用比以往更细的探测粒度和若干新技术，发现了中国网络节点数量5倍于skitter1，对拓扑特征的分析也就会更准确；另一方面，目前尚未有工作对中国IP级网络拓扑进行全面细致的研究，网络动态性使得测量结果具有不可重现性，因此在下一代IPv6网络全面建立之前，有必要对国家网络进行测量。2 IP级拓扑测量目标集、探测技术和监测点集是拓扑测量实践的3项基本因素。首先考察高密度目标抽样的效果，然后提出并评价降低探测负载的改进技术，最后给出多监测点测量结果。2.1 高密度目标抽样提高完整性的一种简单易行的方法是增加目标数量，但现有工作中，较密集目标抽样是从每个/24前缀中选一2,7。自然提出一个问题：采用更高密度的目标抽样对提高完整性有多大帮助？定义1 设目标网络IP地址空间D，从中选择目标集D，则目标抽样度=32+lb(|D|/|D|)。定义2 设目标网络链接集合L，一次目标抽样度为的结果是L的子集L，则链接覆盖率CL()=|L|/|L|。在黑龙江、四川、重庆3个监测点上对随机选取的660个/19前缀（占中国IP地址空间的1/10），采用=31的蛮力测量，将该数据集命名为“FT-BF”。约定：31时，CL()=1。对每一个/19前缀，采用均匀随机抽样模拟测量，取1931间整数，重复35次取平均值。统计九分位数（按升序排列第0、5%、10%、25%、50%、75%、90%、95%、100%位的样本）。重庆监测点的CL()，如图1所示。图1 抽样率与链接覆盖率随着值增加，CL()大体呈线性增长趋势(除了当较大时部分值达到饱和)。对CL()中位数进行线性拟合，得到增长率约为7.588。令人吃惊的是，通常的=24，只有一半左右的CL()超过50%，而要使一半的CL()超过80%，则至少为27。也就是说，通常方法丢失了大量拓扑信息，而获得较高完整性所需的目标集规模是相当庞大的。目标越多越好在实践中受到多种因素制约。简单的看，目标集规模|D|=PF/f，其中P为一轮测量持续时间，F为监测点单位时间发包数量，f为每次traceroute平均发包数量。参考skitter，设P=50h；根据监测点本地网络情况，设F=40packet/s；由测量工具fastrace测试得到f5.6packet；根据公式，确定|D|1.28106，即=26.56。在12个国内监测点上使用不完全相同的目标集，无重复目标总数达5.03106。2.2 改进的探测技术为降低每次traceroute的平均发包数，从而间接提高目标总数，开发了3项新技术，并在fastrace中实现。前两项技术利用了“若目标的IP地址邻近，则其路径也相似”的路由性质。定义3 给定已经测量过的目标集D*和当前将要测量的一个目标iD-D*，D*中IP地址距离i最近的目标为j。监测点到j的路径p，称为i的参照路径。1) 近邻路径倒退技术BNP(backward on neighbors path) 测量i时，从参照路径p的最后一跳h上开始，TTL值递增前向探测，直到探测结束；然后从h1跳开始，TTL值递减倒退探测，直到与p在同一跳上发现相同接口时停止。将h超过实际最后一跳的负载，称作超出负载。2) 近邻无应答结束技术NNS(neighbors non-response stop) 若参照路径p的最后一跳h是无应答结束，且测量i时，h跳的第一个探测包也没有应答，则结束探测。将称为NNS结束。3) 多类型探测技术MTP(multi types probing) 交替使用TCP SYN(port 80)、UDP、ICMP类型探测包。按照MTP、NNS、BNP的顺序,逐步将新技术加入到传统traceroute中进行评价。1) MTP 在北京监测点，使用3种单一类型探测包和MTP对随机选取的20万个目标进行扫描，统计各类探测结束原因所占百分比，如表1所示。到达率不超过四分之一，无应答率约占一半；不同类型探测对测量结果略有影响。采用MTP使到达率提高约3%，同时无应答率降低约3%。表1不同探测类型的结束原因百分比探测类型到达率/%无应答率/%不可达率/%ICMP215524UDP205723TCP215722MTP245224下面2项评价在FT-BF数据上，以抽样度=26.56来进行。2) NNS+MTP 表2给出了NNS结束数量与无应答结束数量的比值CS，结果CS大于30%。这对于占半数的无应答结束来说，所节省的负载是很可观的。表2新技术评价结果重庆黑龙江四川CS50%33%40%CL99%99%99%CH40%53%46%CO8%12%9%3) BNP+NNS+MTP 测量的完整性、负载、超出负载的测度分别为CL=L/L、CH= H/H、CO=HO/H。传统技术发现的链接数量为L，负载为H；采用新技术的分别为L和H；BNP超出负载记为HO。实验中设每跳消耗一个探测包，无应答结束消耗3个探测包，结果如表2所示。CL都高达99%；CH低于55%，换句话说，减少了45%以上的负载；CO都低于15%。可见，对于高密度（=26.56）目标集，新技术可以在保证完整性前提下，有效降低负载，额外的超出负载也是可接受的。2.3 测量结果表4SKCN04与CNTP04复杂网络特征比较度量值nmrATdmaxBSKCN0415 53431 0473.9972.9750.7930.027 60.1380.069 89.5973.746291.769CNTP0481 765143 1783.5022.6280.6640.1460.047 30.013 09.5252.197252.017skitter监测点共25个, apan-jp, f-root, m-root, neu4个监测点没有在2004年12月1921日期间的数据。多监测点间互相弥补在下游连通性上的缺失，fastrace与skitter监测点以本地与非本地的视点观测中国网络。在2004年12月1921日期间，fastrace在12个分布于不同省份的监测点实施测量。与此同时，收集CAIDA的21个skitter监测点在此期间一个测量周期的数据(经CAIDA授权)，提取目标落入中国网络的部分。在拓扑提取过程中，只保留中国的公共IP地址，对匿名和私有IP地址全部删除而不做推测，共删除8 000个私有或国外IP地址。如此得到的图的规模是下界，以保证数据的规范性。两份数据中拓扑规模的比较如表3所示。fastrace各监测点平均发现节点或链接数量都高于skitter；节点总数是skitter的5倍，链接总数是其4倍，同时skitter独自发现8 600条链接是对fastrace的重要补充。可见，广泛使用的CAIDA的skitter数据集丢失了大量拓扑信息，这是由于整个Internet规模对skitter目前的测量能力而言过于庞大，难以针对中国网络进行高密度测量。表3fastrace与skitter拓扑规模比较节点/链接数量(103)平均值标准差总和独自全部Fastrace62/7914/1782/13667/11082/143Skitter2.4/5.00.38/0.4416/310.7/8.63 中国网络拓扑分析将fastrace与skitter合并后的拓扑，称为CNTP04；将skitter发现的拓扑，称为SKCN04。首先，通过比较CNTP04和SKCN04的复杂网络特征来更准确的刻画中国网络拓扑。然后，研究细粒度的IP级拓扑在粗粒度的AS上的分布情况。3.1 复杂网络特征比较复杂网络是图论与统计物理交叉所产生的新兴研究领域。一方面，利用图这个数学概念形式化表达事物的结构与交互；另一方面，运用统计物理分析大规模真实网络的统计特征，寻找其结构、动力学和功能的内在规律。CNTP04和SKCN04的统计特征如表4所示。网络拓扑的直观抽象是无权无向图，设节点数量为n，链接数量为m。1)平均节点度 =2m/n，用以描述图的疏密。SKCN04比CNTP04更密，原因之一：由于度较大的节点具有更大的介数(见后面6)，有更大概率被发现11。因此，skitter较小的目标集就倾向于发现这些高度节点，而fastrace的大目标集在发现高度节点的同时，也发现了更多的低度节点，使得平均值稍低。2)节点度分布P(k) 定义为度k节点数量占节点总数的比例。Faloutsos等9发现P(k)服从幂律(power-law)，即P(k)k-r，呈无尺度(scale-free)性质。文献2进一步发现Weibull分布exp(-(k/)的拟合程度更好。2种分布都是典型的重尾(heavy tail)分布，反映了节点连通性的强弱极其不均衡，分别由指数r和来描述。P(k)的补累积分布函数(CCDF)如图2所示。图2显示2个拓扑的度分布总体上相似，但SKCN04的曲线比CNTP04的衰减得更快，表4中SKCN04的2个值也都略大于CNTP04，说明SKCN04连通性的不均衡性更显著。不仅如此，当k较小时，SKCN04的曲线比CNTP04的高，即SKCN04中低度节点所占比例更小，进一步说明了SKCN04的较大的原因。图2 度的补累积分布函数3)度相关性(correlation) P(k1,k2) 定义为随机选择的一条链接的两端节点度为k1，k2的概率。通常简化为平均邻居连通性(average neighbor connectivity)，K(k)等于k度节点的邻接节点度期望。以K(k)/(n1)正规化，如图3所示。另外，P(k1, k2)还可由相称系数(assortativity coefficient) A (1A1)7来刻画。若A0，称图是相称的(assortative)。Newman7发现Internet节点度相关性是非相称的。图3和表4中A都显示CNTP04比SKCN04具有更明显的不相称性。这说明fastrace发现了更完整的边缘网络拓扑，这部分网络为了向尽可能多的用户提供接入服务，而呈类似星型的结构，即一个高度节点连接了大量低度节点。图3 度-正规平均邻居连通性4)聚集(clustering) k度节点的局部聚集(local clustering)c等于邻居间链接数量除以k(k1)/2。特别的，当k=1时，c=0。聚集系数(clustering coefficient) 等于c的平均值，这是描述小世界(small world)现象的一个度量8。另一个可替代来刻画聚集性的度量是传递性(transitivity)T，定义为若节点u同时与节点v，w相连，则v和w也相连的概率7。表4显示SKCN04的2个聚集特征都要强于CNTP04。前者低度节点较少和较高已对此有所预兆，而且后者的不相称性也使得高度节点的c较小。5)距离分布P(d) 定义为随机选取一对节点间最短路径长度d的概率分布，如图4所示。P(d)服从类似高斯分布，因此用d的平均值和标准差来描述。也称为特征路径长度，用来描述小世界现象中路径较短的性质8。图直径dmax等于d的最大值。一般直觉认为，图规模较小而且较高，意味着有更多捷径可走，P(d)的分布也应更集中，期望SKCN04的，和dmax都比CNTP04的小。然而，实际情况与直觉相反：CNTP04的各个值都比SKCN04的小。产生以上现象的原因是CNTP04的规模大和略低是由于包含更多边缘网络的低度节点，但在承担传输任务的网络核心部分却包含比SKCN04具有更丰富的链接。图4 距离分布6)度与介数(betweenness)相关性b(k) 定义为k度节点正规化介数的平均值。其中，一个节点的介数b等于所有节点对之间最短路径经过该节点的概率之和。可以将介数看作在节点对均匀随机通信的情况下，经过节点的流量11。用b/n(n1)将b正规化，这样，b(k)就反映了不同度的节点的流量分布，如图5所示。当k20)的度与介数的相关性较弱，其原因就是前面在度相关性部分的解释，即部分高度节点处于网络边缘。图5 度-平均正规化介数综上所述，2个拓扑大体上具有类似特征。不同之处主要在于CNTP04比SKCN04包含了更丰富的网络核心链接以及更多的边缘网络拓扑信息，呈现更明显的不相称性、更弱的聚集特征、更短的距离、更不均衡的节点流量分布。由此，可以推测实际拓扑比CNTP04在这些特征上的倾向程度更强。3.2 自治域规模统计为了解ISP基础设施建设状况，考察IP级拓扑在AS上的分布，采集2004-12-1821期间的BGP路由表数据，从中提取源AS前缀对，映射CNTP04的IP地址到AS号。数据源包括RouteViews1，RIPE NCC RIS2和CERNET BGP VIEW3。提取源AS属于中国的记录，去掉私有AS号和多宿主的记录，不进行前缀合并，共得到12 000条记录，覆盖了中国191个AS中的123个。采用最长前缀匹配，共发现97个AS。文献12在5个月之后(2005年5月)，使用类似方法测量发现84个AS。将CNTP04中节点和链接按照是否连接不同AS来划分，域际节点占5.1%，域际链接占4.9%。统计发现，AS规模，即包含节点与链接数量，呈现重尾特征。以幂律分布P(x)x-r对尾部(x100)拟合，得到指数r分别为1.703和1.603。这反映了现实中几个大AS承担国内网络服务的同时，又有大量地区性小AS作为补充。表5列出了规模最大的前十个AS。中国电信的CHINANET骨干网和网通集团的CHINA169骨干网列前两位是意料之中，分别占节点总数的36%和20%，占链接总数的45%和19%，远高于其他ISP。上述观察也再次体现了Internet中普遍存在的不均衡特征。表5中国AS规模前十名AS号节点数(103)链接数(103)名称413429.263.5CHINANET-BACKBONE483716.127.1CHINA169-BACKBONE98005.96.2UNICOM48125.311.8CHINANET-SH-AP98085.07.4CMNET-GD93943.14.5CRNET99292.43.9CNCNET-CN45382.33.4ERX-CERNET-BKB48081.44.0CHINA169-BJ48141.21.8CHINA169-BBN4 结束语本文主要贡献在于：1)高密度抽样实验发现通常测量丢失了大量链接；同时，新改进的技术可将负载降低一半左右。这2点都具有一般性，不只限于中国网络，也可指导其他网络的测量实践。发现被广泛使用的CAIDA的skitter数据集在完整性上存在局限，至少丢失了实际中国网络拓扑链接中的约80%。2)首次对中国IP级网络拓扑特征进行了提取。通过对CNTP04与SKCN04图论特征的比较发现，定性考察时两者无本质差异，但定量考察时，却存在一些显著的不同。这说明在使用测量数据进行某项工作之前，需要仔细检查其可用性，并判断所关心问题是否对测量中存在的不足很敏感。提取的特征参数还可作为中国网络拓扑建模的参考。3)统计了中国AS规模分布，指出规模分布的重尾特征。然而，本文工作仍然与获取完整、准确的网络拓扑数据的目标具有一定差距，同时中国网络作为整个Internet的一部分，两者在统计特征上也会有差异。在今后工作中，将从测量目标的优化选取入手，进一步提高测量完整性；同时研究网络拓扑的自相似性，考察局部统计特征与全局统计特征的关系，通过对中国网络拓扑的研究来帮助认识Internet的全貌。参考文献：1BROIDO A, CLAFFY K. Internet topology: connectivity of IP graphsA. SPIE International Symposium on Covergence of IT and CommunicationC. 2001. 172-178.2HUFFAKER B, PLUMMER D, MOORE D, et al. Topology discovery by active probingA. The 2002 Symposium on Applications and the Internet (SAINT) WorkshopsC. 2002. 90-96.3SHAVITT Y, SHIR E. DIMES: let the Internet measure itselfJ. SIGCOMM Computer Communication Review, 2005, 35(5):71-74.4BOCCALETTI S, LATORA V, MORENO Y, et al. Complex networks: structure and dynamicsJ. Physics Reports, 2006, 424:175-308.5DOROGOVTSEV S N, MENDES J F F. Evolution of networksJ.Advances in Phys