@@传统测量与层析成像结合的网络拓扑识别方法研究

电子科技大学

硕士学位论文

传统测量与层析成像结合的网络拓扑识别方法研究

姓名：廖海亮

申请学位级别：硕士

专业：通信与信息系统

指导教师：胡光岷

20090501

摘要

摘要

传统的网络拓扑识别方法主要是基于各种协议的协作和中间节点反馈的信息来推测网络的拓扑，但是随着对网络安全性的要求越来越高，得到协议的协作和中间节点反馈的信息变得越来越困难。基于层析成像技术的网络拓扑识别可以在不借助路由协议或者中间节点协作的条件下，完成网络拓扑识别，但需要发送大量的探测包以计算链路的统计特性，计算过程也过于复杂。我们认为：传统网络拓扑识别方法要求大量的中间路由器配合，这在实际的大型网络中往往是难以办到的；基于网络层析成像的拓扑识别方法假设所有中间路由器均不协作，增大了测量工作的难度。在实际的网络中必然存在一些不协作节点，也必然存在一些可协作节点。因此本文提出了一类传统测量和层析成像结合的网络拓扑识别方法，能够根据待测网络中协作的中间节点反馈的拓扑信息，加快识别速度和减少发包量；对于不协作的部分，也能够动态的利用层析成像技术进行拓扑识别。

本文研究了基于协作的传统拓扑识别方法以及基于层析成像的网络拓扑识别方法，做了三个方面的研究工作：

（１）在拓扑识别的算法方面，改进并提出了一套新的基于层析成像的拓扑识别方法。该方法利用“三明治’’包作为探测手段，通过测量“三明治＂包中两个小包到达目的节点的时间差作为节点对的相似度以推测共享路径长度。该方法包括基于最小相似度的分层聚类算法以及叶节点的划分算法，叶节点的划分算法又根据所测拓扑的类型不同分为一般朴树的叶节点划分算法和二叉拓扑树的叶节点划分算法。该方法使得拓扑识别的计算复杂度大为降低，精确度也有所提升。

（２）在拓扑识别的测量方法方面，针对拓扑识别中普通“三明治＂包测量方法存在的问题，提出了ＴＴＬ可变的“三明治”包测量方法。普通“三明治’’包测量方法只能得到节点对的相似度，然后再利用这些相似度数据去推测节点对的共享路径长度，这样测得的共享路径长度的精度会受到相似度误差的影响。ＴＴＬ可变的“三明治＂包测量方法基于对同一拓扑树发送不同ＴＴＬ值的“三明治＂包所得相似度的比较，能够直接获得节点对共享路径准确的长度。该方法使得发包量减少到只有原来的１０％，拓扑识别精确度也得到了很大的提高。（３）结合算法和测量方法的改进，提出一个综合的解决方案，即传统

摘要

ｔｒａｃｅｒｏｕｔｅ探测方法和层析成像结合的网络拓扑识别方法。该方法利用ｔｒａｃｅｒｏｕｔｅ从被测网络的协作节点得到网络的部分拓扑信息，并利用初始拓扑构造算法得到不完整的初始拓扑，然后结合相应的层析成像方法，利用匿名节点处理算法对初始拓扑中不正确或不完整的部分进行识别，以得到最终拓扑。该方法不仅可以识别包含不协作节点的网络拓扑，而且进一步减少了发包量，拓扑识别的准确度也进一步提高。

本文通过ＮＳ２的仿真证明了这种结合传统测量的拓扑识别方法不仅在算法的复杂度有所降低，而且发送探测包的数量大大降低，拓扑识别的准确度也有较大的提升。关键词：网络拓扑识别，网络层析成像，分层聚类，ＴＴＬ，ｔｒａｃｅｒｏｕｔｅ

ＡＢＳＴＲＡ（Ｘ

ＡＢＳＴＲＡＣＴ

Ｔｒａｄｉｔｉｏｎａｌｍｅｔｈｏｄ

ｃｏｌｌａｂｏｒａｔｉｏｎｏｆｏｆｎｅｔｗｏｒｋｔｏｐｏｌｏｇｙｉｎｆｅｒｅｎｃｅｉｓｍａｉｎｌｙｂａｓｅｄｏｎｔｈｅｐｒｏｔｏｃｏｌｓａｎｄｉｎｆｏｒｍａｔｉｏｎｆｅｅｄｂａｃｋｂｙｔｈｅｔｏｕｔｅｒｓ．Ｈｏｗｅｖｅｒ，ｉｔ’Ｓｍｏｒｅａｎｄｍｏｒｅｄｉｆｆｉｃｕｌｔｔｏ

ｒｏｕｔｅｒｓｇｅｔｔｈｅｃｏｌｌａｂｏｒａｔｉｏｎｏｆｐｒｏｔｏｃｏｌｓａｎｄｉｎｆｏｒｍａｔｉｏｎｆｅｅｄｂａｃｋｂｙｔｈｅｄｕｅｔｏｔｈｅｄｅｍａｎｄｏｆｎｅｔｗｏｒｋｓｅｃｕｒｉｔｙ．ＮｅｔｗｏｒｋｔｏｐｏｌｏｇｙｉｎｆｅｒｅｎｃｅｂａｓｅｄｏｎｎｅｔｗｏｒｋｔｏｍｏｇｒａｐｈｙＣａｎｉｎｆｅｒｔｈｅｗｈｏｌｅｔｏｐｏｌｏｇｙｏｆｎｅｔｗｏｒｋｗｉｔｈｏｕｔｔｈｅｃｏｌｌａｂｏｒａｔｉｏｎｏｆｒｏｕｔｅｒｐｒｏｔｏｃｏｌｓａｎｄ

ｏｎｉｎｔｅｒｎａｌｎｏｄｅｓ．Ｈｏｗｅｖｅｒ，ｔｈｅｍｅｔｈｏｄｏｆｔｏｏｎｅｔｗｏｒｋｔｏｐｏｌｏｇｙｉｎｆｅｒｅｎｃｅｂａｓｅｄ

ｎｅｅｄ

ＩｎｔｏｍｏｇｒａｐｈｙｏＲｅｎｔａｋｅｓｍｕｃｈｔｉｍｅｉｎｃａｌｃｕｌａｔｉｎｇｂｅｃａｕｓｅｏｆｔｈｅｔｏｔｏｓｅｎｄａｌａｒｇｅｎｕｍｂｅｒｏｆｐｒｏｂｅｐａｃｋｅｔｓｃａｌｃｕｌａｔｅｔｈｅｓｔａｔｉｓｔｉｃａｌｃｈａｒａｃｔｅｒｉｓｔｉｃｓ．ｄｅｐｅｎｄｏｎｏｕｒｏｐｉｎｉｏｎｓ，ｔｒａｄｉｔｉｏｎａｌｍｅｔｈｏｄｓｏｆｎｅｔｗｏｒｋ

