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

《路由器原理与设计-2010-lesson3-IP查表技术基础.ppt》由会员分享，可在线阅读，更多相关《路由器原理与设计-2010-lesson3-IP查表技术基础.ppt（64页珍藏版）》请在装配图网上搜索。

1、IP查表技术基础,国防科大计算机学院 孙志刚,2010年路由器原理与设计,主要内容,路由器设计的硬件器件基础 路由器体系结构发展 路由器最长前缀匹配原理 IP路由查表算法,路由器设计的硬件器件基础,SRAM和DRAM,SRAM 随机访问速度快（地址-数据） 不需要刷新，容量相对较低 价格相对较高（大容量SRAM只在通信设备中使用） DRAM 随机访问速度慢（行地址-列地址-数据） 需要刷新，容量大 价格相对便宜,DDRII SRAM（1）,DDRII SRAM（2）,随机访问时间小于7ns,RLDRAM（1）,RLDRAM（2）,随机访问时间小于20ns，允许多个bank间插访问,DDRII

2、SRAM和RL DRAM比较,主流DDRII SRAM,Width: 9,18,36bit Density：up to 72Mbit Clock rate：up to 400MHz Peak bandwidth：up to 28.8Gps 随机访问延时小于7ns,主流RL DRAM,Width: 9-36bit Density：up to 576Mbit Clock rate：200-533MHz Bank：8 Peak Bandwidth：up to 38.4Gps 随机访问延时小于20ns,TCAM（1）,CAM （内容可寻址存储器） 输入内容，返回一个地址，这个地址中的内容与输入的内容相

3、同 TCAM三态的CAM 通过设置屏蔽位，确定某位是否参加比较 因此TCAM中的内容为：0，1，X,TCAM（2）,TCAM（3）,TCAM（4）,TCAM（5）,当前主流TCAM器件 密度256K*72bits 可配置为128K*144bits 可配置为64K*288bits 可配置为32K*576bits 每秒100M次匹配 功耗30W左右 查表速度快，价格昂贵，功耗大,FPGA（1）,现场可编程逻辑器件 操作通过有限状态机控制执行,FPGA（2）,FPGA的配置,FPGA（3）,FPGA的优点 现场可编程，逻辑可更改 内部资源丰富 RAMDSPCPU高速IO 其他硬核，如PCI expr

4、ess、 千兆以太网MAC 工作频率较低，最大500MHz IO性能较低,网络处理器（1）,支持网络分组处理的特殊CPU 内部CPU核的并行处理 专用的加速协处理器 优点 功能通过编程实现，易于升级 开发周期短（相比ASIC），功能重用 缺点：开发难度大,网络处理器（2）,路由器体系结构的发展,Internet网络带宽和流量增长趋势,商用路由器的容量 Capacity 1992 2Gb/s Capacity 1995 10Gb/s Capacity 1998 40Gb/s Capacity 2001 160Gb/s Capacity 2003 640Gb/s Capacity 2005 92T

5、b/s 平均增长速度每18个月2.2倍,路由器性能提高的速度,第一代路由器（1）,Shared Backplane,Line Interface,第一代路由器（2）,性能限制 IO性能 采用描述府机制，优化中断处理 转发性能 转发表Cache，在驱动层次实现分组转发,第一代路由器（3）,第二代路由器（1）,Route Table,CPU,Line Card,Buffer Memory,Line Card,MAC,Buffer Memory,Line Card,MAC,Buffer Memory,Fwding Cache,Fwding Cache,MAC,Buffer Memory,Typica

6、lly 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,Routing Table,Fwding Table,Typically 50Gb/s aggregate capacity,第三代路由器（2）,Cisco GSR 12416,Juniper M160,6ft,19”,2ft,Capacity: 160Gb

7、/sPower: 4.2kW,3ft,2.5ft,19”,Capacity: 80Gb/sPower: 2.6kW,第三代路由器（3）,Physical Layer,Framing & Maintenance,Packet Processing,Buffer Mgmt & Scheduling,Buffer Mgmt & Scheduling,Buffer & State Memory,Buffer & State Memory,10G接口卡,30M gates 2.5Gbits of memory 300W 1m2 $25k cost, $100k price.,Lookup Tables,

