CSMA/CA: De­fi­ni­ti­on und Erklärung des Ver­fah­rens

Die tech­ni­schen Un­ter­schie­de zwischen ka­bel­ge­bun­de­nen und draht­lo­sen Netz­wer­ken führen auch zum so­ge­nann­ten Hidden-Station-Problem. Stationen in einem Funk­netz­werk haben nur eine begrenzte Reich­wei­te. So kann es passieren, dass sich Teil­neh­mer in einem Netzwerk ge­gen­sei­tig nicht wahr­neh­men.

Es ist vor­stell­bar – und nicht un­wahr­schein­lich –, dass zwei Stationen, die sich ge­gen­sei­tig nicht wahr­neh­men, eine Station, die zwischen ihnen liegt, gleich­zei­tig erreichen möchten. Über­tra­gun­gen können sich am Emp­fän­ger­kno­ten über­la­gern und so dazu führen, dass die Daten verloren gehen. Beide Sender erkennen die Kollision nicht und starten daher keinen neuen Sen­dungs­ver­such. CSMA/CA kann dieses Problem allein nicht beheben, weshalb man eine optionale Er­wei­te­rung ge­schaf­fen hat: RTS/CTS („Request to Send“ und „Clear to Send“).

CSMA/CA passt das Verfahren zum Umgang mit Kol­li­sio­nen (CSMA/CD), das man bei Halb­du­plex-Ethernet-Netz­wer­ken einsetzt, an die Her­aus­for­de­run­gen von Funk­netz­wer­ken an. CSMA/CD versucht dabei weniger, Kol­li­sio­nen zu vermeiden. Statt­des­sen versteht das Protokoll Kol­li­sio­nen als Selbst­ver­ständ­lich­kei­ten und etabliert einen Me­cha­nis­mus, wie die Netz­werk­teil­neh­mer im Falle einer Kollision verfahren müssen, um zu ver­hin­dern, dass Kol­li­sio­nen auch beim zweiten Versuch direkt wieder auftreten: Eine zufällige Zeit­span­ne (Backoff), die Stationen nach einer fehl­ge­schla­ge­nen Über­tra­gung abwarten müssen, damit nicht wieder beide be­tei­lig­ten Teil­neh­mer zum gleichen Zeitpunkt anfangen zu senden, soll dies be­werk­stel­li­gen.

Ein draht­lo­ses Netzwerk lässt sich nicht so sicher über­wa­chen, wie dies bei einem ka­bel­ge­bun­de­nen Netz der Fall ist. Kol­li­sio­nen können durch einen zweiten Sender ver­ur­sacht werden, der außerhalb der Reich­wei­te des ersten liegt. Beide haben keine Mög­lich­keit, den Sen­dungs­ver­such des anderen wahr­zu­neh­men. Deshalb muss der Fokus darauf liegen, die Wahr­schein­lich­keit von Kol­li­sio­nen zu ver­rin­gern. CSMA/CA zieht den Backoff im Ablauf nach vorne und setzt ihn so bereits vor dem ersten Sen­dungs­vor­gang ein. Dies sorgt dafür, dass es un­wahr­schein­li­cher wird, dass Teil­neh­mer gleich­zei­tig mit einer Über­tra­gung beginnen und so Kol­li­sio­nen ver­ur­sa­chen.

Grundidee hinter CSMA/CA ist das Prinzip „Listen before Talk“. Das heißt, dass zunächst überprüft werden muss, ob die Leitung frei („idle“) ist, bevor die Station mit einer Über­tra­gung beginnen darf. Doch dies ist nur der erste Schritt. Weitere Funk­tio­nen innerhalb des Ver­fah­rens sorgen dafür, dass Kol­li­sio­nen zu einem großen Teil vermieden werden können.

Die Dis­tri­bu­ted Coor­di­na­ti­on Function (DCF) regelt innerhalb von CSMA/CA den Zeitraum, den eine Station wartet, bevor sie bei einem freien Medium die Über­tra­gung einleitet. Auch für weitere Aktionen weist DCF den Netz­teil­neh­mern bestimmte Time Slots zu und schafft so eine ver­bind­li­che zeitliche Glie­de­rung. Dieses Verfahren ist der Schwer­punkt der Collision Avoidance. Durch die komplexe Zeit­struk­tur wird die Ver­mei­dung von Kol­li­sio­nen erst er­mög­licht. Beim Erstellen der zeit­li­chen Glie­de­rung be­rück­sich­tigt DCF ver­schie­de­ne In­ter­val­le.