ｏｆｔｈｅｒｅｕｔｅｒｓ，ｗｈｉｃｈｉｓｏＲｅｎｔｏｐｏｌｏｇｙｉｎｆｅｒｅｎｃｅ

ａｓｓｕｍｅｔｈｅｆｅｅｄｂａｃｋｄｉｆｆｉｃｕｌｔｔｏｉｎｆｅｒｅｎｃｅａｐｐｌｙｉｎｔｈｅａｃｔｕａｌｌａｒｇｅ－ｓｃａｌｅｔｈａｔａｌｌｎｅｔｗｏｒｋｓ；ｔｏｍｏｇｒａｐｈｙｂａｓｅｄｔｏｐｏｌｏｇｙ

ｃｏｌｌａｂｏｒａｔｉｖｅ

ｔｈｉｓｐａｐｅｒｒｅｕｔｅｒｓａｒｅｕｎｃｏｏｐｅｒａｔｉｖｅ，ｗｈｉｃｈｍａｋｅｔｈｅｍｅａｓｕｒｉｎｇｗｏｒｋｍｕｃｈｍｏｒｅｄｉｆｆｉｃｕｌｔ．Ｔｈｅｒｅｒｏｕｔｅｒｓｂｕｔａｌｓｏａａｒｅｎｏｔｏｎｌｙｕｎｃｏｏｐｅｒａｔｉｖｅｒｏｕｔｅｒｓｉｎｔｈｅａｃｔｕａｌｎｅｔｗｏｒｋｓ．Ｔｈｅｒｅｆｏｒｅ，

ｎｏｔｏｎｌｙｂｅｉｎｔｒｏｄｕｃｅｓｍｅｔｈｏｄｏｆｔｏｐｏｌｏｇｙｉｎｆｅｒｅｎｃｅｃｏｍｂｍｅｔｈｅｔｒａｄｉｔｉｏｎａｌｍｅｔｈｏｄｓｏｆｔｏｐｏｌｏｇｙｉｎｆｅｒｅｎｃｅ

ａｂｌｅｔｏａｎｄｔｏｐｏｌｏｇｙｉｎｆｅｒｅｎｃｅｂａｓｅｄｏｎｔｏｍｏｇｒａｐｈｙ，ｗｈｉｃｈｓｐｅｅｄｕｐｔｈｅｐｒｏｃｅｓｓｏｆｔｏｐｏｌｏｇｙｉｎｆｅｒｅｎｃｅａｎｄｒｅｄｕｃｅｔｈｅｎｕｍｂｅｒｏｆｐａｃｋｅｔｓａｃｃｏｒｄｉｎｇｔｏｔｈｅ

ｂｅａｂｌｅｔｏｍａｋｅｆｅｅｄｂａｃｋｉｎｆｏｒｍａｔｉｏｎｆｒｏｍｔｈｅｃｏｏｒｄｉｎａｔｅｎｏｄｅｉｎｔｈｅｎｅｔｗｏｒｋｂｕｔａｌｓｏｕｓｅｏｆｔｏｍｏｇｒａｐｈｙｔｅｃｈｎｏｌｏｇｙｆｏｒｔｏｐｏｌｏｇｙｉｎｆｅｒｅｎｃｅｄｙｎａｍｉｃａｌｌｙｔｏｔｈｅｎｏｎ－ｃｏｌｌａｂｏｒａｔｉｖｅｐａｒｔｏｆｔｈｅｎｅｔｗｏｒｋ．

ｏｎＩｎｔｈｉｓｐａｐｅｒ，ｗｅｉｎｔｒｏｄｕｃｅｔｈｒｅｅａｓｐｅｃｔｓｏｆｒｅｓｅａｒｃｈｒｅｓｕｌｔｓｔｈｒｏｕｇｈｔｈｅｓｔｕｄｙ

ｔｒａｄｉｔｉｏｎａｌｍｅｔｈｏｄｓｏｆｔｏｐｏｌｏｇｙｉｎｆｅｒｅｎｃｅａｓｗｅｌｌａｓｔｏｍｏｇｒａｐｈｙ－ｂａｓｅｄｔｏｐｏｌｏｇｙ

ｅｘｉｓｔｅｄ

ｏｎｉｎｆｅｒｅｎｃｅ：（１）Ａｔｔｈｅａｓｐｅｃｔｏｆａｌｇｏｒｉｔｈｍｔｏｔｏｐｏｌｏｇｙｉｎｆｅｒｅｎｃｅ，ｗｅａｉｍｐｒｏｖｅｔｈｅｔｏｐｏｌｏｇｙｉｎｆｅｒｅｎｃｅｍｅｔｈｏｄｓａｎｄｉｎｔｒｏｄｕｃｅｎｅｗｍｅｔｈｏｄｏｆｔｏｐｏｌｏｇｙｉｎｆｅｒｅｎｃｅｂａｓｅｄ

ｔｏｍｏｇｒａｐｈｙｕｓｉｎｇ“ｓａｎｄｗｉｃｈ”ｐｒｏｂｅ，ｗｈｉｃｈｍｅａｓｕｒｅｔｈｅｄｉｆｆｅｒｅｎｃｅｏｆｔｈｅａｒｒｉｖｅｔｉｍｅｏｆｔｈｅｔｗｏｓｍａｌｌｐａｃｋｅｔｓｏｆｔｈｅ“ｓａｎｄｗｉｃｈ”ｐａｃｋｅｔ－ｇｒｏｕｐｉｎｏｒｄｅｒｔｏｉｎｆｅｒｔｈｅｌｅｎｇｔｈｏｆｔｈｅ

ｏｎｓｈａｒｅｄｐａｔｈ．Ｔｈｉｓｋｉｎｄｏｆｍｅｔｈｏｄｉｎｃｌｕｄｅｓｔｈｅｈｉｅｒａｒｃｈｉｃａｌｃｌｕｓｔｅｒｉｎｇａｌｇｏｒｉｔｈｍｂａｓｅｄ

ｔｈｅｓｍａｌｌｅｓｔｓｉｍｉｌａｒｉｔｙａｓｗｅｌｌａｓｔｈｅｄｉｖｉｓｉｏｎｏｆ１ｅａｆｎｏｄｅｓａｌｇｏｒｉｔｈｍ．ＴｈｅｄｉｖｉｓｉｏｎｏｆＩＩＩ

ｌｅａｆｎｏｄｅｓａｌｇｏｒｉｔｈｍＣａｌｌｂｅｄｉｖｉｄｅｄｉｎｔｏｄｉｖｉｓｉｏｎｏｆｌｅａｆｎｏｄｅｓａｌｇｏｒｉｔｈｍｆｏｒｇｅｎｅｒａｌｔｏｐｏｌｏｇｙｔｒｅｅａｎｄｄｉｖｉｓｉｏｎｏｆｌｅａｆｎｏｄｅｓａｌｇｏｒｉｔｈｍｆｏｒｂｉｎａｒｙ

