路由器原理与设计-2010-lesson3-IP查表技术基础.ppt

IP查表技术基础 国防科大计算机学院 孙志刚 2010年路由器原理与设计 主要内容 o 路由器设计的硬件器件基础 o 路由器体系结构发展 o 路由器最长前缀匹配原理 o IP路由查表算法 路由器设计的硬件器件基础 SRAM和DRAM o SRAM n 随机访问速度快（地址-数据） n 不需要刷新，容量相对较低 n 价格相对较高（大容量SRAM只在通信设备中使用 ） o DRAM n 随机访问速度慢（行地址-列地址-数据） n 需要刷新，容量大 n 价格相对便宜 DDRII SRAM（1） DDRII SRAM（2） 随机访问时间小于7ns RLDRAM（1） RLDRAM（2） 随机访问时间小于20ns，允 许多个bank间插访问 DDRII SRAM和RL DRAM比较 主流DDRII SRAM o Width: 9,18,36bit o Density：up to 72Mbit o Clock rate：up to 400MHz o Peak bandwidth：up to 28.8Gps o 随机访问延时小于7ns 主流RL DRAM o Width: 9-36bit o Density：up to 576Mbit o Clock rate：200- 533MHz o Bank：8 o Peak Bandwidth：up to 38.4Gps o 随机访问延时小于20ns TCAM（1） o CAM （内容可寻址存储器） n 输入内容，返回一个地址，这个地址中的内容 与输入的内容相同 o TCAM三态的CAM n 通过设置屏蔽位，确定某位是否参加比较 n 因此TCAM中的内容为：0，1，X TCAM（2） TCAM（3） TCAM（4） TCAM（5） o 当前主流TCAM器件 n 密度256K*72bits o 可配置为128K*144bits o 可配置为64K*288bits o 可配置为32K*576bits n 每秒100M次匹配 n 功耗30W左右 o 查表速度快，价格昂贵，功耗大 FPGA（1） o 现场可编程逻辑器件 n 操作通过有限状态机控制执行 FPGA（2） o FPGA的配置 FPGA（3） o FPGA的优点 n 现场可编程，逻辑可更改 n 内部资源丰富 o RAMDSPCPU高速IO o 其他硬核，如PCI express、 千兆以太网MAC o 工作频率较低，最大500MHz o IO性能较低 网络处理器（1） o 支持网络分组处理的特殊CPU n 内部CPU核的并行处理 n 专用的加速协处理器 o 优点 n 功能通过编程实现，易于升级 n 开发周期短（相比ASIC），功能重用 o 缺点：开发难度大 网络处理器（2） 路由器体系结构的发展 Internet网络带宽和流量增长趋势 o 商用路由器的容量 n Capacity 1992 2Gb/s n Capacity 1995 10Gb/s n Capacity 1998 40Gb/s n Capacity 2001 160Gb/s n Capacity 2003 640Gb/s n Capacity 2005 92Tb/s o平均增长速度每18个月2.2倍 路由器性能提高的速度 Route Table CPU Buffer Memory Line Interface MAC Line Interface MAC Line Interface MAC 聚合交换能力小于0.5Gbps 第一代路由器（1） Shared Backplane Line Interface CPU Memory 第一代路由器（2） o 性能限制 n IO性能 o 采用描述府机制，优化中断处理 n 转发性能 o 转发表Cache，在驱动层次实现分组转发 第一代路由器（3） 第二代路由器（1） Route Table CPU Line Card Buffer Memory Line Card MAC Buffer Memory Line Card MAC Buffer Memory Fwding Cache Fwding Cache Fwding Cache MAC Buffer Memory Typically 5Gb/s aggregate capacity 第二代路由器（2） 第三代路由器（1） Line Card MAC Local Buffer Memory CPU Card Line Card MAC Local Buffer Memory Switched Backplane Line Interface CPU Memory Fwding Table Routing Table Fwding Table Typically 50Gb/s aggregate capacity 第三代路由器（2） Cisco GSR 12416Juniper M160 6ft 19” 2ft Capacity: 160Gb/s Power: 4.2kW 3ft 2.5ft 19” Capacity: 80Gb/s Power: 2.6kW 第三代路由器（3） Physical Layer Framing & Maintenance Packet Processing Buffer Mgmt & Scheduling Buffer Mgmt & Scheduling Buffer & State Memory Buffer & State Memory 10G接口卡 v 30M gates v 2.5Gbits of memory v300W v 1m2 v $25k cost, $100k price. Lookup Tables Optics Scheduler 40-55% of power in chip-to-chip serial links 第四代路由器（1） 多级交换 可扩展的多级交 换结构 分布控制平面 控制软件在多个控 制处理器上分布处 理 Interface Module MID-PLANE Line Card Line Card 8 of 8 2 of 8 1 of 8 S1 S1S2 S2 S3 S3 S1S2S3 Cisco SPP Cisco SPP Modular Service Card 8K Qs 8K Qs Route Processor Route Processor 接口 具有多种接口类 型，支持上千个 接口数目 采用多机柜降低功率密度 路由器最长前缀匹配原理 IP地址分类 o IPv4地址格式 A类 0NNNNNNNHHHHHHHHHHHHHHHHHHHHHH 范围：1.0.0.0-127.255.255.255,126个1600万主机 B类 10NNNNNNNNNNNNNNHHHHHHHHHHHHHH 范围：128.0.0.0-191.255.255.255，16382个64K主机 C类 110NNNNNNNNNNNNNNNNNNNNNHHHHHH 范围：192.0.0.0-223.255.255.255，200万个254主机 D类 1110HHHHHHHHHHHHHHHHHHHHHHHHHHH 范围：224.0.0.0-239.255.255.255 E类 11110RRRRRRRRRRRRRRRRRRRRRRRRRRR 范围：240.0.0.0-247.255.255.255 其他特殊地址 子网划分（1） o 网络地址浪费（A类浪费，C类缺乏） o 解决方法:通过引入子网屏蔽码将网络细分 n如：C类地址IP=202.197.12.xxx可划分为2个子网 Router 202.197.12.128 202.197.12.1 子网地址范围是202.197.12.128- 202.197.12.255 子网地址范围是202.197.12.0- 202.197.12.127 子网划分（2） o 子网划分导致路由器FIB表项增加 Router2 202.197.12.128 202.197.12.1 Router1 port1port2 port1 port2 port3 子网出 口 202.197.12.1/251 202.197.12.0/251 子网出口 202.197.12.1/252 202.197.12.0/253 无类域间路由（1） o 通过路由合并减小路由表项 Router2 202.197.12.128 202.197.12.1 Router1 port1port2 port1 port2 port3 子网出 口 202.197.12/241 子网出口 202.197.12.1/252 202.197.12.0/253 无类域间路由（2） o 最长前缀匹配问题 Router2 202.197.12.128 202.197.12.1 Router1 port1 port2 port1 port2 port3 子网出 口 202.197.12/241 202.197.12.1/253 子网出口 202.197.12.1/252 202.197.12.0/253 port3 202.197.12.129 到达202.197.12.128网 络，接口3是最好选择！ 国防科技大学计算机学院38 128.9/16 128.9.16/20 128.9.176/20 128.9.19/24 128.9.25/24 PrefixPort 5 2 7 10 1 128.9.16.14 最长前缀匹配查找原理（1） 国防科技大学计算机学院39 最长前缀匹配查找原理（2） 到达地址： 128.9.16.14 =1000-0000-0000-1001-0001-0000-0000-1110 路由表项地址： 128.9.19/24 =1000-0000-0000-1001-0001-0011-xxxx-xxxx NO 128.9/16 =1000-0000-0000-1001-xxxx-xxxx-xxxx-xxxx YES 128.9.16/20 =1000-0000-0000-1001-0001-xxxx-xxxx-xxxx YES 128.9.25/24 =1000-0000-0000-1001-0001-1001-xxxx-xxxx NO 128.9.176/20 =1000-0000-0000-1001-1011-xxxx-xxxx-xxxx NO IP路由查找算法 FIB查表是分组头处理的重要组成 FIB查表在路由器 分组处理中的位置 FIB查表问题 o 高速接口的查表需求 n 10G以太网接口，IP报文大小为64字节 n 帧到达速率=10G/(64+14+4+8+12)*8 =12.3M个 n 每个报文处理时间1s/12.3M=81.2ns o 如何快速进行FIB查找？ n 使用更快的器件 n 使用更好的算法设计 国防科技大学计算机学院 FIB查表算法指标 o 查找时间 n 取决于访存次数 n 必须与网络接口处理分组的速率相匹配 o 存储空间 n 必须考虑当前存储器的容量和价格 o 表修改时间 n 考虑表修改的访存次数 国防科技大学计算机学院 FIB查表算法（1） o 逐项匹配查找算法 n 访存次数路由表项数 n 优点： o 算法实现简单 o 转发表组织简单 n 缺点：性能较差 n 当前核心路由器转发表项数大于100K，每次访 存10ns，那么每次查表时间为1ms。即每秒查 找1000次。 最坏情况下需 要32次访存 ，效率很低。 FIB查表算法（2） o 二叉树查找：根据前缀值构建二叉树，用目标地址 二进制位作为索引，搜索能够匹配的前缀中最长的一个 。 例如： 101*命中d 100*命中e 国防科技大学计算机学院 o 多分支算法：降低树高，减少访存数 n 问题：用空间换取时间，空间浪费严重，更新困难 ，仍然需要多次访存 FIB查表算法（3） 国防科技大学计算机学院47 o IP路由查找方法的优化 n 树的压缩 o 减小访存次数 n 转发表压缩 o 锁定到cache，减小访存时间 n 专用处理引擎 o 协处理器，减小CPU干预 FIB查表算法（4） FIB查表算法（5） o 基于TCAM的方法 TCAM SRAM 硬件 控制器 o每次查找可在一次访存的时间内完成，10ns左右 o输出的地址可作为指针，指向转发控制块 o项数有限，目前每片最大约32K项，可级连 FIB查表算法（6） o 基于TCAM的方法 n 昂贵，容量小 n 全并行匹配，功耗大，大部分比较操作做无用功 n 表项组织：前缀长的表项位于低地址处，更新复杂 8 9 10 11 空闲 8 9 10 11 空闲 空闲 空闲 Small Forwarding Tables for Fast Routing Lookups Brodnik, S. Carlsson, M. Degermark, S. Pink. Proc. ACM SIGCOMM 1997 IP路由表的树结构表示（1） 整个32位IP地址空间全展开， 形成一个深度为32的树结构 由于需要最长前缀匹配，一个 前缀可能覆盖另一个前缀 如在地址范围r内，e1前缀被 e2前缀覆盖 完全的前缀树：树的每个节点要么 有左右两个孩子节点，要么没有孩 子节点 非完全前缀树到完全前缀树的转换 前缀覆盖 前缀空间的树结构表示 三级前缀树划分 前缀树划分为三级，第一级树的深 度为16，共64K个节点，用8KB表 示节点状态， 16bit划分为一个bit mask，共有4096个bit mask 若树的第16层有节点，或无节点但有一个前缀长度小于16的前缀 ，且对应的最小地址为该节点，则状态为1，其余为0 完全前缀树不可能出线的情形 不可能代表有一个长度小于2 的前缀，不可能代表一个 长度大于等于2的前缀（00无法匹配） 头信息的索引（1） 2b14b RAddr1 GAddr2 RAddr3 RAddr5 子树信息 转发信息 子树信息 子树信息 头的信息连续存放， 需要计算指针地址 使用IP地址可以检索到对应的bit mask位置，算法的核心是如何计算在64K 个bitmask中，该位置前面有多少个1（用来计算描述符表的偏移量） 描述符表 状态比特为1表示： R型：前缀在第16级被截断，第二级 还有对应的数据 G型：有一个长度小于16的前缀 头信息的索引（2） o 用于查找头指针的数据结构 用于标识bit mask模 式的ID，对于特定IP 地址，用来计算bit mask内的偏移 每4个bit mask一组 ，共享Base Index 记录组内指针的偏移 ，组内前面的bit mask有3个1 第二组之前共有13个1（指针） Code array中：ID为10b，指针偏移为6b（最大64，实际取 值最大为48） 头信息的索引（3） o 4096个bit mask n用来表示第一级树64K个节点的状态（0,1） n用IP地址的前12b检索 o 1024个Base index array n每4个bit mask共享一个Base index array n记录array之间的偏移量（之前1的个数） n用IP地址的前10b检索 o 4096个code word array n用来记录组内前面其他bit mask中1的个数 n用IP地址的前12b检索 Bit Mask模式ID（1） o 每个bitmask为16 bit，但没有216个模式 n完全树结构决定不可能出线某种模式 n如，对于4个节点的树，不可能出现0100 o 模式计算方法 n对于长度为2n的非0 mask，模式数目为2个长度为n的非0 mask任意组合 n若a(n)表示长度为2n的mask模式数目，则 n加1为模式1100，即前面2n-1个为全1，后面2n-1个为全0 ，无法用a(n-1)组合产生 Bit Mask模式ID（2） o 例如 n n=0,1个节点，a(0)=1， n n=1,2个节点，a(1)=2，(10,11) n n=2,4个节点， a(2)=5(1010,1011,1110,1111,1100) n n=3,8个节点，a(3)=26 n n=4,16个节点，a(4)=677 o 即每个16位的bit mask最多有678种模式（包 括全0），即用10位ID表示即可 MAPTAble o 指明bit mask内部的偏移 ID01234567891 0 1 1 1 2 1 3 1 4 1 5 xxx011112234555 567