计算机网络【五】：路由选择协议

     我们知道网络层的关键作用在于路由寻址，这主要依靠路由选择协议来实现，而路由选择协议的核心在于利用路由算法生成路由表。在正式介绍今天的路由算法以前，我们先来了解一下关于路由的几个基本概念。
1. 理想的路由算法
     设计一个路由算法，如果要达到理想的作用，应该具备以下几个特点：
-1. 正确性：这是最基本的，即通过路由表中的记录保证数据分组一定可以最终到达目的主机；
-2. 简单：路由算法的计算不应使网络增加太大的开销；
-3. 自适应性：路由算法应当能够适应网络通信量和网络拓扑的变化，即具有稳健性；
-4. 稳定性：即在网络通信量和网络拓扑相对稳定的前提下，算法应当收敛于一个可接受的解；
-5. 公平性；
-6. 最佳的；
     一般根据路由算法是否具有自适应性，可以将其分为静态路由选择策略和动态路由选择策略。
2. 分层次的路由选择协议
     现实中的路由协议建立在分层管理实现的基础之上，这主要是基于AS（Autonomous System）的划分，所谓AS，经典定义是在单一的技术管理下的一组路由器，因为现实中出现了内部多种路由协议的AS，因此现在一般认为AS尽管内部有可能使用多种内部路由选择协议和度量，但是一个AS对其他AS表现出的是一个单一的和一致的路由选择策略。
     之所以选择将网络拓扑的路由分层管理，一个原因是因特网的规模很大，因此如果保存所有目的网络的地址，路由表会是一个相当大的规模；另一个原因则是有些单位基于保密性的需要不希望外界看到自己内部的网络拓扑情况。
     出现了AS概念之后，我们可以简单地理解为统一管理的一组路由器，内部可以使用相同或不同的路由选择协议，一般在AS内部使用的路由选择协议称之为内部网关协议IGP，比如RIP和OSPF；在AS间使用的路由选择协议则称之为外部网关协议EGP，比如BGP协议。关于AS、IGP、BGP的一个简单的示意图如下：

---

一、内部网关协议：RIP
     路由信息协议RIP(Routing Information Protocol)是内部网关协议IGP中最先得到广泛使用的协议，RIP是一个分布式的基于距离向量的路由选择协议，其最大优点就是简单。下面不再罗嗦地细致介绍，而是简要列出RIP协议的一些要点和关键概念。
1. 距离向量：RIP协议中每个路由器都要维护自己到每一个目的网络的距离记录，由于是一组距离，因此称之为距离向量，这将作为路由选择的度量；一般直连网段定义为1，每通过一个路由器距离+1，当然也可以定义直连网段为0，由于是统一的确定起始的基数，因此不会影响RIP协议的路由比较和选择。
2. RIP协议的三个要点：
-a. Who：与谁交换信息？
       RIP协议中的信息交换仅发生在相邻的两个路由器之间，不相邻的路由器不交换信息；
-b. What：交换什么信息？
       路由器交换的信息是当前本路由器知道的全部信息，即自己的路由表【我到本AS中所有网络的最短距离+到每个网路的NextHop】；
-c. When：什么时候交换信息？
     路由器按规定的时间间隔交换路由信息，比如每隔30秒，然后路由器根据收到的信息更新路由表；当网络拓扑发生变化时，路由器也会及时的告知相邻路由器；
3. RIP协议的路由向量算法
     RIP协议基于以下路由算法得出路由表，以路由器A为例：
-1. A自动获取直连网段的路由；
-2. 收到RIP更新包后，假设来自于相邻路由器B，则对其中的记录进行修改-
   *将所有路由记录项的距离+1；
   *将所有路由记录的下一跳改为B；
-3. 接下来针对修改过的B的路由表进行以下判断和处理：
   *若原来路由表中没有的目的网络记录，则添加该项路由；
   *若原来路由表中有下一跳为B的记录，直接更新；
   *若收到的项目中的距离小于原先路由表中的距离，则进行更新；
   *否则什么也不做；
