目录

一、有关路由选择协议的几个基本概念

1. 理想的路由算法

2. 分层次的路由选择协议

 二、内部网关协议RIP

1. 工作原理

2. 距离向量算法

3. RIP协议的报文格式

4. RIP的优缺点

三、内部网关协议OSPF

1. OSPF协议的基本特点

2. OSPF协议的数据报

3. OSPF的五种分组类型

四、外部网关协议BGP

五、路由器的构成

1. 路由器的结构：

2. 交换结构

---

一、有关路由选择协议的几个基本概念

1. 理想的路由算法

(1)算法必须是正确的和完整的。

        即沿着各路由器所指的路由，分组一定能够最终到达目的网络和目的主机。

(2)算法在计算上应简单。

(3)算法应能适应通信量和网络拓扑的变化，这就是说，要有自适应性。

        当网络中的通信录发生变化时，算法能自适应改变路由以均衡各链路的负载。

当某个或某些结点、链路发生故障，或者修理好了再投入，算法应该能及时改变路由。

(4)算法应具有稳定性。

        在网络通信量和网络拓扑相对稳定情况下，路由算法应该收敛于一个可以接受的解，不应该不断变化。

(5)算法应是公平的。

        算法对所有用户是平等的，不能为了某个用户牺牲大部分用户。

(6)算法应是最佳的。

        不存在一种绝对的最佳路由算法。

        所谓“最佳”只能是相对于某一种特定要求下得出的较为合理的选择而已。

        实际的路由选择算法，应尽可能接近于理想的算法。

        路由选择是个非常复杂的问题

                它是网络中的所有结点共同协调工作的结果。

                路由选择的环境往往是不断变化的，而这种变化有时无法事先知道。

路由算法分类：

        静态路由选择策略——即非自适应路由选择，其特点是简单和开销较小，但不能及时适应网络状态的变化。

        动态路由选择策略——即自适应路由选择，其特点是能较好地适应网络状态的变化，但实现起来较为复杂，开销也比较大。

2. 分层次的路由选择协议

        互联网采用的路由选择协议主要是自适应的(即动态的)、分布式路由选择协议。

互联网采用分层次的路由选择协议原因：

        (1) 互联网规模非常大。如果让所有的路由器知道所有的网络应怎样到达，则这种路由表将非常大，处理起来也太花时间。而所有这些路由器之间交换路由信息所需的带宽就会使互联网的通信链路饱和。

        (2) 许多单位不愿意外界了解自己单位网络的布局细节和本部门所采用的路由选择协议（这属于本部门内部的事情），但同时还希望连接到互联网上。  

因此，把互联网划分成许多较小的自治系统，一般记为AS。

        自治系统AS是在单一技术管理下的一组路由器，这些路由器使用一种自治系统内部的路由选择协议和共同的度量。

        一个AS对其他AS表现出的是一个单一的和一致的路由选择策略。

        在互联网种，一个大的ISP就是一个自治系统。

路由选择协议分为两大类：

(1) 内部网关协议IGP

        在一个自治系统内部使用的路由选择协议，和互联网中其他自治系统选择什么路由选择协议无关。

        目前使用最多的是RIP和OSPF协议。

(2)外部网关协议EGP

        若源主机和目的主机不在一个自治系统中，这两个自治系统可能使用不同内部网关协议。二者传递数据，在两个自治系统边界交换时，就需要使用一种协议传递。

        目前使用最多的时BGP的版本4，即BGP-4。

自治系统之间的路由选择叫做域间路由选择，自治系统内部的路由选择叫做域内路由选择。

 二、内部网关协议RIP

        RIP是内部网关协议IGP中最先得到广泛使用的协议，它的中文名字叫做路由信息协议。最大的优点就是简单。

1. 工作原理

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

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

 距离定义：

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

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

        RIP 协议中的“距离”也称为“跳数”(hop count)，因为每经过一个路由器，跳数就加 1。

        这里的“距离”实际上指的是“最短距离”。因为从一个路由到另一个路由可能有多种走法。

有关距离的要点：

        RIP 认为一个好的路由就是它通过的路由器的数目少，即“距离短”。

        RIP 允许一条路径最多只能包含 15 个路由器。

        “距离”的最大值为 16 时即相当于不可达。可见 RIP 只适用于小型互联网。

        RIP 不能在两个网络之间同时使用多条路由。RIP 选择一个具有最少路由器的路由（即最短路由），哪怕还存在另一条高速(低时延)但路由器较多的路由。  

