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@xxxxxxxxxxxxxx>
---
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@xxxxxxxxxxxxxxx
More majordomo info at http://vger.kernel.org/majordomo-info.html
-
To unsubscribe from this list: send the line "unsubscribe dccp" in
the body of a message to majordomo@xxxxxxxxxxxxxxx
More majordomo info at http://vger.kernel.org/majordomo-info.html
