Additiv ökning/multiplikativ minskning

additiv -ökning/multiplikativ-minskning ( AIMD ) är en återkopplingskontrollalgoritm som är mest känd för sin användning i TCP-överbelastningskontroll . AIMD kombinerar linjär tillväxt av trängselfönstret när det inte finns någon trängsel med en exponentiell minskning när trängsel detekteras. Flera flöden som använder AIMD överbelastningskontroll kommer så småningom att konvergera till lika användning av en delad länk. De relaterade systemen för multiplikativ ökning/multiplikativ minskning (MIMD) och additiv ökning/additiv-minskning (AIAD) når inte stabilitet .

Algoritm

Tillvägagångssättet som används är att öka överföringshastigheten (fönsterstorlek), söka efter användbar bandbredd, tills förlust inträffar. Policyn med additiv ökning kan till exempel öka trängselfönstret med ett fast belopp varje tur och retur . När trängsel detekteras, minskar sändaren överföringshastigheten med en multiplikationsfaktor; till exempel, halvera trängselfönstret efter förlust. Resultatet är ett sågtandsbeteende som representerar processen för bandbreddsundersökning.

AIMD kräver en binär överbelastningssignal. Oftast fungerar paketförlust som signalen; den multiplikativa minskningen utlöses när en timeout eller ett bekräftelsemeddelande indikerar ett förlorat paket. Det är också möjligt för switchar/routrar i nätverket att markera överbelastning (utan att kassera paket) som i Explicit Congestion Notification (ECN).

Matematisk formel

Låt $w(t)$ vara överbelastningsfönstrets storlek som anger mängden data under flygning under tidsluckan ${\displaystyle t} ,$ a $\displaystyle a}$ ( $a>0$ ) vara den additiva ökningsparametern, och $b$ ( $0<b<1$ ) vara den multiplikativa minskningsfaktorn.

$w(t+1)={\begin{cases}w(t)+ a&{\text{ om trängsel inte upptäcks}}\\w(t)\ gånger b&{\text{ om trängsel upptäcks}}\end{cases}}$

I TCP, efter långsam start , är den additiva ökningsparametern $a$ typiskt en MSS ( maximal segmentstorlek ) per tur-och-retur-tid , och den multiplikativa minskningsfaktorn $b$ är vanligtvis 1/2.

Protokoll

AIMD undvikande av trängsel används eller användes i:

I naturen

AIMD har visat sig användas av olika biologiska system , inklusive för att reglera födosök av skördarmyrkolonier , upprätthålla homeostas i cellstorlek och för synaptisk inlärning och anpassning i neurala kretsar .