IP address - longest prefix match

F

friend.05

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

Jürgen Exner

[email protected] said:
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)
Click to expand...

This may not be the smartest ways to do it, but at least it works:

use warnings; use strict;
my @IPs = qw (
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;
);

sub lead {
#I'm sure this can be optimized
#or there is probably a module function somewhere, too
my ($s, $t) = @_; my $i=0;
while ($i < length ($s) and $i < length ($t)) {
if (substr($s, $i, 1) eq substr($t, $i, 1)) {
$i++;
} else {
return $i;
}
}
return $i;
}

my $C_IP = '12.120.29.25';
my $best = $IPs[0];
my $bestlen = lead($best, $C_IP);
for my $IP (@IPs) {
if (lead($IP, $C_IP) > $bestlen) {
$best = $IP;
$bestlen = lead ($best, $C_IP);
}
}
print "Longest lead: '$best'; matching $bestlen characters: '".
substr($best, 0, $bestlen). "'\n";
 
F

friend.05

[email protected] said:
Suppose I have C_IP address : 12.120.29.25
Click to expand...
and I have list of following IP addresses :

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)
Click to expand...

This may not be the smartest ways to do it, but at least it works:

use warnings; use strict;
my @IPs = qw (
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;
             );

sub lead {
#I'm sure this can be optimized
#or there is probably a module function somewhere, too
    my ($s, $t) = @_; my $i=0;
    while ($i < length ($s) and $i < length ($t)) {
        if (substr($s, $i, 1) eq substr($t, $i, 1)) {
            $i++;
        } else {
            return $i;
        }
    }
    return $i;

}

my $C_IP = '12.120.29.25';
my $best = $IPs[0];
my $bestlen = lead($best, $C_IP);
for my $IP (@IPs) {
    if (lead($IP, $C_IP) > $bestlen) {
        $best = $IP;
        $bestlen = lead ($best, $C_IP);
    }}

print "Longest lead: '$best'; matching $bestlen characters: '".
    substr($best, 0, $bestlen). "'\n";- Hide quoted text -

- Show quoted text -
Click to expand...

Thanks for your reply.

But I new to perl. I am not getting for code. Can please explain me in
more detail.

Thanks.
 
S

sln

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)
Click to expand...
I get the feeling you mean 'largest' instead of 'longest'. Otherwise,
what would be the purpose of this exercise?

sln

----------------------------
# output:
# 12.120.0.0|15
# 12.120.0.0|21
# 12.120.16.0|20
# 12.120.16.0|22
# 12.120.24.0|21
# 12.120.36.0|22
# 12.120.40.0|21
# 12.120.72.0|22
# 12.120.80.0|20
# 12.120.96.0|20
# 12.120.192.0|19
# 116.212.120.0|24
# 194.212.120.0|21
# 212.120.32.0|19
# 212.120.64.0|18
# 212.120.128.0|19
# 212.120.192.0|19
# 213.3.12.120|29
# Found largest 12.120 = 12.120.192.0|19

use strict;
use warnings;
use sort 'stable';

my $ippatt = '12.120';
my @IPs = ();
my $iplargest = '';

while (<DATA>)
{
chomp;
if (/(\d{1,3})\.(\d{1,3})\.(\d{1,3})\.(\d{1,3})\|(\d*);/)
{
push @IPs, [$1,$2,$3,$4,$5];

}
}
if (@IPs)
{
for my $i (0..4) {
@IPs = sort {$a->[4-$i] <=> $b->[4-$i]} @IPs;
}
for my $ip (@IPs) {
my $ipstr = "$ip->[0].$ip->[1].$ip->[2].$ip->[3]|$ip->[4]";
print "$ipstr\n";
if ($ipstr =~ /^$ippatt/) {
$iplargest = $ipstr;
}
}
}
if (length($iplargest)) {
print "Found largest $ippatt = $iplargest\n";
} else {
print "Did not find $ippatt in list\n";
}


__DATA__

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

Jürgen Exner

[email protected] said:
But I new to perl. I am not getting for code. Can please explain me in
more detail.
Click to expand...

Adding explanations inline
Never run a program without (unless you really, really know why).
Your test data
Initialization with of $s and $t with function parameters, use $i as
index into the strings to be compared
As long as $i hasn't reached the end of either string ...
.... if the i-th character in both strings is the same, look at the next
character
otherwise those strings were the same up to the current value of $i
POST for while loop: $i is larger than the length of the shorter string.
Therefore one string is a complete prefix of the other.The value you are looking for
my $best = $IPs[0];
my $bestlen = lead($best, $C_IP);
Click to expand...
Click to expand...
Initialize $best and $bestlen with the first element of the test data.
Could have chosen any other, it doesn't matter which on you pick.
For each IP ...
....check if the match is better than the currently best...
.... and if it is then pick this one as the new currently best

At the end of the loop $best will contain the best overall.

jue
 
S

sln

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)
Click to expand...
Ok, I searched LPM. Routing table lookup.

This is the key: (C_IP address) 12.120.29.25

32 bit key = 12<<24 + 120<<16 + 29<<8 + 25

