CS144-check7 & spring23期末卷

Check7

check7的内容呢，是根据我们之前实现的一切，借助Stanford的服务器与其他同学进行通信，显然我们没有条件实践了（笑）

其中在endtoedd.cc中帮我们做了很多socket相关的内容，有兴趣的话可以读一下源码。

Spring 23 期末考试

所以为了凑一下本篇的内容，我们来锐评一下往年的卷子吧。

应用层

填空 16points

你打开电脑并首次将其连接到 Wi-Fi 网络。你的电脑执行一个（ ）请求以了解其 IP 地址以及默认路由器和 DNS 服务器的 IP 地址。

你打开 Web 浏览器并导航至 https://cs144.stanford.edu。你的电脑发送一个（ ）请求以了解默认路由器的以太网（MAC）地址，并使用（ ）协议将“cs144.stanford.edu”主机名转换为 IP 地址。

你的电脑发送一个 TCP 段，其中（ ）标志被设置，以初始化与 cs144.stanford.edu 计算机的 TCP 连接。

两台计算机使用（ ）协议在 TCP 字节流中建立一个加密且完整性受保护的字节流。

作为该协议的一部分，cs144.stanford.edu 出示一个证书，证明其（ ） key 正当地属于“cs144.stanford.edu”。你的 Web 浏览器验证这个证书是否由其信任的（ ）签名。

使用加密的字节流，你的浏览器发送一个（ ）请求获取“/”路径，并接收一个其正文包含 HTML 文档的响应。

这填空真水吧，答案略

简答 8ps

为什么 IP、UDP 和 TCP 校验和无法检测或纠正恶意对手在传输中修改数据报和段的尝试？（请写 1-2 句简洁的句子。）

MAC（消息认证码）或 AEAD（Authenticated Encryption with Associated Data）密码如何在恶意对手故意修改的情况下保持完整性？（请写 1-2 句简洁的句子。）

这简答真水吧，iptcpudp设计出来就不包含抵御攻击啊，checksum随便调调就一致了。MAC和AEAD有一个仅有双方有的密钥啊（

网络服务抽象

解释错误 12ps

(a) “IP 提供了一个不可靠的数据报服务，所以使用 IP 的应用程序不可靠。”

(b) “UDP 提供了一个不可靠的数据报服务，所以使用 UDP 的应用程序不可靠。”

(c) “UDP 流量不受拥塞控制。”

(d) “NATs 转换 TCP 连接的地址和端口，从‘内部’ IP/端口到‘外部’ IP/端口。UDP 是无连接的，所以它不适用于 NATs。”

这真水吧，每个都挺离谱的其实。
简单说一下d，虽然UDP确实经常做内网穿透（NAT Traversal），但是这跟是否适用没有关系啊（

选择并解释 6ps

TCP 传统上运行在 IP 之上。假设你决定在单个 UDP 隧道内传输多个 TCP 流，将完整的 TCP 段，包括头部，放置在 UDP 数据报的有效载荷中。

(a) 这会影响应用程序的吞吐量超过 5% 吗？请圈出你的答案。
A 是的，将 TCP 隧道化到 UDP 内将会影响应用程序 TCP 吞吐量超过 5%。
B 不会，将 TCP 隧道化到 UDP 内不会影响应用程序 TCP 吞吐量超过 5%。
请用 1-3 句简洁的话来证明你的答案。

(b) 这会影响 TCP 段的传输行为吗？请圈出你的答案。
A 是的，将 TCP 隧道化到 UDP 内会影响 TCP 段的传输行为。
B 不会，将 TCP 隧道化到 UDP 内不会影响 TCP 段的传输行为。
请用 1-3 句简洁的话来证明你的答案。

BB是显然的，UDP header怎么可能占5%，至于传输行为更是无从谈起，我们都手搓过TCP了（
TCP IN UDP IN IP已经成熟多少年了（笑
TCP不在乎你过程中怎么传输，反正在对端把负载抽出来就行，这就是网络抽象的好处，例如鸽联网（笑

选择并解释2 6ps

UDP 传统上运行在 IP 之上。假设你决定在单个 TCP 流内隧道化多个 UDP 流，将完整的 UDP 段，包括头部，放置在 TCP 流中。

