Das Kefk Network Wiki befindet sich im Testbetrieb.
Carrier Sense Multiple Access/Collision Detection
Aus Kefk.
Der englische Begriff Carrier Sense Multiple Access/Collision Detection (CSMA/CD) (zu 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.
Inhaltsverzeichnis |
Kollisionen
Siehe auch: Kollisionsdomäne.
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).
Netzwerkausdehnung und Kollisionserkennung durch den Sender
Eine Kollision muss insbesondere vom Sender erkannt werden, damit er eine Sendewiederholung initiieren kann. Daher darf ein Netzwerk nur eine begrenzte Ausdehnung haben, eine maximale RoundTripDelayTime (RTDT) darf nicht überschritten werden. Die RTDT ist die Zeit die ein Netzwerkpaket benötigt um vom einen Ende des Netzes zum weitestentfernten anderen Ende der Netzes zu gelangen - und wieder zurück. Damit Kollisionen erkennbar sind, 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“), die minimale Paketlänge, bzw. die Sendedauer für ein Paket minimaler Länge, muss also stets größer sein als die maximal zulässige RoundTripDelayTime. Sollen „zu kurze“ Daten-Pakete übertragen werden, müssen diese dazu nötigenfalls auf eine zulässige minimale Paketlänge verlängert werden. Wären die Pakete zu klein, was die gleiche Wirkung wie ein zu großes Netz (zu hohe RTDT) hätte, würden vom Sender unerkannte Kollisionen möglich werden und der gesamte Netzverkehr beeinträchtigt sein. Solche Störungen sind hinterlistig, da Übertragungen bei niederer Netzlast oder auch bei bestimmten Paketgrößen normal funktionieren können. Da Repeater und Hubs in die RTDT mit eingehen, aber keine wirklich fassbare Ausdehnung, wohl aber messbare Verzögerungszeiten haben, ist es hier praktischer von Zeiten als von Paketlängen zu sprechen.
Beispiel
In einem Netz maximaler Ausdehnung (~maximale RoundTripDelayTime) sind Station Alpha und Omega die beiden am weitesten auseinanderliegenden Stationen. Das Medium ist frei und Alpha beginnt mit der Übertragung. Bis Omega bemerkt, dass Alpha sendet, dauert es genau eine halbe RoundTripDelayTime - die Zeit die die Pakete/Signale von Alpha brauchen um bis zur Station Omega zu gelangen. Hat nun Omega auch etwas zu übertragen und unmittelbar vor dem Eintreffen der Pakete von Alpha mit dem Senden begonnen - als aus Sicht von Omega die Leitung ja noch frei war - kommt es zunächst bei Omega zur Kollision, Omega bemerkt die Störung seiner Aussendung und kann entsprechend reagieren. Bis jetzt auch Alpha die Kollision bemerkt, dauert es noch mindestens eine weitere halbe RTDT - die Zeit die die Signale von Omega brauchen um bis zur Station Alpha zu gelangen. Damit Alpha die Kollision bemerkt und eine Sendewiederholung initiieren kann, muss Alpha also noch solange weiter am Senden sein, bis die Pakete von Omega eingetroffen sind. Zusätzlich müssen alle Stationen die die Pakete von Alpha empfangen haben noch rechtzeitig über die Kollision informiert werden. Die minimale Sendedauer (~ minimale Paketgröße) muss also stets größer als die RTDT (~ doppelte Ausdehnung des Netzes) sein.
Das Backoff-Verfahren bei Ethernet
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 [0;(2i) − 1], wobei i für die Anzahl der bereits aufgetretenen Konflikte steht. Die Sendestation wartet nun den Zeitraum von z * slot time (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 der auftretenden Kollisionen ist es nicht möglich, die theoretische Übertragungskapazität eines Mediums voll auszuschöpfen. In der Praxis kann man davon ausgehen, dass sich im günstigsten Fall etwa 70% der Nominalleistung erzielen lassen, unter ungünstigeren Bedingung sind es unter 30%. Die Ursache ist einfach: Je mehr Rechner sich im Netzwerk beteiligen und je höher die Auslastung steigt, desto mehr Kollisionen treten auf, folglich sinkt der reell erzielte Datendurchsatz deutlich ab.
Nutzen nur zwei Stationen dasselbe Übertragungsmedium, schafft der Duplex-Betrieb Abhilfe. Bei Ethernet kann das Medium mittels Switch oder Bridge in mehrere Kollisionsdomänen aufgeteilt werden. Dann können pro Segment oder Kollosionsdomäne zwei Knoten (Stationen) im Duplex-Betrieb aktiv sein, ohne dass es zu Kollisionen kommt.
Auch gibt es gänzlich kollisionsfreie Übertragungsprinzipien wie das Token Passing, es kommt z.B. bei ARCNET oder Token Ring zum Einsatz.
Siehe auch
Weblinks
- IEEE 802.3 IEEE 802.3 CSMA/CD (ETHERNET)
 | Dieses Dokument entstammt in seiner ersten oder einer späteren Version der deutschsprachigen Wikipedia. Es ist dort zu finden unter dem Stichwort Carrier_Sense_Multiple_Access/Collision_Detection, die Liste der bisherigen Autoren befindet sich in der Versionsliste; die Originalfassung kann dort auch bearbeitet werden. Alle Texte der Wikipedia und ihre Derivate stehen unter der GNU-Lizenz für freie Dokumentation. |
