KE 3

• Protokolle als Kommunikationsregeln

• Kommunikation durch Nachrichtenübermittlung

  • wenn nicht VS wäre auch z.B. geteilter Speicher möglich

  • Ablauf:

    • P will mit Q kommunizieren

    • P baut Nachricht in eigenem Adressraum

    • P führt Systemaufruf aus

    • OS sendet Nachricht über Netzwerk zu Q

• connection-oriented service

  • Sender und Empfänger stellen Verbindung her vor Datenaustausch

  • ggf. verhandeln Parameter des Protokolls

  • richtige Reihenfolge auch gewährleistet

  • nach Austausch Verbindung trennen

  • Vergleich: Telefon

• connectionless service

  • keine Verbindung nötig

  • einfach nur Nachricht schicken

  • richtige Reihenfolge der Nachrichten nicht gewährleistet

  • Vergleich: Brief in Briefkasten werfen

• jede Schicht fügt header hinzu und gibt Nachricht weiter

  • ggf. auch Trailer

• beginnt bei Application layer

• beim Auspacken werden die header wieder von der entsprechenden Schicht entfernt

• Information in layer-n header ist für layer-n Schicht

= Sammlung Protokolle, die in bestimmten System verwendet wird

• logisch im OSI application layer

• aber viele general-purpose Protokolle

• Beispiele

  • DNS (Domain Name System)

    • sucht Adresse für domain name

    • ist Anwendung

  • Authentication protocols

  • commit protocols

    • zum herstellen von atomicity

      • .= entwender alle Transaktionen werden hergestellt oder keine

  • distributed locking protocol

    • schützt vor gleichzeitigem Zugriff auf eine Ressource

• Anwendungsprotokolle

• Middlewareprotokolle

• Transportprotokolle (TCP, UDP)

• Protokolle der unteren Schichten

1. persistent

• Middleware speichert Nachricht so lange wie nötig für Lieferung

• Sender-Prozess braucht nur losschicken

• Empfänger-Prozess braucht nicht laufen beim Abschicken

• bsp. Email wird auf dem Server gespeichert und wartet auf den Abruf

  
  

1. transient

• Nachricht nur solange gespeichert wie Sender- und Empfängerprozesse laufen

• middleware lässt Nachricht verfallen, die nicht geliefert werden kann

  • z.B. weil Empfänger nichts annimmt

  • oder Verbindung unterbrochen wurde

• Transport-level services nur transient

  • store-and-forward router

1. asynchron

• Sender kann nach Senden gleich weiterarbeiten

• Middleware speichert (temporär) Nachricht nach Übergabe

1. synchron

• Sender blockiert, bis Akzeptieren der Anfrage bekannt gegeben wird

1. Blockiert bis Middleware sagt, dass es Senden übernimmt

2. Blockiert bis Nachricht an Sender übermittelt

3. Blockiert, bis Anfrage vollständig verarbeitet wurde (also bis zur Antwort des Empfängers)

zum Auflösen von Domainnamen in IP-Adresse

• Mensch gut mit symbolischen Namen

• Computer: Zugriff über IP-Adresse - auf Transportschicht nichts anderes möglich

  • Socket braucht Zahlen

• Transparenz: man muss nur Namen des Hosts kennen

  • interne Adresse egal

• Skalierbarkeit:

  • Name kann mehrere Adressen haben

  • Adresse kann mehrere Namen haben

1. Root Name-Server

   • fuer IP-Adressen von Top-Level NS

2. Top-Level Name Server

   • fuer IP-Adressen von Autoritativen NS

3. Autoritativer Name Server

   • fuer Anfrage

   • jeder Server ist bei einem autoriv. NS registiert

4. Lokaler Name-Server

   • Auflösungsanfrage geht immer erst hier her

   • oft hat er schon Antwort

1. Remote Procedure Call

2. Remote Invocation Method

3. Authentifikatinsprotokolle

4. Verteilte Commit-Protokolle

5. Verteilte Locking-Protokolle

= Remote Procedure call

• Prozess kann lokal eine Prozedur aufrufen, die auf remote machine implementiert ist

• realisiert Zugriffstransparenz

• prozedurales Programmierparadigma

vorher:

• man musste send und receive verwenden

• -> keine Zugriffstransparenz

transient und synchron

• Client blockiert bis er Antwort erhält

1. client ruft client stub auf

   • aufrufender Prozess bei A blockiert

1. Marshaling - stub packt parameter in eine Nachricht und ruft lokales OS auf

2. client OS sendet Nachricht an remote OS

3. remote OS gibt Nachricht an server stub

4. Unmarshaling - server stub packt Paramter aus und ruft server auf

5. server arbeitet und gibt Ergebnis an stub

6. Marshaling server stub verpackt Ergebnis in Nachricht und gibt sie an lokales OS

7. server OS sendet Nachricht to client OS

8. client OS gibt Nachricht zu client stub

9. Unmarhaling stub packt Ergebnis aus und gibt es dem client

   
   

-> Programmer sieht keine Nachrichtenübergabe

• Prozedur auch nicht