RIP协议的三个特点：

        (1) 仅和相邻路由器交换信息。

        (2) 交换的信息是当前本路由器所知道的全部信息，即自己的路由表。

        (3) 按固定的时间间隔交换路由信息，例如，每隔 30 秒。当网络拓扑发生变化时，路由器也及时向相邻路由器通告拓扑变化后的路由信息。

路由表的建立:

        路由器在刚刚开始工作时，它的路由表是空的。只知道到直接连接的网络的距离（此距离定义为1）。

        以后，每一个路由器也只和数目非常有限的相邻路由器交换并更新路由信息。

        经过若干次更新后，所有的路由器最终都会知道到达本自治系统中任何一个网络的最短距离和下一跳路由器的地址。

        RIP 协议的收敛过程较快。“收敛”就是在自治系统中所有的结点都得到正确的路由选择信息的过程。

2. 距离向量算法

        这种算法的要点是这样的： 设X是结点 A 到 B 的最短路径上的一个结点。 若把路径 A→B 拆成两段路径 A→X 和 X→B，则每一段路径 A→X 和 X→B 也都分别是结点 A 到 X 和结点 X 到 B 的最短路径。

        RIP 协议让互联网中的所有路由器都和自己的相邻路由器不断交换路由信息，并不断更新其路由表，使得从每一个路由器到每一个目的网络的路由都是最短的（即跳数最少）。

        虽然所有的路由器最终都拥有了整个自治系统的全局路由信息，但由于每一个路由器的位置不同，它们的路由表当然也应当是不同的。  

路由表：

目的网络	距离	下一跳路由
Net	3	R

算法内容：

路由器对收到相邻路由器（其地址为X，目的网络为 N）的每一个 RIP 报文：

(1) 先修改此 RIP 报文中的所有项目：把“下一跳”字段中的地址都改为 X，并把所有的“距离”字段的值加 1。

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

        若项目中的目的网络N不在路由表中，则把该项目加到路由表中。  

        否则 (即目的网络N在路由表)

                若路由表中目的网络N下一跳路由器地址为X，则把收到的项目替换原路由表中的项目。

                否则(即原路由表中目的网络N的下一跳地址不是X)

                        若收到项目中的距离小于路由表中的距离，则进行更新。

                         否则

                                什么也不做。

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

(4) 返回。

例子：

已知路由器 R6 有 表(a) 所示的路由表。现在收到相邻路由器 R4 发来的路由更新信息，如 表(b) 所示。试更新路由器 R6 的路由表。

 Net1为新的目的网络，Net2为更新的网络，Net3为距离更近更新的网络。

3. RIP协议的报文格式

RIP协议使用运输层的用户数据报UDP进行传送，因此IP数据报数据头部为UDP头部。

RIP数据报由首部和路由部分组成：

首部：

        首部占4个字节，命令字段指出报文的意义。例如，1代表请求路由信息，2代表对请求路由信息的响应或未被请求而发出的路由更新报文。

        后面必为0是为了凑齐4个字节，用0补齐。

路由部分：

        RIP2 报文中的路由部分由若干个路由信息组成。每个路由信息需要用 20 个字节。

                地址族标识符（又称为地址类别）字段用来标志所使用的地址协议。

                路由标记填入自治系统的号码,这是考虑RIP 有可能收到本自治系统以外的路由选择信息.

                再后面指出某个网络地址,该网络的子网掩码,下一跳路由器地址以及到此网络的距离。

其他要点：

        一个 RIP 报文最多可包括 25 个路由，因而 RIP 报文的最大长度是4  + 20 *25 = 504 字节。如超过，必须再用一个 RIP 报文来传送。

        RIP2(上面说的都是RIP2) 具有简单的鉴别功能。

                若使用鉴别功能，则将原来写入第一个路由信息（20字节）的位置用作鉴别。

                在鉴别数据之后才写入路由信息，但这时最多只能再放入 24 个路由信息。

4. RIP的优缺点

优点： 

        实现简单，开销较小。

缺点：

        RIP 限制了网络的规模，它能使用的最大距离为 15（16 表示不可达）。

        路由器之间交换的路由信息是路由器中的完整路由表，因而随着网络规模的扩大，开销也就增加。

        “坏消息传播得慢”，使更新过程的收敛时间过长。

坏消息传得慢解释：

 

         网1出现问题，R1标记为16，但是R2发送了自己的路由信息，R1会更新自己路由表，将网1重新距离改为3，这样会不断更新，直到2者到网1都为16为止。

