Algorithms Documentation

This page contains the Algorithms Package documentation.

The lulea Module

Module for LPM algorithm Lulea Compressed Tries.

class netbench.lpm.algorithms.lulea.LULEA(n=3)

Bases: netbench.lpm.algorithms.blpm.BLPM

LPM algorithm Lulea Compressed Tries for lookup prefixes.

display()
Display the structure of the tree.
load_prefixset(prefixset)
Load prefixes and generate all necessary data structures.
lookup(ip)

Lookup prefix that match ip. Return matched prefix. If ip match no prefix then None will be returned

ip: value to compare with

report_memory()
Print detailed info about algorithm memory requirements.
class netbench.lpm.algorithms.lulea.Node(n)

Bases: object

Common class necessary for the class Tree and LULEA. Value is reference to the Prefix or reference to next node. Bitmap is structure where are indicates omit element (prefix). pom represent list where is stored if value is prefix or reference on next node.

class netbench.lpm.algorithms.lulea.Tree(n)

Bases: object

Common class necessary for the class LULEA. It consists of Nodes and represents the whole tree in which will be looking up the prefixes.

add_prefix(key, value)
Add prefix into tree. New Nodes will be created if needed. key is prefix in the binary notation. value is reference to the Prefix.

The cpe Module

Module for LPM algorithm Controlled Prefix Expansion.

class netbench.lpm.algorithms.cpe.CPE(n=3)

Bases: netbench.lpm.algorithms.blpm.BLPM

LPM algorithm Controlled Prefix Expansion for lookup prefixes.

display()
Display the structure of the tree.
load_prefixset(prefixset)
Load prefixes and generate all necessary data structures.
lookup(ip)

Lookup prefix that match ip. Return matched prefix. If ip match no prefix then None will be returned

ip: value to compare with

report_memory()
Print detailed info about algorithm memory requirements.
class netbench.lpm.algorithms.cpe.Node(n=3)

Bases: object

Common class necessary for the class Tree and CPE. Key is list of numbers from 0 to (2**n - 1) in binary scheme. Value is reference to the Prefix or reference to next node. pom represent list where is stored if value is prefix or reference on next node.

class netbench.lpm.algorithms.cpe.Tree(n=3)

Bases: object

Common class necessary for the class CPE. It consists of Nodes and represents the whole tree in which will be looking up the prefixes.

add_prefix(key, value)
Add prefix into tree. New Nodes will be created if needed. key is prefix in the binary notation. value is reference to the Prefix.

The bsi Module

Module for LPM algorithm binary search on intervals.

class netbench.lpm.algorithms.bsi.BSI

Bases: netbench.lpm.algorithms.blpm.BLPM

Class for LPM algorithm binary search on intervals.

display()
Display the table of address|prefix.
load_prefixset(prefixset)
Load prefixes and generate all necessary data structures.
lookup(ip)

Lookup prefix that match ip. Return the matched prefix. If ip match no prefix, then None will be returned.

ip: value to compare with

report_memory()
Print detailed info about algorithm memory requirements.

The trie Module

Module for unibit Trie LPM algorithm

class netbench.lpm.algorithms.trie.Node(key='', value=None)

Bases: object

Common class necessary for the class Trie Key is the path from root to the current node in the binary notation Value is reference to the Prefix if any Each Node can have two child - lchild and rchild

class netbench.lpm.algorithms.trie.Tree

Bases: object

Common class necessary for the class Trie It consists of Nodes and represents the whole tree in which will be looking up the prefixes

add_prefix(key, value)
Add prefix into tree. New Nodes will be created if needed Key is prefix in the binary notation Value is reference to the Prefix
class netbench.lpm.algorithms.trie.Trie

Bases: netbench.lpm.algorithms.blpm.BLPM

Trie LPM algorithm for lookup prefixes

display()
Display the structure of the tree
load_prefixset(prefixset)
Load prefixes and generate all necessary data structures.
lookup(ip)

Lookup prefixes that match ip. Return the list of matched prefixes. If ip matches no prefix, the list will be empty.

ip: value of the ip address according to maskedint.py

report_memory()
Return detailed info about algorithm memory requirements.

The sst Module

Module for shape-shifting trie LPM algorithm

class netbench.lpm.algorithms.sst.SSNode

Bases: object

Common class necessary for the class SST It is one node in SSTree. It contains 3 bitmaps(SBM,IBM,EBM) which describe the node.

class netbench.lpm.algorithms.sst.SST(K=3)

Bases: netbench.lpm.algorithms.blpm.BLPM

Shape-shifting trie LPM algorithm for lookup prefixes

count_nodes(node=None)
Count the nodes in every subtree of the tree
display(node)
Display the structure of the tree
left_most(node, stack, stackB)
Traverse to the left most node of current branch
load_prefixset(prefixset)
Load prefixes and generate all necessary data structures.
lookup(ip)