(a) 这可能会导致应用程序吞吐量变化超过 5% 吗？请圈出你的答案。
A 是的，将 UDP 隧道化到 TCP 内可能会影响应用程序 UDP 吞吐量超过 5%。
B 不会，将 UDP 隧道化到 TCP 内不可能会影响应用程序 UDP 吞吐量超过 5%。
请用 1-3 句简洁的话来证明你的答案。

(b) 这会影响 UDP 段的传输行为吗？请圈出你的答案。
A 是的，将 UDP 隧道化到 TCP 内会影响 UDP 段的传输行为。
B 不会，将 UDP 隧道化到 TCP 内不会影响 UDP 段的传输行为。
请用 1-3 句简洁的话来证明你的答案。

AA是显然的，这就相当于自己给UDP加上了额外的重传策略。

真实世界的网络

Question 20ps

考虑两个位于不同网络地址端口转换 (NAPT) 后面的用户/计算机，在例如视频聊天或文件共享应用程序中尝试通过互联网发送大量数据。回想一下在课堂上讨论的以下四个等级的点对点 (P2P) 网络：

• 等级 9a：通过公共文件服务器进行 P2P 网络连接（例如 Google Drive、GitHub）
• 等级 9b：通过公共代理/中继/TURN 服务器进行 P2P 网络连接，例如你在实验检查点 6 中使用的中继服务器
• 等级 9c：通过用户安装的显式 NAPT 规则（“端口转发”）进行 P2P 网络连接
• 等级 9d：通过 NAPT 穿透（又称“打洞”）进行 P2P 网络连接

你是一名应用程序开发者，正在考虑不同 P2P 网络风格的成本和收益。

(a) 对于哪些类型的 P2P 网络，应用程序开发者通常需要操作（或依赖）一个或多个位于公共互联网上的服务器？请检查所有适用的选项：
□ 等级 9a □ 等级 9b □ 等级 9c □ 等级 9d

(b) 对于你在上面勾选的每个等级，附加服务器的目的是什么？

• 等级 9a：
• 等级 9b：
• 等级 9c：
• 等级 9d：

(c) 对于哪些风格的 P2P 网络，开发者操作的服务器需要存储大量的状态信息（与被传输的数据量成比例，或者更糟）？
□ 等级 9a □ 等级 9b □ 等级 9c □ 等级 9d

(d) 对于哪些风格的 P2P 网络，开发者操作的服务器在连接期间需要使用大量的 CPU 或网络资源（与被传输的数据量成比例，或者更糟）？
□ 等级 9a □ 等级 9b □ 等级 9c □ 等级 9d

(e) 对于哪些风格的应用程序，至少需要一个用户位于一个 NAPT 后面，当它看到一个新的出站连接时，它会创建非限制性规则（又称“圆锥形” NAPT）？
□ 等级 9a □ 等级 9b □ 等级 9c □ 等级 9d

Ans

开始有点意思了，以下内容小写字母为题号，大写字母为选项。

显然ABD是需要服务器的。

区别于B的TURN，D的NAT hole punching是服务器负责交换两方的端点与会话信息，并不负责数据转发。所以c,d题是不包含d的，而由于不进行数据转发，所以需要至少有一个用户在锥形NAT后，即可以从发出消息的外部ip收到来自任何发送者的消息。对于锥形NAT策略参见下图()

所以a选ABD，c选A，因为只有a需要存储，其余为转发。d选AB，因为B需要进行字节流的构造和转发。e选D。

数据包交换

Question 15ps

在这个问题中，我们将考虑一个单一流量在一个两跳网络路径上的传输。路由器是“普通”的，并且以数据包为单位处理每个数据包（整个数据包必须到达后才能开始发送到下一个链路）。

(a) 假设网络中没有其他流量。如果发送方发送一个大小为 20 kbit 的单个数据包给接收方，这个数据包完全到达需要多长时间？（换句话说，它的总端到端延迟是多少？）请用毫秒表示你的答案。
(b) 如果发送方连续发送两个数据包，每个大小为 10 kbit，那么在路由器处，数据包 p2 经历的排队延迟是多少（以毫秒为单位）？
(c) 如果发送方连续发送两个数据包，第一个数据包大小为 10 kbit，第二个数据包大小为 p2，那么 p2 的最小大小是多少，以便排队延迟为 0？

水题 第二个包到达前第一个包已经离开排队延迟即为0。

公平策略

Question 15ps

在下面的网络中,发送方A向接收方a发送一个流量,发送方B向接收方b发送一个流量,发送方C向接收方c发送一个流量。x和y之间的链路速率为6兆比特每秒,y和z之间的链路速率也是6兆比特每秒。

