习题_28_34.md

P28 考虑下图所示的网络，假设每个结点初始时知道到它每个邻居的费用。考虑距离向量算法，并显示在结点 z 中的距离表表项。

P29 考虑一个一般性拓扑（即不是以上所显示的特定网络）和一个同步版本的距离向量算法。假设每次迭代时，一个结点与其邻居交换其距离向量并接受它们的距离向量。假定算法开始时，每个结点只知道其直接邻居的费用，在该分布式算法收敛前所需的最大迭代次数是多少？评估你的答案。

• 对于一个同步版本的距离向量算法有 4 个结点 A - B - C - D，在第一次交换彼此的距离向量后，A 知道了到 C 两跳的最短路径，这是 B 告诉它的。C 知道了到达 A 两跳的最短路径，这是 B 告诉它的，B 知道了到达 D 两跳的最短路径，这是 C 告诉它的。但是 A 不知道如何到 D，D 也是如此。在下一次交换距离向量后，所有结点都知道了如何到达彼此的信息。因为 B 知道如何到 D，B 告诉了 A，因此 A 知道了如何到 D。因此，假设 A 是 B 的邻居，在 B 向它的所有邻居交换了一次距离向量后，所有 B 的邻居都知道了到 A 的一跳或者两跳的最短路径。因此假设图的 "直径" 为 d，那么在迭代 d - 1 次后，所有结点都知道如何抵达彼此，那么算法将开始收敛。

P30 考虑下图所示的网络段。x 只有两个相连邻居 w 与 y。w 有一条通向目的地 u (没有显示)的最低费用路径，其值为 5；y 有一条通向目的地 u 的最低费用路径，其值为 6。从 w 与 y 到 u (以及 w 与 y 之间)的完整路径没有显示出来。网络中所有链路费用皆为正整数。

a. 给出 x 对目的地 w, y 和 u 的距离向量

b. 给出对 c(x, w) 或 c(x, y) 的链路费用的变化，使得执行了距离向量算法后，x 将通知其邻居有一条通向 u 的新最低费用路径。

c. 给出对 c(x, w) 或 c(x, y) 的链路费用的变化，使得执行了距离向量算法后，x 将不通知其邻居有一条通向 u 的新最低费用路径。

• a.

  • Dx(w) = 2，Dx(y) = 4, Dx(u) = 7

• b.

  • 现在到 u 的路径为 x - w - u
  • 考虑如果减小 c(x, y)，那么即使 c(x, y) = 1，最小费用的路径仍然是 x - w - u = 7，所以减小当前链路中的费用，不会改变最小费用路径
  • 考虑增大链路的费用，当 c(x, w) 增加到 7 时，Dx(u) = min{7 + 5, 5 + 6} = 11，因此 x 将通知其邻居有一条通向 u 的新最低费用路径。

• c.

  • 保证 c(x, w) 在小于 7 范围内的增加，以及减少 c(x, w) 或减少 c(x, y) 都不会改变 x 到 u 的最低费用路径。

P31 考虑如图 4-30 中所示的 3 个结点的拓扑。不使用显示在图 4-30 中的费用值，链路费用值现在是 c(x, y) = 3, c(y, z) = 6, c(z, x) = 4。在距离向量表初始化后和在同步版本的距离向量算法每次迭代后，计算它的距离向量表（如我们之前对图 4-30 讨论时做的那样）

P32 考虑在距离向量路由选择中的无穷计数问题。如果我们减小一条链路的费用，将会出现无穷计数问题吗？为什么？如果我们连接没有链路的两个结点，会出现什么情况？

• 减小链路的费用不会出现无穷计数问题，因为减小链路的费用不会出现环，而增加链路费用会导致出现环。
• 连接两个没有链路的结点，相当于把链路费用从无穷大减小到有限。

P33 讨论在图 4-30 中的距离向量算法，距离向量 D(x) 中的每个值不是递增的并且最终将在有限步中稳定下来。

