A new self-limiting epidemic service for ad hoc networks

Contact: Alaeddine Elfawal

We define the self-limiting epidemic service as a broadcast dissemination service for short messages in ad-hoc environments, that is limited to a local scope around each source. A typical application is chatting or a bulletin board among users in a traffic jam, in a railway hall, on a campus, or, in contrast, along a desert highway. In all these cases, the application is broadcast; if there would be no limits in network capacity, node storage or node processing, then an epidemic or flooding mechanism would be thinkable. However it may not be desirable, both from user and capacity viewpoints, to reach all users that can be reached by epidemic forwarding (on a busy hour this may be users spanning hundreds of kilometers along highways).

Our goal is to support a self-limiting service across a wide range of conditions (dense or sparse, connected or not). The scope limit should adapt to the density of node and number of active of users. In a dense environment with 100% active users (users chatting in traffic jam, crowd on campus), the information generated by one user would remain in close vicinity, perhaps reaching order of 100 nodes. In a similar environment but with only a small fraction of active users (i.e. few users generate fresh information, but many relay), the spread could be much larger in kilometers. Note that in these dense cases, the problem is less a possible lack of connectivity than congestion and information overflow. At the other end of the spectrum, in a sparse environment (desert highway, or area with very small penetration of the system) the service should have a much wider spread. Last, transitions from a dense to a sparse environment may occur without user control, so we would like the service to smoothly adapt to such changes.

We propose a system design with the following elements: (1) manipulation of TTL by adaptive aging mechanisms; (2) control of forwarding factor by self-inhibition and inter-inhibition and (3) control of rate of injection by sources.

As a typical self-limiting epidemic service we have developed in the past couple of months in Java a Chat application. The implementation is designed to work independently of the OSs and the wireless cards. But it still need to manually configure the card before using it.

  • The current implementation is standalone. We wish to integrate it in the Haggle architecture (http://www.cl.cam.ac.uk/~ph315/publications/haggle-wons06-editforxtoff.pdf) developed in Java. For this purpose we are searching a MSc student interested in software development in wireless networks. The candidate is expected to have good background in networking and Java language programming.

Benefits: Exposure to an exciting project, jointly with Thomson, Cambridge University and other partners in Haggle (http://www.haggleproject.org)

Domain: Protocol design and implementation