路由匹配算法

前几天听说用哈希算法查找路由的，说是linux就是这样实现的。没想明白是如何实现的。从原理上来说，路由匹配

是最长匹配，它需要匹配掩码，这一点与session 匹配以及mac地址查找不同。session或者mac查找过程里面，往

表里面填的数据是确定值的，但是在路由查找里面，需要比较掩码。所以路由查找一般都是采用树型算法。如果采用

哈希算法，不知道这个哈希表如何构造。按掩码，从1~32构造32个哈希表。匹配的时候，从最长的32位掩码开始，

直到0位掩码匹配缺省路由？不知道这样做是否可行，或者效果如何。

ip classify或者policy match的思路与此相同。当然，policy match通常有多个dimensions，也就是说有多个匹配项，

这些项之间是与的关系。所以可以把这些项加起来，比如5-tuple，可以构造出一个8+32*3=104 bits的匹配树，有掩码

的部分填成0就可以了。

ip classify算法是网络里面的核心算法，不过大多数人都没太仔细考虑过其中的细节。