Der Schwänzeltanz der Internet-Server
An einer Konferenz über mathematische Modelle sozialer Insekten wurde eine Arbeit präsentiert, die das Verhalten der Bienen beim Nektarsammeln zur Berechnung der optimalen Lastverteilung bei Internet-Servern heranzieht. Wie sich in den Simulationen der Wissenschafter zeigte, lassen sich vom Verhalten der Bienen Verfahren ableiten, die gängigen Algorithmen um bis zu 50 Prozent überlegen sind.
gsz. Dass Bienen gute Bauingenieure sind, ahnte schon der Römer Marcus Terentius Varro, als er ihre hexagonalen Waben untersuchte und vermutete, dass diese in Bezug auf die Lagerung von Honig und den Verbrauch von Wachs die effizienteste Struktur darstellen. Seit kurzem ist bekannt, dass Bienen auch gute Computeringenieure sein können. Die beiden Wissenschafter Sunil Nakrani von der Universität Oxford und Craig Tovey vom Georgia Institute of Technology haben an einer Konferenz über mathematische Modelle sozialer Insekten eine Arbeit präsentiert, in der sie das Verhalten der Bienen beim Nektarsammeln zur Berechnung der optimalen Lastverteilung bei Internet-Servern heranziehen.
In den 1930er Jahren hatte der Zoologe und Nobelpreisträger Karl von Frisch herausgefunden, dass Bienen nach ihrer Rückkehr in den Stock ihren Kolleginnen mit einer Art Schwänzeltanz Bericht über die Entfernung und die Qualität der Blumenbeete geben. Unbeschäftigte Bienen beobachten einen der Schwänzeltänze und schwärmen dann aus. Sie kommunizieren unterwegs nicht, und keine weiss, wie viele von ihnen welche Beete ernten. Trotzdem optimiert das Bienenvolk den Nektarertrag, indem kümmerliche Blumenbeete von bloss wenigen, reichliche und naheliegende Beete von zahlreichen Bienen angeflogen werden. Es kommt nämlich die sogenannte Schwarmintelligenz zum Zuge: Obwohl jedes Individuum bloss einige einfache Regeln befolgt, entfaltet der Schwarm gesamthaft gesehen ein nahezu optimales Verhalten.
Nachfrageschwankungen
Sunil Nakrani und Craig Tovey untersuchten das Problem, das der Betreiber eines Internet-Server-Parks lösen muss. Dieser bietet mehrere Internetdienste an und stellt dafür eine Anzahl von Servern bereit. Entsprechend der geschätzten Nachfrage teilt der Provider jedem Dienst - Auktionen, Börsengeschäfte, Flugreservationen - eine gewisse Anzahl von Servern zu (Cluster).
Die eintreffenden Anfragen werden auf Warteschlangen für die verschiedenen Dienste verteilt. Für jeden erfüllten Auftrag erhält der Betreiber eine Zahlung. Das Aufkommen von Anfragen verändert sich andauernd, und unterbeschäftigte Server können überlasteten Clustern zugeteilt werden. Allerdings ist das mit Kosten verbunden, denn der umgeteilte Server muss für die neue Aufgabe rekonfiguriert und mit neuer Software beladen werden. Während dieser Zeit - im Allgemeinen etwa fünf Minuten - können eingehende Anfragen und Aufträge nicht bedient werden. Wird die Wartezeit zu lange, wenden sich die Kunden ab, und potenzieller Gewinn geht verloren.
Das Problem des Betreibers besteht darin, die Server derart auf die Cluster zu verteilen - und die Verteilung den sich dauernd verändernden Gegebenheiten dynamisch anzupassen -, dass eine möglichst grosse Zahl von Aufträgen bedient und der Profit maximiert wird.
Bienen bedienen Server
Traditionell werden zur Berechnung der Profitabilität von Server-Zuteilungen drei Algorithmen benützt: der «allwissende» Algorithmus, der nach jedem Zeitintervall feststellt, welche Zuteilung optimal gewesen wäre, der «Greedy»-Algorithmus, der auf der Daumenregel beruht, dass das unmittelbar vorhergehende Auftragsaufkommen auch für das nächste Zeitintervall massgebend ist, und der «optimal-statische» Algorithmus, der im Nachhinein die beste, während des gesamten Beobachtungszeitraums unveränderliche Server-Verteilung berechnet. Nakrani und Tovey verglichen diese drei Algorithmen mit dem Verhalten der Bienen. In ihrem Modell entsprechen Warteschlangen den Blumenbeeten, Server den Bienen und Server-Cluster der Bienengruppe, die ein gewisses Beet anfliegt. Der Schwänzeltanz wird in ihrem Modell durch ein Anschlagbrett dargestellt. Nach Erfüllung ihrer Aufträge geben Server mit einer gewissen Wahrscheinlichkeit die Eigenschaften der bedienten Warteschlange auf dem Anschlagbrett bekannt. Andere Server lesen mit einer Wahrscheinlichkeit - die umso grösser ist, je unprofitabler die zurzeit bediente Warteschlange ist - eine der Bekanntgaben auf dem Anschlagbrett und ändern daraufhin möglicherweise ihre Cluster. Die Kosten eines Cluster-Wechsels sind vergleichbar mit dem Zeitaufwand einer Biene für das Betrachten eines Schwänzeltanzes und dem Wechsel von einem Beet zu einem anderen.
Wie sich in den Simulationen der Wissenschafter herausstellte, ist das Verhalten der Bienen bei der Nektarsuche bei zwei der drei Algorithmen an Profitabilität zwischen einem und 50 Prozent überlegen. Bloss der allwissende Algorithmus ergäbe noch grössere Profite. Aber dieser Algorithmus, der die absolut oberste Grenze der Profitabilität angibt, ist ohnehin wegen der unrealistischen Annahme, dass das künftige Kundenverhalten bekannt ist), und wegen der enormen Computerressourcen, die zur Berechnung der optimalen Zuteilung nötig wären, nicht praktikabel.
Nur annähernd optimal
Dass hexagonale Waben die effizienteste Unterteilung der Ebene sind, konnte der amerikanische Mathematiker Tom Hales erst 1999 beweisen. Doch auch Bienen sind - trotz ihrer erstaunlichen Fähigkeit, sich dem Optimum anzunähern - nicht perfekt. Die vielgelobten Waben sind, wenn sie in drei Dimensionen betrachtet werden, nur annähernd optimal: Der ungarische Mathematiker Laszlo Fejes-Tóth hatte 1964 gezeigt, dass es eine Wabe gibt, die 0,3 Prozent weniger Wachs benötigt als die von den Bienen gebauten.
