Chapter 6 —— 网络层（2）

路由选择协议

· 路由：源站到目的站经过的一连串结点序列。

· 路由选择：也称为寻址/寻径，指的是寻找一条将分组从源站到目的站的传输路径的过程。

路由选择算法的基本概念

· 一个理想的路由选择算法应该是：

正确和完整的。
计算上简单。
适应计算量和拓扑变化，有自适应性。
具有稳定性、公平性和最佳性。

· 注意，这里的最佳指的是相对而言的最佳，路由选择是一个非常复杂的问题，它是网络中所有节点共同协调工作的结果，路由选择的环境往往是不断变化的，而这种变化往往无法预知。

· 路由算法分为：

静态路由算法：非自适应的，特点就是简单&开销小，缺点就是无法实时变化。
动态路由算法：自适应的，特点就是较好地自适应网络状态变化，缺点就是实现复杂&开销大。

· 分层次的路由选择协议：

互联网分布广，对象多，动态变化，如果某个路由表改变，就会引起上层全部的变化，有一种牵一发而动全身的感觉，这会造成网络带宽的占用，甚至会影响正常通信。因此，我们需要把路由表的变化限制在互联网中一定范围内。故提出分层次的路由选择协议。
自治系统（Autonomous System，AS）：一个自治系统就是一个互联网，其中所有的网络都属于一个行政单位，如一个公司/大学/部门等。一个ISP也是一个AS。然后AS之间再通过路由器来传递信息。
然后，针对自治系统的内部和外部，使用不同的协议进行路由选择：
- 内部网关协议（Interior Gateway Protocol，IGP）：自治系统内部使用，常用RIP或OSPF协议。
- 外部网关协议（External Gateway Protocol，EGP）：不同自治系统之间使用，最多用的是BGP-4。
自治系统内部路由选择称为域内路由选择（intra-domain routing），自治系统之间的路由选择称为域间路由选择（inter-domain routing）。
网关（Gateway）：互联网早期把路由器称为网关，到了现代，网关其实就是路由器，已经作为同义词。真正的网关应该在高层（传输层）。最早一个外部网关协议的名字是EGP，后来改进后被称为"边界网关协议（BGP）"，它们两个其实都是外部网关协议。

内部网关协议-路由信息协议RIP

· 路由信息协议（Routing Information Protocol，RIP）：最先得到广泛使用的IGP协议。

· 它是一种分布式的，基于距离向量的路由选择协议。

· RIP协议要求网络中的每一个路由器都要维护从它自己到其它每个目的网络的距离记录。

· "距离"的定义：

从路由器自身到一个直接连接的网络的距离定义为1。
从路由器自身到非直连的网络的距离定义为所经过的路由器数+1。
RIP协议中的"距离"也被称为跳数（Hop Count），因为每经过一个路由器，跳数都+1。

· RIP作为一个基于距离的协议，目的是寻找一个"最短距离"的路径，因此，RIP不能在两个网络之间同时使用多条路由。除此之外，RIP只允许一条路径最多包含15个路由器，即距离最大为16，若大于这个距离则相当于不可达。因此RIP只适用于小型互联网。

· RIP协议的三个要点：

仅和相邻路由器交换信息。我们定义连接在同一个网络上的2个路由器为相邻，如上图中的R1和R2都连接在net2上，故它们相邻。
路由器交换的是本路由器知道的全部信息，即自己的路由表。
路由器按固定的时间间隔交换路由信息，如每30秒交换一次；除此之外，当网络拓扑发生变化的时候，也会交换信息。

· 路由器之间交换信息与路由表更新

· RIP协议建立路由表的过程：

整个建立过程如下图所示：
首先，网络初始化的时候，是那个路由器都只有自己所在的网络的路由信息。
然后，R2由于与R1和R3都相邻，会首先更新自己的路由表，获取到前往10和40网络的路由。
然后，R1和R2相邻，R2会共享信息给R1，因此，R1得到了前往30和40网络的路由。
最后，R3和R2相邻，同样的R2共享信息给R3，R3得到了前往10和20网络的路由。
至此，3台路由器的路由表更新完毕。

· 距离向量算法：

首先我们来看伪代码：

rip = "收到来自地址X的RIP报文"
router_map = [] # 当前路由器的路由表

# 修改rip中所有下一跳的地址为X
for route in rip:
    route.next_hop = X

# 所有距离字段+1
for route in rip:
    route.distance += 1

# 遍历修改后的rip中的每一条路由
for route in rip:
    # 如果当前项目不在路由表中
    if route not in router_map:
        # 将当前项目直接添加到路由表中
        router_map.append(route)
    # 当前项目在路由表中
    else:
        # 如果当前项目的下一跳与路由表中对应项目的下一跳相同，则直接替换路由
        if route.next_hop == router_map[route.destination].next_hop:
            router_map[route.destination] = route
        # 若下一跳不相同
        else:
            # 如果当前项目中的距离小于路由表中对应项目的距离，则更新
            if route.distance < router_map[route.destination].distance:
                router_map[route.destination] = route
            # 否则，就什么也不做，因为距离变大了

2. 对应的算法流程图如下：

3. 一个简单的例子如下：

首先可以看到，表B是R4发来的原始路由表，然后在表C中先把所有的下一跳改为R4，然后再把所有的距离+1。

然后，用修改后的RIP报文即表C与路由器R6的原始路由表表A进行比较：

- Net1不在路由表中，直接添加。

- Net2在路由表中，且下一跳与路由表中值相同，都为R4，则直接替换。

- Net3在路由表中，但是下一跳不同，比较距离，RIP中的距离更小，于是替换该路由。

· RIP（Version 2）的报文格式如下：

- 可以看到，最终被封装成了IP数据报，其中RIP报文被封装为UDP数据报。

- RIP报文中，首部占4字节，包含了命令和版本信息。

- 路由部分就是路由表内容，其中可以装最多25条路由项目的信息，若超过25条则要使用多个RIP报文发送。

· RIP协议的一个特点：好消息传的快，坏消息传的慢。

好消息传的快：接入一个新网络/新主机，更新路由表速度很快。
坏消息传的慢：某一个网络出现故障时，要经过比较长的时间（数分钟），才能将该信息传递给所有路由器。

· 总的来说，RIP协议：

优点：实现简单，开销小。
缺点：
- 限制了网络规模为15。
- 路由器间交换的信息为完整路由表，随着网络规模增大，开销越来越大。
- "坏消息传的慢"使得收敛过程时间变长。

内部网关协议-OSPF协议

· OSPF协议的基本特点：

开放最短路径优先（Open Shortest Path First，OSPF）的"开放"表示公开发表，不受任何一个厂商控制；"最短路径优先"表示使用了迪杰斯特拉Dijkstra的最短路径算法。
它采用的是分布式的链路状态协议（Link State Protocol）。
注意，OSPF只是一个协议的名字，它并不表示其它路由选择协议不是"最短路径优先"的。

· 链路状态（Link State）：指的是当前路由器和哪些网络或路由器相邻，以及将数据发往这些网络或路由器所需要的费用或度量（费用/距离/时延/带宽）。

· OSPF的三个要点：