|Bachelor thesis: Peer to peer networks
||Network Coding in
By the use of special
(so-called 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 peer-to-peer 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 peer-to-peer-network.
|Bachelor thesis: On-line algorithms
exploration and on-line Routing: Visualization of JITE (Just in
multiple message on-line routing)
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(h2).
For optimizing traffic a single-path 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 multi-path online
routing algorithm that delivers a message within O(h) steps causing
traffic O((h+p) log3h).
In this bachelor thesis the student implements a
Java applet that presents the JITE-algorithm and other algorithms.
Fairness in the medium access layer (MAC)
Contact: Christian Schindelhauer
are distributed self-organizing wireless communications networks
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 AIMD-strategy within TCP.
In this bachelor thises
the student examines
probabilistic procedures according to their ability to share the
Using simulation models the student investigates fairness and
efficiency, i.e. bandwidth utilization.
for Master Theses
also refer to current research. Topics cover the following areas.
- Computational complexity
- Distributed algorithms
- Peer to peer networks
- Sensor networks
- On-line algorithms
|Master Thesis: Distributed Algorithms
aggregation in the Push and Pull model
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
. 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 ton Peer networks
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
can prove, the Plush (also known as Push&Pull) always produces a
uniform random graph. However, the speed of convergence is an open
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
protocols for sensor networks
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 multi-hop 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
and test of a mobile Ad-hoc-network
Contact: Christian Schindelhauer
Ad-hoc-networks 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
|Master thesis: Computational complexity
|Expected hard problems
Leonid Levin introduced the theory of Average-NP-compeletenes. In
a nutshell this theory says, that if an Average-NP-complete 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 so-called 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
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
Average-NP-completeness based on the expectation? And if not, why?
for Phd Theses
Please contact me.
If there are open positions for Phd students in our research group this
information will be stated here.
and past students
- Bachelor students
- Nicolas Heine (current)
- Thomas Janson (current)
- Martin Tofall (2005)
- Master students
- Birgitta Weber (1999)
- Kerstin Voß (2005) - master
- Markus Scherschanski (2005) - PeerNear-master thesis
- Inés Bebea (current)
- Maria Ana Ruiz Cañamero (current)
- Arne Vater (current)
- Phd students
- Klaus Volbert (2005)
- Stefan Rührup (current)
- Peter Mahlmann (current)