a. 对这三个流量的最大最小公平分配吞吐量是多少?

b. 对这三个流量的最大利用率分配吞吐量是多少?(此分配最大化了三个流量的总吞吐量。)

c. 对这三个流量的比例公平分配吞吐量是多少?(此分配最大化了每个流量吞吐量对数之和。)

水题 鉴定为小学数学 其中 A->a B->b C->c 流量分别为 3，3，3 ； 6，6，0；4，4，2

路由

Question 12ps

请参考下面的网络图。节点代表路由器，每条链路旁边的数字代表该链路的成本。在接下来的问题中，你可以将“最短”和“最长”解释为“成本最低”和“成本最高”。

(a) 对于哪一对路由器，它们之间的最低成本路径是最大的？请以一对路由器名称给出答案；例如 (A, B)。
(b) 这条路径（你在部分 (a) 中确定的两个路由器之间的最低成本路径）的成本是多少？请以一个正整数给出答案。
(c) 至少需要同时失效多少条链路，才能阻止一对路由器相互通信？
(d) 假设这个网络使用我们在课堂上看到的简化版贝尔曼-福特算法来构建它的路由表，在该算法中，所有路由器与它们的邻居同步交换信息。如果所有路由器从头开始（即，距离向量初始化为无穷大），网络需要多少步才能达到最终的路由表配置？请以一个正整数给出答案。

模拟题 怪友善的 最后一问参考答案为4

弹性缓冲区

Question 25ps

在课堂上，我们讨论了如何使用弹性缓冲区来缓解接收方和发送方之间时钟速率的差异。假设你得到了以下参数：
• 最大传输单元（帧大小）为 MTU
• 数据包间隔时间为 p
• 弹性缓冲区大小为 B
进一步假设：
• 发送方发送的数据包大小正好等于 MTU
• 发送方在串行化一个数据包后总是等待时间 p，然后才开始串行化下一个数据包
• 当缓冲区半满时，读取器开始从弹性缓冲区读取数据，继续读取直到它读到一个数据包的末尾，并且在开始再次读取之前等待缓冲区再次半满。
• 传播延迟可以忽略不计
设 $r_{sender}$ 为发送方时钟的频率，$r_{receiver}$ 为接收方时钟的频率。假设 $r_{sender} > r_{receiver}$（我们担心的是溢出情况）。

(a) 当发送方开始发送一个数据包时，缓冲区包含 x 字节，$x \leq B/2$。写出一个代数表达式，表示发送方完成串行化数据包时缓冲区中将有多少字节：

(b) 将上述值称为“y”。在数据包间隔期间，接收方可以排空多少字节？
答案用：$\min(y, \;\;\;)$的形式

(c) 假设数据包间隔时间 p 足够长，以便接收方可以排空整个缓冲区。

• B 可以多小，以确保没有溢出？
• 画出随时间变化的缓冲区占用的图表，显示两个数据包被发送和接收。清楚地标记
  （1）线条的斜率
  （2）任何斜率变化时的缓冲区占用。

(d) 相反，假设 B 和 p 的组合刚好足够。换句话说，p 和 B 都尽可能小，同时仍然防止溢出。画出随时间变化的缓冲区占用的图表，显示完全有两个数据包被发送和接收。清楚地标记
（1）线条的斜率
（2）任何斜率变化时的缓冲区占用。

Ans

elastic buffer(弹性缓冲区)是用来缓解接收方和发送方之间时钟速率差异的常用措施。既然时钟频率不一样就难以同时一边send一边receive。

(a) 显然发送方发送了一部分之后缓冲区过半，之后接收方开始读取
$$\min(x + MTU - r_{receiver}\times\frac{MTU-(B/2-x)}{r_{sender}})$$

(b) $\min(y,r_{receiver})$

(c) $s.t. MTU-r_{receiver}\times\frac{MTU-B/2}{r_{sender}}$

(d) 因为p足够小，所以当上一个数据包被读到缓冲区剩一半时就可以发送下一个数据包了。
我们可以假设这样一种情况，假如第n+1个数据包到来时缓冲区占用过半，那么对于恒定的p，n+2个数据包到来时只会更糟。

总评

卷子是非常友好友善有意思的，没有要死记硬背的，比我校的卷子不知道强到哪里去了

完结撒花