Mihai Budiu -- mihaib+@cs.cmu.edu
http://www.cs.cmu.edu/~mihaib
15 ianuarie 1999
Tehnologiile noi se insinuează încetul cu încetul în existența oamenilor, schimbînd pînă la urmă radical stilul lor de viață. În prima fază, o tehnologie revoluționară nu face decît să înlocuiască tehnologii mai vechi, a căror funcțiune o poate îndeplini mai bine. Dar, cu timpul, își asumă tot felul de sarcini inexistente anterior, transformînd societatea în mod fundamental. Așa s-au petrecut lucrurile, de pildă, cu curentul electric: la început acesta a preluat funcțiile iluminatului cu gaz, pentru că era mai ieftin și mai sigur. Dar încetul cu încetul i-au fost găsite mii de aplicații; societatea modernă de astăzi nu mai este de conceput fără existența sa: electricitatea a devenit o parte din infrastructură.
O revoluție asemănătoare este în curs de desfășurare: Internetul, rețeaua mondială, este noua tehnologie care va schimba fața lumii; începuturile sale comerciale sunt cu numai cinci ani în urmă, și evoluția sa se află încă în prima fază, de ``îmbunătățire'' a serviciilor existente. Maturizarea sa este rapidă, și în viitor ne așteaptă mutații neașteptate.
Internetul este, așa cum arată și numele său, ``inter-net'', o colecție de rețele, o super-rețea, care leagă laolaltă o sumedenie de rețele mici. Atenția articolului de față se va îndrepta spre una din cărămizile constitutive ale Internet-ului, cea mai importantă (din punct de vedere cantitativ): rețeaua locală.
În 1973 Robert Metcalfe, de la centrul de cercetare PARC (Palo Alto Research Center) al companiei Xerox, împreună cu alți cercetători, punea la punct un tip de rețea extrem de ieftin și eficace, numit Ethernet. Ethernetul permitea conectarea mai multor calculatoare printr-un singur cablu coaxial, asemănător cu cele folosite în televiziunea pe cablu; viteza de transmisiune inițială era de pînă la 4 megabiți pe secundă (adică în jur de jumătate de megaoctet pe secundă).
Pentru a comercializa Ethernetul, Xerox a format apoi împreună cu Intel și Digital o nouă companie, condusă de Metcalfe, care a devenit apoi independentă sub numele ``3 companii'', sau 3Com. 3Com este la ora actuală, după Cisco, cea mai mare companie de echipamente de rețele din lume, cu venituri anuale de 6 miliarde de dolari.
Tipul de rețea inventat de Xerox a fost standardizat de IEEE sub sugestivul nume de 802.3; deși rețeaua 802.3 este oarecum diferită de Ethernet, numele încetățenit pentru aceste rețele este tot Ethernet. Ethernet-ul a fost apoi perfecționat pentru a merge la viteze de pînă la 10Mbps. La începutul anilor '90 au apărut variantele fast-Ethernet, de 100Mbps, iar acum este în proces de standardizare varianta Gigabit-Ethernet, care merge la 1000Mbps! Ethernet-ul este de departe cea mai populară rețea din lume, ca număr de instalări. Ethernet-ul este ceea ce se numește o ``rețea locală'' (LAN: Local Area Network). Motivul principal este că poate conecta calculatoare pe o distanță relativ restrînsă (lungimea unui cablu este limitată din motive de durată a propagării semnalului electromagnetic la 500m).
La începutul anilor '80, General Motors și Boeing erau nesatisfăcute de anumite proprietăți ale rețelei Ethernet (și anume de faptul că Ethernet nu garantează cît de mult timp trece pînă cînd un calculator poate transmite un pachet), așa că au investit pentru dezvoltarea unor tipuri alternative de rețele locale. Comitetul IEEE 802, care a standardizat Ethernet, s-a ocupat și de aceste noi tipuri de rețele. Rețelele rezultate sunt 802.4, sau ``token bus'' și 802.5, sau ``token ring''1. Token bus folosește tot un cablu coaxial, însă ordinea accesului calculatoarelor (stațiilor) la cablu este riguros stabilită; în acest fel fiecare calculator știe că după un anumit timp va avea posibilitatea să trimită ce are de trimis. Token ring conectează calculatoarele într-un inel fizic, fiecare calculator cu doi vecini; datele curg apoi de-a lungul inelului într-o singură direcție. Cele trei tipuri fundamentale de rețele locale sunt ilustrate în figura 1.
În acest articol ne interesează mai puțin natura fizică a rețelelor și mai mult conceptele care stau la baza utilizării lor. În unele privințe toate rețelele standardului 802 se aseamănă, de aceea anumite părți ale standardului sunt comune tuturor tipurilor; de pildă 802.1 stabilește regulile de adresare pe toate aceste rețele.
De fiecare dată cînd într-o conversație sunt implicate mai mult de două persoane, este necesar să se folosească niște metode pentru a identifica fiecare participant. Fiecare participant trebuie să aibă un nume2.
În terminologia rețelelor de calculatoare numele unui participant se numește adresă. În rețelele locale 802 adresele sunt numere de 48 de biți (6 octeți). Metoda standard de scriere a unei adrese folosește șase numere scrise în hexazecimal, separate de liniuțe. Aceasta este, de pildă, o adresă validă: 8-0-20-c0-ff-ee. IEEE are grijă ca în lume să nu existe două calculatoare cu aceeași adresă. Acest lucru se face atribuind fiecărui fabricant un anumit spațiu de adrese (descris de primii 3 octeți), fabricanții apoi promit ca fiecare ``placă'' fabricată să aibă o altă adresă.
Unicitatea adreselor, și faptul că sunt suficient de multe, face operarea și administrarea rețelelor locale o treabă relativ simplă; în cele mai multe cazuri instalarea unui calculator într-o rețea locală este ``plug-and-play'': nimic nu trebuie configurat de către un administrator uman pentru a-l face să comunice cu celelalte3.
Cînd un calculator vrea să trimită date altui calculator, atunci pune pe rețea un pachețel; în pachețel se află, în afară de date, și informații despre:
Anumite adrese sunt rezervate pentru a indica grupuri de calculatoare (adrese multicast) sau ``toate calculatoarele de pe rețeaua locală'' (broadcast, difuzare). Un calculator poate fi instruit să asculte unele adrese de tip multicast; în acest fel o informație poate fi transmisă cu un singur pachet de la o sursă la mai multe destinații.
Transmisiunile de tip multicast sunt utile într-o multitudine de circumstanțe:
Dacă avem două rețele locale pe care vrem să le conectăm între ele avem două posibilități. Cea mai simplă folosește un repetor (repeater).
Repetorul nu este nimic altceva decît un amplificator electric, care preia semnale dintr-o parte și le pune în cealaltă. Rețelele de televiziune pe cablu folosesc astfel de amplificatoare, pentru a mări puterea semnalului transmis pe distanțe mari. După cum este evident, repetoarele se pot folosi numai între rețele locale de același tip (adică nu putem conecta un token bus cu un token ring).
Mai mult, deși sunt eficace în a transforma două rețele într-una, în anumite privințe rețeaua rezultată este limitată. De pildă, așa cum am menționat mai sus, durata de propagare a semnalului electromagnetic între oricare două calculatoare nu poate fi prea mare într-o rețea de tip Ethernet. O altă limitare provine din faptul că toate calculatoarele de pe aceeași rețea locală folosesc în comun același mediu de transmisie, deci cu cît sunt mai multe, cu atît rata efectivă de transmisie de care se poate bucura fiecare din ele scade mai mult.
Pentru a rezolva acest gen de probleme au fost create podurile (bridges).
Un pod nu este nimic altceva decît un calculator specializat care este conectat la două (sau mai multe) rețele locale simultan. Podul știe să preia pachete de date dintr-o rețea și să le transmită în cealaltă, dacă este nevoie. Poduri sunt ilustrate în figurile 2 și 3.
Aparent funcțiunile unui pod sunt aceleași cu ale unui repetor. Există însă importante diferențe:
Lucrurile par să stea ca și cum transmisiunea unui pachet între calculatoarele A și B din figura 2 se face în doi pași: de la A la bridge, și de la bridge la B. Pentru a lega însă cele două rețele într-un mod invizibil, ca și cum ar fi una singură, existența podului trebuie să fie indiscernabilă; podul trebuie să fie transparent.
Din cauza asta, podul capturează pachetul trimis de A, deși acesta specifică adresa B (care nu este tot una cu adresa podului). Podul apoi trimite pachetul pe rețeaua Ethernet fără a schimba însă adresa sursă sau destinație din pachet! Pachetul apare pe rețeaua Ethernet ca și cum A ar fi fost cuplat direct la rețea.
Întrebarea care se pune este: din moment ce podurile nu necesită nici un fel de configurație manuală, de unde știu ele de fapt cînd trebuie să preia un pachet și cînd nu, și de unde știu pe care dintre rețele să-i dea drumul?
Răspunsul este: nici nu știu, cel puțin la început. Însă învață; din cauza asta se și numesc learning bridges. Vom ilustra algoritmul printr-un exemplu:
Podurile ``uită'' periodic informațiile învățate; în acest fel o stație poate fi deconectată dintr-o rețea și mutată în cealaltă, și podurile continuă să opereze corect.
Este ușor de verificat că algoritmul descris mai sus funcționează și pentru poduri care leagă mai mult de două rețele, și că funcționează și pentru rețele cu topologii complexe, ca în figura 3.
Din păcate lucrurile nu stau chiar așa pentru orice topologie; figura 4 prezintă o topologie de rețele locale pentru care aplicarea acestui algoritm duce la o catastrofă.
Să vedem tot printr-un exemplu ce se întîmplă de fapt:
În general, orice rețea care are cicluri (mai multe drumuri posibile între două calculatoare) duce la astfel de probleme, pentru că bridge-urile nu se așteaptă să vadă pachete de la un calculator venind de pe două interfețe diferite.
Care e soluția? Putem cere administratorilor de rețea să nu conecteze niciodată rețele cu cicluri; în acest fel sunt singurii vinovați dacă așa ceva se întîmplă.
Însă ideea de a conecta o rețea în mod redundant, în așa fel încît între calculatoare să existe uneori mai mult de un singur drum, este o idee foarte bună, pentru că este rezilientă la erori. Dacă avem două conexiuni și una dintre ele se strică, cealaltă poate prelua traficul fără întreruperea conectivității.
Clar, trebuie oferită o altă soluție. Aceasta constă în algoritmul prin care bridge-urile reduc orice rețea cu cicluri la una fără cicluri, căzînd de acord ca anumite legături să nu fie niciodată folosite. În cazul în care topologia rețelei se schimbă, prin căderea uneia dintre legături, bridge-urile recalculează legăturile folosite, refăcînd conectivitatea rețelei.
Dacă vedem o serie de rețele LAN ca noduri într-un graf, iar bridge-urile ca arce, algoritmul care rezolvă problema expusă mai sus calculează ceea ce se numește arbore de acoperire (spanning tree) al grafului. Acesta este un graf care este arbore (nu are cicluri) și cuprinde toate nodurile grafului. Acest algoritm a fost inventat de Radia Perlman, și este folosit de toate podurile transparente din lume. Prezentarea algoritmului se bazează pe cea din cartea ei de la Addison-Wesley ``Interconnections'', pe care am recomandat-o și cu alte ocazii. Radia Perlman este o personalitate în lumea rețelelor; are un doctorat în domeniu de la MIT, și a lucrat mai bine de 10 la Digital în proiectare de protocoale. Multe din protocoalele de rutare din Internetul de azi sunt bazate pe prototipurile folosite în DECnet (rețeaua dezvoltată de Digital); de pildă protocolul OSPF (Open Shortest-Path First) este în mare măsură creația Radiei Perlman.
Acest gen de algoritmi sunt foarte greu de înțeles, și mai greu de proiectat, extrem de greu de depanat și aproape imposibil de certificat ca fiind corecți. Asta pentru că acești algoritmi sunt distribuiți: fiecare entitate care participă în calcule are numai informații parțiale despre întregul ansamblu, și trebuie să reconstituie totul doar din informațiile primite. Vom vedea mai jos că o sumedenie de factori practici (cum ar fi căderile unor stații, erori tranziente, etc.) fac garantarea funcționării unui astfel de protocol în toate circumstanțele o treabă practic imposibilă. Dar înainte de asta să vedem care este algoritmul de bază.
Algoritmul se bazează pe un set de mesaje de configurare pe care podurile le trimit între ele, folosind o adresă multicast specială. Folosind mesajele de configurare, toate podurile ajung la o aceeași concluzie despre topologia rețelei:
Fiecare bridge transmite mesaje de configurare și calculează în funcție de mesajele primite cum arată rețeaua. Un pod nu retransmite mesajele primite de la alte poduri (așa cum face cu mesajele care conțin date); fiecare mesaj de configurare deci călătorește pe un singur LAN. După un număr de runde, fiecare pod are suficiente informații pentru a deduce topologia corectă și algoritmul se termină.
Fiecare bridge folosește drept nume (identificator, ID) un număr unic, de obicei adresa uneia din interfețele sale (întotdeauna aceeași). Pod-rădăcină va fi ales cel care are cel mai mic ID.
Fiecare pod transmite un mesaj compus din trei bucăți:
Inițial fiecare pod crede despre sine că este rădăcina, deci primul mesaj are forma (ID meu, 0, ID meu). Cu vremea această opinie se schimbă pentru fiecare pod. Un bridge primește într-una mesaje de configurare pe fiecare port, și menține pentru fiecare port ``cel mai bun'' mesaj de configurare pe care l-a primit. ``Cel mai bun'' mesaj de configurare este obținut comparînd:
Un mesaj e ``mai bun'' decît altul dacă e ``mai mic'' în ordine lexicografică. Cu alte cuvinte: (a, b, c) < (d, e, f) dacă:
Podurile transmit simultan mesaje de configurare pe toate porturile. În momentul în care un pod primește pe un port un mesaj mai bun decît ar fi vrut el să transmită, atunci încetează să mai transmită pe acel port. Motivul este că mesajele pot deveni doar din ce în ce mai bune cu trecerea timpului, deci propriul lui mesaj nu mai are nici o șansă să devină cel mai bun pe acel LAN.
Un bridge își clasează apoi porturile în trei categorii:
În exemplul din figura 4, rezultatul protocolului va fi că bridge-ul cu cel mai mic ID devine rădăcină, iar celălalt își dezactivează ambele porturi.
Figura 5 ilustrează un fragment dintr-o rețea locală și cele trei feluri de porturi pentru un bridge b2.
Iată concret pe un exemplu numeric acțiunile lui b2 din figura 5 într-o rundă posibilă a protocolului:
Mesajele primite de b2 (ID = 18) | |||
Rădăcină | Cost | Transmițător | |
Port spre A | 12 | 4 | 85 |
Port spre B | 20 | 0 | 20 |
Port spre C | 22 | 2 | 44 |
Port spre D | 12 | 5 | 16 |
Cel ``mai bun'' mesaj primit este (12, 4, 85). Ca atare b2 decide că el se află la distanță 4+1=5 de rădăcină; mesajul pe care îl va transmite în runda următoare va fi deci: (12, 5, 18). Acest mesaj este comparat cu toate celelalte 4 mesaje. Acest mesaje este mai bun decît cele de la porturile spre B și C, deci b2 devine pod desemnat pentru aceste LAN-uri. Portul spre A duce spre rădăcină (pe acolo a sosit cel mai bun mesaj), iar portul D este dezactivat, pentru că mesajul primit de acolo e mai bun decît cel calculat. Rezultatul algoritmului în jurul lui b2 este cel din figura 5.
Acesta este algoritmul distribuit pentru calculul arborilor de acoperire. Analizîndu-l cu oarecare grijă putem să ne convingem de corectitudinea lui: algoritmul se termină pentru că mesajele trimise vor fi din ce în ce mai ``bune'', pînă cînd numai bridge-ul rădăcină mai vorbește, topologia stabilită nu va avea cicluri, pentru că cel puțin un bridge într-un ciclu va fi forțat să-și dezactiveze o interfață, și topologia stabilită va fi conexă (adică va lega toate rețelele), pentru că fiecare rețea o să aibă un ``designated bridge'', și pentru că orice lipsă de conectivitate între două părți este remediată de o rundă de mesaje. (Desigur, aceasta este o argumentație foarte sumară.)
Pe de altă parte această demonstrație este valabilă în cazul în care rețeaua este stabilă (stable, quiescent); în momentul cînd se fac schimbări topologice ce se întîmplă cu algoritmul? Dacă un bridge sau o rețea cad, sau dacă administratorul adaugă noi bridge-uri, care încă nu știu de vechea configurație, cum de lucrurile continuă să funcționeze?
Aici lucrurile sunt mult mai problematice, tocmai pentru că e foarte greu de imaginat dinainte orice tip de eveniment; pentru unele cazuri foarte exotice, cum ar fi prezența unei defecțiuni care permite transmisiunea într-un singur sens, nici nu există soluții prestabilite.
Iată ilustrate unele dintre posibilele complicații și soluțiile adoptate în practică:
Închei aici acest articol despre poduri, deși problemele care trebuie considerate în practică sunt mult mai multe și mai complicate decît am apucat să ilustrez. Principiile de bază ale funcționării unui bridge sunt însă, sper, cuprinse în acest text. Restul sunt detalii.
Să recapitulăm învățămintele principale: există mai multe tipuri de rețele locale, care realizează transmisiunea informației între calculatoare relativ puține (sute) aflate la distanțe relativ mici (kilometri) cu viteza relativ mare (sute de megabiți pe secundă, în tehnologiile cele mai mature). Rețelele locale se pot lega între ele folosind repetoare sau poduri. Repetoarele sunt doar o conexiune electrică, pe cînd bridge-urile sunt echipamente inteligente, care învață așezarea stațiilor, filtrează traficul nenecesar între rețelele pe care le leagă, și colaborează pentru a construi o rețea completă fără cicluri, pentru a preveni proliferarea nelimitată a unor pachete.
Rețelele locale reprezintă cea mai importantă (numeric vorbind) piesă din Internet, care este o colecție de rețele legate laolaltă. Evoluția lor este departe de a fi terminată: cursa spre distanțe și viteze mari continuă. Fiți cu ochii, și cu datele, pe ele!