Advanced search


Ein Kunde berichtete über eine Nichterreichbarkeit des Webservers der Piratenpartei. Die Störung sah aus wie ein Routingproblem, aber es war viel viel schlimmer.

Zusätzlich zu der Nichterreichbarkeit der Webseite waren auch zwei Traceroutes mitgeliefert worden. Einer aus Kundensicht und einer vom Webserver aus. Die sehen so aus (IP Adresse des Kunden durch die eines Routers ersetzt)

traceroute from 178.19.71.117 to 178.19.224.1
 1  178.19.71.1 (178.19.71.1) [AS29551]  0.673 ms * *
 2  * * *
 3  * * *
 4  80.81.193.74 (80.81.193.74) [AS6695]  0.660 ms * *
 5  * * *
 6  * * 217.71.99.134 (217.71.99.134) [AS13237]  8.215 ms
 7  109.73.31.194 (109.73.31.194) [AS196714]  8.227 ms * *
 8  * * *
 9  * * *

Sowie

traceroute from 178.19.224.1 to 178.19.71.117
 1  rudo1-g01-115 (217.17.207.161)  18.793 ms  1.234 ms  5.662 ms
 2  NUE-2.de.lambdanet.net (217.71.100.33)  4.153 ms  4.303 ms  4.192 ms
 3  xe0-0-0.irt1.fra44.de.as13237.net (217.71.96.73)  7.408 ms  7.421 ms  7.426 ms
 4  decix.fra2.tng.de (80.81.192.83)  12.095 ms  12.027 ms  12.094 ms
 5  t4-1.decix.rt02.of.aixit.net (83.141.1.187)  12.080 ms  12.286 ms  12.279 ms
 6  v7.rt03.boe.aixit.net (83.141.0.249)  12.015 ms  12.500 ms  13.041 ms
 7  v3-rt01.boe.aixit.net (83.141.1.97)  12.021 ms  12.247 ms  12.502 ms
 8  * * *
 9  * * *

Führt man Traces von anderen Systemen aus, so scheint alles ok zu sein.

Nach direktem Kontakt zu einem Admin der BundesIT (vielen Dank für die Geduld mit meinen doch sehr erstaunten Fragen) stellte sich heraus.

  • Eingehende ICMP-Pakete sind bei der Firewall der Piratenpartei rate-limited.
  • Einige Server dort hatten die falsche Netzmaske, deswegen glaubte der Webserver, die Antworten im lokalen Netz ausliefern zu können.

Wie kommt man zu einer falschen Netzmaske? Ganz einfach: Die Server waren classful konfiguriert. 178.19.224.1 und 178.19.71.117 liegen nun mal im gleichen /16 (ehemals Class-B Netz).

Ob des Ratelimits weist der Traceroute die Sterne unterwegs auf: Die Antworten erreichen die tracende Maschine gar nicht.

Nebenbei stellte sich auch heraus, warum Ping komplett gesperrt und ICMP rate-limited ist: Man könnte ja herausbekommen, welche IPs benutzt werden.

Und das Problem wird schon länger gesucht, wie eine Diskussion auf Twitter zeigt.

Dokumentation ist das Stiefkind der IT. Aktuelle Doku is jedoch das Rückrat erfolgreicher Projekte. Wie hält man Dokumentation aktuell? In dem man sie freiwillig benutzt, weil sie einen Mehrwert abwirft. Netzplänen sollten also nicht nur das "Was ist" dokumentieren, sondern auch das "Was geschieht".

Admin kontra Managment

Typischerweise benutzt man zur Beantwortung der Frage, was denn da im Netz geschieht Trafficgraphen und für den groben Überblick eine Weathermap. Installation und Aufbereitung solcher Systeme ist ziemlich aufwendig. Wenn man sie schon hat, will man möglichst komplette Informationen an einer Stelle abrufen können.

Darüberhinaus benutzt man für die Projektdokumentation gern vereinfachende AdHoc Darstellungen, die schnell und auf Zuruf z.B. mit Visio erstellt werden. Diese verstauben dann in den Projektunterlagen, bis irgend ein Manager ein seit Monaten veraltetes Dokument in den Händen hält, um damit neue Planungen vorzunehmen und Entscheidungen zu fällen.

Obwohl Visio mächtig genug ist, die Dokumentation auch mit externen Datenquellen zu animieren, weigert sich der Netzwerkadmin, diesem Tool direkten Zugriffe auf die Netzwerkknoten zu erlauben. Außerdem müßte der Zugriff dann auch beim Kunden oder auf Präsentationen funktionieren.

Andererseits ist das Netzwerkmonitoring der Admins für den Manager zu komplex und zu mächtig. Endkunden will man gar nicht alle Details des realen Netzes zeigen. Schon gar nicht will man einen externen Zugriff des Endkunden auf die Managementsysteme selbst.

Einfach erstellt, einfach genutzt

Was liegt also näher, die Visio-Dokumente, die für den Endkunden erstellt wurden, auf eine Supportwebseite zu legen und dieser Webseite zu erlauben, die Graphik zu animieren? Zum einen sind die Dokumente nicht webtauglich und andererseits will man auf den Webseiten keine Office-Software aktiv laufen lassen.

Glücklicherweise kann Visio nach SVG exportieren. Und dieser Output ist hervorragend maschinell nachbearbeitbar. Mittlerweile ist SVG auch browserseitig ausreichend unterstützt, um dort bedenkenlos den Einsatz freizugeben. Die Anfangszeiten, bei denen extra Plugins benötigt wurden, sind glücklicherweise vorbei.

<g id="shape69-50" v:mID="69" v:groupContext="shape" v:layerMember="2"
     transform="translate(276.378,-523.305)">
 <title>Dynamic connector.69</title>
 <desc>G0/2</desc>
 <v:textBlock v:margins="rect(4,4,4,4)" v:tabSpace="42.5197"/>
 <v:textRect cx="21.292" cy="602.833" width="40" height="17.6036"/>
 <path d="M0 601.45 L336.41 603.27" class="st1" />
 <rect v:rectContext="textBkgnd" x="12.2454" y="598.034"
         width="17.3436" height="9.59985" class="st5"/>
 <text x="12.62" y="605.23" class="st6" v:langID="1031">
   <v:paragraph v:horizAlign="1"/>
   <v:tabList/>
   G0/2
  </text>
</g>

Um aus einem Visio-SVG eine Weathermap zu machen, müssen die manuell angelegten Verbinder eingefärbt werden. Je nach Auslastung der Leitung ändern sich die Farben von einem leichten Grün bis zu einem kräftigen Rot. (Hier mit einer anderen Linie.)

 <path d="M-6.07 595.28 L-8.11 806.72" class="st1" style='stroke:red'/>
