路由选择：源节点和目的节点之间有多条传输路径，为收到的分组确定传输路径的行为。
路由选择是网络层的基本功能。
- 数据报子网：进入通信子网的每个分组，始终需要每个节点为其进行路由选择。
- 虚电路子网：建立虚电路时，每个节点要为呼叫请求分组做路由选择，建立后，不再需要。
路由选择包含了2个基本操作：
- 最佳路径的判定：相对2更复杂
- 网间信息包的传送（这个还不理解）
路由选择算法，Routing Algorithm
路由选择算法：路由选择的策略。
路由选择算法需要考虑很多技术要素：
- 选择最短路由，还是最佳路由
- 通信子网采用虚电路操作方式还是数据报操作方式
- 采用分布式路由算法，还是集中式路由算法：分布式——每个节点都参与路由，集中式——中央节点或始发节点决定路由
- 考虑网络拓扑、流量、延迟等网络信息
- 采用静态路由选择，还是动态路由选择
5.2.1 最优化原则，Optimality Principle
最优化原则
假设：节点 I 和节点 K 之间的若干条路由中，存在一条最佳路由“I - K”，"I - K"又经过了节点 J，那么其中的“ J - K”部分，也是节点 J 到节点 K 的若干条路由中的最佳路由。
汇集树，Sink Tree
根据最优化原则，可以推导出汇集树。
汇集树：目的节点作为根，网络中任一节点到该目的节点的最佳路由，组成的一棵树。
一个目的节点的汇集树并不唯一！
路由选择算法的目的：为所有节点找到汇集树。
汇集树的理论优势，以及实际应用
理论上讲：
汇集树是一棵树，其拓扑结构没有循环，因此分组沿汇集树传输必定在有限站数内到达目的节点，而且还是最佳路由。
但实际运行情况特别复杂：
- 链路经常被切断；
- 路由器（节点）经常停止工作后又恢复工作；
不同节点对子网的拓扑结构的理解不同。
- 不同的节点获取子网信息和汇集树信息的方法不同
最终，不同的节点对整个子网生成的汇集树可能差异很大。
5.2.2 静态路由选择算法
静态路由选择算法：不需要测量，不依靠网络的实时状态信息，由网管按照某种规则，手工建立映射表。
20世纪90年代以来，大多数优秀的路由选择算法都是动态的，但静态路由选择算法仍然有意义：
它能够为一些无法选择路由的数据包指定目标路由器，将其转发过去，弥补了动态路由选择算法的某些不足。
1. 最短路由选择算法，Shortest Routing（利用已知的静态”距离“）
最短路由算法简单易懂、应用广泛。
最短路由选择算法的基本思想： 用子网图描述拓扑结构，每个节点代表路由器，弧线代表链路，弧线上的数字是链路的权重（这里可以理解为长度）。要为一对节点选择一条路由，只需找到它们之间权重和最小的路径即可(可以理解为最短路径)。
链路的权重，在现实世界可能有多种含义：
- 站点数量
- 物理距离
- 信道带宽
- 平均通信量
- 通信开销
- 队列长度
- 传播时延
Dijkstra算法，迪杰斯特拉算法
勘误 原文：
>检查与B相邻的所有节点。如果B的标注与从B到所有检查的节点距离之和小于此节点的标注，就重新标注这个节点。”
正确的应该是：
>检查与B相邻的所有节点。如果B的标注与从B到所检查的节点距离之和小于此节点的标注，就重新标注这个节点。”
断句如下：
检查与B相邻的所有节点。如果（B的标注）+（从B到所检查节点的距离）< 所检查节点的初始标注（原标注），就以到B的距离重新标注这个节点。 每个节点都有一个标注值，代表了”从源节点沿着最佳路径到该节点”的权值（通常是距离）。
Dijkstra算法的步骤
根据源节点到“被检查节点”之间的距离（即链路的权重值），对“所检查节点”进行标注。
标注分为暂时性的（空心圆点），和永久性的（实心圆点）——当发现该标注代表了：从源节点到该节点的最短路径时。被设定为永久性标注的节点会作为新的源节点。
最开始时，不存在任何一条最佳路径，将除源节点外的所有节点都标注为无穷大（暂时性的）。
随着“从源节点到其他节点”的最佳路径的不断发现，代表最短路径的节点标注也不断的从暂时性修改为永久性的。
以书上的图为例，源节点为A，目的节点为D，中间节点若干。
- 将源节点A设为工作节点，标注为永久性的——实心圆点
- 用权值（例中为距离）标注“与A相邻的每一个节点”，标注时除了写明节点的权值，还应该注明源节点，比如 B(2,A)
- 检查完A以后，在已经标注的A相邻节点中，寻找标注最小的点（示例中为B），将其修改为永久标注，并作为新的工作点。
- 检查与B相邻的所有节点（A不用检查了，A已经是永久节点了），如果：\(B的标注 + 从B到所检查点的距离 \lt 所检查点的标注\)，那么：应该修改所检查点的标注=从B到所检查点的距离
在示例中，B的标注=2，从B到E的距离=4 ，E的标注=无穷，因此应该将E的标注修改为（4,B）
- 寻找与B相邻的所有节点中，标注最小的，将其设为永久性，并作为新的工作点。
值得一说的是： 图5-3 d 和 图5-3 e
G点在第一次和A的检查中，被标注为G(6,A）——图b
图d中，以E(4,B)为新的工作点，标注出 F(6,E) G(5,E)。
因为 E(4 + G(5 < G(6 ，因此应该重新标注G点，由此得到 G(5,E)!
2. 扩散法，Flooding（不需要测量，依靠固定规则）
扩散法，又叫“泛射路由选择法”、“洪泛法”，是最简单的静态路由选择算法。
源节点发出一个分组，子网中的某个节点收到该分组后，向“除来路外的所有链路”发送该分组（每经过一个节点，就会复制出新的分组，分组数量等于“节点相连的链路数-1”），最先到达目的节点的分组必定走过了最短的路径。而且，所有到达目的节点的分组所经路径的集合，就是所有可能的路径。
扩散法存在一个严重的问题：产生大量的重复分组，甚至无穷个分组。
解决重复分组的办法
1. 让分组携带站计数器 节点在转发分组前，会将其站计数器 - 1，对做减法后“站计数器=0”的分组，节点将其丢弃不再转发。
Q.如何设置站计数器的初值呢？
A.理想的情况：站计数器初值=源节点到目的节点的路径长度（站数量）。
实际上很多时候不知道路径长度，可以把站计数器初值设置成“子网直径（即网络中最大链路段数）”。
子网直径：从任一源节点到任一目的节点的最大中间链路段数。
2. 在节点记录分组，避免重复 基本思想：记录下分组传输的路径，避免分组被扩散进历史路径。
通信子网中，与主机相连的节点，称为“源端节点”，其余称为“非源端节点”。
每个非源端节点，对应每个源端节点都有一张记录表。
主机向源端节点发送多个分组，源节点赋予每个分组一个序号，再扩散出去。
非源端节点每次收到分组时，会在“相应的源端节点记录表”中记下分组序号，得到“源端节点：序号”这样一个表项。 据此，可以判断收到的分组是不是重复分组，如果是就丢弃，从而避免了再次扩散。
因此每收到一个分组就要写入表中，源端节点记录表会不断增长，为控制表的长度，加入一个计数器 K ，表示K的序号已经看到。序号小于K的分组为复制品，不再存放。（但这里有点儿问题，数据报并非按序到达，序号小于K的分组可能在后续到达吧，不理解这里的K是什么意思）。
扩散法的应用
扩散法很少被实际应用，但也有它特定的用途：
- 对强壮性要求很高的网络：军事网络，网络的拓扑结构可能被破坏
- 广播式数据交换：无线网络、分布式数据库应用——同步更新所有数据库
- 寻找网络的最短路径、最小传输延迟
选择扩散法（Selective Flooding）
选择扩散法是扩散法的改进版，节点不会把分组向每一条非来路链路发送，而只向与目标方向接近的那些链路发送（也会复制出多个分组）。
3. 基于流量的路由选择，Flow-based Routing
网络负载：单位时间内流经设备（单一节点、多个节点、通信链路、通信子网）的数据量，单位 bps。
最短路径路由选择算法和扩散法，只考虑了网络的拓扑结构，没有考虑网络负载。
在一些网络中，节点间的平均流量是相对稳定的或可预测的。进行静态路由选择时，完全可以把网络负载考虑进去。
基于流量的静态路由选择算法，兼顾了拓扑结构和网络负载。
基于流量的路由选择法的基本思想：
如果已知某条线路的负载和平均流量，就可以根据排队论计算出它的平均分组延迟。根据所有线路的平均分组延迟，可计算出流量的加权平均值，从而得到整个网络的平均分组延迟。（不懂排队论，这里并不真正的理解），具有最小平均延迟的线路（负载和节点处理能力匹配较好）自然是最佳线路。
至此，基于流量的路由选择问题，转化为：“寻找最小平均延迟线路”的路由选择算法。
P.S. 分组延迟：分组进入路由器后，先在缓冲区中排队，节点处理后再转发出去，这段时间称为延迟。
运用此方法的前提：
- 拓扑结构已知
- 通信量矩阵、线路容量矩阵已知
5.2.3 动态路由选择算法
因为静态路由选择算法不考虑网络的实时状态，因此实际运用中，动态路由选择算法才是主流。
动态路由选择算法：根据网络的实时状态进行路由选择的算法，也称为自适应路由选择算法。
- 优点：能适应网络流量、拓扑结构的变化，有助于改善网络性能。
- 缺点：算法复杂，会增加网络的负担，开销大。
1. 距离矢量路由算法
每个路由器都保存、维护了一张路由表（即矢量），其中记录了3个要素：
- 当前已知的所有路由器（包括自身）：作为目标路由表，这些路由器也是路由表的索引。“当前已知”表明子网中的路由器存在动态变化
- 从自身出发，“到达目标路由器的最佳线路”所要经过的相邻路由器
- 从自身出发，通过最佳线路到达相邻路由器的“距离”
路由表的更新，是通过与相邻路由器的不断的信息交换来实现的。
工作步骤：
假设：以“延迟”作为距离的度量标准，路由器A 具有3个邻居：XYZ，A知道它到XYZ的延迟。每隔T毫秒：
- 路由器A就向它的每个邻居发送一个列表（列表不是路由表），其中记录了从A到子网中任一路由器i（目标路由器）的延迟估计值 \(A_{i}\)。
- 同时，XYZ也向A发送它们自己的列表。 X 向 A 发送的一个列表中的一个表项显示：从 X 到目标路由器 i 的延迟估计值为 \(X_i\) 毫秒。
如果 A 到 X 的延迟是 \(X_{A}\)，可以得知：从 A 经过 X 到达目标路由器 i 的延迟估计值最大为 \(X_{i} + X_{A}\) 毫秒。 A 从 XYZ 都收到各自的列表，最终通过从 \(X_{i}+X_{A}\)、\(Y_{i}+Y_{A}\)、\(Z_{i}+Z_{A}\) 取最小值，作为从 A 到目标路由器 i 的延迟估计值\(A_{i}\)，写入 A 的路由表中。
在下一次的 T 毫秒间隔后，路由器A 将更新后的 \(A_{i}\)发送给XYZ，供它们计算、更新自己到目标路由器 i 的路由表。
说明：
如果 \(X_i\) 是 X 经过 A 到达 i 的延迟估计值，那么 A 到 i 的延迟估计值应该为 \(X_{i} - X_{A}\) ，此时从 A 经过 X 到达目标路由器 i 的延迟估计值为 \(X_{i} - X_{A} + 2\cdot X_{A} = X_{i}+X_{A}\)。
早期的ARPANET，和因特网的 RIP 路由信息协议，都使用了“距离矢量路由算法”。
2. 链路状态路由算法，Link State Routing
1979年以前，ARPANET一直使用距离矢量路由算法，之后，采用了链路状态路由算法。
至今，链路状态路由算法是主流的动态路由选择算法。比如广泛应用的开放式最短路径优先协议OSPF(Open Shortest Path First)，就采用了链路状态路由算法。
第一步.发现邻居节点
每个路由器向连接自身的每一条点到点线路，发送一个特殊的HELLO分组，线路另一端的路由器回送一个包含它唯一名称等信息的应答信息。
路由器记录下应答信息即建立了邻居节点的数据库。
第二步.测量线路开销（延迟）
路由器在线路上发送一个特殊的ECHO分组，另一端立即回送一个应答，将这个时间除以2，发送方路由器就记录下这个延迟的估计值。
第三步.创建链路状态分组
根据前两步收集到的数据，路由器就可以创建出“链路状态分组”，分组包含了：
- 发送方的标识：发出分组的源路由器的唯一名称，比如A
- 链路状态分组的序列号：源路由器每次收集到新的邻居节点、线路开销，都会生成新的链路状态分组，第一个的序号为1，以此类推，从而进行区别。
- 年龄：这个不知道是什么
- 邻居列表、自身到邻居的延迟
第四步.发布链路状态分组
源路由器生成了链路状态分组后，就需要用扩散法将其发布到子网中。
每个路由器在收到链路状态分组后，会在一个表中记录下源路由器和序列号，当扩散产生的重复分组再次到达路由器时，通过查询记录表会发现它是重复分组，从而将其丢弃。
而且，序列号还有记录分组产生时间的作用：如果一个路由器已经收到了某源路由器产生的序号为 k 的分组，随后又收到了同一源路由器序号为 j 的分组，j<k ，那么可以直接将其丢弃，因为 j 所记录的链路状态已经过时了。
第五步.计算新的路由
如果一个路由器，已经在扩散法的影响下，收到了子网中所有路由器产生的链路状态分组，那么就可以构造出完整的子网图（包括拓扑结构、线路开销等信息）。
此时，在自身节点上运用最短路由选择算法（比如Dijkstra算法），就可以生成自身的路由表。
最终，每一个路由器都生成了自己的路由表，网络开始正常工作。
5.2.4 移动主机的路由选择
固定主机：物理位置几乎永远固定的主机，通常具有永久性的地址。
迁移主机：经常从一个固定位置迁移到另一个固定位置，移动中与网络断开，到达位置后才接入网络。
漫游主机(Mobile Host)：有原始接入点（路由器）、可以随时移动，移动中也利用网络传输数据的主机。或者说，离开了原始站点还继续连接网络的主机。通常具有变化的地址。
移动主机只是网络中的一部分，仍然还有很多固定主机。
对这些包含移动主机的网络来说，移动主机的路由算法的目标是：
能够在“地址不变的固定主机”和“地址可变的移动主机”之间进行路由选择，将分组正确的送达。
移动式主机的出现，引出了一个问题：
网络如何找到移动主机，或者说，如何把移动主机接入网络
假设有一个网络系统，若干的LAN、MAN、无线蜂窝单元，通过一个WAN（内含路由器和主机）连接在一起。这些LAN、无线蜂窝单元称为“区域”。
每个区域中，有两种代理：
- 一个主代理：管理属于本区域，但此时移动到其他区域的移动主机。
- 一个或多个外地代理：管理不属于本区域但来到该区域的移动主机。
一个移动用户进入其他区域时，以有线或无线的方式接入网络时，必须在该区域的外地代理中进行登记，称为登录。
登录过程：
- 外地代理定期向区域广播一个分组，告知各主机自己的地址等信息，新来的移动主机可以被动等待这个消息。移动主机也可以广播一个分组，主动询问外地代理的信息。
- 与外地代理联系上以后，移动主机需要提供：原区域的信息（比如在原区域的地址）、当前数据链路层地址（类似于物理地址）、一些安全性信息
- 外地代理与移动主机所属的原区域的主代理联系，核实移动主机是否真的来自那里。
- 外地代理从主代理得到确认后，在它的记录表中增加一项，并通知移动主机登录成功
至此，就完成了移动主机接入其他区域的工作。
当用户离开其他区域时，应该告知外地代理注销自己，但大多数情况下都不是这样。
发给移动主机的分组，会先被原区域的主代理收到，然后它再转发给移动主机，如果此时移动主机已经移动到其他区域，那么主代理会查找移动主机的新位置，找到目前登录的外地代理。之后，主代理会做2件事：
- 将发给移动主机的分组，装入一个外地分组的有效载荷中（用外地代理地址再次封装了一个分组），再将该外地分组发给外地代理。
- 告诉发送者，将分组装入外地分组的有效载荷字段，直接发往外地代理所在的地址。
外地代理最终会把分组转发给移动主机。
5.2.5 广播路由选择 , Broadcasting
广播：给子网中所有的路由器发送分组。
实现广播路由的方法有几种。
1. 逐个发送，最笨的办法
源节点向每个节点依次发送分组，实现广播。
缺点：
- 浪费带宽：节点可能会共享链路，而这种方法重复使用了链路
- 源节点必须知道所有目标节点的地址
2. 扩散法
扩散法不适合点对点的通信，但很适合广播式通信。
扩散法的缺点：产生大量重复分组，浪费带宽。
3. 多目标路由，Multi-destination Routing
发出的每个分组，或者包含了多个目标地址，或者包含了一个指示了目标节点的位图(bitmap)。
当路由器收到一个多目标分组时，会计算出所有的“必要的输出线路”（必要线路：到达至少一个目标节点的最佳线路）。
假设计算出3条必要线路：甲乙丙，甲通向目标 i，乙通向目标 j 和目标 k，丙通向目标 l 和目标 m 目标 n 。
路由器会为每一条必要线路生成原分组的副本，但仅包含了“该条线路所连接目标的地址”：
- 线路甲的分组副本 P1：仅包含了地址 i
- 线路乙的分组副本 P2：仅包含了地址 j k
- 线路丙的分组副本 P3：仅包含了地址 l m n 。
这样，原分组中的目标集合被分散到了各必要线路上。多目标分组每经历一个节点的拆解后，最终只包含一个目标，就和普通分组没有区别了。
多目标路由方法就如同单个地址的分组一样，只不过当多个分组必须沿着同样的路径被转发的时候，其中一个分组承担全部的费用，而其他的分组都是免费搭乘的。
这段话不理解，多目标分组是在一个分组内包含了多个目标地址，这和多个分组都需要经过一段链路有什么关系呢(不论它们最终的目标是否相同）？所以感觉这段话没有意义。
4. 显式利用：以“广播源”节点为根的生成树
生成树 (Spanning Tree) 是子网的子集，由：所有的路由器 + 不构成环的部分链路（没有循环）所构成。
P.S. 生成树包括了汇集树。
每个路由器都知道自己的哪些链路属于“以广播源为根的生成树”，当广播分组到来时，它就将其复制并发送到“生成树中除来路以外的”所有链路中。
注意：
- 以广播源节点为根的生成树并不唯一，但在这里不影响，只要找出一个就行了
- 所有的路由器都必须使用以广播源节点为根的同一棵树！否则会出问题
优点：1. 最佳的利用了带宽（涉及的线路必要又不多余）； 2. 复制出了最少的分组。（最优化原则）
缺点：子网中的每个路由器都必须知道：以广播源为根的同一棵生成树，这就要求每个节点必须获取整个网络的状态信息——比如采用链路状态路由算法。如果采用了距离矢量路由算法，则无法获取生成树信息。
5. 逆向路径转发，Reverse Path Forwarding
如果路由器不知道生成树的信息，根据“广播分组的来路”是否是“当前路由与源节点的首选链路”，也可以实现“利用以广播源为根的生成树方法”近似的效果。
基本思想：
当一个广播分组到达某个路由器时，路由器对分组的来路进行检查：
- 如果来路是当前路由器向源节点发送分组的首选线路：说明广播分组是沿着最佳路径过来的，是到达当前路由器的第一份副本（最佳路径必然最先到达）。
- 如果来路不是当前路由器向源节点发送分组的首选线路：该分组属于非最佳路径的其他节点生成的重复分组，应该丢弃。
具体操作不再描述，其实就是根据生成树来判断分组是否重复。
优点：不需要路由器都知道生成树（只需要知道与源节点的最短路径即可），也不需要分组中携带多个目标地址或位图，也不需要扩散法中对重复分组的控制。因此它效率相对合理，容易实现。
5.2.6 多播路由选择
什么叫多播，和广播的区别
多点播送，简称多播，又称组播，Multicasting。
分布在各主机的进程，以组的方式协同工作。
组中的进程经常需要给组中其他所有的成员发送信息。
P.S. 组实际容纳的是进程，而非主机！多个进程可以共存于一台主机中，也可以分散在多个主机中。
如果组的规模比较小，那么可以用点对点的方式每个其他成员发送信息。
如果组的规模比较大，那么就不能逐个点对点的发送了，可以采用广播，但可能产生一些问题，比如：
- 组的成员数量虽然多，但相对整个网络却很小，大多数节点对该分组没有兴趣：组有1000台主机，网络有100万个节点
- 组内的信息不应该让整个网络的节点看到
多播路由选择
适用于多播的路由算法，称为多播路由选择 Multicast Routing。
多播传输需要对组进行管理：
- 需要创建、销毁组的方法
- 允许进程加入、离开组
对于主机来所，自己是否有进程加入了某个组，需要由进程来告知它。
对于路由器，它连接的哪些主机属于哪个组时需要明确的。
当主机和组的从属关系发生变化时，要么是主机告诉路由器，要么是路由器定期询问自己连接的主机。
路由器获取到自己的主机属于哪些组后，将其告知邻居（类似于链路状态分组）。
如何实现多播
子网中的每个路由器，都需要生成一棵以自己为根的生成树。
当某个主机中的某个进程向自己所在的组发送多播分组时，与主机相连的第一个路由器就检查以自己为根的生成树，把该树中“不通向该组其他成员主机的路由器”的链路修剪掉，得到一棵只通向同一组的成员主机的生成树。多播分组最终沿着修剪后的生成树传播。
修剪链路的工作，应该从每条路径的末端开始，逐步向根节点前进，去掉所有不属于改组的路由器。