您现在的位置:首页 >> IPv6技术前沿 >> 内容

Linux中ipv6代码阅读(3)

时间:2010/3/4 15:44:09 点击:2502

  核心提示:三.路由模块的处理1. 路由节点结构是fib6_node的结构,通过这个结构来组织成一棵路由树。这个结构主要是用来组织路由结构树的,具体的路由信息是存放在fib6_node-leaf结构中,这是一个rt6_info的结构体。每个fib6_node伴随着一个rt6_info。查找路由的时候,遍历整个路...

三.路由模块的处理
1. 路由节点结构是fib6_node的结构,通过这个结构来组织成一棵路由树。这个结构主要是用来组织路由结构树的,具体的路由信息是存放在fib6_node->leaf结构中,这是一个rt6_info的结构体。每个fib6_node伴随着一个rt6_info。查找路由的时候,遍历整个路由树,根据每个fib6_node节点的rt6_info信息,判断是否是自己需要的节点。如果是,则返回,然后根据这个节点的rt6_info信息进行路由。
2. 路由表的组织结构如下图所示。
这里多说两句,定义CONFIG_IPv6_SUBTREES情况,fib6_lookup_1会递归调用,但最多只能递归一次(因为subtree里不会再有subtree)。递归的那次fib6_lookup_1调用只对src进行了匹配,因为args[1]里的addr是src。
下图中的蓝色部分,表示每个fib6_node都伴随着一个rt6_info结构用来携带具体的路由信息。


3. IPv6的路由表是是一个radix树,根对应默认路由,结点的层次和路由prefix_len对应。在fib6_lookup_1()中下面的循环把fn设为叶子结点,然后从他开始匹配,如果不符就fn = fn->parent。这样就做到了最长匹配原则。

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;

}

4. 关于radix树的介绍,可以google,这里简单介绍一下,参考了blog:http://wurong81.spaces.live.com/blog/cns!5EB4A630986C6ECC!393.entry?sa=419936170 。Radix tree 是一种搜索树,采用二进制数据进行查找,如下图所示。但对于路由表,采用的是二叉树的方式,只有一个Left和right两个子节点。(好像fn_bit表示的是prefix_len,就是路由前缀的长度,不确定?)转载请注明出自IPv6之家 - 临时论坛 http://www.IPv6home.cn/bbs/,本贴地址:http://www.IPv6home.cn/bbs/thread-1988-1-1.html

作者:IPv6edu.com 来源:网络


共有评论 0相关评论
发表我的评论
  • 大名:
  • 内容:
  • IPv6教育(www.ipv6edu.com) © 2017 版权所有 All Rights Reserved.
  • Email:master@ipv6edu.com 京ICP备09058832号
  • Powered by ipv6edu!