Geographic distributed hash table (DHT) protocols assume that the set of (key, value) pairs, called indexes, should be distributed among nodes. In geographic DHT protocols, the overhead of index redistribution due to node mobility may be high enough to impact the normal lookup operation if each node contains a large number of indexes. In our previous work, we proposed an efficient lookup protocol, called Double Indirect Access (DIA), that dispenses with index redistribution to improve lookup performance. We also evaluated the performance of DIA by using our own simulator which could show only limited simulation results with the assumptions that all nodes are connected and the packets are transferred instantly without delay. In this paper, we implement DIA into the packet-level simulator ns2 in order to evaluate how DIA is affected by the underlying unstable routing in MANET. The metrics of the effectiveness are considered lookup success rate and bandwidth consumption, and the simulation results show that DIA performs better than a conventional geographic DHT protocol.

The rapid increase in the usage of mobile devices and the development of wireless technology bring to the needs of service lookup (i.e. discovery) methods in mobile networks. If a geographical distributed hash table (DHT) is directly applied to a location-aware mobile ad hoc network, the key redistribution overhead could be severe. To reduce the key redistribution overhead, we propose a novel peer-to-peer lookup protocol, two-phase geographical distributed hash table. The proposed protocol causes the home consistency problem because it uses two DHTs in tandem: we also provide a solution to the problem so that a query for a key can be routed correctly to the node which is currently responsible for the key.

With a large number of internal disks and the rapid growth of disk capacity, storage systems become more susceptible to double disk failures. Thus, the need for such reliable storage systems as RAID6 is expected to gain in importance. However RAID6 architectures such as RM2, P+Q, EVEN-ODD, and DATUM traditionally suffer from a low write I/O performance caused by updating two distinctive parity data associated with user data. To overcome such a low write I/O performance, we propose an enhanced RM2 architecture which combines RM2, one of the well-known RAID6 architectures, with a Lazy Parity Update (LPU) technique. Extensive performance evaluations reveal that the write I/O performance of the proposed architecture is about two times higher than that of RM2 under various I/O workloads with little degradation in reliability.

Under the condition that the communication time is relatively shorter than the computation time for a given task, the task duplication-based scheduling (TDS) algorithm proposed by S. Darbha and D.P. Agrawal (1998) generates an optimal schedule. In this paper, we propose an extended TDS algorithm whose optimality condition is less restricted and where the length of the generated schedule is shorter than the original TDS algorithm.

Fibre channel SAN (storage area network) is considered to be a promising solution to address storage problems caused by the sheer volume of data and their management. To adopt this new storage environment, we design and implement a high performance fibre channel network driver for SAN-attached RAID controllers in a real-time operating system. We describe the architecture of the fibre channel driver which consists of two modes; a target mode and an initiator mode. An exception handling mechanism for enduring a disk failure is also given. Lastly, we measured the performance of the fibre channel driver. Testing results reveal a moderately successful performance of the fibre channel driver.

The task scheduling problem in distributed memory machines is to allocate the tasks of an application into processors in order to minimize the total execution time. This is known as an NP-complete problem. Under the condition where the communication time is relatively shorter than the computation time for every task, the task duplication based scheduling (TDS) algorithm proposed by Darbha and Agrawal (1998) generates an optimal schedule. We propose an extended TDS algorithm whose optimality condition is less restricted than the TDS algorithm. Given a DAG where the condition is met, our algorithm has the time complexity of O(|V|/sup 2/d/sup 2/) where |V| represents the number of tasks, and d represents the maximum degree of tasks.

There is a growing demand in high reliability beyond what current RAID can provide and there are various levels of user demand for data reliability. An efficient data placement scheme called RM2 has been proposed in [11], which makes a disk array system tolerable against double disk failures. In this paper, we consider how to choose an optimal striping unit for RM2 particularly when no workload information is available except read/write ratio. A disk array simulator for RM2 has been developed for experimental works. It is shown that RM2 has an optimal striping unit of two and half tracks in the case of disk read operations, and one third of a single track if any disk write operations are involved. Key words : data placement, disk array, performance, reliability, striping 1 Introduction In the past few years, the performance of processors has been growing steadily, doubling approximately every two years [6], and with the advance of parallel processing technology, the processi...

In this paper, we deal with the data/parity placement problem which is described as follows: how to place data and parity evenly across disks in order to tolerate two disk failures, given the number of disks N and the redundancy rate p which represents the amount of disk spaces to store parity information. To begin with, we transform the data/parity placement problem into the problem of constructing an N/spl times/N matrix such that the matrix will correspond to a solution to the problem. The method to construct a matrix has been proposed and we have shown how our method works through several illustrative examples. It is also shown that any matrix constructed by our proposed method can be mapped into a solution to the placement problem if a certain condition holds between N and p where N is the number of disks and p is a redundancy rate.

This paper presents an efficient algorithm for network partitioning problem, which improves Fiduccia and Mattheyses' (F-M's) algorithm (1982). We have noticed that the main problem of F-M's algorithm is that the cell move operation is largely influenced by the balancing constraint. In order to handle this kind of inherent limitation in F-M's algorithm, a cost function is adopted which reflects balance degree of a partition as well as its cutset size. The weighting factor R is introduced in the cost function to determine the relative importance of the two factors: cutset size and balance degree. Using this cost function, we propose an iterative improvement algorithm which has the time complexity of O(b(m+c/sup 2/)), where b is the number of blocks, m is the size of network, and c is the number of cells. It is proven that the proposed algorithm guarantees to find a balanced partition if the value of R satisfies a certain condition. Experimental results show that the proposed algorithm outperforms F-M's algorithm in most cases.>