ｔｈｅｔｙｐｅｏｆｔｏｐｏｌｏｇｙ．Ｔｈｉｓｍｅｔｈｏｄｔｏｐｏｌｏｇｙｔｒｅｅａｃｃｏｒｄｉｎｇｔｏｒｅｄｕｃｅｓｔｈｅｃｏｍｐｕｔａｔｉｏｎａｌｃｏｍｐｌｅｘｉｔｙａｎｄｉｍｐｒｏｖｅｓｔｈｅａｃｃｕｒａｃｙａｓｗｅｌｌ．

ａｓｐｅｃｔｏｆｍｅａｓｕｒｅｍｅｔｈｏｄ，ｗｅ（２）Ａｔｔｈｅ

ｂａｓｅｄｏｎｉｎｔｒｏｄｕｃｅｔｈｅｎｅｗ“ｓａｎｄｗｉｃｈ＇’ｐｒｏｂｅｃｏｉｎｌｎｏｎ“ｓａｎｄｗｉｃｈ＇’ｐｒｏｂｅ．Ｔｈｅ

ｕｓｉｎｇｔｈｅｓｉｍｉｌａｒｉｔｙＴＴＬｖａｒｉａｂｌｅｐａｃｋｅｔｔｏｓｏｌｖｅｔｈｅｐｒｏｂｌｅｍｏｆｌｅｎｇｔｈｏｆｔｈｅ

ｂｅｃｏｍｍｏｎ‘‘ｓａｎｄｗｉｃｈ＇’ｐｒｏｂｅｉｎｆｅｒｔｈｅｄａｔａ．Ｔｈｅａｃｃｕｒａｃｙｏｆｔｈｅｓｈａｒｅｄｐａｔｈｂｙｅｒｒｏｒｌｅｎｇｔｈｗｉｌｌ

ｏｎａｆｆｅｃｔｅｄｂｙｔｈｅｃａｎｏｆｔｈｅｓｉｍｉｌａｒｉｔｙｄａｔａ．Ｔｈｅ“ｓａｎｄｗｉｃｈ＇’ｐｒｏｂｅｂａｓｅｄ

ｓｈａｒｅｄｐａｔｈ

ｐｒｏｂｅ、析ｎｌｂｙＴＴＬｖａｒｉａｂｌｅｐａｃｋｅｔｏｂｔａｉｎｔｈｅｅｘａｃｔｌｅｎｇｔｈｏｆｔｈｅｂｙｃｏｍｐａｒｅｏｆｔｈｅｓｉｍｉｌａｒｉｔｉｅｓｗｈｉｃｈａｒｅｏｂｔａｉｎｅｄｓｅｎｄｉｎｇ‘‘ｓａｎｄｗｉｃｈ＇’ｔｏｏｎｌｙ１０％ｄｉｆｆｅｒｅｎｔ丌Ｌ．Ｔｈｉｓｍｅｔｈｏｄｒｅｄｕｃｅｓｔｈｅｎｕｍｂｅｒｏｆｐａｃｋｅｔｓ

ｃｏｍｐａｒｅｔｏｔｈｅｏｒｉｇｉｎａｌｎｕｍｂｅｒａｎｄｔｈｅａｃｃｕｒａｃｙｉｓａｌｓｏｇｒｅａｔｌｙｉｍｐｒｏｖｅｄ．

（３）Ｆｉｎａｌｌｙ，Ｗｅｐｒｏｐｏｓｅａｃｏｍｐｒｅｈｅｎｓｉｖｅ

ｗｉｔｈｓｏｌｕｔｉｏｎｂｙｔｈｅａｎｄｃｏｍｂｉｎａｔｉｏｎｏｆｔｈｅａｌｇｏｒｉｔｈｍｓｔｒａｄｉｔｉｏｎａｌｉｎｆｅｒｅｎｃｅｍｅｔｈｏｄｓｔｒａｃｅｒｏｕｔｅｉｍｐｒｏｖｅｄａｎｄ

ｍｅａｓｕｒｅｍｅｎｔ

ｔｏｐｏｌｏｇｉｃａｌ

ａｎｏｎｙｍｏｕｓｍｅｔｈｏｄｓ．Ｔｈｉｓｍｅｔｈｏｄｆｉｒｓｔｌｙｏｂｔａｉｎｓｓｏｍｅｏｆｔｈｅｔｏｐｏｌｏｇｙａｌｌｉｎｆｏｒｍａｔｉｏｎｉｎｉｔｉａｌｕｓｅｆｒｏｍｔｈｅｃｏｏｒｄｉｎａｔｅｎｏｄｅｓｉｎｔｈｅｎｅｔｗｏｒｋａｎｄｔｈｅｎｐｒｏｐｏｓｅｓｓｔｒｕｃｔｕｒｅｂｙｉｎｃｏｍｐｌｅｔｅｕｓｉｎｇｔｈｅｉｎｉｔｉａｌｔｏｐｏｌｏｇｙｃｏｎｓｔｒｕｃｔａｌｇｏｒｉｔｈｍ．Ｆｉｎａｌｌｙ，ｗｅｔｏｎｏｄｅｐｒｏｃｅｓｓａｌｇｏｒｉｔｈｍｉｄｅｎｔｉｆｙｔｈｅｉｎｃｏｒｒｅ：ｃｔｏｒｉｎｃｏｍｐｌｅｔｅｐａｒｔｏｆｔｈｅｉｎｉｔｉａｌｔｏｐｏｌｏｇｉｃａｌｓｔｒｕｃｔｕｒｅｔｏｇｅｔｔｈｅｆｉｎａｌｔｏｐｏｌｏｇｙ．ＴｈｉｓｍｅｔｈｏｄｆＢｒｔｈｅｒｒｅｄｕｃｅｓｔｈｅｎｕｍｂｅｒｏｆｐａｃｋｅｔｓａｎｄｆｕｒｔｈｅｒｉｍｐｒｏｖｅｓ

ＵｓｉｎｇＮＳ２ｓｉｍｕｌａｔｉｏｎｓｔｈｅｉｎｆｅｒｅｎｃｅａｃｃｕｒａｃｙ．ｗｅｈａｖｅｐｒｏｖｅｄｔｈａｔｔｈｅｃｏｍｂｉｎａｔｉｏｎ

ｔｏｍｏｇｒａｐｈｙｎｏｔｏｎｌｙｏｆｔｒａｄｉｔｉｏｎａｌｍｅｔｈｏｄｓａｎｄｔｏｐｏｌｏｇｙｉｎｆｅｒｅｎｃｅｂａｓｅｄｏｎｒｅｄｕｃｅｔｈｅｃｏｍｐｌｅｘｉｔｙ