三、内部网关协议OSPF

        开放最短路径优先 OSPF 是为克服 RIP 的缺点在1989年开发出来的。

        OSPF 的原理很简单，但实现起来却较复杂。

1. OSPF协议的基本特点

        “开放”表明 OSPF 协议不是受某一家厂商控制，而是公开发表的。

        “最短路径优先”是因为使用了 Dijkstra 提出的最短路径算法 SPF 。OSPF 只是一个协议的名字，它并不表示其他的路由选择协议不是“最短路径优先”。

        采用分布式的链路状态协议 。 

三个要点：

        (1)向本自治系统中所有路由器发送信息，这里使用的方法是洪泛法，就是路由器通过所有的输出端口向所有相邻的路由器发送信息。然后每个相邻路由器又将此信息发往其所有的相邻路由器(除了发给他的那个路由器)。

        (2)发送的信息就是与本路由器相邻的所有路由器的链路状态，但这只是路由器所知道的部分信息。

        “链路状态”就是说明本路由器都和哪些路由器相邻，以及该链路的“度量”。

        (3)只有当链路状态发生变化时，路由器才用洪泛法向所有路由器发送此信息。  

链路状态数据库：

        由于各路由器之间频繁地交换链路状态信息，因此所有的路由器最终都能建立一个链路状态数据库。

        这个数据库实际上就是全网的拓扑结构图，它在全网范围内是一致的（这称为链路状态数据库的同步）。

        OSPF 的链路状态数据库能较快地进行更新，使各个路由器能及时更新其路由表。

        OSPF 的更新过程收敛得快是其重要优点。

区域：

        为了使 OSPF 能够用于规模很大的网络，OSPF 将一个自治系统再划分为若干个更小的范围，叫作区域。

        每一个区域都有一个 32 位的区域标识符（用点分十进制表示）。

        区域也不能太大，在一个区域内的路由器最好不超过 200 个。  

         划分区域的好处就是将利用洪泛法交换链路状态信息的范围局限于每一个区域而不是整个的自治系统，这就减少了整个网络上的通信量。

        在一个区域内部的路由器只知道本区域的完整网络拓扑，而不知道其他区域的网络拓扑的情况。 

主干区域：

        OSPF 使用层次结构的区域划分。在上层的区域叫作主干区域 。

        主干区域的标识符规定为0.0.0.0。主干区域的作用是用来连通其他在下层的区域。  

区域边界路由器：

        从其他区域来的信息都由区域边界路由器进行概括。例如上图中R3、R4、R7。

主干路由器：

        在主干区域内的路由器叫做主干路由器。例如上图中R3、R4、R5、R6、R7。

2. OSPF协议的数据报

        OSPF 不用 UDP 而是直接用 IP 数据报传送。

        OSPF 构成的数据报很短。这样做可减少路由信息的通信量。

        数据报很短的另一好处是可以不必将长的数据报分片传送。

        分片传送的数据报只要丢失一个，就无法组装成原来的数据报，而整个数据报就必须重传。

(1)版本        当前版本号是2

(2)类型        可以是五种类型分组中的一种。下面会介绍。

(3)分组长度        包括OSPF首部在内的分组长度，以字节为单位。

(4)路由器标识符        标志发送该分组的路由器的接口的IP地址。

(5)区域标识符        分组属于的区域的标识符。

(6)检验和        用来检测分组中的差错。

(7)鉴别类型        目前只要两种，0表示不用，1表示口令。

(8)鉴别        鉴别类型为0就填入0，鉴别类型为1就填入8个字符的口令。

其他特点：

        (1)OSPF 对不同的链路可根据 IP 分组的不同服务类型 TOS 而设置成不同的代价。因此，OSPF 对于不同类型的业务可计算出不同的路由。

        (2)如果到同一个目的网络有多条相同代价的路径，那么可以将通信量分配给这几条路径。这叫作多路径间的负载平衡。

        (3)所有在 OSPF 路由器之间交换的分组都具有鉴别的功能。

        (4)支持可变长度的子网划分和无分类编址 CIDR。

        (5)每一个链路状态都带上一个 32 位的序号，序号越大状态就越新。

3. OSPF的五种分组类型

(1)问候分组。用来发现和维持邻站的可达性。

(2)数据库描述分组。向邻站给出自己的链路状态数据库中所有链路状态项目的摘要信息。

(3)链路状态请求分组。向对方发送某些链路状态项目的详细信息。

(4)链路状态更新分组。用洪泛法对全网更新链路状态。这是最复杂、最核心的部分。

(5)链路状态确认分组。对链路更新分组的确认。

