Kollisionserkennung (Kommunikationstechnik)

Dieser Artikel wurde aufgrund von inhaltlichen Mängeln auf der Qualitätssicherungsseite der Redaktion Informatik eingetragen. Dies geschieht, um die Qualität der Artikel aus dem Themengebiet Informatik auf ein akzeptables Niveau zu bringen. Hilf mit, die inhaltlichen Mängel dieses Artikels zu beseitigen und beteilige dich an der Diskussion! (+)
Begründung: Das Beispiel nach "Netzwerkausdehnung und Kollisionerkennung durch den Sender" scheint nicht ganz plausibel. Im ersten Satz steht "In einem Netz maximaler Ausdehnung (~maximale RoundTripDelayTime)" und im letzten Satz steht "größer sein als die RTDT (~ doppelte Ausdehnung des Netzes)". Also die RTDT ist die Zeit, die die Nachricht von einem Knoten bis zum am weitesten entferntesten Knoten benötigt und wieder zurück - also doppelte Ausdehnung des Netzes. In den beiden zitierten Textteilen scheint mir eine Inkonsistenz zu sein. Des Weiteren: Da eine Nachricht von einem Knoten bis zum am weitesten entferntesten Knoten benötigt (halbe RTDT) kann es nicht sein, dass eine Nachricht "noch mindestens eine weitere halbe RTDT – die Zeit, welche die Signale von Omega [zu Alpha] brauchen". Es kann sich hierbei nur um maximal eine weitere halbe RTDT handeln. Wäre es mehr als eine halbe RTDT, hätte Omega die Nachricht bereits erhalten. Das hat zur Folge, dass Omega nicht sendet und somit keine Kollision verursacht.

Der englische Begriff Carrier Sense Multiple Access/Collision Detection (CSMA/CD) (zu Deutsch etwa: „Mehrfachzugriff mit Trägerprüfung und Kollisionserkennung“) bezeichnet ein Medienzugriffsverfahren, das den Zugriff verschiedener Stationen auf ein gemeinsames Übertragungsmedium regelt. Es handelt sich um eine Erweiterung von CSMA. Verwendung findet CSMA/CD beispielsweise im Bereich der Computernetze beim Ethernet und ist dort als IEEE 802.3 standardisiert worden. Bei Wireless LANs wird ein ähnlicher Mechanismus namens Carrier Sense Multiple Access/Collision Avoidance (CSMA/CA) benutzt. Der im Automobilbereich verwendeten CAN-Bus verwendet einen Mechanismus namens Carrier Sense Multiple Access/Collision Resolution (CSMA/CR).

Kollisionen

Siehe auch: Kollisionsdomäne.

Bei Netzübertragungsverfahren wie Ethernet findet eine paketorientierte Datenübertragung in Datagrammen (Datenframes) auf einem gemeinsam genutzten Medium (Funk, Kabel), oder genauer innerhalb einer gemeinsamen Kollisionsdomäne statt. Es wird also weder ein endloser Datenstrom erzeugt noch werden Zugriffe auf das Medium anderweitig deterministisch gesteuert. Daher ist es möglich, dass mehrere Stationen dasselbe Medium (z. B. Koaxialkabel) zeitgleich verwenden wollen. Hierdurch können dann Kollisionen entstehen, welche die übertragenen Signale unbrauchbar machen. Um dies wirkungsvoll zu unterbinden, wird das CSMA/CD-Verfahren eingesetzt. Aufgabe des CSMA/CD-Verfahrens ist es, auftretende Kollisionen aufzuspüren, zu reagieren und zu verhindern, dass sich diese wiederholen.

Das Verfahren ist, verglichen mit Token-Passing-Verfahren (z. B. Token Ring) oder Master-kontrollierten Netzen (z. B. ISDN), relativ einfach, was auch entscheidend zu seiner Verbreitung beigetragen hat. Modernere Ethernetverfahren (z. B. Fast Ethernet) umgehen die Kollisionsbildung ebenfalls. Kollisionen werden dort beispielsweise durch den Einsatz von gepufferten aktiven Verteilern (Switch) in geswitchten Umgebungen ebenfalls wirkungsvoll verhindert.

Realisierung

Wenn ein Gerät Daten senden möchte, hält es sich an folgenden Ablauf:

1. Horchen: Zuerst muss das Medium überwacht werden, ob es belegt ist.

→ Frei: Wenn das Medium eine bestimmte Zeit lang (IFS) frei ist, weiter mit Schritt 2.

→ Belegt: Weiter mit Schritt 3.

2. Senden: Informationsübertragung, zugleich wird das Medium fortwährend weiter abgehört.

→ Erfolg: Übertragung wird erfolgreich abgeschlossen und eine Erfolgsmeldung an höhere Netzwerkschichten gemeldet, weiter mit Schritt 5.

→ Kollision: Wird eine Kollision entdeckt, 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 3.

3. Leitung ist belegt: Überprüfung der Anzahl der Übertragungsversuche:

→ Maximum nicht erreicht: Eine zufällige Zeit (Backoff, s.u.) abwarten, dann wieder bei Schritt 1 beginnen.

→ Maximum erreicht: Weiter mit Schritt 4.

4. Fehler: Maximale Anzahl von Übertragungsversuchen wurde überschritten. Ein Fehler wird an die höheren Netzwerkschichten gemeldet, weiter mit Schritt 5.

5. Ende: Übertragungsmodus verlassen

Physische Kollisionserkennung

Da die Signale als Spannungspegel messbar sind und da 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 Netz nur eine begrenzte Ausdehnung haben, eine maximale RoundTripDelayTime (RTDT) darf nicht überschritten werden. Die RTDT ist die Zeit, die ein Datenpaket benötigt, um vom einen Ende des Netzes zum weitestentfernten anderen Ende des 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, könnte es zu vom Sender unerkannten Kollisionen kommen, und der gesamte Netzverkehr könnte beeinträchtigt werden. Solche Störungen sind tückisch, da Übertragungen bei niederer Netzlast oder auch bei bestimmten Paketgrößen normal funktionieren können. Da Repeater und Hubs in die RTDT eingehen, jedoch keine wirklich fassbare Ausdehnung, wenn auch eine messbare Verzögerungszeiten haben, ist es praktikabler, 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, welche 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, welche 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. Außerdem müssen alle Stationen, die die Pakete von Alpha empfangen haben, rechtzeitig über die Kollision informiert werden. Die minimale Sendedauer (~ minimale Paketgröße) muss also stets größer sein als die RTDT (~ doppelte Ausdehnung des Netzes).

Das Backoff-Verfahren bei Ethernet

Funktionsdarstellung in einem Programmablaufplan

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;(2ⁱ) − 1] (das sog. Contention Window), 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 Bedingungen 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 Kollisionsdomä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.

Weblinks

• IEEE 802.3 IEEE 802.3 CSMA/CD (ETHERNET)