基于概率的最优路由查询数据结构构建

Optimal Ip lookups data structure's construction based on probability

路由器的主要功能是按照IP分组中的目的地址转发分组,查找路由表决定将分组发往哪个端口.而路由查找是需要完成最长匹配地址前缀的查找,因此快速IP地址路由查找算法是实现高速分组转发的关键,而设计高性能的数据结构是实现高速路由查找的关键.本文针对前缀路由查询,根据前缀被访问的概率依据字母表树构建了一种基于概率的最优路由查询数据结构.

The router＇s main function is forwarding IP packets by destination address and looking up route table to decide which port the packet to be transmitted. Because looking up is the longest address prefix match, so rapid IP address prefix looking up algorithm is the key for rapid forwarding, however, high properties data structure is the key of IP looking up. This paper constructs a data structure to implement optimal looking up by alphabet tree based on probabilities of the prefix to be accessed.