Protocol de rutare a statului de legătură - Link-state routing protocol

Protocoalele de rutare a stării de legătură sunt una dintre cele două clase principale de protocoale de rutare utilizate în rețelele de comutare a pachetelor pentru comunicații computerizate , cealaltă fiind protocoalele de rutare a distanței vectoriale . Exemple de protocoale de rutare a stării de legătură includ Open Shortest Path First (OSPF) și Intermediate System to Intermediate System (IS-IS).

Protocolul de stare a legăturii este realizat de fiecare nod de comutare din rețea (adică, noduri care sunt pregătite pentru redirecționarea pachetelor; în Internet , acestea se numesc routere ). Conceptul de bază al rutei de legătură este că fiecare nod construiește o hartă a conectivității la rețea, sub forma unui grafic , care arată ce noduri sunt conectate la ce alte noduri. Fiecare nod calculează apoi în mod independent următoarea cea mai bună cale logică de la acesta la fiecare destinație posibilă din rețea. Fiecare colecție de cele mai bune căi va forma apoi tabela de rutare a fiecărui nod .

Acest lucru contrastează cu protocoalele de rutare vector-distanță , care funcționează prin faptul că fiecare nod își partajează tabela de rutare cu vecinii săi, într-un protocol de stare de legătură, singura informație transmisă între noduri este legată de conectivitate . Algoritmii de stare de legătură sunt uneori caracterizați informal ca fiecare router, „spunând lumii despre vecinii săi”.

Istorie

Ceea ce se crede a fi prima rețea de rutare adaptivă a computerelor, folosind ca inimă rutare legată de stat, a fost proiectată și implementată în perioada 1976-77 de o echipă din Radar Plessey condusă de Bernard J Harris; proiectul era pentru „Wavell” - un sistem de comandă și control computerizat pentru armata britanică.

Primul concept de rutare a statului de legătură a fost publicat în 1979 de John M. McQuillan (pe atunci la Bolt, Beranek și Newman ) ca un mecanism care ar calcula rute mai rapid atunci când condițiile de rețea s-au schimbat și, astfel, ar duce la o rutare mai stabilă.

Lucrările ulterioare la BBN Technologies au arătat cum să folosim tehnica stării legăturilor într-un sistem ierarhic (adică unul în care rețeaua a fost împărțită în zone), astfel încât fiecare nod de comutare să nu aibă nevoie de o hartă a întregii rețele, doar a zonei ( s) în care este inclus.

Tehnica a fost ulterior adaptată pentru utilizare în protocoalele de rutare IS-IS și OSPF contemporane. Literatura Cisco se referă la protocolul îmbunătățit de rutare a gateway-ului interior (EIGRP) ca protocol „hibrid”, în ciuda faptului că distribuie tabele de rutare în loc de hărți topologice. Cu toate acestea, sincronizează tabelele de rutare la pornire așa cum o face OSPF și trimite actualizări specifice numai atunci când apar modificări de topologie.

În 2004, Radia Perlman a propus utilizarea rutării link-state pentru redirecționarea cadrelor de nivel 2 cu dispozitive numite poduri de rutare sau Rbridges. Internet Engineering Task Force a standardizat interconectarea transparentă a loturilor de link - uri (tril) protocol pentru a realiza acest lucru.

Mai recent, această tehnică ierarhică a fost aplicată rețelelor de rețea fără fir utilizând protocolul de rutare de stare de legătură optimizat (OLSR). În cazul în care o conexiune poate avea o calitate diferită, calitatea unei conexiuni poate fi utilizată pentru a selecta conexiuni mai bune. Aceasta este utilizată în unele protocoale de rutare care utilizează transmisia de frecvență radio.

În 2012, IEEE a finalizat și a aprobat standardizarea utilizării IS-IS pentru a controla redirecționarea Ethernet cu IEEE 802.1aq shortest path bridge (SPB).

Distribuirea hărților

Această descriere acoperă doar cea mai simplă configurație; adică una fără zone, astfel încât toate nodurile să aibă o hartă a întregii rețele. Cazul ierarhic este ceva mai complex; vezi diversele specificații ale protocolului.

După cum s-a menționat anterior, prima etapă principală a algoritmului de stare a legăturii este de a da o hartă a rețelei fiecărui nod. Acest lucru se face cu mai mulți pași subsidiari.

Determinarea vecinilor fiecărui nod

În primul rând, fiecare nod trebuie să determine la ce alte porturi este conectat, prin legături complet funcționale; face acest lucru folosind protocolul de accesibilitate , rulează periodic și separat cu fiecare dintre vecinii săi conectați direct.

Distribuirea informațiilor pentru hartă