一些规定：

        每隔10秒相邻的两个路由器就要发送一次问候分组，来确认是否可达。若有40秒没有收到某个相邻路由器的问候分组，就认为是不可达的，并立即修改链路状态数据库。

        其余四种分组都是用来进行链路状态数据库的同步。

        OSPF 还规定每隔一段时间，如 30 分钟，要刷新一次数据库中的链路状态。

        由于一个路由器的链路状态只涉及到与相邻路由器的连通状态，因而与整个互联网的规模并无直接关系。因此当互联网规模很大时，OSPF  协议要比距离向量协议 RIP 好得多。

        OSPF 没有“坏消息传播得慢”的问题，据统计，其响应网络变化的时间小于 100 ms。

指定路由器：

        多点接入的局域网采用了指定的路由器的方法，使广播的信息量大大减少。

        指定的路由器代表该局域网上所有的链路向连接到该网络上的各路由器发送状态信息。

四、外部网关协议BGP

        BGP 是不同自治系统的路由器之间交换路由信息的协议。

        BGP 较新版本是 2006 年 1 月发表的 BGP-4（BGP 第 4 个版本），即 RFC 4271 ~ 4278。 可以将 BGP-4 简写为 BGP。

BGP与内部网关协议环境不同：

        内部网关协议主要是设法使数据报在一个AS内尽可能有效的从源站传送到目的站，在一个AS内部也不需要考虑其他方面的策略。

而BGP使用环境不同，原因如下：

(1) 互联网的规模太大，使得自治系统之间路由选择非常困难。对于自治系统之间的路由选择，要寻找最佳路由是很不现实的。

         当一条路径通过几个不同 AS 时，要想对这样的路径计算出有意义的代价是不太可能的。

        比较合理的做法是在 AS 之间交换“可达性”信息。

(2)自治系统之间的路由选择必须考虑有关策略。

          -----------------------------------------------------------------------------------------------------

        因此，边界网关协议 BGP 只能是力求寻找一条能够到达目的网络且比较好的路由（不能兜圈子），而并非要寻找一条最佳路由。

BGP发言人：

        每一个自治系统的管理员要选择至少一个路由器作为该自治系统的“ BGP 发言人”  。

        一般说来，两个 BGP 发言人都是通过一个共享网络连接在一起的，而 BGP 发言人往往就是 BGP 边界路由器，但也可以不是 BGP 边界路由器。

BGP交换路由信息：

        一个 BGP 发言人与其他自治系统中的 BGP 发言人要交换路由信息，就要先建立 TCP 连接，然后在此连接上交换 BGP 报文以建立 BGP 会话，利用 BGP 会话交换路由信息。

        使用 TCP 连接能提供可靠的服务，也简化了路由选择协议。

        使用 TCP 连接交换路由信息的两个 BGP 发言人，彼此成为对方的邻站或对等站。

BGP发言人和自治系统AS之间的关系：

AS连通图：

        BGP 所交换的网络可达性的信息就是要到达某个网络所要经过的一系列 AS。

        当 BGP 发言人互相交换了网络可达性的信息后，各 BGP 发言人就根据所采用的策略从收到的路由信息中找出到达各 AS 的较好路由。

下图为一个BGP发言人构造出的自治系统连通图，是树形结构：

                

 

        自治系统 AS2 的 BGP 发言人通知主干网 AS1 的 BGP 发言人：“要到达网络 N1、 N2、N3 和 N4 可经过 AS2。”

        主干网还可发出通知：“要到达网络 N5、N6 和 N7 可沿路径（AS1, AS3）。”

 BGP协议特点：

        BGP 协议交换路由信息的结点数量级是自治系统数的量级，这要比这些自治系统中的网络数少很多。

        每一个自治系统中 BGP 发言人（或边界路由器）的数目是很少的。这样就使得自治系统之间的路由选择不致过分复杂。  

        BGP 支持 CIDR，因此 BGP 的路由表也就应当包括目的网络前缀、下一跳路由器，以及到达该目的网络所要经过的各个自治系统序列。

        在BGP 刚刚运行时，BGP 的邻站是交换整个的 BGP 路由表。但以后只需要在发生变化时更新有变化的部分。这样做对节省网络带宽和减少路由器的处理开销都有好处。

BGP-4的四种报文：

(1) 打开 (OPEN) 报文，用来与相邻的另一个BGP发言人建立关系。

(2) 更新 (UPDATE) 报文，用来发送某一路由的信息，以及列出要撤消的多条路由。

(3) 保活 (KEEPALIVE) 报文，用来确认打开报文和周期性地证实邻站关系。

