题目集合（Direct Link Networks:） R4,R5,R6,R8,P1,P2,P3,P5,P6,P8, P10,P11,P14,P15,P18,P19,P23,P24,P25,P26¶

R4¶

假设两个节点同时经一个速率为 $R$ 的广播信道开始传输一个长度为 $L$ 的分组。用 $d_{prop}$ 表示这两个节点之间的传播时延。如果 $d_{\text{prop}}<L/R$，会发生碰撞吗？为什么¶

会发生碰撞。由于 $L/R>d_{prop}$，所以当 A 传输的分组的第一个 bit 到达 B 的时候，B 的传输还没有结束，就侦测到了碰撞。A 同理。

广播信道的 4 种希望的特性： 1. 当仅有一个节点发送数据时候，该节点有 $R$ bps 的吞吐量 2. 当有 $M$ 个节点发送数据时，每个节点吞吐量为 $R/M$ bps。这不必要求 $M$ 个节点中的每一个节点总有 $R/M$ 的瞬间速率。 3. 协议是去中心化的。（不会主节点故障就整个系统崩溃） 4. 协议是简单的，实现不昂贵。时隙 ALOHA 满足 1. 但是 2 不一定满足 ALOHA 是去中心化的，因为每个节点独立决定是否发送（随机化的） ALOHA 的实现简单。

令牌传递具有如下特点：
- 1、仅有一个结点发送数据时，该结点具有 R bps 吞吐量
- 2、M 个结点发送数据时，每个结点平均吞吐量为 R/M bps
- 3、协议分散，但会因为一个结点的故障导致整个系统崩溃。也可能因为令牌没有被释放导致整个系统崩溃。
- 4、协议简单，实现不昂贵。

R6¶

在 CSMA/CD 中，在第 5 次碰撞后，节点选择 $K=4$ 的概率有多大？结果 $K=4$ 在 `10Mbps` 以太网上对应于多少秒的时延？¶

5 次碰撞，在 $\{ 0,1,2,\dots,2^{5}-1 \}$ 中选，选择 $K=4$ 的概率为 $\frac{1}{32}$ 对应 $$ 4\times\left( \frac{512}{10^{6}\times 10} \right)=4*51.2\mu s=204.8\mu s $$

R8¶

如果局域网有很大的周长时，为什么令牌环协议将是低效的？¶

如果互联网有很大的周长，要经过相当长的时间令牌才会走完一周，这期间可能有很多帧积压而没有及时发送。也就是信道利用率比较低。

P1¶

假设某分组的信息内容是比特模式 `1110 0110 1001 1101`，并且使用了偶校验方案。在采用二维奇偶校验方案的情况下，包含该检验比特的字段的值是什么？¶

采取二维奇偶：对每行和每列计算。 - 具体来说是每行每列都计算偶校验码 - 最后应该每一行每一列的bit 是 1 的都是偶数个。

0 bit	1 bit	2bit	3bit	checkcode
1	1	1	0	1
0	1	1	0	0
1	0	0	1	0
1	1	0	1	1
1	1	0	0	0
包含该检验比特的字段的值如图所示
## P2
### 说明二维奇偶校验可以纠正和检测单 bit 差错。说明某些双比特差错能够被检测不能被纠正。
单比特差错：

如果 1110 0110 1001 1101 中的第二位（1->0）出错了

0 bit	1 bit	2bit	3bit	checkcode
1	1	1	0	1
0	1	1	0	0
1	0	0	1	0
1	1	0	1	1
1	1	0	0	0

错误后：

0 bit	1 bit	2bit	3bit	checkcode
1	0	1	0	1
0	1	1	0	0
1	0	0	1	0
1	1	0	1	1
1	1	0	0	0
我们可以横纵找不正确的校验吗，定位到错误位置，取反即可。
- 横向为奇数个的为第一行
- 纵向伪奇数个的为第二列
- 确定 `(1,2)`, 取反，即纠正完毕。
双比特的话，只能检测到发生错误，但不知道具体位置。
## P3
### 假设某分组的信息部分（图 6.3 种的 D）包含 10 字节，它由字符串“Internet”的 8 比特无符号二进制 ASCII 表示组成。对该数据计算因特网检验和。
首先获得 `Internet` 的 ASCII 码
- 字符串的ASCII码分别为：`I (73)`，`n (110)`，`t (116)`，`e (101)`，`r (114)`，`n (110)`，`e (101)`，`t (116)`。
- 转化为0x496E, 0x7465, 0x726E, 0x6565, 0x7465
- 计算校验和，结果为0xF602。

