EditWYSIWYGAttachPrintable
r20 - 19 Mar 2008 - 22:07:13 - Main.sha2You are here: TWiki >  Main Web > ResearchGroups > Transport > BIC

BIC and CUBIC

The demands for fast transfer of large volumes of data, and the deployment of the network infrastructures to support the demand are ever increasing. However, the dominant network transport protocol of today, TCP, does not meet this demand. The slow response of TCP in fast long distance networks leaves sizeable unused bandwidth in such networks. BIC TCP and CUBIC are congestion control protocols designed to remedy this problem. Our goal is to design a protocol that can scale its performance up to several tens of gigabits per second over high-speed long distance networks while maintaining strong fairness, stability and TCP friendliness.

News

Date Description
2008/03/05 TCP testing results are available on line
Tested kernel version: 2.6.25-rc3
2008/03/04 CUBIC implementation in Linux kernel has been updated and synced with the NS2 simulation code.
See the changelog for this update.
Now, CUBIC has a good convergence time and scalability
2007/11/29 BIC and CUBIC NS2 simulation code has been updated. Now it is the same as the linux version.
A link to download is here
More ...

Media Coverage

Kyle Schurman wrote an article, BIC-TCP, Giving Researchers High-Speed Hopes.

BIC Overview

bic_curve.PNG
Fig.1 the growth function of BIC

The main feature of BIC is its unique window growth function. Fig. 1 shows the growth function of BIC. When it gets a packet loss event, BIC reduces its window by a multiplicative factor (beta). The window size just before the reduction is set to the maximum and the window size just after the reduction is set to the minimum. Then, BIC performs a binary search using these two parameters – by jumping to the “midpoint” between the maximum (Wmax) and the minimum (Wmin). Since packet losses have occurred at Wmax the window size that the network can currently handle without loss must be somewhere between these two numbers.

However, jumping to the midpoint could be too much increase within one RTT, so if the distance between the midpoint and the current minimum is larger than a fixed constant, called Smax, BIC increments the current window size by Smax (linear increase). If BIC does not get packet losses at the updated window size, that window size becomes the new minimum. If it gets a packet loss, that window size becomes the new maximum. This process continues until the window increment is less than some small constant called Smin at which point, the window is set to the current maximum. So the growing function after a window reduction will be most likely to be a linear one followed by a logarithmic one (marked as "additive increase" and "binary search" in the figure).

If the window grows past the maximum, the equilibrium window size must be larger than the current maximum and a new maximum must be found. BIC enters a new phase called "max probing". The growth function during max probing is the inverse of those in binary search and additive increase. It grows exponentially (which is very slow at the beginning) and then linearly. Max probing uses a window growth function exactly symmetric to those used in binary increase (additive increase and binary search) -- only in a different order: it uses the inverse of binary search (which is logarithmic; its reciprocal will be exponential) and then additive increase. Fig.1 shows the growth function during max probing. During max probing, the window grows slowly initially to find the new maximum nearby, and after some time of slow growth, if it does not find the new maximum, i.e., packet losses, then it guesses the new maximum is further away so it switches to a faster increase by switching to additive increase where the window size is incremented by a large fixed increment.

The good performance of BIC comes from the slow increase (see "plateau" in the figure) around Wmax and linear increase during additive increase and max probing.

  • First it gives TCP friendliness. During this time, the window growth is slower than TCP so that the plateau gives time for competing TCP flows to grow their windows.
  • Second, it enhances the stability of the protocol and the network. As the window gets closer to the maximum, this plateau keeps the window near that maximum a long time. This has an effect of reducing window fluctuations. In fact, the window increment just before the maximum is the smallest (this feature contrasts with other protocols where the increment is the largest near the maximum). BIC tends to overshoot over the network capacity by a smaller amount than other protocols. This tends to reduce the impact of the overshoot to other competing flows.
  • Third, the plateau increases the utilization of the network. In steady state, the network is in the full utilization at Wmax. Since BIC keeps the network in the full utilization for a longer time (even with a small buffer at the router), it tends to achieve higher network utilization than other protocols.
  • Fourth, the linear increase during additive increase and max probing also helps improve the fairness of the protocol. It makes the protocol behave like AIMD. AIMD achieves bounded RTT fairness where the throughput ratio of two competing flows with different RTTs is bounded by the square of the RTT ratio. It also achieves the fair bandwidth share among competing BIC flows with the same RTTs. BIC inherits these features of AIMD.

CUBIC Overview

Three new features of CUBIC.

  1. New window growth function (cubic)
  2. New TCP friendly mode
  3. Low utilization detection

1. New window growth function (cubic)

