# Congestió de xarxa

La congestió de xarxa és el fenomen produït quan en una xarxa informàtica o part d'ella se li ofereix més trànsit del que pot cursar.

## Causes de la congestió

Hi ha diverses causes de congestió. Les més habituals són:

### Memòria insuficient en els commutadors

    Els paquets es reben massa pressa per ser processats (el que produeix que s'ompli la memòria d'entrada). A més pot ser que en la memòria de sortida hagi massa paquets esperant ser atesos, llavors s'omple memòria de sortida.

### Insuficient CPU en els nodes

    Pot ser que el node sigui incapaç de processar tota la informació que li arriba, amb el que farà que se saturin les cues.

### Velocitat insuficient de les línies
## Control d'una congestió

Comprèn tot un conjunt de tècniques per detectar i corregir els problemes que sorgeixen quan no tot el trànsit d'una xarxa informàtica pot ser cursat.

### Mecanismes de control d'una congestió

El problema del control de congestió pot enfocar matemàticament des del punt de vista de la teoria de control de processos, i segons això poden proposar solucions en bucle obert i en bucle tancat.

### Solucions

Evitació de la congestió és l'algoritme que va en combinació amb l'algoritme de començament lent, per dur a terme el control de congestió. Així, s'ha de tenir en consideració el valor del slow start threshold size (sstresh), que no és més que una variable que s'encarrega d'indicar la grandària màxima de la finestra de transmissió, que s'inicialitza en aquest algoritme a 65535 bytes. Cada vegada que es detecti congestió s'actualitzarà el valor d'aquest camp a la meitat del mínim entre window (win) i congestion window (cwnd). Si el motiu de la congestió és a causa de l'expiració del temps per a la confirmació de la recepció d'un segment (venç el temporitzador de retransmissió), es posarà el valor de cwnd a MSS (Maximum Segment Size), la qual cosa equival a inicialitzar la finestra de transmissió de començament lent. Quan s'incrementa cwnd sempre es té en compte el valor de sstresh, de manera que si el valor de cwnd no ha superat el d'sstresh, la forma d'incrementar-se serà de la mateixa manera que es fa en començament lent que no és una altra forma que exponencial, mentre que si s'ha superat l'increment serà lineal.

#### Solucions en bucle obert

També anomenades solucions passives. Combaten la congestió de les xarxes mitjançant un adequat disseny d'aquestes. Hi ha múltiples variables amb les que el dissenyador pot jugar a l'hora de dissenyar la xarxa. Aquestes variables influiran en el comportament de la xarxa enfront de la congestió. Les resumirem en funció del nivell del model OSI a què fan referència:
* Nivell d'enllaç
** Variables de disseny:
** Disseny de temporitzadors i política de retransmissions: Quan els temporitzadors esgoten el seu compte, els paquets afectats seran retransmesos per la font. Si aquest temps és molt petit, hi haurà gran quantitat de retransmissions. En canvi, si és gran, hi haurà menys congestió, però el retard mitjà augmentarà. A més, podem controlar el que es retransmet quan el temporitzador s'esgota.
** Política de descarts i emmagatzematge de paquets que arriben fora d'ordre: El rebuig pot ser simple, que origina més retransmissions, o bé selectiu, obligant a un emmagatzematge temporal dels paquets que arriben fora d'ordre i millorant la congestió.
** Política d'assentaments: El piggybacking, o utilització de part d'un paquet de dades per enviar assentaments de paquets anteriorment rebuts, redueix, en principi, el trànsit, però pot donar lloc a retransmissions que contribueixin a la congestió.
** Política de control de flux: Parant a una font que aboca molt trànsit podem reduir el risc de congestió.
* Nivell de xarxa
** Variables de disseny:
*** Circuits Virtuals davant datagrames: Molts algorismes de control de congestió funcionen només en mode circuit virtual.
*** Política de cues (Teoria de cues) i de servei: Els routers poden dissenyar amb una cua per línia d'entrada, una cua per línia de sortida, o ambdós. A més, pot jugar amb l'ordre en què els paquets són processats, donant més prioritat als paquets de control, que contenen informació útil des del punt de vista de la congestió.
*** Política de descart de paquets: De nou, la correcta elecció dels paquets que es descarten pot disminuir el risc de congestió.
*** Algorisme d'encaminament: És bo des del punt de vista de la congestió el balanceig del trànsit entre totes les línies de la xarxa.
*** Temps de vida dels paquets: La correcta elecció d'aquesta variable permet reduir el nombre de retransmissions, millorant així el comportament de la xarxa des del punt de vista de la congestió.

##### Nivell de transport

    Anàleg al nivell d'enllaç, però entre sistemes finals.

#### Solucions en bucle tancat

