Memory Allocation in Information Storage Networks

Jiang, Anxiao (Andrew) and Bruck, Jehoshua (2002) Memory Allocation in Information Storage Networks. Technical Report. California Institute of Technology. [CaltechPARADISE:2002.ETR048]

Full text available as:

	Postscript - Requires a viewer, such as GhostView
	PDF (Adobe PDF (1.8MB)) - Requires Adobe Acrobat Reader or other PDF viewer.

Abstract

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.

EPrint Type:	Monograph (Technical Report)
Additional Information:	[Alternate URL: http://www.paradise.caltech.edu/papers/ETR048.ps]
Subjects:	All Records
ID Code:	63
Deposited By:	Jehoshua Bruck
Deposited On:	09 December 2002
Record Number:	CaltechPARADISE:2002.ETR048
Official Persistent URL:	http://resolver.caltech.edu/CaltechPARADISE:2002.ETR048
Usage Policy:	You are granted permission for individual, educational, research and non-commercial reproduction, distribution, display and performance of this work in any format.

Archive Staff Only: edit this record