Carrier Sense Multiple Access / Collision Detection

Der englische Begriff Carrier Sense Multiple Access/Collision Detection (CSMA/CD) (deutsch etwa: „Mehrfachzugang mit Trägerprüfung und Kollisionserkennung“) bezeichnet ein Medienzugriffsverfahren, das den Zugriff verschiedener Stationen auf ein gemeinsames Übertragungsmedium im Zeitmultiplexverfahren (TDMA) beschreibt. Verwendung findet CSMA/CD beispielsweise im Bereich der Computernetzwerke beim Ethernet und ist dort als IEEE 802.3 standardisiert worden. Bei Wireless LANs oder dem im Automobilbereich verwendeten CAN-Bus wird ein ähnlicher Mechanismus namens CSMA/CA benutzt.

Kollisionen

Bei Netzwerkverfahren wie Ethernet findet eine Datenübertragung in Datagrammen (Datenframes) statt. Es wird kein endloser Datenstrom erzeugt. So wird es einerseits möglich, dass mehrere Stationen dasselbe Medium (z.B. Kabel) verwenden, andererseits entsteht dadurch die Gefahr von Kollisionen:

Da es nicht vorherbestimmt ist, zu welchem Zeitpunkt eine Station zu senden hat, kann es geschehen, dass mehrere Sendestationen zum selben Zeitpunkt senden möchten, wodurch sich die beiden Signale überlagern und somit stören: Keine der Stationen kann etwas Brauchbares senden. CSMA/CD ist ein Verfahren, um auf auftretende Kollisionen zu reagieren und zu verhindern, dass sie sich wiederholen.

Realisierung

Das Schema ist, verglichen mit Token Ring oder Master-kontrollierten Netzwerken, relativ simpel. Wenn ein Gerät Daten senden möchte, hält es sich an folgenden Ablauf:

Carrier Sense = auf Signal horchen: Zuerst muss das Medium überwacht werden.
Wenn das Medium eine bestimmte Zeit lang (IFS) frei ist, beginne mit der Übertragung, andernfalls weiter mit Schritt 5.
Informationsübertragung, zugleich wird das Medium fortwährend weiter abgehört. Wenn hierbei eine Kollision entdeckt wird, beende die Datenübertragung und setze ein definiertes Störsignal (jam) auf die Leitung (um sicherzustellen, dass alle anderen Transceiver die Kollision ebenfalls erkennen), dann weiter mit Schritt 5.
Übertragung erfolgreich abgeschlossen: Erfolgsmeldung an höhere Netzwerkschichten, Übertragungsmodus verlassen.
Leitung ist belegt: Warten, bis die Leitung wieder frei ist.
Leitung ist gerade frei geworden. Noch eine zufällige Zeit (Backoff, s.u.) abwarten, dann wieder bei Schritt 1 beginnen, wenn die maximale Anzahl von Übertragungsversuchen nicht überschritten wurde.
Maximale Anzahl von Übertragungsversuchen überschritten: Fehler an höhere Netzwerkschichten melden, Übertragungsmodus verlassen.

Da die Signale als Spannungspegel messbar sind, und eine Überlagerung eine Addition der Pegel bedeutet, wird eine Kollision von allen (auch den momentan unbeteiligten) Rechnern erkannt, da ein Schwellwert der Gleichspannungsanteile überschritten wird (Collision Detection = Kollisionserkennung). Die Kollision muss insbesondere vom Sender erkannt werden, damit er eine Sendewiederholung initiieren kann. Dazu muss die minimale Paketlänge so bemessen werden, dass die Übertragungsdauer ("slot time") ausreicht, um das Signal zweimal über die längste Distanz zu übertragen (so genanntes "propagation delay"). Sollen "zu kurze" Daten übertragen werden, müssen sie dazu nötigenfalls auf die minimale Paketlänge verlängert werden.

Das Backoff-Verfahren bei Ethernet

CSMA-CDxx.gif Muss die Übertragung wegen eines Konflikts abgebrochen werden, so käme es unmittelbar zu einem erneuten Konflikt, wenn die beteiligten Sendestationen sofort nach dem Abbruch erneut senden würden. Sie müssen daher im Idealfall eine unterschiedlich lange Pause einlegen, sodass die Stationen eine Sendereihenfolge zugeordnet bekommen.

Bei Ethernet wählen die Konfliktparteien hierzu eine zufällige ganze Zahl z aus dem Intervall $(2^i)-1$ , wobei i für die Anzahl der bereits aufgetretenen Konflikte steht. Die Sendestation wartet nun den Zeitraum von z * slot delay (s.o.) ab und sendet danach erneut, falls das Medium frei ist. Hat keine andere Station dasselbe z gezogen, gibt es also keinen Konflikt mehr.

Da die Streuung der möglichen Wartezeiten exponentiell mit der Anzahl der aufgetretenen Konflikte wächst, ist die Wahrscheinlichkeit sehr gering, dass viele Konflikte hintereinander auftreten, da die Konfliktparteien hierzu regelmäßig dieselbe Zufallszahl ziehen müssten. Daher wird nach 16 Konflikten in Folge der Sendeversuch abgebrochen und ein Systemfehler angenommen.

Der Nachteil der Methode ist, dass rechnerisch keinerlei Garantie herrscht, dass ein Paket zu einem bestimmten Zeitpunkt bereits angekommen ist. Der Übertragungserfolg hat lediglich eine gewisse Wahrscheinlichkeit. Das Verfahren ist also nicht echtzeitfähig, wie es etwa bei Token Ring der Fall ist.

Kollisionen verhindern

Aufgrund dieser auftretenden Kollisionen ist es nicht möglich, die theoretische Übertragungskapazität voll auszuschöpfen. Je mehr Rechner sich im Netzwerk beteiligen, desto mehr Kollisionen treten auf und der Datendurchsatz sinkt somit deutlich.

Nutzen nur zwei Stationen dasselbe Übertragungsmedium, schafft der Duplex-Betrieb Abhilfe. Bei manchen Übertragungsmethoden kann das Medium mittels eines Switches oder einer Brücke in mehrere Kollisionsdomänen aufgeteilt werden. Dann können mehrere Stationen im Duplex-Betrieb aktiv sein, sofern der Switch die jeweiligen MAC-Adressen in seiner Adressliste gespeichert hat.

Auch gibt es gänzlich kollisionsfreie Übertragungsprinzipien wie Token Passing.

Siehe auch

Weblinks

IEEE 802.3 IEEE 802.3 CSMA/CD (ETHERNET)