3.网络层技术：路由选择

网络层技术：路由选择

路由选择

选择标准

路由选择是设计分组交换网中最关键最复杂的问题。路由选择是指在交换过程中选择一条经过网络的路径，称为路由（routing）。通常站点到站点之间会有多条可行路由，因此需要选择经过哪一条路由。通常路由选择的过程中需要考虑：
- 正确性（correctness）
正确地找到终点。
- 简洁性（simplicity）
通常指可以找到最小花费的路由，花费中包括了钱、时间以及其他通信资源等。
- 鲁棒性（robustness）
可以在网络遇到突发事件时做出正确响应。
- 稳定性（reliability）
路由上的数据率等特性，以及一些功能能够稳定正常执行。
- 公平性（fairness）
路由的选择需要考虑这样的选择对整个网络的资源利用率都高效。
- 最优性（optimality）
选择的路由开销最小，表现最突出。
- 高效性（efficient）

选择要素

在选择时需要考虑的要素如下表所示：

类型	标准
性能评估标准	跳数、代价、时延、吞吐量
判决时间（做出路由选择的时间点）	每个分组发送时决定路由、会话建立/建立连接时决定路由
判决地点（做出路由选择的位置）	每个节点（分布式）、中心节点（集中式）、源节点（源点式）
网络信息更新时间	连续的、周期的

性能评估标准

性能评估的两个基本标准是最小跳数标准和最小代价标准。
最简单标准是选择经过网络的最小跳数路由，即途经节点的数量最少（路由上中间结点数+1即为跳数），这种标注容易测量，且使消耗的的网络资源最少。
最小代价标准是最小跳数标准的延伸，在评估时除了要考虑跳数外，还要考虑数据率、时延等等。

判决时间

判决时间是做出路由选择的时间点，基本上是由选择无连接的分组交换还是面向连接的分组交换确定的（基于分组的还是基于虚电路的）。在无连接的分组交换中，结点在发送每个分组时就需要为每一个分组单独决定路由。而面向连接的分组交换中，在建立连接的过程中路由需要被选择，通信过程中没有路由选择的过程。

判决地点和网络信息资源

判决地点是做出路由选择的位置，最常见的是分布式路由选择，即网络中的每一个结点负责为接收到的分组选择发送时的路由。但是路由选择要求公平性，这暗示了需要要求进行路由选择的结点需要具备知道网络中其他结点状态的能力。对于网络中的每个结点，要求其知道整个网络中其他结点的状态所需要的开销是巨大的，因此结点在选择时一般只会了解相邻结点的网络状态。因此，单个结点已知的信息有限，其做出的路由选择对于整个网络而言只能是局部最优的解决方案。
集中式路由选择则是将路由选择的功能交给了某些设定的节点执行，这样的结点一般具有知道整个网络中大部分结点状态的能力，因此对分组发送做出的路由选择方案能够更从全局的角度上考虑。但是这样的选择缺点是稳定性较低，如果这些结点失效，那么整个网络的路由选择将无法进行。

信息更新定时

对于固定式路由，其不需要信息更新定时，虽然能够减少由于同步带来的网络负担，但是无法对拥塞和网络故障产生反应。
对于动态路由，如果没有可以利用的信息，也就不存在信息的更新。有用信息越多，更新频率越快，网络就更可能做出良好的路由选择，对网络资源的消耗更大。因此，相较于分布式路由选择，采用集中式路由选择往往要求更高的信息更新频率。
结点的信息更新包括结点自身的信息（本地信息）更新和网络中其他结点的信息更新。本地信息更新的本质是连续性的。对于相邻结点和所有结点的更新定时取决于路由选择策略。使用自适应策略，信息需要经常更新，使路由选择判决能够适应变化的条件。

路由策略

静态路由

静态路由为网络中每一个源的终端选择一条永久固定的路由。路由通过最小代价算法生成，生成后的路由会通过一张或多张链表(称为路由表)表示节点之间的映射关系并存储在结点中，其中每一个结点的路由表只关心数据分组的上一个来源的编号和需要转发到的下一个结点的编号。
如下图所示。

