Linux 路由表的结构与算法分析

黄一文

 

路由是网络栈的核心部分。路由表本身的设计很大情度上影响着路由的性能，并且好的设计能减少系统资源的消耗，这两方面尤其体现在路由表的查找上。目前的内核路由存在两种查找算法，一种为HASH算法，另一种为LC-trie算法，前者是目前内核使用的缺省算法，而后者更适用在超大路由表的情况，它在这种情况提高查找效率的同时，大大地增加了算法本身的复杂性和内存的消耗。综上，这两种算法各有其适用的场合，本文分析了基于2.6.18内核路由部分的代码在HASH算法上路由表结构的实现，并且在文章最后给出了一个简单的策略路由的应用。

 

一、路由表的结构

       为了支持策略路由，Linux使用了多个路由表而不是一个，即使不使用策略路由，Linux也使用了两个路由表，一个用于上传给本地上层协议，另一个则用于转发。Linux使用多个路由表而不是一个，使不同策略的路由存放在不同的表中，有效地被免了查找庞大的路由表，在一定情度上提高了查找了效率。

 

       路由表本身不是由一个结构表示，而是由多个结构组合而成。路由表可以说是一个分层的结构组合。在第一层，它先将所有的路由根据子网掩码（netmask）的长度（0~32）分成33个部分（structfn_zone），然后在同一子网掩码（同一层）中，再根据子网的不同（如10.1.1.0/24和10.1.2.0/24），划分为第二层(struct fib_node)，在同一子网中，有可能由于TOS等属性的不同而使用不同的路由，这就是第三层（structfib_alias），第三层结构表示一个路由表项，而每个路由表项又包括一个相应的参数，如协议，下一跳路由地址等等，这就是第四层(structfib_info)。分层的好处是显而易见的，它使路由表的更加优化，逻辑上也更加清淅，并且使数据可以共享（如structfib_info），从而减少了数据的冗余。

 

 

       +

图1（引自[1]）

这个结构中包括这个表的ID，以及主要的一些用于操作路由表的函数指针，这里我们只关心最后一个域――tb_data[0]，这是一个零长的数组，它在内核中也较为常见，它表示

 

这个结构中有两个域比较重要，一个为fz_hash域，它指向一个HASH表的表头，这个HASH的长度是fz_divisor。并且这个HASH表的长度是可变的，当表长达到一个限定值时，将重建这个HASH表，被免出现HASH冲突表过长造成查找效率降低。

 

为了提高查找的效率，内核使用了大量的HASH表，而路由表就是一个例子。在图1中可以看到，等长子网掩码的路由存放在同一个fn_zone中，而根据到不同子网（fib_node）的路由键值（fn_key），将它HASH到相应的链表中。

 

这个键值其实就是这个子网值了（如10.1.1.0/24，则子网值为10.1.1），得到这个键值通过n =fn_hash()函数HASH之后就是这个子网对应的HASH值，然后就可以插入到相应的fz_hash[n]链表中了。冲突的fib_node由fn_hash域相链，而fn_alias则是指向到达这个子网的路由了。

当到达这个子网的路由由于TOS等属性的不同可存在着多个路由时，它们就通过fib_alias中fa_list域将这些路由表项链成一个链表。这个结构中的另一个域fa_info指向一个fib_info结构，这个才是存放真正重要路由信息的结构。

 

这个结构里面是一个用于路由的标志和属性，其中最重要的一个域是fib_nh[0]，在这里，我们再次看到了零长数组的应用，它是通过零长来实现变长结构的功能的。因为，我们需要一个定长的fib_info结构，但是在这个结构末尾，我们需要的fib_nh结构的个数是不确定的，它在运行时确定。这样，我们就可以通过这种结构组成，在运行时为fib_info分配空间的时候，同时在其末尾分配所需的若干个fib_nh结构数组，并且这个结构数组可以通过fib_info->fib_nh[n]来访问，在完成fib_info的分配后将fib_nhs域置为这个数组的长度。

 

另一方面，fib_info也是HASH表的一个应用，结构中存在着两个域，分别是fib_hash和fib_lhash，它们都用于HASH链表。这个结构在完成分配后，将被用fib_hash域链入fib_info_hash表中，如果这个路由存在首选源地址，这个fib_info将同时被用fib_lhash链入fib_info_laddrhash表中。这样，就可以根据不同目的实现快速查找了。

 

