使用压缩树转发表的网络路由器搜索引擎

摘要

网络路由设备在路由表(138、140、142)和分配的转发表中使用多层树(144,146,148)数据结构。每个结构的每一层与在所接收分组中出现的一个网络地址的不同字段相关联。每个结构中的指针用于标识下一跳网络的一个地址或者将被寻找下一跳地址的一个下一层树。一个未压缩树路由表使用直接寻址的树以便简化指针的存储和提取,并且下一树指针直接标识下一树。通过将在一层或多层上存储的指针数目减少到基本上为在该层上与网络地址相关的唯一下一跳地址的数目,根据未压缩路由表生成压缩树转发表。单个映射表将一层上的指针值映射到压缩树中下一层上的树的位置。下一跳指针查找逻辑电路(50,52,76,78)根据压缩树的结构执行查找。而且,查找逻辑电路存储和选择性地操作多个转发表以为虚拟路由操作提供支持。

主权项

1.一种转发表，用于标识分组应当被转发到的网络的下一跳的地址，该转发表包括第一层表，该表的表目可以由分组地址字段的地址比特的第一字段直接寻址，和第二层表，该表的表目可以由分组地址字段的地址比特的第二字段联合寻址，第一层表格为一些分组有效地提供(i)表示下一跳网络地址的下一跳索引，这些分组地址的地址比特的第一字段足以确定下一跳地址，和(ii)为另一些分组提供到第二层表的一个指针，这些分组地址的地址比特不足以确定下一跳地址；第二层表为一些分组有效地提供表示下一跳网络地址的一个下一跳索引，这些分组地址的地址比特的第一和第二字段足以确定下一跳地址。