国科大——计网（0812）——考试真题

前沿： 此篇文章记录了国科大秋季学期计网（0812）课程的一些考试真题，某些题目的答案仅供参考，还请自行辨别。

备注： 计网的考试题一般都会多一道，每道题的分值相同，例如：24年总共有11题，每题10分，最后计算成绩时，取top10分值计算。

2015年

1 假定有一个通信协议，每个分组都引入100字节的开销用于头和成帧。现在使用这个协议发送1M字节的数据，然而在传送的过程中有一个字节被破坏了，因而包含该字节的那个分组被丢弃。试对于1000、5000、20000和 40000 字节的分组数据大小分别计算“开销+丢失”字节的总数目？分组数据大小的最佳值是多少（提示：最佳值不是1000、5000、20000和40000辛节中的任一个）？

参考答案
注： 此题理解上可能会有一点歧义，但本质上计算方法是相同的。

假设分组大小为X，则分组数 N = 1M / X （或者是 1M / ( X-100 ) ），则“开销+丢失”的总数目为：N * 100 + X ，其中前者是开销的总数目，后者是丢失的总数目，由于X肯定为正整数，此时利用不等式求最小值即可。

2 考察下图中示出的透明桥接器的布局。假定开始时所有的转发表都是空的，试给出在下列的传输序列之后。桥接器B1-B4中的每一个的转发表的内容：

*A 给C传送
*C给A发送
*D给C发送

要求在表中用可以从一个端口可以直接到达的那个邻居结点来标识该端口，例如，B1 的两个端口可标识为
BI 的A端口和B1 的B2端口。

参考答案

注： 在FDB表为空的时候, 初始收到某个数据包且表中没有的时候,会选择广播给相邻的节点。 而如果表中有的话,就是选择这条记录然后单播。

3 什么对称加密算法，什么是非对称加密算法，各自的优续点是什么？RSA是对称加密算法还是非对称加密算法？假定在RSA 算法中，两个质数 p=3，q=5，求解对明文10加解密的全过程？

参考答案：
（1）

（2）非对称加密算法。

（3）RSA 算法流程如下：

a. 选择两个大素数（质数）p和q
b. 计算 n=p×q 和 m=(p-1)×(q-1)
c. 选择一个与m互质的数，令其为d
d. 找到一个 e 使满足 e x d = 1 (mod m)
e. 公开密钥为(e，n)，私有密钥为(d，n)
f. 设明文为M，则加密过程：C = M^e mod n ，解密过程为：M‘ = C^d mod n

本题中，p = 3，q = 5，M = 10，因此，n = 15，m = 8，令 d = 3，则e = 3，满足 e ✖️ d = 1 （mod m）。随后，对明文M进行加密得到 C = M^e mod n = 10^3 mod 15 = 10，对C进行解密可以得到 C^d mod n = 10^3 mod 15 = 10 = M 。

4 CDN 通常根据客户端所使用的 DNS服务器地址，来指定为客户端提供数据的CDN服务器。例如，根据国科大自动配置的DNS服务器，为国科大怀柔小区的客户端选择位于怀柔数据中心的服务器。请分析这种根据 DNS服务器地址来为客户端选择CDN 服务器的优劣势，以及如何改进来避免存在的劣势。

参考答案：

优势：当用户访问已经加入 CDN 服务的网站时，首先通过 DNS 重定向技术确定最接近用户的最佳 CDN 节点，同时将用户的请求指向该节点。

劣势： 其实在 DNS 查询过程有一个这样的问题，权威服务器接收请求的时候，只能得到 local DNS 的 IP，并不知道 client IP。一般如果 Local DNS 设置不当，例如没有使用当前 ISP 提供的 Local DNS 这种实现方式可能会误判用户的位置， 从而将用户误导到错误的CDN 缓存节点，造成加速效果差的问题。

改进：利用 end-user mapping 的技术，通过 client IP 地址的前缀，来对 client 进行识别。

5 数据中心网络内部构成一个网络。请从网络管理、协议设计的角度，定性对比数据中心网络和互联网网络。

参考答案：

6 （1）什么是主动测量，什么是被动测量，它们各自的优缺点？（2）什么是链路带宽，什么是可用带宽？（3）打开一个视频网站发现在线视频的加载速度通常都达不到家里宽带带宽，请分析各种可能的原因。

参考答案：
（1）

（2）
链路带宽： 该链路上数据报文的最大传输速率。
可用带宽： 当应用程序和其它背景流(Cross Traffic)共享网络路径时，该应用程序所能得到的带宽。也就是指网络在不降低其它业务流的传输速率的情况下，所能提供给一个业务流的最大传输速率。

7 给定一个路由转发表如下表所示，路由器收到数据包后，按照最长前缀匹配方式查找 IP地址的相应转发端口。对于如下IP地址列表，请写出每个地址对应转发接口。

（1）10.1.1.1
（2）192.168.240.1
（3）192.168.136.1
（4）192.168.224.1
（5）192.168.128.1
参考答案：
（1）D （2）C （3）B （4）C （5）A

8 TCP/IP 体系结构对移动性支持不好的主要原因是什么？为什么？如何解决？

参考答案：
（1）原因：
a. IP 地址的二义性，既表示位置（移动过程中改变），又表示身份（移动过程中不变），即位置和身份的紧耦合；
b. 不支持地址和身份的动态绑定。
(2) 解决思路：

a. 假设移动主机有一个永久的 IP 地址，称为本地地址(home address)，作为 identifier，与移动前的网络拥有相同前缀。
b. 主机移动到新的网络时，获得新的 IP 地址，作为 locator。
c. 两个地址可以共存，locator 负责接收数据，identifier 负责解复用数据。

9 Timeout Retransmission（超时重传）对 TCP传输性能的影响体现在哪几个方面？为什么说超时重传对高大宽、高时延（RTT）的网络影响最大？是否可以直接减小 RTO时间来减小超时重传的影响？

参考答案：
首先 RTO 可能是 RTT 的几个数量级以上，在 RTO 时间内不能传输数据，因此将会使发送端经过较长时间的等待才能发现报文段丢失，降低了连接数据传输的吞吐量。此外，超时重传会导致进入 slow start。

