- Parent Category: Programming Assignments' Solutions
We Helped With This Python Programming Homework: Have A Similar One?
|More Info||Python Assignment|
Short Assignment Requirements
Assignment 2 (100 points): Due 23:59:59, Oct 19, 2018
Before you start
This assignment is almost entirely programming with a few written questions that you will answer based on the code you write. Hence, most of the instructions are in the starter code for this assignment. We have also included an autogenerated PDF that provides you a code walkthrough; it contains information about the important Python classes in the starter code and is generated by combining together comments in the starter code. Please read the code walkthrough PDF in addition to this one.
Here, we’ll summarize information that is not in the starter code. In addition to python3, you’ll need to install the python libraries for matplotlib, a graph plotting library. You should be able to install matplotlib by following the instructions here: https://matplotlib.org/users/installing.html. If you’re using the VM image, which we recommend you do, matplotlib is already installed on it.
This assignment will take more time than assignment 1. Please start early and ask for help if you’re stuck. Use GitHub to upload your final assignment submission; we’ll send you GitHub instructions separately. Keep pushing your code to GitHub often in case your computer crashes the night before the assignment is due. When answering the written questions, provide as much detail as you think is appropriate, but err on the side of providing more rather than less detail for a question. We’ll read everything you turn in.
The assignment will also teach you how to develop protocols using a network simulator, a computer program that imitates the behavior of the essential components of a network. For this assignment, we’ll be using a custom simulator developed solely for assignment 2. I’ll list some of the non-obvious details of the simulator here because they might help you when debugging your solutions to assignment 2.
Randomness in the simulator. The simulator uses a random number generator to generate independent and identically distributed (IID) packet losses when packets are dequeued. This is in addition to packet drops if a queue overflows when packets are enqueued. You do not need to understand probability for this assignment, but you should be aware of the fact that randomness causes non-determinism in simulations. For instance, if you run two simulations with identical settings and the same loss rate, you might see different outputs because the sequence of packet drops will be randomly generated. To make such random simulations deterministic, you can use a seed to initialize a random number generator so that it generates the same sequence of random numbers. If you pass the same seed to the simulator in two different simulation runs with the same settings, the output will be the same. Also, if you don’t use random losses in your simulation (i.e., you set the loss ratio to 0), then your output should be deterministic because no other simulator component uses a random number generator.
Sequence numbers. As a matter of convention, sequence numbers for packets start from 0 (i.e., the first packet has sequence number 0). Also, we’ll be dealing with providing reliability at the level of packets, not bytes.
1 MOVING AVERAGES AND RETRANSMISSION TIMEOUTS (20 POINTS)
Link capacity in the simulator. The link capacity in all our simulations is fixed to 1 packet per simulation tick. This seems like an arbitrary restriction, but it simplifies the implementation of the simulation and the assignment, without losing anything in terms of what you will learn from the assignment. All time-based quantities (RTT, timeout, RTTmin, queueing delay, etc.) in this assignment are measured in units of simulation ticks, an arbitrary unit of time we use in our simulations.
RTTmin in the simulator. Because time is quantized to ticks in our simulation, an RTTmin of 10 ticks will result in a delay of 11 ticks between when the first packet is sent out in StopAndWait and when the second packet is sent out. This is because the first packet will be sent out in tick 0, its ACK will be received 10 ticks, later, and then only in the next tick (tick 11) can the second packet be sent. For this reason, we subtract one from the user-specified RTTmin before feeding it into our simulator. This is not particularly important, but it’s good to know in case you wonder why there is some odd-looking code in simulator.py.
Senders and receivers. Because this is a simulator, we get to simplify as much as we want, while still imitating network components relevant to what we’re trying to study. Hence, the sender and the receiver are really the same Python object called host. This host could belong to one of three classes: StopAndWaitHost, SlidingWindowHost, or AimdHost. All three classes implement two methods send() and recv() corresponding to the sender and receiver respectively.
Running the simulator. Running python3 simulator.py -h or python3 simulator.py --help should give you the usage for the simulator. For instance, the simulator lets you set RTTmin, the limit on the number of packets in the link’s queue, the loss ratio, the window size for the sliding window protocol and so on. The simulator reports the max sequence number that has been received in order at the end of the simulation period. Adding 1 to this gives you the number of packets that have been received in order. Dividing the number of packets by the simulation period will give you the transport-layer throughput.
Python Linters. Using a python linter is a good idea to help catch errors and generally improve your coding style. For a compiled language such as C or Java, the compiler will often catch errors for you, however in the case of interpreted languages (such as python), there is no compiler to do this. To help catch the errors that a compiler might normally catch, you can use a tool called “pylint”, which more scrupulously reviews your code to help catch bugs. To install, use pip3: pip3 install pylint. It can be run in “full output mode” as simply pylint or with a suppression flag enabled to edit down the warnings that it gives: pylint -E for example. An example of a typical warning you might get if you ran pylint on the simulator.py class in the homework might be: simulator.py:7:0: W0614: Unused import UnackedPacket from wildcard import (unused-wildcard-import). This would tell you that you have imported something without calling it in the file, and that you should make sure it gets used to make the program run properly.
1 Moving averages and retransmission timeouts (20 points)
1.1 Moving averages (5 points)
Implement a simple exponentially weighted moving average (EWMA) filter by translating the equations for the EWMA from lecture 4 into Python code. We have provided starter code in ewma.py. You’ll use your implementation to understand how α (also called the gain of the EWMA) affects how quickly the mean value calculated by the EWMA converges to the true value.
For this, we’ll use a synthetic set of 100 samples. The first 50 samples are 0, and the next 50 are 1. We’ll feed this to an EWMA and see how the mean estimate (also called the smoothed estimate) tracks the actual samples. Run ewma.py using two different α values: one high (0.5) and one low (0.01). How does the value of α affect convergence? Explain this using the equation for an EWMA filter.
1.2 Retransmission timeouts (15 points) 4 CONGESTION COLLAPSE (20 POINTS)
1.2 Retransmission timeouts (15 points)
Complete the TODOs in timeout calculator.py, which is a class used by both the Stop-And-Wait and sliding window protocols for their timeout calculations. Make sure that any computed timeout values always fall between MIN TIMEOUT and MAX TIMEOUT. You’ll be able to test out your retransmission logic as part of the Stop-And-Wait and sliding window implementations in the next two questions.
Why do we need a minimum value of the retransmission timeout? Why do we need a maximum value of the retransmission timeout? These questions might be easier to answer once you have incorporated the retransmission logic into both the Stop-And-Wait and sliding window protocols. To answer these two questions, you could try disabling either the MIN or the MAX TIMEOUTs and see (1) what the effect on throughput is and (2) how it affects the likelihood of congestion collapse.
2 The Stop-And-Wait protocol (20 points)
Implement the Stop-And-Wait protocol using the starter code provided in stop and wait host.py. Run the protocol using simulator.py. Carry out and report on the results of the following experiments. Use the simulator’s default large queue size limits (1M packets) for this experiment.
1. (7 points) Make sure your implementation works. This means checking that a packet is being sent out every RTTmin ticks. Print out a line to the terminal every time you send out a packet, and attach this output with your submission.
2. (6 points) Run the Stop-And-Wait protocol for several different values of RTTmin . Check that the throughput tracks the RTT1 min equation we derived in class. Plot the throughput you get and compare it with the equation we derived in class. You can use matplotlib for this.
3. (7 points) Introduce a small amount of IID loss (about 1%). Check (1) if the throughput continues to be close to the value predicted by the equation and (2) that the protocol continues to function correctly despite the loss of packets. If the throughput is much less than the value predicted by the equation, explain why, by looking at when packets are originally transmitted and when they are retransmitted. Does the divergence between the simulation’s throughput and the equation’s predicted throughput increase or decrease as RTTmin increases? Why?
3 The sliding window protocol (20 points)
Implement the sliding window protocol using the starter code provided in sliding window host.py. Again, run the protocol using simulator.py. Use the simulator’s default large queue size limits for this experiment. Answer the same three questions as the Stop-And-Wait protocol in the previous section, but remember to vary the window size as well in addition to RTTmin. When a small amount of loss (1%) is introduced, how does the divergence between the simulation’s throughput and the equation’s predicted throughput vary now as a function of both RTTmin and the window size. The point breakdown is the same as the previous question.
4 Congestion collapse (20 points)
We’ll now simulate congestion collapse using our simulator. For this, use the sliding window protocol. Calculate the bandwidth-delay product (BDP) as the product of the link capacity and the minimum round-trip time. Vary the window size from 1 to the BDP. Check that the transport-layer throughput matches up with the
W RTTmin equation, similar to the previous question. Now vary the window size beyond the BDP all the way until 100.BDP. Plot the transport-layer throughput as a function of the window size. Can you see the congestion collapse pattern that we discussed in class (i.e., utility goes down as offered load increases)? What is the reason for this congestion collapse? Can you provide evidence for this by looking at the number of retransmissions and the number of original packets being delivered by the link?
For this assignment, to keep the simulations short, pick an RTTmin of around 10 so that the BDP is around 10 (recall link capacity is 1). This will allow you to vary window sizes from 1 to 1000 and still complete each simulation in 100000 simulation ticks or so. Large window sizes will need a longer simulation time before the simulation settles into steady state. Do not introduce any IID loss (i.e., set loss ratio to 0) for this experiment. You could also try modifying MIN TIMEOUT and MAX TIMEOUT to observe a sharper version of the congestion collapse, which may also help you answer §1.2. Finally, you could also try reducing the queue size limit to observe a sharper version of the congestion collapse.
For this question, you get 10 points if you can demonstrate one set of simulation settings that leads to a congestion collapse. Write down what these settings were in your assignment submission. To demonstrate a congestion collapse, you must provide a plot of transport-layer throughput vs. window size that resembles the classic congestion collapse curve we discussed in class. You get the next 10 points if you can explain why this congestion collapse occurs and provide quantitative justification for your explanation using the number of original and retransmitted packets from your simulations.
5 AIMD (20 points)
In the final part of this assignment, you will implement the AIMD algorithm that fixes congestion collapse. Use the file aimd host.py, which shares a considerable amount of code with sliding window host.py. So if you have completed sliding window host.py, most of your work for AIMD is already done. The only major new parts of AIMD are implementing the Additive Increase and Multiplicative Decrease rules. Answer the following questions. If you need a concrete value of RTTmin, you can set it to 10 ticks for this experiment, but feel free to use your own value of RTTmin if you wish.
1. (5 points) First make sure the AIMD algorithm is implemented as per the instructions in the TODOs.
2. (5 points) Why do we wait for an RTT before we decrease the window a second time using multiplicative decrease? What would happen if we didn’t wait?
3. (5 points) Set the queue size limit to something small, like about half the BDP. Use matplotlib (or a program of your choice) to plot the evolution of the window size over time. You can plot the window size by printing out the window size and the tick number every time the send() function is called. Attach the plot with your submission. Do you see the additive increase, multiplicative decrease, sawtooth pattern that we discussed in the lecture? What is the period of the sawtooth? You can measure the period from the window size plot that demonstrates the sawtooth pattern. What is the throughput of AIMD in this case?
4. (3 points) Increase the queue size limit from half the BDP to 1 BDP and then 2 and 3 BDP. What happens to the throughput of AIMD? Why?
5. (2 points) AIMD needs a certain amount of queue capacity so that it achieves throughput close to the link’s capacity. What is the purpose of this queue?
6 Sample output
We have provided some sample output below for you to confirm if your implementations of the Stop-And-Wait, Sliding Window, and AIMD protocols are working correctly. Note that your output may not match up exactly with these outputs because there is some flexibility in how you implement each protocol and there are no simple “unit tests” for congestion-control protocols. If you’re unsure if your protocol is working correctly, ask the course staff.
Anirudhs-Air:asg2˙code˙sols anirudh$ python3 simulator.py --seed 1
--host˙type StopAndWait --rtt˙min 10 --ticks 50
Namespace(host˙type=’StopAndWait’, loss˙ratio=0.0, queue˙limit=1000000, rtt˙min=10, seed=1, ticks=50, window˙size=None) sent packet @ 0 with sequence number 0 @ 9 timeout computed to be 100 rx packet @ 9 with sequence number 0 sent packet @ 10 with sequence number 1 @ 19 timeout computed to be 100 rx packet @ 19 with sequence number 1 sent packet @ 20 with sequence number 2 @ 29 timeout computed to be 100 rx packet @ 29 with sequence number 2 sent packet @ 30 with sequence number 3 @ 39 timeout computed to be 100 rx packet @ 39 with sequence number 3 sent packet @ 40 with sequence number 4 @ 49 timeout computed to be 100 rx packet @ 49 with sequence number 4 Maximum in order received sequence number 4
6.2 Sliding Window
Anirudhs-Air:asg2˙code˙sols anirudh$ python3 simulator.py --seed 1 --host˙type SlidingWindow
--rtt˙min 10 --ticks 50 --window˙size 5
Namespace(host˙type=’SlidingWindow’, loss˙ratio=0.0, queue˙limit=1000000, rtt˙min=10, seed=1, ticks=50, window˙size=5) sent packet @ 0 with sequence number 0 sent packet @ 0 with sequence number 1 sent packet @ 0 with sequence number 2 sent packet @ 0 with sequence number 3 sent packet @ 0 with sequence number 4 sent packet @ 10 with sequence number 5 sent packet @ 11 with sequence number 6
sent packet @ 12 with sequence number 7 sent packet @ 13 with sequence number 8 sent packet @ 14 with sequence number 9 sent packet @ 20 with sequence number 10 sent packet @ 21 with sequence number 11 sent packet @ 22 with sequence number 12 sent packet @ 23 with sequence number 13 sent packet @ 24 with sequence number 14 sent packet @ 30 with sequence number 15 sent packet @ 31 with sequence number 16 sent packet @ 32 with sequence number 17 sent packet @ 33 with sequence number 18 sent packet @ 34 with sequence number 19 sent packet @ 40 with sequence number 20 sent packet @ 41 with sequence number 21 sent packet @ 42 with sequence number 22
Figure 1: Evolution of window size when running the AIMD protocol. AIMD should set the window size W according to this pattern over time; the window size slowly ramps up (slow start) until reaching a threshold where it is larger than the network can allow, so AIMD quickly backs off to a much smaller baseline W.
sent packet @ 43 with sequence number 23 sent packet @ 44 with sequence number 24 Maximum in order received sequence number 20
See Figure 1.
 In other words, every packet is dropped independent of every other packet, but we use the same probability to decide whether to drop a packet or not.