ａｎｄｔｈｅｎｕｍｂｅｒｏｆｐａｃｋｅｔｓｔｏｂｅｓｅｎｄｂｕｔａｌｓｏｉｍｐｒｏｖｅｔｈｅｉｎｆｅｒｅｎｃｅａｃｃｕｒａｃｙｏｆｔｏｐｏｌｏｇｙ．

Ｋｅｙｗｏｒｄｓ：ｎｅｔｗｏｒｋｔｏｐｏｌｏｇｙｉｎｆｅｒｅｎｃｅ，ｎｅｔｗｏｒｋ

ＴＴＬ．ｔｒａｃｅｒｏｕｔｅｔｏｍｏｇｒａｐｈｙ，ｈｉｅｒａｒｃｈｉｃａｌｃｌｕｓｔｅｒｉｎｇ，

ＩＶ

图形目录

图形目录

图２．１网络拓扑识别的过程…………………………………………………………。７图２．２端到端测量网络………………………………………………………………．８图２．３物理拓扑及其逻辑抽象………………………………………………………．９图３一ｌ“三明治＂包发送示意图……………………………………………………１９图３－２中继设备的接收缓冲区和发送缓冲区………………………………………２０图３－３“三明治’’包组时间差变大原理解析……………………………………．．２１图３－４网络的真实拓扑……………………………………………………………２３图３－５第一层分类…………………………………………………………………．２３图３－６第二层分类…………………………………………………………………．２４图３－７最小相似度聚类算法流程图………………………………………………．２５图３—８叶节点划分算法流程图……………………………………………………２７图３－９二叉树的叶节点划分算法流程图…………………………………………２８图３－１０ｎｓ２的仿真过程……………………………………………………………２９图３－１１仿真采用的网络拓扑……………………………………………………。３ｌ图３－１２仿真拓扑图………………………………………………………………一３２图３－１３ｎｓ２中的“三明治’’包（１）…………………………………………………３２图３－１４ｎｓ２中的“三明治＂包（２）………：………………………………………．３３图３－１５节点的划分过程及拓扑树形成…………………………………………．．３６图３－１６网络重载情况下节点的划分过程………………………………………。３９图４－１ＩＰ数据报格式………………………………………………………………４０图４－２“三明治＂包发送过程……………………………………………………４２图４—３共享路径长度为３的拓扑树………………………………………………４３图４－４ＴＴＬ＝Ｉ的等价拓扑…………………………………………………………４３图４－５ＴＴＬ＝２的等价拓扑…………………………………………………………４４图４—６ＴＴＬ＝３等价拓扑与实际拓扑一致…………………………………………４４图４－７ＴＴＬ＝４等价拓扑与实际拓扑一致…………………………………………．４５图４－８仿真所用拓扑图……………………………………………………………４６图４－９大包在节点１被丢弃………………………………………………………．４６ＶＩｌ

图形目录

图４－１０节点对９－１０不同ＴＴＬ的相似度…………………………………………。４７图４－１１节点对９－５不同ＴＴＬ的相似度…………………………………………。４７图４－１２节点对９－６不同ＴＴＬ的相似度…………………………………………．．４８图４－１３节点对９－１１不同ＴＴＬ的相似度…………………………………………。４８图４－１４节点对１０－５不同ＴＴＬ的相似度…………………………………………４９图４－１５节点对１０－６不同ＴＴＬ的相似度…………………………………………４９图４－１６节点对６－１１不同ＴＴＬ的相似度…………………………………………５０图４一１７节点对６－８不同ＴＴＬ的相似度…………………………………………．．５０图４一１８节点对１１—１２不同ＴＴＬ的相似度………………………………………一５１图４—１９节点对１２－８不同ＴＴＬ的相似度…………………………………………５１图４—２０节点对不同ＴＴＬ值的相似度比较…………………………………………５２图５—１第一类或第二类匿名路由器带来的影响…………………………………．５６图５－２第三类匿名路由器带来的影响……………………………………………。５６图５－３初始拓扑树构造算法流程图………………………………………………５８图５－４匿名节点归并算法流程图…………………………………………………．５９图５－５仿真拓扑……………………………………………………………………．６０图５－６初始拓扑树…………………………………………………………………。６１图５－７进行归并的子拓扑树………………………………………………………．６２图５－８第三类匿名节点的识别……………………………………………………６２图５—９节点协作度和拓扑识别所需时间…………………………………………６３图５－１０节点协作度和发送的探测包数量…………………………………………６３

表格目录

表格目录

表３－１节点对的相似度数据………………………………………………．………３３表３－２叶节点划分结果……………………………………………………………．．３４表３—３最小相似度聚类结果………………………………………………………．３４表３—４叶节点划分结果（部分）…………………………………………………３５表３—５重载情况下节点对的相似度数据…………………………………………．３６表３－６重载下叶节点划分结果……………………………………………………。３７表３—７重载下的最小相似度聚类结果……………………………………………．３７表３－８重载下的叶节点划分结果（部分）………………………………………３８表５—１ｔｒａｃｅｒｏｕｔｅ探测结果………………………………………………………．６０ＩＸ

术语表

术语表

凇

ＢＤＴ

ＣＢＲＡｇｇｌｏｍｅｒａｔｉｖｅＬｉｋｅｌｉｈｏｏｄＴｒｅｅＢｉｎａｒｙＤｅｌａｙ－ｖａｒｉａｎｃｅＴｒｅｅ凝聚似然树二值延迟协方差树固定比特速率

计算机层析成像Ｃｏ娜ｔａｎｔＢｉｔＲａｔｅＣＴＣｏｍｐｍｅｒｉｓｅｄＴｏｍｏｇｒａｐｈｙ

ＤＴＤｅｌａｙ－ｖａｒｉａｎｃｅＴｒｅｅ延迟协方差树

快速分层拓扑结构估计

先进先出

高斯混合模型

分层拓扑结构估计

生存周期ＦＨＴＥＦａｓｔＨｉｅｒａｒｃｈｉｃａｌＴｏｐｏｌｏｇｙＥｓｔｉｍａｔｉｏｎＦｉｒｓｔ—ＩｎＦＩＦｏＦ豳ｔ．０ｕｔＭｉｘｔｕｒｅＭｏｄｅｌＧＭＭＨＴＥＧａｕｓｓｉａｎＨｉｅｒａｒｃｈｉｃａｌＴｏｐｏｌｏｇｙＥｓｔｉｍａｔｉｏｎＴＴＬＴｉｍｅ－Ｔｏ．Ｌｉｖｅ

ＩＣＭＰ

ｏＳＰＦＩｎｔｅｒｎｅｔＣｏｎｔｒｏｌＭｅｓｓａｇｅＰｒｏＰｅｌ．。因特网控制报文协议开放最短路径优先

