【免费】CUBICANewTCP-FriendlyHighSpeedTCPVariant资源-CSDN文库

CUBIC

Congestion

5星 · 超过95%的资源需积分: 0 33 浏览量 2012-11-19 16:21:31 上传评论收藏 1.22MB PDF 举报

资源推荐

资源详情

资源评论

CUBIC: A New TCP-Friendly High-Speed TCP Variant

∗

Sangtae Ha, Injong Rhee

Dept of Computer Science

North Carolina State University

Raleigh, NC 27695

{sha2,rhee}@ncsu.edu

Lisong Xu

Dept of Comp. Sci. and Eng.

University of Nebraska

Lincoln, Nebraska 68588

xu@cse.unl.edu

ABSTRACT

CUBIC is a congestion control protocol for TCP (t ransmis-

sion control protocol) and the current default TCP algo-

rithm in Linux. The protocol modiﬁes th e linear window

growth function of existing TCP standards to be a cubic

function in order to improve the scalability of TCP over

fast and long distance networks. It also achieves more eq-

uitable bandwidth allocations among ﬂows with diﬀerent

RTTs (round trip times) by making t he window growth to

be independent of RTT – t hus those ﬂows grow their conges-

tion window at the same rate. During steady state, CUBIC

increases the window size aggressively when the window is

far from the saturation point, and the slowly when it is close

to the saturation point. This feature allows CUBIC to be

very scalable when the bandwidth and delay product of the

network is large, and at the same t ime, b e highly stable and

also fair to standard TCP ﬂows. The implementation of

CUBIC in Linux has gone through several upgrades. This

paper documents its design, implementation, performance

and evolution as the default TCP algorithm of Linux.

1. INTRODUCTION

As the Internet evolves to include many very h igh speed

and long distance network paths, the performance of TCP

was challenged. These networks are characterized by large

bandwidth and delay product (BDP) which rep resents the

total number of packets n eed ed in ﬂight while keeping the

bandwidth fully utilized, in oth er words, the size of the con-

gestion window. In standard TCP like TCP-Reno, TCP-

NewReno and TCP-SACK, TCP grows its window one per

round trip time (RTT). This makes the data transp ort speed

of TCP

∗

used in all major operating systems including Win-

dows and Linux rather sluggish, to say the least, extremely

under-utilizing the networks especially if the length of ﬂows

is much shorter than the time TCP grows its windows t o

the full size of the BDP of a path. For instance, if the band-

width of a network path is 10 Gbps and the RTT is 100 ms,

with packets of 1250 bytes, the BDP of the p ath is around

100,000 packets. For TCP to grow its window from the mid-

point of the BDP, say 50,000, it takes about 50,000 RTTs

which amounts to 5000 seconds ( 1.4 hours). If a ﬂow ﬁnishes

before that time, it severely under-utilizes the path.

To counter this under-utilization problem of TCP, many

∗

A short version [27] of this paper was presented at the Inter-

national Workshop on Protocols for Fast and Long Distance

Networks in 2005.

∗

For brevity, we also denote Standard TCP as TCP.

“high-speed ” TCP variants are proposed (e.g., FAST [24],

HSTCP [15], STCP [25], HTCP [28], SQRT [19], West-

wood [14], and BIC-TCP [30]). Recognizing this problem

with TCP, th e Linux community responded quickly to im-

plement a majority of these protocols in Linux and ship

them as part of its operating system. After a series of third-

party testing and performance validation [11, 21], in 2004,

from version 2.6.8, it selected BIC-TCP as the default TCP

algorithm and the other TCP variants as optional.

What makes BIC-TCP stand out from other TCP algor-

tihms is its stability. It uses a binary search algorithm where

the window grows to the mid-point between the last win-

dow size (i.e., max) where TCP h as a packet loss and the

last window size (i.e., min) it does not have a loss for one

RTT period. This “search” into the mid- point intuitively

makes sense because the capacity of the current path must

be somewhere between the two min and max window sizes

if the network conditions do not quickly change since the

last congestion signal (which is the last p acket loss). After

the window grows to the mid-point, if the network does not

have packet losses, then it means t hat the network can han-

dle more traﬃc and thus BIC-TCP sets the mid-point to

be the new min and performs another “bin ary-search ” with

the min and max windows. This has an eﬀect of growing

the window really fast when the current window size is far

from the available capacity of the path, and furthermore, if

it is close to the available capacity (where we had the pre-

vious loss), it slowly reduces its window increment. It has

the smallest window increment at the saturation point and

its overshoots amount beyond the saturation point where