• Bellman-Ford 方程只会减小每个结点的距离向量，而没有增加操作，如果没有改变发生，那么就不会发送任何报文，因为链路费用是有限的，因此距离向量将会经过有限步骤最终达到稳定。

P34 考虑图 4-31。假定有另一台路由器 w, 与路由器 y 和 z 连接。所有链路的费用给定如下：c(x, y) = 4, c(x, z) = 50, c(y, w) = 1, c(z, w) = 1, c(y, z) = 3。假设在距离向量路由选择算法中使用了毒性逆转。

a. 当距离向量路由选择稳定时，路由器 w, y 和 z 向 x 通知它们的距离。它们告诉彼此什么样的距离值？

b. 现在假设 x 和 y 之间的链路成本增加到 60。即使使用了毒性逆转，将会存在无穷计数的问题吗？为什么？如果存在无穷计数的问题，距离向量路由选择需要迭代多少次才能再次达到稳定状态？评估你的答案。

c. 如果 c(y, x) 从 4 变化到 60，怎样修改 c(y, z) 使得不存在无穷计数问题。

• a.

  • 当距离向量路由选择稳定时，各结点距离向量如下图所示
  • 
  • 当距离向量路由选择稳定时，路径的毒化如下所述
    • 对于 x 结点
      • 到达 y 下一跳是 y，因此通告 y Dx(y) = ∞
      • 到达 w 下一跳是 y，因此通告 y Dx(w) = ∞
      • 到达 z 下一跳是 y，因此通告 y Dx(z) = ∞
    • 对于 y 结点
      • 到达 x 下一跳是 x，因此通告 x Dy(x) = ∞
      • 到达 w 下一跳是 w，因此通告 w Dy(w) = ∞
      • 到达 z 下一跳是 w，因此通告 z Dy(z) = ∞
    • 对于 w 结点
      • 到达 x 下一跳是 y，因此通告 y Dw(x) = ∞
      • 到达 y 下一跳是 y，因此通告 y Dw(y) = ∞
      • 到达 z 下一跳是 z，因此通告 z Dw(z) = ∞
    • 对于 z 结点
      • 到达 x 下一跳是 w，因此通告 w Dz(x) = ∞
      • 到达 y 下一跳是 w，因此通告 w Dz(y) = ∞
      • 到达 w 下一跳是 w，因此通告 w Dz(w) = ∞
    • 下面是上述毒化的图示
    • 
  • 对于 z 来说
    • 从上图中可以看出，w 是 z 到 x 路径上的下一跳，因此 z 将向 w 通告，Dz(x) = ∞, 这样的话，假设 c(y, w) 增加，那么由于 w 知道（其实它被欺骗了）它无法通过 z 到达 x，因此它不会试图把分组传递给 z，也就不会形成环。
    • 但是，y 不是 z 到 x 路径上的下一跳，z 其实不关心 w 如何将分组传递给 x，所以 z 将继续向 y 通告，Dz(x) = 6
  • 对于 w 来说
    • y 是 w 去往 x 的下一跳，因此 w 将向 y 通告，Dw(x) = ∞，这样的话，假设 c(y, x) 增加，那么由于 y 知道 (其实它被欺骗了)它不能通过 w 到达 x，因此它不会试图将分组传递给 w，也就避免了形成环。
    • 由于 z 不是 w 去往 x 的下一跳，因此 w 向 z 通告，可以经由它以 Dw(x) = 5 到达 x
  • 对于 y 来说
    • y 的下一跳就是 x，因此 y 将通告 z 和 w, 它可以以 Dy(x) = 4 到达 x