Although BIC achieves pretty good scalability, fairness, and stability during the current high speed environments, the BIC's growth function can still be too aggressive for TCP, especially under short RTT or low speed networks. Furthermore, the several different phases of window control adds a lot of complexity in analyzing the protocol. We have been searching for a new window growth function that while retaining most of strengths of BIC (especially, its stability and scalability), simplifies the window control and enhances its TCP friendliness.

In the new release of BIC, we introduce a new window growth function – a cubic function. Figure 2 shows a cubic function whose shape is similar to the BIC window curve [See Figure 1 in BIC overview page]. The function grows much slower than binary increase (which is the logarithmic) near the origin (or plateau).

cubic_curve.PNG
Fig.2: the cubic window growth function of CUBIC

We set the origin to be Wmax. So after a window reduction, the window grows very fast, but as it gets closer to Wmax, it slows down its growth. At Wmax, its increment becomes zero. After that, the window grows slowly, accelerating its growth as it moves away from Wmax. It has the same plateau as in BIC's window curve, but its growth rate accelerates much more slowly than BIC's. This slow growth significantly contributes to the improved TCP friendliness of the protocol. Furthermore, the function extremely simplifies the window control since there are only one function to use and no multiple phases.

Let us examine these features in more detail.

Two issues need attention: RTT-fairness and intra-protocol fairness. Since AIMD is no longer used, we need special mechanisms to ensure these fairness properties. Our strategy for ensuring these properties is to allow the window to grow at a rate dependent on the elapsed time after the last packet loss event. This strategy is also adopted by SQRT and HTCP. More specifically, the window size W is determined by the following function.

\begin {eqnarray} W_{cubic} = C(T-K)^3 + W_{max} \end {eqnarray}

C is a scaling constant, and K = \sqrt[3]{\frac{W_{max}\beta}{C}}

Wmax is the window size just before the last window reduction, T is the elapsed time from the last window reduction, and beta is the multiplicative decrease factor after a packet loss event.

This function ensures the intra-protocol fairness among the competing flows of the same protocol. To see this, suppose that two flows are competing on the same end-to-end path. The two flows converge to a fair share since they drop by the same multiplicative factor beta -- so a flow with larger Wmax will reduce more, and the growth function allows the flow with larger Wmax will increase more slowly – K is larger as Wmax is larger.

The function also offers a good RTT fairness property because the window growth rate is dominated by T, the elapsed time. This ensures linear RTT fairness since any competing flows with different RTT will have the same T after a synchronized packet loss (note that TCP and BIC offer square RTT fairness in terms of throughput ratio).

BIC increases the window additively when the window increment per RTT becomes larger than some constant. However, CUBIC increases its window to be real-time dependent; when under short RTTs, the linear increment per RTT is smaller although stays constant in real time.

The real-time increase of the window enormously helps enhance the TCP friendliness of the protocol. Note that the window growth function of other RTT dependent protocols (TCP being a good example), grows proportionally faster (in real time) in shorter RTT networks whereas CUBIC will grow independently of RTT. Since TCP gets more aggressive while CUBIC being unchanged, short RTT network environments will make CUBIC more friendly to TCP.

The cubic function is very TCP friendly as well. Note that when the window size is small, its Wmaxβ is small. This means that K is small and therefore, the growth rate of the cubic function is very slow – even slower than TCP’s. Thus, when the BDP of the network is small, CUBIC becomes very friendly to TCP.

We empirically set C to 0.4, Smax to 160, and beta to 0.2. Based on our analysis, these values give reasonable TCP friendliness, fairness, scalability, and convergence speed.

Note that the entire window growth function is described by just one function – in CUBIC, we don't need different phases of window control like additive increase, binary search, and max probing in BIC. This immensely simplifies our analysis of CUBIC. We omit the formal analytical evaluation of CUBIC here and defer it to a future research paper.

2. New TCP mode

We mentioned that the window growth rate of CUBIC can be slower than TCP under short RTT and/or small BDP (bandwidth delay product) networks. In order to achieve comparable performance to TCP in this regime, we allow the window of CUBIC to grow at least at the speed of TCP. We accomplish this by adding a "TCP" mode.

Most high-speed TCP variant protocols have some form of “TCP modes” during which a protocol behaves in the same way as TCP. HSTCP and STCP enter their TCP modes when the window size is less than some small cutoff constant (typically around 30 packets). This cutoff value is determined by the intersection point between the response function of a high speed protocol and that of TCP. Note that a response function of a protocol is the sending packet rate per RTT (or window size) in terms of packet loss rates. BIC also adopts this approach. However, this approach has a major drawback. TCP may give very good performance even if the window size gets larger than 30. This happens when RTT is very short, but big enough to make its BDP larger than the cutoff value. For instance, 200Mb/s bandwidth and 10 ms RTT gives BDP around 200 but TCP performs very well in this environment, utilizing the full bandwidth. If used in this environment, this approach can make BIC (also HSTCP and STCP) too aggressive for competing TCP flows sometimes.

