Carrier Sense Multiple Access/Collision Avoidance

Der englische Begriff Carrier Sense Multiple Access/Collision Avoidance (CSMA/CA) (Mehrfachzugriff mit Trägerprüfung und Kollisionsvermeidung) bezeichnet ein Prinzip für die Kollisionsvermeidung bei Zugriff mehrerer Netzwerkstationen auf denselben Übertragungskanal. Es wird häufig unter anderem bei drahtlosen Netzwerken (Wireless LANs) eingesetzt, findet aber abgewandelt auch bei Kommunikationsverfahren wie ISDN Anwendung, oder in vielen Kommunikationsnetzen, bei denen mehrere Clients Daten auf einen Bus legen und es nicht zu Kollisionen kommen darf. In zentral koordinierten Kommunikationsnetzen tritt das Problem nicht auf.

Motivation für CSMA/CA in Funknetzen

Drahtlose Netze unterscheiden sich in Bezug auf den gemeinsamen Medienzugriff durch zwei wichtige Faktoren von drahtgebundenen Netzen:

• Der Netzadapter ist nicht notwendigerweise Voll-Duplex-fähig. Während einer eigenen Übertragung kann das Medium nicht überwacht werden. Der Einsatz eines „Collision Detection“-Mechanismus, wie er etwa von CSMA/CD vorgesehen ist und bei Ethernet verwendet wird, würde dann fehlschlagen. Deswegen wurde CSMA/CD zu einem Mechanismus weiterentwickelt, der konsequenter dem Prinzip „listen before talk“ („erst hören, dann sprechen“) folgt. An die Stelle der Kollisionserkennung („CD - Collision Detection“) sollte die (bestmögliche) Kollisionsvermeidung („CA - Collision Avoidance“) treten. Dadurch lassen sich gleichzeitige Datenübertragungen zwar nicht völlig verhindern, aber doch minimieren.

• Die Reichweite des Signals ist stark begrenzt, da der Empfangspegel quadratisch mit der Entfernung abnimmt. Deshalb kann es zu Effekten wie „versteckten“ oder „exponierten“ Endgeräten kommen.

Hidden-Station-Problem

Eine Hidden Station oder ein Hidden Terminal (engl. „verstecktes Endgerät“) bezeichnet in asynchronen und nicht zentral koordinierten Kommunikationsnetzen, Funknetzen oder Rechnernetzen den unerwünschten Umstand, dass bei einer Übertragung zwischen zwei Teilnehmern (A und B) ein weiterer potentieller Sender (C, das Hidden Terminal) in der Nähe des Empfängers (B) ist, der vom eigentlichen Sender (A) nicht gesehen werden kann (sehen bedeutet hier durch Carrier Sense erkannt werden). Dieser potentielle Sender (C) kann die Kommunikation der anderen beiden Knoten (A und B) stören, indem er ebenfalls eine Nachricht an den Knoten in der Mitte (B) sendet, dies kann zu einer Kollision an dem Empfänger (B) führen.

Hidden Station in Funknetzen

Die Abbildung stellt die typische Situation des Hidden-Station-Problems in Funknetzen mit nur einem Modulationsverfahren auf einer Funkfrequenz dar. Netzwerkknoten A sendet Daten an Knoten B. Das Signal erreicht B, wegen der begrenzten Reichweite der Funkverbindung aber den weiter entfernt liegenden Knoten C nicht. C bekommt also von dem laufenden Datenaustausch nichts mit und gewinnt den Eindruck, das Kommunikationsmedium sei frei, um Daten an Knoten B zu senden. Beginnt nun auch C mit dem Senden, so überlagern sich die Signale bei B. Das Ergebnis ist eine Datenkollision, aufgrund der B weder die Nachrichten von A noch von C erfolgreich empfängt.

Spezielle Verfahren können diese Kollision nicht ausschließen, aber sie schaffen mit stochastischen Verfahren ein deterministisches Verhalten der beteiligten Teilnehmer. Durch die Verwendung von RTS/CTS wird versucht das Hidden-Station-Problem zu vermeiden. Wenn B auf einen Request-to-send von A mit einem Clear-to-send antwortet, hört C dies mit und wartet für die Zeit der Übertragung zwischen A und B. Dies kann das Problem aber nicht vollständig verhindern.

