Replica Management for Self-Organizing Networks in the Context of Wireless Ad-Hoc Networks
From GRK-Wiki
Wireless mesh networks (WMNs) capable of sensing and transferring data are the natural choice for IT support in the disaster management. WMNs exhibit self-organization, are inexpensive, easy to install and independent from existing infrastructures.
In some WMN scenarios network applications require that selected data is available in the WN for the desired time in order to the system to reliably fulfil its purpose. Data which a WMN shall reliably store are for example states of services used for implementing redundancy at the service level or distress calls waiting to be delivered.
There exists a not negligible possibility, that in WNs some nodes will stop working or will become unreachable. A reason can be an empty battery, a rapid drop of the link quality, a sabotage (nodes are usually unattended) or finally a disaster. When a node permanently fails (crashes) its data is gone as well. Additionally nodes are also routers. A failure of a node may cause network partitioning. In disaster scenarios where a whole group of nodes may crash simultaneously, network partitioning becomes even more probable. Stored data is unreachable between the partitions.
These observations show how node failures lower the availability of data stored in wireless networks.
Replication is a well known solution to increase data availability but it must not exhaust wireless network’s limited resources.
The key considerations are the number of copies (replicas), their placement in the network (on which nodes replicas shall be stored) and methods for efficient distributing and discovering the replicas.
The number of data copies is restricted by the nodes capacity. It is usually not possible to set replicas of all replicated data on every node. The replication factor will depend on the available memory, network’s size and application requirements.
At first, the same replication factor for all replicated data will be assumed. Its value will be derived from the maximum amount of data objects volume which the network is able replicate.
For the given replication factor the placement of replicas is critical. Appropriate placement must be reached. Optimal is distributing replicas in a way that after any failure they will cover the maximum possible number of partitions. This can be solved by graph analysis.
The state of the network after the crash depends on the characteristics of the failure itself and on the topology of the original network. In my model the location of a crash is not known, only the shape and size of the area where all nodes fail are given. These parameters are corresponding to the usual damages caused by various disasters (e.g. fire, flood).
Some of the WMN used in disaster management will reassemble user-initiated wireless networks. Their topologies are much more diversified than topologies of uniform-random graphs. The position of the node in the network is then meaningful and determines how valuable for the replication a node is.
The distributed algorithm evaluating each node’s importance for the replication will only approximate its position in the network’s topology. This can be done with a probabilistic protocol. A method for finding data (at least one replica of specified data) must give very high guarantee of successful search in case that the data is reachable. Data availability can be measured as the percentage of resolved data requests. The costs of distributing and finding data objects can be expressed in the total amount of transferred data. These metrics can be used for evaluation of the proposed methods.
In my research I want to find the optimal replica placement which will be used as a reference in future evaluation. I will examine the impact of different crash models on the graph’s connectivity by simulation. I will try to identify and characterize nodes which after a group failure are more likely to stay connected to big network components.
Next I will observe the relation between the number and placement of replicas (both random and optimal) and the data availability for the given network and failure model.
Further work shall result in a replica distribution protocol, where data copies will be efficiently placed on appropriate nodes. Also the method to efficiently find the desired data must be developed.
Other open topics are adapting of replication factor to different availability requirements and sudden increase of data requests (flash crowds).
The aspiration of my research is to provide a middleware for reliable data storage in unreliable networks in the context of disaster management.
