Massachusetts Institute of TechnologyDepartment of Electrical Engineering and Computer Science6.829 Fall 2005Problem Set 1 September 8, 2005This problem set has 4 questions, most with multiple parts. Answer them as clearly and concisely aspossible. You may discuss ideas with others in the class, but your solutions and presentation mustbe your own (for each such discussion, please mention whom you collaborated with). Do not lookat anyone else’s solutions or copy them from anywhere (in particular, “bibles” are not allowed).Turn in your solutions by 5:00 pm, Thursday, September 22, 2005 to 32-G940.This problem set includes a programming exercise. More detailed instructions on that are providedwithin the question.1 MultiplexingIn this problem, we will compare statistical multiplexing to time-division multiplexing (TDM).1In our statistical multiplexing scheme, packets of all sessions are merged into a single queue and transmitted on a first-come first-served (FCFS) basis. In the TDM scheme, packets from eachsession are queued separately. Time is divided into slots and each queue is assigned a time slot ina round robin manner. We assume the size of a slot is much smaller than the time required fortransmitting a frame/packet on the link.A switch is said to be work conserving if the only time it is idle is when there are no frames waitingfor service.1. Is our TDM scheme work conserving? What about our statistical multiplexing scheme?2. Let’s study the impact of statistical multiplexing on queuing delays. Suppose there are Nconcurrent sessions each with a Poisson traffic stream with rate λ frames/second. Also supposethat frame lengths are exponentially distributed, such that the average rate at which framesare serviced at the switch is µ frames per second (µ>Nλ). What is the average delay seenby a frame in TDM and in statistical multiplexing? What is the physical interpretation ofyour result?3. Assume that all the sessions send frames at a simple constant bit rate and that there are Aactive sessions at a given point in time out of a possible N, sharing an output link. What isthe utilization of the output link when the aggregate input rate for the A active sessions is µframes/second. Sketch this as a function of A for both statistical multiplexing and TDM.4. Explain why TDM has smaller variation in the delay of a frame through a switch, comparedto statistical multiplexing. (This delay variation is sometimes called the jitter.)1If you have no background in queueing, check Data Networks by Bertsek as and Gallager.12TodelayACKornot?A TCP receiver must acknowledge every alternate segment under normal operation. Sometimes,segments may be lost or delayed, requiring a delayed ACK timer to acknowledge the last in-sequencebyte so that the connection may continue. Most BSD-derived TCP implementations implement thedelayed ACK timer using a 200 ms heartbeat timer. Whenever the heartbeat timer fires, the receiverlooks through all its established TCP connections and sends and ACK on each connection that hasan ACK pending. In contrast, some versions of Solaris TCP implement this using a 50 ms intervaltimer, which schedules an ACK for a connection to be sent exactly 50 ms after a segment arrives onthe connection. Of course, if the next segment were to arrive in the interim, this timer is canceledand the appropriate delayed ACK sent.1. Suppose the delayed ACK timer is set to δ seconds, the maximum available bandwidth forthe path is r bits/s, the connection’s round-trip time is ρ seconds, and data packets are ofsize s bits. Suppose the connection has a window size of larger than one segment. Under whatcondition does the delayed ACK timer prevent normal delayed ACKs from ever being sent?That is, under what condition do all the ACKs get sent triggered by the interval timer, interms of the parameters above?2. If the average TCP segment size s is 512 bytes, δ is 50 ms, and ρ is 120 ms, what values of rcause an ACK for every incoming segment triggered by the interval timer? Is this a realisticbandwidth range in today’s Internet? Therefore, is this 50 msinterval timer a reasonableimplementation of delayed ACKs?3TCPchecksumsTCP has an end-to-end checksum that covers part of the IP header, in addition to the TCP headerand data. When the receiver receives a data segment whose checksum doesn’t match, it can do oneof two things:1. Discard the segment and send an ACK to the data sender with the cumulative ACK field setto the next in-sequence byte it expects to receive, or2. Discard the segment and do nothing else.Is one action preferable to the other (or are they both equivalent)? Why? (You should look up theTCP and headers in any standard networking textbook; note that the header formats in Cerf &Kahn’s paper aren’t used any more.)24 Reliable Message Transfer ProtocolThe goal of this assignment is to implement a reliable message transport protocol (RMTP), similarto TCP. The assignment will involve building a simple server and client that realize this protocol.The simple client requests a filename from the server and the server transmits the file reliably tothe client. Unlike a TCP client, the RMTP client does not need to handle reordered packets verycarefully. The full specification of the protocol is as follows:• All messages exchanged between the client and the server have a message type (e.g., SYN,SYNACK, SYNRETRY, SYNACKACK, DATA, ACK, FIN, FINACK), a sequence number,a timestamp and the payload (i.e., the actual data).• The client initially contacts the server (which is listening on a specific host and port) with aSYN message. The data field of the SYN message specifies the filename that the client wantsto download. The sequence number of the SYN message is set to 0 by convention.• On receiving the SYN message, the server tries to open the specified file for reading. If thefile open succeeds, the server a) picks a random sequence number, and b) sends a SYNACKmessage with the sequence number picked in (a). The server specifies the size of the chunksin which the file will be transmitted in the payload field of the SYNACK message.If the file open fails, the server sends a SYNRETRY message to the client.• The client has the responsibility of reliably transmitting the SYN message. If the SYN,SYNACK or SYNRETRY messages are lost, the client times out and retransmits the SYNuntil it is successfully received and acknowledged by the server.• If the client gets a