Classification Documentation

This page contains the Classification Package documentation.

The prefixset Module

Module providing operations with sets of prefixes.

class netbench.classification.prefixset.PrefixSet

Bases: object

Class for operations with sets of prefixes

add_prefix(prefix)

Adds one prefix into the PrefixSet. Prefixes are kept sorted by length. If you add something other than Prefix, it’s appended to the end.

prefix: Prefix or MaskedInt to be added into the PrefixSet.

add_prefix_fast(prefix)

Adds one prefix into the PrefixSet. Prefixes are NOT kept sorted by length. Added prefix is simply appended to the end.

prefix: Prefix or MaskedInt to be added into the PrefixSet.

add_range(r_from, r_to, domain_size)

Add range to the PrefixSet. Range will be converted to the form of prefixes and these will be added to the existing ones in the set.

r_from: Lower bound of the range (including this value). r_to: Higher bound of the range (including this value). domain_size: Number of bits of the domain.

clear()
Clears the PrefixSet to contain no prefix.
covers(other)

Return True if prefixset fully covers another prefixset.

other: Prefixset that we want to cover.

display(format='')

Print all prefixes in human-readable format.

format: Format of printing. Possible values: ‘ipv4_prefix’, ‘ipv6_prefix’, ‘range’, ‘value’, ‘’ (‘’ - use previously set format, if none is set, guess from domain_size)

get_histogram()
Return histogram of prefixes Histogram is an array in range <0, (max_domain_size + 1)> histogram[i] contains count of prefixes with length i
get_mean_length()
Return mean length of prefixes
get_nesting(p)
Compute number of prefixes covering p (not including p)
get_prefixes()
Return the list of all prefixes.
is_universal()
Return true if all prefixes are universal.
match(ip)

Return list of all matching prefixes. The list is sorted by length from the longest to shortest. Return empty list if ip matches no prefix.

ip: value to compare with

match_bool(ip)

Return True if ip matches any prefix, False if it matches no prefix. (Fastest if you don’t care about the value of the prefix.)

ip: value to compare with

match_longest(ip)

Return the longest matching prefix, if ip matches some prefix. Return None if ip matches no prefix.

ip: value to compare with

remove_prefix(prefix)
Removes specific prefix from prefixset
set_display_format(format)
Set format in which prefixes are displayed. Possible values are: ‘prefix’, ‘prefix6’, ‘range’, ‘value’
set_prefixes(prefixes)

Set the PrefixSet to contain given prefixes. Delete previous prefixes.

prefixes: list of prefixes. Will be automatically sorted and checked for duplicates.

set_range(r_from, r_to, domain_size)

Set the PrefixSet to cover the given continous range by prefixes. All necessary prefixes will be generated and added.

r_from: Lower bound of the range (including this value). r_to: Higher bound of the range (including this value). domain_size: Number of bits of the domain.

sortbinary()
Sort prefixes - according to their binary notation in alphabetical order Used in LPM algorithm LC-Trie

The prefix Module

Module providing basic operations with prefixes.

class netbench.classification.prefix.Prefix(domain_size, value, length=None, mask=None, display_format='')

Bases: netbench.classification.maskedint.MaskedInt

Class for basic operations with prefixes of arbitrary length (IP or other). It’s subclass of MaskedInt.

get_binary()
Returns prefix in binary notation as a string
get_length()
Return length of prefix in bits.
get_range()
Return list of [low, high] bounds of the range defined by the prefix, bounds included. Untested for 128-bit domain.
set_length(length)
Set length of the prefix in bits. Zero is valid value, meaning that the prefix matches any IP.
set_mask(mask)

Set mask of Prefix. Length is recomputed to correspond to the new mask.

mask: int or long, must be a valid mask of prefix

The range_bv Module

class netbench.classification.range_bv.RangeBV(start_value, end_value, domain_size)

Bases: netbench.classification.range.Range

Range which has bitvector (list, its length is equal of number of rules) It’s subclass of Range

has_bitvector()
has_pointers()

The ruleset Module

Module providing operations with packet classification ruletets.

