P17 前面讲过，使用 CSMA/CD 协议，适配器在碰撞之后等待 K * 512 比特时间，其中 K 是随机选取的。对于 K = 100，对于一个 10 Mbps 的广播信道，适配器返回到第二步要等多长时间？对于 100 Mbps 的广播信道来说呢？
-
CSMA/CD 协议的运行分为下面步骤：
- 1、适配器接收网络层数据报，准备链路层帧，将其放入帧适配器缓存中。
- 2、适配器侦听信道是否忙，若忙，等待直到信道不忙。若信道不忙，则开始传输帧
- 3、适配器一边传输一边侦听信道是否有其他适配器开始使用广播信道。如果有，那么中止传输，等待一个随机时间量，然后回到第 2 步。如果传输完整个帧都没有检测有其他适配器使用信道，那么就算完成该帧。
-
对于 10 Mbps 的广播信道，512 比特时间就是 51.2 us，因此需要等 5.12 ms
-
对于 100 Mbps 的广播信道，512 比特时间是 5.12 us，因此需要等 0.512 ms
P18 假设结点 A 和结点 B 在同一个 10 Mbps 的广播信道上，这两个结点的传播时延为 325 比特时间。假设对这个广播信道使用 CSMA/CD 和以太网分组。假设结点 A 开始传输一帧，并且在它传输结束之前结点 B 开始传输一帧。在 A 检测到 B 已经传输之前，A 能完成传输吗？为什么？如果回答是可以，则 A 错误地认为它的帧已成功传输而无碰撞。提示：假设在 t = 0 比特时刻，A 开始传世一帧。在最坏的情况下，A 传输一个 512 + 64 比特时间的最小长度的帧。因此 A 将在 t = 512 + 64 比特时刻完成帧的传输。如果 B 的信号在比特时间 t = 512 + 64 比特之前到达 A，则答案是否定的。在最坏情况下，B 的信号什么时刻到达 A ?
-
假设 A 传输一个最小长度的帧，该帧长度为 72 字节，即网络层数据报为 46 字节，8 字节前同步码，12 字节源目的 MAC，2 字节类型，4 字节 CRC。则 A 传输这 72 字节总共需要的时间如下：
-
d_trans_A = 72 * 8 / 10^7 = 57.6 us -
如果在 A 开始传输第一帧的时刻，B 也开始传输第一帧，那么 B 也在占用广播信道这一消息通知到 A 需要的时间如下:
-
d_notify_A = 325 / 10^7 = 32.5 us -
假如 A 和 B 同时开始传输，在 A 传输完成之前，A 就能检测到碰撞。
-
但是在最坏情况下，B 在 t = 324 比特时间才开始传输帧，因此在 A 传输完之前，都没有侦测到 B 在同一时间段内有占用过信道。
-
如下图所示
-
P19 假设结点 A 和结点 B 在相同的 100 Mbps 广播信道上，并且这两个结点的传播时延为 245 比特时间。假设 A 和 B 同时发送以太网帧，帧发生了碰撞，然后 A 和 B 在 CSMA/CD 算法中选择不同的 K 值。假设没有其他结点处于活跃状态，来自 A 和 B 的重传会碰撞吗？为此，完成下面的例子就足以说明问题了。假设 A 和 B 在 t = 0 比特时间开始传输。它们在 t = 245 比特时间都检测到了碰撞。假设 Ka = 0, Kb = 1。B 会将它的重传调整到什么时间？A 在什么时间开始发送？（注意：这些结点在返回第 2 步之后，都必须等待一个空闲信道，参见协议。）A 的信号在什么时间到达 B 呢？B 在它预定的时刻抑制传输吗？
- 假设 A 和 B 检测到碰撞并回退到第二步然后选择不同的 K 值，结点 A 选择了 0，也就是立即重传，但是在立即重传前，A 需要在 96 比特时间内帧听信道都没有被使用，才能开始传送帧。因此 A 即使选择了 K = 0，也至少还要等待 96 比特时间才可以开始传输帧。结点 B 选择了 1，也就是等待 512 + 96 比特时间。
- 同时，在检测到碰撞之后，还需要再发完 48 比特的干扰信号，而不是立即停止。
| time | event |
|---|---|
| t = 0 | A 和 B 同时开始传输帧 |
| t = 245 | A 和 B 各自检测到碰撞 |
| t = 245 + 48 = 293 | A 和 B 都传输完了各自的强化干扰信号 |
| t = 245 + 245 = 490 | B 强化干扰信号第 1 bit 到达了 A，A 强化干扰信号第 1 bit 到达了 B |
| t = 293 + 245 = 538 | A 强化干扰信号的最后 1 bit 到达了 B，B 强化干扰信号的最后 1 bit 到达了 A, A 侦测到信道空闲 |
| t = 538 + 96 = 634 | A 开始传输帧 |
| t = 293 + 512 = 805 | B 开始等待空闲信道 |
| t = 643 + 245 = 888 | A 的第 1 bit 到达 B，B 侦听倒信道忙 |
- 因为 B 在等待空闲信道时侦听到信道忙，所以不会和 A 发生碰撞。
P20 在这个习题中，你将对一个类似于 CSMA/CD 的多路访问协议的效率进行推导。在这个协议中，时间分为时隙，并且所有适配器都与时隙同步。然而，和时隙 ALOHA 不同的是，一个时隙的长度（以秒计）比一帧的时间（即传输一帧的时间）小得多。令 S 表示一个时隙的长度。假设所有帧都有恒定长度 L = kRS，其中 R 是信道的传输速率，k 是一个大整数。假定有 N 个结点，每个结点都有无穷多帧要发送。我们还假设 d_prop < S，以便所有结点在一个时隙时间结束之前能够检测到碰撞。这个协议描述如下：
- 对于某给定的时隙，如果没有结点占用这个信道，所有结点竞争该信道；特别是每个结点以概率 p 在该时隙传输。如果刚好有一个结点在该时隙中传输，该结点在后续 k - 1 个时隙占有信道，并传输它的整个帧。
- 如果某结点占用了信道，所有其他结点抑制传输，直到占有信道的这个结点完成了该帧的传输为止。一旦该结点传输完它的帧，所有结点竞争该信道。
- 注意到此信道在两种状态之间交替：“生产性状态”（它恰好持续 k 个时隙）和 “非生产性状态”（它持续随机数个时隙）。显然，该信道的效率是 k /(k + x)，其中 x 是连续的非生产性时隙的期望值。
-
a.
- 设事件 A 为在某个时隙中首次成功传输帧。设 Y 为成功传输帧的时隙的序号，设在第 m 个时隙中成功传输了帧。设在某个时隙中成功传输帧的概率为 b，则
P(A) = P(Y = m) = b(1 - b)^(m-1)- 这是一个几何分布，所以
E(Y) = 1/b，因此浪费的时隙的个数为E(X) = E(Y) - 1 = (1 - b)/b - 由于
b = Np(1 - p)^(N-1) - 因此信道的效率为
-
b.
- 对于信道效率
k/(k + x)，那么 x 越小，信道效率越大。 - 即让
E(Y)最小即可，即求 b 的极大值，故等同于求f(p) = Np(1 - p)^(N-1)的极大值，则p = 1/N
- 对于信道效率
-
c.
-
d.
- 由上式可以看出，随着
k -> ∞，效率趋近于 1。
- 由上式可以看出，随着
