This page contains information regarding the Siena fast forwarding algorithm
(sff), and related software components, including source code and
technical and user documentation. The Siena fast forwarding algorithm
implements the core of the forwarding function in a content-based network.
News: (November 20, 2013) new release of the Siena
fast forwarding engine (v2.0.1). this
is a bug-fix and improvement release. The main changes are
improvements of the performance timers. In particular, the new version
includes a fix for an error in the implementation of the timers based
on clock_gettime, plus a completely new implementation based on the
std::chrono feature of C++11.
See the ChangeLog for more detail.
Siena Fast Forwarding Library and Driver
The Siena Fast Forwarding (SFF) software package contains an
implementation of a number of forwarding algorithms for a
content-based network router. The algorithms are available in a
software library and they are also usable for testing purposes from a
driver program. This implementation uses a generic data model that
supports user-defined values, messages, and predicates. Also, the
implementation features specialized memory management for the
forwarding table and pluggable user-defined output handlers.
You can access the main SFF source repository
through Git with:
git clone http://www.inf.usi.ch/carzaniga/sff.git
If you would like to contribute to SFF, please consider producing
patches against (branches from) the Git repository.
The following packages are also available for download:
Documentation is available within the source packages, as well
as here.
Documentation of the 1.x version is also available
on-line here.
Siena fast forwarding 1.0.0
This is the implementation that we used for the evaluation of the
forwarding algorithm in our
SIGCOMM'03 paper. This
implementation is obsolete and no longer maintained. However, we make
it available as an appendix to the paper. You may download the
source package or browse the
technical and user documentation.
License
Copyright © 2001-2005 University of Colorado.
Copyright © 2005-2013 Antonio Carzaniga.
The Siena fast forwarding algorithm is free software. you can
redistribute it and/or modify it under the terms of the GNU General Public License as published by the
Free Software Foundation; either
version 2 of the License, or (at your option) any later version.
The Siena fast forwarding algorithm is distributed in the hope that
it will be useful, but WITHOUT ANY WARRANTY; without even the implied
warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See
the GNU General Public License for more details.
Related Software Packages
SFF SysMon
Cyrus Hall has developed
sff-sysmon, an OS monitor integrated
with the Siena Fast Forwarding algorithm. sff-sysmon consists of a
module for the Linux kernel plus an application program, and can
monitor file-system as well as process activities. sff-sysmon is no
longer maintained and available.
Siena synthetic workload generator
ssbg 0.x
This is the workload generator that we used to evaluate the forwarding
algorithm in our
SIGCOMM'03 paper. The workload generator
is available in a source package (
ssbg-0.0.4.tar.gz). Notice that this
workload generator uses a number of files to determine workload
parameters such as the distribution of attribute names in messages or
the distribution of operators in filters. Many of these distribution
files can be easily generated using the
gen_dictionary
utility program that comes with the workload generator. A sample set
of distribution files is also available
here.
ssbg 1.x
This is the most current, actively maintained version of the workload
generator. This version include an expanded set of distributions for
names, values, and operators. It also provides message and predicate
generation as library functionalities. The following packages are
available for download:
Simplifier Library
Matt Rutherford
has developed
SSimp, a library that implements procedures for
determining conflicting and covering relationships between predicates.
This library provides an implementation of the basic
predicate interface, as defined by the
SFF
library, that can be dynamically constructed and simplified (i.e.,
reduced) by removing redundant sub-expressions.
The following packages are available for download:
Documentation is available within the source and binary packages,
as well as here.
Siena Fast Forwarding Algorithm
The Siena fast forwarding algorithm is based on a main-memory data
structure that provides an efficient representation of a forwarding
table. The entry point to this structure is an index of attribute
names, attribute names are then mapped into constraints, constraints
into filters, and filters into interfaces. The algorithm examine the
attributes of a notification one by one. For each attribute, the
algorithm looks up the forwarding table attempting to match single
constraints, then entire filters, and ultimately interfaces. The
algorithm shortcuts the evaluation of filters whose interface has
already been matched by other, previously evaluated attributes in the
message. The matching algorithm can apply additional shortcuts by
pre-computing a set of interfaces that can be safely ignored for each
given input message. A detailed description of the forwarding
algorithm and its data structures is presented in:
Forwarding in a Content-Based Network
A. Carzaniga and
A.L. Wolf
Proceedings of ACM SIGCOMM 2003. p. 163-174. Karlsruhe,
Germany. August 2003.
In order to test and fine-tune the performances of the Siena fast
forwarding algorithm, we have used synthetic workloads composed of
randomly generated forwarding tables, and randomly generated
notifications. The parameters that define the workloads are also
discussed in our technical paper.