• DCF In­ter­frame Space (DIFS): Im ersten Schritt müssen Teil­neh­mer das Netzwerk für die Dauer des DIFS über­wa­chen, um fest­zu­stel­len, ob dieses gerade frei ist. Für CSMA/CA bedeutet dies, dass zum Zeitpunkt des Sendens keine andere Station in Reich­wei­te sendet. Der DIFS ergibt sich aus dem SIFS und der doppelten Slotzeit und ist zwischen 28 und 50 µs lang.

• Con­ten­ti­on Window: Wenn Teil­neh­mer fest­stel­len, dass der Kanal frei ist, warten sie zunächst noch eine zufällige Zeit­span­ne, bevor sie mit dem Versand beginnen. Diese Dauer ent­spricht dem so­ge­nann­ten Con­ten­ti­on Window. Dieses Zeit­fens­ter ver­dop­pelt sich mit jeder auf­tre­ten­den Kollision und ent­spricht somit dem Binary Ex­po­nen­ti­al Backoff (BEB), wie man ihn von CSMA/CD kennt.

• Short In­ter­frame Space (SIFS): Nach dem Senden des Da­ten­pa­kets ver­schickt der Emp­fän­ger­kno­ten eine Be­nach­rich­ti­gung – falls zu­sätz­lich das RTS/CTS-Verfahren an­ge­wen­det wird. Vor dem Ab­schi­cken wartet al­ler­dings auch diese Station eine fest­ge­leg­te Zeit­span­ne ab. SIFS ist die Zeit, die es braucht, ein Da­ten­pa­ket zu ver­ar­bei­ten. Die Dauer ist abhängig vom ver­wen­de­ten IEEE-802.11-Standard und liegt zwischen 10 µs und 16 µs.

Die Frames Request to Send (RTS) und Clear to Send (CTS) sind Teil der op­tio­na­len Er­wei­te­rung CSMA/CA RTS/CTS. Dieses Verfahren ist der ei­gent­li­chen Da­ten­über­tra­gung vor­ge­la­gert. Wenn ein Teil­neh­mer fest­stellt, dass das Über­tra­gungs­me­di­um frei ist, sendet das Gerät zunächst einen RTS-Frame an den Teil­neh­mer, der Empfänger der Daten sein soll. Hiermit macht der Aus­gangs­rech­ner deutlich, dass er eine Über­tra­gung starten möchte und dabei das Über­tra­gungs­me­di­um für eine gewisse Zeit belegen wird.

Der Empfänger wiederum sendet einen CTS-Frame an den ur­sprüng­li­chen Sender. Hierüber werden zum einen – wie auch schon mit dem RTS-Frame – alle anderen Teil­neh­mer in der Reich­wei­te darüber in­for­miert, dass das Über­tra­gungs­me­di­um derzeit belegt ist, und zum anderen erhält der Sender die Freigabe zur Über­tra­gung. Erst dann beginnt das ur­sprüng­li­che Gerät mit der Über­tra­gung der Daten. Nun ist es für die Teil­neh­mer in einem draht­lo­sen Netzwerk nicht möglich, Kol­li­sio­nen oder andere Störungen bei der Über­tra­gung fest­zu­stel­len. Aus diesem Grund ist es notwendig, dass die Emp­fän­ger­sta­ti­on eine Be­stä­ti­gung (ACK) sendet, wenn das Da­ten­pa­ket korrekt an­ge­kom­men ist.

Bleibt der ACK-Frame aus, geht der Sender der Daten davon aus, dass es zu einer Kom­pli­ka­ti­on gekommen ist, und sendet das Da­ten­pa­ket erneut. Dabei hat die Station ein Vor­zugs­recht, das Medium zu benutzen – muss also nicht erneut warten, bis der Kanal frei ist. Die drei Frame-Arten bestehen jeweils aus mehreren Feldern.

