netmask calculation trick

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

 

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

 

: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

 

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

 

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