网络流量的有效测量方法分析

被引：28

作者：

刘湘辉

殷建平

唐乐乐

赵建民

机构：

[1] 国防科学技术大学计算机学院

[2] 浙江师范大学计算机学院湖南长沙

[3] 浙江金华

来源：

软件学报 | 2003年 / 02期

关键词：

弱顶点覆盖; NP难的; 近似算法; 流守恒;

D O I：

10.13328/j.cnki.jos.2003.02.019

中图分类号：

TP393.06 [];

学科分类号：

081201 ; 1201 ;

摘要：

把网络流量的有效测量问题抽象为求给定图G=(V,E)的最小弱顶点覆盖集的问题.给出了一个求最小弱顶点覆盖集的近似算法,并证明了该算法具有比界2(lnd+1),其中d是图G中顶点的最大度.指出了该算法的时间复杂性为O(|V|2).

引用

页码：300 / 304

页数：5

共 6 条

[1]

Measuring bandwidth.In:Proceedings of theIEEE INFOCOM99. LaiK,BakerM. NewYork . 1999

[2]

Efficiently monitoring bandwidth and latency in IP network. Breibart Y,Chan CY,Carofalakis M,Rastogi R,Silberschatz A. . 2000

[3]

Using pathchar to estimate internet link characteristics. DowneyAB. Proceedings of theACM SIGCOMM99Conference onApplications,Technology,Architectures andProtocals forComputerCommunications . 1999

[4]

On the placement of internet instrumentation. JaminS,JinC,JinY,RazD,ShavittY,ZhangL. Proceedings of theIEEE INFOCOM 2000 . 2000

[5]

Measurement and analysis ofIP network usage and behavior. CceresR,DuffieldNG,FeldmanA,FriedmannJ,GreenergA,GreerR,JohnsonT,KalmanekC,KrishnamurthyB,LavelleD,MishraPP,RamakrishnanKK,RexfordJ,TrueF,van derMerweJE. IEEE Communications Magazine . 2000

[6]

← 1 →