This commit implements a new TCP congestion control algorithm, namely Agile-SD.
A detailed description of Agile-SD is published in the following 2 articles:
[1] "Agile-SD: a Linux-based TCP congestion control algorithm for supporting high-speed and short-distance networks",
Alrshah, M.A., Othman, M., Ali, B. and Hanapi, Z.M. Journal of Network and Computer Applications, Vol. 55, pages.181-190, May-June 2015.
[2] "Modeling the Throughput of the Linux-Based Agile-SD Transmission Control Protocol",
Alrshah, M.A., Othman, M., Ali, B. and Hanapi, Z.M.
IEEE Access journal, Vol. 4, pages.9724-9732, Jan 2017.
The Internet has predominantly used Reno or CUBIC, relying on packet loss as the
signal to slow down. While this worked well for many years, these congestion control
algorithms are unfortunately unable to present an acceptable bandwidth utilization
over today's networks. On today's Internet, data losses are very common and the
existing congestion control algorithms are very sensitive to packet losses causing
unwanted delay and retransmission of data. Also, the existing congestion control
algorithms shows long epochs which affect the general performance of TCP.
Agile-SD has significantly increased throughput, reduced sensitivity to packet loss,
and improved the ability to work with small and large buffers. Agile-SD shrinks the
needed epoch time to recover after data loss, which improves throughput up to 50% in
many cases, see [1,2].
Agile-SD is a Congestion Control Algorithm for High-speed Networks. Agile-SD is a
loss-based and RTT-independent TCP congestion control algorithm designed to support
high-speed networks. Agile-SD requires only changes on the sender side, not in the
network or the receiver side. So, it can be incrementally deployed on today's Internet
and/or in datacenters. Agile-SD introduces the Agility Factor Mechanism (AFM), which
allows Agile-SD to deal with small buffer sizes while reducing its sensitivity to packet
loss. Due to the use of this mechanism, Agile-SD improves the throughput of TCP up to 50%
compared to Cubic-TCP and Compound-TCP in many cases, especially when the buffer is small
and the data loss is common. Its performance was evaluated using simulation and testbed
to measure the average throughput, loss ratio, and fairness.
Our long-term goal is to improve the congestion control algorithms used on the Internet.
We are hopeful that Agile-SD can help advance the efforts toward this goal, and motivate
the community to do further research.
Signed-off-by: Mohamed A. Alrshah <redacted>
Signed-off-by: Mohamed Othman <redacted>
Signed-off-by: Borhanuddin Ali <redacted>
Signed-off-by: Zurina Hanapi <redacted>
---
net/ipv4/Kconfig | 15 ++++
net/ipv4/Makefile | 1 +
net/ipv4/tcp_agilesd.c | 193 +++++++++++++++++++++++++++++++++++++++++++++++++
3 files changed, 209 insertions(+)
create mode 100755 net/ipv4/tcp_agilesd.c
@@ -0,0 +1,193 @@+/* Agile-SD is a Loss-Based Congestion Control Algorithm for High-speed Networks. +*Agile-SDisanewloss-basedandRTT-independentTCPcongestioncontrolalgorithm+*designedtosupporthigh-speednetworks.ItintroducestheAgilityFactorMechanism(AFM),+*whichallowsAgile-SDtodealwithsmallbuffersizeswhilereducingitssensitivityto+*packetloss.Duetotheuseofthismechanism,Agile-SDimprovesthethroughputofTCP+*upto50%comparedtoCubic-TCPandCompound-TCPinmanycases,especiallywhenthebuffer+*issmallandthedatalossiscommon.Itsperformancewasevaluatedusingsimulationand+*testbedtomeasuretheaveragethroughput,lossratio,andfairness.+*+*Agile-SDisdescribedindetailin:+*"Agile-SD: a Linux-based TCP congestion control algorithm for supporting high-speed and short-distance networks",+*Alrshah,M.A.,Othman,M.,Ali,B.andHanapi,Z.M.+*JournalofNetworkandComputerApplications,Vol.55,pages.181-190,May-June2015.+*+*Moreover,Agile-SDperformancehasbeenmathematicallyprovenin:+*"Modeling the Throughput of the Linux-Based Agile-SD Transmission Control Protocol",+*Alrshah,M.A.,Othman,M.,Ali,B.andHanapi,Z.M.+*IEEEAccessjournal,Vol.4,pages.9724-9732,Jan2017.+*/++#include<linux/mm.h>+#include<linux/module.h>+#include<linux/math64.h>+#include<net/tcp.h>++#define SCALE 1000 /* Scale factor to avoid fractions */+#define Double_SCALE 1000000 /* Double_SCALE must be equal to SCALE^2 */+#define beta 900 /* beta for multiplicative decrease */++/* Agile-SD Parameters */+structagilesdtcp{+u32loss_cwnd;/* congestion window at last loss.*/+u32frac_tracer;/* This is to trace the fractions of the increment.*/+u32degraded_loss_cwnd;/* loss_cwnd after degradation.*/+enumdystate{SS=0,CA=1}agilesd_tcp_status;+};++/* To reset the parameters if needed*/+staticinlinevoidagilesdtcp_reset(structsock*sk)+{++}++/* This function is called after the first acknowledgment is received and before the congestion+*controlalgorithmwillbecalledforthefirsttime.Ifthecongestioncontrolalgorithmhas+*privatedata,itshouldinitializeitsprivatedatehere.*/+staticvoidagilesdtcp_init(structsock*sk)+{+structagilesdtcp*ca=inet_csk_ca(sk);++/* The value of initial_ssthresh parameter is not used here, thus, snd_ssthresh is initialized by a large value.*/+tcp_sk(sk)->snd_ssthresh=0x7fffffff;++ca->loss_cwnd=0;+ca->frac_tracer=0;+ca->agilesd_tcp_status=SS;+}++/* This function is called whenever an ack is received and the congestion window can be increased.+*Thisisequivalenttoopencwndintcp.cc.+*ackisthenumberofbytesthatareacknowledgedinthelatestacknowledgment;+*rttisthetherttmeasuredbythelatestacknowledgment;+*in_flightisthepacketinflightbeforethelatestacknowledgment;+*good_ackisanindicatorwhetherthecurrentsituationisnormal(noduplicateack,nolossandnoSACK).*/+staticvoidagilesdtcp_cong_avoid(structsock*sk,u32ack,u32in_flight)+{+structtcp_sock*tp=tcp_sk(sk);+structagilesdtcp*ca=inet_csk_ca(sk);+u32inc_factor;+u32ca_inc;+u32current_gap,total_gap;+/* The value of inc_factor is limited by lower_fl and upper_fl.+*Thelower_flmustbealways=1.Thegreatertheupper_flthehighertheaggressiveness.+*But,ifupper_flsetto1,Agile-SDwillworkexactlyasnewreno.+*Wehavealreadydesignedanequationtocalculatetheoptimumupper_flbasedonthegivenbeta.+*Thisequationwillberevealedonceitsarticleispublished*/+u32lower_fl=1*SCALE;+u32upper_fl=3*SCALE;++if(!tcp_is_cwnd_limited(sk))return;++if(tp->snd_cwnd<tp->snd_ssthresh){+ca->agilesd_tcp_status=SS;+tcp_slow_start(tp,in_flight);+}+else{+ca->agilesd_tcp_status=CA;++if(ca->loss_cwnd>ca->degraded_loss_cwnd)+total_gap=ca->loss_cwnd-ca->degraded_loss_cwnd;+else+total_gap=1;++if(ca->loss_cwnd>tp->snd_cwnd)+current_gap=ca->loss_cwnd-tp->snd_cwnd;+else+current_gap=0;++inc_factor=min(max(((upper_fl*current_gap)/total_gap),lower_fl),upper_fl);++ca_inc=((inc_factor*SCALE)/tp->snd_cwnd);/* SCALE is used to avoid fractions*/++ca->frac_tracer+=ca_inc;/* This in order to take the fraction increase into account */+if(ca->frac_tracer>=Double_SCALE)/* To take factor scale into account */+{+tp->snd_cwnd+=1;+ca->frac_tracer-=Double_SCALE;+}+}+}++/* This function is called when the TCP flow detects a loss.+*Itreturnstheslowstartthresholdofaflow,afterapacketlossisdetected.*/+staticu32agilesdtcp_recalc_ssthresh(structsock*sk)+{+conststructtcp_sock*tp=tcp_sk(sk);+structagilesdtcp*ca=inet_csk_ca(sk);++ca->loss_cwnd=tp->snd_cwnd;++if(ca->agilesd_tcp_status==CA)+ca->degraded_loss_cwnd=max((tp->snd_cwnd*beta)/SCALE,2U);+else+ca->degraded_loss_cwnd=max((tp->snd_cwnd*beta)/SCALE,2U);++ca->frac_tracer=0;++returnca->degraded_loss_cwnd;+}++staticu32agilesdtcp_undo_cwnd(structsock*sk)+{+conststructtcp_sock*tp=tcp_sk(sk);+conststructagilesdtcp*ca=inet_csk_ca(sk);+returnmax(tp->snd_cwnd,ca->loss_cwnd);+}++/* This function is called when the congestion state of the TCP is changed.+*newstateisthestatecodeforthestatethatTCPisgoingtobein.+*Thepossiblestatesarelistedbelow:+*Thecurrentcongestioncontrolstate,whichcanbeoneofthefollowings:+*TCP_CA_Open:normalstate+*TCP_CA_Recovery:LossRecoveryafteraFastTransmission+*TCP_CA_Loss:LossRecoveryafteraTimeout+*(ThefollowingtwostatesarenoteffectiveinTCP-LinuxbutiseffectiveinLinux)+*TCP_CA_Disorder:duplicatepacketsdetected,buthaven'treachthethreshold.SoTCPshallassumethatpacketreorderingishappening.+*TCP_CA_CWR:thestatethatcongestionwindowisdecreasing(afterlocalcongestioninNIC,orECNandetc).+*Itistonotifythecongestioncontrolalgorithmandisusedbysome+*algorithmswhichturnofftheirspecialcontrolduringlossrecovery.*/+staticvoidagilesdtcp_state(structsock*sk,u8new_state)+{+if(new_state==TCP_CA_Loss)+agilesdtcp_reset(inet_csk_ca(sk));+}++/* This function is called when there is an acknowledgment that acknowledges some new packets.+*num_ackedisthenumberofpacketsthatareacknowledgedbythisacknowledgments.*/+staticvoidagilesdtcp_acked(structsock*sk,u32num_acked,s32rtt_us)+{++}++staticstructtcp_congestion_opsagilesdtcp__read_mostly={+.init=agilesdtcp_init,+.ssthresh=agilesdtcp_recalc_ssthresh,+.cong_avoid=agilesdtcp_cong_avoid,+.set_state=agilesdtcp_state,+.undo_cwnd=agilesdtcp_undo_cwnd,+.pkts_acked=agilesdtcp_acked,+.owner=THIS_MODULE,+.name="agilesd",+};++staticint__initagilesdtcp_register(void)+{+BUILD_BUG_ON(sizeof(structagilesdtcp)>ICSK_CA_PRIV_SIZE);+returntcp_register_congestion_control(&agilesdtcp);+}++staticvoid__exitagilesdtcp_unregister(void)+{+tcp_unregister_congestion_control(&agilesdtcp);+}++module_init(agilesdtcp_register);+module_exit(agilesdtcp_unregister);++MODULE_AUTHOR("Mohamed A. Alrshah <mohamed.a.alrshah@ieee.org>");+MODULE_AUTHOR("Mohamed Othman");+MODULE_AUTHOR("Borhanuddin Ali");+MODULE_AUTHOR("Zurina Hanapi");+MODULE_LICENSE("Dual BSD/GPL");+MODULE_DESCRIPTION("Agile-SD is a Loss-Based Congestion Control Algorithm for High-speed Networks");
+ u32 frac_tracer; /* This is to trace the fractions of the increment.*/+ u32 degraded_loss_cwnd; /* loss_cwnd after degradation.*/+ enum dystate{SS=0, CA=1} agilesd_tcp_status;
Per Linux style, please define the enum separately before declaring
the variable of that type, and format the enum using Linux style. Also
please use a longer, more specific name, to avoid name collisions. I'd
suggest:
enum dystate {
AGILE_SD_SS = 0, /* comment ... */
AGILE_SD_CA = 1, /* comment ... */
};
quoted hunk
+};++/* To reset the parameters if needed*/+static inline void agilesdtcp_reset(struct sock *sk)+{++}++/* This function is called after the first acknowledgment is received and before the congestion+ * control algorithm will be called for the first time. If the congestion control algorithm has+ * private data, it should initialize its private date here. */
Multi-line comments should end with the trailing */ on a line by
itself. Here and elsewhere.
Please read:
https://www.kernel.org/doc/html/v4.10/process/coding-style.html
Please check the style of patches before submitting with the following
script in the Linux kernel tree:
scripts/checkpatch.pl
quoted hunk
+static void agilesdtcp_init(struct sock *sk)+{+ struct agilesdtcp *ca = inet_csk_ca(sk);++ /* The value of initial_ssthresh parameter is not used here, thus, snd_ssthresh is initialized by a large value.*/+ tcp_sk(sk)->snd_ssthresh = 0x7fffffff;++ ca->loss_cwnd = 0;+ ca->frac_tracer = 0;+ ca->agilesd_tcp_status = SS;+}++/* This function is called whenever an ack is received and the congestion window can be increased.+ * This is equivalent to opencwnd in tcp.cc.+ * ack is the number of bytes that are acknowledged in the latest acknowledgment;+ * rtt is the the rtt measured by the latest acknowledgment;+ * in_flight is the packet in flight before the latest acknowledgment;+ * good_ack is an indicator whether the current situation is normal (no duplicate ack, no loss and no SACK). */+static void agilesdtcp_cong_avoid(struct sock *sk, u32 ack, u32 in_flight)+{+ struct tcp_sock *tp = tcp_sk(sk);+ struct agilesdtcp *ca = inet_csk_ca(sk);+ u32 inc_factor;+ u32 ca_inc;+ u32 current_gap, total_gap;
For coding style, please order local variable declarations from
longest to shortest line, also know as Reverse Christmas Tree Format.
quoted hunk
+ /* The value of inc_factor is limited by lower_fl and upper_fl.+ * The lower_fl must be always = 1. The greater the upper_fl the higher the aggressiveness.+ * But, if upper_fl set to 1, Agile-SD will work exactly as newreno.+ * We have already designed an equation to calculate the optimum upper_fl based on the given beta.+ * This equation will be revealed once its article is published*/+ u32 lower_fl = 1 * SCALE;+ u32 upper_fl = 3 * SCALE;++ if (!tcp_is_cwnd_limited(sk)) return;
Please put this return (or any if/else body) on a line by itself.
Please use the existing kernel helper macro for this:
#define clamp(val, lo, hi) min((typeof(val))max(val, lo), hi)
quoted hunk
++ ca_inc = ((inc_factor * SCALE) / tp->snd_cwnd); /* SCALE is used to avoid fractions*/++ ca->frac_tracer += ca_inc; /* This in order to take the fraction increase into account */+ if (ca->frac_tracer >= Double_SCALE) /* To take factor scale into account */+ {
The opening brace goes on the previous line.
+/* This function is called when the TCP flow detects a loss.
+ * It returns the slow start threshold of a flow, after a packet loss is detected. */
On Tue, Aug 15, 2017 at 9:08 AM, mohamedalrshah
[off-list ref] wrote:
This commit implements a new TCP congestion control algorithm, namely Agile-SD.
Also, please use a summary line for your patch that is more in keeping
with Linux style, using spaces rather than dashes, and leading with
tcp: or tcp_agile_sd:. For example:
tcp: add Agile SD TCP congestion control module
And please read:
https://www.kernel.org/doc/html/latest/process/submitting-patches.html
Thanks,
neal
+ It contributes the Agility Factor (AF) to shorten the epoch time + and to make TCP independent from RTT. AF reduces the sensitivity + to packet losses, which in turn Agile-SD to achieve better throughput
in turn allows Agile-SD
+ over high-speed networks.
+
Please drop the tab(s) and space(s) at the ends of lines.
From: kbuild test robot <hidden> Date: 2017-08-17 00:12:46
Hi mohamedalrshah,
[auto build test ERROR on net/master]
[also build test ERROR on v4.13-rc5 next-20170816]
[if your patch is applied to the wrong git tree, please drop us a note to help improve the system]
url: https://github.com/0day-ci/linux/commits/mohamedalrshah/Adding-Agile-SD-TCP-module-and-modifying-Kconfig-and-makefile/20170817-055643
config: i386-allyesconfig (attached as .config)
compiler: gcc-6 (Debian 6.2.0-3) 6.2.0 20160901
reproduce:
# save the attached .config to linux build tree
make ARCH=i386
All errors (new ones prefixed by >>):
quoted
net//ipv4/tcp_agilesd.c:35:15: error: expected identifier before numeric constant
enum dystate{SS=0, CA=1} agilesd_tcp_status;
^~
net//ipv4/tcp_agilesd.c: In function 'agilesdtcp_cong_avoid':
net//ipv4/tcp_agilesd.c:87:28: error: 'CA' undeclared (first use in this function)
ca->agilesd_tcp_status = CA;
^~
net//ipv4/tcp_agilesd.c:87:28: note: each undeclared identifier is reported only once for each function it appears in
net//ipv4/tcp_agilesd.c: In function 'agilesdtcp_recalc_ssthresh':
net//ipv4/tcp_agilesd.c:121:32: error: 'CA' undeclared (first use in this function)
if (ca->agilesd_tcp_status == CA)
^~
net//ipv4/tcp_agilesd.c: At top level:
net//ipv4/tcp_agilesd.c:169:16: error: initialization from incompatible pointer type [-Werror=incompatible-pointer-types]
.pkts_acked = agilesdtcp_acked,
^~~~~~~~~~~~~~~~
net//ipv4/tcp_agilesd.c:169:16: note: (near initialization for 'agilesdtcp.pkts_acked')
cc1: some warnings being treated as errors
vim +35 net//ipv4/tcp_agilesd.c
29
30 /* Agile-SD Parameters */
31 struct agilesdtcp {
32 u32 loss_cwnd; /* congestion window at last loss.*/
33 u32 frac_tracer; /* This is to trace the fractions of the increment.*/
34 u32 degraded_loss_cwnd; /* loss_cwnd after degradation.*/
> 35 enum dystate{SS=0, CA=1} agilesd_tcp_status;
36 };
37
---
0-DAY kernel test infrastructure Open Source Technology Center
https://lists.01.org/pipermail/kbuild-all Intel Corporation