Structfib_nh也是一个重要的结构。它存放着下一跳路由的地址（nh_gw）。刚刚已经提到，一个路由（fib_alias）可能有多个fib_nh结构，它表示这个路由有多个下一跳地址，即它是多路径（multipath）的。下一跳地址的选择也有多种算法，这些算法都是基于nh_weight，nh_power域的。nh_hash域则是用于将nh_hash链入HASH表的。

 

二、路由的查找

       路由的查找速度直接影响着路由及整个网络栈的性能。路由的查找当然首先发生在路由缓存中，当在缓存中查找失败时，它再转去路由表中查找，这是本文所关注的地方。

 

       上一节已经详细地描述了路由表的组成。当一个主要的IP层将要发送或接收到一个IP数据包时，它就要调用路由子系统完成路由的查找工作。路由表查找就是根据给定的参数，在某一个路由表中找到合适的下一跳路由的地址。

 

       上面已提到过，当一个主机不支持策略路由时，它只使用了两个路由表，一个是ip_fib_local_table，用于本地，另一个是ip_fib_main_table，用于接发。只有在查找ip_fib_local_table表时没有找到匹配的路由（不是发给本地的）它才会去查找ip_fib_main_table。当一个主机支持策略路由时，它就有可能存在着多个路由表，因而路由表的选择也就是查找的一部分。路由表的选择是由策略来确定的，而策略则是由应用（用户）来指定的，如能过iprule命令：

       如上，第一条命令创建了基于源地址路由的一条策略，这个策略使用了RT1这个路由表，第二条命令创建了基于数据包入口的一个策略，这个策略使用了RT2这个路由表。当被指定的路由表不存在时，相应的路由表将被创建。

 

       第二步就是遍历这个路由表的fn_zone，遍历是从最长前缀（子网掩码最长）的fn_zone开始的，直到找到或出错为止。因为最长前缀才是最匹配的。假设有如下一个路由表：

 

它会先找到第二条路由，然后选择10.1.0.1作为下一跳地址。但是，如果由第二步定位到的子网(fib_node)有多个路由，如下：

 

到达同一个子网有两个可选的路由，仅凭目的子网无法确定，这时，它就需要更多的信息来确定路由的选择了，这就是用于查找路由的键值（structflowi）还包括其它信息（如TOS）的原因。这样，它才能定位到对应一个路由的一个fib_alias实例。而它指向的fib_info就是路由所需的信息了。

最后一步，如果内核被编译成支持多路径(multipath)路由，则fib_info中有多个fin_nh，这样，它还要从这个fib_nh数组中选出最合适的一个fib_nh，作为下一跳路由。

 

 

三、路由的插入与删除

       路由表的插入与删除可以看看是路由查找的一个应用，插入与删除的过程本身也包含一个查找的过程，这两个操作都需要检查被插入或被删除的路由表项是否存在，插入一个已经存在的路由表项要做特殊的处理，而删除一个不存在的路由表项当然会出错。

       下面看一个路由表插入的例子：

 

 

 

 

这个命令在内核中建立一条新的路由。它首先查找路由表RT3中的子网掩码长为24的fn_zone，如果找不到，则创建一个fn_zone。接着，继续查找子网为10.0.1的fib_node，同样，如果不存在，创建一个fib_node。然后它会在新建一个fib_info结构，这个结构包含2个fib_nh结构的数组（因为有两个nexthop），并根据用户空间传递过来的信息初始化这个结构，最后内核再创建一个fib_alias结构（如果先前已经存在，则出错），并用fib_nh来创始化相应的域，最后将自己链入fib_node的链中，这样就完成了路由的插入操作。

 

路由的删除操作是插入操作的逆过程，它包含一系列的查找与内存的释放操作，过程比较简单，这里就不再赘述了。

 

 

四、策略路由的一个简单应用

       Linux系统在策略路由开启的时候将使用多个路由表，它不同于其它某些系统，在所有情况下都只使用单个路由表。虽然使用单个路由表也可以实现策略路由，但是如本文之前所提到的，使用多个路由表可以得到更好的性能，特别在一个大型的路由系统中。下面只通过简单的情况说明Linux下策略路由的应用。