(4) 通知 (NOTIFICATION) 报文，用来发送检测到的差错。

四种报文具有同样的通用首部，长度为19字节，分为三个字段：

        标记字段，长16字节，用来鉴别收到的BGP报文。不适用鉴别时，这个字段全为1.

        长度字段，长2字节，指出包括首部在内的整个BGP报文以字节为单位的长度(<=4096,>=1).

        类型字段，长1字节，值为1到4，对应上述四种报文中的一种。

五、路由器的构成

路由器是一种典型的网络层设备。

路由器是互联网中的关键设备。

路由器的主要作用是：

        连通不同的网络。

        选择信息传送的线路。选择通畅快捷的近路，能大大提高通信速度，减轻网络系统通信负荷，节约网络系统资源，提高网络系统畅通率，从而让网络系统发挥出更大的效益来。

1. 路由器的结构：

        路由器是一种具有多个输入端口和多个输出端口的专用计算机，其任务是转发分组。

        下一跳路由器也按照这种方法处理分组，直到该分组到达终点为止。

        路由器的转发分组正是网络层的主要工作。

 由上图可知，路由器的结构可以划分为两大部分：路由选择部分和分组转发部分。

路由选择部分：

        路由选择也叫做控制部分，核心构件是路由选择处理机。

        路由选择处理机的任务是根据所选定的路由选择协议构造出路由表，同时经常或定期地和相邻路由器交换路由信息而不断地更新和维护路由表。

