Massachusetts Institute of TechnologyDepartment of Electrical Engineering and Computer Science6.829 Fall 2005Problem Set 3 October 4, 2005This problem set has four questions. The first two questions involve programming and experimentalanalysis. Turn in your solutions on Friday, October 14, 2005 in recitation. Do a make handinin your code directory and email the tarball to [email protected] before 1:30pm on October 14,2005. Your code will be tested and graded in a manner similar to Problem Set 1.Congestion Control in RMTPThe first two questions in the problem set involve implementing and understanding congestioncontrol in RMTP. To answer these questions, you must extend the RMTP framework from ProblemSet 1 to include TCP-style congestion control. We have re-factored the RMTP code to be moregenerally extensible, and so your earlier ReliableServer implementation cannot be used for thisproblem set.The framework code is available in tar’d, gzip’d format at http://nms.csail.mit.edu/6.829/rmtp/rmtp.tar.gz. Download that file onto your local machine, and run the following to get tothe code:tar -xzf rmtp.tar.gz; cd rmtpYou will find nine Python files in this directory:• msg.py: Defines a class for the messages sent between the client and server. Also defines themessages types.• network.py: A networking layer used by both the client and the server to transmit mes-sages. This file handles all the messy details of scheduling timeouts and writing to sockets.The client and server interact with the network mostly through Network.sendMessage andNetwork.cancelTimeout (please note that cancelTimeout now returns the canceled time-out).• queue.py: Used by the network layer to emulate a bottleneck link. Schedules packets at aspecified rate, and drops new packets whenever a queue of finite size is full.• client.py: Defines the ReliableClient class, which implements the client side of the RMTPprotocol. This file now contains a full implementation.• vserver.py: Defines the VirtualServer, the parent class to all server types. It’s a bit of aPython hack – you don’t need to understand how this class works.• server.py: Defines the ReliableServer class. This file now contains a full implementation.• ccserver.py: Defines the AIMDReliableServer class, a sub-class of ReliableServer.Youmust complete this class by extending and overriding ReliableServer methods to implementTCP-style congestion control. This file also contains the AIMDData class, which you mustpopulate with any data that is used directly by your AIMDReliableServer class (e.g., cwnd,ssthresh, rtt, outstanding,etc.).1• manyservers.py: Creates multiple AIMDReliableServers that all share the same networkbottleneck.• mhserver.py: Creates a single logical, multi-homed server that allows data to be stripedacross multiple network paths.Code documentation for these files is available at http://nms.csail.mit.edu/6.829/rmtp.Your implementation of AIMDReliableServer should implement three main aspects of TCP-stylecongestion control: slow start, AIMD congestion avoidance, and fast retransmit.1To implementslow-start, the AIMDReliableServer starts transmitting data with a cwnd of 1 packet. On everyACK, cwnd is incremented by 1 packet until cwnd reaches ssthresh (initially, set ssthresh tobe AIMDData.SSTHRESHMAX). Thereafter, the server enters the congestion avoidance phase andimplements AIMD style congestion control, i.e., cwnd is incremented by 1/cwnd on every ACK.Out-of-order ACKs are treated as indicative of lost packets. Upon receiving three out-of-orderACKs, it retransmits the lost packet (even before it times out) and halves its cwnd. This multi-plicative decrease is done at most once per RTT. Note that the server needs to maintain additionalstate about which packets have been transmitted and which ACKs have been received, in orderto identify out-of-order ACKs. Note also that the RTT estimate should now be stored as part ofAIMDData since it is used in AIMD-related computations. On a timeout, the server sets ssthreshto half the current value of cwnd, resets cwnd to 1 and begins slow start.The Network class now has several new parameters: size, rate, and delay. The rate specifies therate at which packets are drained from some queue in the network, and can be used to emulatebottleneck links with a specified bandwidth (in packets per second). The queue size specifies themaximum number of untransmitted packets the queue can hold; the network layer will drop newpackets when the queue is full. In addition, if a non-zero delay value is specified, all packets throughthe network layer are transmitted after the specified delay. This can be used to emulate a connectionwith a specific RTT. Also, as in Problem Set 1, when a non-zero loss rate is specified, all packetsbeing transmitted over the network are dropped with the specified probability. By convention, anyqueuing and delay occurs on the server side of the connection.Note that the questions in this problem set are intended to be research-oriented, and in many casesare under-specified on purpose. Use your good judgment to fill in any holes in the problem withreasonable choices, and explain in your solutions what you did.Security advisory: Running the server exposes any file on your computer to anyonewho knows the protocol a nd the port number. Do not leave the server running forlong periods of time.1 Multiple TCP connections sharing a bottleneckIn this problem we will study the behavior of multiple TCP connections sharing a bottlenecklink. You will first need to complete the AIMDReliableServer and AIMDData classes. The filemanyservers.py creates multiple AIMD servers all of which share the same bottleneck, emulatingthe real-life situation of multiple TCP connections sharing the same bottleneck link. For example,to start two servers sharing a bottleneck link of 10 packets/second with a queue size of 5 packets,you can do the following:1Note that the fast rxmit field in AIMDReliableServer should turn fast retransmits on and off.2python manyservers.py --port 6829 --delay .5 --loss 0 --port 6830 --delay .1 --loss.05 --rate 10 --queue-size 5In this case, the first server listens on port 6829, has a delay of 500 ms, and no loss. The secondserver listens on port 6830, has a delay of 100 ms, and a loss rate of 5%. To download files fromthe two servers simultaneously, run a command like this on the client machine (all on one line):python client.py --port 6829