% $Id: dp1-sum.tex,v 1.1 2004/03/18 18:06:12 dan Exp $
\documentclass{article}
\input{../6033-preamble}
\usepackage{clrscode,graphicx,fancyhdr}

\begin{document}


\title{A Concurrently-Staged Design for Surveillance Monitoring}
\author{Dan Ports}

\lhead{D. Ports}
\chead{A Concurrently-Staged Design for Surveillance Monitoring   }
\rhead{   Exec. Summ.}
\pagestyle{fancy}

\maketitle
\begin{center}
  \Large{\textbf{Executive Summary}}
\end{center}

%\-\paragraph{}\-

\section{Design Overview: The SEDA Model}
\label{sec:overview}

We present the design for a Surveillance-At-Home system. The primary
objectives of this design are, in order, fault isolation, graceful
degradation during periods of unexpectedly heavy load, and high
performance and scalability.

These objectives are met using a novel design based on the Staged
Event-Driven Architecture (SEDA) model developed by Matt Welsh. This
model decomposes the system's processing into a pipeline of individual
\emph{stages} that perform one segment of the processing, as in our
system's dataflow diagram in Figure~\ref{fig:dataflow}. Each stage is
executed concurrently, using one or more processes per stage.

\begin{figure}[h]
  \centering
  \includegraphics[width=5.5in]{dataflowdiagram}  
  \caption{System data flow diagram}
  \label{fig:dataflow}
\end{figure}

The input to each stage is an \emph{event}: a data structure that
contains all the information necessary for the stage's processing. In
this system, an event represents either a partially-processed
segment of video data from one camera, or an incoming HTTP request
from one of the spotters' web browsers.

Each stage consists of a \emph{stage controller} that maintains a
queue of events to be processed, and \emph{event handler} subprocesses
that may be created by the controller to process individual events.
Each stage controller uses a socket-based interface to listen for
incoming events. Other stages submit incoming events by connecting to
the destination stage controller and transmitting the event in a
marshalled form. The destination stage controller then places the
event in its queue. It either processes the event itself, or creates
an event handler process to do so. Enqueuing is the only means for
stages to communicate with each other, which helps enforce modularity
and provide fault isolation.


\subsection{The Stages}
\label{sec:stages}

The following stages are used in this design:

\begin{description}
\item[Camera HTTP Accumulator] This interface stage opens the HTTP
  connections to the cameras. It then operates as a loop (without
  event handler subprocesses) that receives data from
  the cameras via the HTTP connection It stores incoming data from
  each camera in a buffer, and divides it into one-second segments
  that are formatted as events and passed to the Transcoder stage.

\item[Transcoder] This stage uses event handlers as wrappers for the
  \proc{Transcode} procedure. It converts events from the Camera HTTP
  Accumulator stage into events that can be processed by the Anomaly
  Detection stage.

\item[Anomaly Detection] Similarly, this stage uses event handlers as
  wrappers for
  the \proc{detect-anomaly} procedure. It takes in a transcoded video
  stream, and outputs a threat index and the single most suspicious
  frame.
  
\item[Assignment] This stage handles the assignment of video frames to
  spotters. It operates by using a loop that queries two input queues:
  one receiving scored frames from the Anomaly Detection stage, and
  one receiving HTTP requests from the HTTP Server Parser. Received
  frames are stored in a state table. An incoming HTTP request causes
  a frame to be selected from the state table according to a weight
  function that ensures that the highest-threat frames are selected
  first, without allowing any camera to be starved of attention.  The
  pairing of the HTTP request and selected frame is enqueued for the
  HTTP Server Reply stage.
  
\item[HTTP Server Accumulator] The HTTP Server Accumulator is an
  interface stage that listens on TCP port 80 for HTTP connections
  from the spotters, It buffers incoming data, passing HTTP requests
  to the HTTP Server Parser stage.
  
\item[HTTP Server Parser] This stage parses an incoming HTTP request
  from a spotter's web browser, and passes it to the Assignment stage.
  
\item[HTTP Server Reply] This stage generates and sends a reply to the
  spotter, based on an event containing a HTTP connection ID and a
  frame.

\end{description}


\subsection{Adaptive Feedback Algorithms}
\label{sec:adaptive}

In addition to the stage controller and event handler processes, the
system also has a \emph{master controller} process that communicates
with the stage controller process via a shared memory segment,
synchronized with mutual-exclusion locks. It monitors the number of
events in each stage's queue, and the average rate at which events are
being processed by each stage.

The master controller controls the number of event handler processes
that each stage is allowed to use. It allocates these processes to
each stage proportionally to the amount of work in the queue and the
length of processing time required per event. Since the kernel
schedules processes in a round-robin fashion, this allocates more
processing time to the stages that need it most. This minimizes the
effect of bottlenecks, when one stage runs considerably slower than
the others.

The master controller also implements load-shedding. When the measured
rate at which data is being processed by the camera-processing
pipeline falls below the rate at which data becomes available, the
master controller instructs the Camera HTTP Accumulator stage to begin
shedding load at a certain rate. The Camera HTTP Accumulator stage
then begins dropping video segments from each camera, in a fair manner
that ensures that the same proportion of frames from each camera are
processed.


\section{Analysis}
\label{sec:analysis}

The SEDA-based design presented in this paper achieves the design
goals of fault isolation, graceful degradation, and high performance.

Fault isolation is achieved in two ways. First, event handler
processes operate in their own address spaces, so bugs in individual
event handlers (including the known-buggy \proc{Transcode} and
\proc{Detect-Anomaly} functions) cannot interfere with other parts of
the system. Furthermore, communication between stages is restricted
to the narrow interface for inserting events into another stage's
queue. This effectively isolates each stage from the others.

The adaptive feedback algorithms described above ensure that this
design achieves graceful degradation under load. As the system becomes
overloaded, the master controller will shift the allocation of system
resources to bottleneck stages. The load-shedding algorithm causes
video segments to be dropped when necessary. This load shedding is
performed at the beginning of the pipeline, minimizing wasted work,
and is performed in a fair manner, dropping segments from each camera
equally so that all cameras continue to be monitored regularly.

High performance is achieved through the use of the SEDA architecture,
with its event-driven concurrency and adaptive algorithms. This
architecture has proven effective in implementing other
high-performance applications, such as a web server. Furthermore, the
architecture scales easily to a multi-CPU system, or a network of
multiple systems.
\end{document}