• Frame Control: Das in jedem 802.11-Frame ent­hal­te­ne FC-Feld ist 2 Byte groß (16 Bit) und wiederum in mehrere Elemente un­ter­teilt:
  • Protocol Version: Gibt die Version des ver­wen­de­ten Pro­to­kolls an.
  • Type: Gibt an, ob es sich um einen Control Frame (wie bei RTS/CTS und ACK), Data Frame oder Ma­nage­ment Frame handelt.
  • Sub-Type: Spe­zi­fi­ziert den Typus des Frames, indem eine von 25 Un­ter­ka­te­go­rien angegeben wird.
  • To Dis­tri­bu­ti­on System: Ist gesetzt, wenn der Frame an ein Dis­tri­bu­ti­on System geht.
  • From Dis­tri­bu­ti­on System: Ist gesetzt, wenn der Frame von einem Dis­tri­bu­ti­on System kommt.
  • More Fragments: Hat nur dann Inhalt, wenn noch mehr Frames folgen (nur bei Data Frames und Ma­nage­ment Frames relevant).
  • Retry: Gibt an, ob und wie oft der Versand des Frames schon versucht wurde.
  • Power Ma­nage­ment: Zeigt den Strom­spar­mo­dus an.
  • More Data: Gibt an, dass mehr Daten versendet werden sollen.
  • WEP: Gibt Auskunft darüber, ob die Daten mit WEP ver­schlüs­selt sind.
  • Order: Teilt dem Empfänger mit, ob die Daten in der richtigen Rei­hen­fol­ge versendet werden.

• Duration: Gibt die Zeit an, die der Sender für die Da­ten­über­tra­gung benötigt. Diese In­for­ma­ti­on ist ent­schei­dend für den Network Al­lo­ca­ti­on Vector. Auch dieses Feld ist 2 Byte groß.

• Receiver Address: Enthält die MAC-Adresse des Emp­fän­gers (6 Byte).

• Trans­mit­ter Address: Enthält die MAC-Adresse des Absenders (6 Byte); nur er­for­der­lich für RTS, nicht für CTS und ACK.

• Frame Check Sequence: Bei der 4 Byte langen Block­prüf­zei­chen­fol­ge handelt es sich um eine Prüfsumme. Hiermit kann die emp­fan­gen­de Station fest­stel­len, ob der Data Frame so an­ge­kom­men ist, wie es geplant war. Der Sender errechnet hierfür die Prüfsumme aus den Daten des Frames. Der gleiche Vorgang findet auch auf Seiten des Emp­fän­gers statt, wenn der Frame bei ihm an­ge­kom­men ist. Sollte das Ergebnis des Emp­fän­gers mit dem über­ein­stim­men, was der Sender als FCS an den Frame angehängt hat, war die Über­tra­gung er­folg­reich.

Bis auf das Feld, das die Trans­mit­ter Address angibt, sind grund­sätz­lich alle Felder in RTS, CTS und ACK enthalten. Das Ab­sen­der­feld ist al­ler­dings nur in­ter­es­sant bei der ersten Kon­takt­auf­nah­me, damit der Empfänger weiß, mit welchem Knoten er nun kom­mu­ni­ziert.

Durch die Er­wei­te­rung des CSMA/CA-Pro­to­kolls durch RTS/CTS ist es möglich, Kol­li­sio­nen auf den an­fäng­li­chen RTS-Frame zu re­du­zie­ren. So ist es trotzdem wahr­schein­lich, dass zwei Teil­neh­mer gleich­zei­tig einen Request to Send an dieselbe Station senden. In einem solchen Fall sendet der Empfänger al­ler­dings keinen CTS-Frame, da die RTS-Frames nicht korrekt an­ge­kom­men sind. Somit kann RTS/CTS das Hidden-Station-Problem lösen: Auch wenn die beiden Sender sich ge­gen­sei­tig aufgrund der be­grenz­ten Reich­wei­te nicht wahr­neh­men, sind nur die RTS-Frames gefährdet und nicht die ei­gent­li­chen Daten. Im Anschluss greift CSMA/CA, und die Über­tra­gung kann geordnet statt­fin­den.