P5 CRC¶

考虑 5 比特生成多项式(CRC)，$G=10011$，并且假设 $D$ 的值为 $1010101010$, $R$ 的值是什么¶

满足 $R=\text{remainder}\;{\dfrac{D\cdot2^{r}}{G}}$ 取 r=5, 得 0100

P6¶

考虑上一个习题，此时假设 $D$ 具有值：¶

a. 1001 0101 01 算得 R= 0000 b. 0101 1010 10 算得 R= 1111 c. 1010 1000 00 同，略。

P8¶

完成 ALOHA 效率的推导。¶

a. 当有 $N$ 个活跃节点的时候，时隙 ALOHA 的效率是 $Np(1-p)^{N-1}$。求出使这个表达式最大化的 $p$ 值求导，得到一阶条件 $$ N(1-p)^{{N-1}-Np\cdot(N-1)(1-p)}{N-2}=0 $$ 得到 $1-p-pN+p=0$, 则 $p=\dfrac{1}{N}$ b. 令 $N$ 趋近于无穷，得到效率 $$ N\times \frac{1}{N}\left( 1-\frac{1}{N} \right)^{N-1}=\frac{1}{e} $$

P10¶

考虑两个节点 A 和 B，他们都使用时隙 ALOHA 协议来竞争一个信道。假定节点 A 比节点 B 有更多的数据要传输，并且节点 A 的重传概率 $p_{A}$ 比节点 $B$ 的重传概率 $p_{B}$ 要大¶

a. 吞吐量：$p_{A}(1-p_{B})$ b. 并不是. B 的吞吐量为 $p_B(1-p_{A})=p_{B}(1-2p_{B})$，A $2p_{B}(1-p_{B})，$ 可见不是严格两倍。如果让 A = 2B 得到 Pa 和 Pb 关系为 Pa = 2Pb/(1 + Pb)

P11¶

假定 4 个活跃节点 A、B、C 和 D 都使用时隙 ALOHA 来竞争访问某信道。假设每个结点有无限个分组要发送。每个结点在每个时隙中以概率 p 尝试传输。第一个时隙编号为时隙 1，第二个时隙编号为时隙 2，等等。¶

a. 结点 A 在时隙 5 中首次成功的概率是多少？¶

设事件 A 为 A 在时隙中成功传输帧 - P(A) = P(A 传输 && B 不传输 && C 不传输 && D 不传输) - P(A) = p(1 - p)^3 - 设事件 N 为结点 A 在时隙 5 中首次成功传输帧，则 - P(N) = P(A)(1 - P(A))^4 - - 因此 P(N) = p(1 - p)^3[1 - p(1 - p)^3]^4

b. 某个结点（A、B、C 或 D）在时隙 4 中成功的概率是多少？¶

设事件 B 为任意结点在某个时隙中成功传输帧，则
P(B) = p(1 - p)^3 C，D 同理
如果随便某个成功的概率，则是 $4p(1-p)^{3}$

c. 在时隙 3 中出现首个成功的概率是多少？¶

计算每个节点在时隙 3 不成功的概率，做乘积，然后用 1 减去即可。 - P(D) = 4p(1 - p)^3[1 - 4p(1 - p)^3]^2

d. 这个 4 结点系统的效率是多少？¶

只要有一个节点能传输就可以。各节点是独立的。所以总体概率是 $4p(1-p)^{3}$

P14¶

![[Pasted image 20250521100532.png]] c： - E 发送 IP 包，链路层打包包，发现子网内没有这个包的 mac 地址，无法直接传送，于是封装目标 mac 地址，发现子网内没有这个 IP，传给路由器 r3处理 - 路由器 r3 查询保存的路由表于是检查自己的交换表，若其中有网关路由器 MAC 地址对应的表项，那么就转发到指定端口。若没有，那么向除了来路外的所有端口广播该帧，于是中间一个适配器 F将收到该帧，其适配器检查到该帧不是向自己寻址后将其丢弃。

