netmask calculation trick

Discussion in 'Cisco' started by Walter Roberson, Jan 31, 2004.

  1. Maybe this is well known to anyone who has ever studied CCIE ;-) but
    I've never run across it before I (re-?) invented it last night.

    Q: Suppose you see traffic coming *from* an IP address. What's the
    *smallest* enclosing network mask that the IP address might have?

    A: Note: The following doesn't work on some point-to-point links.

    If you see traffic *from* a particular IP, then the IP must not be the
    base address of a subnet nor the broadcast address of a subnet.

    [Exception: point-to-points link that are using address- conservation
    extensions.]

    Because subnets build up in powers of two and cannot be arbitrarily
    aligned, seeing traffic from a particular IP also gives you information
    about which other IPs that cannot be be base or broadcast addresses.
    For example, if you see traffic from .35 then you can deduce that .33
    through .38 are also not base or broadcast addresses.

    A fast formula for calculating the minimum Cisco IOS-style wildcard
    bits implied by any IP address, X, is:

    M = X xor (X+1) if X is odd xor is the "exclusive or" operation
    M = X xor (X-1) if X is even

    This value can be used directly in IOS ACLs. The equivilent standard
    netmask is the bitwise compliment of this value.

    The implied base IP is then (X and (not M)),
    and the implied broadcast is (X or M) [bitwise 'and', 'or', and 'not']

    Example: the odd IP address .35 is binary xxx00100011
    X+1 is then xxx00100100 i.e .36
    and xor'ing those gives ...00000000111 i.e. 0.0.0.7
    which is a stanrd netmask of ...11111111000 i.e. 255.255.255.248
    The implied base IP is then xxx00100000 i.e. .32
    The implied broadcast is then xxx00100111 i.e. .39


    On the remote chance that no-one has come up with this before,
    you can call this "Roberson's Netmask Trick" ;-)
     
    Walter Roberson, Jan 31, 2004
    #1
    1. Advertisements

  2. :Q: Suppose you see traffic coming *from* an IP address. What's the
    :*smallest* enclosing network mask that the IP address might have?

    : M = X xor (X+1) if X is odd xor is the "exclusive or" operation
    : M = X xor (X-1) if X is even


    And here's a useful perl program that makes use of this Trick.
    This program takes as input a list of IPs, one per line. It
    assumes traffic has been "seen" from each of the IPs, and it calculates
    and displays the set of subnets that are consistant with all of the
    traffic.

    For example, fed the 192.168.*.* addresses I have defined in my hosts
    file, it spits out:

    base IP netmask | base IP IOS mask
    --------------- --------------- | --------------- ---------------
    192.168.0.0 255.255.255.192 | 192.168.0.0 0.0.0.63
    192.168.3.160 255.255.255.240 | 192.168.3.160 0.0.0.15
    192.168.132.80 255.255.255.252 | 192.168.132.80 0.0.0.3
    192.168.132.88 255.255.255.248 | 192.168.132.88 0.0.0.7


    I made the input and output wrappers around the functionality so
    that others can adapt the routines for their own purposes.


    #!/usr/freeware/bin/perl

    # Written 20040131, by Walter Roberson -cnrc.gc.ca

    # When traffic is seen -from- an IP address, you can deduce the
    # smallest enclosing subnet. For example, traffic from .35 implies
    # that the subnet base must be at least .32 and the broadcast at least .39
    #
    # This program reads a bunch of IP addresses, and calculates the
    # smallest subnets that are consistant with traffic having appeared
    # on all of the IPs, and displays the corresponding bases, netmasks,
    # and IOS masks.

    use strict;
    use warnings;

    # a bunch of auxillary routines

    # pack and unpack values. There are some conversions you can't do directly.

    sub s2L($) { unpack 'L', shift } #string to unsigned 32 bit long
    sub ab2s(@) { pack 'C*', @_ } #array of bytes to string
    sub q2L($) { s2L ab2s (split /\./, shift) } #dotted-quad to unsigned 32 long
    sub s2ab($) { unpack 'C*', shift } #string to array of bytes
    sub s2q($) { join '.', s2ab shift } #string to dotted quad
    sub L2s($) { pack 'L', shift } #unsigned 32 long to string
    sub L2q($) { s2q L2s shift } #unsigned 32 long to dotted quad


    # convert unsigned 32 bit long to base and broadcast pair

    sub L2bb ( $ ) {
    # this algorithm should work on all endians of machines.

    my $ipb = $_[0];
    my $mask = ($ipb & 1) ? ($ipb ^ ($ipb+1)) : ($ipb ^ ($ipb-1)); # xor's!

    ($ipb & ~ $mask, $ipb | $mask) #return base and broadcast pair
    }


    # given a list of IPs, return a hash of the minimal enclosing
    # subnets. The hash key is the subnet base, and the hash value is
    # the broadcast. An array of pairs might seem slightly more obvious,
    # but it's easier to sort a hash.

    sub auto_topo( @ ) {
    my @ips = @_;

    my %bbpairs = ();

    foreach (@ips) {
    my ($base, $top) = L2bb $_;
    next if exists $bbpairs{$base} && $top <= $bbpairs{$base};
    my $is_enclosed = 0;
    foreach (keys %bbpairs) {
    if ($_ >= $base && $bbpairs{$_} <= $top) { #new encloses previous
    delete $bbpairs{$_};
    } else {
    if ($base >= $_ && $top <= $bbpairs{$_}) { #old encloses new
    $is_enclosed = 1;
    last; # out of the foreach
    }
    }
    }
    $bbpairs{$base} = $top unless $is_enclosed;
    }

    return %bbpairs;
    }


    # auxillary routine for presentation purposes
    sub P15($) { substr $_[0] . ' ' x 15, 0, 15 } #pad to 15 chars


    # read IPs from standard input, compute the minimal subnet topologies
    # and format the results to output

    sub auto_topo_main( ) {

    my %ips = ();

    while ( <> ) { # read a line
    chomp; # remove cr/lf
    s/\s*[#;!].*$//; s/^\s*//; # trim comments and blanks
    next unless m/^\d{1,3}\.\d{1,3}\.\d{1,3}\.\d{1,3}$/; #only IPs allowed
    $ips{q2L $_} = 1; # record IP
    }

    my %bbpairs = auto_topo keys %ips; # send in unique IPs only

    print P15 'base IP', ' ', P15 'netmask', ' | ',
    P15 'base IP', ' ', "IOS mask\n";
    print "--------------- --------------- | --------------- ---------------\n";

    foreach (sort keys %bbpairs) { # now format the results
    my $wildbits = $bbpairs{$_} - $_;
    my $bq = P15 L2q $_;
    print $bq, ' ', P15 L2q ~ $wildbits, ' | ',
    $bq, ' ', P15 L2q $wildbits, "\n";
    }
    }

    auto_topo_main;
     
    Walter Roberson, Feb 1, 2004
    #2
    1. Advertisements

  3. :And here's a useful perl program that makes use of this Trick.

    Dang, a patch already.

    :# pack and unpack values. There are some conversions you can't do directly.

    :sub s2L($) { unpack 'L', shift } #string to unsigned 32 bit long

    :sub L2s($) { pack 'L', shift } #unsigned 32 long to string

    Those should both be 'N' instead of 'L' for proper functioning on
    little-endian machines.

    Surely little endian addressing was invented by aSat!n
     
    Walter Roberson, Feb 1, 2004
    #3
  4. Walter Roberson

    Randy Howard Guest

    Jonathan Swift's descendants will be sad to hear about that.
     
    Randy Howard, Feb 2, 2004
    #4
  5. |In article <bvjiln$1qt$>, -cnrc.gc.ca
    says...
    |> Surely little endian addressing was invented by aSat!n

    |Jonathan Swift's descendants will be sad to hear about that.

    Jonathan Swift's modest proposal applied only to eggs.
    Someone else is responsbile for the addessing architecture that was
    then dubbed "little endian".
     
    Walter Roberson, Feb 2, 2004
    #5
    1. Advertisements

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 (here). After that, you can post your question and our members will help you out.