简单网络管理协议ＯｐｅｎＳｈｏｒｔｅｓｔＰａｔｈＦｉｒｓｔＳＮＭＰＳｉｍｐｌｅＮｅｔｗｏｒｋＭａｎａｇｅｍｅｎｔＰｒｏｔｏｃｏｌ

Ｘ

主要符号表

主要符号表

Ｔ拓扑树

节点的集合

中间节点的集合

边的集合

叶节点集合ＶＶｉＥＶｒ

ｐａｔｈ（ｉｊ）

ａｎｃｅｓｔｏｒ（ｉ，ｊ）

ｃｏｍｍｏｎ＿ｐａｔｈ（ｉｊ）

ｌｅｎｇｔｈ（ｐａｔｈ）从ｉ节点到Ｊ节点的路径节点ｉ和节点Ｊ的最近公共祖先节点目标节点ｉ和节点ｊ的共享路径路径ｐａｔｈ的长度ＸＩ

独创性声明

本人声明所呈交的学位论文是本人在导师指导下进行的研究工作及取得的研究成果。据我所知，除了文中特别加以标注和致谢的地方外，论文中不包含其他人已经发表或撰写过的研究成果，也不包含为获得电子科技大学或其它教育机构的学位或证书而使用过的材料。与我一同工作的同志对本研究所做的任何贡献均已在论文中作了明确的说明并表示谢意。

签名：廖叠毫日期：枷７年石月ｚ日

关于论文使用授权的说明

本学位论文作者完全了解电子科技大学有关保留、使用学位论文的规定，有权保留并向国家有关部门或机构送交论文的复印件和磁盘，允许论文被查阅和借阅。本人授权电子科技大学可以将学位论文的全部或部分内容编入有关数据库进行检索，可以采用影印、缩印或扫描等复制手段保存、汇编学位论文。

（保密的学位论文在解密后应遵守此规定）

签名：套监导师签名：塑呲日期：２９。７年６月２日

第一章引言

第一章引言

１．．１网络拓扑识别研究背景

网络拓扑识别是利用各种测量手段对所关心网络的逻辑拓扑进行推测。随着网络与人们的生活联系越来越密切，不管是用户还是网络管理人员也越来越关注网络的性能特征，关注网络服务质量能有多大程度的保障。这一方面要求现代网络管理系统更完善地发展，更好地控制网络的行为。另一方面要求对网络性能参数进行精确地检测和方便地调控。为此，学者们开发了各式各样的网络测量系统以测量和推断网络性能参数的变化。网络拓扑识别是这些网络测量系统的主要基础，同时也是现代网络管理系统的重要组成部分，在现代计算机网络科学发展中具有十分重要的地位。

网络拓扑识别是指利用某种算法发现目标网络上的感兴趣的网络元素以及元素之间的连接关系，并以适当的形式把这种拓扑结构呈现出来。我们所关注的网络元素因我们的视角不同而有所不同。从这个角度上来说，我们可以把网络拓扑分为逻辑拓扑和物理拓扑。

传统的网络拓扑识别的方法都是基于协议的协作，根据中间节点反馈的路由信息来推测网络的拓扑结构。这种网络拓扑识别方法需要中间节点和路由协议的完全协作。传统的网络拓扑识别方法的好处是：拓扑识别速度快，准确度高，被测网络负载小。然而随着网络规模的不断扩大和对安全性的要求越来越高，要求节点间的协作变得越来越困难，因而传统网络拓扑识别方法的应用也变得越来越困难。

基于层析成像技术的网络拓扑识别方法是拓扑识别领域的新方法，近年来已经得到了学术界越来越多的关注和研究。相比传统拓扑识别方法，基于网络层析成像的拓扑识别方法只通过对网络端到端的测量来推测网络拓扑结构。因而基于层析成像方法最大的优势在于可以不需要中间节点的协作就能完成网络拓扑结构识别。然而基于层析成像的网络拓扑识别方法本身的缺点也非常明显：由于需要发送大量的探测包来获取网络的统计特性，因此发包本身就会给被测网络带来很大的负载；另一方面，由于测量误差的存在，该方法的算法设计和计算复杂度都

电子科技大学硕士学位论文

很高。

传统网络拓扑识别方法的缺陷是要求大量的中间节点配合以及相应的协议的支持，这在实际的大型网络中往往是难以办到的：基于网络层析成像的拓扑识别方法假设所有中间路由器均不协作，纯粹采用发送大量探测包的方法，增大了识别工作的难度。我们认为在实际的大规模网络测量问题中，要求大量的中问路由器协作是不现实的，假设所有中间节点均不协作也是没有必要的。在网络中必然存在一些不协作节点，也必然存在一些可协作节点。因此，本文提出了传统测量和层析成像结合的网络拓扑识别方法，利用中间节点所反馈的不完整的路由信息，配合基于网络层析成像的主动探测手段，来获得一个精确的网络拓扑结构。１．２网络拓扑识别研究现状

网络是一个很好的系统，它有着分工明确又协助良好的体系结构，来完成每一个信息的传递。就像需要给每一个城市绘制地图一样，从网络诞生的那一刻起，世界上就有许许多多的学者在研究如何快速而准确的得到一个网络的拓扑。总的来说，网络拓扑识别算法可分为两大类：基于协议支持的网络拓扑识别方法和基于网络层析成像技术的拓扑识别方法。

基于协议支持的网络拓扑识别方法假定所有的中间节点都是可协作的，这种方法研究网络中的协议并挖掘隐藏与这些协议中的网络拓扑信息。这类网络拓扑识别的方法最早由Ｒ．Ｓｉａｍｗａｌｌａ，Ｒ．Ｓｈａｒｍａ和Ｓ．Ｋｅｓｈａｖ提出【Ｉ】，利用ｐｉｎｇ，ｔｒａｃｅｒｏｕｔｅ以及ＤＮＳＺｏｎｅＴｒａｎｓｆｅｒ等技术来探测网络的拓扑。基于协议支持的网络拓扑识别技术主要是利用网络中的各种协议，首先通过向待测网络发送探测包来获得网络中的部分端节点和中间节点，然后获取这些节点之间的连接关系，最后把获取到的节点以及其连接关系构成网络拓扑。根据算法采用的协议的不同可以将基于协议支持的网络拓扑识别方法分为基于ＩＣＭＰ协议的方法和基于ＳＮＭＰ协议【２】【３】的方法。目前这类方法研究比较成熟，常用的几个方法包括：

（１）Ｐｉｎｇ与广播Ｐｉｎｇ

Ｐｉｎｇ操作主要用来检测目的主机是否存活在网络中，它采用异步方式发送和接收ＩＣＭＰ应答包。Ｐｉｎｇ通过一个存活的主机大约只需几十毫秒，一个Ｃ类网可在几秒钟内搜索完毕。但如果该主机关机或在ＩＰ层上不可达，则将耗费较长时间。广播Ｐｉｎｇ是将ＩＣＭＰ包发向整个子网，但这种并发发送会增加网络流，甚至会引２

