Linux内核工程导论——网络：路由：路由原理

Linux内核工程导论——网络：路由：路由原理

总览

路由表

IP层通过路由将数据包送达该送达的目的地址，这就要求在整个网络中建立正确的路由表。路由表的内容是记录要到达哪里下一跳需要发到哪里（可以是端口可以是ip），如此整个网络在单个节点只知道自己局部转发信息的情况下就能正确的转发。

路由协议

路由表的原理简单，难的是维护。如何在全网络形成这样一张大表，如果在网络变动的时候全网的表快速收敛聚合？如果全部是手动的固然可以实现，但是成本太高。这就需要自动化的协议。这种形成并更新路由表的协议叫做路由协议。

内部网关协议和外部网关协议

世界如果是一个集权国家，就可以统一规划一个网络（即使如此，可能也会有试验网络）。但是世界各个组织和国家的博弈过程，各组织内部的网络协议不可能统一，但是因特网又希望可以在世界各国自由的通信。唯一的解决方法就是各个组织之间的交换路由表的方式尽可能的统一，但是各个组织内部怎样组织和更新自己的路由表，各组织是自由的。这就是外部网关协议和内部网关协议。

常见的路由协议

常见的内部网关协议有RIP、RIPv2，OSPF，IS-IS。常见的外部网关协议有EGP、BGP。其中内部网关协议目前最常用的是OSPFh和IS-IS，事实上这两个协议几乎是一样的。RIP比较老，用的算法问题比较多，逐渐退出使用。BGP是EGP的升级版，现在一般使用BGP。

分布式分层网络

网络是集中式和分布式的合体，集中式的网络最好管理，但是现实的网络大部分是分布式的。即使是一个组织内部，也被刻意的实现为了分层的分布式的。同一层次之间的节点的路由表靠同层通信形成，而不是靠上层下发（当然使用上层网络向自治区外的路由仍然需要上层网络的参与）。如此设计的好处是自动化。集中式的需要顶层管理，而分布式的靠互相协商。
但是像中国这么大的国家，全部路由节点同一层次分布式，必然导致信息爆炸。现实世界使用聚合的思想（也就是分层的思想），将一个区域的节点聚合为一个节点，如此每个层级都有较少的节点。每个节点的下部就又构成了一个自治域。

分布式网络路由表可行更新策略与成本

目的是更新同层次和上下层次路由器的路由表，最直观的方案是各个节点都同层广播自己的路由表，再仔细想还有更新部分条目的做法，再深入路由表结构，还有发布节点状态或者链路状态，相关节点自己去计算路由表的做法。无论协议如何设计，都是要解决以下问题：
- 传输问题：
- 传输内容是什么
- 传输给谁
- 是周期性传输还是触发性传输
- 传输想要更新的内容全网更新要多久（收敛、聚合速度）
- 描述问题
- 对不同网络的描述方式是怎样的
- 如何评价一条链路与另一条可行链路的质量孰好孰坏
- 如何定义与划分同一个层级的网络节点
- 如何与不同层次的节点交互信息
- 认证
- 如何确定发布路由信息的节点是可信的

这里的路由表都是指路由器上的，而不是普通的主机。普通主机的路由工作都是设置一个网关，将所有上网的数据包直接发送给网关即可，无需关心路由问题。

传输问题

我们的目的是更新网络中的路由表，传输内容就有：路由表、路由条目、链路状态。前两个很直观，链路状态是指一个路由器的所有端口连接的对端路由器的状态（或者是这个端口自己的状态），比如掉线了，改网段了，连到其他的路由器了等事件。
传输路由表是RIP采用的方法，并且采用周期性的全网广播（RIPv2引进了多播），当网络比较大时，对应的路由表也就比较大，如此传输无论对带宽还是收敛速度来说都是几乎不可接受的。收敛太慢，网络的波动性就大，有的时候第一个路由表还没收到，第二个同一个节点的更新已经来了。对于变化比较多的大型网络拓扑来说几乎无法使用。
所以OSPF和IS-IS采用传输链路状态的方法。我们知道路由表中记录的是下一跳，并不是链路状态，但是每个路由器可以根据其他路由器的链路状态动态计算出下一跳（例如B到10.0.0.0/24网段的链路断掉了，A就可以计算出要到10.0.0.0/24网段的吓一跳不能是B了，要看看其他路由器有没有链接到这个网段的链路）。

网络变化带来的传输量

RIP采用距离矢量，OSPF采用的是链路状态。距离矢量路由协议，更新的是“路由条目”，一条重要的链路如果发生变化，意味着需通告多条涉及到的路由条目。链路状态路由协议，更新的是“拓扑”，每台路由器上都有完全相同的拓扑，他们各自分别进行SPF算法，计算出路由条目。一条重要链路的变化，不必再发送所有被波及的路由条目，只需发送一条链路通告，告知其它路由器本链路发生故障即可。其它路由器会根据链路状态，改变自已的拓扑数据库，重新计算路由条目。

收敛速度

从一个节点变化到全网络都改变路由表的速度。RIP的模式自然很慢，OSPF和IS-IS等先进算法目前都对链路方式进行了大量的研发。例如在SPF的基础上发展出了部分更新的ISPF。针对不是掉线，而只是路由信息发生变化的情况（拓扑没变），发展了PRC（Partial Route Calculate，部分路由计算算法）。针对扩散和计算是否可以重叠以加速响应的问题，发展出了LSP快速扩散算法。
当然，这远不是这两个协议发展的终点。比如通过链路质量的变化做预测的预测方法也可以继续向协议整合。

描述问题

