开源世界中的算法与数据结构 3 -- Linux IPv6 FIB表实现 -- 算法 -- IT技术博客大学习 -- 共学习共进步！

您现在的位置：首页 --> 算法 --> 开源世界中的算法与数据结构 3 -- Linux IPv6 FIB表实现

开源世界中的算法与数据结构 3 -- Linux IPv6 FIB表实现

浏览:2386次出处信息

在Linux 2.4 IPv4 FIB的数据结构基础上实现IPv6的FIB是否可行呢？如果读了我前面这篇文字你应该会有一个判断。IPv4的FIB实现可以说有些拙劣，如果照搬一个IPv6版本，最差情况下需要进行128次hash key计算这还不包括链表的查找过程。看了一下Linux 2.6的IPv6 FIB实现，已经有了调整，用了Patrix（Radix）树实现了这个算法，下面是一些背景知识：

首先是Trie树，下图是Wiki http://en.wikipedia.org/wiki/Trie 之中的一个例子

Trie树，尤其是二叉Trie树属于：是一直被使用，从未被（教科书）重视的东东。其特点是键值的内容成为树的检索路径，例如上图的to，tea等几条键值标明的路径。如果要对trie分类的话，我想只能按照出度来分类，上图假定键值的每一字节取值a-z，则这个trie是26叉trie树，最小出度的Trie树是二叉Trie树，简称BTrie。

所谓PATRICIA Tree或Radix Tree是同一种数据结构，不是标准Trie树，是Trie树的优化变异，Wiki http://en.wikipedia.org/wiki/Radix_tree上有如下图：

romane和romanus以及romulus有共同前缀rom，此处r是根，om本应为两个节点，现在合并为一个，这个就是Radix树的优化思路，优化之后，可以减少tree的层次，提高匹配速度。而IPv6 FIB就实现为一种二叉 Radix树，其实现结构同这种标准的Radix树还有少许改动，下面简介其实现：

其节点数据结构如下：

struct fib6_node {

struct fib6_node *parent; -- 因为其lookup算法实现要求回溯，所以引入了parent指针，如果按照标准的radix树Wiki实现，则不需要这个节点。

struct fib6_node *left;

struct fib6_node *right;

#ifdef CONFIG_IPV6_SUBTREES

struct fib6_node *subtree; -- 用于MobileIPv6

#endif

struct rt6_info *leaf; -- 存储路由信息

__u16 fn_bit; Prefix长度

__u16 fn_flags;

__u32 fn_sernum;

struct rt6_info *rr_ptr;

};

其查找算法实现为如下函数fib6_lookup_1：

static struct fib6_node * fib6_lookup_1(struct fib6_node *root,
                    struct lookup_args *args)
{
    struct fib6_node *fn;
    __be32 dir;

if (unlikely(args->offset == 0))
return NULL;

    /*
     *    Descend on a tree
     */

fn = root;

这一段for循环按照输入的IP进行最长掩码匹配

由于fib node之中没有保存父子点common的prefix，

因此无法进行精确匹配，只能按照分支bit进行匹配，决定前进方向

for (;;) {

struct fib6_node *next;

dir = addr_bit_set(args->addr, fn->fn_bit);

next = dir ? fn->right : fn->left;

        if (next) {
            fn = next;
            continue;
        }

break;
}

上述for循环结束时，找到了最match的节点。但是由于是模糊匹配，

需要回溯每个节点，找到一个最终的正确的最长掩码匹配。

    while(fn) {
        if (FIB6_SUBTREE(fn) || fn->fn_flags & RTN_RTINFO) {
            struct rt6key *key;

key = (struct rt6key *) ((u8 *) fn->leaf +
args->offset);

            if (ipv6_prefix_equal(&key->addr, args->addr, key->plen)) {
#ifdef CONFIG_IPV6_SUBTREES
                if (fn->subtree)
                    fn = fib6_lookup_1(fn->subtree, args + 1);
#endif
                if (!fn || fn->fn_flags & RTN_RTINFO)
                    return fn;
            }
        }

if (fn->fn_flags & RTN_ROOT)
break;

fn = fn->parent;
}

return NULL;
}