文章目录

• 层次路由
• • 动态路由算法
  • 距离向量算法(RIP)
  • • RIP 协议将“距离”定义
    • RIP 协议的特点是：
    • RIP路由表格式
    • 直连网络&直接交付@间接交付
    • RIP算法
    • • 特点
    • 实例
    • 例
  • OSPF协议的基本特点
  • OSPF与 RIP主要区别:
  • 三种路由协议的比较

层次路由

• 当网络规模扩大时，路由器的路由表成比例地增大.
• 这不仅会消耗越来越多的路由器缓冲区空间，而且需要用更多CPU时间来扫描路由表，占用更多的带宽来交换路由状态信息.
• 因此路由选择必须按照层次的方式进行.
• 因特网将整个互联网划分为许多较小的自治系统（注意一个自治系统中包含很多局域网），
  • 每个自治系统有权自主地决定本系统内应采用何种路由选择协议.
  • 如果两个自治系统需要通信，那么就需要一种在两个自治系统之间的协议来屏蔽这些差异.
• 据此，因特网把路由选择协议划分为两大类：
  • 1)一个自治系统内部所使用的路由选择协议称为内部网关协议(IGP),也称域内路由选择，具体的协议有RIP和OSPF等.
  • 2)自治系统之间所使用的路由选择协议称为外部网关协议(EGP),也称域间路由选择，
    • 用在不同自治系统的路由器之间交换路由信息，并负责为分组在不同自治系统之间选择最优的路径.具体的协议有BGP.
    • 使用层次路由时，OSPF将一个自治系统再划分为若干区域(Area),每个路由器都知道在本区域内如何把分组路由到目的地的细节，但不用知道其他区域的内部结构.
    • 采用分层次划分区域的方法虽然会使交换信息的种类增多，也会使OSPF协议更加复杂;但这样做却能使每个区域内部交换路由信息的通信量大大减小，因而使OSP℉协议能够用于规模很大的自治系统中.

动态路由算法

• 动态路由算法以目的网络为导向,借助下一跳路由来实现相关算法.
• 主要包括RIP和OSPF

距离向量算法(RIP)

• Routing Information Protocol - Wikipedia
• 属于应用层协议🎈
  • 虽然在网络从介绍它,但从它的报文格式看,是应用层协议
  • 通过传输层的UDP协议来封装RIP报文
• RIP (Routing Information Protocol)是内部网关协议 IGP 中最先得到广泛使用的协议[RFC 1058]，它的中文名称叫做路由信息协议，但很少被使用。
• RIP 是一种分布式的基于距离向量的路由选择协议，是互联网的标准协议，其最大优点就是简单。
• RIP 协议要求网络中的每一个路由器都要维护从它自己到其他每一个目的网络的距离记录（因此，这是一组距离，即“距离向量”）。

RIP 协议将“距离”定义

• 从一路由器到直接连接的网络的距离定义为 1。

• 从一路由器到非直接连接的网络的距离定义为所经过的路由器数加 1。

• “加 1”是因为到达目的网络后就进行直接交付，而到直接连接的网络的距离已经定义为 1

• 需要注意的是，到直接连接的网络的距离也可定义为 0

  • 采用这种定义的理由是：路由器在和直接连接在该网络上的主机通信时，不需要经过另外的路由器。
  • 既然每经过一个路由器要将距离加 1，那么不再经过路由器的距离就应当为 0
  • 但两种不同的定义对实现 RIP 协议并无影响，因为重要的是要找出最短距离，将所有的距离都加 1 或都减 1，对选择最佳路由其实是一样的。
  • 两种定义不影响RIP算法的正确性(不应该混用1和0,选定其中一种定义后就坚持到底)

• RIP 协议的“距离”也称为“跳数”(hop count)，

  • 因为每经过一个路由器，跳数就加1。
  • RIP 认为好的路由就是它通过的路由器的数目少，即“距离短”。
  • RIP 允许一条路径最多只能包含 15 个路由器。
  • 因此“距离”等于 16 时即相当于不可达。
  • 可见 RIP 只适用于小型互联网。

• RIP 不能在两个网络之间同时使用多条路由。

  • RIP 选择一条具有最少路由器的路由（即最短路由），哪怕还存在另一条高速(低时延)但路由器较多的路由。

• RIP 协议和 OSPF 协议，都是分布式路由选择协议。

  • 它们的共同特点就是每一个路由器都要不断地和其他一些路由器交换路由信息。
  • 我们一定要弄清以下三个要点，即和哪些路由器交换信息？交换什么信息？在什么时候交换信息？

RIP 协议的特点是：

• (1) 仅和相邻路由器交换信息。
  • 如果两个路由器之间的通信不需要经过另一个路由器，那么这两个路由器就是相邻的。RIP 协议规定，不相邻的路由器不交换信息。
• (2) 路由器交换的信息是当前本路由器所知道的全部信息，即自己现在的路由表。
  • 也就是说，交换的信息是：“我到本自治系统中所有网络的（最短）距离，以及到每个网络应经过的下一跳路由器”。
