Dynamic Service Aggregation for Interactive Information Delivery over Networks

National Science Foundation Grant No. NSF NCR-9523958, CISE Networking and Communications Research Program
Principal Investigator: Thomas D.C. Little

Project Summary

Digital audio and video are increasingly common as data that are manipulated in computer and communication systems. To support future interactive information delivery services such as on-demand video, distance learning, and telecommuting, there is a need to balance individual interactivity with the desire to maximize the number of supported sessions. There also exists a requirement to support participants of varying service classes and the dynamics of network loading. Current resource allocation mechanisms for network-based multipoint information delivery are static in nature and cannot support interactivity for each participant. Point-to-point approaches can support interactivity but are inefficient for scaling to a large number of participants. Currently, no techniques have demonstrated the ability to renegotiate and scale service parameters per session in progress as required to adapt to differing terminal equipment characteristics and network congestion.

The DSAP project, sponsored by the National Science Foundation and supported by related grants from Hewlett Packard and EMC Corporation, addresses this problem through the definition of decomposable service groups that permit aggregation of interactivity, terminal characteristics, and levels of service scaling. Interactivity implies the availability of a unique service group. A mechanism is proposed to dynamically reassign elements to service groups based on changing interactivity and session requirements. Such a mechanism will allow the adjustment of service quality based on cost, available resources, or user-equipment characteristics, and will adapt to changing network loading. The proposed approach applies the characteristics of end applications and data storage requirements to the design of a data scaling mechanism.

Specific tasks in this project include (1) formalizing a model for characterizing and aggregating service groups, (2) development of a protocol for dynamic service aggregation, (3) identification of a mapping for application requirements to service groups and network quality of service, (4) the establishment of a network access mechanism to support service degradation and scaling for multiple sessions, and (5) the simulation, implementation, and evaluation using established multipoint applications and multicast protocols.

This material is based upon work supported by the National Science Foundation under Grant No. NCR-9523958. Any opinions, findings, and conclusions or recommendations expressed in this material are those of the author(s) and do not necessarily reflect the views of the National Science Foundation.

Participants

Graduate students: Prithwish Basu, Wang Ke, Rajesh Krishnan, Ashok Narayanan, Naved Khan.

Other collaborators: Azer Bestavros, Boston University; Dinesh Venkatesh, EMC Corporation; Yannis Paschalidis, Boston University.

The proposed research addresses the means to efficiently support point-to-multipoint information delivery applications by providing levels of constrained interaction and quality of service (QoS), and the means to switch among them. These levels are designed to allow flexibility for clients to adapt to interactive or non-interactive service at various levels of service quality, thereby permitting the system to accommodate the largest possible user population without sacrificing interactive functions. The work consists of the development of algorithms for aggregating users actively while a session is in progress. The scheme focuses on supporting a very large customer population, general information dissemination, instantaneous interaction, and active aggregation of sessions via rate adaptation and content insertion.

• Development of a technique for accelerating the content progression of MPEG-1 video streams by in order to facilitate aggregation of temporally skewed streams. This technique is essential for bridging the gap between two streams that can be merged into a single stream. This was achieved by dropping less important ``B'' frames from an MPEG encoded audio/video data stream [Krishnan and Little, 1997].
• Development of a technique for performing service aggregation at the video server using a single storage format for both normal and accelerated content progression rates. This cuts down the disk storage consumption to half [Krishnan and Little, 1997].
• Investigation of algorithms for reclamation of video streams at a video server by clustering them into groups under server overload scenarios [Krishnan et al., 1997].
• Development of a mechanism for conditioning MPEG-1 system streams in order to make them suitable for error resilient network delivery [Basu et al., 1998a].
• Development of a video server prototype for demonstrating dynamic service aggregation using rate-adaptive merging of conditioned MPEG-1 streams in an interactive configuration [Basu et al., 1998a, Narayanan et al., 1997].
• Development of a Java-based software client suitable for interpreting a conditioned MPEG-1 metadata format for recovery from packet errors introduced by network losses or intentional dropouts [Basu et al., 1998a, Narayanan et al., 1997].
• Development of a theoretical framework for clustering of streams for reclaiming network resources during video delivery [Basu et al., 1998b].
• Development of optimal stream clustering algorithms in static situations and their extension to more dynamic scenarios [Basu et al., 1998b].
• Performance analysis of optimal stream clustering algorithms with respect to other heuristic algorithms [Basu et al., 1998b].
• Development of a discrete event simulation tool, vodsim for simulating an interactive VoD system and for studying the performance of various stream clustering algorithms [Basu et al., 1998b].
• Development of optimal algorithms for secondary content insertion (or ad-insertion) for aggregation of digital video streams [Basu et al., 1999].
• Augmentation of the vodsim simulator for handling the discrete staircase-like merging patterns while obeying constraints on the rate of ad insertion [Basu et al., 1999].
• Development of an approach for modeling dynamic service aggregation in an interactive VoD system using Stochastic Dynamic Programming [Basu et al., 2000].
• Investigation of hybrid VoD schemes involving periodic broadcast delivery and on-demand delivery in CATV systems.
• Investigation of variants of the rectilinear Steiner minimum arborescence (RSMA) algorithm for repeated invocation for achieving dynamic aggregation. Performed qualitative studies to estimate the dynamic aggregation. Performed qualitative studies to estimate the relationship between the channel reclamation rate and the frequency of invocation [Basu et al., 2000].
• Development of techniques for estimation of bandwidth requirements in an RSMA-based aggregation system. The results are useful for capacity planning in video servers [Ke et al., 2000].
• Investigation of pricing related issues in VoD systems as a function of several system parameters [Basu and Little, 2000].
• Development of an informal WWW-based poll to gain some indication of user tolerance to pricing of VoD services containing secondary content (advertisements).