Durch den RTS/CTS-Austausch wird zwar das Hidden-Station-Prinzip gelöst, die Er­wei­te­rung sorgt aber für eine andere Schwie­rig­keit – das Exposed-Station-Problem. Die Situation ist zunächst die gleiche wie beim Hidden-Station-Problem: Eine Station befindet sich in der Mitte von zwei anderen Stationen, die sich ge­gen­sei­tig nicht erreichen können. Eines der beiden Geräte möchte nun Daten an die Station in der Mitte senden. Alle er­reich­ba­ren Kno­ten­punk­te empfangen den CTS-Frame, der sie von einer Sendung abhält. Das umgeht das Hidden-Station-Problem – schafft dabei aber ein neues.

Eine dritte Station wird nun nämlich vom Senden ab­ge­hal­ten, auch dann, wenn ei­gent­lich eine ganz andere, vierte Station das Ziel der Sendung wäre. Diese Über­tra­gung würde keine Kollision erzeugen und wird dennoch un­ter­bun­den, was zu einer Ver­lang­sa­mung des ganzen Netzes führt.

Bevor ein Gerät im Netzwerk mit einer Über­tra­gung beginnt, sendet dieses zunächst eine In­for­ma­ti­on (im Duration-Feld des RTS-Frames) an alle anderen Teil­neh­mer. So teilt die Station mit, wie lange das Netz durch die Über­tra­gung belegt sein wird. Jedes andere Gerät trägt diese In­for­ma­ti­on in seinen ganz per­sön­li­chen Netz­be­le­gungs­vek­tor ein (bei dem es sich ma­the­ma­tisch gesehen nicht wirklich um einen Vektor handelt). Dieser wird intern verwaltet und gibt die Zeit an, ab wann ein Sen­dungs­ver­such wieder möglich ist. Der Network Al­lo­ca­ti­on Vector (NAV) zählt fort­lau­fend herunter und wird nur durch neue In­for­ma­tio­nen von anderen Stationen wieder auf­ge­füllt.

Ein NAV kann den Timer um maximal 33 ms (32.767 µs) hoch­set­zen. Das ist die Ma­xi­mal­dau­er, für die ein Sender das Medium blo­ckie­ren darf. Die Geräte im Netzwerk sind, während der Netz­be­le­gungs­vek­tor noch nicht ab­ge­lau­fen ist, inaktiv. Dies spart Energie. Erst wenn der Zähler auf 0 steht, wird der Teil­neh­mer wieder aktiv und überprüft das Netz. Der NAV passt sich nicht nur durch den RTS an, sondern wird auch durch CTS und ACK be­ein­flusst. Letzteres ist für alle Teil­neh­mer das Signal, den NVA wieder auf 0 zu setzen: Das Medium ist wieder frei.

Wenn Teil­neh­mer in einem draht­lo­sen Netzwerk den Vorgaben von Carrier Sense Multiple Access with Collision Avoidance folgen, müssen bestimmte Schritte ein­ge­hal­ten werden: Zunächst über­wa­chen die Stationen das Über­tra­gungs­me­di­um. Das bedeutet im Falle von WLAN, dass der Carrier Sense den Funkkanal überwacht und dabei prüft, ob andere Netz­teil­neh­mer – soweit sie für das jeweilige Gerät sichtbar sind – gerade senden.

Stellt sich heraus, dass das Über­tra­gungs­me­di­um derzeit belegt ist, wird ein zu­fäl­li­ger Backoff ein­ge­lei­tet: Die Station wartet eine zufällige Zeit­span­ne, bis eine erneute Über­prü­fung einsetzt. Allen anderen Stationen, die nicht gerade mit Senden oder Empfangen be­schäf­tigt sind, geht es genauso. Die durch den Zufall bestimmte Wartezeit sorgt dafür, dass die Teil­neh­mer nicht gleich­zei­tig beginnen, das Netzwerk zu über­prü­fen, und somit auch nicht gleich­zei­tig mit der Über­tra­gung von Daten beginnen können. Dies geschieht aber nur dann, wenn der Station nicht ohnehin aufgrund des Netz­be­le­gungs­vek­tors (NAV) klar ist, dass das Medium belegt ist.