接下来网关路由器 R3 的适配器收到了该帧，确认了是向自己寻址的帧后，拆封向上交给网络层，于是检查自己的转发表，决定恰当的端口进行转发。
在路由器恰当的输出端口适配器中，由于路由器的 ARP 表是最新的，所以路由器查找到了下一跳路由器 R1 的 MAC 地址将其作为帧的目的 MAC，然后转发出去。
当中间的交换机 S2 收到此帧，检查自己的交换表，有记录则转发。无记录则广播。
现在最左边的路由器 R1 收到了该帧，确认好是向自己寻址的帧后，向上交给网络层
由于目标 B 在 R1 的子网内，所以其存有 mac 地址（存在更新后的 ARP 表中），包传输完成

P15¶

考虑图 6-33，用一台交换机 $S_{1}$ 代替子网 1 和子网 2 之间的路由器，并且将子网 2 和子网 3 之间的路由器标记为 $R_{1}$¶

a. 主机 E 向主机 F 发送一个 IP 报，主机 E 将请求路由器 R1 帮忙转发该数据报吗？为什么？ethernet frame 中的 src dst ip, mac 是？ E 向 F 发送 IP 报文不会请求路由器 R1 转发，因为 E 和 F 在一个子网内。 src IP: 192.168.3.2, src MAC:II-II-II-II-II-II dst IP: 192.168.3.3, dst MAC: JJ-JJ-JJ-JJ-JJ-JJ b. 假定 E 希望向 B 发送一个 IP 数据报，假设 E 的 ARP 缓存中不包含 B 的 MAC 地址，E 将执行 ARP 查询来发现 B 的 MAC 地址吗？为什么？在交付给路由器 R1 的 ethernet frame（包含发向 B 的 IP 数据报）中，src 和 dst IP 和 MAC 分别是什么？ E 不会执行，因为他们不在一个子网，E 会传给路由器网关(gw)去 forward 这个包 - 因此将执行 ARP 查询网关路由器的 MAC 地址，而不是 B 的。 - 源 IP : 192.168.3.2 - 目的 IP : 192.168.1.3 - 源 MAC : II-II-II-II-II-II - 目的 MAC : HH-HH-HH-HH-HH-HH c. 交换机 S1 收到 ARP request，就保存 A 的 IP-MAC 映射到自己的转发表 R1 会收到这个 ARPrequest（因为是广播的），但是其不会向子网 3 转发，因为子网 3 中没有 B 的 ip 前缀匹配主机 B 收到 ARP request，回发一个响应报文。它不需要查询报文，因为 ARP request 的 src MAC 就是 A 的 mac 地址 S1 会存储 B 的 IP-MAC 表，同时发送 A 的 ARP reply

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$ 传输一个 512+64 比特的帧，传输完成需要 576bit/10*10^6bps=57.6us B 侦测到 A 开始传输，假如立刻发送一个报文，经过 325bit/10Mbps=32.5us 可以告诉 A，此时 A 还没有结束，所以 A 不能完成传输。

从最坏情况下，B 将从 324bit 发送。（即侦测到 A 进行传输之前 1bit），此时 64.9us 才能发送到 A.

P19¶

假设节点 $A$ 和节点 $B$ 在相同的 `10 Mbps` 广播信道上，并且这两个节点的传播时延为 245 比特时间。假设 A 和 B 同时发送以太网帧，帧发生了碰撞。然后 A 和 B 在 CSMA/CD 算法中选择不同的 $K$ 值。假设没有其他节点处于活跃状态，来自 A 和 B 的重传会发生碰撞吗？为此完成下面的例子就足以说明问题了。假设 A 和 B 在 t=0 比特时间开始传输。它们在 t=245 比特时间都检测到了碰撞。假设 $K_{A}=0,K_{B}=1$。B 将会调整它的重传到什么时间？A 什么时间开始发送？（注意：这些节点在返回第 2步后，必须等待一个空闲信道，参见协议。）A 的信号在什么时间到达 B 呢？B 在它预定的时刻抑制传输吗？¶

CSMA/CD介绍) 解答： - 同时，在检测到碰撞之后，还需要再发完 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 发生碰撞。

P23¶

考虑图 6-15 。假定所有链路都是 `100Mbps`。在该网络中的 9 台主机和两台服务器之间，能够取得的最大总聚合吞吐量是多少？你能够假设任何主机或服务器能够向任何其他主机或服务器发送分组。为什么？¶