如图2，有如下一个应用需求，其中网关服务器上有三个网络接口。接口1的IP为172.16.100.1，子网掩码为255.255.255.0，网关gw1为a.b.c.d，172.16.100.0/24这个网段的主机可以通过这个网关上网；接口2的IP是172.16.10.1，子网掩码同接口一，网关gw2为e.f.g.h，172.16.10.0/24这个网段的主机可以通过这个网关上网；接口0的IP为192.168.1.1，这个网段的主机由于网络带宽的需求需要通过e.f.g.h这个更快的网关路由出去。

 

图 2

 

步骤一：设置各个网络接口的IP，和默认网关：

       其它接口IP的设置和第一个接口一样，这时，如果没有其它设置，则所有的数据通过这个默认网关路由出去。

 

步骤二：使子网172.16.10.0/24可以通过gw2路由出去

 

 

步骤三：添加一个路由表 

 

 

步骤四：使用策略路由使192.168.1.0/24网段的主机可以通过e.f.g.h这个网关上网

 

      

步骤五：刷新路由cache，使新的路由表生效

 

这样就可以实现了以上要求的策略路由了，并且可以通过traceroute工具来检测上面的设置是否能正常工作。

 
===============================================================================

linux双网卡怎么设置我就不说了,我这里说的是linux双网卡的流量问题...
可能这个问题很偏们..你们也许用不上..我还是要说..

问题描述,一个linux主机,上面两个网卡..:)

route -n的输出是这样的.

Destination     Gateway         Genmask         Flags Metric Ref    Use Iface
 
61.132.43.128   0.0.0.0         255.255.255.192 U     0      0        0 eth1
127.0.0.0       0.0.0.0         255.0.0.0       U     0      0        0 lo
0.0.0.0         61.132.43.134   0.0.0.0         UG    0      0        0 eth0
 

这里解释一下...第一行是说,你要访问61.132.43.128这个网段,掩码是255.255.255.192的话..从e
th1这个网卡出去..
第二行是关于本机的,访问自己从lo这个虚拟的本地网卡走..
第三行是说你要去任何地方的话..从网关61.132.43.134出去.并且网卡是eth0

 

到这里我们看到了..我们除了去61.132.43.128这个网络是从eth1走以外..去其他地方都是从eth0�
�...

这样是不是很浪费了双网卡??没错..是很浪费..因为不论你用那种监测工具查看流量..都是eth0有
..而其他网卡没有...天哪...为此我是煞费苦心..甚至怀疑网卡是不是坏了..因为在win2k上这种�
虑槭遣豢赡芊⑸�..:)

那我们怎么解决这个问题呢?有人也许会说给个不同网关让另一块网卡用其他网关不就可以..是这�
鍪强梢�..但是问题是我的ip都是在同一个网段..那来的不同网关.?网关就一个61.132.43.134...

还好linux系统给我们提供了一个很好的路由套件---iproute2

我们来熟悉一下..iproute2由几个常见的命令..
ip ro ls ip就是ip命令啦,ro就是route的所写,ls是list的缩写...
整个命令就是列出系统的路由表..这个可和route
-n的效果差不多..但是更为清楚系统的route是如何的..

我们来看看吧:

[root@localhost root]# ip ro ls
 
61.132.43.128/26 dev eth1  proto kernel  scope link  src 61.132.43.136 
127.0.0.0/8 dev lo  scope link 
default via 61.132.43.134 dev eth0 
 

 

是不是一样呢?由几个地方不同..第一条多了一个src,增加了对源数据包的选择,而且子网掩码也变
成/26的形式..(参考ip地址的书籍)
最后一个仍然是网关...

现在我们只要稍稍动手把从61.132.43.136出来的流量让他不要从eth0出去..然他走eth1
我们加一条自定义的路由表

ip ro add default via 61.132.43.134 table 200
 
 

这里只是加了一条默认路由到一个自定义的路由表200中,最大数值是255,但是你不要用255,因为那
是系统默认用了..你用200以下就可以.
具体的路由表在/etc/iproute2/rt_tables中

 

查看刚才建立的路由表可以用ip ro ls table 200

