One-time data delivery for interactive visualization applications

Databases for interactive visualization applications are often far too large to be stored and managed in main memory by most rendering machines. However, with spatial decomposition, only a relatively small but time varying subset of the database is needed for generating the images to be displayed at any one time. This motivates and enables the development of the UCLA Virtual World Data Server which, similar to existing video-on-demand servers, stores huge databases on disk and continuously delivers the required data to the client machines. In order to provide the desired level of user perceived quality, the system has to continuously "predict" what data may be needed by the applications, have it requested in advance, and employ admission control to reserve adequate system resources to guarantee that the data will be delivered on-time. The main focus of this dissertation is on how to provide on-time data delivery guarantees for interactive visualization applications and, at the same time, achieve the highest resource utilization possible.;In this dissertation, we first consider the scenario that the data has to be sent over one transport resource, e.g., sending data across a single network link or reading data from disk to main memory. We describe a two-level framework that allows us to separate the application and resource specific aspects of the problems, so that only one scheduling and admission control solution is needed for each type of application regardless of the type of transport resource used. Based on the two-level framework, we explore the applicability of existing scheduling and admission control techniques (designed for video-playback applications) to interactive visualization applications. Due to the imperfect request prediction arising from user control over navigation in interactive visualization applications, these existing techniques do not produce satisfactory results. Therefore, we propose a new approach that employs the idea of per-session traffic shaping. Our empirical results show that, by carefully selecting the system parameters, this approach can provide guaranteed on-time data delivery for interactive visualization applications and achieve up to 80% effective resource utilization. We also propose two schemes to extend our solution for single transport resource systems to provide end-to-end guaranteed delay bound in systems with multiple transport resources in tandem.