Assignment 2 (100 points)
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. python编程课业代做
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. python编程课业代做
The simulator uses a random number generator to generate independent and identically distributed (IID) packet losses1 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.
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.
Sequence numbers. python编程课业代做
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.
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 (RT T,timeout, RT Tmin, queueing delay, etc.) in this assignment are measured in units of simulation ticks, an arbitrary unit of time we use in our simulations.
RT Tmin in the simulator.
Because time is quantized to ticks in our simulation, an RT Tmin 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 RT Tmin 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. python编程课业代做
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 RT Tmin, 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. python编程课业代做
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:38:0: W0311: Bad indentation. Found 2 spaces, expected 4 (bad-indentation). 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.
Plotting graphs.
Several questions in this assignment require you to plot graphs. You can use the Python library matplotlib for this purpose, and the file ewma.py in the starter code contains an example of how to use matplotlib. Essentially, you need to use the plot() (https://matplotlib.org/api/˙as˙gen/matplotlib. pyplot.plot.html) and show() (https://matplotlib.org/api/˙as˙gen/matplotlib.pyplot.show.html? highlight=show#matplotlib.pyplot.show) functions in matplotlib. As long as you produce the required graphs, you are free to use other graph plotting programs (e.g., Excel, gnuplot) if you find them more convenient than matplotlib.
1 Moving averages and retransmission timeouts (20 points) python编程课业代做
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) python编程课业代做
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) python编程课业代做
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.
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 RT Tmin. 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 RT Tmin and the window size. The point breakdown is the same as the previous question.
4 Congestion collapse (20 points)
5 AIMD (20 points) python编程课业代做
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 RT Tmin, you can set it to 10 ticks for this experiment, but feel free to use your own value of RT Tmin if you wish.
- (5 points) First make sure the AIMD algorithm is implemented as per the instructions in the TODOs.
- (5 points) Why do we wait for an RT T before we decrease the window a second time using multiplicative decrease? What would happen if we didn’t wait?
- (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?
- (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?
- (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 python编程课业代做
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.
6.1 Stop-And-Wait
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
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 @ 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 sent packet @ 43 with sequence number 23 sent packet @ 44 with sequence number 24 Maximum in order received sequence number 20
6.3 AIMD
See Figure 1. The figure was generated using the command line:
python3 simulator.py --loss˙ratio 0.0 --seed 1 --host˙type Aimd --rtt˙min 20 --ticks 10000 --queue˙limit 10
更多代写：澳大利亚托管网课 代考gmat 英国企业金融代上网课 澳洲留学论文代写 澳洲实验报告Essay代写 政治essay课业代做
