CSE 221: Final Project

Fall 2003



The goal of the final project is to deepen your knowledge in one area of computer systems research. You can work in groups of 1-3 people of your choice on the project. If you do not form a group on your own, we will help you find one. You will work on the projects in the last half of the class, and we will use our final period to conduct brief presentations of all of the projects.

   Project Types

The project can take one of two forms:

1. Survey

Your project will survey the major research results and directions of a particular systems reseach area (see below for suggestions). You will need to identify the area, propose a set of 6-8 papers for that area, read the papers, and write a 6-8 page report. The report should describe the area, classify and synthesize the approaches and techniques, distinguish contributions made by the various research projects described in the papers, and hypothesize about potential future research directions. The report should demonstrate critical thinking about the work covered in the area, not just regurgitate the material in the papers read.

2. Implementation

Your project will focus on implementating an artifact or experimentally evaluating a system (see below for suggestions). You will need to propose an implementation or evaluation project, and write a 6-8 page report. The report should summarize previous work, state the problem you are investigating, and then describe the implementation or set of experiments you performed. If you performed experiments, you should clearly describe your experimental methodology and the results of your experiments.

If you were assigned a machine for doing kernel hacking for your project, here are directions for remote console and power access to the machine.

   Project Timeline

Groups and topics: 11/4 at 9:30am

Proposal: 11/10 at 23:59 (midnight)

Checkpoint: 11/21 at 23:59 (midnight)

Reports due: 12/9 at 11:30am (at the presentations) (Savage), 12/10 at 12:00 (noon) (Voelker)

Presentations: Tue 12/9 at 11:30am in WLH 2204 (Savage), Fri 12/12 at 8am in WLH 2112 (Voelker)

   Project Topics

Survey Projects

  1. Threads vs. Events. A long-standing debate in operating systems is the use of threads versus events to architect and structure high-performance servers. As a contemporary example of this, Matt Welsh (now at Harvard) demonstrated in his thesis that an event-based architecture for high-performance Internet services scales and performs better than those using a thread architecture. Interestingly, Eric Brewer, Matt's thesis advisor at Berkeley, and his student Rob von Behren just published a paper in this year's SOSP that demonstrates that a thread architecture scales better for Internet services.

    Read and digest the published work on this topic, starting with Welsh's and von Behren's work and progressing backwards through referenced work. Synthesize and summarize the arguments on this topic in your report. Explain how researchers could arrive at seemingly contradictory conclusions. Take a stand, and compellingly argue one side. Can future work end this debate once and for all?

    "SEDA: An Architecture for Well-Conditioned, Scalable Internet Services." Matt Welsh, David Culler, and Eric Brewer. SOSP 2001, October, 2001.

    "Capriccio: Scalable Threads for Internet Services." Rob von Behren, Jeremy Condit, Feng Zhou, George C. Necula, Eric Brewer. SOSP 2003, October 2003.

  2. New Directions in Protection. An old topic that is receiving new attention is protection. Much of this attention is due to issues in the use and control of digital media rights. Efforts are underway, such as the Palladium effort at Intel, to provide additional hardware for implementing additional protection and security features.

    Read and digest published work on this topic, starting with the XOMOS paper referenced below as well as tracking down information on Palladium. Survey these efforts, compare and contrast the new protection and security goals with more traditional goals that we have read and discussed in this course, and describe how operating systems need to change to take advantage of this new hardware. If this hardware becomes prevalent, how will it change the face of computing?

    "Implementing an Untrusted Operating System on Trusted Hardware" David Lie, Chandramohan A. Thekkath, Mark Horowitz. SOSP 2003.

Finally, below is a list of suggested topics that have appeared recently in the OS literature. These are only suggestions; if there is another topic that you are particularly interested in, then I encourage you to pursue that topic.

