Principii și algoritmi de rutare în Internet

4. Principii și algoritmi de rutare pentru Internet

4.1. rutare problemă pe Internet

Algoritmul de rutare este fundația pe care toată activitatea rețelei centrale cu arhitectura TCP / IP. Furnizarea de servicii de rețea de încredere necesită o anumită dinamică de rutare. Schimbări neașteptate în conectivitatea de rețea de bază ar trebui să fie considerate ca fenomen normal și manipulate în mod corespunzător, precum și supraîncărcarea zonelor individuale și canale.

Există o serie de cerințe care trebuie să fie luate în considerare atunci când se alege un algoritm de rutare adecvat:
· Algoritmul de rutare ar trebui să recunoască eșecul și recuperarea canalelor de comunicare sau alte IP-routere și de a comuta la alte căi adecvate. traseu timp de comutare trebuie să fie mai mică decât protocolul TCP tipic timeout utilizator (aproximativ 1 minut);
· Algoritmul ar trebui să excludă formarea ciclurilor, buclele și efectul de „ping-pong“ în rutele prescrise între învecinate IP routere și la distanță pentru IP-routere. Existența efectelor de mai sus nu trebuie să depășească protocolul TCP tipic timeout utilizator (aproximativ 1 minut);
· Incarcarea mesajelor de control care sunt necesare pentru algoritmul de rutare nu trebuie să se degradeze în mod semnificativ sau împiedică funcționarea normală a rețelei. Schimbarea stării rețelei, care poate întrerupe funcționarea normală într-o rețea locală, nu trebuie să afecteze site-urile de la distanță;
· Deoarece dimensiunea rețelei este în continuă creștere, este necesar să se asigure utilizarea eficientă a resurselor de rețea, cum ar fi schimbarea rutelor de matrici pentru a efectua în parte, trecând pe rețelele globale este doar un supliment la baza de date de rutare;
· Dimensiunea de rutare de bază de date nu trebuie să depășească o anumită constantă care nu depinde de topologia rețelei, înmulțită cu numărul de noduri și conectivitatea medie a rețelei. O bună punere în aplicare nu trebuie să necesite stocare de date complete de rutare în fiecare IP-router;
· Dacă utilizați o măsurătoare bazată pe o gazdă este accesibil și întârzierea în livrarea pachetului, acestea nu ar trebui să depindă de conectivitate directă cu toate celelalte routere bazate pe IP sau de a folosi mecanisme de difuzare care sunt specifice pentru anumite rețele. Procedurile de interogare nu ar trebui să facă cheltuieli suplimentare semnificative;
· Traseele implicite trebuie utilizate ca ipotezele inițiale privind rutarea la final și apoi alegeți direcția de transmisie.

În plus față de sarcinile de mai sus IP router trebuie să asigure distribuția eficientă a resurselor proprii, atât în ​​calitate de canal, și volumul de memorie tampon folosit pentru a stoca pachete care așteaptă să fie transmise. Cea mai evidentă strategie de „primul venit - primul servit» (FCFS - primul venit primul servit) pot fi inacceptabile în ceea ce privește congestionarea rețelei.

De exemplu, este de neconceput ca un canal de mare viteză pentru a capta întregul volum al memoriei tampon, lăsând nimic pentru a încetini conexiunea. Într-un algoritm bun trebuie să ia în considerare „serviciu de tip“ IP header-pachet; IP-router poate atribui o prioritate mai mare pentru IP-pachet transmis de către conducere sau informații proprietare.

În cele din urmă, algoritmul de rutare trebuie să furnizeze un algoritm de încredere pentru determinarea stării fiecărui nod și link-ul în rețeaua de bază și, dacă este necesar, starea computerului gazdă.
Acest lucru necesită, cel puțin, se leagă protocolul de strat care implică un schimb periodic de personal prin fiecare canal de comunicare.
Cu toate acestea, acest lucru este de multe ori nu este suficient, astfel încât în ​​plus necesită un mecanism special în algoritmii de rutare.
Din motive tehnice, administrative, geografice, politice și, uneori, IP-routere sunt grupate în așa-numitele „sisteme autonome“.
IP-routere incluse într-un singur sistem autonom controlat de o singură companie, oferind întreținerea acestora, și folosite pentru acest sistem de rutare generale algoritmi autonome.

