Applied Research Laboratory
Publications by Year
1995


Gopalakrishnan, R.; Parulkar, Gurudatta M. "A Real-time Upcall Facility for Protocol Processing with QoS Guarantees," ACM Symposium on Operating Systems Principles, (Poster Session), Copper Mountain CO, December 1995, pp. 231.

There is a growing need to provide guarantees for protocol processing within the host operating system to support multimedia applications that have quality of service (QoS) requirements. The QoS parameters for a multimedia stream translate to protocol processing requirements that can be expressed in terms of a time period T, and the number of protocol data units (PDU) Bp in a batch to be processed per period. This report is an extended abstract of the work that details the design and implementation of a real-time upcall (RTU) facility to support protocol implementations that require periodic processing with guarantees. RTUs are an alternative to real-time periodic threads and have advantages such as low implementation complexity, portability, and efficiency. The RTU mechanism is an enhancement to the upcall mechanism that has been used to structure layered protocol code. RTUs are invoked periodically in real-time in a user process and implement PDU processing code. The RTU mechanism can be easily extended to protocols implemented in the kernel. The RTU facility uses a scheduling policy called rate monotonic with delayed pre-emption (RMPD). Other types of media and bulk data processing with QoS can also benefit from the RTU facility since it falls into the periodic processing model. We the RTU implementation in this report.

Buddhikot, Milind M.; Parulkar, Guru M. "Efficient Data Layout, Scheduling and Playout Control in MARS (longer, updated version)" Invited for publication in the Special Issue of ACM/Springer Multimedia Systems Journal.

Large scale on-demand multimedia servers, that can provide independent and interactive access to a vast amount of multimedia information to a large number of concurrent clients, will be required for a wide spread deployment of exciting multimedia applications. Our project, called Massively-parallel And Real-time Storage (MARS) is aimed at prototype development of such large scale server. This paper primarily focuses on the distributed data layout and scheduling techniques developed as a part of this project. These techniques support a high degree of parallelism and concurrency, and efficiently implement various playout control operations, such as fast forward, rewind, pause, resume, frame advance and random access.

Buddhikot, Milind M.; Parulkar, Gurudatta M. "Efficient Data Layout, Scheduling and Playout Control in MARS" Proceedings of the 5th International Workshop on Network and Operating System Support for Digital Audio and Video (NOSSDAV), April 1995. Also, in " Lecture Notes in Computer Science series, Vol. 1018 Springer-Verlag, ISBN: 3-540-60647-5.

Large scale on-demand multimedia servers, that can provide independent and interactive access to a vast amount of multimedia information to a large number of concurrent clients, will be required for a wide spread deployment of exciting multimedia applications. Our project, called Massively-parallel And Real-time Storage (MARS) is aimed at prototype development of such large scale server. this paper primarily focuses on the distributed data layout and scheduling techniques developed as a part of this project. These techniques support a high degree of parallelism and concurrency, and efficiently implement various playout control operations, such as fast forward, rewind, pause, resume, frame advance and random access.

Huni, Hermann; Johnson, Ralph; and Engel, Robert. "A Framework for Network Protocol Software," submitted to OOPSLA 95.

Writing software to control networks is important and difficult. It must be efficient, reliable, and flexible. Conduits+ is a framework for network software that has been used to implement the signalling system of a multi-protocol ATM access switch. An earlier version was used to implement TCP/IP. It reduces the complexity of network software, makes it easier to extend or modify network protocols, and is sufficiently efficient. Condruits+ shows the power of a componentized object-oriented framework and of common object-oriented design patterns.

Engel, Robert; Bieri, Toni; Keller, Beat. "Signaling in ATM Networks: An Object-Oriented Solution," submitted to IPCCC March 95.

Today the Asynchronous Transfer Mode (ATM) is extensively used on the level of public pilot networks. In the first stages of introduction these networks so not yet support signalling.

However, the standardization bodies ITU-TS (former CCITT) and ATM Forum have already produced first specifications for signalling in ATM networks. These specifications define the basic procedures for point-to-point signalling. Further specifications, that are now being defined, will enlarge the basic set to support fully signalling for multimedia applications between several users (point-to-multipoint).

This signifies that developers of signalling software have to cope with two demands: Until a Recommendation for a specification is approved it undergoes constant change. The introduction of a new specification is associated with an enormous increase in software functionality.

In this paper we show how an object-oriented solution allows the demands of flexibility and extendability to be satisfied. This solution consists of a set of classes that are put together to form a very flexible, extendable framework. This framework can be refined to realize any signalling protocol.

We show how this framework was used to build an implementation of the ATM signalling protocol Q.2931 defined by ITU-TS. The reusability and flexibility of it was verified when the framework classes were integrated in the signalling architecture of a ATM switch.

The framework was realized with object-oriented techniques and implemented in C++.

