Re: [PATCH 6/43]: New infrastructure for loss detection

[Eddie Kohler <kohler@cs.ucla.edu>]

Hi Gerrit,

Sorry if this is a stupid question, but are the entries corresponding to Loss 
Intervals stored elsewhere?  You need at least 8 entries for that mandatory 
option.

Eddie


Gerrit Renker wrote:
> [CCID 3]: New infrastructure for loss detection
> 
> This provides a generic RX history unit for TFRC based protocols.
> 
> Why?
> I have spent several weeks trying to make sense out of the existing, circular-list
> based RX history implementation. It is complex, heavy-weight and puts nothing but
> stones in the way of fixing the identified current bugs in loss detection.
> 
> A full list implementation is in fact not needed: both for RTT estimation
> (needed only to compute the first loss interval, RFC 3448, 6.3.1) and for
> loss detection, only a minimum of 4 entries is needed. The overhead of
> allocating and later garbage-collecting further entries is not justified,
> and it introduces a memory and processing bottleneck.
> 
> The present design is lightweight and object-oriented:
>  * only the minimum number of entries is used;
>  * circular array of pointers:
>    - faster swapping of entries for sorting,
>    - the indexed-array semantics matches the requirments of loss detection
>      (3 consecutive packets) and RTT estimation (also consecutive packets)
>      much more naturally than a doubly-linked list;
>  * one and the same structure is used both for RTT sampling and for
>    loss detection, reducing memory demands;
>  * generic definition, can later be reused for small-packet variant of
>    CCID 3 etc.
> 
> This patch lays the foundation in terms of the main data structure with some rudimentary
> routines for basic access. Further patches will fill in the details with regard to CCID3.
> 
> Details of the algorithm are documented and illustrated in section 3 of
> http://www.erg.abdn.ac.uk/users/gerrit/dccp/docs/ccid3_packet_reception/
> 
> Signed-off-by: Gerrit Renker <gerrit@erg.abdn.ac.uk>
> ---
>  net/dccp/ccids/lib/packet_history.h |  101 ++++++++++++++++++++++++++++++++++++
>  1 file changed, 101 insertions(+)
> 
> --- a/net/dccp/ccids/lib/packet_history.h
> +++ b/net/dccp/ccids/lib/packet_history.h
> @@ -45,6 +45,9 @@
>  /* Number of later packets received before one is considered lost */
>  #define TFRC_RECV_NUM_LATE_LOSS	 3
>  
> +/* Number of packets to wait after a missing packet (RFC 4342, 6.1) */
> +#define NDUPACK 3
> +
>  #define TFRC_WIN_COUNT_PER_RTT	 4
>  /* Subtraction a-b modulo-16, respects circular wrap-around */
>  #define SUB16(a,b)		(((a) + 16 - (b)) & 0xF)
> @@ -106,6 +109,104 @@ struct dccp_rx_hist {
>  extern struct dccp_rx_hist *dccp_rx_hist_new(const char *name);
>  extern void 		dccp_rx_hist_delete(struct dccp_rx_hist *hist);
>  
> +/**
> + *   tfrc_rx_hist  -  RX history structure for TFRC-based protocols
> + *
> + *   @ring:		Packet history for RTT sampling and loss detection
> + *   @loss_count:	Number of entries in circular history
> + *   @loss_start:	Movable index (for loss detection)
> + *   @rtt_sample_prev:  Used during RTT sampling, points to candidate entry
> + *   @lock:		Serialize concurrent access
> + */
> +struct tfrc_rx_hist {
> +	struct dccp_rx_hist_entry	*ring[NDUPACK + 1];
> +	u8				loss_count:2,
> +					loss_start:2;
> +#define rtt_sample_prev			loss_start
> +	spinlock_t			lock;
> +};
> +
> +/*
> + * Macros for loss detection.
> + * @loss_prev:  entry with highest-received-seqno before loss was detected
> + * @hist_index: index to reach n-th entry after loss_start
> + * @hist_entry: return the n-th history entry  after loss_start
> + * @last_rcv:   entry with highest-received-seqno so far
> + */
> +#define loss_prev(h)		(h)->ring[(h)->loss_start]
> +#define hist_index(h, n)	(((h)->loss_start + (n)) & NDUPACK)
> +#define hist_entry(h, n)	(h)->ring[hist_index(h, n)]
> +#define last_rcv(h)		(h)->ring[hist_index(h, (h)->loss_count)]
> +
> +/*
> + * Macros to access history entries for RTT sampling.
> + * @rtt_last_s: reference entry to compute RTT samples against
> + * @rtt_prev_s: previously suitable (wrt rtt_last_s) RTT-sampling entry
> + */
> +#define rtt_last_s(h)		(h)->ring[0]
> +#define rtt_prev_s(h)		(h)->ring[(h)->rtt_sample_prev]
> +
> +/* initialise loss detection and disable RTT sampling */
> +static inline void tfrc_rx_hist_loss_indicated(struct tfrc_rx_hist *h)
> +{
> +	h->loss_count = 1;
> +}
> +
> +/* indicate whether previously a packet was detected missing */
> +static inline int tfrc_rx_loss_pending(struct tfrc_rx_hist *h)
> +{
> +	return h->loss_count;
> +}
> +
> +/* any data packets missing between last reception and skb ? */
> +static inline int tfrc_rx_new_loss_indicated(struct tfrc_rx_hist *h,
> +					     struct sk_buff *skb, u32 ndp)
> +{
> +	int delta = dccp_delta_seqno(last_rcv(h)->dccphrx_seqno,
> +				     DCCP_SKB_CB(skb)->dccpd_seq);
> +
> +	if (delta > 1 && ndp < delta)
> +		tfrc_rx_hist_loss_indicated(h);
> +
> +	return tfrc_rx_loss_pending(h);
> +}
> +
> +/* has the packet contained in skb been seen before ? */
> +static inline int tfrc_rx_duplicate(struct tfrc_rx_hist *h, struct sk_buff *skb)
> +{
> +	const u64 seq = DCCP_SKB_CB(skb)->dccpd_seq;
> +	int i;
> +
> +	if (dccp_delta_seqno(loss_prev(h)->dccphrx_seqno, seq) <= 0)
> +		return 1;
> +
> +	for (i = 1; i <= h->loss_count; i++)
> +		if (dccp_delta_seqno(hist_entry(h, i)->dccphrx_seqno, seq) = 0)
> +			return 1;
> +
> +	return 0;
> +}
> +
> +/* return the signed modulo-2^48 sequence number distance from entry e1 to e2 */
> +static inline s64 tfrc_rx_hist_delta_seqno(struct tfrc_rx_hist *h, u8 e1, u8 e2)
> +{
> +	DCCP_BUG_ON(e1 > h->loss_count || e2 > h->loss_count);
> +
> +	return dccp_delta_seqno(hist_entry(h, e1)->dccphrx_seqno,
> +				hist_entry(h, e2)->dccphrx_seqno);
> +}
> +
> +static inline void tfrc_rx_hist_swap(struct dccp_rx_hist_entry **a,
> +				     struct dccp_rx_hist_entry **b)
> +{
> +	struct dccp_rx_hist_entry *tmp = *a;
> +
> +	*a = *b;
> +	*b = tmp;
> +}
> +
> +
> +/* Older history management functions */
>  static inline struct dccp_rx_hist_entry *
>  			dccp_rx_hist_entry_new(struct dccp_rx_hist *hist,
>  					       const struct sock *sk,
> -
> 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