论文部分内容阅读
【摘 要】网络中路由器拓扑发现是研究网络结构和行为的重要基础。路由器多址综合问题是拓扑发现中的一个难题。在总结现有的路由器多址综合解决方法后提出一种新的方法——邻居-子网综合法。与以往方法相比，该方法可信度提高、效率变快，效果更加明显，较好地解决了路由器多址综合问题。
【关键词】拓扑发现；路由器多址综合方法；邻居-子网综合方法
0.概述
通过对网络拓扑的分析可以发现网络中存在的各种特性，例如鲁棒性（robustness）、可靠性、安全性、传输效率等一些关系到网络发展的重要方面，同时也是推动协议发展、网络管理等的重要动力，例如在不影响现有网络应用的基础上提出新的网络应用。因此，网络拓扑发现作为拓扑分析的基础是非常重要的。
目前，有很多组织和学者致力于网络拓扑发现和研究，主要有 CAIDA的Skitter工程、NLANR的AMP工程、PlanetLab的Scriptroute 探测基础设施、Tel Aviv大学的DIMES工程等。这些项目和工程中探测网络拓扑的主要方法是使用TraceRoute对若干已知的目标 IP地址进行探测。在这些项目中为了对整个Internet有比较全面的了解，通常在全世界范围内布置一些探测节点对整个Internet中的可达地址进行探测，或者使用源选路由的TraceRoute对网络进行 探测。
TraceRoute也存在着各种问题，例如目标地址集的选取问题、匿名路由器问题、路径变化问题、路由器多址综合问题。本文提出了一种新的路由器多址综合问题的解决方 法——邻居-子网综合法，使多址综合的可信度提高、效率变快、资源利用减少、效果更加明显。
1.路由器多址综合问题的一般解决方法
一个路由器一般有若干个接口，每个接口都有独立的IP地址。TraceRoute过程中返回的ICMP响应报文地址为探测报文经过的接口地址而不是路由器本身的标识地址。于是确定哪些地址是同台路由器的地址便成了一个非常重要的问题，称为路由器多址综合（IP Alias Resolution）问题或路由器别名綜合问题。这个问题直接关系到所得拓扑的准确性和完整性。目前主要的解决方法有对路由器的UDP高端口探测、反向DNS查询、IP报文ID值判定、双向TraceRoute子网综合等。
1.1 DNS反向查询
DNS 反向查询是指在 DNS 服务器上查询到 IP 地址对应的域名（DNS Name）。一个路由器包括若干个接口，每个接口都有各自的IP地址。不同的接口地址可能对应不同的域名，但如果在域名命名时采取系统化方法，那么通过分析域名就可以确定这些IP地址是否属于同一个路由器。一个路由器的多个接口地址也可能对应同一个域名，此时域名相同的IP地址都属于同一个路由器。还可以在获取路由器一个接口IP地址的域名后，对其进行DNS查询来获取该路由器的其他接口地址。
DNS反向查询所得结果可信度高，是一种很有效的方法。但是当一些路由器并没有分配域名，或者没有按照系统化结构化的方法分配域名时，DNS反向查询法就失效。
1.2 UDP高端口探测
UDP高端口探测是指对路由器某个接口IP地址发送UDP高端口（应为不可用端口）探测报文，此时路由器返回的ICMP报文中的源地址为路由器的标识地址（一般为路由器接口地址中的最小值或最大值）。因此，在对不同 IP地址进行UDP高端口探测时，如果返回的 ICMP报文源地址相同，那么这些 IP地址就属于同一个路由器。在对接口IF1和 IF2的地址进行UDP高端口探测时，RouterA会回送一个端口不可达的ICMP报文（ICMP1，ICMP2），这些 ICMP 报文中源地址都为 RouterA的标识地址（设为 IF0）。由此可知，IF1和 IF2这2个接口地址属于同一个路由器。
一些路由器对UDP高端口探测报文并不处理，所以，探测源接收不到ICMP报文。还有一些路由器对返回的ICMP报文的地址配置为其出口或者入口地址，而不是路由器标识地址。此时该方法失效。
1.3 IP报文ID值判定 根据IP报文中的ID属性（identity）判定多个IP地址是否属于同一个路由器
一般情况下，路由器发送IP报文的ID值是递增的。
有些路由器发送的IP报文中的ID值是随机的，而且可能因网络延时，2个刺激报文到RouterA的时间间隔较大，这时返回的IP报文的ID值差别也比较大。 此时该方法失效。
2.邻居-子网综合法
各种多址综合问题解决方法都存在这样或那样的问题，下面提出一个解决路由器多址综合问题的更好方法——邻居-子网综合法。按TraceRotue方向，邻居-子网综合法将获得3条路径：…->IP0->IP1->IP2->…，…->IP0->IP1->IP3-> … 和 …->IP0->IP1->IP4->…。从这 3 条路径中可以看出，IP1分别与下一跳IP2，IP3和IP4相邻，那么拥有 IP1 的路由器必定还有另外 3个接口分别与IP2，IP3和IP4相连，假设它们的接口地址分别为 IP2’， IP3’和 IP4’。IP2/IP2’， IP3/IP3’和 IP4/IP4’这6个接口的3对地址分别属于同一个网段，ISP为了节省地址空间，这些网段一般使用31或30位子网掩码。
为了得出 IP2’的具体地址，首先计算出与 IP2处于同一个/31网段中的另一个地址，并使用UDP高端口探测或IP报文 ID 值判断法判断这个地址与 IP1是否属于同一个路由器。如果是则结束，如果不是则对/30段中另外2个地址进行判断。如果是则结束，如果依然不是，则放弃对IP2’的综合。依次对IP1所有对应邻居进行以上操作。
至此只完成了对该路由器的第1次综合，还必须对IP2’和其他由以上方法得出的该路由器的接口再次进行上述操作。如此循环，直到把所有发现的该路由器的接口地址全部综合后，才完成对该路由器的多址综合。
3.实验效果
为了检验本方法的实用性，对某 AS 的所有地址段进行TraceRoute，并对其中的路由器地址（570 个）分别使用 DNS反向查询、UDP高端口探测、邻居-子网综合法进行多址综合，可以发现，邻居-子网综合法的别名率远远高于其他方法，虽然回包率比反向 DNS 查询法低，但是综合率远远低于其他3种方法，说明邻居-子网综合法相对其他方法更加有效。
4.结束语
目标网络探测中路由器多址综合问题是一个非常重要的问题。本文针对这个问题提出了邻居-子网综合法，相对其他方法实现更加简单，多址综合结果更加准确、完整、覆盖范围更广。
以后的工作除了对路由器多址综合问题继续深入研究外，还要针对目标地址集的选取问题、匿名路由器问题、路径变化问题等在路由器级拓扑发现过程中的难题进行研究，进一步加强路由器级拓扑发现的准确性、完整性和有效性。 [科]
【关键词】拓扑发现；路由器多址综合方法；邻居-子网综合方法
0.概述
通过对网络拓扑的分析可以发现网络中存在的各种特性，例如鲁棒性（robustness）、可靠性、安全性、传输效率等一些关系到网络发展的重要方面，同时也是推动协议发展、网络管理等的重要动力，例如在不影响现有网络应用的基础上提出新的网络应用。因此，网络拓扑发现作为拓扑分析的基础是非常重要的。
目前，有很多组织和学者致力于网络拓扑发现和研究，主要有 CAIDA的Skitter工程、NLANR的AMP工程、PlanetLab的Scriptroute 探测基础设施、Tel Aviv大学的DIMES工程等。这些项目和工程中探测网络拓扑的主要方法是使用TraceRoute对若干已知的目标 IP地址进行探测。在这些项目中为了对整个Internet有比较全面的了解，通常在全世界范围内布置一些探测节点对整个Internet中的可达地址进行探测，或者使用源选路由的TraceRoute对网络进行 探测。
TraceRoute也存在着各种问题，例如目标地址集的选取问题、匿名路由器问题、路径变化问题、路由器多址综合问题。本文提出了一种新的路由器多址综合问题的解决方 法——邻居-子网综合法，使多址综合的可信度提高、效率变快、资源利用减少、效果更加明显。
1.路由器多址综合问题的一般解决方法
一个路由器一般有若干个接口，每个接口都有独立的IP地址。TraceRoute过程中返回的ICMP响应报文地址为探测报文经过的接口地址而不是路由器本身的标识地址。于是确定哪些地址是同台路由器的地址便成了一个非常重要的问题，称为路由器多址综合（IP Alias Resolution）问题或路由器别名綜合问题。这个问题直接关系到所得拓扑的准确性和完整性。目前主要的解决方法有对路由器的UDP高端口探测、反向DNS查询、IP报文ID值判定、双向TraceRoute子网综合等。
1.1 DNS反向查询
DNS 反向查询是指在 DNS 服务器上查询到 IP 地址对应的域名（DNS Name）。一个路由器包括若干个接口，每个接口都有各自的IP地址。不同的接口地址可能对应不同的域名，但如果在域名命名时采取系统化方法，那么通过分析域名就可以确定这些IP地址是否属于同一个路由器。一个路由器的多个接口地址也可能对应同一个域名，此时域名相同的IP地址都属于同一个路由器。还可以在获取路由器一个接口IP地址的域名后，对其进行DNS查询来获取该路由器的其他接口地址。
DNS反向查询所得结果可信度高，是一种很有效的方法。但是当一些路由器并没有分配域名，或者没有按照系统化结构化的方法分配域名时，DNS反向查询法就失效。
1.2 UDP高端口探测
UDP高端口探测是指对路由器某个接口IP地址发送UDP高端口（应为不可用端口）探测报文，此时路由器返回的ICMP报文中的源地址为路由器的标识地址（一般为路由器接口地址中的最小值或最大值）。因此，在对不同 IP地址进行UDP高端口探测时，如果返回的 ICMP报文源地址相同，那么这些 IP地址就属于同一个路由器。在对接口IF1和 IF2的地址进行UDP高端口探测时，RouterA会回送一个端口不可达的ICMP报文（ICMP1，ICMP2），这些 ICMP 报文中源地址都为 RouterA的标识地址（设为 IF0）。由此可知，IF1和 IF2这2个接口地址属于同一个路由器。
一些路由器对UDP高端口探测报文并不处理，所以，探测源接收不到ICMP报文。还有一些路由器对返回的ICMP报文的地址配置为其出口或者入口地址，而不是路由器标识地址。此时该方法失效。
1.3 IP报文ID值判定 根据IP报文中的ID属性（identity）判定多个IP地址是否属于同一个路由器
一般情况下，路由器发送IP报文的ID值是递增的。
有些路由器发送的IP报文中的ID值是随机的，而且可能因网络延时，2个刺激报文到RouterA的时间间隔较大，这时返回的IP报文的ID值差别也比较大。 此时该方法失效。
2.邻居-子网综合法
各种多址综合问题解决方法都存在这样或那样的问题，下面提出一个解决路由器多址综合问题的更好方法——邻居-子网综合法。按TraceRotue方向，邻居-子网综合法将获得3条路径：…->IP0->IP1->IP2->…，…->IP0->IP1->IP3-> … 和 …->IP0->IP1->IP4->…。从这 3 条路径中可以看出，IP1分别与下一跳IP2，IP3和IP4相邻，那么拥有 IP1 的路由器必定还有另外 3个接口分别与IP2，IP3和IP4相连，假设它们的接口地址分别为 IP2’， IP3’和 IP4’。IP2/IP2’， IP3/IP3’和 IP4/IP4’这6个接口的3对地址分别属于同一个网段，ISP为了节省地址空间，这些网段一般使用31或30位子网掩码。
为了得出 IP2’的具体地址，首先计算出与 IP2处于同一个/31网段中的另一个地址，并使用UDP高端口探测或IP报文 ID 值判断法判断这个地址与 IP1是否属于同一个路由器。如果是则结束，如果不是则对/30段中另外2个地址进行判断。如果是则结束，如果依然不是，则放弃对IP2’的综合。依次对IP1所有对应邻居进行以上操作。
至此只完成了对该路由器的第1次综合，还必须对IP2’和其他由以上方法得出的该路由器的接口再次进行上述操作。如此循环，直到把所有发现的该路由器的接口地址全部综合后，才完成对该路由器的多址综合。
3.实验效果
为了检验本方法的实用性，对某 AS 的所有地址段进行TraceRoute，并对其中的路由器地址（570 个）分别使用 DNS反向查询、UDP高端口探测、邻居-子网综合法进行多址综合，可以发现，邻居-子网综合法的别名率远远高于其他方法，虽然回包率比反向 DNS 查询法低，但是综合率远远低于其他3种方法，说明邻居-子网综合法相对其他方法更加有效。
4.结束语
目标网络探测中路由器多址综合问题是一个非常重要的问题。本文针对这个问题提出了邻居-子网综合法，相对其他方法实现更加简单，多址综合结果更加准确、完整、覆盖范围更广。
以后的工作除了对路由器多址综合问题继续深入研究外，还要针对目标地址集的选取问题、匿名路由器问题、路径变化问题等在路由器级拓扑发现过程中的难题进行研究，进一步加强路由器级拓扑发现的准确性、完整性和有效性。 [科]