路由器原理与设计讲稿6-交换网络.ppt

路由器原理与设计之六：交换网络及路由器实现中的其他关键技术,内 部 通 信,路由器总体结构,高 速 交 换 网 络（主备）,内 部 通 信（主/备）,主控/管理模块,主 控 模 块（主/备）,转发引擎,线路接口,转发引擎,线路接口,转发引擎,线路接口,外部接口,外部接口,操作维护台,外部接口,本 章 内 容,交换网络的基本原理交换网络分类调度策略缓存器管理组播实现QoS支持,输入缓存与控制,输出缓存与控制,输 入,输 出,输入缓存与控制,输出缓存与控制,输入缓存与控制,输出缓存与控制,输入缓存与控制,输出缓存与控制,6.1交换网络的基本原理,输入缓存与控制,输出缓存与控制,输 入,输 出,输入缓存与控制,输出缓存与控制,输入缓存与控制,输出缓存与控制,输入缓存与控制,输出缓存与控制,合 路,缓 存,分 发,6.1交换网络的基本原理,本 章 内 容,交换网络的基本原理交换网络分类调度策略缓存器管理组播实现QoS支持,共享内存Speed is limited by memory access speed共享总线Speed is limited by bus capacitance空分复用crossbarSpeed is limited by the scheduler,6.2交换网络分类,Shared Memory,6.2交换网络分类共享内存,Route Processor,Memory,DMA,Route Cache,Memory,MAC,Line Card,DMA,Route Cache,Memory,MAC,Line Card,DMA,Route Cache,Memory,MAC,Line Card,Bus,Cache updates,Shared Bus,6.2交换网络分类共享总线,Switched Crossbar,6.2交换网络分类crossbar,6.2交换网络分类crossbar,空分Crossbar是一个交换矩阵，在同一时刻（时隙）每一个输出只能连接到一个输入上，因而当多个输入往同一输出端发包时，必须有缓存，根据缓存器的位置不同，交换结构分为，,输出排队（OQ）结构输入排队（IQ）结构虚拟输入排队（VOQ）组合输入输出排队（CIOQ）结构,输出排队（OQ）结构,优点：高性能；高QoS保障；大量成熟的调度策略可选用缺点：N倍加速问题，在高速环境下应用受限,6.2交换网络分类-输出排队（OQ）结构,Packet Buffering,QueuePacket,BufferMemory,QueuePacket,BufferMemory,QueuePacket,BufferMemory,6.2交换网络分类输出排队（OQ）结构,QueuePacket,BufferMemory,QueuePacket,BufferMemory,QueuePacket,BufferMemory,1,2,N,1,2,N,N times line rate,6.2交换网络分类-输出排队（OQ）结构,虽然输出排队能提供很好的性能，但商用存储器访问速率的限制制约了其在高速路由器中的使用,输出排队（OQ）结构,6.2交换网络分类-输出排队（OQ）结构,优点：不需要加速缺点：链头（HOL）阻塞；对QoS支持较差；调度策略复杂度高,6.2交换网络分类-输入排队（IQ）结构,QueuePacket,BufferMemory,QueuePacket,BufferMemory,QueuePacket,BufferMemory,Scheduler,6.2交换网络分类-输入排队（IQ）结构,A Router with Input Queues,The best that any queueing system can achieve.,理论上吞吐率可下降为原来的58.6%,6.2交换网络分类输入排队的HOL阻塞,6.2交换网络分类输入排队的HOL阻塞,The best that any queueing system can achieve.,6.2交换网络分类输入排队的HOL阻塞,虚拟输入排队（VOQ）,优点：克服了HOL阻塞，提高了吞吐率，理论上可达100%缺点：需要集中式的调度策略支持，较差的QoS保证,对每个输出都在输入端建立一个单独的队列FIFO,6.2交换网络分类,6.2交换网络分类 Virtual Output Queues,The best that any queueing system can achieve.,6.2交换网络分类 Virtual Output Queues,基于输入排队的管理策略,最大匹配MSM（Maximum Size Matching）复杂度高，硬件实现复杂，实际用极大匹配（maximal matching）来近似SLIP（iterative round-robin matching with SLIP）支持优先级和公平调度。扩展版的ESLIP支持组播最大权重匹配MWM（Maximum Weighed Matching）LQF（Longest Queue First）和OCF（Oldest Cell First）算法硬件实现复杂采用iLQF和iOCF来迭代逼近，但实现依然相当复杂稳定结合配对GSA（Gale-Shapley Algorithm）算法利用定义的优先级来调度分组，可以获得好的吞吐率和时延限度输入排队的管理策略都采用了避免HOL阻塞的方法，努力实现好的QoS保证,6.2交换网络分类组合输入输出排队（CIOQ）结构,优点：2倍加速下可模拟实现OQ的性能；适合任意端口数目和流量模式缺点：调度策略复杂度过高，仅具有理论意义,在输入和输出端都建立队列来缓存分组,6.2交换网络分类组合输入输出排队（CIOQ）结构,发展的观点,超摩尔定律 传输速率每九个月翻一番。,结论：处理速率的发展无法跟上传输速率发展的步伐，因此采用并行交换结构是高速路由器的必然趋势。,摩尔定律 CPU的处理速率每18个月将翻一番。,6.2交换网络分类,优点：处理速度要求低，可提供高性能交换,缺陷：在一定程度上导致系统控制维护复杂,6.2交换网络分类并行交换结构,6.2交换网络分类定长包交换与不定长包交换,定长包交换：Crossbar，交换矩阵中的开关转换每隔固定的时间变换一次不定长包交换：无法保证每一路包的传输时间是相等的，因此若用Crossbar交换结构，必须进行切片。,6.2交换网络分类不定长包交换,基于FPGA的88不定长包交换结构,6.2交换网络分类不定长包交换,本 章 内 容,交换网络的基本原理交换网络分类调度策略缓存器管理组播实现QoS支持,调度机是网络节点中的一个组件，它依照一定的调度算法选择缓存队列中最需要发送的包送到输出链路上包调度算法管理着最重要的网络资源输出链路带宽。良好的调度算法能够隔离各个用户流，起到防火墙的作用，为路由器提供安全保障，保证正常使用网络的用户不受其他用户有意或无意的干扰。调度算法直接控制包的时延而缓存器管理控制包的丢失率，所以调度算法与缓存器管理策略控制着QoS中最重要的性能指标时延和丢包率。时延和丢包率是密切相关的，对一个业务流，分配给它的带宽越多，它需要的缓存空间越小，另外，大的包时延容易导致更大的包丢失率。因而包调度算法和缓存器管理策略是网络保证业务QoS最重要两项关键技术,6.3调度策略,6.3调度策略,调度算法可分为尽职工作型（Work-conserving）和非尽职工作型（Non Work-conserving）采用尽职工作型调度算法时，只有缓存器中没有待发送的包时，输出链路才会空闲非尽职工作型调度算法则可能在缓存器中还有包时，输出链路空闲。尽职工作型调度算法可以最大限度地利用输出链路的带宽资源非尽职工作型调度算法在控制时延抖动时往往是一种较好的选择，即包可以进行时延以满足特定的时延要求。,6.3调度策略,现有调度算法主要分为三类：,基于轮询的调度策略(PRR，BBRR，WRR，WFQ,SFQ，DRR，GPS，PGPS，WF2Q)基于保证单节点上时延上界的调度策略(EDF、Stop-and-Go)基于保证端到端时延上界的调度策略(FIFO+、Virtual Clock、SCED),6.3调度策略-实时调度算法研究现状,6.3调度策略-实时调度算法研究现状,包轮询或逐包调度策略（Packet Round Robin；PRR）Nagle的思想是在每一网络节点上将不同流放入不同的队列中，然后逐个轮询调度输出各队列的包，跳过空队列，若有多个活动的流，则每个队列每一轮询周期发送一个包,加权公平排队策略（Weighted Fair Queuing）Demers，Keshav和Shenker对Nagle的算法进行了改进，提出了逐比特轮询调度算法（Bit-by-bit Round Robin Service;BBRR），轮询机每一轮从每一队列中调度一比特而非一个包，因而解决了包长不同带来的不公平，但这仅仅是一个理论分析方法，因为发送时不可能将包打碎。加权逐比特轮询调度算法 当轮询到某一队列时，从该队列中调度的比特数由该队列的权值决定。,6.3调度策略-实时调度算法研究现状,它是BBRR的实用版，其工作原理如下：1.在理论上计算Fi（i=1,2,K；K为队列数）的值，Fi为采用加权BBRR策略时，第i个队列中的包最后一比特被调度出去的时间；2.比较各个队列Fi的大小。若FjFi(i=1,2,K,ij)则调度第j个队列中的一个包输出。FjFi表明采用加权BBRR策略时，所有队列中正在被服务的包中第j个队列的包最先被服务完毕。3.计算第j个队列下一个包的结束时间并记为Fj，回到第二步。,加权公平排队策略(WFQ),6.3调度策略-实时调度算法研究现状,6.3调度策略-实时调度算法研究现状,统计公平排队（Stochastic Fair Queuing；SFQ）SFQ算法是WFQ算法的改进型，是为了解决WFQ中队列太多，计算复杂而引入的调度策略。与WFQ算法的不同之处在于SFQ算法采用Hash变换压缩了队列数目，而调度原理与WFQ完全一样，所有映射到一个队列中的流同等对待。将大量的业务流压缩映射到少量的队列中，可大大减少队列数目。这使得该算法的运算复杂度由O(n)减少到O(1)数量级（n为流数）。该算法的缺陷是当发生碰撞时，会出现不公平。由于其公平性是以一定概率呈现的，所以称为统计公平排队。,加权循环服务(Weighted Round Robin;WRR)调度算法WRR为PRR的改进型。每一个队列具有一个权值，轮询到该队列时，根据其权值发送一定量的数据。与PRR最大的不同在于WRR与“字节”打交道，而不是与“包”打交道。每一轮轮询，调度机都访问所有的队列，当访问到某一队列时，根据权值决定从该队列调度多少个字节输出。与BBRR一样，由于WRR以“字节”分配带宽，而IP网络不能发送半个包，必须寻找可实现的改进或近似方法，后面介绍的欠帐式轮询算法即是WRR算法的一种实现。,6.3调度策略-实时调度算法研究现状,6.3调度策略-实时调度算法研究现状,欠帐式轮询（Deficit Round Robin；DRR)111 调度算法针对不定长包的调度不公平问题，Shreedhar和Varghese提出了一种公平调度算法DRR算法，它是WRR算法的一种改进型。其工作原理如下：采用SFQ算法减少队列数；逐包轮询；轮询机每一轮为每一对列分配N字节输出带宽，为每一队列设置一储蓄计数器Ci(i=1,2,K;K为队列数)。(a)起始状态所有Ci=0；(b)当轮询到一个队列i时，为计数器存入该轮应该输出的字节数N，Ci=N+Ci，如果队列中有整包，且排在队头的那个包的包长Li1Ci（包长一字节为单位），将该包调度输出，并令Ci=Ci-Li1，再观察该队列中是否有整包，若有，且排在队头的包的长度Li2Ci，则将第二个包调度输出，直至该队列中无整包或计数器的值小于队列中第一个包的长度，转到下一队列；(c)如果轮询到一个队列i，且为计数器存入该轮应该输出的字节数N(Ci=N+Ci)之后，发现队列中无整包或第一个包的包长Li1Ci，则将该轮应发的字节数N储蓄起来，留到下一轮使用，转到下一队列；(d)如果轮询到队列i时，队列是空的，则将计数器Ci清零，这一做法是为了不让Ci无限增大，虽然显得不很公平，但是却能够防止突发的形成和对其他队列的影响。DRR算法中，每个队列的计数器记录了轮询机亏欠该队列的字节数，因此称为欠帐式轮询调度算法。,6.3调度策略-实时调度算法研究现状,虚时钟（Virtual Clock）调度算法81,97虚时钟的概念来源于TDM系统，由于每一用户只能在给定的时隙内发送数据，因而TDM系统没有用户间的干扰。但是，当某一用户在某一段时间内没有数据发送时，它所对应的时隙就空闲，带宽资源被浪费了。虚时钟算法的目的就是既得到TDM系统的隔离作用，又保持包交换系统的统计复用效果。TDM系统是在实时钟控制下工作，Virtual Clock算法是在虚时钟控制下工作。假设某一流到达路由器的包具有虚时间空间的固定速率，则每当一个包到达时，就有一个时隙的时间过去了。依据这一思想，为每一数据流指定一个虚时钟，每当这一流的一个包到达时，该时钟走一步，步幅Vticki等于包到达的间隔（设包长固定），如果某一流按照约定的速率发包，则虚时钟的跳变时刻就在实际时间附近。,一般处理器共享（Generalized Processor Sharing Algorithm；GPS）,6.3调度策略-实时调度算法研究现状,6.3调度策略-实时调度算法研究现状,逐包一般处理器共享（Packet-by-Packet GPS；PGPS）算法2,82,84 PGPS算法是GPS的近似实现，它以逐包调度的方式进行。设Fi是采用GPS调度算法时第i个队列中包P的最后一个比特离开节点的时间，则PGPS依照Fi的顺序调度各队列中的包。可见PGPS算法的实际效果同加权公平排队策略完全一样。PGPS的意义在于：在采用漏桶算法限制各个业务时，网络能够提供一个端到端时延的理论上限。,自定时公平排队策略(Self Clocked Fair Queuing;SCFQ)前述几种方案的缺点在于难于实现，计算复杂；需要跟踪GPS；缓存器管理复杂。在SCFQ调度方式中，时标是依照实时系统的事件计算，而非参照GPS系统，所以不必跟踪理想GPS系统的过程，它是一个低复杂度和GPS近似程度的折衷，所以其时延特性不如GPS严格。,6.3调度策略-实时调度算法研究现状,WF2Q调度算法对WFQ做了改进，WFQ算法的调度原则是根据GPS算法计算出的调度顺序调度包；而WF2Q调度算法的基本原则仍然是根据GPS算法计算的顺序调度包，但是采用GPS算法调度时，已开始发送的包优先,WF2Q(Worst-case Fair Weighted Fair Queueing),6.3调度策略-实时调度算法研究现状,Stop-and-Go Stop-and-Go最早由贝尔通信研究所的J.Golestani提出，目的在于在网络的节点上保持业务的平滑特性，防止突发的形成，提供时延和包丢失率的保证。采用Stop-and-Go调度策略时，端到端的传输速率在连接建立时就根据可用的网络资源确定了，Stop-and-Go由在源节点上的每一个连接的接入控制策略（在时间间隔T内每一流发送的数据不能超过r比特）和内部节点上的特殊服务策略组成。Stop-and-Go采用帧结构，将时间轴分成长度为T的帧。所有在一个给定帧内到达的包都将在下一帧内发送，以保证业务的平滑特性，防止突发形成。传输时延抖动也可控制在一定范围内。,6.3调度策略-实时调度算法研究现状,6.3调度策略-实时调度算法研究现状,WF2Q(Worst-case Fair Weighted Fair Queueing),补偿性轮询调度算法的原理框图（Compensating Round Robin;CRR）,6.3调度策略-CRR调度算法,6.3调度策略-CRR调度算法,6.3调度策略-CRR调度算法仿真结果,6.3调度策略-CRR调度算法测试结果,CRR调度算法对不同包长的流的公平性测试：,CRR调度算法对不同速率流的公平性测试：,6.3调度策略-CRR调度算法测试结果,6.3调度策略-CRR调度算法实现电路,6.3调度策略-CRR调度算法的特点,CRR调度算法的优缺点：,公平特性好(FairnessIndexi 0.5,2)运算复杂度小(处理一个包的运算量为O（1）)保证实时业务的时延特性需要缓存器管理策略 的支持,需要研究良好的缓存器管理策略,本 章 内 容,交换网络的基本原理交换网络分类调度策略缓存器管理组播实现QoS支持,缓存（Buffering）网络节点接收到达该节点的包，然后发送到相应的目的线路上。如果在某些时间间隔内，到达包的速率超过了输出线路的速率，则需要对输入报文进行缓存。缓存器不能增加带宽，但可增加带宽的利用率，它就象一条河中的水库，能吸收短时突发，利用线路空闲资源。主要的缓存技术有共享存储器方式和每流单独缓存方式缓存器的采用对传送标准数据业务（如文件传输等）非常有利，但是传送那些对对时延敏感的多媒体业务时必须要特别注意，因为缓存技术是靠增加端到端的时延来提高带宽利用率的。,6.3 缓存器管理,6.3 缓存器管理,缓存器管理缓存器管理机制是在缓存器已满或将满时的丢包策略。缓存器管理机制仅仅在一个队列中起作用，若有许多个队列，各队列可采用不同的丢包策略。缓存器管理主要有先到先丢(FIFD)、末尾丢弃（Drop Tail）、随机早期探测（Random Early Detection,RED）、标记随机早期探测（RED with IN and OUT bit;RIO）和加权随机早期探测（Weighted RED；WRED）机制。,共享存储器缓存技术和每流单独缓存技术,共享存储器缓存技术和每流单独缓存技术,6.3 缓存器管理,末尾丢弃(Drop Tail),标记随机早期探测(RIO),随机早期探测(RED),6.3 缓存器管理管理算法,支持业务分类 具有随机早期探测的特点，可防止链路速率振荡 与CRR调度算法相结合可支持不同业务的不同服 务质量需求，如保证实时业务的时延特性,CBRED(Classification Based Random Early Detection)缓存器管理策略的特点：,CRR+CBRED 提供QoS保证,6.3 缓存器管理管理算法CBRED,本 章 内 容,交换网络的基本原理交换网络分类调度策略缓存器管理组播实现QoS支持,6.5组播实现,组播实现的方法：,按包处理，逐一复制按端口（接口）复制,输入缓存与控制,输出缓存与控制,输 入,输 出,输入缓存与控制,输出缓存与控制,输入缓存与控制,输出缓存与控制,输入缓存与控制,输出缓存与控制,合 路,缓 存,分 发,6.5组播实现按端口（接口）复制,本 章 内 容,交换网络的基本原理交换网络分类调度策略缓存器管理组播实现QoS支持,6.6 QoS支持,QoS支持方法：,调度算法缓存器管理调度算法缓存器管理,缓存器,调度机,6.6 QoS支持调度算法支持,根据包的优先级调度包输出,：高优先级包,：中优先级包,：低优先级包,：丢弃的包,6.6 QoS支持缓存器管理支持,