/ 
Net-IPAM-Tree-1.05
River stage zero No dependents
/ Net::IPAM::Tree

NAME

Net::IPAM::Tree - A CIDR/Block tree library for fast IP lookup with longest-prefix-match.

DESCRIPTION

A module for fast IP-routing-table lookups and IP-ACLs (Access Control Lists).

It is NOT a standard patricia-trie implementation. This isn't possible for general blocks not represented by bitmasks, every tree item is a Net::IPAM::Block.

The complexity for tree operations is in worst case O(h * log n) with h <= 128 (IPv6) or h <=32 (IPv4).

SYNOPSIS

use Net::IPAM::Tree;

my $t = Net::IPAM::Tree->new();

$t->insert(@blocks) || die("duplicate block...");
$t->remove($block)  || warn("block not in tree...");

my $block = $t->lookup($ip_or_block)
  && printf( "longest-prefix-match in tree for %s is %s\n", $ip_or_block, $block );

$t->contains($ip_or_block)
  && printf( "ip or block %s is contained in tree\n", $ip_or_block );

say $t->to_string;

▼
├─ ::/8
├─ 100::/8
├─ 2000::/3
│  ├─ 2000::/4
│  └─ 3000::/4
├─ 4000::/3
...

METHODS

new

Create Net::IPAM::Tree object.

my $t = Net::IPAM::Tree->new;

insert

Insert block(s) into the tree. Inserting a bulk of blocks is much faster than inserting unsorted single blocks in a loop.

Returns the tree object on success for method chaining.

my $t = Net::IPAM::Tree->new->insert(@blocks) // die("one or more blocks are duplicate");;

Returns undef on duplicate blocks in the tree and generate warnings (warnings can be disabled).

{
  no warnings 'Net::IPAM::Tree';
  $t->insert($dup)
}

contains($thing)

Returns true if the given $thing (Net::IPAM::IP or Net::IPAM::Block) is contained in any block of the tree. Just returns true or false and not the matching prefix, this is much faster than a full lookup for the longest-prefix-match.

This can be used for fast ACL lookups.

# make blocks
my @deny = map { Net::IPAM::Block->new($_) } qw(2001:db8::-2001:db8::1234:ffea fe80::/10);

# make tree
my $deny = Net::IPAM::Tree->new->insert(@deny) or die;

my $ip = Net::IPAM::IP->new( get_ip_from($some_request) );
say "request forbidden for $ip" if $deny->contains($ip);

lookup($thing)

Returns Net::IPAM::Block with longest prefix match for $thing (Net::IPAM::IP or Net::IPAM::Block) in the tree, undef if not found.

This can be used for fast routing table lookups.

# make blocks
my @priv = map { Net::IPAM::Block->new($_) } qw(10.0.0.0/8 172.16.0.0/12 192.168.0.0 fc00::/7);

# make tree
my $priv = Net::IPAM::Tree->new->insert(@priv) or die;

my $b = Net::IPAM::Block->new('fdcd:aa59:8bce::/48') or die;

my $lpm = $priv->lookup($b)
  && say "longest-prefix-match for $b is $lpm";

remove

Remove one block from tree, relink parent/child relation at the gap.

$t->remove($block) // warn("block not found");

Returns undef if $block is not found.

remove_branch

Remove $block and the branch below from tree.

$t->remove_branch($block) // warn("block not found");

Returns undef if $block is not found.

to_string

Returns the tree as ordered graph or undef on empty trees.

$t->to_string($callback);

The optional callback is called on every block. Returns the decorated string for block.

$t->to_string( sub { my $block = shift; return decorate($block) } );

example (without callback):

▼
├─ ::/8
├─ 100::/8
├─ 2000::/3
│  ├─ 2000::/4
│  └─ 3000::/4
├─ 6000::/3

possible example (with callback):

▼
├─ ::/8.................   "Reserved by IETF     [RFC3513][RFC4291]"
├─ 100::/8..............   "Reserved by IETF     [RFC3513][RFC4291]"
├─ 2000::/3.............   "Global Unicast       [RFC3513][RFC4291]"
│  ├─ 2000::/4.............  "Test"
│  └─ 3000::/4.............  "FREE"
├─ 6000::/3.............   "Reserved by IETF     [RFC3513][RFC4291]"

walk

Walks the tree starting at root node in depth first order.

my $err_string = $t->walk($callback);

For every node Net::IPAM::Tree::Node the callback funtion is called with the node and the current depth (counting from 0) as arguments.

my $err_string = $callback->($node, $depth);

The callback must return undef if there is no error! On error, the walk is stopped and the error is returned to the caller.

Example, get some tree statistics:

my ( $n, $max_d, $max_c ) = ( 0, 0, 0 );

my $cb = sub {
  my ( $node, $depth ) = @_;

  $n++;
  $max_c = $node->childs if $max_c < $node->childs;
  $max_d = $depth + 1    if $max_d < $depth + 1;

  return;    # explicit return (undef) if there is no error!
};

my $err = $t->walk($cb);
say "tree has $n nodes and is $max_d levels deep, the number of max childs/node is $max_c" unless $err;

len

Returns the number of blocks in the tree.

AUTHOR

Karl Gaissmaier, <karl.gaissmaier(at)uni-ulm.de>

SUPPORT

You can find documentation for this module with the perldoc command.

perldoc Net::IPAM::Tree

You can also look for information at:

  • on github

    TODO

SEE ALSO

Net::IPAM::Tree::Node Net::IPAM::IP Net::IPAM::Block

LICENSE AND COPYRIGHT

This software is copyright (c) 2020 by Karl Gaissmaier.

This is free software; you can redistribute it and/or modify it under the same terms as the Perl 5 programming language system itself.