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.
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.
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:-
You will find more information about SB Routers, here Feel free to contact your TA about this topic.
- 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?
There is renewed interest in scalable routing protocols to replace BGP,
and efficiently support multipath (i.e. load-balanced) routing.
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.
For prototyping, simulation and demonstration, we have some tools that you
- SIM : You are familiar with this already. You can extend the source to add new
- 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.
- 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.