Quelltext der Seite 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 [[Rechnernetz|Netzwerkstationen]] auf denselben [[Übertragungskanal]]. Es wird häufig unter anderem bei drahtlosen Netzwerken ([[Wireless LAN]]s) eingesetzt, findet aber abgewandelt auch bei Kommunikationsverfahren wie [[Integrated Services Digital Network|ISDN]] Anwendung, oder in vielen Kommunikationsnetzen, bei denen mehrere Clients Daten auf einen [[Bus (Datenverarbeitung)|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 [[Übertragungstechnik|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''' ([[Englische Sprache|engl.]] „verstecktes Endgerät“) bezeichnet in asynchronen und nicht zentral koordinierten [[Kommunikationsnetz]]en, [[Funknetz]]en oder [[Rechnernetz]]en 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.

[[Datei:Hidden Station.svg|mini|Hidden Station in Funknetzen]]
Die Abbildung stellt die typische Situation des Hidden-Station-Problems in [[Funknetz]]en 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 derer 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 Koordination|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:

# Zuerst wird das Medium abgehört („horcht“, „Carrier Sense“).
# Ist das Medium für die Dauer eines [[Inter Frame Spacing|DIFS]] frei, wird eine [[Backoff]]zeit aus dem [[Contention Window]] ausgewürfelt und nach Ablauf dieser gesendet.
# Ist das Medium belegt, wird der Backoff bis zum Ablauf des [[Network Allocation Vector]]s (NAV) gestoppt, bevor er nach einem weiteren DIFS entsprechend weiter läuft.
# Nach vollständigem Empfang des Paketes wartet der Empfänger ein [[Inter Frame Spacing|SIFS]], bevor das ACK gesendet wird.
# Eine Kollision durch gleichzeitigen Ablauf des Backoffs führt zu einem ACK-Timeout – nach welchem ein [[Inter Frame Spacing|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 ==
[[Datei:RTS CTS.jpg|mini|Vergleich: RTS/CTS mit gleichen bzw. verschiedenen Verkehrsklassen]]
Um das Problem der ''Hidden Station''s zu vermindern, ist eine Erweiterung definiert, die als '''CSMA/CA RTS/CTS''' ('''R'''equest '''T'''o '''S'''end/'''C'''lear '''T'''o '''S'''end) bezeichnet wird. Synonym steht der Begriff '''MACA''' für '''M'''ultiple '''A'''ccess with '''C'''ollision '''A'''voidance.

Die Sendestation versucht nach Abwarten von [[Inter Frame Spacing|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 [[Inter Frame Spacing|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 [[Binary Exponential Backoff|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.<ref>Hermann Pommer: ''Roaming zwischen Wireless Local Networks''. VDM 2008, ISBN 978-3-8364-8708-5, S.&nbsp;179.</ref>

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''' ('''P'''oint '''C'''oordination '''F'''unction) ist ein weiteres Verfahren zur Vermeidung von Kollisionen in drahtlosen Netzwerken ([[Wireless LAN]]s), bei dem der [[Wireless Access Point|Access Point]] den Medienzugriff zentral steuert.

Dazu richtet der Access Point neben der Wettbewerbsperiode (CP, '''C'''ontention '''P'''eriod) eine wettbewerbsfreie Periode (CFP, '''C'''ontention '''F'''ree '''P'''eriod) ein. In der CFP fordert der AP nach '''dem Abwarten von [[Inter Frame Spacing|PIF]]'''[[Inter Frame Spacing|S]] alle Stationen zum Senden eines [[Datenframe]]s auf. Eine sendewillige Station kann nach Abwarten von [[Inter Frame Spacing|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]]
* [https://www.saylor.org/site/wp-content/uploads/2011/10/SAYLOR.ORG-CS402-CSMACOLLISIONAVOIDANCE.pdf DataLink Layer – Carrier Sense Multiple Access with Collision Avoidance]

== Einzelnachweise ==
<references />

[[Kategorie:Netzwerkarchitektur]]
[[Kategorie:WLAN]]

[[he:Carrier sense multiple access#CSMA/CA]]
[[zh:载波侦听多路访问#CSMA/CA]]