Telematik 1: Unterschied zwischen den Versionen
Zeile 693: | Zeile 693: | ||
*Welche Dienste muss das Netzwrk bieten? | *Welche Dienste muss das Netzwrk bieten? | ||
*Wie siehts in einem Router aus | *Wie siehts in einem Router aus | ||
− | *Herr Jäger müffelt immer noch | + | *Herr Jäger müffelt immer noch [Anm. von Herrn J.: "Deine Oma....."] |
*Ipv4, IPv6 | *Ipv4, IPv6 | ||
*Routing in großen Netzwerken ist allein mit guten Routingalgorithmen nicht zu machen, wir brauchen dazu noch hierarchisches Routing | *Routing in großen Netzwerken ist allein mit guten Routingalgorithmen nicht zu machen, wir brauchen dazu noch hierarchisches Routing |
Version vom 2. Juli 2006, 13:49 Uhr
Zusammenfassung
Vorgeplänkel
Daten, Informationen, Signale
- Daten repräsentieren Fakten, Ideen, Modelle etc. in einer für Menschen und Maschinen verständlichen Form, z.B. Zeichen, Schrift oder Sprache.
- Information ist das, was ein Mensch aus Daten gewinnen kann, indem er unter Kenntnis der Regeln des Entstehens der Daten den Sinn und Zweck der Daten interpretiert. Eine Maschine kann das nicht, daher spricht man bei der Datenübertragung auch nie von Informationsübertragung.
- Signale repräsentieren das Modell "Daten" in der realen Welt durch zeitliche oder räumliche Veränderung physikalischer Größen wie Spannung, Strom, Wellenlänge etc.
Signalausbreitung auf einer Leitung
- Ein Bit benötigt eine Ausbreitungsverzögerung dprop, um von Host A zu Host B zu gelangen. Dies hängt von der Geschwindigkeit des Signals auf der Leitung (z.B. v = 2/3 c) und der Länge der Leitung ab („wie schnell ist das Medium“).
- Die Datenrate R gibt an, wie schnell der Sender die Bits auf die Leitung geben kann.
- Die Übertragungszeit dtrans gibt an, wie viele Bits der Sender bezogen auf die Datenrate auf die Leitung geben kann.
Simplex/Duplex
- Simplex: Nur einer sendet (Bsp. Radio).
- Half Duplex: Beide senden abwechselnd aber nie gleichzeitig (also muss der eine warten bis der andere pferdsch is) – Problem, wenn man nur ein Kabel verwenden will: Wann weiß der eine wann der andere pferdsch is? Lösung: zB Methode TDD (time division duplex) – jeder kriegt ne gewisse Sendezeit und sendet dann – muss natürlich zu sendende Daten puffern, wenn er grad nich senden darf.
- Full Duplex – jeder kann senden, zu jeder Zeit. Um Interferenzen bei Verwendung eines Kabels zu vermeiden, kann zB mit verschiedenen Frequenzen gesendet werden.
Netzwerkelemente
- Switch: Kann eine direkte physikalische Verbindung zwischen den Kommunikationspartnern herstellen (also wirklich ne Leitung schalten, wie das Fräulein vom Amt), verschwendet dann aber Ressourcen bei Pausen.
- Alternative: Möglichkeit des Packet Switching, also Daten in Pakete gliedern und diese halt vom Switch zu ihren Empfängern verteilen zu lassen – wie die Post (store and forward). Vorteil: Leitung wird nur dann genutzt, wenn sie auch gebraucht wird, aber unheimlicher Verwaltungsaufwand – wo beginnt ein Paket, wo hörts auf, an wen geht es, etc etc etc.
Multiplexing
- Daten von den Sendern gehen zum Switch (Multiplexer). Der sendet das zeug zusammen über ein einziges Kabel zu einem anderen Switch (Demultiplexer), der die Daten auf die Empfänger verteilt. So hat jedes Kommunikationspaar den Eindruck, die Leitung gehöre ihm allein und es kann einen kontinuierlichen Fluss an Daten senden. Vom viel komplizierteren System darunter, das die Daten verteilen muss, sieht es nichts.
- Wie werden die Pakete auf der Leitung auseinander gehalten vom Demultiplexer? Sender kann verschiedene Möglichkeiten des Sendens nutzen: TDM (Zeit), FDM (Frequenz), CDM (Code) etc.
- Was ist wenn Multiplexer nicht verfügbar? Dann hat man keinen, der den Datenfluss organisiert und verteilt, folglich muss das von den Teilnehmern selbst geregelt werden, die müssen sich auf dem gemeinsam genutzten Medium verständigen und sich nicht gegenseitig die Bandbreite klauen wie Thunderchild den AMW-lern in der Mensa– Medium Access nennt sich das dann (Bsp Klassenraum – Regel: Wenn der Kuchen spricht, haben die Krümel Sendepause)
Walk the LAN
- Wie werden die Pakte im Netzwerk verteilt? Woher weiß der Router wohin er die Pakte senden muss? Was ist der beste Weg von A nach B?
- Flooding: einfach alles an alle senden, das ist - Achtung Sarkasmus – sehr bandbreiteneffizient
- Hot Potato Routing – einfach zufällig irgendwem die heiße Kartoffel zuwerfen, der wirftse dann gleich weiter
- um das ein bissel intelligenter zu gestalten (kurze Wege, Schleifenfreiheit), muss der Router ständig etwas über die Struktur des Netzwerks lernen – er legt sich Routingtabellen an, indem er erstmal die Pakete beobachtet oder Infos mit anderen Routern tauscht
- Um die Tabellen nicht riesig groß werden zu lassen: divide and conquer
Fehler
- Fehlerquellen: Konvertierung von Signalen zu Bits, Shared Medium Access, Packetverluste, Fehlleitung von Paketen, Speicher des Routers voll, Sebbl im Netzwerk, ....
- benötigen Fehlerkontrolle, Flusskontrolle (Empfänger darf nich zuviel auf einmal empfangen) Staukontrolle (nicht zuviele Pakete ins Netzwerk reingeben)
Dienste, Protokolle, Schichten
Welche Dienste muss das Kommunikationssystem unterstützen, welche Regeln (Protokolle) sind dafür zu implementieren? Wie kann man das System in wohldefinierte Schichten unterteilen?
Schichten sind notwendig, da das Zusammenfassen aller Funktionen in einer Applikation schlicht unmöglich ist. Daher werden virtuelle Schichten eingeführt, die ihrerseits kleine Teilprobleme lösen, auf den Schichten unter ihnen aufbauen und diese ergänzen und den anderen Schichten über ihnen Schnittstellen zur Verfügung stellen, auf denen dann aufgebaut werden kann. Auch das ist eine Form von Divide and Conquer.
Dienste
Jede Schicht bietet also einen Dienst an, auf den über einen Standardisierten Service Access Point (SAP) zugegriffen werden kann. Dabei ist den anderen Schichten völlig Brust, wie dieser Dienst von statten geht. Er ist einfach da und man kann ihn nutzen ohne zu wissen wie er funktioniert.
Dienste haben gewisse Grundfunktionen (primitives). Zum Beispiel:
- Request (REQ): Schicht um einen Dienst bitten
- Indication (IND): Höhere Schichten darüber informieren, das jetzt was passiert
- Response (RES): Höhere Schicht antwortet auf Indikation (indem zB Daten angenommen werden)
- Confirmation (CONF): Der, der den Dienst ursprünglich in Anspruch nehmen wollte, wird nun über Erfolg oder Misserfolg informiert.
Das Ganze mal an Hand eines Telefongesprächs:
1.Sebbls Nummer wählen – REQ
2.Telefon nutzt das Netz und das Telefon klingelt bei Sebbl – IND
3.Sebbl macht den Porno aus und nimmt das Telefon ab - RES
4.Sebbl meldet sich am Telefon mit erotischer stimme – CONF
Übertragung über das Netz
2 Möglichkeiten:
- als eindeutig abgegrenzte Pakete (so machts IP)
- als Bytestrom, den der Empfänger dann auseinanderfuddeln muss
An beide Möglichkeiten können verschiedene Ansprüche gestellt werden (nicht immer alles notwendig):
- Daten müssen komplett ankommen
- Korrektheit (WENN es ankommt, DANN ist es auch korrekt)
- Daten werden in der Reihenfolge empfangen, in der sie gesendet wurden
- Netzwerk soll sicher und verlässlich sein
- Sender muss darüber informiert werden, wenn Daten angekommen sind (Acknowledge)
verbindungsloser vs. verbindungsorientierter Dienst
Verbindungsorientierte Dienste bauen vorm Datenaustausch erst eine Verbindung auf (CONNECT) und müssen auch in der Lage sein, auf eine Verbindung zu warten wie beim Freizeichen (LISTEN) und müssen diese nach getaner Arbeit wieder terminieren können (DISCONNECT). Außerdem müssen sie eingehende Verbindungen peilen (INCOMING_CONN) und diese annehmen können (ACCEPT). Beispiel: Telefongespräch
Verbindungslose Dienste brauchen diesen ganzen Schnickschnack nicht, da kann man eifnach so Dienste in Anspruch nehmen, ohne das da großartig Verbindungen vorher aufgebaut werden müssen. Beispiel: Post (muss Omma nich sagen, das ich ihr n Paket schicke und sie muss das bestätigen – ich kanns einfach als Überraschung schicken).
Protokolle
Protokolle sind in der Netzwerkwelt unabdingbar – sie geben die Regeln vor, nach denen sich die Maschinen zu verhalten haben. In Protokollen werden die grundlegenden Abläufe definiert und festgeschrieben. Wenn zB der Sender eine 1 mit „Strom fließt interpretiert, der Empfänger aber unter „Strom fließt“ eine 0 versteht“, dann funktioniert das Netzwerk genauso gut wie Sebbls .NET-Programme. Ich glaube demnächst werde ich mal das Opfer wechseln und jemand anders dumm machen, sonst haut mir der Sebbl noch aufs Maul.
Zurück zum Wesentlichen – Protokolle sind also als ein Set von Regeln zu verstehen, die den Service quasi implementieren. Da die höhere liegenden Schichten nicht direkt miteinander kommunizieren sondern sich dafür die unteren Schichten zu Eigen machen, müssen die höheren Schichten logischerweise dieselben Protokolle verwenden um sich verstehen zu können. Dafür ist möglicherweise das Anfügen eines Headers an die Daten notwendig.
Protokolle können folgende Aufgaben haben: Adressierung, Fragmentierung, Teilen von langen Paketen in kleinere, Fehlerkontrolle, Anordnen von Paketen, Flusskontrolle, Flood-Schutz bei langsamen Netzwerkelementen, Ressourcenmanagement, Komprimierung und Herrn Jägers Mutter füttern (harte Aufgabe).
Protokolle sind also eine horizontale Beziehung zwischen 2 gleichen Schichten verschiedener Netzwerkteilnehmer.
Dienste hingegen sind vertikale Beziehungen der Schichten untereinander.
Schichten
Die einzelne Schichten kennt an sich nur die Schicht über und die Schicht unter sich und kann auch nur deren Schnittstellen nutzen bzw von der darüber liegenden Schicht benutzt werden. Dabei weiß die höhere Schicht nichts über die untere, die untere Schicht ist einfach da und funktioniert. Mehr muss man nicht wissen. Ich zitiere aus meinem Artikel zum Objekten und Klassen: „Das ist wie wenn Frauen Auto fahren: Sie wissen nicht, wie das Auto funktioniert aber bewegen können sie es trotzdem (zumindest so halbwegs).“
Die Daten wandern also von der höchsten Schicht des Senders immer weiter runter zur untersten physikalischen Schicht, werden dort übertragen und wandern dann am Empfänger alle Schichten wieder fein artig hoch. Das ist natürlich nicht sonderlich effizient (Redundanz, Kompetenzüberschneidungen), macht aber Verbesserungen, Wartung, Updates etc einer einzelnen Schicht extrem einfach.
ISO/OSI-Modell
Altbekannt, Bildchen gibbs im Netz. Nur nochmal ein kurzer Überblick über die Schichten:
- Physical Layer: Sorgt für die physikalische Verbindung zwischen 2 Netzwerkteilnehmern. So richtig mit Strom, Spannung und so weiter. Dabei sind verschiedene Datenübertragungskanäle möglich, also nicht nur Kupferkabel sondern auch Glasfaser oder drahtlose Kanäle wie WLAN. Stellt außerdem sicher, dass die Bits in der richtigen Reihenfolge ankommen und kann unter Umständen Fehlerkontrolle enthalten.
- Link Layer: Synchronisiert die Blöcke.
- Network Layer: Sorgt sich um den Weg der Daten zum Ziel. Bereitet logische Wege der Daten vor, auch zu Subnetzwerken die sich sonstwo befinden können, Routing halt. Stellt Netzwerkadresse zur Verfügung.
- Transport Layer: Sorgt für den endgültigen Transport der Daten, abhängig von der Netzwerkstruktur (verbindungsorientiert/verbindungslos/verlässlich/...)
- Session Layer: Synchronisation und Austauschmanagement der Daten - wann darf wer wieviel und wie lange senden
- Presentation Layer: präsentiert die Daten (Aufbereitung für Application Layer) - dafür wird der Syntax verändert, die Semantik bleibt jedoch erhalten. Der verwendete Syntax ist systemabhängig.
- Application Layer: Direkte Schnittstelle zum Enduser, stellt diesem dann halt einfach zu nutzende Funktionen zur Verfügung >> Virtual Terminal
Kritikpunkte am ISO/OSI-Modell gibt es zuhauf: Zwar ist die grundlegende Idee der Unterteilung in Schichten auch heute noch gebräuchlich, aber für das Modell entwickelte Protokolle spielen heutzutage keine Rolle, dem Modell fehlt einfach die Martkakzeptanz. Es ist zu groß, zu komplex, es gibt Entwurfsfehler, die ersten Implementierungen waren grottenschlecht und der ganze bürokratische Muff von der ISO bekam der Sache auch nicht gut. Zusätzlich erschien es zu einem ungünstigen Zeitpunkt.
Welche Anforderungen muss ein Modell für das Internet erfüllen?
Das Internet Protocol Modell verbindet die 3 obersten Schichten von ISO/OSI zu einer „Internet Layer“. Die Anforderungen an das Internet sind vielfältig: Es muss jede Art von Daten aufnehmen können (Audio, Nachrichten, Pornos), muss mit verschiedenen Netzwerktechnologien und Clients zurechtkommen (PC, PDA, Handy, ....), muss robust sein, muss ständig erweiterbar sein ohne an Performance zu verlieren (Skalierbarkeit), etc.
Günstig hierfür ist eine Struktur mit einem „dummen“ Netzwerk aber sehr komplexen Endgeräten (Telefon is andersrum). So ist das Internet an sich robust, wenn ein Endgerät mal ausfällt is das ziemlich Brust. Außerdem werden so alle Pakete gleich behandelt (best effort Dienst) und Pakete können verloren gehen, verdoppelt werden etc – die Reihenfolge muss gleich garnicht stimmen. Dafür is das alles sehr billig und man aknn schnell riesige Netze errichten. Die intelligenten, teuren Endsystem bügelt das schon aus (reorder usw.)
Das Ganze wird mit 2 Protokollen auf Basis der Transportschicht geregelt:
- TCP – ein verlässlicher Bytestrom
- UDP – unverlässlicher Datagrammdienst
Darunter ist der IP-Service (best-effort) auf Layer 2, darüber finden sich halt die bekannten Dienste wie zB HTTP, FTP, SMTP, DNS, etc.
Das Ganze nennt sich nun TCP/IP. Dazu existiert lustigerweise kein Modell, es ist aber das, was heutzutage in der Praxis verwendet wird. Ind er Vorlesung behandeln wir eine vereinfachte Variante von ISO/OSI, mit dem man auch TCP/IP erklären kann. Dazu wird der Applikationsschicht die Session-Layer und die Presentation-Layer, die eh kein Mensch kapiert hat, einverleibt. Somit gibt’s also nur 5 Schichten.
Zusammenfassung
- Die Komplexität von großen Netzwerken fordert die Unterteilung in Schichten, um das Ganze handhabbar zu machen.
- Jede dieser Schichten offeriert einen Dienst, nach oben hin werden die Dienste immer komplexer (und abstrakter), sie bauen auf den darunter liegenden Diensten auf und nutzen diese.
- Gleiche Schichten in verschiedenen Teilnehmern nutzen Protokolle, um zu kopperieren – diese Schichten sind nicht miteinander verbunden und brauchen daher Standards/Regeln, die jeder kennt und achtet.
- Protokolle sind also eine horizontale Beziehung zwischen 2 gleichen Schichten verschiedener Netzwerkteilnehmer. Dienste hingegen sind vertikale Beziehungen der Schichten untereinander.
- Es gibt 2 bedeutende Referenzmodelle, die das Schichtensystem abstrahieren – ISO/OSI (bedeutendes Modell, keine praktisch Relevanz) und TCP/IP (kein Modell, praktisch relevant) – durch sie wird beschrieben, welche Dienste welche Schicht anbieten muss und wie die passenden Protokolle aussehen müssen
Physical Layer
Wie können Daten über ein physikalisches Medium transportiert werden?
Die Data Link Layer gibt dem Physical Layer einen Bitstrom weite,r also eine Folge von Bits, die korrekt sind und in richtiger Reihenfolge geliefert werden. Die Physical Layer muss das Zeusch jetzt übertragen – mit Bit-zu-Signal-Konvertierungsregeln (zB Bit=1: Strom fließt, Bit = 0: Ruhe aufm Leiter).
Fouriertheorem
Jede periodische Funktion lässt sich als Summe von sin und cos Schwingungen ausdrücken, deren Frequenzen ganzzahlige Vielfache einer Grundfrequenz f = 1/ T sind.
Auch unsere übertragenen Daten – die ja so aussehen wie eine zufällige Folge von Rechtecken (digitale 0en und 1en halt) - kann man Fourier-transformieren, wenn man annimmt, sie wiederholen sich unendlich hofft –> Annahme, das Zeug sei periodisch.
Probleme bei der Übertragung
- Der Empfänger empfängt womöglich ein völlig verrauschtes Signal - die Entscheidung, was gesendet wurde, kann schwierig werden.
- Signale werden gedämpft, Teile der Leistung der Signale geht verloren. Dämpfung a = PSender / PEmpfänger. Die Dämpfung hängt vom Material, von der Entfernung und von anderen Faktoren ab, angegeben wird sie allgemein in dB.
- nicht alle Frequenzen gehen durch das Medium: Das Medium kann zB eine obere Grenzfrequenz haben.
- die Dämpfung kann natürlich auch frequenzabhängig sein – manche Frequenzen werden kaum gedämpft, andere dagegen sehr stark.
- Das Medium verzerrt die Signale, da sich einige Frequenzen schneller ausbreiten als andere – damit haben wir eine frequenzabhängige Phasenverschiebung am Ausgang
- reale Medien sind verrauscht – Zum Signal wird ein zufälliges Rauschen addiert, zB AWGN – TKT lässt grüßen
Lösungsansätze
Der Empfänger tastet die empfangene Rechteckfolge ab, am besten genau in der Mitte eines Bits, weil da die Wahrscheinlichkeit am höchsten ist, das da die korrekte Amplitude liecht. Aber wo ist die Mitte des Bits? Nicht einfach zu finden bei Sinus-Schwingungen! Nicht genau erkennbar, ob 0 oder 1 gewendet wurde, wenn wir an der Amplitude abtasten – wir müssen also Schwellwerte einführen. (03-22). Unter threashold 1 ists 0, über threashold 2 ist es 1 und dazwischen isses nicht definiert.
Diesen Zwischenbereich darf man nicht zu groß und nicht zu klein wählen – ist er zu groß, fallen mehr Punkte rein und man kann mehr Punkte nicht entscheiden, ist er zu klein, ist die Wahrscheinlichkeit für eine Fehlentscheidung höher. Man kann bei sehr niedriger Bandbreite also nur noch die Zeit, die ein Bit braucht, so lange erhöhen, bis die Kurve definitiv über die entsprechende Schwelle gestiegen ist – dann reduziert sich aber die Datenrate. Daraus ergibt sich eine Gleichung für die Datenrate: maximum data rate = 2 B bits/s (B=Bandbreite)
Symbole
Wer sagt eigentlich, das wir nur 2 Bits unterscheiden können? Wie wärs zum Beispiel mit Signalen mit 4 verschiedenen Stufen? Dann hätten wir 4 Symbole, die wir mit 2 Bits darstellen können. So ein Symbol kann natürlich euch aus mehr Bits bestehen. Gemessen wird die Symbolrate in baud (die Datenrate hingegen in bits/s).
Wenn wir ein Symbol aus 2 Bits bauen ist die Symbolrate natürlich nur halb so groß wie die Datenrate.
Wenn wir ein Symbol aus 3 Bits bauen ist die Symbolrate natürlich nur 1/3 mal so groß wie die Datenrate.
Allgemein gilt (nach Nyquist): maximum data rate = 2 B log_2 V bits/s wobei V für die Anzahl der Symbole steht. Heißt das nicht, das ich eine unendlich hohe Datenrate erhalte, wenn ich nur genügend Symbollevels definiere? Ja, theoretisch schon – aber umso höher meine Symbollevelanzahl, umso näher liegend ie ja zusammen und ich hab schon bei kleinem Rauschen schnell mal ne Fehlentscheidung – also eine sehr hohe Symbolfehlerrate. V hängt also vom Rauschpegel N ab – aber auch von der Signalstärke S, da ich ja bei stärkerem Signal auch größeres Rauschen haben kann. V = (1 + S/N)^1/2
Daraus folgt: maximum data rate = B log_2 (1 + S/N) bits/s
Takt
Logischerweise brauchen wir auch einen Takt, damit der Empfänger weiß, wann er das Signal auf seinen Wert abtasten soll. Synchronisation zwischen Sender und Empfänger notwendig. Wie soll er sonst wissen, ob man nun 10 oder 11 Einsen am Stück gesendet hat?
Man kann das Taktsignal extra übertragen, das kostet aber Material und eignet sich daher nur für kleine Entfernungen. Man könnte auch nur an bestimmten Punkten synchronisieren, muss dann aber mit Ungenauigkeiten rechnen. Am besten ist es, die Synchronisation direkt aus dem übertragenen Datensignal zu kriegen.
Das geht fast schon automatisch, wenn ich viele 0-1 Flanken (oder andersherum) hab – da is die Synchro einfach.
Wenn ich aber viele Nullen und Einsen hintereinander übertrage, verliere ich den Takt. Daher gibt’s die Manchester-Codierung (03-36) – da wird die 1 durch eine high-low Flanke und die 0 durch eine low-high Flanke repräsentiert. Problem – ich brauche dafür natürlich die doppelte Bitrate, das ist natürlich sehr verschwenderisch.
Breitbandübertragung
Wie gesagt, im Basisband haben wir viele Probleme – die 0en und 1en gehen direkt aufs Kabel, sind quasi als Rechteckfunktionen zu vertsehen und brauchen daher im Frequenzbereich eine enorme Bandbreite. Hinzu kommen frequenzabhängige Phasenverschiebungen und Dämpfungen. Wie werden wir das los? Wir bemächtigen uns einer sinusförmigen Trägerschwingung mit einer einzigen (hohen) Frequenz. Womit wir wieder bei AM, PM und FM wären, die der Sinus-Schwingung Informationen '“aufdampfen“. Das auch digital, mit ASK, PSK und FSK. Beispiel für On-Off-Keying: 03-41 bzw. QPSK: 03-44.
Zusammenfassung
- Der Physical Layer hat die Aufgabe, eine logische Bitfolge in ein physikalisches Signal (viele Möglichkeiten) zu verwandeln und über einen Kanal zu senden.
- Es gibt viele lustige Probleme wie Rauschen, zu wenig Bandbreite usw.
- Bits kann man in Symbole zusammenfassen
- Modulation mit stufenförmigen Trägern bringt viele Vorteile
Link Layer
Die Link Layer hat die Aufgabe, den kontinuierlichen Bitstrom in Rahmen/Pakete zu verpacken, ihn also für darüberliegende Schichten lesbar zu machen. Dabei werden auch gleich Fehler gefunden und korrigiert – die physikalische Schicht garantiert ja für nix und einer muss die Fehler ja finden :) Dabei gibt’s viele Fragen – soll es ein zuverlässiger Dienst sein (also fehlerfreie in richtiger Reihenfolge Pakte liefern), soll er verbindungorientiert arbeiten, wie groß soll die Paketlänge sein (umso größer, umso größer ist die Paketfehlerwahrscheinlichkeit)?
Auch Flusskontrolle gehört zur Aufgabe der LL – wenn der Empfänger langsamer ist als der Sender, läuft der Pufferspeicher des Empfängers schnell voll und viele Daten gehen verloren, wenn der Sender nicht mal Pause macht.
Framing
Rahmen und Pakete sind dasselbe, aber auf Link-Layer-Ebene heißts eben Rahmen. Die Rahmengröße ist an das Übertragungsmedium anpassen – je besser das Medium, desto länger kann der Rahmen sein.
Ein großes Problem der Sache ist – wie erkennt der Empfänger aus einem kontinuierlichen Bitstrom, wo ein Rahmen anfängt und wo er wieder aufhört? Verschiedene Verfahren:
- Character Counting (04-12): Rahmen bekommt einen Header, in dem drinsteht, wie lang der Rahmen ist. Einfacher gehts nicht – was aber wenn die Information im Header verloren geht oder beschädigt/verfälscht wird? Dann kommt hinten nur dünnes raus, wie bei Herrn Jäger nach nem halben Bier!
- Flag Bytes / Byte Stuffing: Das Flag-Byte zeigt Beginn und Ende eines Rahmens an. Problem: Was ist, wenn Flag-Byte in den Nutzdaten auftauacht, weil die Nutzdaten halt so aussehen? Nehmen wir mal an, das Flag Byte wäre 0 11 11 11 0. Wenn das nun in den Nutzdaten auftauchen würde, wäre der Rahmen und alle darauf folgenden unbrauchbar. Also werden Bytes in die Nutzdaten gestopft, das keine 6 Einsen hintereinander auftreten können – zB wird nach der 5ten 1 immer eine 0 gestopft. Der Empfänger weiß das und nimmt nach jeder 5ten 1 die 0 wieder raus. So tritt das Flag Byte niemals in den Nutzdaten auf.
- Coding Violations: Frames kann mach auch abgrenzen, indem man Coding Regeln verletzt – zB. bei Manchester ein high-high oder low-low überträgt.
Fehlerkontrolle
- wurde ein oder mehrere Bits gekippt bei der Übertragung?
- soll LL die Fehler nur erkennen oder auch reparieren? beides, Network-Layer will sich nicht mit Fehlern rumplagen
Möglich ist aber auch, das die Fehler nicht korrigiert werden – Der Rahmen wird dann einfach weggeschmissen.
Ebenso möglich ist eine Korrektur ohne Erkennung – versuchen, soviel wie möglich zu reparieren aber nicht dafür garantieren, das alles fehlerfrei ist, das mus dann halt die nächste Schicht wissen und sich darauf einstellen.
Wenn man korrigiert, gibt’s 2 Möglichkeiten:
- Backward Error Correction – Fehler ausbügeln, nachdem sie passiert sind (durch neu senden zB)
- Forward Error Correction – Fehler garnicht erst entstehen lassen, zB durch Redundanz in den zu übertragenden Daten
Egal wie sehr man sich anstrengt – die Fehlerwahrscheinlichkeit sinkt nie auf 0!
Wie kann man nun Fehler in einem Rahmen finden?
---Redundanz--- Redundanz ist für die Fehlererkennung unerlässlich. Ohne redundante Bits gibt es 2^m legale Rahmen der Länge m – der Empfänger kann nicht entscheiden, ob ein Rahmen falsch ist, weil es keine illegalen Rahmen gibt. Kippt ein Bit, wird aus einem gültigen Rahmen ein anderer gültiger Rahmen. Man muss also einige mögliche Rahmen als illegal erklären. Daher hängt man also ein paar Redundanzbits an (will m Datenbits behalten) und erklärt ein paar Kombinationen als illegal und hofft nun, dass, wenn ein Bit kippt, aus einem legalen Rahmen ein illegaler Rahmen wird. Wie aber drückt man die Wahrscheinlichkeit nach unten, das auch bei Bitfehlern ein legaler Rahmen entsteht? Möglichkeiten:
- Paritiy-Bit: Ein Parity-Bit wird so angehangen, das man eine gerade Anzahl von Einsen im Rahmen hat (oder halt gerade Anzahl von Nullen oder ungerade Anzahl von Einsen, wie mans halt definiert). Kippt ein Bit, kann man definitiv sagen, das der Rahmen falsch ist. Ach bei 3,5,7,.... Bits. Problem: Kippt eine gerade Anzahl von Bits, kann man den Fehler nicht erkennen. Korrigieren kann man ihn in keinem Fall.
- Checksums: Der Sender behandelt die Daten als Integer-Zahlen und addiert sie zusammen – dann wird das Ergebnis der Addition an den Rahmen angehängt und der Empfänger kann die Korrektheit des Rahmens prüfen. Wenn natürlich die Bits so bleede kippen das die Summe nach dem Fehler gleich bleibt, funzt das ooch nich (04-28).
---Hamming-Abstand---
Der Abstand d(x,y) wird definiert als die Anzahl der Einsen in x XOR y. Beispiel: 04-30. Die Hamming-Distanz ist nun D(s) = min{d(x,y)}, also der kleinste Abstand zwischen 2 Rahmen x und y wobei x !=y. S steht für sein Set legaler Rahmen (4-31).
- Wenn die Hammingdistanz 1 ist, unterscheiden sich ein oder mehrere Rahmenpaare nur in einem Bit – Fehlererkennung oder gar Korrektur unmöglich.
- Ist die Hamming-Distanz 2, führt ein Bitfehler grundsätzlich dazu, das der Rahmen illegal wird, weil alle legalen Rahmen sich in 2Bits unterscheiden. Korrektur? Fehlanzeige.
- Ist die Hamming-Distanz 3 wird’s kompliziert. x und y sind legale Rahmen. u wird empfangen. Nehmen wir an, u hat den Abstand 1 zu x und den Abstand 2 zu y. Dann ist es wahrscheinlicher, das der empfangen Rahmen u ein x sein soll – wenns doch ein y war, bei dem sich 2 Bits gedreht haben, haben wirs verschlimmbessert.
- allgemein: Um n Bitfehler zu finden, ist Hamming-Distanz von n+1 nötig. Um n Bitfehler zu korrigieren, Hamming-Distanz von 2n+1 nötig.
Cyclic Redundancy Check - CRC
CRC kommt mit wenigen Redundanzbits aus, ist zuverlässig und kann leicht in Hardware implementiert werden. Das Ganze basiert auf einer Interpration des Bitstroms als Polynom – das i-te Bit ist Koeffizient der i-ten Potenz. Damit gibt’s nur Nullen und Einsen als Koeffizienten. Also – ein Bitstrom, der n+1 Bits lang ist, enstpricht einem n-gradigem Polynom (weil b0*x^0)
- Rechenregeln: Addition ohne Übertrag = Subtraktion ohne Übertrag. Weill man an einen Bitstring hinten k Nullen an hängen entspricht das der Multiplikation des Polynoms mit x^k – logisch, das Polyonom wird um k verschoben. Und guckt euch das Beispiel der Polynomdivision auf Seite 4.41 nochmal an. Interessant ist für uns der Rest der Polynomdivision.
Wie funktioniert der Spaß nun? Zuerst mal definieren wir uns ein Generatorpolynom G(x) g-ten Grades, das sowohl Sender als auch Empfänger bekannt ist – wir haben also g Redundanzbits. Die Nachricht M wird durch das Polynom M(x) repräsentiert.
1. Zuerst mal hängen wir an M(x) g Nullen dran – x^g * M(x) 2. Dann teilen wir x^g * M(x) durch G8x) und berechnen den Rest r(x). 3. jetzt machmer noch x^g * M(x) – r(x), das bewirkt, das die letzten g Nullen von x^g * M(x) durch den wert r(x) ersetzt werden – Subtraktion ohne Übertrag = XOR.
Das Zeug – nenne wir es T(x) - übertragen wir jetzt zum Empfänger. Lustig ist nämlich, das T(x) jetzt ohne Rest durch G(x) teilbar sein muss. Gibt es Bitfehler, wird T(x) + E(x) empfangen.
Der Empfänger prüft jetzt das Empfangene indem er das Empfangene durch G(x) teilt.. Wurde die Nachricht fehlerfrei übertragen, gibt’s keinen Rest. Gibt es einen Fehler E(x), so bleibt der Rest E(x)/G(x) nach der Division übrig – Fehler wurde gefunden und kann korrigiert werden.
Nur für den unwahrscheinlichen Fall, das E(x) / G(x) = 0 ist, erkennen wir den Fehler nicht. Damit das nicht passiert, musst G(x) möglichst intelligent gewählt werden. TCP zB verwendet CRC-32, also ein Polynom 32ten Grades – wenn da doch noch ein Fehler durchschlüpft, also wenn G(x) tatsächlich noch Teiler von E(x) sein sollte, wird das einfach ignoriert.
Backward error correction
Wenn der Empfänger einen Fehler feststellt, kann der Rahmen natürlich nicht einfach so zur nächsten Schicht weitergeleitet werden – reparieren oder wegschmeißen (und dann neu anfordern). Fürs Reparieren braucht man aber viele redundante Informationen im Rahmen (forward error Zeusch). Backward-Protokolle laufen unter dem Namen ARQ – Automatic Repeat Request (schigge mir das Bageed nochäma neu duuu!).
Wie weiß der Sender, das ein Paket nicht ankam? Der Empfänger könnte zB ACKS schicken. Nur... Dann weiß der Sender immer noch nicht, welches Paket nicht ankam. Und was ist, wenn ACKS verloren gehen?
- Send 'n Wait: Der Sender könnte zB mit dem Senden eines neuen Paketes warten, bis das alte beim Empfänger ankam und es ein ACK dafür gab. Kommt das ACK nicht, wird das Paket nach einem Timeout neu gesendet. Da haben wir gleich noch Flusskontrolle mit drin. Problem ist nur – was ist wenn ein ACK verloren geht? Dann wird das selbe Paket nochmal gesendet. Der Empfänger weiß aber nicht, ob das das alte Paket ist oder ein neues, das zufällig die gleiche Information tragen muss.
- Alternating Bit Protocol: Was dagegen tun? Den Paketen Sequenznummern geben und diese in einem Header mit übertragen – und die ACKs müssen diese Sequenznummern auch enthalten. Damit kriegt das ACK eine zusätzliche Bedeutung – er erlaubt dem Sender nun auch, das neue Paket zu senden und bestätigt nicht nur den Empfang des alten. Das Ganze heißt dann Alternating Bit Protocol, weil die Pakete jeweils abwechselnd mit 0 oder 1 identifiziert werden. (4-60). Aber ist das Alternating Bit Protocol auch effizient? Wenn ein Paket über die Leitung geht, braucht es ja eine Zeit d_prop um drüben zu sein. Wenn der E dann das ACK zurückschickt, ist das ja auch lange unterwegs. Das bedeutet,d ie Leitung bleibt lange unnutzbar für Daten. (4-61).
- Sliding Windows:
Was tun – klar, mehrere Pakete hintereinander senden, noch bevor die ACKs fürs vorige Paket kamen. Dann reicht aber das Alternating Bit nicht mehr aus, um die Pakete eindeutig zu identifizieren – ein größerer Adressraum ist von Nöten. Und Full Duplex braucht man ooch noch. Geben wir der Sache mal einen n-wertigen Adresseraum mit 2^n möglichen Adressen (von denen vll ein paar verboten sind). S und E einigen sich auf ein bestimmtes Set von Paketnummern, die in einer bestimmten Zeit übertragen werden dürfen – der Sender sendet also Pakete und der Empfänger nimmt nur Pakete an, deren Nummer im Set steht. Die Anzahl der Nummern und damit auch die Anzahl der Pakete die in einem bestimmten Zeitraum gesendet werden dürfen, ist die Fenstergröße. Die Fenstergröße an S und E kann auch unterschiedlich sein – Flusskontrolle.
- Go Back N: Geht nun ein Rahmen durch einen Fehler verloren, zB weil er nicht durch die CRC Prüfung kam, gibt’s ein Problem – dadurch das die Paketnummern eine bestimmte Reihenfolge haben, schmeißt der Empfänger alle Pakete, die ihn nach dem fehlerhaften Paket erreichen, weg. Der Sender aber kriegt davon erstmal nix mit, er sendet fröhlich weiter seine Pakete – nur die ACKs dafür bleiben aus. Das merkt der Sender auch irgendwann nach einem Timeout-Intervall. Aber bis dahin wurden viele Ressourcen auf der Leitung verschwendet. Der Sender geht also um n Schritte zurück, zum letzten Paket, dessen Übertragung geklappt hat und setzt von dort aus die Übertragung fort.
- Selective Reject: Schade natürlich, das bei Go-Back-N so viele eigentlich intakte Pakete weggeschmissen wurden – wäre es nicht besser, der E würde die Pakete erstmal cachen? Das macht Selective Reject – es speichert die Pakete nach einem Fehler, sendet aber erstmal immer das ACK des letzten korrekt empfangenen Pakets vor dem Fehler, damit der S merkt das es einen Fehler gab. Liefert der Sender nun das fehlende Paket nach, sind darauf folgende Pakete bereits im Speicher und können über ACKs bestätigt werden. (4-67).
- Piggybagging: Wenn beide Teilnehmer full duplex unterstützen und Daten hin und her senden, muss man Daten und ACKs ja nicht trennen – Die ACKs werden in den Daten mitgeschickt.
Zu Effizienz der Geschichten bitte mal die paar Seiten ab 04-70 lesen, das sind Grafiken und Formeln, da habsch jetzt keen Bock...
Zusammenfassung
- Am meisten hat die LL mit Fehlern zu tun – entweder bei der Synchronisation (in Rahmen packen) oder bei der Übertragung (Fehlererkennung/-Reparatur
- Einige Fehlererkennungsprotokolle implantieren gleich die Flusskontrolle mit
- manche Fehlererkennungsmechanismen beeinflussen die Performance kräftig – gute Wahl treffen
- Vermögensaufbau und -abbau müssen noch behandelt werden – S und E müssen sich ja vorm Datenübertragen über einiges einigen, zB Windows Size, Paketsequenznummern usw
- Herr Jäger müffelt. [Anm. von Herrn J.: "Deine Mutter ...."]
Medium Access Control
Wie teilt man sich ein Medium mit vielen Teilnehmern, so das es performant bleibt? Wenn sich zB auf ner Cocktailpaty zuviele Leute unterhalten, versteht keiner mehr was – genauso ist das beim Netzwerk, wenn ein E gleichzeitig 2 oder mehr Signale empfängt, gibts Interferenz.
Daher gibts Multiple Acces Protocols, die den Zugriff auf ein shared Medium regeln.
Statisches Multiplexing
Modell: Gruppe von Sendern, auf der anderen Seite der Leitung Grupep von Empfängern – Multiplexer empfängt gleichzeitig die Pakete der Sender, gibt sie auf die Leitung, Demultiplexer verteilt Pakete an Empfänger. Dabei kriegen die Pakete entweder gewisse Sendezeiten oder gewisse Frequenzen auf der Leitung.
Das is aber Mist, wenn man lange idlet und dann mal irgendwann 10 Minuten hohen Traffic erzeugt, weil man ja feste Zeiten zugewiesen kriegt, und diese lange nicht nutzt (idle) aber dann, wenn man Traffic braucht, kriegt man keinen – das muss dynamischer werden, mit Prioritäten und dem ganzen Kram.
Dynamic Channel Allocation
- Teilen sich Stationen einen Kanal, dann können sei nur über diesen kommunzieren – is der tot is alles scheiße
- Auf einem Kanal kann es zu Kollision von Paketen kommen, wenn diese „frontal zusammenstoßen“
- Man müsste Stationen anzeigen, das der Kanal belegt ist
- Wie verteilt man die Ressource fair? - Wichtig ist, soviele Pakete wie möglich so schnell wie möglich zu transferieren, trotzdem muss für viele Situationen noch genügend Durchsatz für die Einzelstation verfügbar sein und die das Delay darf nicht zu groß werden
Wir utnerscheiden nun verschiedene Protokolltypen an Hand eines wichtigen Merkmales – lassen sie Kollisionen zu oder nicht? (Protokolle, die Kollisionen zulassen, heißen auch Contention-Protokolle, contention = Streit, Auseinandersetzung)
Collision based Protocols
- ALOHA:
Rede einfach, wenns dir grad passt – das einfachste Protokoll. Vorteile sind, das es einfach zu implementieren ist und das keine Kommunikation zwischen den Teilnehmern nötig ist (also zB müssen sich die Sender zum Satelliten nicht untereinander verständigen). Nachteil ist – Kollisionen kommen definitiv vor. Und – der Sender weiß nicht, ob sein Paket angekommen ist, denn auch die ACKs können kollidieren.
Performance von ALOHA: Verträgt unendlich viele Stationen, die alle unabhängig von einander und gleichartig arbeiten (u.i.v.). Ein Paket wird entweder von einem Paket zerstört, das vor ihm rausging und auf dem Medium ist oder von einem Paket, das nach ihm rausgeht, bevor es am E angekommen ist – das entspricht einem Intervall von 2 d_Trans. Auf 5-22 wird berechnet, das ALOHA gerade mal 20% Durchsatz erreichen kann. Das ist alles andere als schnell. Das Problem is, das ein Paket soo lange Zeit verwundbar ist. Man kann jetzt noch Zeitpunkte (time slots) einführen, bei denen Pakete gesendet werden dürfen (und nur dann), das verbessert die Sache nochmal, bringts aber auch nicht wirklich (slotted ALOHA)
- Carrier Sense Multpiple Access (CSMA):
Besser man hört erstmal zu bevor man losbrabbelt – also das Medium erstmal abhören, obs auch wirklich frei ist. Nur... Wenn das Medium belegt ist, wann bin ich dran? Wann versuch ichs wieder? Wenn ich sofort, nachdem das Medium wieder frei ist sende (persistentes CSMA), is das sehr ungedugldig, denn wenn das mehrere machen, gibbs Kollisionen. Also wartet man einfach ne zufällige Zeit (nicht persistentes CSMA), bis man es nochnal versucht. Einfach nicht so gierig sein, Rücksicht auf die anderen nehmen – nicht dauernd den Kanal überwachen. Problem: Es gibt Fälle, da wartet man, obwohl man nicht warten muss, das is natürlich Verschwendung...
Persistentes und nicht-peristentes CSMA kann man kombinieren zum p-peristenten CSMA: Einteilung in Zeitintervalle. Wenn Kanal idle ist, dann mit Wahrscheinlichkeit p senden, mit Wahrsch. 1-p aufs nächste Intervall warten. Umso kleiner p, umso weniger Kollisionen – aber umso länger muss ich warten, bis ich mal was senden kann (die scheiße hier!) Hinzu kommt, das, wenn einer sendet, das ein anderer Sender nicht sofort mitkriegt und dann vll auch in den vermeintlich leeren Channel sendet – Kollision!
CSMA/CD: (Kollisionsdetektion) Wenn man nun Kollisionen entdecken könnte auf dem Medium würde man viel Zeit sparen, weil man nicht ewig auf Timeouts warten müsste – man könnte alsbald wieder neu senden. Ethernet arbeitet mit CSMA/CD. Der Sender hört einfach das Material ab – wenn das Empfangene sich von dem, was gerade gesendet hat, unterschiedet, gabs ne Kollision, dann... ja, was dann?
Man kann natürlich nicht sofort wieder neu senden, dann gibts ja gleich wieder ne Kollision. Man wartet also ne zufällige zeit und probierts dann neu – in einem der nächsten Zeitintervalle. Sicher resultiert auch dieses Verfahren in eine gewisse Idle-Zeit, aber... naja geht halt nich anders. Wenn man sich jetzt ein sog. „contention window“ mit k slots bastelt, kann der Sender einen dieser k Slots zum Senden raussuchen. Wie wählt man k? Umso kleiner, umso schneller gehts aber umso höher ist das Kollisionsrisiko. Man machts von den angeschlossene Teilnehmern abhängig – hat man wenig Teilnehmer, kann k kleine sein. k kann man auch immer schön dynamisch anpassen, je nachdem wie viele Teilnehmer angeschlossen sind bzw wie viel Last sie erzeugen – man siehts ja an der Zahl der Kollisionen, ob k zu klein ist, dann senken. Dabei verdoppelt bzw halbiert man die Fenstergöße oder addiert/subtrahiert immer ne Konstante oder... es gibt da viele Spielarten ^^
Kollisosionfreie Protokolle
Einfachstes Beispiel – TDMA. Jeder Netzwerkteilnehmer kriegt ein festes Zeitintervall zum senden. Naja, wir wissen ja – unfair, Ilden verschwendet Bandbreite usw.
- Bit-Map Protokoll
Wir vergeben die Zeitslots nur an die, die wirklich senden wollen. Die können sich melden und kriegen von einem Master einen Token, wie in der Schulklasse halt. Oder der Token wandert immer im Kreis (könnte dann aber auch verloren gehen).
Bit Map machts so – es gibt Contention Slots, das sind kurze Zeitintveralle die ein Sender für sich reservieren kann. Damit meldet er sich, das er ein Paket senden will. Das kann er tun, nachdem alle contention slots durchgelaufen sind. Bei wenig Daten ist das n bissel blöd, weil es ja ein wenig dauert bis die contention slots durchgelaufen sind, das gibt ein Delay. Bei ordentlich Traffic bewährt sich das Protokoll aber mit wenig Wartezeit und guten Durchsatz.
limited contention protocols
Man möchte eine kurze Wartezeit bei wenig Traffic und einen guten Durchsatz bei viel Traffic – gibts da ne gute Lösung? Man muss die contentions slots irgendwie dynamischer handeln, so das man bei wenig Last nicht warten muss, bis alle contentsion slots aller Teilnehmer durchgelaufen sind.
- Adaptive Tree Walk:
Wurde von den Ebenen eines Baumes inspiriert (05-44). Auf dem hächsten Level gibts nur einen Slot, den alle Knoten sich teilen (wenig Last). Gibts Kollisionen, dh entsteht zuviel Last, wird die Anzahl der Slots verdoppelt, so lange, bis das Netz wieder ohne Kollisionen arbeitet. Bei wenig Last dann halt wieder die Anzahl der Slots halbieren.
Ethernet
Ethernet (IEEE 802.3) ist bekanntlich die am meisten verwendete Kabelnetzwerktechnologie. Sie ist vor allem billig und geht bis 10 Gbit/s. Heutige Netzwerke sind meist sternförmig aufgebaut, dh alle Knoten führen zu einem zentralen Element (Hub, Switch). Ringförmig ginge auch, wer erinnert sich nicht an das gute alte BNC-Netzwerk auf der ersten Garagen-LAN? Ich glaube Herr Jäger, der durfte nie mitspielen ^^
Ethernet ist ein unzuverlässiger verbindungsloser Dienst – Es wird also keine Verbidnung vorm Senden aufgebaut und der Empfänger sendet auch keine ACKS, der Datagramstrom kann Lücken haben die dann von höheren Layern gefüllt werden müssen. Allgmemein wird die Manchester Codierung verwendet (+/- 0,85V) mit der Option auf Codeverletzung – zum Synchronisieren zB.
Paketaufteilung auf 05-52. Wenn Rahmen fehlerhaft sind und durchs CRC fallen, werden sie einfach weggeworfen.
Ethernet verwendet CSMA/CD mit binary exponential backoff. Das heißt:
- carrier sense (Adapter hört die Leitung ab, sendet nicht wenn jmd anderes sendet)
- collision detection: Der sender bricht seine Übertragung ab, wenn er merkt, das jemand parallel mit ihm sendet
- random access: Bevor der Sender es nochmal versucht, wartet er eine zufällige Zeit.
Im Detail:
Adapter empfängt Datagramm von der Netzwerkschicht, Wenn der channel idle ist, wird gesendet, wenn nicht, wird gewartet bis der Channel idle ist und dann sofort gesendet. Wenn der Frame durchgeht, ohne das der Sender eine andere parallele Übertragung bemerkt hat, gitl der frame als erfolgreich übertragen. Wenn jemand anderes sendet, wird die Übertragung abgebrochen und ein jam signal (Störsignal) wird an alle Stationen im Netz gesendet. Danach wird die exponential backoff Technik angewndet: Dabei hängt die zufällige Wartezeit von der Last des Netzes ab. Der Adapter wartet K*512 Bitzeiten mit K € {0,1,2,...,2^m -1}. Bei der ersten Kollision ist K entweder 0 oder 1(2^1 Möglichkeiten). Bei der zweiten Kollision ist K € {0,1,2,3} – also 2^2 Möglichkeiten. Bei der n-ten Kollsion gibts 2^n Möglichkeiten für k (also 0 bis 1023). Eine Bitzeit ist bei 10 Mbit Ethernet 1 µs, für K=1023 wartet der Adapter also satte 50 ms.
Effizienz: Schwer auszurechnen. Es gilt die Formel auf (5-56)
Ethernet is also viel besser als ALOHA, trotzdem einfach und billig.
Netzwerkelemente:
- Hub: Ein Hub ist dumm. Wenn er einen Frame von einem Adapter kriegt, schickt er ihn an alle anderen weiter. Stumpfsinnige elektrische Zusammenschaltung. Er kann nichts puffern, er verhindert keine Kollisionen, im Gegenteil.
- Switch: Ein Switch ist viel komplexer. Wenn er einen Frame empfängt, kann er ihn puffern und ihn auslesen, also er weiß wo der Frame hin soll und er weiß wie er ihn zum Ziel schicken kann. In einer Sterntopologie kommt es damit logischerweise auch nicht mehr zu Kollisionen und man kann auf das Performance-raubende CSMA/CD verzichten. Wenn an den Switch auf einem incoming-port mehrere Rechner angeschlossen sind, so wird aus diesen Rechner eine collision domain – also innerhalb dieser Rechner kann es noch zu Kollisionen kommen aber nicht zwischen verschiedenen collision domains.
Ein weiterer Vorteil des Switch ist, das er auch gleichzeitig mehrere 100 Mbit/s Connections verwalten kann, das heißt das die Performance des Netzwerks nicht unbedingt von der Anzahl der Knoten abhängt (beim Hub müssen sich die Knoten die Bandbreite teilen).
Fast Ethernet
Ethernet war ja eigenltich auf 10 Mbit/s ausgelegt. Es wurde aber zu Fast Ethernet verbessert, das bekanntlich 100 oder gar 1000 MBit/s Bandbreite liefert. Dabei sind die Protokolle untereinander kompatibel – man hat einfach die Bitzeit verkürzt. Damit ergeben sich allerdings Komplikationen, was die Kabellänge angeht, so das zB CAT5 Kabel, die ja bis zu 100 m lang sein dürfen, nicht mehr mit Manchseter arbeiten sondern mit 4B/5B.
Außerdem ist beim fast Ethernet jedes Kabel mit genau 2 Netzwerkelementen verbunden, das heiß´t jeder Rechner ist genau mit einem Hub/Switch/anderen rechner verbunden. So gibt es auch keine collision domains mehr und damit auch keinerlei Kollisionen, wenn man einen Switch verwendet. Und man kann full-duplex senden. Verwendet man einen Hub, ist das nich ganz so einfach – dann sind nur Kabellängen bis 25m möglich, man kann auch nur half-duplex senden. Daher kauft man eigentlich nur noch Switches, die sind ja auch nich so teuer.
Zusammenfassung
- ausgeklügelte MAC Protokolle sind wichtig für die Performance des Netzwerks
- 3 Hauptkategorien: Kollision, limitierte Kollision, Kollisionsfrei
- MAC-Protokoll muss Gleichgewicht zwischen Durchsatz, Wartezeit und Fairness finden – es gibt da nicht wirklich DIE optimale Lösung
- Beispiel: Ethernet – wichtig: Keep it simple!
Internetworking
Also.. wir können bis jetzt schonmal zwischen Knoten kommunizieren, die irgendwie am selben Medium hängen. Toll. Herrn Jäger seine Lichtanalage funktioniert auch und wir sind glücklich. Was aber, wenn wir über den Tellerrand hinaus blicken wollen? Wie verbinden wir verschiedene Netzwerke? Dazu, liebe Kinder, erzählt euch der Onkel jetzt mal die Geschichte von Routern, Bridges und Gateways. Es war einmal eine einsame Bridge, bis eines Tages ein Gateway... So Schluss jetzt, wieder ernsthaft:
LAN Interconnection
Wie verbinde ich mehrere LANs? Fangen wir beim Ethernet an. Wenn ich ein LAN mit zu vielen Knoten ausstatte, verliert es arg an Performance und das CSMA/CD pfeifft aus dem letzten Loch wie Sebbl nach einer Runde laufen aufm Sportplatz, wenn zuviele Kollisionen auftreten. Außerdem kann jeder zuhören/die Leitung abhören.
Also brauchen wir viele kleine LANs, die wir miteinander verbinden wollen. Und – vielleicht wollen wir auch mal verschiedene LANs miteinander verbinden, zB ein Ethernet mit einem Token Ring?
Gut, also wir brauchen dafür natürlich Geräte, die das machen. Aber in welcher Schicht setzen wir das an? Es gibt da verschiedene Möglichkeiten – Übersicht siehe 06-06.
Physical Layer Interconnects
- Repeater Einfachste Option. Einfach ein dummer Signalverstärker, der nicht sieht was er da verstärkt – es interessiert ihn auch nicht. Er verhindert nur die Abschwächung des Signals.
- Hub: Auch nich viel intelligenter. Viele Kabel gehen rein, viele Kabel kommen raus. Der Hub empfängt ein Paket von einem Kabel und gibt dieses auf alle anderen Kabel. Einfach eine elektrische Verbindung. Der Hub weiß nicht, wo das Paket hin soll und es interessiert ihn auch nicht. Daher erkennt er keine Kollisionen und verhindert damit auch keine.
Die Lösungen auf der physikalischen Schicht sind nicht zufriedenstellend. Man muss die Pakete auslesen können, man muss auf Lastsituationen reagieren können.
Data-Link-Layer interconnects
Der Switch kann die Pakete speichern und auslesen - er weiß wo sie hin wollen und kann sie zum Ziel leiten, also aufs richtige Kabel geben. So gibts keine collision domains. Problem ist natürlich – der Switch muss sich im Netzwerk auskennen, muss wissen über welches Kabel er welchen Teilnehmer erreicht – Routing.
Dazu benutzt der Switch eine Switchtabelle, in der so Sachen wie MAC Adresse, Interface, Zeitstempel usw drin stehen (Zeitstempel für Timeouts, wenn Rechner down oder vom Netz). Die Tabelle füllt er durch zuhören – wenn er ein Paket von A empfängt, weiß er ja, wos herkommt und über welches Kabel er A erreichen kann. Das nennt sich backward learning.
Wenn der Switch nun einen Frame kriegt, dessen Zieladresse er kennt, schaut er, ob Dest-Adress == Source adress. Dann wirft er den Frame weg, weil das Ziel den Frame schon erhalten hat. Andernfalls leitet der Switch den Frame weiter. Kennt der Switch die Zieladresse des Frames nicht, floodet er (schickt den Frame an alle).
Eine Bridge kann nicht nur einzelne Terminals verbinden wie ein Switch, sie kann ganze Netzwerke verbinden (zB Token Ring mit Ethernet). Auch die Bridge untersucht eingehende Pakete und schaut, wo sie hin wollen – die Bridge verbindet nun aber einzelne collision domains untereinander. Für einen Switch in einem der Netzwerke ist eine Bridge nichts weiter als ein Terminal. So wird ein ganzes Netzwerk auf einen einzigen Terminal abgebildet.
Eine Bridge verfügt natürlich auch über so eine Tabelle, in der alle Adressen drin stehen. Aber – reicht das backward learing, wie es der Switch macht, aus? Eigentlich schon. Beispiele mit lustigen Bildchen auf 6-18. Entweder die Bridge leitet das Paket intelligent weiter, wenn sie die Zieladresse kennt. Oder sie leitet das Paket an alle weiter (außer zurück zum Sender) wenn sie die Zieladresse nicht kennt. Oder sie verwirft das Paket, wenns unwichtig ist – zB wenn Empfänger und Sender im gleichen Netzwerk sind, dann muss das Paket nicht an andere Netzwerke rausgehen.
Problem des backward leraings: Wenn man 2 Bridges verwendet, kann das Paket im Kreis laufen (6-20). B1 floodet, Paket zu B2. B2 floodet, Packet zu B1. Usw. Solche Schleifen müssen verhindert werden! Lösungen:
- Merken, welche Pakete ich bereits weitergeleitet habe, kommt so ein Paket nochmal, einfach wegwerfen. Dazu müssen die Pakete aber eindeutig unterscheidbar sein – zB mit Quellenadresse, Zieladresse und Sequenznummer. Das gibt natürlich Overhead... Auch ist es zeitaufwändig, ständig den Status jedes Paketes zu überprüfen und es braucht Speicher, um sich zu merken, welche Pakete schon da waren.
- Spanning Trees: Netzwerk als Graph aufmalen: Bridges sind die Kanten und LANs sind die die Knoten im Graph. So kann man redundante Brücken, die die Loops verursachen, finden und eliminieren, indem man ein Baumdiagramm (spanning tree) daraus macht.
Heutzutage wird zwischen Switch und Bridges nicht mehr unterschieden, fast jeder Switch verfügt über einen Uplink, der es möglich macht, ein weiteres Netzwerk anzuschließen.
Higher Layer interconnects
- Router: Wenn man außerhalb von Netzwerken kommunizieren will, reichen die einfachen, flachen Adressen der MAC-Schicht nicht mehr aus. Da muss eine komplexere Struktur her. Das machen die Router und Gateways, die im nächsten Kapitel behandelt werden. So kann man dann auch logische Netzwerke von den physikalischen Netzwerken unabhängig machen – wenn man zB ein Labor in den USA und eines in Ilmenau hat, sind das 2 physikalische Netzwerke, die über das Internet verbunden sind. Man kann nun aber aus den beiden kleinen Netzwerken ein logisches, großes Netzwerk machen, was durchaus Sinn macht.
Zusammenfassung
- einfache LANs riechen für komplexe Strukturen nicht aus
- Interconnection der LANs notwendig: Hub/Repeater auf der physikalischen Schicht, Bridges und Switches auf der Data-Link-Layer, Router auf der Netzwerkschicht und Gateways auf höheren Schichten
- Probleme: Pakete können Schleifen durchlaufen, simple Adressen skalieren nicht (komplexere Adressräume benötigt)
Network Layer
Wir wissen nun also, das wir große Netzwerke nicht einfach durch zusammenschalten kleiner LANs erreichen können, das skaliert nicht mit. Wenn wir große Netzwerke bauen, müssen wir intelligente Routenführung mit effizienten Routingtabellen (bessere Adresstruktur).
Wenn wir ein Netzwerk mit vielen Millionen Knoten haben, gibts Rountingprobleme zu lösen, die wir bis jetzt noch nicht hatten. ZB ist Flooden hier keine gute Idee, der Spanning Tree Algorithmus ist hier aber ein guter Start: Wenn wir einmal einen Ästepfad zum Ziel kennen, gehen wir den auch, wenn der Knoten tot ist, zerfällt der Baum in 2 Bäume. Es gibt dabei 2 Arten der wegewahl:
- Forwarding: Pakete einfach weiterleiten. Genauso. wie wenn ich auf Reisen gehe und nicht vorher plane wos langgeht sondern ich entscheide an jeder Kreuzung neu, wohin ich fahre.
- Routing: Route für Paket planen – und zwar intelligent. Das ist, wenn ich in Urlaub fahre, und mir vorher genau angucke, welche Straße ich nehmen muss und an welcher Abfahrt ich welche Nutte ins Auto einsteigen lasse.
Wie findet man etwas in der Routing Table? Zuerst sucht man den Hostnamen, dann die Netzwerkadresse und dann einen Default-Eintrag (welcher eine Liste von Einträgen mit gleichem next-hop zusammenfasst)
Verbindungsaufbau bei verbindungsorientierten Diensten: Bevor Daten transferiert werden können, wird eine Verbindung aufgebaut zwischen S und E – die Router dazwischen errichten einen Status für diese virtuelle Verbindung. Auf der Netzwerkschicht entsteht dabei eine Verbindung zwischen 2 Hosts, auf der Transportschicht zwischen 2 Prozessen – im Internet gibts nur letzteres (logischerweise).
Welches Protokoll kümmert sich denn nun eigentlich um den Transport der Datagramme von Sender zu Empfänger? 2 Ansätze:
- individual datagrams: Jedes Datengramm einzeln behandeln (das wird dann garantiert in zB 40 msec geliefert)
- Fluss von Datagrammen: Muss diese in Reihenfolge liefern und sich um den Zeitabstand dazwischen kümmern, Zwischenstationen brauchen Zustände dafür
Virtual Circuit vs. Datagram-Networks
- VC-Netzwerke bieten einen verbindungsorientierten Dienst auf Netzwerk-Schicht-Ebene
(beides Host-zu-Host)
VC verhält sich son bissel wie Telefongespräche – erst anrufen, E muss Anruf annehmen bevor Daten ausgetauscht werden können. Jedes Paket enthält einen VC identifier (nicht zu verwexeln mit der dest host adress). Jeder Router, der auf dem Pfad liegt, hält einen bestimmten Status für die Verbindung aufrecht, damit einer bestimmten Verbindung bestimmte Bandbreite oder bestimmte Puffergrößen zugewiesen werden können. Damit besteht ein VC aus einem Pfad von source nach dest, VC-Nummern für jeden Link auf dem Pfad und bestimmten Einträgen in der Forwarding-Tabellen der Router auf dem Pfad. Dabei wird die VC-Nummer des Pakets nach jedem Link geändert – die neue VC-Nummer kommt aus der Forwarding-Table des jeweiligen Routers. Dort werden auch die alten VC-Nummern gespeichert, somit lässt sich der Weg zurückverfolgen. Bei VC geht jedes Paket denselben Weg, nämlich den, mit dem die Verbindung eingerichtet wurde.
Beispiel für VC-Netze – ATM, X25, etc. Zeichnet sich durch einfache Endgeräte aus, das Netz dazwischen ist aber saukompliziert. die Komplexitätä steckt also im Netzwerk. Dafür gibts ein striktes Timing (Telefongespräch halt, da darf nix zu spät kommen).
- Datagrammnetzwerke bieten einen verbindungslosen Dienst auf Netzwerk-Schicht-Ebene
In Datzagramm-Netzwerken kann jedes Paket einen anderen Weg gehen – wie im Internet (nur ist es im Netz nicht soo chaotisch). Es gibt keinen Verbindungsaufbau oder sowas, keinen Status im Router, die Pakete werden einfach nach ihrer Destination Host Adress weitergeleitet.
Hier ist das Netz sehr einfach, aber die Komplexität steckt in den Endgeräten – die müssen nämlich die Unzulänglichkeiten des Netzes (kein Timing, Fehler, etc) ausbügeln
Dann mal bitte einen Blick auf 07-22 zum, Thema „Adressen in Forwarding Tabellen“ werfen, das tippsch hier nich ab, ich bin doch nich bleede!
Wie sieht so'n Router eigentlich von innen aus?
Ein Router macht hauptsächlich 2 Sachen neben dumm in der Ecke stehen und Kabel aus sich rausgucken lassen: Er betreibt ein Routing Protokoll um Daten sicher und effizient ans Ziel zu bringen und er forwarded Datagramme vom eingehenden zum ausgehenden Link. Er guckt sich an wo das datagramm hinwill, sucht den entsprechenden Eintrag in der Routing Tabelle und ab gehter der Peter (Übereinstimmungen mit Namen von lebenden Personen sind rein zufällig und nicht beabsichtigt). Wenn dabei Stau entsteht, weil der Router zuviele Pakete kriegt und sie nicht so schnell abarbeiten kann (wie Sebbl mit seiner Pornofilmsammlung) wird das Zeusch eben gequeued.
3 verschiedene Verfahren – Bilder auf 7-27:
- Switching via Memory: Das machen zB PCs, die als Router eingesetzt werden so – incoming Paket wird in den systemspeicher kopiert, ausgewertet und wieder rausgeben – Bandbreite ist eigentlich nur vom FSB des Rechner begrenzt
- Switching via Bus: Router hat nen internen Bus, den sich alle incoming Pakete teilen müssen
- Switching via Interconnection Network (crossbar): Busbandbreitenlimitation aufhaben, indem über eine Matrix geswitcht wird, so wie beim ROM-Speicher (Bild angucken)
Daten rausgeben: Zuerst mal puffern, wenn der Router die Daten schneller verarbeitet als er sie auf die Leitung geben kann. Der Buffer kann natürlich auch volllaufen (wie ne Kuh im Wasser), wenn viele Datagramme auf diesen Buffer gegeben werden, dann gibts nicht nur Delay sondern auch Verluste.
Ein lustiges Ding ist auch das Head-Of-Line Blocking – wenn ein Paket, das im Incoming-Buffer steckt, nicht mehr weiterkann, weil sein Ziel-Outgoing Buffer voll ist, können die Pakete danach auch nicht weiter, auch wenn ihre Outgoing-Buffers leer sind – wie wenn man an der Kreuzung steht, gerade aus fahren will aber vor einem steht ein Linksabbieger der den Gegenverkehr beachten muss.
IP: Internet Protocol
Das IP legt Regel fast, wie die Adressen auszusehen haben, wie das Datagramm auszusehen hat, wie mit Paketen umgegangen wird etc. Aufbau eines IP-Pakets auf 7-36. Die Time to Live bezieht sich auf die Anzahl der Hops, die das Paket machen darf – wird an jedem Router dekrementiert. Protokoll gibt an, ob TCP oder UDP oder sonstwas.
Paar Worte zur Fragmentierung: Kommt zustande wenn die Länge eines Pakets auf Link-Layer Ebene kürzer ist als die Länge eines Pakets auf Netzwer-Layer-Ebene. Gibt natürlich Overhead, weil zu allen Fragmenten jeweils ein Header mitgeschickt werden muss. Wird ein Paket fragmentiert, so gibt es einige Informationen, die benötigt werden, um es wieder zusammenzusetzen – das geschieht ausschließlich beim endgültigen Empfänger. Zuerst mal gibts ein Flag, das anzeigt, ob es fragmentiert ist, dann ein Fragment Offset, das angibt, wo das Paket im Originalframe stand und eine identification number, die verschiedene Fragmente zu einem Originalframe zuordnet. Beispiel: 7-40
- Wie adressiert IPv4?
Wir wissen, das jedes Gerät eine global eindeutige MAC-Adresse hat. Warum brauchen wir noch andere Adressen? Weil nicht jeder Router Millionen Einträge speichern und ständig durchsuchen kann. Man braucht also ein hierarchisches Schema, das die tatsächliche Struktur der Netze wiedergibt – Adressen relativ zu höheren Gruppen also zB: Subnetz1:Subnetz2_von_Subnetz1:Subnetz_3_von_Subnetz_2_von_Subnetz_1:....:Geräte-ID
Dabei sollte darauf geachtet werden, das ein Unterschied zwischen physikalischer, geographischer Nähe und logischer Nähe gemacht wird!
Angucken: IP-Adressklassen auf 7-46
Klasse A ist für große Organisationen die viele Rechner haben. Klasse C für kleine Netze mit wenig Rechnern, dafür eben viele dieser Netze. Alle können aber nur eine Level2-Hierarchie herstellen, man kann aber den Host-Bereich noch in weitere Subnetze unterteilen. Adressen mit 127.x.x.x sind loopbacks – siehe die Bitchchecker-Story ^^ Die ersten Bits von IP-Adressen werden für die Subnetze vergeben, die letzten für den Rechner an sich. Dabei kann ein Rechner mehrere NICs haben, jeder kriegt ne eigene IP. Ein Subnetz bezeichnet alle Rechner mit gleicher Subnetzadresse, die untereinander kommunizieren können, ohne den Router dafür zu beanspruchen.
Die bereits gezeigt Einteilung in Klasse A,B,C,D,E (classful adressing) sind verschwenderisch mit Adressräumen – einem Klasse B-Netz stehen zB 65.000 Hostadressen zur Verfügung, auch wenn es nur 1.000 davon nutzt – dann sind 64000 Adressen verschwendet. Daher verwendet man CIDR – Classless InterDomain Routing. Die Subnetzadresse kann hier beliebig lang gestaltet werden udn wird der IP-Adresse angehangen – zB 213.5.15.489/23 – die ersten 23 Bits stehen da für das Subnetz. Die Subnetzgrößen können sich also nur verdoppeln – 256,512,1024,...
Der ISP kauft nun einen bestimmten Adressbereich und vergeben dann aus diesem Bereich wiederum kleinere Bereiche an die Endkunden. Wie das genau aussieht schreibsch jetz nich, draußen sinds 30°C und England spielt gerade gegen Portugal im Viertelfinale. Guckt euch den Dreck gefälligst selber an – 7-56. Das Ganze erlaubt sehr effizientes Routing der Daten. so hat zB ganz Europa einen bestimmten Adressbereich – das heißt, der Router, der in den USA steht, braucht für ganz Europa nur einen Eintrag zu führen. Das Ganze überwacht die ICANN.
Der Host kriegt seine IP übrigens „hard-coded“ vom Sysadmin (Systemsteuerung > Netzwerk > TCP/IP> IP-Adresse) oder vom DHCP-Server – Dynamic Host Configuration Protocol
- NAT – Network Address Translation
Idee – ein Subnet erhält nur eine IP-Adresse nach außen hin, so braucht man keinen großen IP-Bereich vom ISP kaufen. Außerdem kann man die Adressen in seinem kleinen Netzwerk ändern, ohne das jemand von außen was davon mitkriegt – genauso kann man den ISP ändern, ohne das jedem PC sagen zu müssen. Und man kann von außen nicht direkt auf die Rechner im Subnetz zugreifen – Hackergeschützt ^^ Wie aber peilt der NAT-Router, welchem Rechner im Subnetz nun ein Paket aus dem Internet gehört? Es gibt eine NAT-Tabelle, in der jede Kombination aus (NAT IP / Port #) mit jeder (IP / Port #) drinstehen.
Geht ein Paket raus, wird dessen Quell-IP durch eine NAAT-IP ersetzt und es kriegt einen neuen Port. Kommt ein Paket rein, wird die NAT-IP durch die richtige Ziel-IP ersetzt und auch der richtige Port wieder eingesetzt. Der Router muss halt genau wissen, welche (eindeutige) Kombination aus NAT IP und Port er welchem Rechner im Subnetz zugeordnet hat. Wers nich gerallt hat: 7-63.
Da wir 16 Bit Port-Adressen haben, sind 60000 mögliche Verbindungen mit nur einer IP-Adresse möglich. NAT vergewaltigt aber so ein bissel das ganze Netzwerk-Konzept mit Ende-zu-Ende Verbindung und der Idee, das Router nur bis zur Layer 3 gehen – da lieber sollte man die IP-Adressenknappheit mit IPv6 lösen... Naja...
- ARP – Address Resolution Protocol: Wenn der Router ein Paket empfängt und die IP-Adresse keiner MAC-Adresse in seinem Netz zuordnen kann, was macht er dann? Rumschrein – Wem gehört die IP 'so-und-so'? (Senden eines Paketes mit MAC-Dest FF-FF-FF-FF-FF-FF, alle kriegen das dann). Empfänger antwortet dann mit seiner MAC-Adresse. Der Router kann Des Empfänger's MAC nun in seiner ARP-Tabelle speichern.
- Routing to Another LAN: Bsp 7-67
- ICMP – Internet Control Message Protocol: Wird von Hosts und Routern verwendet, um sich über Netzwerkspezifische Dinge zu verständigen – also zB „Dest. A nicht mehr verfügbar“ oder Einigung über Protokolle, Ports etc.
- IPv6: Da der 32 Bit Adressraum von Ipv4 bald erschöpft ist, wird der auf 128 Bit angehoben. Außerdem gibts dann 40 Byte Header, die auch die QoS verbessern sollen. Und Fragmentierung solls auch nimmer geben. Checksum wurde auch gestrichen, um Rechenzeit bei jedem Hop zu sparen. Und am ICMP wurde auch geschraubt (ICMPv6) – neu zB „Packet too big“
Da nicht das ganze Inet an einem Tag umgestellt werden kann, sondern nur Teile, werden in der Übergangszeit die IPv6 Pakete noch einen Ipv4 Header kriegen.
Routing Algorithmen
Dient dazu, den effizientesten Weg eines Pakets durch das Netzwerk zu finden.
- verbindungsorientiert: Routing Algorithmus nur beim verbindungsaufbau
- verbindungslos: entweder für jedes Paket einzeln oder die Forwarding-Tabellen der Routerwerden periodisch aufgefrischt
Dabei wird eine Metrik eingeführt – die Kosten. Das kann für die Anzahl der Hops stehen, für die €-Kosten der Benutzung der Leitung (vom ISP zB), für Delay etc. Dementsrechend ist der kürzeste Weg nicht unbedingt der mit den wenigsten Hops oder den wenigsten zurückgelegten Metern – sondern das bezieht sich auf die jeweilige Kostenmetrik.
Man unterscheidet nun 2 Typen von Routing-Algorithmen:
- nichtadaptive Routingalgorithmen: Basieren ihre Wegewahl nicht auf den aktuellen Netzwerkzustand (zB Flooding)
- adaptive Routingalgorithmen: Basieren ihre Wegewahl auf den aktuellen Netzwerkzustand (zB Distance Vector)
- Flooding: Jedes Paket wird in alle Richtungen versandt – außer in die, aus der es kam – haben dann x doppelte Pakete im Netzwerk. Die reduzieren mit:
a) Hop-Counter im Header – jedes Paket darf nur so und so viele Hops machen, wenn der Counter =0: wegschmeißen. Idelerweise ist der Hop Counter mit der Länge des optimalen Wegs initialisiert worden b) Sequenznummern vergeben – damit können Pakete, dessen Sequenznummern schonmal durch sind, weggeschmissen werden Bei militärischen Einsätzen ganz gut – Da gibts viiieeele Router und wenn einer zerstört wird, lebt das Paket noch weiter. Oder bei Ad-Hoc Netzwerken, wo die Zahl der User immer schwankt. Oder bei Updates von vielen Systemen gleichzeitig
Adaptive Routing-Algorithmen
Die nicht-adaptiven Routingalgorithmen versagen, wenn das Netz unausgeglichenen und ständig wechselnden Traffic hat. Das Netz muss sich solchen Situationen anpassen können. Dafür gibts ja die adaptiven Routingalgorithmen:
- Zentralisiert: Ein zentraler Router, dessen Routingtabelle vom Traffic abhängt. Jeder Router im Netz lässt dem zentralen Router Infos zukommen und dieser errechnet daraus die optimale Route. Diese Routen werden dann ausgetauscht.
- Isolated Adaptive Routing: basiert auf lokalen Infos des Routers, kein Austausch mit anderen Routern. Bsp: Hot Potato Routing – das Paket einfach so schnell wie möglich loswerden – also an den Ausgabeport mit der kleinsten Queue. Noch n Bsp: Backward Learning: Die Pakete beinhalten dest und source Adresse und einen Hop Counter – aus diesen Daten kann das anfänglich dumme Netzwerk Daten über seine Topologie sammeln. Am Anfang gibts zB Hot Potato. Ein Router stellt zB fest, das ein Paket mit Hop Count von 1 von seinem direkten Nachbarn kommt. Hop Count n – Source ist n Hops weit weg. So lernt das Netzwerk immer besser – muss aber auch mal periodisch alles vergessen, um tote Links zu erkennen.
- Distributed Adaptive Routing: Router tauschen sich ständig aus und passen dahingehend ihre Routingtabellen an. So kann ein Pfad mit geringen Kosten durch den Routerdschungel gefunden werden – Router kennt seine Nachbarn und Kosten dahin. Static:Routers brauchen lange für ne Änderung. Dynamic:Änderung geht ficks
Distance Vector
- iterativ: geht so lange, bis keine Knoten mehr Infos austauschen
- asynchron: Knoten müssen Infos nich immer zu bestimmter Zeit austauschen, die machen das, wennse Bock haben
- distributed: Jeder Knoten kommuniziert nur mit seinem direkten Nachbarn – nicht mit allen anderen Knoten im Netz
- jeder Knoten hat seine eigene Distance Table – Zeilen für alle Ziele, Spalten für alle direkten Nachbarn
Dazu mal das Zeug auf 7-92 ff. angucken, da kommt viel mit Formeln, das machsch jetzt nicht. Außerdem spielt gerade Frankreich-Brasilien. Das Beispiel dort reicht eigentlich, um das Prinzip des Verfahren zu verstehen. Die Tabelle ist übrigens korrekt, für den Fall das einige zweifeln. Warum steht zB für D^E(B,A) eine 7 in der Tabelle, wo man eine 8 erwarten könnte? Tja, weil die Kosten von A nach B 7 betragen (hätte man also insgesamt 8) – das ist so teuer, das man lieber wieder aussen rum geht: Also E > A >E >D >C>B = 7. Die Distance Table kann zu einer kompakteren Routingtable umgeformt werden, wenn man die uwnichtigen, teuren Wege weglässt.
Sollten sich nun die Kosten zu einem Knoten ändern, informiert dieser Knoten seine Nachbarn darüber. diese berechnen ihre Routingtabelle neu und informieren ggf. ihre Nachbarn usw. - nur informieren, wenn sich wirklich ein Weg zu einem Ziel verbilligt.
Link State Routing und Dijkstra-Algorithmus
Die Kosten zu allen Knoten sind hier jedem bekannt, jeder Router hat die gleichen Informationen durch Broadcasten. Somit kann ein Router den Weg durch das ganze Netzwerk selber berechnen – das geht mit Dijkstra:
Hierbei starte ich mit einer Initialmenge N, die ein Set von Quellknoten s enthält. Bei jedem Schritt füge ich nun einen weiteren Knoten v hinzu und berechne mit meinem wissen den kürzesten Weg dahin. Das heißt, ich guck in mein bekanntes Set von Knoten und suche aus diesem bekannten Set den Weg mit geringsten Kosten zum neuen Knoten v. Dann gehört v zu N. Jetzt muss ich nur noch die Kosten zu allen Nachbarn, die noch nicht in N drin sind, nochmal neu berechnen, denn durch den neuen Knoten könnte sich ja ein Weg verbilligt haben.
In der Routing-Tabelle steht dann für einen Knoten v zwei Einträge: d(v) (also die Kosten dahin) und p(v) (welchen Knoten muss ich zuletzt passieren, bevor ich bei v bin – predecessor)
Ist v jetzt also der neue Knoten, w ein Knoten der bereits in N ist und d(w) der bisher günstigste Weg zu w. Wenn jetzt d(v) + c(v,w) < d(w) so wird d(w) = d(v) + c(v,w). Also – wenn es günstiger ist, w über v zu erreichen, dann mach ich das auch. c(x,y) steht für die Kosten zwischen c und y. Dijkstra merkt sich ja auch immer den letzten Knoten, der auf dem Weg passiert werden muss: p(w)=v
d(v) ist also der kürzeste weg zu v – vorerst. Wenn ein neuer Knoten reinkommt, könntes dann ja einen noch kürzeren geben. Also ist d(v), so lange der Algorithmus noch nicht terminiert ist, immer eine Schätzung. Das Beispiel zu Dijkstra ist sehr hilfreich: 7-108 ff. Danach kommt ooch noch dieser illustre Korrektheitsbeweis, durchlesen kann man sich den ja mal. Dijkstra bietet eine Komplexität von O=n², was bei dichten Netzen sehr gut ist – bei weniger dicht besiedelten gibts bessere Verfahren.
Zurück zum Link State Routing: Jeder Router berechnet die Kosten zwischen sich und den angrenzenden Routern, packt diese Infos in ein Paket und flooded das durchs ganze Netzwerk (mit Sequenznummern, damit die Pakete weggeworfen werden, wenn ein Router sie bereits gesehen hat). Wenn ein Router alle Pakete aller anderen Router empfangen hat, kann er die Topologie des Netzwerks berechnen und damit auch den kürzesten Weg zu einem beliebigen Ziel X.
Der Bellman-Ford-Algorithmus: Dijkstra berechnet den kürzesten Weg nur für Kosten, die positiv sind – 0 geht auch noch. Bellman-Ford geht weiter, hier sind auch negative Kosten der Links möglich. Man muss hier nur aufpassen, das man keine Runden mit negativen Gewichten läuft, denn so sind Kosten von -Unendlich möglich – das Perpetuum Mobile hat Herr Effpunkt aber noch nicht erfunden, das kommt erst in 5 Jahren.
Bellman-Ford ist die Basis für das Distance-Vector Verfahren. Der Hauptunterschied zwischen Dijkstra und Bellman ist, das Dijkstra in jedem Schritt einen neuen Knoten hinzufügt und seine Nachbarn durchrechnet auf Kosten – die Knoten, die schon in N sind, nimmt es als optimal an und lässt sie so wie sie sind. Bei Bellman ist das anders, da werden in jedem Schritt alle Knoten durch gerechnet.
Zum Algorithmus auf 7-123, der negative cycle check: Ich teste, ob ich über u noch schneller zu v komme. das habe ich in der Schleife vorher aber auch schon getan und d(v) so angepasst, das ich über u zu v komme. Warum prüfe ich das jetzt nochmal? Naja, wenn der Weg schon über u zu v führt und ich bei der zweiten Prüfung nochmal eine Verbilligung feststellen kann, ist was faul – denn wenn ich zehnmal prüfe wirds zehnmal billiger usw – also muss hier so ein Perpetuum-mobile-Kreis vorliegen, der irgendwann in Kosten von -Unendlich endet.
Jetzt kommt noch der lustige Korrektheitsbeweis auf 7-125.
Verlgeich zwischen Distance Vector und Link State:
- Nachrichtenkomplexitiät: Bei LS müssen sich alle Router untereinander austauschen, bei DV nur die direkten Nachbarn – LS hat da also O(n*E), wobei n = Anz. Knoten, E= Anz. Kanten
- Konvergenzgeschwindigkeit: LS: O(n²) benötigt O(n*E) Nachrichten, kann oszillieren, bei DV variiert die Konvergenzzeit, es kann Routingschleifen geben und es gibt das Count-To-Infinity-Problem
- Robustheit – was passiert, wenn ein Router falsche Linkkosten propagiert?: LS: Jeder Knoten berechnet seine eigene Tabelle – der Fehler wirkt sich nur lokal aus. DV: Da jeder Knoten die Tabelle anderer Knoten nutzt, verteilt sich der Fehler über das ganze Netz.
Hierarchisches Routing
Bisher haben wir angenommen, alle Router seien gleich und das Netzwerk sei flach – is natürlich n bissel anders. Man kann nicht alle 600 Millionen Rechner in seiner Routingtabelle führen. Das Internet besteht aus vielen Netzwerken, in denen jeder Admin das Routing selber in die Hand nehmen will, vll mit verschiedenen Algorithmen. Wir fassen nun Router in verschiedenen Regionen zu Autonomen Systemen (AS) zusammen – Router im gleichen AS haben auch das gleiche Protokoll (Intra-AS), Routers in versch. AS können auch versch. Protokolle haben. Wie kommunizieren die AS untereinander? Mit sog. „Gateway-Routern“ (Inter-AS-Routing untereinander). Grafik 7-132.
Damit ist klar, das das Inter-AS Routing irgendwie durch einen Standard für alle gleich sein muss, damit alle AS im Internet kommunzieren können. Das Intra-AS kann der jeweilige Admin dann selber bestimmen, der Gateway Router „übersetzt“ ja quasi von Internet ins interne Netzwerk. So kann auch ein performantes internes Netzwerk entstehen, obwohl es nach außen hin vielleicht langsam ist (policy). Die Teilnehmer im Inneren des Netzwerkes müssen nicht alle Adressen des Internets kennen, die müssen nur wissen, über welchen Gateway-Router sie wohin im Netz gelangen können – die Forwarding Tables werden daher auch schön klein. Das ist genauso wie wenn ich von Ilmenau nach München will – ich muss nicht wissen, wie ich genau da hinkomme, es reicht mir, wenn ich weiß welche Straße ich aus Ilmenau raus nehmen muss. Das setzt natürlich voraus, das die Gateway Router in ihrem kleinen Netzwerk propagieren, welche anderen AS sie erreichen. Daher haben auch die internen Router, die keine direkte Verbindung zum Netz haben, sowohl Intra-AS-Protokoll als auch Inter-AS-Protokoll haben müssen – sie wissen vom Inter-AS welchen Gateway sie nach draußen nehmen sollen und über Intra-AS wie sie am günstigsten zu diesem Gateway kommen.
Man klassifiziert die AS nun an Hand der Anzahl ihrer Gateway-Router, die das AS mit dem Internet verbinden – ein kleines Firmennetzwerk hat zB nur einen Uplink zum Netz, ein etwas größeres hat vielleicht 2. Dieses etwas größere könnte dann routen, dh es könnte Verbindungen weiterleiten – will das aber nicht. Bsp Gartentür: Ich hab 2 Gartentüren, meine Nachbarn könnten dann meinen Garten als Durchgang benutzen – das willsch aber nicht. Die, die das wollen, sind die ISPs, die haben viele Uplinks zum Netz, die kriegen dann aber auch Geld dafür – das nennt sich dann Transit AS.
Routing im Internet
In den Intra-AS spielen 3 Routingverfahren eine Rolle:
- Routing Information Protocol (RIP) – Distance Vector
- Open Shortest Path First (OSPF) – Link State
- proprietäres Cisco-Ding: Interior Gateway Routing Protocol (IGRP)
Im Inter-AS hat man sich weltweit auf das Border Gateway Protocol (BGP) geeinigt.
RIP:
Distanzvektorverfahren mit Metrik = Anzahl der hops (maximal 15). Alle Router senden aller 30 Sekunden Nachrichten (adveristments, UDP-Pakete) zu ihren Nachbarn und teilen mit, wohin sie routen können – das ist eigentlich nicht nötig, es würde reichen was zu sagen, wenn sich was geändert hat - aber so merkt man, wenn ein Router stirbt. Bsp: 7-143. Wenn man 180 s nix mehr hört von nem Router, wird er für tot erklärt. Das schickt man in nem Ad weiter, die anderen Router berechnen ihre Tabellen neu und schicken ggf, wenn sich was geändert hat, auch wieder Ads weiter. So verbreiten sich tote Links sehr schnell im Netzwerk.
OSPF:
Link State – dh, alle Router kennen die Topologie des Netzwerks und verwenden Dijkstra zum Berechnen des besten Wegs. Die Adveritsments werden an alle gefloodet, es sind IP-Pakete (also unter TCP/UDP). Es sind viele Pfade mit gleichen Kosten erlaubt, RIP kann immer nur einen. Außerdem kann OSPF auch Kosten an den Links verwalten, das kann RIP ooch nich.
Das hierarchische OSPF ist kompliziert aufgebaut, mit verschiedenen Routertypen – zB gibts da Area Border Routers, die alle Infos aus ihrem Gebiet sammeln und an andere Area Border Routers weitergeben. Oder die Boundary Routers, die verschiedene AS miteinander verbinden.
BGP':
Wenden wir uns dem Inter-AS Protokoll zu. Das ist der Standard im Internet. BGP vermittelt jedem AS, welche Rechner/Subnetze es in anderen AS erreichen kann. Das muss dann jeder Router in so einem AS wissen. Somit kann erst ein Subnetz seine Existenz ins Internet hinausschreien - „Hallo, hier bin ich! Hiiieeer! Hier unten!!!“ Außerdem errechnet BGP noch, welche Wege denn nun kostengünstig sind.
Also unterhalten sich die Gateway Router (stellvertretend für ihre AS) über BGP-Sessions (TCP-basiert) und tauschen Informationen aus. Wenn ein AS sagt - „Über mich erreichst du Sebbl“, verpflichten sich das AS, alles, was zu Sebbl geht, anzunehmen – (in diesem Beispiel kann das AS Urlaub nehmen ^^).
Man unterscheidet da zwischen internen und externen BGP-Sitzungen – intern erzählt der Gateway eigenen AS, was durch ihn erreicht wird ('Hier Kinners, wenn ihr nach London telefonieren wollt, dann über mich') und extern heißt, zwei Gateways tauschen sich aus – zB kann ein Gateway einem anderen sagen, das er Verbidnugnen weiterroutet ('ich hab hier nen heißen Draht nach Paris, wenn du willst, kann ich alle Anfragen aus deinem AS über mein AS nach Paris weiterleiten, das kostet aber). BSP: 7-155.
In so einem BGP-Paket steht der prefix drin (Adresse) und die Route dahin – also durch welche AS geht es und man gibt den nächsten Router im AS an. Also wenn ich durch AS67, AS17 und dann zu AS30 will, muss ich wissen, an welchen Router in AS67 ich mich wenden soll.
Ein Router muss so ein Ad nicht annehmen, wenn er nicht will – das kommt auf die policy an – will ich mit meinem AS routen oder nicht, will ich, das Leute durch meinen Garten trampeln (7-159)? Genauso muss ich auch nicht werben – wenn ich ISP bin muss ich Leuten, die nicht meine Kunden sind, auch nicht sagen, wohin ich routen könnte. Ein Router kann auch mehrere verfügbare Routen mitgeteilt bekommen – dann muss er sich entscheiden – wo kostets am wenigsten, wie weit ist der next-hop entfernt, womöglich hot potato.
Zusammenfassung
- Welche Dienste muss das Netzwrk bieten?
- Wie siehts in einem Router aus
- Herr Jäger müffelt immer noch [Anm. von Herrn J.: "Deine Oma....."]
- Ipv4, IPv6
- Routing in großen Netzwerken ist allein mit guten Routingalgorithmen nicht zu machen, wir brauchen dazu noch hierarchisches Routing
- Internet Routingprotkolle – RIP, OSPF, BGP
- Netzwerkstruktur muss auf die Adressenstruktur projiziert werden, sonst gibts zuviel Overhead (Adressraumvereschwendung)
Klausur
Anmeldung
Zusätzlich zur Anmeldung an der Fak, muss noch eine eMail an die Klausurveranstalter geschickt werden. Zwecks Mateial- und Raumplanung. Nähere Infos gibts hier.
Material
Es darf nichts verwendet werden. Kein Script, keine Bücher, keine Aufzeichnungen.