CS 118 Spring 2011 : Homework 2Problem 1Assume you are to send a mail message via SMTP.a. If the message is very small, what is the minimum number of round trips required to achieve this?Ignore TCP connection establishment and termination. Explain each round trip. (Clarification: around trip involves only the time for a SMTP message to go to from the client to the server and thereply from the server to come back to the client. In this case you are asked only for minimum numberof such round trips. An easy way to understand this is to connect directly to a mail server as explainedin the lecture notes and in Section 2.4.1 of your textbook.)b. You may notice that, in most cases, the server responses do not affect what the client sends next.Thus, to speed up SMTP, a client might choose to implement command pipelining: sending multiplecommands in a single message. Which portion of the exchange in your answer to part a would yourecommend be pipelined? Justify your answer. (Hint: assume the message could be large.)a. The task of sending a small message requires 6 round trips. One round trip is required for the each ofthe following:• HELO command• MAIL FROM command• RCPT TO command• DATA command• Body of message• QUIT commandb. HELO, MAIL FROM, RCPT TO, and (optionally) DATA. Explanation: It makes sense to send theHELO, MAIL FROM, RCPT TO, and perhaps DATA commands all at once, since the commandsand responses are all small, the cost of unnecessary transmission is low, and the savings (in terms ofround trips) is proportionally high. However, it is advisable to examine the server’s response for errorsbefore sending the message body, since the cost of unnecessary transmission could be quite high if themessage is large.Problem 2POP3 allows users to fetch and download e-mail from a remote mailbox. Does this mean that the internalformat of mailboxes has to be standardized so any POP3 program on the client side can read the mailboxon any mail server? Justify your answer.HERE No. By design, protocols are agnostic of server implementations, file formats, etc. POP3 programsare on the client side don’t see the server’s mailbox format or vice versa, the protocol abstracts this away.Problem 3Imagine a limited scope P2P query flooding network like the one discussed in Section 2.6.2 of your book.Let each peer be connected to at most N peers in the overlay network. Also let the “peer-count” field beinitially set to K. Suppose Bob sends a query for his favorite song. What is the upper bound on the numberof query messages that are sent throughout the overlay network as a result of Bob’s query? Explain youranswer.Problem 3 continued on next page. . . Page 1 of 2CS 118 Spring 2011 : Homework 2Bob sends his query to at most N neighbors. Each of these neighbors forwards the query to at most N − 1neighbors (they will not forward the query back to Bob). Each of those neighbors, in turn, forwards thequery to at most N − 1 neighbors, and so on. Thus the maximum number of query messages isN + N (N − 1) + N (N − 1)2+ ... + N (N − 1)K−1=N (1 + (N − 1) + (N − 1)2+ ... + (N − 1)K−1)=NK−1Xi=0(N − 1)i=N1 − (N − 1)K1 − (N − 1)=N(N − 1)K− 1N − 2(Any of the above or any other concise, equivalent expression is an acceptable answer, as long as you explainhow you got it.)Problem 4Consider the following simplified BitTorrent scenario. There is a swarm of 2npeers and, during the timein question, no peers join or leave the swarm. It takes a peer one time unit to upload or download a piece,during which time it can only do one or the other. Initially one peer, let’s call him Fred, has the whole file.All other peers have nothing. If the swarm’s target file consists of only one piece, what is the minimumnumber of time units necessary for all the peers to obtain the file? Ignore all but upload/download time.Explain your answer.During the first time unit, Fred can only send his piece to one other peer. Now two peers have the file. Inthe next time unit, the two peers send to two other peers, meaning four peers now have the file. The processcontinues exponentially, meaning that, at time unit t, 2tpeers have received the file. Thus, all 2npeers willreceive the file in n time units.Page 2 of
View Full Document
Unlocking...