[Live-devel] Algorithmic problem with RTP packet reordering

[Ralf Schröder]

Hello,
incoming RTP packets are stored with an reorder object using a simple
list implementation (file MultiFramedRTPSource.cpp class
ReorderingPacketBuffer). Method storePacket implements a linear insert
into the list starting with the head pointer, whereas most inserts
happens on tail (in local networks near 100%). This list can become
long especially on overload situations, profiling show the problem:

-----------------------------------------------
                1.55   17.97  749605/749605
BasicTaskScheduler::SingleStep(unsigned int) [4]
[5]     43.9    1.55   17.97  749605
MultiFramedRTPSource::networkReadHandler1() [5]
                5.21    1.00  749571/749571
ReorderingPacketBuffer::storePacket(BufferedPacket*) [6]
                0.54    4.17  749599/749599
BufferedPacket::fillInData(RTPInterface&, unsigned int&) [9]
                1.44    3.22  749571/754606
MultiFramedRTPSource::doGetNextFrame1() <cycle 1> [16]
                0.30    0.98  749572/749572
RTPReceptionStatsDB::noteIncomingPacket(unsigned int, unsigned short,
unsigned int, unsigned int, unsigned int, timeval&, unsigned int&,
unsigned int) [22]
                0.76    0.00  749573/749573
RTPReceptionStats::noteIncomingPacket(unsigned short, unsigned int,
unsigned int, unsigned int, timeval&, unsigned int&, unsigned int)
[30]
                0.19    0.14  749603/749603
ReorderingPacketBuffer::getFreePacket(MultiFramedRTPSource*) [59]
                0.03    0.00  749573/749573
MultiFramedRTPSource::packetIsUsableInJitterCalculation(unsigned
char*, unsigned int) [180]
-----------------------------------------------
                5.21    1.00  749571/749571
MultiFramedRTPSource::networkReadHandler1() [5]
[6]     14.0    5.21    1.00  749571
ReorderingPacketBuffer::storePacket(BufferedPacket*) [6]
                1.00    0.00 20447561/20447561     seqNumLT(unsigned
short, unsigned short) [23]
-----------------------------------------------

The main problem is, if a packet drop with a multi-Stream application
(about 16 RTP/UDP streams on a slow ARM CPU) happens, the drop rate
explodes.

Solution:
======
Because a double linked list with starting on tail is an interface
change, I patched only the implementation class ReorderingPacketBuffer
holding a tail pointer. So 99% of incoming packages can be saved
directly using the tail pointer, out of order packets have to go the
way from head as before. As result the CPU situation was dramatically
improved. With next profiling
reorderingPacketBuffer::storePacket(BufferedPacket*) was gone behind
place [40].

This could dramatically improve the CPU situation at least for H.26x
players with RTP/UDP. Here the small patch:

--- live/liveMedia/MultiFramedRTPSource.cpp	2011-03-15 00:40:37.000000000 +0100
+++ live/liveMedia/patch/MultiFramedRTPSource.cpp	2011-10-18
13:53:54.000000000 +0200
@@ -52,6 +52,7 @@
   Boolean fHaveSeenFirstPacket; // used to set initial "fNextExpectedSeqNo"
   unsigned short fNextExpectedSeqNo;
   BufferedPacket* fHeadPacket;
+  BufferedPacket* fTailPacket;
   BufferedPacket* fSavedPacket;
       // to avoid calling new/free in the common case
   Boolean fSavedPacketFree;
@@ -453,7 +454,7 @@
 ReorderingPacketBuffer
 ::ReorderingPacketBuffer(BufferedPacketFactory* packetFactory)
   : fThresholdTime(100000) /* default reordering threshold: 100 ms */,
-    fHaveSeenFirstPacket(False), fHeadPacket(NULL),
fSavedPacket(NULL), fSavedPacketFree(True) {
+    fHaveSeenFirstPacket(False), fHeadPacket(NULL),
fTailPacket(NULL), fSavedPacket(NULL), fSavedPacketFree(True) {
   fPacketFactory = (packetFactory == NULL)
     ? (new BufferedPacketFactory)
     : packetFactory;
@@ -469,6 +470,7 @@
   delete fHeadPacket; // will also delete fSavedPacket if it's in the list
   fHaveSeenFirstPacket = False;
   fHeadPacket = NULL;
+  fTailPacket = NULL;
   fSavedPacket = NULL;
 }

@@ -499,7 +501,24 @@
   // that we're looking for (in this case, it's been excessively delayed).
   if (seqNumLT(rtpSeqNo, fNextExpectedSeqNo)) return False;

-  // Figure out where the new packet will be stored in the queue:
+  if (fTailPacket) {
+    if (seqNumLT(fTailPacket->rtpSeqNo(), rtpSeqNo))
+    {
+      fTailPacket->nextPacket() = bPacket;
+      bPacket->nextPacket() = NULL;
+      fTailPacket = bPacket;
+      return True;
+    }
+    if (rtpSeqNo == fTailPacket->rtpSeqNo()) {
+      // This is a duplicate packet - ignore it
+      return False;
+    }
+  } else {
+    bPacket->nextPacket() = NULL;
+    fHeadPacket = fTailPacket = bPacket;
+    return True;
+  }
+  // this long way for packets out of order
   BufferedPacket* beforePtr = NULL;
   BufferedPacket* afterPtr = fHeadPacket;
   while (afterPtr != NULL) {
@@ -530,6 +549,9 @@
   ++fNextExpectedSeqNo; // because we're finished with this packet now

   fHeadPacket = fHeadPacket->nextPacket();
+  if (!fHeadPacket) {
+    fTailPacket = NULL;
+  }
   packet->nextPacket() = NULL;

   freePacket(packet);


May be it could help somehow,
Ralf

-- 
Dr. Ralf Schröder
DResearch Fahrzeugelektronik GmbH
Otto-Schmirgal-Str. 3, 10319 Berlin, Germany

Tel: +49 30 515932-294 mailto:schroeder at dresearch-fe.de
Fax: +49 30 515932-299
Geschäftsführer: Dr. Michael Weber, Werner Mögle; Amtsgericht Berlin
Charlottenburg; HRB 130120 B; Ust.-IDNr. DE273952058