Content-Based Forwarding
links

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.

this page is maintained by Antonio Carzaniga and was updated on January 18, 2016