東京大学 情報理工学系研究科 創造情報学専攻 2024年8月実施 筆記試験 第2問

标签：

• Tokyo-University
• Stop-and-Wait-Automatic-Repeat-Request
• Sliding-Window-Protocol
• Bandwidth-Delay-Product
• Protocol-Throughput-and-Utilization
• Server-Concurrency-and-Request-Queueing

Author

itsuitsuki

Description

We transmit data via packet switching between sender S and receiver R connected as shown in Figure 1. Assume that one-way propagation delay $d_{prop}$ is 250 ms and bandwidth $B$ is 200 kbps. Ignore packet losses and assume that the packets are not fragmented during transmission. The communication is full-duplex. The prefix “k” represents $10^3$.

Answer the following questions.

(1) Assume that the packet size is 1500 bytes. Calculate the time from the moment S starts sending a packet to the moment R completely receives the packet. Note that the time required to push all the bits of a packet into the communication channel is referred to as transmission delay, and the time asked in this question is the sum of the transmission delay and the one-way propagation delay.

(2) Assume that the packet size is 1500 bytes. Consider a communication method where each time R completes receiving a packet, R sends an acknowledgment packet to S, then S sends the next packet immediately after S receives the acknowledgement packet. The acknowledgment packet is small enough that we can ignore its transmission delay. Calculate the effective speed in this setting. Provide your answer in kbps and round it to one decimal place. Note that effective speed refers to the value obtained by dividing the transmitted data size by the time from the moment S starts sending the first packet to the moment S receives the acknowledgment packet for the last packet.

(3) We define line utilization as the ratio of effective speed to bandwidth. Let's consider improving line utilization by increasing the packet size. Answer the minimum packet size $P$ that gives line utilization of 20% or more. Additionally, express line utilization as an equation in terms of the packet size $P$. Note that the unit of $P$ is bytes.

We adopt the following communication method to improve communication efficiency with a fixed packet size. Sender S continuously sends $\omega$ packets, and then checks whether the acknowledgment packet for the first packet has arrived at S at the time $\omega$ packets have been sent. If the packet has arrived, then S sends the next packet. Otherwise, S waits for the arrival of the acknowledgement packet, then S sends the next packet immediately after the arrival. Subsequent packets will be processed in the same way.

(4) Calculate the minimum value of $\omega$ such that the communication method described above fully utilizes the bandwidth. Assume that the packet size is 1500 bytes. Also, depict the communication in this case in a sequence diagram. Note that “fully utilize the bandwidth” refers to the situation that S is always pushing packets into the communication channel until all the packets have been sent.

(5) Express the minimum value of $\omega$ as an equation in terms of one-way propagation delay $d_{prop}$ (in ms), bandwidth $B$ (in kbps), and packet size $P$ (in bytes) such that the communication method described above fully utilizes the bandwidth. Note that the smallest integer greater than or equal to a real number $x$ is denoted by $\lceil x \rceil$.

Consider a network that transmits data via packet switching as shown in Figure 2. The server stores a file of size $4 \times 10^5$ bytes, and each client acquires the file via the network. First, a client sends a packet that requests the file to the server, and then the server sends the file to the client after receiving the request. Note that the communication between the server and a client is full-duplex. Also, the server and each client are connected by a dedicated communication channel, and therefore its bandwidth is not affected by other communication channels. The packet that requests a file is small enough that we can ignore its transmission delay.

Answer the following questions. Note that time $t$ is the elapsed time measured from the moment Client 1 sends a file request packet.

(6) Assume that the server can process only one file request packet at a time. When the server receives a file request packet from a client, the server sends the file to the client. Assume that it takes 5 ms from the moment when the server starts processing a file request packet to the moment it starts sending the file, and that the server completes processing the file request packet when it completes sending the file. When a new file request packet arrives from another client while the server is processing a file request packet, the new file request packet is stored in a queue. The server starts processing the file request packet at the head of the queue immediately after it completes processing the current file request packet. Each client sends a file request packet to the server at times shown in Table 1. The configuration of the network each client is connected to is shown in Table 1. Answer the time when Client 1, 2, and 3 complete receiving the file, respectively.