第一章引言

起网络拥塞而且许多子网并不支持此操作。

（２）ｔｒａｃｅｒｏｕｔｅ

可以探索ＩＰ数据报从一台主机发送到另一台目的主机所经过的全部路径。ＩＰ包首部有个ＴＴＬ字段（生存周期）开始信源发送一个ＴＴＬ值为１的ＵＤＰ报文，第一个路由器收到此报文后，将ＴＴＬ值减ｌ为０，便丢弃此报文，同时发回一个ＩＣＭＰ超时错报文给信源。这样信源得到第一个路由器信息。然后信源第二次发ＩＰ包时，增加ＴＴＬ值为２，这样每重发一次时，ＴＴＬ值增ｌ，接收报文的路由器先将ＴＴＬ值减１，若ＴＴＬ值不为Ｏ，则继续向路由器的下一跳转发；若值为Ｏ，便丢弃该报文，并向源主机发送ＩＣＭＰ超时应答报文，源主机便记下该路由器信息，在到达最终目的主机时，返回信源一个ＩＣＭＰ端口不可达报文。以此逐步探索可得到域内全部路由器拓扑信息。

（３）ＤＮＳ的Ｚｏｎｅｔｒａｎｓｆｅｒ

ＩＰ网络中每个节点有唯一的ＩＰ地址，ＤＮＳ中包含有每个主机名字与ＩＰ地址转换表，Ｚｏｎｅｔｒａｎｓｆｅｒ［４】命令可以很快地发现域内主机和其它网络设备的名字，通常它与广播Ｐｉｎｇ或Ｔｒａｃｅｒｏｕｔｅ工具结合使用，搜索子网内的主机和设备或作为其它发现算法的起点。这种技术简单快捷，但是出于安全考虑，有些ＤＮＳ服务器并不提供这种工具。而且ＤＮＳ数据库存储数据是静态的，它不能随时更新，所以信息有时并不准确。

网络拓扑识别的层析成像方法假定所有中间节点都是不协作的，通过发送端到端的探测包，收集并分析探测包的统计特征（如时间差的平均值，方差，以及丢包率等），推测网络拓扑。Ｒａｔｎａｓａｍｙ［５】和Ｄｕｆｆｉｅｌｄ［６】等人在这种方法的研究上面做出了先驱工作。他们主要识别网络的逻辑拓扑。网络的逻辑拓扑结构是只反映不同路径的节点的物理拓扑的一种抽象。换句话说，一个只有单个入口和出口的节点被抽象成连接相邻节点的链路。通过由源节点向目的节点端到端的发送探测包计算在共享链路上的丢包率。他们利用向节点对广播发送多包组的方法收集共享链路的丢包率信息，利用ＤＢＴ算法

ｃｌａｓｓｉｆｉｃａｔｉｏｎ（ｄｅｔｅｒｍｉｎｉｓｔｉｃｂｉｎａｒｙｔｒｅｅａｌｇｏｒｉｔｈｍ）实现二元逻辑状拓扑的识别ｒ７１。这个收敛算法选择一个在共享链路上丢包最严重的节点对，然后将它们连接到一个新的父节点。然后这个父节点将作为叶节点来代替原始的叶节点。两条新加的链路丢包也将重新计算。这个过程不断的迭代只到最后只有一个叶节点。目前所有的收敛算法都和ＤＢＴ采用的方法类似。ＤＢＴ算法同样被用来利用多包组时延等测量度量的拓扑识别。

电子科技大学硕士学位论文

Ｃａｓｔｒｏ［８】等人在单播网络测量方面提出很大改进，他们提出了一种利用共享链路队列延迟的Ｓａｎｄｗｉｃｈ探测方法，Ｓａｎｄｗｉｃｈ包由中间的一个大包和两个小包组成，大包和小包的目的节点不同。第二个小包在他们分开之前总是在队列中排在大包后面。这个链路测量等同于共享链路上的队列延迟。Ｃａｓｔｒｏ还提出ＡＬＴ算法

【９】（ＡｇｇｌｏｍｅｒａｔｉｖｅＴｒｅｅＡｌｇｏｒｉｔｈｍ）实现拓扑重构，将ＤＢＴ进行修改以适应测量值

ｄｅｎｓｉｔｙ在概率密度函数（ｐｒｏｂａｂｉｌｉｔｙｆｕｎｃｔｉｏｎ）上的分布。为使此方法不用

设定门限并适用于一般树结构，Ｃａｓｔｒｏ等人继而提出了反转跳马尔科夫链蒙特卡洛（ＲｅｖｅｒｓｉｂｌｅＪｕｍｐＭａｒｋｏｖＣｈａｉｎＭｏｎｔｅＣａｒｌｏ）算法进行最大似然估计的拓扑识别【８】，通过插入和删除节点建立一个侯选树，能够得到最大似然的候选树将作为估计的结果。

Ｍｅｎｇ—ＦｕＳｈｉｈ等人通过建立有限混合模型【１０】获得“Ｓａｎｄｗｉｃｈ’’包对均值的时延差分布，进而采用图聚类【ｌｌ】的方法获得网络拓扑结构。不同于以前的用启发式（ｈｅｕｒｉｓｔｉｃ）或蒙特卡罗方法（Ｍｏｎｔｅ—Ｃａｒｌｏ）先估计一个二叉树然后扩充为普通树，他们的方法直接估计一个普通树。方法的核心是把问题抽象成一个基于节点对相似度测量的叶节点分层聚类问题。中间的每个节点代表了一个特定的聚类团，这个聚类团里的叶节点有一个共同的祖先节点。并将在同一个类（ｃｌｕｓｔｅｒ）里的节点称为类中（ｉｎｔｒａ－ｃｌｕｓｔｅｒ），将不再同一个类的节点称为类间（ｉｎｔｅｒ—ｃｌｕｓｔｅｒ）。一对叶节点的相似度可以用和共享路径（从根节点到两个叶节点最近代共同的祖先节点的路径）相关联的单调函数表示。任何可以准确估计不同相似度度量的方法都可以用在这里。有三种不同的端到端的相似度度量方法：使用三明治包测量的队列延迟（ｑｕｅｕｉｎｇｄｅｌａｙ），使用背靠背包（ｐａｃｋｅｔｐａｉｒｓ）的延迟的方差（ｄｅｌａｙｖａｒｉａｎｃｅ）和使用背靠背的丢包率（１０ｓｓｒａｔｅ）。修改节点对相似模型引入每个节点对最近的祖先节点对先验分布（ｐｒｉｏｒｄｉｓｔｒｉｂｕｔｉｏｎ）。推出一个有限混合模型，当中每个混合成份对应单源树中的一个中间节点。对由中间节点和中间节点子节点分割的后代叶节点，混合模型中有最小均值的混合成份对应类间（ｉｎｔｅｒ—ｃｌｕｓｔｅｒ）的叶节点对。将这个成份叫做类间成份（ｉｎｔｅｒ—ｃｌｕｓｔｅｒｃｏｍｐｏｎｅｎｔ）。为了定义一个分类的相似度将每个类中的叶节点分为类间对（ｉｎｔｅｒ—ｃｌｕｓｔｅｒｐａｉｒｓ）和类中对（ｉｎｔｒａ－ｃｌｕｓｔｅｒｐａｉｒｓ）等组合。这个相似度表示为类间相似度和类中相似度的乘积。每个类中相似度符合有限混合模型，类间相似度由类间成份决定。

