高级检索

    链路约束的分布式网络监测模型

    A Distributed Network Monitoring Model with Link Constraint

    • 摘要: 分布式网络监测系统能够实时有效地收集网络性能数据,但收集过程受到链路延迟和路由跳数的约束.链路约束的分布式网络监测模型研究如何在链路约束下用最小的代价部署整个分布式网络监测系统;链路约束的演化网络监测模型研究在网络演化的情况下,如何用最小的更新代价重新部署监测系统使之满足链路约束.求取这两个模型的最优解的问题都是NP难的.通过指定权函数的形式,两个模型对应的最优化问题能够映射成带权的集合覆盖问题,采用贪婪策略能够得到近似比不超过ln n+1的近似算法,其中n是被监测节点的数目.通过仿真实验还讨论了如何选择恰当的链路延迟约束值.

       

      Abstract: Distributed network monitoring system could obtain up-to-date performance information of the network effectively. The monitoring and aggregating procedure require the establishment of reliable, low delay and low cost aggregating routes. Hence the aggregating procedure is constrained by the link delay and the round hops. Addressed in this paper are the problem of optimizing a distributed monitoring system and the problem of optimally upgrading the existing monitoring infrastructure as the network evolves. It is shown that both problems are NP hard, and could be mapped to the well-known weighted set cover problem by assigning the weight function. A greedy algorithm could be used to solve these problems with an approximation ratio ln n+1, where n is the number of monitored nodes. Furthermore, how to choose an appropriate link constraint value by simulation is discussed.

       

    /

    返回文章
    返回