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］解决。 (责任编辑：南粤论文中心)转贴于南粤论文中心: http://www.nylw.net(南粤论文中心__代写代发论文_毕业论文带写_广州职称论文代发_广州论文网）