• L(n) ：算法目前所知从节点 到节点 的最 算法目前所知从节点s到节点 到节点n的最 小代价路径的代价
—算法结束时，就是从节点s到节点 的最小代价 算法结束时，就是从节点 到节点 到节点n的最小代价 算法结束时 路径的代价
Dijkstra算法 算法
• Step 1 初始化
—T = {s} 目前的节点集合只有源节点 —L(n) = w(s, n) for n ≠ s 相邻节点的初始路径代价就是 链路代价
3 4
{1, 2, 4} {1, 2, 4, 5} {1, 2, 3, 4, 5} {1, 2, 3, 4, 5, 6}
2 2
1–2 1–2
4 3
1-4-3 1-4-5–3
1 1
1–4 1–4
2 2
1-4–5 1-4–5
1-4-5–6
5
2
—对于某些向所有节点散播的重要信息来说十分有用，被 用于某些路由选择策略的信息发布机制中
随机路由选择
• 使用随机路由选择时，为了重传收到的分组，节点 只选择一条输出链路。 • 这条链路是从除了分组到达时所经过的那条链路之 外的其他链路中随机 随机选取的。如果所有链路被选中 随机 的可能性都相等，那么节点可能会简单地以轮流方 轮流方 式使用输出链路。 • 改良方法是为每条链路分配一个概率，并根据概率 来选择链路。这个概率可以基于数据率或固定链路 代价的。 • 与洪泛式一样，随机路由选择不需要使用网络信息 。因为采取什么路由是随机决定的，所以实际的路 由往往既不是最小代价路由也不是最小跳数路由
Example of Dijkstra’s Algorithm
Results of Example Dijkstra’s Algorithm
Ite rati on 1 2 T L(2) Path L(3) Path L(4) Path L(5) Path L(6 ) ∞ ∞ ∞ 4 Path {1} {1,4} 2 2 1–2 1–2 5 4 1-3 1-4-3 1 1 1–4 1–4 ∞ 2 1-4–5 -
算法中变量
• • • • N ：网络中的节点集合 s ：源节点 T ：目前由算法合并的节点集合 w(i, j) ：节点 到j之间的链路代价 节点i到 之间的链路代价
—w(i, i) = 0 —w(i, j) = ∞ 如果两节点之间不是直接连接的 —w(i, j) ≥ 0如果两节点之间是直接连接的 如果两节点之间是直接连接的
Isolated Adaptive Routing（独立的自适应选择 ）
5.4 最小代价算法
• 所有分组交换网络的路由选择判决都是基于某种形式的 最小代价标准
— 如果这个标准取得是最小跳数，那么每条链路具有的值都是1 — 更常见的情况是链路的值与链路容量成反比，与链路当前负荷成 正比，或是这两者的结合。
• 与固定式路由选择相比，自适应路由选择的 与固定式路由选择相比， 缺点： 缺点
—路由选择的判决更加复杂，因而增加了网络节 点的处理负担 —大多情况下，自适应策略所依据的状态信息是 从一个地点收集却在另一个地点使用。此时， 需要在信息质量和额外开销之间寻求平衡。交 换的信息越多，且交换频率越快，则每个节点 所做的路由判决越好，但另一方面，这个信息 本身就是网络的负荷，它会导致性能下降。 —自适应策略可能反应过快，导致拥塞发生震荡 。如果反应太慢，那这个策略又没有什么实际 的用处
洪泛式 路由选 择
洪泛式技术的特点
• 洪泛式技术具有三个重要属性 三个重要属性： 三个重要属性 • 在源点和终点之间的所有路由都被尝试过
—非常稳健 —可用于发送紧急报文
• 因为所有路由都被尝试过，因此分组至少有一个副 本使用的是最小跳数路由到达终点
—可用于虚电路路由的最初建立
• 所有直接或间接与源节点相连的节点全部被访络信息，其工作过程如下： • 一个分组由源节点发送到与其相邻的每一个节点上 • 在各个节点上，收到的分组再次被传输到除分组到达时所 经过的链路外的所有输出链路。 • 最终会有几分这个分组的副本到达目的节点 • 这个分组必须具有某种唯一性的标识（如源节点和序号， 或许电路号和序号）以便目的节点保留所收到的第一份副 本，而丢弃其他副本。 • 为防止分组在网络中无穷无尽地传输，也可以让节点记住 所重传过的那些分组的标识，当该分组的副本再到达时被 丢弃；或者在每个分组中包含一个跳数计数器字段，每次 节点向前传输一个分组时，将该分组计数器值减一，当计 数器值为零时，该分组被丢弃。
2. 路由选择策略
• • • • 固定式路由选择（ 固定式路由选择（Fixed） ） 洪泛式路由选择（ 洪泛式路由选择（Flooding） ） 随机路由选择（ 随机路由选择（Random） ） 自适应路由选择（ 自适应路由选择（Adaptive） ）
固定式路由选择
• 固定式路由选择为网络中的每一对源节点和目的 节点选择一条永久的路由。 节点选择一条永久的路由。 • 这些路由是固定的，只有在网络拓扑结构发生改 这些路由是固定的， 变时， 变时，它们才有可能改变 • 因此，在设计路由时所使用的链路代价不可能是 因此， 基于通信量的动态改变
5.4.1 Dijkstra算法 算法
• Dijkstra算法思路如下 算法思路如下： 算法思路如下
—通过拓展路径以不断增加这条路径的长度 通过拓展路径以不断增加这条路径的长度 ，从而寻找给定源节点到所有其他节点之 间的路径。 间的路径。
• 该算法分阶段进行： 该算法分阶段进行：
—在第 阶段，已经判断出 个离源节点最近 在第k阶段 已经判断出k个离源节点最近 在第 阶段， 它们之间的代价最小） 的（它们之间的代价最小）节点具有的最 短路径，这些节点在集合T中 在第k+1阶 短路径，这些节点在集合 中。在第 阶 不在T中但具有到源节点最短路径的 段，不在 中但具有到源节点最短路径的 节点被加入到T中 当每个节点加入T时 节点被加入到 中。当每个节点加入 时， 就定义了它与源节点之间的路径。 就定义了它与源节点之间的路径。
固定 路由 选择
• 使用固定路由选择，数据报和虚电路在路由 使用固定路由选择， 选择时没有区别。从指定源节点到指定目的 选择时没有区别 节点的所有分组都沿相同的路由前进。 • 固定路由选择的优点是它的简洁性，并且在 一个具有稳定负荷的可靠网络中表现良好。 • 其缺点在于缺乏灵活性，无法对网络拥塞或 故障做出反应。
• 循环 循环step2-step3，当所有节点都已经加入T后算法终 ，当所有节点都已经加入 后算法终 止
Dijkstra’s Algorithm Notes
• 结束时， 与各节点x相关的值L(x)是从s到x的最小代 价路径的代价） • T定义了从s到各节点的最小代价路径 • 第2步和第3步每循环一次就向T中加入一个新节点并 定义了从s到该节点的最小代价路径
• （1）如果节点1选择1-3-6，节点2选择2-5-6，则 由于每条链路的业务量只有信道容量的一半，因 而时延很小。如果节点1选择1-4-6，节点2选择24-6，则链路4-6运载的业务量为10个单位，达到 了链路的最大容量，因而时延会很大。 • （2）节点2的输入业务量为15个单位，由于媒体 链路容量仅为10个单位，在仅使用一条路径情况 下，节点2至少要丢掉5个单位的业务量。如果节 点2将输入业务量在2-4-6和2-5-6之间分摊，节点1 选择1-3-6，则每条链路上的业务流量都不超过链 路容量的75%，因而实验较小。
4. 路由选择算法的分类
4. 路由选择算法分类
5. 对路由选择算法的要求
6. 路由算法的实现 路由算法的实现——路由表 路由表
7. 路由算法和流量控制的关系
5.2 电路交换网络中的路由
• 静态路由方式
—网络交换机被组织成树形结构或层次结构 —路由选择机制无法适应条件的变化
第五章 路由算法
5.1 路由算法概述
1. 路由算法的功能
2. 面临的问题
3. 路由选择的目的和要求
例 5.1
• 网络中有两个源节点 和一个目的节点。所 有链路的容量为10个 单位，两个源节点1 和2的输入业务量分 别为λ1 和λ2，试讨论 （1） λ1= λ2=5单位时 （2） λ1=5单位， λ2=15单位时，路由 选择对网络性能的影 响
—本地的（独立的） • 网络中的节点在为每个分组选择路由时会选择队列长 度Q最短的输出链路。它具有平衡输出链路负荷的效 果，但有些输出链路所指的大方向可能不正确。 • 加上对首选方向的考虑，就能改善上述缺陷。从节点 出发到每个目的站点的各条链路具有一个偏移值 • 仅根据本地信息的自适应机制很少使用 —相邻节点的 —所有节点的
• Step 3 更新最小代价路径
—L(n) = min[L(n), L(x) + w(x, n)] for all n ∉ T —如果后一项较小，则从 到n的路径变为从 到x的路径与从 如果后一项较小， 的路径变为从s到 的路径与从 的路径与从x 如果后一项较小 则从s到 的路径变为从 的链路衔接） 到n的链路衔接） 的链路衔接
Adaptive Routing - Advantages
• 目前为止，自适应路由选择仍是使 目前为止， 用最普遍的： 用最普遍的：
—从网络用户的角度来看，能提高网 从网络用户的角度来看， 从网络用户的角度来看 络性能 —有助于拥塞控制 有助于拥塞控制
自适应路由选择策略的分类
• 以信息源为依据，分为三类：
• Step 2 找到下一个节点
—从不属于 的相邻节点中找到到源节点路径代价最小的节 从不属于T的相邻节点中找到到源节点路径代价最小的节 从不属于 点x —将该节点 合并到 中 将该节点x合并到 将该节点 合并到T中 —向T加入一条边，这条边恰好在 上，且在 加入一条边， 向 加入一条边 这条边恰好在x上 且在L(x)中加入最小 中加入最小 代价元素
从端局X到端局Y的交替路由