一种基于in自我的qos路由算法

一种基于in自我的qos路由算法

1混合网络模型在当前的网络中，所有服务都使用了最大的分类模式，并且不能提供服务质量qos的保证。随着用户服务的需要和各种多媒体应用的出现，qos网络的需求越来越大。目前，主要有两个qos网络体系模型：interv综合网络系统模型和differv区别网络模型。IntServ网络模型通过资源预留和接纳控制提供基于每一个流的QoS能力.IntServ要求网络交换节点(路由器)维持每一个流的状态信息,对于较大规模的网络,可能同时存在上百万级的数据流,建立和维持这么多流的状态信息需要相当大的存储空间和处理耗费.因此,IntServ网络的可扩展性差.为了解决可扩展性问题,人们又提出了DiffServ模型.DiffServ考虑的是流的聚合,并不关心单个的数据流,其目的在于提供不同服务类别之间的区别处理,而不是提供每一个流的绝对QoS保证.因此它不要求网络交换节点维持每一个流的状态信息,具有较好的可扩展性.以上两种网络模型,各有其优缺点.在实际的操作中,往往希望可以提供每一个流的QoS保证,同时也具有好的网络可扩展性.因此,一种混合的网络模型被建议采用:边缘网络采用IntServ网络,核心网络采用DiffServ网络.在网络的边缘,流数量较少,可扩展性要求较低,使用每一流的处理,采用IntServ网络.而在网络的中心部位,流数量较大,高速的数据传输是最重要的要求,采用DiffServ网络.本文的目标就是研究在这种具有良好可扩展性的混合网络模型下的QoS路由算法.2带宽预留算法速率相关(Rate-proportional)调度算法能够保证每一个数据流的分组性能,包括虚时钟调度(VirtualClock),加权公平排队调度(WeightedFairQueueing),基于帧的公平排队调度(Frame-basedFairQueueing)等,这些调度算法确保同一个输出链路上的不同队列之间依各自的比例共享链路的带宽容量.在IntServ中,分组基于每一流排队,也就是每一个流使用独立的一个队列进行排队调度.当网络节点使用这类速率相关的调度算法时,数据流分组的端到端延时,延时抖动和为了保证数据分组不丢失而需要的每个网络节点的缓存大小都是流所预留带宽和流的流量源特征参数的函数.可表述如下:在IntServ中,给定一个n跳的路径P,流f的流量源特征令牌桶为(σ,b),σ是平均令牌产生速率,即流速率.b是桶的大小,即流突发大小.设第i跳链路的总带宽为Ci,假设路径的各链路都预留同样的带宽r(r≥σ),Lmax是网络最大分组大小,propi是第i跳的链路传播延时.可以证明分组从源节点到目的节点所经历的端到端延时、延时抖动的上限值和第j跳网络节点所需的缓存空间可由下列公式给出:D(Ρ,f,r)=br+n⋅Lmaxr+n∑i=1LmaxCi+n∑i=1propi(1)J(Ρ,f,r)=br+n⋅Lmaxr(2)B(Ρ,f,j)=b+j⋅Lmax(3)这些公式将延时,延时抖动的上限值,缓存空间,预留的带宽和过滤流的流量源令牌桶特性联系在一起.若把n看成变量j,公式即可变成到第j跳的相应值.3混合网络模型QoS路由的目标是为具有QoS要求的应用寻找满足条件的网络路径,同时优化网络资源利用率.在IntServ/DiffServ这种混合网络模型中,IntServ网络部分仍然可以通过采用速率相关的调度算法获得确定的QoS性能.因此为了在混合网络中提供确定QoS的端到端服务,最关键的问题是如何在核心网络的DiffServ域部分提供QoS保证.DiffServ网络采用聚合流排队,无法通过缓存预留来获得分组的零丢包率保证,并且网络节点具有较大的延时抖动.基于此,本文主要研究混合网络模型中的带宽—延时限制路由问题.3.1interv节点sdv存储的带宽分配算法本节研究在DiffServ网络中提供带宽和延时保证,希望在保证流带宽的同时可以给出分组通过网络节点转送所经历延时的确定上限值.通过对标准化的确保转发AFPHB进行相应的配置,或者定义新的PHB,可以实现这样的服务.本文称这种服务为确保延时服务GD.在这里,PHB具有服务类和丢弃优先级两个属性,属于相同服务类的数据分组在同一个队列中被调度.在拥塞发生的时候,根据丢弃优先级的不同进行相应的丢弃处理.对于使用GD服务的任一个流f,为了提供带宽保证,需要预留u=σ的带宽,σ是f的速率.假设在DiffServ域的某个网络节点k,出口链路的总带宽为Ck,分配给GD服务Rk的带宽,Rk<Ck,则所有聚合流的总预留带宽不能超过Rk.相应缓存队列长度为Bk,分组调度仍然采用速率相关的调度算法.那么属于该服务类并且被成功转发的数据分组在这个k节点所经历的最大延时为:dk=BkRk+LmaxCk+propk(4)最短延时为:tk=LmaxCk+propk(5)此处,Lmax是数据分组的最大长度,propk是出口链路的传播延时.则k节点相应的延时抖动上限为:jk=BkRk(6)据此可以将纯IntServ下的公式(1),(2),(3)扩展到IntServ/DiffServ混合网络模型:在IntServ/DiffServ混合网络中,IntServ节点部分使用每一流排队,DiffServ节点部分使用GD服务,给定一个n+m跳的路径P,其中n跳是IntServ节点,m跳是DiffServ节点.流f的流量源特征令牌桶为(σ,b),σ是平均令牌产生速率,b是桶的大小,对于n跳的IntServ节点部分,设第i跳链路的总带宽为Ci,假设各跳链路都预留同样的带宽r(r≥σ),Lmax是最大分组大小,propi是第i跳的链路传播延时.则分组从源节点到目的节点所经历的端到端延时,延时抖动的上限值以及IntServ节点部分第j跳网络节点所需的缓存空间可由下列公式给出:D(Ρ,f,r)=br+n⋅Lmaxr+n∑i=1LmaxCi+n∑i=1propi+m∑k=1dk(7)J(Ρ,f,r)=br+n⋅Lmaxr+m∑k=1jk(8)B(Ρ,f,j)=b+j⋅Lmax(9)各参数的含义参考前面公式的说明.在这里,IntServ节点部分缓存大小的预留仍然延用公式(3)的结果,而DiffServ节点部分没有每个流的缓存预留.由公式可知,延时和延时抖动与IntServ域预留的带宽,流量源突发和跳数等有关,而IntServ域中节点需要的缓存大小只与流量源突发和跳数有关.3.2带宽—混合网络模型的带宽-延时保证服务在IntServ/DiffServ混合网络模型中,对于流量源特征令牌桶为(σ,b)的流f,源节点为S,目的节点为D,给定要求的端到端延时的最大值为Drequest,假设路径预留带宽为r,根据一定的标准,找寻一条从S到D的路径P,满足r≥σ,D(P,f,r)<Drequest.这就是混合网络模型的带宽—延时限制QoS路由问题.在混合网络中,要提供端到端的带宽—延时保证,DiffServ域需要使用GD服务.同时为了降低包丢失率,在IntServ节点部分将保证没有分组的丢失,分组丢失是DiffServ域中由于多个流聚合在同一个服务类的队列中排队调度引起的,只发生在DiffServ节点部分.具体的接纳控制条件为:D(P,f,r)≤Drequest;在IntServ节点部分,预留的带宽r要大于流量源平均速率σ,即r≥σ;而因为丢包只发生在DiffServ节点部分,所以IntServ节点部分仍然有缓存预留的要求,假设IntServ第i跳网络节点可获得的缓存空间为B(i)available,则要求B(P,f,i)≤B(i)available(本文总是假设网络节点具有足够的缓存空间);在DiffServ节点部分,因为使用GD服务,需要预留u=σ的带宽.假设第k跳网络节点分配给GD服务类Rk的带宽,已经预留的总带宽为Uk,则要求u+Uk≤Rk.3.3基于贝尔曼-景观的interv节点带宽计算定义(4)式为DiffServ域的链路耗费值:dk=BkRk+LmaxCk+propk,定义IntServ域的链路耗费值为:dj=Lmaxr+LmaxCj+propj(10)再定义路径的IntServ节点部分的最大可预留带宽mrb,设给定的路径为P,则mrb(P)=min(Rj|j∈P的IntServ域链路)(11)Rj为第j条链路的剩余带宽.由定义可知,mrb肯定是等于路径的IntServ域某些链路的剩余带宽.由(7)式可知,当路径的IntServ节点部分预留带宽为mrb时,流可以取得最小的端到端延时.设网络的IntServ域所有链路的剩余带宽值构成集合为R,对于∀r,r∈R假设路径IntServ节点部分预留带宽r,则网络拓扑图G中IntServ域部分链路剩余带宽值小于r的链路不可能成为该路径的链路,在G中去掉这些链路,得到一个剩余图G’.根据(4),(10)式,分别计算G’的DiffServ域和IntServ域的链路耗费值.贝尔曼-福特(Bellman-Ford)算法是依据源节点到目的节点跳数的增加依次计算最小耗费值路径,使用该算法进行计算,依据前文的接纳控制条件,保留满足条件的不同跳数的最短路径,得到一组路径的集合.对于R中的满足r≥σ的不同剩余带宽值,都可以计算相应的一组路径集合,这样就构成如表1所示的可选路径表.假设选定了表中具体的某条路径作为流的实际路由路径,为了充分的利用网络资源,应该在IntServ节点部分尽可能小的预留带宽值.根据(7)式和接纳控制的要求,可以求得IntServ节点部分实际需要预留的带宽最小值rmin,这就是实际应该预留的带宽值.上面的算法在中被称为迭代贝尔曼-福特算法.3.4仿真实验a基于较低性能目标的链路相对负载率a需要依照一定的标准来从这些可选路径中选择最优的路径作为实际路由路径,从而达到合理高效的使用网络资源的目的.在混合网络中,因为DiffServ节点部分使用聚合流排队,预留的带宽值为流速率σ定值,并且有分组丢包的产生,QoS保证能力差.所以主要考虑IntServ域部分的网络资源利用,本节后面部分所提到的链路未加说明的都是指混合模型中IntServ域部分的链路.考虑的出发点是节约网络资源和均衡分布网络流量这两个目标,而这两个目标往往是相互冲突的,只能在两者间取某种程度的折中.首先定义链路的相对负载率u:u=链路已经预留的带宽/链路总的带宽(12)接下来定义路径P的IntServ部分相对负载率U,可以给出两种定义:a)U=max(uj|j∈P的IntServ链路)b)U=1nn∑j=1uj,n为路径的IntServ链路数uj为第j条链路的相对负载率.本文的仿真实验采用的是b)定义,而a)定义具有类似的性能.最后给出五种选择标准,分别是:最轻的最短路径(l-s:Lightest-shortestpath):跳数最小的路径,如果有多条这样的路径,选择预留带宽后具有最小U值的一条.最短的最轻路径(s-l:Shortest-lightestpath):预留带宽后具有最小U值的路径,如果有多条这样的路径,选择跳数最小的一条.最小带宽路径(m-b:Mimimum-bandwidthpath):IntServ域实际需要预留带宽值最小的路径,如果有多条这样的路径,选择跳数最小的一条.最小延时路径(s-d:Shortest-delaypath):当路径IntServ部分预留带宽为路径的mrb值时,具有最小端到端延时值的路径.如果有多条这样的路径,选择跳数最小的一条.最小包丢失可能路径(m-l:Min-losspath):具有最小Diff-Serv域跳数的路径,如果有多条这样的路径,选择总跳数最小的一条.4流量源特征提取这一节讨论混合网络模型中这种端到端带宽—延时保证的流的数据分组丢失.因为IntServ域部分提供每个流的缓存保证,不会引起包丢失.而DiffServ域部分使用GD服务,多个流被聚集在同一个服务类缓存队列中排队调度,当队列满的时候就会产生分组数据包的丢失.因此分组丢失的多少与队列的长度密切相关.如果单纯为了保证低的包丢失率,可以提供尽可能大的缓存队列.但是,随着队列长度的增加,数据分组在节点所经历的延时上限也增加,拥塞发生时,分组数据包在网络节点可能经历相当长的排队延时,这对于需要端到端延时保证的流是相当不利的.考虑混合网络模型的IBF算法,当DiffServ域节点的延时上限相对较大时,路由算法成功搜索到满足延时要求的路由路径的可能性就会降低.所以要综合考虑路由算法的成功率和数据分组丢失两个方面来合理的设置DiffServ域节点的GD服务的缓存队列长度B.拥塞主要是流的聚集以及流的突发产生的.假设某一个流f,其流量源特征令牌桶为(σ,b),σ是平均令牌产生速率,b是桶的大小.定义流f的突发度:Τ=bσ(13)由定义可知,这是一个时间参数.对于DiffServ域的任一节点k,分配Rk的带宽给GD服务类,相应缓存队列长度为Bk,定义该服务类聚合流的允许平均突发度为:ˉΤk=BkRk(14)由定义可知,它也是一个时间参数,并且等于节点的延时抖动上限,表示缓存队列可以容纳的聚合流的突发度.而相应的节点最大延时公式(4)变为:dk=Τ¯k+LmaxCk+propk(15)考虑若干个流的聚合.假设为d个流,相应的流量源特征令牌桶分别为(σi,bi),i=1…d,并且它们的突发度大小都为T.令所有流的速率和为V,令牌桶和为G,即V=∑i=1dσi,G=∑i=1dbi,则G=T×V.在这里,G表示流聚合的总突发数量,而V表示流聚合的总速率.由GD服务的带宽预留条件可知,V≤Rk.要容纳这d个流聚合的总突发,则要求有G≤Bk.而当Τ¯k≥Τ时,该式总是成立的.即当服务类聚合流的允许平均突发度大于等于流的突发度时,可以容纳流聚合的总突发.因为网络的动态性以及分组数据包的丢失,并且流在DiffServ节点是聚合排队的,单个流在网络节点中的模式与其流量源是不会完全符合的,会有所改变.流量源特征令牌桶只能近似的表示它在该网络节点的流量模式.因此G只能近似的表示确保延时服务类GD聚合流的总突发,在缓存队列长度为Bk时,分组的丢失仍然可能会发生.假设流的突发为[b1,b2]之间的均匀分布,速率为[σ1,σ2]之间的均匀分布.则流的最大和最小的突发度分别为Τmax=b2σ1‚Τmin=b1σ2.而为了满足所有流的突发,应该取Τ¯k=Τmax=b2σ1,但是这将导致过大的节点延时上限,不利于路由算法路径搜索的成功.而且对于较小突发度的流,设置这么大Τ¯k值的缓存队列也是不必要的.因此,合理的设置应该是取Tmin～Tmax之间的某个值.本文取流的突发度分布的概率均值(期望)Ta作为缓存队列的Τ¯k.由于Τ¯k＜Τmax,这种方法仍然会使聚合流产生一定的包丢失率.而且对于突发度较小的流,Τ¯k仍然偏大.突发度较小的流,其引起的队列拥塞作用也较小,更应该优先保证这种突发度较小的流被成功路由.为了改进性能,考虑使用多个服务类,每个服务类对应不同的突发度范围的流.流的数据分组依据其突发度的不同分开排队,相应的队列使用不同的允许平均突发度,同一个服务类中的分组数据包仍然根据丢弃优先级的不同进行相应的丢包处理.本文按分布概率将流突发度均分为三段,每段取1/3的突发度分布区间.分别为[Tmin,T1],[T1,T2],[T2,Tmax].每一段对应一个服务类i,分配Rki=Rk3的带宽,i=1,2,3.取每一段的流突发度概率均值Tai作为该段服务类的聚合流的允许平均突发度Τ¯ki,通过采用多个服务类,将突发程度不同的流在不同的队列排队,小的突发采用较小的队列,大的突发采用较大的队列,则可达到提高较小突发流路由成功率的目的.对于属于同一个服务类的流,可以根据其数据丢失率的要求,采用不同的丢弃优先级别,从而获得相对不同的分组丢失率.具体的丢弃策略可以使用主动队列管理REM技术.5链路剩余带宽值的近似算法由于IntServ网络的链路剩余带宽值的数量可能很大,而IBF算法要对所有的链路剩余带宽值都进行运算,即使不同的链路剩余带宽值的差异很小.为了减小算法时间复杂度,可以使用一个较小数量的链路剩余带宽值集合V,将每条链路实际的剩余带宽值近似到集合V中的某一个值.这样只需要对这个数量较少的剩余带宽值集合进行IBF算法计算即可.文献中的结论显示,这种近似算法具有接近甚至优于非近似算法的性能.因此,本文的仿真实验都使用这种近似算法来进行研究.5.1仿真的ipf算法仿真仿真采用的网络拓扑如图1所示.该网络一共有N=18个节点,L=30条链路.图中实线表示DiffServ链路,而虚线表示IntServ链路.设置DiffServ链路带宽C1=1500M,IntServ链路带宽C2=150M.假设链路的传播延时均匀分布于[0.1ms,1ms],网络最大数据分组的大小Lmax=15Kbit.假设网络的流量分布包括两个部分,50%的流在网络中均匀分布,也就是流等概率的产生于网络中任意的两个节点之间.而另外50%的流分布于东-西方向,令A={1,2,3,4,5},B={14,15,16,17,18},表示两个节点的集合.则该50%的流等概率的产生于从A到B或者从B到A的节点之间.节点i产生的流服从均值为λi的Poisson分布,到达率λi取决于网络总的流量负载和流在网络中的分布.假设流的持续时间服从均值为1/μ=500ms的负指数分布,流的流量源特征令牌桶大小也就是流的突发大小均匀分布于[40kb,80kb]之间.流的速率均匀分布于[1M,5M](bit/s)之间,平均速率为b¯=3Μ,则进入网络的总的流量负载为ρ=1μ⋅b¯⋅∑i=118λi.通过调整λi的取值可以得到不同的网络总负载,从而观察算法在不同网络负载下的性能.仿真实验采用近似的IBF算法.可以想象,在IntServ域,单个流如果预留太大的带宽,将减少其它流被接纳的成功率,导致网络总的路由性能下降.因此,限制单个流的最大可预留带宽.因为流的最大请求带宽为5M,限制单个流的最大可预留带宽为25M.近似IBF算法选择一组带宽集合V={v1,…,vn},v1>…>vn.v1是最大可预留带宽.对于每条链路,近似其链路剩余带宽值v到满足vi≤v的最大vi.在近似IBF算法中,每次迭代运算都以vi作为实际的可预留带宽.集合V的选择取决于链路带宽和流请求带宽的分布.为了使用尽量少的剩余带宽值而又不显著的减少可考虑的可选路径,可行的办法是随着带宽值的减小而缩小连续两个带宽值之间的距离.在仿真实验中,集合V={25,20,16,14,12,10,8,7,6,5,4,3,2,1}.5.2不同路径流阻塞性能由于流的突发大小均匀分布于[40kb,80kb]之间,速率均匀分布于[1M,5M]之间,则计算可知,流突发分布于[8ms,80ms],概率均值Ta=24.14ms.以此来设置GD服务的缓存队列的允许平均突发度,即Τ¯k=24.14ms.IntServ网络域中,链路的延时上限取决于预留的带宽.而DiffServ域链路具有充足的带宽资源,并且流在DiffServ域只需要预留与其速率相等的带宽即可,不会因为带宽的缺乏而被阻塞.而链路延时上限则取决于缓存队列的允许平均突发度,为固定值,并且相对IntServ域链路的值要更大.因此在混合网络中,对路由成功率起决定作用的是IntServ域的链路带宽和DiffServ域的链路延时上限.图2(a)、(b)分别表示流的端到端延时上限要求d=Drequest均匀分布于[60ms,80ms]和[70ms,90ms]之间的情况下各种路径选择标准的流阻塞率性能.图3(a)、(b)图4(a)、(b)则分别表示在这两种情况下,路由成功的流在网络中的平均预留带宽以及流所经历的DiffServ域平均跳数.由图2(a)、(b)图3(a)、(b)可知,各路径选择标准的流阻塞率以及在IntServ域的平均预留带宽由小到大依次为:m-b,s-d,m-l,l-s,s-l.流在DiffServ域经历的跳数越小,则经历的路径延时上限也越小.因此它可以在IntServ域经历更大的路径延时,由(7)可知,它可以在IntServ域经历更多的跳数并且预留更小的链路带宽,更能节约IntServ域带宽资源.m-l选择具有最小DiffServ域跳数的路径,s-d选择具有最小端到端延时的路径,DiffServ域跳数越小,端到端路径延时也相对越小.m-b选择IntServ域预留带宽最小的路径,IntServ域延时上限较大,则DiffServ域需要经历较小的跳数.而l-s,s-l主要考虑的是路径总跳数以及IntServ域的流量均衡,相对具有较大的DiffServ域跳数.如图4(a)、(b)所示,流经历的DiffServ域平均跳数由小到大依次为:m-l,s-d,m-b,l-s,s-l.对比图2(a)、(b),图3(a)、(b),图4(a)、(b),可以看到,对于各种路径选择标准,延时上限要求越小则流阻塞率越大,并且流在IntServ域需要预留更大的链路带宽,而在DiffServ域需要经历更小的跳数.5.3流平均阻塞率以流阻塞率性能最好的路径选择标准m-b为例,研究GD服务采用多个服务类也就是多个缓存队列排队调度时的算法性能.按分布概率将流突发