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

Author

itsuitsuki

Description

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

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

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

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

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

Description (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 . 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 and the transmission bandwidths of three transmission links are and (where ), 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 , where , 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 . 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 , and an ACK packet shall not be received by Host 1 after .

(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 is large. Propose two methods, so as to improve the throughput, providing their maximum throughput and their required conditions.