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

路由器原理与设计之六：交换网络及路由器实现中的其他关键技术兰巨龙E-mail:[e-mail]中国人民解放军信息工程大学信息工程学院内部通信路由器总体结构高速交换网络（主\备）内部通信（主/备）主控/管理模块主控模块（主/备）转发引擎线路接口转发引擎线路接口转发引擎线路接口外部接口外部接口操作维护台外部接口本章内容交换网络的基本原理交换网络分类调度策略缓存器管理组播实现QoS支持输入缓存与控制输出缓存与控制输入输出输入缓存与控制输出缓存与控制输入缓存与控制输出缓存与控制输入缓存与控制输出缓存与控制6.1交换网络的基本原理输入缓存与控制输出缓存与控制输入输出输入缓存与控制输出缓存与控制输入缓存与控制输出缓存与控制输入缓存与控制输出缓存与控制合路缓存分发6.1交换网络的基本原理本章内容交换网络的基本原理交换网络分类调度策略缓存器管理组播实现QoS支持共享内存Speedislimitedbymemoryaccessspeed共享总线Speedislimitedbybuscapacitance空分复用crossbarSpeedislimitedbythescheduler6.2交换网络分类SharedMemory6.2交换网络分类－共享内存RouteProcessorMemoryDMARouteCacheMemoryMACLineCardDMARouteCacheMemoryMACLineCardDMARouteCacheMemoryMACLineCardBusCacheupdatesSharedBus6.2交换网络分类－共享总线SwitchedCrossbar6.2交换网络分类－crossbar6.2交换网络分类－crossbar空分Crossbar是一个交换矩阵，在同一时刻（时隙）每一个输出只能连接到一个输入上，因而当多个输入往同一输出端发包时，必须有缓存，根据缓存器的位置不同，交换结构分为，输出排队（OQ）结构输入排队（IQ）结构虚拟输入排队（VOQ）组合输入输出排队（CIOQ）结构输出排队（OQ）结构优点：高性能；高QoS保障；大量成熟的调度策略可选用缺点：N倍加速问题，在高速环境下应用受限6.2交换网络分类-输出排队（OQ）结构PacketBufferingLookupIPAddressUpdateHeaderHeaderProcessingAddressTableLookupIPAddressUpdateHeaderHeaderProcessingAddressTableLookupIPAddressUpdateHeaderHeaderProcessingAddressTableQueuePacketBufferMemoryQueuePacketBufferMemoryQueuePacketBufferMemoryBufferManagerBufferMemoryBufferManagerBufferMemoryBufferManagerBufferMemory6.2交换网络分类－输出排队（OQ）结构LookupIPAddressUpdateHeaderHeaderProcessingAddressTableLookupIPAddressUpdateHeaderHeaderProcessingAddressTableLookupIPAddressUpdateHeaderHeaderProcessingAddressTableQueuePacketBufferMemoryQueuePacketBufferMemoryQueuePacketBufferMemoryDataHdrDataHdrDataHdr12N12NNtimeslinerateNtimeslinerate6.2交换网络分类-输出排队（OQ）结构虽然输出排队能提供很好的性能，但商用存储器访问速率的限制制约了其在高速路由器中的使用输出排队（OQ）结构6.2交换网络分类-输出排队（OQ）结构优点：不需要加速缺点：链头（HOL）阻塞；对QoS支持较差；调度策略复杂度高6.2交换网络分类-输入排队（IQ）结构LookupIPAddressUpdateHeaderHeaderProcessingAddressTableLookupIPAddressUpdateHeaderHeaderProcessingAddressTableLookupIPAddressUpdateHeaderHeaderProcessingAddressTableQueuePacketBufferMemoryQueuePacketBufferMemoryQueuePacketBufferMemoryDataHdrDataHdrDataHdr12N12NDataHdrDataHdrDataHdrScheduler6.2交换网络分类-输入排队（IQ）结构0%20%40%60%80%100%LoadDelayARouterwithInputQueuesThebestthatanyqueueingsystemcanachieve.理论上吞吐率可下降为原来的58.6%6.2交换网络分类－输入排队的HOL阻塞6.2交换网络分类－输入排队的HOL阻塞0%20%40%60%80%100%LoadDelayThebestthatanyqueueingsystemcanachieve.2258%6.2交换网络分类－输入排队的HOL阻塞虚拟输入排队（VOQ）优点：克服了HOL阻塞，提高了吞吐率，理论上可达100%缺点：需要集中式的调度策略支持，较差的QoS保证对每个输出都在输入端建立一个单独的队列FIFO6.2交换网络分类6.2交换网络分类－VirtualOutputQueues0%20%40%60%80%100%LoadDelayThebestthatanyqueueingsystemcanachieve.6.2交换网络分类－VirtualOutputQueues基于输入排队的管理策略最大匹配MSM（MaximumSizeMatching）复杂度高，硬件实现复杂，实际用极大匹配（maximalmatching）来近似ίSLIP（iterativeround-robinmatchingwithSLIP）支持优先级和公平调度。扩展版的ESLIP支持组播最大权重匹配MWM（MaximumWeighedMatching）LQF（LongestQueueFirst）和OCF（OldestCellFirst）算法硬件实现复杂采用iLQF和iOCF来迭代逼近，但实现依然相当复杂稳定结合配对GSA（Gale-ShapleyAlgorithm）算法利用定义的优先级来调度分组，可以获得好的吞吐率和时延限度输入排队的管理策略都采用了避免HOL阻塞的方法，努力实现好的QoS保证6.2交换网络分类－组合输入输出排队（CIOQ）结构优点：2倍加速下可模拟实现OQ的性能；适合任意端口数目和流量模式缺点：调度策略复杂度过高，仅具有理论意义在输入和输出端都建立队列来缓存分组6.2交换网络分类－组合输入输出排队（CIOQ）结构发展的观点超摩尔定律传输速率每九个月翻一番。结论：处理速率的发展无法跟上传输速率发展的步伐，因此采用并行交换结构是高速路由器的必然趋势。摩尔定律CPU的处理速率每18个月将翻一番。6.2交换网络分类优点：处理速度要求低，可提供高性能交换缺陷：在一定程度上导致系统控制维护复杂RR1rrrrrr子层交换结构分路器分路器R1RNN12K合路器合路器6.2交换网络分类－并行交换结构6.2交换网络分类－定长包交换与不定长包交换定长包交换：Crossbar，交换矩阵中的开关转换每隔固定的时间变换一次不定长包交换：无法保证每一路包的传输时间是相等的，因此若用Crossbar交换结构，必须进行切片。轮询调度机8个分离式的轮询调度机2倍加速带优先级控制输入控制输出缓存按优先级排队输出控制输入缓存(按输出端口排队00输入控制输出缓存按优先级排队输出控制输入缓存(按输出端口排队nn输入控制输出缓存按优先级排队输出控制输入缓存(按输出端口排队77::::::::::::输入接口输出接口板级处理机接口统计信息及状态信息统计信息6.2交换网络分类－不定长包交换基于FPGA的8×8不定长包交换结构输入控制分路/组播复制高速输入到0端口的缓存到7端口的缓存0端口的优先级0报文0端口的优先级7报文到n端口的缓存0端口的优先级m报文输出控制高速输出输入控制分路/组播复制高速输入到0端口的缓存到7端口的缓存n端口的优先级0报文n端口的优先级7报文到n端口的缓存n端口的优先级m报文输出控制高速输出输入控制分路/组播复制高速输入到0端口的缓存到7端口的缓存7端口的优先级0报文7端口的优先级7报文到n端口的缓存7端口的优先级m报文输出控制高速输出0端口带优先级调度n端口带优先级调度7端口带优先级调度0n77n0板级处理机接口统计与自检6.2交换网络分类－不定长包交换本章内容交换网络的基本原理交换网络分类调度策略缓存器管理组播实现QoS支持调度机是网络节点中的一个组件，它依照一定的调度算法选择缓存队列中最需要发送的包送到输出链路上包调度算法管理着最重要的网络资源——输出链路带宽。良好的调度算法能够隔离各个用户流，起到防火墙的作用，为路由器提供安全保障，保证正常使用网络的用户不受其他用户有意或无意的干扰。调度算法直接控制包的时延而缓存器管理控制包的丢失率，所以调度算法与缓存器管理策略控制着QoS中最重要的性能指标——时延和丢包率。时延和丢包率是密切相关的，对一个业务流，分配给它的带宽越多，它需要的缓存空间越小，另外，大的包时延容易导致更大的包丢失率。因而包调度算法和缓存器管理策略是网络保证业务QoS最重要两项关键技术6.3调度策略6.3调度策略图3.3包调度原理示意图调度算法可分为尽职工作型（Work-conserving）和非尽职工作型（NonWork-conserving）采用尽职工作型调度算法时，只有缓存器中没有待发送的包时，输出链路才会空闲非尽职工作型调度算法则可能在缓存器中还有包时，输出链路空闲。尽职工作型调度算法可以最大限度地利用输出链路的带宽资源非尽职工作型调度算法在控制时延抖动时往往是一种较好的选择，即包可以进行时延以满足特定的时延要求。6.3调度策略现有调度算法主要分为三类：基于轮询的调度策略(PRR，BBRR，WRR，WFQ,SFQ，DRR，GPS，PGPS，WF2Q)基于保证单节点上时延上界的调度策略(EDF、Stop-and-Go)基于保证端到端时延上界的调度策略(FIFO+、VirtualClock、SCED)6.3调度策略-实时调度算法研究现状6.3调度策略-实时调度算法研究现状包轮询或逐包调度策略（PacketRoundRobin；PRR）Nagle的思想是在每一网络节点上将不同流放入不同的队列中，然后逐个轮询调度输出各队列的包，跳过空队列，若有多个活动的流，则每个队列每一轮询周期发送一个包图3.4逐包调度策略示意图加权公平排队策略（WeightedFairQueuing）Demers，Keshav和Shenker对Nagle的算法进行了改进，提出了逐比特轮询调度算法（Bit-by-bitRoundRobinService;BBRR），轮询机每一轮从每一队列中调度一比特而非一个包，因而解决了包长不同带来的不公平，但这仅仅是一个理论分析方法，因为发送时不可能将包打碎。加权逐比特轮询调度算法当轮询到某一队列时，从该队列中调度的比特数由该队列的权值决定。6.3调度策略-实时调度算法研究现状它是BBRR的实用版，其工作原理如下：1.在理论上计算Fi（i=1,2,,K；K为队列数）的值，Fi为采用加权BBRR策略时，第i个队列中的包最后一比特被调度出去的时间；2.比较各个队列Fi的大小。若FjFi(