% $Id: relwork.tex,v 1.4 2004/05/12 13:46:44 gokhale Exp $

\section{Related Work}
\label{related}

In this section we survey the literature on Pu\-bli\-sher/Subs\-criber
systems, both proprietary and standards-based.
We concentrate on Publisher/Subscriber 
systems for real-time systems, but also include other research that
tackles different QoS properties.  Finally, when the authors do
present performance results we try to contrast their results with
ours.  We avoid making direct performance comparisons because the
underlying hardware and software often make such comparisons
impossible, instead we try to constrast the relative performance of
their Publisher/Subscriber system vs. the underlying infrastructure
and our system vs. our underlying infrastructure.

\section{Standards-based Publisher/Subscribers}
\label{sec:survey:standard}

\subsection{The CORBA Event Service}

The CORBA Event Service is a specification that defines a basic
Publisher/Subscriber architecture for CORBA systems.  In the CORBA
Event Service the Publishers are called \emph{Suppliers}.  Suppliers
can be either push-style or pull-style, the first pro-actively
generate events and send those events to the event channel for
distribution.  Pull-style suppliers passively wait until the event
channel requires an event and supply one if the event is available.
Likewise, the CORBA Event Service uses \emph{Consumers} to play the
Subscriber role.  Consumers can also be pull-style or push-style, the
first style requires consumers to periodically or pro-actively query
events from the event service.  Push-style consumers are simply
notified when a new event is available.  Both styles can be mixed, in
other words, push-style consumers can receive events generated by
pull-style suppliers, or vice-versa.  The CORBA Event Service does not
provide any mechanisms to control QoS behavior, and filtering is
limited to the so-called
\emph{Typed Event Channels} where consumers and suppliers can receive
an specific IDL-type.
However, Typed Events is an optional compliance point in the CORBA
Event Service and very few implementations for this variant of the
service exist.  Therefore, in practice, filtering is not supported.

There are several commercial CORBA-compliant Event Service
implementations available from multiple vendors, such as IONA and
Borland.  IONA also produces OrbixTalk, which is a messaging service
based on UDP/IP multicast.  Since the CORBA Event Service
specification does not address issues critical for real-time
applications, the QoS behavior of these implementations are not
acceptable solutions for many application domains.

\subsection{The CORBA Notification Service}

The OMG has issued a specification for a Notification
Service~\cite{CORBAService:99a}, which is a superset of the CORBA
Event Service.  This specification adds interfaces for event
filtering, configurable event delivery semantics (e.g., at least once
or at most once), security, and event delivery QoS.
We believe that the patterns and techniques used in the
implementation of TAO's Real-time Event Service can be used to improve
the performance and predictability of Notification Service
implementations.  Based on that idea, we have implemented a
Notification Service for TAO~\cite{Schmidt:01g} and used it to
validate the feasibility of building reusable components for the
Notification Service, CORBA Event Service and TAO's Real-time Event
Service.

\subsection{The CORBA Distributed Notification Service}

The OMG has also issued a specification to build distributed versions
of the Notification Service via its ``Management of Event Domains
Specification''~\cite{CORBAService:01b}.
This document describes how multiple instances of the Notification
Service can be interconnected to avoid the excessive overhead and
eliminate the single point of failure represented by the Event Channel
object.
This specification, however, does not incorporate any mechanisms to
reduce event delivery based on filters (as we do in this
dissertation), nor any of the advanced algorithms described in the
SIENA papers (see below), to automatically propagate filters.

\subsection{Fault-tolerant Notification Services}

In~\cite{Ramani:01} the authors study the fault tolerance capabilities
provided by the CORBA Notification Service and propose a configuration
that can achieve the highest event delivery guarantees.  The authors
then examine the performance of such configuration of the Notification
Service under different loads.  TAO's Real-time Event Service has been
designed to satisfy the requirement of high-performance real-time
systems and of highly-scalable distributed interactive simulations.
In these environments, reliability is commonly obtained via other
means, such as hardware redundancy.  Nevertheless, we believe that
extending TAO's Real-time Event Service to provide higher degrees of
reliability is possible, and we are pursuing this topic in our future
work.

