（计算机应用技术专业论文）基于改善网络多媒体qos的队列操作优化与管理的技术探讨.pdf

塑室堕窒堕丕查兰婴主兰篁笙苎! ! ! ! 量显3摘要r侈媒体网络服务质量( q o s ) 很大程度上依赖于包的调度算法，旦前人们，提出的大多数调度算法都用到优先队列。近几年来，人们在调度算法上作了很多研究，提出了很多好的调度算法，这些算法对资源的计算、分配，对延迟及延迟抖动等服务质量的保证提出了多种有效_ 白勺解决方法。但是，没有做很多研究“本文针对某些调度算法，对调度算法中优先队列操作的改进上却结合实际情况。重点对优先队列上包的插入和排序的方法做了较为深入的研究，分别提出了“分步建堆算法”和“固定范围插入算法”。“分步建堆算法”在兼顾c p u 资源的基础上，使得网络交换机输出链路的利用率得到很大提高。“固定范围插入算法”则使得包插入优先队列的复杂度大大降低。同时为了充分利用缓冲资源，并降低包的丢弃率，本文还提出了“动态双向队列”的队列资源分配管理算法。关键词多媒体网络服务质量调度算法优先队列分步建堆固定范围插入算法双向队列基于改善网络多媒体0 0 s 的队列操作优化与管理的技术探讨a b s t r a c tq u a li t yo fs e r v i c e ( q o s ) o fm u l t i m e d i an e t w o r km a i n l yd e p e n d so nt h ea l g o r i t h mo fp a c k e ts c h e d u l e a tp r e s e n t ，t h ep r i o rq u e u ew a su s e db yt h em o s ta l g e r i t h m so fp a c k e ts c h e d u l ew h i c hp e o p l eh a dp u tf o r w a r d i nr e c e n ty e a r s ，p e o p l eh a v ed o n eal o to fw o r ki na l g o r i t h mo fp a c k e ts c h e d u l e ，a n dd e v e l o p e dm a n yg o o da l g o r i t h m s t h e s ea l g o r i t h i n sa r eg o o dm e t h o d sf o rc a l c u l a t i o n ，d i s t r i b u t i o no fr e s o u r c e ，a n df o rg u a r a n t e eo fd e l a ya n dd e l a yji t t e r b u tp e o p l ed i dn o tg i v et h e i ra t t e n t i o nt ot h ed e v e l o p m e n to fq u e u ei na l g o r i t h mo fp a c k e ts c h e d u l e t h i sp a p e rs t u d i e dt h ew a y so fi n s e r t i o na n ds o r to fp a c k e ti np r i o rq u e u ef o rs o m ec e r t a i na l g o r i t h i n s ，a n dp r e s e n t e d“c o n s t r u c th e a pi nm u l t i s t e p sa l g o r i t h i n a n d “i i m i t e db o u n di n s e r t i o na l g o r i t h m ”“c o n s t r u c th e a pi nm u l t i s t e p sa l g o r i t h m ”i m p r o v e dt h eu t i l i z a t i o no fo u t p u tl i n ko fn e t w o r ks w i t c h “1 i m i t e db o u n di n s e r t i o na l g o r i t h m ”d e p r e s s e dt h ec o m p li c a t i o no fi n s e r t i n gt op r i o r q u e u eo fp a c k e t t h i sp a p e ra l s op r o p o s e d“d y n a m i cb i d i r e c t i o n a lq u e u e ”w h i c hi sa na l g o r i t h mo fm a n a g e m e n to fq u e u er e s o u r c ef o ru s i n gt h eq u e u er e s o u r c er i c h l ya n dr e d u c i n gt h ed r o p p i n gq u o t i e t yo fp a c k e t k e yw o r d sm u l t i m e d i an e t w o r k ，q u a li t yo fs e r v i c e ，s c h e d u li n ga l g o r i t h m ，p r i o rq u e u e ，c o n s t r u c th e a pi nm u t i1 一s t e p s ，1i m i t e db o u n di n s e r t i o na l g o r i t h m ，d y n a m i cb i d i r e c t i o n a lq u e u ei i南京航空航天大学硕士学位论文第一章绪论1 1 多媒体网络概述随着信息时代的到来，人们对各种信息的需求越来越大。多年来，为了适应信息传递的要求，各种通信网络纷纷出现，如电话网，x 2 5 ，f d d i 以及d d n ，以太网，令牌网等。这些网络或以传递话音为主，或为传递数据而设计，各具特色。但是，随着多媒体会议系统，视频点播系统( v o d ) 等多媒体应用的出现，要求通信网络不仅能够传递单一特性信息，而且还要将话音，数据，图象等大量信息同时传递。为了支持这些多媒体应用，通信网络有四个关键的性能指标非常重要：吞吐量、延迟、延迟抖动和差错率 1 ，这些参数与支持连续媒体的实时传送密切相关。1 吞吐量吞吐量表示网络交换二进制信息的速度，常用的单位是位数秒，简记为b p s 。当网络处理的包块的太小固定时，也可以使用其它单位，如包数秒。吞吐量也称为传送率或带宽。2 延迟延迟是由发送端系统发送的第一个数据块的第一位到接收端系统接收到该数据位之间的时间。延迟参数对远程的同步应用来说是一个十分重要的衡量标准。由于电信号和光信号的传输都需要时间，因此，所有网络都存在延迟，只是有些网络的延迟比其他一些网络短而己。3 延迟抖动延迟抖动指传输延迟的时间变化。延迟抖动有多种多样的度量，但最常用的的度量是延迟方差，这是统计的方法。延迟抖动的的其他定义是基于在一段时间内最长和最短传输延迟之间的差值。4 差错率差错率是作为对数据发送中改动、丢失、复制或失序这些网络行为的度量。多媒体网络应用的具体实现，需要两个重要的前提 2 ：高带宽。支持服务质量( o o s ) 。随着网络技术及光纤通信技术的发展，通信网络的带宽得到了很大的提高。同时，许多支持服务质量( q o s ) 的技术( 如a t m ) 和协议( 如i p v 6 ，r s v p 等) 也得到了广泛的研究，有些已经进入了实用阶段。下面简单介绍a t m i p v 6 及r s v p 。基于改善网络多媒体q o s 的队列操作优化与管理的技术探讨1 - 1 1a t m 简介及其特点i t u t 在i 11 3 建议中定义：a t m 是一种传递模式，在这一模式中，信息被组成信元( c e l l ) ，因包含一段信息的信元不需要周期性的出现，这种传递模式是异步的。“传递模式”是指电信网所采用的复用。交换，传输技术，即信息从一个地点“传递”到另一个地点所用的传递方式。“信元”是a t m 所特有的分组，语音，数据，视像等所有的数字信息被分成长度一定的数据块。a t m 信元总共有5 3 个字节，分为两个部分。前面5 个字节为信头，用于表征信元去向的逻辑地址，优先等级等控制信息；后面4 8 个字节为信息段，用来装载来自不同用户，不同业务的信息。任何业务的信息都经过切割，封装成统一格式的信元 2 。在宽带综合服务数字网( b - i s d n ) 中，所有的业务( 不同比特率，不同质量，不同突发性的业务) 都要共享网络资源，不能再象时分复用网络那样给业务分配固定的带宽。a t m 采用虚连接( v i r t u a lc o n n e c t i o l l ) 的方式工作，比特率高的业务信元出现的频次高，比特率低的业务信元出现的频次低，按需占据带宽。a t m 有以下技术特点：( 1 ) 因传输线路质量高，不需要逐段进行差错控制。( 2 ) a t m 在通信前需要先建立一个逻辑( 虚) 连接来预留网络资源，并在呼叫期间保持这连接，所以a t m 以面向连接的方式工作。( 3 ) 信头的主要功能是标识业务本身和它的逻辑去向，功能有限。( 4 ) 信元长度小，时延小，实时性较好。1 1 2i p 版本6i p 版本6 ( 简称i p v 6 ) 是一种新型的i n t e r n e ti p 协议版。目前，世界上广泛使用的是i p 版本4 。多媒体数据流和大型地址空间及数据流的真实性鉴别和加密是新版i p 产生的原因。i p v 6 的一个重要的设计目标是保证与i p v 4 兼容。因此i p v 6 是建立在与旧的i p版本相同的主要思想基础上的，但它却有一些十分吸引人的新特点：( 1 ) 1 2 8 位的地址空间( 2 ) 改进的多站点寻址方案( 3 ) 用于真实性，完整性及数据加密性的新机制( 4 ) 使用i p v 6 的流标识可以用来支持资源预订和q o s 承诺的功能1 1 3 资源预定协议( r s v p )r s v p ( r e s o u r c er e s e r v a t i o np r o t o c 0 1 ) 的目标是在网络中为建立特定的服务质量( q o s ) 提供一种方法，以减小网络传输延迟它支持端到端的o o s 协商与控制2南京航空航天大学硕士学位论文 1 7 。r s v p 的基本原理是发送者在发送数据前首先发送p a t h 消息与接收者建立一个传输路径。p a t h 消息含有数据流标识符( i d ) 和其它控制信息。沿途的各个路由器都记录这个流标识，并为它做好保留资源的准备。接收者收到p a t h 消息后，则使用相同的流标识符回送一个r e s v 消息进行应答。r e s v 消息沿相同的路径传送给发送者。途径各个路由器时，对p a t h 消息指定的q o s 级给予确认。以后，发送者和接收者之间通过这条路径传输数据流，沿途的各个路由器为该数据流保留资源，按协商的q o s 级提供转发服务。1 2 多媒体网络的服务质量( q o s )服务质量( q u a l i t yo fs e r v i c e ，q o s ) 是用来衡量涉及多媒体应用时网络的工作质量。由于不同的应用对网络的性能要求不同，所以，各个具体应用对网络的工作期望值也不同，下面以q o s 参数形式来表示这类期望值。目前，存在许多表示q o s 需求的方法。q o s 参数可以表示成：最大许可延迟，延迟抖动，吞吐率( 带宽) ，差错率等。某些应用，比如实时会议系统，可以对延迟和吞吐率施加q o s 需求。而其它一些情况可能要求差错率为零，但对延迟及吞吐率则不严格限制，如文本传输。要保证多媒体应用的服务质量，网络必需能进行资源预定和分配，预定常常是指从现有的资源中减去一个值。例如，如果一个应用的平均吞吐量( 带宽) 为t b p s ，它所使用的物理链路的总的吞吐量( 带宽) 为c b p s 那么该输出链路的剩余的吞吐量( 带宽) 为r c r j b p s 。即在通信前，应用事先向网络提出它所要求的服务质量( 关于延迟，延迟抖动和带宽等) ，网络根据这些服务质量的参数计算出所需的资源，比如确定的带宽，缓冲区等。如果有足够的资源，网络就接受该应用的申请，进行资源规划并执行相应的资源分配；如果没有充足的资源，网络会拒绝这一请求，或与应用进行协商以降低应用的某些q o s 参数。当网络最终与应用就某个q o s 达成一致之后( 可以称其为达成了一个台约) ，应用就可以使用网络提供的服务。在此期间，网络的q o s 管理机制需要对应用的行为进行必要的监控，当应用出现违约行为时，网络将采取必要的措施来防止这种违约行为给其它的应用造成损害。服务质量( q o s ) 的保证不仅要有相应的资源，还需要有相应的调度算法。1 3 调度算法( 服务原则)调度算法，又称为服务原则，是用来决定队列中包的发送次序。调度算法通过给每个包赋一个键值。根据这个键值的大小对包进行排序，来决定包的发送次序。3基于改善网络多媒体q o s 的队列操作优化与管理的技术探讨不同的调度算法计算键值的方法不同。由于f c f s 调度算法无法保证服务质量( q o s ) ，所以，近几年来，人们对调度算法作了大量的研究，提出了许多调度算法，主要有：d e l a y e d d ( e a r l i s t d e a d l i n e f i r s t ) 3 3 ，j i t t e r e d d ( e a r l i s t - d e a d l i n e - f i r s t ) 4 3 ，v i r t u a l c l o c k 5 ，l e a v e - i n - t i m e 6 并口r c s p 7 ，h r r 8 。s t o p a n d - g o 9 ，1 0 ，1 1 ，p g p s 1 2 ，1 3 ，1 4 ，b u r s ts c h e d u l i n g 1 5 等。另外，调度算法可以划分为两大类 1 6 ：基于延迟的调度和基于速率的调度。基于延迟的调度使用延迟上界，如r c s p 7 调度给每个会话连接赋予延迟上界，根据延迟约束优先级排序到达的包，保证会话连接的延迟上界。基于速率的调度提供会话连接最小带宽，给每个会话连接分配整个带宽的一部分，根据会话连接的通信量特征计算延迟上界。1 3 1 基于速率的调度算法所有基于速率的调度算法模拟以下两个系统：( 1 ) 时分多路复用系统( t d m ) ：把时间片分为固定大小的帧，每个帧又分为时间槽，分配时间槽给每个会话连接。( 2 ) 通用处理机共享系统( g p s ) ：给每个会话连接赋予共事因子，提供给会话连接的服务正比于它的共享因子。s t o p a n d - g o 、h r r 、v i r t u a l c l o c k 、l e a v e i n t i m e 弄日b u r s ts c h e d u l i n g 调度算法模拟t d m 系统，连接间相互隔离，每个连接分配固定的带宽。s t o p a n d - g o 和h r r调度采用分帧机制，在帧期间到达的包等待在下一帧时间内发送，不同会话连接的包在一帧内的发送顺序为任意的。分帧策略的缺点类似于t d m ，若连接没有用完分配的带宽，剩余的带宽会浪费掉。v i r t u a l c l o c k 、l e a v e i n t i m e 和b u r s ts c h e d u l i n g 调度算法给每个包赋予虚拟完成时间，按虚拟完成时间的增加的顺序发送包，这一类调度算法在本文第三章有详细描述。模拟通用处理机共享系统( g p s ) 的代表算法是p g p s ( p a c k e t _ b y p a c k e tg e n e r a l i z e dp r o c e s s o rs h a r i n g ) 。若g p s 系统有个会话连接，输出链路的发送速率为l ，连接f 的服务速率为g 。= 竹盼，其中尉f j n 表示在时间f 有等待，i e b ( t )包发送的连接集合。因此，g p s 系统给有包发送的连接j 分配的带宽正比于它们的服务因子纯。p g p s 用类似v i r t u a l c l o c k 模拟t d m 的方法模拟g p s 系统：每个包都赋予虚拟完成时间，虚拟完成时间对应于它们在g p s 系统中的完成时间。按虚拟完成时问的增加的顺序发送包。1 3 1 基于延迟的调度算法基于延迟的调度算法给每个会话连接的包赋予延迟上界延迟边界测试根据所4南京航空航天大学硕士学位论文有连接的通信量和调度算法的特性，计算连接的最大延迟。延迟边界测试是连接准入控制的主要内容，如果计算出的最大延迟超过连接要求的延迟上界，网络就不接收该会话连接。基于延迟的调度算法主要有d e l a y e d d 3 ，j i t t e r e d d 4 和r c s p 7 。d e l a y - e d d 调度给每个到达的包赋予调度期限( d e a d l i n e ) ，即到达时间与延迟上界之和，选择最小期限的包发送。j i t t e r e d d 调度在d e l a y e d d 调度的基础上增加了延迟抖动控制，提供连接的延迟抖动上界。e d d 调度因查找排序队列而使操作复杂性高，为了降低复杂度提出了r c s p 调度。它将连接集分成p 个子集，每个子集中的所有连接具有相同的延迟上界。r c s p 调度维持p 个具有优先级的f c f s 队列。优先级高的延迟上界小。r c s p 调度选择优先级最高的非空队列的包发送。大部分调度算法都只给出了计算包的排序键值的方法，至于如何更高效地对包进行排序和搜索，这方面的工作却做的不多。实际上针对某些特定的调度算法或在某些特定的情况下，可以对包的排序和插入进行优化，这种优化能明显提高系统的性能。1 4 本文所做的工作本文所做的工作主要有以下三部分：( 1 ) 提出了一种改进的堆搜索算法“分步建堆算法”，它在通常情况下具有一般堆搜索算法的高效率，同时克服了一般堆搜索算法在最坏情况下搜索时间过长的缺点。通过对堆搜索算法的改进而得到的分步建堆算法在最坏情况下一定程度上减少了搜索包的时间从而使输出链路的利用率得到提高。( 2 ) 由于“保证速率类”调度算法中，包插入优先队列的复杂度较高，达到了d 似h j ，其中以为优先队列的大小。本文则提出了一系列新的插入算法：“固定范围插入算法”及其变种，该算法的插入范围具有一个与一无关的上限，使得插入复杂度达到0 f l j 。( 3 ) 提出了“动态双向队列”的队列资源管理方法，从而能更为充分地使用缓冲队列资源，并降低包的丢弃率。1 5 本文的重要概念与约定在本文中多次提到“会话”，在此“会话”是指网络上端到端的一个流连接，而不是指端到端的一个应用的连接。因为一个端到端的应用可以建立多个流连接，例如某个多媒体应用需要传输视频流，音频流和数据流，它可能会建立三个流连接，来分别传输视频，音频和数据。因为这三种流所要求的服务质量( q o s ) 不同，视频流和音频流都要求提供延迟保证，但它们都允许一定的差错率，同时视频流要求有5基于改善网络多媒体q o s 的队列操作优化与管理的技术探讨更高的带宽，而音频流则要求较小的带宽。数据流对差错率有很高的要求，但它不要求提供延迟保证。通过对要求不同服务质量( o o s ) 的传输的划分，使得网络可以针对不同服务质量( o o s ) 的流，分配相应的资源及采用相应的管理策略。w o r k - c o n s e r v i n g 调度指只要输出队列中有包，调度器就不能空闲必须持续发送队列中的包。n o n w o r k c o n s e r v i n g 调度指当输出队列中有包时，调度器可能会空闲等待，大多数情况这种等待是为了抑制延迟抖动。本文中牵涉到的调度都是w o r k c o n s e r v i n g 调度。本文假设调度的最小单位是包，而且正在被调度的包不能被剥夺。同时，假设包的长度固定，这样可以使得算法更简明、清晰，另一个原因是由于a t m 技术是未来网络发展的趋势，而a t m 中的包( 也称为信元c e l l ) 的长度是固定的。6南京航空航天大学硕士学位论文第二章基于优先队列的分步建堆算法2 1 概述多媒体网络要提供延迟，延迟抖动，丢失率等服务质量保证，需要预约网络资源，包括带宽，缓冲区。c p u 资源，同时要有相应的算法来实现。近几年来，人们提出了许多调度算法( d e l a y e d d 3 ，v i r t u a l c l o c k 5 ，p g p s 1 2 ，1 3 ，1 4 。和j i t t e r - e d d 4 3 ，l e a v e - i n - t i m e 6 等) ，这些算法都有一个共性：每收到一个包，都要计算此包的“预期最迟发送时间”，也称“时间戳”，“全局虚拟时钟”等，我们统一称此值为包的g v c ( g l o b a lv i r t u a lc l o c k ) 值。以该值为包的优先级，g v c 值越小，优先级越高，即有高的先发权利。因为要计算包的g v c 值，并在此后要根据包的g v c 值进行排序、插入、搜索等操作，而这些操作又是一件耗时( 消耗c p u 资源)的操作，以上的算法都假设有充足的c p u 资源。但实际上，随着交换机带宽和吞吐量的需求越来越大，要求每个包从进入交换机到被发送出去这段包处理时间也越来越小，包处理操作中的其它的处理过程，如包的接收，路由，监控等，这些处理过程都较简单而且都可用硬件实现，所占用的c p u 资源都很少，而包的排序、插入、搜索的操作复杂，难于用硬件实现，相对占用较多的c p u 资源，已成为包处理时间的瓶颈。如果包的处理时间大于输出链路发送包的时间，则输出链路将不得不等待，这将严重影响交换机吞吐量的提高。因此，降低这些操作的时问复杂度以节省c p u 资源成为一件非常重要且有意义的工作。本文针对以上的一些基于优先队列的调度算法，在一般堆搜索算法的基础上，提出了一种新的堆算法的实现，称为“分步建堆算法”。它能适用于所有基于优先队列的调度算法。在一般情况下，它的性能与一个正常的堆相似，但在最坏情况下它的性能比正常堆要优越。本章不将重点放在调度算法上，也不去介绍每个调度算法，仅假设每个包的g v c值己被相应的调度算法计算好，并将重点放在如何从队列中用最优的方法找出具有最小g v c 值的包。本文提出的分步建堆算法是一利改进的堆算法，其目的是在许多较坏情况下，减少包的搜索时间，从而减少每个包的处理时间，最终使得输出链路不会因等待包处理而空闲。7基于改善网络多媒体q o s 的队列操作优化与管理的技术探讨2 2 输出缓冲队列的结构及说明在输出缓冲队列的使用上有几种不同的方法，比较通用的有以下两种。1 不共享输出队列，这种方法给每一个会话分配一个队列，每个会话队列为f i f o如图2 1 所示。图2 1 不共享输出队列2 共享输出队列，这种方法给所有共享一个输出链路的会话分配一个共享队列显然，这是一个优先队列，按每个包的g v c 值排序，如图2 2 所示。图2 2 共享输出队列共享输出队列能更有效地利用缓冲队列资源，但由于每个包要插入到优先队列中插入操作的时间复杂度为o ( 1 0 9 ) ，( 在本文的第三章中，提出了一系列“固定范围8南京航空航天大学硕士学位论文插入算法”，使得插入操作的时间复杂度与n 无关) ，以为队列中包的数目。不共享输出队列对缓冲队列资源的有效利用上不如共享输出队列，但调度发送器仅需搜索每个会话队列头元素，搜索操作的时间复杂度在线性搜索算法下为d ( m ) ，肘为共享同一输出链路的最大会话数目。如果用堆来实现排序和搜索，复杂度为o ( t o g m ) 。本章提出的分步建堆算法基于不共享输出队列。为了下面的说明方便，我们先对下列符号进行定义与说明：m ：共享同一输出链路的最大会话个数。 ：每个包的传送时间长度( 所有包的长度固定) 。不失一般性，可设 = t 。一t 6其中：t 。：每个包的开始传送时间。t 。：每个包的结束传送时间。g v c ：全局虚拟时钟值，即包的优先值( 键值) 。激活会话：会话队列中有等待发送的包。不激活会话：会话队列中没有等待发送的包。由于会话队列为f i f o 结构，下一个被发送的包必为某个会话队列的头一个包，所以为了确定下一个被发送的包，也就是找到下一个会话，这个会话队列的头个包的优先值( g v c 值) 比其余会话队列的头一个包的优先值( g v c 值) 都要小。所以搜索范围是当前所有激活会话。同时，应当注意到这样一个问题：为了充分利用输出链路带宽，提高交换机的吞吐率，当个包被发送时，要求下一个包必须在当前包发送结束时间t 。前被搜索出；然而，这样的要求并非总能满足。假定在即将到达t 。时刻前瞬间有许多会话由不激活状态变为激活状态，即这些会话有新包到达输出队列中，这些会话队列的头一个包都将参与搜索，而没有一种搜索算法能在一个非常小的时间内搜索出下一个包。因此，在此提出临界时间点的概念，在临界时间点前到达的包才参与本次搜索，在临界时间点后到达的包不加入本次搜索，它们将在下一次包发送时被搜索。临界时间点将连续到达的包按时间分割为段，每一次包搜索都是针对某一段时间内到达的包。如图2 3 所示，只有在 f 。，t 。一e ( e ) 的时间内变为激活的会话才会参9基于改善网络多媒体o o s 的队列操作优化与管理的技术探讨与本次搜索，而在 t 一e ，f 。 ( ) 的时间内变为激活的会话不参与本次搜索，它们将在下一个包的发送时间内被搜索。e 的取值我们将在后面讨论。图2 3 临界时间点示意图2 3 一般的堆搜索算法的思想如果用线性搜索算法搜索肘个会话，这种算法的平均效率和在最坏情况下的效率相同，都为0 ( m ) 。由于这种算法的平均效率太差，通常不被采用。为了提高搜索的平均效率常常使用堆搜索算法，这种算法要为每个输出链路维护一个堆。堆中每个元素都是激活会话的队列头一个包，所以堆的大小h 满足0 h 蔓m ，堆的维护与实现在调度发送器对象中完成。对外界来说，调度发送器对象是封闭的，它仅提供两个接口给外界使用，一个接口用来向堆中插入一个元素，用函数v o i d h e a pi n s e r t ( s e s s i o n l d ) 表示，参数s e s s i o n l d 标识一个会话，该会话队列中的第一个包将要插入堆。另一个接口用来获得当前堆中优先值最小的包，用函数s e s s i o n l dh e a pr e n l o v em i n ( v o i dj 表示，该函数的返回值s e s s i o n l d 是一个会话标识，它指明该会话队列的首包的虚拟时钟值( g v o 比其它所有会话的首包的虚拟时钟值( g v o 都要小。也就是说，在当前所有会话队列中的所有包的虚拟时钟值( g v c ) 中，会话s e s s i o n l d 队列首包的虚拟时钟值( g v c ) 是最小的。图2 4 给出了一个调度发送器的简单的模型。i o南京航空航天大学硕士学位论文图2 4 一般堆搜索调度发送对象模型堆维护主要需要以下三种操作：1 插入新元素到堆中，v o i d h e a p i n s e r t ( s e s s i o n l d ) ，操作的时间复杂度为o ( 1 0 9 m ) 。2 取出堆中最小优先值的元素，s e s s i o n l d h e a p r e t o o l ，e m i a ( v o i d ) ，由于堆中最小元索是堆顶元素，所以操作复杂度为o ( 1 ) 。3 堆顶元素移走，重新排列堆( 将堆中最后元素由堆顶向下移动) 用函数v o i dh e a p u p d a t e m i n ( v o i d ) 表示，操作复杂度为o ( 1 0 9 m )堆仅在以下两种情况下需要维护：1 有会话由不激活状态变为激活状态，即原来会话的空队列有新包进入。此时应执行h e a p i n s e r t ( s e s s i o n l d ) 操作将新包元素插入堆中。2 调度发送器取出堆中有最小优先值的包元素，即执行了h e a p r e m o v e m i n ( v o l d ) ，此时，由于堆结构被破坏，需重新调整，一般的调整方法是将堆中最后的元素由堆顶向下移动。也就是执行h e a p 一印d a t e m i n ( v o i d ) 。如果被取出的包元素属于会话s ，而会话s 仍处于激活状态，即会话s 队列不为空，1 1基于改善网络多媒体o o s 的队列操作优化与管理的技术探讨此时为了提高效率，应延迟执行h e a p u p d a t e m i n ( v o i d ) 。因为如果不延迟执行在执行h e a p 一印d a t e m i n ( v o i d ) 后，会话s 的下一个包又要插入堆中( 执行h e a p i n s e r t ( s e s s i o n l d ) ) 。可通过延迟执行h e a p u p d a t e m i n ( v o i d ) ，首先将会话s 的下一个包直接加入到堆尾。再执行h e a p 一印d a t e m i n ( v o i d ) ，一次完成堆重排和插入。下面分析堆在平均和最坏情况下的效率：每当调度发送器取出堆中最小优先值的元素后，都必须要执行h e a p 一砌d a t e m i n ( 1 ，o l d ) 以重新调整堆，再从调整好的堆中搜索出最小优先值的元素。由于真正搜索堆中最小优先值的元素的操作很简单，复杂度为d r l j ，而大量耗费时间的操作是在执行调整堆的操作h e a p u p d a t e m i n ( v o i d ) ，复杂度为o q o g m ) 。所以，在平均情况下，搜索出下一个包的操作复杂度为o q o g m ) 。然而，最坏情况是，当调度发送器取出堆中最小优先值的元素后，倘若在临界时间点之前有m 个会话由不激活状态变为激活状态，且此时堆中的元素数目为零，为了搜索出下一个元素，必需执行m 次h e a p i n s e r t ( s e s s i o n l d ) 操作。这实际上就是重新构造堆，所以，在最坏情况下搜索t b t - - 个元素的复杂度为o ( m l o g m ) 。如果这种最坏情况出现在非常接近临界点的时候，那么调度发送器要在e 时间内完成这一复杂操作是很难的，尤其是当m 很大而e 很小时。这时，由于调度发送器不能在当前包发送结束时间t 前完成搜索，所以输出链路不得不空闲等待。为了使输出链路不等待或尽可能少等待，应优化最坏情况下的搜索时间。1 2南京航空航天大学硕士学位论文2 4 分步建堆搜索算法在平均和最坏情况下，比较一下一般的堆搜索算法和简单的线性搜索算法，可见：简单的线性搜索算法在平均和最坏情况下有相同的搜索效率0 ( m ) ，而堆搜索算法在平均情况下，有很高的效率o ( 1 0 9 m ) ，而在最坏情况下的效率却很低，仅为0 似姗m ) ，所以，可以设想能不能将两种算 去结合起来，使得在平均情况下有o ( 1 0 9 u ) 的效, ，而在最坏情况下有o ( m ) 的效率。为了实现这种新算法的设想，首先要对原来的堆结构进行一点改进，如图2 5 所示。图2 5 分步建堆搜索调度发送对象模型比较图2 4 与图2 5 两图，可见：在图2 5 所示的新算法结构中增加了两个部件，即插入等待队列( i w q ) 和线性搜索器。每一个要插入堆中的包元素先进入插入等待队列( i w q ) ，之所以要有这样一个插入等待队列i w q 是因为如下两个原因：1 如果在某个时刻，有多个包元素要求插入时，而调度发送对象来不及完成多个包元素的排序，会使多个会话在调用h e a p i n s e r t ( s e s s i o n l d ) 时阻塞等待，加入1 3基于改善网络多媒体q o s 的队列操作优化与管理的技术探讨插入等待队列( i w q ) 可以使日却一i n s e r t ( s e s s i o n l d ) 函数的操作效率达到o o ) ，因为h e a p i n s e r t ( s e s s i o n l d ) 并不真正进行插入堆的动作，而仅仅将包元素先插入i w q 。2 在执行线性搜索时的操作对象大部分都在插入等待队列( i w q ) 中。线性搜索器用来实现线性搜索算法，它将比较堆中最小包元素及插入等待队列( i w q ) 中的包元素，找出最小的包元素。下面详细描述分步建堆算法，它与临界时间点有密切的关系。正如前面所说的，在每个包的发送时间段内，将临界时间点以后到达的包元素被排除在本次搜索之外，它们将在下一个包的发送时间段内参与搜索。当调度发送对象将当前最小优先值的包传送给输出链路( 此时即为t 。) 后，在 t 。，t 。一 时间段内，也就是在临界时间点之前，它所做的操作与一般堆算法相同，都是将每一个插入的包插入到堆中，当到达临界时间点时，它将根据此刻插入等待队列( i v q ) 中包元素数目，堆中包元素数目及堆插入操作时间和线性搜索时问，来决定是继续完成堆插入后搜索，还是进行线性搜索。为了方便分析，特作以下约定：c 。：分配给当前输出链路的c p u 资源( 单位时间内分配到的时间) 。m 。：当前处于激活状态的共享会话数，0 m 。m 。 ：当前堆中的元素数目。叮：当前插入等待队列( 1 w q ) 中包元素数目。l ：线性搜索基本操作时间。h 。：堆操作基本操作时间。由此，可以推得在临界时间点时，完成堆插入排序的时问为t h = h 。i o g ( h + f ji = l而线性排序的时间为t ，= r g + 1 j x l 。另外，定义堆排序剩余时间t ，且1 4南京航空航天大学硕士学位论文即f = 8 一h ，i o g ( h + f )i = 1堆排序剩余时间f 的实际物理意义是从临界点开始执行堆排序，当堆排序完成时，距t 。还剩余的时间。如果求出的t 小于0 ，则说明堆排序所用的时间超出了s 吒。，超出的时间为一t 。因此，在临界时间点，算法要作以下计算和判断：t = s x 乞。一h , e l o g ( h + f ji = l然后，根据f 的值决定执行堆插入搜索还是线性搜索。下面对调度发送对象的搜索算法做一个完整描述，在描述之前先定义两个函数：a 1 w q i n s e r t ( v o i d ) 函数执行将i w q 队列中的元素插入堆中。b _ s e s s i o n l dl i n e s e a r c h ( v o i d ) 函数对i w q 队列中的所有元素及堆首元素进行线性搜索，搜索出最小的元素并将其返回。于是，我们有【分步建堆搜索算法】1 枷抛( 临界时间点未到)i w q i n s e r t ( v o i d ) ；2 计算f ：g c 。一h 。l o g ( h + i ，临界时间点到i = l3 矿( f 0 )有足够时间完成堆插入(4 f o r ( = o ；i q ；f + + )将插入等待队列i w q 中的包插入堆i w q i n s e r t ( v o i d ) ；m i n s e s s i o n l d = 堆首元素1 5基于改善网络多媒体q o s 的队列操作优化与管理的技术探讨没有足够时间完成堆插入，执行线性搜索m i n s e s s i o n i d = l i n e s e a r c h ( v o i d ) ；为了简化计算，可将圭k r + u 用g t o g ( h + 叮j 代替，得到f 的简化计算式t = 5 巳。一h ，q l o g ( h + 叮j图2 6 所示为算法的简单示意图，图2 6 分步建堆算法初步示意图从图2 6 中可以看出，分步建堆算法的实质是：在从临界时间点到f 这段e 时间内，如果能够完成堆插入搜索，则优先使用堆插入搜索。否则为了尽快搜索出下一个包元素以在f 。前发送，则使用线性搜索算法，这是由于线性搜索算法虽然平均性能较差，但相比之下，在最坏情况下却优于堆搜索算法。当t ( 0 时，算法将使用线性搜索。如果t 。小于e c 。很多，这意味着用线性搜索找出下一个包后，还要等待e c o t 。时间才能再发送包( 假设调度发送对象必需等前一个包被输出链路发送出去才能再向输出链路发下一个包) ，这段等待时间不应被浪费。尤其是插入等待队列( i w q ) 中仍有包等待插入堆中，完全可以利用这段时间来作将插入等待队列( i w q ) 中的包插入堆中的工作，如图2 7 所示。因此，还可以对分步建堆算法作进一步的改进，以使在临界点后，尽可能多地1 6南京航空航天大学硕士学位论文执行堆插入排序，再执行线性搜索。所以，改进的算法的要点是确定临界时闻点后执行几个包元素的堆插入操作?图2 7 分步建堆算法示煮图当t 0 时，仍旧执行堆插入搜索( 对i w q 中所有包元素) 。当t 0 时，假设先对插入等待队列( 1 w q ) 中的x 个包进行堆插入排序，再对剩余的包元素及堆首元素进行线性搜索。那么，为了充分利用c p u 的资源，_ x 的取值应取满足下面不等式的最大正整数值：x l l 。t o g ( h + 叮j + f 叮一x + 1 j 厶5 c 荦。( 2 一1 )由上式，可以很容易推导出x ：i ! 堡虻咝li f o g ( h + 口j 一厶j因此，前述分步建堆算法应当作如下改进，即将步骤55 m i n s e s s i o n l d = l i n e s e a r c h ( v o i d ) ；改进为5 x ：k 生盟业堕iiq l o # ( h + q j 一if o r p ti = o ；i x ；i + + )i w q i n s e r t o ，o i a ) ；m i n s e s s i o n l d = l i n e s e a r c h ( v o i d ) ；式( 2 一1 ) 中，c 。的取值范围为0 c 。曼1 ，这取决于具体的交换机的设计结构a在许多普通类型的交换机上，多个输出链路共享一个c p u 。例如，假设1 0 个输出链基于改善网络多媒体q o s 的队列操作优化与管理的技术探讨路共享一个c p u ，每个输出链路平均分配c p u 的时间，则每个输出链路的c 一= o 1 。而在许多高性能的交换机的设计上，采用模块化设计，将输出链路设计成独立的模块，将每个输出链路及相关的部分设计成一个插件，每个插件上有自己c p u ( 即c 删= 1 ) 及缓冲区，通过系统总线与系统相连。这样的设计使得系统有更好的扩充性，更好的可靠性和更好的性能。由于这种模块化的设计方法是一种必然的趋势，而多个输出链路共享一个c p u 的设计将被淘汰。所以。在模拟实验中c 。取l 。这也就是意味着每个输出链路有自己的c p u 。现将完整的分步建堆算法描述如下。【分步建堆搜索算法】i w _ i l f f c ( 临界时间点未到)i w q i n s e r t ( v o i d ) ；2 计算t = g h q l o g ( h + g ，临界时间点到3 矿( f 0 )有足够时间完成堆插入4 _ ，打o = o ；i 口? “+ )将插入等待队列i w o 中的包插入堆i w q i n s e r t ( v o i d ) ；m i n s e s s i o n l d = 堆首元素)e l s e没有足够时间完成堆插入(5 x ：i ! 二型兰些一il qx l o 譬( h + g j 一jf o r ( i n tf = o j f 1( 3 _ 2 )下面给出“g r 调度算法的简单算法描述。在调度模块部分，每当收到一个包时，执行如下“g r ”调度算法：【“g r 调度算法】1 调度模块收到一个包2 确定该包属于会话s 的第f 个包3 根据式( 3 2 ) 计算出该包的g v c 值e 。4 将g v c 值附在包上，并根据该值插入输出排序队列同时，对于输出链路服务器来说，算法也较简单：【输出链路算法】1 等待输出链路空闲2 i f 输出队列不空3 取出输出队列的第一个包元素4 将包元素中的数据发往输出链路5 释放该包的相应资源6 e n d i f7 g o t o 】基于改善网络多媒体q o s 的队列操作优化与管理的技术探讨调度模块将根据包的g v c 值将包插入输出队列。假设队列中有n 个包，那么一般的插入算法的时间复杂度为d ( ? 昭一) 。当h 较大时，插入操作占用了交换机较多的c p u 资源，这将严重影响交换机的整体性能。在本章后面提出的一系列“固定范围插入算法”就是基于“g r ”调度算法的插入算法，它的复杂度将与以无关。3 3 “固定范围插入算法”概述“固定范围插入算法”通过缩小包的插入范围( 插入范围大小与n 无关) 来实现更小的时间复杂度。( b ) 固定范围插入算法，插入范围i p i q ，插入复杂度与n 无关图3 3 一般插入算法与固定范围插入算法比较图由图3 3 ( b ) 可见，“固定范围插入算法”的实现关键在于确定新的插入范围起点i p 及范围终点i 。，其做法是先计算范围起点i ，再算出范围的大小，据此可以算出范围终点，。，为此先作以下定义：k 。? 会话j 在输出队列中最后一个包的索引只? 输出队列中第f 个包的g v c 值注意e 与曩，的区别，f i 的下标索引i 指的是输出共享队列的索引，而e ，的下标索引f 指的是会话s 的第f 个包。本文后面提出的“固定范围插入算法a ”，“固定范围插入算法b ”，“固定范南京航空航天大学硕士学位论文围插入算法a ”及“固定范围插入算法b 在计算插入范围起点j ，上是相同的，它们的不同之处在于插入范围大小的计算上有别。3 4 “固定范围插入算法a ”的描述及证明“固定范围插入算法a ”的算法描述如下：【固定范围插入算法a 】1 调度模块收到会话s 的第i 个包，并计算出它的g v c 值e ，2 i f 当前输出队列中没有会话s 的包( 己被发送)第一