未命名文件夹/redkoldnote/docs/计算机网络/Notes/链路层 Direct Link Networks#交换机网络中的聚合吞吐量 图 6-15 是交换机网络，总聚合吞吐量为 $\sum_{i=1}R_{i}$，为 11*100Mbps=1100Mbps 因为它们通过交换机连成一个一个子网。

P24¶

未命名文件夹/redkoldnote/docs/计算机网络/Notes/链路层 Direct Link Networks#集线器网络中的聚合吞吐量

三台连接各系的用集线器来代替。所有链路是 1Gbps。回答问题。¶

集线器是竞争信道，所以为 1Gbps*3+2Gbps=5Gbps

P25¶

所有交换机用集线器代替，所有链路是 1Gbps。回答问题。¶

回答问题。由于中间交换机连接了所有子网，其为集线器就限制了总体吞吐率，所以为 1Gbps

P26¶

在某网络标识 A 到 F 的 6 个节点，以星形和一台交换机连接，考虑在该网络环境中某个在学习的交换机的运行情况。假定：（i）B 向 E 发送一个帧;（ii）E 向 B 回答一个帧; （iii）A 向 B 发送一个帧; （iv）B 向 A 回答一个帧。交换机表初始为空。显示在这些事件的前后该交换机表的状态，指出上面你转发传输帧的链路。¶

(i) B 向 E 发送： B 向交换机发送帧交换机记录 B 的 ip-mac，广播询问谁有这个 IP E 回答交换机记录 E 的 ip-mac，转发包

（ii）E 回答： E 向交换机发送帧交换机发现 B 的已经记录，直接转发。（iii）A 向 B 发送： A 向交换机发送交换机记录 A 得 ip-mac 直接转发 B （iv）B 回答 A B 向交换机发送交换机发现已经记录了 A，直接转发

题目集合（Direct Link Networks:） R4,R5,R6,R8,P1,P2,P3,P5,P6,P8, P10,P11,P14,P15,P18,P19,P23,P24,P25,P26¶

R4¶

假设两个节点同时经一个速率为 \(R\) 的广播信道开始传输一个长度为 \(L\) 的分组。用 \(d_{prop}\) 表示这两个节点之间的传播时延。如果 \(d_{\text{prop}}<L/R\)，会发生碰撞吗？为什么¶

R5¶

在 6.3 节中，我们列出了广播信道的 4 种希望的特性。这些特性中的哪些是时隙 ALOHA 所具有的？令牌传递具有这些特性中的哪些？¶

R6¶

在 CSMA/CD 中，在第 5 次碰撞后，节点选择 \(K=4\) 的概率有多大？结果 \(K=4\) 在 `10Mbps` 以太网上对应于多少秒的时延？¶

R8¶

如果局域网有很大的周长时，为什么令牌环协议将是低效的？¶

P1¶

假设某分组的信息内容是比特模式 `1110 0110 1001 1101`，并且使用了偶校验方案。在采用二维奇偶校验方案的情况下，包含该检验比特的字段的值是什么？¶

P5 CRC¶

考虑 5 比特生成多项式(CRC)，\(G=10011\)，并且假设 \(D\) 的值为 \(1010101010\), \(R\) 的值是什么¶

P6¶

考虑上一个习题，此时假设 \(D\) 具有值：¶

P8¶

完成 ALOHA 效率的推导。¶

P10¶

考虑两个节点 A 和 B，他们都使用时隙 ALOHA 协议来竞争一个信道。假定节点 A 比节点 B 有更多的数据要传输，并且节点 A 的重传概率 \(p_{A}\) 比节点 \(B\) 的重传概率 \(p_{B}\) 要大¶

P11¶

假定 4 个活跃节点 A、B、C 和 D 都使用时隙 ALOHA 来竞争访问某信道。假设每个结点有无限个分组要发送。每个结点在每个时隙中以概率 p 尝试传输。第一个时隙编号为时隙 1，第二个时隙编号为时隙 2，等等。¶

a. 结点 A 在时隙 5 中首次成功的概率是多少？¶

b. 某个结点（A、B、C 或 D）在时隙 4 中成功的概率是多少？¶

c. 在时隙 3 中出现首个成功的概率是多少？¶

d. 这个 4 结点系统的效率是多少？¶

P14¶

P15¶

考虑图 6-33，用一台交换机 \(S_{1}\) 代替子网 1 和子网 2 之间的路由器，并且将子网 2 和子网 3 之间的路由器标记为 \(R_{1}\)¶

