基于路由行为分析的网络拓扑测量目标采样.doc

·· 通信学报 第30卷
第4期 张宇等：基于路由行为分析的网络拓扑测量目标采样 ··

第30卷第4期 通信学报 Vol.30No.4
2009年4月 JournalonCommunications April2009

基于路由行为分析的网络拓扑测量目标采样
张宇，方滨兴，张宏莉
（哈尔滨工业大学计算机网络与信息安全技术研究中心，黑龙江哈尔滨150001）
摘要：鉴于当前网络拓扑测量实践中目标采样的不充分以及测量模型的失真问题，提出了一类基于路由行为分析的目标采样方法：1)作为基准的均匀随机采样，2)作为优化方法的最小覆盖采样，3)针对路径多样性的末跳采样，4)针对目的前缀多样性的二分采样。基于真实测量数据回放的实验表明，通常的“/24选1”随机采样丢失了一半的拓扑信息，其中，约10%源自路径多样性，其余源自目的前缀多样性；最小覆盖采样不仅对路由动态性是顽健的，而且长期上优于均匀随机采样。
关键词：网络拓扑测量；目标采样；路由行为；路由动态性
中图分类号：TP393文献标识码：A文章编号：1000-436X(2009)04-0125-05
Targetsamplingbasedonroutingbehavioranalysisinnetworktopologymeasurement
ZHANGYu,FANGBin-xing,ZHANGHong-li
(ResearchCenterofComputerNetworkandInformationSecurityTechnology,HarbinInstituteofTechnology,Harbin150001,China)
Abstract:Inordertoinvestigatetheinsufficiencyoftargetsamplingincurrentnetworktopologymeasurementpracticeandthedistortionofmeasurementmodels,asortoftargetsamplingmethodsbasedonroutingbehavioranalysiswerepresented,namely,theuniformrandomsamplingasabenchmarkmethod,theminimumcoversamplingasanoptimalmethod,thelast-hopsamplingforthepathdiversity,andthebisectionsamplingforthedestinationprefixdiversity.Experimentsbasedonrealmeasurementdatashowthatahalfoftopologyinformationcanbemissedinthetraditional‘1per/24’randomsampling,ofwhich10%ofmissedinformationiscausedbythepathdiversityandtherestiscausedbydestinationprefixdiversity.Theminimumcoversamplingisrobusttotheroutingdynamicsandperformsbetterthantheuniformrandomsamplingatthelong-termpractice.
Keywords:networktopologymeasurement;targetsampling;routingbehavior;routingdynamics

1引言
收稿日期：2008-11-10；修回日期：2009-01-15
基金项目：国家重点基础研究发展计划（“973”计划）基金资助项目（2007CB311101）；国家高技术研究发展计划（“863”计划）基金资助项目（2006AA01Z452）
FoundationItems:TheNationalBasicResearchProgramofChina(973Program)(2007CB311101);TheNationalHighTechnologyResearchandDevelopmentProgramofChina(863Program)(2006AA01Z452)
IP级网络拓扑测量通过收集监测点到目标集之间顺序相连路由器的路径信息，为了解网络基础设施状况以及认识网络结构性质提供了重要的基础数据[1~3]。测量完整性与有效性是研究的核心问题。为此，Barford等[4]分析了增加监测点和目标对于完整性的边际效用；Dall'Asta等[5]采用平均场近似建立了测量完整性模型。这2项工