Apoi, fiecare nod periodic (și în cazul modificărilor de conectivitate) trimite un mesaj scurt, reclama de stat de legătură , care:

• Identifică nodul care îl produce.
• Identifică toate celelalte noduri (fie routere, fie rețele) la care este conectat direct.
• Include un „număr de secvență”, care crește de fiecare dată când nodul sursă alcătuiește o nouă versiune a mesajului .

Acest mesaj este trimis către toate nodurile unei rețele. Ca un precursor necesar, fiecare nod din rețea își amintește, pentru fiecare dintre vecinii săi , numărul secvenței ultimului mesaj de stare de legătură pe care l-a primit de la acel nod. Când se primește o reclamă de stat de legătură la un nod, nodul caută numărul de secvență pe care l-a stocat pentru sursa acelui mesaj de stare de legătură: dacă acest mesaj este mai nou (adică are un număr de ordine mai mare), acesta este salvat , numărul de ordine este actualizat și o copie este trimisă pe rând la fiecare dintre vecinii acelui nod. Această procedură primește rapid o copie a celei mai recente versiuni a reclamei fiecărui nod la fiecare nod din rețea.

Rețelele care rulează algoritmi de stare a legăturilor pot fi, de asemenea, segmentate în ierarhii care limitează sfera modificărilor rutei. Aceste caracteristici înseamnă că algoritmii de stare a legăturilor se adaptează mai bine la rețele mai mari.

Crearea hărții

În cele din urmă, având în mână setul complet de reclame de stat de legătură (câte unul din fiecare nod din rețea), fiecare nod produce graficul pentru harta rețelei. Algoritmul repetă colecția de reclame de stat de legătură; pentru fiecare, face legături pe harta rețelei, de la nodul care a trimis acel mesaj, la toate nodurile pe care acel mesaj le indică sunt vecine ale nodului de trimitere.

Niciun link nu este considerat raportat corect decât dacă cele două capete sunt de acord; adică, dacă un nod raportează că este conectat la altul, dar celălalt nod nu raportează că este conectat la primul, există o problemă, iar legătura nu este inclusă pe hartă.

Note despre această etapă

Mesajul statului de legătură care oferă informații despre vecini este recalculat și apoi inundat în întreaga rețea, ori de câte ori există o schimbare a conectivității dintre nod și vecinii săi; de exemplu, atunci când un link eșuează. Orice astfel de modificare va fi detectată de protocolul de accesibilitate pe care fiecare nod îl rulează cu vecinii săi.

Calculul tabelei de rutare

Așa cum s-a menționat inițial, a doua etapă principală în algoritmul stării de legătură este producerea de tabele de rutare, prin inspectarea hărților. Acest lucru se face din nou cu mai mulți pași.

Calculul celor mai scurte căi

Fiecare nod rulează independent un algoritm peste hartă pentru a determina cea mai scurtă cale de la sine la fiecare alt nod din rețea; în general se folosește o variantă a algoritmului lui Dijkstra . Aceasta se bazează pe un cost al legăturii pe fiecare cale, care include lățimea de bandă disponibilă, printre altele.

Un nod menține două structuri de date: un arbore care conține noduri care sunt „terminate” și o listă de candidați . Algoritmul începe cu ambele structuri goale; apoi adaugă la primul nodul însuși. Varianta unui algoritm Greedy face apoi în mod repetat următoarele:

• Toate nodurile vecine care sunt conectate direct la nod sunt doar adăugate în arbore (cu excepția oricăror noduri care sunt deja fie în arbore, fie în lista de candidați). Restul sunt adăugate la a doua listă (candidat).
• Fiecare nod din lista de candidați este comparat cu fiecare dintre nodurile deja în arbore. Nodul candidat care este cel mai apropiat de oricare dintre nodurile deja în copac este el însuși mutat în copac și atașat la nodul vecin corespunzător. Când un nod este mutat din lista de candidați în arbore, acesta este eliminat din lista de candidați și nu este luat în considerare în iterațiile ulterioare ale algoritmului.

Cei doi pași de mai sus se repetă atâta timp cât au mai rămas noduri în lista de candidați. (Atunci când nu există niciunul, toate nodurile din rețea vor fi adăugate în arborele.) Această procedură se încheie cu arborele care conține toate nodurile din rețea, cu nodul pe care rulează algoritmul ca rădăcină a arborelui . Cea mai scurtă cale de la acel nod la orice alt nod este indicată de lista nodurilor pe care le parcurgeți pentru a ajunge de la rădăcina arborelui, până la nodul dorit din arbore ..!

Umplerea mesei de rutare

