路由维护方法和装置以及路由查询方法和装置

摘要

本发明公开了一种路由维护方法和装置以及路由查询方法和装置。本发明分别为公网和每个VPN设置对应的虚拟路由(VR)表，如果路由表项IP地址前缀的掩码长度小于等于M，则直接在VR表中与IP地址前缀最高字节匹配的M比特数组元素下的路由集合中存放、查询该路由表项；如果路由表项IP地址前缀的掩码长度大于M，则逐级查询对应IP地址前缀后续相应比特的若干级哈希表，直至该IP地址前缀的掩码长度小于等于数组元素对应的最高M比特与后续若干级哈希表所对应的相应比特之和，然后匹配的哈希元素下的路由集合中存放、查询该路由表项。因此，本发明能够提高路由查询效率、且同时适用于组播路由。

主权项

1.一种路由维护方法，其特征在于，分别为公网和每个VPN设置对应的虚拟路由VR表，每张VR表中包含有2^M个用于与IP地址前缀最高字节匹配的M比特数组元素、每个数组元素下可衍生出第1级哈希表和/或第1级路由集合、第i级哈希表中每个哈希元素下可衍生出第i+1级哈希表和/或第i+1级路由集合、i大于等于1且小于等于哈希表的预设最大级数P、P为大于等于1且小于等于32-M的正整数，且对于需要存储的公网或任意VPN的路由表项，该路由维护方法包括：利用该路由表项的IP地址前缀的最高字节在对应VR表中查找匹配的数组元素；当该路由表项IP地址前缀的掩码长度小于等于M时，将该路由表项存放至匹配的数组元素下的第1级路由集合中；当该路由表项IP地址前缀的掩码长度大于M时，从匹配的数组元素下的第1级哈希表开始，依次查找第i级哈希表中与IP地址前缀第比特匹配的Ni比特哈希元素、并针对第i级哈希表判断该路由表项IP地址前缀第比特的掩码长度是否小于等于Ni，如果是，将该路由表项存放至第i级哈希表中匹配的Ni比特哈希元素下的第i+1级路由集合中，否则，继续针对第i级哈希表中匹配的Ni比特哈希元素下的第i+1级哈希表进行判断；其中，N0取0，且Ni为满足N1～NP之和等于32-M这一条件下任意设定的正整数。