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 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 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 + 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

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

cpanm Net::IPAM::Tree

perl -MCPAN -e shell
install Net::IPAM::Tree