Loop(Entries)
{
Example table entry:
12.120.24.0 | 21;
^^^^^^^^^^^
32 bits
^^
Bitmask (the bits to mask) = ((2 ** 21)-1) << (32-21)

32 bit entry = 12<<24 + 120<<16 + 24<<8 + 0

Masked key = 32 bit key & Bitmask;
Masked entry = 32 bit entry & Bitmask;

if (Masked key == Masked entry && Bitmask > LargestBitmask)
{
LPM = 32 bit entry;
LargestBitmask = Bitmask;
}
}

Print the LPM..

Source (there were many, but this seamed easiest):
http://www.xilinx.com/support/documentation/application_notes/xapp738.pdf

For an entry to be considered a match to the search key, it must satisfy these three conditions
(refer also to the numbers in Figure 2):
1. The entry’s Valid bit must be set.
2. The entry’s masked IP address and the masked search key are equal to each other.
An IP address is masked by performing a bitwise AND of the mask and the IP address.
3. The entry’s mask is greater than or equal to the mask of any previously matched entry.


------------------------------------------------------
# output:
# Found possible match 12.120.192.0|19;
# Found possible match 212.120.128.0|19;
# Found possible match 12.120.0.0|15;
# Found possible match 12.120.72.0|22;
# Found possible match 12.120.96.0|20;
# Found possible match 12.120.40.0|21;
# Found possible match 12.120.0.0|21;
# Found possible match 12.120.192.0|19;
# Found possible match 12.120.36.0|22;
# Found possible match 212.120.32.0|19;
# Found possible match 212.120.64.0|18;
# Found possible match 212.120.192.0|19;
# Found possible match 213.3.12.120|29;
# Found possible match 12.120.24.0|21;
#
# LPM = 213.3.12.120|29;

use strict;
use warnings;
use sort 'stable';

my $LPM = '';
my $LargestMask = 0;
my $Key32 = 12<<24 + 120<<16 + 29<<8 + 25;

while (<DATA>)
{
chomp;
if (/(\d{1,3})\.(\d{1,3})\.(\d{1,3})\.(\d{1,3})\|(\d*)/)
{
my $Entry32 = $1<<24 + $2<<16 + $3<<8 + $4;

my $Mask = ((2 ** $5)-1) << (32-$5);

my $MaskedKey = $Key32 & $Mask;
my $MaskedEntry = $Entry32 & $Mask;

if ($MaskedKey == $MaskedEntry)
{
print "Found possible match $_\n";
if ($Mask > $LargestMask) {
$LPM = $_;
$LargestMask = $Mask;
}
}
}
}
if (length($LPM)) {
print "LPM = $LPM\n";
} else {
print "Did not find LMP match in list\n";
}


__DATA__

12.120.192.0|19;
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;
 
S

sln

Suppose I have C_IP address : 12.120.29.25

and I have list of following IP addresses :

[snip]

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)
Click to expand...
Ok, I searched LPM. Routing table lookup.

This is the key: (C_IP address) 12.120.29.25

32 bit key = 12<<24 + 120<<16 + 29<<8 + 25

Loop(Entries)
{
Example table entry:
12.120.24.0 | 21;
^^^^^^^^^^^
32 bits
^^
Bitmask (the bits to mask) = ((2 ** 21)-1) << (32-21)

32 bit entry = 12<<24 + 120<<16 + 24<<8 + 0

Masked key = 32 bit key & Bitmask;
Masked entry = 32 bit entry & Bitmask;

if (Masked key == Masked entry && Bitmask > LargestBitmask)
{
LPM = 32 bit entry;
LargestBitmask = Bitmask;
}
}

Print the LPM..

Source (there were many, but this seamed easiest):
http://www.xilinx.com/support/documentation/application_notes/xapp738.pdf

For an entry to be considered a match to the search key, it must satisfy these three conditions
(refer also to the numbers in Figure 2):
1. The entry’s Valid bit must be set.
2. The entry’s masked IP address and the masked search key are equal to each other.
An IP address is masked by performing a bitwise AND of the mask and the IP address.
3. The entry’s mask is greater than or equal to the mask of any previously matched entry.
Click to expand...
[snip]

They also have an array of algorithyms available that shorten the search time.
The method I posted is linear.

But they have linear variations that do kind of a bubble sort.
Itterate the list just checking the first term. From that list, just check the
second, from that ... etc.

This aviods all the math of shifting all terms in each entry in the whole list.

If you get away from linear, there are some wildly exotic methodologies.


sln
 
S

sln

Ok, I searched LPM. Routing table lookup.

This is the key: (C_IP address) 12.120.29.25

32 bit key = 12<<24 + 120<<16 + 29<<8 + 25

Loop(Entries)
{
Example table entry:
12.120.24.0 | 21;
^^^^^^^^^^^
32 bits
^^
Bitmask (the bits to mask) = ((2 ** 21)-1) << (32-21)

32 bit entry = 12<<24 + 120<<16 + 24<<8 + 0

Masked key = 32 bit key & Bitmask;
Masked entry = 32 bit entry & Bitmask;

if (Masked key == Masked entry && Bitmask > LargestBitmask)
{
LPM = 32 bit entry;
LargestBitmask = Bitmask;
}
}

