2. 路由
一、路由简介
域间路由与域内路由
路由研究信息沿着什么样的路径传输的问题。
让世界上的每一个节点都遵循同一个路由协议是很困难的，但是互联网是一个局域网连接起来的网络，域内路由协议（或内部网关协议，IGPs）可能不同（例如OSPF，开放最短路径优先，和 IS-IS，中间系统到中间系统），但是域间路由协议（或外部网关协议，EGPs）只有一种： BGP（边界网关协议）。
二、域内路由模型
全连接网络拓扑
首先域内路由模型可以抽象为图，假设任意两个节点之间都有链路连接，这种网络就叫全连接网络拓扑。
这种网络的优点是带宽大大提高，适合小型网络；缺点显而易见，后面再增添一个节点，就需要连接更多链路，扩展性极差。
单链路网络拓扑
一条链路连接所有机器，称之为单链路网络拓扑，如图所示：
跟多链路相反，单链路带宽较小，但是扩展性很好。
带路由器的网络拓扑
路由器能够转发节点之间的消息：
这样不仅带宽大，扩展性好，而且增强了健壮性：一条链路坏了，还可以走其他链路。
路由协议
路由协议不考虑终端主机，只考虑路由器之间的传输；一个终端主机会把数据全部丢给路由器，这叫终端主机的默认路由。
路由协议的数据包报头包含了源地址和目的地址：
接下来需要解决几个问题：
- 怎么给每个机器分配地址？
- 路由器拿到数据包，如何知道这个包应该往哪里发送？
- 互联网是不断变化的：可能突然出现新节点，可能某个节点失效。
- 链路可能会丢失数据包。
路由是分布式的
针对第三个问题，我们很难去做一个单一的巨大的数据库去存放路由信息，解决问题的办法是利用分布式：每一个路由器解决一部分路由问题，大家共同去解决全局问题。
三、路由状态
转发表
前面讲过路由问题：路由器拿到数据包，如何知道这个包应该往哪里发送？
也许我们可以转发给随机一个邻居路由器，但是可能无法到达目的地；也许还可以转发给所有邻居路由器，但是很浪费资源。
现实中的解决方法是通过路由状态。
数据包将要被转发到的下一个中间路由器被称为下一跳。对于每个可能的最终目的地，我们可以写下对应的下一跳以将数据包转发到更接近该目的地的位置。这个结果被称为转发表。
现实中的转发表不是像图中的 R1、R2 这样，而是物理层面上的端口号。这里简化了方便讲解。
转发表的特征是：如果转发表不变，那么所有同样目的地的数据包必然会发送到同一个下一跳，我们称为基于目的地的转发。
路由与转发
路由是路由器之间相互通信以确定如何填充其转发表的过程；转发是指接收数据包，在表中查找合适的下一跳，并将数据包发送到合适的邻居的过程。
转发是一个局部过程，当路由器转发数据包时，路由器不需要知道完整的网络拓扑；路由是一个全局过程，为了填写转发表，我们需要了解网络的全局拓扑结构。
路由状态有效性
路由状态由每个路由器的转发表组成，一个路由状态是否有效，要看通过了这个路由状态转发出去的数据包是否能够达到目的地（这是一个全局上的评估）；全局路由状态则由所有路由器中的所有转发表集合组成。因此路由状态是全局的。
全局路由状态是有效的，当且仅当对于任何目的地，数据包都不会被困在死胡同或循环中。
- 如果数据包到达路由器，但路由器不知道如何将数据包转发到其目的地，则数据包不会被转发，这种情况称为死胡同。
- 如果在节点循环中发送数据包，就会发生循环。
- 没有死胡同也没有循环是有效性的充分必要条件。
总的来说，只有满足没有死胡同和循环，路由状态才是有效的。
定向交付树
我们可以提出这样的问题：给定一个全局路由状态，我们如何检查它是否有效？
在生成的图中，每个节点将只有一个出射箭头。即使一个节点有多个输入箭头（路径），由于只有一个输出箭头，这些路径现在会汇聚成一条路径，这样就能确保数据包能够到达目的地。这样的路径被称为 定向交付树。这是一个以目的地为根的有向生成树。
可以发现这样的树不会有死胡同或者循环，因此是有效的。
最低成本路由
我们现在可以设计一个有效的路由状态，接下来我们要提升效率。
最短路径路由是一种常见的衡量路由是否良好的方法。在最短路径路由中，我们为每条链路分配一个数值成本，并寻找能够最小化成本的路由。换句话说，我们希望找到能让数据包沿着最低成本路径到达目的地的路由。（每条链路的成本取决于建设链路的费用、传播延迟、链路的物理距离等许多因素）
假设每条链路的成本一样都是 1，那么最短路径路由就会特化成最小化跳数。
静态路由
我们可以不用某种特定算法生成转发表，而是直接让网络管理员手动填充转发表。这种方式被称为静态路由。
未完待续...