Sollte das Netz frei sein, leitet die Station DCF ein: Zunächst wird also der Kanal für die Dauer des DIFS weiter überprüft. Sollte er auch für diese Zeit­span­ne frei bleiben, startet ein zu­fäl­li­ger Backoff und erst dann beginnt der RTS/CTS-Austausch – falls dieser zu­sätz­li­che Me­cha­nis­mus verwendet wird. Ist der Request to Send er­folg­reich beim Empfänger an­ge­kom­men und somit keine Kollision ein­ge­tre­ten, erhält der Sender durch den CTS-Frame die Erlaubnis, das Über­tra­gungs­me­di­um zu belegen.

Gleich­zei­tig werden alle anderen Teil­neh­mer darüber in­for­miert, dass das Netzwerk gerade benutzt wird. Dadurch setzen diese ihren Netz­be­le­gungs­vek­tor wieder hoch und warten, bis sie erneut über­prü­fen, ob der Kanal frei ist. Nun beginnt die Station mit der Über­tra­gung. Ist diese beendet, wartet der Empfänger für die Dauer eines SIFS und antwortet an­schlie­ßend mit einem ACK-Frame, um dem Sender den voll­stän­di­gen Empfang zu be­stä­ti­gen und den Netz­be­le­gungs­vek­tor auf 0 zu setzen – das Netz ist frei für eine neue Über­tra­gung.

CSMA/CA löst einige Probleme, die in draht­lo­sen Netz­wer­ken auftreten und nicht durch CSMA/CD gelöst werden können. Dennoch ist das Verfahren auch nicht ohne Nachteile: Zum einen können gewisse Pro­blem­fäl­le so nicht voll­stän­dig gelöst werden und zum anderen bringt CSMA/CA neue Schwie­rig­kei­ten mit sich.

Da das CSMA/CA-Verfahren bei weitem nicht perfekt ist, gibt es Be­stre­bun­gen, es zu erweitern. So sollen Schwach­punk­te aus­ge­merzt werden. Zwei Verfahren, die beide den Ansatz von ko­or­di­nier­ten Mehr­fach­zu­grif­fen verfolgen, sind zwar aus­ge­ar­bei­tet, werden aber aus ver­schie­de­nen Gründen kaum ein­ge­setzt. Ko­or­di­nier­te Mehr­fach­zu­grif­fe eta­blie­ren eine zentrale Or­ga­ni­sa­ti­ons­stel­le: Die Zu­griffs­rech­te der einzelnen Stationen auf das Über­tra­gungs­me­di­um sollen dabei nicht mehr aus­schließ­lich un­ter­ein­an­der ko­or­di­niert werden. Statt­des­sen laufen Anfragen über den Access Point (z. B. über den WLAN-Router).

Die Point Coor­di­na­ti­on Function (PCF) wird zu­sätz­lich in das CSMA/CA-Verfahren ein­ge­glie­dert und ersetzt oder ergänzt die Dis­tri­bu­ted Coor­di­na­ti­on Function (DCF). Der Access Point fungiert als Ko­or­di­na­tor (Point Coor­di­na­tor) und spricht die Stationen innerhalb des Netzes gezielt an. Bevor dies nicht geschehen ist, darf niemand das Über­tra­gungs­me­di­um belegen. Für die Ordnung der einzelnen Stationen besitzt der Ko­or­di­na­tor eine so­ge­nann­te Polling-Liste.

Dieser Liste nach wird jeder Netz­teil­neh­mer entweder einfach nach­ein­an­der oder der Priorität nach geordnet gefragt, ob er eine Über­mitt­lung vornehmen möchte. Bevor der Access Point al­ler­dings die Nachfrage beginnt, läuft wie bei DFC eine Zeit­span­ne ab, al­ler­dings in der Länge eines PIFS. Der PCF In­ter­frame Space ist um eine Slotzeit kürzer als der DIFS und hat damit eine höhere Priorität. PCF greift damit früher als DCF.

Das Verfahren liefert einen Ansatz, um das Hidden-Station-Problem zu lösen: Durch eine gute Po­si­tio­nie­rung des Access Points kann die benötigte Reich­wei­te halbiert werden. Durch PCF müssen die Teil­neh­mer sich nicht mehr ge­gen­sei­tig wahr­neh­men. Es reicht, wenn der Access Point mittig platziert ist und so stern­för­mig alle Stationen erreichen kann.