In fact, our observation is that the regime where TCP performs well is defined by the congestion epoch size (not by the window size) – the period between two consecutive loss events. For instance, if RTT is 1 ms, TCP can grow its window by 1000 packets per second (with delayed ack, by 500), and this speed should be fast enough to fully utilize the capacity in most of large bandwidth networks (if there is enough buffer space in the bottleneck link). On the other hand, if RTT is 200ms, then TCP can grow its window by 5 packets per second. This could be too slow for a large BDP network. Controlling the TCP mode using only the window size may not be applicable for all situations. On the other hand, the congestion epoch can tell whether the network environment is good for TCP.

CUBIC solves this problem quite elegantly. Since the window growth rate of CUBIC is independent of RTT, as TCP changes aggressiveness based on RTT, the real time duration that CUBIC grows more slowly than TCP after the previous epoch is determined by the aggressiveness of TCP. As TCP becomes very aggressive, this "TCP friendly period" becomes longer.

In order to estimate the growth rate of TCP, we emulate the TCP window adjustment algorithm after a packet loss event. To be more accurate, we need to compare the throughput of TCP and CUBIC. However, we believe that estimating the window growth rate would be a close approximation to the throughput.

Since CUBIC reduces its window by a factor of β after a loss event, the TCP fair rate would be 3((1-β)/(1+β)) per RTT. This is because the average sending rate of AIMD is

$ \frac{1}{RTT} \sqrt{\frac{\alpha}{2} \frac{1+\beta}{1-\beta} \frac{1}{p}} $
where α is the additive window increment and p is the loss rate. Therefore, TCP will get
$ \frac{1}{RTT} \sqrt{\frac{3}{2} \frac{1}{p}} $
since α=1 and β=1/2. To achieve the same average sending rate as TCP with an arbitrary beta, we need alpha equal to 3((1-β)(1+β)). Since we set to 0.2, the additive increase factor is 0.5. Given this growth rate per RTT, the window size of TCP at time t (after the last epoch) is

\begin \mbox{W}_{tcp} = {\beta}{W_{max}} + 3(\frac{1-\beta}{1+\beta})\frac{t}{RTT} \end

If tcp is larger than clamped Wcubic (in eqn. 1), then we set the window size to Wtcp. Otherwise, clamped Wcubic is the current congestion window size. Note that clamped Wcubic is obtained by clamping Wcubic in eqn. 1 to grow no faster than Smax per second.

Stability Study of BIC and CUBIC

Slow Start of BIC and CUBIC

Download

Since Linux 2.6.13, BIC had been included in the standard Linux distribution and set to the default TCP. Currently, the successor of the BIC, CUBIC, is set to default. If your kernel version is greater than 2.6.13, please download the source codes of BIC and CUBIC from standard linux kernel archives. Optionally, you can directly refer the source code of BIC (tcp_bic.c) and CUBIC (tcp_cubic.c) from LXR (Linux Cross Reference).

BIC download

Latest BIC NS2 Simulation Code

We release the NS2 implementation of BIC protocol, which has been changed to match Linux implementation. We remove the low utilization detection mechanism to match with Linux implementation.

File Name Installation HowTo Comment NS Version Results Last updated
ns_bic_cubic_v1.zip txt README BIC and CUBIC simulation code NS2 2.6 [1][2][more..] 11/29/2007

Old BIC NS2 Simulation Versions

File Name Installation HowTo Comment NS Version Last updated
bic-infocom2004-code.zip html README NS2 Simulation scripts for INFOCOM 2004 BIC paper NS2 2.6 07/02/2004
bic-ns-code.zip txt README Historical version of BIC simulation NS2 2.6 08/01/2003

Old Linux Kernel Patches

Do not use this patch unless your kernel version is less than 2.6.13. Recent Linux kernel includes the latest update.
File Name Kernel version Comment Last updated
html installbic_2.6.13.htm Linux kernel 2.6.13 BIC Install Howto for Linux 2.6.13 Kernel 11/16/2005
txt bic-kernel-2.6.13.patch Linux kernel 2.6.13 BIC Linux 2.6.13 Kernel Patch 11/16/2005
txt sack-fastpath-kernel-2.6.13.patch Linux kernel 2.6.13 SACK patch for Linux 2.6.13 Kernel 11/16/2005
html installbic.htm Linux kernel 2.4.25 BIC Install Howto for Linux 2.4.25 07/02/2004
txt bictcp-web100.2.3.6-kernel2.4.25.patch Linux kernel 2.4.25 BIC Linux 2.4.25 Web100 Patch 07/02/2004

