Carnegie MellonComputer Science Department.15-441 Spring 2008MidtermName:Andrew ID:INSTRUCTIONS:There are 22 pages (numbered at the bottom). Make sure you have all of them.Please write your name on this cover and at the top of ea ch page in this booklet except the last.If you find a question ambiguous, b e sure to write down any assumptions you make.It is better to partia lly ans wer a question than to not attempt it at all.Be clear and concis e. Limit your answers to the space provided.A B C D E F Total/ 20 / 30 / 10 / 16 / 20 / 4 / 100A Routing1. For the network depicted below, circle the answers that list valid paths that packets may take undervalley free routing between a pair o f clients.LegendClient / Stub networkProviderCustomerPeerPeerISP YISP XISP ZISP A000111000011110000111100011100011100001111000000000000111111111111000011110000000000001111111111110000111100000000000011111111111100000000111111110000111100000000000011111111111100001111A. Client −→ ISP Z −→ ISP X −→ ISP A −→ ClientB. Client −→ ISP X −→ ISP Y −→ ISP A −→ ISP Z −→ ClientC. Client −→ ISP Y −→ ISP X −→ ClientD. Client −→ ISP Z −→ ISP A −→ ISP Y −→ ClientE. Client −→ ISP Z −→ ISP X −→ ISP Y −→ ClientSolution: Total: max 5 pts(C)(3 pts) and (D)(3 pts) are correct paths.3 pts deducted for each incorrect answerPage 22. We discussed thre e different r outing protocols: link state routing (LS), distance vector routing (DV),and path vector routing (PV). Please answer the following questions by circling the protocol(s) for whichthe claim applies:LS, DV, PV - Requires a map of the complete topolog yLS, DV, PV - Sends its routing table to its neighborsLS, DV, PV - Requires floodingLS, DV, PV - Suffers the count to infinity problemLS, DV, PV - BGP is this type of routing pro toco lSolution: (a) LS (b) DV,PV (c) LS (d) DV (e) PVPage 3B Multicast3. The major use of multicast today is not on the wider Internet, but in the datacenter. It is used todistribute informa tio n or files to only thos e nodes interested in the information. One application inparticular is used in a testbed called Emulab, which a llows users to grab from 1 to 200 machines and runprograms on them. Emulab’s “frisbee” program distributes entire disk images (hundreds of MB each) toeach testbed ma chine when a use r starts an experiment, so that the machines start from a fre sh, knownoperating system installation.(a) Frisbee runs very quickly, transmitting at over 10 0Mbit/ sec. It could be quite bad if this multicasttraffic leaked out all over the Internet. What mechanism could its designers use to prevent thishigh-rate multicast traffic from leaking out of their network onto the Internet, even if so meone onthe Internet intentionally subscribed to it?Solution: The designers should use TTL-scoped multicast. (We also accepted “use firewallrules to blo ck the multicast address at the border routers” , but this solution is not as robustor convenient.)(b) You recall from class that an alternative to native multicast is “application-layer” multicast, in whichhosts transmit to each other. One logical way to set up application-layer multicast for Frisbee wouldbe to use a distribution tree: the source sends to two nodes, 1 and 2. Each of these nodes sends totwo mor e nodes, and so on, and so on.Assume that each node can send and receive at the same rate of R packets per second and canforward a packet as soon as it receives it. Assume that the switch is not a bottleneck (it c anforward as many packets as the hosts can send).Assume that there are N=128 nodes.(a) How much more time, as a percentage (100%? 100000%?), will it take to send the disk imagesto the nodes using application-layer multicast than native multicast?Solution: Given the assumption we stated above (a node forwards a packet as soon as itreceives it), the answer is: I t will take 200% of the time it would ordina rily take.The sender now sends to two nodes. There fo re, it can only send at 50% of its normalsending rate to each of those no des. Those nodes transmit two packets out for each packetthey receive–but they only receive at 5 0% of their maximum tra ffic rate.There is also a s mall additional delay from the time needed for the last packet to traversethe 7 layers of the forwarding hierarchy, but this delay (milliseconds) is tiny compared tothe transmission time.However: We were fairly flexible on gr ading this problem and also accepted the answer700%, which would be correct iff a node could only send traffic after it received it. Well,kind o f—technically, since it would have to send two copies of the disk imag e , it wouldreally be 1400 %, so we took that too.(b) If the disk image is 100,000 packets in size, how many total packet transmissions will therebe using native multicast? Using application-layer multicast? Your ans wer doesn’t have to becompletely exact, but should be within a few percent.Solution: Using native multicast, the source will send each packet exactly once. Therewill b e 100,000 packet transmissio ns.Using application-layer multicast, ea ch packet is sent using unicast. Therefore, each packetmust be transmitted in order to be received. There are 128 nodes that must receive thepacket, and therefore , there will be 128 ∗ 100, 000 total packet transmissions.Page 4(c) Again, with a disk image of 100,000 packets, how many total packet receptions will there beusing native? using application-layer?Solution: Using both schemes, every node must receive every packet. There will thereforebe 128 ∗ 1 00, 000 total packet receptions regardless of the scheme.(This illustrates the differe nce between native and a pplication-layer multicast: In native,there is one transmission but there are N receptions.)(d) Name one advantage of native multicast and one advantage of application-layer multicast.Solution: Native multicast requires fewer transmissions and is faster.Application-layer multicas t works in more heterogenous environments, because it doesn’tdepend on any particular suppo rt in switches and routers. It can also take advantageof caching and r etransmissions at the application layer, things that are fairly complex toimplement with native multicast.Page 5(Space for answers)Page 6C Tru e or False: Tunneling4. Which of the following applica tions use tunneling? (Circle EVERY item that does.)A. Converting between IPv4 and IPv6B. Virtual Private NetorksC. Network Address Transla
View Full Document
Unlocking...