• (3) 按固定的时间间隔交换路由信息，
  • 例如，每隔 30 秒。
  • 然后路由器根据收到的路由信息更新路由表。
  • 当网络拓扑发生变化时，路由器也及时向相邻路由器通告拓扑变化后的路由信息。
  • 路由器在刚刚开始工作时，它的路由表是空的。
  • 然后路由器就得出到直接相连的几个网络的距离（这些距离定义为 1）。
  • 接着，每一个路由器也只和数目非常有限的相邻路由器交换并更新路由信息。
  • 但经过若干次的更新后，所有的路由器最终都会知道到达本自治系统中任何一个网络的最短距离和下一跳路由器的地址。
  • 看起来 RIP 协议有些奇怪，因为“我的路由表中的信息要依赖于你的，而你的信息又依赖于我的。
  • ”然而事实证明，通过这样的方式—“我告诉别人一些信息，而别人又告诉我一些信息。我再把我知道的更新后的信息告诉别人，别人也这样把更新后的信息再告诉我”，最后在自治系统中所有的结点都得到了正确的路由选择信息。
  • 在一般情况下，RIP 协议可以收敛，并且过程也较快。
    • “收敛”就是在自治系统中所有的结点都得到正确的路由选择信息的过程。
  • 路由表中最主要的信息就是：到某个网络的距离（即最短距离），以及应经过的下一跳地址。
  • 路由表更新的原则是找出到每个目的网络的最短距离。
  • 这种更新算法又称为距离向量算法。

RIP路由表格式

• 目的网络	距离(跳数/延迟)	下一条路由(NextRouter)

直连网络&直接交付@间接交付

• 路由选择分为直接交付和间接交付

• 当发送站与目的站在同一网段内时，就使用直接交付，反之使用间接交付，

• 间接交付的最后一个路由器肯定直接交付

• 直接交付在同一网段内，因此不涉及路由器

• 本路由器可以直接完成转任务,而不需要第二个路由器参时也可能是间接交付

• 因为同一个路由器可以链接两个网段,如果发生跨网段,就是间接交付

• 不跨网段才是直接交付

• 例如:Net1和Net2中的主机交换信息,就属于间接交付

  • 例如,Net1中有计算机C1想要发送数据到Net2中的C4

• 如果是C1想要发送数据到C2,它们不需要经过路由器可以通信(处于同一网段)

RIP算法

• 路由器收到相邻路由器（其地址为）的一个RIP报文：

• (1)先修改此RIP报文中的所有项目：

  • 把“下一跳”字段中的地址都改为X,
  • 并把所有的“距离”字段的值加1.

• (2)对修改后的RIP报文中的每一个项目，重复以下步骤：

  • 若项目中的目的网络D不在路由表中，则把该项目加到路由表中.
  • 否则(路由表中存在目的网络值为D的相关表项,只需要更新表项)
    • 若下一跳字段给出的路由器地址是同样的，则把收到的项目替换原路由表中的项目
      • 这种情况下距离字段可能发生变化;
        • 可能变大,也可能变小(更新原因是表项的内容可能是过时而不准确的,纯粹是为了获得最新信息)
    • 否则,下一跳路由地址是不同的
      • 这表示不同于现在路由表中所知道的路径是不同的(通往D新的路径出现了)
      • 但是新的路径未必比旧的路径更优(更短)因此还需要比较一下,再决定是使用新路径还是保留旧路径而放弃新路径
      • 若收到项目中的距离小于路由表中的距离，则进行更新，
        • 否则，什么也不做.

• (3)若3分钟还没有收到相邻路由器的更新路由表，则把此相邻路由器记为不可达路由器，即将距离置为16（表示不可达）.

• (4)返回.

特点

• 距离向量算法的基础就是 Bellman-Ford 算法（或 Ford-Fulkerson 算法）。
• 这种算法的要点是这样的：
• 设 X 是结点 A 到 B 的最短路径上的一个结点。
• 若把路径 A→B 拆成两段路径 A→X 和X→B，则每一段路径 A→X 和 X→B 也都分别是结点 A 到 X 和结点 X 到 B 的最短路径
• 好消息传播得快，而坏消息传播得慢。
• 网络出故障的传播时间往往需要较长的时间(例如数分钟)。这是 RIP 的一个主要缺点。
• 但如果一个路由器发现了更短的路由，那么这种更新信息就传播得很快。
  • 为了使坏消息传播得更快些，可以采取多种措施。
  • 例如，让路由器记录收到某特定路由信息的接口，而不让同一路由信息再通过此接口向反方向传送。
• RIP 协议最大的优点就是实现简单，开销较小。
• 但 RIP 协议的缺点也较多。
  • 首先，RIP 限制了网络的规模，它能使用的最大距离为 15（16 表示不可达）。
  • 其次，路由器之间交换的路由信息是路由器中的完整路由表，因而随着网络规模的扩大，开销也就增加。
  • 最后，“坏消息传播得慢”，使更新过程的收敛时间过长。(慢收敛容易造成路由回路问题)

实例

• R6路由表

  • 目的网络	距离(跳数)	下一跳路由
    Net2	3	R4
    Net3	4	R5
    …	…	…

