[SOLVED] EN.601.619 Final Exam

Section 1

Please answer all the questions in this section (100 points). Please remember to explain all your answers (e.g., an answer with a numerical result should show how you derived it).

1.  We saw in the Jupiter paper that large-scale datacenters are built as Clos, a topology that we had seen earlier in the Fat-tree paper. Discuss two advantages and two disadvantages of Clos-based datacenters compared to datacenter designs based on random graphs such as Jelly􏰅sh.
2.  Suppose ASes run standard BGP routing policies (Gao-Rexford model), an undi- rected link between Si and Sj means that Si and Sj are peers, and a link from Si to Sj (Si → Sj) means that Si is a provider of Sj (equivalently, Sj is a customer of Si). In the network below, will S5 be able to reach S9?

   • If yes, what path does S5 take to reach S9? Compute the path stretch, de􏰅ned as the ratio of the length of the BGP policy compliant path to that of the shortest path.

   • If no, explain why several of the paths in the network (at least three) from S5 to S9 violate Gao-Rexford policies.

3.  We saw that, similar to vanilla TCP, datacenter transport protocols such as DCTCP harness Additive Increase, Multiplicative Decrease (AIMD). This allows them to dynamically adjust their sending rates, in a fully distributed manner, while converging to both fairness and e􏰌ciency. From two possible alternatives to AIMD􏰎Multiplicative Increase, Additive Decrease (MIAD) and Additive Increase, Additive Decrease (AIAD)􏰎which one(s) converge to fairness and e􏰌ciency? Draw the Chiu Jain plots to demonstrate your answers.
4.  What is the max-min fair bandwidth allocation in the network below? A, B, C, D are hosts that each wish to send at the maximum possible rate to E. The arrows are links and the numbers denote link capacities.

5. What does agility mean and why is it an important property in designing cloud infrastructures and systems? Discuss at least one technique that cloud providers deploy to maximize agility.
6.  The OpenFlow paper that we read discusses the original design of SDN.
   • Analyze, in a qualitative manner, (a) scalability, (b) fault-tolerance, and (c) performance limitations of this design.
   • Discuss two approaches that cloud providers deploy to target and mitigate any of these limitations. You can discuss any SDN-based cloud systems and their solutions to SDN’s original shortcomings.
7.  Failure detectors are key building blocks of many cloud systems including key- value stores. We saw that it is impossible to build failure detectors that guarantee both completeness (each failure is eventually detected by at least one non-faulty node) and accuracy (no mistaken detection) in unreliable networks that occasionally drop packets.
   • Which of these two properties􏰎completeness and accuracy􏰎practical cloud systems guarantee and why?
   • Explain how a Ring failure detector works and why it is not complete.
   • Why o􏰄-the-shelf gossip-based failure detectors can have poor accuracy in datacenters?

     Section 2: Peer Validation

8. The 􏰅nal task for the project is to evaluate a peer project. Similar to the second assignment, we need you to validate and comment on the reproducibility of the results of the group project assigned to you. The group-validator assignments has been posted on Piazza.
   • Write a brief summary (1 paragraph) of the project assigned to you: What problem they target? Why is it important? Their approach? Their progress?
   • Write a comment or question for that project.
   • Please use the following rubric to leave a score on the reproducibility of their results. Note that this is not their 􏰅nal grade. The teaching sta􏰄 will be evaluating the projects and reproduce the results separately. This is just to give us another perspective and practice peer-validation.
     1. (a)  Code ran to completion and results matched very well with the report.
     2. (b)  Code ran to completion and results matched fairly well with the report.
     3. (c)  Code ran to completion but results did not match the ones in the report, or all results in the report were not produced with the default run con􏰅guration.
     4. (d)  Code did not run to completion (exceptions, in􏰅nite loops, no progress/debug out- put/log output, etc.)
     5. (e)  Instructions were so vague or incomplete that the setup could not be completed to even start the code.
     6. (f)  Instructions not found.
   • [Optional] Feel free to write some additional feedback in addition to the reproducibility score. We will also appreciate if you can comment on the quality of analysis and if you thought it was interesting.

Section 3: Extra Credit

You can optionally answer at most one question in this section. If more than one question in this section is answered, we will grade only the 􏰅rst one.

9. [5 points] Describe a desired property in cloud computing that cannot be guaranteed with either Consistent Updates (CU) or Consensus Routing (CR). Give an example that shows a violation of this property despite using CR or CU. You can alternatively show how deploying CU (or CR) itself can occasionally violate this property.
10. [5 points] In class, we saw the complete membership protocol in which each node retains the complete list of all other members of the group. An alternative membership protocol that is deployed in systems such as Cyclon is retaining a partial membership list at each node that is selected independently (for each node) and uniformly at random from all members. Compare, asymptotically, the expected propagation time of gossiping in a complete membership protocol and in a partial one.
11. [10 points] We analyzed the scalability and fault-tolerance of the push epidemic multicast protocol. In push epidemic multicast protocols, once a node is infected, it starts transmitting the message. Analyze the scalability of the pull epidemic multicast protocol where each node periodically polls a few randomly selected nodes for new multicast messages.

4