COMP 361 Tutorial 7

COMP 361 -- Tutorial Week 7

More Problems of Chapter 3

Last revised: 03/15/2005 18:03 +0800

Problem 1:

Consider a channel that can lose packets but has a maximum delay that is known. Modify protocol rdt2.1 to include sender timeout and retransmit. Informally argue why your protocol can communicate correctly over this channel.

Problem 2:

Consider the Go-Back-N protocol with a sender window size of 3 and a sequence number range of 1024. Suppose that at time t, the next in-order packet that the receiver is expecting has a sequence number of k. Assume that the medium does not reorder messages. Answer the following questions:

What are the possible sets of sequence number inside the sender's window at time t ? Justify your answer.
What are all possible values of the ACK field in the message currently propagating back to sender at time t ? Justify your answer.

Problem 3:

Suppose we have two network entities, A and B. B has a supply of data messages that will be sent to A according to the following conventions. When A gets a request from the layer above to get the next data (D) message from B, A must send a request (R) message to B on the A-to-B channel; Only when B receives an R message can it send a data (D) message back to A on the B-to-A channel. A should deliver exactly one copy of each D message to the above layer. R messages can be lost (but not corrupted) in the A-to-B channel; D messages, once sent are always delivered correctly. The delay along both channels is unknown and variable.

Design (give a FSM) description of a protocol that incorporates the appropriate mechanisms to compensate for the loss-prone A-to-B channel and implements message passing to the above layer at entity A , as discussed above . Use only those mechanisms that are absolutely necessary.

Problem 4:

Consider the selective-repeat protocols. Suppose the sequence number space is of size k. What is the largest allowable sender window that will avoid problems such as that in Figure 3.27 on page 226 of the book (page 66 of the chapter 3 notes) from occurring for each of these protocols?

Problem 5:

In this problem you will be drawing examples of the application of the GBN and Selective Repeat protocols. We start with the setup:

machine A is sender; machine B is receiver.
Window size N=4
Sequence # has 4 bits
Packets time out after 5 time units. That is, if the clock is started at t=2 then timeout occurs at t=7.
packet 0 is sent from A at time t=0.
Data/Ack packets can only be sent from A at integer times, i.e., t=0,1,2,3
It takes a successful packet exactly one unit of time to travel from A to B or from B to A
At each time step A will always first check if there is a timeout.
- If there is a timeout, it will resend all appropriate packets
- If there is no timeout and the protocol allows it to send a new packet then it will receive a new packet from above and send it
- If there is no timeout and the protocol does not allow it to send snew packet then it will do nothing until the next time step.
If B receives more than one packet simultaneously at any time step you should assume that the packets arrive in sorted order and operate accordingly. F or example, if B receives packets 7,5,6 at t=7 it operates as if it received them in the order 5,6,7.
If A receives more than one ACK simultaneously at any time step you should assume that the ACKS arrive in sorted order and operate accordingly.

In the two problems that follow you should draw the operations of the protocols. That is, for A, at each time t, you should note which data packets were sent at time t and which ACKS were received at time t. for B, at each t, you should note which data packets were received at time t and which packets were ACKd at time t. Draw all arrows corresponding to successful packets sent (from A to B or (B to A) Draw half arrows corresponding to lost packets. Use the diagram below as a template

(I) Assume that all packets sent by A are received successfully but the (ACK) packets sent from B to A at every 3rd time step get lost. That is, packets sent by B at times t=0,3,6,9... all get lost but packets sent at time t=1,2,4,5,7,8... are all delivered successfully.

Run all actions performed by A and B under the GBN protocol until A receives a successful ACK6 (i.e., A is sure that packets 0,1,2,3,4,5,6 have all been successfully received).

(II) The same as Problem I but now run Selective Repeat.

Problem 6:

Consider transferring an enormous file of L bytes from host A to host B. Assume an MSS of 1460 bytes.

What is the maximum value of L such that TCP sequence numbers are not exhausted? Recall that the TCP sequence number field has four bytes.
For the L you obtain in (a), find how long it takes to transmit the file. Assume that a total of 66 bytes of transport, network, and data-link header are added to each segment before the resulting packet is sent out over a 10 Mbps link. Ignore flow control and congestion control, so A can pump out the segments back-to-back and continuously.

Problem 7:

In Figure 3.31, we see that TCP waits until it has received three duplicate ACK before performing a fast retransmit. Why do you think the TCP designers chose not to perform a fast retransmit after the first duplicate ACK for a segment is received?

Problem 8:

Consider the TCP procedure for estimating RTT. Suppose that x= 0.1. Let SampleRTT₁ be the most recent sample RTT, let SampleRTT₂ be the next most recent sample RTT, etc.

For a given TCP connection, suppose four acknowledgments have been returned with corresponding sample RTTs SampleRTT₄, SampleRTT₃, SampleRTT₂ , and SampleRTT₁. Express EstimatedRTT in terms of the four sample RTTs.
Generalize your formula for n sample round-trip times.
For the formula in part (b) let n approach infinity. Comment on why this averaging procedure is called an exponential moving average.

Problem 9:

Assume a network in which packets (and not bytes) have sequence numbers. Assume that the network that has a maximum packet size of 128 bytes, a maximum packet lifetime of 32s, and a 8 bit packet sequence number. Assuming that a sliding-window flow control algorithm is used and and that, therefore, two packets with the same sequence # can not coexist. What is the maximum data rate per connection?