Bachelor thesis: Peer to peer networks

Network Coding in
random networks
Contact Christian
Schindelhauer/Peter Mahlmann
By the use of special
encoding techniques
(socalled network coding) data can be broadcasted in a very
efficient, fast and robust way. This technique is used to distribute
large files such as music files, video
files, and software packages by peertopeer networks.
In this bachelor
thesis the student implements a download system which combines a random
network with a random linear network coding. This work extends an
existing random Java based peertopeernetwork.

Bachelor thesis: Online algorithms 
Online
exploration and online Routing: Visualization of JITE (Just in
time
multiple message online routing)
Contact Christian
Schindelhauer/Stefan Rührup
We consider the problem
of routing a message in a mesh network with faulty nodes. The number
and positions of faulty nodes is unknown. It is known that a flooding
strategy like expanding ring search can route a message linear in the
minimum number of steps h while it causes a traffic (i.e. the total number of messages) of O(h^{2}).
For optimizing traffic a singlepath strategy is optimal producing
traffic O(h+p), where p is the number of border nodes neighbored to
faulty nodes. The JITE protocol is a deterministic multipath online
routing algorithm that delivers a message within O(h) steps causing
traffic O((h+p) log^{3}h).
In this bachelor thesis the student implements a
Java applet that presents the JITEalgorithm and other algorithms. 
Bachelor Thesis
Adhocnetworks:

Efficiency and
Fairness in the medium access layer (MAC)
Contact: Christian Schindelhauer
Mobile adhocnetworks
are distributed selforganizing wireless communications networks
without central
control. The frequency band available for such networks is limited and
concurrent systems cannot distinguish other networks from static noise.
If network protocols simply ignore this fact and increase signal
strength then all eventually no communication is possible. So, it is
advisable to back off like the AIMDstrategy within TCP.
In this bachelor thises
the student examines
distributed
probabilistic procedures according to their ability to share the
transmission medium.
Using simulation models the student investigates fairness and
efficiency, i.e. bandwidth utilization.

Topics
for Master Theses
also refer to current research. Topics cover the following areas.
 Computational complexity
 Distributed algorithms
 Peer to peer networks
 Sensor networks
 Adhocnetworks
 Online algorithms

Master Thesis: Distributed Algorithms

Distributed data
aggregation in the Push and Pull model
Contact: Christian
Schindelhauer/Peter Mahlmann
The following game describes that
Random call model. In each round each player selects a random
communication partner. If the information is transmitted from the
calling to the callee, this transfer is called a "push". If the callee
transfers an information to the caller this operaiton is called "pull".
Now each player i has a
number xi
. If player i and j
communicate, then they adapt their values and receive (xi+xj)/2 as new value.
In this master thesis the student investigates the question how quickly
these variables converge against the average value? Do push and pull
behave differently (as being observed in the disrete case)?

Master thesis: Peer to peer networks

The mixing time of
coincidental Peer to Peer networks
Contact: Christian
Schindelhauer/Peter Mahlmann
Many networks, like for example
Gnutella, have no central structures or hierarchies. Thus they are
nearly invulnerable and indestructible. Further improvements are
possible if Peers exchange regularly neighbors. A possibility is the
Plush operation (see
illustration).
One
can prove, the Plush (also known as Push&Pull) always produces a
uniform random graph. However, the speed of convergence is an open
problem.
A
goal of this master thesis is to enhance our knowledge on this process.
This can be done by empirical experiments of via
rigorous analysis of the underlying Markov. 
Master thesis: Sensor networks 
Energy efficient
protocols for sensor networks
Contact: Christian
Schindelhauer
Wireless sensor networks have become a very important research subject
due to their potential of providing diverse services to numerous
applications. In Paderborn we have developed a protocol called 1QK,
enabling an energy efficient wireless multihop sensor network. It
collects sensor data from sensor nodes and to send application data to
sensor nodes. Due to many restrictions concerning hardware and
software, both, the use of energy efficient components and the development of new
protocols and architectures are necessary to satisfy all conditions.
Moreover the cost aspect in our application has to be mentioned as an
extra critical point, since the industry plans to produce millions of
these sensor nodes.
In its latest version 1QK uses only 128 Bytes RAM (1Q = 1 quarter Kilobyte) and utilizes several channels.
This is the result of a preceding master thesis and a bachelor thesi
As the next step this protocol may be improved and experimental studies
on an implementation. 
Master thesis: Ad hoc networks

Analysis
and test of a mobile Adhocnetwork
Contact: Christian Schindelhauer
Adhocnetworks are wireless networks without central control and
control. They connect laptop with each other and with the Internet.
PAMANET (the Paderborn Mobile Ad hoc NETwork) has been developed in
cooperation with the research groups of Franz Rammig and Stefan
Böttcher within a
students' project group. The main advantage of PAMANET is its
scalability, i.e. it can connect arbitrarily many network nodes.
A goal of this master thesis is the theoretical
analysis of PAMANET and/or the execution and evaluation of field tests
with a large number network nodes (> 100). This master thesis uses
the results of a preceding students' project group and a preceding
bachelor thesis.

Master thesis: Computational complexity

Expected hard problems
Contact: Christian
Schindelhauer
Leonid Levin introduced the theory of AverageNPcompeletenes. In
a nutshell this theory says, that if an AverageNPcomplete problem can
be solved in average polynomial time, then all NP problems can be
solved in polynomial time. For this he considered problem and
probability distribution as socalled distributional problem.
Furthermore, he used a weaker notion than the expectation measure,
which bounds the expectation of a polynomial root of the running time.
The reason is that the expectation measure preserves simulation
properties.
The goal of this master thesis is to revisit the reasons to choose this
weaker (now called Levin's) measure. Is it possible to define
AverageNPcompleteness based on the expectation? And if not, why?

Themen für Dissertationen
Auf
Anfrage. Zu besetzende Stellen werde hier veröffentlicht. Im
Moment sind keine Stellen zu besetzen.

Studenten
 BachelorStudenten
 Thomas Janson (current)
 Martin Tofall (2005)
 MasterStudenten
 Birgitta Weber (1999)
 Kerstin Voß (2005)  Diplomarbeit
 Markus Scherschanski (2005), PeerNearDiplomarbeit
 Inés Bebea (current)
 Maria Ana Ruiz Cañamero (current)
 Arne Vater (current)
 Promotionsstudenten
 Klaus Volbert (2005)
 Stefan Rührup (current)
 Peter Mahlmann (current)
