longest prefix match

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

  1. Guest

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

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

  3. Guest

    On Nov 24, 11:30 am, Jürgen Exner <> wrote:
    > "" <> 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)
    , Nov 24, 2008
    #3
  4. Ted Zlatanov Guest

    On Mon, 24 Nov 2008 08:46:53 -0800 (PST) "" <> 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
    Ted Zlatanov, Nov 24, 2008
    #4
  5. Guest

    On Nov 24, 12:05 pm, Ted Zlatanov <> wrote:
    > On Mon, 24 Nov 2008 08:46:53 -0800 (PST) "" <> 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
    , Nov 24, 2008
    #5
  6. Ted Zlatanov Guest

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

    f0c> On Nov 24, 12:05 pm, Ted Zlatanov <> wrote:
    >> On Mon, 24 Nov 2008 08:46:53 -0800 (PST) "" <> 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::Dumper;
    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
    Ted Zlatanov, Nov 24, 2008
    #6
    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:
    680
    Joerg Schuster
    Dec 3, 2003
  2. Licheng Fang
    Replies:
    32
    Views:
    1,228
    Tim Peters
    Sep 17, 2006
  3. John Gordon
    Replies:
    13
    Views:
    457
    Ian Kelly
    Dec 20, 2011
  4. A. Farber
    Replies:
    3
    Views:
    146
    Big and Blue
    May 3, 2004
  5. Replies:
    11
    Views:
    793
    Peter J. Holzer
    Nov 29, 2008
Loading...

Share This Page