Malaviya National Institute of Technology Jaipur

Department of Computer Science and Engineering

Transport Layer Assignment –II
Question 1.
Ben decides to use the sliding window transport protocol and implemented on the network
below. The receiver sends end-to-end ACKs to the sender. The switch in the middle simply
forwards packets in best-effort fashion.

A. The sender's window size is 10 packets. Selecting the best answer from the choices
below, at what approximate rate (in packets per second) will the protocol deliver a
multi-gigabyte file from the sender to the receiver? Assume that there is no other
traffic in the network and packets can only be lost because the queues overflow.
a. Between 900 and 1000.
b. Between 450 and 500.
c. Between 225 and 250.
d. Depends on the timeout value used.
B. You would like to double the throughput of this sliding window transport protocol
running on the network shown on the previous page. To do so, you can apply one of
the following techniques alone:
a. Double the window size.
b. Halve the propagation time of the links.
c. Double the speed of the link between the Switch and Receiver.
For each of the following sender window sizes, list which of the above techniques, if
any, can approximately double the throughput. If no technique does the job, answer
"None". There might be more than one answer for each window size, in which case
you should list them all. Note that each technique works in isolation. Explain your
answers.
 Malaviya National Institute of Technology Jaipur
Department of Computer Science and Engineering
Transport Layer Assignment –II
1. W = 10.
2. W = 50.

3. W = 30.
Question 2. A sender uses the stop and wait ARQ protocol for reliable transmission of
segments. Segments are of size 1000 bytes and the transmission rate at the sender is 80 Kbps.
Size of an acknowledgement is 100 bytes and the transmission rate at the receiver is 8 Kbps.
The one way propagation delay is 100 msec. Assuming no segment is lost, the sender
throughput is __________ bytes/sec.
Question 3. Consider two hosts X and Y connected by a single direct link of rate
106 bits/sec. The distance between the two hosts is 10,000 km and the propagation speed
along the link is 2 x 108 m/sec. Host X sends a file of 50,000 bytes as one large message to
host Y continuously. Let the transmission and propagation delays be p milliseconds and q
milliseconds respectively.
Then the value of p and q are-
1. p = 50 and q = 100
2. p = 50 and q = 400
3. p = 100 and q = 50
4. p = 400 and q = 50
Question 4. In the reliable transport protocols we studied, the receiver sends an
acknowledgment (ACK) saying “I got k” whenever it receives a packet with sequence
number k. Ben Bitdiddle invents a different method using cumulative ACKs: whenever the
receiver gets a packet, whether in order or not, it sends an ACK saying “I got every packet up
to and including `”, where ` is the highest, in-order packet received so far. The definition of
the window is the same as before: a window size of W means that the maximum number of
unacknowledged packets is W. Every time the sender gets an ACK, it may transmit one or
more packets, within the constraint of the window size. It also implements a timeout
mechanism to retransmit packets that it believes are lost using the algorithm from. Network
assumptions. The protocol runs over a best-effort network, but no packet or ACK is
duplicated at the network or link layers. The sender sends a stream of new packets according
to the sliding window protocol, and in response gets the following cumulative ACKs from the
receiver: 1 2 3 4 4 4 4 4 4 4
 Malaviya National Institute of Technology Jaipur
Department of Computer Science and Engineering
Transport Layer Assignment –II
a) Now, suppose that the sender times out and retransmits the first unacknowledged
packet. When the receiver gets that retransmitted packet, what can you say about the
ACK, a, that it sends? (Circle the BEST answer)
(a) a = 5. (b) a ≥ 5. (c) 5 ≤ a ≤ 11. (d) a = 11. (e) a ≤ 11.
b) Is it possible for the given sequence of cumulative ACKs to have arrived at the sender
even when no packets were lost en route to the receiver when they were sent?
Question 5. Give one example of a situation where the cumulative ACK protocol gets higher
throughput than the sliding window protocol.
Question 6. A little bit into the data transfer, the sender observes the following sequence of
cumulative ACKs sent from the receiver: 21 22 23 25 28 The window size is 8 packets. What
packet(s) should the sender transmit upon receiving each of the above ACKs, if it wants to
maximize the number of unacknowledged packets?
Question 7. Ben Bitdiddle implements a reliable data transport protocol intended to provide
"exactly once" semantics. Each packet has an 8-bit incrementing sequence number, starting at
0. As the connection progresses, the sender "wraps around" the sequence number once it
reaches 255, going back to 0 and incrementing it for successive packets. Each packet size is S
= 1000 bytes long (including all packet headers).
Suppose the link capacity between sender and receiver is C = 1 Mbyte per second and the
round-trip time is R = 100 milliseconds.
a) What is the highest throughput achievable if Ben's implementation is stop-and-wait?
b) To improve performance, Ben implements a sliding window protocol. Assuming no
packet losses, what should Ben set the window size to in order to saturate the link
capacity?
c) Ben runs his protocol on increasingly higher-speed bottleneck links. At a certain link
speed, he finds that his implementation stops working properly. Can you explain what
might be happening? What threshold link speed causes this protocol to stop
functioning properly?
Question 8. A sender S and receiver R are connected over a network that has k links that can
each lose packets. Link i has a packet loss rate of p_i in one direction (on the path from S to
R) and q_i in the other (on the path from R to S). Assume that each packet on a link is
received or lost independent of other packets, and that each packet's loss probability is the
 Malaviya National Institute of Technology Jaipur