[root@localhost root]# ip ro ls table 200
 
default via 61.132.43.134 dev eth1 
 

 

看到了吗?虽然我没有指定dev是什么.但是系统自动分配了一个eth1给这个路由表,因为eth0已经用
在主路由表中了..
这也说明了,的确不能在同一个路由表中由相同的网关..虽然可以设置,但是具体没什么作用.

然后我们要用一个规则把,匹配的数据包引导到刚刚建立的路由表中..:)

ip ru add from 61.132.43.136 table 200
 
 

这里ru是rule的缩写.from是一个匹配的动作.就是所源地址是61.132.43.136的包..请走自定义路�
杀�的设置..:)

 

查看一下

[root@localhost root]# ip ru ls
 
0:      from all lookup local 
32765:  from 61.132.43.136 lookup 200 
32766:  from all lookup main 
32767:  from all lookup 253 
 

 
ip ro flush cache

linux 下 双网卡 同网段，可以把IP_FORWARD 打开，这样一个网卡down掉数据会从另外一个网卡出去
===============================================================================
linux路由表

宏CONFIG_IP_MULTIPLE_TABLES表示路由策略，当定义了该宏,也即意味着内核配置了“路由策略”。产生的最大的不同就是内核可以使用多达256张FIB。其实，这256张FIB在内核中的表示是一个全局数组：
        struct fib_table *myfib_tables[RT_TABLE_MAX+1];
