佛山网站建设慕枫,网站制作 网页显示不全,网站的管理和维护,wordpress 网页目录目录
一、迪杰斯特拉算法
1. 术语定义
2. 算法描述
3. 举例说明
4. 构建从源节点到目的节点的路径
5. 构建最低费用路径树
6. 构建转发表
二、距离向量路由算法
1. 术语定义
2. 举例说明
3. 距离向量表
4. 更新距离向量表
5. 举例说明
三、距离向量路由算法 PLUS…目录
一、迪杰斯特拉算法
1. 术语定义
2. 算法描述
3. 举例说明
4. 构建从源节点到目的节点的路径
5. 构建最低费用路径树
6. 构建转发表
二、距离向量路由算法
1. 术语定义
2. 举例说明
3. 距离向量表
4. 更新距离向量表
5. 举例说明
三、距离向量路由算法 PLUS
1. 链路费用改变与链路故障
2. 毒性逆转
3. 毒性逆转的 BUG
四、LS 算法和 DV 算法比较
1. 消息复杂度
2. 收敛速度
3. 健壮性 一、迪杰斯特拉算法 迪杰斯特拉算法属于 LS 算法。 1. 术语定义 2. 算法描述 3. 举例说明
计算从 u 到所有可能目的节点的最低费用路径。 计算过程如表表中的每一行表示一次迭代结束时的算法变量值。 - 代表无穷/ 代表已经加入集合 N 。 4. 构建从源节点到目的节点的路径 5. 构建最低费用路径树 最低费用路径树不同于最小生成树。最小生成树保证连接所有节点的路径权值之和最小而最低费用路径树只是保证源节点到各目的节点的路径权值之和最小。因此最小生成树不用指出一个源节点而最低费用路径树必须指出一个源节点。源节点的不同会导致最低费用路径树的不同。 根据目的节点找出顺序及其前驱节点可以画出从源节点 u 到所有目的节点的最低费用路径树。 根据得到的最低费用路径树可以生成源节点 u 的转发表。 6. 构建转发表 默认路由 * 用于表示所有具有相同下一跳的表项。即将下一跳相同的项合并为一项用 * 表示目的节点。默认路由的优先级最低转发分组时只有找不到对应表项时才使用默认路由。 二、距离向量路由算法
1. 术语定义
最低费用路径的费用表示 2. 举例说明 所有 d 值都是邻居节点告诉源节点的源节点只知道它与邻居节点的直接链路的链路费用。 3. 距离向量表 初始时 x 并不知道 y 和 z 的距离向量因此都设置为无穷。 4. 更新距离向量表 5. 举例说明 初始节点只知道自己到邻居节点的链路费用。 开始后节点将自己的距离向量表发送给邻居同时接收邻居的距离向量表。然后根据邻居的距离向量表来更新自己的距离向量。 注意c(x, z) 等数值来源于图Dy 和 Dz 来源与邻居的距离向量表。此外这一时刻的 Dx 由 BF 公式计算而得跟上一时刻的 Dx 值无关不需要和上一时刻的 Dx 值比大小因此更新的 Dx 值可能更大也可能更小。 只要自己的距离向量更新了就需要发送给自己的邻居节点同时也要接收邻居节点发来的更新的距离向量。 第二次没有需要更新的距离向量因此不会再发送给邻居节点从而算法终止。 总结 ① 多次重复从邻居节点接收更新的距离向量并重新计算距离向量再向邻居节点发送更新的距离向量一直持续到没有更新的距离向量发出为止。 ② 算法进入暂时的静止状态直到某个链路的费用发生改变为止。 ③ 再次重复 ① 的操作。 三、距离向量路由算法 PLUS
1. 链路费用改变与链路故障 当一个节点检测到它与邻居节点之间的链路费用发生变化时就用 BF 公式重新计算其距离向量。若距离向量发生变化则通知其邻居节点。 1某链路费用减少时的情况 说明节点之间链路费用减少的 好消息 在网络中能迅速传播。 2某链路费用增加时的情况 Q为什么计算出来的新费用是错的 A由于链路费用改变Dz(x) 已经不等于 5 了但 y 还是使用了旧的 Dz(x) 。 产生选路回环为到达 x y 通过 z 选路z 又通过 y 选路。即目的地为 x 的分组到达 y 或 z 后将在这两个节点之间不停地来回反复直到转发表发生新的改变为止。 说明链路费用增加的 坏消息 传播得很慢当链路费用增加的很大时会出现 计数到无穷 问题。如链路费用 c(yx) 变为 10000c(zx) 变为 9999 时。 2. 毒性逆转
解决 计数到无穷 的方法毒性逆转。
毒性逆转假如 z 为了实现最低路径费用而需要通过 y 去到达 x则 z 告诉 y 它到 x 的距离是无穷大的从而 y 将不会再经过 z 到 x 。 假设 y 计算出它到达 x 的最低费用路径为y→z→...→x而 z 计算出它到达 x 的最低费用路径为z→y→...→x则会产生选路循环。因此如果 z 到 x 需要经过 y则让 y 到 x 的时候一定不要经过 z因为无论如何 y 经 z 到 x 的费用都会比 y 到 x 的大因为 z 到 x 包含了 y 到 x y 内心 OS还不如俺自己去找 x 。 前两步还是和之前一样的操作不过引入毒性逆转后x 或 y或 z 需要根据自己的下一跳来通知邻居节点其某个距离向量为无穷。 链路费用的改变打破了原本的安宁 z 根据 y 更新的距离向量来更新自己的距离向量。 虽然 z 的距离向量改变了但由于该路径还是会经过 y对于 y 仍应该是无穷因此不必再通知 y 了从而又进入了暂时静止状态。 3. 毒性逆转的 BUG Q毒性逆转可以完全解决计数到无穷的问题吗 A不能。如果是三个以上节点的环路则不能被毒性逆转技术检测到。 Dz(a) 的路径为z→y→...→a进一步这条路为z→y→x→...→a但是 z 只知道自己的下一跳是谁而不知道自己的下一跳又去经过了 x因此基于下一跳的毒性逆转策略失效了。 其它解决环路的方法
定义最大度量以防止计数至无穷大抑制计时器水平分割路由毒化触发更新 四、LS 算法和 DV 算法比较
1. 消息复杂度
LS 算法知道网络每条链路的费用需发送 O(nE) 个报文当一条链路的费用变化时必须通知所有节点。
DV 算法迭代时仅在两个直接相连邻居之间交换报文当链路费用改变时只有该链路相连的节点的最低费用路径发生改变时才传播已改变的链路费用。 2. 收敛速度
LS 算法需要 O(nE) 个报文和 O(n2) 的搜寻可能会振荡。
DV 算法收敛较慢。可能会遇到选路回环或计数到无穷的问题。 3. 健壮性 Q当一台路由器发生故障、操作错误或受到破坏时会发生什么情况 LS 算法路由器向其连接的一条链路广播不正确费用路由计算基本独立仅计算自己的转发表有一定健壮性。
DV 算法一个节点可向任意或所有目的节点发布其不正确的最低费用路径一个节点的计算值会传递给它的邻居并间接地传递给邻居的邻居。一个不正确的计算值会扩散到整个网络。
