《路由器原理与设计讲稿6-交换网络》由会员分享，可在线阅读，更多相关《路由器原理与设计讲稿6-交换网络（70页珍藏版）》请在金锄头文库上搜索。
1、路由器原理与设计路由器原理与设计之六：之六：交换网络及路由器实现中的其他关键技术交换网络及路由器实现中的其他关键技术交换网络及路由器实现中的其他关键技术交换网络及路由器实现中的其他关键技术内内 部部 通通 信信路由器总体结构路由器总体结构高高 速速 交交 换换 网网 络络（主主备备）内内 部部 通通 信（主信（主/备）备）主控主控/管理模块管理模块主主 控控 模模 块块（主（主/备）备）转发引擎转发引擎线路接口线路接口转发引擎转发引擎线路接口线路接口转发引擎转发引擎线路接口线路接口外外部部接接口口外外部部接接口口操作维护台操作维护台外外部部接接口口本本 章章 内内 容容n交换网络的基本原理交换
2、网络的基本原理n交换网络分类交换网络分类n调度策略调度策略n缓存器管理缓存器管理n组播实现组播实现nQoS支持支持输入缓存与控制输入缓存与控制输出缓存与控制输出缓存与控制输输 入入输输 出出输入缓存与控制输入缓存与控制输出缓存与控制输出缓存与控制输入缓存与控制输入缓存与控制输出缓存与控制输出缓存与控制输入缓存与控制输入缓存与控制输出缓存与控制输出缓存与控制6.1交换网络的基本原理交换网络的基本原理输入缓存与控制输入缓存与控制输出缓存与控制输出缓存与控制输输 入入输输 出出输入缓存与控制输入缓存与控制输出缓存与控制输出缓存与控制输入缓存与控制输入缓存与控制输出缓存与控制输出缓存与控制输入缓存与控
3、制输入缓存与控制输出缓存与控制输出缓存与控制合合 路路缓缓 存存分分 发发6.1交换网络的基本原理交换网络的基本原理本本 章章 内内 容容n交换网络的基本原理交换网络的基本原理n交换网络分类交换网络分类n调度策略调度策略n缓存器管理缓存器管理n组播实现组播实现nQoS支持支持n共享内存Speed is limited by memory access speedn共享总线Speed is limited by bus capacitancen空分复用crossbarSpeed is limited by the scheduler6.2交换网络分类交换网络分类Shared MemoryShar
4、ed Memory6.2交换网络分类交换网络分类共享内存Route ProcessorMemoryDMARoute CacheMemoryMACLine CardDMARoute CacheMemoryMACLine CardDMARoute CacheMemoryMACLine CardBus Cache updatesShared BusShared Bus6.2交换网络分类交换网络分类共享总线Switched CrossbarSwitched Crossbar6.2交换网络分类交换网络分类crossbar6.2交换网络分类交换网络分类crossbar空分空分Crossbar是一个交换矩阵
5、，在同一时刻（时是一个交换矩阵，在同一时刻（时隙）每一个输出只能连接到一个输入上，因而当隙）每一个输出只能连接到一个输入上，因而当多个输入往同一输出端发包时，必须有缓存，根多个输入往同一输出端发包时，必须有缓存，根据缓存器的位置不同，交换结构分为，据缓存器的位置不同，交换结构分为，输出排队（输出排队（OQ）结构）结构输入排队（输入排队（IQ）结构）结构虚拟输入排队（虚拟输入排队（VOQ）组合输入输出排队（组合输入输出排队（CIOQ）结构）结构输出排队（输出排队（输出排队（输出排队（OQOQ）结构）结构）结构）结构优点：高性能；高QoS保障；大量成熟的调度策略可选用缺点：N倍加速问题，在高速环境
6、下应用受限6.2交换网络分类交换网络分类-输出排队（输出排队（输出排队（输出排队（OQOQ）结构）结构）结构）结构Packet BufferingPacket BufferingLookupIP AddressUpdateHeaderHeader ProcessingAddressTableLookupIP AddressUpdateHeaderHeader ProcessingAddressTableLookupIP AddressUpdateHeaderHeader ProcessingAddressTableQueuePacketBufferMemoryQueuePacketBuffer
7、MemoryQueuePacketBufferMemoryBufferManagerBufferMemoryBufferManagerBufferMemoryBufferManagerBufferMemory6.2交换网络分类交换网络分类输出排队（输出排队（输出排队（输出排队（OQOQ）结构）结构）结构）结构LookupIP AddressUpdateHeaderHeader ProcessingAddressTableLookupIP AddressUpdateHeaderHeader ProcessingAddressTableLookupIP AddressUpdateHeaderHea
8、der ProcessingAddressTableQueuePacketBufferMemoryQueuePacketBufferMemoryQueuePacketBufferMemoryDataHdrDataHdrDataHdr12N 12NN times line rateN times line rate6.2交换网络分类交换网络分类-输出排队（输出排队（输出排队（输出排队（OQOQ）结构）结构）结构）结构虽然输出排队能提供很好的性能，但商虽然输出排队能提供很好的性能，但商用存储器访问速率的限制制约了其在高用存储器访问速率的限制制约了其在高速路由器中的使用速路由器中的使用输出排队（输出
9、排队（输出排队（输出排队（OQOQ）结构）结构）结构）结构6.2交换网络分类交换网络分类-输出排队（输出排队（输出排队（输出排队（OQOQ）结构）结构）结构）结构优点：不需要加速缺点：链头（HOL）阻塞；对QoS支持较差；调度策略复杂度高6.2交换网络分类交换网络分类-输入排队（输入排队（输入排队（输入排队（IQIQ）结构）结构）结构）结构LookupIP AddressUpdateHeaderHeader ProcessingAddressTableLookupIP AddressUpdateHeaderHeader ProcessingAddressTableLookupIP Addres
10、sUpdateHeaderHeader ProcessingAddressTableQueuePacketBufferMemoryQueuePacketBufferMemoryQueuePacketBufferMemoryDataHdrDataHdrDataHdr12N 12NDataHdrDataHdrDataHdrScheduler6.2交换网络分类交换网络分类-输入排队（输入排队（输入排队（输入排队（IQIQ）结构）结构）结构）结构A Router with Input QueuesA Router with Input QueuesThe best that any queueing
11、system can achieve.理论上吞吐率可下降为原来的58.6%6.2交换网络分类交换网络分类输入排队的输入排队的输入排队的输入排队的HOLHOL阻塞阻塞阻塞阻塞6.2交换网络分类交换网络分类输入排队的输入排队的输入排队的输入排队的HOLHOL阻塞阻塞阻塞阻塞The best that any queueing system can achieve.6.2交换网络分类交换网络分类输入排队的输入排队的输入排队的输入排队的HOLHOL阻塞阻塞阻塞阻塞虚拟输入排队（虚拟输入排队（虚拟输入排队（虚拟输入排队（VOQVOQ）优点：克服了HOL阻塞，提高了吞吐率，理论上可达100%缺点：需要集中
12、式的调度策略支持，较差的QoS保证对每个输出都在输入端建立一个单独的队列FIFO6.2交换网络分类交换网络分类6.2交换网络分类交换网络分类 Virtual Output QueuesVirtual Output QueuesThe best that any queueing system can achieve.6.2交换网络分类交换网络分类 Virtual Output QueuesVirtual Output Queues基于输入排队的管理策略基于输入排队的管理策略基于输入排队的管理策略基于输入排队的管理策略u最大匹配MSM（Maximum Size Matching）u复杂度高，硬件
13、实现复杂，实际用极大匹配（maximal matching）来近似uSLIP（iterative round-robin matching with SLIP）支持优先级和公平调度。扩展版的ESLIP支持组播u最大权重匹配MWM（Maximum Weighed Matching）uLQF（Longest Queue First）和OCF（Oldest Cell First）算法硬件实现复杂采用iLQF和iOCF来迭代逼近，但实现依然相当复杂u稳定结合配对uGSA（Gale-Shapley Algorithm）算法u利用定义的优先级来调度分组，可以获得好的吞吐率和时延限度u输入排队的管理策略都采
14、用了避免HOL阻塞的方法，努力实现好的QoS保证6.2交换网络分类交换网络分类组合输入输出排队（组合输入输出排队（组合输入输出排队（组合输入输出排队（CIOQCIOQ）结构）结构）结构）结构优点：2倍加速下可模拟实现OQ的性能；适合任意端口数目和流量模式缺点：调度策略复杂度过高，仅具有理论意义在输入和输出端都建立队列来缓存分组6.2交换网络分类交换网络分类组合输入输出排队（组合输入输出排队（组合输入输出排队（组合输入输出排队（CIOQCIOQ）结构）结构）结构）结构发展的观点发展的观点发展的观点发展的观点 超摩尔定律 传输速率每九个月翻一番。结结 论论：处处理理速速率率的的发发展展无无法法跟跟
15、上上传传输输速速率率发发展展的的步伐，因此采用并行交换结构是高速路由器的必然步伐，因此采用并行交换结构是高速路由器的必然趋势。趋势。摩尔定律 CPU的处理速率每18个月将翻一番。6.2交换网络分类交换网络分类优点：处理速度要求低，可提供高性能交换缺陷：在一定程度上导致系统控制维护复杂6.2交换网络分类交换网络分类并行交换结构并行交换结构并行交换结构并行交换结构6.2交换网络分类交换网络分类定长包交换与不定长包交换定长包交换与不定长包交换定长包交换与不定长包交换定长包交换与不定长包交换定长包交换：定长包交换：Crossbar，交换矩阵中的开关转换，交换矩阵中的开关转换每隔固定的时间变换一次每隔固
16、定的时间变换一次不定长包交换：无法保证每一路包的传输时间是不定长包交换：无法保证每一路包的传输时间是相等的，因此若用相等的，因此若用Crossbar交换结构，必须进行切交换结构，必须进行切片。片。6.2交换网络分类交换网络分类不定长包交换不定长包交换基于基于基于基于FPGAFPGA的的的的8888不定长包交换结构不定长包交换结构不定长包交换结构不定长包交换结构6.2交换网络分类交换网络分类不定长包交换不定长包交换本本 章章 内内 容容n交换网络的基本原理交换网络的基本原理n交换网络分类交换网络分类n调度策略调度策略n缓存器管理缓存器管理n组播实现组播实现nQoS支持支持调度机是网络节点中的一个组件，它依照一定的调度算法选择缓存队列中最需要发送的包送到输出链路上包调度算法管理着最重要的网络资源输出链路带宽。良好的调度算法能够隔离各个用户流，起到防火墙的作用，为路由器提供安全保障，保证正常使用网络的用户不受其他用户有意或无意的干扰。调度算法直接控制包的时延而缓存器管理控制包的丢失率，所以调度算法与缓存器管理策略控制着QoS中最重要的性能指标时延和丢包率。时延和丢包率是密切相关的，对一个业务