• b.

  • 假设 c(x, y) = 60，那么现在算法运行轨迹如下：

  • 

  • 从图中可以发现，即使使用了毒性逆转，仍然出现了无穷计数的问题。从 t1 时刻 c(x, y) 增加到 60 开始，分析如下

    • t1 y 知道通过 z 能够以 3 + 6 = 9 到达 x，因此从 y 去往 x 的路上，下一跳是 z，并毒化 z -> y，同时将通告邻居 w 和 z

    • t2 w 收到 y 的通告，知道通过 y 能够以 9 + 1 = 10 到达 x，因此从 w 去往 x 的路上，下一跳是 y，并毒化 y -> w，同时通告邻居 y 和 z

    • t3 z 收到 w 的通告，知道通过 w 能够以 10 + 1 = 11 到达 x，因此从 z 去往 x 的路上，下一跳是 w，并毒化 w -> z，同时通告邻居 y 和 w

    • t4 y 收到 z 的通告，知道通过 z 能够以 3 + 11 = 14 到达 x，因此 y 去往 x 的路上，下一跳是 z，并毒化 z -> y，同时通告邻居 w 和 z

    • t5 w 收到 y 的通告，知道通过 y 能够以 14 + 1 = 15 到达 x，毒化来路，通告邻居

    • t6 z 收到 w 的通告，知道通过 w 能够以 15 + 1 = 16 到达 x，毒化来路，通告邻居

    • t7 y 知道能够以 3 + 16 = 19 到达 x，毒化来路，通告邻居

    • t8 w 知道能够以 20 到达 x，毒化来路，通告邻居

    • t9 z 知道 21 到达 x

    • t10 y 知道 24 到达 x

    • t11 w 知道 25 到达 x

    • t12 z 知道 26 到达 x

    • t13 y 知道 29 到达 x

    • t14 w 知道 30

    • t15 z 知道 31

    • t16 y 知道 34

    • t17 w 知道 35

    • t18 z 36

    • t19 y 39

    • t20 w 40

    • t21 z 41

    • t22 y 44

    • t23 w 45

    • t24 z 收到 w 的通告，知道通过 w 能够以 45 + 1 = 46 到达 x，因此从 z 去往 x 的路上，下一跳是 w，并毒化 w -> z，同时通告邻居 y 和 w

    • t25 y 收到 z 的通告，知道通过 z 能够以 46 + 3 = 49 到达 x，因此从 y 去往 x 的路上，下一跳是 z，并毒化 z -> y，同时通告邻居 z 和 w

    • t26 w 收到 y 的通告，知道通过 y 能够以 49 + 1 = 50 到达 x，因此从 w 去往 x 的路上，下一跳是 y，并毒化 y -> w，同时通告邻居 y 和 z

    • t27 ⚠️⚠️⚠️z 收到 w 的通告，知道通过 w 能够以 50 + 1 到达 x，但 z 也知道，通过 50 能够直接到达 x，因此从 z 去往 x 的路上，下一跳是 x，并毒化 x -> z。同时通告邻居 y 和 w : 通过 z 能够以 50 到达 x。

    • t28 🍎y 收到 z 的通告，那么 y 知道通过 z 能够以 50 + 3 = 53 到达 x，由于在 t26 中 y -> w 已经被毒化，因此由 y 去往 x 的路上，y 不会选择使用 w 作为下一跳，因此下一跳是 z，并毒化 z -> y，同时通告邻居 x 和 w；🍎w 收到 z 的通告，w 知道通过 y 能够以 1 + 49 = 50 到达 x，也知道通过 z 能够以 50 + 1 = 51 到达 x，因此选择 y 作为下一跳，并毒化 y -> w，同时通告邻居 y 和 z

    • t29 🍎w 收到 y 的通告，w 知道 y 能够以 53 + 1 = 54 到达 x，也知道通过 z 能够以 50 + 1 = 51 到达 x，因此选择 z 作为下一跳，并毒化 z -> w，同时通告邻居 y 和 z；🍎z 收到 w 的通告，z 不发生改变

    • t30 🍎y 收到 w 的通告， y 变为 1 + 51 = 52，下一跳是 w，然后通告 w 和 z；🍎 z 收到 w 的通告，z 不发生改变

    • t31 w 不发生改变，z 不发生改变

• 所以总共需要迭代 31 次才能达到稳定状态。

• c.

  • 当 c(y, x) 从 4 变化为 60 时，切断 x - y 就可以接触无穷计数问题。