当数据分组到达某个结点时，结点根据路由表上记录的规则将某个来源的分组转发到对应的下一个结点上。
从某个指定的源点到某个指定的终端中的所有分组都会沿着相同的路由前进。只有在网络的拓扑结构发生改变时，静态路由表才会发生改变。
静态路由的优点是其简洁性，在具有稳定负荷的、可靠的网络中表现良好。其缺点是缺乏灵活性，无法对在网络拥塞和结点故障时进行调度。

洪泛

洪泛(flooding)不需要任何网络信息。洪泛策略中，网络中的每个结点在接收到某个分组后会复制该分组，并且转发给每一个相邻接点。最终终端会收到多份相同的分组。由于每个源点发送的分组都有唯一的编号，因此终端可以根据编号将编号相同的分组丢弃。

洪泛有三个重要属性：
- 源点和终端之间所有的可能路由都被尝试过，因此只要源点和终点间有一条路由能够正常工作，分组都会成功交付到源点。
这样的性质使得洪泛的鲁棒性非常的强，因此洪泛路由常用于广播，目的是：
- 使网络中的所有结点都能收到消息（尤其是应急通信场景）
- 知晓网络中所有结点的网络状态
- 源点和终端之间所有的可能路由都被尝试过，因此可以找到最小跳数路由。
- 所有直接或间接地与源点相连的节点都会被访问到。

洪泛式路由的优点是鲁棒性强，同时可以访问到尽可能多的结点，在使用洪泛式路由时不需要知道网络的状态，执行相对比较简单。
其缺点是洪泛的通信负荷量非常高，极容易产生拥塞。

随机路由

随机路由保留了洪泛的的简洁性，同时降低了通信量，其具体策略是：
网络中的每一个结点根据链路的数据率、有概率地为选择一条路由。其中最经典的随机路由分配机制是轮盘赌，在轮盘赌法则中，即某条链路的数据率为\(R_i\)，这条链路被选择作为路由的概率为：
\[P_i=\frac{R_i}{∑_jR_j}\] 随机路由只需要获得节点自身的数据率信息，不需要获得整个网络中其他节点的状态。由于随机性的选择，选择到的路由极有可能不是最小代价路由或者最小跳数路由，因此通信负荷量并非最小。

自适应路由

顾名思义，在自适应路由中，路由的选择根据网络的状态的改变而改变。自适应路由需要通过一些机制知道整个网络的状态。此外，自适应路由的根据网络状态更改的响应时间选择非常重要：如果对网络状态的响应过快，资源利用率低，并且容易引起网络波动。如果对网络状态的响应过慢，收集到的网络状态信息时效性差，路由判决的有效性差。
因此相比于前几种路由策略，自适应路由的决策更加复杂。
但是自适应路由有非常好的表现，尤其是当网络出现拥塞时，自适应路由可以及时调整路由缓解拥塞。
基本上所有的分组交换网络都采用自适应路由。

不同交换方式采取的路由策略

电路交换

电路交换在会话的过程中建立静态路由：每个节点都做最小代价算法决定下一个节点，并建立映射关系。路由建立后通信资源会被分配给建立的连接。连接被建立后，各个节点上的传输是透传的。

分组交换

• 虚电路
  虚电路和电路交换的路由是静态的，为会话确定。
  虚电路，比如ATM（ATM结点收到信元后会根据头部中的类型决定是否读内容），建立连接时，网络中的结点需要读内容（解包并移交给上层）。一旦连接被确定，映射关系会被结点储存。相较于电路交换，在映射关系建立后，虚电路不会为通信分配固定带宽。
  电路交换和虚电路的路由建立过程是基本上相同的。电路交换中，建立连接的信道和通信的信道是不同且固定的。虚电路中没有信令和消息信道之分，靠分组的首部确定。

• 数据报
  数据报的路由是动态的，为每个分组确定。
  数据报中每一个分组都是独立的，每个节点都需要对每一个分组处理。数据报网络中的节点也不会关心分组的具体内容，只关心分组的首部。结点根据网络状态和头部信息利用最小代价算法决定下一个结点。每一个数据包的路由受到结点收到时刻时的网络状态的影响。