Gopalakrishnan, R.; Parulkar, Gurudatta M. "Quality of Service Support for Protocol Processing Within Endsystems," High Speed Networking for Multimedia Applications, Wolfgang Effelsberg et. al. (Editors), Kluwer Academic Publishers, 1995.

We describe a framework for providing quality-of-service (QoS) guarantees within the endsystem for networked multimedia applications. There are four components in this framework namely-QoS specification; QoS mapping; QoS enforcement; and protocol implementation. QoS specifications are at a high level, and use a small number of parameters to allow applications greater ease in specifying their requirements. Based on the QoS specifications, QoS mapping operations derive resource requirements for each end-to-end session of the application. Important resources considered are the CPU and the network connection. The third component of the framework is QoS enforcement. Enforcement is mainly concerned with providing real-time processing guarantees for protocol code during data transfer. We have implemented a real-time up-call (RTU) facility which is an enhancement to the well known upcall mechanism for structuring protocols. RTUs are scheduled using a policy called rate monotonic with delayed pre-emption (RMPD) that takes advantage of the iterative nature of protocol processing to reduce context switching overhead and increase scheduling efficiency. The last component of our framework is an application level protocol implementation model. Protocol code is structured as RTUs with attributes that are derived from high level specifications by the QoS mapping operations. We describe techniques to reduce the cost of data movement and context switching in such implementation. The RTU mechanism currently runs in the NetBSD OS on Sparc and Pentium based platforms. Initial measurements show that it is an effective means to implement protocols with QoS support.

Fuhrmann, D.R.; Baro, J.A.; and Cox, Jerome, R. "Experimental Evaluation of Psychophysical Distortion Metrics For JPEG-Encoded Images," Journal of Electronic Imaging, October 1995, Vol. 4, No. 4, pp. 397-406.

Two experiments for evaluating psychophysical distortion metrics in Joint Photographic Experts Group (JPEG) encoded images are described. The first is a threshold experiment, in which subjects determined the bit rae or level of distortion at which distortion was just noticeable. The second is a suprathreshold experiment in which subjects ranked image blocks according to perceived distortion. The results of these experiments were used to determine the predictive value of a number of computer image distortion metrics. It was found that mean-square-error is not a good predictor of distortion thresholds or suprathreshold perceived distortion. Some simple pointwise measures were in good agreement with psychophysical data; other more computationally intensive metrics involving spatial properties of the human visual system gave mixed results. It was determined that mean intensity, which is not accounted for in the JPEG algorithm, plays a significant role in perceived distortion.

Gopalakrishnan, R.; Parulkar, Gurudatta M. "A Framework for QoS Guarantees for Multimedia Applications within an Endsystem," Swiss German Computer Society Conference, September, 1995.

We describe a framework for providing quality-of-service guarantees within the endsystem for networked multimedia applications. Our framework integrates four components namely, QoS specification; QoS mapping; QoS enforcement; and a protocol implementation model. The framework allows QoS specifications to be at a high level so that an application can easily specify its requirements using a small number of parameters. The second component of the framework is QoS mapping. The mapping operations derive resource requirements for each end-to-end session from the QoS parameters specified by the application. Important resources considered are the CPU and the network connection. The third component of the framework is QoS enforcement. An important enforcement issue is providing processing guarantees for protocol code.An efficient real-time signal facility (RTSig) had been implemented to achieve this. The last component is an application level protocol implementation model. Protocol code structured according to this model can take advantage of the QoS support facilities in our framework. We also review related work in these areas and show how they fit into the general framework.

Papadopoulos, Christos; Parulkar, Gurudatta M.; "Implosion Control for Multipoint Applications," Proceedings of the 10th Annual IEEE Workshop on Computer Communications, September 1995.

One of the new challenges posed by multipoint applications in future networks is scalable multicast error control. Current error control mechanisms do not scale because they do not deal with message implosion, caused by synchronized feedback messages (e.g. positive or negative acknowledgments) from the receivers in a multicast connection.

Implosion control can be performed by the receivers or the sender. The former, where receivers collaborate to control implosion has been the most popular so far. In the latter, the sender is responsible for directly controlling feedback from the receivers. Sender-controlled implosion is appropriate for cases where receivers are isolated from each other (e.g. where privacy or anonymity is desired, where receivers have limited processing capabilities and in one-to-many connections in connection-oriented networks). Implosion can also be controlled by structuring receivers in a virtual tree

hierarchy with the sender at the root, where feedback messages are restricted from children to their parents. Such a structure is also suitable for ACK consolidation which is required for implosion controlling reliable multicast.

In this paper we present the design and propose to investigate via analysis, simulation and implementation two implosion control mechanisms: a sender-controlled and a dynamic hierarchical implosion control mechanism. Our hierarchical mechanism uses dynamic structures called multicast recovery trees (MRTs) formed by the receivers.