També anomenades solucions actives. Actuen quan es detecten problemes.
Tenen tres fases:
    a) Monitoratge de paràmetres . Es vigilen els següents paràmetres:
       1. Ocupació dels enllaços i dels buffers (cues d'espera en els nodes).
       2. Percentatge de descarts.
       3. Nombre de retransmissions.
       4. Retards i jitters .
       Els jitters són oscil·lacions de la separació temporal entre paquets. En aplicacions que requereixen sincronització (videoconferència, sincronitzar àudio amb vídeo), és molt important que aquestes oscil·lacions siguin petites.
    b) Reacció: enviament d'informació als punts necessaris . La comunicació es realitza gràcies a:
       1. Paquets especials.
          No estan sotmesos a control de congestió i se salten les cues d'espera en els nodes. Els envia el node que, gràcies al monitoratge, ha detectat la congestió.
       2. Bits de capçalera.
          En els paquets enviats, indico a la capçalera que comença a haver congestió. (Exemple: Frame Relay ).
       3. Informació específica.
          Si es rep una alerta de congestió (mitjançant bits de capçalera de paquets que circulen per la xarxa), es demana més informació.
    c) Ajust del sistema . Hi ha diverses mesures:
       1. Reduir la velocitat d'enviament
       2. Control d'accés. No es permeten més connexions.
       3. Llençar paquets. Controlar ràfegues de paquets que arriben.

### Algorismes de control de congestió

Es descriuen dos algorismes en bucle tancat: l' algorisme de descart de paquets , i un algorisme de paquets reguladors i un algorisme en bucle obert anomenat mecanisme de Traffic Shaping .

#### Algorisme de descart de paquets

És un algorisme de control de congestió en bucle tancat. Es basa en el fet que els nodes descarten paquets quan la seva ocupació és alta. Per això els nodes han de conèixer els seus recursos (Unitat Central de Procés i memòria). Fa una assignació dinàmica dels buffers basant-se en les necessitats de cada línia.
No obstant això, cada línia necessita almenys una (o més) posicions de memòria per a gestionar informació rellevant, tal com assentaments, que permet l'alliberament de posicions de memòria ocupades per paquets que estaven esperant per si necessitaven retransmetre.
Si la línia arriben dades (no assentiments o altra informació rellevant) i el buffer de sortida de la línia corresponent està ple, es descarta el paquet. Hi ha diverses formes de fer l'assignació de buffers:
    a) Atenent a l'ús.
       No és molt eficient, perquè quan una línia es comença a carregar acapara tots els recursos.
    b) Assignació fixa.
       Tampoc és molt bona, ja que desaprofita recursos.
    c) Assignació subòptima (d'Irlanda).

#### Algorisme de paquets reguladors

En terminologia anglesa, del paquet regulador se l'anomena Bobina de xoc packet. Es fa en bucle tancat. Associa un pes a cada línia que canvia amb el temps. Si el pes supera un cert llindar, es posa la línia en estat d'alerta i es considera que pot haver congestió. Si passa un determinat temps sense rebre notificacions de congestió, es torna a pujar el flux que pot cursar l'origen. Si per contra se supera un llindar major, es passa directament a fer descart de paquets.
Es fonamenta en la següent funció: Un = a · Un-1+(1-a) · f on:
* Un és una funció del pes que depèn de l'instant actual a través de fy l'instant anterior a través d'Un-1
* F té el valor 0 si no es transmet en l'instant actual i 1 si es tracta de l'instant actual.
* A és una constant, el valor ha d'estar entre 0 i 1 i que ha d'assignar segons la importància donada a cada enllaç.
En el moment en què un arriba al primer valor llindar assignat, la línia es Colca en alerta, de manera que s'envia un paquet regulador cap enrere. En els successius paquets que el node anterior s'envia cap endavant es posa un flag a 1 que indica que l'encaminador anterior està avisat. Aquest encaminador redueix el seu flux de transmissió i si, en un temps estipulat, no torna a rebre un paquet regulador augmenta de nou el seu flux de transmissió. Si s'assoleix el segon valor llindar assignat, es passa a descartar paquets.
Variacions d'aquest algorisme:
* Poden enviar paquets reguladors amb informació d'estat (greu, molt greu, etc.).
* En lloc de monitorar les línies de sortida poden mesurar altres paràmetres, com ara la mida de les cues en els nodes.

#### Mecanisme de Traffic Shaping

Traffic Shaping significa conformat de trànsit. És un mecanisme en bucle obert. Conforma el trànsit que una font pot injectar a la xarxa informàtica. S'usa en xarxes ATM (Asynchronous Transfer Mode) amb una tecnologia de xarxa orientada a connexió. Si es té una ràfega llista per transmetre, el sistema obliga a no transmetre tot seguit (perquè conforma el trànsit). Requereix un acord entre proveïdor i client.
El proveïdor garanteix que es cursa el trànsit si es transmet a una taxa determinada i tira el trànsit si se supera. Això es pot fer mitjançant un algorisme de leaky bucket (cub foradat), el nom es deu al fet que el sistema es comporta com un bidó que es va omplint amb un cabal determinat i pel que surt el líquid amb un altre cabal (menor) diferent. Si omplim molt de pressa el bidó acabarà omplint i abocant per dalt, el que s'assembla una pèrdua de paquets en una xarxa.

## Enllaços externs

* pablo/asignaturas/rysc1/alumnos/05-Congestion.pdf Control de Congestió
* Algorismes de congestió de xarxes
* Prometeu/RSC/apunts/Conger/conges.html Congestió
* Control i Congestió de xarxes Arxivat 2007-09-29 a Wayback Machine.