Definiția. Un exemplu particular de realizare a protocolului de rutare, care funcționează într-un sistem autonom se numește un protocol de rutare intern (IGP - Interior Gateway Protocol).

Este posibil ca unele IP-pachete pentru a ajunge la destinație, va trebui să treacă prin IP - routerele de două sau mai multe sisteme autonome. Prin urmare, sistemele autonome ar trebui să poată să facă schimb de informații cu privire la starea lor.

Definiția. Protocolul pentru schimbul de informații oficiale între sistemele autonome sunt numite protocol de gateway-ul exterior (EGP - Exterior Gateway Protocol).

Fiecare IP-ruter trebuie să asigure punerea în aplicare a protocoalelor protocoalelor, link-ul de date, nivelul de rețea și de acces la rețea fizică. Deoarece ultimele protocoale Ethernet folosite, Frame Relay, ATM, SLIP, PPP, și multe altele, și la rețea cu X.25 / 2 Arhitectura protocol ISO (LAP-B).
În plus, IP-router este necesară pentru a pune în aplicare un algoritm pentru tabela de rutare de selecție traseu, precum și algoritmul de actualizare.

Există algoritmi statice și dinamice se actualizeze tabelul.

Gateway-urile care fac parte dintr-un sistem autonom poate efectua algoritm de rutare dinamic - protocoale bazate pe algoritmul Bellman-Ford și protocoale bazate pe algoritmul Dijkstra.
Fiecare arc a graficului este atribuit un număr real, numit lungimea arcului; atunci lungimea traseului este suma lungimilor muchiilor sale constitutive.
De obicei acest număr perepriomov sau întârziere medie de pachete, dar alte valori, de exemplu, capacitatea canalului de comunicare, fiabilitate.

Gateway-uri care rulează pe algoritmul Bellman-Ford. lungimi vector magazin de trasee mai scurte pentru toate rețelele care fac parte dintr-o rețea. unite
Periodic fiecare Gateway transferă vectorul sistemului autonom învecinat gateway-uri și elemente vectoriale, preluate dintr-o poartă de acces din apropiere, constau din lungimi de linii de ieșire.
Pe baza tabelului rezultat este construit un nou vector de lungimi mai scurte rute - Ford algoritmul Bellman (DV - algoritmul Distanța Vector).
Protocoale bazate pe DV-algoritm pur și simplu puse în aplicare, necesită puțină memorie și timp de procesor, cu toate acestea, ele au o serie de dezavantaje. Atunci când numărul de rețele care alcătuiesc sistemul autonom crește dramatic cantitatea de informații transmise, din moment ce DV-algoritm impune ca toate gateway-urile transmit periodic rutele sale de lungime vector.

Gateway-uri, care lucrează sub algoritmul Dijkstra (calea cea mai scurtă întâi - SPF-algoritm), se determină mai întâi cele mai scurte rute către toate rețelele de sistem autonom. În acest scop, fiecare poarta de acces este construit complet copac calea cea mai scurtă înrădăcinat la această poartă.
Procedura pentru construirea cea mai scurtă cale de copac folosește principiul că, în primul copac dintre cele mai scurte trasee incluse lungimea arcului cu cea mai mică, astfel încât algoritmul Dijkstra este adesea numit primul calea cea mai scurtă.
Odată ce gateway-a construit drumul minim, modificări ale caracteristicilor liniilor de comunicație, determinarea lungimilor arcelor respective, modificările topologie de rețea ca rezultat mic calcul suplimentar pentru corectarea drumul minim.
Gateways face schimb doar informații despre lungimile liniilor de ieșire, mai degrabă decât lungimea vectorului de rute, ca și în cazul algoritmului Bellman-Ford. pachete de corecție Dimensiune cu informații de serviciu pentru rutare este mică și nu depinde de numărul de rețele în sistemul autonom. Fiecare poarta de acces trimite aceste pachete prin inundații. Când vă aflați într-o nouă poartă de acces pentru rețea sau de a introduce o nouă linie de schimbări de comunicare în topologia rețelei nu sunt luate în considerare atunci când rutare de ceva timp pentru a se asigura că informațiile despre schimbările care au avut loc au avut timp pentru a ajunge la toate gateway-urile unui sistem autonom.

