B.A.T.M.A.N. III (Introducere) (

B.A.T.M.A.N. este un protocol de rutare proactiv pentru rețelele wireless Ad-hoc Mesh, inclusiv (dar nu limitat la) rețelele mobile ad-hoc (MANET). Protocolul menține în mod proactiv informații despre existența tuturor nodurilor din mesh care sunt accesibile prin legături de comunicație cu un singur hop sau multi-hop. Strategia B.A.T.M.A.N. este de a determina pentru fiecare destinație din mesh un vecin cu un singur hop, care poate fi utilizat ca cel mai bun gateway pentru a comunica cu nodul de destinație. Pentru a efectua rutare bazată pe IP multi-hop, tabela de rutare a unui nod trebuie să conțină o poartă de legătură locală pentru fiecare gazdă sau rută de rețea. Pentru a afla despre cel mai bun next-hop pentru fiecare destinație este tot ceea ce B.A.T.M.A.N. algoritmului îi pasă. Nu este nevoie să aflați sau să calculați ruta completă, ceea ce face posibilă o implementare foarte rapidă și eficientă.

către nodul

B.A.T.M.A.N. III (Scurtă prezentare generală) (

B.A.T.M.A.N. IV (TQ) (

B.A.T.M.A.N. Algoritmul III are probleme serioase când vine vorba de legături asimetrice. Verificarea legăturii bidirecționale încearcă să-și limiteze impactul, dar rezultatul este departe de a fi perfect. Perioada în care B.A.T.M.A.N. acceptă propriile OGM-uri, retransmise de către vecin, permite modificarea comportamentului. Dacă acest interval de timp este destul de scurt, B.A.T.M.A.N. este foarte strict în alegerea linkurilor. Acest lucru poate duce la multe linkuri ignorate care ar putea fi utilizate într-o singură direcție. Se vor lua în considerare doar conexiunile simetrice. Dacă valoarea intervalului de timp este mai puțin strictă B.A.T.M.A.N. va accepta mai multe legături, dar tinde să direcționeze în direcția greșită.

Exemplu: OGM-urile din nodul A se propagă către B. Legătura este asimetrică, prin urmare B primește toate pachetele de la A spre deosebire de A care nu primește aproape nimic de la B. Pe măsură ce toate pachetele de la A ajung la B, numărul pachetelor de pe partea lui B crește . B va presupune că are o legătură perfectă către A ceea ce nu este cazul.

Pentru a depăși acest defect B.A.T.M.A.N. IV a fost îmbunătățit cu algoritmul Transmit Quality (TQ). Următoarele secțiuni vor descrie designul său și modul în care consolidează capacitățile de rutare ale B.A.T.M.A.N. în medii asimetrice.

B.A.T.M.A.N. IV Formatul mesajului inițiator¶

00 01 02 03
00-03 Versiune Steaguri TTL Steaguri GW
04-07 Număr de secvență Portul GW
08-11 Adresa inițiatorului
11-15 Adresa expeditorului anterior
16-19 TQ Lungimea HNA ()

Tabel: B.A.T.M.A.N. IV (Layer 3) Format pachet

Calitatea Transmitere¶

B.A.T.M.A.N. IV împarte o anumită calitate a legăturii în 2 părți distincte: primirea calității legăturii și transmiterea calității legăturii. Calitatea legăturii de recepție exprimă probabilitatea unei transmisii de pachete de succes către nod. Calitatea legăturii de transmisie descrie probabilitatea unei transmisii reușite către un nod vecin. Evident, B.A.T.M.A.N. este mai interesat de calitatea legăturii de transmisie, deoarece calitatea legăturii de recepție nu poate fi utilizată pentru a influența decizia de rutare.

După cum sa explicat în secțiunea anterioară, numărarea pachetelor inundă rețeaua cu o calitate a legăturii primitoare, mai degrabă decât cu o calitate a legăturii de transmisie. La nivel de legătură locală, calitatea legăturii de transmisie poate fi derivată din calitatea legăturii de recepție prin aplicarea unor calcule asupra numărului de pachete.

B.A.T.M.A.N. cunoaște calitatea legăturii de primire (RQ) prin numărarea pachetelor vecinilor săi.

B.A.T.M.A.N. cunoaște calitatea legăturii de ecou (EQ) prin numărarea retransmisiunilor propriilor OGM de la vecinii săi.

B.A.T.M.A.N. poate calcula calitatea legăturii de transmisie (TQ) prin împărțirea calității legăturii de ecou la calitatea legăturii de recepție.

Acest lucru arată că B.A.T.M.A.N. IV este capabil să calculeze calitatea de transmisie locală utilizând aceleași mecanisme ca și B.A.T.M.A.N. III fără a adăuga alte cheltuieli generale.

Transmite propagarea calității¶

Calitatea legăturilor locale trebuie să fie propagată în întreaga rețea pentru a informa alte noduri despre calitatea transmisiei. Prin urmare B.A.TM.A.N. IV introduce un nou câmp numit „TQ” care are o lungime de 1 octet. Acest câmp este adăugat la cunoscutul B.A.T.M.A.N. Pachetul III. Ori de câte ori este generat OGM, acest câmp este setat la lungimea maximă (255) înainte de a fi difuzat. Vecinul primitor își va calcula propria calitate a legăturii locale în valoarea TQ primită și va retransmite pachetul. Prin urmare, fiecare nod care primește un pachet știe despre calitatea transmisiei către nodul inițiator.

Pentru a adăuga calitatea linkului local în valoarea TQ, se efectuează următorul calcul:

Exemplu: Nodul A transmite pachetul cu TQ max. Nodul B îl primește, aplică calculul TQ și îl retransmite. Când nodul C primește pachetul, știe despre calitatea transmisiei către nodul A.

B.A.T.M.A.N. IV nu poate retransmite întotdeauna noul TQ calculat care a venit cu cel mai recent OGM. În schimb, TQ-ul care a fost primit prin cel mai bun vecin este redifuzat pentru a sprijini mai bine scenariile de legături asimetrice.

Exemplu: Nodul A și B sunt vecini. Nodul A are o conexiune bună cu nodul B, dar nu invers. Nodul C are o conexiune bună cu nodul A și o conexiune defectă înapoi, iar C are o calitate bună a legăturii de recepție și o calitate de trimitere proastă către B.

Datorită acestui aspect, mesajele inițiatorului de la nodul A au șanse mari să ajungă la B, dar valoarea TQ propagată de nodul B este foarte mică datorită pierderii mari de pachete către nodul A. Mesajele de la nodul A care călătoresc prin nodul C au o probabilitate redusă de a ajunge la nodul B datorită pierderii de pachete către nodul B, dar au o valoare TQ mult mai bună. Nodul B va propaga multe mesaje cu o valoare TQ scăzută (primite direct de la nodul A) și câteva mesaje cu o valoare TQ ridicată (primite de la nodul A prin nodul C), deși conexiunea către nodul A este foarte bună.

Prin urmare, B.A.T.M.A.N. IV va retransmite OGM-ul primit cu valoarea TQ a celui mai bun vecin către inițiator. În exemplul dat, nodul B va plasa valoarea TQ primită prin nodul C în mesajul de la nodul A înainte de a-l retransmite. Va inunda doar cel mai bun TQ.

TQ local vs TQ global¶

Un B.A.T.M.A.N. Nodul IV trebuie să țină evidența a 2 valori TQ diferite:

  1. TQ local care reprezintă calitatea transmisiei către fiecare vecin de hop (recuperat prin numărul de pachete plus calculul TQ).
  2. Calitatea link-ului global care descrie calitatea link-ului către fiecare vecin multi hop (primit prin pachete B.A.T.M.A.N. IV).

Calculul pentru TQ-ul local necesită numărul de pachete OGM al vecinului și numărul de pachete OGM propriu redifuzat chiar de acel vecin. Prin urmare, un B.A.T.M.A.N. nodul urmărește pachetele primite pe un anumit interval. Dimensiunea ferestrei de glisare a acestor statistici se numește TQ_LOCAL_WINDOW_SIZE.

TQ global este o medie a tuturor valorilor TQ primite de la un inițiator prin intermediul unui vecin distinct. Pachetele cu o valoare TQ de 0 se consideră, de asemenea, ca pachete nerecepționate. B.A.T.M.A.N. IV folosește dimensiunea ferestrei glisante TQ_GLOBAL_WINDOW_SIZE mai mare de 1 pentru a medie TQ.

Manipularea legăturilor asimetrice¶

Deși calitatea legăturii de transmisie este cel mai important factor de decizie B.A.T.M.A.N. IV ține, de asemenea, evidența calității linkului de recepție. Pe stratul WiFi, fiecare pachet unicast trebuie confirmat de către nodul vecin pentru a aproba transmisia. Dacă acest vecin nu este capabil să-și trimită cu succes ACK-urile, stratul WiFi consideră că această transmisie eșuează și încearcă să retransmită până când renunță.

Astfel B.A.T.M.A.N. IV trebuie să penalizeze link-urile care au o calitate slabă a linkului de primire. Pentru a evita o simplă histerezis care activează sau dezactivează complet un link, B.A.T.M.A.N. IV folosește funcția

pentru a cântări penalizarea pentru calitatea linkului de primire. După cum este vizibil în graficul de mai jos, pierderea de pachete mici va influența ratingul legăturii doar puțin, în timp ce pierderea imensă de pachete va avea în continuare o influență severă.

Această valoare obținută este înmulțită pe TQ înainte de a fi retransmisă. Nodurile vecine pot pondera decizia de rutare pe baza acestor informații. În unele situații, legătura slabă este singura legătură disponibilă, deci doriți să o utilizați, în timp ce în alte cazuri pot exista conexiuni mai bune.

Eliminarea ecoului¶

B.A.T.M.A.N. IV slăbește politica strictă de eliminare a pachetelor folosită de B.A.T.M.A.N. III pentru a face ca algoritmul TQ să funcționeze. B.A.T.M.A.N. IV verifică numerele de secvență necunoscute prin intermediul unui vecin specific, în timp ce B.A.T.M.A.N. III verifică numerele de secvență cunoscute. Dacă această combinație este „nouă”, OGM va fi acceptat, procesat și retransmis. Acest lucru poate duplica informațiile cunoscute atunci când mesajul „revine” din cauza retransmisiei (așa-numitele ecouri). În zonele dense, fără pierderi mari de pachete, acest lucru duce la creșterea lățimii de bandă și a utilizării procesorului.

Exemplu: 3 noduri (A, B și C) la rând (A poate auzi B dar nu C). Nodul A emite un OGM, Nodul B îl aude și îl retransmite. Difuzarea de la nodul B ajunge la A și C. Nodul A va renunța la mesajul pe măsură ce A detectează că a fost inițiatorul acestui OGM. C va procesa și retransmite mesajul. Nodul B va primi chiar OGM-ul pe care l-a trimis înainte și va retransmite fericit din nou (ecoul propriului mesaj), deoarece B nu poate detecta că a difuzat mesajul înainte.

Pentru a detecta ecouri (mesaje care au trecut deja printr-un nod) B.A.T.M.A.N. IV introduce un nou câmp de protocol numit „expeditor anterior” care conține adresa IP a nodului care retransmite OGM. Ori de câte ori un nod primește un mesaj de la un vecin, acesta va umple câmpul „expeditor anterior” cu adresa vecinului expeditor înainte de a-l retransmite. Dacă un nod își detectează propria adresă IP în câmpul „expeditor anterior”, pachetul va fi ignorat.

Înapoi la exemplu: Nodul B va ignora (arunca) pachetul care revine din nodul C, deoarece nodul C a scris adresa IP a nodului B în câmpul „expeditor anterior”.

Chiar și în scenarii mai sofisticate cu mai multe noduri/hamei, acest concept reduce cu succes pachetele. Se asigură că pachetul parcurge numai căi care nu vedeau acest OGM înainte.

Sanctiune Hop

Până în prezent, B.A.T.M.A.N. IV se concentrează numai pe calitatea legăturii pentru a evalua căile, dar nu pe numărul de hamei din cale, deoarece nu știe topologia dincolo de orizontul său. În anumite setări de rețea, calitatea legăturilor vecinilor este foarte similară, în timp ce numărul de hamei nu este. În aceste scenarii, este foarte de dorit să alegeți calea cea mai scurtă pentru a reduce latența și pentru a asigura lățimea de bandă sigură (pe mediile wireless). Următoarea secțiune va ilustra problema și modul în care va fi abordată folosind o rețea Ethernet ca exemplu, din motive de simplitate. WiFi și alte medii sunt mai puțin sensibile ca Ethernet, dar sunt încă afectate.

Exemplu: nodurile A, B și C care sunt conectate la un comutator de rețea. Nodul A generează primul mesaj care este primit, procesat și retransmis de către B imediat. Să presupunem că retransmisia de la nodul B ajunge la nodul C înainte de sosirea mesajului de la nodul A. Deoarece calitatea legăturii este aceeași și perfectă (în acest exemplu) Nodul C își asumă o cale spre nodul A prin nodul B.

Pentru a depăși această problemă B.A.T.M.A.N. IV introduce o penalizare hop: de fiecare dată când un OGM trece un nod, valoarea TQ va fi redusă cu o valoare fixă, indiferent de penalizarea legăturii asimetrice înainte de a retransmite pachetul. În exemplul dat, scade valoarea rutei prin nodul B și favorizează conexiunea directă. [imagine2 penalizare]

Agregare de pachete¶

În zonele nodulare dense cu pierderi reduse de pachete B.A.T.M.A.N. III generează destul de multe pachete, ceea ce crește probabilitatea de coliziune, pierde timpul de aer și provoacă o încărcare mai mare a procesorului. Fiecare OGM fiind de 20 de octeți mic, B.A.T.M.A.N. IV introduce o agregare de pachete care combină mai multe OGM distincte într-un singur pachet. Pentru a realiza acest lucru, B.A.T.M.A.N. IV reține pachetele care urmează să fie trimise și așteaptă ca pachetele primite să le adauge înainte de a difuza pachetul unic agregat.

Fiecare OGM este format din B.A.T.M.A.N. Antet IV (vezi: formatul mesajului inițiator) plus partea dinamică a mesajului HNA.

00 01 02 03
00-03 Adresa HNA
04-07 Mască de rețea

Tabel: Format mesaj HNA (Layer 3)

B.A.T.M.A.N. IV permite să nu adăugați niciun mesaj, unul sau mai multe mesaje HNA. Deoarece fiecare OGM poate transporta mai multe informații HNA, este necesar să stocați numărul de mesaje HNA în câmpul de lungime HNA nou creat.

00 01 02 03
00-03 Versiune Steaguri TTL Steaguri GW
04-07 Număr de secvență Portul GW
08-11 Adresa inițiatorului
11-15 Adresa expeditorului anterior
16-19 TQ Lungimea HNA = 2 Adresa HNA nr. 1
20-23 Adresa HNA # 1 (continuare) Subnetmask # 1 Adresa HNA # 2
24-27 Adresa HNA # 2 (continuare) Subnetmask # 2
28-31 următorul B.A.T.M.A.N. Antet IV

Tabel: Exemplu B.A.T.M.A.N. IV (Stratul 3) Pachet agregat

Interfețe multiple¶

Pentru a sprijini nodurile cu mai multe interfețe de rețea Б.А.Т.М.А.Н. trebuie să detecteze ce legătură se conectează la ce interfață. Deoarece fiecare pachet de intrare este redifuzat prin toate interfețele existente B.A.T.M.A.N. IV trebuie să utilizeze un flag (link direct flag) pentru a distinge între conexiuni reale și retransmisiuni.

Procesul de detectare: nodul A emite un OGM fără semnalizări activate. Vecinul B primește mesajul și verifică dacă adresa expeditorului UDP și adresa inițiatorului sunt egale. În acest caz, va retransmite OGM cu semnalizatorul de legătură directă activat, altfel semnalizatoarele nu vor fi modificate. Odată ce nodul A primește această retransmisie a propriului său OGM, acesta recunoaște acest vecin ca un vecin cu un singur hop datorită semnalizatorului de legătură directă existent. Dacă nodul A a primit acest pachet prin aceeași interfață a fost trimis (adresa interfeței de intrare este egală cu adresa inițiatorului) nodul A va accepta acest pachet și va crește numărul de pachete Echo Quality (EQ). Este ignorat altfel.

Exemple: Nodul A are 2 interfețe și transmite OGM-ul unei interfețe pe ambele interfețe pentru ao face cunoscut în cloud mesh. Nodul B are, de asemenea, 2 interfețe și primește această transmisie prin ambele. OGM care a apărut prin interfața căreia îi aparține este acceptat de altul ignorat (pentru detecția ulterioară a interfeței).

Nodul B va retransmite mesajul și pe ambele interfețe, dar va seta doar semnalizatorul interfeței de legătură directă pe pachetul care părăsește nodul prin interfața în care a intrat mesajul. Nodul A va ignora pachetul fără semnalizatorul de legătură directă și numără doar OGM-ul care vine prin interfața pe care a lăsat-o în primul rând.