IP address - longest prefix match

Discussion in 'Perl Misc' started by friend.05@gmail.com, Nov 24, 2008.

  1. Guest

    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)
    , Nov 24, 2008
    #1
    1. Advertising

  2. "" <> wrote:
    >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)


    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";
    Jürgen Exner, Nov 24, 2008
    #2
    1. Advertising

  3. Guest

    On Nov 24, 2:24 pm, Jürgen Exner <> wrote:
    > "" <> wrote:
    > >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)

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


    Thanks for your reply.

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

    Thanks.
    , Nov 24, 2008
    #3
  4. Guest

    On Mon, 24 Nov 2008 10:45:21 -0800 (PST), "" <> wrote:

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

    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;
    , Nov 24, 2008
    #4
  5. "" <> wrote:
    >On Nov 24, 2:24 pm, Jürgen Exner <> wrote:
    >But I new to perl. I am not getting for code. Can please explain me in
    >more detail.


    Adding explanations inline

    >> use warnings; use strict;

    Never run a program without (unless you really, really know why).

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

    Your test data

    >> sub lead {
    >> #I'm sure this can be optimized
    >> #or there is probably a module function somewhere, too
    >>     my ($s, $t) = @_; my $i=0;

    Initialization with of $s and $t with function parameters, use $i as
    index into the strings to be compared

    >>     while ($i < length ($s) and $i < length ($t)) {

    As long as $i hasn't reached the end of either string ...

    >>         if (substr($s, $i, 1) eq substr($t, $i, 1)) {
    >>             $i++;

    .... if the i-th character in both strings is the same, look at the next
    character

    >>         } else {
    >>             return $i;

    otherwise those strings were the same up to the current value of $i

    >>         }
    >>     }
    >>     return $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.
    >>
    >> }
    >>
    >> my $C_IP = '12.120.29.25';

    The value you are looking for

    >> my $best = $IPs[0];
    >> my $bestlen = lead($best, $C_IP);

    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 my $IP (@IPs) {

    For each IP ...

    >>     if (lead($IP, $C_IP) > $bestlen) {

    ....check if the match is better than the currently best...

    >>         $best = $IP;
    >>         $bestlen = lead ($best, $C_IP);

    .... and if it is then pick this one as the new currently best

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


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

    jue
    Jürgen Exner, Nov 24, 2008
    #5
  6. Guest

    On Mon, 24 Nov 2008 10:45:21 -0800 (PST), "" <> wrote:

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

    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;
    , Nov 25, 2008
    #6
  7. Guest

    On Tue, 25 Nov 2008 01:19:07 GMT, wrote:

    >On Mon, 24 Nov 2008 10:45:21 -0800 (PST), "" <> wrote:
    >
    >>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)
    >>

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

    [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
    , Nov 25, 2008
    #7
  8. Guest

    On Tue, 25 Nov 2008 01:19:07 GMT, wrote:

    >On Mon, 24 Nov 2008 10:45:21 -0800 (PST), "" <> wrote:
    >
    >>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)
    >>

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

    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;
    , Nov 25, 2008
    #8
  9. Jim Gibson Guest

    In article
    <>,
    <""> wrote:

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


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

    --
    Jim Gibson
    Jim Gibson, Nov 26, 2008
    #9
  10. Guest

    On Wed, 26 Nov 2008 00:18:20 +0000, Big and Blue <> wrote:

    > 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


    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
    , Nov 26, 2008
    #10
  11. Guest

    On Tue, 25 Nov 2008 16:56:26 -0800, Jim Gibson <> wrote:

    >In article
    ><>,
    ><""> wrote:
    >
    >> 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)

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

    He even asked it here on 2 threads, 1 day apart.

    sln
    , Nov 26, 2008
    #11
  12. On 2008-11-24 19:24, Jürgen Exner <> wrote:
    > "" <> wrote:
    >>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)

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


    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
    Peter J. Holzer, Nov 29, 2008
    #12
    1. Advertising

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

It takes just 2 minutes to sign up (and it's free!). Just click the sign up button to choose a username and then you can ask your own questions on the forum.
Similar Threads
  1. Joerg Schuster

    leftmost longest match (of disjunctions)

    Joerg Schuster, Dec 1, 2003, in forum: Python
    Replies:
    12
    Views:
    681
    Joerg Schuster
    Dec 3, 2003
  2. Licheng Fang
    Replies:
    32
    Views:
    1,233
    Tim Peters
    Sep 17, 2006
  3. John Gordon
    Replies:
    13
    Views:
    458
    Ian Kelly
    Dec 20, 2011
  4. A. Farber
    Replies:
    3
    Views:
    147
    Big and Blue
    May 3, 2004
  5. longest prefix match

    , Nov 24, 2008, in forum: Perl Misc
    Replies:
    5
    Views:
    545
    Ted Zlatanov
    Nov 24, 2008
Loading...

Share This Page