《路由器原理与设计讲稿5转发引擎》由会员分享，可在线阅读，更多相关《路由器原理与设计讲稿5转发引擎（43页珍藏版）》请在金锄头文库上搜索。
1、路由器原理与设计路由器原理与设计之五：之五：转发引擎转发引擎转发引擎转发引擎内内 部部 通通 信信路由器总体结构路由器总体结构高高 速速 交交 换换 网网 络络（主主备备）内内 部部 通通 信（主信（主/备）备）主控主控 / 管理模块管理模块主主 控控 模模 块块 （主（主/备）备）转发引擎转发引擎线路接口线路接口转发引擎转发引擎线路接口线路接口转发引擎转发引擎线路接口线路接口外外部部接接口口外外部部接接口口操作维护台操作维护台外外部部接接口口主要内容主要内容1.1.转发引擎的功能转发引擎的功能2.2.转发引擎处理能力的估算转发引擎处理能力的估算3.3.有效性检查有效性检查4.4.路由查表路由
2、查表5.5.包分类包分类5.1 转发引擎的功能转发引擎的功能转发引擎是路由器的核心部件转发引擎是路由器的核心部件转发引擎进行三层（转发引擎进行三层（IP层）处理层）处理转发引擎的查表速度决定了路由器的包处理能力转发引擎的查表速度决定了路由器的包处理能力转发引擎对转发引擎对IP包头的各个域进行处理包头的各个域进行处理检查检查IP分组的有效性分组的有效性生成生成ICMP差错报告消息差错报告消息查找路由转发表，确定输出端口和下一跳查找路由转发表，确定输出端口和下一跳IP地址（单播和组播）地址（单播和组播）进行网络层安全性检查，实现安全监测与过滤功能进行网络层安全性检查，实现安全监测与过滤功能包分类包
3、分类转发引擎的基本功能是实现转发引擎的基本功能是实现IP包第三层处理包第三层处理5.1 转发引擎的功能转发引擎的功能包过滤包过滤有效性检查有效性检查性能性能统计统计路由查表路由查表ICMP报文报文生成生成输出报文形成输出报文形成交换网络交换网络线路接口线路接口报文报文上交上交处处理理机机5.1 转发引擎的功能转发引擎的功能5.1 转发引擎的功能转发引擎的功能IPIP报头信息获取报头信息获取报头信息获取报头信息获取因特网协议的报头不仅包含了源地址和目的地址，而且还指明了对路由器的操作必不可少的一系列参数，因此路由器必须首先获得IP报头的所有信息IHL服 务 类 型总 长 度 标 识 符 标志段
4、偏 移 量 存活时间 协 议 报 头 校 验 和 源 地 址目 的 地 址 选 项 填 充版本号主要内容主要内容1.1.转发引擎的功能转发引擎的功能2.2.转发引擎处理能力的估算转发引擎处理能力的估算3.3.有效性检查有效性检查4.4.路由查表路由查表5.5.包分类包分类若端口速率为若端口速率为若端口速率为若端口速率为R,R,则线速转发要求的报文转发率则线速转发要求的报文转发率则线速转发要求的报文转发率则线速转发要求的报文转发率X X为：为：为：为：X=X=端口速率端口速率端口速率端口速率R R最小包长（最小包长（最小包长（最小包长（ 408408）转发引擎的处理能力要求：转发引擎的处理能力要
5、求：转发引擎的处理能力要求：转发引擎的处理能力要求：报文线速率转发报文线速率转发报文线速率转发报文线速率转发5.2 转发引擎处理能力的估算转发引擎处理能力的估算例如，端口速率为例如，端口速率为例如，端口速率为例如，端口速率为R=2.5GbpsR=2.5Gbps时，时，时，时，X=X=2500000000 bps2500000000 bps408 bit408 bit=7812500pps =7812500pps 7.81Mpps7.81Mpps系统转包率系统转包率系统转包率系统转包率= =端口报文转发率端口报文转发率端口报文转发率端口报文转发率 端口数端口数端口数端口数MppsMpps5.2
6、转发引擎处理能力的估算转发引擎处理能力的估算转发引擎对每个转发引擎对每个转发引擎对每个转发引擎对每个IPIP包的处理时间包的处理时间包的处理时间包的处理时间T TT=T=1 1X X最小包长（最小包长（最小包长（最小包长（ 408 408 ）端口速率端口速率端口速率端口速率= =例如，端口速率为例如，端口速率为例如，端口速率为例如，端口速率为2.5Gbps2.5Gbps时，时，时，时， T=T=408 bit408 bit2500000000 bps2500000000 bps=128ns=128ns 端口速率为端口速率为端口速率为端口速率为10Gbps10Gbps时，时，时，时， T=T=4
7、08 bit408 bit10000000000 bps10000000000 bps=32ns=32ns 端口速率为端口速率为端口速率为端口速率为40Gbps40Gbps时，时，时，时， T=T=408 bit408 bit40000000000 bps40000000000 bps=8ns=8ns线路速率转包率X (40Byte packet)一个包的处理时间T622Mb/s1.94M514ns2.5Gb/s7.81M128ns10Gb/s31.25M32ns40Gb/s125M8ns5.2 转发引擎处理能力的估算转发引擎处理能力的估算线速率转发线速率转发线速率转发线速率转发: : 要求转
8、发引擎在一个包的处理时间要求转发引擎在一个包的处理时间要求转发引擎在一个包的处理时间要求转发引擎在一个包的处理时间T T内完成所有的功能内完成所有的功能内完成所有的功能内完成所有的功能线速查表难点与拟采取的措施线速查表难点与拟采取的措施 查表时间短（单端口最短查表时间短（单端口最短IP分组）分组） 硬件实现硬件实现 表项极多表项极多 分段分段 长长Prefix表项压缩表项压缩 最长匹配功能最长匹配功能 长长Prefix覆盖覆盖短短Prefix 更新速度快更新速度快 减少段内减少段内Prefix表表项数目项数目5.2 转发引擎处理能力的估算转发引擎处理能力的估算主要内容主要内容1.1.转发引擎的
9、功能转发引擎的功能2.2.转发引擎处理能力的估算转发引擎处理能力的估算3.3.有效性检查有效性检查4.4.路由查表路由查表5.5.包分类包分类5.3 有效性检查有效性检查IHL服 务 类 型总 长 度 标 识 符 标志段 偏 移 量 存活时间 协 议 报 头 校 验 和 源 地 址目 的 地 址 选 项 填 充版本号IP 报头报头有效性检查的内容有：u生存时间TTLu版本号VERu报头校验和CHECKSUMu协议可否识别 若报文为无效报文，则将该报文丢弃。若报文有效，进行查表，形成内部传输帧进行转发。5.3 有效性检查有效性检查5.3 有效性检查有效性检查主要内容主要内容1.1.转发引擎的功能
10、转发引擎的功能2.2.转发引擎处理能力的估算转发引擎处理能力的估算3.3.有效性检查有效性检查4.4.路由查表路由查表5.5.包分类包分类路由查找过程示意图路由查找过程示意图路由查找过程示意图路由查找过程示意图headerpayloadPacketRouterDestination AddressOutgoing PortDestinationNext HopForwarding TableRouting Lookup Data Structure3175.4 路由查表路由查表报头综合处理单播查表组播查表安检查表优先级查表负荷分担交换网络单播表组播表过滤表FIFO处理机线路接口线路接口5.4
11、路由查表路由查表5.4 路由查表路由查表5.4 路由查表路由查表单播查表单播查表目的目的IP地址地址单单播播查查表表目的端口号，下一跳目的端口号，下一跳IP地址地址组播查表组播查表目的目的IP地址地址组组播播查查表表目的端口号列表目的端口号列表5.4 路由查表路由查表安检查表安检查表源源IP地址，地址，目的目的IP地址，地址，输入端口号，输入端口号，协议号，协议号，安安检检查查表表处理策略（如，是否让通过）处理策略（如，是否让通过）优先级查表优先级查表TOS或分类或分类标志标志优优先先级级查查表表优先级优先级5.4 路由查表路由查表判断前判断前3位位目的目的IP地址地址表表1:8位地址位地址表
12、表2:16位地址位地址表表3:24位地址位地址无类域间路由CIDR（Classless InterDomain Routing）uCIDR的提出uInternet指数增长，IP地址即将用完，IP is rapidly becoming a victim of its own popularity.u基于分类的IP地址空间的组织浪费了大量的地址The real villain is the class B network.uCIDRuRFC 1519u基本思想：将剩余的C类地址分成大小可变的地址空间；u例如，需要2000个地址，则分配一个2048个地址（8个C类地址）的连续地址块，而不是一个B类
13、地址；5.4 路由查表路由查表uRFC 1519 改变了过去C类地址的分配规则，将世界分成4个区，每个区分配一块连续的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 亚太： 1
14、1001010 00000000 00000000 00000000 11010011 11111111 11111111 11111111 路由表中增加一个32位的掩码（mask）域u最长匹配原则：路由查找时，若多个路由表项匹配成功，选择掩码长（1比特数多）的路由表项；uCIDR思想可用于所有IP地址，没有A、B、C类之分。uaddress format: a.b.c.d/x, where x is # bits in network portion of address5.4 路由查表路由查表5.4 路由查表路由查表11000000 00000010 00000000 00000000：1
15、1000000 00000010 00000001 00000000：11000000 00000010 00000010 00000000：5.4 路由查表路由查表11000000 00000010 00000000 00000000：11000000 00000010 00000001 00000000：11000000 00000010 00000010 00000000：CIDR地址结构下的查找问题地址结构下的查找问题192.2.2/240232-1200.11.0/22192.2.0/22192.2.2.100Longest Matching PrefixRouting lookup
16、: Find the longest matching prefix (the most specific route) among all prefixes that match the destination address.5.4 路由查表路由查表例uCambridge University 需要2048个地址，掩码；Oxford University 需要4096个地址，掩码；Edinburgh University 需要1024个地址，掩码；u路由表内容地址掩码11000010 00011000 00000000 0000000011111111 11111111 11111000
17、0000000011000010 00011000 00010000 0000000011111111 11111111 11110000 0000000011000010 00011000 00001000 0000000011111111 11111111 11111100 000000005.4 路由查表路由查表u一个目的地址为的包到达路由器，路由表查找过程如下：u的二进制表示为11000010 00011000 00010001 00000100u该地址与第一项Cambridge的掩码做 AND 操作，得到11000010 00011000 00010000 00000000与Camb
18、ridge的地址11000010 00011000 00000不同，匹配不成功；u该地址与下一项Oxford的掩码做 AND 操作，得到11000010 00011000 00010000 00000000与Oxford的地址11000010 00011000 00010000 00000000相同，匹配成功。u继续匹配，最后选择前缀最长的路由表项5.4 路由查表路由查表5.4 路由查表路由查表查表算法查表算法 路由查表技术的研究现状：路由查表技术的研究现状： Binary Trie， Patricia， Path-compressed Trie（更新速度快，查表速度较慢） Binary Se
19、arch on Lengths（查表速度较快，更新速度慢） 基于CAM的查表算法(查表速度和更新速度都较快，成本较高) RLMS（Routing Lookups at Memory Speed）算法(查表速度快、成本低,更新速度较慢)简单覆盖式存储原理简单覆盖式存储原理R1Prefix: 00000001 xxxxxxxxPrefix: 000000011 xxxxxxxPrefix: 0000000110 xxxxxx占用表项单元：占用表项单元：1.0 1.255占用表项单元：占用表项单元：1.128 1.255占用表项单元：占用表项单元：1.128 1.191以以Prefix长度为长度为8
20、 16的情况为例的情况为例R2R35.4 路由查表路由查表查表算法查表算法0.00.10.2551.255255.2552.01.01.11.1271.1281.1291.1901.1911.1921.254R1R1R1R1R1R1R1R1R1R1R1R1R1R2R2R2R2R2R2R2R2R2R3R3R3R3R35.4 路由查表路由查表查表算法查表算法分段查表的依据：骨干路由器前缀分布分段查表的依据：骨干路由器前缀分布分段式最长匹配线速查表算法原理组成分段式最长匹配线速查表算法原理组成SegMidSegUpDA16M1MSegLow64K1624812Prefix=816Prefix=172
21、4Prefix=2532控制逻辑5.4 路由查表路由查表查表算法查表算法0.00.10.2551.255255.2552.01.01.11.1271.1281.1291.1901.1911.1921.254简单覆盖式混合存储原理简单覆盖式混合存储原理R1Prefix: 00000001 xxxxxxxxPrefix: 000000011 xxxxxxxPrefix: 0000000110 xxxxxx占用表项单元：占用表项单元：1.0 1.255占用表项单元：占用表项单元：1.128 1.255占用表项单元：占用表项单元：1.128 1.191（Prefix长度：长度： 24）以以Prefix
22、长度为长度为8 16的情况为例的情况为例Seg_lowR1R1R1R1R1R1R1R1R1R1R1R1R1R2R2R2R2R2R2R2R2R2R2R3R3R3R3R3R35.4 路由查表路由查表查表算法查表算法索引覆盖式存储原理索引覆盖式存储原理R1 （占用表项单元：（占用表项单元： Index i +0_ Index i +127）Prefix: 00000001 10001010 10111100 0xxxxxxx（Prefix长度：长度： 24）Index i812R2 （占用表项单元：（占用表项单元： Index i +32_ Index i +63）Prefix: 00000001
23、10001010 10111100 001xxxxxIndex i +0Index i +1Index i +127R1R1R1R1+20Seg_midSeg_upIndex i +32Index i +33R2R2R2R2Index i +635.4 路由查表路由查表查表算法查表算法5.4 路由查表路由查表组播查表组播查表5.4 路由查表路由查表组播查表组播查表主要内容主要内容1.1.转发引擎的功能转发引擎的功能2.2.转发引擎处理能力的估算转发引擎处理能力的估算3.3.有效性检查有效性检查4.4.路由查表路由查表5.5.包分类包分类5.5 包分类包分类包分类的目的：包分类的目的： 判断一个
24、到达的包属于哪一类业务，进行不同处理 包分类的功能：包分类的功能： 提供区分服务，是保证QoS的基础 防火墙 基于策略的路由选择 业务速率限制和警管具有包分类功能的路由器也称为 流识别路由器流识别路由器(Flow-aware Router)(Flow-aware Router) 或无层交换机或无层交换机(Layerless Switches(Layerless Switches）因此路由查表时包分类的一个特例5.5 包分类包分类包分类涉及到的域：包分类涉及到的域：5.5 包分类包分类PCNSE（Packet Classification with Network Search Engine） 分类器的原理框图分类器的原理框图5.5 包分类包分类
