Velocity Reviews - Computer Hardware Reviews

Velocity Reviews > Newsgroups > Programming > Perl > Perl Misc > longest prefix match

Reply
Thread Tools

longest prefix match

 
 
friend.05@gmail.com
Guest
Posts: n/a
 
      11-24-2008
I have table of ip adress with prefix.

Now I need to match IP address with corresponding IP with longest
prefix.

I am not sure how can I do that.
 
Reply With Quote
 
 
 
 
Jürgen Exner
Guest
Posts: n/a
 
      11-24-2008
"(E-Mail Removed)" <(E-Mail Removed)> wrote:
>I have table of ip adress with prefix.


'table' is not a standard Perl data structure. How is that 'table'
implemented?

>Now I need to match IP address with corresponding IP with longest
>prefix.


No idea what an IP prefix is, either, but assuming you are talking about
a list of strings then a pragmatic approach would be:

grep() all list elements, where the IP part is eq to the wanted IP, then
sort() the result by length() and pick the last element.

However If the list is large and performance an issue, then you can
write a simple loop to find the wanted item in one single pass. Just
loop through the list and keep a "best candidate", which is updated
every time you find a better candidate.

for (@IPswithPrefix) {
if (IPsMatch() and length($_) > length($candidate)) {
$candidate = $_;
}
}
print $candidate;

jue
 
Reply With Quote
 
 
 
 
friend.05@gmail.com
Guest
Posts: n/a
 
      11-24-2008
On Nov 24, 11:30*am, Jürgen Exner <(E-Mail Removed)> wrote:
> "(E-Mail Removed)" <(E-Mail Removed)> wrote:
> >I have table of ip adress with prefix.

>
> 'table' is not a standard Perl data structure. How is that 'table'
> implemented?
>
> >Now I need to match IP address with corresponding IP with longest
> >prefix.

>
> No idea what an IP prefix is, either, but assuming you are talking about
> a list of strings then a pragmatic approach would be:
>
> grep() all list elements, where the IP part is eq to the wanted IP, then
> sort() the result by length() and pick the last element.
>
> However If the list is large and performance an issue, then you can
> write a simple loop to find the wanted item in one single pass. Just
> loop through the list and keep a "best candidate", which is updated
> every time you find a better candidate.
>
> for (@IPswithPrefix) {
> * * * * if (IPsMatch() and length($_) > length($candidate)) {
> * * * * * * * * $candidate = $_;
> * * * * }}
>
> print $candidate;
>
> jue


Suppose I have C_IP address : 12.120.29.25


and I have list of following IP addresses :

212.120.128.0|19;
12.120.0.0|15;
12.120.16.0|20;
12.120.72.0|22;
12.120.96.0|20;
12.120.40.0|21;
12.120.0.0|21;
12.120.192.0|19;
12.120.16.0|22;
12.120.36.0|22;
12.120.80.0|20;
194.212.120.0|21;
212.120.32.0|19;
212.120.64.0|18;
212.120.192.0|19;
213.3.12.120|29;
116.212.120.0|24;
12.120.24.0|21;


Now I need to map C_IP to list with longest prefix match. (As u can
there are many IP address with 12.120. but I need to map to one with
longest prefix match)
 
Reply With Quote
 
Ted Zlatanov
Guest
Posts: n/a
 
      11-24-2008
On Mon, 24 Nov 2008 08:46:53 -0800 (PST) "(E-Mail Removed)" <(E-Mail Removed)> wrote:

f> Suppose I have C_IP address : 12.120.29.25

f> and I have list of following IP addresses :
f> 212.120.128.0|19;
f> 12.120.0.0|15;
f> 12.120.16.0|20;
f> 12.120.72.0|22;
f> 12.120.96.0|20;
f> 12.120.40.0|21;
f> 12.120.0.0|21;
f> 12.120.192.0|19;
f> 12.120.16.0|22;
f> 12.120.36.0|22;
f> 12.120.80.0|20;
f> 194.212.120.0|21;
f> 212.120.32.0|19;
f> 212.120.64.0|18;
f> 212.120.192.0|19;
f> 213.3.12.120|29;
f> 116.212.120.0|24;
f> 12.120.24.0|21;

f> Now I need to map C_IP to list with longest prefix match. (As u can
f> there are many IP address with 12.120. but I need to map to one with
f> longest prefix match)

Look at Net::Netmask and the match() method in particular; just iterate
through the list above in order from largest prefix to smallest and
return when there's a match.

Ted


 
Reply With Quote
 
friend.05@gmail.com
Guest
Posts: n/a
 
      11-24-2008
