QoS调度算法（通用8篇）
QoS调度算法 篇1
引言
为适应移动通信技术的快速发展, 第三代合作伙伴计划 (3GPP) 启动了长期演进 (Long Term Evolution, LTE) 系统方案[1]。LTE系统采用正交频分多址 (Orthogonal Frequency Division Multiple Access, OFDMA) 技术[2]和多入多出 (Multiple Input Multiple Output, MIMO) 技术[3], 可以在时域、频域和码域上灵活地进行无线资源管理[4]。无线资源管理是LTE的关键技术之一, 它的主要功能是通过分组调度算法来确保用户的QoS和用户间的公平性并最大化系统的吞吐量。PF算法是最大载干比调度 (Max C/I) 和轮询调度 (RR) 的折中, 它兼顾了用户的公平性和系统的吞吐量, 但并没有考虑到QoS的速率需求[5]。文献[6]提出的USGF算法考虑了QoS的速率需求, 提高了整个系统的用户满意程度, 但当调度过程中所有用户都能满足QoS速率需求且有无线资源富余时, 并没有最大化系统的吞吐量。
为此, 这里结合PF算法和USGF算法, 引入用户满意度反馈提出一种判决因素可变的调度算法 (Factor Chang i ng Sc h ed u l i ng A lgo r i t h m, FCS) , 并在系统吞吐量、用户平均满意度和不同QoS速率需求业务之间的公平性等方面进行仿真和结果分析。
系统模型
考虑一个多小区的TDD LTE系统, 每个小区有三个扇区且小区半径相同, 基站位于小区的中心位置, 采用两发两收天线。每个扇区有N个用户和M个物理资源 (Physical Resource Block, PRB) , 用户k的QoS速率需求为Vk, 每个PRB占用B kHz的带宽和L个子载波。系统使用自适应调制编码 (Adaptive Modulation And Coding, AMC) 技术, 根据信道的瞬时状态采用QPSK、16QAM、64QAM三种不同的调制编码方案 (Modulation And Coding Scheme, MCS) [7]。采用动态系统仿真 (Dynamic System Simulation, DSS) , 为了考察用户间的公平性, 假定用户初始位置随机分配且有一部分用户长时间处于信道状况极度不好的状态。调度算法每个传输间隔 (Transmission Time Interval, TTI) 执行一次, 信道反馈延时d个I。
算法描述
定义矩阵单位阶跃函数ε (P) , P是一个一维矩阵, M 1为矩阵长度, 则有:
PF算法
PF算法一方面充分利用用户信道的时变性, 另一方面较好地保证了系统多用户分集与公平性间的平衡。用户k在物理资源块m上的优先级为[8]:
式中rk, m (t) 为时间片t内用户k在物理资源块m上所支持的最大数据速率;Rk (t) 为用户k当前获得的平均速率, 每次调度后更新[9]。计算公式为:
式中tc为计算平均速率的时间片长度;rk', m (t) 为时间片t内用户k在物力资源块m上获得的速率, 当物理资源块m分配给用户k时, , 否则
USGF算法
USGF算法是一种保证用户满意度的公平算法, 用户k在物理资源块m上的优先级为:
式中R'k (t) 表示在时间片t内的调度过程中, 用户k获得的累计数据速率。
FCS算法
FCS算法是对USGF的一种改进, 引入用户满意度反馈ρk (t) 和Qos速率需求满足程度矩阵∆V, 在保证用户满意度和公平性的条件下提高系统的吞吐量。用户k在物理资源块m上的优先级为:
其中ρk (t) 表示用户k当前的满意度, 定义为:
ρk (t) 的最小值定义为0.05以防止极小的满意度产生一个极大的优先级值, ∆V表示速率需求满足程度列矩阵, 定义为:
在时间片t开始调度过程中的t1时刻若ε (∆V) =0, 即此时PRB没有分配完毕, 但是所有用户都已经满足QoS速率需求, 同时还存在剩余的频率资源, 则式 (5) 化简为:
这时调度算法将不再考虑QoS速率需求, 而是将该资源块分配给在此资源块上数据速率最大的那个用户以获得最大的系统吞吐量。
调度结束后, 用户k所获得的吞吐量的计算公式为, 系统吞吐量计算公式为。
算法步骤:
1) 初始化用户集UE={U1, U 2...UN}, 物理资源块集PRB={RB1, RB2...RBM}和每个用户已获得的速率R'k (t) =0。
2) 取出用户集合UE和PRB中的一个物理资源块RBm。
3) 若α=0, 则用公式 (5) 计算优先级wk, m;若α=1, 则用公式 (9) 计算优先级wk, m。k∈[1, N], 选择最大的Wk, m并将RBm分配给Uk。
4) 将RBm从PRB中移除, 更新R'k (t) 和α后回到步骤2) , 直到所有RB分配完毕, 即PRB为空。
仿真与结果分析
仿真环境与参数设定
简单地, 假定系统中有如下两类业务类型。第一类业务 (class2) :目标速率Rk (t) =128kbps, 用户数为N/2;第二类业务 (class3) :目标速率Rk (t) =64kbps, 用户数为N/2;仿真参数如表1所示。
天线模型
每个基站均采用3扇区1 2 0度定向天线, 天线方向增益为:G (θ) =G-min[12 (θ/β) 2max, Gs] (dB) , 其中-π≤θ≤π, β=65π/180, Gs=20dB, Gmax=16dB。
宏观路损
使用3GPP TS25.814规范中定义的路损模型 (只和距离有关) 的路损公式来产生宏观路损图, 路损计算公式为L=128.1+37.6 log10 (R[km]) 。
阴影衰落
阴影衰落是由用户和基站间的传播路径中的障碍物引起的, 也可以看成是地形中的一些不规则的地理因素。它通常近似为一个均值为0dB、标准差为10dB的对数正态分布。
阴影会在一个较大的范围内产生影响, 为了捕捉对宏小区的动态影响, 这里采用了具有一定空间相关性的二维高斯过程。本模型中, 用一种低复杂度的方法将空间相关性引入到高斯过程中, 同时还保留它的统计属性和位置间的相关性。
仿真结果分析
(1) 图1给出了采用三种不同算法所获得的系统总吞吐量。可以看出PF算法所获得的总吞吐量远高于其它两种算法, 这是因为其它两种算法考虑了用户的速率需求, 部分速率需求高而信道状况差的用户造成了系统吞吐量的下降。通过计算, FCS算法比USGF算法系统吞吐量有所提高, 原因在于有些用户在某些时刻信道状况非常好, FCS算法能在满足用户速率需求的同时最大化系统的吞吐量。
(2) 图2给出了用户的平均满意度曲线。可以看出, FCS算法和USGF算法很接近, 而PF算法远低于这两种算法, 因为PF算法没有考虑用户的速率需求, 部分信道状况好而速率需求低的用户被分配了过多的资源造成了系统整体满意度的下降。
(3) 图3给出了三种算法下用户满意度的累积分布函数, 由用户的满意度累计分布函数曲线可以看出, 采用FCS算法和USGF算法时, 业务1和业务2的累计分布曲线较为接近, 而与PF算法则相差较大, 这说明FCS算法和USGF算法均能按照用户的速率需求分配资源, 相比PF算法更好地实现了不同用户不同速率需求业务之间的公平性。
结论
本文提出了一种保证QoS速率需求的分组调度算法并进行了仿真验证。通过对比, 得出该方法能够保证不同速率需求业务之间的公平性, 且在不降低用户满意度的条件下提高系统的总吞吐量。
参考文献
[1]沈嘉, 索士强, 全海洋, 等.3GPP长期演进 (LTE) 技术原理与系统设计[M].北京:人民邮电出版社, 2008
[2]ZHU H J, Hafez R H M.Scheduling Schemes for Multimedia Service in Wireless OFDM Systems[J].IEEE Wireless Communications, 2007, 14, (5) :99-105
[3]P.Xia, S.Zhou, G.B.Giannakis.Adaptive MIMO OFDM Based on Partial Channel State Information[J].IEEE Transactions on Signal Processing, 2004, 52, (2) :202-213
[4]3GPP TS36.331V8.5.0.E-UTRAN Radio Resource Control Protocols Specification[S].2009
[5]陆巍炜.LTE中QoS调度算法研究[D].西安:西安电子科技大学, 2009
[6]郑培超, 宋瀚涛, 贾韶军, 莫笑丽.LTE系统上行保证服务质量的分组调度算法[J].电子科技大学学报, 2009, 38, (2) :186-189
[7][Z/OL].http://www.nt.tuwien.ac.at
[8]Hoon Kim, Keunyoung Kim, Youngnam Han, Sangboh Yun.A Proportional Fair Scheduling for Multicarrier Transmission System[J].IEEE Communications Letters, 2005, 9, (3) :210-212
[9]Pramod Viswanath, David N.C.Tse, Rajiv Laroia.Opportunistic Beamforming Using Dumb Antennas[J].IEEE Transactions on Information Theory, 2002, 48, (6) :1277–1294
[10]3GPP TS25.814.Physical Layer Aspects for E-UTRA[S].2006
[11]3GPP TS36.942V8.2.0.Radio Frequency System scenarios[S].2009
[12]H.Claussen.Efficient Modelling of Channel Maps with Correlated Shadow Fading in Mobile Radio Systems[C]//IEEE 16th International Symposium on Personal, Indoor and Mobile Radio, Swindon, UK:IEEE, 2005:512-516
QoS调度算法 篇2
关键词：市场驱动,QoS,任务调度算法,网格工作流
0 引 言
在网格环境中调度工作流应用是一个NP完全问题,目前已经提出了许多启发式的调度算法对其进行调度。这些算法所采用的调度策略可分为三类:性能驱动、市场驱动和信任驱动。性能驱动策略的目标是调度系统有效的分配工作流任务到合适的网格资源,使完成整个应用所花费的时间最少。目前,大多数网格工作流调度系统都采用这种策略(如GrADS,Prodan)。市场驱动策略则是在满足用户QoS需求的情况下,使完成整个应用所花费的成本最低。也有一些网格系统采用这个策略(如Nimrod-G)[1]。而信任驱动的策略才提出不久,应用较少。
本文旨在讨论一个市场驱动的网格工作流任务调度算法,即要在用户指定的时间约束范围内,使完成整个工作量所花费的成本最低。
1 问题描述
在网格环境中,不同的第三方提供了许多相似或相等的资源,使用这些资源都可以完成某项任务。但根据服务质量的不同,所需要花费的时间和成本就各不相同。因此,网格用户可以根据他们自身需求选择合适的资源。对于一个网格工作流管理系统,只考虑功能性的需求是不够的,必须考虑不同的QoS需求,如时间约束、成本约束等。目前,对工作流QoS的一般分类如图1所示。
在本文中我们只考虑时间约束。因为对于大部分用户,他们可能并不需要在最短的时间获得最好的服务,而是希望在某个时间期限内能够用最低的成本来完成某个应用。所以,我们提出的任务调度算法的目标就是在满足用户的时间需求的情况下,使完成应用所花费的成本最低。
2 工作流任务调度算法
为了实现上述目标,可以采用分治法来解决任务调度,实现的步骤分为三步:
(1) 资源发现和需求识别[2,3]
对工作流图中的每个任务,使用网格信息服务分别识别所有可用的资源,列出可用资源列表,并对资源按价格进行降序排列;同时获得用户的QoS参数,如时间约束。
(2) 分配时间约束:
将用户给定的总时间期限分配给每个任务 网格工作流的流程运转模型分为四类:简单运转模型、发散运转模型、聚合运转模型、特殊运转模型。在本文中只考虑流程的结构为串行、并行发散和同步聚合的情况,如图2所示。
为了讲述问题的方便,也使读者更容易理解,本文后面部分都将以下述流程(图3)为例,对其进行任务调度。
a) 对于串行的情况,我们采用动态规划的方法来分配时间约束
将本文的目标函数描述成静态规划问题,如下:
其中D表示总的时间约束, ti表示分配给单个任务的子时间约束, gi(ti)表示在ti范围内对应的所采用资源的价格,c表示完成该流程所花费的总的成本。
把问题中的变量ti作为决策变量,将累积的量或随递推过程变化的量作为状态变量。设状态变量Si表示分配给任务Ti到任务Tn的子时间约束;决策变量di表示分配给任务Ti的子时间约束,即di=ti;这样就可以得到状态转移方程:Si+1=Si-di=Si-Ti,以及运行决策集合:
Di(Si)={di|0≤di=Ti≤Si}
从而写出动态规划的递推关系式为:
利用这个递推关系式进行逐段计算,最后求得f1(D) 即为所求问题的最小花费。
b) 对于并行发散和同步聚合的情况,采用如下准则进行时间约束的分配
准则1:从开始任务到结束任务的每一条支路上的所有子时间约束之和小于等于总的时间约束D。
准则2:并行发散的每个分支所分配的子时间约束相同。如由Task9和Task10组成的分支和Task11的分支具有相同的时间约束。
准则3:分配给每个任务的子时间约束必须大于或等于其最小执行时间。
准则4:根据用三点时间估算法估计出来的时间来分配总的时间约束。
三点时间估算法所涉及的三个时间分别为:最早完成时间a;最可能完成时间m;最晚完成时间b。显然,完成某项任务所需要的上述三种时间都具有一定的概率。根据经验,这些时间的概率分布可以认为近似于正态分布,一般情况下,可按下列公式计算执行时间:T=(a+4m+b)/6。
根据上述准则,就可以将总的时间约束合理地分配给并行发散和同步聚合的任务。
(3) 任务调度
分别为每个任务在其所分配的时间约束的允许范围内选择价钱最低的服务,对这个价钱求和,就得到了完成这个工作流应用的总的花费。该调度算法的伪代码如下:
3 仿真实验及性能评价
GridSim[5]是为R Buyya开发的,是一种基于计算经济模型的网格仿真平台,可以提供时间约束和/或成本约束的调度,能够模拟网格的多方面特性,因此,本文将扩展Gridsim来进行仿真实验。
根据流程的需要,我们模拟了12种类型的资源,每种类型的资源都有4个不同的服务提供者,因服务质量不同,所需要花费的时间和价钱就有所不同,因此我们总共模拟了48个服务提供者。表1仅列出了用GridSim模拟的对Task1的测试资源。
在实验中,我们比较了两种不同的调度算法,一是本文提出的市场驱动的Market-Driven调度算法,二是不考虑约束条件,只要保证完成任务所花费成本最低的Min-Cost调度算法。我们以时间约束为横坐标,分别以所花费时间和所花费成本为纵坐标,对两种算法进行比较。
从图4中可以看出,本文提出的市场驱动的任务调度算法可以在用户时间约束范围内获得局部最优解,以按时抢占市场;而Min-Cost调度算法虽然可以以最低的成本完成某个应用,但所花费的时间却远远超出了用户的需求,这样就有可能导致用户错过市场先机,造成不可估量的损失。
4 总结和展望
本文在充分考虑了用户的QoS需求的情况下,提出了一种市场驱动的、对网格工作流进行调度的任务调度算法。仿真实验结果表明,该算法可以在用户指定的时间约束内完成某个应用,并获得较优的执行代价,能够满足市场的需求。
另外,在本文中只考虑了两种工作流运转模型,也只关注了QoS的一个方面——即时间约束。在未来的工作中,将充分考虑各种运转模型,并研究QoS其它方面对网格工作流任务调度的影响,以进一步改进本算法。
参考文献
[1]Buyya R.Economic-based Distributed Resource Management and Scheduling for Grid Computing.PhD Thesis,Monash University,Aus-tralia,2002,12.
[2]Buyya R,Murshed M.A Deadline Budget Constrained Cost-Time Opti-mize Algorithm for Scheduling Parameter Sweep Applications on the Grid.GridSim Toolkit Release Document,Dec.2001.
[3]Buyya R,Murshed M,Abramson D.ADeadline and Budget Constrained Cost-Time Optimization Algorithm for Scheduling Task Farming Appli-cations on Global Grids.Technical Report,Monash University,March2002.
[4]Wolski R,Plank J,Brevik J,Bryan T.Analyzing Market-based Re-source Allocation Strategies for the Computational Grid.International Journal of High-performance Computing Applications,2001,15(3).
短作业优先调度算法 篇3
姓名：陈凯
学号：541413430202
地点：四教楼301
指导老师：张旭
专业班级：嵌入式软件14-02
实验名称：短作业优先调度算法
一、实验目的：
测试数据可以随即输入或从文件中读入。必须要考虑到作业的到达时间
最终能够计算每一个作业的周转时间。
二、实验内容：
模拟实现短作业调度算法，具体如下：
设置作业体：作业名，作业的到达时间，服务时间，作业间的链接指针 进程初始化：由用户输入作业名、作业的到达时间和服务时间进行初始化。显示函数：
1、显示当前调度的是哪个作业，后备队列中有哪些作业
2、最终显示每个作业的作业名、到达时间、服务时间、完成时间和周转时间
排序函数：对就已到达的作业按照服务时间进行排序。注意考虑到达时间 调度函数：每次从已到达的作业队列队首调度优一个作业执行。删除函数：作业结束后撤销。
三、实验代码
#include
char name[10];//进程名
floatarrivetime;//到达时间
floatservicetime;//服务时间
floatstarttime;
//开始时间
floatfinishtime;//完成时间 floatzztime;//周转时间 floatdqzztime;
//带权周转时间 };
sjf b[100];
//定义短作业优先算法进程的最大数量 voidSinput(sjf *p,int N)
//输入函数 { int i;
printf(“输入进程的名称、到达时间、服务时间:n”);for(i=0;i<=N-1;i++){
printf(“输入第%d进程的名称、到达时间、服务时间:”,i+1);scanf(“%s%f%f”,&p[i].name,&p[i].arrivetime,&p[i].servicetime);} }
//输出函数 voidSPrint(sjf *p,floatarrivetime,floatservicetime,floatstarttime,floatfinishtime,floatzztime,floatdqzztime,int N){ int k;
printf(“n执行顺序:n”);printf(“%s”,p[0].name);
for(k=1;k { printf(“-%s”,p[k].name);} printf(“n进程名tarrivetservicetstarttfinishtzztdqzzn”); for(k=0;k<=N-1;k++) { printf(“%st%-.2ft%-.2ft%-.2ft%-.2ft%-.2ft%-.2ftnn”,p[k].name,p[k].arrivetime,p[k].servicetime,p[k].starttime,p[k].finishtime,p[k].zztime,p[k].dqzztime); } } voidSsort(sjf *p,int N) //按短作业优先算法排序 { for(int i=1;i<=N-1;i++)for(int j=1;j<=i;j++) if(p[i].servicetime sjf temp;temp=p[i]; p[i]=p[j]; p[j]=temp;} } //运行结果 voidSdeal(sjf *p, float arrivetime,floatservicetime,floatstarttime,floatfinishtime,float&zztime,float&dqzztime,int N){ int k; for(k=0;k<=N-1;k++) { if(k==0){ p[k].starttime=p[k].arrivetime; p[k].finishtime=p[k].arrivetime+p[k].servicetime; } else { p[k].starttime=p[k-1].finishtime;//开始时间=前一个进程的完成时间 p[k].finishtime=p[k-1].finishtime+p[k].servicetime; //结束时间=前一个进程的完成时间+现在进程的服务时间 } } for(k=0;k<=N-1;k++){ p[k].zztime=p[k].finishtime-p[k].arrivetime; //周转时间=完成时间-到达时间 p[k].dqzztime=p[k].zztime/p[k].servicetime; //带权周转时间=周转时间/服务时间 } } void SJF(sjf *p,int N){ float arrivetime=0,servicetime=0,starttime=0,finishtime=0,zztime=0,dqzztime=0; Ssort(p,N); Sdeal(p,arrivetime,servicetime,starttime,finishtime,zztime,dqzztime,N); SPrint(p,arrivetime,servicetime,starttime,finishtime,zztime,dqzztime,N);} void main()//主函数 { int M;printf(“------------短作业优先调度算法-----------n”);printf(“输入作业数:”);scanf(“%d”,&M); Sinput(b,M);SJF(b,M);} 四、实验结果 五、实验总结 在无线自组织网络,传感器网络等多跳网络中,数据的传输要经过多个中继节点[2]。在路由方式确定的情况下,尽量减少数据包在每个中继节点的转发时延是提高整个系统吞吐量,减小全路径时延的有效方法。 队列调度算法为单个节点上的集中式算法,在网络环境下非常容易被忽略。传统的网络条件下一般采用单队列的先到先服务(FIFO)策略。但是,这种策略在实时性,公平性等方面存在明显不足。 1 先来先服务(First Come First Served) 先进先出属于典型的被动式队列管理的方法,它调度包的方法是:先到达网络节点的分组先被传输,其他分组采用默认的排队方法。然而,节点的缓冲总是有限的,如果分组到达时缓存已满,那么节点就不得不丢弃该分组。由于FIFO总是丢弃队尾的分组,所以又称它为“去尾”算法。FIFO和“去尾”是最简单的分组调度和丢弃策略,两者有时可被视为一体,简单成为FIFO排队[3]。 FIFO排队的算法简单,所以实施起来比较容易,当数据到达中继节点后,进入缓冲区唯一数据队列,队列中同时存在多媒体数据和常规数据报文,数据报文的转发按照先进先出的方式进行。 多媒体数据包在若干常规数据包之后发送,造成非实时数据先于实时数据发送的情形。如果将此队列重新进行排序,将多媒体数据包提前调度转发,则减少了后面数据包报文转发时延,代价只是稍微延长了常规数据报文的时延(常规数据报文对实时性不敏感)。 同时,由于常规数据报文在多媒体数据报文间分布不均,使得本来连续的多媒体数据流在经历多跳之后,相邻数据包的时间间隔差异加大,对于实时解码的接收端会造成多媒体服务的抖动,严重影响接收端媒体播放的质量。 本文中第二部分将具体描述我们面向无线多跳网络Qo S需求所设计的中继节点数据转发队列调度方法;第三部分通过计算机模拟的方式进行了性能评测;最后是总结和下一步工作。 2 策略描述 2.1 术语定义 多媒体数据报文代表具有实时特性的数据包,对网络传输时延有阀值限制,具有数据量较大、持续传输等特点,多为图像、声音和多媒体流等数据。 常规数据报文对实时性要求不高的数据,包括完全时间容忍的(如电子邮件数据)和时延要求不是很高的数据(如网页请求及下载数据)。 2.2 具体策略描述 当数据包到达转发节点时,根据数据包的类型进行分类,多媒体数据包插入队列头部,常规数据包从尾部插入。多媒体数据包加入队列的位置根据数据包Qo S参数中数据包初始发送Ts和当前时钟Tc的差为当前数据转发耗费时延,传输剩余时间Tl由服务类型设置的丢弃时间Td减去已经耗费时间得到Tl=Td-(Tc-Ts)。剩余时间越小说明数据包的实时性越高,被丢弃的可能性越大,将被优先转发,插入到转发队列中的位置最靠前。常规数据包依旧采取先到先服务的方式加入队列。转发策略如图1中伪代码所示[4]: 3 仿真实验 为了评测我们所设计的调度算法对网络性能的改进,我们基于Wolverine公司的GPSSH[5]队列仿真软件对此策略进行了模拟。 模型假设: 常规数据报文实时性要求较低,数据量较小,满足随机到达条件[6],到达间隔满足间隔为50ms的指数分布; 多媒体数据数据有实时性要求,时延有阀值要求,数据量大。多媒体数据具有自相似性质,我们采取概率近似的方式来进行仿真[7]。 数据包到达间隔函数如表1所示: 实验设置: 相对于简单的FIFO队列,通过进行排序的作用,有效的解决了实时数据报文发送时的延迟现象。在理想状态下,不同业务类型的数据包随机进入缓存区,时间参数如表2所示: ……000000X000X000XX00000000000X00X (注:X为多媒体报文,0为常规数据报文) 我们通过设置报文到达的周转时间,对仿真结果进行分析,主要将排序后的周转时间同排序前进行对比。初始周转时间如表3所示(表中数据为十进制): 经过排序后,如下所示: …….0000000000000000000000XXXXX 因为FIFO队列是按作业到达时间的先后而决定发送的先后,所以发送顺序为1,2,3,4。由此可见,经过排序后明显的第四个多媒体数据包周转时间提前了,而常规数据包文影响极少。有效减少了多媒体数据包在单队列发送中排序后减少了等待的时延,提高了整个系统的性能。排序后周转时间如表4所示: 上述时延性能提高的原因主要是进行了数据包的重新排序,调节发送顺序可以有效减少多媒体数据包在队列中等待的时间。 4 结论 本文通过对无线多跳网络中继节点FIFO队列中不同业务类型的数据包进行调度,将实时性要求较高的数据经过重新排序后优先发送,其余非实时性数据报文随后发送,从而使对实时性要求高的多媒体数据尽早发送,优化系统传输效率,改善服务质量。 从我们的仿真结果中可以看出,合理的数据调度可以使系统运行在相对优化的状态下。下一步,我们将主要研究双队列情况下引入转发比率来调节实时性数据包和常规数据包的转发比率,解决公平性问题,在提高多媒体数据传输的质量,减少时延和抖动的情况下,保证常规数据包不会被饿死。 参考文献 [1]Ashour M,Le-Ngoc T,End-to-end delay margin balancing approach for routinginmulti-classnetworks[J].Wireless Networks,2007,13(3):311-322. [2]Pantazis N,Vergados D,A survey on power control issues in wireless sensor networks[J],IEEE Communication Survey,2007,9(4):86-107. [3]印红云,王志良,王莉.网络中常用的队列管理方法比较[J].微计算机信息,2005,(21):3-4. [4]潘金贵.算法导论(第2版).机械工业出版社,2006. [5]齐欢.系统建模与仿真[M].清华大学出版社,2004. [6]苏驷希.通信网性能分析基础[M].北京邮电大学出版社,2006. 路由由两部分组成:一是网络状态信息的发布和搜集;二是根据网络状态信息寻找一条合适的路径。而路由算法则属于路由的第二部分,即通常所说的路由算法是建立在网络状态信息已知的假设之上的。与传统的路由算法不同的是QoS路由算法需要选择度量参数,QoS路由的度量参数包括带宽、代价、延迟、抖动、丢失率和跳数等。另外,QoS路由算法与传统路由算法目的也不同,QoS路由算法只需寻找满足QoS约束的可行路径,不像传统路由算法只求最“短”路径。 1 QoS路由问题 在一个QoS参数已知的网络中,在任意两网络节点间,寻找一条或多条满足各QoS约束的可行路径。该问题转变为数学模型则是在一个已知边上各权值的有向图G(V,E)(无向图可视为一种特殊的有向图)中寻找任意两顶点间一条或多条满足各权值约束的路径。图中顶点代表网络节点,边代表网络通信链路。V是网络节点集合,E是网络通信链路集合。根据各QoS参数特性,有可将QoS参数分为三类:凹性参数,加性参数,乘性参数。其中,各参数性质表1所示。 2 QoS路由算法分类及今后发展方向 由于以两个或两个以上的加性参数或乘性参数为约束的多QoS约束路由是NPC问题[1],故而在研究QoS路由算法时,人们提出了各种启发式算法,试图在多项式时间内尽可能正确求解QoS路由问题的结果。其中,大部分启发式算法应用了图论中的两点间最短距离算法,如Dijkstra、Bellman-Ford等。根据路由选择时使用的度量参数个数大致可将以往QoS路由算法分为单混合度量参数路由算法和多度量参数路由算法,另外,也有不少仿生算法应用到了QoS路由领域中。 2.1 单混合度量参数路由算法 单混合度量参数路由算法主要思想是将多个QoS参数通过一个线性或非线性函数表示成一个度量值,然后应用求最“短”路径算法最终近似解决QoS路由问题[2,3]。其理论依据是单个度量参数求解两节点间最短路径能在多项式时间内完成。由此,此类算法通常具备较低的计算复杂度,但它有两个主要缺陷:1)不能确定单混合度量参数的表达式,也就因此关于混合度量参数的表达式的研究也有不少,从简单的线性组合到复杂的非线性组合;2)因为路由选择时使用的是混合参数,这样不可避免地丢失了各QoS参数部分信息,最终导致计算结果未必正确,即混合参数值最小的路径未必满足各QoS参数要求。 2.2 多混合参数路由算法 独立看待各QoS参数,进行QoS路由选择。由于多个独立的QoS参数(带宽等凹性参数除外)路由问题是NP完全问题,故目前这方面研究主要通过以下手段简化问题和降低计算复杂度: 1)由于不同应用对QoS参数重视程度不一样,如IP电话对延迟要求较高,文件传输对丢包率要求较高登。所以可以从多个QoS参数选择最重要一个做为度量值进行路由选择[4],在满足该约束的路径集合中,再找出满足其它约束条件的路径。此类算法缺点是随着QoS约束参数增加,成功率也会相对降低。 2)通过缩小各QoS参数取值空间,在有限的QoS取值范围内进行QoS路由选择[5]。而缩小QoS参数取值空间的手段主要有参数量化和参数定界,即通过不同手段将QoS参数取值映射到一个有限的特定集合中去。由于各QoS参数取值个数有限,故原来的NPC问题转变为P问题。虽然随着映射集合规模的变小,计算复杂度会被降低,但成功率会相应变低。 2.3 仿生算法 人们根据自然界某些现象设计的一类算法被称为仿生算法,如根据蚂蚁寻路现象设计了蚁群算法;根据生物进化中优良基因更易存活下来,设计了遗传算法;根据热量扩散设计出了模拟退火算法等。此类算法已被引入QoS约束路由算法领域,但它们在解决QoS路由问题时依旧存在各自的不足,如蚁群算法[6]在计算过程中容易造成大量无效搜索或陷入局部最优问题;遗传算法[7]属于一种多目标优化算法,其本身在执行效率方面并不适合路由选择问题等。 2.4 QoS路由算法发展方向 在实际应用中,我们对QoS路由算法的要求主要有计算复杂度低,正确率高,可扩展性好。所以,今后QoS路由算法的研究始终是不会脱离这几点。在降低复杂度方面,可能更为有效地将节点控制和路由控制结合,预先处理各种网络参数和增加各网络参数的联系,从而设计出更为准确的度量表达式,降低计算复杂度和提高算法的正确性。随网络规模日益扩大,算法的可扩展性变得尤为重要,故分布式路由算法将会变得更为重要,当然源路由算法和分布式算法结合也可能是未来QoS路由算法的发展方向之一。而网络规模增大,导致网络参数信息的准确性降低,因此研究网络参数信息的准确性也将成为QoS路由算法领域又一研究重点。 3 结论 多QoS约束路由算法属于NPC问题,因此其仍旧具备广阔的研究空间。而在现实中,网络规模日益增大和复杂化,以及人们对网络服务要求也日益提高,解决多QoS约束路由问题也成为了现实需要,故而QoS路由算法的研究具备重大研究意义。而从理论算法研究到技术实现及实际应用仍将需要大量时间和工作。 摘要：QoS(Quality of Service)路由算法是解决QoS问题的关键,也是当前网络领域里的一大研究热点。QoS路由算法的主要目的是为接入的业务选择满足服务质量要求的传输路径,同时保证整个网络资源的有效利用。改文深入探讨了QoS路由问题的实质,并对以往的QoS路由算法进行了归纳总结。基于已有的QoS路由算法的研究,该文对QoS路由算法的发展方向进行了预测。 关键词：QoS路由,多约束,NPC(Non-deterministic Polynomial complete)问题,路由算法 参考文献 [1]Zheng Wang,Crowcroft J.Quality-of-service routing for supporting multimedia applications[J].IEEE Journal on Selected Areas in Commu nications,1996,7(14):148-154. [2]Cui Yong,Xu Ke,Wu Jianping,et al.Precomputation for finding paths with two additive weights[J].In International Conference on Communi cations,2003,1:636-640. [3]Kunavut K,Sanguankotchakorn T.Multi-Constrained Path(MCP)QoS routing in OLSR based on multiple additive QoS metrics[J].Commu nications and Information Technologies(ISCIT),2010International Symposium,2010:226-231. [4]Orda A.Routing with end to end QoS guarantees in broadband networks[C].INFOCOM'98.Seventeenth Annual Joint Conference of the IEEE Computer and Communications Societies,1998,1:27-34. [5]Chen Shigang,Song Meongchul,Sahni Sartaj.Two techniques for fast computation of constrained shortest paths[J].IEEE/ACM Transactions on Networking,2008,16(1):105-114. [6]林娜,邵志学.基于蚁群算法的多路径QoS路由算法研究[J].Journal of Shenyang Aerospace University,2011(1). 文献[4]提出的基于遗传算法的Qo S路由,该算法选择带宽、时延、丢包率作为约束参数,寻找最优路径,但是未对网络资源及负载均衡优化,且未考虑过算法的收敛性。文献[5]提出的改进遗传算法以网络消耗和负载均衡分布为目标函数,最终使网络达到负载均衡,降低了网络的拥塞,但是并未考虑算法的过早收敛以及收敛速度。 针对现有算法的问题,本文通过对遗传算法适应度函数和遗传算子的改进,使得算法最终有较快的收敛速度,同时避免早收敛,提高Qo S满意率。 1网络模型以及数学描述 Qo S路由的网络可以描述为图G( V,E) ,在满足给定约束的条件下,寻找从源服务节点s到目的服务节点d的一条最优服务路径。对于路径P( s,d) ,在Qo S路由选择时主要考虑的参数有网络链路带宽B、时延D、花费C、丢包率L。20节点网络拓扑如图1所示。 s到d之间的路径带宽满足 式中: B为要求链路带宽 。 而时延满足 式中: D为要求最大时延。丢包率满足 式中: L为要求的最大丢包率。花费满足 本文就是在带宽、时延、丢包率约束条件下,寻找一条最优服务路径,同时链路花费少、收敛于最优路径速度快,且有较高的Qo S满意率。 2基于遗传算法的Qo S路由 2. 1编码方法以及群体初始化 本文采用较为简单的编码方式,根据网络的拓扑,采用深度优先搜索算法找到一条从源服务节点到目的服务节点的路径。在遗传操作中无论是交叉还是变异,都无需编码和解码了。在种群初始化时,先做一个预处理,在网络中将不满足带宽B要求的链路先删除掉,得到新的拓扑图,如若得到的拓扑图是非连通的,且源节点和目的节点不在同一连通子图里则无法提供服务。本文假设经过处理后的图为连通的,由于深度优先搜索算法是根据邻接矩阵搜索的,所以从源节点开始每搜完一个节点后就随机选取当前节点下的一个邻接点,且此节点并未被搜索过, 然后再搜索,直到搜索到目的节点而完成单次寻找路径的过程,重复此过程直到达到种群规模。 2. 2适应度函数的设计 适应度函数的设计是遗传算法的关键部分,直接影响到算法收敛的速度,以及能否找到优化解。本论文设计的适应度函数为 式中: ψ( P( s,d) ) 是一个惩罚函数,当路径上的时延或者丢失率不满足要求时,它的值会相应减少,且有 在式( 5 ) 中, C是一个常数 。D ( B ) 代表了选择当前路径之后剩下可用带宽偏离程度即链路负载均衡度, N L为当前路径中的链路数目 。 如果选择的路径D ( B ) 越小, 说明链路负载均衡能力越好,这样可以有效降低网络的拥塞程度,那么全局负载就会越均衡 。 系数A , B是一个为了平衡分母下每个优化目标的影响 。 如果一个优化目标过大会使得另一个优化目标被忽略 。 而式( 5) 中的指数函数是为了在算法后期拉开个体之间的差异,从而加快收敛速度,最终找到最优路径。 2. 3选择操作 选择算子的优劣直接影响到算法的收敛性,文献[6] 提出的基于切断的轮盘赌选择的方式来单独选择最优个体,同时在选定个体后相应减少其比例的大小,重复这样的操作直到个体达到种群规模为止,但是基于赌轮的选择本身就存在较大的随机误差,于是本文对文献[6]提出的基于切断的轮盘赌选择进一步改进为通过多轮盘赌选择, 并且为了增加选择的多样性对比例的减少也做了改进。 这样的选择操作进一步减少了随机误差,增大了最优个体被保留的可能性,同时又不失种群的多样性。 假设种群大小为M,计算所有个体选择概率Pi,并将计算出的概率根据其大小分布在[0,1]上,则在[0,1]上存在着M个区间,这M个区间为A1,A2,…,AM。然后开始M × N多轮盘赌选择,M为种群数目,N代表在每一次选择个体时都要进行轮盘赌N次,并统计这N次中落在M个区间中每个区间的次数,选择次数最大的个体为本轮选择的个体,种群数目有M个,则重复M次从而得到M个个体。若出现落入区间最大次数相同的个体,则选择概率大的。初始时根据每个个体适应度计算其选择概率,即为 ,则具体的算法步骤如下: 1 ) 计算比例 ,并按照上述的方式分布在[ 0 , 1 ]区间内 。 2) 进行N次轮盘赌选择,并统计落入每个区间的次数。选择区间落入次数最多的一个个体t( t ∈[1,M]) , 判断Pt,如果Pt- 1 / M ≤ 0 ,则令Pt= Pt/2 ,否则Pt= Pt- 1 / M 。 3) 若选出的个体数目达到种群大小M,则结束。否则转到1) 继续选择个体。 2. 4交叉操作 遗传算法中交叉算子模拟自然界生物的杂交过程对个体进行交叉操作,不断产生新的个体,增加种群的多样性。在路由寻址的应用中体现了其较强的全局搜索能力, 它扩展了求解空间,并为寻找到最优路径发挥着重要作用。本文的交叉算子实现较为简单,具体过程如下: 1) 根据选择概率随机选择父代中参与交叉操作的链路Px和Py,随机选择Px和Py除源节点和目的节点的共同节点作为杂交点。如果没有共同节点,则随机选择交叉节点。 2) 交换杂交点后的所有节点得到新的子女个体。如果新的子女个体在节点之间不存在链路连接,利用上文提及的根据邻接矩阵使用随机化的深度优先搜索算法寻找节点之间的链路。如若新个体中存在环路,则删除形成环路。 2. 5变异操作 种群的变异是为了使物种提高自身的适应能力,并存活下来,使得群体质量上升。但是变异也存在优劣之差,优良的变异使得物种适应环境并延续后代,较差的变异会直接导致物种被大自然淘汰。为了使得物种适应环境的变化,朝着好的方向变异。本文提出了一种新的变异算子,其具体的思想为在选择后的当前种群中,优秀的个体即为较高适应度的个体,必然是某些优秀基因的存在导致的,而本文对优秀基因的判别是统计在优秀个体中此基因出现次数的和。某种基因在当代种群的优秀个体中出现的次数越多,说明其越是优秀,变异的可能性就会越低, 相反在优秀个体中没有出现的或者是统计次数较低的基因,其变异的可能性就会很大。这样个体变异就会朝着好的方向发展,可以提高算法收敛速度。具体的算法步骤如下: 1) 执行完选择操作后,统计当前种群中所有链路个体中除源节点和目的节点以外经过的每个相同节点各自出现的次数和,这里把经过选择后当前链路种群中适应度值大于平均适应度值的链路定义为优秀链路。将当前种群中节点出现次数排在前N位的节点定义为优秀节点基因,其中N可表示为 2) 在经过交叉后的链路群体中依照变异概率随机地选择一个个体链路Px,然后从个体链路中随机地选择非优秀基因进行变异操作。具体的变异操作过程为在链路中随机地选取一个非优秀基因g。以g为起点,在链路Px上沿着g向前向后移动,直到移动到的节点基因为优秀节点基因为止。随机选择使用花费Cost、链路剩余带宽的倒数1 /B,或者时延D之一为链路的参数,以A* 算法求出节点g之前向前向后移动到的优秀节点基因之间的路径。 最后,将此路径替换个体链路Px中最开始的链路,如果替换后有回路,则将其删除。 3实验仿真 本文利用含有20个节点的图1进行实验仿真。设置每条链路的参数,其中链路的带宽在1 ~10之间,链路的时延在10 ~100之间,链路的丢失率在0. 01 ~ 0. 1之间,花费在1 ~5之间。用户要求的带宽为2,时延小于200,丢失率小于0.2。且本文路由的源节点为1,目的节点为20。 1) 验证本文提出的改进遗传算法的可行性。本文首先利用深度优先搜索算法穷举出两点间所有的可达路径, 并比较它们之间的适应度值,求出最大适应度值的路径, 即本文所要求的最佳路径,其为1→4→7→14→20,其适应度为13. 06。本文算法的遗传迭代过程如图2所示。 从图2可以看出,在本算法进行到第5代时就收敛到全局最优解1→4→7→14→20,并且收敛过程中每一代的丢失率与时延变化如图3、图4所示。 从图3和图4可以看出,求解的最优路径丢失率和时延均满足要求时延,因此本文提出的改进遗传算法用于寻找一条满足时延、丢失率、带宽的最优路径是可行的。 2) 与传统遗传算法相比。验证本文提出的改进遗传算法较之传统的遗传算法在收敛速度和Qo S满意率方面的优势。其中定义收敛速度为每次实验成功迭代到全局最优解的代数的累积和与成功实验次数总和之比,定义Qo S满意率为每次实验成功找到全局最优解的累计次数与实验次数总和之比。本次实验的两个算法具有相同的初始环境,即算法的种群规模均为50,迭代次数均为20, 且两个算法均实验50次,每次的初始种群均是相同的,使用的适应度函数均为本文提出的适应度函数。具体的实验数据比较如表1所示。 从表1的数据可以看出,在收敛速度上,改进的遗传算法平均在迭代的第3代即可收敛到最优解,而传统的遗传算法平均在迭代的4. 7代才可以收敛到最优解,故改进的遗传算法在收敛速度上有一定的提升。在Qo S满意率方面,改进遗传算法的满意率为86% ,大于传统遗传算法70% 的满意率,也就是表明改进的遗传算法可收敛到最优解的概率明显大于传统的遗传算法。 4总结 在多约束Qo S路由网络中,本文提出的改进遗传算法将带宽、时延、丢失率作为约束条件,改进了适应度公式和遗传操作。实验仿真表明该算法是可行的,并能在一定程度上克服传统的遗传算法缺点,提高收敛速度,有效避免过早收敛,提高Qo S满意率。 摘要：遗传算法良好的全局搜索能力使其被广泛地应用于网络中多约束QoS路由寻址,并取得了较好的成果。然而大部分应用于多约束QoS寻址的改进遗传算法存在无法有效利用网络资源使得网络拥塞、网络过早收敛陷入局部最优解,以及过慢结束的缺点。针对上述问题,对传统遗传算法中的适应度函数和遗传算子做出相应的改进,并通过实验验证提出改进遗传算法。最终,仿真实验表明该算法是可行的,并能在一定程度上克服传统遗传算法的缺点,提高收敛速度,有效避免过早收敛,提高QoS满意率。 BP神经网络通过学习和推理这两个过程,能够修正各个连接途径的权值,无限地逼近样本值,不断修正结果,并且对相关信息实施处理[3 - 4]。BP神经网络在学习、分类和优化上有优势,有较强的局部搜索能力。蚁群算法( Ant Colony Algorithm,AC) 是蚁群能够找到一条从巢穴到食物的最短路径的方法[5],蚁群算法的优点是具有较强的鲁棒性、分布式计算、易于融合其他算法,同时具有较强的全局搜索能力,但是收敛速度慢、易陷入局部最小点。 本文结合BP神经网络和蚁群算法的优点,提出了一种新型的神经网络蚁群算法( Neural Network Ant Colony Algorithm,NNAC) 。结合BP神经网络局部搜索的优势和蚁群算法全局搜索的优势,同时BP神经网络还能弥补蚁群算法易陷入局部最小点的不足。 1 Qo S组播路由网络模型 在Qo S组播路由网络模型中,通常用加权图G = ( V,E) 表示通信网络,V表示节点集,E表示链路集,节点数和链路数分别由V和E表示[6 - 7]。同一对节点间的链路数≤1 的网络模型如图1 所示。 R+、R*分别表示正实数集和非负实数集。数据由源节点s ∈ V传送到目的节点集D V - { s} ,组播组M = { s} ∪ D 。定义组播树T = ( VT,ET) ,组播树T由源节点传送到目的节点的路径为l( s,d) ,则对于任意链路e ∈E可定义以下Qo S参数: 时延函数 带宽函数 时延抖动函数 包丢失率函数 链路代价函数 求解多约束Qo S组播路由优化问题是指寻找从源节点到目的节点的组播树T ,并且满足Qo S参数的约束条件 式中: Dp,Bp,Jp,Lp分别为时延、带宽、时延抖动、包丢失率约束量。 2 NNAC算法 结合BP神经网络局部搜索的优势和蚁群算法全局搜索的优势,进行Qo S组播路由算法的设计,提出了一种新型的神经网络蚁群算法( NNAC)[8 - 10]。 2. 1 NNAC算法实现步骤 NNAC算法步骤为: Step1: 确定BP神经网络结构,给定BP神经网络权值和阈值; 对蚁群算法初始化设置,包括多路径信息强度、蚂蚁数量。 Step2: 计算各个路径的适应度。 Step3: 从源节点出发,通过赌轮规则选择合适的路径,进行分泌物强度调整。 Step4: 将收集的参数作为BP神经网络初始权值和阈值,并对BP神经网络进行训练。 Step5: 应用BP神经网络在当前路径中找到更优解,如果有更优解则替代原有路径。 Step6: 计算各组播树的代价,判断大部分路径是否收敛于同一组播树,收敛则为最优路径,退出程序; 否则,只保留最小代价的组播树,转到Step7。 Step7: 返回源节点,转到Step2。 2. 2 初始化 初始化中需要设定BP神经网络的权值和阈值para = { wi} ,wi为N个较小的随机值,N个随机值组成集合Iwi= { wijwij∈[- l,l]} ,i = 1,2,…,N; j = 1,2,…,N ,设wi对应的信息素为 τij,初始时刻、信息素相等,上限为 τ0= τmax。 2. 3 路径适应度 NNAC算法依据适应度函数选取路径[8],选用的适应度函数为 式中: phePj表示路径Pj的分泌物强度,phePj值越大,表明路径Pj被选择的概率越大。 2. 4 信息调整 分泌物强度调整函数为 式中: ω 为常量参数; l为链路代价。每当蚁群走完一条路径后,需要对所有路径的分泌物挥发性进行调整[9 - 10] 式中: η 为分泌物挥发度; α 为各个路径的初始信息强度。 2. 5 BP网络训练和调整 BP神经网络采用包括输入层、隐含层、输出层的网络结构[11 - 13]。在BP神经网络训练时,并不知道准确的输出结果,将Step3 中分泌物强度phePj最大的路径和其他路径进行比较,来指导BP神经网络。同时,BP神经网络采用附加动量法进行训练,当修正的权值对误差的影响较大时,应放弃新权值,并停止动量; 当新的误差变化率超过设定的最大误差变化率值后,应放弃对权值的变化。最大误差变化率一般设置为1. 04。附加动量法判断公式为 式中: mc为动量因子,取0. 95; k为训练次数。 设BP神经网络输入向量为X = [x1,x2,…,xn]T,输出向量为Y = [y1,y2,…,yl]T,期望输出为D = [d1,d2,…,dl]T。 BP神经网络的目的就是求误差能量E的最小值,应用BP神经网络在当前路径中找到更优解的方程为 式中: cij表示链路代价; dij表示时延; vij表示神经元的输出; λ → ∞ ; 能量函数u1项表示代价和时延的最小值; 能量函数u2项表示每个节点的出、入边数相等时的最小值,保证从源节点到目的节点为一完整路径。 3 算法仿真分析 首先对NNAC算法全局最小值的寻找进行仿真[14]。由于该算法采用附加动量的BP神经网络进行了训练,所以在附加动量的驱动下,可以避免局部极小值的干扰,从而最终寻找到全局最小值,结果如图2 所示。 对NNAC算法进行仿真分析的网络拓扑结构采用8节点网络结构,如图3 所示。拓扑结构图中的源节点为s,目的节点为a,c,e,f,图中各个边上的数值代表延时和代价,用( Dp,CP) 表示,( Dp,CP) 的数值是随机的,BP神经网络误差能量的公式中的u1= 1 000 ,u2= 200 。 利用MATLAB编写NNAC算法程序,得到最优组播树如图4 所示。通过图4 可知,总延时为35,总代价费用为21。 为了进一步分析NNAC算法的性能,引入AC算法,通过两种算法进行最优组播树的寻找成功率进行对比分析,通过实验可以得到如表1 所示结果。 % 通过表1 可以看出,两种算法在指定的网络环境下,完成150 个度约束组播路由路径时,NNAC算法在进行最优组播树的寻找成功率上高于AC算法。因为NNAC算法融合了BP神经网络局部搜索的优势,克服了易陷入局部最小点的不足。 4 结论 接纳控制作为一种预防性流量控制方案, 是实现QoS保证的重要手段。区别于PBAC算法, 基于测量的QoS接纳控制算法MBAC (Measurement-based Admission Control) 通过对实际到达的网络业务流进行测量来做出QoS决策。因此, 这类算法能够提高网络带宽的利用率。 1 多阶段过滤算法MF 多级过滤MF算法的思想是使用多个stage来找出网络中的主要流, 从而在内存有限的约束条件下, 将系统的有限资源用于关注网络中的主要流。MF算法能够在有限的内存使用量下, 提高网络流量采集算法的准确率。网络中的许多设备如路由器, 其内存远小于网络中的流数目, 因此MF算法有着重要的意义。 定义1 一个Flow ID是一个形如 (S, D) 二元序偶, 其中S表示源地址, D表示目标地址。 典型的MF算法如图1所示。MF算法使用多个stage来过滤网络流。一个stage由多个桶 (bucket) 组成。每个桶使用Flow ID作为索引, 在桶中累计流大小。不同的stage使用相互独立的hash函数来计算流所对应的桶的位置, 因此相同Flow ID在不同的stage中将会有大的概率处于不同序号的桶中。 MF算法使用过滤时段来过滤网络中的流。一个过滤时段是一段连续时间, 过滤时段结束后MF算法将对网络中的流进行过滤, 选出候选的流。在以后的采集过程中, 采集算法仅对这些候选的流进行统计和采集。 MF算法在一个过滤时段结束后对stage进行扫描, 若一个流被采集算法接纳, 那么其Flow ID在所有stage中的所对应的桶的流大小至少为T字节。即T为判定是否接纳流的一个阈值。 在网络业务流突发的条件下, 业务量的突发特性使得网络中的流数目远大于一个stage所能提供的桶数目。因此, 不同的流将有可能被hash函数映射到同一个桶中。传统的基于采样的单级过滤算法会带来两个问题: (1) 因为小的流映射到大的流所在的桶, 从而导致小的流被错误接纳; (2) 由于一些小的流被映射到同一个桶中, 从而使得该桶的流大小大于T, 导致小的流被错误的接纳。而MF算法采用多个stage过滤的方法, 能够消除传统基于单级过滤的抽样采集算法带来的上述两个问题。 当可用内存为M时, MF算法的平均错误率为1/M, 优于传统基于采样的采集算法1/姨M的平均错误率。 2 基于多级过滤的QoS接纳控制算法 2.1 通信量模型 现实网络中的流数目远大于网络测量设备所能提供的资源。文献[6]对一对端到端的主机在一个小时内的网络流量进行测量, 得到的网络流数在80万到170万之间。保留所有网络流的状态信息对于网络测量来说是不现实的。因此, 如果能在资源有限的情况下迅速找出大的网络流, 将提高QoS接纳控制算法的效率。 考虑一基于事件驱动的聚集类QoS接纳控制算法。核心网络的入口节点首先对到达的通信量进行分类。分类的标准是通信量的QoS需求, 对于多媒体业务来说, 通常为端到端的时延和丢包率。与传统的接纳控制算法不同, 本文对于通信量的统计特征不作任何假设。 定义2令ai表示聚集类i到达传输队列这一事件, Ai表示到达传输队列的所有流量, 则有: 定义3令表示在第n个事件时刻聚集类i所被丢弃的包数, 则在第n个事件时刻已进入传输队列的流数Riin (n) 定义为: 定义4聚集类i的时延Di (n) 定义为: 设现实网络中的通信量可划分为N个聚集类, 则第i个聚集类的QoS要求可表示为: 其中, di表示时延限度, εi表示丢包率。 下面的讨论基于区分服务的等价类QoS接纳控制机制。根据用户的不同需求, 网络服务QoS保障可按优先级作一排序。为了讨论方便, 假定已经将QoS保障的优先级由高到低做了划分: D={D1, D2…, DN}。在第n个事件时刻, 区分服务的优先级可表述为: 其中, λcomp k为优先级比对因子。对于D来说, 总有λcomp k≥1, 以保证QoS服务的优先级。由式5可得:DN (n) = () D1 (n) , 为了确定当前的QoS保障是否得到满足, 我们引用文献[7]对聚集类时延权重的定义, 并在此定义的基础上提出基于MF的QoS接纳算法。 令mi=且m1=1, 给出聚集类i的时延权重定义如下: 定义5聚集类i的时延权重D*i (n) 满足 定理1若所有聚集类的QoS要求均得到满足, 对于D*有: 2.2 基于MF的QoS接纳控制算法 MFAC算法着眼于当网络通信量的QoS要求无法得到全部满足时的QoS策略的实施。当高优先级的聚集类的QoS服务无法满足时, MFAC算法首先拒绝接纳低优先级聚集类中的大的网络流。从而减轻网络负载, 以确保区分服务域内高优先级的聚集类的QoS性能。 令D* (n) =表示时延权重均值, 定义MFAC算法的服务质量误差Ti (n) 如下。 定义6 MFAC算法的服务质量误差Ti (n) 满足: 因此, 聚集类i的QoS时延要求可表示为:Ti<δi。其中, δi为聚集类i所能接受的服务质量误差的下限。该表示等价于表达式 (4) 。可以为每个聚集类i定义服务质量误差。 定理2若所有聚集类的QoS要求均能得到满足, 对于服务质量误差Ti (n) , 有: 证明:由定理1, MFAC算法以Δt (n) 为间隔时间, 对于每个聚集类i计算其服务质量误差Ti, 若所有的Ti满足式8。则无需实施拒绝接纳策略。否则, 需要拒绝低优先级聚集类中的大网络流。 为了实施QoS策略, 我们在对文献[4]提出的MF算法的基础上, 提出扩展的Flow ID。 定义7一个扩展的Flow ID是一个形如 (S, D, i) 的三元组。其中S表示源地址, D表示目标地址, i为该流所属的聚集类。 由2.1节可知, i可由核心网络的入口节点给出。 上述修改, 使得MFAC算法的每个stage在记录流大小的同时, 记录了网络流所属的聚集类。为拒绝接纳策略提供了依据。 MFAC算法描述如下: (1) 事件n到达时刻, 计算所有的Ti, 对于每个聚集类, 检查是否满足表达式 (8) 。若是, 则转 (6) 。否则, 转 (2) ; (2) 对于所有聚集类计算其服务质量误差Ti, 检查其Ti是否满足:Ti<δi。将所有不满足的QoS服务质量误差的聚集类按优先级由高至低放入队列q中; (3) 依次扫描q中的聚集类i, 检查所有QoS优先级大于i的聚集类的网络流。查看其在所有的stage中的流大小是否大于流许可门限sk, i 聚集类i的流许可门限si可以采用下述方式计算, si=βC+ (1-β) riΔt。其中, C为网络带宽容量, β为权重因子 (0≤β≤1) , ri为聚集类i的最高服务速率, Δt (n) 表示第n和第n+1个事件的间隔。若β=0, 则MFAC算法退化为无优先级的QoS接纳控制算法。 MFAC算法在网络负载重时, 需要通过拒绝接纳策略来保障高优先级聚集类的服务质量, 因此算法应当具有较好的收敛性, 在实施拒绝策略的同时, 不会引起全局性能的抖动。 下面的讨论, 考虑MFAC在最坏情况下的算法的收敛性。 定理3设网络当前共有N个聚集类, 在n事件到达时刻, 若聚集类k的QoS无法得到满足。 那么, MFAC算法最多需要拒绝, (N-k) C/Nsmin, 1≤k≤N个网络流。 其中, C为网络带宽, smin=min{s1, s2, …, sN}。 考虑最坏情况, k=1时, MFAC算法最多需要拒绝的网络流数目为 (N-k) C/Nsmin。当N较大时, 需要拒绝的流数接近于C/smin。 相关研究指出, 占用网络带宽的网络流主要为流量大的网络流。因此, MFAC算法通常只需拒绝少量大的网络流, 即能收敛。算法的快速收敛性, 能够避免因为实施拒绝接纳的策略, 而引起全局性能的抖动。同时, MFAC算法仅仅拒绝接纳聚集类中大的网络流, 而不是拒绝整个聚集类, 从而与传统的接纳控制算法相比, 粒度更细, 能够提供更好的QoS服务质量。 3 结束语 与传统的接纳控制算法相比, 该算法保留了MF算法使用较少状态快速识别出网络中大的网络流的特点, 通过拒绝接纳来保证网络负载重情况下的区分服务域的服务质量。理论分析表明该算法具有快速的收敛性, 同时与传统的CAC算法相比, 粒度更细。由于算法不对网络流的统计特征做任何假设, 具有更好的扩展性, 能够适应网络业务的变化。 MFAC算法假定DiffServ域的入口节点能够对网络时延的变化做出快速的反应, 这点在LAN的环境下是合理的。然而, 在WAN等大时滞网络环境下, MFAC算法可能无法对网络时延的变化做出快速反应, 这是下一步研究的方向。 参考文献 [1]JAMIN S, DANZIG P, SCHENKER S, et al.A Measurement-based Admission Control Algorithm for Integrated Services Packet Net-works.IEEE/ACM Trans.on Networking, 1997, 5 (1) :56-70. [2]BRESLAU L, JAMIN S, SCHENKER S.Commenton the Performance of Measurement-based Admission Control Algorithm.Proceeding of IEEE INFOCOM, 2000:1233-1242. [3]BRESLAU L, KNIGHTLY E, SHENKER S, etc al.End-point admission control:Architectural issues and performance.Proceeding of ACM SIGCOMM’00, Stockholm, Sweden, 2000:57-69. [4]FELDMAN A, GREENBERG A, LUND C.etc.Deriving Traffic De-manDiffServ for Operational IP Networks:Methodology an Experi-ence.IEEE/ACM Trans.on Networking, 2001, 9 (3) :265-279. [5]CRISTIAN.E.and GEORGE.V.New Directions in Traffic Measure-ment and Accounting:Focusing on the Elephants, Ignoring the Mice.ACM Transactions on Computer Systems, 2002, 21 (3) :270-313.QoS调度算法 篇4
多QoS约束路由算法综述 篇5
QoS调度算法 篇6
一种新的QoS组播路由算法 篇7
QoS调度算法 篇8