Einführung in die Cloud: Funktionsweise dynamischer Verkehrsverteilungsmethoden

    In einem unserer früheren Artikel wir sprachen über die statische Lastausgleichsverfahren in der Cloud-IaaS - Anbieter. Heutzutage folgen dynamische Methoden: die Algorithmen „Biene“ und „Ameise“ sowie der Ansatz der voreingenommenen Zufallsstichprobe. / Flickr / Quinn Dombrowski / CC BY-SA Dynamische Ausgleichsmethoden berücksichtigen im Gegensatz zu statischen den aktuellen Zustand des gesamten Systems und reagieren auf Änderungen. Oft werden Informationen über die Last von Knoten in einer Statustabelle gespeichert, aus der Lastausgleichssysteme Informationen beziehen.







    Dynamische Lastverteilung - durchgeführte Überwachung

    Voreingenommene Zufallsstichprobe


    Um diesen Ansatz zu implementieren, das Netzwerk dargestellt als virtuelle gerichteten Graphen , in dem alle Server - es übersteigt. Nach Erhalt einer Anforderung zum Ausführen einer Aufgabe weist der Load Balancer diese dem Scheitelpunkt (Knoten) zu, dessen Annäherungsgrad mindestens einem entspricht.

    Wenn der Knoten die Aufgabe empfängt, beginnt der Prozessor mit seiner Ausführung und signalisiert gleichzeitig eine Verringerung der Anzahl verfügbarer Rechenressourcen, wodurch der halbe Grad der Annäherung verringert wird. Wenn die Aufgabe „gelöst“ ist, erhöht der Knoten diesen Indikator und meldet die Freigabe von Ressourcen.

    Die Auswahl des anfänglichen Scheitelpunkts für die Aufgabe erfolgtzufällig (daher zufällige Stichprobe); Nachfolgende Aufgaben werden benachbarten Knoten zugewiesen, die ebenfalls zufällig ausgewählt werden. Diese Lastausgleichsmethode ist vollständig dezentralisiert und daher für den Einsatz in Cloud-Netzwerken geeignet. Einschließlich geografisch verteilt.

    Wissenschaftler aus Liverpool fanden heraus, dass eine voreingenommene Zufallsstichprobe, die zusätzlich die geografische Verteilung der Knoten im Netzwerk berücksichtigt, die Latenz bei der Datenübertragung um 22% reduzieren kann. In dem Test mit 512 Knoten in einem Umkreis von 1000 km betrug die durchschnittliche Verzögerung ungefähr 70 ms (in einem Experiment mit einem Netzwerk, das die geografische Verteilung der Knoten nicht berücksichtigte, betrug diese Zahl 92,5 ms).

    Optimierungsalgorithmus "Ameise" (Optimierung der Ameisenkolonie)


    Zum ersten Mal wurde dieses Konzept vorgestellt in den frühen neunziger Jahren. Sie lässt sich vom Verhalten der Ameisen inspirieren. Eine Ameise kann immer einen Weg von einer Nahrungsquelle zu einem Ameisenhügel finden, selbst wenn der gewohnheitsmäßige Weg „blockiert“ war. Dafür markieren diese Insekten die Route mit speziellen Pheromonen. Es wird angenommen, dass die Nahrungsquelle umso näher ist, je stärker dieser „Geruch“ ist.

    Im Zusammenhang mit dem Lastausgleich in Telekommunikationsnetzen ist dies wie folgt. Das Netzwerk wird in Form eines Diagramms dargestellt, und aus allen möglichen Knoten wird der Hauptknoten ausgewählt, der die größte Anzahl von Nachbarn aufweist. Schaltstationen werden in den Knoten des Diagramms und Kommunikationslinien zwischen ihnen angezeigt - an den Rändern.

    Jeder Knoten enthält eine „Pheromontabelle“, die Daten zu verwendeten Ressourcen und verfügbaren Kapazitäten enthält: Speichermenge, Anzahl der Prozessoren usw. Von jedem Knoten werden regelmäßig Ameisen gestartet und an zufällige Empfängerknoten gesendet. "Insekten" bewegen sich zwischen Knoten, geführt von einer Pheromontabelle. Diese Tabelle wird jedes Mal aktualisiert, wenn eine Ameise darauf zugreift.

    Ameisen haben ein Alter, das der Länge des zurückgelegten Weges entspricht. Ameisen verweilen auch in Knoten, die mit Anrufen überfüllt sind. Insekten, die einen kürzeren und weniger befahrenen Weg wählen, beeinflussen die Wahrscheinlichkeit, diesen Weg durch nachfolgende Ameisen zu wählen, stärker als Ameisen, die den schlechtesten Weg in Länge und Belastung wählen.

    Dies liegt an der Tatsache, dass die ersten Ameisen früher in den Empfangsknoten gelangen und weniger alt sind. Neue Anforderungen werden auf den kürzesten entladenen Routen gesendet. Auf diese Weise können Sie Ressourcen ausgleichen, indem Sie Knoten in dichten Richtungen im Netzwerk entladen.

    Eine der Variationen dieses Algorithmus verwendet das Framework für P2P-Anthill-Anwendungen. Dieses System ist ein selbstorganisierendes Netzwerk verbundener „Ameisenhaufenkammern“ - Knoten, die Berechnungen durchführen und Daten verarbeiten können.


    Die Struktur des Ameisenhaufen-Netzwerks

    Wenn ein Knoten eine Anforderung von einer Anwendung empfängt, startet er einen eigenständigen Agenten - eine Ameise, die die Aufgabe ausführen muss. Es bewegt sich über das Netzwerk von Knoten zu Knoten, bis die Anforderung abgeschlossen ist. Beim Umzug "tragen" die Ameisen Informationen über die Anfrage, das Ergebnis und andere Metadaten mit sich.

    Ameisen kommunizieren nicht direkt miteinander, sondern überlassen die zur Lösung des Problems erforderlichen Informationen den Ressourcenmanagern in den von ihnen besuchten Knoten. Beispielsweise kann eine Ameise, die einen Suchdienst implementiert, Routing-Informationen auf diese Weise hinterlassen, was anderen Ameisen helfen würde, den Weg zu Knoten zu ebnen, die die benötigten Daten enthalten. Eine ähnliche Form der indirekten Kommunikation wird auch von echten Ameisen verwendet - dies nennt man Stigmergie..

    Optimierungsalgorithmus "Bee" (Honigbienenfutter)


    Der erste Artikel, die ein Verfahren zur Bienen beschreibt, wurde veröffentlicht im Jahr 2005. Es basiert auf der Modellierung des Verhaltens von Bienen bei der Suche nach Nektar. In den Bienenstöcken gibt es sogenannte Pfadfinderbienen, die nach Lichtungen mit Blumen suchen . Wenn sie eine Nahrungsquelle finden, kehren sie in den Bienenstock zurück, um anderen mit Hilfe eines speziellen „wedelnden Tanzes“ davon zu erzählen.


    / Flickr / Unregelmäßiger Blog - Daedalus / CC BY-SA

    Bei diesem Tanz berichtet die Biene, wie gut der Nektar auf der Lichtung ist und wie weit er entfernt ist. Danach reagieren Häckslerbienen auf ihren Ruf, die dem Späher nachfliegen, die „Ernte“ sammeln und mit der „Beute“ zum Bienenstock zurückkehren. Dann kann die Futtersuchbiene eine der folgenden Aktionen ausführen: Sie wird eine unbesetzte Futtersucherin, verlässt die aktuelle Nektarquelle, sammelt sie weiterhin selbst oder ruft zusammen mit mehreren anderen unbesetzten Bienen an, um zu helfen.

    Dieses Modell wird verwendet, um die Last wie folgt auszugleichen. Zunächst wird die aktuelle Belastung virtueller Maschinen berechnet und deren Zustand (ausgeglichen, entladen, überlastet) in Abhängigkeit von den von ihnen festgelegten Schwellenwerten ermittelt. Wenn die Last auf der VM gering ist, werden alle neuen Aufgaben an sie geleitet.

    Wenn das System virtuelle Maschinen überlastet ist, jeder von ihnen nimmt die Rolle eines Scout oder forager. Bei der Bearbeitung der Anfrage berechnet der virtuelle Server einen bestimmten Wert, der analog zur "Qualität" der Wiese mit Blumen ist, die einen Bienentanz zeigt. Eine der Optionen zum Auswerten dieses Werts kann die Zeit sein, die die CPU benötigt, um ihn abzuschließen. Dann „kündigt“ der Server diese Aufgabe dem gesamten System an, als würde er sie auf einer Pinnwand veröffentlichen - auf diese Weise übernimmt der Server die Rolle des Scouts. Andere Server können dieses Bulletin Board anzeigen und die dort gestellten Anfragen verarbeiten und werden zu Häckslern.

    Weitere Inhalte aus dem Unternehmensblog von 1cloud:


    Jetzt auch beliebt: