最长前缀匹配算法详解：哈希表与Trie树的优化之道

最长前缀匹配算法详解：哈希表与Trie树的优化之道

在互联网中，路由器负责将数据包转发到正确的下一跳网络节点。在路由器中维护着一个路由表，包含若干路由表条目。路由表中每个条目包含一个 IP 地址前缀和转发链路信息，所有具有某一条目的前缀的 IP 地址都可以匹配到这个条目。由于同一个IP地址可能匹配到多个前缀，路由器需要选择其中最长可匹配的前缀作为匹配条目，即执行最长前缀匹配（LPM）查询。

背景介绍

在互联网中，路由器负责将数据包转发到正确的下一跳网络节点。在路由器中维护着一个路由表，包含若干路由表条目。路由表中每个条目包含一个 IP 地址前缀和转发链路信息，所有具有某一条目的前缀的 IP 地址都可以匹配到这个条目。由于同一个IP地址可能匹配到多个前缀，路由器需要选择其中最长可匹配的前缀作为匹配条目，即执行最长前缀匹配（LPM）查询。

一方面，由于当前互联网采用了无类别域间路由（Classless Inter-Domain Routing, CIDR），路由表条目的前缀长度可以任意变化，这增加了执行LPM查询的难度。另一方面，随着网络的普及和网络应用的发展，路由表的规模和转发速度需求都在飞速增长。这使得LPM查询成为了网络性能的一个关键瓶颈。本文回顾了过往的LPM查询软件算法，并总结了这些算法使用的优化技巧。

算法概览

LPM算法可视作为路由表建立一个索引，利用索引可以快速寻找到IP地址对应的路由表条目。

为了确保查询到IP地址的最长可匹配的前缀，一种最简单的做法是搜索所有长度的前缀，但是这样会使得搜索次数很多。因此，最长前缀匹配算法中第一个优化方向就是如何尽量减少搜索次数。过往算法中应用了二分搜索或者间隔搜索，有效地优化了搜索次数。

由于路由表规模越来越大，超过了CPU缓存的容量。因此，访问内存成为了LPM查询的最大开销。基于CPU的缓存机制，路由表索引的内存占用越少，则可以将更多的信息存储在缓存中，从而可以大大降低访存开销。为此，现有算法采用多种方法进行内存压缩，减少浪费和重复的内存。

此外，除去LPM查询外，对于路由表的更新也需要有所考虑。当网络变动频繁时，每秒可以进行很多次路由表更新。如若不能及时更新，则可能有大量数据包被发送到错误的链路中，从而造成丢包或者网络拥堵。过往算法为了优化LPM查询，对于路由表更新的优化较少，甚至无法支持在线的更新操作，必须一次性建立整个路由表。

基于哈希表的算法介绍

Marcel Waldvogel等人在[1]中提出了一种基于哈希表的LPM算法。该算法将路由表中的前缀按照长度划分，分别插入到不同的路由表中。在执行LPM查询的时候，一种简单的做法是从长到短线性地在对应哈希表中搜索是否有可匹配前缀。该论文为了减少搜索哈希表的次数，设计了二分搜索的算法。为了支持二分搜索的查询算法，论文引入了辅助信息Marker。具体来说，每个前缀除了插入到对应长度的哈希表中外，还应将其子前缀的Marker插入到子前缀对应的哈希表中（如果子前缀在该哈希表中不存在）。

在二分搜索中，每次搜索中间长度的哈希表，如若搜索到匹配前缀或者搜索到匹配的前缀Marker，则继续在更长的前缀哈希表中进行二分搜索；反之，若均未搜索到，则继续在更短的前缀哈希表中进行二分搜索。此外，为了记录搜索到的最长可匹配前缀，还需要对每一个前缀Marker执行预计算，计算其在整个路由表中可匹配的最长前缀。每当搜索到匹配前缀时，记录之作为当前最长可匹配前缀；每当搜索到匹配的前缀Marker时，则记录其预计算的前缀作为当前最长可匹配前缀。搜索完成后所记录的最长可匹配前缀即是LPM查询的最终结果。

图 1：哈希表上执行二分查找

该论文还讨论了进一步优化方式，通过基于前缀分布建立不同的二分搜索树，减少平均搜索时间。图2展示了在不同权重下建立的二分搜索树。这种搜索树可能使得最坏搜索时间增加，但是使得平均搜索时间减少。

图 2：根据前缀分布建立不同的二分搜索树

基于Trie树的算法介绍

Trie树索引在前缀查询中应用广泛。Trie树中每一个结点都可以表示一个字符串，即可以自然地表示一个前缀。然而，由于CIDR协议，IP前缀的最小单位为一个比特。如果Trie树设计为1比特步长，即每个结点仅能检查一个比特位，则树的高度将会很大，查询效率就会很低。而如果使用多比特步长的Trie树，则结点自身只能对应于特定长度的前缀，需要设计方法来存储和查询非特定长度的IP前缀。目前工作中主要有两种设计思路，一种是利用前缀拓展（或称叶子结点下推），将非特定长度的前缀拓展成若干条特定长度前缀；另外一种思路是单独用叶子结点存储前缀，而不是直接用Trie树结点表示前缀。本文介绍这两种设计思路的过往工作

Poptrie算法

Poptrie算法[2]使用了6比特步长的Trie树，并采用了前缀拓展的策略，使得所有前缀长度均为6的倍数。同时，如果有一个前缀是另外一个前缀的子前缀，也需要拓展该子前缀。这样，所有的前缀都可以用一个Trie树结点表示，且每个Trie树结点要么是内部结点（不包含前缀），要么是叶子结点（对应于一个前缀，但是没有子节点）。

图3展示了一个2比特步长Poptrie内部结点数据结构样例。它用一个bitmap来指示每一个子节点的类型，0表示是叶子结点，1表示内部节点。为了减少子结点指针的开销，Poptrie将所有内部结点和叶子结点分别用一个数组存储，同时每个结点的子结点分别在内部结点数组和叶子结点数组中占用连续的空间。这样，在每个Poptrie的内部结点中，只需要分别存储其子节点中内部结点和叶子结点的起始结点在对应数组中的基地址。当需要查询其子结点时，先通过bitmap查询对应子结点是内部结点还是叶子结点。如果是内部结点，则计算在bitmap在该位前1的个数，结合储存的得到其对应子结点在内部结点数组中的基地址，可以得到对应子结点位置。该子结点为叶子结点时的情况也类似。特别的，Poptrie论文使用了CPU的popcnt指令集来加速计算1的个数的速度，以此实现高效的查询。在执行LPM查询时，只需要沿着Poptrie搜索到叶子结点即可得到最长可匹配前缀，不存在需要回溯的问题。

图 3：2比特步长Poptrie内部结点数据结构

由于前缀拓展会将同一个前缀拓展为多个前缀，但是它们的信息都是相同的，因此可以进行进一步的压缩。如图4所示，另外每个结点用另外一个bitmap来指示对应叶子结点与其前面叶子结点是否相同，这样对于由同一个前缀拓展出来的前缀叶子结点，只需要存储一次。

图 4：对相同叶子结点进行压缩后的内部结点数据结构

此外，为了提高LPM查询效率。Poptrie论文设计了Direct Pointing的策略，将前若干层的Poptrie结点直接存储在一层中，用一个2s长度（s为压缩的层次对应的IP地址比特位数）的四字节数组指示对应结点的类型（使用最高的一个比特位）及其在对应数组中的位置。

图 5：使用Direct Pointing减少访问结点次数

Tree Bitmap算法

使用前缀拓展的优势在于可以解决回溯的问题，但是代价是对于路由表的更新变得困难。因为更新可能需要将新的前缀或者旧的前缀进行拓展，并修改多个结点。Tree Bitmap[3]采用了另外一种方法设计多比特Trie树。

如图6所示，对于一个3比特步长的Trie树，每个Trie树结点可以视作包含三层的二叉Trie树的子树。其中标注为黑色的圆点代表二叉Trie树结点对应了一个前缀。Tree Bitmap算法用一个Internal Tree Bitmap来表示结点所对应的二叉Trie树结点是否对应前缀。同样，对于其子结点，用一个Extending Paths Bitmap表示对应子结点是否存在。这样，类似于Poptrie中的做法，Tree Bitmap将每个结点的前缀连续地存储在叶子结点中，而将其子结点连续地存储在子结点数组中。这样就可以只存储两类结点地基地址，减少指针占用地内存。

Tree Bitmap的设计不能像前缀拓展保证叶子结点一定是可匹配到的前缀，因此需要解决回溯的问题。Tree Bitmap采用的策略是在每次访问一个结点时，先查询其是否有可匹配的叶子结点，若有，则记录最长可匹配前缀，然后再进行下一层结点的查询。

图 6：Tree Bitmap的结点存储方式

Tree Bitmap的设计既保持了良好的内存效率，也兼顾了路由表索引的更新效率，代价是需要解决回溯的问题，使得查询效率无法很高。但是由于CPU缓存机制的存在，以及网络实际环境中大量相同或有相同前缀的IP地址查询，其实际查询效率仍然是可以接受的。

总结

本文回顾了关于LPM算法的过往算法，并对其采用的思想进行总结。在减少查询时间方面，可以采用二分搜索和间隔搜索的策略。在减少内存占用方面，可以使用bitmap进行压缩，减少内存的闲置和重复记录。此外，还可以使用预计算、预分配结点数组等策略优化时间和空间效率。

参考文献

[1] WALDVOGEL M, VARGHESE G, TURNER J, et al. Scalable high speed IP routing lookups[J/OL]. SIGCOMM Comput. Commun. Rev., 1997, 27(4):25-36.

[2] ASAI H, OHARA Y. Poptrie: A Compressed Trie with Population Count for Fast and Scalable Software IP Routing Table Lookup[J/OL]. SIGCOMM Comput. Commun. Rev., 2015, 45(4):57-70.

[3] EATHERTON W, VARGHESE G, DITTIA Z. Tree bitmap: hardware/software IP lookups with incremental updates[J/OL]. SIGCOMM Comput. Commun. Rev., 2004, 34(2):97-122.