Adding-Agile-SD-TCP-module-and-modifying-Kconfig-and-makefile

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 <mohamed.a.alrshah@ieee.org>
Signed-off-by: Mohamed Othman <mothman@upm.edu.my>
Signed-off-by: Borhanuddin Ali <borhan@upm.edu.my>
Signed-off-by: Zurina Hanapi <zurinamh@upm.edu.my>

---
 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

On Tue, Aug 15, 2017 at 9:08 AM, mohamedalrshah
<mohamed.a.alrshah@ieee.org> wrote:
> +
> +/* Agile-SD Parameters */
> +struct agilesdtcp {
> +       u32     loss_cwnd;             /* congestion window at last loss.*/

Please rebase your change on top of the latest net-next changes and
update this module to use the latest approach from the recent commit:

  https://git.kernel.org/pub/scm/linux/kernel/git/davem/net-next.git/commit/?id=f1722a1be19dc38e0a4b282d4e6e6ec5e1b11a67
  tcp: consolidate congestion control undo functions

Specifically:

- reference tp->prior_cwnd instead of ca->loss_cwnd
- remove the  ca->loss_cwnd field
- have the .undo_cwnd field reference tcp_reno_undo_cwnd

> +       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 ... */
};


> +};
> +
> +/* 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

> +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.

> +       /* 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.

> +
> +       if (tp->snd_cwnd < tp->snd_ssthresh){

Need a space between ) and {.

> +               ca->agilesd_tcp_status = SS;
> +               tcp_slow_start(tp, in_flight);
> +       }
> +       else {

The else needs to go on the same line as the closing brace.


> +               inc_factor = min(max(((upper_fl * current_gap) / total_gap), lower_fl), upper_fl);

Please use the existing kernel helper macro for this:

#define clamp(val, lo, hi) min((typeof(val))max(val, lo), hi)


> +
> +               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. */

Trailing */ style issue again.

> +static u32 agilesdtcp_recalc_ssthresh(struct sock *sk)
> +{
> +       const struct tcp_sock *tp = tcp_sk(sk);
> +       struct agilesdtcp *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);

These two branches of the if/else look the same? Can they be condensed
to a single line?

Thanks,
neal

On Tue, Aug 15, 2017 at 9:08 AM, mohamedalrshah
<mohamed.a.alrshah@ieee.org> 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

On 08/15/2017 06:51 AM, Neal Cardwell wrote:
> On Tue, Aug 15, 2017 at 9:08 AM, mohamedalrshah
> <mohamed.a.alrshah@ieee.org> wrote:
> 
>> +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.

Per what coding style, please?  This is not in current coding style nor in the
netdev-FAQ exceptions.

On 08/15/2017 06:08 AM, mohamedalrshah wrote:
> diff --git a/net/ipv4/Kconfig b/net/ipv4/Kconfig
> index 91a2557..474f72c 100644
> --- a/net/ipv4/Kconfig
> +++ b/net/ipv4/Kconfig
> @@ -677,6 +677,17 @@ config TCP_CONG_BBR
>  	bufferbloat, policers, or AQM schemes that do not provide a delay
>  	signal. It requires the fq ("Fair Queue") pacing packet scheduler.
>  
> +config TCP_CONG_AGILESD
> +        tristate "Agile-SD Congestion control"
> +        default n
> +        ---help---
> +        
> +        This is version 1.0 of Agile-SD TCP. It is a sender-side only. 

	                                        It is a sender-side only <what>.

> +        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.

>  choice
>  	prompt "Default TCP congestion control"
>  	default DEFAULT_CUBIC
> @@ -713,6 +724,9 @@ choice
>  
>  	config DEFAULT_BBR
>  		bool "BBR" if TCP_CONG_BBR=y
> +        
> +        config DEFAULT_AGILESD

Indent above with tab, not spaces.

> +		bool "AGILESD" if TCP_CONG_AGILESD=y
>  
>  	config DEFAULT_RENO
>  		bool "Reno"
> @@ -738,6 +752,7 @@ config DEFAULT_TCP_CONG
>  	default "dctcp" if DEFAULT_DCTCP
>  	default "cdg" if DEFAULT_CDG
>  	default "bbr" if DEFAULT_BBR
> +        default "agilesd" if DEFAULT_AGILESD

Indent above with tab, not spaces.

>  	default "cubic"
>  
>  config TCP_MD5SIG

From: Randy Dunlap <rdunlap@infradead.org>
Date: Tue, 15 Aug 2017 09:41:53 -0700

> On 08/15/2017 06:51 AM, Neal Cardwell wrote:
>> On Tue, Aug 15, 2017 at 9:08 AM, mohamedalrshah
>> <mohamed.a.alrshah@ieee.org> wrote:
>> 
>>> +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.
> 
> Per what coding style, please?  This is not in current coding style nor in the
> netdev-FAQ exceptions.

It is the established practice, documented or not, and I enforce this for all
networking code submissions.

On 08/15/2017 10:36 AM, David Miller wrote:
> From: Randy Dunlap <rdunlap@infradead.org>
> Date: Tue, 15 Aug 2017 09:41:53 -0700
> 
>> On 08/15/2017 06:51 AM, Neal Cardwell wrote:
>>> On Tue, Aug 15, 2017 at 9:08 AM, mohamedalrshah
>>> <mohamed.a.alrshah@ieee.org> wrote:
>>>
>>>> +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.
>>
>> Per what coding style, please?  This is not in current coding style nor in the
>> netdev-FAQ exceptions.
> 
> It is the established practice, documented or not, and I enforce this for all
> networking code submissions.

I see.  Thanks for clarifying that.

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: ia64-allyesconfig (attached as .config)
compiler: ia64-linux-gcc (GCC) 6.2.0
reproduce:
        wget https://raw.githubusercontent.com/01org/lkp-tests/master/sbin/make.cross -O ~/bin/make.cross
        chmod +x ~/bin/make.cross
        # save the attached .config to linux build tree
        make.cross ARCH=ia64 

All errors (new ones prefixed by >>):

>> 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 +169 net//ipv4/tcp_agilesd.c

   162	
   163	static struct tcp_congestion_ops agilesdtcp __read_mostly = {
   164		.init		= agilesdtcp_init,
   165		.ssthresh	= agilesdtcp_recalc_ssthresh,
   166		.cong_avoid	= agilesdtcp_cong_avoid,
   167		.set_state	= agilesdtcp_state,
   168		.undo_cwnd	= agilesdtcp_undo_cwnd,
 > 169		.pkts_acked	= agilesdtcp_acked,
   170		.owner		= THIS_MODULE,
   171		.name		= "agilesd",
   172	};
   173	

---
0-DAY kernel test infrastructure                Open Source Technology Center
https://lists.01.org/pipermail/kbuild-all                   Intel Corporation

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 >>):

>> 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