论文部分内容阅读
随着IP网络应用日益膨胀,各种服务层出不穷。对网络管理者来说,需要了解各个节点之间的带宽信息,以支持可区分的服务。这些及时的带宽信息对于许多网管业务,如主动式和被动式的资源管理、流量工程、端到端的服务质量保证,显得尤为重要。特别是现代的网络管理系统注重于服务级、应用级的管理,带宽的测量过程需要更大的数据量和更高的数据采集频率。 根据是否发送探测包,IP网络带宽测量方法可分为被动测量和主动测量。被动测量不向网络发送探测包,而是监听网络中的IP报文来推测网络的带宽情况,但了解网络全局各链路带宽数值时,需要专门的统一时钟和数据收集机制。主动测量向网络发送探测包,通过对发送的实际业务量的测量来反映网络提供给用户的带宽参数,但这种方法可能因为设置过多的观测节点而增加网络的额外负担。 目前,网络流量的测量方法还只是针对特定感兴趣的链路、路径,人工合理地规划网络的观测节点,并在这些节点上安装特定的测量软件。这种方法难以扩展,不便于动态适应网络的变化。我们强调测量方法的关键是既要准确获取网络流量参数,又要尽量减少数据收集对实际网络传输数据造成的影响。基于此,本文主要研究带宽测量的监测节点的布置问题,对于主、被动测量不同的应用背景提出了不同的带宽测量模型,主要的创新点如下: 1、在被动带宽测量研究中,由于挖掘节点上的流量约束信息,可以把有效观测网络实际使用带宽的问题抽象为求给定图G的最小弱顶点覆盖集的问题,我们证明了最小弱顶点覆盖问题是NP完全的,同时将模型扩展为基于流划分的弱顶点覆盖问题,并对模型的误差做了分析。 2、由于弱顶点覆盖问题是NP难的,至今尚无多项式求解算法,退一步考虑,我们只好寻找模型的多项式时间内的近似解。为此我们设计了贪婪算法和原始对偶算法来求解该问题。算法的近似程度从2(lnd+1)提高到2,其中d是图中最大的顶点度。 3、被动带宽测量虽然能够实现对观察点网络行为的详尽了解,但在了解网络全局各链路带宽的数值时,需要专门的数据收集机制。因此如何既能减少数据收集过程对实际网络上传输数据的影响,又能保证全局视图对数据共享的要求是一个关键的问