The Net Wizard HauptseiteISP SetupNetzwerkeVelotourenSoftwareKryptografieVaria

Rechnen mit IP Adressen

IPs und Dezimalzahlen

Wer sich häufig mit Computern und Netzwerken beschäftigt, kommt immer wieder in die Situation, dass er mit IP Adressen rechnen muss. Das ist immer etwas mühsam, darum habe ich hier einige Perl Routinen zusammengestellt, die es erleichtern. Das Ganze beruht auf der einfachen Tatsache, dass IP Adressen auch als Zahlen im 256er Zahlensystem aufgefasst werden können. Das bedeutet, dass es möglich ist, eine IP Adresse in eine Dezimalzahl umzurechnen, und dann mit dieser Dezimalzahl ganz normal zu rechnen. Danach kann das Resultat wieder in eine IP Adresse umgewandelt werden.
    01:
    02:
    03:
    04:
    05:
    06:
    07:
    08:
    09:
    10:
    11:
    12:
    13:
    14:
    15:
    16:
    17:
    18:
    19:
    20:
    21:
    22:
    23:
    24:
    25:
    26:
    27:
    28:
    29:
    30:
    31:
    32:
    33:
    34:
    35:
    36:
    37:
    38:
    39:
    40:
    41:
    42:
    #!/usr/bin/perl 

    use strict;
    use warnings;

    sub ip2dec ($) {
        
        my $ip_num;

        my $ip=$_[0];
        if ( $ip =~ /(\d{1,3})\.(\d{1,3})\.(\d{1,3})\.(\d{1,3})/ ) {
            $ip_num = (($1*256**3) + ($2*256**2) + ($3*256) + $4);
        } else {
            $ip_num = -1;
        }
        return($ip_num);
    }



    sub dec2ip ($) {

        my $ip;

        my $ip_num=$_[0];

        if ( ($ip_num>0) && ($ip_num<4244897280) ) {
            my $o1=$ip_num%256;
            $ip_num=int($ip_num/256);
            my $o2=$ip_num%256;
            $ip_num=int($ip_num/256);
            my $o3=$ip_num%256;
            $ip_num=int($ip_num/256);
            my $o4=$ip_num%256;
            $ip="$o4.$o3.$o2.$o1";
        } else {
            $ip=-1;
        }

        return ($ip);
    }


Arbeiten mit Bereichen von IP Adressen

Bereiche von IP Adressen koennen mit der CIDR Notation zusammengefasst werden, falls sie zusammenhängend sind. Um diesen Mechanismus zu verstehen, schaut man sich am Besten die binäre Darstellung einer einer IP Adresse an. Nehmen wir 8.8.8.8, so ist das binär 00001000.00001000.00001000.00001000. Will ich jetzt herausfinden, was 8.8.8.8/24 bedeutet, dann betrachte ich als erstes nur die ersten 24 Bit der Adresse und fülle den Rest mit Nullen auf. Das gibt dann 00001000.00001000.00001000.00000000, oder 8.8.8.0. Dies entspricht der ersten Adresse dieses Bereiches. Analog kann man, um die letzte Adresse des Ranges zu bestimmen, die restlichen acht Bit mit Einsen auffüllen. Das ergiebt dann 8.8.8.255. Der Vorteil dieser Darstellung liegt auf der Hand. Um zu bestimmen, ob eine Adresse innerhalb des Bereiches ist, reicht es die ersten relevanten Bits zu vergleichen, was recht einfach zu implementieren ist.

Die minimale Routingtabelle