\subsection{COBEA}

COBEA~\cite{Cobea:98} is a CORBA-based event architecture service that
generates parameterized events, which are published by a trading
service.  For scalability, clients must register their interest with
the service, at which point an access control check is performed.
Subsequently, whenever a matching event occurs, the client is
notified.  As with TAO's Real-time Event Service the authors propose a
number of extensions to support event filtering and correlation.
However, the COBEA does not take advantage of the broadcast
capabilities of modern networks to reduce traffic, nor does COBEA use
multicast to offload processing from the CPU to the network cards.

\subsection{Reliable CORBA Event Services}

In~\cite{Defago:97}, the authors explore extensions to the CORBA Event
Service to improve its reliability.  In particular, they strengthen
the ``at-most-once, best-effort'' semantics provided by the CORBA
Event Service to include retransmissions of lost events and FIFO
delivery of events.  Their system does not tolerate publisher or
subscriber crashes, and, under certain circumstances, can lose
events.  But it always notifies applications if an event is lost.  The
authors based their system on IONA's OrbixTalk implementation of the
CORBA Event Service, this is a multicast-based implementation, thus
not prone to single points of failure in the Event Channel.  The
authors analyze the performance of their system, unfortunately without
any description of the hardware involved, thus making direct
comparisons with our results impossible.  With this in mind, we note
that in their experiments the system fails to sustain more than 60
events per second, or two orders of magnitude slower than our results.

\subsection{Asynchronous Method Invocation}

The OMG Messaging specification~\cite{Async:98} gives application
developers control over several QoS parameters, such as one-way
reliability and timeouts, and introduces type-safe asynchronous method
invocation (AMI) models~\cite{Schmidt:99w}.  The CORBA AMI
specification solves many problems with the original CORBA invocation
model, but it does not address anonymous or
single-point-to-multiple-point communication.  The Messaging
specification can complement implementations of the CORBA Event
Service, for example, it defines several levels of reliability for
one-way calls, this feature could be used in Event Service
implementations to improve decoupling of the clients, without risking
lost messages.  We have augmented TAO with the
features~\cite{Schmidt:99w} defined by the Messaging specification,
which complement its Real-time Event Service implementation.

\section{Proprietary Publisher/Subscriber Systems}
\label{sec:survey:proprietary}

\subsection{Cadena Event Channel Framework}

Cadena Event Communication Framework~\cite{Singh:04} includes a
CORBA-based event channel which has been integrated into the OpenCCM
infrastructure. The framework implements a number of features of the
event service middleware, such as event filtering, event correlation,
and direct-dispatching. However, it still hasn't addressed the problems
such as real-time event scheduling and dispatching and periodic event 
processing, which are cruicial in a lot of mission critical real-time
applications.


\subsection{SIENA}

SIENA~\cite{Carzaniga:01,Carzaniga:00} is a notification service
architecture for Internet-scale event distribution.  The architecture
is based on \emph{content-based networking}, where a network of
routers propagate packets based not on a specific destination
address, but on the contents of the packet.

The authors propose using an event format similar to the CORBA
Notification Service, {\em i.e.}, sequence of $(name,value)$ tuples.
Using this format consumers use a boolean predicate on the tuple
values to describe the sets of events they are interested in.  The
authors describe algorithms to reduce the use of network
resources. For example, the authors propagate filtering information as
close to the sources as possible, likewise, filtering constraints are
combined and simplified to minimize the use of computation resources
in the routers.

Both SIENA and TAO's Real-time Event Service use similar techniques to
conserve network and CPU resources, however, SIENA's event and
filtering models are more powerful than the model in our Real-time
Event Service.  In contrast, however, our Event Service is better
suited for applications with stringent latency and predictability
requirements, such as avionics mission computing.

