From mboxrd@z Thu Jan 1 00:00:00 1970 From: Eddie Kohler Date: Tue, 10 Apr 2007 17:24:03 +0000 Subject: Re: [PATCH 2/25]: Avoid accumulation of large send credit Message-Id: <461BC833.8090409@cs.ucla.edu> List-Id: References: <200703211844.12007@strip-the-willow> In-Reply-To: <200703211844.12007@strip-the-willow> MIME-Version: 1.0 Content-Type: text/plain; charset="us-ascii" Content-Transfer-Encoding: 7bit To: dccp@vger.kernel.org > Fix: > ---- > Avoid any backlog of sending time which is greater than one whole t_ipi. This > permits the coarse-granularity bursts mentioned in [RFC 3448, 4.6], but disallows > the disproportionally large bursts. Actually this does not permit coarse granularity bursts, since it limits the maximum burst size to 2 packets. That is not sufficient for high rates and medium-to-low granularities and it is far stricter than TCP. Eddie > D e t a i l e d J u s t i f i c a t i o n [not commit message] > ------------------------------------------------------------------ > Let t_nom < t_now be such that t_now = t_nom + n*t_ipi + t_r, where > n is a natural number and t_r < t_ipi. Then > > t_nom - t_now = - (n*t_ipi + t_r) > > First consider n=0: the current packet is sent immediately, and for > the next one the send time is > > t_nom' = t_nom + t_ipi = t_now + (t_ipi - t_r) > > Thus the next packet is sent t_r time units earlier. The result is > burstier traffic, as the inter-packet spacing is reduced; this > burstiness is mentioned by [RFC 3448, 4.6]. > > Now consider n=1. This case is illustrated below > > |<----- t_ipi -------->|<-- t_r -->| > > |----------------------|-----------| > t_nom t_now > > Not only can the next packet be sent t_r time units earlier, a third > packet can additionally be sent at the same time. > > This case can be generalised in that the packet scheduling mechanism > now acts as a Token Bucket Filter whose bucket size equals n: when > n=0, a packet can only be sent when the next token arrives. When n>0, > a burst of n packets can be sent immediately in addition to the tokens > which arrive with rate rho = 1/t_ipi. > > The aim of CCID 3 is an on average smooth traffic with allowed sending > rate X. The following determines the required bucket size n for the > purpose of achieving, over the period of one RTT R, an average allowed > sending rate X. > The number of bytes sent during this period is X*R. Tokens arrive with > rate rho at the bucket, whose size n shall be determined now. Over the > period of R, the TBF allows s * (n + R * rho) bytes to be sent, since > each token represents a packet of size s. Hence we have the equation > > s * (n + R * rho) = X * R > <=> n + R/t_ipi = X/s * R = R / t_ipi > > which shows that n must be 0. Hence we can not allow a `credit' of > t_nom - t_now > t_ipi time units to accrue in the packet scheduling. > > > Signed-off-by: Gerrit Renker > --- > net/dccp/ccids/ccid3.c | 12 ++++++++++-- > 1 file changed, 10 insertions(+), 2 deletions(-) > > --- a/net/dccp/ccids/ccid3.c > +++ b/net/dccp/ccids/ccid3.c > @@ -362,7 +362,15 @@ static int ccid3_hc_tx_send_packet(struc > case TFRC_SSTATE_NO_FBACK: > case TFRC_SSTATE_FBACK: > delay = timeval_delta(&hctx->ccid3hctx_t_nom, &now); > - ccid3_pr_debug("delay=%ld\n", (long)delay); > + /* > + * Lagging behind for more than a full t_ipi: when this occurs, > + * a send credit accrues which causes packet storms, violating > + * even the average allowed sending rate. This case happens if > + * the application idles for some time, or if it emits packets > + * at a rate smaller than X/s. Avoid such accumulation. > + */ > + if (delay + (suseconds_t)hctx->ccid3hctx_t_ipi < 0) > + hctx->ccid3hctx_t_nom = now; > /* > * Scheduling of packet transmissions [RFC 3448, 4.6] > * > @@ -371,7 +379,7 @@ static int ccid3_hc_tx_send_packet(struc > * else > * // send the packet in (t_nom - t_now) milliseconds. > */ > - if (delay - (suseconds_t)hctx->ccid3hctx_delta >= 0) > + else if (delay - (suseconds_t)hctx->ccid3hctx_delta >= 0) > return delay / 1000L; > > ccid3_hc_tx_update_win_count(hctx, &now); > - > To unsubscribe from this list: send the line "unsubscribe dccp" in > the body of a message to majordomo@vger.kernel.org > More majordomo info at http://vger.kernel.org/majordomo-info.html