Assignment

1. In class, we showed that to implement reliable communication in the presence of lost or damaged packets, we need sequence numbers on both data packets and acknowledgment packets. Briefly explain why/how numbering only data packets can lead to protocol failure.

2. In class we said that to implement a reliable protocol, we need only 1-bit sequence numbers on both data packets and acknowledgments. Explain why a single bit is sufficient.

3. Briefly explain why NAKs are most useful when the variance of the round-trip time (RTT) is high.

4. In class we discussed sliding window protocols in which packets are numbered with 2ⁿ sequence numbers that range from 0 to 2ⁿ - 1 for some n. We identified limitations on the use of sequence numbers for both Go-Back-N and Selective Repeat, as discussed below.

(a) For Go-Back-N, the receive window size is 1, and the maximum send window size is 2ⁿ - 1 sequence numbers (one less than the total number of sequence numbers). For example, with n = 2, the maximum send window size is 2² - 1 = 3. Draw a timing diagram for n = 2 illustrating a situation where a send window size of 2ⁿ = 4 can cause the protocol to fail.

(b) For Selective Repeat, the receive window size is 2^n-1, and the maximum send window size is also 2^n-1 (half the total number of sequence numbers). Draw a timing diagram for n = 2 illustrating a situation where a send window size of 2ⁿ - 1 = 3 can cause the protocol to fail.

5. The Moon is approximately 4 x 10⁸ meters from Earth. The speed of light is 3 x 10⁸ meters/sec. NASA has developed a laser-based communication channel that operates at 18 Mbps (18,000,000 bits per second) for communication with future Moon outposts. Assume that packets are 1500 bytes (12000 bits) long.

(a) How many packets fit on the "cable" from Earth to the Moon?

(b) If a stop-and-wait protocol is used and there are no errors, what is the utilization of the channel? Ignore packet headers and the transmission time for acknowledgments (do not ignore the propagation delay for packets and acknowledgments).

(c) If a sliding window protocol is used, how large must the window be to enable the sender to transmit packets continuously?

(d) Assume selective repeat is used with 12-bit sequence numbers, the packet loss rate P₁ is 0.2 and the ack loss rate P₂ is 0.1. What is the maximum utilization of the channel, ignoring packet headers and the transmission time for acknowledgments (do not ignore the propagation time for packets and acknowledgments).

6. UDP is advertised as a best-effort, unreliable protocol. Yet, the UDP header contains a checksum computed on the header and the data. Briefly explain why UDP computes checksums on data if it does not guarantee reliability.

7. Describe the UDP pseudoheader. What is it used for and how does it violate network protocol layering?

8. In some of the sliding window protocols we discussed in class, sequence numbers refer to packets. However, the sequence numbers and acknowledgment numbers contained in TCP headers refer to bytes, not packets. Discuss the advantages of numbering bytes instead of packets.

9. TCP is a bidirectional protocol that assigns sequence numbers to bytes flowing in each direction. The initial sequence numbers for a given connection are selected (randomly, or using a hash function) from the range of possible sequence numbers (0 to 2³² - 1). What is the rationale for not starting at 0?

10. Draw a figure showing how three-way handshake works in TCP. Be sure to identify the values of key flags (i.e., SYN and ACK) and sequence number relationships.

11. A sliding window protocol for the transport layer needs to adapt to dynamic conditions in the network and at the endpoints (hosts). Describe how TCP adapts to changing conditions in order to set the timeout value. Be specific.

12. The sliding window protocol used in TCP implements implements both congestion control (to mitigate congestion, which is a network issue) and flow control (to avoid overwhelming the receiver, an end-to-end issue). Briefly describe the mechanisms TCP uses to accomplish this task, using a single send window.

13. Describe Fast Retransmit in TCP and why it is used.

14. State Little's Law and define each of the variables. To which types of queueing systems does Little's Law apply?

15. Consider a communication link between two nodes, A and B. The bit rate of the channel is 1 Gbps (1,000,000,000 bits per second). Packets arriving at the channel are placed in a queue until they are transmitted. (Assume the number of buffers in the queue is infinite.) Assume packet lengths (including headers) are exponentially distributed, with a mean packet length of 5,000 bits. Assume packet arrivals are Poisson at a mean rate of 50,000 packets per second.

(a) The service rate p, is the rate at which "customers" can be processed by the server. What is the value of it in this case (how many packets per second can be transmitted on this channel)? Show your work.

(b) On average, how long (T) does a packet spend in the system (both in the queue and being transmitted). Show your work.

(c) On average, what is the number of packets in the system? Show your work.

(d) What is the probability that exactly two packets will arrive within a period of 2 mi­croseconds (2 x 10^-6 seconds)? Show your work.

(e) Assume that router A has just finished transmitting a packet and that the queue currently holds 5 packets. What is the probability that exactly three of these packets will be transmitted completely in a period of 2 microseconds? Show your work.

(f) Imagine that we partition the channel into 100 subchannels, each with a bit rate of 10,000,000 bits per second and each with its own queue. Assume that arriving packets are randomly placed in one of the 10 outgoing queues. Compute the average time (T') that a packet spends in this system (both in the queue and being transmitted). Show your work.