Skype Operator
The Three mobile phone company sells phones with a built-in Skype client.
This client can make Skype-to-Skype calls for free, and it can make
Skypeout calls to international numbers at the normal Skypeout rate.
However, Three blocks Skypeout calls to domestic numbers.
This project will involve programming a Skype
client that waits for an incoming call, listens to the caller, works out
what number they want to call, places a Skypeout call to that number,
and hooks it all together as a conference call. This will get around Three's
restriction.
This project will involve scripting Skype, through the Skype API. The best
way to do this is with Python and COM. This project is only suitable
for students with some experience of Windows programming.
-
The virtual economy of P2P [ppt]
TCP can be seen as a virtual economy, in which dropped packets play the
role of prices, and Jacobson's congestion control algorithm plays the part
of a rational utility-maximizing economic agent. The outcome is that TCP
selects transmission rates which solve a network-wide social welfare
maximization problem.
I believe that we can view P2P networks in the same way. The downloader
pays, the network charges, and the uploader also charges. It may be that
economic insights can lead us to algorithms which make more intelligent
choices about peering and throughput.
This project will involve inventing and tweaking novel algorithms for
congestion control and peer selection. It will be based on
simulation (probably in ns2, as well as
quick-and-dirty custom-written simulations) and mathematical modelling.
You should understand the material I teach about utility maximization
and drift models, and you should be an inventive algorithm designer.
-
Blocking/tokens versus signalling for congestion control
Some data networks prevent packet loss by holding back data at each
step until the destination has space free. (This is how road traffic
works.) Eventually, a backlog builds up all the way to the data
source, which stops sending until the backlog clears. The disadvantage of
this scheme is that it creates congestion on a path all the way from
the original congestion point right back to the source, and innocent
cross-flows may suffer. The advantage is that it guarantees zero loss.
Such a scheme might be improved by allowing the congested point to
communicate back to the source, to tell it to back off (like TCP).
The project will involve writing a simulator to experiment with toy
models of congestion control using different mixtures of blocking and
signalling. It will require you to show creativity in formulating
questions and then testing them.
-
Structure of web pages
A typical modern web page is composed of tens or hundreds of separate
items, often small items (no more than one packet big). Some items
trigger requests for other items. In the best case the main html
document will trigger requests for all the other items which may then
be downloaded in parallel. In the worst case the web page uses
badly-written javascript which blocks while it is waiting for each
download to complete, and then the items must all be downloaded
sequentially. The set of dependencies can be uncovered by repeatedly
loading a web page, and blocking different sets of replies. I have done
this manually for gmail.com.
This project will be a data-gathering exercise to find out the typical
size and structure of a web page. It will involve automating the
process of discovering the structure of a web page. This will involve
scripting a browser (e.g. Internet Explorer) and writing a simple http
proxy. I recommend programming in Python or similar. This project
should only be undertaken by a student who has some experience of
programming with sockets.
-
MAC3: Medium Access Coding and Congestion Control
The classic approach to wireless networking is to have a physical
layer that deals with coding and modulation and bitrate selection, a
MAC layer that retransmits packets in the event of contention, and
TCP or similar to control the rate at which packets are injected into
the network. This approach does not deal well with problems like
hidden terminals or exposed terminals.
This project will investigate the idea that contention should be dealt
with by a combination of coding and rate control, i.e. that the
classic MAC layer should be fundamentally changed. For more details on
the proposal, see my slides
from a talk.
The project will involve simulation, analysis, and algorithm design.
This project was completed, and generated interesting answers.
The students investigated a simple slotted-time model. They found that
with about 5% overhead in the coding scheme, it is possible to
build a working congestion control mechanism
for simultaneous wireless transmission.
It does much better than classic MAC-style congestion/contention control
in network settings with more than one receiver.
-
Distributed algorithms for a peer-to-peer interactive whiteboard
I envisage a peer-to-peer interactive whiteboard application. Each
user will be able to write on his/her own device, and the updates will
be propagated to other users who are currently logged in. When a user
goes offline for a while then logs in again, he/she will receive
updates for everything that has been added in the meantime. These
should all be accomplished with minimum latency, and they must
preserve the order in which each participant writes or erases on the
whiteboard, via Lamport clocks.
This project will involve designing and writing an algorithm to
achieve these tasks. The algorithm will be a hybrid of Lamport clocks,
gossip-based broadcast, and BitTorrent-like swarming.
I have a high-level design for the algorithm in
mind, but it needs experimentation and tweaking and refinement. You
may write either a simulation or an actual piece of running code. This
project should only be undertaken by a student who has attended Dr
Karp's course on distributed algorithms.
This project was successfully completed. You can
try it
out yourself. There are still some issues with the robustness of
the network algorithms to packet drops, and with congestion control,
and there is much scope for improvement in the GUI and the data model.
-
Multipath topology problem
If we allow TCP to spread its traffic over multiple routes, we need to
decide which set of routes to allocate to each TCP flow. Simple mathematical
models suggest that all we need is to allocate two routes to each TCP flow,
as long as these two routes are reasonably diverse.
The goal of this project
will be to understand how much diversity of routing is needed. It will involve
using data on Internet topology, and simulating a variety of algorithms for
route allocation, and testing to what extent this set of routes permits
the network to balance its load.
You will have to parse data that other researchers have gathered on Internet
topology, and you will have to write a simulator to test route allocations. Suggested
languages are C++, Python, and Java.
This project has been partially completed.
Some output is shown in
a
talk I gave: look for the slides showing the GEANT network.
The outcome of this project shows us how to evaluate the
effectiveness of a given multipath routing algorithm, but we have not
yet used this to assist us in designing better multipath routing algorithms.
-
QCN simulator and differential equation modelling
QCN is an algorithm for controlling traffic in very high-speed local
area networks, currently being standardized by the IEEE. It is
intended to be the control algorithm for the next generation of
ethernet, and it may end up spreading to the wide area. Our
understanding of QCN is still very limited.
This project will involve
simulating QCN, and testing mathematical models to approximate it. The
QCN simulator will most likely be an adaptation of Mark Handley's fast
C++ simulator. You should be prepared to program in C++, and you
should recall basic A-level mathematics. If you wish, the project may
also involve Matlab or Mathematica.
This project is underway.