• calling and called procedures laufen auf verschiedenen Maschinen mit unterschiedlichen Adressräumen

• parameter marshaling

  = Parameter in Nachricht packen

  • unmarshaling = wieder auspacken

1. Problem: server sieht nur Bytes der Nachricht - muss vestehen, was die bedeuten

• keine zusätzliche Information gegeben

  • und bei der wüsste man auch nicht, wie man die erkennen soll

• maschinen nutzen little endian oder big endian

  • big endian ist aber meist genutzt

• Lösung 1:

  •  Daten zu einem Netzwerk-unabhängigen Format übertragen

    • durch maschinen-abhängige Routinen

  • client und server sollten dann das Format erwarten

    • durch Programmier-Sprachen

• call by value vs. call by reference ist wichtig

  • weil es entscheidet, welche Variablen geändert werden

    • bei call by value wird das ursprüngliche Objekt nicht geändert

1. Problem: Umgang mit Referenzen

• Lösung 2:

  • a) Pointer/ Referenzen verbieten

  • b) gesamte Datenstruktur kopieren

    • wenn es nur gelesen wird, braucht man nichts zurück kopieren

  • c) globale Referenzen verwenden

    • die für client und server gleichermaßen gelten

    • z.B. wenn client und server Zugriff aufs gleiche Dateisystem haben

      • dann nur Datei-handle übergeben

    • verteilte Objekte

      • muss man lokale und verteilte Objekte unterscheiden

      • keine Verteilungstransparenz mehr

      • schwieriger, verteilte Applikationen zu schreiben

    • neues Problem: bei Booelan, Integer

      • auch da muss immer RPC gemacht werden

1. Problem: komplizierte (benutzerdefinierte) Datentypen als Parameter

• Lösung 3:

  • auspacken vielleicht nicht nötig oder erwünscht

synchrone Kommunikation mit objektorientieren Programmierparadigma

Komponenten:

1. Proxy-Objekt

   • Stellvertreter für eigentliches Serverobjekt

2. Client-Stub

   • bietet Funktionalität für Marshaling, Unmarshaling und Verbindungsaufbau

3. Server-Stub

   • nimmt Aufruf an und gibt ihn an Serverobjekt

   • Ergebnis wird auf umgekehrten Weg zurückgegeben

   • Client blockiert bis zum Empfang des Ergebnisses

• für high-speed interconnection networks

  • z.B. in high-performance server clustern

• hardware und plattform-unabhängig

• für parallele Anwendungen

• transient und asynchron

• serious failures are fatal

  • z.B. Prozess-abstürze

  • keine automatische Recovery

• Kommukation in Gruppen

  • jede Gruppe ein Identifier

  • jeder Prozesse eine ID

  • -> (groupID, processId) verwendet anstelle von transport-level Adresse

• extrem viele Operationen (440 in v3)

• message oriented middleware (MOM)

• für persistente asynchrone Kommunikation

• für Nachrichtenübermittlung, die Minuten dauern kann

  • bei Socket eher (Milli-)Sekunden

• Nachrichten können alle möglichen Daten enthalten

• Nachrichten brauchen logische Namen (unabhängig von Standort und Entstehung), der auf Kontaktadresse abgebildet werden kann

Grundidee:

• Kommunikation durch Warteschlangen für Nachrichten

• Nachrichten über Kommunikationsserver weitergeben

• irgendwann zum Ziel geben

sehr einfaches Interface

jede Anwendung hat eigene, private Queue

• mehrere Applikationen können auch Q teilen

Man braucht Message Broker

• Nachricht kann beim Sender anderes Format haben als beim Empfänger

• Message Broker behebt das

• queue manager organisiert Warteschlange für Nachrichten

• Anwendung kann Nachrichten nur in lokale Q tun und auch nur aus lokaler Q holen

• QM sorgt, dafür dass Nachricht an Ziel kommt

  • Info über Ziel hängt an Nachricht

Besonderheiten:

• Nachrichten haben logische, orts-unabhängige Namen

• jeder Name sollte Kontaktadresse haben

• jeder QM kennt Adresse anderer QM kennen

• mit lookup-Tabelle

• kann zu Overlay-Network werden

message broker

• nodes die Nachrichten konvertieren

• erscheint als nur eine weitere Applikation

= Nachrichten zu verschiedenen Empfängern senden

• für one-to-many-Kommunikation

• vs. unicast

mit Netzwerk-Protokollen

• z.B. Kommunikationspfade einrichten

• braucht viel Management, manchmal menschlichen Eingriff

neuer (und hier): auf der Anwendungsschicht in peer-to-peer Netzwerken

• brauchen keine expliziten Kommunikationspfade

• Nodes müssen in overlay-Netzwerk organisiert sein

• keine Netzwerk-Router in den Gruppen

  • -> Routing nicht optimal

nur fuer spezifische Untergruppe

• -> nicht alle Knoten brauchen Nachricht erhalten und weiterleiten

• am besten ein Overlay-Netzwerk pro Untergruppe

• Nachteil: Knoten müssen verschiedene Listen verwalten, wenn sie zu verschiedenen Gruppen gehören

