Mattia Rossi                                                                                                                                 
Centre for Advanced Internet Architectures,                                                                                                  
Swinburne University of Technology,                                                                                                          
Melbourne, Australia                                                                                                                         
CRICOS number 00111D                                                                                                                         

30th July, 2009

----------------------------------------------
OVERVIEW                                      
----------------------------------------------

Quagga Accelerator - Version 0.1

The Quagga Accelerator (QA) is a combination of a modified 
Update Regenerator (URQA) from the MDFMT and a set of 
patched Quagga's. The UR replays a recorded MRT dump file into a 
live BGP session in an accelerated time frame.
Time information is passed through a shared memory block to the 
patched Quagga. Operating speed is automatically adjusted by 
Quagga giving feedback about it's processing load through a 
second shared memory block.

For detailed usage please consult the documentation at [4].

The Quagga Accelerator Version 0.1 tarball (qa-0.1.tar.bz2)
consists of the following files and folders:

        README-quagga-accelerator
        update-regenerator-qa.py
	quagga-0.99.13-qa.patch
	quagga-git-qa.patch

	dpkt-patchset:
	    README-dpkt-patchset
	    dpkt-patchset.patch
	mrt_slice:
	    README-mrtslice
	    mrt_slice-0.1.py
	asip:
	    README-asip
	    asip.py

Please refer to the appropriate README files in the subfolders
for usage of the relative tools.

-----------------------
LICENCE                
-----------------------

The Quagga Accelerator is released under a new BSD License. For more details
please refer to the included source files.

-----------------------
USAGE                  
-----------------------

The QA needs two parts to work:
 
- the Update Regenerator (URQA) for the Quagga Accelerator, which can be executed after 
  installing the 4 byte AS number capable dpkt and pybgpdump as indicated in the 
  included README of the subfolder. For more information about the MDFMT, please consult
  the MDFMT documentation at [2].

- A patched Quagga, which accepts simulated time information from the URQA.
  Patches are available for Quagga git version and for Quagga
  version 0.99.13.

Patch Quagga version 0.99.13:

  - unpack the Quagga 0.99.13 source code
  - cd into the quagga-0.99.13 directory
  - apply the patch:
  	patch -p1 < quagga-0.99.13-qa.patch

  - compile:
  	./configure --enable-simulator;
        make;

    optional (as root): 
	make install;

Patch Quagga from git:

  - get Quagga from git via
	git clone git://code.quagga.net/quagga.git
  - cd into the quagga directory
  - apply the patch:
	patch -p1 < quagga-git-qa.patch
  - compile:
	./bootstrap.sh;
	./configure --enable-simulator;
	make;
	
    optional (as root):
        make install;


Execute the simulator by executing the UR as follows:

        ./update-regenerator-qa.py -m MRTFILE -d DestIP -a ASIPFILE -q QUAGGAFILE

MRTFILE     is the input MRT file (must contain an initial RIB update sequence).
	    Can be generated using the MRT-slice tool included. for detailed 
	    documentation please consult [2].
ASIPFILE    is a text file containing IPv4 address to AS number mappings
            of the participating routers. This needs to include information about 
	    the use of 4 byte AS numbers.
	    An entry has the form:
	    	<IP address> <AS number> <1|0>
	    where 1 means using 4 byte AS numbers and 0 means using 2 byte AS numbers.
	    This file can be generated from the input MRT file using the asip.py script
	    included. for more information about the script please consult the MDFMT
	    documentation at [2].
DestIP      is the destination IP address of the router the UR wants to connect to.
QUAGGAFILE  is a text file containing the command to execute a Qaugga bgpd instance.
	    The entries in the file need to be proper bgpd commands recognised by Quagga.
	    The minimum commnad line needed for Quagga to cooperate with the URQA is:

	    	bgpd -f <configfile> -l <ip address> -i <pidfile>  -s <syncfile>
	    
	    As the Quagga instances are executed on the same system as the URQA, they access a single
	    interface with multiple IP addresses. Quagga needs to be directed to listen to the correct
	    IP address (-l) and to load the proper configuration file (-f). Each Quagga instance needs 
	    it's own pid file (-i) and syncfile (-s) for load feedback. The patched Quagga also accepts
	    a -t option, in case the location for the faketime needs to be changed. 
	    The faketime filename is currently hardcoded in the URQA, so you need to change it there too!
	    !!Take care to pass the correct paths to the bgpd command as well as to the various files!!


----------------------
ADDITIONAL INFORMATION
----------------------

The URQA works only with a patched dpkt library which allows the use
of 4 byte AS numbers and Multiprotocol capabilities. 
The patchset is part of the Quagga Accelerator as well as the MDFMT
and should be located in folder dpkt-patchset in both cases.
The asip.py script included can generate proper AS-IP mapping files 
needed for the simulator. The script is also part of the MDFMT scripts.
The MRT-slice tool included, can create MRT dumps suitable for use with 
the simulator.
The dpkt patches, the asip.py script and the MRT-slice tool are included
in the Qaugga Accelerator. If missing they are also included in the MDFMT
which can be obtained at:

        http://caia.swin.edu.au/urp/bgp/tools.html

Refer to the various README files for more information on how to install 
dpkt and the patchset, pybgpdump and how to use the additional tools.

For a detailed documentation of the Quagga Accelerator see [4].
For the initial idea of the Quagga ACcelerator see [3].
For a detailed documentation of the MDFMT see [2].
To read more about the MRT dump format see [1].

----------------------------------------------
KNOWN LIMITATIONS
----------------------------------------------

The URQA can connect to only one peer, but can "impersonate" multiple peers. The simulator 
is experimental work and haas been created for a specific project, and tested with Python
version 2.5 and 2.6 as well as Quagga version 0.99.10 and higher. It has proven to work with MRT 
dumps produced by Quagga and Zebra (like Routeviews creates).
It uses a lot of resources, and needs a quite powerful machine to run on. A dual core processor
is strongly suggested. All tests have been performed on FreeBSD 7 and CURRENT (8 beta1).
The simulator should anyhow work without problems on Linux platforms too.

----------------------------------------------
RELATED READING
----------------------------------------------

[1] MRT dump formats draft:

        http://tools.ietf.org/html/draft-ietf-grow-mrt-08

[2] MRT dump file manipulation toolkit (MDFMT) - version 0.2
    (CAIA technical report) PDF format

        http://caia.swin.edu.au/reports/090730B/CAIA-TR-090730B.pdf

[3] Accelerated Processing of Historical BGP Events for Testing New BGP Heuristics
    (CAIA technical report) PDF format

	http://caia.swin.edu.au/reports/090321A/CAIA-TR-090321A.pdf

[4] Quagga-Accelerator: An Implementation for Accelerated Processing
    of Historical BGP Events using Quagga 0.99.13 - version 0.1
    (CAIA technical report) PDF format                              

        http://caia.swin.edu.au/reports/090730C/CAIA-TR-090730C.pdf

----------------------------------------------
ACKNOWLEDGEMENTS
----------------------------------------------

This project has been made possible in part by
a grant from the Cisco University Research Program
Fund at Community Foundation Silicon Valley