The 802.11 MAC protocol leads to inefficient equilibria

Dit artikel toont aan dat het bestaande 802.11 MAC-protocol in niet-coöperatieve omgevingen leidt tot inefficiënte Nash-evenwichten, en stelt voor dat een idealer protocol dat de kanaalallocatie onafhankelijk maakt van de transmissiestrategieën van individuele knopen, kan resulteren in evenwichten met een hogere totale doorvoer.

De kern

Hier is een uitleg van het paper "The 802.11 MAC Protocol Leads to Inefficient Equilibria" in simpel, alledaags Nederlands, met behulp van creatieve vergelijkingen.

De Kernboodschap: "Ik win, dus jij verliest"

Stel je voor dat je in een drukke kamer bent waar iedereen tegelijkertijd wil praten. Er is maar één microfoon (de wifi-kanalen). De huidige regels voor wie mag spreken (het 802.11-protocol, ofwel DCF) leiden tot een rare situatie: iedereen probeert slim te zijn voor zichzelf, maar als gevolg daarvan wordt het gesprek voor iedereen langzamer en rommeliger.

De auteurs van dit paper, Godfrey Tan en John Guttag, laten zien dat dit niet per se de schuld is van de mensen (de apparaten), maar van de regels zelf.

De Analogie: De Drukke Bibliotheek

Laten we de wifi-netwerken vergelijken met een drukke bibliotheek waar twee mensen (Noem ze Alice en Bob) willen studeren en hun notities willen delen via een speciaal systeem.

1. De Regels (DCF): De bibliotheek heeft een regel: "Wie het eerst komt, mag het eerst lezen." Als je een notitie wilt delen, moet je wachten tot de ander stopt. Als je een fout maakt (een notitie die niet aankomt), moet je langer wachten voordat je het opnieuw probeert.
2. De Snelheid: Je kunt notities op twee manieren sturen:
   • Snel maar kwetsbaar: Je schreeuwt je notities hard en snel. Als er iemand langsloopt (storing), is je boodschap weg.
   • Langzaam maar veilig: Je fluistert je notities rustig en duidelijk. Het duurt langer om alles te zeggen, maar de kans dat het verkeerd overkomt is heel klein.

Het Probleem: De "Luie" Strategie

Stel, Bob zit dicht bij de bibliotheekbibliotheek (goed signaal) en Alice zit ver weg (slecht signaal).

• Bob kan prima hard praten (snel).
• Alice moet fluisteren (langzaam) om zeker te zijn dat haar boodschap aankomt.

Onder de huidige regels (DCF) wordt er gekeken naar hoe vaak je mag spreken, niet hoe lang je spreekt.

• Als Alice hard probeert te schreeuwen (snel), faalt ze vaak. Ze moet dan steeds wachten en opnieuw beginnen. Ze krijgt dus weinig "sprekingsrecht".
• Als Alice besluit om langzaam te fluisteren, faalt ze zelden. Ze mag dan weliswaar minder vaak spreken, maar elke keer dat ze spreekt, duurt het gesprek lang.

Het slimme (maar egoïstische) trucje:
Alice merkt dat als ze langzaam fluistert, ze een langere tijd aan de microfoon krijgt dan als ze snel probeert te schreeuwen. Omdat de regels zeggen "wie het eerst komt, mag het eerst", en Alice nu langer aan de beurt is, denkt ze: "Ik ga lekker langzaam praten, dan heb ik meer tijd voor mezelf!"

Het resultaat:
Alice verandert haar strategie naar "langzaam" om meer tijd te krijgen. Maar omdat ze langzaam praat, duurt het gesprek voor iedereen (ook voor Bob) veel langer.

• Bob moet nu ook veel langer wachten op zijn beurt.
• De totale hoeveelheid informatie die de bibliotheek kan verwerken, daalt drastisch.

Dit noemen de auteurs een "Inefficiënt Evenwicht". Iedereen doet wat voor zichzelf het beste lijkt (Alice wil meer tijd, Bob wil snel zijn), maar samen maken ze alles trager. Het is alsof iedereen in een file langzaam rijdt om te voorkomen dat ze in de file komen, maar daardoor staat de hele weg vast.

Wat zegt het paper over de toekomst?

De auteurs zeggen: "Deze regels (DCF en de nieuwe EDCF) zijn verouderd voor een wereld waar apparaten verschillend ver van elkaar staan."

Ze stellen een nieuwe regel voor, een Slimme Bibliotheekmanager:

1. Geen "wie het eerst komt", maar "wie veel tijd nodig heeft": De manager kijkt niet naar het aantal keren dat je spreekt, maar naar de totale tijd die je aan de microfoon hebt.
2. De Beloning: Als Alice kiest voor de snelle manier (wat voor haar het beste is als ze alleen is), krijgt ze precies de tijd die ze nodig heeft. Als ze kiest voor de trage manier, krijgt ze niet extra tijd als beloning.
3. Het Resultaat: Omdat Alice nu geen extra tijd krijgt door langzaam te praten, kiest ze automatisch voor de snelste manier (want dat is het meest efficiënt voor haar).
   • Alice praat snel.
   • Bob praat snel.
   • Iedereen is tevreden en de bibliotheek werkt weer soepel.

Samenvatting in één zin

De huidige wifi-regels belonen apparaten onbedoeld voor het vertragen van hun eigen verbinding, waardoor ze meer tijd krijgen, maar de hele netwerksnelheid in de war sturen; we hebben nieuwe regels nodig die apparaten belonen voor snelheid in plaats van voor het "in beslag nemen" van de tijd.

Kortom: De huidige wifi-standaard is alsof je in een race mag winnen door je auto trager te maken, omdat de regels zeggen dat wie het langst op de baan blijft, wint. De auteurs willen regels die zeggen: "Wie het snelst en veiligst rijdt, wint."

Technische samenvatting

Hier is een gedetailleerde technische samenvatting van het paper "The 802.11 MAC Protocol Leads to Inefficient Equilibria" van Godfrey Tan en John Guttag, geschreven in het Nederlands.

Titel: Het 802.11 MAC-protocol leidt tot inefficiënte evenwichten

1. Het Probleem

De paper adresseert een fundamenteel probleem in draadloze lokale netwerken (WLANs) gebaseerd op de 802.11-standaard, met name in niet-coöperatieve omgevingen zoals openbare hotspots of aangrenzende bedrijfsnetwerken.

• Context: 802.11-netwerken ondersteunen meerdere transmissiesnelheden. Een lagere snelheid (met een robuustere modulatie) verhoogt de zendtijd per frame maar verlaagt de bitfoutkans (BER).
• Het Dilemma: In een rationele, niet-coöperatieve setting maximaliseert elke node zijn eigen doorvoersnelheid (throughput) onafhankelijk van de impact op het totale systeem.
• De Oorzaak van Inefficiëntie: Het huidige Distributed Coordination Function (DCF) protocol en de geavanceerde EDCF (onderdeel van 802.11e) verdelen de kanaaltoegang op basis van het aantal transmissiekansen (TXOPs), niet op basis van kanaaltijd.
  • Omdat DCF probeert elke node een gelijke kans te geven om te zenden (ongeacht de gebruikte snelheid), kan een node zijn aandeel in de totale kanaaltijd vergroten door bewust een lagere, inefficiënte transmissiesnelheid te kiezen.
  • Een lagere snelheid betekent een langere zendtijd per frame. Omdat de kans op een transmissiekans gelijk is, krijgt deze node meer "tijd" op het kanaal.
  • Resultaat: Rationele nodes kiezen voor een suboptimale snelheid om hun individuele throughput te maximaliseren. Dit leidt tot een Nash-evenwicht waarbij de totale aggregaat-doorvoersnelheid van het netwerk aanzienlijk lager is dan optimaal mogelijk zou zijn.

2. Methodologie

De auteurs gebruiken een combinatie van theoretische analyse en simulaties om hun stellingen te onderbouwen.

• Game-theoretisch Model:
  • Ze modelleren het probleem als een herhaald niet-coöperatief spel tussen twee rationele nodes.
  • De spelers (nodes) kiezen strategieën bestaande uit een combinatie van data-rate en frame-grootte.
  • Het doel van elke speler is het maximaliseren van de behaalde throughput.
  • Ze analyseren de Nash Equilibriums (NE) en Subgame Perfect Equilibriums (SPE) om te bepalen of rationele spelers zullen afwijken van de meest efficiënte strategie.
• Analyse van Protocollen:
  • DCF: Analyseert hoe het protocol nodes dwingt tot gelijke aantallen frames, wat leidt tot inefficiëntie bij verschillende kanaalcondities.
  • EDCF (Enhanced DCF): Onderzoekt twee varianten:
    1. Backoff upon First Loss (BFL): Een node stopt met zenden na een fout. Dit leidt tot dezelfde inefficiënte evenwichten als DCF.
    2. Backoff at End of Burst (BEB): Een node zendt een volledige burst af, ongeacht fouten. Dit kan leiden tot efficiënte evenwichten, maar is minder robuust bij bursty fouten.
• Simulaties:
  • Uitgevoerd in NS-2 met een Rayleigh fast-fading kanaalmodel om realistische mobiele omstandigheden te simuleren.
  • Gebruik van TCP-flows (in plaats van alleen UDP in de theorie) en het RBAR (Receiver-based Auto-rate) protocol om de resultaten te valideren in een realistischere setting.