Print the LPM..

Source (there were many, but this seamed easiest):
http://www.xilinx.com/support/documentation/application_notes/xapp738.pdf

For an entry to be considered a match to the search key, it must satisfy these three conditions
(refer also to the numbers in Figure 2):
1. The entry’s Valid bit must be set.
2. The entry’s masked IP address and the masked search key are equal to each other.
An IP address is masked by performing a bitwise AND of the mask and the IP address.
3. The entry’s mask is greater than or equal to the mask of any previously matched entry.


------------------------------------------------------
Click to expand...
I guess it would help if I pay attention to what I'm doing..

sln

-----------------------------------------------
# output:
# Found possible match 12.120.0.0|15;
# Found possible match 12.120.16.0|20;
# Found possible match 12.120.24.0|21;
#
# LPM = 12.120.24.0|21;

use strict;
use warnings;
use sort 'stable';

my $LPM = '';
my $LargestMask = 0;

# search LPM for: 12.120.29.25;
my $Key32 = (12<<24) + (120<<16) + (29<<8) + 25;

while (<DATA>)
{
chomp;
if (/(\d{1,3})\.(\d{1,3})\.(\d{1,3})\.(\d{1,3})\|(\d*)/)
{
my $Entry32 = ($1<<24) + ($2<<16) + ($3<<8) + $4;

my $Mask = ((2 ** $5)-1) << (32-$5);

my $MaskedKey = $Key32 & $Mask;
my $MaskedEntry = $Entry32 & $Mask;

if ($MaskedKey > 0 && $MaskedKey == $MaskedEntry)
{
print "Found possible match $_\n";
if ($Mask > $LargestMask) {
$LPM = $_;
$LargestMask = $Mask;
}
}
}
}
if (length($LPM)) {
print "\nLPM = $LPM\n";
} else {
print "Did not find LMP match in list\n";
}

__DATA__

12.120.192.0|19;
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;
 
J

Jim Gibson

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)
Click to expand...

You asked the same question on the perl.beginners list, and I answered
you there.
 
S

sln

(e-mail address removed) wrote:

Look at inet_ntoa and inet_aton (in IO::Socket or Socket...)

And you need to bear in mind that networks and routings are no longer
based on class A/B/C addresses, but use wil be using any netmask length.

So turn the binary into a 32-bit string (sprintf) and find the longest
common match. Probably can be done by :

1. Take all addresses
2. inet_aton them
3. sort (binary) the results
4, binary chop you (binary) search into the list that you have
check whether the result preceding or following where you end up is the
closest match
Click to expand...

Let me paraphrase what I think you mean.

The mask and largest prefix don't matter anymore.
Basically turn the ip list into 32-bit integer like this
($1<<24) + ($2<<16) + ($3<<8) + $4

Stuff them into an array. Sort the array, or an index into an array
Get the key into a 32-bit integer.

Do a binary searh into the array of integers for the key, picking the closest
absolute value of the difference from the key to where you stopped.

Where a binary search is something like this:
- - -
-
-
- -
- - Stopped/or found exact match. Compare, use lesser of abs(key-either side)
- - -
-
-
-
-
-
- -

I'm not too sure about current Networking standards. I know IpV6 uses more values,
and broadens the Ip format. Bit-wise manipulations are fairly easy. Unfortunately,
nobody is paying me to do this stuff and its not really a hobby.

sln
 
P

Peter J. Holzer

[email protected] said:
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.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)
Click to expand...

This may not be the smartest ways to do it, but at least it works:
Click to expand...

No, it doesn't.

For the 174344 IP addresses in the example netblocks, it fails in 76288
cases (or 44%).

You can't find an IP prefix by searching for a string prefix in the
dotted quad representation, you have to use the binary representation.
For example, if you have two netblocks 143.130.32.0/20 and
143.130.48.0/20, and an IP address 143.130.45.1, your method would find
143.130.48.0/20 while the correct answer is 143.130.32.0/20:

143.130.45.1: 10001111 10000010 00101101 00000001
143.130.32.0/20: 10001111 10000010 0010
143.130.48.0/20: 10001111 10000010 0011

As you can see, 143.130.32.0/20 matches, but 143.130.48.0/20 doesn't.

As Ted wrote, use Net::Netmask.

hp
 

Ask a Question

Want to reply to this thread or ask your own question?

You'll need to choose a username for the site, which only take a couple of moments. After that, you can post your question and our members will help you out.

Ask a Question

Similar Threads

longest prefix match 5
Minimum Total Difficulty 0
Google gauge chart 2
Machine Learning.. Endless Struggle 3
How to find longest bitrange of ones 2
A number everyday of the month "and" a different number depending on the day of the month´s day time 2
Help with code 0
New baby here 2

Members online

Total: 25 (members: 1, guests: 24)
Robots: 316

Forum statistics

Threads
473,755
Messages
2,569,535
Members
45,007
Latest member
obedient dusk

Latest Threads

Top