1

Curs 2

Introducere în algoritmica de reţea

Introducere în algoritmica de reţea

Scop - combaterea strangulărilor de reţea Asigură unelte (metode, algoritmi). Abordare interdisciplinară :

- arhitecturi şi sisteme de operare; - proiectare hardware (routere), - proiectarea de algoritmi (scalabili).

Abordare sistemică - set de 15 principii ruterele şi serverele sunt sisteme, în care eficienţa

poate fi obţinută prin deplasarea funcţiilor în spaţiu şi timp între subsisteme.

2

Apar de obicei la nodurile terminale/endnodes şi la routere Nodurile terminale - calculatoarele personale, staţii de lucru, servere de mari dimensiuni, furnizoare de servicii. sunt dedicate calculelor de uz general cauzele strangulărilor: structura şi

scala/dimensiunea

Strangulări de reţea

Structura nodurilor terminale

Nodurile terminale au sistem de operare (mediază între aplicaţii şi hardware) Structura sistemului de operare pe niveluri; există mecanisme de protecţie; rutinele nucleului sistemului de operare

( planificatoare si proceduri de alocare) cât mai generale. Structura pe niveluri, prezenţa mecanismelor de protecţie, şi generalitatea excesivă pot duce la încetinirea software-ului reţelei.

3

Scala (dimensiunea)

Existenţa serverelor mari (cum este un server de Web cu mii de clienţi concurenţi) poate crea probleme dacă sistemele de operare corespunzătoare folosesc structuri de date ineficiente sau algoritmi învechiţi.

Principalele strangulări ale nodurilor terminale

structurile sistemului de operare convenţional impun copierea pachetelor de date între domeniile protejate; în cazul serverelor de Web se fac copieri pentru sistemul de fişiere sau verificări ale pachetelor - sumele ciclice de control.

Remote Direct Memory Access (RDMA) is a DMA from the memory of one computer into that of another without involving either one's operating system.

4

Control

Comutarea între firele de control (sau domeniile de protecţie) în timpul procesării unui pachet.

Contoare de timp

Aplicaţiile de reţea folosesc contoare de timp/temporizatoare pentru a rezolva defecţiunile. Cu un număr mare de legături la un server supraîncărcarea dată de contoarele de timp poate deveni mare.

5

Demultiplexarea

Mesajele de la reţea trebuie demultiplexate/orientate pentru a fi recepţionate de aplicaţia corectă.

Sarcini de procesare ale protocoalelor

sarcini de procesare ale protocoalelor

alocarea bufferelor/tampoanelor de memorie suma de control

6

Strangulările în routere

Aproape toate tehnicile descrise pot fi folosite şi în cazul :

altor echipamente de reţea : punţi/bridge, comutatoare/switch, porţi/gateway, dispozitive de securitate, altor protocoale decât TCP/IP (FiberChannel).

Router dispozitiv generic de interconectare a reţelei. cu scop special : lucrul cu reţelele.

Problemele fundamentale pe care le întâlneşte un router sunt legate de dimensiune/scală şi servicii.

Scala

