路由器原理与设计讲稿5-转发引擎.ppt

《路由器原理与设计讲稿5-转发引擎.ppt》由会员分享，可在线阅读，更多相关《路由器原理与设计讲稿5-转发引擎.ppt（43页珍藏版）》请在三一办公上搜索。

1、路由器原理与设计之五：转发引擎,内 部 通 信,路由器总体结构,高 速 交 换 网 络（主备）,内 部 通 信（主/备）,主控/管理模块,主 控 模 块（主/备）,转发引擎,线路接口,转发引擎,线路接口,转发引擎,线路接口,外部接口,外部接口,操作维护台,外部接口,主要内容,转发引擎的功能转发引擎处理能力的估算有效性检查路由查表包分类,5.1 转发引擎的功能,转发引擎是路由器的核心部件转发引擎进行三层（IP层）处理转发引擎的查表速度决定了路由器的包处理能力转发引擎对IP包头的各个域进行处理,检查IP分组的有效性生成ICMP差错报告消息查找路由转发表，确定输出端口和下一跳IP地址（单播和组播）进

2、行网络层安全性检查，实现安全监测与过滤功能包分类,转发引擎的基本功能是实现IP包第三层处理,5.1 转发引擎的功能,包过滤,有效性检查,性能统计,路由查表,ICMP报文生成,输出报文形成,交换网络,线路接口,报文上交,处理机,5.1 转发引擎的功能,5.1 转发引擎的功能,IP报头信息获取,因特网协议的报头不仅包含了源地址和目的地址，而且还指明了对路由器的操作必不可少的一系列参数，因此路由器必须首先获得IP报头的所有信息,主要内容,转发引擎的功能转发引擎处理能力的估算有效性检查路由查表包分类,若端口速率为R,则线速转发要求的报文转发率X为：,X=,端口速率R,最小包长（408）,转发引擎的处理

3、能力要求：报文线速率转发,5.2 转发引擎处理能力的估算,例如，端口速率为R=2.5Gbps时，,X=,2500000000 bps,408 bit,=7812500pps 7.81Mpps,系统转包率=端口报文转发率端口数,Mpps,5.2 转发引擎处理能力的估算,转发引擎对每个IP包的处理时间T,T=,1,X,最小包长（408）,端口速率,=,5.2 转发引擎处理能力的估算,线速率转发:要求转发引擎在一个包的处理时间T内完成所有的功能,线速查表难点与拟采取的措施,查表时间短（单端口最短IP分组）硬件实现 表项极多 分段 长Prefix表项压缩 最长匹配功能 长Prefix覆盖短Prefix

4、 更新速度快 减少段内Prefix表项数目,5.2 转发引擎处理能力的估算,主要内容,转发引擎的功能转发引擎处理能力的估算有效性检查路由查表包分类,5.3 有效性检查,IP 报头,有效性检查的内容有：生存时间TTL版本号VER报头校验和CHECKSUM协议可否识别 若报文为无效报文，则将该报文丢弃。若报文有效，进行查表，形成内部传输帧进行转发。,5.3 有效性检查,5.3 有效性检查,主要内容,转发引擎的功能转发引擎处理能力的估算有效性检查路由查表包分类,路由查找过程示意图,header,payload,Packet,Router,Destination Address,Outgoing Po

5、rt,Destination,Next Hop,Forwarding Table,Routing Lookup Data Structure,3,1,7,5.4 路由查表,报头综合处理,单播查表,组播查表,安检查表,优先级查表,负荷分担,交换网络,单播表,组播表,过滤表,FIFO,处理机,线路接口,5.4 路由查表,5.4 路由查表,5.4 路由查表,5.4 路由查表,安检查表,源IP地址，目的IP地址，输入端口号，协议号，,安检查表,处理策略（如，是否让通过）,5.4 路由查表,判断前3位,目的IP地址,表1:8位地址,表2:16位地址,表3:24位地址,无类域间路由CIDR（Classle

6、ss InterDomain Routing）CIDR的提出Internet指数增长，IP地址即将用完，IP is rapidly becoming a victim of its own popularity.基于分类的IP地址空间的组织浪费了大量的地址The real villain is the class B network.CIDRRFC 1519基本思想：将剩余的C类地址分成大小可变的地址空间；例如，需要2000个地址，则分配一个2048个地址（8个C类地址）的连续地址块，而不是一个B类地址；,5.4 路由查表,RFC 1519 改变了过去C类地址的分配规则，将世界分成4个区，每个

7、区分配一块连续的C类地址空间；欧洲：11000010 00000000 00000000 00000000 11000011 11111111 11111111 11111111 北美：11000110 00000000 00000000 00000000 11000111 11111111 11111111 11111111 中、南美：11001000 00000000 00000000 00000000 11010001 11111111 11111111 11111111 亚太：11001010 00000000 00000000 00000000 11010011 11111111 1

