Skip to contentSkip to conversation

: New receiver history data structure

PATCH In review Gerrit Renker 2 participants 2 messages Jun 15, 2007 – Jun 24, 2007 Networking

lore
Share & tools
lore
#0 lore raw

PATCH 1/9 : New receiver history data structure

[TFRC]: New receiver history data structure

This provides a generic RX history unit for TFRC based protocols.

The data structure is heavily optimised to reduce the overhead to the smallest possible minimum.

A full list implementation is in fact not needed: both for RTT estimation 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/notes/ccid3_packet_reception/

---
 net/dccp/ccids/ccid3.h              |    2 
 net/dccp/ccids/lib/packet_history.h |  121 +++++++++++++++++++++++++++++++++---
 2 files changed, 113 insertions(+), 10 deletions(-)
net/dccp/ccids/ccid3.h +1 -1
@@ -158,7 +158,7 @@ struct ccid3_hc_rx_sock {
 	enum ccid3_hc_rx_states		ccid3hcrx_state:8;
 	u32				ccid3hcrx_bytes_recv;
 	ktime_t				ccid3hcrx_last_feedback;
-	struct list_head		ccid3hcrx_hist;
+	struct tfrc_rx_hist		ccid3hcrx_hist;
 	struct list_head		ccid3hcrx_li_hist;
 	u16				ccid3hcrx_s;
 	u32				ccid3hcrx_pinv;
net/dccp/ccids/lib/packet_history.h +112 -9

139 lines not on this page · raw message