netzplan-linie1

Da Leitungen in beide Richtungen Daten transportieren können, müssen die Verbinderlinien doppelt eingefärbt werden. Weathermaps lösen dies, in dem sie zwei Pfeile statt einer Verbindung einzeichnen und diese Pfeile separate einfärben. Schöner wäre es aber, wenn der Verbinder selbst seine Farbe ändern könnte. Glücklicherweise beherscht SVG Gradienten, um lineare Farbverläufe vorzugeben.

<linearGradient id="gruen-rot">
 <stop offset="0" style="stop-color:#00ff00;stop-opacity:1"/>
 <stop offset="1" style="stop-color:#ff0000;stop-opacity:1"/>
</linearGradient>
[...]
<path d="M-6.07 595.28 L-8.11 806.72" class="st1" style='stroke:url(#gruen-rot)'/>

Unglücklicherweise ist der Farbverlauf streng horizontal, so daß diese steile Linie den Farbwechsel nur in ihrer Breite durchmacht. Der Farbverlauf hätte eigentlich der Linie folgen sollen. Alle Versuchen mit Transformationen den Farbverlauf zu beeinflussen, waren vergeblich. Denn der Farbverlauf kann und muß separat gedreht werden.

<linearGradient id="gruen-rot" gradientTransform="rotate(90)">
 <stop offset="0" style="stop-color:#00ff00;stop-opacity:1"/>
 <stop offset="1" style="stop-color:#ff0000;stop-opacity:1"/>
</linearGradient>

Jetzt verlaufen die Farben wie gewünscht der Linie entlang.

Für jede Linie ist nun ein extra Gradient anzulegen. Dabei ist darauf zu achten, daß der Verlauf der Definition der Linie folgt, damit man später automatisiert die Leitungsauslastungen als Farbwerte an den Endstellen einsetzen kann. Die Zeichenrichtung im Visio hat wenig mit der Zeichenrichtung im SVG zu tun. Dies kann also komplexere Transformationen erfordern, denn eine Rotation um 180° dreht den Farbverlauf komplett aus dem Liniensegment heraus. Mit einer Matixoperation kann man den Verlauf gleich wieder an die richtige Stelle schieben.

Darüberhinaus empfiehlt es sich, kleine Ansätze an den Verbindern stehen zu lassen, um keinen so abrupten Farbwechsel am Gerät zu bekommen. Man setzt dazu seine Start- und Endwerte erst bei 10% vorm Ende. Da die Farbwerte später ersetzt werden sollen, muß bereits hier vermerkt werden, welches Interface an welchem Gerät zum Einsatz kommen soll.

<!-- device:interface max_bandwith -->
<linearGradient id="line13" gradientTransform="matrix(-1,0,0,-1,1,1)">
 <stop offset="0" style="stop-color:#000000;stop-opacity:1"/>
 <stop offset=".1" style="stop-color:#00ff00;stop-opacity:1"/>
 <stop offset=".9" style="stop-color:#ff0000;stop-opacity:1"/>
 <stop offset="1" style="stop-color:#000000;stop-opacity:1"/>
</linearGradient>

Es kann aber passieren, daß die Umfärbung völlig scheitert: Die Linie verschwindet ganz. Dies passiert, wenn eine Linie exakt horizontal oder vertikal liegt. Dann ist die Höhe oder Breite der Linie exakt Null und die Gradientenoperation bricht mit einer Division durch Null ab. In dem Fall muß man einfach einen Endpunkt der Linie um ein winziges Stück verschieben. (Wieder eine andere Linie.)

<path d="M0 588.19 L222.79 588.20" class="st1" style='stroke:url(#line3)'/>

Alles zusammen sollte sich dann ein Bild ergeben, bei dem klar ersichtlich ist, welche Meßstelle die Daten liefern wird. Diese wurde hier beschriftet und muß das grüne Ende des Verbinders erhalten. Damit sind die Voraussetzungen für eine maschinelle Überarbeitung geschaffen.

netzplan-animiert

Besonders hübsch ist, wie der Farbverlauf auch den gebogenen Pfaden folgt.

Diese manuellen Anpassungen des Visio-Exportes sind in einer guten halben Stunde zu erledigen. Mit etwas Übung geht dauert es nur einige Minuten. Komplexere Netzpläne oder ewig wiederkehrende Exports kann man automatisieren.

Die SVG Graphik kann nur auf einem beliebigen Webserver als statische Datei abgelegt werden (Mime-Type: image/svg+xml). Die URL kann zur Abnahme herumgeschickt werden.

Leben einhauchen

Zur Weathermap mutiert dieses Bild dann, indem es von einem Perl/PHP/Whatever-Script überarbeitet wird. Dieses holt sich bei Bedarf die notwendigen Daten aus einer Datenbank (MRTG, etc.) oder live von den Geräten. Der Farbwert wechselt gemäß rgb(255*load, 255*(1-load), 0) für die Hin- und Rückrichtung des Links.

Es spricht überhaupt nichts dagegen, weitere Angaben mit der Graphik zu verknüpfen. So kann das Symbol der aktiven Technik zwischen grau und rot umgefärbt werden, um die CPU-Last zu visualisieren. Ebenso bietet es sich an, die Speicherauslastung als "Füllhöhe" der Füllfarbe anzuzeigen. Wer noch Ideen hat, möge sie in die Kommentare schreiben oder einfach selbst umsetzen.

Die Implementation auf dem Webserver kann als PHP Datei die Daten, z.B. per SSH von einem zu SNMP berechtigten Host, holen und die SVG Datei vor der Ausliefung überarbeiten. Der SNMP-Host liefert, z.B. per command="/usr/local/sbin/obtain-line-rates.pl customer", die aktuellen Input- und Outputraten ausschließlich für die hinterlegten Geräte und Interfaces.

#! /usr/bin/perl

use strict;
use warnings;

my %points = ();

if($ARGV[0] eq 'customer') {
    %points = (
        'S1' => ['Port-channel32', 'Port-channel1', 'GigabitEthernet4/3', 'GigabitEthernet1/3', 'GigabitEthernet1/2'],
        'R1' => ['GigabitEthernet0/0', 'GigabitEthernet0/1', 'GigabitEthernet0/3'],
        'R2' => ['GigabitEthernet0/0', 'GigabitEthernet0/1', 'GigabitEthernet0/2'],
        'R3' => ['GigabitEthernet0/0', 'GigabitEthernet0/1', 'GigabitEthernet0/2'],
    );
} else {
    die "Usage: $0 name\n";
}

my %conf = ();
# Fill the config with the SNMP communities

