本文整理计算机网络概述中的配套习题,涉及分层概念、交换方式、时延和吞吐量。
本文的参考笔记位于计算机网络概述 。题目标题中的年份标记表示对应年份的统考真题。
一、分层与 OSI 参考模型
1. 概念辨析
此类题目的关键是先确定对象或功能的作用范围,再定位层次。实体、协议、接口与服务描述的对象不同;流量控制等功能则可能出现在多个层次,不能只凭功能名称判断。
实现各层功能的规则 上下层之间进行交互时所要的信息 各层中实现该层功能的软件或硬件 同一节点中相邻两层相互作用的地方 答案 解析 在 OSI 参考模型中,实体指各层中实现该层功能的软件或硬件,参见分层结构与实体 。
实体(entity)是层中的活动元素,可以由软件或硬件实现,例如程序、模块、进程或设备。不同节点中处于同一层并承担相应功能的实体互为对等实体。
选项 A 描述协议;选项 D 描述层间接口或服务访问点(Service Access Point,SAP);选项 B 只描述相邻层交互时传递的信息。
2013 统考真题 在 OSI 参考模型中,功能需由应用层的相邻层实现的是( )
对话管理 数据格式转换 路由选择 可靠数据传输 答案 解析 OSI 模型中应用层是第 7 层,其相邻下层是第 6 层表示层。表示层处理通信双方数据表示方式的差异,典型功能包括字符集或编码转换、数据格式转换、数据压缩以及加密和解密。
对话管理属于会话层;路由选择属于网络层;端到端的可靠数据传输通常由传输层提供,在单段链路范围内也可能由数据链路层的可靠传输机制提供,但都不是表示层的功能。
此题需要先由“应用层的相邻层”定位到表示层,再由功能反推层次,参见 OSI 七层模型 。
2022 统考真题 在 ISO/OSI 参考模型中,实现两个相邻节点间流量控制功能的是( )
物理层 数据链路层 网络层 传输层 答案 解析 流量控制可能出现在多个层次,题干中的限定词是“相邻节点”,它把控制范围限定在一段链路上。数据链路层以帧为数据单位,负责相邻节点之间的数据传输,并可在这一范围内实施差错控制与流量控制。
传输层的流量控制面向端系统中的通信端点,作用范围是端到端;网络层关注分组在网络中的转发,并可能参与网络范围的流量调节与拥塞控制;物理层负责在信道上传输比特,不负责帧级流量控制。
判断此类题目的关键是作用范围:相邻节点对应数据链路层,端到端通信对应传输层,参见 OSI 七层模型 。
二、交换方式与时延
1. 端到端时延计算
设分组长度为 L L L 、链路传输速率为 R R R ,单个分组在该链路上的传输时延为
d t r a n s = L R . d_{\mathrm{trans}}=\frac{L}{R}. d trans = R L .
若 P P P 个等长分组连续通过 N N N 段等速链路,采用存储转发,并且忽略传播、处理、排队、丢包与重传,则分组流水线的端到端完成时间为
T message = ( P + N − 1 ) d t r a n s . T_{\text{message}}=(P+N-1)d_{\mathrm{trans}}. T message = ( P + N − 1 ) d trans .
存在额外处理资源竞争、链路速率不同或传播时延时,需要把这些条件单独计入,不能直接套用该式。
在采用存储转发方式的分组交换网中,主机 A 向 B 连续发送两个长度为 1000 B 1000\ \mathrm{B} 1000 B 的分组。路由器处理单个分组的时延为 10 m s 10\ \mathrm{ms} 10 ms ,同时最多只能处理一个分组;处理期间到达的新分组进入缓存区,处理器与输出链路可并行工作。忽略传播时延,两段链路的传输速率均为 1 M b / s 1\ \mathrm{Mb/s} 1 Mb/s 。求从 A 开始发送到 B 接收完两个分组的最短时间
题目拓扑:路由器处理单个分组需要 10 ms 答案 36 m s 36\ \mathrm{ms} 36 ms
解析 先计算每段链路的传输时延,再按“完整接收—等待处理器—处理—再次发送”的顺序排列两个分组。每个分组在每段链路上的传输时延为
d t r a n s = 1000 × 8 b i t 1 × 10 6 b i t / s = 8 m s . d_{\mathrm{trans}}=\frac{1000\times 8\ \mathrm{bit}}{1\times10^6\ \mathrm{bit/s}}=8\ \mathrm{ms}. d trans = 1 × 1 0 6 bit/s 1000 × 8 bit = 8 ms . 解题时序:第二个分组在路由器等待 2 ms,最终于 36 ms 传输完毕 分组 2 在 16 m s 16\ \mathrm{ms} 16 ms 时已经到达路由器,但分组 1 要到 18 m s 18\ \mathrm{ms} 18 ms 才处理完,因此产生 2 m s 2\ \mathrm{ms} 2 ms 的排队时延。处理器与输出链路是两个资源,所以分组 2 的处理可以和分组 1 在第二段链路上的发送重叠。主机 B 在 36 m s 36\ \mathrm{ms} 36 ms 时接收完两个分组。
处理与排队可能改变流水线节拍。以第一个分组开始发送的时刻为计时起点,即 s 1 = 0 s_1=0 s 1 = 0 ;设第 p p p 个分组从源端开始发送的时刻为 s p s_p s p ,则其到达目的端的时刻为
A p = s p + ∑ i = 1 N ( L R i + d p r o p , i ) + ∑ j = 1 N − 1 ( d p r o c , p , j + d q u e u e , p , j ) . A_p=s_p+\sum_{i=1}^{N}\left(\frac{L}{R_i}+d_{\mathrm{prop},i}\right)+\sum_{j=1}^{N-1}\left(d_{\mathrm{proc},p,j}+d_{\mathrm{queue},p,j}\right). A p = s p + i = 1 ∑ N ( R i L + d prop , i ) + j = 1 ∑ N − 1 ( d proc , p , j + d queue , p , j ) .
整个报文的完成时间为 T message = max 1 ≤ p ≤ P A p T_{\text{message}}=\max_{1\le p\le P}A_p T message = max 1 ≤ p ≤ P A p 。各分组的处理与排队时延应按实际时间线确定,不能把单个分组的时延直接乘以分组数。
主机 H1 和 H2 之间可采用电路交换、报文交换或分组交换。电路交换的建连时间为 2 s 2\ \mathrm{s} 2 s ;报文交换和分组交换经过一台路由器连接的两段链路,分组长度为 5 k b 5\ \mathrm{kb} 5 kb 。三种方式的传输速率均为 2.5 k b / s 2.5\ \mathrm{kb/s} 2.5 kb/s 。忽略传播时延、分组开销和其他线路延迟,推导三种交换方式的完成时间,并分别计算数据量为 5 k b 5\ \mathrm{kb} 5 kb 、10 k b 10\ \mathrm{kb} 10 kb 、15 k b 15\ \mathrm{kb} 15 kb 和 500 k b 500\ \mathrm{kb} 500 kb 时的结果
电路交换需要先建立连接,另外两种方式需要经过一台路由器存储转发 答案 M = 5 k b M=5\ \mathrm{kb} M = 5 kb 时三者相同;其余三种数据量下,分组交换与电路交换用时相同,均短于报文交换。
解析 电路交换只支付一次建连时间;报文交换必须在两段链路上各发送一遍完整报文;分组交换则可在两段链路之间形成流水线。设数据量为 M M M ,链路速率 R = 2.5 k b / s R=2.5\ \mathrm{kb/s} R = 2.5 kb/s ,分组长度 L = 5 k b L=5\ \mathrm{kb} L = 5 kb ,建连时间 t s e t u p = 2 s t_{\mathrm{setup}}=2\ \mathrm{s} t setup = 2 s ,且题目中的数据量均能被 L L L 整除。三种方式的时间分别为
d c i r c u i t = t s e t u p + M R , d m e s s a g e = 2 M R , d p a c k e t = ( M L + 1 ) L R = M R + L R . \begin{aligned}d_{\mathrm{circuit}}&=t_{\mathrm{setup}}+\frac{M}{R},\\d_{\mathrm{message}}&=2\frac{M}{R},\\d_{\mathrm{packet}}&=\left(\frac{M}{L}+1\right)\frac{L}{R}=\frac{M}{R}+\frac{L}{R}.\end{aligned} d circuit d message d packet = t setup + R M , = 2 R M , = ( L M + 1 ) R L = R M + R L . 代入四组数据:
数据量 M M M 电路交换 报文交换 分组交换 5 k b 5\ \mathrm{kb} 5 kb 4 s 4\ \mathrm{s} 4 s 4 s 4\ \mathrm{s} 4 s 4 s 4\ \mathrm{s} 4 s 10 k b 10\ \mathrm{kb} 10 kb 6 s 6\ \mathrm{s} 6 s 8 s 8\ \mathrm{s} 8 s 6 s 6\ \mathrm{s} 6 s 15 k b 15\ \mathrm{kb} 15 kb 8 s 8\ \mathrm{s} 8 s 12 s 12\ \mathrm{s} 12 s 8 s 8\ \mathrm{s} 8 s 500 k b 500\ \mathrm{kb} 500 kb 202 s 202\ \mathrm{s} 202 s 400 s 400\ \mathrm{s} 400 s 202 s 202\ \mathrm{s} 202 s
对包含 k k k 段等速链路的路径,若报文被拆成 P P P 个长度为 L L L 的分组,忽略处理、排队和重传,则
T c i r c u i t = t s e t u p + M R + ∑ i = 1 k d p r o p , i , T m e s s a g e = k M R + ∑ i = 1 k d p r o p , i , T p a c k e t = ( P + k − 1 ) L R + ∑ i = 1 k d p r o p , i . \begin{aligned}T_{\mathrm{circuit}}&=t_{\mathrm{setup}}+\frac{M}{R}+\sum_{i=1}^{k}d_{\mathrm{prop},i},\\T_{\mathrm{message}}&=k\frac{M}{R}+\sum_{i=1}^{k}d_{\mathrm{prop},i},\\T_{\mathrm{packet}}&=(P+k-1)\frac{L}{R}+\sum_{i=1}^{k}d_{\mathrm{prop},i}.\end{aligned} T circuit T message T packet = t setup + R M + i = 1 ∑ k d prop , i , = k R M + i = 1 ∑ k d prop , i , = ( P + k − 1 ) R L + i = 1 ∑ k d prop , i .
三式分别体现建连时间、完整报文的逐跳传输和分组流水线。题干中的小写 b \mathrm{b} b 表示比特;数据量和速率统一使用 k b \mathrm{kb} kb 与 k b / s \mathrm{kb/s} kb/s 时,可以直接相除。
2010 统考真题 在采用存储转发方式的分组交换网络中,所有链路的传输速率均为 100 M b / s 100\ \mathrm{Mb/s} 100 Mb/s 。分组长度为 1000 B 1000\ \mathrm{B} 1000 B ,其中首部为 20 B 20\ \mathrm{B} 20 B 。主机 H1 向 H2 发送一个大小为 980000 B 980000\ \mathrm{B} 980000 B 的文件,不考虑分组拆装时间和传播时延。求从 H1 开始发送到 H2 接收完文件的最短时间
最短路径经过两台交换机,共包含三段链路 答案 80.16 m s 80.16\ \mathrm{ms} 80.16 ms
解析 分组大小包含首部,需要先由有效载荷计算分组数,再选择链路数最少的路径计算存储转发流水线的总时间。每个分组携带的文件数据为
1000 − 20 = 980 B , 1000-20=980\ \mathrm{B}, 1000 − 20 = 980 B , 因此分组数为
P = 980000 980 = 1000. P=\frac{980000}{980}=1000. P = 980 980000 = 1000. 最短路径经过两台交换机,共有 N = 3 N=3 N = 3 段链路。每个完整分组在一段链路上的传输时延为
d t r a n s = 1000 × 8 b i t 100 × 10 6 b i t / s = 0.08 m s . d_{\mathrm{trans}}=\frac{1000\times8\ \mathrm{bit}}{100\times10^6\ \mathrm{bit/s}}=0.08\ \mathrm{ms}. d trans = 100 × 1 0 6 bit/s 1000 × 8 bit = 0.08 ms . 第一个分组需要 3 3 3 个发送时隙才能到达 H2,此后每隔一个发送时隙到达一个分组。总时间为
T message = ( P + N − 1 ) d t r a n s = ( 1000 + 3 − 1 ) × 0.08 m s = 80.16 m s . T_{\text{message}}=(P+N-1)d_{\mathrm{trans}}=(1000+3-1)\times0.08\ \mathrm{ms}=80.16\ \mathrm{ms}. T message = ( P + N − 1 ) d trans = ( 1000 + 3 − 1 ) × 0.08 ms = 80.16 ms .
设文件有效数据量为 M M M 、完整分组长度为 L L L 、首部长度为 H H H ,则分组数为
P = ⌈ M L − H ⌉ . P=\left\lceil\frac{M}{L-H}\right\rceil. P = ⌈ L − H M ⌉ .
当所有分组均按长度 L L L 传输、路径包含 N N N 段等速链路,并忽略传播、处理与排队时延时,
T message = ( P + N − 1 ) L R . T_{\text{message}}=(P+N-1)\frac{L}{R}. T message = ( P + N − 1 ) R L .
首部影响有效载荷和分组数;包含首部的完整分组长度才用于计算传输时延。若前 P − 1 P-1 P − 1 个分组的长度均为 L L L ,最后一个分组不补齐且实际长度为 L l a s t < L L_{\mathrm{last}}<L L last < L ,则在上述条件下
T message = ( P + N − 2 ) L + L l a s t R . T_{\text{message}}=\frac{(P+N-2)L+L_{\mathrm{last}}}{R}. T message = R ( P + N − 2 ) L + L last .
2023 统考真题 在分组交换网络中,主机 H1 和 H2 通过路由器互连,两段链路的带宽均为 100 M b / s 100\ \mathrm{Mb/s} 100 Mb/s ,时延带宽积(单向传播时延 × \times × 带宽)均为 1000 b 1000\ \mathrm{b} 1000 b 。若 H1 向 H2 发送一个大小为 1 M B 1\ \mathrm{MB} 1 MB 的文件,分组长度为 1000 B 1000\ \mathrm{B} 1000 B ,求从 H1 开始发送到 H2 接收完文件的最短时间(注:1 M = 10 6 1\ \mathrm{M}=10^6 1 M = 1 0 6 )
两段链路的传输速率和单向传播时延均相同 答案 80.10 m s 80.10\ \mathrm{ms} 80.10 ms
解析 时延带宽积给出链路中正在传播的比特数,由它反求单向传播时延。传输时延和传播时延来源不同,需要分别计算。文件被划分为
P = 10 6 B 1000 B = 1000 P=\frac{10^6\ \mathrm{B}}{1000\ \mathrm{B}}=1000 P = 1000 B 1 0 6 B = 1000 个分组。单个分组在每段链路上的传输时延为
d t r a n s = 1000 × 8 b i t 100 × 10 6 b i t / s = 0.08 m s . d_{\mathrm{trans}}=\frac{1000\times8\ \mathrm{bit}}{100\times10^6\ \mathrm{bit/s}}=0.08\ \mathrm{ms}. d trans = 100 × 1 0 6 bit/s 1000 × 8 bit = 0.08 ms . 每段链路的单向传播时延为
d p r o p = 1000 b i t 100 × 10 6 b i t / s = 0.01 m s . d_{\mathrm{prop}}=\frac{1000\ \mathrm{bit}}{100\times10^6\ \mathrm{bit/s}}=0.01\ \mathrm{ms}. d prop = 100 × 1 0 6 bit/s 1000 bit = 0.01 ms . 第一个分组经过两次发送和两次传播后到达 H2,其余 999 999 999 个分组以 0.08 m s 0.08\ \mathrm{ms} 0.08 ms 为间隔流出流水线,因此
T message = 2 ( d t r a n s + d p r o p ) + ( P − 1 ) d t r a n s = 2 ( 0.08 + 0.01 ) + 999 × 0.08 = 80.10 m s . \begin{aligned}T_{\text{message}}&=2(d_{\mathrm{trans}}+d_{\mathrm{prop}})+(P-1)d_{\mathrm{trans}}\\&=2(0.08+0.01)+999\times0.08\\&=80.10\ \mathrm{ms}.\end{aligned} T message = 2 ( d trans + d prop ) + ( P − 1 ) d trans = 2 ( 0.08 + 0.01 ) + 999 × 0.08 = 80.10 ms .
设一段链路的时延带宽积为 B D P \mathrm{BDP} BDP ,则其单向传播时延为
d p r o p = B D P R . d_{\mathrm{prop}}=\frac{\mathrm{BDP}}{R}. d prop = R BDP .
对 P P P 个等长分组和 N N N 段等速链路,若忽略处理与排队时延,则
T message = ( P + N − 1 ) L R + ∑ i = 1 N d p r o p , i . T_{\text{message}}=(P+N-1)\frac{L}{R}+\sum_{i=1}^{N}d_{\mathrm{prop},i}. T message = ( P + N − 1 ) R L + i = 1 ∑ N d prop , i .
时延带宽积中的“时延”只指单向传播时延,不包含把分组推入链路的传输时延。
三、端到端吞吐量
1. 路径瓶颈
忽略其他流量和协议开销时,一条路径的稳态吞吐量受路径上最慢链路限制。存在多条候选路径且一次仅使用一条路径时,先求每条路径的瓶颈带宽,再选择其中最大者;所有路径共享的链路还会形成共同的上界。
2024 统考真题 某分组交换网络及每段链路的带宽如下图所示,求 H1 到 H2 的最大吞吐量,并指出可选路径与公共链路中的瓶颈
三条内部路径共享两端各 10 Mb/s 的链路 答案 10 M b / s 10\ \mathrm{Mb/s} 10 Mb/s
解析 忽略其他流量与协议开销时,单条端到端路径的吞吐量等于该路径上各段链路带宽的最小值。分别计算三条候选路径的瓶颈:
路径 依次经过的链路带宽 路径瓶颈 上方路径 10 , 1000 , 1000 , 10 M b / s 10,1000,1000,10\ \mathrm{Mb/s} 10 , 1000 , 1000 , 10 Mb/s 10 M b / s 10\ \mathrm{Mb/s} 10 Mb/s 中间路径 10 , 1 , 10 M b / s 10,1,10\ \mathrm{Mb/s} 10 , 1 , 10 Mb/s 1 M b / s 1\ \mathrm{Mb/s} 1 Mb/s 下方路径 10 , 100 , 100 , 10 M b / s 10,100,100,10\ \mathrm{Mb/s} 10 , 100 , 100 , 10 Mb/s 10 M b / s 10\ \mathrm{Mb/s} 10 Mb/s
上方路径和下方路径都能达到约 10 M b / s 10\ \mathrm{Mb/s} 10 Mb/s ,因此 H1 到 H2 的最大吞吐量约为 10 M b / s 10\ \mathrm{Mb/s} 10 Mb/s 。
对一条路径 π \pi π ,忽略其他流量和协议开销时,其稳态吞吐量为
Γ π = min i ∈ π R i . \Gamma_\pi=\min_{i\in\pi}R_i. Γ π = i ∈ π min R i .
在候选路径集合 P \mathcal P P 中,单路径最大吞吐量为 Γ max = max π ∈ P Γ π \Gamma_{\max}=\max_{\pi\in\mathcal P}\Gamma_\pi Γ m a x = max π ∈ P Γ π 。若允许多条路径并发,聚合吞吐量通常还要结合流量分配与共享链路容量计算,不能直接套用该式。本题两端各有一段所有路径共享的 10 M b / s 10\ \mathrm{Mb/s} 10 Mb/s 链路,因此聚合吞吐量也不可能超过 10 M b / s 10\ \mathrm{Mb/s} 10 Mb/s ;选择上方或下方路径即可达到该上界。