doc: add design for rtp retransmission

Describe how rtprtxsend and rtprtxreceive generally work
but also how the association algorithm is implemented.

2 files changed, 151 insertions, 1 deletions

diff --git a/docs/design/Makefile.am b/docs/design/Makefile.am
index 69c452bf7..352980864 100644
--- a/docs/design/Makefile.am
+++ b/docs/design/Makefile.am
@@ -2,5 +2,6 @@ SUBDIRS =
 
 
 EXTRA_DIST = \
-	design-rtpcollision.txt
+	design-rtpcollision.txt \
+	design-rtpretransmission.txt
 
diff --git a/docs/design/design-rtpretransmission.txt b/docs/design/design-rtpretransmission.txt
new file mode 100644
index 000000000..03a67359a
--- /dev/null
+++ b/docs/design/design-rtpretransmission.txt
@@ -0,0 +1,149 @@
+RTP retransmission design
+
+
+GstRTPRetransmissionRequest
+---------------------------
+
+Custom upstream event which mainly contains the ssrc and the seqnum of the
+packet which is asked to be retransmisted.
+
+On the pipeline receiver side this event is generated by the
+gstrtpjitterbuffer element. Then it is translated to a NACK to be sent over
+the network.
+
+On the pipeline sender side, this event is generated by the gstrtpsession
+element when it receives a NACK from the network.
+
+
+rtprtxsend element
+------------------
+
+-- basic mecansim
+
+rtprtxsend keeps a history of rtp packets that it has already sent.
+When it receives the event GstRTPRetransmissionRequest from the downstream
+gstrtpsession element, it loopkup the requested seqnum in its stored packets.
+If the packet is present in its history, it will create a RTX packet according
+to RFC 4588. Then this rtx packet is pushed to its src pad as other packets.
+
+rtprtxsend works in SSRC-multiplexed mode, so it has one always sink and
+src pad.
+
+-- building retransmission packet fron original packet
+
+A rtx packet is mostly the same as an orignal packet, except it has its own
+ssrc and its own seqnum. That's why rtprtxsend works in SSRC-multiplexed mode.
+It also means that the same session is used.
+Another difference between rtx packet and its original is that it inserts the
+original seqnum (OSN: 2 bytes) at the beginning of the payload.
+Also rtprtxsend builds rtx packet without padding, to let other elements do that.
+The last difference is the payload type. For now the user has to set it through
+the rtx-payload-type property. Later it will be automatically retreive this
+information from SDP. See fmtp field as specifies in the RPC4588
+(a=fmtp:99 apt=98) fmtp is the payload type of the retransmission stream
+and apt the payload type of its associated master stream.
+
+-- restransmission ssrc and seqnum
+
+To choose rtx_ssrc it randomly selects a number between 0 and 2^32-1 until
+it is different than master_ssrc.
+rtx_seqnum is randomly selected between 0 and 2^16-1
+
+- deeper in the stored buffer history
+
+For the history it uses a GSequence with 2^15-1 as its maximum size.
+Which is resonable as the default value is 100.
+It contains the packets in reverse order they have been sent
+(head:newest, tail:oldest)
+GSequence allows to add and remove an element in constant time (like a queue).
+Also GSequence allows to do a binary search when rtprtxsend lookup in its
+history.
+It's important if it receives a lot of requests or if the history is large.
+
+-- pending rtx packets
+
+When looking up in its history, if seqnum is found then it pushes the buffer
+into a GQueue to its tail.
+Before to send the current master stream packet, rtprtxsend sends all the
+buffers which are in this GQueue. Taking care of converting them to rtx
+packets.
+This way, rtx packets are sent in the same order they have been requested.
+(g_list_foreach traverse the queue from head to tail)
+The GQueue is cleared between sending 2 master stream packets.
+So for this GQueue to contain more than one element, it means that rtprtxsend
+receives more than one rtx request between sending 2 master packets.
+
+-- collision
+
+When handling a GstRTPCollision event, if the ssrc is its rtx ssrc then
+rtprtxsend clear its history and its pending retransmission queue.
+Then it chooses a rtx_ssrc until it's different than master ssrc.
+If the GstRTPCollision event does not contain its rtx ssrc, for example
+its master ssrc or other, then it just forwards the event to upstream.
+So that it can be handled by the rtppayloader.
+
+
+rtprtxreceive element
+------------------
+
+-- basic mecanims
+
+The same rtprtxreceive instance can receive several master streams and several
+retransmission streams.
+So it will try to dynamically associate a rtx ssrc with its master ssrc.
+So that it can reconstruct the original from the proper rtx packet.
+
+The algorithm is based on the fact that seqnums of different streams
+(considering all master and all rtx streams) evolve at a different rate.
+It means that the initial seqnum is random for each one and the offset could
+also be different. So that they are statistically all different at a given
+time. If bad luck then the association is delayed to the next rtx request.
+
+The algorithm also needs to know if a given packet is a rtx packet or not.
+To know this information there is the rtx-payload-types property. For now the
+user as to configure it but later it will be automatically retreive this
+information from SDP.
+It needs to know if the current packet is rtx or not in order to know if
+it can extract the OSN from the payload. Otherwise it would extract the OSN
+even on master streams which means nothing and so it could do bad things.
+In theory maybe it could work but we have this information in SDP so why not
+using it to avoid bad associations.
+
+Note that it also means that several master streams can have the same payload
+type. And also several rtx streams can have the same payload type.
+So the information from SDP which gives us which rtx payload type belong to
+a give master payload type is not enough to do the association between rtx ssrc
+and master ssrc.
+
+rtprtxreceive works in SSRC-multiplexed mode, so it has one always sink and
+src pad.
+
+-- deeper in the association algorithm
+
+When it receives a GstRTPRetransmissionRequest event it will remember the ssrc
+and the seqnum from this request.
+
+On incoming packets, if the packet has its ssrc already associated then it
+knows if the ssrc is an rtx ssrc or a master stream ssrc.
+If this is a rtx packet then it recontructs the original and pushs the result to
+src pad as if it was a master packet.
+
+If the ssrc is not yet associated rtprtxreceive checks the payload type.
+if the packet has its payload type marked as rtx then it will extract the OSN
+(original seqnum number) and lookup in its stored requests if a seqnum matchs.
+If found, then it associates the current ssrc to the master ssrc marked in the
+request. If not found it just drops the packet.
+Then it removes the request from the stored requests.
+
+If there are 2 requests with the same seqnum and different ssrc, then the
+couple seqnum,ssrc is removed from the stored requests.
+A stored request actually means that actually the couple seqnum,ssrc is stored.
+If it's happens the request is droped but it avoids to do bad associations.
+In this case the association is just delayed to the next request.
+
+- building original packet from rtx packet
+
+Header, extensions, payload and padding are mostly the same. Except that the
+OSN is removed from the payload. Then ssrc, seqnum, and original payload type
+are correctly set. Original payload type is actually also stored when the
+rtx request is handled.