BIC TCP (Binary Increase Congestion control) is one of the
congestion control algorithms that can be used for
Transmission Control Protocol
The Transmission Control Protocol (TCP) is one of the main protocols of the Internet protocol suite. It originated in the initial network implementation in which it complemented the Internet Protocol (IP). Therefore, the entire suite is common ...
(TCP). BIC is optimized for high speed networks with high latency: so-called "
long fat network
In data communications, the bandwidth-delay product is the product of a data link's capacity (in bits per second) and its round-trip delay time (in seconds). The result, an amount of data measured in bits (or bytes), is equivalent to the maximu ...
s". For these networks, BIC has significant advantage over previous congestion control schemes in correcting for severely underutilized bandwidth.
BIC implements a unique congestion window (cwnd) algorithm. This algorithm tries to find the maximum cwnd by searching in three parts:
binary search
In computer science, binary search, also known as half-interval search, logarithmic search, or binary chop, is a search algorithm that finds the position of a target value within a sorted array. Binary search compares the target value to the ...
increase,
additive increase, and slow start. When a network failure occurs, the BIC uses multiplicative decrease in correcting the cwnd.
BIC TCP is implemented and used by default in
Linux
Linux ( or ) is a family of open-source Unix-like operating systems based on the Linux kernel, an operating system kernel first released on September 17, 1991, by Linus Torvalds. Linux is typically packaged as a Linux distribution, w ...
kernels 2.6.8 and above. The default implementation was again changed to
CUBIC TCP
CUBIC is a network congestion avoidance algorithm for TCP which can achieve high bandwidth connections over networks more quickly and reliably in the face of high latency than earlier algorithms. It helps optimize long fat networks.
In 2006, ...
in the 2.6.19 version.
Algorithm
Define the following variables:
S
max: the maximum increment
S
min: the minimum increment
w
max: the maximum window size
β: multiplicative window decrease factor
cwnd: congestion window size
bic_inc: window increment per RTT (round trip time)
At every RTT interval update cwnd with the following:
If no packets are dropped, the congestion window (cwnd) increases in three distinct ways: binary search increase, additive increase, and slow start. In each step, one is used as an increment.
One step of increasing cwnd:
if (cwnd < w
max) // binary search OR additive
bic_inc = (w
max - cwnd) / 2;
else // slow start OR additive
bic_inc = cwnd - w
max;
if (bic_inc > S
max) // additive
bic_inc = S
max;
else if (bic_inc < S
min) // binary search OR slow start
bic_inc = S
min;
cwnd = cwnd + (bic_inc / cwnd);
If one or more packets are dropped, the cwnd is reduced using
multiplicative decrease Multiplicative may refer to:
*Multiplication
*Multiplicative function
*Multiplicative group
*Multiplicative identity
*Multiplicative inverse
*Multiplicative order
*Multiplicative partition
*Multiplicative case
* For the multiplicative numerals once, ...
. This requires β, which is used in decreasing cwnd by (100×β)%. In the case of two flows, one with a large cwnd and the other a small cwnd, ''fast convergence'' is used to decrease the greater cwnd flow's w
max at a greater rate than the smaller cwnd's flow to allow faster convergence of the greater cwnd's flow when increasing its cwnd.
One step of decreasing cwnd:
if (cwnd < w
max) // fast convergence
w
max = cwnd * (2-β) / 2;
else
w
max = cwnd;
cwnd = cwnd * (1-β);
See also
*
TCP congestion avoidance algorithm
Transmission Control Protocol (TCP) uses a network congestion-avoidance algorithm that includes various aspects of an additive increase/multiplicative decrease (AIMD) scheme, along with other schemes including #Slow start, slow start and #Conge ...
*
*
SCTP
The Stream Control Transmission Protocol (SCTP) is a computer networking communications protocol in the transport layer of the Internet protocol suite. Originally intended for Signaling System 7 (SS7) message transport in telecommunication, the p ...
*
CUBIC TCP
CUBIC is a network congestion avoidance algorithm for TCP which can achieve high bandwidth connections over networks more quickly and reliably in the face of high latency than earlier algorithms. It helps optimize long fat networks.
In 2006, ...
References
External links
Home Page.
TCP congestion control
{{compu-network-stub