# Read in the interface Name-ID mapping
my %ids = ();
foreach my $host (keys %conf) {
    open(S, "snmpbulkwalk -v2c -c '$conf{$host}' -t 2 -r 2 -L o: $host IF-MIB::ifDescr |") || next;
    while(<S>) {
        next unless my ($id,$val) = /\.([^\s.]+) = \S+: (.*\S)/;
        next unless grep {$_ eq $val} @{$points{$host}};
        $ids{$host}{$id} = $val;
    }
    close(S);
}

# Read the line rates and print them
while(my($host,$hh) = each %ids) {
    my @m = ((map {"1.3.6.1.4.1.9.2.2.1.1.6.$_"}  keys %$hh),
             (map {"1.3.6.1.4.1.9.2.2.1.1.8.$_"} keys %$hh));
    my $mc = $#m + 1;
    my $ms = join(" ", sort @m);

    my %c = ();

    open(S, "snmpget -v2c -c '$conf{$host}' -t 2 -r 2 -L o: $host $ms |") || next
    while(<S>) {
        next unless my ($dir,$id,$val) = /(\d+)\.([^\s.]+) = \S+: (.*\S)/;
        next unless defined $hh->{$id};
        $c{$hh->{$id}}{$dir} = $val;
    }
    close(S);

    while(my($name,$vals) = each %c) {
        print "$host:$name ".$vals->{6}," ".$vals->{8}."\n";
    }
}

Mein PHP Script zur Überarbeitung der Graphik ist dann ebenfalls ziemlich einfach:

<?
$unknown_color = '909090'; // Make links grey if no data is available
$svg_file = 'path/to/plan.svg';

// Read the current in/out bandwith values
$max_bandwidth = 1;
$max_bandwidth = max($max_bandwidth, $match[2], $match[3]);
$traf = popen("ssh -i path/to/sshkey user@snmp-host true", "r");
while($line = fgets($traf)) {
    if(preg_match('/^(\S+:\S+) (\d+) (\d+)$/', $line, $match)) {
        $inrate [$match[1]] = $match[2];
        $outrate[$match[1]] = $match[3];
        $max_bandwidth = max($max_bandwidth, $match[2], $match[3]);
    }
}
pclose($traf);

header("Content-Type: image/svg+xml");

$svg = fopen($svg_file, "r");
while($line = fgets($svg)) {
    if(preg_match('/<!-- (\S+:\S+) (\d+) -->/', $line, $match)) {
        $current_interface = $match[1];
        $current_speed = $match[2];
        if(is_numeric($_REQUEST['maxscale']))
          $current_speed *= $_REQUEST['maxscale'];
        elseif($_REQUEST['maxscale'] == 'max')
          $current_speed = min($max_bandwidth, $current_speed);
    }
    if(preg_match('/<linearGradient id="(\S+)"/', $line, $match)) {
        $current_gradient = $match[1];
    }
    if($current_speed > 0 &&
       preg_match('/^(\s+<stop offset=".(\d)" style="stop-color:#)\S{6}(;.*)/', $line, $match)) {
        if(isset($inrate[$current_interface])) {
            $util = (1.0*$inrate[$current_interface])/$current_speed;
            $incolor = sprintf("%02x%02x00", 255*$util, 255*(1-$util));
            $inline[$current_gradient] = sprintf("%02d%% %.2fMbps", $util*100, $inrate[$current_interface]/1000000.0);
        } else {
            $incolor = $unknown_color;
            $inline[$current_gradient] = "n/a";
        }
        if(isset($outrate[$current_interface])) {
            $util = (1.0*$outrate[$current_interface])/$current_speed;
            $outcolor = sprintf("%02x%02x00", 255*$util, 255*(1-$util));
            $outline[$current_gradient] = sprintf("%02d%% %0.2fMbps", $util*100, $outrate[$current_interface]/1000000.0);
        } else {
            $outcolor = $unknown_color;
            $outline[$current_gradient] = "n/a";
        }
        switch($match[2]) {
         case  1: print "$match[1]$outcolor$match[3]\n"; break;
         case  9: print "$match[1]$incolor$match[3]\n"; break;
         default: print $line; break;
        }
    } elseif(preg_match('/^\s*<title>Dynamic connector[.\d]*<\/title>\s*$/', $line)) {
        // Skip output of title
    } elseif(preg_match('/style=.stroke:url\(#(\S+)\)./', $line, $match) && isset($inline[$match[1]])) {
        print $line;
        print "\t\t\t<title>In: {$inline[$match[1]]}\nOut: {$outline[$match[1]]}</title>\n";
    } else {
        print $line;
    }
}
fclose($svg);
?>

Fazit

Kundenspezifische Views wurden mit dem Monitoringsystem verknüpft, so daß alle Beteiligte einen Vorteil davon haben:

  • Der Kunde kann seinen Teil des Netzes anhand der für ihn erstellen Dokumentation live einsehen.
  • Der Admin bekommt einen Einblick der Kundensicht und kann bei Wartungen die Auswirkungen auf den Kunden überprüfen.
  • Der Admin kann - wenn live verknüpft - eine aktuelle Weathermap eines beschränkten Bereiches während einer Umbaus offen halten. Die Dokumentation wurde beispielsweise adhoc für diesen Umbau erstellt und enthält so nur die interessanten Teile.
  • Der Support kann auf einen für den Kunden relevanten Teil der Netzstruktur schauen, während er mit dem Kunden telefoniert.
  • Da die Dokumentation auf der Supportwebseite liegt, kann sie nicht in veralteter Form im Mailpostfach eines Vertrieblers oder in den "Eigenen Dokumenten" eines Managers versauern.

Es gibt also durchaus Gründe, Netze zu dokumentieren und diese Dokumentation aktuell zu halten: Sie aktiv zu nutzen.

In order to terminate a large number of broadband customers on an LNS, MPD on FreeBSD was recommended to me. There seems to exists a group of Russian operators using this software for really large deployments. Alternativly OpenL2TP could be used. However  OpenL2TP does handle all the PPP sessions in user space, while MPD relies on NetGraph.

First contact

The setup is simple, even through the documentation of MPD lacks expressivness. What a command does, is documented at a single point at most. If you do not know where to look, you're stuck.

Additionaly MPD strictly distinguishes between the layers of operation. So you can only configure something at the place (and find documentation) in which this setting is relevant. I.e. vanJacobson compression occurs in the IPCP part of (PPP) bundles. Protocol field compression as part of the PPP session is negotiated in the link layer, which is responsible for setting up PPP. Therefore, all such settings are on this layer—even the authentication protocols to be used by LCP.

The configuration file is strictly linear. Each command can change the current layer. Thus the following commands might be executed in a different context. I can recommend to create the configuration manually (online) and enable "log +console".

Disillusionment

First experiments turned into pure horror.

lasttest-mpd-patch1

