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

标签：

• Tokyo-University
• Stop-and-Wait-Automatic-Repeat-Request
• Reliable-Data-Transfer
• Sliding-Window-Protocol
• Bandwidth-Delay-Product
• Protocol-Throughput-and-Utilization

Author

itsuitsuki

Description

日本語

図 1 に示すようなシステムで、ホスト 1 からホスト 2 へ、パケット転送を行う．転送されるパケットはすべて同じ大きさの $M [\text{Bytes}]$で、ホスト 1 からホスト 2 への通信経路上には、高速な 2 つのスイッチ(SW1 と SW2)が存在しており、他のアプリケーションおよび他のホストが生成したパケットは転送されていないものとする．ホスト 1 とホスト 2 間のパケットの片方向遅延が $D [\text{sec}]$、それぞれの伝送路の帯域幅($B_1, B_2$ および $B_3$ (ただし、$B_2 < B_3 < B_1$))とするとき、以下の問いに答えなさい．

(1) ホスト間で誤りのないデータ転送を提供するために、データパケットの到達確認を行いながらホスト間でのデータ転送を行う．最も単純な方法として、ホスト 1 が送信したパケット(データパケット)がホスト 2 に到達した時、ホスト 2 は、受信確認のパケット(ACK パケット)を生成し、ホスト 1 に返送する方法を考える．なお, ACK パケットの大きさは $m [\text{Bytes}]$で、$\frac{m}{B_2} < \frac{M}{B_2} \ll D$ でありホストおよびスイッチでのパケットの通信路への送信および受信に必要な時間は無視可能とする．さらに，ホスト 1 は ACK パケットを受信した時には遅延時間ゼロで次のデータパケットを送信, ホスト 2 はホスト 1 からのデータパケットを受信した時には遅延時間ゼロで ACK パケットを送信するものとする．この時の，ホスト 1 からホスト 2 へのデータ転送速度の最大値を示しなさい．

(2) 設問(1)のシステムにおいて、データパケットおよび ACK パケットが伝送中にランダムに確率 $\rho$ で紛失される時、データパケットがホスト 1 からホスト 2 に誤りなく転送されるために必要な時間の平均値を示しなさい．なお, ホスト 1 は, データパケットの送信後 $3D [\text{sec}]$待っても, ACK パケットが到着しない場合にはデータパケットの再送を行うものとし, $3D [\text{sec}]$以降には, ACK パケットはホスト 1 には到着しないものとする．

(3) 通信を開始するにあたって, ホスト 1 とホスト 2 との間で情報の同期手順を行いたい．ホスト 1 とホスト 2 との間で同期される情報は, 1 パケットで転送可能であると仮定する．パケットが途中の伝送路中で紛失されることが想定される場合の手順を, ホスト 1 およびホスト 2 で実行されるべき状態遷移図(あるいは状態遷移表)とともに記述しなさい．

(4) 設問(1)のパケット転送方式では, $D$ が大きい時には, データ転送速度が大きくならない．データ転送速度を向上させる方法を, 2 つ提案し, 各方式での最大データ転送速度と, 最大データ転送速度を実現するために必要な条件を示しなさい．

题目描述

在图 1 的系统中，从主机 1 向主机 2 传送大小均为 (M) 字节的数据包。路径中有两台高速交换机 SW1、SW2，且没有其他应用或主机产生的分组流量。主机间分组的单向时延为 (D) 秒，三段链路带宽为 (B_1,B_2,B_3)，满足 (B_2<B_3<B_1)。

1. 为实现无差错数据传输，采用停等确认：主机 1 发出一个数据包，主机 2 收到后立即生成大小为 (m) 字节的 ACK 并返回；主机 1 收到 ACK 后立即发送下一个数据包。已知 [ \frac m{B_2}<\frac M{B_2}\ll D, ] 忽略主机和交换机收发分组所需的处理时间，且上述两种响应延迟均为 0。求主机 1 到主机 2 的最大数据传输速率。
2. 在第 1 问系统中，每个数据包和 ACK 在传输途中均以概率 (\rho) 随机丢失。主机 1 发包后若等待 (3D) 秒仍未收到 ACK，就重传数据包；并假定超过 (3D) 后 ACK 不会再到达。求一个数据包从主机 1 无误传至主机 2 所需时间的期望。
3. 通信开始时，主机 1 与主机 2 要同步一项可由单个分组承载的信息。考虑分组可能在链路中丢失，设计同步协议，并分别画出或列出两台主机应执行的状态转移图（或状态转移表）。
4. 第 1 问的停等方式在 (D) 很大时吞吐率受限。提出两种提高数据传输速率的方法；对每种方法给出最大传输速率，以及达到该速率所需的条件。

考点

• 停等 ARQ 与可靠传输：根据数据—确认往返周期、超时重传及数据包和 ACK 的丢失概率计算吞吐率与期望完成时间。
• 可靠同步协议：用序号、确认、超时和重传设计可应对消息或确认丢失的主机状态机。
• 滑动窗口与带宽时延积：通过流水发送多个未确认分组填满长时延链路，推导窗口大小达到瓶颈带宽所需条件。
• 协议吞吐率与链路利用率：结合三段带宽的瓶颈 (B_2)、包长和往返时延比较不同传输方式的最大速率。

English

Packets are transmitted from Host 1 to Host 2, as shown in the figure 1 below. The data packets, sent from Host 1 to Host 2, have identical length, which is $M [\text{Bytes}]$. There are two packet switches (SW1 and SW2) along the transmission path between Host 1 and Host 2. There are not any packets generated by other hosts, nor any packets generated by other applications on Host 1. When a one way packet propagation delay between Host 1 and Host 2 is $D[\text{sec}]$ and the transmission bandwidths of three transmission links are $B_1, B_2$ and $B_3$ (where $B_2 < B_3 < B_1$), answer the following questions:

(1) In order to achieve error-free data transmission from Host 1 to Host 2, Host 1 transfers data packets to Host 2, while confirming if every data packet is correctly received by Host 2. The following simple algorithm is applied. When a data packet from Host 1 arrives at Host 2, Host 2 sends the acknowledgement packet, called as ACK packet, to Host 1. Here, the size of an ACK packet is $m [\text{Bytes}]$, where $\frac{m}{B_2} < \frac{M}{B_2} \ll D$, so that we can ignore the delay caused by packet transmission/reception at Host 1, Host 2, SW1 and SW2, and Host 1 sends the next data packet right after the reception of an ACK packet from Host 2 with zero latency. Host 2 sends an ACK packet right after the reception of data packet from Host 1 with zero latency. With this system, answer the maximum data transmission throughput from Host 1 to Host 2.

(2) In the system described in (1), the data packets are dropped randomly with a probability of $\rho$. Compute the average latency when the data packet is correctly received by Host 2 after the data packet is sent from Host 1. Here, Host 1 resends the data packet, when Host 1 cannot receive an ACK packet from Host 2, within $3D[\text{sec}]$, and an ACK packet shall not be received by Host 1 after $3D[\text{sec}]$.

(3) Before starting data transmission, Host 1 and Host 2 have to perform a data synchronization procedure. Assuming that the synchronized data between the hosts can be transferred with a single packet. Describe the procedure in Host 1 and Host 2 with the state transition diagram or the state transition matrix, when packets can be dropped during packet transmission between them.

(4) With the packet transmission algorithm described in (1), we cannot obtain large throughput, when $D$ is large. Propose two methods, so as to improve the throughput, providing their maximum throughput and their required conditions.