6.02 Lab #10: Reliable Packet Delivery

Goal

Useful links

lab10_net.py -- Network and related classes
lab10_router.py -- Router class
lab10_random_graph.py -- a random topology generator
lab10_stopwait.py -- template file for Task #1
lab10_slidingwindow.py -- template file for Task #2
lab10.tar.gz -- compressed tarball of all these files

Instructions

Complete the tasks below, submit your task files online before the deadline. Since there isn't sufficient time for our normal checkoff interview process, please enter your answers to the interview questions into a separate file and submit the file using the same process as used to submit your task files. We'll review your submitted code and your answers and enter the appropriate score on-line.

As always, help is available in 32-083 (see the Lab Hours web page).

For this lab, you will need wxPython (2.8.x), which has already been installed on the athena machines. To install it on your computer, visit http://www.wxpython.org/

Introduction and preliminaries

NetSim is a network simulator that simulates a set of switches connected by links. NetSim executes a set of steps every time slot; time increments by 1 each slot. During each time slot a link can deliver one packet from one end of the link to the other end of the link. The nodes in the simulator will be derived from the LSRouter class that you implemented in Lab 9, and therefore will be capable of routing packets between themselves. In this lab, we will develop the core logic of the ReliableSenderNode and ReliableReceiverNode classes, both derived from the LSRouter class, to implement a reliable data transport protocol between a sender and receiver.

Every simulation will consist of a sender and receiver connected by a network of LS routers. The sender will send packets to the receiver using a reliable data transport protocol. You will write the code for the main components of two reliable data transport protocols: a stop-and-wait protocol and a sliding window protocol (with fixed window size).

You can run the python programs for this lab using ipython or python on your computer or on athena (note: on athena, use ipython602 and python602). The lab will not work in IDLE.

To understand the different parameters one can set in NetSim, go to a shell and enter:

# python lab10_stopwait.py -h
(Or, in ipython, run lab10_stopwait.py -h).

# python lab10_slidingwindow.py -h
(Or, in ipython, run lab10_slidingwindow.py -h).

The "-l" option causes data and ACK packets to be dropped on any link with the specified probability. The "-r" option generates a random topology with the specified number of nodes (the default number of nodes is 12 and the default simulation time is 2000 time slots). For lab10_slidingwindow.py, the "-w" option sets the window size to be used in the protocol. The maximum number of unacknowledged packets sent by the sender must not exceed this window size setting.

This lab has two main tasks that implement two different reliable transport protocols. Each task has a few sub-tasks. You will test these implementations on a few different topologies that will be generated when you run the corresponding task files.

Debugging and Testing Procedures

During any point in the simulation, you can click on the sender, node S, to see an estimate of the round trip time (RTT) to the receiver, node R (and back), and the current timeout being used. Clicking on R will show the current throughput at the receiver measured at the number of useful (i.e., in-sequence and non-spurious) packets passed up to the application per simulation timestep, as well as the total number of spurious packets received. We will judge the quality of your transport protocol by the throughput and RTT measurements displayed at the end of the simulation.

If your protocol works correctly, two things should happen:

1. The receiver and sender should not "hang" -- i.e., the protocol should not deadlock with both sides waiting for something to happen.
2. The receiver should not print an error message and terminate the program. That will happen if your protocol delivers an out-of-sequence packet to the receiving application (in the app_receive call, as explained below).

To help debug your code, you can print debug statements whenever a significant event (e.g., data/ack reception) happens at any node. The template code already prints out a few statements; feel free to add more to help you understand what's going on. One can also see the total number of pending packets at various nodes on the bottom panel of the simulator; if this number is persistently in the hundreds, you know something is wrong or that you are transmitting packets faster than the network can clear.

You can use the "-l" option to test the correctness of your protocol at different link loss rates. The loss rate is a parameter between 0 (no loss) and 1 (everything on a link is lost). Note that both packets and ACKs will get lost. In these simulations, routing messages don't get lost.

Task #1: Stop-and-wait protocol (5 points)

The stop-and-wait protocol works as follows:

• Each data packet includes a unique sequence number, derived from a counter that is incremented for each new data packet (see section 22.2.1 of the lecture notes). Each data packet also includes a timestamp (p.start) giving the time at which the data packet was transmitted by the sender. A data packet is saved by the sender until it receives an acknowledgement from the receiver.

• Each time slot the sender's reliable_send method is called. This method decides what packet to send, if any. It has two choices:

  • If there is a saved data packet, the sender should check to see if self.timeout slots have passed since the transmission by comparing the current time with the timestamp of the saved packet. If self.timeout slots have passed, the sender should retransmit the saved data packet, using the old sequence number but with a new timestamp updated to indicate the time of the retransmission. If self.timeout slots have not passed, the sender should do nothing and continue to wait for an acknowledgement.

  • If there is no saved packet, the sender should increment the sequence number counter and send a new data packet, remembering to also save the data packet pending the receipt of an acknowledgement.

