Self-Organized Networks - Cheatsheet

Definition und Merkmale von Selbstorganisation

Definition:

Dezentrale Methode der Netzwerkbildung ohne zentrale Steuerung, Eigenanpassung an sich ändernde Bedingungen.

Details:

• Verteilte Kontrolle
• Flexibilität und Robustheit
• Emergente Eigenschaften
• Autonome Einheitenausführung
• Zufällige und deterministische Prozesse

Vergleich zwischen zentralisierter und dezentralisierter Steuerung

Definition:

Vergleich zentralisierter und dezentralisierter Steuerung in selbst-organisierenden Netzwerken.

Details:

• Zentralisierte Steuerung: Eine zentrale Einheit trifft alle Entscheidungen und steuert das Netzwerk.
• Dezentralisierte Steuerung: Entscheidungen werden lokal an mehreren Knoten im Netzwerk getroffen.
• Vorteile zentralisiert: Weniger Redundanz, einfachere Implementierung, konsistente Entscheidungsfindung.
• Nachteile zentralisiert: Single-Point-of-Failure, schlechtere Skalierbarkeit, höherer Aufwand bei Fehlfunktionen.
• Vorteile dezentralisiert: Erhöhte Fehlertoleranz, bessere Skalierbarkeit, flexiblere Anpassung an lokale Bedingungen.
• Nachteile dezentralisiert: Komplexere Implementierung, mögliche Inkonsistenzen, erhöhte Kommunikationskosten unter Knoten.

Schwarmintelligenz und Agenten-basierte Modellierung

Definition:

Schwarmintelligenz: kollektives Verhalten dezentralisierter, selbstorganisierter Systeme. Agenten-basierte Modellierung: Simulation individueller Agenten und ihrer Interaktionen.

Details:

• Schwarmintelligenz: Ameisenkolonien, Vogelschwärme, Fischschwärme als Beispiele
• Agenten-basierte Modellierung: Nutzung in der Informatik zur Simulation komplexer Systeme
• Mathematische Modellierung: Differentialgleichungen und Wahrscheinlichkeitsmodelle
• Formel zur Wechselwirkung: \( f_i = \frac{{k}}{{r^2_{ij}}} (r_{ij} - r_{ij}^{min}) \)
• Parameter: Anzahl der Agenten, Interaktionsregeln, Umgebung

Routing-Protokolle wie OSPF und BGP

Definition:

Routing-Protokolle bestimmen den Weg von Datenpaketen durch ein Netzwerk.

Details:

• OSPF (Open Shortest Path First): Link-State-Routing-Protokoll, nutzt Dijkstra-Algorithmus, dynamische Updates, schneller Konvergenz, für interne Netzwerke.
• BGP (Border Gateway Protocol): Distance-Vector-Routing-Protokoll, nutzt Pfadlängenkriterium, für Routing zwischen autonomen Systemen (AS), nicht so schnelle Konvergenz wie OSPF, skaliert gut für sehr große Netzwerke.

Peer-to-Peer-Netzwerke und DHTs

Definition:

Technologien, die Peer-to-Peer (P2P) Netzwerke und verteilte Hashtabellen (DHTs) ermöglichen effizientes, dezentralisiertes Ressourcensharing ohne zentrale Server.

Details:

• P2P-Netzwerke: Gleichgestellte Knoten kommunizieren direkt.
• DHT: Verteiltes Speichersystem für Zuordnung Schlüssel zu Werten.
• P2P-Beispiel: BitTorrent, Skype.
• DHT-Beispiel: Kademlia, Chord.
• Routing: Algorithmus leitet Daten effizient.
• Vorteile: Skalierbarkeit, Fehlertoleranz, Redundanz.
• Herausforderungen: Sicherheit, Konsistenz, Netzwerkpartitionierung.
• Wichtige Eigenschaften: Load Balancing, geringe Latenz, hoher Durchsatz.
• Formeln:
  • Zeitkomplexität Suchen in DHT: \text{O}(\text{log}(N))
  • Knotenanzahl: \text{N}

Verteilte Algorithmen und Konsensprotokolle

Definition:

Verteilte Algorithmen koordinieren die Arbeitsweise mehrerer Prozesse zur Lösung eines Problems in verteilten Systemen. Konsensprotokolle dienen dazu, einen einheitlichen Zustand oder eine Entscheidung unter den beteiligten Knoten zu erreichen.

Details:

• Verteilte Algorithmen sind essenziell für die Robustheit und Skalierbarkeit in Netzwerken.
• Konsensprotokolle sorgen für Konsistenz trotz möglicher Fehler und Ausfälle.
• Bekannte Konsensprotokolle: Paxos, RAFT.
• Paxos: Hohe Fehlertoleranz und schwierig zu implementieren.
• RAFT: Einfacher zu verstehen und zu implementieren als Paxos.
• Formale Anforderungen: Sicherheit (Safety) und Lebendigkeit (Liveness).
• Safety: Kein Konsensbeschluss ist falsch.
• Liveness: Jede Anfrage wird irgendwann beantwortet.
• Wichtige Konzepte: Leader (Koordinator), Follower (Teilnehmer), Wahlverfahren bei RAFT.
• Quorum: Mindestanzahl von Knoten, die einer Entscheidung zustimmen müssen.

Selbstorganisierende Roboterschwärme

Definition:

Definiert eine Gruppe von Robotern, die ohne zentrale Kontrolle durch lokale Interaktionen Aufgaben bewältigen.

Details:

• Nutzen Prinzipien der Schwarmintelligenz.
• Interaktionen basieren oft auf einfachen Regeln.
• Typische Algorithmen: Boids, Particle Swarm Optimization (PSO).
• Mathematische Modellierung: Differentialgleichungen, Graphentheorie.
• Anwendungen: Such- und Rettungsmissionen, Landwirtschaft, Überwachung.

Stochastische Prozesse und Wahrscheinlichkeitsverteilungen

Definition:

Mathematische Modelle zur Beschreibung von zufälligen Vorgängen und deren Verteilungen. Kernkonzepte beinhalten die Zeitabhängigkeit und die statistischen Eigenschaften von Systemen mit Zufallseinflüssen.

Details:

• Stochastische Prozesse: Folge von Zufallsvariablen, z.B., Wiener-Prozess (Brownsche Bewegung).
• Wahrscheinlichkeitsverteilungen: Beschreiben die Verteilung von Zufallsvariablen, z.B. Normal-, Exponential-, Poisson-Verteilung.
• Parameter: Verteilung wird durch Parameter charakterisiert (z.B. Mittelwert \(\mu\) und Varianz \(\sigma^2\) der Normalverteilung).
• Erwartungswert \(\mathbb{E}[X]\): Durchschnittswert einer Zufallsvariablen.
• Varianz \(\text{Var}(X)\): Maß für die Streuung der Verteilung.
• Gesetz der großen Zahlen: Mittelwert von Stichproben konvergiert gegen den Erwartungswert bei großer Stichprobengröße.
• Zentrales Grenzwerttheorem: Summe vieler unabhängiger Zufallsvariablen nähert sich einer Normalverteilung, unabhängig von der Ausgangsverteilung.