带宽延迟约束的层次化网络监测模型

如何既准确获取监测数据,又减少监测过程对实际网络传输数据的影响是网络研究的一个根本问题。该文提出了层次化网络测量模型,强调数据聚集过程的传输延迟和监测数据流量占用链路的带宽都小于预设数值同时,尽量追求聚集节点数目最小化。求解该模型的问题是NP难的,在节点间路由唯一的情况下,该文设计的近似算法的近似程度为lnd+1,其中d是监测节点的数量。

The Hierarchical Network Monitoring Model with Bounded Bandwidth and Delay Constraints

Designing optimal monitoring infrastructure is a key step for network monitoring. In this paper the problem of optimizing a hierarchical monitoring system is to reduce the cost of deployment of the monitoring infrastructure by identifying a minimum aggregating set subject to bandwidth constraints on the individual links and delay constraint on the aggregating path. The problem is NP-hard and approximation algorithm is proposed with performance guarantee ln d + 1 under unique aggregating route, where d is the number of monitoring object.