În general, algoritmul lui Dijkstra comparativ cu algoritmul Bellman-Ford oferă o evaluare mai realistă a situației în rețea, un răspuns mai rapid la schimbări importante în rețea (cum ar fi includerea noului link) și reduce de pachete de looping; Algoritmul lui Dijkstra, dar mai dificil de implementat și necesită de multe ori mai multă memorie.

4.2. Gateway Protocol interior

În conformitate cu protocolul GGP (Gateway to Gateway Protocol, RFC 823), a fost elaborat și implementat de BBN pentru prima Internet gateway-ul experimental.
El este încă folosit în gateway-urile societății BBN LSI / 11, deși se crede că GGP are defecte serioase și mai târziu a fost înlocuit cu un SPF algoritm.
GGP algoritm de protocol determină traseul cu numărul perepriomov minim, și anume este pur și simplu o măsură a lungimii numărului de secțiuni de rețea de tranzit între perechi de gateway-uri.
Se pune în aplicare un algoritm distribuit pentru calea cea mai scurtă, care necesită o convergență globală tabelelor de rutare după modificări topologie sau conectivitate.

Protocolul RIP (Routing Information Protocol, RFC 1058, 1581, 1582, 1724) este adesea folosit pentru o clasă de protocoale de rutare bazate pe protocolul XNS (Xerox Network System - Xerox Network System) companie Xerox.
Punerea în aplicare a RIP pentru familia protocolul TCP / IP este disponibil pe scară largă, ca parte a software-ului sistemului de operare UNIX, de exemplu, FreeBSD sau Linux. Datorită simplității sale, protocolul RIP este cel mai probabil să se transforme într-un »protocol„deschis IGP, și anume, un protocol care poate fi utilizat pentru gateway-uri de colaborare furnizate de diferite firme.
Ca de rutare RIP valori utilizând numărul de salturi (pași) la țintă. Acest tip de valoare nu ține cont de diferențele de lățime de bandă sau congestie segmente de rețea separate.
Fiecare traseu este asociat cu un temporizator time-out și un „colector de gunoi“. timer timeout este resetat de fiecare dată când o rută este inițializată sau corectată. Dacă de la ultima ajustare a durat 3 minute și a primit un mesaj că vectorul distanță este de 16, traseul este considerat a fi închis, dar despre aceasta poveste nu este șters până la expirarea timpului afară „de colectare a gunoiului“ (2 minute). Trecerea nu se produce odată cu apariția unui traseu echivalent.
RIP este destul de simplu, dar nu lipsită de dezavantaje:
- este nevoie de o lungă perioadă de timp pentru a restabili conexiunea după un eșec în router (minute); în procesul de stabilire a modurilor sunt disponibile cicluri;
- numărul de pași - un important, dar nu singurul parametru al traseului, iar cei 15 pași - nu limita pentru rețelele de astăzi.

"HELLO" protocol. Software Fuzzball pentru LSI / poartă de acces 11 include punerea în aplicare a unui IGP numit „HELLO“. Spre deosebire de RIP există criteriul de selecție traseu este timpul, nu distanța, astfel încât „HELLO“ necesită o investiție suficient de precise timp de servicii de sincronizare gateway.

