Previous [1] [2] [3] [4] [5] [6] [7] [8] [9] [10]

Journal of Inforamtion Science and Engineering, Vol.17 No.3, pp.633-646 (July 2001)

File Allocation Algorithms to Minimize Data Transmission
Time in Distributed Computing Systems*+


Pao-Yuan Chang, Deng-Jyi Chen** and Krishna M. Kavi++

Information Management Department
Ta Hwa Insitute of Technology
Hsinchu, Taiwan 307, R.O.C.
E-mail: pychang@im.thit.edu.tw
**Computer Science and Information Engineering Department
National Chiao Tung University
Hsinchu, Taiwan 300, R.O.C.
E-mail: djchen@csie.nctu.edu.tw
++Department of Electrical and Computer Engineering
University of Alabama in Huntsville
Huntsville, AL 35899, U.S.A.
E-mail: kavi@ebs330.eb.uah.edu

This work addresses a files allocation problem (FAP) in distributed computing systems. This FAP attempts to minimize the expected data transfer time for a specific program that must access several data files from non-perfect computer sites. We assume that communication capacity can be reserved; hence, the data transmission behavior is modeled as a many-to-one multi-commodity flow problem. A new critical-cut method is proposed to solve this reduced multi-commodity flow problem. Based on this method, two algorithms which use branch-and-bound are proposed for this FAP. The proposed algorithms are able to allocate data files having single copies or multiple replicated copies. Simulation results are presented to demonstrate the performance of the algorithms.

Keywords: distributed computing system (DCS), cut, multi-commodity flow, linear programming, data replication, branch and bound

Full Text () Retrieve PDF document (200107_06.pdf)

Received December 3, 1998; revised May 29, 1999; accepted September 7, 1999.
Communicated by Arbee L. P. Chen.
+ The previous version of this paper was published in Proceedings of IEEE International Computer Performance and Dependability Symposium (IPDS), Sep. 406, 96 Urbanna-Champaign, Illinois, U.S.A.