路由选择算法概述

2018年10月16日 0 作者 snowysong@live.com
阅读需要1分钟

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.影响路由决策的主要因素

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

0 0 vote
Article Rating