Findings:

The encompassed research focuses on the creation of concepts, techniques, and algorithms applied to the project goals. In addition, research prototypes were created to support concepts and facilitation demonstration of research concepts. As such, the research findings consist of new models and techniques to achieve dynamic aggregation of video streams receiving the same content at a video server. Major results of this research are described below.

• A technique for accelerating the content progression of MPEG-1 video streams by in order to facilitate aggregation of temporally skewed streams. This was achieved by dropping less important B frames from the MPEG-encoded video stream [Krishnan and Little, 1997].
• A technique for performing service aggregation at the video server using a single storage format for both normal and accelerated content progression rates [Krishnan and Little, 1997].
• An algorithm, Earliest Maximal Clustering (EMCL) for reclaiming the maximum number of video streams at a video server in a specified window of time by adjusting the content progression rates of streams. EMCL has a time complexity of where is the number of streams at the EMCL has a time complexity of where is the number of streams at the video server [Krishnan et al., 1997].
• Viability of using secondary content insertion as a means of bridging the temporal gap for merging streams under server overload scenarios [Krishnan et al., 1997].
• A mechanism for conditioning MPEG-1 system video streams to make them suitable for error resilient network delivery. Metadata information was added offline to the video streams to make client manipulation straightforward and efficient [Basu et al., 1998a].
• The creation of a video server/client prototype for demonstrating dynamic service aggregation using rate-adaptive merging of video streams in an interactive setup. This involved implementation of the signaling mechanism between the server and the client for switching between Multicast groups. Conditioned MPEG-1 streams were used for network delivery [Basu et al., MMCN 1998, Narayanan et al., 1997].
• A theoretical framework for clustering of video streams - an optimal algorithm (RSMA) was developed for stream clustering in static (snapshot) scenarios, and its extension to more dynamic situations. The algorithm yields the set of content progression rates that each video stream should follow during the merging process. The algorithm has time complexity , and is optimal in the average network bandwidth consumed during the merging period [Basu et al., 1998b].
• Creation of optimal algorithms for secondary content insertion (or ad-insertion) for aggregation of VoD streams. Content insertion was done in a constrained manner for keeping the user experience nominal [Basu et al., 1999].
• The development of a discrete event simulation tool, vodsim for simulating an interactive VoD system. The tool was used for the performance analysis and comparison of the RSMA and other stream clustering algorithms [Basu et al., PDCS 1998], as well as ad insertion algorithms [Basu et al., 1999].
• An approach based on Stochastic Dynamic Programming for modeling An approach based on Stochastic Dynamic Programming for modeling dynamic service aggregation in an interactive VoD system. An event based cost formulation was developed [Basu et al., 2000].
• Techniques for estimation of bandwidth requirements in an RSMA-based aggregation system. The results are useful for capacity planning in video servers [Ke et al., 2000].
• An analytical technique for estimating the relationship between the channel reclamation rate and the frequency of invocation of the RSMA-slide algorithm [Basu et al., 2000].
• An optimization framework for maximization of profit in VoD systems as a function of several system parameters [Basu and Little, 2000].