Table 1 File request time and network configuration of clients

	File request time	Propagation delay between a client and the server (one-way)	Bandwidth
Client 1	$t=0$ ms	50 ms	500 kbps
Client 2	$t=30$ ms	110 ms	250 kbps
Client 3	$t=50$ ms	60 ms	800 kbps

From now on, we improve the server and make it possible for the server to process file request packets from multiple clients concurrently by multi-threading. The server starts a thread each time it receives a file request, and each thread is dedicated to file transmission to a client after the start. Assume that it takes 15 ms from the moment when the server starts processing a file request packet to the moment it starts sending the file after starting a thread. A thread terminates immediately after it completes sending the file.

(7) Assume that a sufficient number of threads can run without interfering with each other on the server. The configuration of the network each client is connected to is shown in Table 1. Answer the time when Client 1, 2, and 3 complete receiving the file, respectively.

(8) Assume that there are $20$ clients connected to the server with an identical configuration as shown in Table $2$. Client $1$, Client $2$, ..., and Client $20$ request the file in this order with $10 \text{ ms}$ intermission.

Table 2 Network configuration of clients

Propagation delay between a client and the server (one-way)	Bandwidth
$50 \text{ ms}$	$500 \text{ kbps}$

Assume that the maximum number of file transmission threads that can run concurrently on the server is $12$. When a file request packet arrives but already $12$ threads are running and the server cannot start a new thread, the file request packet is stored in a queue. When one of the threads terminates, the server immediately starts processing the file request packet at the head of the queue. Answer the time when the server starts processing the file request packet from Client $20$, and the time when Client $20$ completes receiving the file.

题目描述

在图 1 所示发送方 S 与接收方 R 间以分组交换传输数据。单向传播时延 (d_{\mathrm{prop}}=250,\mathrm{ms})，带宽 (B=200,\mathrm{kbps})。忽略丢包，分组不分片，通信为全双工；前缀 k 表示 (10^3)。

1. 分组大小 1500 字节。求 S 开始发送到 R 完整收完的时间，即把全部比特推入信道的发送时延与单向传播时延之和。
2. 分组仍为 1500 字节。R 每收完一包即向 S 返回 ACK，S 收到 ACK 后立即发下一包；ACK 足够小，可忽略其发送时延。求有效速率（kbps，四舍五入到 1 位小数）。有效速率定义为传输数据量除以“首包开始发送到 S 收到末包 ACK”的时间。
3. 线路利用率定义为有效速率/带宽。用字节数 (P) 表示分组大小，写出利用率公式，并求使利用率至少 20% 的最小 (P)。

为在固定包长下提高效率，S 连续发送 (\omega) 个包；发完第 (\omega) 个时检查首包 ACK 是否到达。若已到达便继续发下一包，否则等 ACK 到达后立即继续；后续均同样处理。

4. 包长 1500 字节时，求使带宽完全利用的最小 (\omega)，并画对应时序图。“完全利用”指所有包发完前，S 始终在向信道推送分组。
5. 用单向传播时延 (d_{\mathrm{prop}})（ms）、带宽 (B)（kbps）、包长 (P)（字节）表示完全利用带宽所需的最小 (\omega)，可用上取整 (\lceil x\rceil)。

图 2 网络中，服务器保存大小 (4\times10^5) 字节的文件，各客户端先发请求包，服务器收到请求后发送文件。通信全双工，每个客户端与服务器间是独占信道，带宽不受其他信道影响；请求包很小，忽略发送时延。以下 (t) 从客户端 1 发请求时起算。