TCP 根据得到的 RTT 值更新 RTO 值，发送端对每个发出的数据包进行计时，如果在RTO 时间内没有收到所发出的数据包的对应 ACK，则任务数据包丢失，将重传数据，若RTO 较大，则系统在长时间内无法发送数据包，此时若系统带宽也很大，则造成了资源的大量浪费。

若 RTO 过小，发送端尽管可以很快地检测出报文段的丢失，但也可能将一些延迟大的报文段误认为是丢失，造成不必要的重传，浪费了网络资源。

10 考虑下图所示的子网。使用距离向量路由选择，下列向量刚刚被路由器C收到：

来自B：（5，0，8，12，6，2）
来自D：（16，12，6，0，9，10）
来自E：（7，6，3，9，0，4）
路由器C测量得到的到达B、D和E的延时分别等于6，3和5。试问路由器C的新的路由表是什么？请给出所使用的输出线路和所预期的延时。

参考答案：
此时链路中的距离向量矩阵如下：

根据距离向量算法，可以对C的路由表进行更新，更新后的路由表为：

2016年

1 假定有一个通信协议，每个数据分组都引入 100字节的开销用于头和成帧。现在使用这个协议发送 1 M 字节的数据（为方便计算，1M=10^6），然而在传送的过程中有一个字节被破坏了，因而包含该字节的那个分组被丢弃并重传。（1）、当数据分组大小分别为1000、5000、20000和40000字节时，计算相应（包括开销）的传输字节总数目。（2）、计算分组大小的最优值是多少，即分组大小为何值时总的传输字节数最少。（提示：最优值不是1000、5000、20000 和 40000字节中的任何一个）

参考答案

2 给定一个路由转发表如下表所示，路由器收到数据包后，按照最长前缀匹配方式查找IP 地址的相应转发端口。对于如下IP地址列表，请写出每个地址对应的转发端口。

（1）10.1.1.1
（2）192.168.240.1
（3）192.168.136.1
（4）192.168.224.1
（5）192.168.128.1

参考答案
（1）D （2）C （3）B （4）C （5）A

3 考虑下图所示的子网。使用距离向量路由选择，下列向量刚刚被路由器C收到：

来自B：（5，0，8，12，6，2）
来自D：（16，12，6，0，9，10）
来自E：（7，6，3，9，0，4）
路由器C测量得到的到达B、D和E的延时分别等于6，3和5。试问路由器C的新的路由表是什么？请给出所使用的输出线路和所预期的延时。

参考答案：
a） C到A选B，到F选B
b) 延时：（11, 6, 0, 3, 5, 8)

4 简述 TCP/IP 体系结构对移动性支持不好的主要原因，以及可能的解决方案。

参考答案：
主要原因：
1）IP地址既表示地址，又标识主机。当移动后，IP地址发生变化。
2）连接和IP 地址绑定，当IP地址变化时，连接只能断开。
几种可能的方案：
1）Mobile IP 技术；
2）连接和IP地址解绑定，当IP地址变化时，移动一方通告对方自己新的地址，两端的应用连接不断开。
3）使用NDN等类似机制。

5 请描述“在浏览器中输入网址，到取回网页”这段时间内发生的网络操作。

参考答案：
a）网址域名 DNS 查询，解析到对应IP 地址；
b）生成HTTP 请求，封装 TCP/IP 数据包；
c）查询IP地址对应的网关和下一跳IP地址；
d）查询下一跳IP地址对应的Mac地址；
e）把数据转发到网关；
f）经过路由寻址抵达网页服务器；
g）网页服务器解析，返回所需具体页面；

6 （1）、什么是主动测量，什么是被动测量，它们各自的优缺点？（2）、什么是链路带宽，什么是可用带宽？（3）请简述一种测量可用带宽的经典算法的工作原理。

参考答案：
a） 主动测量是主动发送探测数据进行测量，被动测量是被动捕获数据进行测量。前者更有针对性，但容易有偏采样，探测数据也可能对背景流量产生影响；后者不会对网络背景流量产生影响，但测量没有针对性。
b）链路带宽是指链路每秒钟传输的最大字节数；可用带宽是指网络在不降低其他业务流的传输速率的情况下，所能提供给一个业务流的最大传输速率
C）测量可用带宽的经典算法
1）、探测报文间隔模型：从发送端发送两个连续数据包，设数据包发送的时间间隔为Tin，接收端接受这对数据包的时间间隔为 Tout，数据包大小为L，网络最大带宽为C，则可用带宽为A=C*（1-（Tout-Tin）/Tin）；

2）、探测报文速率模型：当测试报文发送速率小于链路可用带宽时，传输时延相对固定，当测试报文发送速率大于链路可用带宽时，网络出现排队现象，传输时延增大，两种状态之间的那个点即为可用带宽。

7 （1）加密分为单钥加密体制和公钥加密体制，请从计算效率和密钥管理两方面的特性分析这两种模式的优缺点：（2）、RSA 是对称加密算法还是非对称加密算法？假定在RSA 算法中，两个质数p=5，q=7，求解对明文了加解密的全过程？

参考答案：

8 一个“客户-服务器”系统的性能受到两个网络因素的影响：网络带宽（每秒传输多少位）和延迟（第1位从客户传播到服务器花多少秒的时间）。（1）、带宽和延迟成反比关系吗？如果是，请阐迷其关系；如果否，试给出一个具有高带宽高延迟的网络的例子，再给出一个具有低带宽低延迟的网络的例子。（2）、除了带宽和延迟，还需要什么其它的参数，才能很好地刻画一个用于视频传输网络所提供的服务质量？

参考答案：
a） 带宽和延迟不成反比，高带宽高延迟：卫星链路；低延迟带宽：56kbps 调制解调器。
b） 启动时间、缓冲时间、卡顿率等。

9 在标准 TCP 实现中，TCP 连接空闲多长时间就会在下次发送数据包时，触发慢启动（简称 SSAI,Slow start afer idle）？请简述此时重新从慢启动开始的原因。是否可以把SSAI 直接关闭掉，请简述原因