Aus dem bisher gesagten ergiebt sich eine interessante Fragestellung. Gegeben ist eine Anzahl von Netzen. Diese können sich überschneiden, direkt aufeinander folgen oder wild verteilt sein. Gesucht ist die minimale Anzahl von IP Adressen in der CIDR Notation, welche alle diese Adressen und nur diese Adressen enthält. Um dieses Problem zu lösen, habe ich ein kleines perl Programm geschrieben:
    001:
    002:
    003:
    004:
    005:
    006:
    007:
    008:
    009:
    010:
    011:
    012:
    013:
    014:
    015:
    016:
    017:
    018:
    019:
    020:
    021:
    022:
    023:
    024:
    025:
    026:
    027:
    028:
    029:
    030:
    031:
    032:
    033:
    034:
    035:
    036:
    037:
    038:
    039:
    040:
    041:
    042:
    043:
    044:
    045:
    046:
    047:
    048:
    049:
    050:
    051:
    052:
    053:
    054:
    055:
    056:
    057:
    058:
    059:
    060:
    061:
    062:
    063:
    064:
    065:
    066:
    067:
    068:
    069:
    070:
    071:
    072:
    073:
    074:
    075:
    076:
    077:
    078:
    079:
    080:
    081:
    082:
    083:
    084:
    085:
    086:
    087:
    088:
    089:
    090:
    091:
    092:
    093:
    094:
    095:
    096:
    097:
    098:
    099:
    100:
    101:
    102:
    103:
    104:
    105:
    106:
    107:
    108:
    109:
    110:
    111:
    112:
    113:
    114:
    115:
    116:
    117:
    118:
    119:
    120:
    121:
    122:
    123:
    124:
    125:
    126:
    127:
    128:
    129:
    130:
    131:
    132:
    133:
    134:
    135:
    136:
    137:
    138:
    139:
    140:
    141:
    142:
    143:
    144:
    145:
    146:
    147:
    148:
    149:
    150:
    151:
    152:
    153:
    154:
    155:
    156:
    157:
    158:
    159:
    160:
    161:
    162:
    163:
    164:
    165:
    166:
    167:
    168:
    169:
    170:
    171:
    172:
    173:
    174:
    175:
    176:
    177:
    178:
    179:
    180:
    181:
    182:
    183:
    184:
    185:
    186:
    187:
    #!/usr/bin/perl 
    #===============================================================================
    #
    #         FILE:  get_routes.pl
    #
    #        USAGE:  ./get_routes.pl 
    #
    #  DESCRIPTION:  compute the minimal set of routes given an input file
    #                containing various nets
    #
    #      OPTIONS:  ---
    # REQUIREMENTS:  ---
    #         BUGS:  ---
    #        NOTES:  ---
    #       AUTHOR:  Robert Meyer (rmeyer), <r.meyer@net-wizard.org>
    #      COMPANY:  ---
    #      VERSION:  1.0
    #      CREATED:  13.02.2011 11:01:53 CET
    #     REVISION:  ---
    #===============================================================================

    use strict;
    use warnings;

    # Get the input
    my $infile="routes.txt";
    my %ip_hash = ();
    my @first_ip=();
    my @n_ips=();
    my $n_ips=(256**4)-1;

    sub ip2dec ($) {
        
        my $ip_num;

        my $ip=$_[0];
        if ( $ip =~ /(\d{1,3})\.(\d{1,3})\.(\d{1,3})\.(\d{1,3})/ ) {
            $ip_num = (($1*256**3) + ($2*256**2) + ($3*256) + $4);
        } else {
            $ip_num = -1;
        }
        return($ip_num);
    }

    sub dec2ip ($) {

        my $ip;

        my $ip_num=$_[0];

        if ( ($ip_num>0) && ($ip_num<4244897280) ) {
            my $o1=$ip_num%256;
            $ip_num=int($ip_num/256);
            my $o2=$ip_num%256;
            $ip_num=int($ip_num/256);
            my $o3=$ip_num%256;
            $ip_num=int($ip_num/256);
            my $o4=$ip_num%256;
            $ip="$o4.$o3.$o2.$o1";
        } else {
            $ip=-1;
        }

        return ($ip);
    }

    # Read in the data and create a hash with the decimal
    # representations as key values. We will use this hash to
    # create all consecutive ip addresses
    sub read_nets {
        open IFILE, "<$infile" || die "Can't open $infile for reading";
        while (<IFILE>) {
            chomp;
            (my $ip, my $net) = split(/;/,$_);
            my $ip_dec=ip2dec($ip);
            my $net_dec=ip2dec($net);
            my $n_ip=$n_ips-$net_dec+1;
            for (my $i=0; $i<$n_ip; $i++) {
                $ip_hash{$ip_dec}=1;
                $ip=dec2ip($ip_dec);
                $ip_dec++;
            }
        }
    }

    # Sort the hash with the decimal representation of the
    # ip addresses as key values and construct all consecutive
    # ranges of ip addresses
    sub get_nets{

        my $last_key=-10;
        my $i=0;
        my $is_first=0;
        my $start_loop=1;
        foreach my $key (sort {$a<=>$b} keys %ip_hash) {
            my $ip=dec2ip($key);
            if ($start_loop==1) {
                $start_loop=0;
                $last_key=$key;
                next;
            }
            if ( $is_first == 1 ) {
                $i=1;
                $is_first=0;
            } elsif ( $key == ($last_key +1) ) {
                $i++;
            } else {
                my $net_start=$last_key-$i;
                my $net_start_ip=dec2ip($net_start);
                my $n_ips=$i+1;
                push @first_ip, $net_start;
                push @n_ips, $n_ips;
                $is_first=1;
            }
            $last_key=$key;
        }
    }


    # calculate the int(log2)
    sub intlog2 ($) {
        my $range=shift;
        my $i=0;
        while ($range > 0) {
            $range = $range >> 1;
            $i++;
        }
        $i--;
        return($i);
    }

    # recursive function to get the nets, that are within an ip range
    sub rec_get_cidr{

        my $first_ip=shift;
        my $n_ips=shift;
        # Stop recursion if the range is 0
        if ($n_ips<1) {
            return;
        }

        # The biggest possible net is the integer of log2(n_ips)
        my $max_net=2**(intlog2($n_ips));

        # Try, if the biggest possible net is within the given range
        my $start_net;
        if ( ($first_ip % $max_net) == 0 ) {
            $start_net=$first_ip;
        } else {
            $start_net=$first_ip-($first_ip % $max_net) + $max_net;
        }
        if ( ($start_net+$max_net)<=($first_ip+$n_ips) ) {
            my $new_n_ip=($start_net-$first_ip);
            my $start_net_ip=dec2ip($start_net);
            print "t4 $start_net,$start_net_ip,$max_net\n";
            rec_get_cidr($first_ip,$new_n_ip);
            my $new_start_net=$start_net+$max_net;
            $new_n_ip=($first_ip+$n_ips)-($start_net+$max_net);
            rec_get_cidr($new_start_net,$new_n_ip);
        } else {
            # The second biggest net is within the range
            $max_net=2**(intlog2($n_ips))/2;
            $start_net=$first_ip-($first_ip % $max_net) + $max_net;
            my $start_net_ip=dec2ip($start_net);
            print "t4 $start_net,$start_net_ip,$max_net\n";
            my $new_n_ip=($start_net-$first_ip);
            rec_get_cidr($first_ip,$new_n_ip);
            my $new_start_net=$start_net+$max_net;
            $new_n_ip=($first_ip+$n_ips)-($start_net+$max_net);
            rec_get_cidr($new_start_net,$new_n_ip);
        }
    }

    # loop through the created consecutive ip addresses and create
    # valid cidr notation nets
    sub create_cidr {

        for (my $i=0; $i<@first_ip; $i++) {
            rec_get_cidr($first_ip[$i],$n_ips[$i]);
        }
    }

    read_nets();
    get_nets();
    create_cidr();


