The 615 final project should involve an investigation that could form
the basis of a submission to a conference in the fields of mobile
systems, communications or peer-to-peer systems.
I have provided some possible topics below. It's certainly possible
to investigate other topics, but you need to clear it with me by Oct 25.
You may work alone or in pairs. Groups working in pairs
are expected to undertake broader tasks and to perform more extensive
analyses than students working alone. No group may have more than one
If you are running an experiment that requires network measurement
in the Internet at large, I am a member of the
Planet-Lab consortium, which
provides access to a few dozen geographically distributed nodes around
the globe. Consequently, you can collect network statistics from more
than one location in the Internet.
Ad Hoc Networking Topics
- MagnetOS Staged Simulator. The Magnetos simulator has
two features that make it much faster than traditional
simulators such as ns2:
But the simulator has some shortcomings. It currently lacks a
realistic physical propagation model. Also, the benefits of the two
design features have not been evaluated at all. Your task is to add
a proper physical layer to the MagnetOS simulator, so it can be on
par in accuracy with ns2. Then carefully examine the performance
gains due to staged simulation and compile-time configuration.
- The simulator is
structured as a "staged simulator". Typically in a series of
simulations, certain computations are computed over and over
again under slightly different scenarios. For instance, a simulation
study may examine the same movement and traffic pattern, using different
routing protocols. Traditional simulators, like ns2, will recompute the
positions of the mobile nodes separately for each run, even though
most of these computations can be cached - e.g. the particular
locations of the nodes can be computed in the first pass, and
the times at which conectivity changes occur can be cached for
subsequent runs. Future runs then will run drastically faster.
- There is no runtime interpretation overhead. A traditional
simulator will provide dynamic modifications through the use of an
interpreted scripting language, like Tcl in the case of ns2. THe
MagnetOS simulator, on the other hand, has everything compiled
in. Modifications to the simulator occur only through
recompilation. This recompilation is fast & cheap, and incurs no
- MagnetOS Object Migration. The performance measurements
reported in the MagnetOS paper were done using an old simulator that did
not model contention, congestion, or MAC-layer access control at
all. As such, they overestimate the possible gains from the use of
object migration techniques in MagnetOS. Further, the object migration
techniques described in the MagnetOS paper are all
topology-blind. With just a little bit more topology information,
object placement decisions can be made with more accuracy. Finally,
there are other techniques for determining the time at which an object
needs to be moved. So the task here is to revisit the MagnetOS paper
and to essentially do it right. Use the new MagnetOS simulator to
repeat the measurements in the paper. Quantify the benefit of
topology-aware techniques for object migration. Evaluate history-based
techniques for determining the object migration time
granularity. Evaluate different techniques for updating the location
of objects when they are moved.
- MagnetOS Object Replication. An object system like
MagnetOS offers an attractive programming model for developing ad hoc
networking applications. In particular, MagnetOS enables stateful
application components to transparently move around in the
network. However, ad hoc networks fail frequently, and MagnetOS
introduces a new failure mode - an object could disappear if the node
at which it was residing runs out of energy or becomes inaccessible.
Failures can be tolerated by replicating objects. Develop the
necessary Java rewriting tools to rewrite Java objects such that there
will be N consistent replicas of an object. Modify the runtime such
that all replicas observe the same series of method calls in the same
order. This is the baseline functionality necessary for tolerating
faults, but it is quite heavy-weight and fragile. Develop techniques
to determine when such serial ordering is not necessary; e.g. through
binary inspection, identify stateless, idempotent, and commutative
operations, and weaken the serializability requirements for such
operations to improve performance.
Shafat + Hubert
Hongzhou + Piyoosh
- User management for wireless access. Managing users on a
wireless network is quite difficult. Typically, membership in the
network is controlled by a global secret. Anyone with this secret,
e.g. "rover", can connect to the network. Further, for both technical
and non-technical reasons, these secret keys need to be short. So
short, in fact, that key recovery attacks are quite feasible. People
have demonstrated that the $4 billion dollars worth of deployed
802.11b equipment out there suffers from numerous security
vulnerabilities due to these recoverable keys.
To perform user management, and to thwart attacks against keys, we
need to do two things: (1) frequently change the low-level keys before
attackers have the opportunity to capture enough packets and reverse
the key, and (2) cleave out unwanted users from the network. Use a
two-tiered approach. At the lowest level, frequently change keys using
Lamport passwords. At a higher level, use a key broadcast technique to
cleave out unwanted users. Adopt Fiat and Naor's work, which targeted
always-on set-top boxes, to the wireless network domain, where users
may be offline for significant periods of time.
Matt + Mike
Vikash + Adam
- Scent-based RoutingWork with Martin Roth to implement
his biologically inspired data dissemination protocol for ad hoc
networks. Develop your code using the MagnetOS simulator so it can be
deployed as part of the Linux networking stack. Roth's work is
reminiscent of directed diffusion, though more formally grounded, and
less tied to a particular data model. Evaluate metrics, such as
latency, overhead, throughput and jitter achieved by this protocol.
- Ad hoc and Infrastructure Convergence. Reprogram an
access point to operate in ad hoc mode using a widely available ad hoc
routing protocol such as the MagnetOS implementation of AODV. Deploy a
physical testbed in ad hoc mode. Carefully detail the modifications
necessary to the operating system, networking stack and the routing
protocol to make such a testbed a reality. Compare achieved metrics,
such as latency, overhead, throughput and jitter, on this network to a
regular infrastructure network.
- Evaluation of emerging 3G networks .
- Stateless TCP. Servers, on the web, in ad hoc networks,
or in P2P systems, typically need to store some bit of state for each
client who contacts them. This state comprises a TCP control block,
and contains the identity of the client as well as communication
parameters such as the current window size, the number of packets in
transit, etc. All of this state kept on the server makes the server
vulnerable to DoS attacks - by creating large numbers of connections
to a server, it is possible to take up large amounts of its memory and
to tie down precious virtual resources, such as ports. Some network
servers are constantly targeted by such attacks, and need to make
sizable investments to protect against them.
A simple way to thwart such attacks is to push ALL state into
clients. Design a new TCP-like protocol that keeps the connection
state entirely on the client side. The state should be
cryptographically sealed against client tampering (otherwise, I could
manipulate it to get better service at the expense of others). The
protocol should be TCP-friendly. In essence, you will have to convert
TCP from an end-to-end protocol into a continuation-based, single-end
protocol; that is, the client will contact the server, remind the
server where it was and what it was doing, and ask for it to provide
the next bit of data. Implement this in ns2 and compare against the
standard TCP implementation. Ensure that its interaction with regular
TCP flows does not lead to unfair behavior.
Peer to Peer Systems
- Anonymous Communication. Implement Herbivore, a provably
secure, scalable and efficient protocol for anonymous communication.
This protocol is based on
Mark + Milo
- P2P data dissemination. P2P data distribution networks,
such as Freenet, Gnutella, Kazaa, etc. are all client-driven, that is,
the scheduling of requests is determined entirely by clients, and the
data sources serve these clients on a first-come first-served
basis. This can lead to highly sub-optimal results.
For instance, a typical P2P client using Kazaa explicitly names
the peers from which it is willing to download a file, and does not
seek alternatives once the download starts (unless the serving peer
disconnects from the network).
There are two separate components to this project (or possibly
two separate projects). The first component is to devise a scheme
by which people can be securely compensated for the resources they
contribute to the public good. The second is to come up with a
pricing strategy for these resources that upholds the public good,
and does not lead to problems like forgery, inflation, etc.
Adopt a scheme by which peers are incentivized to use network
resources more efficiently. One approach is to store (in the network,
at a node using Pastry/Chord/CAN/et al., or randomly gossip) the fact
that the download is taking place. People with files then query the
list of current downloaders, and rush to serve them if they are
nearby. This scheme may require a secure metering system by which the
system can keep track of which nodes have contributed how many
blocks. Such a system would also keep "free-loaders" (nodes that
perform downloads but do not make files available) out of the
network. Adopt an offline microtransaction scheme (e.g. Franklin &
Young, Secure and Efficient Off-Line Digital Money) and/or a metering
scheme (e.g. Naor & Pinkas, Secure and Efficient Metering) for this
Vivek + Sangeeth
- P2P Measurement. For reasons explained in the previous
project description, load in a P2P network may be highly unbalanced.
Theoreticians predict, in fact, that the worst-case load imbalance
in the Nash equilibrium for such a network can be quite high.
Place a variety of P2P file serving peers on the web. Measure the
loads placed on them, and determine the extent of the load imbalance
in real networks.
The flipside of this study involves acting as a client to measure
the properties of other peers. Adopt TCP/IP-specific hacks to
determine, remotely, as many of the following metrics as you can for
Kazaa/Freenet or Gnutella networks: node lifetime, number of files
served, amount of disk space reserved for files, the min, max, mean
and median sizes of files served by file type, content of files,
popularity distribution of file requests, popularity distribution of
files offered, bottleneck bandwidth to a given node, load, load
variance over time.
- P2P Indexing and Search Engine. Search engines require
large amounts of bandwidth to index the web, large amounts of storage
(both disk and memory) to store the built index, and large amounts of
processing power to run the queries. The minimum hardware cost to
launch a search engine is, consequently, quite high. However, the
aggreage hosts that make up a P2P system provide large amounts of
Investigate a distributed web crawler that uses a structured P2P
system to crawl the web. Construct a distributed index construction
and partitioning scheme such that only a portion of the index is kept
at each node. Route queries to the right set of clients to cover the
full index. Build and measure the performance of such a system.