静态路由算法

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

0x00.固定路由

特性:

  1. 用一个中心路由目录维护路由。
  2. 节点只需相邻节点的信息。
  3. 对于数据包或虚电路作同样路由。

优点:

  1. 简单。
  2. 对具有稳定负载的可靠网络效率很高。

用矩阵表现固定路由

每列来看,1→2 经过2,可得节点1与节点2相邻,用1-2表示;1→3经过4,可得节点1和节点3不相邻,需要经过节点4…..依此类推可得每两两相邻的节点。


0x01.最短路径算法

测量路径长度的方法:

  1. 最小跳计数
  2. 最短距离
  3. 信道带宽
  4. 传输延迟
  5. 平均通讯量

最短路径选择方法

1.子网图

  1. 节点代表路由器。
  2. 弧线代表两个路由器之间的一条链路。

2.Dijkstra算法

找出一个节点到所有其他节点的最短路径。

e.g:使用Dijkstra算法计算A→D的最短路径

初始化:已知相邻节点与相邻节点间的长度。

step1.选择当前工作节点A

step2.标值其他节点到源的距离

此时B(2,A),2表示该点到源点A的距离,A表示与B相连的上一个节点。B(2,A),G(6,A),B点离圆点近,所以将B选择为工作节点。

step3.选择当前工作节点B

step4.标值其他节点到源的距离

此时,E(4,B),以此类推…….

3.扩散法(flooding)

将入境报文输出到所有输出线路(除去入境线路)。

e.g:使用扩散法将数据包从1传输到6

该模型初始化时没有任何路由信息,这是一种广播的方式。

数据包从1发出,2、4接收,2、4接收后进行拷贝,将数据包依次向下发送。

 

 

 

 

特性:

  1. 尝试所有可能的路由。
  2. 至少有一个包通过最小跳路到达目的端。
  3. 所有与源节点链接的节点都被访问。

优点:

  1. 具有一定健壮性。
  2. 简历虚电路。
  3. 将重要信息进行广播。

缺点:

包的拷贝数量呈指数增长。

解决方案:

  1. 在每个节点记下已发出包的表示。
  2. 在每个包中设置一跳计数。