CUBIC download

Lastest CUBIC NS2 Simulation Code

File Name Installation HowTo Comment NS Version Results Last updated
ns_bic_cubic_v1.zip txt README BIC and CUBIC simulation code NS2 2.6 [1][2][more..] 11/29/2007

Old CUBIC NS2 Simulation Versions

File Name Installation HowTo Comment NS Version Last updated
ns2-cubic-pfldnet2005.zip html README NS simulation code for PFLDnet 2005 paper NS2 2.6 02/17/2005

Old Linux Kernel Patches

Do not use this patch unless your kernel version is less than 2.6.13. Recent Linux kernel includes the latest update.
File Name Kernel version Comment Last updated
html installbic_2.6.13.htm Linux kernel 2.6.13 CUBIC Install Howto for Linux 2.6.13 Kernel 11/16/2005
txt cubic-kernel-2.6.13.patch Linux kernel 2.6.13 CUBIC Linux 2.6.13 Kernel Patch 11/16/2005
txt sack-fastpath-kernel-2.6.13.patch Linux kernel 2.6.13 SACK patch for Linux 2.6.13 Kernel 11/16/2005
html installbic.htm Linux kernel 2.4.25 CUBIC Install Howto for Linux 2.4.25 07/02/2004
txt cubictcp-web100.2.3.6-kernel2.4.25.patch Linux kernel 2.4.25 BIC Linux 2.4.25 Web100 Patch 07/02/2004

Experimental Results

Members

Faculty

Ph.D Students

Postdoctorial Fellows

  • Long Le (Currently at Technische Universiat Berlin)
  • Lisong Xu (Currently Assistant Professor at Univ. of Nebraska, Lincoln)

Visiting Scientists

Publications

Journal

  • Sangtae Ha, Long Le, Injong Rhee and Lisong Xu, Impact of Background Traffic on Performance of High-speed TCP Variant Protocols, Computer Networks: The International Journal of Computer and Telecommunications Networking, Volume 15, Issue 4, Aug. 2007, Page(s):852 - 865, 2007.pdf PDF

Internet Drafts

Conferences

  • Sangtae Ha and Injong Rhee, Hybrid Slow Start for High-Bandwidth and Long-Distance Networks, PFLDnet, Manchester, UK, 2008 pdf PDFppt PPT
  • Lachlan Andrew, Cesar Marcondes, Sally Floyd, Lawrence Dunn, Romaric Guillier, Wang Gang, Lars Eggert, Sangtae Ha and Injong Rhee, Towards a Common TCP Evaluation Suite, PFLDnet, Manchester, UK, 2008pdf PDF
  • H. Cai, D. Eun, S. Ha, I. Rhee and L. Xu, Stochastic Ordering for Internet Congestion Control and its Applications, Infocom, IEEE, Anchorage, Alaska, USA, 2007 pdf PDF ppt PPT
  • H. Cai, D. Eun, S. Ha, I. Rhee and L. Xu, Stochastic Ordering for Internet Congestion Control, PFLDnet, to appear, 2007 pdf PDF ppt PPT
  • Sangtae Ha, Yusung Kim, Long Le, Injong Rhee and Lisong Xu, A Step toward Realistic Performance Evaluation of High-Speed TCP Variants, PFLDnet, Nara, Japan, 2006. pdf PDF ppt PPT
  • Injong Rhee and Lisong Xu, CUBIC: A New TCP-Friendly High-Speed TCP Variants, PFLDnet, Lyon, France, 2005. pdf PDF ppt PPT
  • Lisong Xu, Khaled Harfoush, and Injong Rhee, Binary Increase Congestion Control for Fast, Long Distance Networks, Infocom, IEEE, 2004. pdf PDF ppt PPT

Technical Reports

  • Sangtae Ha, Yusung Kim, Long Le, Injong Rhee, and Lisong Xu, A step toward realistic evaluation of high-speed TCP protcols, Web-based Technical Report. html HTML

-- Main.sha2 - 29 Nov 2007

Edit | WYSIWYG | Attach | Printable | Raw View | Backlinks: Web, All Webs | History: r20 < r19 < r18 < r17 < r16 | More topic actions
Main.BIC moved from Main.BIC-TCP on 10 Sep 2007 - 15:49 by Main.sha2 - put it back
 
Powered by TWiki
This site is powered by the TWiki collaboration platformCopyright © by the contributing authors. All material on this collaboration platform is the property of the contributing authors.
Ideas, requests, problems regarding TWiki? Send feedback