Additive increase/multiplicative decrease

<h2 id="algorithm">Algorithm</h2>
<p>The approach taken is to increase the transmission rate (window size), probing for usable bandwidth, until loss occurs. The policy of additive increase may, for instance, increase the congestion window by a fixed amount every <a href="/facts/Round-trip_time/jYgNMK98">round-trip time</a>. When congestion is detected, the transmitter decreases the transmission rate by a multiplicative factor; for example, cut the congestion window in half after loss. The result is a saw-tooth behavior that represents the process of bandwidth probing.
</p><p>AIMD requires a binary congestion signal. Most frequently, packet loss serves as the signal; the multiplicative decrease is triggered when a timeout or an acknowledgement message indicates a packet lost. It is also possible for in-network switches/routers to mark congestion (without discarding packets) as in <a href="/facts/Explicit_Congestion_Notification/VKfVXcKp">Explicit Congestion Notification</a> (ECN).
</p>
<h3>Mathematical Formula</h3>
<p>Let 
  
    
      
        w
        (
        t
        )
      
    
    {\displaystyle w(t)}
  
 be the <a href="/facts/Congestion_window/gC9Fer09">congestion window</a> size indicating the amount of data in flight during time slot 
  
    
      
        t
      
    
    {\displaystyle t}
  
, 
  
    
      
        a
      
    
    {\displaystyle a}
  
 (
  
    
      
        a
        >
        0
      
    
    {\displaystyle a>0}
  
) be the additive increase parameter, and 
  
    
      
        b
      
    
    {\displaystyle b}
  
 (
  
    
      
        0
        <
        b
        <
        1
      
    
    {\displaystyle 0<b<1}
  
) be the multiplicative decrease factor.
</p><p>
  
    
      
        w
        (
        t
        +
        1
        )
        =
        
          
            {
            
              
                
                  w
                  (
                  t
                  )
                  +
                  a
                
                
                  
                     if congestion is not detected
                  
                
              
              
                
                  w
                  (
                  t
                  )
                  ×
                  b
                
                
                  
                     if congestion is detected
                  
                
              
            
            
          
        
      
    
    {\displaystyle w(t+1)={\begin{cases}w(t)+a&{\text{ if congestion is not detected}}\\w(t)\times b&{\text{ if congestion is detected}}\end{cases}}}

</p><p>In TCP, after <a href="/facts/TCP_congestion_control/gC9Fer09">slow start</a>, the additive increase parameter 
  
    
      
        a
      
    
    {\displaystyle a}
  
 is typically one MSS (<a href="/facts/Maximum_segment_size/55jcCycP">maximum segment size</a>) per <a href="/facts/Round-trip_time/jYgNMK98">round-trip time</a>, and the multiplicative decrease factor 
  
    
      
        b
      
    
    {\displaystyle b}
  
 is typically 1/2.
</p>
<h2 id="protocols">Protocols</h2>
<p>AIMD congestion avoidance is or was used in:
</p>
<ul><li><a href="/facts/Transmission_Control_Protocol/WW4sPrt9">Transmission Control Protocol</a> (TCP)</li>
<li><a href="/facts/Scalable_TCP/3MCu3heF">Scalable TCP</a> (STCP)</li>
<li><a href="/facts/Transport_layer/UmIGUCeK">OSI Transport Class 4</a><a class="footnote-ref" id="fnref:2" href="#fn:2"><sup>2</sup></a></li>
<li><a href="/facts/DCCP/JyfrtQRn">DCCP</a> (in some modes)<a class="footnote-ref" id="fnref:3" href="#fn:3"><sup>3</sup></a></li>
<li><a href="/facts/DECnet/9wnFzPvn">DECnet</a><a class="footnote-ref" id="fnref:4" href="#fn:4"><sup>4</sup></a></li></ul>
<h2 id="in-nature">In nature</h2>
<p>AIMD has been found to be utilized by diverse <a href="/facts/Biological_system/yKqVbaxu">biological systems</a>, including maintaining <a href="/facts/Cell_size/wbArMaJU">cell-size</a> homeostasis and for <a href="/facts/Synaptic_plasticity/rdVFxItN">synaptic learning</a> and adaptation in <a href="/facts/Neural_circuit/pgngqMLf">neural circuits</a>.<a class="footnote-ref" id="fnref:5" href="#fn:5"><sup>5</sup></a>
</p>

<h2 id="references">References</h2>

<ol>
<li id="fn:1"><p>Chiu, Dah-Ming; Raj Jain (1989). "Analysis of increase and decrease algorithms for congestion avoidance in computer networks". Computer Networks and ISDN Systems. 17: 1–14. doi:10.1016/0169-7552(89)90019-6. <a href="/wiki/Doi_(identifier)" target="_blank">/wiki/Doi_(identifier)</a> <a href="#fnref:1" class="footnote-back-ref">↩</a></p></li>
<li id="fn:2"><p>Chiu, Dah-Ming; Raj Jain (1989). "Analysis of increase and decrease algorithms for congestion avoidance in computer networks". Computer Networks and ISDN Systems. 17: 1–14. doi:10.1016/0169-7552(89)90019-6. <a href="/wiki/Doi_(identifier)" target="_blank">/wiki/Doi_(identifier)</a> <a href="#fnref:2" class="footnote-back-ref">↩</a></p></li>
<li id="fn:3"><p>Floyd; Kohler (March 2006). Profile for Datagram Congestion Control Protocol (DCCP) Congestion Control ID 2: TCP-like Congestion Control. doi:10.17487/RFC4341. RFC 4341. <a href="https://datatracker.ietf.org/doc/html/rfc4341" target="_blank">https://datatracker.ietf.org/doc/html/rfc4341</a> <a href="#fnref:3" class="footnote-back-ref">↩</a></p></li>
<li id="fn:4"><p>Chiu, Dah-Ming; Raj Jain (1989). "Analysis of increase and decrease algorithms for congestion avoidance in computer networks". Computer Networks and ISDN Systems. 17: 1–14. doi:10.1016/0169-7552(89)90019-6. <a href="/wiki/Doi_(identifier)" target="_blank">/wiki/Doi_(identifier)</a> <a href="#fnref:4" class="footnote-back-ref">↩</a></p></li>
<li id="fn:5"><p>Suen, Jonathan Y.; Navlakha, Saket (2022). "A feedback control principle common to several biological and engineered systems". Journal of the Royal Society Interface. 19 (188): 20210711. doi:10.1098/rsif.2021.0711. PMC 8889180. PMID 35232277. <a href="https://www.ncbi.nlm.nih.gov/pmc/articles/PMC8889180" target="_blank">https://www.ncbi.nlm.nih.gov/pmc/articles/PMC8889180</a> <a href="#fnref:5" class="footnote-back-ref">↩</a></p></li>
</ol>

Additive increase/multiplicative decrease open-in-new

Additive increase/multiplicative decrease