After a quite funny start "no more threads" and "Fatal message queue overflow!" messages were logged. The MPD crashed. But it crashed controlled, so finished all sessions before terminating itself.

The event handling for radius requests caused the problems. MPD implemented event queuing by reading and writing an internal pipe. This pipe correlated to a ring buffer containing the real event information. In order to prevent blocking writes to the pipe, no more bytes (dummy values for "there's an event") should be written beside those that fit into the kernel buffer.

The obvious patch is to increase the pipe size and extend the ring buffer. But I did not make any success: it got a segfault.

Since each event on each layer generates several further events, a event flood can happen. But the single thread for event processing must not block! If any potentional blocking may occur, a new thread is spawned and handled asynchonly. So RADIUS authenication and accounting exceeded the limit of 5000 threads per process. On the RADIUS server, the load looked similar.

A carrier experienced during my tests, how badly RADIUS servers may react. The commercial LAC queries the RADIUS on every login attempt to determine the appropriate LNS for the realm. During a simultanious drop of all sessions, he was overwhelmed by so many requests that his radius servers—specifically the database backend—gave up and the entire DSL infrastructure quit the service. Meanwhile, the realm to LNS mapping is a static configuration.

Slowly, more slowly

It is always better to be kind to its suppliers, particularly to the radius servers. So I droppedthe entire event handling of the MPD and wrote it from scratch using mesg_queue. The required library was already used by MPD.

A distinction is made for "sequential" and "parallel" events. Sequential events run under the global lock the MPD. They keep serialized in the same order in which they were generated. Thus, the layers do not get confused, and event processing can rely on the previous actions. Parallel processing is used for external communication. They are handeled by a fixed number of active worker threads.

The length of both queues determine MPD's overload (Load = 2×queue_len(serial) + 10×queue_len(parallel)). An overloaded MPD does refuse new connections.

Well equipped, I was full of hope and suddenly disappointed. The kernel paniced: deep, deep inside the NetGraph code.

bsd-lasttest-panic-1

And not just once, but also at a completely different place.

bsd-lasttest-panic-2

Is the netgraph code broken? Does the kernel has problems with rapid creation and deletion of interfaces? Do I work too fast?

Even RADIUS accounting created problems, because a test equipment managed to connect, drop, and reconnect three times within one second. My SQL unique constraints refused to accept such data. The MPD is definitely too fast! I added a pause of 20ms (configurable) between the processing of two serial events.

My thread for the serial processing runs separately from the main thread, which was not the case in the original code. I put a separate lock to each NetGraph call. This prevents concurrent access on NetGraph sockets.

So the system started to behave stable.

Stress testing

I choosed an OpenL2TP on Linux for generating lots of sessions:

  • Open a random number of L2TP tunnels.
  • Create up to 9000 PPP sessions (round robin over the L2TP tunnels) as fast as possible.
  • Create new PPP sessions at a limited rate up to 9000 sessions are established.
  • Drop and recreate a random selection of 300 sesssion to simulate a living broadband environment.
  • Stay a while and finally drop the sessions one after the other.

A typical test result is given below: "Sessions" are generated by OpenL2TP/pppd, each of them make MPD "Links" within the tunnels, and negotiate the PPP-"Bundles". Queue lengths are plotted too.

mpd-logins-13040106

The initial length of the parallel queue is large, then the overload functionality throttles the connection rate. The plots for sessions, links and bundles are practically identical. There are no differences, because only successful sessions are count.

It is also nice to see how high the serial queue jumps when interface disappear: The original MPD is definitely susceptible to queue overrun. If this effect occurs, the original MPD drops all connections and stops. An unacceptable situation.

The FreeBSD box with MPD runs at a maximum load of 3 and requires 280 MB of RAM. The Linux machine generates a load of 20 during connection setup and a load of 50 on connection release. The memory required on the Linux side is about 2 GB to hold the many pppd instances.

Touch the limits

Next test simulates a interconnection breakdown: Instead of terminating pppd instances, let's drop the L2TP tunnels.

mpd-logins-13040211

Clearly bundles, as the highest layer, are removed first. Then the associated L2TP links go down. The load on BSD box rises up to 6.

On Linux side a disaster starts: All pppd instances compete for the scheduler in order to stop working. The load rises to over 700, and the machine will not calm down. A courageous "killall -9 pppd" redeemed the machine after half an hour.

But how far can we go? More than 10000? More than 20000? Let's try it out:

mpd-logins-13040213

The setup rises rapidly to 11,500 sessions and stopped spontaneously. On the Linux side OpenL2TP reports erroneous "RPC" parameters: It reached the limits of its implementation. The machine gets tangled and needs to be rebooted. The BSD box is fine.

And now several times in succession:

mpd-logins-130401

Up and down, again and again. Sometimes a crash by my own stupidity, but it does!

Going live

In the production environment, it works surprisingly quiet. Nevertheless, the system keeps crashing:

bsd-lasttest-panic-3

All crashes are now only located in the libalias module. Although the code was moved to svn-HEAD … Read more.

But there are further changes in the MPD code:

  • In order to replace the code in production quickly, the MPD quit itself when there are no more sessions open. The configuration option is called "delayed-one-shot". So MPD needs now to be called in a loop (/usr/local/etc/rc.d/mpd5 contains command="/usr/local/sbin/${name}.loop")
$ cat /usr/local/sbin/mpd5.loop
#! /usr/local/bin/bash

nohup /usr/local/bin/bash -c "
cd /
while true; do
  /usr/local/sbin/mpd5 -k -p /var/run/mpd5.pid -O
  sleep 5
done
"  >/dev/null 2>/dev/null </dev/null &
  • The RADIUS accounting reports only a limited set of termination cause codes, but I do need the complete error message:
ATTRIBUTE      mpd-term-cause  23      string
  • Relevant system logging (interfaces come and go, users log on and off) is now activated permanently, not only for debugging. Similarly, errors are always relevant. Otherwise, the server would run blind.

Oh, and the patch: Here you are. Please feel free to ask for commercial Support.

Bloggen, erzählen, kommunizieren von Problemen hilft. Man bekommt Aufmerksamkeit, die man sonst nie bekommen würde.

Vorwärts immer, rückwärts nimmer

Inzwischen sind auch Entwickler von FreeBSD aufmerksam geworden und empfehlen einen radikalen Schnitt:

  • Upgrade auf SVN-HEAD, die aktuelle Entwicklerversion. Schließlich läuft darauf auch die FreeBSD.org Plattform.
  • Das Treiberproblem mit dem Adaptec ist ja auch gelöst. Wenn auch erst seit heute mittag.
  • Man kann auf pf statt libalias wechseln. Das Locking bremst nicht mehr die Performance aus wie in 8.x oder 9.x.
  • Deine Probelme werden nicht weg sein, aber developers sind deutlich motivierter.