参考答案：
a）1个RTO.（即超时重传时间）
b） 重启慢启动是需要重新探索可用带宽。
c） 两种答案：1）、可以，因为这样可以节省吞吐率从。增长到可用带宽的时间；2）、不可以，因为在1个 RTO 时间内，有可能有新建的流占用了已有带宽，这时还用原来的窗口大小（发送速率）会导致拥塞。（回答任一一种即可）

10 在数据中心网络中，多个发送端向一个接收端发送数据时，会带来 TCP Incast 问题。请简述 TCP Incast 问题发生的原因，以及可能的解决方案。

参考答案：
a） TCP Incast 问题：当多条并发流到达同一交互机设备时，突发流量容易造成丢包。
b） 解决思路：
i.增加设备缓冲区大小
ii.在中间设备增加通知功能，通过显式通知发送方哪些数据包丢失，尽快恢复丢包。

11 下图是 OpenFlow 局域网络拓扑，S1 的流表包含一条转发规则，Controller 持有全局网络的拓扑信息。请描述 Packet 1从C1 到H2的转发过程，包括流表查询、流表安装流程以及具体的流表转发规则。

参考答案：
1） 首先，数据从C1唯一的端口转出，发到S1
2） S1 查询流表，匹配不到对应条目，，因此将该数据包缓存下，并查询 Controller。
3） Controller 下发规则至S1，规则内容为“DstIP =H2, Outport = 2”。
4）S1 按照相应规则，将数据包从 Port 2转出，至S2。
5）S2 收到数据包后，找不到对应规则，因此也将该数据包缓存下，并查询Controller。
6）Controller 下发规则至S2，规则内容为”DstIP = H2,Outport= 2”（注意，这一步可以与第3步合并，即 Controller 同时给S1和S2 下发规则）
7）S2 查询到相应规则后，将数据包从 Port2 转出，至H2

2017年（不全）

1 试描述“在浏览器中输入网址，到取回网页”这段时间发生的网络操作。

参考答案
1.网址域名 DNS 查询，解析对应的 IP 地址。
2. 生成对应的 HTTP 请求，封装 TCP/IP 数据包。
3. 查询 IP 地址对应的网关和下一跳的 IP 地址。
4. 查询下一跳的 IP 地址对应的 Mac 地址。
5. 把数据转发给网关。
6. 经过路由寻址抵达网页服务器。
7. 网页服务器解析，返回所需具体页面。

2 一个“客户-服务器”系统的性能收到两个网络因素的影响：网络带宽（每秒传输多少位）和延迟（第 1 位从客户传播到服务器要花多少秒的时间）。（1）带宽和延迟成反比关系吗？如果是，请阐述其关系；如果否，请给出一个具有高带宽，高延迟的网络的例子，再给出一个具有低带宽低延迟的网络的例子。（2）除了带宽和延迟，还需要什么其他的参数，才能很好的刻画一个用于视频传输网络所提供的服务质量？

参考答案
（1）带宽与延迟不成反比。高带宽高延迟：卫星链路；低带宽低延迟：56kbps 调制解调器。横贯大陆的光纤连接可以有很多千兆位/秒带宽，但是由于光速度传送要越过数千公里，时延将也高。相反，使用 56 kbps 调制解调器呼叫在同一大楼内的计算机则有低带宽和较低的时延。
（2）还需要启动时间、缓冲时间、卡顿率等。丢包率，网络中数据的传输是以发送和接收数据包的形式传输的，理想状态下是发送了多少数据包就能接收到多少数据包，但是由于信号衰减、网络质量等等诸多因素的影响下，可由丢包率来判定视频传输质量，丢包率越小，则该网络质量越好。

3 在标准的 TCP 实现中，TCP 连接空闲多长时间就会在下次发送数据包时，触发慢启动（简称 SSAI）？请简述此时重新从慢启动开始的原因。是否可以把 SSAI 直接关闭掉，请简述原因。

参考答案：
答：（1）1 个 RTO。
（2）重启慢启动是需要重新探索可用带宽。慢启动的目的是，使 TCP 在用拥塞避免探寻更多可用带宽之前得到 cwnd 值，以及帮助 TCP 建立 ACK 时钟。通常，TCP 在建立新连接时执行慢启动，直至有丢包时，执行拥塞避免算法进入稳定状态。在传输初始阶段，由于未知网络传输能力，需要缓慢探测可用传输资源，防止短时间内大量数据注入导致拥塞。慢启动算法正是针对这一问题而设计。在数据传输之初或者重传计时器检测到丢包后，需要执行慢启动。
（3）两种答案：1.可以。因为这样可以节省吞吐率从 0 增长到可用带宽的时间。 2. 不可以。因为在一个 RTO 时间内，有可能有新建的流占用了已有带宽，这时用原来的窗口大小（发送速率）会导致拥塞。（回答一种即可）

4 在数据中心网络中，多个发送端向一个接受端发送数据时，会带来 TCP Incast 问题。请简述 TCP Incast 问题发生的原因，以及可能的解决方案。

参考答案：
（1）TCP Incast 问题当多条并发流到达同一交换机设备时，突发流量容易造成丢包。从根本上讲是由于传统的 TCP/IP 协议在设计之初针对的是带宽较低、延迟较大、地理分布广泛而连接较为稀疏的互联网，而 TCP 协议不能很好地适应数据中心网络高带宽、低延时、地理分布集中而连接密集的特点。
（2）
1.增加设备缓冲区的大小。
2.往中间设备增加通知功能，通过显示通知发送方哪些数据包丢失，尽快回复丢包。在数据中心的链路层，拥塞通知和流控是缓解 TCP Incast 问题的两个主要方法。传输层缓解或解决 TCP Incast 问题的解决方案主要分为三大类：
（1）参数调整。改善 DCN 中 TCP 重传的机制，使 得重传尽快执行，提升吞吐量。
（2）传输机制优化。通过改进拥塞控制，尽量避 免或减少瓶颈链路交换机缓存区占满的情况，减少 丢包，降低 TCP Incast 问题发生概率。
（3）协议替换。通过采用其他传输协议，从根本 上解决该问题中 TCP 协议带来的弊端。

5 下图是 OpenFlow 局域网络拓扑，S1 的流表包含一条转发规则，Controller 持有全局网络的拓扑信息，请描述 Packet 1 从 C1 到 H2 的转发过程，包含流表查询、流表安装流程以及具体的流表转发规则。

参考答案：
1）首先，数据从 C1 唯一的端口发出，发到 S1；
2）S1 查询流表，匹配不到对应条目，因此该数据包缓存下，并查询 Controller。
3）Controller 下发规则至 S1，规则内容为：“DstIP=H2，Outport=2”.
4）S1 按照相应规则，将数据包从 PORT2 转出，至 S2
5）S2 收到数据包后，找不到对应规则，因此也将该数据包缓存下，并查询 Controller
6）Controller 下发规则至 S2，规则内容为 DstIP=H2,output=2
7）S2 查询到相应规则后，将数据包从 port2 转出，至 H2。

2019年

1 互联网体系结构可自下而上分为链路层，网络层，传输层和应用层，请简述各层主要功能，与代表性协议，以及该分层模型的优缺点。

参考答案
链路层：在两个相邻节点传输数据时，将网络层交下来的IP数据报组装成帧，在两个相邻节点
之间的链路上传送帧。PPP点对点协议、计算机与ISP通信时使用的数据链路层协议、CSMA/CD协议 普通局域网内部使用、SLIP串行线路接口协议、HDLC高级链路控制协议。
网络层： 负责为分组网络中的不同主机提供通信服务，并通过选择合适的路由将数据传递到目标主机。在发送数据时，网络层把运输层产生的报文段或用户数据封装成分组或包进行传送。 IP网际协议、ICMP网际控制消息协议以及ARP地址解析协议。
传输层：为两台主机中的进程提供通信服务。TCP传输控制协议，提供面向连接的、可靠的数据传输服务。UDP用户数据报协议，提供无连接的、尽最大努力的数据传输服务，但不保证数据传输的可靠性。
应用层：通过进程间的交互完成特定网络应用。HTTP/HTTPS协议、SMTP电子邮件协议以及FTP文件传送协议
优点：各层之间是独立的、灵活性好、结构上可分割开、易于实现与维护、促进标准化工作。
缺点：层次划分得过于严密，以致不能越层调用下层所提供的服务，降低了协议效率，浪费了性能。

2 交换机/路由器将待处理的数据包放到缓冲队列中，缓冲队列的大小对设备的转发性能有很大的影响，请简述队列过大或过小对传输流的性能影响。RED 机制可以缓解队列过大带来的性能问题，请简述该机制的运行过程。

参考答案
队列过大时，若使用TCP滑动窗口下的传输控制策略，当窗口大小减半时，队列不能清空数据包，因此数据包的延迟会增加，般情况下时延的增加会导致抖动也增加。

队列过小时，当滑动窗口大小减半，发送方在等待对方的数据确认，瓶颈链路处于空闲状态。

随机早期检测算法RED，基本思想是通过监控路由器输出端口队列的平均长度来探测拥塞，一旦发现拥塞逼近，就随机地选择连接来通知拥塞，使他们在队列溢出导致丢包之前减少拥塞窗口，降低发送数据速度，从而缓解网络拥塞。RED基于FIFO队列调度策略，只是丢弃正在进入路由器的数据包。RED有两个和队列长度相关的阈值：minth和maxth。当有包达到路由器时，RED计算出平均队长avgQ。若avgQ小于minth，则没有包需要丢弃；当minth≤avgQ≤maxth时，计算出概率P，并以此概率丢弃包；当avgQ>maxth时，所有的包都被丢弃，于RED使用的是基于时间的平均队长，就有可能会发生实际队长大于平均队长的情况，如果队列已满，则到达的包只能被丢弃。

3 OSPF 路由协议的核心是链路状态机制，请简述该协议的运行原理，拓扑变动后的收敛过程以及如何拓展到规模更大的网络环境的方法。

参考答案：
OSPF开放最短路径优先，OSPF 是基于IP的，其协议号是89。需要每个路由器向其同一管理域内的所有其他路由器发送链路状态广播信息，每台路由器都会收集其它路由器发来的LSA，所有的LSA放在一起便组成了链路状态数据库LSDB。通过交互Hello报文形成邻居关系，通过泛洪LSA通告链路状态信息，通过组建LSDB形成带权有向图，通过SPF最短路径优先算法计算并形成路由维护和更新路由表。当OSPF路由域规模较大时，一般采用分层结构，即将OSPF路由域分割成几个区域（AREA），区域之间通过一个骨干区域互联，每个非骨干区域都需要直接与骨干区域连接。区域内每个节点计算到其他所有节点的路由路径，区域外节点只知道其他区域的路由路径，跨区域的数据包首先会路由到最近的边界路由器节点。区域可以进一步划分成若干子区域，两点之间的路由路径可能不再是最短路径。

4 TCP 拥塞控制机制，包括慢启动、拥塞避免、快速重传、快速恢复等功能，这些功能共同完成了数据流的高可靠和高性能传输，请简述每种功能的原理和设计目标。

参考答案：
慢启动：为了防止大量的数据导致网络阻塞，一个新建立的连接在开始的时候会将cwnd初始化为1，即只会发送一个MSS的数据，每次报文段被确认都会在原有的基础上乘2。
拥塞避免：慢启动的增长速度极快，因此如果一直使用慢启动的话，网络必定是承受不住的。因此需要一个限制来确保传输不会过快，这个限制就是 ssthresh，而这个限制的过程就是拥塞避免。在当前的cwnd值小于ssthresh时，TCP执行慢启动，当cwnd达到ssthresh时，开始执行拥塞避免，每经过一个RTT，cwnd将在原有基础上加1。若发生丢包，即当 TCP 超过 RTO 还没有收到对数据的确认的话，将会调整自己的发送速率，主要做以下几件事：
a. 将此次连接的 ssthresh 设置为当前 cwnd 值的一半;
b. 将 cwnd 值设置为 1，重新进入慢启动阶段
快速重传: 如果每个包的丢失都要等一个 RTO 才能重传的话，会浪费很多时间。当发送端连续收到 3 个重复的 ACK 时，将会触发快重传机制。发送端立即重发丢失的包，然后进入快恢复阶段。
快速恢复:执行了快速重传说明网络也不那么糟糕，所以没有必要像RTO超时那么强烈，并不需要重新回到慢启动进行，这样可能降低效率。将 ssthresh 设置为当前 cwnd 值的一半，将 cwnd 的值设置为 ssthresh + 3，加 3 是因为收到了三个重复的 ACK，表示有三个“老”的数据包离开了网络，之后如果继续收到重复的 ACK 的话，每个重复的 ACK 将导致当前 cwnd + 1，当收到一个新的 ACK 的时候，快恢复结束。将 cwnd 的值设置为 ssthresh，重新进入拥塞避免阶段。