On Nov 24, 12:05*pm, Ted Zlatanov <(E-Mail Removed)> wrote:
> On Mon, 24 Nov 2008 08:46:53 -0800 (PST) "(E-Mail Removed)" <(E-Mail Removed)> wrote:
>
> f> Suppose I have C_IP address : 12.120.29.25
>
> f> and I have list of following IP addresses :
> f> *212.120.128.0|19;
> f> *12.120.0.0|15;
> f> *12.120.16.0|20;
> f> *12.120.72.0|22;
> f> *12.120.96.0|20;
> f> *12.120.40.0|21;
> f> *12.120.0.0|21;
> f> *12.120.192.0|19;
> f> *12.120.16.0|22;
> f> *12.120.36.0|22;
> f> *12.120.80.0|20;
> f> *194.212.120.0|21;
> f> *212.120.32.0|19;
> f> *212.120.64.0|18;
> f> *212.120.192.0|19;
> f> *213.3.12.120|29;
> f> *116.212.120.0|24;
> f> *12.120.24.0|21;
>
> f> Now I need to map C_IP to list with longest prefix match. (As u can
> f> there are many IP address with 12.120. but I need to map to one with
> f> longest prefix match)
>
> Look at Net::Netmask and the match() method in particular; just iterate
> through the list above in order from largest prefix to smallest and
> return when there's a match.
>
> Ted


I am little confuse with largest prefix to smallest.

Example:

12.120.16.0|20;
12.120.96.0|20;
12.120.40.0|21;
12.120.72.0|22;
12.120.16.0|22;

In above list what will be order of largest prefix to smallest.


And is there any tutorial with exmple where can I see steps to use
Net::Netmask
 
Reply With Quote
 
Ted Zlatanov
Guest
Posts: n/a
 
      11-24-2008
On Mon, 24 Nov 2008 10:23:34 -0800 (PST) "(E-Mail Removed)" <(E-Mail Removed)> wrote:

f0c> On Nov 24, 12:05*pm, Ted Zlatanov <(E-Mail Removed)> wrote:
>> On Mon, 24 Nov 2008 08:46:53 -0800 (PST) "(E-Mail Removed)" <(E-Mail Removed)> wrote:
>>

f> Suppose I have C_IP address : 12.120.29.25
>>

f> and I have list of following IP addresses :
f> *212.120.128.0|19;
f> *12.120.0.0|15;
f> *12.120.16.0|20;
f> *12.120.72.0|22;
f> *12.120.96.0|20;
f> *12.120.40.0|21;
f> *12.120.0.0|21;
f> *12.120.192.0|19;
f> *12.120.16.0|22;
f> *12.120.36.0|22;
f> *12.120.80.0|20;
f> *194.212.120.0|21;
f> *212.120.32.0|19;
f> *212.120.64.0|18;
f> *212.120.192.0|19;
f> *213.3.12.120|29;
f> *116.212.120.0|24;
f> *12.120.24.0|21;
>>

f> Now I need to map C_IP to list with longest prefix match. (As u can
f> there are many IP address with 12.120. but I need to map to one with
f> longest prefix match)
>>
>> Look at Net::Netmask and the match() method in particular; just iterate
>> through the list above in order from largest prefix to smallest and
>> return when there's a match.


f> I am little confuse with largest prefix to smallest.

f> Example:

f> 12.120.16.0|20;
f> 12.120.96.0|20;
f> 12.120.40.0|21;
f> 12.120.72.0|22;
f> 12.120.16.0|22;

f> In above list what will be order of largest prefix to smallest.

f> And is there any tutorial with exmple where can I see steps to use
f> Net::Netmask

First of all, let's be clear about the problem as I see it, because I
think you haven't understood it clearly. If I'm wrong, sorry, but I'm
trying to help you.

I think you're trying to find the best (smallest) net block match for an
IP. The numbers you quote are net blocks, and you should know what that
means in IPv4 terms. Look it up if you don't.

The "longest" match you want really means the most specific net block,
meaning the net block with the most bits unmasked (thus, the fewest
addresses in it). If there's a tie by number of unmasked bits, the
first one found can win. In the example you give, either of the 22's
for example, if they match.

OK, so the code below walks through the net blocks, adds them to $table,
then finds the smallest net block in $table that matches the IPs. Do
"print Dumper $table" to see what the storage looks like, if you're
curious. I wrote it so you can give it multiple IPs from the command
line, and it doesn't catch the cases where the IP is not found or
invalid.

#!/usr/bin/perl

use warnings;
use strict;
use Data:umper;
use Net::Netmask;

my $table = {};

while (<DATA>)
{
chomp;
my $net = new Net::Netmask ($_);
$net->storeNetblock($table);
}

print findNetblock($_, $table) . "\n" foreach @ARGV;

__DATA__
12.120.16.0/20
12.120.96.0/20
12.120.40.0/21
12.120.72.0/22
12.120.16.0/22
 
Reply With Quote
 
 
 
Reply

Thread Tools

Posting Rules
You may not post new threads
You may not post replies
You may not post attachments
You may not edit your posts

BB code is On
Smilies are On
[IMG] code is On
HTML code is Off
Trackbacks are On
Pingbacks are On
Refbacks are Off


Similar Threads
Thread Thread Starter Forum Replies Last Post
re.sub(): replace longest match instead of leftmost match? John Gordon Python 13 12-20-2011 02:58 AM
IP address - longest prefix match friend.05@gmail.com Perl Misc 11 11-29-2008 08:43 AM
removing a namespace prefix and removing all attributes not in that same prefix Chris Chiasson XML 6 11-14-2006 05:08 PM
Longest Sites Name With Worlds Longest Stuffs... Vijay Murthy Computer Information 0 02-04-2006 09:57 AM
"static" prefix - to parallel "this" prefix Tim Tyler Java 36 12-10-2004 01:02 AM



Advertisments