基于主动和被动测量的网络测量技术、模型和算法研究

《基于主动和被动测量的网络测量技术、模型和算法研究》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、分类导UDC工学博士学位论文学号——鳖Q§!墼§密教——⋯垒—最一基于主动和被动测量的网络测量技术、模型和算法研究耩士生烂名攀辩专监鞒究寅离指导教烬鉴盎垩盐簋亟鲞棠量羲盎鼓筵蠡毯鏊羹彗熬建垩．整蛰。国防科学技术大学研究生院二oo五年十月里堕型兰茎查查兰堑壅生堕兰焦笙茎Itisimportantthatthenumberofplacedmonitorsbekeptassmallaspossible，sinceitcouldnotonlyreducethedeploymentcostandmaintenancec

2、ost，butalsoreducetheextratrafficsandbandwidthconsumptionforpollingnetworkmanagementdata．Exploitingtheflow-conservationlawcouldreducedeploymentcostandpollingloadwithreducingthenumberofmonitors．Hence，wecoulddevelopalow—overheadlink-bandwidthpassivemonitoringm

3、odelbyusingtheflow-conservationlaw．Theproblemofefficientlymonitoringlink-bandwidthbasedonflow．conservationcouldbereducedtotheweakvertexcovcrproblem，whichisNP-hard．Inthispaper,wedemonstrateanapproximationpreservingreductionfromthevertexcoverproblemtotheweakv

4、ertexcoverproblem．Duetothisreduction，itfollowsthatitisverydifficulttogetallapproximationalgorithmwithconstantapproximationratiolowerthan2fortheweakvertexcoverproblem．Thereexistsomeapproximationalgorithmwithapproximationratio2byusingtheprimal-dualmethod．Weco

5、uldalsousethesealgorithmstosolvetheweakvertexproblemwithblackoutvertices．(3)TheoptimizationproblemofdistributednetworkpollinginfrastructurewithlinkconstraintanditsapproximationalgorithmsForobtainingup-to-datenetworkperformanceinformation，theaggregatingproce

6、durerequirestheestablishmentofreliable，lowdelayandlowcostaggregatingroutes．Hencetheaggregatingprocedureisconstrainedbythelinkdelayandtheroundhops．TheproblemofoptimizingadistributedpollinginfrastructurewithlinkconstraintisNPhard．Itcouldbemappedtothewell—know

7、nweightedsetcoverproblem．Agreedyalgorithmcouldbeusedtosolvethisproblemwithanapproximationratio1+Inl矿l，whereVisthenumberofmonitoringnodes．Itisimportanttochooseanappropriatelinkconstraintvaluesincethenumberofmonitorsisrelatedtothelinkconstraintvalue．Itisdiscu

8、ssedhowtochooseanappropriatelinkconstraintvaluebysimulation．(4)Theoptimizationproblemofdistributedmonitoringmodelwithlinkcons廿aintforevolvingnetworksanditsapproximationalgorithmsWhenthenetworkchangesor