3 Arten:

• baumartig

• flutartig

• gossip-based

• einzigartiger Overlay-Path zwischen jedem Knoten-Paar

  • vs. mesh Netzwerk

    • Knoten haben mehrere Nachbarn

    • robuster als Baum

    • gibt auch mehrere Pfade

• Beschreibung des Aufbaus in Note 4.13 (in Chord)

  • man sucht einen Knoten als Wurzel des Baums

    • mit succ(mid)

      • mid = multicast identifier

  • wer mitmachen will ruft succ(mid) auf

  • kommt er an einen Knoten, der schon drin ist, wird Knoten dessen Kind im Baum

  • alle im Baum sind forwarder der Multicast-Gruppe

• nicht unbedingt effizient

  • Teilstrecken werden mehrmals durchquert, was nicht nötig wäre

• Bsp. Switch-trees

  • Nodes können Parents wechseln

    • neuer Parent darf nur nicht in eigenem Teilbaum sein

  • Wechseln aufgrund von regelmäßigen Informationen über (Verzögerungen zu) anderen Nodes

  • fällt eine Node aus, dann verbindet sich dessen Kind(er) zur Wurzel

1. link stress

   • je link gemessen

     = wie oft ein Paket den Link passiert auf seinem Weg von Ziel zu Knoten

   • > 1 , wenn für Paket logisch verschiedene Verbindung physisch die gleiche ist

1. strech

• "relative delay penalty (RDP)

  = zwischen 2 Knoten: Verzögerung im overlay / Verzögerung im physischen Netzwerk

• Bsp. die Nodes (inkl. Router) zählen im overlay / Anzahl Nodes im physisch. Netzwerk

1. tree cost

• globale Messung

• aggregierte link-Kosten minimieren

  • link-Kosten z.B. Verzögerungen zwischen den beiden Endknoten

  • dann minimalen Spannbaum finden, der Zeit für Informationsverteilung zu allen Knoten minimiert

= alle Knoten bekommen die Nachricht

• vs. spezifische (Unter-)Gruppe

• jeder Knoten leitet Nachricht zu jedem Nachbarn weiter

  • außer zu dem, von dem Nachricht kam

• Duplikate ignorieren

• ineffizient -> doppelt so viele Nachrichten wie Links werden gesendet

  • optimal nur, wenn G ein Baum ist

2 Arten:

• probabilistic flooding

  • um Anzahl Nachrichten zu reduzieren

  • Nachricht nur mit Wahrscheinlichkeit zu einem Nachbarn weiterleiten

  • verringert die Anzahl Nachrichten linear

  • Risiko: nicht alle Knoten werden erreicht

    • hat Q n Nachbarn

    • ist Wahrscheinlichkeit, keine Nachricht zu bekommen

    • (1 - p_flood)^n

    • -> Anzahl Nachbarn wichtig für Wahrscheinlichkeit

• Schema von Schlosser

  • für deterministische Topologie

    • z.B. n-dimensionaler Hypercube

  • Anzahl Nachbarn je Dimension beachten

  • Kanten werden mit der Zahl bezeichnet, welche Bits man ändern muss um von einem Nachbarn zum anderen zu kommen

    • Bild 4_37_hypercube

  • anfänglich: Nachrichten zu allen Nachbarn schicken und mit der Zahl der Kante verbinden

  • Knoten leiten Nachrichten nur über Kanten mit höherer Zahl weiter

  • -> wird optimal, weil nur 2^n - 1 Nachrichten gesendet werden müssen

    • .= ANzahl der Knoten in einem n-dimensionalen Hypercube

• in Choord

  • Nachbarn in Segmente einteilen, für die sie verantwortlich sind

  • die teilen ihre Segmente wieder in Segmente

• verwendet epidemisches Verhalten

  = gossiping

epidemic protocols

• Informationen sehr schnell verbreiten

• nur lokale Informationen verwenden

-> keine zentrale Komponente, um Informationsverbreitung zu koordinieren

rumor spreading

• eine Art von epidemischem Protokoll

• wurde Knoten P aktualisiert mit Daten-Item x

• dann kontaktiert es willkürlich anderen Knoten Q

• wurde Q schon updated, dann verliert P Interesse, weiter zu verbreiten mit Wahrscheinlichkeit p_stop

wird also "removed"

-> keine Garantie, dass alle Knoten erreicht werden

Vorteil von epidemischen Algorithmen:

• Skalierbarkeit

Nachteil:

• machen unrealistische Annahme, dass alle Knoten gleich erreichbar sind

• Daten löschen viel schwieriger

Trick: Löschen der Daten speichern

= death certificates

• neues Problem:

  • jede Menge Infos über historische Daten

  • Lösung: dormant death certificates

    • nach bestimmter Zeit entfernen

einige Knoten behalten death certificates

erhalten sie Updates zu den Daten

schicken sie das Löschen noch mal rum

directional gossiping

Netzwerk-Struktur beachten vorteihaft

z.B. Knoten mit wenigen Nachbarn gezielt mit hoher Wahrscheinlichkeit kontaktieren