class netbench.classification.ruleset.RuleSet

Bases: object

Class for the set of Rules

add_rule(rule, check=False)

Add Rule into RuleSet.

rule: Instance of the Rule class. check: Add only rules that are not covered by any of existing rules.

add_universal_prefixes(fields=None)

Add zero-length prefix for every unused field in all rules, so every rule will define a condition for all fields.

fields: you can provide a list of field names to use, otherwise it’s
get by calling get_field_names() method
classify(packetheader)

Return list of rules matching the packet. The list is sorted by priority, higest priority is first. If no rule matches the packet, empty list is returned.

packetheader: instance of PacketHeader class.

classify_bool(packetheader)

Return True if packet matches any rule, False if it matches no rule.

packetheader: instance of PacketHeader class.

classify_first(packetheader)

Return the first matching rule. Return None if no rule matches.

packetheader: instance of PacketHeader class.

clear()
Delete all rules.
count_rules()
Return number of rules in the ruleset.
del_rule(index)

Delete rule at the given index.

index: Index of rule, rules are ordered by priority, highest priority first

display()
Print all rules in a human-readable format.
expand_prefixsets()
Convert all rules into the form where they contains only single prefix in each condition. (No sets of prefixes)
expand_pseudorules()

Add rules into ruleset, such that every possible LPM combination is covered by some rule.

Every rule should define a condition for all fields (add_universal_prefixes() method).

Ruleset should already contain only one-prefix conditions (expand_prefixsets() method).

Also user will probably want to remove universal rule from the ruleset before calling this method.

get_field_names(fieldtype='')

Return list of names of all fields used in the ruleset.

fieldtype: Return only fields of specified type (given as string,
eg. “RuleSet”)
get_index_of_rule(priority)
Return rule with given priority
get_prefixes(fields=None)

Create a list of all prefixes that appears in the ruleset.

Return dictionary containing a PrefixSet for every field.

fields: you can provide a list of field names to use, otherwise it’s
get by calling get_field_names() method
get_rule(index)

Get the rule at the given index.

index: Index of rule, rules are ordered by priority, highest priority first

get_rules()
Get list of all rules.
is_rule_with_given_priority(priority)
Return true if rule with given priority exists in the ruleset
remove_covered()
Remove rules that are fully covered by some other rule with higher or same priority (it also removes duplicates).
remove_duplicates()
If there are more rules same but the priority, keep only the one with highest priority (lowest number)
remove_spoilers(count)

Detect rules that generate excessive number of pseudorules. These rules are removed from the ruleset, and returned as a list.

count: Number of rules to be removed.

netbench.classification.ruleset.cond2field(cond)
Return array of tuples containing name of header and field, where a value of given condition can be found in packet, and it’s type

The rule Module

Module providing operations with packet classification rules.

class netbench.classification.rule.Rule

Bases: object

Class representing one classification rule.

compute_conditions_hash()
Precompute and store hash of rule’s conditions (not priority).
covers(other, allow_same_priority=True, has_same_conds=False)

Return True if rule fully covers another rule.

other: Rule that we want to compare

allow_same_priority: Do not require different priorities

has_same_conds: set to True to skip check for same rule conditions

display()
Print rule in a human-readable format.
expand_prefixsets()
Return list of rules, covering the same area as the original rule, but each rule contains only one prefix in each condition. (No sets of prefixes)
get_all_conditions()
Get all conditions of the rule in the dictionary.
get_condition(name)

Get the condition for one packet header field. Return None if the condition for the given field doesn’t exist.

name: Name of packet header field.

get_priority()
Get the priority of the rule.
get_pseudo()
Return True if rule is pseudorule.
get_sorting_priority()
get_target()
Get pointer to correct rule in case this is pseudorule.
is_universal()
Return True if rule is universal (matches all packets)
match(packetheader)

Return True if packet satisfies all conditions of the rule.

packetheader: instance of the PacketHeader class.

same_but_priority(other)
Return true if two rules are same, except for they may have the same priority.
set_condition(name, value)

Set the rule condition for one packet header field.

