Jiang, Anxiao (Andrew) and Bruck, Jehoshua (2002) Memory Allocation in Information Storage Networks. California Institute of Technology . (Unpublished) http://resolver.caltech.edu/CaltechPARADISE:2002.ETR048
See Usage Policy.
PDF (Adobe PDF (1.8MB))
See Usage Policy.
Use this Persistent URL to link to this item: http://resolver.caltech.edu/CaltechPARADISE:2002.ETR048
We propose a file storage scheme which bounds the file-retrieving delays in a hetrerogeneous information network, under both fault-free and faulty circumstances. The scheme combines coding with storage for better performance. We study the memory allocation problem for the scheme, which is to decide how much data to store on each node, with the objective of minimizing the total amount of data stored in the network. This problem is NP-hard for general networks. We present three polynomial-time algorithms which solve the memory allocation problem for tree networks. The first two algorithms are for tree networks with and without upper bounds on nodes' memory sizes respectively. The third algorithm finds, among all the optimal solutions for the tree network, the solution that minimizes the greatest memory size of single nodes. By combining these memory allocation algorithms with known data-interleaving techniques, a complete solution to realize the file storage scheme in tree networks is established.
|Item Type:||Report or Paper (Technical Report)|
|Group:||Parallel and Distributed Systems Group|
|Usage Policy:||You are granted permission for individual, educational, research and non-commercial reproduction, distribution, display and performance of this work in any format.|
|Deposited By:||Imported from CaltechPARADISE|
|Deposited On:||09 Dec 2002|
|Last Modified:||26 Dec 2012 13:53|
Repository Staff Only: item control page