QuestionsScore#1 (15 pts) #2 (20 pts) #3 (10 pts) #4 (10 pts) #5 (15 pts) #6 (10 pts) #7 (10 pts) #8 (10 pts) QUESTION 1: Scalability of Peer-to-Peer Systems (15 POINTS)QUESTION 2: Routing Protocols (20 POINTS)NAME:Login name: Computer Science 461Final ExamMay 20, 20071:00-3:00pmThis test has eight (8) questions. Put your name on every page, and write out and sign the Honor Code pledge before turning in the test. Please look through all of the questions at the beginning to help in pacing yourself for the exam. The exam has 100 points and lasts for 120 minutes, so the number of minutes spent per question should be just slightly more than its point value. ``I pledge my honor that I have not violated the Honor Code during this examination.'' 1Questions Score#1 (15 pts) #2 (20 pts) #3 (10 pts) #4 (10 pts) #5 (15 pts) #6 (10 pts) #7 (10 pts) #8 (10 pts) 2QUESTION 1: Scalability of Peer-to-Peer Systems (15 POINTS)The first three parts of this question explore the scalability of peer-to-peer systems, compared to client-server systems. For this question, we assume that the interior of the network has ample bandwidth, and that propagation delay is infinitesimal. The server has a 100 kbyte file that it wants to distribute to a group of 31 receivers. All hosts have bidirectional 40 kilobit/second links to the Internet – that is, they can upload and download 40 kilobits/second – and the core of the Internet is not congested.(1a) What is the minimum time for the server to transmit the data to all of the receivers in a client-server configuration (i.e., where the receivers do not upload any content)? (3 points)The server must transmit the 100 kbyte (800 kbit) file to 31 receivers at a rate of 40 kbits/sec. The total time is (31*100*8)/40, or a total of 620 seconds.(1b) Now, suppose that the receivers can upload data, too, but only after receiving an entire copy of the 100 kbyte file. What is the minimum time for the server and the cooperating peers to transmit the data to all receivers in this configuration? (3 points)The number of receivers with a copy of the file doubles after each full 100 kbyte transmission. Each round takes (100*8)/40 = 20 seconds. The number of rounds is log232 = 5. (That is, 1 receiver completes in the first round, 2 in the second, 4 in the third, 8 in the fourth, and 16 in the fifth, for a total of 31 receivers.) Hence, the total time is 20 * 5, or 100 seconds.(1c) Now, suppose that a receiver can start uploading data to others after receiving the first 20 kbyte chunk of data. How long does it take to deliver the data to all receivers? (3 points)Similar to question 1(b), the first 20 kbytes require five rounds to complete, where each round requires (20 * 8)/40 = 4 seconds to complete. So, by the end of five rounds, 20 seconds (4 * 5) have elapsed, and every peer has the first 20 kbytes of data. The remainder of the data transfer is pipelined, where the last peers download the remaining 80 kbytes as quickly as they can. Theyneed a time of (80 * 8)/40 = 16 seconds to download the rest, for a total of 20 + 16 = 36 seconds.3The remainder of this question focuses on BitTorrent.(1d) Suppose there are many peers transferring chunks of the same large file – some broadband users with very high bandwidth and some dial-up users with very low bandwidth. Why would the broadband peers exchange chunks mostly with each other, and similar the dial-up peers exchange mostly with each other? (2 points)Peers exchange with other peers that upload to them at a high rate. Hence, broadband peers will exchange chunks with other broadband peers, leaving dial-up peers to exchange chunks with each other.(1e) Why is BitTorrent vulnerable to incomplete downloads? What steps are taken to prevent it? (2 points)After downloading the complete file, peers may leave the system rather than remaining to provide chunks to others.The “rarest chunk first” policy increases the likelihood that each chunk is available from at leastone active peer. The “random chunk” policy also helps by distributing the chunks across the peers.(1f) BitTorrent is primarily useful for popular files. Suggest ways to extend BitTorrent to work better for less popular files. (2 points)Currently, BitTorrent’s incentive mechanisms apply to each file independently. Instead, BitTorrent could provide incentives for peers to store chunks for less popular files, even if these peers are not interested in these files. For example, the system could offer virtual currency that could be used to achieve faster downloads on the files these peers actually want.4QUESTION 2: Routing Protocols (20 POINTS)The first two questions concern a shortest-path, link-state routing protocol running on the following network, where the numbers correspond to link weights:(2a) Suppose the link between nodes k and m fails. Before the failure, what is the shortest path from node i to node j? What is the new path after the failure, when routing-protocol convergencecompletes? (2 points)Before the failure: i-k-m-j (cost 6)After the failure: i-r-n-j (cost 8)(2b) A transient forwarding-loop might occur during routing-protocol convergence. Involving what nodes? List two examples of what would happen to the data packets sent from i to j during this period. (3 points)The nodes k and n may experience a forwarding loop, if k learns about the failure first and startsforwarding the packets along the path k-n-j, while n is still forwarding along the (old) path n-k-m-j.Some packets will be discarded when their TTL expires. Others may eventually escape the loop, and experience high delay and arrive out of order.3211514532ijkmnpqr5The remaining parts of the question focus on interdomain routing using BGP.(2c) BGP supports flexible routing policies. Internet Service Providers (ISPs) often have a “prefer customer” policy where they prefer to route through a customer, even if a shorter route exists through a peer or provider. Why? How is this policy realized in BGP? (3 points)Directing traffic through a customer generates revenue, whereas sending through a peer or provider is (at best) revenue neutral and may, in fact, cost money.The policy is realized in BGP by having an import policy that assigns a higher local-preference value to routes learned from customer ASes.(2d) A customer AS (like Princeton) is not supposed to announces routes learned from one upstream provider (like USLEC) to another (like
View Full Document
Unlocking...