• R4发来的路由更新信息:(也就是R4的路由表)

  • 目的网络	距离(跳数)	目的网络
    Net1	3	R1
    Net2	4	R2
    Net3	1	直接交付
    …	…	…

  • R6收到更新信息,开始计算R4路由表的过度表格U(R4)

    • 将R4映射成U(R4):(拷贝一份R4)其执行以下操作

      • 将下一跳路由全部改为R4
      • 将跳数全部加1

    • 这个操作的意图是,使得路径:R6→R4→RxR6\to{R4}\to{Rx}R6→R4→Rx的距离可以从U(R4)的距离字段直接看出来

    • (条目编号)	目的网络	距离(跳数)	下一跳路由
      1	Net1	4	R4
      2	Net2	5	R4
      3	Net3	2	R4
      …	…	…	…

      • 条目编号不是路由表中的字段,为了便于指代和讨论所设立

• R6对比U(R4),增加/更新R6中的项目

  • 目的网络	距离(跳数)	下一跳路由	Note
    Net1	4	R4	这个表项是新增的
    Net2	5	R4	目的网络一致,由于下一跳路由都是R4,强制更新为U(R4)中的值
    Net3	2	R4	对比U(R4)条目3,目的网络一致, 下一跳路由不同,则需要比较距离; U(R4)中的值更优(2<4),更新为2
    …	…	…	…

例

• 考虑如右图所示的子网，

• 该子网使用了距离向量算法，下面的向量刚刚到达路由器C:

  • 来自B的向量为（5,0,8,12,6,2)；
  • 来自D的向量为(16,12,6,0,9,10)；
  • 来自E的向量为(7,6,3,9,0,4)。

• 经过测量，C到B、D和E的延迟分别为6、3和5

• 那么C到达所有结，点的最短路径是（B）。

  • A.(5,6,0,9,6,2)
    B.(11,6,0,3,5,8)
    C.(5,11,0,12,8,9)
    D.(11,8,0,7,4,9)

• 分析:

  • x∈{A,B,C,D,E,F}x\in\{A,B,C,D,E,F\}x∈{A,B,C,D,E,F}

• 🎈本例中,将直接交付定义为延迟0

  • 而且不再以跳数作为衡量,而采用延迟作为衡量好坏

• 		A	B	C	D	E	F
  B→xB\to{x}B→x		5	0	8	12	6	2
  D→xD\to{x}D→x		16	12	6	0	9	10
  E→xE\to{x}E→x		7	6	3	9	0	4
  C→B→xC\to{B}\to{x}C→B→x	$	C\to{B}	=+6$	11	6	14	18
  C→D→xC\to{D}\to{x}C→D→x	$	C\to{D}	=+3$	19	15	9	3
  C→E→xC\to{E}\to{x}C→E→x	$	C\to{E}	=+5$	12	11	8	14
  			B		D	E

• 向量中的各个分量对应的站点应该是从A到F或者其逆向顺序

  • 观察向量中为0的分量,表示到自身,所以可以直接确定B是第2个分量
  • (D,E也是,分别为第4,5个分量)

• 容易看到,C到其他站点的最短距离分别是

  • A:11
  • B:6
  • C:0(目的网络连接在C上,是可以直接交付直连网路,延迟为0,而不会是其他值)
  • D:3
  • E:5
  • F:8

OSPF协议的基本特点

• 开放最短路径优先（OSPF）协议是使用分布式链路状态路由算法的典型代表，也是内部网关协议(IGP）)的一种.
• 基础是Dijkstra算法

OSPF与 RIP主要区别:

• 路由器间交换消息的方式
• 1)OSPF向本自治系统中的所有路由器发送信息，这里使用的方法是洪泛法.而RIP仅向自己相邻的几个路由器发送信息.
• 路由器间交换的消息区别
  • 2）发送的信息是与本路由器相邻的所有路由器的链路状态，但这只是路由器所知道的部分信息.“链路状态”说明本路由器和哪些路由器相邻及该链路的“度量”(或代价).而在RIP中，发送的信息是本路由器所知道的全部信息，即整个路由表.
• 路由表变化频率
  • 3）只有当链路状态发生变化时，路由器才用洪泛法向所有路由器发送此信息，并且更新过程收敛得快，不会出现REP“坏消息传得慢”的问题.
    而在 RIP中，不管网络拓扑是否发生变化，路由器之间都会定期交换路由表的信息.
• 两种协议所处的层次
  • 4)OSPF是网络层协议，它不使用UDP或TCP，而直接用P数据报传送（其P数据报首部的协议字段为89).
    而RIP是应用层协议，它在传输层使用UDP.

三种路由协议的比较

• 协议	RIP	OSPF	BGP
  类型	内部	内部	外部
  路由算法	距离-向量	链路状态	路径-向量
  传递协议	UDP	IP	TCP
  路径选择	跳数最少	代价最低	较好,非最佳
  交换结点	和本结点相邻的路由器	网络中的所有路由器	和本结点相邻的路由器
  交换内容	当前本路由器知道的全部信息,(即,自己的路由表)	与本路由相邻的所有路由器的链路状态	1.首次:整个路由表; 2.非首次:有变化的部分