\documentclass[twocolumn,11pt]{infocom}
\usepackage{url}
\mathchardef\UrlBigBreakPenalty 10
\mathchardef\UrlBreakPenalty 10
\usepackage{epsfig}

\newcommand{\thdr}[1]{\multicolumn{1}{c|}{#1}}

\begin{document}

\title{Ourmon versus IXIA: Monitoring Gigabit Speeds}
\author{James R. Binkley, Bart Massey\\
Computer Science Department\\ 
Portland State University\\
Portland, OR~~USA \\ 
Paper ID: E00-241341058 \\
Pages: \pageref{last} \\
{\em \{jrb,bart\}@cs.pdx.edu}}

\hyphenation{attack gigabit}

\markboth{ACM SIGCOMM Internet Measurement Conference 2004}%
{Binkley and Massey: Ourmon versus IXIA---Monitoring Gigabit Speeds}

\maketitle

\begin{abstract}
We measure the performance of a modern PC host running  {\em
Ourmon}, our
novel network monitoring system.
The goal of the analysis
is to understand system performance under gigabit load with
both maximum-sized and minimum-sized Ethernet frames.
Our testbed consists of an IXIA 1600 high-speed packet
generator that can send packets at near theoretical speeds,
a gigabit switch, and a roughly 2 GHz AMD PC host.  We measure the
performance of the underlying BPF network tap on FreeBSD, as
well as the performance of various application-layer filters
used by the Ourmon system. We show that using a BSD BPF
kernel buffer size of several megabytes permits a
workstation using the Ourmon filters to capture back-to-back
maximum-sized Ethernet packets at gigabit speeds.  We also
show that when minimum-sized packets are sent, the
BPF/Ourmon system fails at a relative small
throughput rate. This failure appears to be due to
limitations of the hardware and/or network stack rather than
the Ourmon system proper.  This result has troubling
implications for network management and intrusion detection
systems, given the current frequency of large volume
Internet attacks using small packets.
\end{abstract}

%%\newcommand{\info}[2]{%
%%   {\par\small{\itshape #1}\/\bfseries---$\!$#2}}

  \begin{keywords}Intrusion detection, Ourmon, IXIA, network monitoring,
  network security.\end{keywords}

\section{Introduction} \label{introduction}

The Internet has recently faced an increasing number of bandwidth-intensive
denial-of-service (DOS) attacks.  For example, in January 2003 the Slammer
worm~\cite{certsql,slammer} caused serious disruption.  Slammer
not only wasted bandwidth and affected reachability, but also
seriously impacted the core routing infrastructure.  At
Portland State, four lab servers with 100 Mb NIC cards 
were infected simultaneously.  These servers then sent approximately 360 Mb
of small packets to random destinations outside of PSU.  This
attack clogged PSU's external connection to the Internet and
also caused important network monitoring failures.
Due to the semi-random nature of the IP destination addresses generated by
the worm, the CPU utilization of a router sitting between network engineers
and network instrumentation rose to 100\%.  Engineers were
thus cut off from 
central network instrumentation at the start of the attack.

We recently acquired an IXIA 1600 high-speed packet
generator.  The Slammer attack inspired us to test our
Ourmon~\cite{ourmon} network monitor system against a set of
Gigabit Ethernet (GigE) flows.  Our test flows included
maximum-sized (1518 byte) and minimum-sized (64 byte) UDP
packets as well as rolling IP destination addresses.

The Ourmon network measurement system architecture consists of two
parts: a front-end probe and a back-end graphic
display system.  Optimally, these two parts should run on
two separate computers in order to minimize the application compute
load on the probe itself.  Our goal in these experiments has
been to test the
performance of the front-end Ourmon probe and its BPF
network tap, rather than the back-end system.  

We constructed a test system consisting of the IXIA with two 
GigE ports, a line speed GigE switch capable of
port-mirroring, and a UNIX workstation with a GigE NIC card.
The IXIA was set up to send packets from one GigE send port
to the other port.  The switch was set up to mirror packets 
from one IXIA port to the UNIX host running our front-end probe. 

Like other tools including tcpdump~\cite{tcpdump}, Snort\cite{snort},
or Ntop~\cite{ntop1,ntop2}, the Ourmon front-end uses the BPF as a
{\em packet tap}.  The application takes a stream of
unfiltered packets directly from an Ethernet device, bypassing the
host TCP/IP stack.  The interface interrupts on packet input, and
hands the trimmed packet (containing all headers
through layer 4) to the kernel
BPF filter buffer.  The front-end Ourmon probe reads 
packets, subjecting each packet in turn to a set of configuration
filters.  It thus makes sense to separately test the performance
of BPF and the performance of the Ourmon probe component filters.  

Our experimental questions include the following:

\begin{enumerate}
\item Using GigE with maximum or minimum-sized packets, at
  what bit rate can the underlying BPF tap and buffer system
  successfully process all packets?

\item Using GigE with maximum or minimum-sized packets,
  what is the smallest BPF kernel buffer size (if any) for
  which all packets are successfully processed?

\item Ourmon has three kinds of filters: hardwired C
  filters, BPF-based interpreted filters, and a ``top-N''
  flow analysis system.  Can we determine anything about the
  relative performance of these filters?  If we are
  receiving a high number of packets per second, which of
  these filters can keep up?
  
\item With the Slammer worm, we know that semi-random IP
  destinations led to inefficient route caching in
  intermediary routers.  What happens when we subject our
  top-N flow monitor to rolling or semi-random IP destinations?
\end{enumerate}

In section \ref{ourmon} we provide a brief introduction to the Ourmon system.  
In section \ref{experiment} we discuss our test setup.  
In section \ref{results} we present test results, and in section \ref{conclusion} we provide 
analysis and conclusions.  

\section {Introduction to Ourmon} \label {ourmon}

In this section, we explain
enough of the Ourmon system functionality to
understand the performance measurement work reported in
sections~\ref{experiment} and~\ref{results}.  In furtherance
of this goal, we focus on the front-end
packet capture system.  The detailed workings of the Ourmon
system are outside the scope of this paper. \footnote {
However for more information on the Ourmon architecture, please
see: {\em http://ourmon.cat.pdx.edu/ourmon/info.html} .}

Ourmon is a real-time web-based network monitor.  Ourmon is
somewhat similar to SNMP RMON~\cite{rmon2} systems or Ntop.  Unlike SNMP
RMON, Ourmon does not present a set of variables encapsulated in a probe
accessed via the SNMP protocol from a management system.  Instead,
Ourmon assumes the port-mirroring functionality of Ethernet-based
switches.

A typical setup may be seen in 
Figure \ref{setup}. 
An Ethernet switch is configured to mirror (duplicate) packets sent
to its Internet  connection on port 1.  All packets received via
the Internet port are copied to port 3, which is running the front-end
Ourmon probe on a FreeBSD system with the BPF packet tap.  
Thus Ourmon's probe setup is similar to that of Snort, which we show running
on port 2 of the switch.  The probe system ideally is
attached
to a border switch that sees all packets going
to and from the Internet.  The back-end Ourmon graphics
engine is not performance critical: it may
run on a second computer, which need not be in the center of a network.

\begin{figure}
\centering
\epsfig{figure=dmz.eps}
\caption{Ourmon network setup}\label{setup}
\end{figure}

The probe has an input configuration file and an output file.  The input
file, called {\em ourmon.conf}, specifies various named filters for
the probe to use.  Probe output is written to
a small ASCII file called {\em mon.lite} that summarizes 
the last 30 seconds of filter activity in terms of byte or 
packet counts per named configuration filter.  
This file may be copied over the network
to the graphics-engine computer, which in turn produces
various graphic outputs and ASCII reports for web display.  The back-end graphics
engines produces several kinds of graphics.  RRDTOOL-based~\cite{rrdtool} strip charts
are used with BPF filter-sets and hardwired
filters. Histograms are used to display the 
top-N flow analysis.  

The Ourmon front-end process uses the BPF in two ways.
It uses it to get packets from the kernel BPF buffer system.  
It also uses the BPF interpreter in user mode. The system
can utilize multiple BPF filter expressions, 
group them together in a BPF {\em filter-set} and graph each expression
in the set as a separate line in a single RRDTOOL strip chart graph.

As an example, here is a simplified configuration for one
BPF filter-set. This filter-set groups the performance of
five application services together, using one BPF expression
each for secure-shell, combined P2P protocols, web, ftp, and
email.
\begin{small}\begin{verbatim}
  bpf "ports" "ssh" "tcp port 22"
  bpf-next "p2p" "tcp port 1241 or 
       tcp port 6881"  
  bpf-next "web" "tcp port 80 or 
       tcp port 443"
  bpf-next "ftp" "tcp port 20 or 
       tcp port 21"
  bpf-next "email" "tcp port 25"
\end{verbatim}\end{small}
Probe output for such a filter over a snapshot period might 
look like this:
\begin{small}\begin{verbatim}
  bpf:ports:5:ssh:254153:p2p:19371519:
   web:41028782:ftp:32941:email:1157835
\end{verbatim}\end{small}

The filter configuration allows the user to name the composite
graph ``ports''. Five separate user-mode BPF configuration expressions
like ``tcp port 22'' are mapped to appropriate line labels (``ssh'') in the same graph.  Thus
ssh/p2p/web/ftp/email byte counts will all appear in the same RRDTOOL
graph as in Figure \ref{bpfs}. 
The probe 
executes the user-mode BPF runtime expressions on the incoming
packet stream from the packet tap and counts matching bytes.  
At the sample period timeout, it
outputs the {\em mon.lite} file which 
in this case includes
the name of the filter-set and various (line label, byte count)
tuples for each BPF expression.  Multiple BPF
filter-sets are possible: many
separate BPF expressions can be executed in the probe application.
The current PSU DMZ probe software is running around 60 BPF expressions
in sixteen filter-sets and does not normally lose packets (barring attack
periods).

\begin{figure*}
\centering
\epsfig{figure=bpfs.eps,width=7in}
\caption{A BPF filter-set graph showing application byte counts}\label{bpfs}
\end{figure*}

Ourmon also supports a small set of ``hardwired''
filters programmed in C
and turned on via special names in the
configuration file.  For example, a hardwired filter
counts packets according to layer 2 unicast, multicast, or
broadcast destination address types.
One very important filter called
the {\em packet capture} filter includes 
statistics on dropped and counted packets provided directly from the BPF kernel code.  
The packet capture filter is fundamental: it is used to determine
when the kernel BPF mechanism is overloaded in our testing.  Typical
front-end output in the {\em mon.lite} file for that filter and
the layer 2 packet address type filter might look like this:
\begin{small}\begin{verbatim}
  pkts: caught 53420 drops: 0
  fixed_cast: mcast: 2337215: 
   unicast: 15691896: bcast: 0: 
\end{verbatim}\end{small}
The {\em packet capture} filter (``pkts'') output means that the BPF during the last sample
period caught 53240 packets and dropped none.  In Figure \ref{overflow}, 
we show an example back-end graph for this filter.  Drops are in green and
captured packets are in blue.  This graph is from
the day of a Slammer re-infection. It can be
seen that the Ourmon probe (at the time a Pentium-3) has caught the attack, even
though many packets have been dropped.

\begin{figure*}
\centering
\epsfig{figure=overflow.eps}
\caption{The packet capture filter graph showing counts and drops during a Slammer attack}\label{overflow}
\end{figure*}

The third and last filter class in Ourmon is a ``top-N'' flow monitor.
The front-end builds up a hash-sorted list of IP flows over the
sample period and writes the top N (typically around 10) TCP, UDP, and IP (all IP
protocols) flows to the output file.  The back-end
takes this information and produces graphical histograms and text reports.  
A flow is defined as a five-tuple consisting of IP source, IP destination, IP next
protocol, L4 source port, and L4 destination port.  See Figure \ref{topn} 
for an example top-N report: we show a DOS attack on a local IT
administrator's host machine. The attack packets are
launched over Internet2 using a
spoofed IP source address.  Multiple UDP flows, each around
1.5 Mb, are shown.

\begin{figure*}
\centering
\epsfig{figure=topn_udp.eps,width=7in}
\caption{Top-N UDP flow histogram showing a DOS attack}\label{topn}
\end{figure*}

In summary, the front-end has three kinds of filters: hardwired
C filters, user-mode BPF filter-sets, and top-N flow
analysis.
Intuitively
we are interested in the execution cost of each of these three
kinds of filters.  While there is only one top-N
flow filter, a user may program any number of BPF filter-sets: 
this complicated the analysis somewhat.
The {\em packet capture}  filter is especially
important, as it serves to tell us when we are losing packets.  We
can view this as an important indicator that the combined kernel and probe
application system is in failure mode. An important cause of failure
is too much work done at the application layer, causing the application
to fail to read buffered kernel packets in a timely manner.

\section {Experimental Setup} \label {experiment}

The hardware used in our testing consists of three pieces of equipment: 
\begin{enumerate}
\item An IXIA 1600 chassis-based packet generator with a two port GigE line card.  
One port sends packets and the other port receives packets.
\item A Packet Engines line speed GigE switch.  Three ports on
the switch are used: one for the IXIA send port, one for the IXIA receive port, and a third port connected
to the UNIX host for mirroring the IXIA flow.
 \item A 1.7 GHz AMD 2000 computer system.
(The AMD processor is roughly comparable to a 2GHz Intel Pentium 4 processor.)
The system motherboard is a 
Tyan Tiger MPX S2466N-4M.  The motherboard has two 64-bit PCI slots: we use a 
SysKonnect SK-9843 SX GigE card in one of the slots.  
\end{enumerate}

Software used includes Ourmon 2.0 and the BSD
lib\-pcap~\cite{tcpdump} library 0.7.2.  
The host operating system is FreeBSD 4.7, running only the Ourmon front-end probe.  

We set up the IXIA to send either minimum-sized packets 
or maximum-sized Ethernet packets.  One port on the
IXIA sent packets through the switch to the other IXIA port.
All packets were UDP packets.
The IXIA allows the user to select an arbitrary
packet sending rate up to the maximum possible rate.
It can also auto-increment
IP destination addresses: we used this as an additional test
against the top-N filter.

According to Peterson~\cite{peterson}
the maximum and minimum theoretical packet rates for
GigE are as shown in
Table~\ref{table1}. We used these values as a measurement baseline.
We observed
that the IXIA 1600 can indeed generate packets at nearly 100\% of
this rate for both maximum and minimum-sized packets.  We used these
numbers to make sure that our Ethernet switch did not drop packets:
we hooked both IXIA GigE ports up directly to the switch and
sent packets from one IXIA port to another IXIA.  The
IXIA's built-in counters at the receive port reported the same
packet counts as at the send port.

\begin{table}
\caption{GigE rates}\label{table1}
\centering
\begin{tabular}{|r|r|r|} \hline
&\multicolumn{1}{c|}{bytes/pkt}&\multicolumn{1}{c|}{pkts/s}\\ \hline
min & 64        & 1488000\\ \hline
max & 1518      & 81300\\ \hline
\end{tabular}
\end{table}
 
The test methodology involves setting up a UNIX host
with a driver script and some set of Ourmon filters.
The
front-end probe is started, and the IXIA is configured to
send min or max packets
at some fraction of the maximal rate. Ourmon is configured
with some combination of hardwired, user-mode
BPF, and top-N filters as desired. The test flows are then
started on the IXIA, and the results observed using
the {\em mon.lite} output file.
 
The test script is the Bourne Shell script shown in Figure \ref{script}.
The FreeBSD {\em sysctl(8)} command is used to set the
kernel BPF buffer size.  This is because recent versions of the PCAP library
on FreeBSD will take this information and automatically size the
buffer to be used by the client application to match
the kernel buffer size.  This
is a relatively new feature and was very handy for our experiment.
It should be noted that the traditional size of the kernel BPF
buffer is typically small (4KB in FreeBSD 4.9) and is intended
for the tcpdump sniffer application.  The parameters to the Ourmon
probe program tell it to take input from a local configuration
file, dump the output information to
the screen every five seconds and use the SysKonnect card as the input 
interface.


\begin{figure}
\begin{small}\begin{verbatim}
  #!/bin/sh
  BSIZE=1048576
  sysctl -w debug.bpf_bufsize=$BSIZE
  sysctl -w debug.bpf_maxbufsize=$BSIZE
  ./ourmon -a 5 -I sk0 -m /dev/tty \
    -f ./ourmon.conf
\end{verbatim}\end{small}
\caption{Test script}\label{script}
\end{figure}
 
Tests were run using either maximum-sized or minimum-sized
packets.  If we dropped packets, we attempted in every case
to eliminate packet drops by increasing the kernel BPF buffer
size (BSIZE above).  If that failed, we then reduced
the IXIA's send rate until all packets were transmitted.

For testing, we identified five interesting categories of Ourmon filters 
and constructed filter tests for these categories.
\begin{description}
\item {\em null:} The packet capture filter cannot be turned
 off, and is the only remaining statistic
when all Ourmon filters (hardwired, etc.) are removed from the configuration.
\item {\em hard:} The hardwired C filters as a group.
\item {\em bpf:} BPF filters as one or more filter-sets.
\item {\em top-n:} The top-N filter mechanism.
\item {\em combo:} A simple combination of all filters.
\end{description}

The null filter tells us whether or not the BPF in
the kernel was losing packets, as its count/drop
information is taken from the operating system.  The hard,
bpf, and top-n filter categories were tested individually in order
to determine if the filter type itself had an impact on the
overall performance.  The six hardwired C filters available
at the time of testing were used in the tests.
The bpf tests were based on a filter-set that
had 4 simple filters in it.  The individual BPF expressions were
configured to capture TCP ports that could not match the output of
the IXIA (UDP packets): it seemed reasonable for BPF expressions to always
fail to match.

Repeatedly testing the top-N mechanism with the same IP flow
would yield no new information.  Therefore, for the top-N
test we used a rolling IP destination setup where each
subsequent UDP packet within a set of 1000 or 10000 had a
different IP destination.  This could be said to be a rough
simulation of the Slammer worm, with its variation in IP
destinations.

\section {Test Results} \label{results}

Test results fall into two basic categories, which are
reported separately: tests with maximum-sized packets, and
tests with minimum-sized packets.

\subsection {Maximum Packets} \label{maxtest}

In this set of tests, packets were always 1518 bytes, the normal maximum
MTU for Ethernet packets.  (This works out to a 986 Mb flow of UDP
packets).  Our tests involved the null, hard, top-n, bpf,
and combo categories as described in section \ref{experiment}.
The test results are summarized in Table \ref{table2}.

\begin{table}
\caption{Maximum packet tests}\label{table2}
\centering
\begin{tabular}{|r|r|r|r|r|} \hline
test &
\thdr{sets} &
\thdr{flows} &
\thdr{bufsz (KB)} &
\thdr{drops (\%)} \\ \hline
null  &  & & 128 & 0\\ \hline
hard &  & & 128 & 0\\ \hline
top-n &  & 1000 & 128 & 0\\ \hline
top-n &  & 10000 & --- & 80\\ \hline
bpf & 1 & & 128 & 0\\ \hline
bpf & 4 & & 128 & 0\\ \hline
bpf & 8 & & 128 & 20\\ \hline
bpf & 8 & & 7168 & 0\\ \hline
combo & 1 & 1000 & 7168 & 0\\ \hline
\end{tabular}
\end{table}

The flow rate was set to maximum: the drop rate therefore shows packets
lost at gigabit speeds. In the null case,
 the configuration {\em almost} worked with the default BPF buffer size
of 4 KB. However, some packets were lost at a 30 second
interval.  This may have had something to do with an operating system timer.  Increasing
the kernel BPF buffer size to 128 KB resulted in perfect
transmission, even after adding in
the hardwired filters.

The top-N filter
worked with no loss at 1000 flows and completely failed at 
10000 flows.  Larger BPF buffers did not help
(dashed table entry).  This is the most significant failure
case with maximum-sized packets. Decreasing
the IXIA flow-rate to 45 Mb resulted in perfect
transmission.
For the bpf tests, we increased the number
of filters to 8 sets (32 BPF expressions) before running into some loss.
At that point, we increased the kernel BPF buffer size.  We found that a very
large buffer of 7 MB could indeed get us back to lossless transmission.  
With the combo configuration (hard + top-n + 1 bpf set)
we did not experience any loss: note however that we used
only 1000 flows with the top-N filter.

\subsection {Minimum Packets} \label{mintest}

Attempts to capture maximum-rate flows of minimum-sized
packets (64 bytes) uncovered serious problems.  We
therefore report our results as a series of small
experiments: each
experiment focuses on a different test domain.

\subsubsection {Null Filter Only} \label{minnull}

It was not always possible
to capture all packets even in the null filter case.
Instead we attempted to determine
the effect of the kernel BPF buffer size on drop rates as
shown in table~\ref{table3}.

\begin{table}
\caption{Minimum packets and null filter}\label{table3}
\centering
\begin{tabular}{|r|r|} \hline
bufsz (KB)&
\thdr{thresh (Mb/s)}\\ \hline
32 & 53.33 \\ \hline
128 & 68.52 \\ \hline
256 & 76.19 \\ \hline
512 & 76.19 \\ \hline
\end{tabular}
\end{table}

A buffer size of 256 KB appears optimal: at this size
the system begins to drop packets at 76 Mb.  Larger kernel buffers
do not improve the result.  Of course the most important aspect
of this test is that we cannot capture more than around 10\% of the 
GigE stream without loss. (Note that packet overhead for minimum packets
results in a maximum flow of around 760 Mb.)

\subsubsection {Individual Filter Types} \label{minsingle}

Having determined baseline drop rates using the null filter,
we could now proceed to measure the impact of other filter
types.  In the BPF filter-set tests, we tried both one and
two filter-set configurations.  In the top-N filter test, we
varied the number of simultaneous flows.  Table \ref{table5} below shows
the results for the hard and BPF tests.  Table
\ref{table6} shows the results for the top-N tests.

\begin{table}
\caption{Hardwired and BPF tests}\label{table5}
\centering
\begin{tabular}{|r|r|r|r|} \hline
test & \thdr{sets} & \thdr{rate (Mb/s)} & \thdr{drops (\%)} \\ \hline
hard & & 76 & 0 \\ \hline
bpf & 1 & 68 & 0 \\ \hline
bpf & 2 & 53 & 0 \\ \hline
\end{tabular}
\end{table}

\begin{table}
\caption{Minimum packets---top-N tests}\label{table6}
\centering
\begin{tabular}{|r|r|r|r|} \hline
flows & \thdr{thresh (Mb/s)} & \thdr{bufsz (KB)} & \thdr{rate (Mb/s)}\\ \hline
1 & 0 & 256 & 76\\ \hline
100 & 1 & 256 & 76\\ \hline
1000 & 25 & 256 & 76\\ \hline
1000 & 0 & 256  & 45\\ \hline
10000 & 50 & --- & --- \\ \hline
\end{tabular}
\end{table}

Hardwired filters appear to have no impact on performance.
The bpf filters
have some performance impact, visible even at a modest 76 Mb
transfer rate.
At this transfer rate, 1000 unique flows is stressful for the top-n filter. 
However reducing the flow rate to 45 Mb allows the filter to
keep up with
the data.  Unfortunately, 10,000 flows cannot be handled
with any kernel buffer size at any measured transfer rate.
Subsequent work on hashing techniques has improved upon this
result, but the top-n filter is still quite expensive.

\subsubsection {Combination filtering} \label{minconfig}

In this experiment we measure the combo filtering
previously discussed.  Here we vary only the flow-rate,
holding the buffer size constant at 256 KB and the number of
flows constant at 1000.  Table~\ref{table7} shows the
results.

\begin{table}
\centering
\caption{Minimum packets---all filter types}\label{table7}
\begin{tabular}{|r|r|} \hline
rate (Mb/s) & \thdr{drops (\%)}\\ \hline
76 & 44 \\ \hline
68 & 37 \\ \hline
53 & 18 \\ \hline
45 & 3 \\ \hline
38 & 0 \\ \hline
\end{tabular}
\end{table}

We see that we must reduce the flow-rate to roughly one-half maximum
in order to prevent drops.
This is probably because of the impact of 1000 flows on the top-N filter.
The filters here are in truth
fairly minimal, as there is only one BPF filter-set.
In reality one would want more filter-sets
to get better traffic information.  The bottom line
is that we must reduce the flow-rate to 38 Mb
for even a modest amount of work to be performed without packet loss.

\section {Conclusion} \label{conclusion}

Our paper introduces Ourmon, a new monitoring tool, and
discusses experiments aimed at measuring the performance of
both the underlying kernel BPF filter system and Ourmon
front-end filter systems.

The measurement system closest to Ourmon is probably
Ntop~\cite {ntop1}.  Ntop is a single program intended to
run on desktops: it can be thought of as a
network version of the UNIX top program.  Ourmon is designed
more along the lines of a traditional distributed SNMP probe,
with a distinct separation between capture and display.
It relies heavily on user-programmable BPF filters and
RRDTOOL-based graphics.  In this paper, our focus is chiefly
on security impacts of measurement.
Thus, the differences between Ourmon and Ntop are not as
germane.

From the intrusion detection point of view, Ourmon and Ntop
can be said to be similar lightweight tools that show
anomalous behavior via graphs. In contrast, an IDS tool
like Snort does signature-based analysis on every packet.
Ourmon is lightweight compared to Snort: it looks only at
the layer 1--4 network headers and entirely ignores the data payload.
It is thus reasonable to expect that Snort's processing
will be impacted even more than Ourmon's by high packet loads.

We can draw some interesting conclusions from our
experimental work.
\begin{enumerate}
\item The default FreeBSD BPF buffer size of 4 KB is
  inadequate for a network monitoring system.  We suggest a
  larger default buffer of at least 256 KB: this size should
  not unduly burden modern systems.  Network administrators
  should understand that a multi-megabyte buffer may be needed.  As a
  point of reference, the current Ourmon probe deployed in
  the PSU DMZ is running on an 2 GHz Intel Pentium 4 with an 8
  MB kernel buffer. It runs 60 BPF expressions and multiple
  kinds of top-N filters, yet only drops packets during severe TCP
  SYN attacks.
  
\item Our BPF filters seem to have a kernel buffer cost
  associated with them.  Our results suggest that there is a
  positive relationship between the amount of kernel buffer
  space needed to mask filter latency and the number of BPFs
  used in our application.  Our tests seem to imply that the
  BPF mechanism is less costly than the top-N filter.
  However the BPF mechanism can have any number of
  expressions, and the expressions themselves can vary in
  complexity. It is thus hard to compare the BPF filter
  mechanism to the top-N filter mechanism in terms of
  compute power.

  The real computation problem for
  the top-N system is that it is driven
  to extremis under attack attempting to cope with random IP addresses (source or
  destination).  The hash-based top-N algorithm will first
  search for the given flow ID, and then perform an insert if it
  fails to find the flow.  Consequently random flows always
  cause an insert.  This leads to an interesting research question: How
  can we deal with boundary conditions caused by random IP
  addresses without unduly impacting efficiency mechanisms
  meant for normal bursty flows?
  
\item Our 2 GHz Pentium-4 class computer cannot capture more
  than 10\% of the minimum-sized packet flow.  Worse, if the
  computer is expected to perform actual application-level
  work using the data, the number of packets we capture
  without loss falls below 5\%.
\end{enumerate}

This last item deserves extended discussion.  Consider an
IDS system such as Snort.  An IDS wants to run an arbitrary
number of signatures over both the packet headers and the
packet data, and may choose to inject its measurement
results into a database system.  Clearly per-packet
processing times may become quite large in this scenario.

Now consider the security principle known as {\em weakest link}.  For
example, Bruce Schneier writes~\cite{schneier}:  ``Security is a
chain.  It's only as secure as the weakest link.'' An IDS system incurs
a significant risk when it drops a single packet, as that packet may be
the one with the Slammer worm that will infect an internal host.
Worse, a set of coordinated systems might launch a distributed DOS
attack against an IDS monitor, first blinding it with small packets and
then sneaking a one-packet worm payload past it.  Packet capture for
small packets at high rates is an important open security
problem.

There is some related work in the area of capturing small
packets.  For example, Mogul and Ramakrishnan~\cite{mogul}
describe the phenomenon seen here as {\em receive livelock}.
They present improved operating system scheduling algorithms
that can lead to fair event scheduling, with the result that
receive interrupts cannot freeze out all other operating
system events.  

One must consider that there is not a lot of
time left with 1,488,000 small packets per second: this
works out to approximately 0.7 $\mu$s per packet.  Some
sophisticated approach, such as improving the individual
compute performance of various filter mechanisms or applying
parallelism, is needed to attain adequate performance,

Some recent work on enhancements to the BPF suggests
alternatives for improving BPF performance.  The xPF
system~\cite{xpf} expands the BPF to a general purpose
computing machine by allowing backward branches.  This
provides the opportunity to enhance BPF performance by
running filters entirely in-kernel.  The BPF+
system~\cite{begel} optimizes BPF performance using both
machine-code compilation and various optimization
techniques.  This results in impressive performance
improvements that we would like to exploit in Ourmon.
A recent IDS~\cite{kemmerer} contains an interesting parallel hardware engine 
based on a flow slicing
technique: this hardware reportedly improves Snort's
performance under high packet loads.
However making such a system that effectively uses
parallelism and remains cost effective is a challenge.

As a result of our testing, we have adopted the long-term
objective of trying to produce a parallelized Ourmon system.
We intend to explore the porting to and parallelization of
Ourmon on the high speed parallel Intel IXP~\cite{ixp}
system.

\section {Acknowledgements} \label{Acknowledgements}

This work would not have been possible without the generous
donation from the IXIA Corporation of an IXIA 1600 tester.  
We also wish to thank our graduate
students Subha Singaram and Gayathri Nagabhushan for their
help with this project.

\bibliographystyle{IEEE}
\vfill
%%\pagebreak
\bibliography{ourmon}

\label{last}
\end{document}