8、Optics,Scheduler,40-55% of power in chip-to-chip serial links,第四代路由器（1）,多级交换 可扩展的多级交换结构,分布控制平面 控制软件在多个控制处理器上分布处理,接口 具有多种接口类型，支持上千个接口数目,采用多机柜降低功率密度,路由器最长前缀匹配原理,IP地址分类,IPv4地址格式 A类 0NNNNNNNHHHHHHHHHHHHHHHHHHHHHH 范围：1.0.0.0-127.255.255.255,126个1600万主机 B类 10NNNNNNNNNNNNNNHHHHHHHHHHHHHH 范围：128.0.0.0-191.2

9、55.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）,网络地址浪费（A类浪费，C类缺乏） 解决方法:通过引入子网屏蔽码将网络细分 如：C类地址IP=202.197.12.x

10、xx可划分为2个子网,202.197.12.1/25,Router,202.197.12.0/25,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）,子网划分导致路由器FIB表项增加,202.197.12.1/25,Router2,202.197.12.0/25,202.197.12.128,202.197.12.1,Router1,port1,port2,port1,port2,port3,无类域间路由（1）,通过路由合并减小路

11、由表项,202.197.12.1/25,Router2,202.197.12.0/25,202.197.12.128,202.197.12.1,Router1,port1,port2,port1,port2,port3,无类域间路由（2）,最长前缀匹配问题,202.197.12.128/25,Router2,202.197.12.127/25,202.197.12.128,202.197.12.1,Router1,port1,port2,port1,port2,port3,port3,202.197.12.129,到达202.197.12.128网络，接口3是最好选择！,国防科技大学计算机学院

12、,38,最长前缀匹配查找原理（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-0

13、000-0000-1001-0001-1001-xxxx-xxxx NO 128.9.176/20 =1000-0000-0000-1001-1011-xxxx-xxxx-xxxx NO,IP路由查找算法,FIB查表是分组头处理的重要组成,FIB查表在路由器分组处理中的位置,FIB查表问题,高速接口的查表需求 10G以太网接口，IP报文大小为64字节 帧到达速率=10G/(64+14+4+8+12)*8 =12.3M个 每个报文处理时间1s/12.3M=81.2ns 如何快速进行FIB查找？ 使用更快的器件 使用更好的算法设计,国防科技大学计算机学院,FIB查表算法指标,查找时间 取决于访存次

14、数 必须与网络接口处理分组的速率相匹配 存储空间 必须考虑当前存储器的容量和价格 表修改时间 考虑表修改的访存次数,国防科技大学计算机学院,FIB查表算法（1）,逐项匹配查找算法 访存次数路由表项数 优点： 算法实现简单 转发表组织简单 缺点：性能较差 当前核心路由器转发表项数大于100K，每次访存10ns，那么每次查表时间为1ms。即每秒查找1000次。,最坏情况下需要32次访存，效率很低。,FIB查表算法（2）,二叉树查找：根据前缀值构建二叉树，用目标地址二进制位作为索引，搜索能够匹配的前缀中最长的一个。,例如： 101*命中d 100*命中e,国防科技大学计算机学院,多分支算法：降低树高

15、，减少访存数 问题：用空间换取时间，空间浪费严重，更新困难，仍然需要多次访存,FIB查表算法（3）,国防科技大学计算机学院,47,IP路由查找方法的优化 树的压缩 减小访存次数 转发表压缩 锁定到cache，减小访存时间 专用处理引擎 协处理器，减小CPU干预,FIB查表算法（4）,FIB查表算法（5）,基于TCAM的方法,TCAM,SRAM,硬件 控制器,每次查找可在一次访存的时间内完成，10ns左右 输出的地址可作为指针，指向转发控制块 项数有限，目前每片最大约32K项，可级连,FIB查表算法（6）,基于TCAM的方法 昂贵，容量小 全并行匹配，功耗大，大部分比较操作做无用功 表项组织：前

