Elastic Time Computation in QoS-Driven Hypermedia Presentations

The development of hypermedia/multimedia systems requires the implementation of an element, usually known as formatter, which is in charge of receiving the specification of a document and controlling its presentation. In order to orchestrate the presentation, formatters should build a presentation plan that will contain the scheduling time for each document object and the inter-object synchronization information, including those whose time of occurrence cannot be predicted, like relationships coming from user interaction. Besides orienting the presentation scheduling, the plan will guide prefetching, reservation and adaptation mechanisms in charge of maintaining the presentation quality of service. Adjustment in the duration of media objects is one of the most important adaptation techniques in order to maintain spatio-temporal relationships specified in a hypermedia document. Elastic time computation accomplishes this goal by stretching and shrinking the ideal duration of media objects.

This paper presents new elastic time algorithms for adjusting the hypermedia document presentation in order to avoid temporal inconsistencies. The algorithms explore the flexibility offered by some hypermedia models in the definition of media object durations, choosing objects to be stretched or shrunk in order to obtain the best possible quality of presentation. Our proposals are based on the out-of-kilter and the cost-scaling methods for minimum cost flow problems on temporal graphs. An aggregation procedure enhances the basic algorithm offering more flexibility in modeling real-life situations in comparison with other previous work based on linear programming.