Lookup prefixes that match ip. Return the list of matched prefixes. If ip matches no prefix, the list will be empty.

ip: value of the ip address according to maskedint.py

make_SSNode(root, tree_list)
Create SSNode from a (unibit trie) subtree
prepare_bfs(node=None)
Order the nodes of the subtree in breadth-first order
report_memory()
Return detailed info about algorithm memory requirements.
class netbench.lpm.algorithms.sst.SSTree(K=3)

Bases: object

Common class necessary for the class SST It consists of SSNodes and represents the whole tree in which will be looking up the prefixes

The bsp Module

Module for ‘binary search on prefixes’ LPM algorithm.

class netbench.lpm.algorithms.bsp.BSP

Bases: netbench.lpm.algorithms.blpm.BLPM

Binary Search on Prefixes LPM algorithm for lookup prefixes.

display()
Display the structure of the tree.
load_prefixset(prefixset)
Load prefixes and generate all necessary data structures.
lookup(ip)

Lookup prefix that match ip. Return the matched prefix or None if we did not find anyone.

ip: value to compare with

report_memory()
Print detailed info about algorithm memory requirements.
class netbench.lpm.algorithms.bsp.Node

Bases: object

Common class necessary for the class BSP(bsp tree). ‘length’ is length of prefix stored in this node. ‘prefixes’ is list where are the prefixes(in binary notation) with length ‘length’. ‘prefixes_index’ is list of indexes to true location(of prefix) in prefixset. ‘prefixes_mark’ is list of True|False, caring on longer prefix exist. ‘marks’ is list of longer prefixes in binary notation. ‘marks_lpm’ is list of LPM(indexes to prefixset) for ‘marks’. Each Node can have two child - lchild and rchild.

The treebitmap Module

Module for Tree-bitmap LPM algorithm

class netbench.lpm.algorithms.treebitmap.Node(stride=3)

Bases: object

Common class necessary for the class TreeBitmap The size of the Node (count of prefixes and children, size if bitmaps)

depends on stride

parent is reference on the parent-node child_bitmap is a bitmap of the children-nodes prefix_bitmap is a bitmap of the valid prefixes in the node children contains reference on the children nodes prefixes contains reference on the valid prefixes in the node children and prefixes contains values in format : (priority, reference)

because they allways have to be sorted and with no gaps between the items
class netbench.lpm.algorithms.treebitmap.Tree(stride=3)

Bases: object

Common class necessary for the class TreeBitmap It consists of Nodes and it represents the whole tree in which will be looking up the prefixes

add_prefix(key, value)
Add prefix into tree. New Nodes will be created if needed Key is prefix in the binary notation Value is reference to the Prefix
class netbench.lpm.algorithms.treebitmap.TreeBitmap(stride=3)

Bases: netbench.lpm.algorithms.blpm.BLPM

Tree Bitmap algorithm for lookup prefixes

display(node)
Display the structure of the tree
load_prefixset(prefixset)
Load prefixes and generate all necessary data structures.
lookup(ip)

Lookup prefixes that match ip. Return the list of matched prefixes. If ip matches no prefix, the list will be empty.

ip: value of the ip address according to maskedint.py

report_memory()
Return detailed info about algorithm memory requirements.

The multimatch Module

Module for multi-match LPM algorithm

class netbench.lpm.algorithms.multimatch.MultiMatch(class_count=4, variant=1, mask=[])

Bases: netbench.lpm.algorithms.blpm.BLPM

Multi-match LPM algorithm for lookup prefixes Prefixes from prefixset will be sorted into classes Count of classes and sorting method can be set as a parameter

display()
Display the structure of the tree
load_prefixset(prefixset)
Load prefixes and generate all necessary data structures.
lookup(ip)

Lookup prefixes that match ip. Return the list of matched prefixes. If ip matches no prefix, the list will be empty.

ip: value of the ip address according to maskedint.py

report_memory()
Return detailed info about algorithm memory requirements.
netbench.lpm.algorithms.multimatch.expand(prefix='', n=8)
Expand the prefix to n bits

The lctrie Module

Module for LC-Trie algorithm

class netbench.lpm.algorithms.lctrie.LCTrie

Bases: netbench.lpm.algorithms.blpm.BLPM

LC-Trie LPM algorithm for lookup prefixes

build_prefix_table()
Finds prefixes of other prefixes, remove them from prefixset and add them into the prefix table, because these are not going to be in the trie.
display()
Display the structure of the tree
load_prefixset(prefixset)

Load prefixes and generate all necessary data structures.

Note that it changes prefixset - it removes prefixes, which are prefixes of other (longer) prefixes

lookup(ip)