6. 服务器一次只能处理一个文件请求。收到请求后，开始处理到开始发文件需 5 ms；发完文件才算处理完成。忙时到达的新请求进入队列，当前请求完成后立即处理队首。客户端参数为：

   客户端	发请求时刻	单向传播时延	带宽
   1	(t=0,\mathrm{ms})	(50,\mathrm{ms})	(500,\mathrm{kbps})
   2	(t=30,\mathrm{ms})	(110,\mathrm{ms})	(250,\mathrm{kbps})
   3	(t=50,\mathrm{ms})	(60,\mathrm{ms})	(800,\mathrm{kbps})

   分别求三个客户端完整收完文件的时刻。

随后把服务器改为多线程：每收到一个请求就启动专用于该客户端文件发送的线程；开始处理（含启动线程）到开始发文件需 15 ms，发完后线程立即终止。

7. 假设线程数充足且互不干扰，仍用表 1 参数，分别求三个客户端收完文件的时刻。
8. 有 20 个客户端，网络配置均为单向传播 (50,\mathrm{ms})、带宽 (500,\mathrm{kbps})。客户端 1～20 依次每隔 10 ms 发出请求。服务器最多同时运行 12 个文件传输线程；满 12 个时新请求排队，任一线程结束后立即处理队首。求服务器开始处理客户端 20 请求的时刻，以及客户端 20 完整收完文件的时刻。

考点

• 停等协议与线路利用率：综合包发送时延和往返传播时延计算有效速率，并反求满足目标利用率的包长。
• 滑动窗口与带宽时延积：求填满往返时延期间信道所需的最小未确认包数并绘制时序。
• 服务器串行请求排队：按请求到达服务器的实际时刻、处理与发送完成时刻模拟单服务队列。
• 并发线程与容量受限排队：区分独占客户端链路与服务器线程上限，计算并行完成及第 20 个请求等待时间。

Kai

(1)

The transmission delay is

$$d_{trans}={1500\text{ bytes}\over 200\text{ kbps}}={1500\text{ bytes}/25\text{ kBps}}=60\text{ ms}.$$

The time required is

$$t = d_{trans} + d_{prop} = 60\text{ ms} + 250\text{ ms} = 310\text{ ms}.$$

(2)

The time required is one transmission delays for the data packet, and two one-way propagation delays (one for the data packet from the sender and one for the ACK from he receiver).

$$t = 2*d_{prop} + {1500\text{ bytes}\over 200\text{ kbps}}=2*250 + 60 = 560\text{ ms}.$$

The effective speed is

$$\text{Effective Speed}={1500\text{ bytes}\over 560\text{ ms}}={150\over 7}\text{ kbps}\approx 21.5 \text{ kbps}.$$

(3)

Since

$$\begin{aligned} d_{trans} &= {P \text{ bytes}\over 200 \text{ kbps}}={P\over 25}\text{ ms}, \\ \text{Effective Speed}&={P\text{ bytes}\over {P\over 25}+2*250\text{ ms}} \\ &={8P\text{ bits}\over {P\over 25}+500\text{ ms}} \\ &={200P\over P+12500}\text{ kbps}, \end{aligned}$$

when the line utilization is not less than 20% i.e. 0.2, we have

$${P\over B}\ge 0.2\implies {200P/(P+12500)\over 200}\ge 0.2\implies {P\over P+12500}\ge 0.2,$$

where $P\ge 3125\text{ bytes}$.

(4)

The time S takes to send $\omega$ packets to R (not until R receives) is the transmission delay, which is

$$t_{S\to R}=d_{trans}={\omega \times 1500 \times 8 \text{ bits}\over 200\text{ kbps}}=60\omega\text{ ms}.$$

Let the time S starts to send the first packet to R be $t=0$. Then the time S completes sending is $t=60\omega\text{ ms}$.

Also, R sends the acknowledgment packet for the first package from S at $t=310\text{ ms}$, and the ACK arrives at S at $t=560\text{ ms}$ as calculated in (1) and (2).

Since the ACK arrival should be earlier than S completes sending $\omega$ packets,