5 请简述“在浏览器中输入网址到获取网页内容”这段时间内发生的操作。

参考答案：
1.网址域名 DNS 查询，解析对应的 IP 地址。
2. 生成对应的 HTTP 请求，封装 TCP/IP 数据包。
3. 查询 IP 地址对应的网关和下一跳的 IP 地址。
4. 查询下一跳的 IP 地址对应的 Mac 地址。
5. 把数据转发给网关。
6. 经过路由寻址抵达网页服务器。
7. 网页服务器解析，返回所需具体页面。

6 请简述基于 Trie 树的 Ipv4 路由表查找算法的时间和空间复杂度以及基于 Ipv6 的路由表的查找算法的优化方法。

7 简述区块链上数据不可伪造、不可抵赖、难以删除和难以篡改的技术原理，请举出现实生活中用区块链技术解决实际问题的一个实例，并说明区块链解决了其中的什么问题

参考答案：
从宏观上，采用分布式平等部署系统、分布式共享相同数据；无中心化控制，全网参与的节点协作完成交易验证和存储。从微观上，数据储存在块中，这些块在逻辑上串联起来构成链条；应用数字签名与完整性校验保证块数据的真实性、时序性、完整性。在技术层面具有不可伪造、不可抵赖、不可篡改、不可撤销等属性，在应用层面具有分布式的公开透明、交易可跟踪等特征。在将区块链应用到支付清算结算系统中，可以帮助解决证券系统T+1到账资金滞后、跨行对账、转账带来的高昂业务成本等等。

8 BBR 是 Google 提出的一种拥塞控制算法，其核心思想是测量最小RTT和瓶颈链路的可用带宽，请简述为什么最小RTT和瓶颈链路的可用带宽不能同时测得，以及如何才能较为准确地测量这两个值。

参考答案：
BBR算法不再基于丢包判断并且也不再使用AIMD线性增乘性减策略来维护拥塞窗口，而是分别采样估计极大带宽和极小延时，并用二者乘积作为发送窗口，并且BBR引入了Pacing使得数据发送速率接近估计的传输通道瓶颈带宽，对pacing rate进行调制，来保持传输中的数据量接近估算得到的带宽延时积（BDP），配合cwnd使用来降低冲击。
要测量最大带宽，就要把瓶颈链路填满，此时buffer中有一定量的数据包，延迟较高。
要测量最低延迟，就要保证buffer为 空，网络中数据包越少越好，但此时带宽较低。

只能交替测量带宽和延迟，用一段时间内的带宽极大值和延迟极小值作为估计值。

带宽采用max{过去10个RTT的所测的带宽}，最小RTT采用min{过去10秒的最小值}，如果10s内没更新minRTT，则测一次（4个MSS）。

9 负载均衡是数据中心网络中提升带宽利用效率的重要机制，请简述数据包级别的负载均衡和数据流（flow，五元组标识）级别的负载均衡的优劣势。

10 CDN 依赖于 DNS 实现用户到服务器的映射，假设使用传统 DNS 协议，用户侧配置公用的 DNS 服务器（如 8.8.8.8）和使用运营商自动配置的本地 DNS 服务器会对这种映射造成什么影响？如何缓解这种影响？

参考答案：
CDN服务本身并不具备DNS解析功能，而是依托于DNS智能解析功能，由DNS根据用户所在地、所用线路进行智能分配最合适的CDN服务节点，然后把缓存在该服务节点的静态缓存内容返回给用户，使用公用的DNS将很难享受智能 DNS 和 CDN 加速的便利，而使用运营商自动配置的DNS大概率将是路径最短、延时最低具有一定的先天优势。使用公用的DNS可能最终映射到的不是最合适的服务器。

11 NDN 等未来互联网体系结构试图改变 TCP/IP 协议的哪些方面，为什么这些新型的互联网体系结构部署比较困难？

参考答案：
试图改变的问题：

1. 效率低。管道是单源单路径的，容易造成拥塞，比如同一个视频，要从单个服务器发送无数次。
2. 可扩展性差。不断打补丁，网络设计管理越来越复杂。IP地址也不够用了。
3. 安全性弱。重视管道保护，但不能保证数据本身的可靠性。比如建立一个信任连接后，对方发的恶意代码也会照收无误。

NDN核心思想：

1. 用户程序只提供数据的名字，无需目的地址；
2. 数据可以来自任何节点；（不用都从服务器拿数据，可以从就近的缓存获取）
3. 每个数据包必须有数字签名；（保证安全可靠）新型的互联网体系结构部署比较困难：相关研究还在发展阶段，大规模部署尚需时间，且现有TCP/IP体系已经很庞大，如何过渡和共存很难兼顾，部署新型互联网体系结构带来的短期经济效益过低。

2020年

1 最小生成树机制能够在有环的物理网络中构造出一个无环的树状逻辑拓扑，在保证网络连通性的同时避免广播风暴。当网络是静态时，即不存在节点/链路的加入和删除，网络对应的最小生成树拓扑是否是唯一的？请简述原因或举例说明。

参考答案
不一定，例如一个正方形网络中，每个顶点各有一个节点，每条边的权重是1，对于某个点，它的最小生成树拓扑有两个。