Das klingt nach einem Plan. Aber nach einem, den man erstmal an einer Testmaschine und dedizierten Lasttests ausprobiert.

Wird fortgesetzt ...

Wird der MPD als LNS unter Hochlast gesetzt, können die L2TP Verbindungen wegbrechen. Die Gründe dafür sind manigfaltig, exemplarisch werden hier einige betrachtet.

Schadensmaximierung

Im Code des MPD sind verschiedenste Asserts verteilt. Wenn davon einer zuschlägt, beendet sich der MPD kontrolliert. Und wenn sich der MPD beendet, fliegen alle Nutzer raus. Ein typischer Assert ist:

ASSERT "new == PHASE_DEAD || new == PHASE_TERMINATE || new == PHASE_AUTHENTICATE"
 failed: file "lcp.c", line 418

Auslöser der Bedingung ist eine Nutzeranmeldung, die nicht protokollkonform abläuft. Das kann immer mal passieren.

Abstürzen darf eine Software deswegen aber nicht. Was könnte man stattdessen tun?

Man sollte diese eine Anmeldung abbrechen, den einzelnen Kanal herunterfahren und einfach weiter machen.

Interface dicht

Wenn es richtig brummt, geht viel Datenvolumen in Richtung der Endgeräte über den L2TP Tunnel. Auf der Datenleitung mischen sich L2TP-Datenpakete und L2TP-Steuerbefehle.

L2TP: Control connection terminated: 6 (No buffer space available)

Wenn ein Interface ausgehend unter Volllast steht, kann es nicht mehr die Daten von den einliefernden Prozessen abnehmen. Die Unmöglichkeit Daten abzunehmen, signalisiert das Unix mit ENOBUFS.

Der MPD beendet daraufhin sofort den L2TP Kanal und wirft alle Nutzer raus. Eine viel bessere Lösung gibt es vermutlich nicht: Man könnte etwas warten und die Aussendung erneut probieren. Für den L2TP Kanal sollte es einem die Mühe wert sein.

Andererseits kann man die Netzwerkkarte effektiver konfigurieren. Denn die hat wirklich ein Problem.

# sysctl dev.igb | fgrep no_desc_avail
dev.igb.1.queue0.no_desc_avail: 19
dev.igb.1.queue1.no_desc_avail: 0
dev.igb.1.queue2.no_desc_avail: 9
dev.igb.1.queue3.no_desc_avail: 0 

Die Defaulteinstellung von hw.igb.txd und hw.igb.rxd kann und sollte man von 1024 auf 4096 erhöhen. Das entschärft das Problem.

Darüberhinaus ist besonders eine Karte mit mehreren Queues anfällig für dieses Problem: Der MPD handelt alle L2TP Verbindungen in einem Thread ab und so landen diese alle in der gleichen Sendequeue. Da vier Sendequeues vorhanden sind, werden diese nur mit einem Viertel der möglichen Geschwindigkeit geleert.

Mehrere LNS laufen unter igb, andere unter em-Treibern. Der em-Treiber hat nur eine ausgehende Warteschlange und diese Maschinen sind deutlich unauffälliger gegen diese Abbrüche. Also wechseln alle LNS von igb auf em.

Die 5%-Hürde führte bei der diesjährigen Bundestagswahl spektakulär zu einem Verwerfen von fast sechs Millionen Stimmen. Auch ich hatte mir dazu Gedanken gemacht. Der überarbeitete Vorschlag besteht darin bis zu 5% der Stimmen im Sinne einer stabilen Mehrheitsfindung zu opfern. Doch was würde eine solche Änderung normalerweise bedeuten?

Für die Beantwortung der Frage, ob die Wahl 2013 ein Ausreißer war oder einem Trend folgt, ist ein Blick in die Vergangenheit notwendig. Dabei stehen ausschließlich die Stimmen und Parteien im Vordergrund, die es nicht in den Bundenstag geschafft haben: Die Sonstigen.

Ausgehend von den Daten des Bundeswahlleiters wurden für jedes Jahr die Bundesergebnisse erfaßt. Zu beachten sind zwei Ausnahmen:

  • Im Jahr 1949 gab es keine 5%.-Hürde
  • Im Jahr 1990 wurde in Ost und West getrennt eine 5%-Hürde angewandt.
Jahr Angetretene Parteien Gültige Stimmen Sonstige Parteien 5%-Hürde Verworfene Stimmen %-Anteil Sonstige
1949 15 23732398 Wahl ohne 5%-Hürde
1953 13 27551272 6 1377564 1803026 6,54
1957 13 29905428 6 1495271 2010826 6,72
1961 9 31550901 5 1577545 1796408 5,69
1965 11 32620442 7 1631022 1186449 3,64
1969 12 32966024 8 1648301 1801699 5,47
1972 8 37459750 4 1872988 348579 0,93
1976 16 37822500 12 1891125 333595 0,88
1980 12 37938981 8 1896949 749646 1,98
1983 13 38940687 8 1947034 201962 0,52
1987 16 37867319 11 1893366 512817 1,35
1990 24 46455772 18 2322789 3740292 8,05
1994 22 47105174 16 2355259 1698766 3,61
1998 33 49308512 27 2465426 2899822 5,88
2002 24 47996480 18 2399824 1459299 3,04
2005 25 47187988 19 2359399 1757610 3,72
2009 27 43371190 21 2168560 2606902 6,01
2013 30 43726856 25 2186343 6859439 15,69

Für die Trendanalyse sind Graphen aber sicher besser geeignet. Also mal schauen, wie die "Sonstigen Parteien" sich so verteilen. Die Anzahl der Stimmen, die unter die 5%-Hürde fallen habe ich im Sinne meines Vorschlags gleich gestrichen.

wahl-sonstige-historie

Es ist klar zu erkennen, daß der Trend zu immer mehr Parteien bei der Wahl geht. Erst 2013 ist ein so erheblicher Teil der Stimmen verworfen worden. Der Wert im Jahr 1990 geht maßgeblich auf den knappen Verlust der Grünen im Westgebiet mit 4,8% zurück. Insofern besteht in beiden Jahren eine ähnliche Situation: Es gibt in beiden Fällen Parteien, die knapp die 5%-Hürde verfehlen, deren Stimmen aber fast komplett über der summierten 5%-Hürde liegen.

Die nun offene Frage ist, wie sich die Begrenzung der 5%-Hürde auf maximal 5% der zu verwerfenden Stimmen auswirkt. Welche Parteien kommen somit wie stark in die Parlamente? Ist dann die damals geschlossene Koalition immer noch möglich?

