山西长治供电公司Linux路由表的结构与算法分析20160420

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

2、nux使用了多个路由表而不就 是一个，即使不使用策略路由，Linux也使用了两个路由 表，一个用于上传给本地上层协议,另一个则用于转发。Li nux使用多个路由表而不就是一个，使不同策略得路由存放 在不同得表中，有效地被免了查找 庞大得路由表，在一定情 度上提高了查找了效率。必路由表本身不就是由一个结构表示，而就是由多个结构组合而成。路由表可以说就是一 个分层得结构组合。在第一层,它先将所有得路由根据子网 掩码（netmask）得长度（03 2 ）分成3 3个部分（str u c t fn_zon e ）,然后在同一子网掩码（同一层）中，再 根据子网得不同(如10、1、1、0/2 4与1 0、

3、1、2、0 /24), 划分为第二层(str u ct fi b _node),在同一子网中，有 可能由于T0S等属性得不同而使用不同得路由，这就就是第 三层(str u ct f i b_ a lia s ),第三层结构表示一个路由表 项，而每个路由表项又包括一个相应得参数，如协议，下一 跳路由地址等等，这就就是第四层(st r uct fib_i n f o) 分层得好处就是显而易见得，它使路由表得更加优化，逻辑 上也更加清淅，并且使数据可以共享(如str u ct fib_info), 从而减少了数据得冗余。str u ct fib_ table * fib_ t ables R T_T