Department of Computer Science and Engineering
Transport Layer Assignment –II
same as any other's (i.e., the random process causing packet losses is indepedent and
identically distributed).
A. Suppose that the probability that a data packet does not reach R when sent by S is p
and the probability that an ACK packet sent by R does not reach S is q. Write
expressions for p and q in terms of the p_i's and q_i's.
B. If all p's are equal to some value α << 1 (much smaller than 1), then what is p (defined
above) approximately equal to?
C. Suppose S and R use a stop-and-wait protocol to communicate. What is the expected
number of transmissions of a packet before S can send the next packet in sequence?
Write your answer in terms of p and q (both defined above).
Question 9. You are hired to design a reliable byte-stream protocol that uses a sliding
window (like TCP). This protocol will run over a 1-Gbps network. The RTT of the network
is 100 ms, and the maximum segment lifetime is 30 seconds.
a. How many bits would you include in the AdvertisedWindow and SequenceNum fields
of your protocol header?
b. How would you determine the numbers given above, and which values might be less
certain?
Question 10. Suppose you are designing a sliding window protocol for a 1-Mbps point-to-
point link to the moon, which has a one-way latency of 1.25 seconds. Assuming that each
segment carries 1 KB of data, what is the minimum number of bits you need for the sequence
number?
Question 11. Draw a timeline diagram for the sliding window algorithm with SWS = RWS =
3 Segment’s, for the following two situations. Use a timeout interval of about 2 × RTT.
(a) Segment 4 is lost.
(b) Segment 4 to 6 are lost.
Question 12. Suppose that we attempt to run the sliding window algorithm with SWS =
RWS = 3 and with MaxSeqNum = 5. The Nth packet DATA[N] thus actually contains N
mod 5 in its sequence number field. Give an example in which the algorithm becomes
confused; that is, a scenario in which the receiver expects DATA[5] and accepts
DATA[0]—which has the same transmitted sequence number—in its stead. No packets may
arrive out of order. Note that this implies MaxSeqNum ≥ 6 is necessary as well as sufficient.
 Malaviya National Institute of Technology Jaipur
Department of Computer Science and Engineering
Transport Layer Assignment –II
Question 13. Consider the sliding window algorithm with SWS = RWS = 3, with no out-of-
order arrivals and with infinite-precision sequence numbers.
a. Show that if DATA[6] is in the receive window, then DATA[0] (or in general any older
data) cannot arrive at the receiver (and hence that MaxSeqNum = 6 would have
sufficed).
b. Show that if ACK[6] may be sent (or, more literally, that DATA[5] is in the sending
window), then ACK[2] (or earlier) cannot be received. Note that part (b) implies that the
scenario of the previous problem cannot be reversed to involve a failure to distinguish
ACK[0] and ACK[5].
Question 14. Suppose that we run the sliding window algorithm with SWS = 5 and RWS =
3, and no out-of-order arrivals.
a. Find the smallest value for MaxSeqNum. You may assume that it suffices to find the
smallest MaxSeqNum such that if DATA[MaxSeqNum] is in the receive window, then
DATA[0] can no longer arrive.
b. Give an example showing that MaxSeqNum − 1 is not sufficient.
c. State a general rule for the minimum MaxSeqNum in terms of SWS and RWS.

A R B

Question 15. Suppose A is connected to B via an intermediate router R, as shown in the

above Figure. The A–R and R–B links each accept and transmit only one packet per second
in each direction (so two packets take 2 seconds), and the two directions transmit
independently. Assume A sends to B using the sliding window protocol with SWS = 4.
(a) For Time = 0,1,2,3,4,5, state what packets arrive at and leave each node, or label them on
a timeline.
(b) What happens if the links have a propagation delay of 1.0 second, but accept immediately
as many packets as are offered (i.e., latency = 1 second but bandwidth is infinite)?
Question 16. Suppose A is connected to B via an intermediate router R, as in the previous
problem. The A–R link is instantaneous, but the R–B link transmits only one packet each
second, one at a time (so two packets take 2 seconds). Assume A sends to B using the sliding
 Malaviya National Institute of Technology Jaipur