对网络的描述

对于传统的IP划分，有A、B、C等网段。但这只是约定划分的，实际的使用中很多网段都是非标准的VLSM，RIP不认识Variable Length Subnet Masks (VLSM)，通过VLSM可以有效指定一大片网络，可以非常灵活的合并以减少网络条目。RIPv2引入了这个特性。但是OSPF和IS-IS原生的支持。
RIP将整个层次的网络缺点为一个一个点，到一个点是一跳，最多支持15跳。这样对于大于15跳到达的网络对于RIP来说是不可达的。并且，如此的跳，一定得注意避免环的问题。OSPF则是链路概念，没有跳数限制，通过收到全网每个节点的每个端口的状态，在本机画出一张网络图，进而计算出网络拓扑。如此的信息持有量是不会出现环路的。
这里的OSPF不会出现环路是针对自治区内部的，自治区之间是可以产生环路的，可以通过OSPF骨干网解决。

同一层次节点划分和与其他层次节点的通信

RIP是完全扁平的，同一层次的所有节点都是在一个广播域。ospf和IS-IS可以将一个层次的节点进一步划分和聚合。如此如果在一个层次中如果有很多节点，RIP也无法适应。
OSPF也是会洪泛广播链路变化，如果网络太大，这也是个问题。所以OSPF加入了自治区域（AS）的概念。洪泛只发生在自治区域内，所以一个AS内部所有节点的拓扑数据库是相同的。连接AS的路由器叫做ABR（Area Border Router），也就是说一台路由器可以同时在两个AS，只要是不同的端口就好。任何一个AS中的任何一台路由器都可以作为ASBR与外部网络相连（这个外部网络可以不是OSPF）。

根据路径质量选择下一跳

RIP选择下一跳完全根据跳数，哪个跳数少选择哪个。而OSPF的通知链路状态的时候会同时通知链路质量。每两个节点之间的链路都有权重值来表示质量。如此就很实际的选择链路质量好的下一跳。但是这里也还是有问题的，几个断点两两间的链路都好，也并不一定意味着整条链路就是最好的（通常情况是），所以很多大公司都会在应用层次再检测一遍，在一个公司的各个机房内重新做路由。可以说，运营商通过OSPF提供的路由可以满足大部分使用，但是对性能的极致追求还是需要自己优化。
OSPF（IS-IS）采用dijkstra算法来找最短路径，由于每个节点都有完整的整个自治区内的节点链路状态，所以dijkstra降本节点放在树的根部，然后生成树。两个节点之间的连接完全是基于链路速度，所以这显然不科学，但是又足够科学可以使用。当然，你可以强制的手动指定一个节点到另一个节点的链路质量，这是一个优化网络该有的做法。
OSPF有一个对等路由的概念，到一个节点经过几个开销相等的节点时，OSPF会传输到任意一个，这就是负载均衡。所以支持OSPF的路由器天生的支持简单的负载均衡。

OSPF数据包类型

外部网关协议

名词解释

1、 SPF是目前被各种基于链路状态的路由协议，它采用Dijkstra算法计算最短路径。其基本思路是根据LSDB里描述的拓扑信息构建SPT（Shortest Path Tree，最短路径生成树），然后将LSDB里描述的路由信息作为树上的叶子生成最终路由
2、 ISPF（Incremental SPF，增强SPF算法），主要用于部分拓扑发生变化的情况，在这种情况下不需要重新计算整个网络拓扑，而只是将变化了的少量拓扑进行修正，从而大大节约路由计算时间。
3、 PRC（Partial Route Calculate，部分路由计算算法），主要用于只是路由信息发生变化的情况，在这种情况下不需要重新计算网络拓扑，只是根据原有的拓扑生成新的路由信息即可，从而大大节约路由计算时间。
4、 LSP快速扩散。为了加快整个网络的收敛速度，当收到其它路由器发来的LSP时，如果此LSP比自己LSDB中的要新，按原来RFC协议的实现，则是用一个定时器，定时将LSDB内的LSP扩散出去，所以LSDB的同步会比较缓慢。LSP快速扩散特性改进了这种方式，配置此特性的路由器收到一个或多个比较新的LSP时，在路由计算之前，先将小于指定数目的LSP扩散出去，加快LSDB的同步过程。这种方式在很大程度上可以提高整个网络的收敛速度
5、 ISIS智能定时器。改进了路由算法后，如果触发路由计算的间隔较长，同样会影响网路的收敛速度。使用毫秒级定时器可以缩短这个间隔时间，但如果网络变化比较频繁，又会造成过度占用CPU资源。SPF智能定时器既可以对少量的外界突发事件进行快速响应，又可以避免过度的占用CPU。
通常情况下，一个正常运行的IS-IS网络是稳定的，发生大量的网络变动的几率很小，IS-IS路由器不会频繁的进行路由计算，所以第一次触发的时间可以设置的非常短（毫秒级）。如果拓扑变化比较频繁，智能定时器会随着计算次数的增加，间隔时间也会逐渐延长，避免占用大量的CPU资源。
与SPF智能定时器类似的还有LSP生成智能定时器。在IS-IS协议中，当LSP生成定时器到期时，系统会根据当前拓扑重新生成一个自己的LSP。原有的实现机制是采用间隔时间定长的定时器，不能同时满足快速收敛和低CPU占用率的需要。为此将LSP生成定时器也设计成智能定时器，使其可以对于突发事件（如接口Up/Down）快速响应，加快网络的收敛速度。同时，当网络变化频繁时，智能定时器的间隔时间会自动延长，避免过度占用CPU资源