$$60\omega \ge 560\text{ ms}\implies \omega\ge {28\over 3}.$$

Since $\omega$ is an integer, $\omega_{\min}=10$.

(5)

Generally, the time of S to complete sending is ${\omega\times P\times 8\over B}$ for $P$ bytes, $\omega$ packets and bandwidth $B$ kbps. The time of the ACK for the first packet to arrive is ${P\times 8\over B}+2d_{prop}$. Hence

$$\begin{aligned} {8\omega P\over B}&\ge {8P\over B}+2d_{prop} \\ {8(\omega-1)P\over B}&\ge 2d_{prop} \\ \omega-1&\ge {2Bd_{prop}\over 8P} \\ \omega_{\min}&=\lceil {Bd_{prop}\over 4P} + 1\rceil. \end{aligned}$$

(6)

The transmission delay for client 1,2,3 are respectively

$$d_{trans}^1={4\times 10^5\text{ bytes}\over 500\text{ kbps}}=6400\text{ ms},\\ d_{trans}^2={4\times 10^5\text{ bytes}\over 250\text{ kbps}}=12800\text{ ms},\\ d_{trans}^3={4\times 10^5\text{ bytes}\over 800\text{ kbps}}=4000\text{ ms}.$$

• Client 1 requests at $t=0\text{ ms}$, the request packet arrives at $t=0+50=50\text{ ms}$;
• Client 2 requests at $t=30\text{ ms}$, the request packet arrives at $t=30 + 110 =140\text{ ms}$;
• Client 3 requests at $t=50\text{ ms}$, the request packet arrives at $t=50 + 60 =110\text{ ms}$.

So the queue is (first) 1,3,2 (last) at the server.

Server after a transmission delay and a preprocessing delay (5ms) completes pushing the packet into the communication channel (link). Hence the

• Server completes sending to client 1 at $t=50+5+6400=6455\text{ ms}$;
• Server completes sending to client 3 at $t=6455+5+4000=10460\text{ ms}$;
• Server completes sending to client 2 at $t=10460+5+12800=23265\text{ ms}$.

After a propagation delay, the client receives the file.

• Client 1 receives at $t=6455+50=6505\text{ ms}$;
• Client 2 receives at $t=23265+110=23375\text{ ms}$;
• Client 3 receives at $t=10460+60=10520\text{ ms}$.

(7)

Notice: the preprocessing delay changes to 15ms.

• Client 1 receives at $t=0+50+15+6400+50=6505\text{ ms}$;
• Client 2 receives at $t=30+110+15+12800+110=13065\text{ ms}$;
• Client 3 receives at $t=50+60+15+4000+60=4185\text{ ms}$.

(8)

The transmission delay is uniformly

$$d_{trans}={4\times 10^5\text{ bytes}\over 500\text{ kbps}}=6400\text{ ms}.$$

• Client 1 to client 12: no queueing;
  • Client 1: $t=0+50=50\text{ ms}$ arrival; server sends at $t=0+50+15+6400=6465\text{ ms}$ (next queueing request starts being preprocessed);
  • ...
  • Client 8: $t=70+50=120\text{ ms}$ arrival; server sends at $t=120+15+6400=6535\text{ ms}$;
  • ...
  • Client 12: server completes sending at $t=110+50+15+6400=6575\text{ ms}$.
• Client 13 to client 20: waiting the processing Client 1,2,..,8 repsectively to end;
  • Client 13: $t=120+50=170\text{ ms}$ arrival; leaves the queue at $t=6465\text{ ms}$ when the request from 1 ends, server sends at $t=6465+15+6400=12880\text{ ms}$;
  • ...
  • Client 20: $t=190+50=240\text{ ms}$ arrival; leaves the queue at $t=6535\text{ ms}$ when the request from 8 ends, server sends at $t=6535+15+6400=12950\text{ ms}$;

Hence, client 20 completes receiving after a one-way propagation delay at $t=12950+50=13000\text{ ms}$.