Skip to content

Latest commit

 

History

History
167 lines (125 loc) · 12.4 KB

习题_44_55.md

File metadata and controls

167 lines (125 loc) · 12.4 KB

P44 考虑习题 P26 中 7 个结点的网络 (结点标为 t ~ z)。给出根在 z 的包括（作为端主机）结点 u、v、w 和 y 的最低费用树。非形式地讨论一下，为什么你给出的树是一棵最低费用树。

  • Prim 算法描述如下：

    • 将源结点到自己的距离初始化为 0，到所有其他结点的距离初始化为无穷大，将源结点插入索引优选队列中，索引为顶点编号，权重值为链路费用。
    • 取出堆中最小权重的顶点，遍历邻边，该插入堆插堆，如果已经在堆中，那么就减小权重。这一步是为了选择一个最小的切分。
    • 堆中已经有若干个顶点，从堆中取出的下一顶点是这若干个顶点的最小切分

  • 实现 最小生成树 Prim 算法

  • 使用该 Prim 算法来处理下列连通图，得到如下结果:

  • 处理过程如下:

 **************** print structure of graph ***************
  V = 7
  E = 12
  0 : { z x 8 } { z y 12 }
  1 : { y v 8 } { y t 7 } { y x 6 } { z y 12 }
  2 : { v w 4 } { v u 3 } { v x 3 } { v t 4 } { y v 8 }
  3 : { u t 2 } { v t 4 } { y t 7 }
  4 : { x w 6 } { v x 3 } { y x 6 } { z x 8 }
  5 : { u w 3 } { x w 6 } { v w 4 }
  6 : { u t 2 } { u w 3 } { v u 3 }
  *********************************************************
  All edges in minimum spaning tree : [weight=25.00] [edgeCount=6]
  { y x  6.00}
  { v x  3.00}
  { u t  2.00}
  { z x  8.00}
  { u w  3.00}
  { v u  3.00}

P45 考虑实现广播的两种基本方法：单播模拟与网络层（即路由器协助）广播，并假定使用生成树广播来实现网络层广播。考虑有一个发送方与 32 个接收方。假设发送方通过一棵路由器二叉树与接收方相连。在单播模拟与网络层广播情况下，对于这个拓扑，发送一个广播分组的费用各是多少？这里每经过单一链路发送一个分组（或一个分组的副本），产生一个单位费用。用什么样的拓扑互联发送方、接收方和路由器，将使得单播模拟与真正的网络层广播产生的费用相差尽可能大？你可按照自己的意愿选择多台路由器。

  • 单播模拟来实现广播总共需要发送 32 个分组，每个分组会经过 5 段链路，若每段链路为一个单位费用，则总费用为 5 * 32 = 160

  • 生成树广播只需要发送一个分组，这个分组被各个结点所复制，通过的总链路数为 2 + 4 + 8 + 16 + 32 = 62，那么总费用也如此。

  • 当所有接收方的第一跳路由器都位于一条线上时，单播模拟和生成树广播差距最大。此时生成树广播为 N (N 为链路的数量), 而单播模拟为 N(N + 1)/2

P46 考虑图 4-44 中反向路径转发（RPF）算法的运行。使用相同的拓扑，找出从所有结点到源结点 A 的一系列路径（并像在图 4-44 中那样用粗线指出这些路径），使得如果这些路径是最低费用路径，则结点 B 将接受来自使用 RPF 的结点 A、C 和 D 的 A 的广播报文的副本。

  • C 位于到源 A 的最少费用路径上，C 向邻居转发分组，因此 B 能收到来自 C 的分组。
  • D 位于到源 A 的最少费用路径上，D 向邻居转发分组，因此 B 能收到来自 D 的分组。
  • A 一开始向邻居转发分组，因此 B 能收到来自 A 的分组。

P47 考虑图 4-44 中所示的拓扑。假定所有链路具有单位费用并且结点 E 是广播源。在给定结点 E 为源的情况下，使用如图 4-44 中所示的箭头，指出使用 RPF 转发分组的链路，以及不转发分组的链路。

  • E 位于 C 回到 E 的最少费用路径上，因此 C 转发来自 E 的分组，F 不位于 C 回到 E 最少费用路径上，因此 C 忽略来自 F 的分组。之后 F 忽略来自 C 分组，A 转发来自 C 的分组，B 丢弃来自 A 的分组，丢弃来自 C 的分组，C 丢弃来自 B 的分组，D 转发来自 E 的分组，B 和 G 都转发来自 D 的分组...

P48 使用习题 P26 中的图重复习题 P47。假定 z 是广播源，并且链路费用如在习题 P26 中所示。

  • z 首先向 x 和 y 发送源为 z 的报文
  • x 收到报文后，因为 z 位于 x 返回 z 的最少费用路径上，于是 x 向 y v w 转发分组；y 收到报文后，因为 z 位于 y 返回 z 的最少费用路径上，因此 y 向 x v t 转发分组
  • 🍎v 收到来自 y 的分组后，因为 y 不位于 v 返回到 z 的最少费用路径上（这条路径应该是 v - x - z），因此 v 丢弃来自 y 的分组；🍎v 收到来自 x 的分组后，因为 x 位于 v 返回到 z 的最少费用路径上，于是 v 向 y t w u 转发分组；🍎w 收到来自 x 的分组后，因为 x 位于 w 返回到 z 的最少费用路径上，因此 w 向 v 和 u 转发分组；🍎t 收到来自 y 的分组后，因为 y 不位于 t 返回到 z 的最少费用路径上，因此 t 丢弃来自 y 的分组；🍎x 收到来自 y 的分组后，因为 y 不位于 x 返回 z 的最少费用路径上，因此 x 丢弃来自 y 的分组；🍎y 收到来自 x 的分组后，因为 x 不位于 y 返回到 z 的最少费用路径上，因此 y 丢弃来自 x 的分组。
  • 🍎t 收到来自 y 的分组后，因为 y 不位于 t 返回到 z 的最少费用路径上，于是 t 丢弃来自 y 的分组；🍎而收到 v 的分组后，转发该分组；🍎w 收到来自 v 的分组后，因为 v 不位于 w 返回到 z 的最少费用路径上，因此 w 丢弃来自 v 的分组....