Exposed-Station-Problem

Unter einer Exposed Station oder einem Exposed Terminal (zu deutsch: exponiertes Endgerät) versteht man, wenn in unserem vorliegenden Szenario die Station B an A sendet und nun C an irgendeine andere Station senden möchte, die nicht im Sendebereich von B liegt. C erkennt die Signale von B und wartet, bis die Übertragung zwischen B und A vorbei ist. Da die Funkwellen von C aber Station A gar nicht erreichen können, wäre es gar nicht nötig zu warten: bei A könnte gar kein Konflikt auftreten. Dennoch ist C von der Sendung der anderen beiden Stationen abhängig (ausgeliefert). Durch das unnötige Warten wird Bandbreite verschwendet.

Kommen allerdings, wie bei Unicast-Übertragungen üblich, Acknowledements (ACKs) zur Bestätigung des korrekten Empfangs zum Einsatz, dann wird der Empfänger der Nachricht nach dem Empfang der Nachricht zum Sender eines ACKs. Damit der ursprüngliche Sender der Nachricht dieses ACK empfangen kann, müssen auch Stationen warten, die in seiner Reichweite sind. Im Beispiel würde A die Übertragung von B durch ein ACK bestätigen. Würde nun C zeitgleich senden, könnte es bei B zu einer Kollision des ACKs von A und der von C gesendeten Nachricht kommen.

Protokollablauf

Möchte ein Gerät Daten nach dem CSMA/CA-Verfahren versenden, so ist unter anderem folgender Ablauf möglich:

1. Zuerst wird das Medium abgehört („horcht“, „Carrier Sense“).
2. Ist das Medium für die Dauer eines DIFS frei, wird eine Backoffzeit aus dem Contention Window ausgewürfelt und nach Ablauf dieser gesendet.
3. Ist das Medium belegt, wird der Backoff bis zum Ablauf des Network Allocation Vectors (NAV) gestoppt, bevor er nach einem weiteren DIFS entsprechend weiter läuft.
4. Nach vollständigem Empfang des Paketes wartet der Empfänger ein SIFS, bevor das ACK gesendet wird.
5. Eine Kollision durch gleichzeitigen Ablauf des Backoffs führt zu einem ACK-Timeout – nach welchem ein EIFS gewartet wird, bevor sich der gesamte Vorgang wiederholen kann ( DIFS → BO .. ).

Zusätzlich sind Verfahren definiert, die eine systematische Lösung für die Problemfälle der Hidden und Exposed Station bieten, ohne die Sendepegel zusätzlich zu beschränken. Voraussetzung ist in diesen Verfahren, dass der Empfänger, der beide Sender hört, in den Prozess durch eigenes Senden eingreift:

• Ein Sendevorgang wird nicht aufgenommen, solange eine Sendung läuft. Jeder Sender sendet nur eine begrenzte Zeit.
• Der Sendevorgang wird abgebrochen, sobald der Sender durch Empfang eines anderen Senders eine Kollision feststellt. Die nächste Aussendung wird dann um eine zufällig bestimmte Pause verzögert.
• Der Empfänger, der allein die Kollision feststellt, sendet selbst ein Signal in der Erwartung, dass beide kollidierenden Sender dies erkennen und dann beide die Pausenroutine einleiten.

RTS/CTS-Koordination

Vergleich: RTS/CTS mit gleichen bzw. verschiedenen Verkehrsklassen

Um das Problem der Hidden Stations zu vermindern, ist eine Erweiterung definiert, die als CSMA/CA RTS/CTS (Request To Send/Clear To Send) bezeichnet wird. Synonym steht der Begriff MACA für Multiple Access with Collision Avoidance.

Die Sendestation versucht nach Abwarten von DIFS den Kanal mit einem RTS-Paket für eine bestimmte, in dem Paket angegebene Zeit zu belegen. Der Empfänger bestätigt dies nach Abwarten von SIFS mit einem CTS-Paket, das ebenfalls eine Belegungsdauer für den Kanal enthält.

Alle in dem Übertragungsbereich befindlichen Stationen, die dieses RTS empfangen, schweigen solange, bis die vom Empfänger zurückkommende CTS-Antwort (clear to send, enthält die Länge des Datenrahmens kopiert aus dem RTS) konfliktfrei empfangen wurde und die Sendestation die Daten versandt hat. Entsprechend warten alle Empfänger des CTS entsprechend der im CTS stehenden Länge.

