随着网络在社会、经济、生活等各个方面重要性的不断提升,越来越多地研究机构和科研人员开始从事网络拓扑结构方面的研究。网络拓扑检测是将检测到的网络设备及其之间的动态连接关系用图形的方式直观地显示出来的技术,其中可以加入各种有价值的网络属性,如流量、带宽、延迟等等,使网络管理和研究人员能够从宏观上掌握整个网络的结构。由于网络的规模可能十分庞大,而且处于快速增长和随时变化之中,通过人工进行网络拓扑的检测工作是不现实的。拓扑检测的目标是要在尽可能少地影响网络本身运行的情况下自动发现网络的拓扑结构,具体有两大要求： 高效性：尽可能快地检测网络的拓扑结构； 完整性：尽可能地发现网络中的所有设备及其之间的连接关系。 快速而准确地检测网络的拓扑结构,无论对于各种实际的网络应用,还是网络相关的理论研究,都有着很广阔的需求和应用前景。尽管目前已经有一些拓扑检测系统,例如Skitter项目,正在运行已获取Internet的拓扑结构,但这些系统通常需要数月甚至数年的运行才能完成整个网络的拓扑检测,而且很少有研究机构和科研人员专门对拓扑检测系统算法的效率进行评估和研究。目前随着无线网络的不断普及,对网络拓扑检测技术效率上的要求也越来越高,因此专门针对效率方面的研究是非常重要和有价值的。 本论文专注于网络拓扑检测技术效率方面的研究,为了有效地提高网络检测的效率,本论文对传统网络拓扑检测算法的效率进行了试验分析和评估,在分析了传统网络拓扑检测算法的实现之后,认识到该算法效率较低的原因在于其有很高的拓扑检测冗余度,从而导致大量重复和无效的探测。为了有效地降低这种拓扑检测冗余度来提高拓扑检测算法的效率,本论文利用基本的网络探测工具Traceroute和网络拓扑的树状特征设计和实现了BacktraceTree算法,该算法对整个网络进行回溯式探测,同时根据探测目的地址是否有响应对其进行分类探测,从而有效地提高了网络拓扑检测的效率。论文最后的分析结果表明,BacktraceTree算法的效率是传统网络拓扑检测算法的3-4倍,同时能够保证算法的覆盖率在95％以上。