Parulkar, Gurudatta M.; Schmidt, Douglas C.; and Turner, Jonathan S. ``aItPm: a Strategy for Integrating IP with ATM,'' Proceedings of SIGCOMM, September 1995.

This paper describes research on new methods and architectures that enable the synergistic combination of IP and ATM technologies. We have designed a highly scalable gigabit IP router based on an ATM core and a set of tightly coupled general-purpose processors. This aItPm (pronounced "IP on ATM or, if you prefer, "ip-attem") architecture provides flexibility in congestion control, routing, resource management, and packet scheduling.

The aItPm architecture is designed to allow experimentation with, and fine tuning of, the protocols and algorithms that are expected to form the core of the next generation IP in the context of a gigabit environment. The underlying multi-CPU embedded system will ensure that there are enough CPU and memory cycles to perform all IP packet processing at gigabit rates. We believe that the aItPm architecture will not only lead to a scalable high-performance gigabit IP router technology, but will also demonstrate that IP and ATM technologies can be mutually supportive.

Turner, Jonathan S. ``Issues in Distributed Control for ATM Networks,'' Proceedings of the Symposium on Principles of Distributed Computing (PODC), August 1995.

This paper describes an architecture for a multicast virtual circuit switch using cell recycling. This is the first nonblocking switch architecture that is optimal in both the switching network complexity and the amount of memory required for routing cells in multicast virtual circuits. Furthermore, it is optimal in the amount of effort required for multicast virtual circuit modification. This architecture makes it both technically and economically feasible to construct the large switching systems that will ultimately be needed for wide scale deployment of Broadband ISDN to residential users.

Dittia, Zubin D.; Parulkar, Gurudatta M.; Cox, Jerome R., Jr. "Design of the APIC: A High Performance ATM Host-Network Interface Chip," Proceedings IEEE INFOCOM 95, Boston, 1995, pp. 179-187.

We present the design of a high performance ATM host-network for multimedia workstations and server. At Washington University, as part of an ARPA-sponsored gigabit local ATM testbed, we are building a prototype of this interface that can support a sustained aggregate bidirectional data rate of 2.4 Gbps. The centerpiece of our interface design is a custom chip called the APIC (ATM Port Interconnect Controller). Multiple such chips can be interconnected to yield a desk-area network (DAN) which would serve as a high speed I/O interconnect for the host computer. This paper details the internal design of the APIC chip, and outlines some of its key features. Noteworthy among these are: connection caching, transmit pacing, cell batching, remote control, and support for AAL-0, AAL-5, Multipoint, and loopback connections. We have chosen to defer to later paper the details pertaining to several other features which provide support for zero-copy, improved interrupt handling, direct control of the chip from user-space, and efficient buffering and demultiplexing.

Gopalakrishnan, R.; Parulkar, Gurudatta M. "RMDP-A Real-time CPU Scheduling Algorithm to Provide Guarantees for Protocol Processing," Proceedings of IEEE Real-time Technology and Applications Symposium,(Poster Session), Chicago, May 1995.

We present the analysis of a real-time CPU scheduling algorithm specifically design to provide processing guarantees for multimedia applications. It is motivated by the need to reduce the number of context switch operations in protocol processing while being ale to provide bandwidth and delay guarantees to each protocol session. We have implemented this scheme in the NetBSD operating system. Our experimental and simulation results show that there is substantial reduction in the number of context switch operations. We present the scheme and derive its schedulability test.

Saied Hosseini-Khayat, Andreas D. Bovopoulos, "A Simple and Efficient Bus Management Scheme that Supports Continuous Streams," ACM Transactions on Computer Systems, Vol. 13, No. 2, May 1995, Pages 122-140.

An efficient bandwidth management and access arbitration scheme for an I/O bus in a multimedia workstation is presented. It assumes that a multimedia workstation consists of a number of processing modules which are interconnected by a packet bus. The scheme is efficient in the sense that it allows the bus to support both continuous media transfers and regular random transactions in such a way that continuous streams can meet their real-time constraints independently of random traffic, and random traffic is not delayed significantly by continuous traffic except when traffic load is very high. Implementation guidelines are provided to show that the scheme is practical. Finally, the performance of this scheme is compared with alternative solutions through simulation.

Cranor, Charles D.; Parulkar, Gurudatta M. "Design of Universal Continuous Media I/O," Proceedings of the 5th International Workshop on Network and Operating Systems Support for Digital Audio and Video (NOSSDAV `95), pp 83-86, April 1995.

The problem this research addresses is how to modify an existing operating system's I/O subsystem to support new high-speed networks and high-bandwidth multimedia applications that will play an important role in future computing environments.

Return to the top

How to request a copy of one of our publications...

Email:
vykky@arl.wustl.edu

Snail mail:
Applied Research Laboratory
Washington University, Campus Box 1045
One Brookings Drive
St. Louis, MO 63130-4899

Return to the top

Return to:

Last modified September 18, 1996

prepared by Vykky Klingenberg