2 考虑下图中的网络拓扑，每条边上的数字代表对应链路的代价，使用距离向量方法进行网络路由选择，当前节点A和C的路由表项分别如下两个子表所示，当两个节点分别收到节点 B的距离向量信息（A：2，B：0, C:4,D：2,E:1,F:3）后，试更新两个节点的路由表项。

3 基于路由转发表表项进行最长前缀，确定下一跳转发路径，是路由查找转发的基本动作。Trie查找是主要路由查找算法之一，下图(a)是路由表示例，图(b)是对应的 Trie 数据结构。请描述IPv4 路由查找中 Trie 查找过程，分析时间复杂度与空间复杂度。

参考答案：
二分思想

4 TCP 通过 AIMD （Additive Increase Multiplicative Decrease，和性增，乘性减）机制来探测可用带宽和保障竞争流间的公平性。只考虑 AIMD机制，试在如下图（a）中画出一个 TCP 流的拥塞窗口随时间变化的形状，并说明该形状的变化周期；对于两个竞争流，从如下图（b）中的起始点出发，在图中画出两个竞争流的发送速率收敛到最优点过程中的变化曲线。

参考答案：

5 TCP 传输协议中，发送的字节数与吞吐（Throughput）以及 RTT 的关系如下图所示。假设，路径的传播时延为RTTprop，瓶颈链路带宽为BW，瓶颈链路处的队列长度为Q。请问 1）D1, Slope1，Slope2, S1, S2分别为多少？2）BBR根据传播时延与瓶颈链路带宽的乘积设置拥塞窗口，如何测得传播时延 RTTprop，以及瓶颈链路带宽BW？

参考答案：

6 假设不使用EDNS，当客户端使用Google8.8.8.8等公共DNS解析服务器进行内容访问时，CDN有可能会给用户分配的 CDN 服务器离客户端距离较远，原因是什么？EDNS为什么能协助解决这个问题？Google的8.8.8.8使用Anycast 技术也能一定程度上缓解该问题，请问原理是什么？

参考答案：
目前大部分 CDN 或者 DNS 智能解析是根据客户 Local DNS IP 来进行调度的。没有使用当前 ISP 提供的 Local DNS 这种实现方式可能会误判用户的位置， 从而将用户误导到错误的 CDN 缓存节点，造成加速效果差的问题。为解决CDN精确调度的问题，Google等互联网公司提出了edns-client-subnet扩展协议（ECS协议），通过附加字段
传递原始用户网络地址给权威DNS，从而权威DNS可根据原始用户源地址信息实现精准调度。从而协助解决上述问题。Anycast多个主机使用相同ip地址的一种技术，当报文发给该地址时，根据路由协议，选择最近（跳数最少）的主机服务。

7 什么是链路带宽，什么是可用带宽？请分别列举一种测量瓶颈带宽和可用带宽的方法并简述其原理。

参考答案：

链路带宽是指该链路上数据报文的最大传输速率；
可用带宽是指网络在不降低其他业务流的传输速率的情况下,所能提供给一个业务流的最大传输速率。
自源端向目的端发送主动测量包，当测量包的速率大于可用带宽时，在链路瓶颈带宽上的探测包就会发生排队现象，测量包之间的时间间隔就会发生变化，通过研究这种时间间隔变化就能得到链路可用带宽值。
可以统计一个包从发出到收到 ACK 的时间间隔，再统计这段时间内的未确认包数，就可以计算出瓶颈带宽。

8 数据中心网络问题：1）ECMP（Equal Cost Multi Path）是如何实现流级别的负载均衡的？流级别负载均衡和数据包级别的负载均衡优、劣势是什么？2）基于ECN的拥塞控制在数据中心网络中广泛使用，简述其原理，以及为什么能缓解 TCP Incast 问题。

参考答案：
1）ECMP是一个逐跳的基于流的负载均衡策略，当路由器发现同一目的地址出现多个最优路径时，会更新路由表，为此目的地址添加多条规则，对应于多个下一跳。可同时利用这些路径转发数据，增加带宽。流级别的负载均衡可能增加链路的拥塞，在非对称网络使用效果不好，基于流的负载均衡效果不好。基于数据包的负载平衡可以确保所有链路上的负荷保持均衡，不过，数据包到达目标的顺序可能会乱，因为网络内可能存在各种延迟。对于基于数据包的负载平衡，转发进程会通过查询路由表并选择使用频率最低的接口来确定每个数据包的出接口。这样可以保证均衡利用链路，但却是一项需要大量占用处理器的任务，并且会影响整体转发性能。这种基于数据包的负载平衡并不太适合速度较高的接口。

2）ECN 是报文在网络设备出口发生拥塞时，将使能ECN（当IP 报文的ECN 字段为01 或10，表示使能ECN）的IP 报文头部的ECN 字段标记ECN=11，表示该IP 报文遇到网络拥塞，且该IP 报文不会被WRED 机制丢弃。如果接收服务器发现IP 报文的ECN 字段被标记成11，就立刻产生CNP 拥塞通知报文，并将该报文发送带源服务器，CNP 消息里包含了拥塞的数据流信息，远端服务器接收到后，通过降低相应的数据流发送速率，环节网络设备拥塞，从而避免发生丢包。
TCP Incast 也用于描述由 Incast 通信模式导致的网络拥塞。短时内的流量激增会导致接收服务器的所对应的交换机的出口处发生拥塞，交换机的出端口的缓存溢出，使得部分数据包被丢弃，而发送服务器感知到丢包之后需要重传之前的数据包，最终导致单个TCP 流的报文吞吐增长缓慢。ECN能够通告发送端降低其发包速率，降低网络拥堵情况。

9 1）未来互联网体系结构NDN、SOFIA、MobilityFirst等都强调名字（Name）与地址（Address）的分离，请问名字与地址分离解决什么问题？2）与TCP/IP体系结构不同，NDN是接收端驱动的，即接收端发送 Interest数据包，发送端收到Interest 数据包后才回复Data，且Data 沿着Interest数据包的反向路径发送给接收端。这样做的好处与劣势是什么？

参考答案：
1）IP地址耗尽问题，内网穿透问题，移动性问题，可扩展地址管理问题，打破传统的C/S结构，解决了TCP/IP网络下热门服务器负载过重的问题。不存在与地址的绑定，天然支持内容移动性。数据和网络安全性高。

