linux有很多子系统，例如IPv4子系统，进程管理子系统，pci子系统等，这次我们要面对的是路由选择子系统，久闻其大名却不曾亲近，让我们一起来看下。
Linux网络栈最重要的目标之一就是转发流量，对骨干网中的核心路由器尤其如此。IP栈层也被称为路由选择子系统负责转发数据包和维护转发数据库。
先介绍两个路由选择术语：默认网关和默认路由。在路由选择表中不与其他路由选择条目匹配的数据包都将转发到默认网关。在无类域间路由选择(CIDR)表示法时，默认路由用0.0.0.0/0表示。
设置默认网络命令如下：
#ip route add default 192.168.1.1
也可以使用route命令，建议是使用ip命令，因为该命令是基于netlink的，正在替换net-tools的工具包命令。
设备和主机发送包的路由通过路由表和路由缓存来实现的。
每个数据包，无论是接收还是发送，都需要在路由子系统中执行一次查找操作。根据路由子系统查找结果，决定是否应对数据包进行转发以及该从哪个接口发送出去。
1. 路由相关概念
一个局域网是一个广播域，属于同一个L2广播域的所有机器会受到相互发送的广播包。
IPv4地址划分如下：
另外IP规范中将一些特定范围内的地址规定为不可路由地址，如下：
路由的scope表示到目的网络的距离。当一个地址只用于主机自身的内部通信时，其scope为主机。当一个地址只在一个局域网内时候，scope为链路，例如子网的广播地址。当一个地址可以在任何地方使用时，其scope为全域，这是大多数地址的默认scope。路由代码和内核其他部分中广泛使用IP地址scope和路由scope.
定向广播的目的地是远端子网的广播地址。定向广播智能由到达目的子网路径上的最后一个网关识别。滥用定向广播可以产生拒绝服务攻击。
2. 查找路由
查找路由表通过函数fib_lookup来实现，将创建一个包含各种路由选择参数的fib_result对象。其中Forwarding Information Base (FIB)保存每个已知路由的细节。 在系统文件/proc/net/route中可以查看。函数如下：
static inline int fib_lookup(struct net *net, const struct flowi4 *flp, struct fib_result *res, unsigned int flags)
其中flowi4对象包含对IPv4路由选择查找过程重要的字段，例如目标地址、源地址、服务类型等。对于IPv6有类似对象flowi6。都定义在include/net/flow.h中。
最后查找成功后将返回一个dst对象(dst_entry)，结构体是dst_entry定义在文件include/net/dst.h中，最重要的input和output两个函数指针，影响包旅程。
struct dst_entry {
……
……
int (*input)(struct sk_buff *);
int (*output)(struct net *net, struct sock *sk, struct sk_buff *skb);
……
}
该对象将被嵌入到结构rtable中。缓存内的路由结构体rtable位于文件include/net/route.h
struct rtable {
struct dst_entry dst;
int rt_genid;
unsigned int rt_flags;//rtable对象的标志
__u16 rt_type;
__u8 rt_is_input;//一个标志，对于输入路由设置为１
__u8 rt_uses_gateway;//下一跳为网关，设置为１，为直连路由设置为０
int rt_iif;//入站接口ifindex
/* Info on neighbour */
__be32 rt_gateway;
/* Miscellaneous cached information */
u32 rt_mtu_locked:1,
rt_pmtu:31;//路径MTU
u32 rt_table_id;
struct list_head rt_uncached;
struct uncached_list *rt_uncached_list;
};
rtable表示一个路由选择条目，可与SKB相关联。dst_entry的重要成员是两个回调函数input和output.
先来看下fib_result结构体,位于文件include/net/ip_fib.h：
struct fib_result {
__be32 prefix;
unsigned char prefixlen; //前缀长度
unsigned char nh_sel;//下一跳数量，只有一个下一跳时，值为０.下一跳存储在fib_info对象。
unsigned char type;//对象类型，决定数据包处理方式，如RTN_UNICAST、RTN_LOCAL、RTN_BROADCAST、RTN_MULTICAST、RTN_UNREACHABLE.
unsigned char scope;
u32 tclassid;
struct fib_info *fi;//指向fib_info对象，存储了下一跳的引用fib_nh
struct fib_table *table;//指向用于查找的FIB表
struct hlist_head *fa_head;//指向一个fib_alias列表
};
其中type类型，定义在：
include/uapi/linux/rtnetlink.h文件中
enum {
RTN_UNSPEC,
RTN_UNICAST, /* Gateway or direct route */
RTN_LOCAL, /* Accept locally */
RTN_BROADCAST, /* Accept locally as broadcast,
send as broadcast */
RTN_ANYCAST, /* Accept locally as broadcast,
but send as unicast */
RTN_MULTICAST, /* Multicast route */
RTN_BLACKHOLE, /* Drop */
RTN_UNREACHABLE, /* Destination is unreachable */
RTN_PROHIBIT, /* Administratively prohibited */
RTN_THROW, /* Not in this table */
RTN_NAT, /* Translate this address */
RTN_XRESOLVE, /* Use external resolver */
__RTN_MAX
};
其中fib_info结构体，路由选择条目，存储了最重要的路由选择条目参数，如下：
struct fib_info {
struct hlist_node fib_hash;
struct hlist_node fib_lhash;
struct net *fib_net;//网络命名空间
int fib_treeref;
refcount_t fib_clntref;
unsigned int fib_flags;
unsigned char fib_dead;
unsigned char fib_protocol;//路由选择协议标识符
unsigned char fib_scope; //目标地址的范围，为地址和路由指定了范围。
unsigned char fib_type;//路由的类型。
__be32 fib_prefsrc;
u32 fib_tb_id;
u32 fib_priority;//优先级
struct dst_metrics *fib_metrics;
#define fib_mtu fib_metrics->metrics[RTAX_MTU-1]
#define fib_window fib_metrics->metrics[RTAX_WINDOW-1]
#define fib_rtt fib_metrics->metrics[RTAX_RTT-1]
#define fib_advmss fib_metrics->metrics[RTAX_ADVMSS-1]
int fib_nhs;//下一跳的数量，没有设置CONFIG_IP_ROUTE_MULTIPATH则不能超过1.
struct rcu_head rcu;
struct fib_nh fib_nh[0];
#define fib_dev fib_nh[0].nh_dev
};
其中fib_scope是目的地址的范围scope，定义于include/uapi/linux/rtnetlink.h：
enum rt_scope_t {
RT_SCOPE_UNIVERSE=0,
/* User defined values */
RT_SCOPE_SITE=200,
RT_SCOPE_LINK=253,
RT_SCOPE_HOST=254,
RT_SCOPE_NOWHERE=255
};
路由缓存查找是使用hash表方式，而在路由表中查找使用最长前缀匹配(LPM)算法。
3. 路由表
路由选择子系统的主数据结构是路由选择表，也叫转发信息库（Forwarding Information Base,FIB），由fib_table表示。路由表中的一条表项包含的信息随着代码优化和新特性引入已经增加了许多。
每个条目指定了前往特定子网所对应的下一跳。
struct fib_table {
struct hlist_node tb_hlist;
u32 tb_id;//路由选择表标识符，主表为254,本地表为255.
int tb_num_default;//包含的默认路由数
struct rcu_head rcu;
unsigned long *tb_data;
unsigned long __data[0]; //路由选择条目对象的占位符
};
路由的ID 如下，位于文件include/uapi/linux/rtnetlink.h。
enum rt_class_t {
RT_TABLE_UNSPEC=0,
/* User defined values */
RT_TABLE_COMPAT=252,
RT_TABLE_DEFAULT=253,
RT_TABLE_MAIN=254,
RT_TABLE_LOCAL=255,
RT_TABLE_MAX=0xFFFFFFFF
};
两个路由选择表：本地表和主表。主表的ID为254(RT_TABLE_MAIN),本地表的ID为255(RT_TABLE_LOCAL)。本地表包含针对本地地址的路由选择条目，只有内核才能在本地表中添加路由选择条目。
从本地地址中查找成功说明封包要提交给自己，
系统表用于所有其他路由，可以由系统管理员配置或路由协议动态插入。
当封包与表中的某条路由相匹配时，默认动作是从路由表得到该路由的转发信息，除此之外，还可以有动作：黑洞(Black hole)、不可到达(Unreachable)、禁止(Prohibit)、放弃(Throw).
4. 缓存
缓存路由选择查找结果是一种优化技术，可以用于改善路由选择子系统的性能。路由选择查找结果缓存在下一跳对象fib_nh中。是缓存寻找结果。
查找的结果缓存在下一跳对象fib_nh中。
在接收和传输路径中，缓存fib_result工作都由方法rt_cache_route完成。
不同于路由选择缓存，路由选择已在3.6中从协议栈删除了。
5. IPv4路由选择缓存
IPv4路由选择缓存容易遭受DoS攻击，因为它会为每个独特的流创建一个缓存条目，通过先个随机目的地发送数据包，可创建无数的路由选择缓存条目。
内核可以选择使用FIB TRIE/FIB散列。
FIB TRIE也叫LC-trie,是一种最长匹配前缀查找算法，在路由选择较大的情况下，其性能优于FIB散列。
6. 下一跳
当目的网络和本地主机不是直连时，需要通过其他的路由器来转发。选择下一跳的算法有：随机算法，加权随机算法，循环法，设备循环算法，
结构fib_nh表示下一跳。
位于文件include/net/ip_fib.h
struct fib_nh {
struct net_device *nh_dev; //外出网络设备
struct hlist_node nh_hash;
struct fib_info *nh_parent;
unsigned int nh_flags;
unsigned char nh_scope; //范围信息
#ifdef CONFIG_IP_ROUTE_MULTIPATH
int nh_weight;
atomic_t nh_upper_bound;
#endif
#ifdef CONFIG_IP_ROUTE_CLASSID
__u32 nh_tclassid;
#endif
int nh_oif;//外出接口索引
__be32 nh_gw;
__be32 nh_saddr;
int nh_saddr_genid;
struct rtable __rcu * __percpu *nh_pcpu_rth_output;
struct rtable __rcu *nh_rth_input;
struct fnhe_hash_bucket __rcu *nh_exceptions;
struct lwtunnel_state *nh_lwtstate;
};
其中nh_dev字段指出了将流量传输到下一跳锁使用的网络设备。
7. 策略路由选择
不使用策略路由选择(没有设置CONFIG_IP_MULTIPLE_TABLES时)，将创建两个路由选择表：本地表和主表。
系统可能创建多张独立的路由表来支持策略路由功能，但是无论路由表数量有多少，只使用一个路由缓存，会导致有些路由表比其他路由表缓存更多缓存项。
使用ip命令即可配置路由，也可配置策略。
8. FIB别名
有些情况下，会针对同一个目标地址或子网创建多个路由选择条目。
使用数据结构fib_alias结构体,相对来说更小，可降低内存量的消耗。
struct fib_alias {
struct hlist_node fa_list;
struct fib_info *fa_info;
u8 fa_tos;
u8 fa_type;
u8 fa_state;
u8 fa_slen;
u32 tb_id;
s16 fa_default;
struct rcu_head rcu;
};
9. ICMPv4重定向消息
有时候路由选择条目可能是次优的，在这种情况下，需要发送ICMPv4重定向消息。
有四种重定向消息代码：
/* Codes for REDIRECT. */
#define ICMP_REDIR_NET 0 /* Redirect Net */
#define ICMP_REDIR_HOST 1 /* Redirect Host */
#define ICMP_REDIR_NETTOS 2 /* Redirect Net for TOS */
#define ICMP_REDIR_HOSTTOS 3 /* Redirect Host for TOS */
在方法ip_forward中，通过调用方法ip_rt_send_redirect来发送ICMPv4重定向消息。
10. 路由协议守护进程
可以根据三种方式将路由插入到内核的路由表：
l  通过用户命令静态配置，如ip route,route
l  通过路由协议，如边界网管协议BGP,外部网管协议RGP,开放式最短路径有限OSPF协议等。协议的用户空间路由守护进程。
l  内核接收和处理的ICMP重定向消息
路由协议和内核之间的通信是双向的。
11. 路由相关内核选项
多播路由：CONFIG_IP_MROUTE=y
策略路由：CONFIG_IP_MULTIPLE_TABLES
多路径：CONFIG_IP_ROUTE_MULTIPATH
详细的路由监控：CONFIG_IP_ROUTE_VERBOSE
12. 路由子系统初始化
路由子系统初始化始于ip_rt_init函数，位于文件net/ipv4/route.c。该函数通过ip_init调用。
ip_rt_init会调用ip_fib_init来初始化fib表。因为路由子系统关心网络设备状态的变化和网络设备上IP配置的变化，所以在ip_fib_init中订阅了两个事件。
register_netdevice_notifier(&fib_netdev_notifier);
register_inetaddr_notifier(&fib_inetaddr_notifier);
13. 组播路由选择
发送组播流量意味着将数据包发送给多个接收方。
组播路由选择不像单播路由选择可以由内核单独处理，组播守护程序种类繁多，例如mrouted和pimd，分别基于距离矢量组播路由选择协议(DVMRP)和协议无关组播(PIM).组播地址位D类地址，其无类域间路由选择前缀为224.0.0.0/4,范围为224.0.0.0~239.255.255.255.
IGMP用于确定和管理组播组成员关系。是IPv4组播的有机组成部分，支持IPv4组播的结点必须实现它。在IPv6中组播管理由组播侦听者发现(Multicast Listener Discovery,MLD)协议处理。
组播路由选择表由结构mr_table表示，如下include/linux/mroute.h
struct mr_table {
struct list_head list;
possible_net_t net; //组播路由选择表相关联的网络命名空间
u32 id; //组播路由选择表ID
struct sock __rcu *mroute_sk;
struct timer_list ipmr_expire_timer;
struct list_head mfc_unres_queue;
struct vif_device vif_table[MAXVIFS];
struct rhltable mfc_hash;
struct list_head mfc_cache_list;
int maxvif;
atomic_t cache_resolve_queue_len;
bool mroute_do_assert;
bool mroute_do_pim;
int mroute_reg_vif_num;
};
MFC(Multicast Forwarding Cache)组播转发缓存是组播路由选择表中最重要的数据结构，实际上是一个缓存条目(mfc_cache对象)。数组名为mfc_cache_array，嵌入在组播路由选择表对象(mr_table)中。
将将机器配置为组播路由器，必须设置内核配置选项CONFIG_IP_MROUTE,还必须运行路由选择守护程序。
组播路由选择支持两种模式：直接组播；将组播封装在单播数据包中通过隧道传输。
组播数据包由方法ip_route_input_mc处理
组播中的TTL还有一层意义，路由器给每个接口都指定了阈值，仅当数据包的TTL大于接口的阈值时才转发。
14. 多路径路由选择
多路径路由选择，能够在路由中添加多个下一跳。
要支持多路径路由选择，必须设置CONFIG_IP_ROUTE_MULTIPATH.
Linux允许管理员通过weight关键字为每个下一跳分配一个权值，从而为选择算法提供了很大的灵活性。
15. 策略路由选择
使用策略路由选择时，系统管理员最多可定义255个路由选择表。
策略路由选择管理使用iproute2中的ip rule命令来完成。
策略路由选择的核心基础设施为模块fib_rules。网络栈中３中协议都会使用到该模块：IPv4,IPv6,DECnet。
