【Wspruce:一种改进的可用带宽测量方法】频率带宽测量方法

　　摘要:可用带宽是反映网络状态的主要参数，对其准确的估计与测量是流量工程和网络监测等必须解决的问题，但对它的实际测量存在许多困难。针对Spruce可用带宽测量方法存在收敛慢、开销大的问题，提出了一种Spruce可用带宽测量的改进方法（Wspruce）。该方法利用隐马尔可夫模型（HMM）的序列预测特性，可以对可用带宽做出较为准确的分析。实际测量结果表明，该方法在可用带宽测量中估算速度更快，开销更低。
　　
　　关键词:可用带宽；流量工程；网络监测；隐马尔可夫模型；序列预测中图分类号:
　　TP393.02文献标志码:A
　　
　　Wspruce: an improved method of measuring available bandwidth
　　JI De.zhi*, WU Wei.dong
　　
　　College of Computer Science and Technology, Wuhan University of Science and Technology, Wuhan Hubei 430065, ChinaAbstract:
　　Available bandwidth is the main parameter to reflect the network status. Its accurate measurement and estimation is an essential problem in traffic engineering and network monitoring. But there are many difficulties in its actual measurement. For spruce, it converges slowly and need high overhead. To solve the problems, Wspruce,an improved method of measuring available bandwidth is proposed. By using Hidden Markov Model(HMM)-series prediction features, available bandwidth can be made ??more accurate analysis. Actual measurements show that the method for estimating the available bandwidth measurement is faster, lower overhead.
　　
　　Available bandwidth is the main parameter to reflect the network status, of which the accurate measurement and estimation is an essential problem in traffic engineering and network monitoring. And there are many difficulties in its actual measurement. For Spruce, it converges slowly and needs high overhead. To solve the problems, Wspruce, an improved method of measuring available bandwidth was proposed. By using Hidden Markov Model (HMM).series prediction features, more accurate analysis can be made on the available bandwidth. The actual measurements show that the method for estimating the available bandwidth measurement is faster, and of lower overhead.
　　
　　Key words:
　　available bandwidth; traffic engineering; network monitoring; Hidden Markov Model (HMM); series prediction
　　
　　0引言
　　网络测量是高性能协议设计、网络设备开发、网络规划与建设、网络管理与操作的基础，同时也是开发高效能网络应用的基础。随着实时业务和多媒体应用等新业务的不断增加，人们对网络的服务质量(Quality of Service,QoS)提出了更高的要求。尽管网络主干带宽和接入带宽成倍增加，但是网络性能并没有得到成倍的提升。其主要原因是网络容量设计、网络资源分配和应用设计的问题。网络带宽测量的目的是精确地找到网络的中的紧致链路(可用带宽最小的链路)所在，从而为全网范围的网络容量规划提供依据。因此带宽测量在网络测量中占有重要地位［1］。
　　带宽测量可以分为原始带宽测量和可用带宽测量。原始带宽capacity，也称为容量，是指在没有背景流量［2-4］的前提下，单链路或者端到端的一条路径单位时间内可以传输的最大数据量；可用带宽，是指在存在背景流量的前提下，在一段时间间隔内，链路或端到端的路径能提供的最大服务速率。即在不导致链路拥塞的前提下，单位时间内能传输的数据量。由于原始带宽很容易从互联网服务提供商（Internet Service Provider）处获得，测量价值不大，因此本文主要针对可用带宽的测量。
　　1背景知识介绍
　　1.1相关概念
　　链路带宽即链路容量，指的是链路在物理设计上能够达到的最大数据传输速率，一般是一个固定值。
　　
　　瓶颈带宽两个节点之间路径上的最小的链路带宽，它表示一条路径的最大传输速率。对于大多数网络来说，两个主机之间的瓶颈带宽不会改变，也不受网络流量的影响。如果LSD={l0,l1，…，ln}表示一条从源端S到目的端D的通路，n表示路径的跳数，li表示第i条链路,bi表示li的链路带宽，那么通路LSD的瓶颈带宽βSD可用式（1）表示:
　　βSD=min(b0,b1,b2，…,bn) （1）
　　链路的可利用带宽链路上未被背景流量占用的剩余带宽。按式（1），如果Ui(0≤Ui≤1)表示Li的利用率，链路Li的可利用带宽αi=βi(1-Ui)。
　　通路的可利用带宽一条路径中最小的链路可利用带宽。通路LSD的可利用带宽αSD可用式（2）表示：
　　αSD=min(a0,a1,a2,…,an)（2）
　　
　　1.2包间隔模型分析
　　包间隔模型(Probe Gap Model,PGM)［5］技术是目前使用最多的一种可用带宽测量技术。测量前提是路径的容量已知，其模型如图1所示。设测量的目标路径为P，PGM发送端以一定速度发送探测包对，设包对间隔为Δin，在接收端得到的包对间隔为Δout。假设路径P 只有一条紧致链路，而且在该路由器上探测包对之间的队列不为空，即第一个探测包离开之后和第二个探测包完全到达之前还有背景流量在路由器缓冲区排队，这样，在接收端得到的探测包对的间隔Δout 为Δin 加上在Δin 的时间间隔内路由器输出缓冲区的竞争数据包的传输时间。这样，传输背景流量的速率为（ Δout - Δin）/ Δin*C，其中C 是紧致链路的容量，可用带宽的大小可以用式(3)得到：AB=C*(1-Δout-ΔinΔin)(3)
　　ε=Δout-ΔinΔin (4)图片
　　图1PGM模型2基于隐马尔可夫模型的可用带宽模型
　　在隐马尔可夫模型(Hidden Markov Model,HMM)［6］的可用带宽模型中，对变量进行了统一定义，如表1所示。
　　
　　2.1HMM的基本问题
　　1)评估问题。给定观察序列O=ξ1，ξ2，…,ξT和模型λ=（π，A，B），计算P（O |λ）。指的是给定模型和输出观察序列，如何计算从模型生成观察序列的概率。实际是评估一个模型和给定观察序列的匹配程度，可以用来在一系列候选模型中选取最匹配的模型。解决方案是Forward.backward算法［7］。
　　第4期
　　纪德志等：Wspruce:一种改进的可用带宽测量方法计算机应用 第32卷
　　
　　2)解码问题。
　　给定观察序列O＝ξ1，ξ2，…,ξT和模型λ=（π，A，B），求在某种意义的情况下最优的相关状态序列。这个最优状态序列就是对输出观察的最佳解释，由此可以试图揭示模型的隐藏部分，比如查找正常的状态序列，一般采用Viterbi算法［8］解决。
　　
　　3)学习问题。
　　给定一个观察序列O＝ξ1，ξ2，…,ξT,如何调整优化模型参数λ=（π，A，B），使得P（O |λ）最大。目前普遍使用的方法是Baum.Welch估计算法［9］。
　　2.2HMM可用带宽模型
　　在一条端对端路径上可用带宽可以被抽象成N个状态，每一个状态代表一定程度的利用率。例如在图2的五个状态中，可用带宽的状态从低到高分别为L，ML，M，MH，H。也就是说，它可以位于范围从［0，0.2），［0.2，0.4），［0.4，0.6），［0.6，0.8），或［0.8，1］内的任何利用率。如果能观察到时间T内的连续状态，那么每个状态范围中间点的平均值就可以认为是时间T内的可用带宽的一个估计。状态定义得越多，每个状态所呈现的可用带宽的范围就会越小，所估计的结果就会越准确。
　　
　　图片
　　图2可用带宽模型
　　然而可用带宽的状态不能直接观察到，但可以通过HMM模型来估计这些未知的状态。这种模型能够用于找出在一定时间段内的与包分布有关的状态序列。它是由X个代表不同可用带宽水平的不相关联的隐藏状态以及所观察到的探测包对的分布变量ξ所组成。B代表在一个特定的状态下所观察到的状态概率。可用带宽状态之间的过渡用矩阵A来表示。这个模型在每一次新的观察出现之后就会被优化一次，用于决定在时间T内所产生的状态序列。最终，时间T内估测到的状态序列的平均值即为可用带宽的平均值。模型如图3所示。图片
　　图3可用带宽的HMM
　　2.3HMM的可用带宽模型的组成
　　1)模型中的状态数目N。
　　定义状态集合为S＝｛S1，S2，…,Sn｝，代表可用带宽的水平依次从低到高排列。再定义t时刻的状态为Xt。
　　2)每一个状态所产生的观察符号的数目（M）。
　　每一个状态会产生很多可能的结果，也就是说，这些符号的集合是和观察到的探测样本的方法相关联的。
　　ξ=「M*|1-ε|�(5)
　　3)状态之间的过渡矩阵A。
　　在HMM中，假设状态之间的过渡只发生在相邻的状态，于是就可以设定好初始的状态矩阵。这个假设有利于初始的计算以便找到模型参数。因为矩阵中的未知元素已被减少到只剩三条斜线。这对于夹杂着背景流量的探测包对来说是一个很好的假设。然而实际情况并不总是这样的，由于一个探测包对夹杂着背景流量，而它随后的一个却找到了空闲的通道，这样会导致状态不是在相邻的状态之间过渡。但随着时间的推移，HMM会了解这种过渡并对过渡概率做出相应的调整。
　　5)初始状态概率π。
　　这是初始状态概率分布的一个矢量,于是可以把模型记为λ=（π，A，B）。
　　2.4 参数估计
　　给定一个时间T内的观察序列O＝ξ1，ξ2，…,ξT，要估算出最有可能产生此序列的模型λ=（π，A，B），并且使得P(O|λ)最大,可以通过Baum.Welch算法来解决。这个算法的目的就是对于每一个新观察到状态序列来更新可用带宽模型。这个算法有两处主要的修改，第一个就是初始转移概率矩阵A是随机生成的是一个一步到位的过渡矩阵。因此，在矩阵中只有三条斜线上有非零数值。第二个就是观察概率矩阵B是固定的。以便状态所产生的观察概率不会改变。这是因为，高度拥挤的链接将增加数据包之间的分散性，反之亦然。事实上，一条链路上没有背景流量的话数据包对之间的分散将为零（或接近零）。整个算法的时间复杂度为O（N2T），运行的步骤如下：
　　
　　1)设定初始模型λ0 ，A0，π0；
　　2)通过λ0和观察到的状态序列O算出一个新的λ=(A,B0, π)；
　　3)如果log P(O| λ)-log P(O|λ0 )

推荐访问:可用 带宽 改进 测量方法