分组转发由三部分组成：

        交换结构 (switching fabric)：又称为交换组织，其作用是根据转发表对分组进行处理。

        一组输入端口。

        一组输出端口。(请注意：这里的端口就是硬件接口）

转发与路由选择的区别：

        “转发”就是路由器根据转发表将用户的 IP 数据报从合适的端口转发出去。

        “路由选择”则是按照分布式算法，根据从各相邻路由器得到的关于网络拓扑的变化情况，动态地改变所选择的路由。

        路由表是根据路由选择算法得出的。而转发表是从路由表得出的。

        在讨论路由选择的原理时，往往不去区分转发表和路由表的区别。

输入端口：

        路由器的输入端口里面装有物理层、数据链路层和网络层的处理模块。

        数据链路层剥去帧首部和尾部后，将分组送到网络层的队列中排队等待处理。这会产生一定的时延。

        输入端口中的查找和转发功能在路由器的交换功能中是最重要的。

输出端口：

        输出端口里面装有物理层、数据链路层和网络层的处理模块。

        输出端口从交换结构接收分组，然后把它们发送到路由器外面的线路上。

        在网络层的处理模块中设有一个缓冲区（队列）。当交换结构传送过来的分组的速率超过输出链路的发送速率时，来不及发送的分组就必须暂时存放在这个队列中。

        数据链路层处理模块将分组加上链路层的首部和尾部，交给物理层后发送到外部线路。

分组丢弃：

        若路由器处理分组的速率赶不上分组进入队列的速率，则队列的存储空间最终必定减少到零，这就使后面再进入队列的分组由于没有存储空间而只能被丢弃。

        路由器中的输入或输出队列产生溢出是造成分组丢失的重要原因。

2. 交换结构

        交换结构是路由器的关键构件。

        正是这个交换结构把分组从一个输入端口转移到某个合适的输出端口。

        实现交换有多种方法。常用交换方法有三种：

                通过存储器

                通过总线

                通过纵横交换结构

通过存储器

        当路由器的某个输入端口收到一个分组时，就用中断方式通知路由选择处理机。然后分组就从输入端口复制到存储器中。

        路由器处理机从分组首部提取目的地址，查找路由表，再将分组复制到合适的输出端口的缓存中。

        若存储器的带宽（读或写）为每秒 M 个分组，那么路由器的交换速率（即分组从输入端口传送到输出端口的速率）一定小于 M/2。

通过总线

        数据报从输入端口通过共享的总线直接传送到合适的输出端口，而不需要路由选择处理机的干预。

        因为每一个要转发的分组都要通过这一条总线，因此路由器的转发带宽就受总线速率的限制。

        现代的技术已经可以将总线的带宽提高到每秒吉比特的速率，因此许多的路由器产品都采用这种通过总线的交换方式。

通过纵横交换结构

        这种交换结构常称为互连网络。

        它有2N条总线，可以使N个输入端口和N个输出端口相连接。

        当输入端口收到一个分组时，就将它发送到与该输入端口相连的水平总线上。

        若通向所要转发的输出端口的垂直总线是空闲的，则在这个结点将垂直总线与水平总线接通，然后将该分组转发到这个输出端口。

       但若该垂直总线已被占用（有另一个分组正在转发到同一个输出端口），则后到达的分组就被阻塞，必须在输入端口排队。

路由选择算法

路由选择的工作是：确定从发送方到接收方通过路由器网络的好路径（等价为路由）

路由选择算法的工作是：给定一组路由器以及连接路由器的链路，路由选择算法要找到一条从源路由器到目的路由器的“好”路径。通常一条好路径指具有最低费用的路径。（实际还要考虑现实世界中的策略之类的问题，如属于组织Y的路由器X不应转发任何来源于组织Z网络的分组之类的规则。）

如下图为计算机网络的抽象模型，显然需要使用图来进行描述，路由选择算法就是找到源到目的的最低费用路径。

 路由选择算法的分类：

根据算法是全局式还是分散式进行分类

全局式路由选择算法：用全局性网络知识计算最低费用路径。即该算法以所有结点之间的连通性及所有链路的费用为输入

分散式路由选择算法：以迭代、分布式的方式计算出最低费用路径。即每个结点仅有与其直接相连链路的费用高知识即可开始。

根据算法是静态的还是动态的进行分类可以分为静态路由选择算法和动态路由选择算法。

根据时负载敏感还是负载迟钝进行分类可以分为负载敏感算法和负载迟钝算法。

链路状态算法（LS算法）

链路状态算法是全局式路由选择算法，网络拓扑和所有的链路费用已知，可以用作LS算法的输入。实践中通过让每个结点向网络中所有其他结点广播链路状态分组（包含所连接的链路特征和费用），使所有结点具有了该网络的等同的、完整的视图。于是每个节点都能够像其他结点一样，运行LS算法并计算出相同的最低费用路径集合。

LS算法其实就是图算法中经典的Dijkstra算法：

定义如下几个记号：

Dijkstra算法为： 

 当LS算法终止时，对于每个结点，我们都得到从源节点沿着它的最低费用路径的前一结点。对于每个前一结点，我们又有它的前一结点，以此方式我们可以构建从源结点到所有目的结点的完整路径。

距离向量算法（DV算法）

DV算法是分散式路由选择算法，是一种迭代的、一步的和分布式的算法。分布式是因为每个结点都要从一个或多分直接相连邻居接受某些信息，执行计算，然后将其计算结果分发给邻居。迭代的是因为此过程一直要持续到邻居之间无更多信息要交换为止。异步的是因为它不要求所有节点相互之间步伐一致地操作。

LS与DV路由选择算法的比较

在DV算法中，每个结点仅与它的直接相连的邻居交谈，但它为其邻居提供了从它自己到网络中（它所知道的）所有其他结点的最低费用估计。  在LS算法中，每个结点（经广播）与所有其他结点交谈，但它仅告诉它们与它直接相连链路的费用。

 通过对比以下属性总结比较LS和DV算法：N是结点（路由器）的集合，E是边（链路）的集合

报文复杂性：LS算法要求每个结点都知道网络中每条链路的费用，这就需要发送O(|N||E|)个报文。而且无论何时一条链路的费用改变时，必须向所有结点发送新的链路费用。DV算法要求在每次迭代时，在两个直接相连邻居之间交换报文，当链路费用改变时，DV算法仅当在新的链路费用导致与该链路相连结点的最低费用路径发生改变时，才传播已改变的链路费用。

收敛速度：LS算法的实现是一个要求O(|N||E|)个报文的O（|N|^2）算法。 DV算法收敛较慢，且在收敛时会遇到路由选择环路。甚至还会遭遇无穷级数的问题。

健壮性：LS结点由于仅计算自己的转发表，所以在某种程度上是分离的，提供了一定程度健壮性。而DV算法中一个结点的计算会传递给它的邻居，然后在下次迭代时再简介地传递给邻居的邻居，在这种情况下，DV算法中一个不正确的结点计算值会扩散到整个网络。

总之，两个算法没有一个是明显的赢家，他们的确都在因特网中得到了应用。

层次路由选择

上面两种算法中，随着路由器数目增多，涉及路由选择信息的计算、存储以及通信的开销将非常高，并且许多组织希望能够按照自己的意愿运行和管理其网络，这些问题都可以通过将路由器组织进自治系统（AS）来解决。

每个AS由一组通常处在相同管理控制下的路由器组成，并且在相同的AS中的路由器全部运行同样的路由选择算法，且拥有彼此信息。在一个自治系统内运行的路由选择算法叫做自治系统内部路由选择协议。当然，将AS互连是必须的，网关路由器负责向在本AS之外的目的地转发分组。从相邻AS获取可达性信息和向该AS中所有路由器传播可达性信息是两项由自治系统间路由选择协议处理的任务。

因特网中的路由选择

自治系统内部路由选择协议

AS内部路由选择协议（也称为内部网关协议）用于确定在一个AS内执行路由选择的方式。历史上有两个路由选择协议被广泛应用于因特尔网上自治系统内的路由选择：路由选择信息协议（RIP）和开放最短路优先（OSPF）

RIP

RIP是一种距离向量协议，使用跳数作为其费用测度，即每条链路的费用为1，一条路径的最大费用被限制为15，因此RIP的使用限制在网络直径不超过15跳的自治系统内。

每台路由器维护一张称为路由选择表的RIP表。一台路由选择器的路由选择表包括该路由器的距离向量和该路由器的转发表。

OSPF

OSPF的核心是一个使用洪泛链路状态信息的链路状态协议和一个Dijkstra最低费用路径算法。使用OSPF，一台路由器构建了一幅关于整个自治系统的完整拓扑图，于是，路由器在本地运行Dijkstra的最短路径算法，以确定一个以自身为根结点的到所有子网的最短路径树。

使用OSPF时，各条链路费用是由网络管理员配置的（可以将链路费用设为1，实现最少跳数路由选择。或者将链路权值按与链路容量成反比来设置）。另外，使用OSPF时，路由器向自治系统内所有其他路由器广播路由选择信息，而不仅仅是向其相邻路由器广播。每当一条链路状态发生变化时，路由器就会广播链路状态信息，即便没有变化，他也要周期性地广播链路状态。

OSPF优点：安全、多条相同费用的路径、对单播与多播路由选择的综合支持、支持在单个路由选择域内的层次结构。

自治系统间的路由选择：BGP

作为一个自治系统间路由选择协议，BGP为每个AS提供了进行以下工作的手段：

• 1.从相邻AS处获得子网可达性信息
• 2.向本AS内部的所有路由器传播这些可达性信息
• 3.基于可达性信息和AS策略，决定到达子网的“好”路由

广播和多播路由选择

在广播路由选择中，网络层提供了从一种源结点到网络中的所有其他结点交付分组的任务。多播路由选择使单个源结点能够向其他网络节点的一个子集发送分组的副本。

广播路由选择算法

无控制洪泛： 源结点向他的所有邻居发送分组的副本，当某结点接收了一个广播分组时，复制分组并向它的所有邻居转发。注意虽然实现简单，但是如果图中有圈，则每个广播分组的一个或多个分组副本将无休无止地循环。

受控洪泛：避免副本循环可以使用序号控制洪泛（给分组加上地址和广播序号）、反向路径转发（当一台路由器接收到具有给定源地址的广播分组时，仅当该分组到达的链路正好是位于它自己的返回其源的最短单播路径上，它才向其所有出链路传输报文）

生成树广播：先对网络节点构造出一颗生成树，当一个源结点要发送一个广播分组时，它向所有属于该生成树的特定链路发送分组。接收广播分组的结点则向在生成树中的所有邻居转发该分组。  生成树不仅消除了冗余的广播分组，而且一旦合适，该生成树能够被任何结点用于开始广播分组。

多播

在单播通信情况下，接收方IP地址承载在每个IP单播数据报中并表示了单个接收方；在广播情况下，所有结点需要接收广播分组，因此不需要目的地址。但在多播情况下，面对多个接收方，该怎么做呢？

多播数据报使用间接地址来编址。即用一个标识来表示一组接收方，寻址到该组的分组副本被交付给所有与该组相关联的多播接收方，且该组使用这个单一标识符。

因特网中，这种表示一组接收方的单一标识就是一个D类多播地址，与一个D类地址相关联的接收方小组被称为一个多播组。因特网中的网络层多播是由两个互补的组件组成：IGMP与多播路由选择协议

因特网组管理协议（IGMP）

IGMP协议运行在一台主机与其直接相连的路由器之间，它为一台主机提供了手段，让它通知与其相连的路由器：在本主机上运行的一个应用程序想加入一个特定的多播组。

IGMP只有三种报文类型，并且报文封装在一个IP数据报中。

membership_query报文：路由器向所有主机连接接口发送，以确定该接口上主机已加入的所有多播组集合。

membership_report报文：主机向路由器响应membership_query报文。

leave_group报文：可选。  路由器可以通过membership_query报文确定多播组主机数量，当无主机响应时，就知道没有主机在这个多播组了

多播路由选择算法

多播路由选择的目标就是发现一颗链路的树，这些链路连接了所有属于该多播组的相连主机的路由器。于是多播分组将能够沿着这棵树从发送方路由到所有属于该多播树的主机。

实践中，采用两种方法确定多路选择树：

• 使用一颗组共享树的多播路由选择    用单一的组共享树来为组中的所有发送方分发流量
• 使用一颗基于源的树的多播路由选择  为每个独立的发送方构建一颗特定元的路由选择树

在因特网中的多播路由选择

第一个用于因特网中的多播路由选择协议是距离向量多播路由选择协议（DVMRP）。DVMRP实现了具有反向路径转发与剪枝算法的基于源的树。

使用最为广泛的因特网多播路由协议是协议无关的多播路由选择协议（PIM）， 该协议明确辨识了两种多播分发情形。

在稠密模式中，多播组的成员位置分布稠密，即该区域内的许多或大多数路由器要参与到多播数据报路由选择过程中。PIM稠密模式是一种洪泛与剪枝反向路径转发技术，类似于DVMPR思想。

在稀疏模式中，具有相连组成员的路路由器数量相对于路由器总数来说很少，组成员极为分担。PIM稀疏模式使用聚集点来建立多播分发树。在源特定多播中，仅允许单一发送方向多播树中发送流量，大大简化了树的构造和维护。

路由选择可分为两类 静态路由选择和动态路由选择

一 静态路由选择

概念 由人工配置的网络路由 默认路由 特定主机路由 黑洞路由等都属于静态路由

特点：这种人工配置方式简单 开销小 但不能及时适应网络状态（流量 拓扑）的变化

适用范围：一般只在小规模网络中采用

二 动态路由选择

概念：路由器通过路由选择协议自动获取路由信息

特点：比较复杂 开销比较大 但能较好的适应网络状态的变化

适用范围：适用于大规模网络

三 因特网所采用的路由选择协议的特点

 

• 自适应

  • 动态路由选择 能够较好的适应网络状态的变化

• 分布式

  • 路由器之间交换路由信息

• 分层次

  • 将整个因特网划分为许多较小的自治系统AS

    (Autonomous System)

自治系统之间的路由选择简称为域间路由选择 使用外部网关协议EGP这个类别的路由选择协议

自治系统内部的路由选择简称为域内路由选择 使用内部网关协议IGP这个类别的路由选择协议

EGP/IGP只是路由选择协议的分类名称 而不是具体的路由选择协议

 

四 路由器的基本结构

 

概念：路由器是一种具有多个输入端口和输出端口的专用计算机 其任务是转发分组

结构：

• 路由选择部分

  • 核心构件：路由选择处理机

  • 任务：根据所使用的路由选择协议周期性的与其他路由器进行路由信息的交互来更新路由表

• 分组转发部分

  • 核心构件：交换结构 一组输入端口 一组输出端口

  • 交换结构 转发表

  • 输入端口

    • 信号从某个端口进入路由器 物理层将信号转换为比特流 送交数据链路层处理

    • 数据链路层从比特流中识别出帧 去掉帧头和帧尾后 送交网络层处理

    • A 如果送交网络层的分组是普通待转发的数据分组 则根据分组首部中的目的地址进行查表转发 若找不到匹配的转发条目 则丢弃该分组 否则 按照匹配条目中所指示的端口进行转发

    • B 如果送交网络层的分组是路由器之间交互路由信息的路由报文 则把这种分组送交路由选择处理机 路由选择处理机根据分组的内容来更新自己的路由表

  • 输出端口

    • 网络层更新数据分组首部中某些字段的值 例如 将数据分组的生存时间-1 然后送交数据链路层进行封装

    • 数据链路层将数据分组封装成帧 送交物理层处理

    • 物理层将帧看作是比特流 将其变换成相应的电信号进行发送

  • 辨析路由器中的路由表和转发表
    • 路由表一般仅含从目的网络到下一跳的映射
    • 路由表需要对网络拓扑变化的计算最优化
    • 转发表是从路由表中得出的

    • 转发表的结构应当使查找过程最优化

                  路由选择处理机 除了处理收到的路由报文外 还会周期性的给其他路由器发送自己所知道的路由信息

                路由器的各端口还应具有输入缓冲区和输出缓冲区

• 输入缓冲区用来暂存新进入路由器还来不及处理的分组

• 输出缓冲区用来暂存已经处理完毕但还来不及发送的分组