2）基于名字路由的可拓展性更优。支持缓存，原路返回的反馈式流量平衡机制——流量，负载均衡；组网传播。基于逐跳的报文包转发——减少冗余传输。劣势是带状态网络将使得网络设备的实现和维护复杂，路由表查找也会变得复杂。

10 区块链里的数字签名使用的是非对称密钥加密,请论述非对称密钥加密的工作原理以及相比于对称密钥加密的优势和劣势。

参考答案：
非对称加密需要两个密钥：公钥 (publickey) 和私钥 (privatekey)。公钥和私钥是一对，如果用公钥对数据加密，那么只能用对应的私钥解密。如果用私钥对数据加密，只能用对应的公钥进行解密。因为加密和解密用的是不同的密钥，所以称为非对称加密。
(1) A 要向 B 发送信息，A 和 B 都要产生一对用于加密和解密的公钥和私钥。
(2) A 的私钥保密，A 的公钥告诉 B；B 的私钥保密，B 的公钥告诉 A。
(3) A 要给 B 发送信息时，A 用 B 的公钥加密信息，因为 A 知道 B 的公钥。
(4) A 将这个消息发给 B (已经用 B 的公钥加密消息)。
(5) B 收到这个消息后，B 用自己的私钥解密 A 的消息。其他所有收到这个报文的人都无法解密，因为只有 B 才有 B 的私钥。

非对称加密算法的保密性好，它消除了最终用户交换密钥的需要。但是加解密速度要远远慢于对称加密，在某些极端情况下，甚至能比对称加密慢上1000倍。对称加密需要协商密钥，而非对称加密可以安全地公开各自的公钥，在N个人之间通信的时候：使用非对称加密只需要N个密钥对，每个人只管理自己的密钥对。而使用对称加密需要则需要N*(N-1)/2 个密钥，因此每个人需要管理 N-1 个密钥，密钥管理难度大，而且非常容易泄漏。

11 区块链的共识算法的作用是什么？请描述一个区块链应用场景，并论述区块链技术主要解决了场景里面的什么问题，是如何解决的。

参考答案：

共识算法作为区块链技术的核心，对区块链安全、效率等方面有着决定性的作用。区块链则是通过分布式的节点共同验证交易来解决双花问题。 区块链中，一笔交易需要经过足够数量共识节点的验证，在确认无误下对交易进行记录并同步给网络中所有的共识节点。在将区块链应用到支付清算结算系统中，可以帮助解决证券系统T+1到账资金滞后、跨行对账、转账带来的高昂业务成本等等。

2022年

1 互联网体系结构可自下而上分为物理层、网络层、传输层和应用层，请简述各层主要功能与代表性协议，以及该分层模型的优缺点。

2 RIP 和 OSPF 是两个典型的域内路由协议，都是基于域内路由节点之间相互交换信息，通过相应的路由算法计算生成路由表。现假设在一个自治域使用 RIP 协议或者 OSPF 协议，请回答下列问题：

a) 路由节点之间相互交换什么信息？请以一个路由器为例，针对RIP和OSPF分别进行回答。
b) 对于一条节点间交换的信息来说，该信息被交换的范围（即该信息会被传送给哪些节点）
是什么？请针对 RIP 和 OSPF 分别进行回答。

3 基于路由转发表进行最长前缀匹配，确定下一跳转发节点，是路由查找转发的关键操作。Trie查找是常用路由查找算法之一，下表是路由表示例，请给出下表对应的单比特 Trie 示意图与Trie 节点数据结构定义。对于 IPv4 路由查找，对比单比特 Trie 与 2 比特 Trie 的查找时间与转发表存储空间开销。

4 . IPv6 路由查找算法中，转发表中每条规则由目标地址前缀和下一跳等信息组成，如下图。由于路由规则具有最长 128 位的前缀长度，在查找算法软件实现中，采用单比特 Trie 存储转发表，查找速度慢；采用较长的多比特 Trie（如每次进行 8 比特查找）能提升查找速度，但存储空间大。介绍高效 IPv6 路由查找算法设计思路，同时具有较低存储空间与较高查找速度。

5 TCP 通过 Additive Increase Multiplicative Decrease (AIMD)机制保障竞争流间的公平性。请简述AIMD 机制的处理流程，并结合下图，从图中起始点（黑色箭头）出发，画出 AIMD 实现流间公平性的过程。

6 TCP 传输协议中，发送的字节数与吞吐（throughput）以及 RTT 的关系如下图所示。假设，路径的传播时延为 RTTprop，瓶颈链路带宽为 BW，瓶颈链路处的队列长度为 Q。请问 1）D1, Slope1, Slope2, S1, S2 分别为多少？2）请根据该图，解释基于丢包的拥塞控制算法（如 Cubic）、基于模型的拥塞控制算法（如 BBR）以及基于时延的拥塞控制算法（如数据中心网络中的 SWIFT）的基本思想。

参考答案：

7 主动测量和被动测量各代表什么含义，其优缺点是什么？请简述某一种测量带宽（瓶颈带宽和可用带宽都可以）的方法。

8 请简述区块链使用了哪些技术手段，使得其上的数据是不可伪造、不可抵赖、不可删除、不可篡改的。

9 TCP/IP 体系结构对移动性支持不好，请回答两个问题：（1）TCP/IP 体系结构由于什么原因，导致对移动性支持不好？（2）LISP（The Locator/ID Separation Protocol）是如何解决这个问题的？

10 数据中心网络传输在多个发送端给一个接收端同时发送数据时，可能会造成 TCP Incast 问题，请回答两个问题：（1）DCTCP 是如何借助 ECN 机制解决这个问题的？（2）SWIFT 等基于时延的协议又是如何解决这个问题的？

11 考虑数据并行的分布式深度学习训练系统，其可扩展系数（scaling factor）𝑆𝐹 = 𝑇₁ / （𝑁∗𝑇_𝑁），其中 N为训练节点数，𝑇₁, 𝑇_𝑁分别表示使用 1 个训练节点和使用 N 个训练节点时，单个节点的训练所需时间。SF 越接近 1 扩展性越好，但是实际系统中 SF 往往远小于 1，请阐述原因，以及提升SF 的可能方案。

