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: (Mar 11, 2010) new release (v1.9.4) of the Siena fast forwarding library and driver. This version introduces the following significant changes and features: (1) The syntax of the SFF driver was augmented to accept keywords (e.g., "select", "ifconfig", and "integer") as well as generic strings as attribute or constraint names. (2) The Bloom filter algorithms now use a configurable, and by default more appropriate number of hash functions. The default is to use a width of M=256-bit and k=10 hash functions. These parameters can be changed at configure time. (3) SFF now offers a command-line option (-c) to count the matching predicates instead of printing them all.
See the ChangeLog for more detail.
Siena Fast Forwarding Library and Driver
The Siena Fast Forwarding (SFF) software package contains the implementation of the fast forwarding algorithm. This package contains a library implementation of the forwarding table and algorithm plus 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. The following packages are available for download:- sff-1.9.4.tar.gz: source package
Documentation is available within the source and binary packages, as well as 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-2010 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 available here.Siena synthetic workload generator
ssbg 0.x
This is the workload generator that we used to evaluate the forwarding algorithm in our 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 thegen_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:- ssbg-1.3.4.tar.gz: source package
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:- ssimp-1.1.4.tar.gz: source package
- ssimp-1.1.4-1.i386.rpm: binary RPM package for i386 GNU/Linux
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:A. Carzaniga
and A.L. Wolf
"Forwarding in a Content-Based Network".
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.