Blooming

Two paragraph summary goes here

See Projects:AirFPGA as an example.

Show Contents...Hide Contents...

Project summary

Status

Release pending:

; Version: 1.0

Authors

; Hardware: Cristian Vairo

Software

Gianni Antichi :

; Demonstration: Gianni Antichi NetFPGA base source: 1.2.5: ; Wordpress Page

Blooming Tree

Background

Because of the rapid growth of both traffic and links capacity, the time budget to perform IP address lookup on a packet continues to decrease and lookup tables of routers unceasingly grow. Therefore, new lookup algorithms and new hardware platform are required. This solution presents a new scheme on top of the NetFPGA board which takes advantage of parallel queries made on perfect hash functions. Such functions are built by using a very compact and fast data structure called Blooming Trees, thus allowing the vast majority of memory accesses to involve small and fast on-chip memories only.

Features

• Use of an array of Blooming Tree.
• Blooming Tree is a new scheme to construct a Minimal Perfect Hash Function (MPHF) based on an alternative to Bloom Filters.
• We use a MPHF for each prefix length greater than 15.
• We use a single Direct Addressing (DA) for other lengths.
• When packet arrives, checks all the MPHFs and DA at the same time.
• The Forwading Table is stored in Block RAM and in SRAM.
• Up to 130.000 entries

Download

Install from NetFPGA Yum repository

1. Install the NetFPGA Base Package

Obtain Project Tarball

Download from [5]

Regression Tests

The regression tests verify the functionality of this project. In order to run the tests, you need to have the machine connected for the regression tests as stated in the Run Regression Tests section of the Guide.

After connecting the cables. Run the following command to run the regression tests.

 nf21_regress_test.pl --project yourprojectname

Regression Tests

Test 1: Example

Name

test_packet_generator

Description

Load test data on NetFPGA's SRAM, trigger the DSP simulator onboard, verify the data packets at eth1
# Initialize netfpga hardware
# Load data onto NetFPGA's SRAM, set parameters for packet generator (Src/Dst IP, Src/Dst MAC, Src/Dst UDP port)
# Trigger DSP simulator. The simulator will feed AirFPGA's packet generator.
# Verify the data packets at eth1 $ Location

projects/airfpga/regress/test_packet_generator $ Output

 SUCCESS!

Usage

Preparation

• Explain how to prepare your machine for a demonstration

Installation

• Describe how to install your tools

NetFPGA source package

1. Download project bitfile:

 nf2_download yourbitfile.bit

Testbed Setup

Data Path

Examples

Related Work

Original Source

Two paragraph summary goes here

See [[Projects:AirFPGA]] as an example.

== Project summary ==

; Status: Release pending
; Version: 1.0
; Authors
; Hardware: [mailto:cristian.vairo@gmail.com Cristian Vairo] 
; Software: [mailto:antichi@netserv.iet.unipi.it Gianni Antichi] 
; Demonstration: [mailto:antichi@netserv.iet.unipi.it Gianni Antichi] 
; NetFPGA base source: 1.2.5
; Wordpress Page
: [http://netfpga.org/wordpress/blooming/ Blooming Tree]

== Background ==

Because of the rapid growth of both traffic and links capacity, the time budget to perform IP address lookup on a packet continues to decrease and lookup tables of routers unceasingly grow. Therefore, new lookup algorithms and new hardware platform are required. This solution presents a new scheme on top of the NetFPGA board which takes advantage of  parallel queries made on perfect hash functions. Such functions are built by using a very compact and fast data structure called Blooming Trees, thus allowing the vast majority of memory accesses to involve small and fast on-chip memories only.

== Features ==

* Use of an array of Blooming Tree.
* Blooming Tree is a new scheme to construct a Minimal Perfect Hash Function (MPHF) based on an alternative to Bloom Filters.
* We use a MPHF for each prefix length greater than 15.
* We use a single Direct Addressing (DA) for other lengths.
* When packet arrives, checks all the MPHFs and DA at the same time.
* The Forwading Table is stored in Block RAM and in SRAM.
* Up to 130.000 entries

== Download ==

=== Install from NetFPGA Yum repository ===
#Install the [http://netfpga.org/netfpgawiki/index.php/Guide#Install_NetFPGA_Base_Package NetFPGA Base Package]

=== Obtain Project Tarball === 
Download from [[http://www.yourwebsite.edu/project]]

== Regression Tests ==

The regression tests verify the functionality of this project.  In order to run the tests, you need to have the machine connected for the regression tests as stated in the [http://netfpga.org/netfpgawiki/index.php/Guide#Run_Regression_Tests Run Regression Tests] section of the Guide.

After connecting the cables. Run the following command to run the regression tests.

 nf21_regress_test.pl --project yourprojectname

=== Regression Tests === 

====Test 1: Example ====
:; Name: test_packet_generator
:; Description: Load test data on NetFPGA's SRAM, trigger the DSP simulator onboard, verify the data packets at eth1
::# Initialize netfpga hardware
::# Load data onto NetFPGA's SRAM, set parameters for packet generator (Src/Dst IP, Src/Dst MAC, Src/Dst UDP port)
::# Trigger DSP simulator. The simulator will feed AirFPGA's packet generator.
::# Verify the data packets at eth1
:; Location
projects/airfpga/regress/test_packet_generator
:; Output
 SUCCESS!

== Usage ==

=== Preparation ===
* Explain how to prepare your machine for a demonstration

==== Installation  ====
* Describe how to install your tools

==== NetFPGA source package ====
# Download project bitfile:
 nf2_download yourbitfile.bit

=== Testbed Setup ===

==== Data Path ====

==== Examples ====

== Related Work ==