losses occur very small. The whole window growth func-

tion is simply a logarithmic concave function. This concave

function keeps the congestion window much longer at the

saturation point or equilibrium t han convex or linear fun c-

tions where they have the largest window increment at the

saturation point and thus have the largest overshoot at th e

time packet losses occur. These features make BIC-TCP

very stable and at the same time highly scalable.

BIC-TCP trades the speed to react to changes in avail-

able bandwidth (i.e., convergence speed) for stability. If the

available capacity has increased since the last packet losses,

the window can grow beyond the max without having a loss.

At that time, BIC-TCP increases the window exponentially.

Note that an exponential function (a convex function) grows

very slowly at the beginning (slower than a linear function).

This feature adds to the stability of the protocol because

even if the protocol makes mistakes in ﬁnding the max win-

dow, it ﬁnds the next max window near the previous max

point ﬁrst, thus staying at the previous saturation point

longer. But the exponential function quickly catches up and

its increment becomes very large if the losses do not occur

(in which case, the saturation point has become much larger

than the p revious one). Because it stays longer near th e pre-

vious saturation point than oth er variants, it can be slug-

gish to ﬁnd the new saturation point if the saturation point

has increased far beyond the last one. BIC-TCP, however,

safely reacts fast to red uced capacity because packet losses

occur before the previous max and it reduces the window

by a multiplicative factor. This tradeoﬀ is a design choice

of BIC-TCP. It is known [31] that available bandwidth in

the Internet change over a long time scale of several hours.

Given that packet losses would occur very asynchronously

and also proportionally to the bandwidth consumption of a

ﬂow under a highly statistically multiplexed environment,

fast convergence is a natural consequence of the network en -

vironment – something the protocol does not have to force.

Thus, although BIC-TCP may converge slowly under low

statistical multiplexing where only a few ﬂows are compet-

ing, its convergence speed is not an issue under typical In-

ternet environments.

CUBIC [27] is the next version of BIC-TCP. It greatly sim-

pliﬁes the window adjustment algorithm of BIC-TCP by re-

placing the concave and convex window growth portions of

BIC-TCP by a cubic function (which contains both concave

and convex portions). In fact, any odd order polynomial

function has this shape. The choice for a cubic function is

incidental and out of convenience. The key feature of CU-

BIC is t hat its window growth depends only on the real time

between two consecutive congestion events. One congestion

event is the time when TCP undergoes fast recovery. We call

this real time a congestion epoch. Thus, the window growth

becomes independent of RTTs. This feature allows CUBIC

ﬂows competing in t he same bottleneck to have approxi-

mately the same window size independent of their RTTs,

achieving good RTT-fairness. Furthermore, when RTTs are

short, since the window growth rate is ﬁxed, its growth rate

could be slower than TCP stand ards. Since TCP standards

(e.g., TCP-SACK) work well under short RTTs, this feature

enhances the TCP-friendliness of the protocol.

The implementation of CUBIC in Linux has gone th rough

several upgrades. The most notable upgrade is the eﬃcient

implementation of cubic ro ot calculation. Since it requires

a ﬂoating point operation, implementing it in the kernel re-

quires some integer approximation. Initially it used the bi-

section method and later changed to the Newton-Raphson

method which red uces the computational cost almost by 10

times. Another change to CUBIC after inception is the re-

moval of window clamping. Wind ow clamping was intro-

duced in BIC-TCP where window increments are clamped

to a maximum increment and was inherited to CUBIC for

the ﬁrst version. This forces the window growth to be linear

when the target mid-point is much larger than the current

window size. The authors conclude that this feature is not

needed after extensive testing due to the increased stability

of CUBIC. CUBIC replaced BIC-TCP as the d efault TCP

algorithm in 2006 after version 2.6.18. The changes and

upgrades of CUBIC in Linux are documented in Table 1.

The remainder of this paper is organized as follows. Section

2 gives related work, Section 3 presents the details of CU-

BIC algorithms in Linux, Section 4 includes the evolution

of CUBIC and its implementation in Linux, and Section 5

includes discussion related to fairness property of CUBIC.

Section 6 presents the results of experimental evaluation and

Section 7 gives conclusion.

2. RELATED WORK

Kelly proposed Scalable TCP (STCP) [25]. The design ob-

jective of STCP is to make the recovery time from loss events

be constant regardless of the window size. This is why it

is called “Scalable”. Note t hat the recovery time of TCP-

NewReno largely depends on the current window size.

HighSpeed TCP (HSTCP) [15] uses a generalized AIMD

where the linear increase factor and multiplicative decrease

