Hendrik Lüth

Kollisionsverhinderung in Netzwerken mit hoher Clientdichte

In ihrem Paper „MAC Protocols for IEEE 802.11ax: Avoiding Collisions on Dense Networks“ beschreiben Rafael A. da Silva und Michele Nogueira, beide von der „Federal University of Paraná“, Curitiba, Brasilien, die Ergebnisse ihrer Forschung. Ich werde versuchen das Ganze etwas zusammenzufassen und die Hintergründe zu erklären. Das originale Paper findet ihr unter diese Link.

In den letzten Jahren gab es viele Veränderungen an den WLAN-Standards, da WLAN mittlerweile das Zugangsmedium ist um sich mit dem Internet zu verbinden. Aber, trotz der Tatsache, dass die Brutto-Datenraten der WLAN-Standards immer weiter stiegen, gab es weiterhin größere Probleme in Bereichen mit vielen Clients auf wenig Raum, wie z.B. in Stadien oder Hörsälen. Durch eine Vielzahl von Modifikationen ist es gelungen diese Orte funktional zu versorgen, leider teilweise zum Nachteil des Datendurchsatzes. Ganz salopp würde man sagen: „Die Luft ist voll“. Eine der Haupt-Ursachen, warum es in diesen Bereichen so schwierig ist, liegt auf Layer 2 des OSI-Modells. Auf dem „Medium Access Layer“ verwendet der IEEE 802.11 Standard seit langer Zeit CSMA/CA (Carrier Sense Multiple Access/Collision Avoidance) als das Mittel der Wahl um den Zugang zum Medium für alle Nutzer zu gewährleisten, allerdings klappt dies nicht mehr zuverlässig.

Das Funktionsprinzip von CSMA/CA ist recht simpel. Wenn eine Station senden möchte, so muss sie ein paar Schritte vollziehen, bis sie dies tun kann:
1) Carrier Sense
In dieser Phase „hört“ die Station, ob das Medium frei ist. Dies ist es nicht, wenn ein gültiges, 20MHz 802.11 Signal mit mindestens -82 dBm oder irgendein anderes Signal mit mindestens -62 dBm oder höher empfangen wird.

2) Auswürfeln einer Backoff Zeit
Sollte der Kanal in einem Rahmen frei sein, der erlaubt zu senden, so wartet die Station, bis die letzte Übertragung abgeschlossen ist und muss ein AIFS (Arbitrary Inter Frame Space) und ein CW (Contention Window) lang warten, bis sie senden darf. Die Länge eines AIFS und des CW ist abhängig von der Art der Übertragung. Die Länge des CW wird von der Station, welche senden möchte, zufällig ausgewählt. Es wird zwischen „Voice“, „Video“, „Best Effort“ und „Background“ unterschieden. Die entsprechenden Längen sind in der folgenden Tabelle aufgeführt:

DatenartLänge AIFSLänge CW
Voice2 Slots + SIFS0-3 Slots
Video2 Slots + SIFS0-7 Slots
Best Effort3 Slots + SIFS0-15 Slots
Background7 Slots + SIFS0-15 Slots

Die Länge eines SIFS (Short Inter Frame Space) und eines Slots ist abhängig vom Standard, der für die Übertragung verwendet wird.
 802.11b802.11a/n/ac802.11g/n
SIFS10µs16µs10µs
Slot time20µs9µs9µs

Wenn dann AIFS und CW vergangen sind und keine andere Station angefangen hat zu senden, dann beginnt die Station zu senden. Somit bekommen alle Stationen irgendwie die Möglichkeit zu senden, durch die verschiedenen Datenkategorien sogar mit einer Art QoS (Quality of Service).

3) Nach einer Übertragung hat die empfangende Station genau ein SIFS (Short Inter Frame Space) Zeit um ein ACK zu senden. Wenn sich nun allerdings, am ehesten in Netzwerken mit einer hohen Clientdichte und auch vielen Clients pro Access Point, mehrere Stationen den selben Slot zum senden aussuchen, dann überlagern die Signale und mit einer sehr hohen Wahrscheinlichkeit kann keines der Signale dekodiert werden. Da kein NACK vorgesehen ist muss die sendende Station auf ein ACK oder einen timeout des ACK warten. Für den Fall, dass eine Übertragung fehlschlägt wird das CW verlängert, um mögliche Kollisionen bei der nächsten Übertragung zu vermeiden. Somit werden die CWs in größeren Netzwerken immer länger, was an sich nicht schlecht ist, allerdings wird nach jeder erfolgreichen Übertragung die Länge des CW wieder auf den vorgesehenen Rahmen zurückgesetzt.

