Tema 6. Control de flux, d'errors i de congestió (2017)

Resumen Catalán
Universidad Universidad Politécnica de Cataluña (UPC)
Grado Ingeniería Telemática - 1º curso
Asignatura FT fonaments de telemàtica
Año del apunte 2017
Páginas 8
Fecha de subida 25/09/2017
Descargas 0
Subido por

Vista previa del texto

TEMA 6 – CONTROL DE FLUX, D’ERRORS I DE CONGESTIÓ 1. CONTROL DE FLUX 1.1.
Introducció Control de flux: conjunt de tècniques que permeten adaptar la taxa d’enviament d’informació (per a cada flux determinat) a la capacitat d’un receptor en particular - Ex 1: baixa capacitat de processament al receptor.
Probablement, el receptor no rebrà correctament el que transmet l’emissor A, degut a la diferència de velocitats.
Ex 2: servidor d’altra capacitat saturat per les peticions dels usuaris - NIVELLS DE CONTROL DE FLUX Salt-a-salt / punt a punt (nivell - Cada node actua com a origen i/o destí - Per a un enllaç, en particular, és simple i amb escenari controlat - Per a una comunicació amb múltiples salts, es requereix un processat addicional a cada node de xarxa d’enllaç) U= Temps que es transmet de forma útil (transmissió de dades) Temps total de la comunicació (Esperes, ACKs, tx amb errrs, etc. ) Extrem-a-extrem - Només implica l’emissor i el receptor finals (estalvi nodes intermediaris) (nivell de transport) - Sovint implica múltiples enllaços  Retard↑ i molt variable (escenari no controlat) 1.2.
Mecanismes de Control de Flux Idea bàsica: a font adapta dinàmicament la seva taxa a les condicions del receptor, i per tant, cal que hi hagi un mecanisme feedback en el sentit Receptor  Emissor Tècniques ❖ ON-OFF: el receptor envia missatges ON (emissor envia a vel màx) o OFF (emissor deixa d’enviar).
1 - Adient per a RTT’s baixos - Presenta problemes per a enllaços amb BER1 elevada (Ex: es poden perdre els missatges ON i OFF) - Utilitzat a línies sèrie curtes i xarxes LAN (BER i RTT solen ser baixos) BER: Bit Error Rate (Taxa d’error binari) 1 ❖ Stop & Wait: permet enviar un únic paquet en un RTT2 i espera el reconeixement (ACK) d’aquest per poder enviar-ne un altre, de manera que indirectament fa un control d’errors i de flux (s’assegura que la informació arribi correctament).
1 𝑝𝑎𝑞𝑢𝑒𝑡 - Velocitat màxima = - Si ↑ RTT, eficiència ↓ 𝑅𝑇𝑇 (𝑝𝑎𝑞𝑢𝑒𝑡𝑠/𝑠𝑒𝑔𝑜𝑛) ❖ Finestra lliscant (w): permet enviar múltiples (w) paquets per RTT i redueix el temps d’espera = optimitza la utilització d’un enllaç.
- Finestra de transmissió: conjunt de paquets transmesos pels quals no s’ha rebut un ACK Ex: w = 3; velocitat = 3/ RTT [paq/seg] b [paq/s]: taxa de servei limitant al llarg del camí.
R [s]: Rount Trip Time de tot el camí.
W [paquets] = mida màxima de la finestra  Finestra lliscant de mida òptima: podem enviar w (paquets) en R, però no podrem passar de b.
Aleshores, ajustem la mida de finestra: 𝑤 𝑅 ≤ 𝑏 → 𝑤𝑜𝑝𝑡 = 𝑏𝑅. Si 𝑤 < 𝑤𝑜𝑝𝑡 desaprofitem el canal, o bé, si 𝑤 > 𝑤𝑜𝑝𝑡 hi ha congestió (nodes intermediaris)  Finestra lliscant de mida w fixa: funciona bé si 𝑤𝑜𝑝𝑡 = 𝑏𝑅 no varien. Però en la pràctica, pot resultar ineficient o crear problemes (congestió de la xarxa o del node receptor), ja que b i R varien amb el temps, al igual que la capacitat del receptor. Aleshores cal adaptar la finestra en cada instant = finestra lliscant de mida variable.
 2. CONTROL D’ERRORS Control d’errors: assegura que les dades Rx i Tx són iguals 2.1.
