Deadlines
lab9.py -- check-in code
lab9_net.py -- Network and related classes
lab9_router.py -- Router class
lab9_random_graph.py -- a random topology generator
lab9_stopwait.py -- template file for Task #1
lab9_slidingwindow.py -- template file for Task #2
lab9_runsliding.sh -- shell script for lab question 2
lab9_prac-theory.py -- python plotter for lab question 2
lab9.zip
-- compressed archive of all these files
Complete the tasks below, submit your task files on-line before the deadline, and sign-up for your check-off interview with your TA.
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/ (use the ANSI version).
Please be prepared to run your Lab 9 code during checkoff.
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 each link can deliver at most one packet from one end of the link to the other end of the link. In our experiments, most links will run at that rate, but you can also set the rate of one of the links on the path between the sender and receiver, called the bottleneck link, to a value between 0 and 1. Each packet is 1 time slot in length, as is each acknowledgment (ACK).
In this lab, you will develop the core logic of the ReliableSenderNode and ReliableReceiverNode classes. These two classes implement the functions of a reliable data transport protocol between sender and receiver that delivers packets reliably and in order to the receiving application. The sender and receiver are connected over one or more network hops via nodes of the Router class. You don't have to worry about how routing and forwarding work in this lab.
This lab has two tasks. You will write the code for the main components of a stop-and-wait protocol and a sliding window protocol (with fixed window size). Your code will involve both the sending and receiving sides of the protocol.
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). This lab will not work in IDLE.
To understand the different parameters in NetSim for this lab, go to a shell and enter:
# python602 lab9_stopwait.py -h
# python602 lab9_slidingwindow.py -h
The programs take the following options:
In addition, for the sliding window protocol, the following option is important:
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 the test topology that will be generated when you run the corresponding task files.
At any point in the simulation, when you run the programs with the -g option, you can click on the sender, node S, to see an estimate of the round trip time (RTT) to the receiver (R) and the current timeout being used by the sender. Clicking on R will show the current throughput at the receiver measured at the number of useful (i.e., unique and in-order) packets passed up to the application per time slot, as well as the total number of spurious (duplicate) packets received. We will judge the quality of your transport protocol by the throughput printed at the end of the simulation, and also by the RTT measurements displayed at the end.
If your protocols work correctly, two things should happen:
If the protocol is correct (i.e., no deadlocks and only in-order
delivery), then the only potential problems that might remain are
performance problems: the protocol may be unacceptably slow or
unexpectedly sluggish. Obviously, we want your protocol to come as
close as possible to the theoretically expected performance. The
performance metric of interest is the receiver
throughput, measured in packets per time slot. By default,
the receiver throughput is printed by the programs only at the end
of the simulation, but if you use the -v (verbose) option,
it will be printed roughly every 100 time slots (more precisely, it
is printed the first time the receiver application gets a new
in-order packet at least 100 time slots since the last such event).
Note that if you want to extract only the throughput numbers in the
verbose mode, you can use the grep utility, running a
command such as:
# python lab9_slidingwindow.py -w 12 -l 0.02 -v|grep throughput
In addition, you can, and probably should, initially run the program with the GUI on for debugging, and click on the sender (S) and receiver (R) in the GUI to view useful information about the performance of your implementation.
To help debug your code, you can print out your own debug statements whenever a significant event occurs at the sender or receiver. You 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, then very likely something is wrong, especially if the window size is much smaller than the number of pending packets.
You can use the -l option to test both the correctness and the performance of your protocols at different link loss rates. Note that both packets and ACKs will get lost, and the value set is the per-link packet loss probability.
Another test worth running (which we may do during check-off) is to introduce variable cross-traffic into the network. You can do that using the -x option, setting a value between 0 and 1 as the rate of the cross traffic on the bottleneck link. Note that cross-traffic will both take away from the link bandwidth available for your data transfer, and will make the round-trip times more variable.
In this lab, each data packet and ACK are the same size, 1 time slot long. Each link sends one packet per time slot. Hence the maximum possible throughput of the protocol is 1 packet per time slot; because of packet losses and cross traffic, you won't achieve that maximum, but your goal should be to maximize throughput while providing reliable, in-order delivery.
Please note: In both tasks below, please use the variable names srtt for the estimate of the smoothed RTT, rttdev for the estimate of the mean linear RTT deviation, and timeout for the sender's retansmission timeout value. These variables should be members of the ReliableSenderNode class. All these quantities will of course vary with time in your protocol, and you will write the code to maintain these values. By using the variable names as mentioned here, the debugging and diagnostics information obtained when you click on the sender node will be correct (the diagnostics code assumes that these variables exist).
Note: This lab is best done either after reading the notes for Lecture 20, or in conjunction with reading them.
The stop-and-wait protocol works as follows:
In ReliableReceiverNode please implement:
Note: 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.
The template code we have provided has additional comments that you may find helpful; please read them.
After writing the required functions, run the protocol for a few different link loss rates. Observe the throughput; click on the sender and observe the RTT and timeout estimates. These observations will help you answer the lab questions for this task.
When your code is working, please submit it on-line by enabling the call to lab9.checkoff. No tests will be performed by the checkoff routine -- it will just upload your code to the server. Your TA will verify your code during checkoff and assign points at that time.
There are on-line lab questions associated with this task. Please remember to answer them.
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. In this protocol, the maximum number of unacknowledged packets at the sender cannot exceed its window size, and is specified on the command line of the program with the -w option (default is 1). 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 packet and delivers each packet in sequence number order to the application. Check out section 20.4.2 of the lecture notes to understand the semantics of the protocol and how it works.
In this task, you will implement the same functions that you did for the previous task, but with the necessary modifications to handle window sizes bigger than 1. A naive way of implementing the receiver will be to throw away all out-of-order packets, but this approach will have low throughput. A better strategy will be to create a buffer and deliver packets in order to the application.
You should copy over the calc_timeout function from the previous task; if you implemented it correctly, then it won't have to change. When you run your code with a window size of 1 (which is the default), you must get the same 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.
The template code we have provided has additional comments that you may find helpful; please read them.
After writing the required functions, run the protocol for various values of the window size ranging from 1 to 20, and also vary the link loss rate. Observe how throughput depends on window size and think about out reasons for the observed throughput. These observations will help you answer the lab questions for this task.
When your code is working, please submit it on-line by enabling the call to lab9.checkoff. No tests will be performed by the checkoff routine -- it will just upload your code to the server. The staff will verify your code during checkoff and assign points at that time.
There are on-line lab questions associated with this task. Please remember to answer them.