/ 
Net-IPAM-Tree-2.10
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([$error_cb])

Create Net::IPAM::Tree object.

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

The only optional argument is a coderef for an error handler. With no error callback "insert" just calls carp() on duplicate items.

The error callback gets the duplicate block as argument.

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. To shut up the warnings on duplicate items, define your own error callback in the constructor.

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

contains($thing)

Returns the outermost block if the given $thing (Net::IPAM::IP or Net::IPAM::Block) is contained in the tree or undef.

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);

contains_not_equal($thing)

Reports whether the given $thing (Net::IPAM::IP or Net::IPAM::Block) is truly contained (not equal) in any child of the node.

Returns the outermost containing block or undef.

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";

lookup_not_equal($thing)

Returns Net::IPAM::Block with longest prefix match (but not equal) 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.

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 in depth first pre-order.

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

For every node Net::IPAM::Tree::Node the callback function 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        if $max_d < $depth;

  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

Just for convenience, "len" returns the number of blocks in the tree, implemented as a simple "walk" callback.

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-2021 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.