Tipuri de scalare: scalarea benzii şi scalarea populării. Scalarea benzii are loc deoarece : crește viteza legăturilor (de la 1-Gbps la 40-Gbps

(comunicații optice), crește traficul (aplicaţii noi).

Scalarea populării are loc deoarece se adaugă tot mai multe noduri terminale la Internet.

7

Serviciile

tot mai multe afaceri se fac online (Amazon), noi servicii online(Ebay). Scop

- eficientizarea Internet-ului - îmbunătăţirea performanţei şi siguranţei Este important să se ofere garanţii ale reţelei

întârzierea în timpul congestiei protecţia în timpul atacurilor, disponibilitatea când apar defecţiuni.

Găsirea unor metode de implementare a acestor noi servicii la viteze mari va fi o mare provocare pentru furnizorii de rutere în decada următoare.

8

Principalele strangulări din routere

Dispozitivele de reţea (de exemplu punţile) expediază pachete destinaţiei prin consultarea (looking up) unui tabel de înaintare (forwarding). Se găseşte o potrivire exactă (exact match) cu adresa destinaţiei. Scheme de căutare rapide şi scalabile, pentru potriviri exacte.

Căutări de prefix

Routerele reţin o singură intrare numită prefix (analog cu codul telefonic de zonă) pentru un grup mare de staţii. Fac o căutare mult mai complexă pentru potrivirea celui mai lung prefix/the longest-prefix-match. Sunt descrise soluţii la această problemă, scalabile la viteze mari şi dimensiuni mari ale tabelelor.

9

Clasificarea pachetelor

Routere-le moderne fac diferenţierea serviciului : pachete diferite sunt tratate diferit. E necesară o formă şi mai complexă de căutare numită clasificarea pachetelor. Căutarea se bazează pe destinaţie, sursă, şi chiar pe serviciile pe care le oferă pachetul respectiv. Channel Access Method (CAM), a protocol for how data is transmitted in the bottom two layers of the OSI model. CAMs describe how networking systems put data on the network media, how low-level errors are dealt with, and how the network polices itself.

Comutarea

Dispozitivele de reţea pot fi considerate comutatoare. Crearea unui comutator de viteză mare (optic ?).

10

Soluţia standard este folosirea paralelismului printr-un comutator crossbar. Programarea unui comutator crossbar la viteze mari este dificilă. Paralelismul este limitat de fenomenul cunoscut ca HOL (head-of-line blocking)/ blocare la începutul liniei.

Sunt necesare comutatoare cu un număr mare de porturi, care exacerbează aceste probleme.

Head-of-line blocking (HOL blocking) in computer networking is a performance-limiting phenomenon that occurs when a line of packets is held up by the first packet. Examples include input buffered network switches, out-of-order delivery and multiple requests in HTTP pipelining.

11

Cozile de așteptare

Strangularea cauzată de cozile de așteptare este produsă de nevoia de servicii noi. Weighted fair queueing (WFQ) is a data packet scheduling algorithm used by network schedulers. WFQ is a natural generalization of fair queuing (FQ). FQ shares the link's capacity in equal subparts, WFQ allows to specify, for each flow, which fraction of the capacity will be given.

Deficit Round Robin (DRR), also Deficit Weighted Round Robin (DWRR), is a scheduling algorithm for the network scheduler. DRR is, like weighted fair queuing (WFQ), a packet-based implementation of the ideal Generalized Processor Sharing (GPS) policy. It was proposed by M. Shreedhar and G. Varghese in 1995 as an efficient (with O(1) complexity) and fair algorithm. In today's Internet congestion control is achieved by relying on end-to-end protocols, such as TCP. For this approach to work it is critical that all end-host cooperate. End-hosts implement homogeneous control algorithms. An alternate approach to achieve congestion control is to provide router support. The major disadvantage of this approach is that the known algorithms to achieve fair share are complex, as they require routers to perform per flow management. More precisely, a router needs to perform (1) per packet classification, (2) per-flow buffer management, and eventually (3) per-flow scheduling. This complexity may prevent them form being cost-effectively deployed at high speeds. To address this problem, a network architecture and an algorithm, called Core-Stateless Fair Queueing (CSFQ) were proposed. The architecture differentiates between edge and core nodes. While edge nodes do perform per flow management, core nodes do not perform per flow management. Therefore they can be efficiently implemented at high speeds. Edge nodes are simpler than regular fair queueing nodes.

12

Lățimea de bandă

Altă strangulare care devine o problemă în creştere este lăţimea de bandă a router-ului. Se folosesc tehnici simple: conectarea directă prin magistrale interne/striping legături chip-la-chip.

Măsurări

Dintre serviciile ce trebuie să facă parte dintr-un viitor Internet, bine administrat, este includerea în router-e a unui suport pentru măsurări, deoarece acestea sunt cheia pentru garanţii. Routere-le de azi asigură suport pentru măsurări, contorizări și înregistrări de NetFlow.

You can maintain packet counts based on the entry and exit points for traffic passing through your network. Entry and exit points are identified by source and destination prefixes grouped into disjoint sets defined as source classes and destination classes. Source class usage (SCU) counts packets sent to customers by performing lookups on the IP source address and the IP destination address. Destination class usage (DCU) counts packets from customers by performing lookups of the IP destination address. DCU makes it possible to track traffic originating from the customer edge and destined for specific prefixes on the provider core router.

13

Securitate

Suportul pentru securitate este deja parţial inclus în router-e. Implementarea securității în router-e este esențială. Dacă dispozitivul de securitate nu poate ţine pasul cu legăturile de mare viteză, pot fi omise informaţii vitale, necesare pentru detectarea unui atac.

Filtre Bloom: structură de date aleatorizată ingenios pentru reprezentarea concisă a unui set/mulţime, care suportă interogări/queries despre apartenenţa aproximativă la mulţime. Are o mare eficienţă spaţială, iar riscul/costul este de a detecta falsuri pozitive.