CS 118 Spring 2011 : Homework 7Figure 1: Binary treeProblem 1Consider two ways of doing network-wide broadcasting: source replication (unicasting each message to eachdestination), and in-network replication (true network-layer broadcast, i.e., routers help). Suppose a source-based spanning-tree is used to achieve network-layer broadcast. Further suppose that there is a single senderand 32 receivers, and the sender is connected to the receivers through a binary tree of routers as shown inFigure 1. Each time one packet (or a copy of a packet) is sent over a single link, it incurs one unit of cost.a. What is the cost of sending a broadcast packet using source replication?b. What is the cost of sending a broadcast packet using in-network replication?c. Now assume you can choose any topology to connect the sender to the 32 receivers. What topologywill have the greatest cost disparity between unicast emulation and true network-layer broadcast?You don’t need to provide any numbers, just describe (or draw) the topology. You can use as manyintermediate routers as you like.a. The sender unicasts a copy to each receiver. Each path has 5 hops. There are thus 160 link crossings(5*32).b. A copy of the message is forwarded over each link exactly once. There are thus 62 link crossings(2+4+8+16+32).c. A topology in which all receivers are in a line, with the sender at one end of the line, will have thelargest disparity between the cost of network-layer broadcast and unicast emulation.Problem 2This question is about the CRC algorithm, as described in your week-8 lecture slides.a. If you have a 4-bit generator G = 1001, and a message M (x) = 10111010, what is the value of R?b. What would the sender of the message send over the wire?a. If we divide 10111010000 by 1001, we get 10101111, with a remainder of R = 111.b. The sender would send 10111010111.Page 1 of 2CS 118 Spring 2011 : Homework 7Problem 3Suppose an IP implementation adheres literally to the following algorithm on receipt of a packet, P, destinedfor IP address D:if (MAC address for D is in ARP cache)send Pelsesend out an ARP query for Dput P into a packet queue until the response comes backa. If the IP layer receives a burst of packets destined for D, how might this algorithm waste resources(not including its packet queue)?b. Describe briefly how you would modify the algorithm to be less wasteful.c. Suppose we simply drop P, after sending out a query, when cache lookup fails. Identify one majorproblem that might occur. (Some early ARP implementations allegedly did this.)a. If multiple packets after the first arrive at the IP layer for outbound delivery, but before the first ARPresponse comes back, then we send out multiple unnecessary ARP packets. Not only do these consumebandwidth, but, because they are broadcast, they interrupt every host on the LAN.b. We should maintain a list of currently outstanding ARP queries. Before sending a query, we first checkthis list. (We also might now retransmit queries on the list after a suitable timeout.)c. This might, among other things, lead to frequent and excessive packet loss at the beginning of newconnections.Page 2 of
View Full Document
Unlocking...