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.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?Problem 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)?Problem 3 continued on next page. . . Page 1 of 2CS 118 Spring 2011 : Homework 7b. 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.)Page 2 of
View Full Document
Unlocking...