P18¶

P19¶

P23¶

考虑图 6-15 。假定所有链路都是 `100Mbps`。在该网络中的 9 台主机和两台服务器之间，能够取得的最大总聚合吞吐量是多少？你能够假设任何主机或服务器能够向任何其他主机或服务器发送分组。为什么？¶

P24¶

三台连接各系的用集线器来代替。所有链路是 1Gbps。回答问题。¶

P25¶

所有交换机用集线器代替，所有链路是 1Gbps。回答问题。¶

P26¶

题目集合（Direct Link Networks:） R4,R5,R6,R8,P1,P2,P3,P5,P6,P8, P10,P11,P14,P15,P18,P19,P23,P24,P25,P26¶

R4¶

假设两个节点同时经一个速率为 \(R\) 的广播信道开始传输一个长度为 \(L\) 的分组。用 \(d_{prop}\) 表示这两个节点之间的传播时延。如果 \(d_{\text{prop}}<L/R\)，会发生碰撞吗？为什么¶

R5¶

在 6.3 节中，我们列出了广播信道的 4 种希望的特性。这些特性中的哪些是时隙 ALOHA 所具有的？令牌传递具有这些特性中的哪些？¶

R6¶

在 CSMA/CD 中，在第 5 次碰撞后，节点选择 \(K=4\) 的概率有多大？结果 \(K=4\) 在 10Mbps 以太网上对应于多少秒的时延？¶

R8¶

如果局域网有很大的周长时，为什么令牌环协议将是低效的？¶

P1¶

假设某分组的信息内容是比特模式 1110 0110 1001 1101，并且使用了偶校验方案。在采用二维奇偶校验方案的情况下，包含该检验比特的字段的值是什么？¶

P5 CRC¶

考虑 5 比特生成多项式(CRC)，\(G=10011\)，并且假设 \(D\) 的值为 \(1010101010\), \(R\) 的值是什么¶

P6¶

考虑上一个习题，此时假设 \(D\) 具有值：¶

P8¶

完成 ALOHA 效率的推导。¶

P10¶

考虑两个节点 A 和 B，他们都使用时隙 ALOHA 协议来竞争一个信道。假定节点 A 比节点 B 有更多的数据要传输，并且节点 A 的重传概率 \(p_{A}\) 比节点 \(B\) 的重传概率 \(p_{B}\) 要大¶

P11¶

假定 4 个活跃节点 A、B、C 和 D 都使用时隙 ALOHA 来竞争访问某信道。假设每个结点有无限个分组要发送。每个结点在每个时隙中以概率 p 尝试传输。第一个时隙编号为时隙 1，第二个时隙编号为时隙 2，等等。¶

a. 结点 A 在时隙 5 中首次成功的概率是多少？¶

b. 某个结点（A、B、C 或 D）在时隙 4 中成功的概率是多少？¶

c. 在时隙 3 中出现首个成功的概率是多少？¶

d. 这个 4 结点系统的效率是多少？¶

P14¶

P15¶

考虑图 6-33，用一台交换机 \(S_{1}\) 代替子网 1 和子网 2 之间的路由器，并且将子网 2 和子网 3 之间的路由器标记为 \(R_{1}\)¶

P18¶

P19¶

P23¶

考虑图 6-15 。假定所有链路都是 100Mbps。在该网络中的 9 台主机和两台服务器之间，能够取得的最大总聚合吞吐量是多少？你能够假设任何主机或服务器能够向任何其他主机或服务器发送分组。为什么？¶

P24¶

三台连接各系的用集线器来代替。所有链路是 1Gbps。回答问题。¶

P25¶

所有交换机用集线器代替，所有链路是 1Gbps。回答问题。¶

P26¶

在 CSMA/CD 中，在第 5 次碰撞后，节点选择 \(K=4\) 的概率有多大？结果 \(K=4\) 在 `10Mbps` 以太网上对应于多少秒的时延？¶

假设某分组的信息内容是比特模式 `1110 0110 1001 1101`，并且使用了偶校验方案。在采用二维奇偶校验方案的情况下，包含该检验比特的字段的值是什么？¶

考虑图 6-15 。假定所有链路都是 `100Mbps`。在该网络中的 9 台主机和两台服务器之间，能够取得的最大总聚合吞吐量是多少？你能够假设任何主机或服务器能够向任何其他主机或服务器发送分组。为什么？¶