4、ABLE_M AX+1 ；/ RT_TABL EJIAX 为 2 55图1为一个路由表得总体结构。自上而下由左向右瞧, 它首先为一个f ib_t a b 1 e结构指针得数组，它被定义为：str u ct fib_ t able au n s i g ne d chartb_id； 4u ns i g ned tb_st amp;int(* t b _lo o kup) (stru c t fi b _table *tb, cons t stru c t fl o wi *flp,st rue t fib_:result res)；ai nt(*tb_in s e rt)(s t ruct f

5、 i b t able *t able, st rue t r t mvo i d(*tb_selec t_defauIt) (stm c t f i b_ta b 1 e * t able,const s tr u c t f 1 o w i *flp, s t ru c tf ib_resul t *re s );unsign e d ch a r tb_data 0；胡；每个f i b _t a ble结构在内核中表示一个路由表：struct fib table工乏W5JS1IUstruct table*struct fib Liable*.strut tfib_ table*bb bf

6、l f flJd.stamp Jtwkupstruct fib jable*lefault routestb.select defaultb_伽struct fn_zone*fz_nal v- fzjwsh fzdivisorTtroctfnzonesuudfn.zone*st(ucl fn_zone*struct fn_z:one,/32 structfnzone* struct fn_zone*fn-zone-list - J i tzhash fzdivisor struct fn zone图1 （引自1）亠这个结构中包括这个表得ID,以及主要得一些用于操作路 由表得函数指针，这里我们只

7、关心最后一域一 一t b_d at a 0,这就是一个零长得数组，它在内核中也较为常见，它 表示s t ruct fn hash struct fn zon e * fn zon e s 3 3 ；stru c t fn_z o ne * fn_zo n e_ 1 i s t ； J ；指向这个结构得末尾。由图1可以瞧到，这个结构得末尾接 着便就是一个S t ru c t fn_ha s h结构，这个结构就是随 fi b_tabl e 结构一起分配得，所以 fib_table-） tb_data就就是f n_hashostruct fn _zone s tr u c tf n_ z one*

8、fz_ne x t；/* Nextno t em p tyzone */astru c thl i st_head*fz_hash；/* Hash table point erintf z_ne n t ;/* Num ber of entrientd ivis o r；/ * Has h divi s o* /au32s k; / *(f z)fz_hashma(fz_d i v isor 一 1)/4t d ef i n e FZ_HASHXIASK(f z ) fz_ha s hm a sk)1ntr ; /* Zone orderu32fz_orde*/#def i neFZjfASK

9、 (fz);fz_m a sk;(f z ) fz_m a sk)这个fn_ z one域就就是我们上面提前得结构，用于 将路由根据子网掩码得长度分开成33个部分，其中f n_z on e s 0用于默认网关。而f n_zone_lis t域就就是将正 在使用得f n_zone链成一个链表接着再深入到st r uct f n_zo n e结构中:这个结构中有两个域比较重要，一个为 fz_h a sh域,它指向一个HASH表得表头，这个HASH得长度 就是fz_d ivisoro并且这个HASH表得长度就是可变得，当表长达到一个限定值时，将重建这个H ASH表,被免出现H ASH冲突表过长造成查

10、找效率降低。为了提高查找得效率，内核使用了大量得HASH表，而 路由表就就是一个例子在图1中可以瞧到，等长子网掩码 得路由存放在同一个fnzo n e中，而根据到不同子网(f i b_node)得路由键值(f n_key),将它HASH到相应得 链表中。struct fi b_n o d e as truct h 1 ist_nodef n ha s h； as t ru c t list h eadfn_alias 严u 32fn_ k e y;；这个键值其实就就是这个子网值了(如10。1 o K 0 / 24,则子网值为10、1、1),得到这个键值通过n = fnh a sh ()函数H

11、ASH之后就就是这个子网对应得HA SH值，然后就可以插入到相应得fz_h ash n链表中了。冲突得fib_node由fn_hash域相链，而f n_al i as则就是 指向到达这个子网得路由了.s t ruct fi b _a 1 ias fa1 ist;struct list_he a dstr uct rcu headrcu；金t r u c t f ib_ info* fa_info；au8f a _tos；u8fa_type ；au 8fa_scope;u8fa_sta t e ；a；当到达这个子网得路由由于TO S等属性得不同可存在 着多个路由时，它们就通过fib_al i a

12、 s中fa_lis t域 将这些路由表项链成一个链表。这个结构中得另一个域 fa_info指向一个fib_ info结构，这个才就是存放真正重 要路由信息得结构。s t ructfi b _i n f os truct hli s t_nodefib_h ash;st r u cthli s t_nodefib_lh a sh Jintf ib_dead；Aunsig n e df ib_f1 a gs；intf ib_protoc ou 32fib_pref s rc；4u3 2f i b_p r iority；i n tf ib n hf ib n hf i b _nh O、nh_ dev

13、struc t f i b_n h0；# def i ne f i b_devJ ;这个结构里面就是一个用于路由得标志与属性，其中最重要得一个域就是fibhO,在这里，我们再次瞧到了 零长数组得应用，它就是通过零长来实现变长结构得功能 得。因为，我们需要一个定长得f ib_info结构，但就是在 这个结构末尾，我们需要得f ib_nh结构得个数就是不确定 得，它在运行时确定。这样，我们就可以通过这种结构组成, 在运行时为fib_i n f 0分配空间得时候，同时在其末尾 分 配所需得若干个f ib_nh结构数组，并且这个结构数组可 以通过f i b _info- f i b _n h n来访问

14、，在完成fi b _in f o得分配后 将f i b_nhs域置为这个数组得长度。另一方面，f i b_ i nfo也就是HASH表得一个应用，结 构中存在着两个域，分别就是f i b_hash与f i b_lhas h,它们都用于HA SH链表。这个结构在完成分配后，将被 用fi b _ h a s h域链入f ib_info_ha s h表中，如果这个 路由存在 首选源地址，这个f i binfo将同时被用fib _1 hash 链入 f i b_info_la d d rha s h 表中.这样，就可以根据不同目得实现快速查找了。亠Struct f ib_nh也就是一个重要得结构。它存

15、放着下 一跳路由得地址(nh_gw)。刚刚已经提到，一个路由 (fib_ali a s)可能有多个f ib_nh结构，它表示这个路由 有多个下一跳地址，即它就是多路径(multipath)得。下一 跳地址得选择也有多种算法，这些算法都就是基于nh_、ve i ght, n h _power 域得。nh_hash 域则就是用 丁-将 nh_ h a sh链入HASH表得。stru c t fib_n h 必st r uct n et_d e v i ce* n h _dev；Astruct h 1ist_nodenh_h a sh;s tr u c tfib_ i nfo* nh_p a ren

16、 t ；uns i g n ednh_ f 1 ags；u nsignedc harn h_ s c o p e;4Jif d ef CONFIG_I P_ R OU T E_MULTI P ATHin tnh_weight；intn h_power；曲e ndifA# ifde f C 0NFIG_N E T_CLS_ROUTE_u32n h_tclas s i d;4ten didi ntnh oif；u32二、路由得查找路由得查找速度直接影响着路由及整个网络栈得性能。 路由得查找当然首先发生在路由缓存中，当在缓存中查找失 败时，它再转去路由表中查找,这就是本文所关注得地方。A 上一节已经

17、详细地描述了路由表得组成。当一个主要得IP 层将要发送或接收到一个IP数据包时，它就要调用路由子 系统完成路由得查找工作。路由表查找就就是根据给定得参 数，在某一个路由表中找到合适得下一跳路由得地址.上面已提到过，当一个主机不支持策略路由时，它只使 用了两个路由表，一个就是ipfib_l o cal_ t abl e ,用 于本地，另一个就是ip_ f ib_mai n_ta b le,用于接发。只 有在查找i P _fi b _ 1 o c al_table表时没有找到匹配得 路由（不就是发给本地得）它才会去查找i P _fib_m8in_t able.当一个主机支持策略路由时，它就有可能存

18、在着多 个路由表，因而路由表得选择也就就是查找得一部分。路由 表得选择就是由策略来确定得，而策略则就是由应用（用户） 来指定得，如能过ip rule命令：ip rul e add from 10. 1. 1、0/24 tabl e T R1 i p rule add i f f ethO tabl e RT2如上，第一条命令创建了基于源地址路由得一条策略，这个策略使用了 RT1这个路由表，第二条命令创建了基于数据包入口得一个策略，这个策略使用了 RT2这个路由表当被指定得路由表不存在时，相应得路由表将被创第二步就就是遍历这个路由表得fn_zone,遍历就是从 最长前缀(子网掩码最长)得fn_z

19、 one开始得，直到找到或 出错为止。因为最长前缀才就是最匹配得。假设有如下一个 路由表：dstn e x t hopdevA10. Io0、0/1610、 1、 1、1eth 01 0 1、0、0/241 0 、 1、 0、1ethl上 它会先找到第二条路由，然后选择10。1 o 0、1作为 下一跳地址。但就是，如果由第二步定位到得子网(fib_ node)有多个路由，如下:next h10. 1。0、0/ 241 0、1、0、1e thl1 0、1、0、0/2 41 0 、 1、 0、2ethlopdev到达同一个子网有两个可选得路由，仅凭目得子网无法 确定，这时，它就需要更多得信息来 确

20、定路由得选择了， 这就就是用于查找路由得键值(struc t f 1 ow i )还包括 其它信息(如T OS)得原因这样，它才能定位到对应一个 路由得一个fibalias实例。而它指向得fi b info就就 是路由所需得信息了。亠最后一步，如果内核被编译成支持多路径(mul tip a th)路由，则fibinfo中有多个 fin_ n h,这样，它还要从这个fibh数组中选出最合适得 一个f ib_n h,作为下一跳路由。三、路由得插入与删除路由表得插入与删除可以瞧瞧就是路由查找得一个 应用，插入与删除得过程本身也包含一个查找得过程，这两 个操作都需要检查被插入或被删除得路由表项就是否存

21、在, 插入一个已经存在得路由表项要做特殊得处理，而删除一个不存在得路由表项当然会岀错。下面瞧一个路由表插入得例 子：ip r oute ad d 10.0。1 0/24 n ex t hop via 10. 0- 11 wei ght 1nexthop via 10. 0. 1、2 we i ghttable RT3这个命令在内核中建立一条新得路由。它首先查找路 由表RT3中得子网掩码长为24得fn_zone,如果找不到， 则创建一个f n_zon e .接着，继续查找子网为1 0. 0。1得fib node,同样，如果不存在，创建一个fi b _n o deo然后 它会在新建一个fib_in

22、 f o结构,这个结构包含2个fib_nh 结构得数组（因为有两个n e x th o p）,并根据用户空间传递 过来得信息初始化这个结构，最后内核再创建一个f i b_ali a s结构（如果先前已经存在，则岀错），并用fib_nh 来创始化相应得域，最后将自己链入fib_node得链中，这样 就完成了路由得插入操作。路由得删除操作就是插入操作得逆过程，它包含一系列 得查找与内存得释放操作，过程比较简单，这里就不再赘述 了。2四、策略路由得一个简单应用A L inux系统在策 略路由开启得时候将使用多个路由表，它不同于其它某些系 统，在所有情况下都只使用 单个路由表虽然使用单个路 由表也可以

23、实现策略路由，但就是如本文之前所提到得，使 用多个路由表可以得到更好得性能，特别在一个大型得路由 系统中。下面只通 过简单得情况说明Linux下策略路由得 应用。4 如图2,有如下一个应用需求，其中网关服务器 上有三个网络接口。接口 1得IP为172、16、10 0、1,子 网掩码为 2 55、2 55、2 5 5、0,网关 g w 1 为 a、b、c、d, 17 2、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这个更快得网