The simulator first creates a Python object for the link (link), a Python object for modeling the minimum RTT (pdbox), and a Python object to capture the end hosts, i.e., the sender and the receiver (host).
There is no separate Python object for the sender and for the receiver. Both the sender and the receiver are implemented within the same Python object called host. host.send() is called when sending packets and host.recv() is called when receiving ACKs for the packet an RTT (i.e., minimum RTT + queuing delay) later.
Similarly, there is no separate packet header format for packets and ACKs. They are one and the same. The acknowledgement process works by calling host.recv() on the same packet that was sent out as part of a host.send()in the past.
The code connects host to link, link to pdbox, and pdbox to host. Hence, packets “flow” from host (where the send() method is called to send packets) to link (where queues build up) to pdbox (where the packets incur a min.RTT worth of delay) back to host (where the recv() method is called to process ACKs for packets that were sent by host.send()).
The current value of time is represented by the variable tick, which is set in the for loop and then passed to each of the objects within the simulator. If you need to access the current value of time when implementing a protocol (e.g., for computing RTT samples, or for setting the timestamp at which a packet was sent), tick is the variable you should be using. You don’t need to create your own version of time.
This class implements a host that follows the AIMD protocol. Data members of this class are unacked: List of unacked packets window: Size of the window at any given moment max_seq: Maximum sequence number sent so far in_order_rx_seq: Maximum sequence number received so far slow_start: Boolean to indicate whether algorithm is in slow start or not next_decrease: Time (in ticks) at which the window size should be descreased
timeout_calculator: An object of class TimeoutCalculator (Refer to TimeoutCalculator class for more information)
There are two member functions - send and recv that perform the task of sending and receiving packets respectively. All send and receive logic should be written within one of these two functions.
Function to get a packet from the network.
pkt: Packet received from the network tick: Simulated time
Function to send packet on to the network. Host should first retransmit any Unacked packets that have timed out. Host should also descrease the window size if it is time for the next decrease. After attempting retransmissions, if the window is not full, fill up the window with new packets.
tick: Simulated time
A list of packets that the host wants to transmit on to the network
Structure to store information associated with an unacked packet so that we can maintain a list of such UnackedPacket objects
Data members of this class include seq_num: Sequence number of the unacked packet num_retx: Number of times this packet has been retransmitted so far timeout_duration: Timeout duration for this packet timeout_tick: The time (in ticks) at which the packet timeout
Constructor for UnackedPacket. This sets the default values for class data members
class network.Link(loss_ratio, queue_limit)
A class to represent a link with a finite capacity of 1 packet per tick We can generalize this to other capacities, but we’re keeping the assignment simple
Function to receive a packet from a device connected at either ends of the link. Device here can represent an end host or any other network device.
The device connected to the link needs to call the recv function to put packet on to the link. If link’s queue is full, it starts dropping packets and does not receive any more packets.
This function simulates what a link would do at each time instant (tick). It dequeue packets and sends it to the propogation delay box
A class to delay packets by the propagation delay In our case, we’ll use it to delay packets by the two-way propagation delay, i.e., RTT_min
class packet.Packet(sent_ts, seq_num)
Class to represent a simulated packet. It has the following data members sent_ts: Time at which the packet was sent seq_num: Sequence number of the packet pdbox_time: Arrival time at the propogation delay box retx: To identify if the packet is a retransmission
This host follows the SlidingWindow protocol. It maintains a window size and the list of unacked packets. The algorithm itself is documented with the send method
Function to get a packet from the network.
pkt: Packet received from the network tick: Simulated time
Method to send packets on to the network. Host must first check if there are any unacked packets, it yes, it should retransmist those first. If the window is still empty, the host can send more new packets on to the network.
tick: Current simulated time
Returns: A list of packets that need to be transmitted. Even in case of a single packet, it should be returned as part of a list (i.e. [packet])
Structure to store information associated with an unacked packet so that we can maintain a list of such UnackedPacket objects.
This structure is different from the packet structure that is used by the simulator. Be careful to not mix Packet and UnackedPacket
The network does not understand an UnackedPacket. It is only used by sliding window host for bookkeeping.
This host implements the stop and wait protocol. Here the host only sends one packet in return of an acknowledgement.
Function to get a packet from the network.
pkt: Packet received from the network tick: Simulated time
Function to send a packet with the next sequence number on to the network.
Timeout Calculator maintains the mean RTT and RTT variance. Data members of this class include alpha, beta and K (which have the same meaning as discussed in the lectures)
This function is used to double the timeout representing an exponential backoff
This function is used to update the mean and variance RTTs
aimd_host, 1 n
packet, 2 s
sliding_window_host, 2 stop_and_wait_host, 3
__init__() (aimd_host.UnackedPacket method), 2
aimd_host (module), 1
AimdHost (class in aimd_host), 1
exp_backoff() (timeout_calculator.TimeoutCalculator method),
Link (class in network), 2
network (module), 2
Packet (class in packet), 2 packet (module), 2
PropDelayBox (class in network), 2
recv() (aimd_host.AimdHost method), 1 recv() (network.Link method), 2 recv() (sliding_window_host.SlidingWindowHost method), 2
recv() (stop_and_wait_host.StopAndWaitHost method), 3
send() (aimd_host.AimdHost method), 1 send() (sliding_window_host.SlidingWindowHost method), 3
send() (stop_and_wait_host.StopAndWaitHost method), 3 simulator (module), 1
sliding_window_host (module), 2
SlidingWindowHost (class in sliding_window_host),
2 stop_and_wait_host (module), 3
StopAndWaitHost (class in stop_and_wait_host), 3
tick() (network.Link method), 2 timeout_calculator (module), 3
TimeoutCalculator (class in timeout_calculator), 3
UnackedPacket (class in aimd_host), 2
UnackedPacket (class in sliding_window_host), 3
update_timeout() (timeout_calculator.TimeoutCalculator method),