• When a data packet arrives at the receiver, the receiver's reliable_receive method is called. It should send an acknowledgement (ACK) packet to the sender (i.e., to the address specified in the source field of the received packet). The ACK packet should include the sequence number and timestamp of the received data packet. The receiver should then deliver the data packet to the application by calling the app_receive method. Note that that if an ACK is lost, the receiver may receive the same packet more than once and must take steps to ensure only one copy of the packet is delivered to the application (see section 22.2.3 of the lecture notes). Note that app_receive maintains the self.app_seqnum instance variable which indicates the sequence number of the last packet packet to be delivered to the application -- so self.app_seqnum+1 should be the sequence number of the next packet to be delivered to the application. This instance variable may be useful in your code...

• When an ACK packet arrives at the sender, the sender's process_ack method is called. It should clear the saved packet, indicating that the next call to reliable_send is free to send the next data packet. It should also call the calc_timeout method to compute the ACKed packet's round trip time and update the value of self.timeout using the formulas described in section 22.2.3 of the lecture notes.

reliable_send(self,time)

This function, invoked every time slot at the sender, decides if the sender should (1) do nothing, (2) retransmit the previous data packet due to a timeout, or (3) send a new data packet -- see the detailed description above. timeis the current network time measure in time slots. The send_pkt can be used to build and send a data packet -- see the definition of this function in lab10_stopwait.py for details about the calling sequence. send_pkt also return the packet it transmitted so it can be saved pending acknowledgement.

process_ack(self, time, acknum, timestamp)

This function is invoked whenever an ACK packet is received. time is the network time when the ACK was received, acknum and timestamp are the sender's sequence number timestamp that were echoed in the ACK. This function must call the calc_timeout function described below, among other things.

calc_timeout(self, time, timestamp)

This function should be called by your process_ack method to compute the most recent data packet's round trip time and then recompute the value of self.timeout. Add a print statement that reports the mean (self.srtt) and deviation (self.rttdev) you've calculated for the round-trip time.

In ReliableReceiverNode please implement:

reliable_recv(self, sender, time, seqnum, timestamp)

This function at the receiver is invoked upon receiving a data packet from the sender -- see the detailed description above. You can use the send_ack method to build and transmit the ACK packet.

If you introduce additional instance variables in the sender or receiver, you should add the appropriate initialization code to the reset method for the class.

Interview Questions

Please enter your answers to the following questions into a separate file (along with your answers to the questions for Task #2) and submit the file on-line by the due date.

• Run your code with no packet loss (specify -l 0 on the command line) and click "Step All" to run for 2000 time slots (the default value for the -t command line argument). What is the RTT estimate you see at the sender during your simulation? Given that every link forwards one packet per timestep, does the observed value match what you would expect?

• For this question you might want to disable all but the throughput and timeout calculation printouts. Run a set of experiments with increasing packet loss probabilities, taking measurements for 0.0, 0.01, 0.02, 0.05, .1 and .25. Report the throughput and the timeout interval you see at the receiver at the end of each simulation.

  For, say, a packet loss probability of 0.01, is the measured throughput what you would expect? Explain. Hint: Remember that the packet loss probability (.01) is per link, so on a 6-link round-trip path, the probability of a loss during the whole round trip is (1 - .99⁶) = 0.0585. Using this probability, compute an estimate of the expected time to transmit 100 packets and then use that to compute an estimate of the throughput.

Task #2: A sliding window protocol (5 points)

The sliding window protocol extends the stop-and-wait protocol by allowing the sender to have multiple packets outstanding (i.e., unacknowledged) at any given time. The maximum number of unacknowledged packets at the sender cannot exceed its "window size", and is specified with the "-w" option. The window size is available as self.window.

Upon receiving a packet, the receiver sends an ACK for the packet's sequence number as before. The receiver then buffers the received packets and delivers them in sequence number order to the application. See section 22.3.2 of the lecture notes.

In this task, you will implement the same functions that you did for the previous task, with the necessary modifications to have multiple unacknowledged packets outstanding. You can copy over the calc_timeout function from the previous task; if implemented correctly, it won't have to change. When you run your code with a window size of 1 ("-w 1" option), you must get the same value throughput as you did in the previous task; this will serve as a necessary (but not sufficient) sanity check for the correctness of your sliding window protocol.

Then run the protocol for various values of the window size ranging from 1 to 10. Determine how the throughput depends on window size and think about out why.

Interview Questions

Please enter your answers to the following questions into a separate file (along with your answers to the questions for Task #1) and submit the file on-line by the due date.

• Using the default values for packet loss (.01) and simulation time (2000 time slots), report the throughputs you observed for window sizes from 1 to 10. Explain why your results make sense.

• In this example, what would be the pros and cons of setting the window size to some large value? Aside from throughput what are the other resource implications of a larger-than-necessary window size?