factor are adjusted by a convex fucntion of t he current con-

gestion window size. When the congestion window is less

than some cutoﬀ value, HSTCP uses the same factors as

TCP. Most of high-speed TCP variants support this form

of TCP compatibility, which is based on the window size.

When the window grows beyond the cutoﬀ point, the con-

vex function increases the increase factor and reduces the

decrease factor proportionally to the window size.

HTCP [28], like CUBIC, uses the elapsed time (∆) since

the last congestion event for calculating the current conges-

tion window size. The window growth function of HTCP

is a quadratic function of ∆. HTCP is unique in that it

adjusts the decrease factor by a function of RTTs which is

engineered to estimate the queue size in the network path

of the current ﬂow. Thus, the decrease factor is adjusted to

be proportional to the queue size.

TCP-Vegas [10] measures the diﬀerence (δ) between expected

throughput and actual throughput based on round-trip de-

lays. When δ is less than a low threshold α, TCP-Vegas

believes the path is not congested and thus increases the

sending rate. When δ is larger than a upper threshold β,

which is a strong indication of congestion, TCP-Vegas re-

duces the sending rate. Otherwise, TCP-Vegas maintains

the current sending rate. The expected throughput is cal-

culated by dividing the current congestion window by the

minimum RTT which typically contains the delay when the

path is n ot congested. For each round trip time, TCP-Vegas

computes the actual throughput by dividing the number of

packets sent by the sampled RTT.

FAST [24] determines the current congestion window size

based on both round-trip delays and packet losses over a

path. FAST updates the sending rate at every other RTT

with rate-pacing. The algorithm estimates the queuing de-

lay of t he path using RTTs and if the delay is well below

a threshold, it increases the window aggressively and if it

gets closer to the threshold, the algorithm slowly reduces

the increasing rate. The opposite happens when the delay

increases beyond the threshold: slowly decreases the window

ﬁrst and then aggressively decreases the window. For packet

losses, FAST halves the congestion window and enters loss

recovery just like TCP.

TCP-Westwood [14] estimates an end-to-end available band-

width by accounting the rate of returning ACKs. For packet

losses, unlike TCP which “blindly” reduces the congestion

window to the half, TCP-Westwood sets the slow start thresh-

old to this estimate. This mechanism is eﬀective especially

over wireless links where frequent channel losses are mis-

interpreted as congestion losses and thus TCP reduces th e

congestion window unn ecessarily.

TCP-Illinois [26] uses a queueing delay to determine an in-

crease factor α and multiplicative decrease factor β instan-

taneously during the window increment phase. Precisely,

TCP-Illinois sets a large α and small β when the average

delay d is small, which is the indication that congestion is

not imminent, and sets a small α and large β when d is large

because of imminent congestion.

TCP-Hybla [13] scales the window increment rule to ensure

fairness among the ﬂows with diﬀerent RTTs. TCP-Hybla

behaves as TCP-NewReno when the RTT of a ﬂow is less

than a certain reference RTT (e.g., 20ms). Otherwise, TCP-

Hybla increases t he congestion window size more aggres-

sively to compensate throughput drop due to RTT increase.

TCP-Veno [17] determines the congestion window size very

similar to TCP-NewReno, but it uses the delay information

of TCP-Vegas to diﬀerentiate non-congestion losses. When

packet loss happens, if the queue size inferred by the delay

increase is within a certain threshold, which is the strong

indication of random loss, TCP-Veno reduces the congestion

window by 20%, not by 50%.

3. CUBIC CONGESTION CONTROL

3.1 BIC-TCP

In this section, we give some details on BIC-TCP which is a

predecessor of CUBIC. The main feature of BIC-TCP is its

unique window growth function as discussed in the introduc-

tion. Figure 1 shows the growth function of BIC-TCP. When

it gets a packet loss event, BIC-TCP reduces its window by

a multiplicative factor β. The window size just before the

reduction is set to the maximum W

max

and the window size

just after the reduction is set to the minimum W

min

. Then,

BIC-TCP performs a binary search using these two param-

eters - by jumping to the “midpoint” between W

max

and

min

. Since packet losses have occurred at W

max

, the win-

dow size that the network can currently hand le without loss

must b e somewhere between these two numbers.

However, jumping to the midpoint could be too much in-

crease within one RTT, so if the distance between the mid-

point and the current minimum is larger than a ﬁxed con-

stant, called S

max

, BIC-TCP increments cwnd by S

max

(lin-

ear increase). If BIC-TCP does not get packet losses at the

updated window size, that window size becomes the new