-4. 若三分钟还没有收到相邻路由器的更新路由表，则把此相邻路由器记为不可达，即把距离记为16（最大15）；
-5. 返回；
     上面给出的距离向量算法的基础就是Bellman-Ford算i法，其要点是设B是A到C的最短路径上的一个节点，若把路径A-C拆为两段路径A-B和B-C，则每一段路径也分别是响应端点之间的最短路径。
     比如路由器6具有路由表1，相邻路由器4发来路由表2，则RIP的运行结果可以分析：


     首先我们对R4发来的路由表做一些处理，距离部分+1，然后下一跳均改为R4：

     然后我们分析比较原先的R6的路由表，发现第一条记录Net1的记录没有，因此直接添加：
     【Net1      4     R4】
     第二条记录Net2存在，且下一跳相同，因此用新的更新旧的：
     【Net2      5     R4】
     第三条记录的下一跳不同，比较距离，新的更短，因此替换掉原先的路由：
     【Net3      2     R4】
     此时我们得到的新的路由表就是：

4. RIP协议的缺点
     RIP实施简单，但是却有自身的不足，比如最大跳数为16，只能适用于小规模网路；路由度量仅仅是路由器跳数，比较单一，无法涵盖跳数多、延迟小的高速链路情况；最为重要的一点是当网络出现故障时，要经过较长的时间才能将此信息传送到所有的路由器。即：好消息传得快，而坏消息传得慢。
     比如当路由器R1到网1的链路出现了故障，R1无法到达网1了，那么R1就将到网1的距离改为了16；在R1向临接的路由器R2发送自己的新路由项前，先收到了R2的路由项【Net1   2   R1】，于是按照规则R1修改后成为了【Net1  3  R2】，并且与16比较后更新了自己的路由表；然后R1再次发送该项给R2，R2接受到以后发现是【Net1   4   R1】，于是直接替换掉了自己的【Net1   2   R1】；然后R2再向R1发送路由表....循环交替，直到Net1的距离成为了16，R2才明白原来无法到达Net1了：

     解决这样问题的方法可以是对于某些特定端口发来的路由信息，不再回送回去。总之，RIP协议最大的优点是实现简单、开销较小，但是对于较大的网络，还是应当使用OSPF协议。

---

二、内部路由协议：OSPF
     OSPF协议的意思是“开放最短路径优先”(Open Shortest Path First)，“开放”指的是OSPF协议不受某一家厂商控制，是公开发表的；“最短路径优先”则是指使用了Dijkstra算法的最短路径算法SPF。OSPF与RIP协议不同，主要使用分布式的链路状态协议，和RIP协议相比，OSPF具有自己的三个特点：
-1. Who
     采用洪泛法（Flooding）向本AS系统内的所有路由器发送信息，首先通过所有直连输出接口向所有相邻的路由器发送信息，每一个相邻的路由器又将此信息发往其相邻的所有路由器（不再重复回传给信源路由器），这样最终整个AS中所有的路由器都得到了这个信息的一个副本。RIP协议只是向自己相邻的路由器发送信息；
-2. What
     发送的信息就是本路由器相邻的所有路由器的链路状态，但这只是路由器所知道的部分信息。所谓链路状态就是指【我的邻居路由器有哪些？我到各个邻居路由器的链路度量】，OSPF用这个度量表示费用、距离、时延和带宽等，而这些都由具体的网络管理人员来规定，因此OSPF相对于RIP的距离向量来说更为灵活。RIP则发送的是【到所有网络的距离以及下一跳】；
-3. When
     只有当链路状态发生变化时路由器才向所有路由器泛洪发送此消息，而不想RIP那样，不管有无变化都发送路由信息。
     除此之外，OSPF相对于RIP来说具有以下不同：
-1. OSPF对于不同类型的业务可计算出不同的路由；
-2. OSPF中到达一个目的网络可以有多条相同代价的路径，那么可以同时分配通信量，做到负载平衡；
     经过各路由器之间频繁的交换链路状态信息，最终一个路由器中都能建立一个链路状态数据库，这里面实际上就是全网络的拓扑结构图。里面记录着【全网络中有哪些服务器、哪些服务器是直接相连的、链路代价是多少】，然后每一个路由器使用最小路径算法得出自己的路由表。RIP协议永远只知道相邻结点的情况，不晓得整体的网络拓扑结构。
     一般为了应用到很大的网络，OSPF又将一个AS分为了更小的范围，称为区域。每次划分都有一个主区域，用于连接各个子区域；每个区域中的路由器最好不要超过200个；区域之间相连的是区域边界路由器；主干区域内的路由器都称为主干路由器，且其中必须有一个用于和其他的AS相连，称之为自治系统边界路由器。

     OSPF的工作过程可以用下面的两个图来说明，第一个图用于说明OSPF初始化建立全网络的链路状态数据库：

     当链路状态发生变化时，就需要泛洪新的链路状态：