基于比特向量的高速路由查找装置及方法

摘要

本发明公开了一种基于比特向量的高速路由查找装置及方法，主要解决现有路由查找方法数据结构与查找操作复杂，硬件实现困难，查找速度低的问题。其装置包括路由表编码模块、路由查找模块和优先编码器模块。其方法的步骤包括：将路由表中存放的所有路由表项按网络前缀长度降序排序；将路由表分割成多个路由表块；将路由表块转换为比特向量阵列存放在存储器中；从存储器中读出对应子地址中的比特向量按位相“与”；找出最长前缀匹配的路由表项。本发明具有数据结构与查找操作简单，易于硬件实现，查找速度高的优点。

主权项

一种基于比特向量的高速路由查找装置，包括路由表编码模块，路由查找模块和优先编码器模块三个模块，其中，所述路由表编码模块，用于将路由表中的所有路由表项按前缀长度降序排序，将排序后的路由表分割为路由表块，采用比特向量编码方法，将每个路由表块转换为比特向量阵列，写入到路由查找模块的存储器中；所述路由查找模块，用于将待查找的目的网络地址的子地址作为存储器的地址，送入对应的存储器中，读出存储器在该地址中存放的比特向量，将同一组路由表项对应的比特向量按位相“与”，得到结果比特向量，输出给优先编码器模块；所述优先编码器模块，用于找到结果向量中第一个为“1”的位置对应的路由表项，该路由表项为匹配前缀最长的路由表项。