This page contains the Algorithms Package documentation.
Module for LPM algorithm Lulea Compressed Tries.
Bases: netbench.lpm.algorithms.blpm.BLPM
LPM algorithm Lulea Compressed Tries for lookup prefixes.
Lookup prefix that match ip. Return matched prefix. If ip match no prefix then None will be returned
ip: value to compare with
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.
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.
Module for LPM algorithm Controlled Prefix Expansion.
Bases: netbench.lpm.algorithms.blpm.BLPM
LPM algorithm Controlled Prefix Expansion for lookup prefixes.
Lookup prefix that match ip. Return matched prefix. If ip match no prefix then None will be returned
ip: value to compare with
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.
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.
Module for LPM algorithm binary search on intervals.
Bases: netbench.lpm.algorithms.blpm.BLPM
Class for LPM algorithm binary search on intervals.
Lookup prefix that match ip. Return the matched prefix. If ip match no prefix, then None will be returned.
ip: value to compare with
Module for unibit Trie LPM algorithm
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
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
Bases: netbench.lpm.algorithms.blpm.BLPM
Trie LPM algorithm for lookup prefixes
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
Module for shape-shifting trie LPM algorithm
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.
Bases: netbench.lpm.algorithms.blpm.BLPM
Shape-shifting trie LPM algorithm for lookup prefixes
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
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
Module for ‘binary search on prefixes’ LPM algorithm.
Bases: netbench.lpm.algorithms.blpm.BLPM
Binary Search on Prefixes LPM algorithm for lookup prefixes.
Lookup prefix that match ip. Return the matched prefix or None if we did not find anyone.
ip: value to compare with
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.
Module for Tree-bitmap LPM algorithm
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
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
Bases: netbench.lpm.algorithms.blpm.BLPM
Tree Bitmap algorithm for lookup prefixes
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
Module for multi-match LPM algorithm
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
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
Module for LC-Trie algorithm
Bases: netbench.lpm.algorithms.blpm.BLPM
LC-Trie LPM algorithm for lookup prefixes
Load prefixes and generate all necessary data structures.
Note that it changes prefixset - it removes prefixes, which are prefixes of other (longer) prefixes
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
Bases: object
Common class necessary for the class Trie
Bases: object
List of prefixes, which are prefixes of other (longer) prefixes. These were removed from the prefixset
Bases: object
Entry in prefix table. Represents a prefix of other (longer) prefix. These prefixes are removed from prefixset
Bases: object
Trie consists of Nodes and represents the whole tree in which will be looking up the prefixes
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
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
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)
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 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.
Module providing abstract class for all LPM algorithms.
Bases: object
Base abstract class for all LPM algorithms.
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
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
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
Module with Hash Tree Bitmap LPM algorithm
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))
Bases: object
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
Bases: object
Bases: object