Implementation Projects

  1. Laptop Access Points. Apple Powerbooks running OS X can act as an 802.11 Access Point (AP). As an AP, a Powerbook can act as a gateway between, say, a wired network and other nearby 802.11 wireless laptops. Implement this functionality for Linux laptops. Open Access Point software exists, so most of the work will be getting it to run smoothly and seemlessly.

  2. HotelNet. The goal of HotelNet is to provide multihop wireless access in an environment that has a single available Internet connection, such as a hotel hosting a conference. Conferences typically provide wireless Internet access near the conference venue, and it would be convenient for attendees to be able to use that Internet access from their hotel rooms in the evening. Assuming that attendess are randomly distributed throughout the hotel, chances are good that they can form an multihop ad-hoc network using attendee's laptops in their rooms and the wireless AP providing Internet access near the conference venue.

    Implement HotelNet using existing software packages. Implementations exist for various ad-hoc routing protocols, such as a Click implementation of AODV.

  3. Network mobility. Folks at Scripps Institute of Oceanography have an interesting need for network mobility and ad-hoc networks. They frequently go on cruises in the ocean around the world to conduct research experiments. Consider each boat as being its own network. When a boat obtains Internet access, either via satellite or when docked at port, SIO wants seemless network access without having to change IP addresses or DNS names -- for connections originating from the boat to the Internet, and viceversa.

    Furthermore, they often have multiple boats within communication range of each other. They would like to form a multihop wireless ad-hoc network among the boats, with the boat with the best satellite connectivity serving as the Internet access point. Again, they require that each ship maintain its own network and that IP addresses and DNS names do not change as the ad-hoc network is formed.

    Using existing implementations for VLANs and ad-hoc routing algorithms, implement a system that SIO can use for its boats.

  4. BREW Cell Phones. BREW is a runtime system for programmable cell phones. Do something with BREW.

  5. Arch/OS interaction. Read these two papers: Ousterhout, "Why Aren't Operating Systems Getting Faster as Fast as Hardware" and Anderson, Levy, Bershad and Lazowska, "The Interaction of Architecture and Operating System Design", ASPLOS 1991. Each deals with performance interactions between operating systems and microprocessor architecture. Repeat one or more important aspects of these studies using current hardware and explain your conclusions.

  6. Disk performance. Modern disks have complicated performance characteristics. Build a test suite to measure how read and write bandwidth change across the disk, changes in seek time.

  7. Virtual honeyfarm. One way to detect new network worms is through the use of a honeypot... a machine that exists purely for the purpose of being broken into. Use Xen to take this idea to the next level: a virtual honey farm. A single PC should be able to support many virtual linux systems. Each should be able to be reloaded on demand. Detect compromises by logging outbound network data.

  8. User-level file system. Take the file system code from a popular operating system (e.g. linux or freebsd) and rehost it at user-level (like the Alpine project did for networking (http://alpine.cs.washington.edu)). It isn't necessary to do this perfectly this quarter :-)

  9. Disk layout. Windows reorganizes data on disk over time to improve performance. Repeat this exercise on linux or freebsd. Consider doing one of the above: a) track which sets of files are read together and arrange to store these files sequentially on disk b) track which files have the most data read and store them on the outside tracks with the greatest bandwidth. c) move frequently accessed files to the center of the disk (to reduce seek latency) Measure how much difference this made.

  10. PC suspend/resume. Build a pc suspend mechanism for linux that copies all essential state (i.e. all allocated memory) either to a server over the network or to a flash card (its quite reasonable to carry 1GB in your wallet these days) and then can restore this state on demand.

  11. Crash server. When an application running under Windows crashes it automatically sends back to Microsoft critical information about the crash and what caused it (application name, register set, stack contents, etc). Build this capability into linux.

  12. SimPoint an OS. Brad Calder and his students have developed a tool called SimPoint that enables fast and accurate program simulation and analysis. So far they have used the tool primarily on user-level applications like the spec benchmarks. Extend and use SimPoint on an open source operating system like Linux or FreeBSD.


voelker@cs.ucsd.edu, savage@cs.ucsd.edu