《计算机网络》PPT电子课件教案-第十一章服务质量控制.ppt

第十一章 服务质量控制,11.1 概述 以提高网络资源的利用率、为用户提供更高服务质量(quality of service,qos)为目标的研究领域目前极具活力。网络资源是有限的,不能满足所有的业务对qos的需求,qos控制机制就是通过对网络资源的合理分配来尽量满足各种业务对它的需求。,早期的许多工作都源于资源预留协议(rsvp, resource reservation protocol),目前已经提出许多qos控制机制,包括internet工程任务组(internet engineering task force,ietf)提出的集成服务(intserv)和区分服务(diffserv)体系结构、分组调度算法等。,11.1.1 分层模型,cbr:constant bit rate vbr:variable bit rate ubr:unspecified bit rate frf:frame relay forum tos:type of service diff-serv:differentiated service rtp:real-time transport protocol rtcp:rtp control protocol rtsp:real time streaming protocol qos控制技术在不同 层上采用不同的方式,11.1.2 服务质量参数定义,ip qos的最终目的是要为各种业务（包括数据、图像、多媒体与语音业务等）提供可靠的端到端的服务质量保证，而实现这一目标的前提是要对各种qos参数进行清楚地定义: （1）业务可用性：用于表明网络是否可以使用的参数。如果一个端到端ip网络业务的包丢失率低于一定的门限值，,则认为该端到端ip网络业务是可用的，否则就是 不可用的。 （2） ip分组传输时延：ip分组传输时延定义为穿过一个或多个网络段，传送ip分组所经历的时间(不考虑传送成功与否)。,（3） ip分组丢失率：ip分组丢失率是丢失的ip分组传送结果与所有ip分组的比值。 （4） ip时延变化(即抖动)：连续传递时，分组与分组之间的时间延迟的变化。,（5） ip分组误差率：ip分组误差率是错误ip分组传送结果与成功ip分组传送结果加错误ip分组传送之和的比值。 （6） 虚假ip分组率：一个出口测量点的虚假ip分组率指在一个特定时间间隔内在测量点上观测到的虚假ip分组数量除以该时间间隔。,（7）流量参数 目前定义了两种类型的吞吐量，一是根据成功传递的ip分组的速率，二是根据传递的这些分组中的字节数： ip分组吞吐量：一个出口测量点上的ip分组吞吐量等于一个特定时间间隔内在该测量点上观测到的所有成功ip分组数量除以该时间间隔。,基于字节的ip分组吞吐量：一个出口测量点的基于字节ip分组吞吐量等于一个特定时间间隔内在该测量点上观测到的所有成功ip分组中的所有字节数量除以该时间间隔。,11.2 集成服务和区分服务,11.2.1 从集成服务到区分服务的发展 1 intserv简介 集成服务体系结构(integrated services architecture,isa)的目的是在基于ip的互联网上能够提供qos支持,isa的主要设计问题是在发生拥塞时如何共享可用的网络容量。isa是一个总的体系结构,使用以下功能来管理拥塞和提供qos传输：,（1）容许控制 （2）路由选择算法 （3）排队规则 （4）丢弃策略,intserv依靠资源预留协议rsvp逐跳(hop-by-hop)地建立(set up)或拆除(tear down)每个流的资源预留软状态(soft state);依靠接纳控制(admission control,也称准入控制)决定链路或网络结点是否有足够的资源满足qos请求;依靠传输控制(traffic control)将ip分组分类成传输流,并根据每个流的状态对分组的传输实施qos路由(routing)、传输调度(scheduling)等控制。,intserv是基于流的(per-flow)、状态相关的(stateful)体系结构。 与状态无关(stateless)的体系结构(原有的ip网络体系结构和新近提出的ip网络的diffserv标准)相比,intserv提供的服务具有更高的灵活性(flexibity)和更好的服务级别保证。,2 intserv的局限性 集成服务的优点在于以下两方面。 （1）能够提供绝对有保证的qos （2）rsvp协议能够支持组播环境,rsvp和intserv在整个internet网络应用,存在如下的根本局限： （1）状态信息数与流的个数成正比,这就需要在路由器中占有很大的存储空间,因此,这种模型不具有扩展性; （2）对路由器的要求高,所有的路由器必须实现rsvp、接纳控制、mf分类和分组调度;,（3）改服务不适合于短生存期的数据流,因为对短生存期的数据流来说,资源预留所占的开销太大,降低了网络利用率； （4）许多应用需要某种形式的qos,但是无法使用intserv模型来表达qos请求； （5）必要的策略控制(policy control)和价格(pricing)机制,如访问控制(access conrol)、鉴别(authentication)、记帐(accounting)等,目前尚处于发展阶段,无法付诸应用。,11.2.2 区分服务的体系结构,区分服务（diffserv）。区分服务是由集成服务发展而来的,它采用了集成服务中的分类标准,抛弃了分组流沿路结点上的资源预留。其实施特点是采用聚合的机制将具有相同特性的若干业务流聚合起来，为整个聚合流提供服务，而不再面向单个业务流。基本实现方法如下： （1）简化网络内部结点的服务机制 （2）聚合网络内部核心路由器的服务对象,区分服务体系结构的框架如图：,1 ds区域与ds区 ds区域是由一些相连的结点构成的集合,它们遵循统一的服务提供策略并实现一致的phb组。ds区域有明确定义的边界,边界由边界结点(boundary node)构成。边界结点连通ds区域和非ds区域(或其他ds区域), 根据不同的数据流传输方向，边界结点可以分为入口结点和出口结点。,diffserv区（region）则是由连续的ds区域构成。一个ds区内的ds区域可以支持不同的phb组，并且各自区域的dscp到phb的映射函数也可能不相同。,2 区分服务标记域与区分服务标记dscp ip报头部的区分服务标记域（ds field）是ds区域边界结点和内部结点传输流聚集信息的媒介，是内部核心路由器转发报文的依据，是连接报文与转发服务（phb）的桥梁，也是边界结点与其它ds区域根据tca进行调节的依据。如图所示，其中dscp（6bit）即为区分服务标记:,边界结点要根据tca对入域(或出域)流进行分类和调节,以保证输入(或输出)流满足tca中规定的规格,并将其归入某个行为聚集、标记相应的dscp值。逻辑上可以分为两个模块：分类器（classifier）和调节器（conditioner），如图 ：,分类器根据数据分组头部的某些域（如dscp或多域五元组）对数据分组进行分类。目前定义了两种类型的分类器： 行为聚集（behavior aggregate，ba）分类器 多域（multi-field，mf）分类器 在逻辑上，调节器可分为计量器（meter）、标记器（marker）、整形器（sharper）和丢分组器（dropper）。,4 每跳行为phb、phb组与phb组簇 每跳行为phb是一个ds结点调度转发特定流聚集这一行为的外特性描述。phb本质上描述的就是单个结点为特定流聚集分配资源的方式。 多个phb由于彼此关系关系密切(如具有按顺序排列的相对丢弃优先级)而必须同时定义,则在实现时就构成一个phb组。,phb组是区分服务体系中的基本定义或实现模块,单个phb是特殊的phb组。若干phb组有相似构造(即各组内的phb间有相似关系),因而这些phb组可以同时定义,则称其属于同一phb组簇。,目前已标准化的phb有: 加速型（expedited forwarding，ef） 确保型（assured forwarding，af） 允许丢失的加速型efd(expedited forwarding with dropping) 默认型be(best effort) 准尽量做好 lbe(lower than best effort),类选择phb cs是diffserv向后兼容rfc1812中的ip优先级队列的产物。 协同phb组phb-i(interoperability phb group)的提出既有创意又可有广泛应用。其思路根据是: （1）phb描述的实质只有两点(延迟及丢失率)。 （2）与丢失、延迟相对应的,所有应用需求都可以归结为一定的级别的重要性(importance)与紧迫性(urgency),简记为i级与u级。,11.2.3 区分服务的技术特点,（1）层次化结构 （2）总体集中控制策略(与intserv分布式控制相对照) （3）利用面向对象的模块化思想与封装思想,增强了灵活性与通用性 （4）不影响路由,11.2.4 mpls支持的区分服务,在mpls网络中,标记交换路径lsp(label switching path)建立之后,核心路由器只根据shim头标中的标记来区分分组所属的fec并进行转发服务,不对ip报头进行解析。而标识区分服务级别的ds码点位于ip,报头中,在mpls网络中无法体现,因此必须将由ds域所标识的dscp正确映射到mpls头标中,才能使网络中的标记交换路由器lsr(label switching router)正确识别ip分组的区分服务等级,提供相应的转发服务,实现对区分服务的支持。,ip分组要在mpls网络中实现区分服务需要分为以下两种情况。 （1）e-lsp(exp-infered-psc lsp) 当网络需要提供服务级别少于8个,即不同的ba不多于8个时,路由器建立称为e-lsp的通道。之所以称它为e-lsp,是因为此类lsp中转发的分组属于那个psc(phb scheduling class,phb调度类)完全由分组的exp域的值决定。,在e-lsp中,分组的ds码点与exp建立完全映射,仅由exp域就可以表达区分服务的信息,如丢弃优先级和排队调度处理等。 沿途的lsr将根据expphb映射表,确定ip分组相应的区分服务等级,（2）l-lsp(label-only-infered-psc lsp) 在l-lsp中lsr将根据分组shim头标中的标记值和exp域的值综合决定对分组采用的区分服务,使较多等级的区分服务在mpls网络中得以实现。这样的lsp之所以被称为l-lsp是因为ip分组所属的psc完全由标记来决定,而不需要任何其他信息,比如exp域的值等。 在l-lsp中传送分组时,对分组要进行如下的处理。, 根据分组标记的内容确定该分组属于那个psc,并建立此psc中不同服务等级与exp域值的映射表。 lsr根据(psc,exp)/phb的映射表,确定对此分组采用的phb,如调度处理和丢弃优先级等,达到区分服务的目的。 转发分组时,将根据以上映射表的逆映射,对转发分组的exp域写入相应值,并由psc对输出分组加上标记。,(psc,exp)phb映射表,11.3 服务质量策略控制,11.3.1 策略控制的必要性 “策略”这个词在网络上是一个广义的概念,它是指网络上设备选择的一系列服务规则,并不具体的关注某一设备或接口,而是关注用户将在网络上接受何种服务。,在策略性网络中按四个策略规则决定网络的运作,它们是服务质量、安全、监控和配置。 构成策略服务的四个关键组成部分是:目录服务器(directory server)、策略服务器(policy server)、策略管理者(policy manager)和策略实施者(policy enforcers)。,11.3.2 qos策略控制系统的实现,策略控制系统示意图,1.目录服务器(directory server) 数据库模块 数据库维护界面 数据库更新模块 存取模块 通信模块,2.策略服务器(policy server) 通信模块 策略配置界面/操作模块 本地高速缓存,3.策略受控路由器 策略受控路由器必须是支持qos的。在需要qos服务的时候,路由器必须向策略服务器提交符合要求的请求在此请求中必须包括路由器所能提取的所有与策略请求相关的信息,例如目的地址、目的端口、源地址、源端口、mac地址、原优先级、输入端口索引(in-ifindex)、输出端口索引(out-ifindex)等。策略受控路由器必须承认由策略服务器指定的服务等级是最终决定,在策略服务器放弃配置(断线或其他原因)的情况下,路由器也要听从本地的策略路由客户软件的配置。,11.3.3策略服务控制的相关协议,1.cops协议 策略服务器(也称为policy decision point,pdp)和它的客户(policy enforcement points,peps)(即路由器、交换机等策略执行者)通过cops来交换策略信息。该协议基于一种请求、应答的工作机制,能够适应于不同的客户类型,并支持不同的qos标准的客户。cops协议具有以下主要特点：, 协议使用了客户/服务器模型,在这个模型中pep发出策略请求、策略更新、策略删除的信息给远端pdp,pdp将其决定返回给pep。 协议使用tcp作为传输层协议,可以提供可靠的报文交换。, 协议被设计成可扩展的。 协议提供了报文级安全,可以进行认证、重发保护和维护报文完整性。 请求/决定声明被客户和服务器共享。 策略服务器可以对客户进行策略配置,当此配置不再适用时还可以将其从客户中删除。,2.ldap协议 ldap协议是对osi的目录标准x.500中定义的目录访问协议dap(directory access protocol)协议的简化。在ldap协议里,主要定义如下:, 基于客户/服务器方式的协议运行模式; 数据模式,例如条目的属性值等; 与x.500的关系; 客户与服务器进行的操作和传送的报文格式以及描述方法。 对编码技术和传送协议的要求; 对客户端和服务器端的要求。,11.4 分组调度算法,11.4.1 ip分组调度机制 分组调度算法是在多点连接的情况下,按照不同的调度粒度(schedulinggranularity),如每一个应用级的连接或者同一类流(所有tcp流量,所有来自某个地址的tcp流、不同性能要求的流类和不同管理要求的流类等)之间进行选择的策略。,分组调度的目的就是实现拥塞控制以及提高服务质量。 较好的分组调度算法应该具有如下属性:公平性、简单性和高效性。 算法主要分为两大类:连续工作型算法(work-conserving)和断续工作型(non-work-conserving)算法。它们之间的主要区别是在于当队列中存在待调度分组时,调度算法是否持续工作。,11.4.2 常用的调度算法,1 连续工作型调度算法 其核心思想是在所设计的调度算法中都维持一个全局的优先级状态变量,每当有分组需要调度时,此优先级状态变量按相应算法进行更新并被作为分组的优先级赋予该分组,在随后的实际输出排队时,分组被按优先级顺序排序并依次输出到输出链路。,（1）vc(virtual clock)算法。 本算法以一个时分复用(tdm)系统作为调度服务器的模拟对象。算法维护的优先级状态变量称为auxiliary virtual clock(用aux vc表示)。当有分组到达时,根据分组所属流的输出链路平均带宽计算相应的改变值,并有aux vc=max(a,aux vc)+ ,a表示分组的实际到达时刻。随后将修改过的aux vc值赋予所调度的分组作为其调度时的优先级。当所调度的流满足漏桶模型时,vc算法可以保证端到端时延、时延抖动和相应的缓冲器大小等调度性能有确定上界。,（2）delay-edd(delay-earliest-due-date)算法。 此算法扩展了传统的earliest deadling first调度。在算法中维护的优先级状态变量称为expected deadline(用exd表示)。算法中假定所调度的流满足( , ,i, )模型并假定有确定的本地(调度)时延d。,当有分组到达时,根据分组所属流的到达时间间隔下届 等参数,计算并修改exd=max(a+d,exd+ ),a表示分组实际的到达时刻。随后将修改过的exd值赋予所调度的分组作为其调度的优先级。,上面两种调度算法在更新其优先级状态变量时都只考虑当前所调度的流的特性。而下面一些调度算法在进行优先级状态变量更新时,同时考虑流本身和调度系统其他流的特性。 在下面的一系列公平队列算法中,各算法都试图模拟一种理想化的流量公平队列(fluid fair queueing,ffq,也称广义处理器共享策略,gener-alized processor sharing policy,gps)工作模型。,在这种工作模型里,所有参与调度的工作流各自组成缓冲队列。在任意的时间段内,调度服务器从所有非空队列中各取队列头任务,按照各工作流的服务速率同时进行服务。 在分组网络环境下实现gps算法时, 在分组进入各自流的缓冲队列时必须由调度算法为其加上调度优先级标记,并依此顺序逐次调度各分组进行服务,才能模拟上述gps系统进行调度。,在下面5种调度算法中,标记包括两部分,一个标记称为起始时间,记为 ,另一个标记称为结束时间,记为 ;有以下非常类似的标记计算公式 ：,其中上标k表示分组的到达顺序,下标j表示分组所属的流j,a表示分组的到达时刻,l表示分组的长度,r表示流在调度时分配的处理器服务占有率。,（1）wfq(weighted fair queueing,orpgpsstandsfor packet-by-packet generalized processor sharing)算法。 在本算法中,虚拟时间函数定义为 ,其中c表示服务器的服务速率, 表示在t时刻有分组等待调度的所有流的服务占有率之和。调度服务器在选择下一个分组进行服务时根据所有非空(流的)缓冲队列头分组中的结束时间标记进行。结束时间最小者获得服务,即本算法的全局优先级变量为结束时间标记。,（2）wf2q(worst-case fair weighted fair queue-ing)算法 在本算法中,虚拟时间函数的定义形式同wfq算法一致,调度分组的选择同样按最小结束时间有限的原则进行。但是,有资格参加选择的分组pjk必须满足 ,也即在选择时刻t,该分组在所模拟的gps系统中必须已经开始获得服务。 在文献20中,提出了规一化最坏情况公平指数的定义:,此处c表示绝对时间最坏情况公平指数,并指出本算法具有一个比wfq算法更小的该指数值 ,也即在此意义上wq算法比wfq算法更加公平。,（3） wf2q+算法。 本算法是对wf2q算法进行的进一步改造。改进主要有两点: 为了降低算法的实现复杂度,定义了新的虚拟时间函数:,b(t)是wf2q+系统在t时刻有分组需调度的流的集,hi(t)是在t时刻处于流i缓冲队列队头分组的顺序号, 是此分组的起始时间。这样算法的实现复杂度就降低到了o(logn)。,为了便于高效的实现,重新定义了起始时间和结束时间的计算公式,并且只把它赋予对应的流而不是其中的所有分组。每当pjk 分组到达队头时引起起始和结束时间的计算如下: 并且 。其中 表示流i在时刻瞬时之前的队列长度。,（4）scfq(self-clocked fair queueing)算法。 本算法是第一个以降低wfq算法的实现复杂度为目标的wfq改进算法。其基本定义与调度选择机制都与wfq算法一致。scfq算法的虚拟时间函数定义为:当t时刻有分组正在调度时,则 (也即等于t时刻正在服务分组的结束时间标记);并且在该流无分组传输时重置v(t)=0。因此,算法的实现复杂度减低为o(logn)。 在文献133中给出了scfq算法的公平度定义并表明公平度为:,（5）sfq(start-time fair queueing)算法。 本算法是继scfq算法之后又一个对wfq算法的改进算法。其在基本定义上与wfq算法一致,但在调度选择时,本算法以各分组中的起始时间标记作为优先级指数,选取具有最小值者进行服务。sfq算法的虚拟时间,函数定义为:当t时刻有分组正在调度时,则 (也即等于t时刻正在服务分组中的起始时间标记);并且在该流无分组传输时重置v(t)等于此前所有接受服务分组中起始时间标记的最大值。因此算法的实现复杂度也减低为o(logn)。,以下几种公平队列算法同样模拟pgps,但与上述5种算法在形式上有所不同。在下面两种公平队列算法中,首先定义了全局的系统变量p(t)。称为系统位势(system potential)和各个调度流的流位势(session potential)变量pipi(t)。 其中 为调度算法所选定的更新周期时刻, sp(t)称为基本位势(base potential)。同时引人起始位势sij(starting potential,i,j分别表示流i和其中的第j个分组)和分组时间戳两个分组变量。,（1）ffq(frame-based fair queueing)算法。在本算法中,引人了片段周期t(frame period)的定义,t=f/r(f为片段周期中所能发送的比特数,r为服务器服务速率),并且以任何被调分组必须在一个片段周期内完成服务为前提。,定义sp(t)=kt,k为时刻t所处的片段周期序号。更新周期时刻设定为当前调度输出分组的分组时间戳大于当前周期号时,相关的性质证明表明,此时刻必定落在一个有限范围的更新时刻窗口内。此性质保证了本算法的公平性度量存在。,（2）spfq(starting potential-based fair queueing)算法。 为了提高算法的公平度,本算法对ffq算法进行了一些修改。首先是取消了ffq算法中的片段周期,规定更新周期时刻为每当有分组完成调度服务的时刻。同时重新定义sp(t)=minsi(t),即t时刻的基本位势等于该时刻所有在等待队列中的流的最小起始位势。在ffq和spfq算法中,公平度的计算采用了与scfq算法中一致的规一化服务之差的定义。,（3）leave-time/without delay jitter control算法。 本算法的基本研究出发点是将vc算法与jitter-edd算法进行有机结合。其算法的基本过程是:每当有分组到达时,首先计算该分组的可被调度时间,然后参考可被调度时间计算分组的调度截至时间,并以此截至时间值作为调度优先级指数。当分组可被调度时,按其截至时间依次进行调度。计算分组的截至时间f及全局变量k的计算公式如下:,上式中的e表示分组到达时赋予的可被调度时间值,d,l,r,t分别表示的是一个可选的延时值,分组长度,服务速率及分组的到达时间。若不加入时延抖动控制,则e=t。此时本算法工作在连续工作方式下。,（4）drr(deficit round robin)算法。 本算法是对传统的循环调度算法的改进,改进的目标是提高调度的公平度。当有分组到达时,分组采用hash算法进入所属流的等待队列,所有流的等待队列依次得到服务。在服务第i个流的分组时,若其分配的份额不足以传输此分组,则将对应此流的一个变量dificitcounteri增加此分组大小,以便下次循环时增加此流所累积的份额。,2 断续工作(non-work-conserving)型调度算法 在以下一些断续工作型调度算法中,当有分组到达时,该分组首先进入一个流的调节器(traffic regulator),通过使用调节算法,使到达分组在适当的时间才可以进行调度输出。 jitter-edd(jitter earliest-due-date)算法:,此算法是对delay-edd算法的进一步扩展。当有分组到达时,首先对该分组进行时延抖动调节,根据该分组中记录的(由上一中继节点标记)提前输出时间值aheadi-1,计算分组的可被调度时间ei=ai+ aheadi-1,并在调节器中保持此分组直到时刻ei。随后调度算法以此时刻作为分组到达时刻,按照在delay-edd算法中所述的相同调度机制进行。但在分组被输出时,必须将其输出时刻与希望输出时刻之间的差值赋予ahead,并记入该分组,以便后继的算法进行。,在下面两种调度算法中,都采用了基于周期(frame)的调度设计方法。调度算法把调度时间划分为等长的时间段,称为frame。 （1）stop-and-go算法。 本算法对各条链路都定义了离开周期和到达周期,其长度为t。一个分组在输出链路的某一个到达周期进入,经过一个确定的时延(0t)后,在输出链路的下一个离开周期被调度输出。,采用本调度算法时,对流中分组的限制是其必须满足(,t)模型,即流中分组的传输必须保证在一个周期内能够完成。为了解决由定长周期引人的调度粒度问题,可以将本算法扩展为拥有多级周期并定 对应大小不同的分组分别选取不同周期级别,并在该级别遵从上述基本算法。不同级别之间低级别优先。,（2）hrr(hierachical round robin)算法。 此算法按与上一算法类似的方法,同样将调度时间划分为不同级别(长度)的周期。调度服务器在不同级别的流(对应不同级别周期)上进行循环调度。一旦循环到某一级别时,不论该级别是否有分组要发送,都必须在对应周期结束后才进行下一级别的调度。,（3）rcsp/rjr(rate-controlled static priority/rate jitte regulator) 算法 此算法对流采用 模型进行描述,采用一个速率调节器来调节分组的到达时刻,对于流j的第k个分组其可被调度时间e按如下公式计算: 在上式中a为分组的到达时间。输出调度采用静态优先级队列方法,即在所有有分组输出的流中,选择从优先级最高流的输出队列对头分组输出。,（4）rcsp/djr(rate-controlled static priority/delay jitter regulator)算法 此算法与上述算法采用相同的静态优先级,所不同的是对调度分组的可被调度时间e的计算。其计算公式如下(其中k表示流j的第k个分组,i表示流经过的中继节点序号,d,分别表示调度服务器的调度时延和两中继结点间的最大传输时延:,（5）leave-in-time/with delay jitter control算法。 在使用带时延抖动的本算法时,进入分组和jitter-edd调度算法同样的时延调节,即计算选取时间e并将分组保持一个由上一中继设置的保留时间后,使其进入输出服务调度器进行调度。在通过类似vc算法的调度后,标记输出分组的下一保留时间并将其输出。带时延抖动的此算法同样可以在所调度的流满足漏桶模型时,达到的有保证的端到端时延、时延抖动和相应的缓冲器大小等调度性能确定上界。,3 分组调度算法研究领域的一些最新进展 （1）将已有算法按不同特性进行分类和综合,给出一类算法的综合模型,如zhang hui等提出的rcsp模型、stiliadis等提出的rps模型、goual等提出的gr模型等。,（2）根据floyd等对层次链路共享和资源管理的相关研究,将分组调度算法的研究从一个一般、平坦的网络拓展到在有层次链路共享的网络中,考虑此时如何使调度算法可以用来同时支持多个服务优先级别的服务要求,如bennett和zhanghui提出的h-pfq(即wf2q+),xie等提出的group priority scheduling、block transfer 等研究。,（3）为了解决wfq一类算法所固有的带宽-时延耦合问题,以支持新型服务模式的需要,出现了一些相应的解决方法研究。主要的思路是引人服务曲线的概念,将带宽的比例分配改为按预先设定的服务曲线进行,如cruz等提出的sced+算法等。 （4）采用特定调度算法实现各种部分确保型服务模型的研究,如,georgiadis等提出基于rcsp实现一种有速率保证(guaranteed rate)的服务等,在区别服务框架中,分组调度算法仍然是其中的重要基础和支柱。 （5）随着近年来无线移动通信的研究的不断深入,将分组调度算法应用于无线网络环境中带来了新的研究课题,主要是如何解决无线移动通信网络环境中存在的信道突发性差错以及与位置相关的信道容量与差错率的变化等问题。,11.5 缓存管理算法,11.5.1 概述 缓存管理技术和分组调度技术是分组交换设备控制资源的两种主要机制。缓存管理是输入控制机制,它根据当前的缓存占用情况决定是否接收刚到达的分组。分组调度时输出控制机制,它决定了对当前缓存中分组服务的顺序和速率。,缓存管理对于控制系统资源的使用、为流量提供qos保证起着重要的作用。如果没有缓存管理,并且在输入时也没有准入控制,恶意的传输流会用尽全部缓存空间,出现拒绝服务的情况,此时分组调度的性能也会下降。,1模型和假设,共享缓存交换结构的缓存管理模型,2 不同的网络环境 分组交换网络包括atm网络和ip网络,它们的传输数据单元不同,分别是定长的atm信元和变长的ip分组。缓存管理策略在两种环境中的作用和性能略有差别。目前高性能的ip路由器内部都包含交换结构,如图：,它针对定长的数据单元进行操作,到达接口的变长ip分组在内部被分成类似atm信元的定长信元,经过交换结构在输出端口前被重新合并成初始的ip分组。在这种情况下,缓存管理策略在接收和丢弃分组时需要考虑将属于这个分组的全部信元共同进行处理,而算法本身不需要做任何改动。,11.5.2 缓存管理算法,1 静态阈值策略 （1）完全共享与分占 完全共享(complete sharing,cs)和完全分占(complete partitioning,cp)两个方案最简单。 在cs中每个端口共享共享整个缓存空间m,如果还有空余缓存,刚到达的分组就可以被接收。cp方案则相反,全部缓存空间m始终划分给n个端口,为每个端口分配的缓存之和等于总的缓存,实际上cp并没有提供共享。,（2）缓存共享的限制和保护 为了获得共享缓存的优势,同时又避免重负载链路独占缓存的情况,“有限制的缓存共享”对每个端口分配的缓存数量引人一个最大限制(所有限制值的和可以大于整个共享内存空间),这种方案成为最大队列长度共享(sharing with maximum queue lengths,smxq)。,虽然smxq限制了各个队列长度,但是当活跃端口较多时,仍会占用全部缓存。另外,该方案没有解决如何在共享缓存环境中为不同优先级传输流保证服务。为此,提出了最小内存分配共享(sharing with a minimum allocation,sma),可以为端口预留一定数量的缓存。,将sma和smxq结合起来就是最大队列长度最小内存分配共享(sharing with a maximum queue and minimum allocation,smqma),端口可以拥有一个最小的分配空间,同时每个端口的队列长度都受到限制。cisco的lightstream1010交换机就使用了这种缓存管理策略。,（3）push-out策略 thareja和agrawala提出的延迟决定策略(delayed resolution policy,drp)。drp直到缓存空间没有空余时才决定是否丢弃分组,丢弃对象可能是刚到达的分组也可能是已接收在缓存中的分组,这由缓存占用状态或不同的优先级决定。类似的,“按要求丢弃”(drop on demand,dod),在缓存满时丢弃缓存中队列最长的分组。这两种策略都是将已接收的,分组从缓存中删除,可以称作push-out策略(po)。 阈值push-out 不同类型的传输流有不同的qos需求,需要提供不同优先级的传输服务,为此提出了虚拟划分完全共享,它与阈值push-out(po with threshold,pot),基本思想一致。pot将缓存虚拟划分成n个部分,对应n个端口。,当缓存不满时,到达的分组都接收。当缓存满时有两种可能:如果到达的分组类型例如i使用的空间少于分配的空间,那么缓存中至少有一种类型的分组超过其分配空间,例如。此时从类型j队列中删除一个分组,接收这个类型为i的分组。相反,如果新到达的分组对应类型的队列超过了其分配空间,就丢弃该分组。可见在缓存未满时pot的操作同cs;在重负载条件下则趋向cp管理。因此,pot能够适应网络传输负载的变化。,最大忙期策略 上面的pot是静态的,其参数需要预先设定好。为了能适应网络的变化,提出了最大忙期策略(maximum busy period,mbp)。因为分组丢弃发生在输出端口处于空闲状态,mpb尽可能保持所有端口的忙期,并从期望等待时间最长的队列中删除分组。对于m/g/1队列,忙期的平均长度由 估计。,2 动态策略 mbp策略实际上是一种动态缓存管理策略,所以能动态适应网络传输变化。有的文献设计了启发式的自适应控制系统,在各种传输负载条件下统计传输到达的数率,随时改变缓存资源的分配。,（1）动态阈值 choudhury和hahne的动态阈值策略(dt)基于下面的思想:在任何时候,端口的队列长度阈值与当前交换机中未使用的缓存数量成比例: 其中常数 被称作阈值分子,若输出端口队列长度等于或者超过当前阈值,到达这个端口的分组将被丢弃。,（2）最佳dt ruixue fan等人中提出了“最佳动态阈值”缓存管理算法,其目标是最大限度的提高缓存利用率,并保证缓存分配公平。在图中,当端口i的分组到达速率和输出服务速率变化时会随之而变化,最佳dt算法的端口队列阈值t(t)依据下式动态的调整大小:,是阈值变化量,若以分组数量计算则 =1;tm表示最小缓存阈值,初始时设定; 表示可用缓存数量, 一般可取0.9以上。,（3）部分共享部分分占 部分共享部分分占(partial sharing partial partitioning,pspp)策略根据活跃和不活跃端口数量将缓存虚拟划分两个部分。按照不活跃端口(队列长度没有超过b/n的端口)数量保留部分缓存空间供其共享使用,这部分缓存称作ps缓存。余下的空间称作pp缓存,均等的分给活跃输出端口。,时刻t为所有不活跃端口分配的缓存空间为 ,其中, 是pspp阈值因子;nm (t)是时刻t的不活跃端口数量,端口总数是n。每个活跃端口的最大队列长度阈值: 其中sm(t)是时刻t所有不活跃端口的集合;qi(t)是时刻t端口i的队列长度。,（4）和谐算法 有的文献中提出了称为和谐策略的缓存管理方案,它按照队列的大小顺序给各个端口分配缓存,大小为第i个的队列获得1/i比例的内存(所以称为和谐策略)。这个方案限制了各个队列的长度与队列子集合的所有队列长度和。和谐策略的约束公式是:,其中s(i)是第i长的输出端口队列(全局排列),ti是端口i获得缓存的阈值,ri 是为端口i保留的缓存的大小,是前k个最长队列和的阈值,3 多优先级策略 （1）多优先级dt choudhury和hahne将他们的dt缓存管理算法扩展到多丢失优先级情况。按照11.5.1节的假设和dt算法的阈值公式,将新到来分组的丢失优先级与阈值 结合起来,可以考虑如下四种方法: 将因子 变为 ,p=0,p-1,按照优先级进行分别: 将阈值t(t)与 或者 比较。 将m按照不同优先级划分为m=mo m1 mp =0;mp表示对应优先 级为p的有效缓存大小。 将q(t)替换为 。,研究所有的情况,根据为每个端口分配缓存情况的不同,有3种结果:根据某个控制参数按比例分配缓存和输出负载,以保证每个优先