8、1111111 11111111 路由表中增加一个32位的掩码（mask）域最长匹配原则：路由查找时，若多个路由表项匹配成功，选择掩码长（1比特数多）的路由表项；CIDR思想可用于所有IP地址，没有A、B、C类之分。address format:a.b.c.d/x,where x is#bits in network portion of address,5.4 路由查表,5.4 路由查表,11000000 00000010 00000000 00000000：11000000 00000010 00000001 00000000：11000000 00000010 00000010 0000

9、0000：,5.4 路由查表,11000000 00000010 00000000 00000000：11000000 00000010 00000001 00000000：11000000 00000010 00000010 00000000：,CIDR地址结构下的查找问题,Routing lookup:Find the longest matching prefix(the most specific route)among all prefixes that match the destination address.,5.4 路由查表,例Cambridge University 需要2

10、048个地址，掩码；Oxford University 需要4096个地址，掩码；Edinburgh University 需要1024个地址，掩码；路由表内容地址掩码11000010 00011000 00000000 0000000011111111 11111111 11111000 0000000011000010 00011000 00010000 0000000011111111 11111111 11110000 0000000011000010 00011000 00001000 0000000011111111 11111111 11111100 00000000,5.4 路

11、由查表,一个目的地址为的包到达路由器，路由表查找过程如下：的二进制表示为11000010 00011000 00010001 00000100该地址与第一项Cambridge的掩码做 AND 操作，得到11000010 00011000 00010000 00000000与Cambridge的地址11000010 00011000 00000不同，匹配不成功；该地址与下一项Oxford的掩码做 AND 操作，得到11000010 00011000 00010000 00000000与Oxford的地址11000010 00011000 00010000 00000000相同，匹配成功。继续匹配

12、，最后选择前缀最长的路由表项,5.4 路由查表,5.4 路由查表查表算法,路由查表技术的研究现状：,Binary Trie，Patricia，Path-compressed Trie（更新速度快，查表速度较慢）Binary Search on Lengths（查表速度较快，更新速度慢）基于CAM的查表算法(查表速度和更新速度都较快，成本较高)RLMS（Routing Lookups at Memory Speed）算法(查表速度快、成本低,更新速度较慢),简单覆盖式存储原理,R1,Prefix:00000001 xxxxxxxx,Prefix:000000011 xxxxxxx,Prefix:

13、0000000110 xxxxxx,占用表项单元：1.0 1.255,占用表项单元：1.128 1.255,占用表项单元：1.128 1.191,以Prefix长度为8 16的情况为例,R2,R3,5.4 路由查表查表算法,5.4 路由查表查表算法,分段查表的依据：骨干路由器前缀分布,分段式最长匹配线速查表算法原理组成,SegMid,SegUp,DA,16M,1M,SegLow,64K,16,24,8,12,Prefix=816,Prefix=1724,Prefix=2532,控制逻辑,5.4 路由查表查表算法,简单覆盖式混合存储原理,R1,Prefix:00000001 xxxxxxxx,P

14、refix:000000011 xxxxxxx,Prefix:0000000110 xxxxxx,占用表项单元：1.0 1.255,占用表项单元：1.128 1.255,占用表项单元：1.128 1.191,（Prefix长度：24）,以Prefix长度为8 16的情况为例,Seg_low,R2,R3,5.4 路由查表查表算法,索引覆盖式存储原理,R1（占用表项单元：Index i+0_ Index i+127）,Prefix:00000001 10001010 10111100 0 xxxxxxx,（Prefix长度：24）,Index i,8,12,R2（占用表项单元：Index i+32

15、_ Index i+63）,Prefix:00000001 10001010 10111100 001xxxxx,Index i+0,Index i+1,Index i+127,R1,R1,R1,R1,+,20,Seg_mid,Seg_up,Index i+32,Index i+33,R2,R2,R2,R2,Index i+63,5.4 路由查表查表算法,5.4 路由查表组播查表,5.4 路由查表组播查表,主要内容,转发引擎的功能转发引擎处理能力的估算有效性检查路由查表包分类,5.5 包分类,包分类的目的：判断一个到达的包属于哪一类业务，进行不同处理 包分类的功能：,提供区分服务，是保证QoS的基础 防火墙 基于策略的路由选择 业务速率限制和警管,具有包分类功能的路由器也称为 流识别路由器(Flow-aware Router)或无层交换机(Layerless Switches）因此路由查表时包分类的一个特例,5.5 包分类,包分类涉及到的域：,5.5 包分类,PCNSE（Packet Classification with Network Search Engine）分类器的原理框图,5.5 包分类,