name: Name of the packet header field. Currently supported header fields: srcipv4, dstipv4, protocol, src_port, dst_port

value: Condition on the packet header field. It should be PrefixSet.

set_priority(priority)
Set the priority of the rule. Lower number means higher priority, 0 is the highest of all.
set_pseudo(val)
Set whether rule is pseudorule.
set_target(target)
Set pointer to correct rule in case this is pseudorule.
netbench.classification.rule.cross_lists(lists)

Recursive function returns crossproduct of all items from all lists. Result is a list of lists.

lists: list of lists of items to be crossproducted.

The prefix_coloured Module

Module providing extensions to the original Prefix class.

class netbench.classification.prefix_coloured.PrefixColoured(domain_size=32)

Bases: netbench.classification.prefix.Prefix

Derived class extending original Prefix class. Allows to add some specific information to the prefix object. This class is used in Prefix Coloured Crossproduct Algorithm.

get_bitmaps()
Return set of bitmaps for this prefix.
get_colour()
Return color number of this prefix
get_condition()
set_bitmaps(bitmaps)
Set bitmap information for this prefix, new bitmaps will be assigned to the attribute _bitmap_set
set_colour(colour)
Assign color for this prefix
set_condition(condition)

The common Module

Module with some common functions. Currently, only function for extracting fields from packet header is implemented.

exception netbench.classification.common.BadPacketError
Bases: exceptions.Exception
exception netbench.classification.common.FieldNotFoundError
Bases: exceptions.Exception
exception netbench.classification.common.UnknownFieldError
Bases: exceptions.Exception
netbench.classification.common.extract_field(header, field_name)

Extracts value of specified filed from given packet header. If the name of field is unknown, an UnknownFieldError exception is raised. If the field is not present in packet header, a FieldNotFoundError exception is raised.

header - Instance of PacketHeader, in which the field will be looked for.

field_name - string, name of filed to extract. Possible values:
srcipv4 dstipv4 src_port dst_port protocol tcpflags

The range Module

class netbench.classification.range.Range(start_value, end_value, domain_size)

Bases: object

Represents IP/Port in range format

covers(interval)
Return True if range fully covers another range(interval).
display(format='')

The maskedint Module

Module providing basic operations with values with mask.

class netbench.classification.maskedint.MaskedInt(value, mask=None, domain_size=None, display_format='')

Bases: object

Class for basic operations with values of arbitrary length with a bitmask (usually prefixes).

covers(other)

Return True if the MaskedInt fully covers another MaskedInt, given as parameter (ie. if every possible value of other is also possible value of this).

other: MaskedInt that we want to compare.

display(format='')

Print prefix in human-readable format, without newline

format: Format of printing. Possible values: ‘ipv4_prefix’, ‘ipv6_prefix’, ‘range’, ‘value’, ‘’ (‘’ - use previously set format, if none is set, guess from domain_size)

get_data()
Return data as tuple (value,mask).
get_display_format()
Get format in which prefix is displayed.
get_domain_size()
Get number of bits of the domain.
get_mask()
Return mask of MaskedInt.
get_value()
Return value of MaskedInt.
is_universal()
Return true if MaskedInt is universal (matches every value).
match(value)

Return True if valid bits of given value matches the value of MaskedInt.

value: list of numbers, one number for each 32bits, value[0] is MSB.

set_data(value, mask)

Set value and mask of MaskedInt.

value: int or long mask: int or long

set_display_format(format)
Set format in which prefix is displayed. Possible values are: ‘ipv4_prefix’, ‘ipv6_prefix’, ‘range’, ‘value’
set_domain_size(size)
Set number of bits of the domain.
set_mask(mask)

Set mask of MaskedInt.

mask: int or long

set_value(value)

Set value of MaskedInt.

value: int or long

netbench.classification.maskedint.is_prefix_mask(x, width)
netbench.classification.maskedint.leftmost_one(x)
netbench.classification.maskedint.log2(num)
Return base-two logarithm of the number (rounded up).
netbench.classification.maskedint.rightmost_one(x)