P49 考虑在图 4-46 中所显示的拓扑，并假定每段链路有单位费用。假设结点 C 在基于中心的多播路由选择算法中被选为中心。假定每个相连路由器都使用到结点 C 的最低费用路径向 C 发送加入报文，画出所产生的基于中心的多播路由选择树。产生的树是一棵最低费用树吗？评估你的答案。

 ➜  progs git:(master) ✗ ./run.sh p49.c 
  **************** print structure of graph ***************
  V = 7
  E = 9
  0 : { A C 1 } { A B 1 }
  1 : { B D 1 } { B C 1 } { A B 1 }
  2 : { C E 1 } { C F 1 } { B C 1 } { A C 1 }
  3 : { D G 1 } { E D 1 } { B D 1 }
  4 : { E D 1 } { F E 1 } { C E 1 }
  5 : { F E 1 } { C F 1 }
  6 : { D G 1 }
  *********************************************************
  All edges in minimum spaning tree : [weight= 6.00] [edgeCount=6]
  { A B  1.00}
  { A C  1.00}
  { B D  1.00}
  { C E  1.00}
  { C F  1.00}
  { D G  1.00}

  • 从上面算法的运行结果我们得到最小生成树如下所示:

  • 由多播路由选择算法得到的多播树如下所示:

  • 可以看出，拓扑结构和最小生成树的不同。

P50 重复习题 P49，使用习题 P26 中的图。假定中心结点是 v。

  • 运行 Prim 算法 得到如下所示的结果

    ➜  progs git:(master) ✗ ./run.sh p50.c 
**************** print structure of graph ***************
V = 7
E = 12
0 : { z x 8 } { z y 12 }
1 : { y v 8 } { y t 7 } { y x 6 } { z y 12 }
2 : { v w 4 } { v u 3 } { v x 3 } { v t 4 } { y v 8 }
3 : { u t 2 } { v t 4 } { y t 7 }
4 : { x w 6 } { v x 3 } { y x 6 } { z x 8 }
5 : { u w 3 } { x w 6 } { v w 4 }
6 : { u t 2 } { u w 3 } { v u 3 }
*********************************************************
All edges in minimum spaning tree : [weight=25.00] [edgeCount=6]
{ y x  6.00}
{ v x  3.00}
{ u t  2.00}
{ z x  8.00}
{ u w  3.00}
{ v u  3.00}
    • 由 Prim 算法运行得到的最小生成树如下图所示:

  • 由多播路由选择算法得到的多播树如下所示:

P51 在 4.5.1 节中我们学习了计算单播路径的 Dijkstra 的链路状态路由选择算法，这些单播路径分别是从源到所有目的地的最小费用路径。这些路径的并集能够被认为形成了一棵最低单播费用路径树（或一棵最短单播路径树，如果所有链路费用是相同的）。通过构造一个反例，标明最低费用路径树并不总是与最小生成树相同。

  • 从上图可以看出，最小生成树和最低费用路径树的拓扑结构并不相同。

P52 考虑所有结点与 3 个其他结点相连的网络。在单一时间步中，一个结点能够从它的邻居接受到所有传输的广播分组，复制分组，并向它的所有邻居发送之（除了发送给定分组的那个结点）。在下个时间步中，相邻结点能够接收、复制和转发这些分组等等。假定使用无控制洪泛以在这样的网络中提供广播。在时间步 t，多少个广播分组的副本将被传输，假定在时间步 1 期间，由源结点向它的 3 个邻居传输单个广播分组。

  • step 1，3 个分组被传输

  • step 2，6 个分组被传输

  • step 3，12 个分组被传输

  • step k, 3 * 2^(k-1) 个分组被传输

P53 我们在 4.7 节中看到，没有任何网络层协议能用于标示参与一个多播组的主机。在这种情况下，多播应用程序怎样知道参与一个多播组的主机的身份？

  • 因为在 IGMP 中，只能够标明一个多播路由器（参与多播组的主机的第一跳路由器）是否加入了一个多播组，而不能标明在多播组中主机的身份，所以标示多播组主机的协议必须在应用层实现。应用层可以通过周期性的向其他多播组的成员多播通告自己的标示号，通过应用层报文。

P54 设计（给出伪代码描述）一个应用级协议，该协议维护参与一个多播组的所有主机的地址。特别要指出你的协议所使用的网络服务（单播或多播），还要指出你的协议发送报文是在带内还是带外（关于多播组参与者之间的应用数据流）并说明理由。

// TODO

P55 多播地址空间的尺寸有多大？假设现在两个不同的多播组随机地选择一个多播地址。它们选择同一个地址的概率有多大？假设现有 1000 个多播组同时正在进行，随机选择它们的多播组地址。它们冲突的概率有多大？

  • 多播地址（又称为 D 类地址）的范围是 224.0.0.0/4, 因此总共有 28 比特，也就是 2^28 个多播地址。

  • 两个不同的多播组随机选择一个多播地址，相同的概率为 1/(2^28) = 3.73 x 10^-9

  • 1000 个多播组同时进行，那么如果都不相同的概率为 P = (N * (N-1) * (N-2) * (N-3) * ... (N-999)) / (N^1000)

  • 因此有冲突的概率为 1 - P = 0.998