minimum. This process continues until the window incre-

ment is less than some small constant called S

min

at which

point, the window is set to the current maximum. So the

growth fun ction 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” respectively in Fig-

ure 1 (a).)

If the window grows past the maximum, the equilibrium

window size must be larger than the current maximum and a

(a) BIC-TCP window growth function.

(b) CUBIC window growth fun ction.

Figure 1: Window growth functions of BIC-TCP

and CUBIC.

new maximum must be found. BIC-TCP enters a new phase

called “max probing”. Max probing uses a window growth

function exactly symmetric to those used in additive increase

and binary search (which is logarithmic; its reciprocal will

be exponential) and then additive increase. Figure 1 (a)

shows the growth function during max probing. D uring max

probing, the window grows slowly initially to ﬁnd the new

maximum nearby, and after some time of slow growth, if it

does not ﬁnd 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 ﬁxed increment.

The good performance of BIC-TCP comes from th e slow

increase around W

max

and linear increase during additive

increase and max probing.

3.2 CUBIC window growth function

BIC-TCP achieves good scalability in high speed networks,

fairness among competing ﬂows of its own and stability with

low window oscillations. However, BIC-TCP’s growth func-

tion can still be too aggressive for TCP, especially under

short RTT or low speed networks. Furthermore, the several

diﬀerent phases (binary search increase, max probing, S

max

and S

min

) of window control add complexity in implement-

ing the protocol and analyzing its performance. We have

been searching for a n ew window growth function that while

retaining strengths of BIC-TCP (especially, its stability and

scalability ), simpliﬁes the window control and enhances its

TCP friendliness.

We introduce a new high-speed TCP variant: CUBIC. As

the name of the protocol represents, t he window growth

function of CUBIC is a cubic function whose shape is very

similar to the growth function of BIC-TCP. CUBIC uses a

cubic function of the elapsed time from the last congestion

event. While most alternative algorithms to Standard TCP

uses a convex increase function where after a loss event, the

剩余10页未读，继续阅读

评论收藏

内容反馈

yhuazz

2018-05-15

内容非常好，很有帮助，有用！
bydyes

2021-08-03

非常好，正是我需要的

masikkk

粉丝: 1622
资源: 105

CUBIC A New TCP-Friendly HighSpeedTCP Variant

最新资源

CUBIC A New TCP-Friendly HighSpeedTCP Variant

micropython-build-cubic-f5270-20220717

Cubic Spline-SOFR-Git.py

tcp cubic算法学习笔记

Linux的TCP拥塞控制算法CUBIC

TCP拥塞算法reno_bic_cubic概述与对比.pdf

cubic-light-source-programs.zip_51 8光立方

Cubic插件使用的three.min.js版本

cubic-1.1.min.js三维饼图和三维柱形图插件

利用数据挖掘技术改进TCP CUBIC拥塞控制算法.pdf

matlab代码中cubic是什么意思-made-in-netherlands:Netherlands在荷兰进行的整洁项目清单

cubic_.rar_B-spline_Cubic Spline_cubic_cubic matlab_subdivision

average-cubic-weight-pkg

matlab代码中cubic是什么意思-pisguru:OpenCV+机器学习

matlab代码中cubic是什么意思-my-data-science-tool-belt:展示我的数据科学工具套件，该套件可以帮助学生更好地

android-cubic-bezier-interpolator:已弃用，支持 https

matlab代码中cubic是什么意思-predicting-viral-topics:在慕尼黑工业大学内部进行的跨学科项目“预测社交媒体上的

matlab代码中cubic是什么意思-pandas-machine-learning-intro:熊猫入门（用于机器学习）

Cubic-S_en_robot_

cubic-bezier:三次贝塞尔曲线编辑器

2023.10.21 雷蛇+鼠标宏+PUBG+绝地求生 步枪通用

115转存助手ui优化版3.9.1网友魔改-转存提取全修复-user

恩山新版中兴Telnet工具体验版-20230830.rar

基于华为eNSP的校园网设计和仿真模拟.zip

蓝牙驱动，解决win11下的设备管理器蓝牙报错提示为：Generic Bluetooth Adapter驱动感叹号解

大漠插件3.1233全套

csgo鼠标宏，lua格式

Chrome浏览器 v109.0.5414.75稳定版 64位 离线安装包

高逼格PPT模板20套.rar

OpenGD77刷机材料

最新资源

2023.10.21 雷蛇+鼠标宏+PUBG+绝地求生步枪通用

Chrome浏览器 v109.0.5414.75稳定版 64位离线安装包