Augment additiu/disminució multiplicativa

L'algoritme d'augment/diminució multiplicativa d'additius (AIMD) és un algorisme de control de retroalimentació més conegut pel seu ús en el control de congestió TCP. AIMD combina el creixement lineal de la finestra de congestió quan no hi ha congestió amb una reducció exponencial quan es detecta congestió. Diversos fluxos que utilitzen el control de congestió AIMD eventualment convergiran cap a un ús igual d'un enllaç compartit.^[1] Els esquemes relacionats d'augment-multiplicatiu/disminució multiplicativa (MIMD) i d'augment-additiu/disminució additiu (AIAD) no aconsegueixen estabilitat.^[2]^[3]

Algoritme[modifica]

L'enfocament utilitzat és augmentar la velocitat de transmissió (mida de la finestra), investigant l'amplada de banda utilitzable, fins que es produeixi la pèrdua. La política d'augment additiu pot, per exemple, augmentar la finestra de congestió en una quantitat fixa cada temps d'anada i tornada. Quan es detecta congestió, el transmissor disminueix la velocitat de transmissió per un factor multiplicatiu; per exemple, retallar la finestra de congestió a la meitat després de la pèrdua. El resultat és un comportament de dents de serra que representa el procés de sondeig de l'ample de banda.

AIMD requereix un senyal de congestió binari. Amb més freqüència, la pèrdua de paquets serveix com a senyal; la disminució multiplicativa s'activa quan un temps d'espera o un missatge de reconeixement indica que s'ha perdut un paquet. També és possible que els commutadors/encaminadors de la xarxa marquin la congestió (sense descartar paquets) com a la Notificació de congestió explícita (ECN).^[4]

Fórmula matemàtica[modifica]

Deixar $w(t)$ ser la mida de la finestra de congestió que indica la quantitat de dades en vol durant la franja horària $t$ , $a$ ( $a>0$ ) sigui el paràmetre d'augment additiu, i $b$ ( $0<b<1$ ) sigui el factor de disminució multiplicatiu.

$w(t+1)={\begin{cases}w(t)+a&{\text{ si la congestió no és detectada}}\\w(t)\times b&{\text{ si la congestió és detectada}}\end{cases}}$

A TCP, després d'un inici lent, el paràmetre d'augment de l'additiu $a$ normalment és un MSS (mida màxima del segment) per temps d'anada i tornada i el factor de disminució multiplicatiu $b$ normalment és 1/2.

Referències[modifica]

↑ Chiu, Dah-Ming; Raj Jain Computer Networks and ISDN Systems, 17, 1989, pàg. 1–14. DOI: 10.1016/0169-7552(89)90019-6.
↑ «Additive increase/multiplicative decrease» (en anglès). [Consulta: 11 novembre 2023].
↑ Amsterdam, Tom. «Understanding Congestion Control» (en anglès americà), 31-03-2021. [Consulta: 11 novembre 2023].
↑ «[https://arxiv.org/pdf/2102.00438.pdf Unified approach for solving exit problems for additive-increase and multiplicative-decrease processes]» (en anglès). [Consulta: 11 novembre 2023].

[chui1989-1] Chiu, Dah-Ming; Raj Jain Computer Networks and ISDN Systems, 17, 1989, pàg. 1–14. DOI: 10.1016/0169-7552(89)90019-6.

[2] «Additive increase/multiplicative decrease» (en anglès). [Consulta: 11 novembre 2023].

[3] Amsterdam, Tom. «Understanding Congestion Control» (en anglès americà), 31-03-2021. [Consulta: 11 novembre 2023].

[4] «[https://arxiv.org/pdf/2102.00438.pdf Unified approach for solving exit problems for additive-increase and multiplicative-decrease processes]» (en anglès). [Consulta: 11 novembre 2023].

[1]

[2]

[3]

[4]