Jahr Gebildete
Koalition
Zusätzliche Parteien beim Abschneiden
von unten
Zusätzliche Parteien beim Abschneiden
von allen
Alte Koalition weiterhin noch möglich?
1953 CDU/CSU,FDP, DP, GB/BHE   12 KPD    6 KPD
   3 BP
Ja/Ja
1957 CDU/CSU, DP   26 GB/BHE   10 GB/BHE Ja/Ja
1961 CDU/CSU, FDP   15 GDP (DP-BHE)    4 GDP (DP-BHE) Ja/Ja
1965 CDU/CSU, FDP 5%-Hürde nicht überschritten
1969 SPD, FDP   23 NPD    3 NPD Nein/Ja
1972 SPD, FDP 5%-Hürde nicht überschritten
1976 SPD, FDP
1980 SPD, FDP
1983 CDU/CSU, FDP
1987 CDU/CSU, FDP
1990 CDU/CSU, FDP   27 GRÜNE   17 GRÜNE
   5 REP
Ja/Ja
1994 CDU/CSU, FDP 5%-Hürde nicht überschritten
1998 SPD, GRÜNE   13 REP    5 REP
   1 DVU
Nein/Ja
2002 SPD, GRÜNE 5%-Hürde nicht überschritten
2005 CDU/CSU,SPD
2009 CDU/CSU, FDP   13 PIRATEN    5 PIRATEN
   2 NPD
Ja/Ja
2013 CDU/CSU, SPD
CDU/CSU, GRÜNE
SPD, LINKE, GRÜNE
  31 FDP
  31 AfD
  14 PIRATEN
  27 FDP
  27 AfD
  10 PIRATEN
   4 NPD
   2 FREIE WÄHLER
Ja/Ja
Ja/Ja
Nein/Nein

Fazit

Die Beschränkung der zu verwerfenden Stimmen auf maximal 5% der gültigen Stimmen ist historisch gesehen nicht schädlich.

Das Verfahren, die Parteien solange rauszuwerfen, bis die 5%-Hürde überschritten würde (Abschneiden von unten), verhindert in zwei Jahren (1969/1998) die doch knappe Koalition. Es kam in den letzten Jahren immer nur die stärkste der sonstigen Parteien hinzu, oft sogar fast in Fraktionsstärke.

Das Verfahren, allen sonstigen Parteien die Stimmen wegzunehmen, bis die 5%-Hürde erreicht ist (Abschneiden von allen), verändert an den historischen Regierungen nichts. In allen Fällen sind die zusätzlich hinzukommenden Parteien deutlich unter Fraktionsstärke und es kommen mehr Parteien ins Parlament.

Die Auswirkungen des "Abschneidens von allen" sind demokratischer (mehr sonstige Parteien, geringerere Einfluß für einzelene sonstige Parteien).

Die Cisco ASA kann mit mehreren CAs umgehen, aber wann kommen welche Zertifikate zur Anwendung? Wie funktioniert das mit mehren CA? Wie überlebt man den Rollover von CA-Schlüsseln?

Hier kommt fast ausschließlich L2TP over IPSec zum Einsatz, weil dieses von praktisch allen Betriebssystemen nativ unterstützt wird. Es ist also keine Clientsoftware notwendig. Für diesen Artikel wird auch nur der Fall behandelt, wenn überhaupt eine Zertifikatsauthenisierung stattfindet.

Was im Hintergrund passiert

Wählt sich ein VPN-Client ein, präsentiert er zuerst sein Zertifikat (aggressive Mode). Zu diesem Zeitpunkt hat die ASA noch keinerlei weitere Informationen und prüft das Client-Zertifikat gegen alle konfigurierten trust-points.

Wurde das Nutzerzertifikat für gültig befunden, schaut die ASA anhand der Angaben des Client-Zertifikats in den certificate map nach, welche Kennung in der tunnel-group-map nachgeschlagen werden soll. Dort findet sich dann die entsprechende tunnel-group. Diese Indirektion gestattet es verschiedene Zertifikatseigenschaften zu analysieren die dann doch nur auf wenigetunnel-groups zusammenfallen.

Fehlt ein passender Eintrag in der certificate-map, wird versucht, den OU-Eintrag im Subject des Client-Zertifikats alstunnel-group Bezeichner zu finden.

Schlägt auch dieses fehl, so wird die Gruppe DefaultRAGroup genutzt.

Nun steht fest, welche tunnel-group genutzt werden soll. Von dort holt sich die ASA den zu verwendenden trust-point. Dieser legt fest, welches Server-Zertifikat ausgewählt wird.

Steht in der tunnel-group auch das Kommando chain, so wird nicht nur das Server-Zertifikat, sondern die ganze Zertifikatskette dieses trust-points mitgeschickt.

CA-Rollover

Es ist möglich, als CA-Zertifikat eines Trust-Points auch ein Zwischenzertifikat (intermediate) einzuspielen. In Verbindung mit derchain Option liefert die ASA dann die Zertifikatskette aus, die der Client zur Validierung benötigt.

Die bisherige aktive CA besteht, weil nach wie vor von ihr ausgestellte CA-Zertifikate im Umlauf sind, die validiert werden müssen. Das Zertifikate der ASA unter dieser CA ist allerdings abgelaufen.

asa-hosting# sh crypto ca certificates iks2013 | in ^C|cn|Name|ate:
Certificate
  Issuer Name:
    cn=CA der IKS Service GmbH (SIGN) 2013
  Subject Name:
    cn=asa-hosting.net.iks-jena.de
  Validity Date:
    start date: 09:15:08 CET Jan 10 2013
    end   date: 09:15:08 CET Jan 10 2014
CA Certificate
  Issuer Name:
    cn=CA der IKS Service GmbH (SIGN) 2013
  Subject Name:
    cn=CA der IKS Service GmbH (SIGN) 2013
  Validity Date:
    start date: 16:48:03 CET Jan 9 2013
    end   date: 16:48:03 CET Feb 8 2015

Zuerst einmal wird die CA des neuen Jahres von der alten CA signiert. Diese Zwischenzertifikat ist der Ersatz für die bisherige alte "iks2013". Überall, wo ikev1 trust-point iks2013, steht nun ikev1 trust-point iks2013-14.

asa-hosting# sh crypto ca certificates iks2013-14 | in ^C|cn|Name|ate:
Certificate
  Issuer Name:
    cn=CA der IKS Service GmbH (SIGN) 2014
  Subject Name:
    cn=asa-hosting.net.iks-jena.de
  Validity Date:
    start date: 02:50:30 CET Jan 10 2014
    end   date: 02:50:30 CET Jan 10 2015
