Fehler in Rechnernetzen

IFB Speyer

Daniel Jonietz

2006

dj2

Worum gehts?

Es können verschiedene Fehler auftreten:– Pakete werden bei Übertragung geändert– Pakete gehen komplett verloren– Pakete werden in einer zeitlich anderen Reihenfolge

übertragen– Pakete werden dupliziert

dj3

Paketänderungen

Was möchte man?– Mindestens:

Feststellen, dass ein Fehler vorliegtParitätsbits, Prüfsummen, CRC

– Schön wäre aber auch: Fehler reparieren Hamming-Code, vgl. Skript WBL

dj4

Motivation

dj5

Welche Bitfehler gibt es?

Einzelbitfehler– Ein Bit ist „gekippt“, d.h. falsch

Doppelbitfehler– Zwei aufeinanderfolgende Bits sind gekippt

Fehlerbündel – N aufeinanderfolgende Bits sind falsch

dj6

Wie stellt man Paketänderungen fest?

Grundsätzlicher Lösungsansatz: Einführen von Redundanz– Paritätsbit– Prüfsummen– Redundanzcodes– Hammingcodes

Rahmenformat muss geändert werden neue Vereinbarung (Protokoll) nötig

dj7

Allgemeiner Ansatz

Sender– wendet Algorithmus auf zu sendende Daten an, dieser

liefert die Prüfbits– versendet Nutzdaten und Prüfbits

Empfänger– trennt Daten und Prüfbits voneinander– wendet gleichen Algorithmus auf die Nutzdaten an– vergleicht gesendete Prüfbits mit den selbst ermittelten

dj8

Paritätsbits

Idee: Ein zusätzliches Bit gibt an, wie viele Bits 1 sind

Varianten:– Gerade Parität (Anzahl 1 gerade Parität 0)

das PB wird so gesetzt, dass Anzahl 1er gerade– Ungerade Parität (Anzahl 1 ungerade Parität 0)

Erfolg:– Es werden nur „ungeradzahlige Bitkipper“ detektiert

dj9

Prüfsummen

Verschiedene Varianten– Z.B. einfache „Summe“ modulo 100:– Zwei Prüfstellen, der Einfachheit halber betrachten wir

Dezimale– 06 23 04 33 (06+23+04=33)– Was taugt dieses Verfahren?– 08 20 05 33 (08+20+08=33) !!!

dj10

Zyklische Redundanzcodes (CRC)

dj11

CRC - Details

Bitfolgen werden als Polynome aufgefasst Berechnungen erfolgen ohne Berücksichtigung

möglicher Überträge Sender und Empfänger einigen sich auf ein

Generator-Polynom Prüfbits = Rest der Division Daten / GP Gibt normierte Polynome, z.B. CRC-4

dj12

CRC - Leistungsfähigkeit

Beispiel CRC-CCITT G=x16+x12+x5+1– Entdeckt alle Einzelbitfehler, alle Doppelbitfehler, alle

Bitfehler mit ungerader Bitanzahl, alle Fehlerbündel bis zu 16 Bit Länge

– Entdeckt 99,997% aller 17-Bit-Fehlerbündel– Entdeckt 99,998% aller Fehlerbündel mit 18 oder mehr

Bits

dj13

Woher kommt das CRC-Polynom?

„Choosing a poly is somewhat of a black art“ (Ross N. Williams: “A painless guide to crc error detection algorithms”)

Viel Mathematik

dj14

Polynom-Beispiele

CRC-16– (16,15,2,0)

Ethernet– (32,26,23,22,16,12,11,10,8,7,5,4,2,1,0)

dj15

Paketverlust: Ursachen

Problem: Pakete können verloren gehen– Grenzfall: „lange“ Übertragungsdauer

Ursachen:– Empfänger verwirft Paket, weil er einen Fehler feststellt– Empfänger ist nicht in der Lage Paket zu empfangen– Netzwerk verliert das Paket

oder leitet es falsch weiter

dj16

Paketverlust: Abhilfe

Quittungsbetrieb– Empfänger sendet nach Erhalt eines Paketes ein

Quittungspaket an Sender und bestätigt damit den Erhalt des Pakets

– Ist das empfangene Paket offensichtlich fehlerhaft, sendet er eine „negative“ Quittung und fordert damit das Paket neu an

– Bleibt die Quittung beim Sender aus, so sendet er von sich aus nach einer gewissen Zeit das Paket erneut

dj17

Folgerung aus Quittungsbetrieb

Sender– Muss auch empfangen können

Empfänger– Muss auch senden können

dj18

Datenfluss

Simplex– A kann nur senden, B nur empfangen

Halbduplex– A und B können senden und empfangen, aber nie

gleichzeitig

(Voll-)Duplex– A und B können senden und empfangen, sogar

gleichzeitig

dj19

Geänderte Paket-Reihenfolge

Idee: Sequenznummern– Sender nummeriert die versendeten Pakete durch– Empfänger ist dann anhand der Nummern in der Lage,

die Reihenfolge wieder herzustellen

dj20

Duplikate von Paketen

Ursache:– Z.B. „langsames“ Paket: Sender sendet nach Timeout

ein Paket erneut

Idee: Sequenznummern– Zwei aufeinander folgende Pakete mit der gleichen

Sequenznummer dürften nicht auftreten– Duplikat kann gelöscht (verworfen) werden

dj21

Send and Wait - Protokoll

(auch: Stop and Wait-Protokoll) Sender

– Sendet Paket– Wartet auf Quittung

Empfänger– Empfängt Paket– Prüft, ob er Fehler feststellen kann– Sendet entsprechend negative / positive Quittung

dj22

Weitere Probleme …

Die Quittung geht (wiederholt) verloren– Z.B. wenn Empfänger grundsätzlich nicht senden kann– Sender würde endlos lange versuchen, das Paket zu übertragen

Lösung:– Hat der Sender N-mal versucht ein bestimmtes Paket zu senden gibt

er auf.

Anderer Ansatz: Mittels 3-Wege-Handshake die Quittung bestätigen