Computer Laboratory

Supervisions 2009/2010

Supervision questions: Advanced Systems Topics

This is the set of questions for my supervisions in Advanced Systems Topics. I will typically email you a list of question numbers before each supervision, but if not, attempt the next two or three. (More questions will appear here as I set them, so come back if you want to make an early start on some of the future work.)

Administrativa & handing in work

I expect you to make a good attempt at producing solutions to the relevant questions before each supervision. I prefer submissions by email (PDF or text format). Please submit your work 24 hours before the supervision. If you want to submit a hard copy of the work to student administration, please hand it in before 17:00 two days before the supervision (i.e. before Wednesday, 17:00 for a Friday afternoon supervision) as I will have to scan it. Remember that Student Administration is closed on weekends.

When emailing me regarding supervisions, please only use my lab address, or your email will be misfiled and may slip by unnoticed:

The questions I set for a supervision are generally intended to take an average student 4-5 hours to answer to a satisfying standard. However, I do realise that some of these allow for fairly verbose answers. If you find you feeling like you are spending too long on a question, I suggest you finish your answer in bullet-point style and move on to the next question. The mark allocation (whilst very approximate) should give you a rough idea of how you should divide your time between the questions, as well as how much credit I expect a similar question to be worth in the exam. It will also serve as a guide for me when marking the questions.

If there is a particular part of the course you would like explaining, or questions you have about the lectures (independent of whether they are covered by the questions or not), please let me know in an email before the supervision so that I can prepare appropriately.

Internet Routing Protocols

  1. Explain, with respect to the topologies considered, the algorithms used, the different parameters and optimisation targets (e.g. minimising upstream traffic, finding shortest/cheapest routes, etc.), the difference between
    • an Interior Routing/Gateway Protocol (IGP),
    • the Interior Border Gateway Protocol (IBGP),
    • and the Exterior Border Gateway Protocol (EBGP).
    [10 marks]
  2. What is "traffic engineering" and why do ISPs do it? (Explain the general concept, but not specific details and methods yet.) [3 marks]
  3. With the aid of a diagram (consider an example network topology), explain why BGP does not have a complete view of the network topology and why this is desirable. [Hint: Consider announcing routes via peering links.] [6 marks]
  4. Explain the following terms and their significance in the context of BGP dynamics and traffic engineering:
    • Hot potato routing,
    • Local Prefences,
    • ASPATH length and padding,
    • Multiple Exit Discriminators (MEDs),
    • the COMMUNITY attribute.
    [12 marks]
  5. 2008 Paper 7 Question 8 [20 marks]
  6. Explain what aggregation means with regards to routing tables, why de-aggregation is happening and why it is a problem. [10 marks]
  7. 2009 Paper 7 Question 3, part (a) only [11 marks]

2. Advanced Operating Systems I

  1. Distributed shared virtual memory can be used within a computing cluster to transparently allow multi-threaded programs to run across multiple machines.
    • Sketch the design of a centralized page manager detailing what data structures are maintained by the page manager.
    • Describe what happens both when a memory read and when a memory write occurs.
    • Comment on the expected performance and robustness of your system and how it can be improved with a distributed design. To illustrate, make a table showing the required number of messages for both read and write operations in the naive and the optimised model.
    [11 marks]
  2. Why is it desirable to have persistent virtual memory? What advantages can we gain from it? [3 marks]
  3. Explain briefly how pointer swizzling can be used to implement persistent virtual memory on existing machines. [5 marks]
  4. Explain how the principle of lighweight recoverable virtual memory implements some degree of persistence in virtual memory. What could this be useful for? [3 marks]
  5. Briefly explain and contrast the three concepts of a monolithic kernel, an extensible kernel and a microkernel and name an example of each. [6 marks]
  6. Seeing that they were invented in the 1980s and given their advantages, why have microkernels not become the dominant way of building operating systems? [3 marks]
  7. How did L4 manage to provide a high-performance microkernel? What are its problems? [4 marks]
  8. 2003 Paper 8 Question 5, part (a) only [16 marks]
  9. What is the problem when virtualising x86 architectures using dynamic binary rewriting? [2 marks]
  10. With the aid of a block diagram, explain briefly how the Xen hypervisor works and how its approach differs from trap-and-emulate and dynamic binary rewriting as performed by VMware. [3 marks]
  11. 2007 Paper 9 Question 1, parts (b) and (c) only [10 marks]

3. Advanced Operating Systems II

  1. 2009 Paper 9 Question 2, part (a) only [8 marks]
  2. Why was the intial NFS design chosen to be a stateless design? What implications does this have for common file operations? [5 marks]
  3. 2006 Paper 9 Question 5, part (b) only [4 marks]
  4. The Andrew File System (AFS) takes a different approach than NFS to provide remote file access. Explain briefly
    • what the basic design principle of AFS is,
    • what is the architecture of AFS is, and what modules are running on clients and on servers. Outline a simple file system operation on AFS.
    • how AFS ensures consistencies between different local Venus caches.
    • what the main advantages and disadvantages of AFS are.
    [8 marks]
  5. Coda offers some improvements on AFS: describe the scenario it was designed for and explain how Coda changes the standard behavior of AFS. [8 marks]
  6. Describe the difference between a symmetric and an asymmetric file system for SANs. [4 marks]
  7. Briefly outline the workings of a simple SAN, referring to the following areas in the context of GFS:
    • How the byte-level communication with disks is performed and which protocols are used.
    • How metadata is stored and handled.
    • What layers exist in the system, and how the low-level LUNs are presented to the OSes accessing them.
    [6 marks]
  8. A hybrid approach to SANs are Network Attached Secure Disks systems (NASD). How do they change the standard SAN approach? [2 marks]
  9. xFS is an example of a serverless network file system. Describe how it works and how it combines different techniques to achieve its goals. [8 marks]
  10. What are the main advantages and disadvantages of xFS? [4 marks]
  11. Describe the architecture of Farsite: how does it cope with failures? What were the performance challenges associated with its implementation? [10 marks]
  12. LBFS adopts an extremely aggressive data compression approach to reduce network traffic and improve performance.
    • When it should be used?
    • Describe what type of mechanisms are adopted to reduce the amount of communication needed.
    [8 marks]

4. Mobile and Sensor Systems

  1. Give examples of link state and distance vector based routing protocols for ad-hoc networks and draw parallels with routing protocols for fixed networks. [6 marks]
  2. Explain and illustrate with a diagram, how geographic routing works using GPSR in “greedy mode” making clear any assumption of the method. [6 marks]
  3. Why is GPSR in need of using the right hand rule and not just use Greedy Forwarding? [6 marks]
  4. Explain what a DTN is, and motivate your explanation with a real world example. [4 marks]
  5. What assumptions do standard network routing protocols make that do not fit with the DTN model? [4 marks]
  6. Compare and contrast deterministic and probabilistic routing in DTNs giving advantages and disadvantages of both. [6 marks]
  7. When is Epidemic routing not beatable as a delay tolerant protocol and why? [6 marks]
  8. Why is process oriented concurrency control not suited to sensor systems? [3 marks]
  9. Explain why the "gradient" concept in direct diffusion allows to cope with sensor faults. [4 marks]
  10. Do you think direct diffusion is the right protocol to use if there are more sources than sinks in the network? Why? [4 marks]
  11. What are the advantages of having abstract region primitives? [4 marks]

My thanks to Narseo Vallina Rodriguez, Salvatore Scellato, John Tang, Kiran Rachuri and Bence Pásztor, who were part of the team that came up with these questions.