CA Certificate
  Issuer Name:
    cn=CA der IKS Service GmbH (SIGN) 2013
  Subject Name:
    cn=CA der IKS Service GmbH (SIGN) 2014
  Validity Date:
    start date: 22:09:53 CET Jan 8 2014
    end   date: 22:09:53 CET Jan 18 2016

Dazu kommt noch das CA des neuen Jahres, die überall dort als trust-point verwendet wird, wo keine alten Zertifikate mehr im Umlauf sind.

asa-hosting# sh crypto ca certificates iks2014 | in ^C|cn|Name|ate:
Certificate
  Issuer Name:
    cn=CA der IKS Service GmbH (SIGN) 2014
  Subject Name:
    cn=asa-hosting.net.iks-jena.de
  Validity Date:
    start date: 02:50:30 CET Jan 10 2014
    end   date: 02:50:30 CET Jan 10 2015
CA Certificate
  Issuer Name:
    cn=CA der IKS Service GmbH (SIGN) 2014
  Subject Name:
    cn=CA der IKS Service GmbH (SIGN) 2014
  Validity Date:
    start date: 22:08:13 CET Jan 8 2014
    end   date: 22:08:13 CET Feb 7 2016

Mittels der crypto ca certificate map Regeln werden die Tunnel-Gruppen so ausgewählt, daß dem Client das jeweils passende Server-Zertifikat vorgelegt wird.

Praktisch genügt es überall, iks2013-14 zu verwenden, weil jeder Client die alte oder neue CA kennt. Mit dem Zwischenzertifikat können beide Clientarten korrekt validieren. Man kann aber mit diesen drei Trust-Points die alten CA-Zertifikate stückweise und im laufenden Betrieb entfernen.

asa-aa-9

In unserer shared Exchange-Umgebung, auf der auch kleine Kunden ein paar Postfächer preisgünstig hosten können, gibt es Quota für die Postfächer. Und wenn dann jemand gegen das Quota rennt, will er natürlich wissen, warum das Postfach voll ist. Als Admin hat man aber sinnvollerweise keinen Einblick in die Inhalte. Was also tun?

Werkzeuge

Glücklicherweise gibt es die PowerShell. Microsoft hat schon vor einigen Jahren damit angefangen, Funktionalitäten zuerst für die Kommandozeile bereit zu stellen und die graphischen Interfaces dann nur bei Bedarf anzubinden. Fast logischerweise ist eine solche Statistikfunktion also auch nicht über die graphischen Administrationsoberflächen erreichbar.

Das benötigte Kommando heißt Get-MailboxFolderStatistics. Es liefert eine Statistik über die Ordner eines Postfaches. Also genau das, was ich brauche.

Als erste Frage stellt die nach der Auswahl. Optionen, die die GUID oder ähnlichen Quatsch haben wollen, sind ungeeignet. Aber mit -Identity kann man E-Mail-Adressen angeben.

Bleibt also nur noch mit Where-Object sich auf die relevanten Folder zu beschränken, diese nach Größe zu sortieren und das Ergebnis in Tablenform auszugeben.

Ergebnis:

[PS] C:\Windows\system32>Get-MailboxFolderStatistics -Identity email@domain |
> where-object FolderSize -gt 0 |
> Sort-Object FolderSize -Descending |
> format-table FolderPath,FolderSize,ItemsInFolder

FolderPath                FolderSize  ItemsInFolder
----------                ----------  -------------
/Posteingang               646.6 MB           1407
/Sent                      236.5 MB            678
/Trash                     2.239 MB             64
/Deletions                 1.691 MB             48
/Drafts                    781.2 KB              8
/Gelöschte Elemente        476.3 KB              9
/Gesendete Elemente         39.0 KB              4
/Kalender                   12.4 KB              3
/Kontakte/Recipient Cache  8.212 KB              6
/Calendar Logging          7.019 KB              1  

Was will mensch mehr?

Nebenan beschäftigt man sich mit der Laufzeit von Programmen anhand des Spieles Subtract a Square. Da ich aus einem anderen Projekt heraus in eine ähnliche Situation geriet, möchte ich diese Vorlage hier nutzen. Es geht darum, eine effiziente Methode zu finden, eine größere Menge an Werten systematisch nach verschiedenen Kriterien zu durchsuchen.

Aufgabestellung

Beim Spiel geht es darum, abwechselnd von einer vorgegebenen, positiven Zahl eine Quadratzahl abzuziehen, ohne ins Minus zu rutschen. Wer die letzte positive Zahl abziehen kann, hat gewonnen. Das Spiel endet offensichtlich mit dem Wert 0.

Für derartige Nimm-Spiele gibt es eine allgemeine Gewinnstrategie: Man zieht so, dass der Gegner nicht gewinnen kann.

Dazu tabellarisiert man alle Spiele mit kleineren Startzahlen und schaut, ob man dieses kleinere Spiel gewinnen könnte. Kann man das nicht, hat man eine Verliererposition. Mit der Kenntnis aller kleineren Spielausgänge muss man nur den ersten Spielzug betrachten.

Prozedurale Lösung

Zum Verständnis hier eine prozedurale Lösung des Problems:

with Ada.Text_IO;
with Ada.Command_Line;

procedure SubtractSquare is

   function Winners(i : Natural) return Boolean is
      type bitfield is array(0 .. i) of Boolean;
      pragma Pack(bitfield);
      win : bitfield := (0 => False, others => True);
   begin
      for pos in win'Range loop
         for offset in 1 .. pos loop
            declare
               square : Natural := offset*offset;
            begin
               exit when square > pos;
               if win(pos - square) then
                  win(pos) := False;
                  exit;
               end if;
            end;
         end loop;
      end loop;
      return win(i);
   end;

   package Cmd renames Ada.Command_Line;
   package BIO is new Ada.Text_IO.Enumeration_IO(Boolean);

   pos : Positive := Positive'Value(Cmd.Argument(1));
begin
   BIO.Put(Winners(pos));
end SubtractSquare;

Dieses Programm erzeugt ein (kompaktes) Bitfeld und setzt die Werte von kleinen zu großen Positionen. Der letzte Wert ist dann das gewünschte Ergebnis. Die gewünschte Position wird dem ersten Argument der Kommandozeile entnommen.

$ gnatmake -O2 subtractsquare.adb 
ada -c -O2 subtractsquare.adb
gnatbind -x subtractsquare.ali
gnatlink subtractsquare.ali -O2
$ ./subtractsquare 9
FALSE

Soweit so einfach.

Die Laufzeit ist maximal quadratisch (wegen der Doppelschleife), es besteht aber Hoffnung nur knapp über linear zu landen, weil die zweite Schleife vorzeitig abgebrochen wird.

Funktionale Lösung

Die direkte Übernahme dieses Ansatzes in eine funktionale Programmiersprache wie Haskell ist trivial:

import System.Environment

squares = [ i*i | i <- [ 1 .. ] ]

winners :: [Bool]
winners = False : [ and [ not $ winners !! (i-x)
                        | x <- takeWhile (<= i) squares
                        ]
                  | i <- [1 .. ]
                  ]

main = do [c] <- getArgs
          count <- readIO c
          print (winners !! count)

Man baut sich also eine unendliche Liste der möglichen Offsets (Quadrate). Mit der bastelt man die unendliche Liste der Gewinnerwerte zusammen, indem man beim Aufbau auf die Liste selbst zurückgreift. Das funktioniert, weil man nur auf Werte zugreift, die schon berechnet werden konnten.

Von der Liste gibt man das entsprechende Element zurück.

Unglücklicherweise ist das ziemlich langsam, denn die Doppelschleife ist eigentlich eine Dreifachschleife. Die Datenstruktur "[]" ist eine einfach verkettete Liste, die der "!!"-Operator immer von Anfang an durchlaufen muss.

Und genau das Problem habe ich in einem anderen Kontext auch. Also muss da eine Lösung her.

Effizientere Implementierung

Um die ständigen Rücksprünge zu vermeiden, kann man die Tatsache ausnutzen, dass man eigentlich mit mehreren Indizes (um Quadrate versetzt) linear durch die Liste durchläuft.

winners :: [Bool]
winners = False : worker 1 squares []
 where
  worker i so@(s:sn) rs
    | s == i    = worker' i sn (winners:rs)
    | otherwise = worker' i so          rs
  worker' i ss rs = and (map (not . head) rs)
                  : worker (i+1) ss (map tail rs)

Die Implementierung besteht also darin, mitzuzählen und jedes mal, wenn man eine Quadratzahl erreicht hat, einen weiteren Runner über das bisherige Feld aufzunehmen. Das macht die Teilfunktion worker.

Die eigentliche Wertermittlung erfolgt in der Teilfunktion worker', die von allen Runnern das erste Element auswertet und mit den Resten in die nächste Iteration läuft.

Ein direkter Vergleich der Laufzeiten zeigt einen durchschlagenden Erfolg:

subsquare-value-runtime

Seltsame Spitzen

Ungewöhnlich sind die Spitzen der violetten Kurve in diesem Graphen. Wo kommen die her? Fehlmessungen?

Also lass ich weitere Werte berechnen und sehe, dass die Spitzen bleiben. (Den Teil mit dem count ignoriere man mal vorerst.)

subsquare-stream-valuesum

Nun gut, es mag an der Schrittweite liegen, denn ich nehme nur alle 1000 Werte einen Messpunkt. Also mal in Einzelschritten in ein solches Intervall hinein hüpfen:

subsquare-stream-detail

Auch hier zeigt die violette Kurve ein extrem zackiges Bild. Warum?

Weil Haskell faul ist. Lazy evaluation ist eine Eigenschaft von Haskell, nur dann einen Wert auszurechnen, wenn der auch gebraucht wird.

In diesem Fall lautet die Aufgabe, einen bestimmten Wert in einer Liste auszugeben. Dazu geht Haskell die Listenkonstruktion durch und stellt fest, dass in jeder Iteration ein neues Element erzeugt wird. (In worker')

Um den konkreten Wert dann doch zu ermitteln, geht Haskell die Berechnung an und beginnt mit dem letzten hinzugefügten Runner. Der steht aber am Anfang der Liste und mit etwas Glück erwischt er gleich einen Abbruchwert. Damit kann Haskell das Ergebnis ausgeben und ist fertig.

Nur, wenn das Spiel wirklich eine komplexere Situation zu bewerten hat, muss Haskell deutlich mehr berechnen.

Um ihn zu zwingen, alle Werte zu ermitteln lasse ich die Anzahl der Gewinnzahlen bis zu der angefragten Position zu ermitteln.

--          print $ winners !! count
          print . length . filter id . take count $ winners

Eine alternative Formulierung wäre:

          print $ length [ x | x <- take count winners , x ]

Das Ergebnis ist verblüffend. Es ist genau die grüne count-Kurve in den oben stehenden Diagrammen.

Immer, wenn ein neuer Gewinnwert dazu kommt (oder in kleinen Schritten erreichbar wäre), steigt die Rechenzeit deutlich an. Das ist an der überlagerten blauen Stufenkurve zu sehen.

Als Gegentest kann man die Konstruktion "(winners:xs)" in worker durch "(xs ++ [winners])" ersetzen und zuerst den Wert des direkten Vorgängers benutzen. Das stellt ebenfalls sicher, dass alle Werte ermittelt werden. Die Laufzeiten liegen dann in vergleichbaren Größenordnungen wie beim count-Fall.

Warum dauert die Abarbeitung in Einzelfällen aber deutlich länger als im count-Fall? Er hat doch eigentlich weniger zu berechnen?

Die von Haskell zurückgelegten Teilberechnungen sind eine teuere Angelegenheit, sie anzulegen und später auszurechnen kostet deutlich mehr Zeit (und Speicher) als direkt zur Rechnung zu schreiten.

Nochmal!

Mit diesen Erkenntnissen vergleiche ich jetzt nochmal die beiden Algorithmen: Backreferenz per "!!"-Operator und mehrere Stream-Runner. Allerdings berechne ich diesmal die Anzahl der Gewinnzahlen.

subsquare-sum-runtime

Auch hier ist der Vergleich ähnlich: Die Runner gewinnen deutlich.

Evtl. hat ja die count-Berechnung auch das andere Verfahren massiv verlangsamt? Also beide Laufzeiten im direkten Vergleich:

subsquare-backref-valuesum

Die Backreferenz-Methode benötigt auch dann viel Zeit, wenn sie gar nicht alle Werte berechnen muss. Die Berechnung aller Werte dauert aber konstant länger. Beide Laufzeiten sind aber vergleichbar.

Zum Abschluss noch der direkte Vergleich der Methoden in der logarithmischen Darstellung:

subsquare-sum-runtime-log

Die Backreferenz-Methode ist klar polynomial (vermutlich O(n3)) während die Stream-Methode noch exponentiell aussieht (was sie aber nicht ist).

Fazit

Man achte bei der Programmierung stets darauf, ob der Algorithmus zum Programmumgebung passt.

Ist das nicht der Fall, verschlechtern sich die Ergebnisse erheblich. Dann muss entweder der Algorithmus (Streams statt Backreferenzen) oder die Umgebung (Data.Array statt Listen) angepasst werden.

Will man die Vorteile der Programmumgebung (Lazy Evaluation) erhalten, muss man die gewohnten algorithmischen Bahnen verlassen.

Als Belohnung winkt eine überdurchschnittliche Performance.