而宏RT_TABLE_MAX定义如下：
        enum rt_class_t
        {
            RT_TABLE_UNSPEC=0,
            RT_TABLE_DEFAULT=253,
            RT_TABLE_MAIN=254,
            RT_TABLE_LOCAL=255,
            __RT_TABLE_MAX
        };
        #define RT_TABLE_MAX (__RT_TABLE_MAX - 1)
    我们可以看到，虽然这张表多达256项，但枚举类型rt_class_t给出的表示最常用的也就三项，在系统初始化时，由内核配置生成的路由表只有RT_TABLE_MAIN，RT_TABLE_LOCAL两张。
   main表中存放的是路由类型为RTN_UNICAST的所有路由项，即网关或直接连接的路由。在myfib_add_ifaddr函数中是这样添加main表项的：对于某个网络设备接口的一个IP地址，如果目的地址的网络号不是零网络（网络号与子网号全为零），并且它是primary地址，同时，它不是D类地址（网络号与子网号占32位）。最后一个条件是：它不是一个环回地址(device上有flagIFF_LOOPBACK）。那么，就添加为main表项，如果是环回地址，则添加为local表的一个表项。
    在我们的系统中，有两个已开启的网络设备接口eth0和lo，eth0上配置的primaryIP地址是172.16.48.2，所以，相应的，main表中就只有一项。为main表添加路由项的时候，该路由项的目的地址是子网内的所有主机（把主机号部分字节清零），而对应于lo，在local表中也有一项，其类型为RTN_LOCAL(注：前一篇文章中的local表的hash8中的路由项表述有误，类型应该是RTN_LOCAL，而不是RTN_BORADCAST)。
   而其它的路由项全部归入local表，主要是广播路由项和本地路由项。在我们的系统环境下，local表共有7项，每个网络设备接口占三项。分别是本地地址（源跟目的地址一致），子网广播地址（主机号全为1)，子网广播地址（主机号为零)。再加上一个lo的RTN_LOCAL项。
    现在我们再来看myfib_add_ifaddr函数的路由添加策略。对于一个传入的ip地址（结构structin_ifaddr表示），如果它是secondary地址，首先要确保同一个网络设备接口上存在一个跟其同类型的primary地址(网络号与子网号完全一致），因为，路由项的信息中的源地址全是primary的，secondary地址其实没有实际使用，它不会在路由表中产生路由项。然后，向local表添加一项目的地址是它本身的，类型为RTN_LOCAL的路由项；如果该ip地址结构中存在广播地址，并且不是受限广播地址(255.255.255.255)，那么向local表添加一个广播路由项；然后，对符合加入main表的条件进行判断，如果符合，除了加入main表，最后，如果不是D类地址，还要加入两个广播地址（其实，已经跟前面有重叠，很多情况下不会实际触发加入的动作，只要记住，一个ip地址项对应最多有两个广播地址就可以了）。

 

多路由表（multiple Routing Tables）

　　传统的路由算法是仅使用一张路由表的。但是在有些情形底下，我们是需要使用多路由表的。例如一个子网通过一个路由器与外界相连，路由器与外界有两条线路相连，其中一条的速度比较快，一条的速度比较慢。对于子网内的大多数用户来说对速度并没有特殊的要求，所以可以让他们用比较慢的路由；但是子网内有一些特殊的用户却是对速度的要求比较苛刻，所以他们需要使用速度比较快的路由。如果使用一张路由表上述要求是无法实现的，而如果根据源地址或其它参数，对不同的用户使用不同的路由表，这样就可以大大提高路由器的性能。

　　规则（rule）

　　规则是策略性的关键性的新的概念。我们可以用自然语言这样描述规则，例如我门可以指定这样的规则：

　　规则一：“所有来自192.16.152.24的IP包，使用路由表10， 本规则的优先级别是1500”

　　规则二：“所有的包，使用路由表253，本规则的优先级别是32767”

　　我们可以看到，规则包含3个要素：

　　什么样的包，将应用本规则（所谓的SELECTOR，可能是filter更能反映其作用）；

　　符合本规则的包将对其采取什么动作（ACTION），例如用那个表；

　　本规则的优先级别。优先级别越高的规则越先匹配（数值越小优先级别越高）。

　　策略性路由的配置方法

　　传统的linux下配置路由的工具是route，而实现策略性路由配置的工具是iproute2工具包。这个软件包是由Alexey Kuznetsov开发的，软件包所在的主要网址为ftp://ftp.inr.ac.ru/ip-routing/。
这里简单介绍策略性路由的配置方法，以便能更好理解第二部分的内容。详细的使用方法请参考Alexey Kuznetsov写的 ip-cfref文档。策略性路由的配置主要包括接口地址的配置、路由的配置、规则的配置。

　　接口地址的配置IP Addr

　　对于接口的配置可以用下面的命令进行：

Usage: ip addr [ add | del ] IFADDR dev STRING

　　例如：

router># ip addr add 192.168.0.1/24 broadcast 192.168.0.255 label eth0 dev eth0

　　上面表示，给接口eth0赋予地址192.168.0.1 掩码是255.255.255.0(24代表掩码中1的个数)，广播地址是192.168.0.255

　　路由的配置IP Route

　　Linux最多可以支持255张路由表，其中有3张表是内置的：

　　表255 本地路由表（Local table） 本地接口地址，广播地址，已及NAT地址都放在这个表。该路由表由系统自动维护，管理员不能直接修改。

　　表254 主路由表（Main table） 如果没有指明路由所属的表，所有的路由都默认都放在这个表里，一般来说，旧的路由工具（如route）所添加的路由都会加到这个表。一般是普通的路由。

　　表253 默认路由表 （Default table） 一般来说默认的路由都放在这张表，但是如果特别指明放的也可以是所有的网关路由。

　　表 0 保留

　　路由配置命令的格式如下：

 

Usage: ip route list SELECTOR ip route { change | del | add | append | replace | monitor } ROUTE

　　如果想查看路由表的内容，可以通过命令：

　　ip route list table table_number

　　对于路由的操作包括change、del、add 、append 、replace 、 monitor这些。例如添加路由可以用：

 

router># ip route add 0/0 via 192.168.0.4 table main router># ip route add 192.168.3.0/24 via 192.168.0.3 table 1

第一条命令是向主路由表（main table）即表254添加一条路由，路由的内容是设置192.168.0.4成为网关。

 

　　第二条命令代表向路由表1添加一条路由，子网192.168.3.0（子网掩码是255.255.255.0）的网关是192.168.0.3。

　　在多路由表的路由体系里，所有的路由的操作，例如网路由表添加路由，或者在路由表里寻找特定的路由，需要指明要操作的路由表，所有没有指明路由表，默认是对主路由表（表254）进行操作。而在单表体系里，路由的操作是不用指明路由表的。

===============================================================================

===============================================================================

来自：http://www.cnblogs.com/gunl/archive/2010/09/14/1826234.html