Hello, Consider following as open discussion. I'm just want to show that linked lists are not the best solution in all cases, and we should be careful and see all possible variants and problems when changing something.
On 2/7/07, Jaroslav Libák <[EMAIL PROTECTED]> wrote: > Have you considered using a sorted linked list for storing packets? Short answer is no, because its only benefits are lesser memory consumption and infinite length. Read below for longer description. > Currently there is a circular queue in static array. With a sorted linked > list, > we could have different buffer length for different codecs, This could be done with dynamic array too. It's matter of API, not internal JB realization. With array we just allocate it once with requested size. > and buffer size could change dynamically. For example if we detect that jitter > is high and there are lots of missing frames we could extend the buffer a > little > bit and introduce small delay in playback. It could change dynamically even with array. To change its size you may store additional pointer to its 'virtual' size and take it into account when adding new packet. So if virtual size is lesser then real there always will be free 'real' space in buffer. Increasing and decreasing virtual size of array is as cheap as icreasing and decreasing size of linked list, if not cheaper. > Insertion into a linked list would be cheap if there are no missing frames, > and slightly more expensive if there are some missing ones and arriving out > of order (this is a constant operation right now). For good implementation of array insertion will be always constant time. > Pulling frames out of MprDejitter would be a constant operation in comparison > to current code, which basically needs buffersize loops since it begins the > loop after the newest frame (if frames arrive in order and there is no loss). Current realization is ugly, :( pulling from array may be done much faster. Just keep pointer to eldest available packet, and you'll get constant time for no loss case and very little time in case of loss. > Frames in linked list would be sorted according to rtp timestamp as sequence > numbers could cause problems. Vice versa. :) You could not use timestamps to sort packets, because there may be several packets with same timestamp (e.g. video frame, splitted to several RTP packets). Moreover, timestamp have undefined step. And sequence number is different for all packets (inside long wrap period), and increased by 1 for each next packet even if it have same timestamp. > It would simplify the code in MprDejitter and in the G711 u and A decoder > decodeIn function substantialy. So, I believe it could be simplified without linked lists. ;) > If we use sorted linked list we can also compute statistics like how many > frames in order (without missing slots) do we have in the list from the head. In linked list it is done in linear time. So I propose using member integer variable to compute this statistic - increase it when packet added to buffer and decrase when it is removed from list. > For example if we detect that we only have some missing frames in next 100ms, > we > can increase the delay before playback until it improves There more to do with good mathematics... You should be more concerned on *when* increase and decrease buffer size to get best voice quality. As I already said it is easy to implement in either case. > (it would have to detect somehow when other side simply stops sending rtp > packets). Stream stop should be reported by higher levels. > We would have to drop very old frames during insertion (the buffer would have > to be > notified about the minimum timestamp that it should accept - that would be > the rtp > timestamp of last played frame). It would be simpler than in the current > implementation, as we would know that frames in the head would be certainly > accepted > by decoder, whereas currently we don't know this when we loop through the > array as > decoder decides whether it wants the frame or not. Deciding which frame > should be > played and which not should be the work of jitter buffer only, decoder should > not > interfere (only supply last played frame). Yeah... There are codecs, wich provide their own jitter buffer and PLC, so our dejitter API should be designed to make them usable. All our efforts should be put on increasing audio quality. So all arrived packets should be reported to decoder, even if packet is out of order. However if you have an idea of better interface, you're welcome to suggest. > I have some code that works using linked lists (not UtlSortedList, but custom > implementation, I didn't want to add too much penalty) without the > improvements. Custom implementations are not very welcome. They may contain bugs, already cleaned from standard ones, they mey be less portable, they may be even worse documented. It would be better to adopt standard implementation to your needs. E.g. one of principles of realtime media processing in sipX is to avoid dynamic memory allocation during frame processing cycle. On embedded system it very time consuming operation. As you may see memory pools are used whenever possible. I should say, that memory pools are faster then dynamic memory allocation even on x86. > I would like to hear whether you think that replacing fixed arrays with > linked list > is the way to go. That's it. :) I hope my criticism will not turn you away from improving jitter buffer quality. It is really one of critical parts of all VoIP applications. I believe linked lists are not better then (dynamic) array here, but I also believe that current implementation should be improved greatly. -- Regards, Alexander Chemeris. _______________________________________________ sipxtapi-dev mailing list [email protected] List Archive: http://list.sipfoundry.org/archive/sipxtapi-dev/
