Student project suggestions
Contact
to Eiko Yoneki (eiko.yoneki@cl.cam.ac.uk) Project 1: Add mobility simulation to
Java Network Simulator
The Java Network Simulator is a Java implementation of the ns-2 simulator originally from Berkeley. It is not as complete as ns-2, but it is a lot more accessible to programmers not familiar with Object Tcl. JNS allows developers of networking protocols to simulate their protocols in a controlled environment. The simulator then produces a trace file (same format as NAM trace files) that can be viewed in a network animator such as Javis (Java Visulalizer). Javis is the Java implementation of Nam, the network animator which can show animations of Nam trace files.
JNS is a project originating from University College London. The latest version is available from sourceforge, and this version adds multicasting, multithreading and dynamic scheduling, thus allowing dynamic scheduling of events. In addition, JNS now supports simulation of "real" Java network applications.
The task is adding mobility simulation 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. The most popular and simplest mobility pattern to implement will be "Random Way Point" algorithm. You might extend the concept of mobility such as policy based node mobility to simulate real world environments.
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.
Interest in mobile ad-hoc networks. Some knowledge of Java networking programming, threading, RMI, and multicast.
Project 2: Dynamic Group Creation by K-means Clustering
for Group Communication
K-means clustering generates a
specific number of disjoint, flat (non-hierarchical) clusters, and the K-means algorithm
is used for similarity-based grouping. The goal is to divide the objects into K
clusters such that some metric relative to the centroids of
the clusters is minimized. Various metrics to the centroids that can
be minimized include:
The metric to minimize and
the choice of a distance measure will determine the shape of
the optimum clusters.
The typical operation
of K-means is:
Interest in mobile ad-hoc networks, and clustering algorithms.
Project 3:
Query Processing
for Network (similar idea as the distributed database)
Recent advances in
computing technology have led to
introduce new devices: the wireless, battery powered, smart sensor.
They are used for monitoring and data collection task. The
sensor applications depend on the ability to extract data
from the network. Often, this data consists of summaries (or
aggregations) rather than raw sensor readings. This project
aims to design an aggregation service for such sensor network
environments. An obvious approach for doing this would
be to
apply traditional data-processing techniques and operators from
the database community. See an example below which describes an query
is distributed over the network, and an aggregated
result is sent back to the query dispatcher. You might consider "data flow"
programming approach, or embedded processor in each node. If you want
to challenge, you might design a simple concurrent processor. For the programming languages, any of Java,
ML, and Prolog will be possible depending on the design.
Project Goal:
Design
and implement an ad hoc group communication mechanism such
as sharing the taxi ride to the same destination.
Summary:
The
goal of the
project is designing a simple group communication mechanism over mobile
ad hoc network environments. The group
should be created in temporal manner
after exchanging interests among the devices. It requires a simple gossiping routing to
exchange the interests among devices/nodes. The main challenge
is to create optimal groups among various interests using K-means clustering
algorithm.
Remarks:
Project 4:
Reliability with probabilistic protocol in peer-to-peer
networks
Project Goal:
Design
and implement query
processing mechanism over the network.
Summary:
Remarks:
Good
knowledge on query processing, concurrency control, and
database.
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.
You can implement a simple messaging system by using a multicast protocol in mobile ad-hoc networks before designing the gossip based reliability support. Alternatively, I will provide one, then you can build gossip algorithm on top of that. There is an effort to refine gossiping algorithm to reduce the noise and to improve reliability such as combining gossip-based and semantic-based reliable protocols. The followings are candidate gossip algorithms.
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 5: 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 dollar 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 6: 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.
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 7: Mobile Device/Web based Remote Controller on Data Repository
This application resides in mobile devices such as
PDA or mobile phones that allows to print, fax and e-mail data
(documents, multimedia etc) remotely to the nearest printer or fax machine.
The user can browse through large data repository by looking at only the name of
files, summaries, or full documents. Once selected, data can be forwarded
to any email address or fax machine for full viewing. The remote
controller can be extended to add web access or email access.
You will design a gateway between
different devices and data access components in back-end computers.
Within the gateway, transforming data format is required, and utilizing
XML schema is essential. You can add data transformation components as much
as feasible within the given time. For example, you can implement
voice based summary function, or short digest of multimedia data, if you can.
For example, you can add location based service to
decide, what Kinko's printer to use for printing. In addition, what devices
and what communication protocols are depending on given time and
resources. One would be minimum to show concept proof.
With this application, when you forget your powerpoint files for the presentation away from your office, you can use mobile phone to look through your file repository, then print to Kinko's printer nearby or email to the meeting organizer.
As an extension, you can add an authentication and access control component in the gateway.