相对于传统的拓扑识别方法，网络拓扑识别的层析成像方法存在的主要问题４

第一章引言

是：由于假设中间所有路由器节点均不协作，造成探测包发送数量过多、求解不稳定、多解性强等缺陷，严重影响了方法的实用性。

１．３本文的研究内容与创新点

本文的研究内容是网络拓扑结构的识别算法，包括基于协议支持的网络拓扑识别算法和基于网络层析成像技术的拓扑识别算法。本文的研究重点放在基于网络层析成像技术的拓扑识别算法上面。

本文的研究内容包括以下几点：

第一，研究了基于传统测量的网络拓扑识别方法。ｔｒａｃｅｒｏｕｔｅ是基于传统测量的网络拓扑识别方法中最典型的方法，如果待测网络上存在一些不协作的节点——匿名路由器，那么基于ｔｒａｃｅｒｏｕｔｅ的网络拓扑识别方法在识别这些节点方面将遇到很大的困难。本文着重研究了匿名路由器给网络拓扑识别带来的影响以及如何解决基于ｔｒａｃｅｒｏｕｔｅ的网络拓扑识别方法在遇到匿名路由器时面临的困境。

第二，研究了基于网络层析成像技术的网络拓扑识别方法，包括了拓扑识别方法的算法以及测量方法的研究。在算法方面，本文研究了在单播网络上利用探测包的时延特性以及丢包率特性推测网络拓扑的算法。在测量方法方面，本文着重研究了“三明治＂包探测技术以及如何将其更好的应用于网络拓扑识别的算法中。

本文的研究工作及创新点包括以下几点：

第一，在拓扑识别算法方面，本文研究了前人利用网络层析成像的探测方法以及利用图聚类算法来进行网络拓扑识别的技术，提出一系列改进的算法来实现利用最小相似度分层聚类的网络拓扑识别方法。其核心思想包括：（１）分层次的节点划分，即算法是一个递归的节点划分算法，只针对当前树的分支节点对叶节点进行初步的划分，然后再对每个划分构成的树递归调用该算法进行划分。（２）最小相似度聚类算法，这个算法根据类内部离散程度变化的思想，用于得到具有最小相似度集合。

第二，在拓扑识别的测量方法方面，针对拓扑识别中普通“三明治＂包测量方法存在的问题，提出了ＴＴＬ可变的“三明治＂包测量方法。普通“三明治’’包测量方法只能得到节点对的相似度，然后再利用这些相似度数据去推测节点对的共享路径长度，这样测得的共享路径长度的精度会受到相似度误差的影响。ＴＴＬ可

电子科技大学硕士学位论文

变的“三明治一包测量方法基于对同一拓扑树发送不同ＴＴＬ值的“三明治’’包所得相似度的比较，能够直接获得节点对共享路径准确的长度。具体方法是：设置“三明治＂包中大包的ＴＴＬ值，从ＴＴＬ＝Ｉ开始，依次向目标节点对发送大包ＴＴＬ值以１为单位依次递增的“三明治＂包，比较不同ＴＴＬ值下的相似度，以得到一个精确的共享链路层次数。该方法使得发包量减少到只有原来的１００，６，拓扑识别精确度也得到了很大的提高。

第三，结合算法和测量方法的改进，提出一个综合的解决方案，即传统ｔｒａｃｅｒｏｕｔｅ探测方法和层析成像结合的网络拓扑识别方法。该方法利用ｔｒａｃｅｒｏｕｔｅ从被测网络的协作节点得到网络的部分拓扑信息，并利用初始拓扑构造算法得到不完整的初始拓扑，然后结合相应的层析成像方法，利用匿名节点处理算法对初始拓扑中不正确或不完整的部分进行识别，以得到最终拓扑。该方法不仅可以识别包含不协作节点的网络拓扑，而且进一步减少了发包量，拓扑识别的准确度也进一步提高。

１．４论文结构

论文共分六章，整体结构与章节安排如下：

第一章概述了网络拓扑识别的研究背景，简单介绍了网络拓扑识别的研究现状，概括了论文的主要研究内容和创新之处。

第二章具体的介绍网络拓扑识别的各种方法以及其面临的困难。着重介绍网络层析成像技术和一些基于网络层析成像技术的拓扑识别方法。

第三章详细介绍利用“三明治”包的网络拓扑识别方法，包括最小相似度分层聚类算法以及叶节点划分算法。并对这个方法进行了ＮＳ２的仿真以及对仿真结果进行分析。

第四章详细介绍ＴＴＬ值可变的“三明治”包探测法以及这个方法给网络拓扑识别带来的好处，并对这个方法的仿真结果进行分析。

第五章详细介绍一个综合的解决方案，即传统ｔｒａｃｅｒｏｕｔｅ探测方法和层析成像结合的网络拓扑识别方法，并对这个方法的仿真结果进行分析。

第六章是全文的总结，并指出了未来的研究方向。

第二章网络层析成像技术综述

第二章网络拓扑识别技术综述

２．１网络拓扑识别的研究

２．１．１网络拓扑识别的研究内容

网络拓扑识别是指利用某种探测手段和算法发现并识别目标网络上的感兴趣的网络元素以及元素之间的连接关系，并以适当的形式把这种拓扑结构呈现出来。网络拓扑识别问题可以形式化的描述为：

Ｔ＝（Ｖ，Ｅ），Ｖ为树的节点集合，Ｖ三｛ｖｏ）ｕｖｒｕＶｉ，其中Ｖｒ为叶节点集合，Ｖｒ＝｛Ｖ１，ｖ２，…，ｖＮ｝，ｌＷ州；Ｖｉ为中间节点集合，假设ＩＶｉＩ＿ｋ，Ｖｉ＝｛Ｒ１，Ｒ２，．．．，Ｒｋ｝，ｋ为中间节点的个数，是待估计的参数。我们要求的是中间节点集合Ｖｉ以及边集Ｅ。

本文所研究的网络拓扑识别指的是给定一个源节点和多个目标节点的网络，网络内部的节点和连接关系未知。通过相应的测量手段以及推测算法把未知的拓扑结构推测出来。图２－１形象的描述了这个过程。