Und genau an dieser Stelle setzt die im Paper behandelte Forschungsarbeit an. Die Autoren haben Berechnungen und Simulationen durchgeführt, welche eindeutige Ergebnisse zeigen. Beispielsweise beträgt die Kollisionswahrscheinlichkeit bei einem Netzwerk mit 5 Clients, welche alle Daten der Kategorie „voice“ senden wollen, bereits 50%. Mit steigender Größe des CW reduziert sich auch die Kollisionswahrscheinlichkeit, was sich in folgender Grafik aus dem Paper erkennen lässt:

All rights of the picture above belong to Rafael A. da Silva and Michele Nogueira, Federal University of Paraná, Curitiba, Brasil.

Natürlich werden vor jeder Aussendung von Data-Frames von einer Station Control-Frames gesendet, welche über einen „virtual carrier sense“ Mechanismus den Kanal reservieren und verhindern sollen, dass es zu Kollisionen kommt, allerdings unterliegen diese Control-Frames ebenfalls der oben genannten Problematik.

Es gibt viele Studien über das aktuelle 802.11 MAC Protokoll und wie es verbessert werden kann. Die IEEE-Taskgroup, welche an 802.11ax arbeitet, hat hierzu Verfahren und Szenarios entwickelt, welche viele Clients und Access Points enthalten um große High Density Netzwerke darstellen, welche genau diese Kollisionsprobleme erzeugen. Eine der Überlegungen ist die Länge eines Slots von 9µs auf 4,5µs zu halbieren und die Zahl der Slots pro CW zu verdoppeln, womit sie so gesehen gleich lang bleiben, sich aber doppelt so viele Möglichkeiten ergeben zu senden. Des weiteren sind dann auch neuere und ältere Geräte miteinander kompatibel. Das ganze Verfahren nennt sich dann EICW (Enlargement of Initial CW). Es gibt allerdings Zweifel, ob EICW eventuell Einfluss auf das CCA (Clear Channel Assessment) haben konnte, da vor dem Senden geprüft werden muss, ob der Kanal belegt ist. Wenn nun die Zeiten halbiert werden, die pro Slot vorgesehen sind, dann stellt sich die Frage, ob es überhaupt Hardwaretechnisch machbar ist, in einer solch kurzen Zeit die Messung durchzuführen. Den Autoren nach sollte dies aufgrund der aktuellen Veränderungen in der Hardwareentwicklung machbar sein.

Ein anderer Ansatz sind Protokolle auf der Basis von TDMA (Time Division Multiple Access). Bei TDMA wird die Airtime auch in Slots aufgeteilt, alle Nodes eines Netzwerks haben ein gleich großes CW und jede Station hat einen für sich reservierten Slot, in welchem sie senden darf. Normalerweise wird dieser Slot zufällig ausgesucht und die Station wird, für den Fall, dass die Übertragung erfolgreich war, danach in keinem anderen Slot senden. Protokolle nach dieser Idee nennen sich „Deterministic Backoff“. Leider treten hierbei Probleme mit der Priorisierung auf, was allerdings durch die Alloziierung mehrerer Slots an ein Device behoben werden kann. Insgesamt ist dennoch fraglich, ob dieses Protokoll wirklich die gewünschten Verbesserungen gibt, da legacy-devices nicht wissen, dass sie einen Slot reservieren müssen, was wiederum zu Aussendungen in bereits belegten Slots führen kann.

