理解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指针和一个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 *aggregate;/目前不解，聚类指针一般用于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 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_match(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)/创建第一个（时间顺序上的第一个，但不一定是根节点）节点，或/创建叶子节点 21 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_link (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 建立第一个节点假设现在没有节点，即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 插入子节点（叶子节点）程序第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行是查询功能，我们不管。17行将node赋值给match，即匹配到node这个节点。Node顺儿子指针被赋值为下一个，此处无论赋值左儿子还是右儿子都是空。（究竟如何确定被赋值为左还是右，下面会详细说到）。Node被赋值为空，于是推出循环体，并到达22行。此处，我们发现回到了上一小节“建立第一个节点”相同的内容。的确是一样，他们都是要重新分配table_node空间，并赋值prefix，但接下来就不同了。此处match不为NULL，我们此处是已经匹配到节点1的，所以执行24行set_link (match, new)。这个函数是将刚创建并赋好值得new插入到match之后，作他的儿子节点。具体怎么插入，我们来看：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范围内完全一样，这个函数其实就是检测prefix之后第一位，如果是零，则为左儿子，否则就是右儿子。father-linkbit = son， son-parent = father即是赋值动作。图二为加了之后的二叉树：图二 加入叶子节点2.3插入父节点或兄弟节点如果待加入的prefix，prefixlen比树第一个节点还要短，或者比树中某一个节点的prefixlen短，再或者跟树中某一个节点prefixlen一样长，但并不匹配它，即从循环体跳出，但node并不为空。此时程序到30行，函数route_node_create（）只是分配table_node大小的内存，并不给new赋值。31行，函数route_common (struct 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 prefixlen=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