Ein Vorteil dieses Verfahrens ist, dass Kollisionen nur während des Sendens von RTS- bzw. CTS-Paketen möglich sind, als Nachteil gilt der hohe Aufwand für den Austausch der Reservierungsnachrichten. RTS/CTS eignet sich insbesondere um das Problem der Hidden Station teilweise zu lösen. Es können jedoch immer noch zwei voreinander versteckte Geräte gleichzeitig RTS an einen gemeinsamen Empfänger senden. Diese kollidieren dabei und gehen verloren. In diesem Fall warten die Sender eine zufällige Zeitspanne ab und senden erneut RTS'. Der angewandte Algorithmus ist dabei das binäre exponentielle Backoff.

Ein experimenteller Vergleich zeigt, dass sich RTS/CTS-Pakete in jeder Verkehrsklasse lohnen. Auch bei kurzen Audio-Frames, welche einen hohen Overhead an RTS/CTS-Frames produzieren, rentiert sich der Einsatz des RTS/CTS-Mechanismus.

Das Problem der Exposed Station wird durch diesen Standard nicht gelöst, ist aber auch nicht so dramatisch einzustufen wie das Hidden Station-Problem, da es lediglich zu einem geringeren Durchsatz führt.

Eine Weiterentwicklung für Ad-hoc-Netzwerke ist das PAMAS-Protokoll (Power Aware Multi-Access Protocol with Signaling Ad Hoc Networks).

Der Unterschied zu MACA besteht darin, dass Empfänger, die das RTS/CTS-Signal hören, sich für die Dauer der Übertragung abschalten. Dies ist möglich, da das RTS/CTS jeweils die Paketgröße beinhalten. Weiterhin wird Energie dadurch gespart, dass sich die Knoten in regelmäßigen Abständen abschalten.

Gegenüber MACA besitzt PAMAS eine Energieersparnis von bis zu 70 %. Dies hängt vom Vernetzungsgrad ab. Der Nachteil an MACA und PAMAS ist die geringere Durchsatzrate – hervorgerufen durch die Beschränkung der Übertragungen auf nur eine in einer Nachbarschaft von wechselseitig erreichbaren Knoten.

PCF-Koordination

CSMA/CA PCF (Point Coordination Function) ist ein weiteres Verfahren zur Vermeidung von Kollisionen in drahtlosen Netzwerken (Wireless LANs), bei dem der Access Point den Medienzugriff zentral steuert.

Dazu richtet der Access Point neben der Wettbewerbsperiode (CP, Contention Period) eine wettbewerbsfreie Periode (CFP, Contention Free Period) ein. In der CFP fordert der AP nach dem Abwarten von PIFS alle Stationen zum Senden eines Datenframes auf. Eine sendewillige Station kann nach Abwarten von SIFS mit dem Senden beginnen, anschließend fährt der AP nach dem Abwarten von SIFS mit dem Senden der Poll-Pakete fort.

CSMA/CA PCF ist optional und wird daher selten implementiert.

Literatur

• R. Michael Buehrer: Code Division Multiple Access (CDMA). 1. Auflage. Morgan & Claypool, 2006, ISBN 1-59829-040-1.
• Volker Jung, Hans-Jürgen Warnecke (Hrsg.): Handbuch für die Telekommunikation. Springer Verlag, Berlin / Heidelberg 1998, ISBN 3-642-97703-0.
• Mark A. Dye, Rick McDonald, Antoon W. Rufi: Netzwerkgrundlagen.' CCNA exploration companion guide. Addison+Wesley Verlag, München 2008, ISBN 978-3-8273-2685-0.
• Dirk Traeger: LAN Praxis Lokaler Netze. Springer Fachmedien, Berlin / Heidelberg, ISBN 978-3-519-06189-2.

Siehe auch

• Wireless Local Area Network
• IEEE 802.11e

Weblinks

• Alan Colvin: CSMA with collision avoidance. 1983. doi:10.1016/0140-3664(83)90084-1
• DataLink Layer – Carrier Sense Multiple Access with Collision Avoidance