In diesem Skript mach ich ziemlich exzessiven Gebrauch IP Adressen als Integers. Darum auch am Anfang die Helfer Routinen, welche die Konversion machen. Als erstes werden die Netze eingelesen (read_nets). Allerdings hatte ich ein leicht anderes input Format (Anstelle der /n Notation war jeweils die Netzmaske des entsprechenden Netzes angegeben). Danach wird ein hash mit den Adressen in Dezimaldarstellung als key und dem Wert eins aufgefüllt. Nachdem sämtliche Adressen im hash eingetragen sind, sortiert man den hash anhand der key values numerisch, um die Bereiche herauszufinden, die aneinander hängend sind (get_nets). Dabei werden die erste IP und die Anzahl IP's im jeweiligen Bereich je in ein Array gespeichert. Diese Bereiche werden dann nacheinander an eine Routine übergeben, die entsprechende CIDR records generiert (rec_get_cidr). In diesem Teil des Codes wird das grösste mögliche Netz gemäss CIDR im Bereich gesucht. Das ist entweder der ganzzahlige Wert des Logaritmus zur Basis 2 der Anzahl IP Adressen, oder diese Zahl geteilt durch zwei. Nachdem dieses Netz gefunden wurde, wird dieselbe Routine mit den Adressen vor dem gefundenen Netz, und mit denjenigen nach diesem aufgerufen. Die Abbruchbedingung für die Rekursion ist gegeben, wenn die Anzahl IP Adressen gleich Null ist.

Powered by w3.css