交换技术基于DRAM的路由查找算法

　在线辅导　面授招生　考试大纲　指定教材　试题汇总

1.基于DRAM的路由查找算法
1）Dm-24-8-BASIC算法
目前应用较多的是一种基于DRAM称为DIR-24-8-BAS1C的路由查表算法。该算法采用存储在DRAM中的两个表，如图7-42所示。第一个表称为TBL24,存储所有长度小于等于24bit的网络前缀，该表有个表项，地址范围从0.0.0~255.255.255,TBL24的每一表项都有图7-43所示的格式。第二个表称为TBLlong，存储所有长度大于24bit的网络前缀。IP地址的这种24-8分割方式的合理性在于：第一，目前的内存技术很容易实现上述两个表；第二，一些骨干路由器转发表的测试结果显示，超过99%的网络前缀的长度小于等于24bit。
假设在一个空路由表里存储一个网络前缀X,如果X长度小于等于24bit,则仅仅存储在TBU4中，表项的第一位置0，表示表项剩余字段保存的是该表项的下一跳信息。如果，长度大于24bit,则根据X的前24位查找到TBL24中的表项，该表项的第一位置1,表示表项剩余字段为一个指向TBLlong表的指针。

事实上，在该算法中长度小于24bU的网络前缀被扩展了。例如，网络前缀128.23/16在TBL24中会有2^6=256个相关表项，范围从128.23_0-128.23.255,这256个表项都有相同内容（对应于网络前缀128_23/16的下一跳地址）。通过这种对内存的低效使用，经过一次内存访问就可获得下一跳信息。
TBLkrng包含了所有长度大丁24bit的网络前缀，对每个TBL24中的表项，其包含的网络前缀只要有一个长度大于24bit,则在TBLlong中就会被分配28=256个表项，每个表项对应了可能的256个长度大于24bit的网络前缀的一个，这256个网络前缀在TBL24中有共同的24位前缀。因为TBLlong的表项仅存储下一跳信息，如果假设作为下一跳节点的路由器少于256个（即路由器的端口数少于256个），则TBLlong每个表项的大小为lbyte。假定长度超过24bit的网络前缀的数童为4096(该值远远超过了实际情况），则TBLlong所占空间为1MB。
由此，对于给定的目的地址，根据该路由查找机制，首先，分离出地址的前24位用来检索TBL24,如果表项第一位是0,则表项后15位就是下一跳地址；否则（第一位是1),用后15位与256相乘作为基址，与原目的地址的后8位相加，再用得到的值检索TBLlong。

图7-45中24位前缀10.78.45包含两个网络前缀：A=10.78.45.128/26和B=10.78.45.132/30,长度最大为30位，则TBLlcmg要分配26=64个表项给前缀10.78.45。通过査询第一和第二个表，获得查询第三个表的索引325。由于30位相对于24位的偏移长度为6,所以要将325与原目的地址的4段中的最后一段（如128与132)的前6位相结合来检索第三个表对网络前缀B而言，其最后一段132的前6位有效，值为（lOOOOlh=33,所以表项325+33含有B的下一跳信息。对前缀A而言，其最后一段128的前2位（10)有效，对应的地址范围为100000~101111(即32~47),所以表项325+32-325+47(除去前缀B所对应的表项325+33)包含A的下一跳信息。

DIR-24-8-INT算法增加了一次内存访问，使流水线操作变为3个阶段，但是节省了TBLlong的内存空间。

返回目录： 通信专业交换技术非连接型快速分组交换汇总

编辑推荐

通信专业实务考试终端与业务教程汇总

通信专业实务考试设备与环境教程汇总

通信工程师考试培训交换理论基确汇总