《浅析route_table是如何工作.doc》由会员分享,可在线阅读,更多相关《浅析route_table是如何工作.doc(8页珍藏版)》请在金锄头文库上搜索。
1、理解Route_table是如何工作指导人:郭巍松作者:王岩广时间:2005-9-71 Route_table结构很重要Dcnos中route_table这个数据结构非常重要,许多结构是通过它来实现,比如PIM-SM中的TIB,注册状态reg,nexthop cache等都其实是一个route_table。Route_table是一个二叉树(每一个节点除带有一个左儿子,一个右儿子,还有一个父指针)。一个完整的route_table,由两种结构组成,一个route_table和若干个route_node。 Struct route_table 这个结构由一个Stuct route_node指针和
2、一个table号组成。Struct route_node *top;U_int32_t id;/table号 Stuct route_node 这个结构其实是一个二叉树。(应为三叉树),它的内容包括:Struct route_node *link2;/两个儿子Stuct prefix p;/前缀信息Struct route_table *table;/指向一个route_table,从我们使用来看,它是回指本身所在的表Stuct route_node *parent;/父节点U_int32_t lock;Void *info;/这个节点真正的信息所在。注意是任意类型指针Void *aggreg
3、ate;/目前不解,聚类指针一般用于ripng中一个Table是由若干个route_node组成,每一个route_node除了有一个父节点和两个儿子节点外,还可以指向另一个table。下图是一个route_table的例子。一个route_table骨架(没有画出info指针)2 Route_table表节点的插入一个route_table是通过函数一次或多次调用route_node_get(table,prefix)来创建和查询,通过route_node_lookup()来查询(不创建)。现在通过get函数来分析一个table是如何建立起来,和如何查询的。Get函数如下:1 struct
4、route_node *2 route_node_get (struct route_table *table, struct prefix *p)3 4 struct route_node *new; 5 struct route_node *node;6 struct route_node *match; /表示被匹配到的节点,如果没有匹配到为空7 match = NULL; 8 node = table-top; 9 while (node & node-p.prefixlen prefixlen & 10 prefix_match (&node-p, p) /如果prefix_matc
5、h(a,b), 即a的prefixlen小于等于b,并/且a的prefix中的前prefixlen跟b相同,即我们一般所/说的最短匹配 11 12 if (node-p.prefixlen = p-prefixlen)13 14 route_lock_node (node);15 return node;/查询作用16 17 match = node; 18 node = node-linkcheck_bit(&p-u.prefix, node-p.prefixlen); 19 20 if (node = NULL)/创建第一个(时间顺序上的第一个,但不一定是根节点)节点,或/创建叶子节点 2
6、1 22 new = route_node_set (table, p); 23 if (match) /创建的是叶子节点24 set_link (match, new); 25 else26 table-top = new; /第一个节点 27 28 else/创建中间节点 29 30 new = route_node_create (); 31 route_common (&node-p, p, &new-p);/new-p尽量长的prefixlen,但要匹配/node-p 32 new-p.family = p-family; 33 new-table = table; 34 set_l
7、ink (new, node); 35 if (match)36 set_link (match, new); 37 else38table-top = new; 39 if (new-p.prefixlen != p-prefixlen)/创建兄弟节点4041 match = new; /创建的这个new不会被return出去,也就是不会被赋值info指针42 new = route_node_set (table, p);43 set_link (match, new);44 45 46 route_lock_node (new); 47 return new;48 2.1 建立第一个节点
8、假设现在没有节点,即route_table-top为NULL,则第8行,node被赋值为NULL,则跳过循环体(一个查询匹配过程),因为node为NULL,程序到22行,new=route_node_set(table,p)函数分配一个route_node大小内存,并把p中的内容内存拷贝到new,则节点创建好了,接下来将这个节点接在table后,即让table-top=new。(显然此处match为NULL),此刻表如图1所示:(注意:图中table_node结构没有画全,省略了lock,aggregate。为了易于理解,1表示加入的顺序号)图1 第一个节点2.2 插入子节点(叶子节点)程序第
9、8行,node被赋值为table-top的值,即上图中1号table_node的地址。子节点的prefixlen一定要大于等于父节点的prefixlen,并且要匹配父节点。Prefix_match(prefix *n,prefix *p)=true函数的含义是:p- prefixlen=n-prefixlen,并且在p-u.prefix的0到n-prefixlen-1位与n-u.prefix的相应位相同,一句话就是我们常说的匹配。其余情况返回false。可以子节点的prefix一定要匹配父节点的prefix,或者说父节点的prefix包含子节点的prefix。进入循环体,12行到16行是查询功
10、能,我们不管。17行将node赋值给match,即匹配到node这个节点。Node顺儿子指针被赋值为下一个,此处无论赋值左儿子还是右儿子都是空。(究竟如何确定被赋值为左还是右,下面会详细说到)。Node被赋值为空,于是推出循环体,并到达22行。此处,我们发现回到了上一小节“建立第一个节点”相同的内容。的确是一样,他们都是要重新分配table_node空间,并赋值prefix,但接下来就不同了。此处match不为NULL,我们此处是已经匹配到节点1的,所以执行24行set_link (match, new)。这个函数是将刚创建并赋好值得new插入到match之后,作他的儿子节点。具体怎么插入,我
11、们来看:static voidset_link (struct route_node *father, struct route_node *son) int bit; bit = check_bit (&son-p.u.prefix, father-p.prefixlen); pal_assert (bit = 0 | bit = 1); father-linkbit = son; son-parent = father;可以看出,要想做father的儿子,首先决定确左儿子还是右儿子,通过函数check_bit来确定。因为儿子跟父子在父子的prefixlen范围内完全一样,这个函数其实就是检
12、测prefix之后第一位,如果是零,则为左儿子,否则就是右儿子。father-linkbit = son, son-parent = father即是赋值动作。图二为加了之后的二叉树:图二 加入叶子节点2.3插入父节点或兄弟节点如果待加入的prefix,prefixlen比树第一个节点还要短,或者比树中某一个节点的prefixlen短,再或者跟树中某一个节点prefixlen一样长,但并不匹配它,即从循环体跳出,但node并不为空。此时程序到30行,函数route_node_create()只是分配table_node大小的内存,并不给new赋值。31行,函数route_common (str
13、uct prefix *n, struct prefix *p, struct prefix *new)其实是给new赋值的过程,如何赋值呢?如果在p-prefixlen之内,从最左边(最高位)开始n-u.prefix跟p-u.prefix连续相同的bit位,赋值给new-u.prefix的相应位,同时这个位数作为new-prefixlen,其他位赋值0。举例n-u.prefix 1100 0000 1110 0001 0010 0001 0000 0001 prefixlen=24p-u.prefix 1100 0100 1100 0001 0010 0001 0000 0001 prefi
14、xlen=18new-u.prefix 1100 0000 0000 0000 0000 0000 0000 0000 prefixlen=5可以看出:l 如果new-prefixlen等于p-prefixlen,则表示在p-prefixlen范围内p的值跟n-u.prefix完全相等,同时p-prefixlen又小于等于n-prefixlen,进一步说p包含了n,则p应为n的父节点。l 如果new-prefixlen小于p-prefixlen,则表示p-u.prefix从new-prefixlen之后开始不同于n-u.prefix,即n和p都应该是new的儿子,且因为第new-prefixlen个bit不同而分为左儿子和又儿子。代码30-38插入父节点new,代码39-44,即为如果new-prefixlen小于p-prefixlen,插入兄弟节点。下图是几种插入后的可能情况:图3-1 插入成为根节点(虚线表示可能需要插入为兄弟节点)图3-2 插入中间结点(虚线表示可能插入为兄弟节点)最后,通过插入过程我们可以看出如下几个特征:l 子节点一定匹配父节点,父节点一定包含子节点(即子的掩码长度=父的,且最短匹配)l 子节点的prefix中在父节点的prefixlen之后的第一位为0,则为左节点,否则为右节点l 左节点和右节点的prefixlen