0x00.路由选择算法的分类

路由选择算法大致可分为两种：非自适应算法（静态路由）和自适应算法（自适应算法），常用的为自适应算法。

非自适应算法：部根据实测或估计的网络的当前通信量和拓补结构来作路由选择。

自适应算法：根据拓补结构、通信量的变化来改变其路由的选择。

前提：路由节点间交换网络状态信息，信息越多，做出的路由决策越好，但信息过多辉加重网络负担导致性能下降。

缺点：

1. 路由决策复杂，从而加重网络节点的处理负担。
2. 依赖于信息状态，这些状态信息在一个地方收集，却用在其他地方，从而加重了网络的交通负担。
3. 不能太快和太慢，自适应决策太快辉引起拥塞抖动，太慢又不符合自适应的初衷。

优点：

1. 可提高网络性能
2. 有助于拥塞控制

0x01.路由选择算法的特征

1. 正确性（correctness）：能为数据链路找到正确的路径。
2. 简单性（simplicity）：计算路由的系统开销要小，提升整体效率。
3. 健壮性（robustness）：及鲁棒性，出现问题是可保证整体数据，不丢失不中断。
4. 稳定性（stability）：运行一段时间的稳定运行。
5. 最优性（optimality）：对不同优先级的数据包提供不同的优先级策略。
6. 公平性（fairness）：中信，中性。
7. 有效性（efficiency）：使用路由表进行数据传递时的开销要小于不适用路由表的开销。

0x02.路由技术元素

1.性能标准（常用的）

• 跳计数：从远端到目的端经历了多少路由的转发，每经历一个，跳计数+1.
• 成本：通常和每一条链路有关，如链路长度等（待补充）。
• 延迟：从源端到目的端的延迟，延迟越小越好。
• 吞吐量：从源端到目的端的吞吐量，吞吐量越大越好。

2.网络信息源

• 无：有的算法不需要网络信息就可以进行路由选择。
• 局部：本地的路由节点可以知道它所链接的线路的概况。
• 邻接节点：从与该节点相邻的节点获取网络信息，所需网络信息为算法所需网络信息。
• 全部节点：如果该算法运行前提为全部网络信息，网络信息源变为全部信息。

3.信息更新时间（是信息源和路由决策的函数）

• 连续：连续不断的更新。
• 定期：每隔一段时间采集网络信息。
• 负载变化：当网络负载发生变化后将网络信息通知所有节点。
• 拓补变化：当网络拓补结构发生变化后将网络信息通知所有节点。

4.决策时间（什么时间生成路由表）

• 包（数据包）：为每个包单独作路由决策。
• 会晤（虚电路）：在2个用户建立虚电路时就要进行决策。

5.决策地点（什么地点生成路由表）

• 每个节点（分布）：在每个节点上进行，完全分布式。分布成本高，但鲁棒性更好。
• 中心节点（集中）：在某些中心节点进行，如网络（控制）中心集中进行决策。当中心节点崩溃整个路由崩溃。
• 原始节点（源端）：在数据包的源端进行路由选择，而非网络进行选择。

6.性能标准

• 最小跳计数。
• 最小成本，成本与数据率有关（数据率越高，成本越低），成本与当前排队延迟有关。最短路径：1-3-6 ，成本：10

         最小成本路径：1-4-5-6 ，成本：4

7.影响路由决策的主要因素

• 故障：当一个节点故障或一段干线故障后，就不再用作路由的一部分。
• 拥塞：当网络的一部分严重拥塞时，要求路由绕开拥塞部位而不是继续通过拥塞区域。