ITR/SY: Algorithms for Data Storage and Movement

University Of Maryland, College Park, College Park MD

Investigators

Abstract

The central focus of this proposal is the development of efficient algorithms for the storage and movement of data. Specifically, we are interested in algorithms that impact the performance of large multimedia data storage systems. In algorithmic terms, some of the principal challenges that arise in the context of multimedia data storage are: (a) deciding how many copies of each data item need to be stored, (b) determining the exact layout of data on a set of servers, (c) dealing with changing workloads and dynamic data access patterns. These related challenges require the development of efficient algorithms for optimizing data layout to maximize client satisfaction, monitoring the performance of data storage systems and scheduling the movement of large amounts of data. Futhermore, what makes the issues that we consider even more significant is the fact that data storage and movement issues also arise within publicly share networks such as the Internet where the bandwidth can be dynamic and highly variable, and can result in a poor choice of paths chosen to transfer data in the network. One way to address this issue is to route data through specific holding points. By doing this we are able to increase throughput and decrease completion times by an order of magnitude to transfer data from several sources to a single destination. Algorithms related to this problem have been developed by us and are being tested with the Bistro framework, which is a framework for providing a data upload service such as one required by IRS for tax submission purposes. Our data movement algorithms are being used to schedule the transfer of data from many different locations to a final destination server. While some specific instances of the individual problems have been considered earlier, there is no work dealing comprehensively with the range of issues that we focus on.