Student project suggestions

  Contact to Eiko Yoneki (eiko.yoneki@cl.cam.ac.uk)

The task is adding mobility simultation to JNS. I worked on the preliminary idea that is adding a thread within the dynamic scheduler, with breaking and establishing links depending on configuration information. Pursue this idea further or go for the challenge of a new design. An important part of this project is understanding mobility patterns and design rich mobility simulation, so that the simulation result will be more valuable.   

A candidate of demo applications will be a simple group communication system over mobile ad-hoc network,  and existing multicast protocol implementations can be used.

 Project 2: Reliability with probabilistic protocol in peer-to-peer networks

Reliable point-to-point communication is usually achieved by applying TCP. In messaging middleware with asynchronous publish/subscribe paradigm, messages may be sent without generating a reply, and they may be processed hours after having been sent. The communicating parties do not handle how messages are transmitted and when they are processed. Thus, the messaging system must provide guarantees. It is not sufficient to know that a message has reached the messaging system that sits between the message producers and consumers. It is necessary to guarantee that the messages will not be lost due to failure of that messaging system. Messaging systems need to provide various guarantees regarding reliability and fault tolerance ranging from best-effort to guaranteed and timely.

In a centralized model of messaging system, the server persists the messages in a central database; since server manages the communication between all clients, it usually implements guaranteed message delivery. Such a central database is not readily available in a mobile ad-hoc network environments, as the availability of any one node at all times is not reliable. In mobile ad-hoc networks, there are several multicast protocols, and they are good candidates to support messaging systems. One approach to provide reliability to those messaging systems is using probabilistic protocol, "gossiping algorithm".  Probabilistic protocols are protocols that guarantee delivery with a certain probability. Although not as safe as guaranteed protocol, the probabilistic protocols typically have less restrictive assumptions and constraints associated and reduced overhead, thus making them in many cases the better choice for mobile ad-hoc networks.

1.     Anonymous Gossip : Gossip is a technique where nodes share the data they process with other nearby nodes, such that all nodes share a consistent view of what has been communicated. A general gossip based reliable multicast involves two phases: an unreliable multicast mechanism is used to multicast the message, and then the gossip phase is initiated, in which gossip is used to recover any lost messages from other nodes that have received them. A gossip message is sent by nodes wanting to gossip after a multicast has finished. Each node randomly selects one of its neighbours and sends a gossip message to it. If the receiver node is a member of the multicast group of sending, the node will randomly decide whether to accept the message or to propagate it. In order to propagate a gossip message, a node will randomly select one of its neighbours and send the gossip message to it. The accepting node will unicast a gossip reply back to the sending node that contains enough information to allow the two nodes to exchange the messages they lack.

2.     Route Driven Gossip : It uses a pure gossip scheme, which gossips uniformly about messages, negative acknowledgements, and membership information without requiring an underlying multicast primitive. It takes into consideration parameters of the network. It does not require a multicast primitive at the network layer and can be deployed on any basic, virtually unmodified, on-demand routing protocol.

 Project 3: Event Aggregation and Correlation

Many applications require the event system (publish/subscribe system) to buffer and/or count events then signal them as required. For example, in financial applications, a trader needs to know when the exchange rate of pound against US dollor reaches its peak; such an event may be expressed as "The rate increased 10 times over the last week and dropped 3 times by the end of this week". You can create a composite event language or use the one created in Opera group. The event composition language is capable to specify "A without B" or "A followed by B". The project aims to develop a composite event engine with aggregation and correlation functionalities including implementation in Java. A composite event language can be designed on XML base such as extending XPath or XQuery.

 Project 4: Hierarchical Bloom Filters

Bloom filters are compact data structures for probabilistic representation of a set in order to support membership queries. Each filter provides a constant-space approximate representation of the contents of a set. Errors between the actual set and the Bloom filter representation are always of the form of false positives to inclusion tests. A Bloom filter is a bit vector, and items are inserted by setting the bits corresponding to a number of independent hash functions.

Consider a set A = {a_1, a_2,...a_n} of n elements. Bloom filters describe membership information of A using a bit vector V of length m. For this, k hash functions, h_1, h_2,...h_k with h_i: X-> {1...m}, are used. Filters can be made incrementally as new elements are added to a set, the corresponding positions are computed through the hash functions and bits are set in the filter.

Bloom filters apply better to data classified and represented by scalars. This project aims to create Bloom filter representation for encoding hierarchical data. There are some efforts on Attenuated Bloom Filter, and  you can use it as base or create your own design.

 Project 5: Mobile Device/Web based Remote Controller on Data Repository