Lookup prefixes that match ip. Return the list of matched prefixes. If ip matches no prefix, the list will be empty.

ip: value of the ip address according to maskedint.py

report_memory()
Return detailed info about algorithm memory requirements.
class netbench.lpm.algorithms.lctrie.Node(branch, skip, adr)

Bases: object

Common class necessary for the class Trie

reinit(branch, skip, adr)
class netbench.lpm.algorithms.lctrie.Prefix_table

Bases: object

List of prefixes, which are prefixes of other (longer) prefixes. These were removed from the prefixset

append(prefix)
Add a prefix to the prefix table
class netbench.lpm.algorithms.lctrie.Prefix_table_entry(prefix, pointer=-1)

Bases: object

Entry in prefix table. Represents a prefix of other (longer) prefix. These prefixes are removed from prefixset

class netbench.lpm.algorithms.lctrie.Trie(prefixset)

Bases: object

Trie consists of Nodes and represents the whole tree in which will be looking up the prefixes

build(first, n, pre, pos)

Used to build LC-Trie. Build part of trie - use “n” prefixes in prefixset, starting at prefix “first”, “pre” bits of these prefixes are not considered. “pos” is index of first free position in the table representing the trie

This is called recursively

checkBranch(branch, pre, first, n, skip)

Check if the “n” prefixes in prefixset, starting at prefix “first” with skip value “skip” can have branching factor “2^branch”. “pre” bits of these prefixes are not considered.

Return “branch” if it is possible, otherwise return 0

computeBranch(pre, first, n, skip)

Compute branching factor for the “n” prefixes in prefixset, starting at prefix “first” with skip value “skip”. “pre” bits of these prefixes are not considered.

Return “branch” (branching factor is 2^branch)

computeSkip(pre, first, n)

Compute skip value for the “n” prefixes in prefixset, starting at prefix “first” “pre” bits of these prefixes are not considered.

Return skip value

display(actual_node, depth, branch, skip)

Display the structure of the tree

Displays the trie starting at the actual node to the depth passed by argument. Branch represents how many children the actual node has and skip represents the skip value of the actual node.

extract(pos, n, vector)
Extract “n” bits from prefix “vector”, starting at position “pos” Return extracted string
get_table()
Print table representation of the trie [branch skip pointer]

The blpm Module

Module providing abstract class for all LPM algorithms.

class netbench.lpm.algorithms.blpm.BLPM

Bases: object

Base abstract class for all LPM algorithms.

check(ip)

Return True if LPM algorithm result is correct. It checks list of all prefixes that match

ip: value of the ip address according to maskedint.py

check_longest(ip)

Return True if LPM algorithm result is correct. It checks only the longenst prefix that match

ip: value of the ip address according to maskedint.py

load_prefixset(prefixset)
Load prefixes and generate all necessary data structures. Abstract method.
lookup(ip)

Lookup prefixes that match ip. Abstract method. Return the list of matched prefixes. If ip matches no prefix, the list will be empty.

ip: value of the ip address according to maskedint.py

report_memory()
Print detailed info about algorithm memory requirements. Abstract method.

The hash_tbm Module

Module with Hash Tree Bitmap LPM algorithm

class netbench.lpm.algorithms.hash_tbm.HashTBM(lengths=[, 0], stride=4)

Bases: netbench.lpm.algorithms.blpm.BLPM

Hash Tree Bitmap LPM algorithm for prefix lookups Prefixes from prefixset will be divided into classes by their length Length span for classes can be configured TBM algorithm stride can also be configured (max height of TBM tree will be roundup(span/stride))

display()
Display the structure of the tree
load_prefixset(prefixset)
Load prefixes and generate all necessary data structures.
lookup(ip)
Longest prefix match lookup for IP address.
NOTE: only longest prefix (or None) is returned !!!
report_memory()
Return detailed info about algorithm memory requirements.
class netbench.lpm.algorithms.hash_tbm.Record

Bases: object

Class representing one field in hash table.
ID = prefix or TBM tree, depending on mark mark = is prefix continuing into TBM tree?
netbench.lpm.algorithms.hash_tbm.TBM_display(node)
Display the structure of the tree
netbench.lpm.algorithms.hash_tbm.TBM_lookup(tree, key)

Lookup longest prefix that match ip. Return only the longest matched prefix. If ip matches no prefix, default_LPM is returned.

ip: value of the ip address according to maskedint.py

class netbench.lpm.algorithms.hash_tbm.Table(length)

Bases: object

Class representing hash table.
len = length of table (prefix starts in table) tab = hash table data
class netbench.lpm.algorithms.hash_tbm.Tree_record(tree)

Bases: object

Class encapsulating TBM tree structure, just adding default LPM used in case that no match found within TBM.
tree = TBM tree default_LPM = result of lookup in case that no match is found in TBM