Though SIENA was designed for Internet-scale applications, we believe
that the techniques described in SIENA can be applied to the CORBA
Notification Service.  In particular, using these techniques described
in SIENA in combination with the architectural and design patterns
described in this dissertation should result in an efficient, scalable
and and predictable implementation of the Notification Service.

\subsection{TMO's Real-Time Multicast and Memory-Replication Channel}

Kim, \emph{et al.}, describe a real-time Publisher/Subscriber system
called the Real-Time Multicast and Memory-Replication Channel
(RMMC), this system is based on the TMO object model~\cite{Kim00b},
where object methods are separated in two groups, first,
\emph{time-triggered methods} are invoked by the system only at times
defined during design. In contrast, \emph{service methods} are
triggered by normal requests from clients.

In the TMO architecture service methods can only execute when there is
no potential conflict with a time-triggered method.
Using this constraint the system can guarantee, at design time, that
all the deadlines will be met.

In~\cite{Kim:00c,Kim:97c} Kim, \emph{et. al.} extend the TMO model to include
Publisher/Subscriber communication.  Their system can not only
broadcast events to all interested parties, but can also update
logically-global, but physically local tuples of information, that
applications can repeatedly query on the receiving node.  This data
replication service can be used by application developers to
efficiently access commonly used data.

Unlikely most Publisher/Suscriber systems TMO's RMMC does not deliver
events as soon as they are received.  Instead, each event carries an
\emph{official release time}, that is to say, the time at which the
event becomes accessible to application.  This feature can be used to
avoid many of the ordering problems present in broadcast or multicast
systems.  The application architect can, at design time, prescribe the
processing order of all events, simply by ensuring that the release
times of two events are always separated by more than the global clock
resolution.

Furthermore, the RMMC infrastructure can use the official delivery
time to guarantee atomicity, as follows.  Official delivery times are
required to be sufficiently ahead in the future to (1) propagate the
event through the networking infrastructure, (2) detect node crashes
and (3) communicate the node crashes to all the nodes in the system.
Under those conditions the events can be withdrawn when a receive has
failed, \emph{before} the event is delivered, and thus, before any
application state changes have taken place.

\subsection{ECO}

The Distributed Systems Group at Trinity College, Dublin has developed
ECO~\cite{Starovic:95}, for ``Events, Constraints and Objects.''
The authors propose building programs out of cooperating objects that
publish or subscribe to events as needed.  Filtering, concurrency and
timeliness constraints are expressed as constraints on the events that
a particular object publishes or subscribes to.

The authors propose extending
general-purpose programming languages, such as C++ or Java, to include
explicit declarations for events, as well as the types of events that
a class can subscribe or publish.  Naturally, this static publications
or subscriptions can be further restricted at run-time, the authors
propose using new language statements for this purpose.

Objects can add \emph{Notify} constraints to limit the objects that
they subscribe to, this conditions are evaluated at the source of the
event and thus are limited to constraints on the event parameters or
the source identity.  Objects can also define \emph{Pre} and
\emph{Post} constraints, this are evaluated on the destination object
and can use the state of the receiving object to affect the event
processing.  \emph{Pre} constraints are evaluated before the event is
delivered and can determine if the event is dropped, enqueued or
processed immediately.

\subsection{CMU Real-time Publisher/Subscriber}

Rajkumar, \emph{et al.}, describe a real-time
pub\-lish\-er/sub\-scrib\-er prototype developed at CMU SEI
\cite{Rajkumar:95}.  Their Pub\-lish\-er/Sub\-scrib\-er model is
functionally similar to the CORBA Event Service, though it defines its
own programming APIs and communication protocols.
The authors details how real-time threads and adequate synchronization
primitives can be used to implement the RT P/S model without undue
priority inversions.
However, the authors also fail to recognize that adequate
synchronization primitives are a necessary condition to address
unbounded priority inversions, but it is not a sufficient condition.
For example, the authors do not detail how their algorithms avoid
critical sections with time bounds dependent on the number of
participants in the system.

An interesting aspect of the CMU model is the separation of priorities
for subscription and event transfer so that these activities can be
handled by different threads with different priorities.  However, the
model does not utilize any QoS specifications from publishers
(suppliers) or subscribers (consumers.)  As a result, the message
delivery mechanism does not assign thread priorities according to the
priorities of publishers or subscribers.  In contrast, the TAO Event
Service utilizes QoS parameters from suppliers and consumers to
guarantee the event delivery semantics determined by a real-time
scheduling service.

Another interesting aspect of the RT P/S model is how the authors use
different communication protocols among the components in the system,
for example, communication to remote nodes is performed via UDP
sockets, while communication to processes in the the same node is
performed via message queues.  This high-level optimizations are
performed without any changes to the programming API, a technique that
modern and standards-based middleware depend on to achieve adequate
performance.

The authors also present experimental results to support the claims of
efficiency and predictability.  Direct comparison of their results is
impossible given the differences in hardware, software and
communication networks.  However, some comparisons based on relative
performance is possible:  the authors measure round-trip communication
delay over UDP, they obtained 2.4 milliseconds of delay between two
nodes in their network.  Using their implementation of the RT P/S
model they obtain 6.74 milliseconds with one remote consumer,
a $280\%$ increase, and 22.78 milliseconds with 9 remote consumers,
a $950\%$ increase.
These results can be indirectly compared to our experiments (see
Section~\ref{sec:experiments:highscale},
for example, we also measure the baseline round-trip delay over a raw
communication protocol (using TCP/IP in our case), and achieve 96
microseconds of round-trip delay.  Our Publisher/Subscriber system
exhibits more overhead for the case of one remote consumer, in
particular the observed round-trip delay is $351 \mu secs$, or a
$366\%$ increase, but with $9$ remote consumers the round-trip delay
is below $442 \mu secs$, a $460\%$ increase over the TCP/IP baseline,
and well below the $950\%$ increase for their system.

It should be noted that the authors do not specify whether these
results are average delay or worst-case delay, neither do they present
any analysis of jitter or the observed predictability of their
system.  Therefore, it is hard to determine if their system remains
predictable as the number of components or the system load increases.

\subsection{Publisher/Subscriber Model for Controller-Area-Networks}

Kaiser, {\em et al.}, describe a real-time Publisher/Subscriber model
for the Controller-Area-Network~\cite{Kaiser:99}. CAN networks are
designed to provide efficient, predictable communication among
components in complex devices such as robots, automobiles and
aircrafts.
These networks can broadcast relatively short messages to all the
nodes in the network, but, unlike other CSMA networks, messages are
not destructed in the event of a collision.  Instead, the highest
priority message gets delivered.

The authors exploit the broadcast characteristics of the communication
media to implement a Publisher/Subscriber model, simultaneously they
take advantage of the real-time properties of the network to improve
the predictability of the system.
The authors evaluate two implementations of their system, one using a
proprietary operating system and another that is implemented directly
on the hardware.
The authors report that their operating system implementation is able
to deliver a single message in $469 \mu secs$, while the
hardware-based implementation can deliver messages in $169 \mu secs$.
No analysis of the probability distribution, jitter or worst-case
scenario for their results are presented.

These results indicate that our system outperforms (see the results
outlined above) systems based on proprietary software, proprietary
operating systems and specialized hardware.

\section{Summary}

Much has been written about Publisher/Subscriber systems, but there is
little documentation on the patterns, optimizations and architectures
required to implement QoS-aware Publisher/Subscriber models.
Much of the research describe ``point solutions'', in other words,
they propose a particular implementation or model, but do not
generalize the underlying pattern and commonality with other
Publisher/Subscriber systems.

There is also very little or no research on how to implement real-time
or high-scale Publisher/Subscriber systems for standards-based
middleware.  Likewise, there is very little or no empirical evidence
to support the performance and predictability claims of several of
these systems, even when research concentrates on real-time
applications.  In many cases, the empirical results are insufficient
to evaluate if the predictability, performance or scalability goals
can be achiever.  For example, many papers simply present average
performance results, without describing the jitter, observed
worst-case or observed data distributions.