Department of Computer Science and Engineering
Transport Layer Assignment –II
window protocol with SWS = 4. For Time = 0,1,2,3,4, state what packets arrive at and are
sent from A and B. How large does the queue at R grow?
Question 17. Consider the situation in the previous exercise, except this time assume that the
router has a queue size of 1; that is, it can hold one packet in addition to the one it is sending
(in each direction). Let A’s timeout be 5 seconds, and let SWS again be 4. Show what
happens at each second from Time = 0 until all four packets from the first window-full are
successfully delivered.
Question 18. Design a reliable, sliding window, byte-stream protocol similar to TCP. It will
be used for communication with a geosynchronous satellite network, for which the
bandwidth is 1 Gbps and the RTT is 275 ms. Assume the maximum segment lifetime is 30
seconds. How many bits wide should you make the AdvertisedWindow and SequenceNum
fields?
Question 20. A system uses the Go – back –N protocol with a window size of 8. Each packet
carries 1024 bits of data, the distance between the sender and receiver is 1000 km and the
propagation speed is 2 x 108 m/s. By ignoring transmission, waiting, processing delays and
also assuming that no segment is lost, then find the time taken to send 1Mb file.
Question 21. Station A needs to send a message consisting of 9 packets to station B using a
sliding window (window size 3) and go back n error control strategy. All packets are ready
and immediately available for transmission. If every 5th packet that A transmits gets lost (but
no ACKs from B ever get lost), then what is the number of packets that A will transmit for
sending the message to B?.
Question 22. Consider the GBN protocol with a sender window size of 4 and a sequence
number range of 1,024. 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:
a. What are the possible sets of sequence numbers inside the sender’s window at time t?
Justify your answer.
b. What are all possible values of the ACK field in all possible messages currently
propagating back to the sender at time t? Justify your answer.
Question 23. Suppose you are designing a sliding window protocol for a 10-Mbps point-to-
point link to a stationary satellite revolving around Planet X at 6×104 km altitude. Assuming
 Malaviya National Institute of Technology Jaipur
Department of Computer Science and Engineering
Transport Layer Assignment –II
that each segment carries 10 KB of data, what is the minimum number of bits you need for
the sequence number in this case when the RWS and SWS are equal? Assume the speed of
light is 3×108 m/s.
Question 24. In SR W s = 5 and we are sending 10 packets where every 5th packet is lost
find number of retransmissions?
Question 25. If there is K bits sequence no. define require sender window size and receiver
window size for S&W, GBN and SR?
Question 26. Show the 4B/5B encoding, and the resulting NRZI signal, for the following bit
sequence:
1101 1110 1010 1101 1011 1110 1110 1111
Question 27. Suppose we want to transmit the message 1011 0010 0100 1011 and protect it
from errors using the CRC8 polynomial x 8 + x 2 + x 1 + 1.
(a) Use polynomial long division to determine the message that should be transmitted.
(b) Suppose the leftmost bit of the message is inverted due to noise on the transmission link.
What is the result of the receiver’s CRC calculation? How does the receiver know that an
error has occurred?
Question 28. Draw a timeline diagram for the sliding window algorithm with SWS=RWS=4
segments for two given scenarios using the following assumptions:
a. The receiver sends a duplicate acknowledgement if it does not receive the expected
segment. For example it sends dupack[2] when it expects to see segment [2] but
receives segment[3] instead.
b. The receiver sends a cumulative acknowledgement after it receives all the outstanding
segments. For example it sends ACK[5] when it receives the lost segments [2] after it
already received segments [3], segments [4] and segments [5].
c. The timeout interval is about 2RTT.
a) Segment 2 is lost. Retransmission takes place upon timeout (as usual).
b) Segment 2 is lost. Retransmission takes place either upon receipt of the first
DUPACK or upon timeout. Does this scheme reduce the transaction time?
Question 29. Answer true or false to the following questions and briefly justify your answer:
a) With the SR protocol, it is possible for the sender to receive an ACK for a packet that
falls outside of its current window.
 Malaviya National Institute of Technology Jaipur
Department of Computer Science and Engineering
Transport Layer Assignment –II
b) With GBN, it is possible for the sender to receive an ACK for a packet that falls outside
of its current window.
c) The alternating-bit protocol is the same as the SR protocol with a sender and receiver
window size of 1.
d) The alternating-bit protocol is the same as the GBN protocol with a sender and receiver
window size of 1.