Control d’errors de bit (produïts a nivell físic) Detecció (i correcció si es pot) a nivell d’enllaç, ja que el canal/enllaç per on s’envien els bits (o símbols si es modula) no és perfecte. Conseqüències:  Errors esporàdics i incorrelats, ràfegues d’errors, pèrdua de sincronisme  BER (Bit Error Ratio): bits rebuts/enviats erròniament 2 RTT: temps que tarda el ACK (anada i tornada) 2 Control d’errors de paquet (produïts a nivell d’enllaç) 2.2.
Detecció (i correcció) a nivell de transport. Assumim que el control d’errors de bit i de paquet funcionen simultàniament. Aleshores, si el control d’error de bits és ideal (detectats i corregits) no es generen errors de paquet. En canvi, si els errors de bit són detectats però no corregits, es generen pèrdues de paquet (s’elimina el paquet en comptes d’enviar-lo amb errors).
2.2.1.
Tipus d’errors de paquet: PÈRDUA Sobrecàrrega o congestió a la xarxa  cues plenes Causes Quan BER > 0: detecció d’errors de bit però no correcció total  paquet descartat ARQ: tècnica més utilitzada de detecció i correcció de pèrdues de paquet Recuperació Si l’emissor no rep un ACK3 en un RTO4 el paquet és retransmès CORRECTE ERROR ERROR Exemples: ACKs Un ACK per cada paquet  Stop & Wait Són acumulatius (l'últim reconeix tots els anteriors)  Finestra lliscant Normalament indica el següent paquet que s'espera rebre i l'últim paquet rebut No importa si perdem un ACK sempre i quean arribi el pròxim lo suficientment ràpid Exemple: 3 4 Finestra lliscant Stop & Wait ACK: reconeixement / Acknowledgment / OK (temps delimitat) RTO: temporitzador de retransmissió 3 El receptor detecta un buit en la seqüència rebuda i envia un NACK per informar la pèrdua NACKs El transmissor pot retransmetre immediatament, sense esperar a RTO NACK suposa càrrega de senyalització innecessària, per això no s'utilitza habitualment Exemple de NACK (reconeixement negatiu): arriba l’1, 2 i 4  notifica que falta el 3  NACK 2.2.2.
Tipus d’errors de paquet: DUPLICACIÓ Es retransmet un paquet ja rebut correctament degut a un ACK perdut o retardat o bé, un paquet retardat o RTO mal triat (RTT > RTO) 2.2.3.
Tipus d’errors de paquet: INSERCIÓ Hi ha paquets rebuts d’alguna altra transmissió. Causes: - La corrupció a la capçalera (canvi de bit) - Paquets retardats a la xarxa: un paquet d’una comunicació antiga és retardat i inserit en una comunicació nova (la resta de paquets ja han arribat; el receptor tanca la connexió i quan torna a obrirla li arriba el paquet antic) 2.2.4.
Tipus d’errors de paquet: REORDENACIÓ Es reben paquets en un ordre incorrecte. Causes: - Pèrdues i retransmissions (transmissió en finestra  no espera al ACK) - Els paquets poden prendre camins diferents (mode datagrama) 2.3.
Números de seqüència Un número de seqüència indica la posició d’un paquet dins un flux, on cada paquet és identificat amb un número de seqüència consecutiu. Permet la detecció dels 4 tipus d’errors de paquet (pèrdua, reordenació, duplicació i inserció).
❖ Espai de números de seqüència: conjunt de possibles números de seqüència representables en una certa capçalera, on n bits  2n números diferents. Ex: 3 bits  espai de núms. de seq: {1,2,3,4,5,6,7}, com que té un comportament cíclic, quan s’arriba al darrer número, el següent torna a ser el 0, és a dir 4 {...5,6,7,0,1,2,3...}. Ha de ser suficientment gran per evitar ambigüitats i s’ha de minimitzar per ocupar el menor espai possible a la capçalera.
2.3.1.
Números de seqüència: quants necessitem? Criteris ❖ Marge de pèrdues per ràfega (Np): assumim que només volem detectar errors, on Np és el nombre màxim de paquets perduts que volem detectar i n és el numero de bits necessaris per a representar el número de seqüència (n > log2 Np). Ex: Np = 8  n > 3 ❖ Elecció de la mida del número de seqüència: cal triar el més gran dels valors de n obtinguts segons diferents criteris.
2.3.2. Temporitzadors de retransmissió - Mecanisme: s’engega un temporitzador de retransmissió cada cop que s’envia un paquet, aleshores si el temporitzador acaba (timeout) i l’emissor no ha rebut cap ACK, retransmet el paquet.
- Problema: el valor del temporitzador ha de ser de l’ordre de magnitud d’un RTT (Round Trip Time).
Estàtic Conèixer l'RTT a priori Dinàmic Mesurar l'RTT Emprar RTO calculat adaptivament Assignar-li aquest valor Funciona bé quan RTT varia poc Problemes intrínsecs Possibilitat: promis dels RTTs mesurats - És difícil escollit el valor inicial de RTT 0 - Les mesures són difícils degut a l’alta variabilitat de RTS  pèrdues + ACK valida més d’un paquet 2.4.
Finestra de control d’errors Finestra de transmissió: espai de números de seqüència que referencien tots els paquets transmesos però encara no reconeguts. Mecanisme (control d’errors de finestra lliscant): La finestra s'expandeix quan l'emissor envia un paquet La font s'atura quan la finestra arriba a la màxima mida posible Cada ACK redueix la finestra per poder enviar altres paquets 5 En enviar un paquet i rebre un ACK, la finestra es mou endavant en l'espai de nº de seqüència 2.5.
Política de retransmissió: Go-Back-N Go-Back-N: retransmissió de tot el contingut de la finestra de control d’errors que expira un RTO i rep un NACK (només accepta paquets en ordre).
Go-back-N Funciona bé quan els errors són a ràfegues Simple: no cal buffer i retransmet tota la finestra de control d'errors Despesa d'ample de banda: retransmissió de paquets innecessaris i afageix càrrega en situacions de congestió 2.6.
Política de retransmissió: Retransmissió selectiva Funcionament: retransmetre únicament els paquets perduts. Per saber quins s’han perdut cada ACK porta un mapa de bits de la finestra de control d’errors actual, marcant els paquets rebuts (SACK). L’emissor por demanar periòdicament un paquet STATE amb el mapa de bits per evitar la despesa d’espai.
Ex: s’han rebut bé els paquets 4,5,7 i 9; no s’han rebut 6 i 8 * Retransmissió ràpida: si suposem que els ACKs són acumulatius (ACK indica paquet que esperem rebre), sortiran ACKs duplicats  reordenació + pèrdua de paquet  recuperació sense esperar RTO.
Avantatge: + eficàcia (només retransmet paquets necessaris +  congestió +  trans innecessàries).
Desavantatge: calen algoritmes de control més complexes i sofisticats (+ capacitat de procés i memòria) 3. CONTROL DE CONGESTIÓ (sobrecàrrega de la xarxa) - Causes: arribada de tràfic (paquets) a la xarxa a un ritme superior al capacitat.
- Efectes: saturació de cues dels nodes de xarxa ( ↑ Retard), pèrdua de paquets ( Retransmissions de paquets) i pèrdua de retransmissions ( retransmissions de retransmissions) - Conseqüència: pèrdua de capacitat efectiva (la carca pot entrar en un mode de funcionament inestable i esdevenir inutilitzable per culpa de la congestió.
Càrrega oferta al sistema Càrrega cursada pel sistema Nº de paquets oferts al sistema (+ retransmissions) Nº de paquets arriben al destí corresponent Percentatge de paquets que són cursats Rendiment 6 * POSSIBLES SOLUCIONS - Control de congestió: conjunt de tècniques que tracten d’evitar la sobrecàrrega o congestió sostinguda en els elements d’una xarxa en el seu conjunt.
- Augmentar la mida de les cues dels nodes: útil per absorbir ràfegues puntuals però no resol la congestió sostinguda (genera majors retards: RTO expira  retransmissions innecessàries  ↑ congestió) - Alternatives: mecanismes en cicle obert (preventius) i en cicle tancat (reactius) 3.2. Mecanismes en cicle obert És un mecanisme a priori que evita que aparegui la congestió i on les decisions preses són independents de l’estat de la xarxa. Ex: cubeta amb degoteig o amb fitxes (Leaky Bucket / Token Bucket) 3.2.1. LEAKY BUCKET (Cubeta amb degoteig) - Sistema amb capacitat finita, per tant, si es desborda implica una pèrdua de dades.
- Taxa de sortida constant: un flux entrant amb taxa variable es converteix en un flux a taxa constant - Conformació de tràfic (traffic shapping) 3.2.1. TOKEN BUCKET (Cubeta amb fitxes) - La cubeta genera una fitxa cada t segons i cada cop que s’envia una unitat de dades d’informació a la xarxa, la font consumeix la fitxa de la cubeta.
* Si el host ha estat inactiu b·∆t, s’hauran pogut emmagatzemar fins a b fitxes a la cubeta, de manera que es podrà enviar una ràfega de b unitats de dades com a mínim.
* Si no resten fitxes a la cubeta, els nous paquets entrants han d’esperar a que se’n generin de noves.
*Si no hi ha fitxes disponibles, els paquets esperen a ser transmesos, són descartats o bé, marcats.
- Ex: considerem que cada token dóna permís per a transmetre 1 byte.
B = capacitat de la cubeta de tokens (bytes) M = velocitat de sortida de la font (Bps) R = taxa d’arribada de fitxes (Bps) t = màxim temps de ràfega (s) Aleshores, s’acompleix que (M > R): B+R·t = M·t  t = B/(M-R) (La cubeta amb fitxes limit el temps màxim durant el qual una font pot transmetre a velocitat màxima) - Taxa mitjana a la qual transmet la font suposant que la cubeta està plena de fitxes inicialment 7 3.3. Mecanismes en cicle tancat Característiques L'emissor rep informació sobre l'estat de la xarxa (realimentació) Millor comportament quan hi ha congestió Els nodes poden ajustar pàrametres per evitar o reduir la congestió Alternatives: realimentació explícita (augment tràfic) o implícita (menys fiable) Exemple: control de congestió de TCP Procediment 1. Decidir com mesurar la congestió de la xarxa (% de paquets descartats per saturació de memòria, ocupació mitja de les cues i estadística del retard dels paquets) 2. Monitoritzar la xarxa per detectar congestió 3. Informar els nodes que poden prendre mesures 4. Actuar per a establir el sistema Possibles actuacions Augmentar la capacitat de la xarxa o dels nodes saturats (pot no ser viable) Dividir o repartir el tràfic sobre rutes menys saturades (balanceig de càrrega) Reduir la càrrega oferta a la xarxa (negant/degradant el servei, etc.) 3.4. Mecanismes emprats a Internet: TCP TCP implementa diferents algoritmes de control de congestió: - Sistema de cicle tancat: utilitza ACKs per a deduir s’hi ha congestió - Tots es basen en reduir la finestra de transmissió: finestra de congestió  finestra de transmissió - Mecanismes preventius: * Slow Start (començar amb una finestra mínima i augmentar-la una unitat per cada ACK que arriba) * Congestion Avoidance 8 ...

Tags:
Comprar Previsualizar