基于端到端报文丢失的网络拓扑推测算法研究.doc

·· 通信学报 第28卷
第10期 李勇军等：基于端到端报文丢失的网络拓扑推测算法研究 ··

第28卷第10期 通信学报 Vol.28No.10
2007年10月 JournalonCommunications October2007

基于端到端报文丢失的网络拓扑推测算法研究
李勇军1,2,蔡皖东1,王伟1,田广利1
（1西北工业大学计算机学院,陕西西安710072;2北京大学计算机科学技术系，北京100871）
摘要：在分析现有网络拓扑推测算法的基础上，提出了一种基于端到端报文丢失性能的网络拓扑推测方法，该方法通过比较节点间的Hamming距离和节点接收到的报文数量推测网络拓扑，在推测拓扑过程中不需要网络内部节点的协助。通过理论比较和分析，证明该方法在推测精度上比现有的方法有显著的提高，最后利用仿真实验验证了该方法的有效性和准确性，推测精度比现有方法提高了20%。
关键词：网络拓扑推测；报文丢失率；Hamming距离
中图分类号：TP393.07文献标识码：A文章编号：1000-436X(2007)10-0085-07
Researchonnetworktopologyidentificationalgorithmbasedonend-to-endlossperformance
LIYong-jun1,2,CAIWan-dong1,WANGWei1,TIANGuang-li1
(1.SchoolofComputerScience,NorthwesternPolytechnicalUniversity,Xi’an710072,China;2.DepartmentofComputerScienceandTechnology,PekingUniversity,Beijing100871,China)
Abstract:Basedontheanalysisofexistingnetworktopologyidentificationalgorithms,animprovednetworktopologyidentificationmethodbasedonend-to-endlossperformancewasproposed.TheproposedalgorithmidentifiednetworktopologyusingHammingdistanceofthesiblingnodesandinferrednumberofreceivedprobepacketsatsiblingnodes.Theproposedalgorithmrequirednosupportfrominternalnodes.Thetheoreticanalysisandcomparisonshownthattheimprovedalgorithmcansignificantlyimprovetheinferenceaccuracy.Tovalidateitsaccuracyandefficiency,theproposedalgorithmwasimplementedinasimulatednetwork.Thesimulationresultshownthattheinferenceaccuracyisimprovedmorethan20%.
Keywords:networktopologyidentification;lossperformance;Hammingdistance

1引言
收稿日期：2006-10-23；修回日期：2007-07-04
网络拓扑对于网络管理和优化网络协议等具有重要意义，但现在要获取网络拓扑变得越来越困难，一方面是因为网络规模越来越大，结构也越来越复杂；另外一方面出于安全或者商业利益的考虑，许多单位不愿意与外界分享其内部的网络拓扑信息。为了克服上述问题，近年来出现了基于端到端测量的网络拓扑推测方法，根据端到端的性能测量值（如报文丢失、链路延时等）推测网络拓扑[1~3]，其核心思想是在给定一个源节点的多播树中，有相同路径的接收节点的报文丢失和链路延时具有相关性，优点在于测量和推测过程中不需要内部节点的协作。其中BHC（binaryHammingdistanceandhopcountbasedclassificationalgorithm）算法是一个具有代表性的算法，该算法无论是在推测精度还是计算复杂度方面都要优于其他同类算法[4]。
BHC算法根据测量的端到端报文丢失情况，计算节点之间的Hamming距离，并结合节点的层次信息，可以准确快速地推测出网络拓扑。但当网络中某些链路报文丢失较为严重时，该算法就显得力不从心了。为了解决BHC算法存在的问题，本文提出了一种新的网络拓扑推测算法HTIGT（Hammingdist