路由器原理与设计lesson高速IP查表算法PPT学习教案

1、会计学1 路由器原理与设计路由器原理与设计lesson高速高速IP查表算查表算 法法 第1页/共59页 第2页/共59页 核心路由器上路由前缀长度超过24的十分少 例如：MAE-EAST骨干路由器中99.93%的路由前缀小于等于24 第3页/共59页 第4页/共59页 前缀长度小于24的将被扩展 例如128.23/16前缀将被扩展为224-16 256项，对应地址为：128.23.0 128.23.255，而这256项将保存相同 的内容，即指向前缀128.23/16转发 信息的指针 查表流程：查表流程： （1）使用高）使用高24位位IP地址查找地址查找TBL24，读出，读出2个字节数据个字节数

2、据 若第若第1位为位为0，后，后15位为下一跳信息位为下一跳信息 否则，把后否则，把后15位乘以位乘以256，加上，加上IP地址低地址低8位，计算新的地址位，计算新的地址 （2）使用新的地址查找）使用新的地址查找TLBlong表，获得下一跳信息表，获得下一跳信息 第5页/共59页 假设到达报文为： （1）10.54.22.147 （2）10.54.34.23 （3）10.54.34.194 232-26=64 每个前缀长度大于24的占用2562512字节 1M字节保存2K个前缀，满足核心路由器上前缀分布的要求 第6页/共59页 n若访存为50ns， 则每秒查表20M 次 第7页/共59页 将2

3、级表 变成3级表，TBLint表用来指示扩展表的大小，而不是默认的256项 用多一次访存换取TLBlong表利用率的提高 TLBlong中表项为26项 第8页/共59页 通过增加访存次数，降低存储开销 先用前n比特查表，若有扩展表项，则用i位索引拼上后续m位地址继续查找第二级表，以此类推 第9页/共59页 Row update：软件计算，为更新每个地址发出一条指令，硬件简单，软件开销太大 Subrange updata：软件计算可以连续更新的区域，发出一条指令，触发硬件更新多个连续的地址 One Instruction update：每个表项中包含对应的前缀长度（6位），硬件自动识别是否要更新

4、相应的表项 第10页/共59页 第11页/共59页 第12页/共59页 第13页/共59页 宽带（如 DSL） 100k个会话，基于会话的队列管理，QoS调度 租用线几K个会话（如T1），帧/语音和VPN的支持 大的企业网QoS支持，加解密，几百个网络接口，对支持的前缀数目 要求不高，但对性能要求较高 边缘ISP成百上千个接口，v4/v6/mpls支持，每个接口可能会有 大量VPN表，对支持的前缀数目和性能要求较高 核心ISP成百上千个接口，v4/v6/mpls支持，对性能要求很高 不同应用场合对路由器查表能力的不同要求不同应用场合对路由器查表能力的不同要求 注：一个物理接口可能包含大量的逻辑

5、接口，如ATM的VC，以太网的VLAN等 第14页/共59页 路由器的查表模型路由器的查表模型 第15页/共59页 转发需要的数据转发需要的数据 第16页/共59页 第17页/共59页 第18页/共59页 第19页/共59页 第20页/共59页 第21页/共59页 第22页/共59页 bank 1第一 级 bank 2第二 级 bank 1第三 级 bank 2第四 级 DRAM1DRAM2 转发引擎 通道通道1通道通道2 1.假设每个假设每个bank每每20ns可以访问一次，存储访问延时可以访问一次，存储访问延时10ns 2.如果同时对如果同时对2个目的个目的IP（d1、d2）进行查找，每个

6、需要访问）进行查找，每个需要访问4次，延时为次，延时为40ns。 3.但但d1在查找第在查找第34级时，级时，d2可以查找可以查找12级，因此平均级，因此平均20ns出一个结果出一个结果 第23页/共59页 第24页/共59页 SRAM和和DRAM存储器的比较存储器的比较 第25页/共59页 第26页/共59页 第27页/共59页 第28页/共59页 第29页/共59页 第30页/共59页 第31页/共59页 第32页/共59页 扩展扩展Tries示意图示意图 每一项都包含前缀和指针每一项都包含前缀和指针 第33页/共59页 Leaf pushing 示意图示意图 每一项包含前缀或指针每一项包

7、含前缀或指针 第34页/共59页 0代表本项与前一代表本项与前一 项相同项相同 Leaf pushing方法 第35页/共59页 第36页/共59页 o存储器采用burst的访问技术，每次访问存储器的数据 大小，例如SDRAM每次可burst32字节，因此multibit节 点的大小可针对存储器的burst大小进行优化 第37页/共59页 第38页/共59页 第39页/共59页 第40页/共59页 第41页/共59页 第42页/共59页 输入地址1110111 第43页/共59页 输入地址1110111 第44页/共59页 输入地址1110111 第45页/共59页 第46页/共59页 0 1 255 第47页/共59页 第48页/共59页 每个节点只保存外部bitmap和指向 子节点的指针 第49页/共59页 第50页/共59页 第51页/共59页 第