目录
(1)算法必须是正确的和完整的。
即沿着各路由器所指的路由，分组一定能够最终到达目的网络和目的主机。
(2)算法在计算上应简单。
(3)算法应能适应通信量和网络拓扑的变化，这就是说，要有自适应性。
当网络中的通信录发生变化时，算法能自适应改变路由以均衡各链路的负载。
当某个或某些结点、链路发生故障，或者修理好了再投入，算法应该能及时改变路由。
(4)算法应具有稳定性。
在网络通信量和网络拓扑相对稳定情况下，路由算法应该收敛于一个可以接受的解，不应该不断变化。
(5)算法应是公平的。
算法对所有用户是平等的，不能为了某个用户牺牲大部分用户。
(6)算法应是最佳的。
不存在一种绝对的最佳路由算法。
所谓“最佳”只能是相对于某一种特定要求下得出的较为合理的选择而已。
实际的路由选择算法，应尽可能接近于理想的算法。
路由选择是个非常复杂的问题
它是网络中的所有结点共同协调工作的结果。
路由选择的环境往往是不断变化的，而这种变化有时无法事先知道。
路由算法分类：
静态路由选择策略——即非自适应路由选择，其特点是简单和开销较小，但不能及时适应网络状态的变化。
动态路由选择策略——即自适应路由选择，其特点是能较好地适应网络状态的变化，但实现起来较为复杂，开销也比较大。
互联网采用的路由选择协议主要是自适应的(即动态的)、分布式路由选择协议。
互联网采用分层次的路由选择协议原因：
(1) 互联网规模非常大。如果让所有的路由器知道所有的网络应怎样到达，则这种路由表将非常大，处理起来也太花时间。而所有这些路由器之间交换路由信息所需的带宽就会使互联网的通信链路饱和。
(2) 许多单位不愿意外界了解自己单位网络的布局细节和本部门所采用的路由选择协议（这属于本部门内部的事情），但同时还希望连接到互联网上。
因此，把互联网划分成许多较小的自治系统，一般记为AS。
自治系统AS是在单一技术管理下的一组路由器，这些路由器使用一种自治系统内部的路由选择协议和共同的度量。
一个AS对其他AS表现出的是一个单一的和一致的路由选择策略。
在互联网种，一个大的ISP就是一个自治系统。
路由选择协议分为两大类：
(1) 内部网关协议IGP
在一个自治系统内部使用的路由选择协议，和互联网中其他自治系统选择什么路由选择协议无关。
目前使用最多的是RIP和OSPF协议。
(2)外部网关协议EGP
若源主机和目的主机不在一个自治系统中，这两个自治系统可能使用不同内部网关协议。二者传递数据，在两个自治系统边界交换时，就需要使用一种协议传递。
目前使用最多的时BGP的版本4，即BGP-4。
自治系统之间的路由选择叫做域间路由选择，自治系统内部的路由选择叫做域内路由选择。
RIP是内部网关协议IGP中最先得到广泛使用的协议，它的中文名字叫做路由信息协议。最大的优点就是简单。
RIP 是一种分布式的、基于距离向量的路由选择协议。
RIP 协议要求网络中的每一个路由器都要维护从它自己到其他每一个目的网络的距离记录。
距离定义：
从一个路由器到直接连接的网络的距离定义为 1。
从一个路由器到非直接连接的网络的距离定义为所经过的路由器数加 1。
RIP 协议中的“距离”也称为“跳数”(hop count)，因为每经过一个路由器，跳数就加 1。
这里的“距离”实际上指的是“最短距离”。因为从一个路由到另一个路由可能有多种走法。
有关距离的要点：
RIP 认为一个好的路由就是它通过的路由器的数目少，即“距离短”。
RIP 允许一条路径最多只能包含 15 个路由器。
“距离”的最大值为 16 时即相当于不可达。可见 RIP 只适用于小型互联网。
RIP 不能在两个网络之间同时使用多条路由。RIP 选择一个具有最少路由器的路由（即最短路由），哪怕还存在另一条高速(低时延)但路由器较多的路由。
RIP协议的三个特点：
(1) 仅和相邻路由器交换信息。
(2) 交换的信息是当前本路由器所知道的全部信息，即自己的路由表。
(3) 按固定的时间间隔交换路由信息，例如，每隔 30 秒。当网络拓扑发生变化时，路由器也及时向相邻路由器通告拓扑变化后的路由信息。
路由表的建立:
路由器在刚刚开始工作时，它的路由表是空的。只知道到直接连接的网络的距离（此距离定义为1）。
以后，每一个路由器也只和数目非常有限的相邻路由器交换并更新路由信息。
经过若干次更新后，所有的路由器最终都会知道到达本自治系统中任何一个网络的最短距离和下一跳路由器的地址。
RIP 协议的收敛过程较快。“收敛”就是在自治系统中所有的结点都得到正确的路由选择信息的过程。
这种算法的要点是这样的： 设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为距离更近更新的网络。
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 个路由信息。
优点：
实现简单，开销较小。
缺点：
RIP 限制了网络的规模，它能使用的最大距离为 15（16 表示不可达）。
路由器之间交换的路由信息是路由器中的完整路由表，因而随着网络规模的扩大，开销也就增加。
“坏消息传播得慢”，使更新过程的收敛时间过长。
坏消息传得慢解释：
网1出现问题，R1标记为16，但是R2发送了自己的路由信息，R1会更新自己路由表，将网1重新距离改为3，这样会不断更新，直到2者到网1都为16为止。
开放最短路径优先 OSPF 是为克服 RIP 的缺点在1989年开发出来的。
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。
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 位的序号，序号越大状态就越新。
(1)问候分组。用来发现和维持邻站的可达性。
(2)数据库描述分组。向邻站给出自己的链路状态数据库中所有链路状态项目的摘要信息。
(3)链路状态请求分组。向对方发送某些链路状态项目的详细信息。
(4)链路状态更新分组。用洪泛法对全网更新链路状态。这是最复杂、最核心的部分。
(5)链路状态确认分组。对链路更新分组的确认。
一些规定：
每隔10秒相邻的两个路由器就要发送一次问候分组，来确认是否可达。若有40秒没有收到某个相邻路由器的问候分组，就认为是不可达的，并立即修改链路状态数据库。
其余四种分组都是用来进行链路状态数据库的同步。
OSPF 还规定每隔一段时间，如 30 分钟，要刷新一次数据库中的链路状态。
由于一个路由器的链路状态只涉及到与相邻路由器的连通状态，因而与整个互联网的规模并无直接关系。因此当互联网规模很大时，OSPF 协议要比距离向量协议 RIP 好得多。
OSPF 没有“坏消息传播得慢”的问题，据统计，其响应网络变化的时间小于 100 ms。
指定路由器：
多点接入的局域网采用了指定的路由器的方法，使广播的信息量大大减少。
指定的路由器代表该局域网上所有的链路向连接到该网络上的各路由器发送状态信息。
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，对应上述四种报文中的一种。
路由器是一种典型的网络层设备。
路由器是互联网中的关键设备。
路由器的主要作用是：
连通不同的网络。
选择信息传送的线路。选择通畅快捷的近路，能大大提高通信速度，减轻网络系统通信负荷，节约网络系统资源，提高网络系统畅通率，从而让网络系统发挥出更大的效益来。
路由器是一种具有多个输入端口和多个输出端口的专用计算机，其任务是转发分组。
下一跳路由器也按照这种方法处理分组，直到该分组到达终点为止。
路由器的转发分组正是网络层的主要工作。
由上图可知，路由器的结构可以划分为两大部分：路由选择部分和分组转发部分。
路由选择部分：
路由选择也叫做控制部分，核心构件是路由选择处理机。
路由选择处理机的任务是根据所选定的路由选择协议构造出路由表，同时经常或定期地和相邻路由器交换路由信息而不断地更新和维护路由表。
分组转发由三部分组成：
交换结构 (switching fabric)：又称为交换组织，其作用是根据转发表对分组进行处理。
一组输入端口。
一组输出端口。(请注意：这里的端口就是硬件接口）
转发与路由选择的区别：
“转发”就是路由器根据转发表将用户的 IP 数据报从合适的端口转发出去。
“路由选择”则是按照分布式算法，根据从各相邻路由器得到的关于网络拓扑的变化情况，动态地改变所选择的路由。
路由表是根据路由选择算法得出的。而转发表是从路由表得出的。
在讨论路由选择的原理时，往往不去区分转发表和路由表的区别。
输入端口：
路由器的输入端口里面装有物理层、数据链路层和网络层的处理模块。
数据链路层剥去帧首部和尾部后，将分组送到网络层的队列中排队等待处理。这会产生一定的时延。
输入端口中的查找和转发功能在路由器的交换功能中是最重要的。
输出端口：
输出端口里面装有物理层、数据链路层和网络层的处理模块。
输出端口从交换结构接收分组，然后把它们发送到路由器外面的线路上。
在网络层的处理模块中设有一个缓冲区（队列）。当交换结构传送过来的分组的速率超过输出链路的发送速率时，来不及发送的分组就必须暂时存放在这个队列中。
数据链路层处理模块将分组加上链路层的首部和尾部，交给物理层后发送到外部线路。
分组丢弃：
若路由器处理分组的速率赶不上分组进入队列的速率，则队列的存储空间最终必定减少到零，这就使后面再进入队列的分组由于没有存储空间而只能被丢弃。
路由器中的输入或输出队列产生溢出是造成分组丢失的重要原因。
交换结构是路由器的关键构件。
正是这个交换结构把分组从一个输入端口转移到某个合适的输出端口。
实现交换有多种方法。常用交换方法有三种：
通过存储器
通过总线
通过纵横交换结构
通过存储器
当路由器的某个输入端口收到一个分组时，就用中断方式通知路由选择处理机。然后分组就从输入端口复制到存储器中。
路由器处理机从分组首部提取目的地址，查找路由表，再将分组复制到合适的输出端口的缓存中。
若存储器的带宽（读或写）为每秒 M 个分组，那么路由器的交换速率（即分组从输入端口传送到输出端口的速率）一定小于 M/2。
通过总线
数据报从输入端口通过共享的总线直接传送到合适的输出端口，而不需要路由选择处理机的干预。
因为每一个要转发的分组都要通过这一条总线，因此路由器的转发带宽就受总线速率的限制。
现代的技术已经可以将总线的带宽提高到每秒吉比特的速率，因此许多的路由器产品都采用这种通过总线的交换方式。
通过纵横交换结构
这种交换结构常称为互连网络。
它有2N条总线，可以使N个输入端口和N个输出端口相连接。
当输入端口收到一个分组时，就将它发送到与该输入端口相连的水平总线上。
若通向所要转发的输出端口的垂直总线是空闲的，则在这个结点将垂直总线与水平总线接通，然后将该分组转发到这个输出端口。
但若该垂直总线已被占用（有另一个分组正在转发到同一个输出端口），则后到达的分组就被阻塞，必须在输入端口排队。