Die Point Coor­di­na­ti­on Function erzeugt al­ler­dings eine andere Schwach­stel­le: Um die Technik nutzen zu können, müssen alle Netz­werk­teil­neh­mer die Fähigkeit zu PCF besitzen. Dies ist aber bei weitem nicht immer der Fall. Wenn Geräte nicht am PCF-Vorgang teil­neh­men, werden sie und ihre Über­tra­gungs­wün­sche einfach ignoriert. Deshalb hat man ein al­ter­nie­ren­des System ent­wi­ckelt: Hierbei können sich PCF und DCF ab­wech­seln, um allen Geräten im Netzwerk die Mög­lich­keit zur Über­tra­gung zu geben. Dafür stellt der Access Point zwei Zeit­span­nen zur Verfügung: Zum einen gibt es die Con­ten­ti­on Free Period (CFP), in der PCF für ko­or­di­nier­te Mehr­fach­zu­grif­fe sorgt, und die Con­ten­ti­on Period (CP), in der DCF gilt und Kol­li­sio­nen wie oben be­schrie­ben mithilfe von CSMA/CA vermieden werden. Ein­ge­lei­tet wird diese Al­ter­nie­rung durch einen Beacon Frame, den der Ko­or­di­na­tor an alle Stationen sendet.

Das andere Verfahren mit ko­or­di­nier­ten Mehr­fach­zu­grif­fen, der HCF Con­trol­led Channel Access, ori­en­tiert sich stark am PCF-Verfahren. HCCA regelt al­ler­dings den Wechsel zwischen der Con­ten­ti­on Period und der Con­ten­ti­on Free Period anders. Statt eines al­ter­nie­ren­den Systems etabliert HCCA die Mög­lich­keit, dass der Access Point jederzeit von CP auf CFP um­schal­ten kann – die sich beim HCCA aber Con­trol­led Access Phase (CAP) nennt. In diesem Zeitraum ko­or­di­niert der Hybrid Coor­di­na­tor (auch hier der Access Point), wer wann Daten ver­schi­cken darf, und zwar auf Basis der Priorität. Diese ermittelt der Ko­or­di­na­tor über Traffic Classes (TC), die Stationen mit­an­ge­ben. So können ver­schie­de­nen Klassen un­ter­schied­li­che Prio­ri­tä­ten zu­ge­ord­net werden.

Hinzu kommt, dass bei HCCA der Über­tra­gungs­zeit­raum zu einer Transmit Op­por­tu­ni­ty (TXOP) wird. Diese be­schreibt eine Zeit­span­ne, in der Sender nicht nur einen Frame ver­schi­cken dürfen, sondern so viele Da­ten­frames, wie es innerhalb der TXOP-Phase möglich ist. Wenn ein Frame zu groß für die Periode sein sollte, muss dieser auf­ge­bro­chen und in mehreren Teilen ver­schickt werden. So ver­hin­dert man, dass lang­sa­me­re Stationen schnel­le­re aus­brem­sen.

In der Zeit der Con­ten­ti­on Period gilt hingegen der Enhanced Dis­tri­bu­ted Channel Access (EDCA). Auch hinter EDCA steckt eine Ordnung nach Prio­ri­tä­ten. Diese Ordnung wird aber nicht durch eine zentrale Stelle or­ga­ni­siert, statt­des­sen ordnen sich die teil­neh­men­den Stationen un­ter­ein­an­der, wie man es von DCF kennt. Kno­ten­punk­te, die wichtigen Traffic zu über­mit­teln haben, brauchen nicht einen vollen DIFS ab­zu­war­ten. Statt­des­sen pausieren solche Stationen nur für die Länge des Ar­bi­tra­ti­on In­ter­frame Space (AIFS). Um genau zu sein, gibt es ver­schie­de­ne AIFS, die – abhängig von der Priorität – durch­num­me­riert sind. Dabei hat AIFS1 die höchste Prio­ri­täts­stu­fe und ist deshalb kleiner als der DIFS, aber länger als ein SIFS. Auch bei EDCA gilt TXOP.