IS-IS protocol. Având în vedere, pe de o parte, TCP arhitectura de rețea pe scară largă / IP, pe de altă parte, atenția guvernului și comerciale organizații pentru arhitectura EMVOS; Se așteaptă ca / ​​arhitectura IP TCP si EMVOS va exista pentru o lungă perioadă de timp împreună. Prin urmare, este nevoie de un gateway care poate ruta atât IP- și EMVOS de trafic.
Protocolul IS-IS (Intermediar Sistem la Intermediarul protocol System, RFC 1195) oferă concepte suport de IP-subrețea, variabila masca de subrețea, rutare bazată pe valoarea câmpului „tip de serviciu“ în pachetul de IP-antet și noțiunea unei rute externe.
IS-IS este un protocol dinamic de rutare construit pe partea de sus a SPF-algoritm.

4.3. Gateway Protocol exterior

protocoale de rutare exterioare sunt proiectate în primul rând pentru comunicarea între sistemele autonome (independente).

Protocol EGP (Exterior Gateway Protocol) este una dintre cele mai cunoscute protocoale de acest tip (RFC 827, 888, 904, 911, 1092, 1093).
RFC document de 827, a propus primul model de gateway pentru a interacționa cu gateway-uri la alte sisteme autonome, și documentul RFC 888, care este o dezvoltare a acestui model, impune limitări substanțiale asupra topologiei rețelei de Internet, presupunând un copac structură pe două niveluri, rădăcina care este așa-numita „coloana vertebrală“ sistem autonom constând din „principale“ gateway-uri.
Principalul avantaj al unui astfel de model de educație este considerată imposibilă într-o structură topologică arbore al unui traseu ciclic între sisteme autonome.

Cu EGP gateway protocol pot furniza reciproc informații despre accesibilități de gateway-uri și gateway învecinate pentru rutele adiacente. În acest calcul traseu dinamic se realizează numai gateway-uri sistem autonom coloana vertebrală, și gateway-uri nontrunk, atunci rezultatele pot fi comunicate.
Non-Trunk Gateways poate oferi, de asemenea, de dirijare a informațiilor și gateway-uri nontrunk, dar nu au nici un drept să treacă pe rutele sunt calculate pe baza informațiilor primite de la alte gateway-uri. Această limitare este adesea numit o restricție privind diseminarea „treilea grup“.
Protocolul EGP include un mecanism de determinare a vecinilor de accesibilitate (numite gateway-uri vecine, care operează în comun protocolul EGP) de control și accesibilități schimbul de informații sub forma unui mesaj de actualizare. Scopul folosind algoritmul accesibilități - asigurați-vă că un vecin este de lucru și poate furniza informații fiabile.
Nu mai puțin important este sarcina de filtrarea informațiilor înainte de a trimite-l la alte gateway-uri pentru a evita schimbări inutile de baze de date.

De obicei, gateway-uri locale transmit extern de protocol numai informațiile referitoare la sistemele lor autonome, să nu crească fără a fi nevoie de a traficului în rețele.

, BGP (Border Gateway Protocol, RFC 1267) - un protocol de rutare între sisteme autonome de pe internet; este construit pe baza experienței acumulate în operarea EGP protocolului.
Scopul principal al BGP - pentru a reduce traficul de tranzit. Protocolul BGP utilizează un concept extins al unui sistem autonom. În acest caz, în cadrul unui sistem autonom gateway pot utiliza diferite protocoale de rutare și mai multe valori. Cu toate acestea, în cadrul sistemului autonom trebuie să fie un singur plan de rutare permite sistemului autonom în ansamblul său.

BGP este folosit ca protocolul TCP protocol de transport.
Protocolul BGP de operare al calculatorului gazdă, nu sunt în mod necesar, în același timp, este o poarta de acces.
Computerul gazdă care nu este un gateway de rutare poate face schimb de informații cu gateway-uri folosind protocolul EGP sau protocolul de rutare internă.
Acest computer gazdă poate utiliza apoi protocolul BGP pentru a face schimb de informații de rutare cu alte gateway-sistem autonom de delimitare.

Fig. 4.1. arhitectura router

Fig. 4.2. Procesarea la portul de intrare