16、缀长的表项位于低地址处，更新复杂,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前缀覆盖,完全的前缀树：树的每个节点要么有左右两个孩子节点，要么没有孩子节点,非完全前缀树到完全前

17、缀树的转换,前缀覆盖,前缀空间的树结构表示,三级前缀树划分,前缀树划分为三级，第一级树的深度为16，共64K个节点，用8KB表示节点状态， 16bit划分为一个bit mask，共有4096个bit mask,若树的第16层有节点，或无节点但有一个前缀长度小于16的前缀，且对应的最小地址为该节点，则状态为1，其余为0,完全前缀树不可能出线的情形,不可能代表有一个长度小于2 的前缀，不可能代表一个长度大于等于2的前缀（00无法匹配）,头信息的索引（1）,子树信息,转发信息,子树信息,子树信息,头的信息连续存放，需要计算指针地址,使用IP地址可以检索到对应的bit mask位置，算法的核心是如何计

18、算在64K个bitmask中，该位置前面有多少个1（用来计算描述符表的偏移量）,描述符表,状态比特为1表示： R型：前缀在第16级被截断，第二级还有对应的数据 G型：有一个长度小于16的前缀,头信息的索引（2）,用于查找头指针的数据结构,用于标识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）,4096个bit mask

19、 用来表示第一级树64K个节点的状态（0,1） 用IP地址的前12b检索 1024个Base index array 每4个bit mask共享一个Base index array 记录array之间的偏移量（之前1的个数） 用IP地址的前10b检索 4096个code word array 用来记录组内前面其他bit mask中1的个数 用IP地址的前12b检索,Bit Mask模式ID（1）,每个bitmask为16 bit，但没有216个模式 完全树结构决定不可能出线某种模式 如，对于4个节点的树，不可能出现0100 模式计算方法 对于长度为2n的非0 mask，模式数目为2个长度为n的

20、非0 mask任意组合 若a(n)表示长度为2n的mask模式数目，则 加1为模式1100，即前面2n-1个为全1，后面2n-1个为全0，无法用a(n-1)组合产生,Bit Mask模式ID（2）,例如 n=0,1个节点，a(0)=1， n=1,2个节点，a(1)=2，(10,11) n=2,4个节点，a(2)=5(1010,1011,1110,1111,1100) n=3,8个节点，a(3)=26 n=4,16个节点，a(4)=677 即每个16位的bit mask最多有678种模式（包括全0），即用10位ID表示即可,MAPTAble,指明bit mask内部的偏移,指针计算（1）,Bit

21、 mask组组间的偏移，即在本组前，已经有多少个1,Bit mask组内偏移，即在本bitmask前，组内其他的bitmask中已经有多少个1,Bit mask内部偏移，即在本bitmask内，本IP地址指定的bit前，已经有多少个1,指针计算（2）,第一级查表共需读取7个字节 2字节：code word 2字节：Base Index 1字节：Maptable值（4比特） 2字节：指针,第一级表的存储开销 8KB code word array 2KB Base Index array 5.3K的Maptable （678164b）,第一级查表的算法描述,优化方法： 当bitmask内部只有0

22、个或1个1时，不需查Maptable Code word直接保存指针，即当Mask ID大于677时，code word内容为指针，否则为mask ID,第2级和第3级组织（1）,第2级和第3级包含高度为8的树，称为Chunks，分为3种类型 包含18个1，稀疏chunks，直接用8个指针指向子树信息或转发信息 包含864个1，密集chunks，利用第一级的处理方法，但16个code word只用一个base index，因为6比特可以标识64个1 包含65256个1，十分密集chunks，完全采用与第一级相同的处理方法,性能分析（1）,性能分析使用的转发表数据 性能分析使用的机器,性能分析（2）,由于Pentium处理器的二级Cache（256KB）比Alpha（96K）大，因此需要处理周期数比较少 根据分布可以大致看出处理器的多级Cache结构 平均每个周期4ns，每次查表50周期，那么支持查表速率为：5M次/秒,谢 谢！,