[RFC] Implementing an additional TCP congestion control algorithm (TCP-PR) - communication and organisation.
Hello, I'm Richard Sailer and I've started implementing an alternative congestion control algorithm for linux, capable of maintaining high throughput during persistent packet reordering (TCP-PR). Before continuing my learning and work I want to send a coordinative mail to the netdev list to: * Ask whether this algorithm is wanted in general and will be merged * To synchronize and communicate my work with the other subsystem developers and maintainers. And this organisational and communication-specific part is where I need help, the technical part is fine so far. I have been unsure for long and put quite some effort in writing the following mail (see next section), including letting several colleagues review it. It would be a great help for me, if you could (even if just shortly) review the mailtext and tell me your opinion. Please do not answer the questions in the mail, they're somehow meant as discussion starters for the netdev list. And I have two questions regarding organisation: 1. I usually GPG sign all my Mails for work or academica. I recognised most netdev users don't. Which behaviour is correct? Should I sign my Mail? 2. Is directly asking for a mentor appropriate? Since I'm quite used to reading literature, documentation or source code and figuring things out myself this would mean little effort in "parenting" :p. It would mostly boil down to review my code once a week or less and consulting me on design designs (like tradeoffs), since I would try to ask as less as possible and cause as less extra work as possible. == The Mail == Subject: Implementing an additional alternative TCP congestion control algorithm (TCP-PR) Hello, I'm Richard Sailer and I want to implement and maintain an additional congestion control algorithm for linux, capable of maintaining high thourghput during persistent packet reordering (TCP-PR). The main purpose of this mail is to organize, synchronize and communicate this work *before* I start the coding, to avoid a situation and patch, you and I would be unhappy with. == About me == I'm a 23 year old computer science student and programmer, living and studying in Augsburg, germany. Also I'm working for an IT company in munich as a freelancer. I've specialized on reading, understanding and maintaining existing legacy code. Sadly the most legacy code I'm currently dealing with is written in perl. I would describe myself as a diligent, perfectionistic and slow programmer. I like and use unixoid operating systems for several years now. I've been interested in computer networking for a long time and therefore chose my bachelor thesis on multipath tunneling (other name: osi layer 3 link aggregation). During my experiments I observed that these aggregation produces severe packet reordering and several TCP implementations available dealt quite bad with it. (details see next section). After searching for reordering robust TCP variants I discovered TCP-PR and a implementation for linux 2.4.18. == About TCP-PR == TCP-PR is an alternative congestion control algorithm. Since it doesn't use DUPACKs at all to detect packet loss, packet reordering has no big impact on the goodput. This way the following 2 things can not happen: 1. out-of-order ACK segments get recognized as DUPACKs - these mean spurious retransmit and reducing of cwnd 2. out-of-order data segments won't trigger sending of DUPACKs - actually even if this happens the sender just ignores these DUPACKs therefore a sender-side only implementation of TCP-PR is sufficient. But therefore all packet losses have to be detectet by timeouts, which means different timeout definitions and handling mechanisms have to be applied. Mainly this means that any timeout reduces cwnd to cwnd/2 instead of setting it to 1. Also RTO adjustment is callculated differently. While all this may sound like big changes from TCP Cubic or New Reno, during algorithm design, a great amount of work was invested in making TCP-PR behave throughput-fair to other TCP variants on the same network. This has also been validated by excessive ns-2 simulations. The exact results of these simulations as well as further details of the timeout definitions and other aspects of the algorithm can be found in the original paper at: www.ece.ucsb.edu/~hespanha/published/366Bohacek.pdf If requested I'm happy to describe more details of tcp-pr, it's algorithm and RTO definitions. Also a closer discussion and comparison to TCP Cubic or New Reno (with or without adjusted DUPACK settings set in /proc/ ) is possible but I wanted to keep this first mail (relatively) short. == Some Questions == 0. In general, is this congestion control algorithm of interest for you? Does it have a fair change of beeing merged, assumed: * I provide a clean and documented implementation * I apply all adjustments and improvements requested 1. From reading netdev-FAQ.txt I assume I should use *net-next* as my base for coding and testing. Is this correct? 2. Is *testing* my patches against net-next kernels sensible? Or should I use the torvalds or stable tree for sound tests? 3. I'm currently using paravirtualized Xen VMs for most of my virtualization needs. Is using Xen PV for testing my TCP extension a good idea? I think it's not problematic but I'm not entirely sure. 4. Do you prefer to get this whole patch via Email or by somehow interacting with a git repository? I think setting up a git repository would make a continuous review process before finally merging easier, which I would like. If I set up a repository mirror, is there any webinterface or server side software you would prefer or recommend. I suppose you don't like using github for that purpose. 5. In the documntation file networking/tcp.txt there is a section called: How the new TCP output machine [nyi] works. =========================================== Is the [nyi] still true? The file says: "last updated february 2008". Can I rely on this information or is it better to look elsewhere and/or in the source code? If during my work and reading/understanding the relevant code, I would update this and perhaps other documentation I stumble uppon is this something appreciated or wanted? 6. I'm currently reading "practical C programming" and severeal of the doc files in the kernel repo. Are there any further books you would recommend for me? I have already read "Unix Network Programming" by stevens, and own a copy of Tanenbaums "Computer Networks" and "Operating Systems" books. Thanks -- Richard
On Wed, Aug 12, 2015 at 03:32:07AM +0200, Richard Sailer wrote:
It would be a great help for me, if you could (even if just shortly) review the mailtext and tell me your opinion. Please do not answer the questions in the mail, they're somehow meant as discussion starters for the netdev list.
I will answer one question you have, to save yourself a lot of time and effort here:
Hello, I'm Richard Sailer and I want to implement and maintain an additional congestion control algorithm for linux, capable of maintaining high thourghput during persistent packet reordering (TCP-PR). The main purpose of this mail is to organize, synchronize and communicate this work *before* I start the coding, to avoid a situation and patch, you and I would be unhappy with.
Kernel development is done with code, not with lots of talking about things beforehand. Please show up with at least a first pass of a working implementation of your ideas to be taken seriously. best of luck, greg k-h
Hi! On 03:32 Wed 12 Aug , Richard Sailer wrote:
Hello, I'm Richard Sailer and I've started implementing an alternative congestion control algorithm for linux, capable of maintaining high throughput during persistent packet reordering (TCP-PR).
I am not a maintainer and I am not that familiar with TCP, but if you want my opinion: Dealing with reordering inside congestion control sounds rather weird. If reordering causes TCP to believe packets are lost, there will probably be other issues as well, like sending of useless retransmits. I would rather try to detect this kind of reordering and ignore dupacks and rely only on timeouts to detect loss. Also, the recipient may send an ack for each incoming data packet instead of delaying+combine acks. -Michi -- programing a layer 3+4 network protocol for mesh networks see http://michaelblizek.twilightparadox.com
Hi,
If reordering causes TCP to believe packets are lost, there will probably be other issues as well, like sending of useless retransmits. I would rather try to detect this kind of reordering and ignore dupacks and rely only on timeouts to detect loss. Well this is exactly how TCP-PR works :). But maybe this misunderstanding is my fault for writing a much to long and detailed mail. I will try to write shorter mails in future.
== About: Doing this inside Congestion control (CC) == Well I think sending retransmit is part of CC. Strictly CC is "everything done to adapt the amount of data sent to the transmission capacity of the network". But I'm not entirely sure if saying retransmission is part of this is 100% correct. Well in the end practically it doesn't matter how one classifies the "not sending of retransmits" it has to be implemented. And from an implementation point of view I think you are right. None of the existing CC modules interferes with reacting on DUPACKs or sending retransmits. Also looking at the function pointer interface for modules /tcp_congestion_ops/ : struct tcp_congestion_ops { struct list_head list; u32 key; u32 flags; /* initialize private data (optional) */ void (*init)(struct sock *sk); /* cleanup private data (optional) */ void (*release)(struct sock *sk); /* return slow start threshold (required) */ u32 (*ssthresh)(struct sock *sk); /* do new cwnd calculation (required) */ void (*cong_avoid)(struct sock *sk, u32 ack, u32 acked); /* call before changing ca_state (optional) */ void (*set_state)(struct sock *sk, u8 new_state); /* call when cwnd event occurs (optional) */ void (*cwnd_event)(struct sock *sk, enum tcp_ca_event ev); /* call when ack arrives (optional) */ void (*in_ack_event)(struct sock *sk, u32 flags); /* new value of cwnd after loss (optional) */ u32 (*undo_cwnd)(struct sock *sk); /* hook for packet ack accounting (optional) */ void (*pkts_acked)(struct sock *sk, u32 num_acked, s32 rtt_us); /* get info for inet_diag (optional) */ size_t (*get_info)(struct sock *sk, u32 ext, int *attr, union tcp_cc_info *info); char name[TCP_CA_NAME_MAX]; struct module *owner; }; doesn't look that promising. Well there is (*cwnd_event) which be meaningfull in "not reducing cwnd after a retransmission has been sent" and perhaps even for "not stopping the timer". But I'm not sure if sending retransmit packets can be prevented from here. Currently it looks like I will have to make some further parts of tcp_input.c and tcp_output.c available for CC modules. But I have to look deeper into this the next few days to know and do this for sure. If you're interested I will tell you, when i know more. -- Richi
Hi! On 16:41 Sun 16 Aug , Richard Sailer wrote:
Hi,
If reordering causes TCP to believe packets are lost, there will probably be other issues as well, like sending of useless retransmits. I would rather try to detect this kind of reordering and ignore dupacks and rely only on timeouts to detect loss. Well this is exactly how TCP-PR works :). But maybe this misunderstanding is my fault for writing a much to long and detailed mail. I will try to write shorter mails in future.
== About: Doing this inside Congestion control (CC) ==
Well I think sending retransmit is part of CC. Strictly CC is "everything done to adapt the amount of data sent to the transmission capacity of the network". But I'm not entirely sure if saying retransmission is part of this is 100% correct.
Well in the end practically it doesn't matter how one classifies the "not sending of retransmits" it has to be implemented.
This is what confused me: To me congestion control is only about adapting the send speed.
And from an implementation point of view I think you are right. None of the existing CC modules interferes with reacting on DUPACKs or sending retransmits. Also looking at the function pointer interface for modules /tcp_congestion_ops/ :
struct tcp_congestion_ops { struct list_head list; u32 key; u32 flags;
/* initialize private data (optional) */ void (*init)(struct sock *sk); /* cleanup private data (optional) */ void (*release)(struct sock *sk);
/* return slow start threshold (required) */ u32 (*ssthresh)(struct sock *sk); /* do new cwnd calculation (required) */ void (*cong_avoid)(struct sock *sk, u32 ack, u32 acked); /* call before changing ca_state (optional) */ void (*set_state)(struct sock *sk, u8 new_state); /* call when cwnd event occurs (optional) */ void (*cwnd_event)(struct sock *sk, enum tcp_ca_event ev); /* call when ack arrives (optional) */ void (*in_ack_event)(struct sock *sk, u32 flags); /* new value of cwnd after loss (optional) */ u32 (*undo_cwnd)(struct sock *sk); /* hook for packet ack accounting (optional) */ void (*pkts_acked)(struct sock *sk, u32 num_acked, s32 rtt_us); /* get info for inet_diag (optional) */ size_t (*get_info)(struct sock *sk, u32 ext, int *attr, union tcp_cc_info *info);
char name[TCP_CA_NAME_MAX]; struct module *owner; };
doesn't look that promising. Well there is (*cwnd_event) which be meaningfull in "not reducing cwnd after a retransmission has been sent" and perhaps even for "not stopping the timer". But I'm not sure if sending retransmit packets can be prevented from here. Currently it looks like I will have to make some further parts of tcp_input.c and tcp_output.c available for CC modules. But I have to look deeper into this the next few days to know and do this for sure.
This is what I meant when I said congestion control is probably not what you want to mess with. -Michi -- programing a layer 3+4 network protocol for mesh networks see http://michaelblizek.twilightparadox.com
participants (3)
-
Greg KH -
michi1＠michaelblizek.twilightparadox.com -
Richard Sailer