Die dritte Methode, welche in diesem Paper vorgestellt wird nennt sich ganz charmant und kurz TDuCSMA, was für „Time-Division Unbalanced Carrier Sense Multiple Access“ steht. Hierbei wird vom Service Provider ein gewisser Prozentsatz der verfügbaren Airtime für jeden User vorgesehen. Zum Beispiel kann ein Time Circle (TC) mit der Dauer von 100ms in mehrere Time Frames (TF) von 10ms aufgeteilt werden und jedes TF wird dann an eine der Stationen alloziiert, in der sie dann ohne Contention senden können, da sie in ihrem TF den kürzesten AIFS verwenden können. Alle anderen Stationen senden in diesem Zeitraum mit den normalen CWs und der Medium Access wird weiterhin durch CSMA/CA geregelt und funktioniert somit auch für legacy-Clients. Leider sind die Fragen der Synchronisation der Timer und die Koordination zwischen den benachbarten Zellen noch nicht endgültig geklärt.

Wenn die drei oben genannten Methoden in gleichen Szenarios verglichen werden bringen sie alle eine Minderung der Kollisionsraten im Vergleich zum 802.11n MAC-Protokoll, allerdings bedeutet eine Reduzierung der Kollisionsraten nicht unbedingt auch eine Steigerung des Datendurchsatzes, da bei manchen Protokollen die Datenpakete eher einen Timeout erleiden, während die Station auf eine Möglichkeit zum Senden wartet, als bei anderen Verfahren. Da 802.11ax wieder ein Dual-Band Standard werden wird, werden alle Messungen mit 802.11n und nicht mit 802.11ac verglichen, da sich 802.11ac nur auf 5GHz bezieht.

Ein weiterer Punkt, welcher bei der Suche nach einem geeigneten MAC-Protokoll für 802.11ax beachtet werden muss, ist die Multi User Fähigkeit des Protokolls. Seit der Einführung von DL MU-MIMO (Downlink Multiuser Multiple Input Multiple Output) mit 802.11ac wird nun auch nach der Realisierbarkeit von UL MU-MIMO geforscht, wozu wieder ein geeignetes MAC-Protokoll gefunden werden muss. Es gibt eine Masse an Vorschlägen, wie ein solches Protokoll aussehen könnte, allerdings sollte sich dann die TaskGroup ax für eine koordinierte Methode entscheiden. Koordiniert bedeutet, dass zum Beispiel jede Station eine Übertragung ankündigt und auf ein Trigger frame hin mehrere Stationen parallel ihre Daten senden. Das folgende Bild zeigt ein Beispiel, wie dies aussehen könnte:

All rights of the picture above belong to Rafael A. da Silva and Michele Nogueira, Federal University of Paraná, Curitiba, Brasil.

Eine andere Möglichkeit für Multi User Übertragungen ist OFDMA (Orthogonal Frequency Division Multiple Access). Wie auch schon in WiMax und LTE könnte OFDMA eine Performancesteigerung für 802.11ax mit sich bringen. OFDMA weist jeder Station ihren eigenen OFDM-Subchannel zu, auf welchem die Station dann ohne größere Störungen senden kann. Allerdings wird es schwieriger zu überprüfen, ob ein Kanal belegt ist oder nicht, was wiederum vom AP koordinierten MAC-Protokollen in die Hände spielt. Zwar gibt es seit 802.11n sog. CSI (Channel State Information), welche sich der AP von Stations holen muss, um zu erkennen inwieweit das Medium belegt ist und was gerade passiert. Allerdings muss das CSI Feedback überarbeitet werden, damit es ausreichend Informationen mit fast keinem overhead liefert.

Zusammenfassend haben alle Protokolle ihre Problemchen und es wird sich zeigen, welche Wege gefunden werden um diese zu umgehen und welches Protokoll, bzw. welcher Mechanismus, dann endgültig in den 802.11ax Standard aufgenommen wird um dem Namen „High Efficiency WLAN“ gerecht zu werden.

3 Kommentare zu “Kollisionsverhinderung in Netzwerken mit hoher Clientdichte

  1. Barteamer Anonymous

    Hallo Hendrik,

    Ich bin echt erstaunt, das du neben deinen Bartätigkeiten auch so ein tollen und informativen Blog führst!
    Wirklich gute und fundierte Informationen! (obwohl ich nur wenig davon verstehe 😛 )

    Viele Grüße,
    K2 Barteamer anonymous

Schreibe einen Kommentar

Deine E-Mail-Adresse wird nicht veröffentlicht. Erforderliche Felder sind mit * markiert.