Training and Development:

Graduate student participants have gained a variety of independent research skills while undertaking literature research, mathematical analysis, simulation, and experimentation as part of the project. In addition, students have been expected to produce regular project reports and oral presentations that ultimately have been refined into conference and journal publications. This experience has proven to be invaluable in developing the students into independent investigators.

The research sponsored under this grant is promoted via the Web and via various open-house-type activities on campus, including support of Pathways, a program designed to encourage young women to pursue careers in science and engineering.

• R. Krishnan and T.D.C. Little, "Service Aggregation Through Rate Adaptation Using a Single Storage Format," Proc. 7th Intl. Workshop on Network and Operating System Support for Digital Audio and Video, St. Louis, MO, May 1997 [pdf].
• R. Krishnan, D. Venkatesh, and T.D.C. Little, A Failure and Overload Tolerance Mechanism for Continuous Media Servers," Proc. ACM Multimedia, Seattle, WA, November 1997 [pdf].
• P. Basu, A. Narayanan, R. Krishnan, and T.D.C. Little, "An Implementation of Dynamic Service Aggregation for Interactive Video Delivery," Proc. SPIE -- Multimedia Computing and Networking, San Jose, CA, January 1998 [pdf].
• P. Basu, R. Krishnan, and T.D.C. Little, "Optimal Stream Clustering Problems in Video-on-Demand," Proc. Parallel and Distributed Computing and Systems, Las Vegas, NV, October 1998 [pdf].
• P. Basu, A. Narayanan, W. Ke, T.D.C. Little, and A. Bestavros, "Optimal Scheduling of Secondary Content for Aggregation in Video-on-Demand Systems,'' Proc. 8th Intl. Conf. on Computer Communications and Networks (ICCCN '99), October 1999 [pdf].
• P. Basu and T.D.C. Little, "Pricing Considerations in Video-on-Demand Systems,'' Proc. 8th ACM Intl. Multimedia Conf. 2000, Los Angeles, CA November 2000 [pdf].
• P. Basu, T.D.C. Little, W. Ke, and R. Krishnan, "Server-Based Aggregation Schemes for Interactive Video-on-Demand, in Handbook of Video Databases: Design and Applications, Borko Furht and Oge Marques, Eds, CRC Press, Boca Raton, FL, 2004, pp. 927-960 [pdf].
• W. Ke, P. Basu, and T.D.C. Little, "Time Domain Modeling of Batching under User Interaction and Dynamic Piggybacking Schemes,'' Proc. SPIE, Multimedia Computing and Networking (MMCN 2002), San Jose, CA, January 2002 [pdf].
• A. Narayanan, P. Basu, and T.D.C. Little, "Rate-Adaptive Merging as a Technique for Efficient Resource Utilization in Video-on-Demand Servers,'' Demonstration, exhibited at the 4th Intl. Conf. on Multimedia Computing and Systems, Ottawa, Canada, June 1997 [pdf].

A variety of software was developed as proof-of-concepts under the grant. As such, its value has been in the demonstration of ideas rather than as deployable implementations. These ideas are described in detail in the listed publications. As appropriate, developed software is available via the aforementioned WWW address. Software products include a proof-of-concept prototype demonstrating stream aggregation, an MPEG-1 stream conditioner, and an interactive VoD simulator.

A proof-of concept prototype was developed to demonstrated the basic concepts related to DSAP. It consists of a video server and a client component, written in Java. The server component accepts requests for titles in a database of movies and initiates streaming them on-demand to the clients. It maintains a list of active users at any point of time, and continually attempts to merge the active video streams so as to yield a decreasing number of independent streams of the same content. This is achieved by manipulating a set of multicast streams with different content progression rates (this is where the clustering/merging algorithms fit in). Once a merge point is reached, the server sends a directive to all clients listening to the tailing stream to start listening on the multicast group of the leading stream. We believe that this concept of ``server-directed channel switch'' is an important one, and can be used extensively in large content delivery systems in the future.

A video clip of the demonstration can be found on the project web site. The software distribution is also available; however, the value of the prototype exists in supporting the research concepts.

