Electrical computers and digital processing systems: multicomput – Computer-to-computer data modifying – Compressing/decompressing
Reexamination Certificate
1998-08-21
2003-12-16
Thompson, Marc D. (Department: 2142)
Electrical computers and digital processing systems: multicomput
Computer-to-computer data modifying
Compressing/decompressing
C709S231000, C709S232000, C709S233000
Reexamination Certificate
active
06665732
ABSTRACT:
TECHNICAL FIELD
This invention relates to the scheduling, within multimedia database servers, of resources for storing or transmitting composite multimedia objects that contain various forms of multimedia data such as images, video, and audio.
BACKGROUND OF THE INVENTION
Next generation database systems will need to provide support (for example, identify the storage (memory) and disk or transmission bandwidth requirements) for various forms of multimedia data such as images, video, and audio. These new data types differ from conventional alphanumeric data in their characteristics, and hence require different techniques for their organization and management. A fundamental issue is that digital video and audio streams consist of a sequence of media quanta (for example, video frames and audio samples) which convey meaning only when presented continuously in time. Hence, a multimedia database server needs to provide a guaranteed level of service for accessing such continuous media (CM streams in order to satisfy their pre-specified real-time delivery rates and ensure intra-media continuity. Given the limited amount of resources (for example, memory and disk or transmission bandwidth), it is a challenging problem to design effective resource scheduling algorithms that can provide on-demand support for a large number of concurrent continuous media clients.
An important requirement for multimedia database systems is the ability to dynamically compose new multimedia objects from an existing repository of CM streams. Temporal and spatial primitives specifying the relative timing and output layout of component CM streams provide perhaps the most powerful and natural method of authoring such composite multimedia presentations. Thus, to compose tailored multimedia presentations, a user might define temporal dependencies among multiple CM streams having various length and display bandwidth requirements. For example, a story for the evening news can start out by displaying a high resolution video clip with concurrent background music and narration added after an initial delay. After some time into the story, the video screen is split and a new video clip starts playing on the left half of the screen. After the second video clip ends, the narration stops and the story comes to a conclusion with the display of the first clip and the background music.
In the presence of such composite multimedia objects, a scheduling algorithm must ensure that the inter-media synchronization constraints defined by the temporal relationships among CM components are met. Handling these synchronization constraints requires a task model that is significantly more complex than the models employed in scheduling theory and practice. See, Soumen Chakrabarti and S. Muthukrishnan, “Resource Scheduling for Parallel Database and Scientific Applications”,
Proceedings of the Eighth Annual ACM Symposium on Parallel Algorithms and Architectures
, pages 329-335, Padua, Italy, June 1996; M. R. Garey and R. L. Graham, “Bounds for Multiprocessor Scheduling with Resource Constraints”,
SIAM Journal on Computing
, 4(2):187-200, June 1975; and M. R. Garey, R. L. Graham, D. S. Johnson, and Andrew Chi-Chih Yao, “Resource Constrained Scheduling as Generalized Bin Packing”,
Journal of Combinatorial Theory
(A), 21:257-298, 1976. More specifically, composite multimedia objects essentially correspond to resource-constrained tasks with time-varying resource demands. Resource constraints come from the limited amount of server resources available to satisfy the requirements of CM streams and time-variability stems from the user-defined inter-media synchronization requirements. We believe that this is a task model that has not been previously studied in the context of deterministic scheduling theory. Furthermore, despite the obvious importance of the problem for multimedia database systems, our work appears to be the first systematic study of the problems involved in scheduling multiple composite multimedia objects. We suspect that this may be due to the difficulty of the problems, most of which are non-trivial generalizations of NP-hard optimization problems.
It appears that today's multimedia storage servers offer no clever scheduling support for composite multimedia presentations. The approach typically employed is to reserve server resources based on the maximum (that is, worst-case) resource demand over the duration of a composite presentation. Examples of systems using this worst-case resource reservation method include the Fellini and CineBlitz multimedia storage servers developed at Bell Laboratories and discussed in Cliff Martin, P. S. Narayanan, Banu Özden, Rajeev Rastogi, and Avi Silberschatz, “The Fellini Multimedia Storage Server”,
Multimedia Information Storage and Management
, pages 117-146, (S. M. Chung ed., Kluwer Academic Publishers 1996); Starlight's StarWorks (http://www.starlight.com/); and Oracle's Media Server (http://www.oracle.com/). Conceptually, this approach is equivalent to identifying the resource requirements of the presentation over time with their enclosing Minimum Bounding Rectangle MBR). Although this simplification significantly reduces the complexity of the relevant scheduling problems, it suffers from two major deficiencies.
The volume (that is, resource-time product as in Chakrabarti et al. and in our Minos N. Garofalakis and Yannis E. Ioannidis, “Parallel Query Scheduling and Optimization with Time- and Space-Shared Resources”,
Proceedings of the
23
rd International Conference on Very Large Data Bases
, pages 296-305, Athens, Greece, August 1997. ) in the enclosing MBR can be significantly larger than the actual requirements of the composite object. This can result in wasting large fractions of precious server resources, especially for relatively “sparse” composite objects.
The MBR simplification “hides” the timing structure of individual streams from the scheduler, making it impossible to improve the performance of a schedule through clever use of memory buffers.
A number of conceptual models have been developed for capturing the temporal aspects of multimedia data. They can be roughly classified into three categories, namely: 1) graph-based models (for example, object composition petri nets as in Thomas D. C. Little and Arif Ghafoor, “Synchronization and Storage Models for Multimedia Objects”,
IEEE Journal on Selected Areas in Communications
, 8 (3):413-427, April 1990 and presentation graphs as in Kingsley C. Nwosu, Bhavani Thuraisingham, and P. Bruce Berra, eds.,
Multimedia Database Systems: Design and Implementation Strategies
, Kluwer Academic Publishers, 1996); 2) language-based models (for example, HyTime as in Steven R. Newcomb, Neill A. Kipp, and Victoria T. Newcomb, “The HyTime Hypermedia/Time-based Document Structuring Language”,
Communications of the ACM
, 34 (11), November 1991 and MHEG as in R. Price, “MHEG: An Introduction to the Future International Standard for Hypermedia Object Interchange”,
Proceedings of ACM Multimedia
'93, pages 121-128, Anaheim, Calif., August 1993.), and 3) temporal abstraction models (for example, temporal intervals and relations as in J. F. Allen, “Maintaining Knowledge About Temporal Intervals”,
Communications of the ACM
, 26(11):832-843, November 1983, and Thomas D. C. Little and Arif Ghafoor, “Interval-Based Conceptual Models for Time-Dependent Multimedia Data”,
IEEE Transactions on Knowledge and Data Engineering
, 5(4):551-563, August 1993). Candan et al. present a method based on linear difference constraints for defining flexible inter-media synchronization requirements and show how these constraints can be solved and/or modified to ensure consistency in K. Selcuk Candan, B. Prabhakaran and V. S. Subrahmanian, “Retrieval Schedules Based on Resource Availability and Flexible Presentation Specifications”, Technical Report CS-TR-3616, University of Maryland, College Park, 1996. Thimm et al. describe a feedback-based architecture for adapting a multimedia presentation to the changes in resource availability by modifying the pr
Garofalakis Minos N.
Ioannidis Yannis E.
Ozden Banu
LandOfFree
Method and system for resource scheduling composite... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Method and system for resource scheduling composite..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method and system for resource scheduling composite... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3173711