2023年(回忆版)

1 互联网体系结构可自下而上分为物理层、网络层、传输层和应用层，请简述各层主要功能与代表性协议，以及该分层模型的优缺点。

2 ABCD四个站的码片，发送的码片，计算ABCD各发送的消息

3 RIP、OSPF、BGP三个协议的不同

4 最长匹配，选择路由

5 TCP流量控制和拥塞控制的目的以及实现原理

6 链路带宽、可用带宽是什么，测量这两种带宽的方法

7 综合服务模型，区分服务模型有啥区别，RSVP工作原理，为啥逐跳路由

8 对称加密算法和非对称加密算法是什么，优劣势，加密和签名过程

9 根域名服务器的作用，递归查询和迭代查询的原理

10 区块链的哈希链是啥，作用以及举例区块链的作用

11 总线和无线使用的协议分别是啥，为啥不一样

2024年（回忆版和乱序版）

1 请简述“在浏览器中输入网址到获取网页内容”这段时间内发生的操作。

参考答案：
1.网址域名 DNS 查询，解析对应的 IP 地址。
2. 生成对应的 HTTP 请求，封装 TCP/IP 数据包。
3. 查询 IP 地址对应的网关和下一跳的 IP 地址。
4. 查询下一跳的 IP 地址对应的 Mac 地址。
5. 把数据转发给网关。
6. 经过路由寻址抵达网页服务器。
7. 网页服务器解析，返回所需具体页面。

注： 此次题目给了所捕获到的数据包，所以答案基本已经给出，算是送分题。

2 RIP 和 OSPF 是两个典型的域内路由协议，都是基于域内路由节点之间相互交换信息，通过相应的路由算法计算生成路由表。现假设在一个自治域使用 RIP 协议或者 OSPF 协议，请回答下列问题：

a) 路由节点之间相互交换什么信息？请以一个路由器为例，针对RIP和OSPF分别进行回答。
b) 对于一条节点间交换的信息来说，该信息被交换的范围（即该信息会被传送给哪些节点）
是什么？请针对 RIP 和 OSPF 分别进行回答。

3 TCP 通过 Additive Increase Multiplicative Decrease (AIMD)机制保障竞争流间的公平性。请简述AIMD 机制的处理流程，并结合下图，从图中起始点（黑色箭头）出发，画出 AIMD 实现流间公平性的过程。

4 给定以下图，1）给定一个IP地址，给出相应的查询过程；2）增加前缀，并画出增加前缀后的树；3）删除前缀，并画出删除前缀后的树

参考答案：
（1）

（2）

（3）

5 TCP 传输协议中，发送的字节数与吞吐（throughput）以及 RTT 的关系如下图所示。假设，路径的传播时延为 RTTprop，瓶颈链路带宽为 BW，瓶颈链路处的队列长度为 Q。请问 1）D1, Slope1, Slope2, S1, S2 分别为多少？2）请根据该图，解释基于丢包的拥塞控制算法（如 Cubic）、基于模型的拥塞控制算法（如 BBR）以及基于时延的拥塞控制算法（如数据中心网络中的 SWIFT）的基本思想。

参考答案：

6 在RSA 算法中，两个质数 p=3，q=5，求解对明文10加解密的全过程？

参考答案：
RSA 算法流程如下：

a. 选择两个大素数（质数）p和q
b. 计算 n=p×q 和 m=(p-1)×(q-1)
c. 选择一个与m互质的数，令其为d
d. 找到一个 e 使满足 e x d = 1 (mod m)
e. 公开密钥为(e，n)，私有密钥为(d，n)
f. 设明文为M，则加密过程：C = M^e mod n ，解密过程为：M‘ = C^d mod n

本题中，p = 3，q = 5，M = 10，因此，n = 15，m = 8，令 d = 3，则e = 3，满足 e ✖️ d = 1 （mod m）。随后，对明文M进行加密得到 C = M^e mod n = 10^3 mod 15 = 10，对C进行解密可以得到 C^d mod n = 10^3 mod 15 = 10 = M 。
注： 此题还给出了RSA算法的流程，只需按照流程计算即可，难度降低。

7 简述区块链上数据不可伪造、不可抵赖、难以删除和难以篡改的技术原理，请举出现实生活中用区块链技术解决实际问题的一个实例，并说明区块链解决了其中的什么问题

参考答案：
从宏观上，采用分布式平等部署系统、分布式共享相同数据；无中心化控制，全网参与的节点协作完成交易验证和存储。从微观上，数据储存在块中，这些块在逻辑上串联起来构成链条；应用数字签名与完整性校验保证块数据的真实性、时序性、完整性。在技术层面具有不可伪造、不可抵赖、不可篡改、不可撤销等属性，在应用层面具有分布式的公开透明、交易可跟踪等特征。在将区块链应用到支付清算结算系统中，可以帮助解决证券系统T+1到账资金滞后、跨行对账、转账带来的高昂业务成本等等。

8 多路径传输问题

9 下图是 OpenFlow 局域网络拓扑，S1 的流表包含一条转发规则，Controller 持有全局网络的拓扑信息，请描述 Packet 1 从 C1 到 H2 的转发过程，包含流表查询、流表安装流程以及具体的流表转发规则。

参考答案：
1）首先，数据从 C1 唯一的端口发出，发到 S1；
2）S1 查询流表，匹配不到对应条目，因此该数据包缓存下，并查询 Controller。
3）Controller 下发规则至 S1，规则内容为：“DstIP=H2，Outport=2”.
4）S1 按照相应规则，将数据包从 PORT2 转出，至 S2
5）S2 收到数据包后，找不到对应规则，因此也将该数据包缓存下，并查询 Controller
6）Controller 下发规则至 S2，规则内容为 DstIP=H2,output=2
7）S2 查询到相应规则后，将数据包从 port2 转出，至 H2。

还有两道题记不清了。不过整体上就多路径传输问题那道题有点难，其他题均为往年题。