／

一．，一‘一．／

图２－１网络拓扑识别的过程

２．１．２端到端的测量网络

所谓端到端的测量网络是指对目标网络拓扑识别的测量形式。端到端的测量７

电子科技大学硕士学位论文

指的是发送探测包和接收探测包都是在端节点上进行。端到端的测量建立在逻辑拓扑的基础之上，逻辑拓扑是区别于物理拓扑而言，物理拓扑指的是网络中的物理节点存在的物理结构。其节点代表了网络中的中继节点和终端，物理拓扑的边代表了这两个物理节点是直接相连的。

而逻辑拓扑是对拓扑识别有意义的拓扑，在物理拓扑中，只有存在分支的节点才是逻辑拓扑中的节点，因为没有分支的节点对于逻辑拓扑没有意义。本文所关注的逻辑拓扑是单源节点多目标节点的，也就是说，发送探测包的节点只有一个，并且是端节点，而接收探测包的可以有很多个目标节点。这种单源多目标的端到端测量网络如图２－２所示。

目标节点

图２—２端到端测量网络

２．１．３网络拓扑识别的框架结构

首先要确定网络拓扑的框架结构，即实际物理网络拓扑的抽象。对以网络拓扑的识别来说，只有有分支的节点才是网络拓扑识别关心的节点，因为对于只有一个入端口和一个出端口的中问节点，其存在与否对于网络拓扑并无影响，因为

第二章网络层析成像技术综述

所有经过这个节点的报文必定是从其中一个端口进入从另外一个端口发出。在本文中，所关注的拓扑是在测量中保持不变并将其抽象为树形的逻辑拓扑图。它的节点可以是计算机或者任何中继设备。图２—３说明了一个网络的物理拓扑以及其逻辑抽象的关系。

图２－３物理拓扑及其逻辑抽象

２．２基于协议支持的网络拓扑识别

２．２．１基于ＩＣＭＰ协议的网络拓扑识别

基于ＩＣＭＰ协议的网络拓扑识别方法的目标就是从网络上广泛运行的ＴＣＰ／ＩＰ协议族中的ＩＣＭＰ协议来挖掘拓扑信息。网络拓扑识别算法主要解决两个问题，一是通过向待测网络发送探测包来获得网络中的部分端节点和中间节点，在ＩＰ网络中就是发现待测子网的地址空间，进而获得待测子网中活动的路由器的接口地址以及目的主机的地址，二是发现各路由器之间的连接关系。

基于ＩＣＭＰ协议的网络拓扑识别方法就是利用ｔｒａｃｅｒｏｕｔｅ工具【１２】来探测源节点到待测节点间的路径。在ＩＰ协议设计中，为了防止选路回路造成数据报无限制地传输，在ＩＰ头部中加入了ＴＴＬ（ＴｉｍｅＴｏＬｉｖｅ）字段，每经过一个路由器，该字段的值减１，如果路由器发现该值递减为Ｏ，则丢弃相应数据报，并向发送数据报的源端发送ＩＣＭＰ超时报文。在这个ＩＣＭＰ超时报文中携带了丢弃该报文的路由器９

电子科技大学硕士学位论文

的地址，这样一来我们便能获取中间路由器的信息。Ｔｒａｃｅｒｏｕｔｅ就是利用这个协议特性，从Ｔ，Ｉ＇Ｌ＝１开始，依次向目标节点发送ＴＴＬ值以１为单位依次递增的数据报，每次接收到超时报文就提取该报文的源地址（路由器的地址），最终得到的地址序列就是从探测源节点到目标节点的路径中所经过的路由器序列，也就是在网络层上得到了到达目标的路径。ｔｒａｃｅｒｏｕｔｅ工具可以发现探针在某次测量中所经过的精确途径，但这种工具需要向待测子网主动发送探测报文，这些探测报文有时未必能到达目的地，也可能被中间节点过滤掉。同时，ｔｒａｃｅｒｏｕｔｅ发送的探针部分占用了网络带宽，且造成一定的通信开销。尽管ｔｒａｃｅｒｏｕｔｅ方法具有一些不足和缺陷，但对于规模不大的子网上的路径探测仍不失为一种有效的工具。

这类算法的另一个重要的工作就是发现待测网络中可向之发送ｔｒａｃｅｒｏｕｔｅ探测报文的目标节点的地址。获取ｔｒａｃｅｒｏｕｔｅ探测报文的目标节点的地址的基本方法是先得到待测网络的网络地址以及子网掩码，然后根据地址分配的连续性依次向该网络地址及其子网掩码下的所有可能地址发送ｐｉｎｇ报文，以探测这些节点是否存在从而获得待测网络内所有目标节点，以作为ｔｒａｃｅｒｏｕｔｅ目标节点。由于ｐｉｎｇ对不存在的目标节点探测耗时较大的特性，这种方法运行速度较慢，很难扩展到更大规模的网络中，特别是对那些子网内活动地址分布稀疏的子网尤为如此。为此，学者们尝试了许多其他的解决方案。如：利用ＤＮＳ

某个域内的某些地址，以达到加快探测速度的目的。Ｚｏｎｅｔｒａｎｓｆｅｒ获取

２．２．２基于ＳＮＭＰ协议的网络拓扑识别

ＳＮＭＰ（ＳｉｍｐｌｅＮｅｔｗｏｒｋＭａｎａｇｅｍｅｎｔＰｒｏｔｏｃ０１）是在ＩＰ网络中最为常用的网络

ＥｎｇｉｎｅｅｒｉｎｇＴａｓｋ管理协议。ＳＮＭＰ首先是由Ｉｎｔｅｒｎｅｔ工程任务组织（Ｉｎｔｅｒｎｅｔ

Ｆｏｒｃｅ）（ＩＥＴＦ）的研究小组为了解决Ｉｎｔｅｒｎｅｔ上的路由器管理问题而提出的。ＳＮＭＰ被设计成与协议无关，它可以在ＩＰ，ＩＰＸ，ＡｐｐｌｅＴａｌｋ，ＯＳＩ以及其他用到的传输协议上被使用。ＳＮＭＰ是一系列协议组和规范，它们提供了一种从网络上的设备中收集网络管理信息的方法。ＳＮＭＰ也为设备向网络管理工作站报告问题和错误提供了一种方法。设备的管理者收集这些信息并记录在管理信息库（ＭＩＢ）中。这些信息报告设备的特性、数据吞吐量、通信超载和错误等。ＭＩＢ有公共的格式，所以来自多个厂商的ＳＮＭＰ管理工具可以收集ＭＩＢ信息，在管理控制台上呈现给系统管理员。

基于ＳＮＭＰ协议的网络拓扑识别方法【１３】【１４】主要是利用ＳＮＭＰ协议的管理信息数ｌＯ

本文来源：https://www.bwwdw.com/article/lde1.html