NAME
Net::IP::LPM - Perl implementation of Longest Prefix Match algorithm
SYNOPSIS
use Net::IP::LPM;
my $lpm = Net::IP::LPM->new("prefixes.db");
# add prefixes
$lpm->add('0.0.0.0/0', 'default');
$lpm->add('::/0', 'defaultv6');
$lpm->add('147.229.0.0/16', 'net1');
$lpm->add('147.229.3.0/24', 'net2');
$lpm->add('147.229.3.10/32', 'host3');
$lpm->add('147.229.3.11', 'host4');
$lpm->add('2001:67c:1220::/32', 'net16');
$lpm->add('2001:67c:1220:f565::/64', 'net26');
$lpm->add('2001:67c:1220:f565::1235/128', 'host36');
$lpm->add('2001:67c:1220:f565::1236', 'host46');
# rebuild the database
$lpm->rebuild();
printf $lpm->lookup('147.229.100.100'); # returns net1
printf $lpm->lookup('147.229.3.10'); # returns host3
printf $lpm->lookup('2001:67c:1220::1');# returns net16DESCRIPTION
The module Net::IP::LPM implements the Longest Prefix Matxh algo for both IPv4 and IPv6 protocols. Module divides prefixes into intervals of numbers and them uses range search to match proper prefix.
Module also allows to store builded database into file. It is usefull when the module is used on large database (for example full BGP tables containing over half of milion records) when initial building can take long time (a few seconds). The separate script can download and prepare prebuilded database and another one can just use the prepared database and perform fast lookups.
PERFORMANCE
The module is able to match ~ 180 000 lookups (or 300 000 with cache enables) per second on complete Internet BGP table (aprox 500 000 prefixes) on ordinary hardware (2.4GHz Xeon CPU). For more detail you can try make test on module source to check performance on your system.
CLASS METHODS
new - Class Constructor
$lpm = Net::IP::LPM->new( [ $filename ] );Constructs a new Net::IP::LPM object. The $filename can be specified as the database of prebuilded prefixes. If the file name is not handled the whole structure will be stored into the memory.
OBJECT METHODS
add - Add Prefix
$code = $lpm->add( $prefix, $value );Adds prefix $prefix into database with value $value. Returns 1 if the prefix was added sucesfully. Returns 0 when some error happens (typically wrong address formating).
After adding prefixes rebuild of database have to be performed.
rebuild - Rebuild Prefix Database
$code = $lpm->rebuild();Rebuilds the database. After adding new prefixes the database have to be rebuilded before lookups are performed. Depends on the $filename handled in the constructor the database will be stored into $filename or keept in the memory if the file name was nos specified.
Returns 1 if the the rebuild was succesfull or 0 if something wrong happend.
lookup - Lookup Address
$value = $lpm->$lookup( $address );Lookups the prefix in the database and returns the value. If the prefix is not found or error ocured the undef value is returned.
Before lookups are performed the database have to be rebuilded by $lpm->rebuild() operation.
lookup_raw - Lookup Address in raw format
$value = $lpm->lookup_raw( $address );Same as $lpm->lookup but takes $address in raw format (result of inet_ntop function). It is more effective than $lpm->lookup, because convertion from text format is not nescessary.
lookup_cache_raw - Lookup Address in raw format with cache
$value = $lpm->lookup_cache_raw( $address );Same as $lpm->lookup_raw but the cache is used to speed up lookups. It might be usefull when there is big probability that lookup for the same address will be porformed more often.
The cache becomes effective when the ratio of hit cache entries is bigger than 50%. For less hit ratio the overhead discard the cache benefits.
NOTE: Cache entries are stored into memory, so it can lead to unexpected memory comsumption.
SEE ALSO
There are also other implementation of Longest Prefix Matxh in perl. However most of them have some disadvantage (poor performance, lack of support for IPv6 or requires a lot of time for initial database building). However in some cases it might be usefull:
AUTHOR
Tomas Podermanski <tpoder@cis.vutbr.cz> Brno University of Technology
COPYRIGHT AND LICENSE
Copyright (C) 2012, Brno University of Technology
This library is free software; you can redistribute it and/or modify it under the same terms as Perl itself.