We based our video encoding on the MPEG-1 system stream standard (open and available prior to initiating the research program). In order to make the MPEG system stream robust to packet errors and losses, a tool (MPEG conditioner) was developed. The MPEG conditioner essentially parses an existing MPEG-1 stream and reorganizes the components in the stream (called MPEG packets) such that the system layer and the compression layer become correlated, and hence the video frame units can be aligned with packet boundaries. In this repacketization process, special care is taken to adhere to the MPEG-1 Systems standard. Then, each conditioned MPEG file is augmented with a metadata information consisting of the offsets to the video frames. Since this process is performed offline and the results are maintained in a system-compliant format, the server does not need to re-parse the video stream before streaming it. This process also makes error recovery on the clients considerably more straightforward. This conditioner was used to support streaming and merging of MPEG-compressed video in the proof-of-concept prototype. The MPEG-1 Stream Conditioner software distribution is available on our web site.

In order to study the performance of the stream clustering and merging algorithms that form a major component of the research, we developed a VoD simulator called vodsim. All algorithms that were developed during the research were implemented and tested using this simulator. Details about the design of vodsim can be found in [Basu et al., 1998b, Basu et al., 1999]. A modular design approach was taken in order to make it extensible. New clustering algorithms can easily be included into the framework. The Interactive VoD Simulator software distribution is available on our web site.

Internet Dissemination:

http://hulk.bu.edu/projects/dsap/summary.htm. This link includes project summary and links to project publications and other software.

The project contributes to the disciplines associated with computer networking, video servers, and streaming media, as well as to other core scientific and engineering disciplines. These, and other contributions educational or societal goals are described below.

The proposed research addresses the means to efficiently support point-to-multipoint information delivery applications by providing levels of constrained interaction and quality of service (QoS), and the means to switch among them. These levels are designed to allow flexibility for clients to adapt to interactive or non-interactive service at various levels of service quality, thereby permitting the system to accommodate the largest possible user population without sacrificing interactive functions.

Results to date contribute to an understanding of the gains achievable in the middle ground between complete interactivity (e.g., Internet services) and non-interactivity (e.g., broadcast). Proof-of-concept and simulation results show the viability of our techniques in scaling very large populations of users to interactive servives.

The research is best described as supporting concepts towards supporting digital video streaming for video servers and the broader disciplines of information dissemination in networked information systems and computer networks. A core goal of the work is to support ubiquitous interactive streaming media without the heavy resource burden of a fully provisioned system. That is, to find techniques and approaches to timeshare and optimize the use of the system to provide a nearly identical performance to each user. Our main contributions to this goal are summarized as: (1) proposal of encoded-video conditioning techniques to permit selective frame dropping for stream merging, (2) demonstration of stream merging to support stream acceleration, (3) theoretical concepts and demonstration of clustering techniques for stream merging, (4) techniques for modeling and simulating interactive video-on-demand systems that support future research in this discipline.

The work undertaken under this grant is based on theoretical clustering techniques relevant to broader aggregation theory. We have made modest contributions to work that attempts to aggregate workload in a manner to improve efficiency of processes undertaken by common resources, especially ones with long lifetimes (e.g., streaming video such as movies). The work is also highly applied, having ready utility for organizations hoping to provision large scale information systems including cable TV plants and the WWW for the support of interactive digital video and large-scale information dissemination.

Primary contributions are the development of new researchers in engineering through course development, independent graduate student research, and the support of outreach programs.

Teaching activities included the support of coursework to reflect the changing needs of computer engineers. Many components of the research project were integrated into the PI's coursework as fresh or novel concepts used as a substrate for instructional development.

The research activities supported by this grant will continue to serve as a catalyst for additional programs in the lab and in undergraduate and graduate teaching.

Teaching activities included the support of coursework to reflect the changing needs of computer engineers. Many components of the research project were integrated into the PI's coursework as fresh or novel concepts used as a substrate for instructional development.

The research activities supported by this grant will continue to serve as a catalyst for additional programs in the lab and in undergraduate and graduate teaching.

Our work is intended to significantly improve the ability to disseminate aggregatable interactive media requiring longevity delivery. If realized in deployment, our results can lead to more efficient use of large-scale network bandwidth and can enable a richer interactive experience for users. It can be interpreted as enabling technology for a class of interactive applications, or a performance enhancing one, depending upon how it is applied. Its use will affect large scale network-based information delivery systems such as cable TV plants and the Internet.

Research results are significant towards the development of future information delivery services. The proposed DSAP concept is designed to provide scalability in the support of interactive television. Our goal is to enable the widespread use of interactive services with the use of our core enabling concepts within five years.

We hope that through promotion and dissemination of our techniques we will ultimately contribute to the development of deployed networks and products to achieve this goal in the greater scientific community.