PACKET_SIZE option and congestion control on variable-length packets
There have been discussions on whether s' is fixed in CCID 2/3 or whether, in spite of RFC 4341/2, s' is variable. To resolve the discussion into material which is practically implementable and yet does not defy existing standards-track documents, a simple algorithmic strategy is suggested below.
An aside to the discussion was the PACKET_SIZE socket option, but in actual fact this option is of no use other than causing unnecessary confusion: for CCID 2 it is entirely irrelevant, and for CCID 3 (and its variations) it is redundant and not useful due to argumentation below.
Strategy
----------
1/ Remove the PACKET_SIZE socket options as they don't help with the problem;
I have therefore updated Ian's patch to be used standalone [attached].
2/ In the initialisation code, set ccid3hctx_s = ccid3hcrx_s = 0 instead of the
TFRC_STD_PACKET_SIZE (which would give wrong estimates)
3/ Update ccid3hc{rx,tx}_s using the `payload len' value taken each time from
* dccp_sendmsg (after the check against dccp_mss_cache)
* dccp_v{4,6}_rcv (only on Data/DataAck packets)
using a moving average with a large q = 8/10 ... 9/10:
s <-- q * s + (1-q) * len
4/ Don't use MTU minus header length for `s' (justified below).
Thus, if the application is well-behaved and sends only `fixed' size packets, step
(3) reduces to a no-op. Otherwise, it slowly converges to a long-term value. The exact/optimal weight of q can be found through experimentation, but 9/10 seems conservative enough. The algorithm above is in accordance with recent modifications suggested in [HFPW06]. It could be extended to guard against excessive changes in packet length for CCID 2 as suggested in [RFC 4341, sec. 5.3].
R A T I O N A L E
The problem in assuming that `s' may vary and in allowing it to be set to some other (but fixed) value, such as the path MTU minus header/option lengths, lies in required changes to the loss rate estimation algorithm.
References which explicitly warn against this are given below; in both [Wid00, p. 21] and [FHP+00, 3.1.2] it is pointed out that this part has taken much discussion and testing; for good reasons, since any changes endanger both efficiency and fairness wrt competing TCP flows.
Theorems and numerical examples that attest that inaccuracies lead to either non-TCP-friendly or suboptimal application behaviour can be found in [RR99]; trends to be confirmed later by a much more comprehensive analysis in [VLB05].
These findings were validated and confirmed by Widmer et al in [WBLB04]. This article, as well as the earlier technical report [Vas00] warn against using the MTU as fixed' packet size parameter of the throughput equation, in such scenarios where the application is allowed to send variable-sized packets. To solve the problem of a non-fixed' s, Widmer et al introduce a number of changes to the loss estimation algorithm in [WBLB04].
Similar ideas and a confirmation that the loss interval estimation needs updating when `s' may vary can be found in [FK06]; where a constant of s=1460 is plugged into the throughput equation. Consequently adjustments to estimating the loss event rate do follow; and an upper bound on the sending rate is additionally imposed to support using non-`fixed' s.
In summary, using variable packet sizes is not well understood and even less well specified. There are several publications which explicitly warn against clamping `s' to the path MTU [Vas00, WBLB04,VLB05, RR99] and thereby allowing applications to be liberal with (the length of) what they send.
References
--------------
[RR99] Ramesh, Sridhar and Injong Rhee. Issues in TCP Model-Based Flow
Control. Technical report, TR-99-15, NCSU, North Carolina State University, Raleigh, 1999.
[VLB05] Vojnovic, Milan and Jean-Yves Le Boudec. On the long-run behavior
of equation-based rate control. IEEE/ACM Transactions on Networking (TON), 13(3):568--581, 6/2005.
[WBLB04] Widmer, Jörg, Catherine Boutremans and Jean-Yves Le Boudec.
End-to-End Congestion Control for TCP-Friendly Flows with Variable Packet Size. ACM SIGCOMM Computer Communication Review, 34(2):137--151, 4/2004.
[Vas00] Vasallo, Pedro Reviriego. Variable Packet Size Equation Based
Congestion Control. Technical Report, tr-00-008, ICSI, 4/2000.
[FK06] Floyd, Sally and Eddie Kohler. TCP Friendly Rate Control (TFRC):
the Small-Packet (SP) Variant. draft-ietf-dccp-tfrc-voip-05.txt, 1/3/2006.
[HFPW06] draft-floyd-rfc3448bis-00.txt
[Wid00] Widmer, Jörg. Equation-Based Congestion Control. Diploma Thesis,
Department of Mathematics and Computer Science, University of Mannheim, Germany, 2/2000.
[FHP+00] Floyd, Sally, Mark Handley, Jitendra Padhye and Jörg Widmer.
Equation-Based Congestion Control for Unicast Applications. ACM SIGCOMM Computer Communication Review, 30(4):43--56, 10/2000.
include/linux/dccp.h +0 -2
@@ -196,7 +196,6 @@ struct dccp_so_feat { };/* DCCP socket options */ -#define DCCP_SOCKOPT_PACKET_SIZE 1#define DCCP_SOCKOPT_SERVICE 2#define DCCP_SOCKOPT_CHANGE_L 3#define DCCP_SOCKOPT_CHANGE_R 4
@@ -464,7 +463,6 @@ struct dccp_sock {struct dccp_service_list *dccps_service_list;struct timeval dccps_timestamp_time;__u32 dccps_timestamp_echo; -__u32 dccps_packet_size;__u16 dccps_l_ack_ratio;__u16 dccps_r_ack_ratio;unsigned long dccps_ndp_count;
net/dccp/ccids/ccid3.c +2 -10
@@ -652,11 +652,7 @@ static int ccid3_hc_tx_init(struct ccidstruct dccp_sock *dp =dccp_sk (sk);struct ccid3_hc_tx_sock *hctx =ccid_priv (ccid); -if (dp->dccps_packet_size >=TFRC_MIN_PACKET_SIZE && - dp->dccps_packet_size <=TFRC_MAX_PACKET_SIZE ) - hctx->ccid3hctx_s = dp->dccps_packet_size; -else - hctx->ccid3hctx_s =TFRC_STD_PACKET_SIZE ; + hctx->ccid3hctx_s =TFRC_STD_PACKET_SIZE ;/* Set transmission rate to 1 packet per second */ hctx->ccid3hctx_x = hctx->ccid3hctx_s;
@@ -1125,11 +1121,7 @@ static int ccid3_hc_rx_init(struct ccidccid3_pr_debug ("%s, sk=%p\n" ,dccp_role (sk), sk); -if (dp->dccps_packet_size >=TFRC_MIN_PACKET_SIZE && - dp->dccps_packet_size <=TFRC_MAX_PACKET_SIZE ) - hcrx->ccid3hcrx_s = dp->dccps_packet_size; -else - hcrx->ccid3hcrx_s =TFRC_STD_PACKET_SIZE ; + hcrx->ccid3hcrx_s =TFRC_STD_PACKET_SIZE ; hcrx->ccid3hcrx_state =TFRC_RSTATE_NO_DATA ;INIT_LIST_HEAD (&hcrx->ccid3hcrx_hist);
net/dccp/proto.c +1 -12
@@ -451,8 +451,7 @@ out_free_val:static int do_dccp_setsockopt (struct sock *sk,int level,int optname,char __user *optval,int optlen) { -struct dccp_sock *dp; -int err; +int err =0 ;int val;if (optlen <sizeof (int ))
@@ -465,14 +464,8 @@ static int do_dccp_setsockopt(struct socreturn dccp_setsockopt_service (sk, val, optval, optlen);lock_sock (sk); - dp =dccp_sk (sk); - err =0 ;switch (optname) { -case DCCP_SOCKOPT_PACKET_SIZE : - dp->dccps_packet_size = val; -break ; -case DCCP_SOCKOPT_CHANGE_L :if (optlen !=sizeof (struct dccp_so_feat )) err = -EINVAL ;
@@ -568,10 +561,6 @@ static int do_dccp_getsockopt(struct soc dp =dccp_sk (sk);switch (optname) { -case DCCP_SOCKOPT_PACKET_SIZE : - val = dp->dccps_packet_size; - len =sizeof (dp->dccps_packet_size); -break ;case DCCP_SOCKOPT_SERVICE :return dccp_getsockopt_service (sk, len, (__be32 __user *)optval, optlen);
Quoted 10 lines · Gerrit Renker
There have been discussions on whether
s' is fixed in CCID 2/3 or whether, in spite of RFC 4341/2,s' is variable. To resolve the discussion into material which is practically implementable and yet does not defy existing standards-track documents, a simple algorithmic strategy is suggested below.An aside to the discussion was the
PACKET_SIZEsocket option, but in actual fact this option is of no use other than causing unnecessary confusion: for CCID 2 it is entirely irrelevant, and for CCID 3 (and its variations) it is redundant and not useful due to argumentation below.
Quoted 4 lines
Strategy
----------
1/ Remove thePACKET_SIZEsocket options as they don't help with the problem;
I have therefore updated Ian's patch to be used standalone [attached].
NAK this patch. At present it just sets s to be 256 bytes where the spec says to use the MSS. My patch is not perfect but it is better than this as it allows you to set the size where you can't at present, nor with this patch.
Gerrit - your strategy below is OK, although complicated, but without patches for these steps we shouldn't regress to a worse state. Something can be implemented if it is better than mine but this isn't yet.
Quoted 9 lines
2/ In the initialisation code, set
ccid3hctx_s=ccid3hcrx_s= 0 instead of the
TFRC_STD_PACKET_SIZE(which would give wrong estimates)
3/ Update ccid3hc{rx,tx}_s using the `payload len' value taken each time from
*dccp_sendmsg(after the check againstdccp_mss_cache)
* dccp_v{4,6}_rcv (only on Data/DataAck packets)
using a moving average with a large q = 8/10 ... 9/10:
s <-- q * s + (1-q) * len
4/ Don't use MTU minus header length for `s' (justified below).
I agree that a moving average is better than my patch if it is implemented.
I think it is better again to track just packets per second but this needs further discussions with the DCCP working group.
Ian
--
Ian McDonald
Web: http://wand.net.nz/~iam4
Blog: http://imcdnzl.blogspot.com
WAND Network Research Group
Department of Computer Science
University of Waikato
New Zealand
| > Strategy | > ---------- | > 1/ Remove the PACKET_SIZE socket options as they don't help with the problem; | > I have therefore updated Ian's patch to be used standalone [attached]. | | NAK this patch. At present it just sets s to be 256 bytes where the | spec says to use the MSS. My patch is not perfect but it is better | than this as it allows you to set the size where you can't at present, | nor with this patch.
Oops, this is going into an entirely wrong direction! The posting is not about patches, it presented a strategy for discussion, and sums up an extract of the reading I have been stuck with for a couple of days.
Frankly, I am really sorry that this should evolve into a discussion regarding whose patches are better - such was never my intention. You have put in a lot of work into these patches, despite having other work to do, and this in itself really is very commendable.
Lastly, can you please go back one posting and look through said patch - it does not even touch the default settings you are mentioning; all it does is removing the PACKET_SIZE socket option. This is the code I am actually using myself and have sent it as an aid; since it is now decoupled from other issues (please do have a look).
Sorry, I was not able to produce the full works, reading up on this fixed `s' issue and resolving the contradictory statements in RFC 3448/4340/4342 (plus CCID 4 draft) ate away a lot of time that could have been spent implementing.
I further understand that you are working on the CCID-3 code and therefore wanted to bring up the strategy/discussion first.
What I am currently working on is tidying up the general socket API. This involves:
* default fallback service code [done]
* removing the PACKET_SIZE option [this discussion/posting]
* setting the CCIDs via socket option and poll the actual CCID via getsockopt [tbd]
* fitting partial-checksum coverage into the code [in progress]
* any other reasonable suggestions which may help getting application programming started
[since: no stable API --> no coherent API documentation --> no application programs]
Once this is wrapped up I intend to update the documentation on the API, in form of a `DCCP socket programming mini HowTo', to be put online or added to the existing documentation. With the help of constructive discussion this may happen.
To summarise:
-------------
1) The real problem is not in patches - RFC 4340..2 are elusive and in parts outright wrong about assumptions on the packet size. Substantial evidence that for instance using MSS as fixed `s' is detrimental was provided in the last posting.
2) Weighted average was introduced as a strategy to resolve this in an implementable format.
3) Can we reach agreement regarding that PACKET_SIZE option does not help with the `fixed s' issue and therefore it is OK to remove it???
4) Literature research as per previous posting prevented coming up with patch. If you would rather not work on it and no one else is interested, I will try to find some free time.
-Gerrit
Quoted 9 lines · Gerrit Renker
| > Strategy | > ---------- | > 1/ Remove the PACKET_SIZE socket options as they don't help with the problem; | > I have therefore updated Ian's patch to be used standalone [attached]. | | NAK this patch. At present it just sets s to be 256 bytes where the | spec says to use the MSS. My patch is not perfect but it is better | than this as it allows you to set the size where you can't at present, | nor with this patch.
Quoted 3 lines
Oops, this is going into an entirely wrong direction! The posting is not about patches, it presented a strategy for discussion, and sums up an extract of the reading I have been stuck with for a couple of days.
You are posting onto a development list with a patch. Of course I am going to discuss the patch. If you had posted to the discussion without the patch my answer would have been very different!
Quoted 3 lines
Frankly, I am really sorry that this should evolve into a discussion regarding whose patches are better - such was never my intention. You have put in a lot of work into these patches, despite having other work to do, and this in itself really is very commendable.
I wasn't talking about the quality of code etc. I was talking about experimental results. With only that one patch it would have broken my research that I am doing. If it had been carried through to all it would have been fine.
Quoted 6 lines
Lastly, can you please go back one posting and look through said patch - it does not even touch the default settings you are mentioning; all it does is removing the
PACKET_SIZEsocket option. This is the code I am actually using myself and have sent it as an aid; since it is now decoupled from other issues (please do have a look).
Agree - but my code allowed the PACKET_SIZE option to work. Until yours is completed my series of patches works better. It is not compulsory to use the option under my code so no loss. I totally think your idea is better than my implementation. However as Dave M says "show me the code" - i.e. fully coded good ideas are better than half coded great ideas.
Quoted 4 lines
Sorry, I was not able to produce the full works, reading up on this fixed `s' issue and resolving the contradictory statements in RFC 3448/4340/4342 (plus CCID 4 draft) ate away a lot of time that could have been spent implementing.
Not my fault. I was debating the code not the ideas. Don't take it personally. With the research you've come up with I think you're smarter than me!
Quoted 9 lines
I further understand that you are working on the CCID-3 code and therefore wanted to bring up the strategy/discussion first.
What I am currently working on is tidying up the general socket API. This involves:
* default fallback service code [done]
* removing thePACKET_SIZEoption [this discussion/posting]
* setting the CCIDs via socket option and poll the actual CCID via getsockopt [tbd]
* fitting partial-checksum coverage into the code [in progress]
* any other reasonable suggestions which may help getting application programming started
Quoted 6 lines
[since: no stable API --> no coherent API documentation --> no application programs]Once this is wrapped up I intend to update the documentation on the API, in form of a `DCCP socket programming mini HowTo', to be put online or added to the existing documentation. With the help of constructive discussion this may happen.
Yes this would be useful.
Quoted 6 lines
To summarise:
-------------
1) The real problem is not in patches - RFC 4340..2 are elusive and in parts outright wrong about assumptions on the packet size. Substantial evidence that for instance using MSS as fixed `s' is detrimental was provided in the last posting.
Agree 100% as you can see in my other posting. I think packet size/sec is better for CCID3 but not allowed.
Quoted 1 line
2) Weighted average was introduced as a strategy to resolve this in an implementable format.
Agree this is better.
Quoted 2 lines
3) Can we reach agreement regarding that
PACKET_SIZEoption does not help with the `fixed s' issue and therefore it is OK to remove it???
No we can't. Until point 2) is done or a packet/sec implementation then I would like my code in as it solves a real problem for me and others. I think your option 2 if coded would be better than my code though so happy to have yours in if coded soon otherwise I would like mine in.
Quoted 3 lines
4) Literature research as per previous posting prevented coming up with patch. If you would rather not work on it and no one else is interested, I will try to find some free time.
Up to you. At the moment Real Life (tm Arnaldo) has intervened and I can't whip up patches quickly.
Quoted 2 lines
-Gerrit
Ian
Signature · 7 lines
Ian McDonald Web: http://wand.net.nz/~iam4 Blog: http://imcdnzl.blogspot.com WAND Network Research Group Department of Computer Science University of Waikato New Zealand
Quoted 14 lines · Ian McDonald
Quoted 9 lines · Gerrit Renker
| > Strategy | > ---------- | > 1/ Remove the PACKET_SIZE socket options as they don't help with the problem; | > I have therefore updated Ian's patch to be used standalone [attached]. | | NAK this patch. At present it just sets s to be 256 bytes where the | spec says to use the MSS. My patch is not perfect but it is better | than this as it allows you to set the size where you can't at present, | nor with this patch.Quoted 3 lines
Oops, this is going into an entirely wrong direction! The posting is not about patches, it presented a strategy for discussion, and sums up an extract of the reading I have been stuck with for a couple of days.
Quoted 4 lines
You are posting onto a development list with a patch. Of course I am going to discuss the patch. If you had posted to the discussion without the patch my answer would have been very different!
My apologies to you on this. I have just worked through my ideas in another thread and proved myself wrong.
Quoted 11 lines
Quoted 3 lines
1) The real problem is not in patches - RFC 4340..2 are elusive and in parts outright wrong about assumptions on the packet size. Substantial evidence that for instance using MSS as fixed `s' is detrimental was provided in the last posting.
Agree 100% as you can see in my other posting. I think packet size/sec is better for CCID3 but not allowed.
Quoted 1 line
2) Weighted average was introduced as a strategy to resolve this in an implementable format.
Agree this is better.
By my calculations you don't need to do this now as it calculates the correct packet sending rate. Would be easy to verify but I don't have my equipment available right now or the time.
Signature · 7 lines
Ian McDonald Web: http://wand.net.nz/~iam4 Blog: http://imcdnzl.blogspot.com WAND Network Research Group Department of Computer Science University of Waikato New Zealand