Cu cele mai scurte căi în mână, următorul pas este completarea tabelului de rutare. Pentru orice nod de destinație dat, cea mai bună cale pentru această destinație este nodul care este primul pas de la nodul rădăcină, în josul ramurii din arborele cu cea mai scurtă cale care duce spre nodul de destinație dorit. Pentru a crea tabela de rutare, este necesar doar să parcurgeți copacul, amintindu-vă de identitatea nodului din capul fiecărei ramuri și completând intrarea tabelei de rutare pentru fiecare nod pe care îl întâlniți cu identitatea respectivă.

Optimizări ale algoritmului

Algoritmul descris mai sus a fost făcut cât mai simplu posibil, pentru a facilita înțelegerea. În practică, există o serie de optimizări care sunt utilizate.

Recomputație parțială

Ori de câte ori se întâmplă o modificare a hărții de conectivitate, este necesar să recomputați arborele cu cea mai scurtă cale și apoi să recreați tabelul de rutare. Lucrările BBN Technologies au descoperit cum să se recompute doar acea parte a copacului care ar fi putut fi afectată de o modificare dată a hărții. De asemenea, tabelul de rutare ar fi completat în mod normal pe măsură ce se calculează arborele cu cea mai scurtă cale, în loc să o facă o operație separată.

Reducerea topologiei

În unele cazuri, este rezonabil să reduceți numărul de noduri care generează mesaje LSA. De exemplu, un nod care are o singură conexiune la graficul de rețea nu trebuie să trimită mesaje LSA, deoarece informațiile despre existența sa ar putea fi deja incluse în mesajul LSA al singurului său vecin. Din acest motiv poate fi aplicată o strategie de reducere a topologiei, în care doar un subset de noduri de rețea generează mesaje LSA. Două abordări studiate pe scară largă pentru reducerea topologiei sunt:

1. Relee MultiPoint care se află la baza protocolului OLSR , dar au fost, de asemenea, propuse pentru OSPF
2. Seturi dominante conectate care au fost din nou propuse pentru OSPF

Rutare de stat Fisheye

Cu FSR , LSA sunt trimise cu valori TTL diferite pentru a restricționa difuzarea acestora și a limita cheltuielile generale datorate mesajelor de control. Același concept este utilizat și în Protocolul de rutare a statului legăturii nevăzute .

Moduri de eșec

Dacă toate nodurile nu funcționează exact din aceeași hartă, se pot forma bucle de rutare . Acestea sunt situații în care, în cea mai simplă formă, două noduri vecine consideră că celălalt este cel mai bun drum către o anumită destinație. Orice pachet îndreptat către acea destinație care ajunge la oricare dintre noduri va face o buclă între cele două, de unde și numele. Sunt posibile și bucle de rutare care implică mai mult de două noduri.

Acest lucru se poate întâmpla deoarece fiecare nod calculează arborele cu cea mai scurtă cale și tabelul său de rutare fără a interacționa în niciun fel cu alte noduri. Dacă două noduri încep cu hărți diferite, este posibil să existe scenarii în care sunt create bucle de rutare. În anumite circumstanțe, buclele diferențiale pot fi activate într-un mediu multi cloud. Nodurile de acces variabil din protocolul de interfață pot ocoli problema simultană a nodului de acces.

Protocolul de rutare a statului de legătură optimizat pentru rețelele mobile ad hoc

Optimized Link Stat Protocolul de rutare (OLSR) este un protocol de rutare link-stat optimizat pentru rețele mobile ad - hoc (care pot fi , de asemenea , folosite în alte rețele fără fir ad - hoc ). OLSR este proactiv, folosește mesaje Hello și Topology Control (TC) pentru a descoperi și disemina informații despre starea legăturilor în rețeaua mobilă ad hoc . Folosind mesaje Hello fiecare nod descoperă informații cu 2-hop vecini și alege un set de relee multipunct (MPR). MPR-urile fac OLSR unic din alte protocoale de rutare a stării de legătură. Nodurile individuale folosesc informațiile topologiei pentru a calcula urmatoarele căi de salt referitoare la toate nodurile din rețea folosind cele mai scurte căi de redirecționare a hopului.

Vezi si

• 802.1aq Cea mai scurtă punte de cale

Referințe

• Josh Seeger și Atul Khanna, Reducing Routing Overhead într-un DDN în creștere , MILCOMM '86, IEEE, 1986
• Radia Perlman „Rbridges: Transparent Routing” , Infocom 2004.

Lecturi suplimentare

• Secțiunea „Link-State Versus Distance Vector” în capitolul „Routing Basics” din „ Cisco Internet Handbook Technology Handbook”