Project Topics

Some Basic Information

An important part of being a researcher is learning how to choose and define a problem - then solve it. In fact, learning how to choose a problem that is relevant, solvable and interesting is a big part of the art of research. The goal of the projects is to give you some experience picking a topic. To that end, we only list project areas below - not detailed project specifications. You need to spend some time defining the project (discussing it with whoever you want and need to), then writing a proposal to us. As you'll see from the project schedule, you need to submit your proposal by Wednesday April 17th.

Project Guidelines

Here are some guiding principles when picking a project:

Pick a project that solves a problem. Be sure that you can clearly articulate the problem. For example, you could try to solve the problem that iterative scheduling algorithms don't seem able to provide throughput guarantees without speedup.
Pick a project for which you are interested in the outcome. If you are not passionate about the topic, you won't feel enthused to find a result.
Pick a project that involves more than just simulation, or menial checking. While simulation can be useful to help develop intuition, and to demonstrate ideas, it can't prove anything, and is rarely convincing in its own right. Pick a problem that has some analytical aspect to it, even if your model and analysis is approximate.
Avoid projects that are a "survey" of work done by other --- we want to see projects that solve an interesting and useful problem, contain an analytical component to them, and (at least attempt to) lead to a novel result. Of course, any good project report will include a survey of the work that has gone before.
A good template for a problem is one in which there is a well defined, easily understood problem, that can be analyzed with a (perhaps simple) model, and can then be demonstrated using simulation or prototyping. Of course, the best methods to use for a particular problem are dependent on the problem itself; but this is a useful guideline.

Project Areas

Here are some areas you might consider. It's not an exhaustive list, but gives you a starting point:

Switch scheduling algorithms:
For example, you could propose a new switch scheduling algorithm, then prove its stability using methods described in class. You might consider unicast or multicast; priority classes; randomized algorithms, iterative algorithms, or some other. There are many unexplored directions.
IP lookup and classification algorithms:
You could propose a new method for classifying packets. You could think about new algorithms, new circuits for existing algorithms, or new applications for which new algorithms are needed. You could analyze the worst case and typical case storage requirements and lookup speed. You could demonstrate the algorithm, and compare it to existing algorithms by adding it to the PALAC simulator.
Simulation tools:
You could deduce precise ways to determine that a simulated switch has stabilized (or not), then add a new module to SIM to demonstrate that it works.
Congestion Control:
There are many new, interesting differential-equation based models of congestion control algorithms. These models lead to many interesting questions: such as, what queue management algorithms work well, how big should router buffers be, and what new congestion algorithms would work better than the existing ones. This is a rich area for novel research.
Multistage switches:
In class, we have so far seen only switches with one stage of buffering. We'll soon see switches with a single switch fabric, but two stages of buffering (and "speedup"). There are many proposed switches with multiple stages of switching and buffering, but generally there are no closed form models for them, and no ways known to analyze their performance.
Single Buffered Switches: Single Buffered Switches, are switches with a single stage of buffering. You will see examples of such switches in class. Primary amongst these are the Parallel Packet Switch, and the Distributed Shared Memory Router. As you will see SB Routers can be analyzed for their delay properties, with speedup. There are a lot of open problems here. For example:-
- What is the minimum speedup required for SB Routers?
- What can one say about delay properties in SB Routers, where there is no global state?
You will find more information about SB Routers, here Feel free to contact your TA about this topic.
Routing:
There is renewed interest in scalable routing protocols to replace BGP, and efficiently support multipath (i.e. load-balanced) routing.
Measurement:
Very little is known about how the Internet really behaves. For example, while it is (somewhat) possible to capture packet traces at a single point in the network, it is not yet possible to gather and correlate large packet traces from multiple locations at a time. But if we were able to gather such data, what methods could we use to analyze the data, and what might we expect to learn?
New Ideas:
You are welcome to suggest new topics which might be of interest. Feel free to discuss your new topic proposals with the TA's and the Instructors.

Tools

For prototyping, simulation and demonstration, we have some tools that you can use.

SIM : You are familiar with this already. You can extend the source to add new algorithms etc.
Xdistribute : A tool for spawning and managing multiple simulation processes on a number of machines in parallel. Useful for big simulation tasks.
PALAC: A simulation tool for comparing different lookup and classification algorithms
Virtual Router: A tool (used in CS244a) for implementing and modifying a router in user space in Linux.
NetFPGA: A hardware platform (used in CS344) for designing and implementing algorithms in hardware (Verilog), then deploying them in a real operational network. Other tools:
NS-2: A general purpose network simulator that contains implementations of TCP/IP, and end hosts.
SSFNET: Similar to NS-2, but designed to simulate large networks more efficiently.