（微电子学与固体电子学专业论文）分层轮循调度算法研究与asic工程实现.pdf

摘要 摘要 随着因特网业务持续高速增长，新的用户不断接入因特网，用户要求有更高 的带宽并具有一定的服务质量( q o s ) 保证。网络服务质量的保证主要包括三个方 面：数据包缓冲，队列调度和队列管理。队列调度算法作为保障网络服务质量的 重要一环，有着不可取代的重要作用。本文主要研究了队列调度算法以及相关技 术，具体工作如下： 首先，研究与队列调度紧密相关的数据包缓冲技术与队列管理技术，并选择 了适合的缓冲算法和队列管理算法，它们帮助队列调度算法更有效地调度数据包。 其次，研究了当前高速网络设备中广泛运用的两类主流队列调度算法( 基于 时间戳的调度算法和基于轮循的调度算法) ，分析了它们的优缺点，并选择了综合 两类算法优点的分层轮循调度算法作为本文设计调度器的调度算法。 再次，在分析分层轮循调度算法的理论后，提出了该算法的硬件实现方案， 并且通过v e r i l o g 硬件描述语言实现了该调度算法。然后为了验证功能对设计的 电路搭建测试环境，并最终验证设计能完全实现分层轮循调度算法的功能。 最后，基于f u j i t s u 公司0 1 3 m s 工艺库，通过d e s i g nc o m p i l e r 软件对设计 进行综合，验证所有关键路径符合时序约束，设计的芯片面积符合面积约束。 关键词：服务质量专用集成电路设计分层轮循调度仿真验证综合 a b s t r a c t a b s t r a c t 、研t l lt h ec o n t i n u o u s l yr a p i di n c r e a s i n go fi n t c r n e ts e r v i c e s a sm o r ea n dm o r eu s e r s a c c e s si n t e r n e t ，c o n s u m e r sn e e dm o r eb a n d w i d t ha n dq u a l i t yo fs e r v i c e ( q o s ) q u a l i t y o fs e r v i c em a i n l yi n c l u d e s3a s p e c t s ：p a c k e t sb u f f e r i n g ，q u e u es c h e d u l i n ga n dq u e u e m a n a g i n g a st h ei m p o r t a n tp a r to fq u a l i t yo fs e r v i c e ，q u e u es c h e d u l i n gi s i n - d i s p e n s a b l e t h eq u e u es c h e d u l i n ga l g o r i t h ma n dr e l a t i v et e c h n o l o g i e sa r es t u d i e di n t h i st h e s i s t h em a i nw o r ki sa sb e l o w ： f i r s t l y , p a c k e tb u 伍n gt e c h n o l o g i e sa n dq u e u em a n a g i n gt e c h n o l o g i e sw h i c ha r e t i g h t l yr e l a t e dw i t hq u e u es c h e d u l i n ga r es t u d i e di nt h et h e s i s a n dt h es u i t a b l eb u f f i n g a l g o r i t h ma n dq u e u em a n a g i n ga l g o r i t h ma l ec h o s e nt oh e l pt h ep a c k e t ss c h e d u l e dm o r e e f f i c i e n t l yb yt h eq u e u es c h e d u l i n ga l g o r i t h m s e c o n d l y , t w ok i n d so fq u e u es c h e d u l i n ga l g o r i t h m sw h i c ha r eb r o a d l yu s e di nh i g h s p e e dn e t w o r ke q u i p m e n t sa r es t u d i e di nt h et h e s i s t h e i ra d v a n t a g e sa n dd i s a d v a n t a g e s a r ea l s oa n a l y z e d a n dt h es t r a t i f i e dr o u n dr o b i n w h i c hc o n t a i n st h ea d v a n t a g e so ft w o k i n d so fq u e u es c h e d u l i n ga l g o r i t h m si sc h o s e na st h es c h e d u l i n ga l g o r i t h mo ft h eq u e u e s c h e d u l e r t h i r d l y , a f t e rr e s e a r c h i n gt h et h e o r yo fs t r a t i f i e dr o u n dr o b i n ，t h eh a r d w a r e a c h i e v e m e n to ft h ea l g o r i t h mi sd e v e l o p e d a n dt h es c h e d u l i n ga l g o r i t h mi sa c h i e v e db y v e r i l o gh a r d w a r ed e s c r i p t i o nl a n g u a g e t h e n ，t h ev e r i f i c a t i o ne n v i r o n m e n ti sb u i l tu p f o rf u n c t i o ns i m u l a t i o nt e s to ft h ed e s i g n i tf i n a l l yc o n f i r m st h a tt h es t r a t i f i e dr o u n d r o b i ni st o t a l l ya c h i e v e db yt h ed e s i g n a tl a s t ，t h ed e s i g ni ss y n t h e s i z e db a s e do nt h ef u j i t s uc o m p a n y s0 13 m st e c h n o l o g y l i b r a r yb yd e s i g nc o m p i l e rs o f t w a r e a l lt h ec r i t i c a lp a t h sa r ev e r i f i e dt om e e tt h e r e q u i r e m e n to ft i m er e s t r i c t i o n a n dt h ed e s i g na l s om e e t st h er e q u i r e m e n to fa r e a r e s t r i e t i o n k e yw o r d s ：q u a l i t yo fs e r v i c e a s i cs t r a t i f i e dr o u n dr o b i ns i m u l a t i o n s y n t h e s i s 西安电子科技大学 学位论文独创性声明 秉承学校严谨的学风和优良的科学道德，本人声明所呈交的论文是我个人在 导师的指导下进行的研究工作及取得的研究成果。尽我所知，除了文中特别加以 标注和致谢中所罗列的内容以外，论文中不包含其他人已经发表或撰写过的研究 成果；也不包含为获得西安电子科技大学或其它教育结构的学位或证书而使用过 的材料。与我一同工作的同志对本研究所做的任何贡献均已在论文中作了明确的 说明并表示了谢意。 申请学位论文与资料若有不实之处，本人承担一切的法律责任。 本人签名：压熬日期：呈! 翌星型：兰 西安电子科技大学 关于论文使用授权的说明 本人完全了解西安电子科技大学有关保留和使用学位论文的规定，即：研究 生在校攻读学位期间论文工作的知识产权单位属西安电子科技大学。学校有权保 留送交论文的复印件，允许查阅和借阅论文；学校可以公布论文的全部或部分内 容，可以允许采用影印、缩印或其它复制手段保存论文。同时本人保证，毕业后 结合学位论文研究课题再攥写的文章一律署名单位为西安电子科技大学。( 保密的 论文在解密后遵守此规定) 本学位论文属于保弯，在一年解密后适用本授权书。 本人签名：么燃日期：墨! ! 星：! 兰 导师签名： e 蚓4日期：筮遂：之； ii 第一章绪论 第一章绪论 1 1 服务质量技术由来与发展现状 服务质量( q o s ) 并不是现在才产生的想法，i n t e l n e t 的创建者们开始就预见了这 种需要，并在口包头预留了个字节，称为t o s 字段，从而使得最初的口规范 就包括q o s ，他们这样描述t o s 字段的用途：t o s 用于指示所需q o s 的抽象参 数。在特定的网络中传输数据报文时，这些比特位用于指导如何选择实际的服务 参数。 直到上个世纪8 0 年代，i n t e r a c t 还处于象牙塔中，网络通信很有限，因此是否 支持q o s 显得无关紧要，几乎所有的d 网络都忽视了这个字段，路由器也不使用 它来参与p 分组的转发处理。随着i n t e r n e t 的日益普及和发展，它和电信网一样 成为人们生活中应用最大的网络平台之一。人们对i n t e r n e t 的要求也不仅仅只满足 于单纯的数据传输，i p 电话、远程视频会议，视频点播等多媒体和实时新业务纷 至沓来，这些应用一般都需要一定的带宽、时延、可靠性等服务质量要求，因此 s l a 得到广泛应用。一方面，商业客户希望网络能始终提供有保证的服务；另一 方面运营商渴望细分用户群，提供不同的服务，收取不同的费用。 服务质量所要满足的传输质量在于：数据包不仅要到达其欲传输的目的地址， 而且要保证数据包的顺序性、完整性和实时性。因此需要q o s 能够对数据包进行 合理的排队，对含有内容标识的数据包进行优化，并对其中特定的数据包赋以较 高的优先级，从而加速传输的进程，以实现实时交互。提供q o s 保证的网络应该 能够按照业务量的类型或级别加以区分，并能够依次对各级别进行处理。 不同业务提供不同级别的q o s 服务对网络提出了一些全新的要求，其中最重 要的是如何使各类业务有效的共享网络资源。目前的研究主要包括以下3 个方面： 数据包缓冲、队列调度和队列管理。 数据包缓冲器负责将数据包存入缓冲区以等待传输并在网络出现拥塞时 有选择的丢包。 队列管理负责在网络服务的需求将超过网络提供的能力，引起链路带宽分 享的不公平甚至导致网络拥塞时，如何丢弃数据报文。 队列调度器则负责从缓冲区中选择相应的数据包传输，很显然两者之间是 相互关联的。传统的路由器只有一个队列，所以调度任务简单，只要底层 链路能够传输，调度器就从队列中尽快地取出分组。而在当今要求保证网 络q o s 的路由器中队列调度器是相对优先权、时延、时延抖动和带宽分 配最后的监视程序。调度器能够通过改变队列被服务的频率为业务提供最 2 一 分层轮循算法研究与a s i c 工程实现 小带宽保证和最大带宽限制，并且不断地调整服务规律以确保每个队列在 配置范围内的平均带宽或时延。 队列调度算法在保证网络服务质量的过程中起着非常重要的作用，它也是本 文主要的研究对象。 1 2 队列调度算法研究现状 网络路由器所采用队列调度算法是许多q o s 结构中一个重要的组成部分，队 列调度器决定各种不同的数据流的输出次序，这些数据流被一个共享带宽的输出 链接所转发。一般来说，队列调度器需要有以下特性： 公平性：在多路数据流竞争同一个共享输出链接时，调度器必须提供一些 分割的度量标准。尤其每个数据流必须得到其被合理分配的可用带宽，这 部分带宽不应该因为其他流的存在或它们的不端行为而被影响。 有限的延迟：像视频和音频会议这种交互式应用要求一个数据包在网络 上的全部延迟被限制在一个终端到终端的基础上。队列调度器决定数据包 在输出链接处的次序，因此它也决定了一个数据包在网络上每个中间路由 器所需的队列延迟。 低复杂度：当线速率增加到4 0 g b p s 时，所有路由器执行的包处理任务， 包括输出调度，它们能否在纳秒时间范围能被处理就显得尤为关键。挑选 下一个被调度数据包的时间复杂度必须很小，尤其希望这个复杂度能是一 个很小的常数，无论数据流的数量是多少。同样重要的是，调度算法必须 易于被高效地硬件实现。 在队列调度算法漫长的发展过程中，大致可以分为以下两种基本的设计方法。 一种是基于时间戳的调度算法，它被证明有很好的延迟和公平特性。但一般需要 根据截止时间将数据包分类，因此需要忍受与数据流数目n 成指数倍关系的复杂 度。这个分类的瓶颈使得这些算法在实际实现中变得问题重重，也迫使人们设计 简单些的解决方案。基于轮循的算法出现了，它拥有o ( 1 ) 的复杂度。在其支持公 平分配带宽的同时，他们却无法提供很好的延迟误差。因此即使在现代计算机网 络中公平队列问题被广泛的研究，但调度算法在具有良好特性与高速路由器中方 便实现之间仍然存在明显的隔阂。 总的来说，时间戳调度器有很好的公平和延迟特性，但复杂度很高。而轮调 度器虽然易于实现，但它的延迟限制很差，而且存在输出脉冲现象。越来越多近 期被提到的算法已经尝试去综合时间戳调度器的公平和延迟特性与轮循调度器低 复杂度的优点。本文研究的分层轮循调度器正是遵循这个方式。 第一章绪论 1 3 论文意义与本人完成的工作 3 一 分层轮循调度算法( s t r a t i f i e dr o u n dr o b i n ) 是一种基于公平队列的数据包调度 算法，它有良好的公平性，低延迟特性以及接近0 ( 1 ) 的复杂度。由于它提供了不 受流数量影响的单包延时特性，分层轮循调度算法在其他类似复杂度的调度算法 中是独一无二的。更重要的是，s r r 也非常容易在硬件上实现。这正好填充了当 前调度算法中的一个间隙，即又具有很好的性能，同时又可以在高速路由器中实 现。 本文的主要工作是根据分层轮循调度算法的理论，基于a s i c 技术将算法硬件 实现并完成验证及综合等相关的工作，具体工作内容如下： 1 研究与队列调度紧密相关的数据包缓冲技术与队列管理技术，在分析了典 型的缓冲算法如( 输入缓冲、输出缓冲和组合输入输出缓冲) 和队列管理算法如 ( 弃尾算法和随机早期探测算法) 后，根据它们的优缺点选择了适合的算法，它 们帮助队列调度算法更有效地调度数据包。 2 研究了当前高速网络设备中广泛运用的两类主流队列调度算法( 基于时间 戳的调度算法和基于轮循的调度算法) ，分析了它们的优缺点，并选择了综合两类 算法优点的分层轮循调度算法作为本文设计调度器的调度算法。 3 在分析分层轮循调度算法的理论后，提出了该算法的硬件实现方案，并且 通过v e r i l o g 硬件描述语言实现了该调度算法。同时为了验证功能对设计的电路搭 建测试环境，并最终验证设计能完全实现分层轮循调度算法的功能。 4 完成了综合脚本文件的设计工作。基于f u j i t s u 公司0 1 3 m s 工艺库下，证 明设计的调度器所有关键路径完全符合时序要求，同时也完全符合设计的面积限 制。 第二章q o s 相关技术研究与选择 5 一 第二章q o s 相关技术研究与选择 为了给不同业务提供不同级别的q o s 服务，只有队列调度是远远不够的，数 据包缓冲和拥塞控制也是同样重要的部分。本章主要为队列调度器选择合适的数 据缓冲器和队列管理器，使得队列调度算法能更好地发挥它的作用。 2 1 网络服务质量的性能量度 了接q o s 性能量度能帮助我们在相关技术中更好地选择和组合，对整个q o s 的实现起到标尺的作用。q o s 旨在提供具有确定性能限制的端到端连接。带宽分 配、分组时延、时延抖动以及分组丢失率是网络中表征连接性能的常用度量尺度。 带宽( b a n d w i d t h ) ：带宽用来描述给定连接的额定吞吐量，实际上是指应 用程序在网络中通信所需的“管道大小。通常来说对于需要提供服务保证的连 接会有一定的带宽要求，并希望网络为它们专门分配最小带宽。 分组时延( d e l a y ) ：分组时延包括处理时延、传播时延和输出时延。 1 处理时延：数据包在网络单元中被处理的时间之和，主要包括排队时间 和交换时间等等。 2 传播时延：数据从发送方到达接收方所需的时间即使在最好的情况下， 数据的传播速度也比光速小得多，所以这种时延有时也会很明显。它主要取决 于传输距离和传输介质，与分配的带宽无关。 3 输出时延：输出速率一定的情况下，设备传输一个分组所需的时间输出 时延取决于分配的链路带宽以及分组的大小。例如，以3 m b i t s 的链路速度传输 一个6 4 字节的分组大约需要1 7 1 u s 。 时延抖动( d e l a yj i t t e r ) ：网络中每个分组经历的时延随网络的瞬时状况而 异。当网络没有拥塞且路由器没有排队时，总的分组时延由每个中继段的传播时 延和输出时延组成，这是网络的最小时延。如果网络发生拥塞，排队时延将影响 数据包的端到端时延并导致通过同一连接的分组的时延各不相同。分组时延的这 种变化就是时延抖动。 分组丢失率( l o s sr a t e ) ：分组丢失率通常是指在特定时间段内丢失的分组 占传输分组总数的比例。网络拥塞和传输线被破坏都会导致分组丢失，当接收分 组的缓冲区溢出时分组也会被丢弃。 2 2 数据包缓冲器研究与选择 在路由器中队列调度器从数据包缓冲区中选择相应的数据包传输，数据包缓 6 一 分层轮循算法研究与a s i c 工程实现 冲器的优劣直接决定了队列调度器在调度过程中的效率。数据包缓冲器主要负责 将数据包存入缓冲区以等待传输并在网络出现拥塞时有选择的丢包。 2 2 1 典型数据包缓冲器研究 一般来说路由器中的数据包缓冲器是按其所处位置来划分，缓冲器有三种：输 出缓冲器( o q ，o u t p u tq u e u e ) 输入缓冲器( i q ，i n p u tq u e u e ) 组合输入输出缓冲器 ( c i o q ，c o m b i n e di n p u ta n do u t p u tq u e u e s ) 。 输出缓冲器 输出缓冲是一种最基本的信元缓存方法，其结构如图2 1 ，到达输入端口的信 元马上被交换到相应的输出端口，在每个输出端口放置缓冲器，使其在每个时隙 最多接收n 个信元，而只有一个信元送到输出链路，其余留在缓冲器内。由于不 存在输入端的链头阻塞，所以o q 的优点是能够提供最优的吞吐量和延迟控制。 但为了保证o q 的正常运行，交换结构的内部带宽和输出队列的存储器访问速率 必须是输入端口链路速率的n 倍是输入端口数，如果输入速率不同，则为端口 速率之和) ，即要求n 倍的加速比。 l n i - 一 i 交换结构 1 1 -r 1 1 n 图2 1 输出缓冲器 输出型缓冲具有以下特点： 1 ) 当输出缓冲为无穷大时，不存在包头阻塞；有限的缓冲容量，也可以 减少冲突； 2 ) 由于存储器带宽的限制，纯输出型不适合于高速路由器。 输入缓冲器 为了克服输出缓冲器结构的可扩展性问题，高速路由器考虑采用输入缓冲器 ( i q ) 。其结构如图2 2 。到达的信元首先被保存在输入端口的缓冲区中，然后通过 调度算法决定信元何时通过交换结构传送到输出端口。i q 的优点是加速比n 为l ， 即交换结构的内部带宽和输出队列的存储器访问速率等于输入端口链路速率。但 是存在链头阻塞问题( h o l ，h e a do fl i n eb l o c ki n ) ；如果队列链头的信元被阻塞， 同队列到其他输出端口的信元就不能被转发。 第二章q o s 相关技术研究与选择 1 n 一 一 交换结构 一i 一2 l n 7 一 图2 2 输入缓冲器 输入缓冲器具有以下特点： 1 ) 输入缓冲型路由器最大流量5 8 6 ； 2 ) 存在包头阻塞效应：在缓冲队列中非队列头上的消息包，即使它所去的输 出口是空闲的，也无法输出； 3 ) 可以支持消息多播，但是实现比较复杂，并且其性能随流量增加而迅速下 降。 组合输入输出缓冲器 组合输入输出缓冲器在交换结构的输入端和输出端同时设置缓冲器。其结构 如图2 3 。采用单纯的输出缓冲时，如果加速因子小于n ，会发生数据包丢失。如 果同时在输入端也设置缓冲器，在发生竞争现象时，受加速因子限制而不能同时 传送到输出端缓冲器的数据包可以暂时保存在输入端缓冲器中，避免了数据包的 丢失。 l n - 一i 一 一l i ： 交换结构 一 一 一1 f r r l n 图2 3 组合输入输出缓冲器 组合输入输出缓冲器具有以下特点： 1 ) 为了提高性能，输出缓冲应大于输入缓冲； 2 ) 在给定输出缓冲大小的情况下，加速因子越大，其流量越大； 3 ) 由于各输入、输出采用独立缓冲器这种结构适合于内部高频传输。 2 2 2 数据包缓冲器选择 如上节所述，输出缓冲器具有良好的吞吐率和平均排队时延特性，而且可以 通过控制数据包在输出缓冲器的排队实现q o s 。但由于输出缓冲要求加速比大于 l ，所以当交换规模或端口速率增大时，输出缓冲结构实现更加复杂。例如当输入 端口数为3 2 、端口速率为1 0 g b p s 时，若采用5 1 2 b i t 并行数据宽度的存储器，其读 写周期就要1 6 n s ，目前的存储器速度很难满足。 分层轮循算法研究与a s i c 工程实现 输入缓冲器存在链头阻塞问题，研究表明，当端口数较多时，在所有输出均 匀分布的b e r n o u l l i 到达下，输入缓冲器只能达到5 8 6 的吞吐率。对于本文线速 为3 0 g b p s 的高速路由器而言，输入缓冲器显然是无法满足要求的。 由于组合输入输出缓冲器在输入端和输出端同时设置缓冲器，即使在处理高 速传输的数据包时，仍能保证不丢弃数据包。它完全符合高速路由器的设计需要， 在队列调度之前能很好地储存数据包。 2 3 队列管理算法研究与选择 对于高速路由器而言，当某个端口的数据流到达速度大于其输出速度时，就 会在路由器内产生拥塞，在使用完所有的缓冲区后，数据包将被丢失。当网络发 生拥塞时，队列管理器将决定哪些数据包可以被优先发送，哪些数据包将被丢弃。 队列调度器与队列管理器有着紧密的联系，它们共同保证了每条数据流得到相应 的网络服务质量。在实际的硬件设计过程中，队列调度器和队列管理器往往在同 一个模块中实现。 2 3 1 典型队列管理算法研究 队列管理算法按其对队列的处理方式可以分为主动队列管理方式和被动队列 管理方式，以下将例举两类管理方式中典型的算法 弃尾算法( t a i ld r o p ) 弃尾算法属于被动队列管理算法，它公平地处理所有的数据流，它不区分数 据流的类别。当队列发生阻塞时，队列的缓冲区都使用完时，随后到达的数据包 将被丢弃。直到阻塞被消除了或者队列的缓冲区有新的空间时，新到达的数据包 才能被存储到缓冲区中等待队列调度器的调度。 随机早期探测算法( r e d ) 随机早期探测算法是主动队列管理a q m ( a c t i v eq u e u em a n a g e m e n t ) 的典型代 表。它改变了过去以检测到丢包作为网络拥塞指示的方法，通过计算平均排队长 度发现初始的拥塞现象。该算法在路由器中设置两个阈值：m a x 和m i n ，对于每个 到达的数据包，计算其平均队列长度q a v g 。q a v g 与两个预先设定的阈值比较，当 当q a v g 小于最小的阈值m i n 时，数据包将被允许参与调度；当q a v g 超过最小的 阈值m i n 小于最大阈值m a x 时，数据包被随机丢弃：当q a v g 超过最大的阈值m a x 时，数据包将被丢弃。 第二章q o s 相关技术研究与选择 2 3 2 队列管理器算法选择 9 一 随机早期探测算法由于采用了主动队列管理方式，它能早期预测拥塞，平均队 列长度小，有利于吸收短期突发数据流，但同样它也存在参数确定较难，稳定性不 好的缺点。 弃尾算法会导致全局同步和公平性等问题，但它非常易于硬件实现，由于本 文涉及的路由器并不需要处理很复杂的网络情况，它主要面对的是企业级的用户。 采用随机早期探测算法虽然能很好的控制拥塞发生，但由于算法复杂度的增加而 造成a s i c 芯片面积和功耗的增加，对于整个设计而言是得不偿失的。所以弃尾算 法完全能满足本路由器在队列管理方面的需要，具体设计将在第四章中详细描述。 2 4 本章小结 本章主要研究了与队列调度算法紧密相关的数据包缓冲器和队列管理算法，根 据本文路由器的设计要求，设计了适合的数据包缓冲器以及队列管理器。它们将 有力地帮助队列调度器发挥其调度功能，在保证整个网络服务质量的过程中也起 到了不可或缺的作用。 第三章分层轮循调度算法研究 第三章分层轮循调度算法研究 在探索拥有延迟和公平性保证的队列调度算法上，前人做了大量的工作。通 用服务器共享( g 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 假设的流体模型很难 实际实现，这是因为因特网通讯是以数据包的形式进行的，数据包必须很快的传 输。尽管如此g p s 仍然是其它调度准则在公平性和延迟保证上的标尺。实际的调 度准则可以大致被分为两类：基于时间戳的队列调度算法和基于轮循的队列调度 算法。 时间戳调度算法虽然有很好的公平和延迟特性，但复杂度很高。而轮循调度 算法虽然易于实现，但它的延迟限制很差，而且存在输出脉冲现象。分层轮循调 度算法( s r r ) 尝试综合时间戳调度器的公平和延迟特性与轮循调度算法低复杂度 的优点，得到一种易于工程实现同时又拥有很好公平性和延迟特性的队列调度算 法。 。 3 1 分层轮循调度算法的理论基础 分层轮循调度算法是在以往队列调度算法的基础上，吸取两类主流调度算法 优点而得到的一种崭新的算法。前人在时间戳调度算法与轮循调度算法中做的大 量研究，为分层轮循调度算法奠定了坚实的基础，本节将详细介绍这两类调度算 法，并对两类调度算法中典型的调度算法举例介绍。 基于时间戳的调度器尝试通过计算每个包的时间戳来模仿g p s 的操作过程。 然后数据包以它们时间戳的递增次序来传输。这些算法大都能提供较好的公平性 和时延特性，但是时间复杂度也比较高，复杂度为o ( n ) 或o ( 1 0 9 n ) ，其中n 为系 统中数据流的数目。以下列举一些典型的基于时间戳的调度算法。 3 1 1 基于时间戳的调度算法研究 加权公平排队算法和最坏情况加权公平排队算法是基于时间戳调度算法中最 典型的算法。 1 ) 加权公平排队算法 加权公平排队算法( w e i g h t e df a i rq u e u i n g ) 计算每个数据包的时间戳，即它在 一个标准g p s 服务器中服务结束的时间。当给出了输出端口的比特率、所有活动 的队列中分组数量、每个队列的权重以及新到队伍分组的长度，就可以计算出每 个新到来的数据包的调度完成时间，这里的时间不一定是实际的时间，也可以是 比例于分组调度完成时间的一个数字。原理如图3 1 。 1 2 分层轮循算法研究与a s i c 工程实现 蛐t 粥嘲 ：国圜遂耍 r 删 蜥2 帮嘲 二【匾圆圆 l 懈il 锩il 獠 - - - - - 1 _ - - _ - - - _ - - 1 j - - - - _ _ _ j l j - _ _ - - - - - - 翔d 瞳8 叵一圈甲一一圈 图3 i 加权公平排队算法原理 当个数据包到达的时候，经过分类后进入到相应的队列中，调度器同时为 该数据包计算完成时间。当w f q 进行调度是，从所有分组中选择完成时间最早的 数据包作为下一个从输出端口传输出去的数据包。 加权公平排队算法的具有两个突出的优点： _ 由于给每个类型的数据流都分配了不同比例的输出带宽，因此能保证每个 数据流都得到服务。 通过在网络边缘和数据流控制策略的结合，w f q 可以提供在可接受延迟 下的带宽公平分配。 但同样w f q 也有受算法的限制，有以下的缺点： 目前w f q 实现方法主要是软件方式，而不是硬件方式，所以限制了它在 网络边界的低速接口上的应用。 _ 虽然服务类型不同的数据流之间不会互相影响，但是同一服务分类中的数 据流却仍然会相互影响。 - w f q 复杂的实现算法要求更大的存储空间来保存必要的状态信息。这些 状态信息随着数据包的到达或离开，都要求进行更新。 _ 复杂的计算削减了对高速接口中大量不同类数据流的支持。而且有时候为 了得到有保障的延迟要求而牺牲的用于计算的代价也许比增加的延迟大 很多。 2 ) 最坏情况加权公平排队算法 由于加权公平排队算法有以上缺点，后人在w f q 的基础上做了很多的改进， 其中最坏情况加权公平排队算法wf 2q ( w o r s t - c a s ef a i rw e i g h t e df a i rq u e u i n g ) 和 w f 2 q + 是其中最著名的。 w f 2 q 算法改变了w f q 算法选择分组的策略。与w f q 算法在所有等待调度 的数据包中选择下一个要发送的数据包不用，w f 2 q 算法首先需要对等待调度的 数据包进行资格测试，只有开始服务时间小于系统得虚拟时间的数据包才可以通 过测试。然后w f 2q 算法在通过测试的分组中选择具有最小服务时间的数据包进 露 鲨 第三章分层轮循调度算法研究 1 3 行发送。w f 2 q 与w f q 调度算法具有相同量级的复杂度，均为o ( n ) ( n 为待服务 的数据流数目) 。但由于算法上的改进使得采用w f 2 q 算法调度的网络，端到端的 时延抖动达到最小。 w f 2 q + ( w o r s t c a s ef a i rw e i g h t e df a i rq u e u i n g + ) 调度算法针对w f 2 q 重新定 义了系统虚拟时间的更新公式，从而简化了调度算法的复杂度，同样的w f 2 q + 算 法于w f 2 q 一样也是在通过资格测试的数据包中选择具有最小结束服务时间的数 据包进行发送，但由于重新定义了系统虚拟时间的计算方法，使其算法复杂度降 为o ( 1 0 9 n ) ，其中n 为等待调度的数据流的数目。 3 1 2 基于轮循的调度算法研究 轮循调度算法是另一种广泛应用的调度算法。这种调度算法的特点是以轮循 的方式来调度数据流。通过降低与时间戳调度器相关的分类时间瓶颈，轮循调度 算法实现了o ( 1 ) 的处理复杂度，且非常易于硬件实现。但是它也导致了比较差的 延时特性和的公平性。加权轮循调度算法和赤字轮循调度算法是轮循调度算法中 最典型的调度算法。 1 ) 加权轮循调度算法 加权轮循调度( w e i g h t e dr o u n dr o b i n ) 算法将从参与调度的数据包按照它们各 自的权重w e i g h t 分配到相应的队列中。每个队列根据其权重被分配了相应的带宽， 分配的方式为：每个轮循轮次中，该队列将被允许传送出相应的额定的数据包数， 当传递的数据包数达到额定数据包数或者队列中没有数据包时，下一个队列将被 服务。当所有的队列都传递完毕后，将开始新一个轮次的轮循。 加权轮循调度算法有以下优点： w r r 可以使用硬件实现，它可以被运用于高速接口的核心或边缘网络设 备上。 一w r r 根据每个队列的权重相对粗略的分配了其输出带宽。 由于采用了轮循的调度方式，保证所有队列都能得到部分的带宽，避免高 优先级的队列占据了所有的带宽，导致低优先级的队列出现带宽饥饿现象 ( b a n d w i d t hs t a r v a t i o n ) 。 加权轮循调度算法的缺点如下： 由于w r r 算法最初是被设计来保证a t m 的q o s ，在a t m 网络中传递的信 元是定长的，w r r 算法可以有效地分配网络的带宽。但当面对以太网中不定长的 数据包时，w r r 暴露出了带宽分配不公平的现象，而且更容易导致输出脉冲现象。 例如，当一个低权重的队列传递的都是包长很大的数据包时，它实际占据的输出 带宽比它实际应该分配的带宽大很多，而且还会导致输出脉冲的现象。 分层轮循算法研究与a s i c 工程实现 2 ) 赤字轮循调度算法 赤字轮循调度算法( d e f i c i tw e i g h t e dr o u n dr o b i n ) 是轮循方案中一个著名的例 子。d w r r 是设计用来改善w r r 调度算法的最基本的一类轮循调度算法。它采 用和w r r 相类似的分组方式，当队列中包含有变长分组时，d w r r 通过简单设 置队列的权重就能精确的实现对带宽的公平分配，避免了w r r 算法在调度变包长 数据包时带宽分配不均的缺点。同时由于d w r r 采用轮循的调度方式，它很容易 以硬件的方式实现，这使得d w r r 能应用于高速网络边界和核心路由器上。 在d w r r 调度算法中，每个队列都有以下一系列参数： - w d g h t ：定义相应的队列所占带宽的比例。 _ d e f i c i tc o u n t e r ：定义了每个调度器访问一个队列时允许从该队列中传送 的最大字节数( b y t e ) 。如果当前队列最前面的数据包长度大于d e f i c i t c o u n t e r 值，这个轮次中该队列将停止传送，而d e f i c i tc o u n t e r 的值将累 积到下一个轮循轮次。 _ q u a n t u m ：这个参数决定了相对应队列的权重，它的单位也是b y t e s 。比 如一个队列的q u a n t u m 值为另一个队列的两倍时，其所分配到的带宽也是 另一队列的两倍。 经典的d w r r 算法调度方式如图3 2 ，如果队列1 头部的数据包大于其 d e f i c i tc o u n t e r 值时，调度器移到下个队列为其服务。如果数据包小于等于 d e f i c i tc o u n t e r 值时，该数据包将被传送，同时d e f i c i tc o u n t e r 减去所传递数 据包的包长。当所有队列都被服务过后，每个队列的d e f i c i tc o u n t e r 值将在原 来值得基础上增加q u a n t u m 值。 a u e 啪t 拳沁魄q i 壤岫m n 】z 1 o q u e u e 2 2 5 魄a 枷种圈= 5 0 0 ) a i 袷u 3 b 概a i 嘲嘲= 5 0 0 图3 2 d w r r 算法原理图 d w r r 算法的优点如下： 1 ) 为不同队列提供了保护。当某一个队列中出现行为不端的数据流时，它将 无法影响到其它正常的队列。 2 ) 克服了w r r 算法在变长数据包传输中无法提供准确的带宽分配的缺点。 第三章分层轮循调度算法研究 能很好的根据队列的权重分配相应的带宽。 3 ) 由于采用轮循的调度方式，避免带宽饥饿现象，能有效地保证低优先级队 列中的数据传输。 4 ) 易于硬件实现，可以广泛的应用于高速网络设备中，如c i s c o 的g s r 系 列交换路由器。 当然d w r r 也有一些缺点： 1 ) d w r r 无法如时间戳调度算法一样准确地提供端到端的延迟保证。 2 ) 当传输单个数据包时，最坏情况下的延迟仍然与数据流数目n 成比例。 3 1 3 两类调度算法优缺点小结 基于时间戳的调度算法有很好的公平和延迟特性，但复杂度很高。尤其当数 据流的数目很大时，该调度算法的复杂度将大大增大，对于工程实现而言也增加 了非常大的难度。所以在实际运用中，该种算法只能运用于低速的网络路由器， 算法主要通过软件运算实现，无法用硬件实现。 基于轮循的调度算法由于其易于硬件实现，同时能有效地避免带宽饥饿现象， 因此其被广泛用于高速网络交换设备中。但采用轮循的调度方式，一旦一个队列 被服务了，无论它的权重多高，它都必须等待n 1 个其他队列被服务后才能再次 被服务到。同时在每个轮循轮次中，一个队列会马上把它所有配额的数据都传输 出去。这导致基于轮循的调度算法有糟糕的延迟和脉冲特性。 两类调度算法由于各自的缺点，使得它们无法非常好的保证网络的服务质量。 在实际的运用过程中也存在一定的局限性。 3 2 分层轮循调度算法设计思想 通过上节我们发现轮循调度算法和时间戳调度算法的优缺点正好互相弥补。 如果综合两类调度算法的优点，可以得到一种即易于硬件实现，运算复杂度相对 较低，又能够保证公平性的算法，分层轮循调度算法( s r r ) 工e 是遵循了这种思路设 计的。 3 2 1 分层轮循调度算法模型 假设存在n 条数据流石，以 共享输出链接的带宽r ，数据流z 有一个预 留带宽，i 必须满足 1 6 _ 一 分层轮循算法研究与a s i c 工程实现 r ( 3 - 1 ) 另外假设每条流z 的带宽小于r 。否则的话调度就没有什么意义，因为一条 数据流就占用了所有输出带宽。考虑输出链接的全部带宽，数据流z 的权重被 定义为它所预留的带宽。 w 2 簧 ( 3 _ 2 ) 换言之，一条数据流的权重w f 代表的输出带宽的部分就是预留给数据流z 的带 宽。因此 w 1 ( 3 - 3 ) 每条流的带宽是按照它们的权重来分配的。如果所有n 条数据流都就绪了， 即有数据包排队等待传输，平均分配到数据流z 的带宽应该是： 索啪 侉4 ， 因此分配给就绪数据流彳的带宽通常至少是它预留的带宽，；。当兰。w - - 1 h ；寸， 输出带宽被完整地在n 条数据流之间分配。 分层轮循调度器勉强算是轮循调度器，经过它给每条数据流分配时间片，当 一个数据流分配到一个时间片时，其队列中的数据包被允许从输出链接发送出去。 主要的调度决定是来决定在n 条数据流中哪条将会得到下一个时间片。然而为了 避免轮循算法糟糕的延迟特性，在同时保留其低复杂度的前提下，s r r 必须在按 照循环方式分配时间片前预先做一部分工作。同时得到以上两个优点的关键做法 是将数据流汇集成数据流组。 3 2 2 分层轮循调度算法数据流分层 数据流按照他们的权重被“分层 到数据流组中，形式上，当k 1 时，数据流组e 定义为： e = k1 2 。钒 击) 仔5 ， 数据流组疋将所有权重近似于2 。的数据流归类到一起，图3 3 举例说明数据 流如何根据它们的权重被聚合入数据流组。 第三章分层轮循调度算法研究 l 去 l l 裒 1 7 图3 3s r r 算法数据流组聚合 流石的权重2 言，它属于互组，流五和流石的权重分别为w 22 言和w 32 素， 它们属于e 组，最后流五和流石的权重分别为w 4 = 壶和w 5 = 去，它们属于只组。 l ol o 根据定义属于同一个e 组的任何两个数据流z 和的权重都在一个相邻的2 的倍 数之间，对于每个k ，札表示e 的基数。简单起见，假设所有属于同一个数据流 组的数据流都就绪，当一个数据流f 未就绪时，它将从相应的数据流组e 中被移 出，当它再次就绪时，它将被重新加入到e 中。 理论上带宽是无限可分的，一条数据流可以预定输出带宽中任意小的部分。在 实际使用中，带宽按固定尺寸的间隔被划分。假设r 代表可以分给一条数据流的最 小带宽单位。如果一条数据流有r 的预留带宽，则它属于数据组e ，其 击， 击。因此需要维护的数据流组数量为刀：r 1 0 9 ：墨 。举例而言，输出 厶厶lrj 带宽为4 0 g 的网络设备，最小的预留带宽为1 k 时，它所需维护的数据流组数量仅 为1 6 个。 将数据流分层到数据组中，分层轮循算法可以为理解为一个两步调度器。第 一步( 中间组调度) 先从n 个数据流组中选择一个组来调度，由于将数据流分层 到数据组中使得这步实现起来更简单些，因为相对于要考虑潜在的很大数量的n 条数据流，现在我们只需要考虑相对小数量的n 个数据组。第二步( 内部组调度) 则从属于那个组中的所有数据流中选择一条数据流来调度，这步同样比较简单， 因为所有属于同一数据组的数据流都有很相近的权重。第一步使用同其他时间戳 调度器类似的截止时间机带u ( d c a d l i n cm e c h a n i s m ) ，第二步为一个基本的轮循机制。 因此，分层轮循算法也可以被认为是两种调度类型调度器的一种混合体。 分层轮循算法研究与a s i c 工程实现 3 3 分层轮循调度算法的实现 分层轮循调度算法主要有两个调度器实现，第一个为中间组调度器，它主要 作用为给数据流组分配时间片，它是基于时间戳的调度方式；第二个调度器为内 部组调度器，它负责在分配到时间片的数据流组内选择数据流输出，它是基于轮 循的调度方式。 3 3 i 中间组调度器实现 中间组调度算法中，必须阐明2 个概念：时钟时间和调度间隔。 为了调度的目的，时间按照时间片来度量，时间片用一个从0 开始的非负整 数来计数。时钟时间用t 表示，它涉及当前时间片。每个时间片最多被分配给一个 数据流，在这个期间该数据流将被服务