3. Belangrijkste Bijdragen

1. Analytisch Bewijs van Inefficiëntie: De auteurs bewijzen wiskundig dat zowel DCF als EDCF (met BFL) onder bepaalde omstandigheden leiden tot unieke Nash-evenwichten die sociaal ongewenst zijn. In deze evenwichten kiezen nodes voor lagere snelheden om meer kanaaltijd te "stelen", wat de totale netwerkefficiëntie verlaagt.
2. Identificatie van de Mechanische Oorzaak: Ze identificeren dat het probleem ligt in de koppeling tussen de toewijzing van transmissiekansen en de transmissiestrategie. Omdat de toewijzing gebaseerd is op kansen (aantal frames) en niet op tijd, hebben nodes een prikkel om de duur van een transmissie te verlengen.
3. Voorstel voor een Ideale MAC: Ze stellen een nieuw MAC-protocolconcept voor dat de toewijzing van de gedeelde resource (kanaaltijd) onafhankelijk maakt van de transmissiestrategie van de individuele node.
   • Kernidee: Garandeer een langdurig aandeel in de kanaaltijd (time-share) in plaats van een aandeel in het aantal transmissies.
   • Implementatie: Dynamisch aanpassen van de contention window (CW) grootte op basis van de waargenomen kanaaltijd-share. Als een node te veel tijd gebruikt (door een lage snelheid), wordt zijn kans op een volgende transmissie verlaagd, zodat de totale tijd-share gelijk blijft.

4. Resultaten

• Theoretische Resultaten:
  • In het DCF-model leidt de unieke Nash-strategie vaak tot het gebruik van een inefficiënte lage snelheid, zelfs als een hogere snelheid voor die node alleen beter zou zijn. De aggregaat-doorvoer daalt hierdoor.
  • Bij EDCF met BFL (Backoff upon First Loss) treden dezelfde inefficiënte evenwichten op.
  • Bij EDCF met BEB (Backoff at End of Burst) kunnen efficiënte evenwichten worden bereikt, maar dit is minder ideaal voor omgevingen met bursty fouten.
• Simulatie Resultaten:
  • Simulaties met TCP en RBAR bevestigen de theorie. In specifieke regio's (bepaalde afstanden tussen zender en ontvanger) kiezen rationele nodes bewust voor een lagere snelheid (bijv. 2 Mbps in plaats van 11 Mbps) om meer throughput te krijgen in een concurrerende setting.
  • Dit gedrag zorgt voor een significante daling van de totale aggregaat-doorvoer van het netwerk.
  • Oplossing: De simulaties tonen aan dat een protocol dat de tijd-share garandeert (door de contention window dynamisch aan te passen), nodes ertoe dwingt de meest efficiënte snelheid te kiezen. In dit scenario is de aggregaat-doorvoer aanzienlijk hoger dan onder standaard DCF.

5. Betekenis en Conclusie

De paper is van groot belang voor het ontwerp van toekomstige draadloze protocollen en de beheersing van WLANs in niet-coöperatieve omgevingen.

• Inzicht: Het toont aan dat "rationeel" gedrag van individuele nodes (het maximaliseren van eigen throughput) kan leiden tot een "tragedy of the commons" waarbij het totale systeem faalt.
• Praktische Implicatie: Bestaande 802.11-standaarden (DCF/EDCF) zijn fundamenteel gebrekkig voor niet-coöperatieve netwerken omdat ze nodes belonen voor inefficiënt gedrag.
• Toekomstperspectief: De auteurs bepleiten een evolutie van het MAC-protocol waarbij de toewijzing van resources gebaseerd is op tijd en niet op kansen. Dit kan worden bereikt door distributieve mechanismen die de contention window aanpassen op basis van waargenomen tijdgebruik.
• Implementatie: Hoewel dit complexer is dan huidige protocollen, is het haalbaar omdat nodes al informatie hebben over kanaalgebruik (via carrier sensing). De auteurs benadrukken dat fabrikanten en gebruikers vaak de data-rate en frame-grootte kunnen aanpassen (via drivers of firmware), maar dat de MAC-standaard zelf moet worden aangepast om deze manipulatie te neutraliseren en efficiëntie te garanderen.

Kortom, de paper concludeert dat zonder een wijziging in het MAC-protocol dat de toewijzing van kanaaltijd koppelt aan de noden in plaats van aan hun strategie, rationele nodes zullen blijven kiezen voor inefficiënte strategieën, wat leidt tot een drastisch verminderde prestatie van het totale draadloze netwerk.