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

路由器原理与设计之六 交换网络及路由器实现中的其他关键技术 兰巨龙E mail ljl 内部通信 路由器总体结构 高速交换网络 主 备 内部通信 主 备 主控 管理模块 主控模块 主 备 转发引擎 线路接口 转发引擎 线路接口 转发引擎 线路接口 外部接口 外部接口 操作维护台 外部接口 本章内容 交换网络的基本原理交换网络分类调度策略缓存器管理组播实现QoS支持 输入缓存与控制 输出缓存与控制 输入 输出 输入缓存与控制 输出缓存与控制 输入缓存与控制 输出缓存与控制 输入缓存与控制 输出缓存与控制 6 1交换网络的基本原理 输入缓存与控制 输出缓存与控制 输入 输出 输入缓存与控制 输出缓存与控制 输入缓存与控制 输出缓存与控制 输入缓存与控制 输出缓存与控制 合路 缓存 分发 6 1交换网络的基本原理 本章内容 交换网络的基本原理交换网络分类调度策略缓存器管理组播实现QoS支持 共享内存Speedislimitedbymemoryaccessspeed共享总线Speedislimitedbybuscapacitance空分复用crossbarSpeedislimitedbythescheduler 6 2交换网络分类 SharedMemory 6 2交换网络分类 共享内存 RouteProcessor Memory DMA RouteCache Memory MAC LineCard DMA RouteCache Memory MAC LineCard DMA RouteCache Memory MAC LineCard Bus Cacheupdates SharedBus 6 2交换网络分类 共享总线 SwitchedCrossbar 6 2交换网络分类 crossbar 6 2交换网络分类 crossbar 空分Crossbar是一个交换矩阵 在同一时刻 时隙 每一个输出只能连接到一个输入上 因而当多个输入往同一输出端发包时 必须有缓存 根据缓存器的位置不同 交换结构分为 输出排队 OQ 结构输入排队 IQ 结构虚拟输入排队 VOQ 组合输入输出排队 CIOQ 结构 输出排队 OQ 结构 优点 高性能 高QoS保障 大量成熟的调度策略可选用缺点 N倍加速问题 在高速环境下应用受限 6 2交换网络分类 输出排队 OQ 结构 PacketBuffering QueuePacket BufferMemory QueuePacket BufferMemory QueuePacket BufferMemory 6 2交换网络分类 输出排队 OQ 结构 QueuePacket BufferMemory QueuePacket BufferMemory QueuePacket BufferMemory 1 2 N 1 2 N Ntimeslinerate 6 2交换网络分类 输出排队 OQ 结构 虽然输出排队能提供很好的性能 但商用存储器访问速率的限制制约了其在高速路由器中的使用 输出排队 OQ 结构 6 2交换网络分类 输出排队 OQ 结构 优点 不需要加速缺点 链头 HOL 阻塞 对QoS支持较差 调度策略复杂度高 6 2交换网络分类 输入排队 IQ 结构 QueuePacket BufferMemory QueuePacket BufferMemory QueuePacket BufferMemory Scheduler 6 2交换网络分类 输入排队 IQ 结构 ARouterwithInputQueues Thebestthatanyqueueingsystemcanachieve 理论上吞吐率可下降为原来的58 6 6 2交换网络分类 输入排队的HOL阻塞 6 2交换网络分类 输入排队的HOL阻塞 Thebestthatanyqueueingsystemcanachieve 6 2交换网络分类 输入排队的HOL阻塞 虚拟输入排队 VOQ 优点 克服了HOL阻塞 提高了吞吐率 理论上可达100 缺点 需要集中式的调度策略支持 较差的QoS保证 对每个输出都在输入端建立一个单独的队列FIFO 6 2交换网络分类 6 2交换网络分类 VirtualOutputQueues Thebestthatanyqueueingsystemcanachieve 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交换网络分类 优点 处理速度要求低 可提供高性能交换 缺陷 在一定程度上导致系统控制维护复杂 6 2交换网络分类 并行交换结构 6 2交换网络分类 定长包交换与不定长包交换 定长包交换 Crossbar 交换矩阵中的开关转换每隔固定的时间变换一次不定长包交换 无法保证每一路包的传输时间是相等的 因此若用Crossbar交换结构 必须进行切片 6 2交换网络分类 不定长包交换 基于FPGA的8 8不定长包交换结构 6 2交换网络分类 不定长包交换 本章内容 交换网络的基本原理交换网络分类调度策略缓存器管理组播实现QoS支持 调度机是网络节点中的一个组件 它依照一定的调度算法选择缓存队列中最需要发送的包送到输出链路上包调度算法管理着最重要的网络资源 输出链路带宽 良好的调度算法能够隔离各个用户流 起到防火墙的作用 为路由器提供安全保障 保证正常使用网络的用户不受其他用户有意或无意的干扰 调度算法直接控制包的时延而缓存器管理控制包的丢失率 所以调度算法与缓存器管理策略控制着QoS中最重要的性能指标 时延和丢包率 时延和丢包率是密切相关的 对一个业务流 分配给它的带宽越多 它需要的缓存空间越小 另外 大的包时延容易导致更大的包丢失率 因而包调度算法和缓存器管理策略是网络保证业务QoS最重要两项关键技术 6 3调度策略 6 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的思想是在每一网络节点上将不同流放入不同的队列中 然后逐个轮询调度输出各队列的包 跳过空队列 若有多个活动的流 则每个队列每一轮询周期发送一个包 加权公平排队策略 WeightedFairQueuing Demers Keshav和Shenker对Nagle的算法进行了改进 提出了逐比特轮询调度算法 Bit by bitRoundRobinService BBRR 轮询机每一轮从每一队列中调度一比特而非一个包 因而解决了包长不同带来的不公平 但这仅仅是一个理论分析方法 因为发送时不可能将包打碎 加权逐比特轮询调度算法当轮询到某一队列时 从该队列中调度的比特数由该队列的权值决定 6 3调度策略 实时调度算法研究现状 它是BBRR的实用版 其工作原理如下 1 在理论上计算Fi i 1 2 K K为队列数 的值 Fi为采用加权BBRR策略时 第i个队列中的包最后一比特被调度出去的时间 2 比较各个队列Fi的大小 若Fj Fi i 1 2 K i j 则调度第j个队列中的一个包输出 Fj Fi表明采用加权BBRR策略时 所有队列中正在被服务的包中第j个队列的包最先被服务完毕 3 计算第j个队列下一个包的结束时间并记为Fj 回到第二步 加权公平排队策略 WFQ 6 3调度策略 实时调度算法研究现状 6 3调度策略 实时调度算法研究现状 统计公平排队 StochasticFairQueuing SFQ SFQ算法是WFQ算法的改进型 是为了解决WFQ中队列太多 计算复杂而引入的调度策略 与WFQ算法的不同之处在于SFQ算法采用Hash变换压缩了队列数目 而调度原理与WFQ完全一样 所有映射到一个队列中的流同等对待 将大量的业务流压缩映射到少量的队列中 可大大减少队列数目 这使得该算法的运算复杂度由O n 减少到O 1 数量级 n为流数 该算法的缺陷是当发生碰撞时 会出现不公平 由于其公平性是以一定概率呈现的 所以称为统计公平排队 加权循环服务 WeightedRoundRobin WRR 调度算法WRR为PRR的改进型 每一个队列具有一个权值 轮询到该队列时 根据其权值发送一定量的数据 与PRR最大的不同在于WRR与 字节 打交道 而不是与 包 打交道 每一轮轮询 调度机都访问所有的队列 当访问到某一队列时 根据权值决定从该队列调度多少个字节输出 与BBRR一样 由于WRR以 字节 分配带宽 而IP网络不能发送半个包 必须寻找可实现的改进或近似方法 后面介绍的欠帐式轮询算法即是WRR算法的一种实现 6 3调度策略 实时调度算法研究现状 6 3调度策略 实时调度算法研究现状 欠帐式轮询 DeficitRoundRobin DRR 111 调度算法针对不定长包的调度不公平问题 Shreedhar和Varghese提出了一种公平调度算法 DRR算法 它是WRR算法的一种改进型 其工作原理如下 采用SFQ算法减少队列数 逐包轮询 轮询机每一轮为每一对列分配N字节输出带宽 为每一队列设置一储蓄计数器C i i 1 2 K K为队列数 a 起始状态所有Ci 0 b 当轮询到一个队列i时 为计数器存入该轮应该输出的字节数N Ci N Ci 如果队列中有整包 且排在队头的那个包的包长Li1 Ci 包长一字节为单位 将该包调度输出 并令Ci Ci Li1 再观察该队列中是否有整包 若有 且排在队头的包的长度Li2 Ci 则将第二个包调度输出 直至该队列中无整包或计数器的值小于队列中第一个包的长度 转到下一队列 c 如果轮询到一个队列i 且为计数器存入该轮应该输出的字节数N Ci N Ci 之后 发现队列中无整包或第一个包的包长Li1 Ci 则将该轮应发的字节数N储蓄起来 留到下一轮使用 转到下一队列 d 如果轮询到队列i时 队列是空的 则将计数器Ci清零 这一做法是为了不让Ci无限增大 虽然显得不很公平 但是却能够防止突发的形成和对其他队列的影响 DRR算法中 每个队列的计数器记录了轮询机亏欠该队列的字节数 因此称为欠帐式轮询调度算法 6 3调度策略 实时调度算法研究现状 虚时钟 VirtualClock 调度算法 81 97 虚时钟的概念来源于TDM系统 由于每一用户只能在给定的时隙内发送数据 因而TDM系统没有用户间的干扰 但是 当某一用户在某一段时间内没有数据发送时 它所对应的时隙就空闲 带宽资源被浪费了 虚时钟算法的目的就是既得到TDM系统的隔离作用 又保持包交换系统的统计复用效果 TDM系统是在实时钟控制下工作 VirtualClock算法是在虚时钟控制下工作 假设某一流到达路由器的包具有虚时间空间的固定速率 则每当一个包到达时 就有一个时隙的时间过去了 依据这一思想 为每一数据流指定一个虚时钟 每当这一流的一个包到达时 该时钟走一步 步幅Vticki等于包到达的间隔 设包长固定 如果某一流按照约定的速率发包 则虚时钟的跳变时刻就在实际时间附近 一般处理器共享 GeneralizedProcessorSharingAlgorithm GPS 6 3调度策略 实时调度算法研究现状 6 3调度策略 实时调度算法研究现状 逐包一般处理器共享 Packet by PacketGPS PGPS 算法 2 82 84 PGPS算法是GPS的近似实现 它以逐包调度的方式进行 设Fi是采用GPS调度算法时第i个队列中包P的最后一个比特离开节点的时间 则PGPS依照Fi的顺序调度各队列中的包 可见PGPS算法的实际效果同加权公平排队策略完全一样 PGPS的意义在于 在采用漏桶算法限制各个业务时 网络能够提供一个端到端时延的理论上限 自定时公平排队策略 SelfClockedFairQueuing SCFQ 前述几种方案的缺点在于难于实现 计算复杂 需要跟踪GPS 缓存器管理复杂 在SCFQ调度方式中 时标是依照实时系统的事件计算 而非参照GPS系统 所以不必跟踪理想GPS系统的过程 它是一个低复杂度和GPS近似程度的折衷 所以其时延特性不如GPS严格 6 3调度策略 实时调度算法研究现状 WF2Q调度算法对WFQ做了改进 WFQ算法的调度原则是根据GPS算法计算出的调度顺序调度包 而WF2Q调度算法的基本原则仍然是根据GPS算法计算的顺序调度包 但是采用GPS算法调度时 已开始发送的包优先 WF2Q Worst caseFairWeightedFairQueueing 6 3调度策略 实时调度算法研究现状 Stop and GoStop and Go最早由贝尔通信研究所的J Golestani提出 目的在于在网络的节点上保持业务的平滑特性 防止突发的形成 提供时延和包丢失率的保证 采用Stop and Go调度策略时 端到端的传输速率在连接建立时就根据可用的网络资源确定了 Stop and Go由在源节点上的每一个连接的接入控制策略 在时间间隔T内每一流发送的数据不能超过r比特 和内部节点上的特殊服务策略组成 Stop and Go采用帧结构 将时间轴分成长度为T的帧 所有在一个给定帧内到达的包都将在下一帧内发送 以保证业务的平滑特性 防止突发形成 传输时延抖动也可控制在一定范围内 6 3调度策略 实时调度算法研究现状 6 3调度策略 实时调度算法研究现状 WF2Q Worst caseFairWeightedFairQueueing 补偿性轮询调度算法的原理框图 CompensatingRoundRobin 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缓