[erlang-questions] Packets deduplication

[Jesper Louis Andersen]

A simple solution that may work in the end is to keep track of a window of
bits:

* shift the window as the ID increases
* check older packets against the window

This gives you "SACK" support, is fast to check against and fast to expire
old data due to the shifting.

Simply using an ordered list or a map could also work if you clean it up
eventually. It depends on how fast your CPU core is.


On Thu, Feb 18, 2016 at 2:24 PM, Alexander Petrovsky <askjuise@REDACTED>
wrote:

> Ouch, I forgot to say, the IDs can be sparse, so they not really
> monotonically, they just grow, and can be reordered.
>
> 2016-02-18 16:20 GMT+03:00 Danil Zagoskin <z@REDACTED>:
>
>> Hi!
>>
>> If ID grows monotinically and you have no plans of recovering after
>> packet reordering, then you can just keep the previous ID.
>>   - If CurID > PrevID, CurID is unique;
>>   - If CurID == PrevID, it is not unique;
>>   - If CurID < PrevID, it is a bug or reordering, let it crash.
>>
>>
>> On Thu, Feb 18, 2016 at 3:01 PM, Alexander Petrovsky <askjuise@REDACTED>
>> wrote:
>>
>>> Hi!
>>>
>>> I have the stream of packets with ID (int), and I need to check is the
>>> packet is uniq (by ID) or not?
>>>
>>> Incoming rate is about 20k pps and ID is monotonically grows. What's the
>>> best way and data structure fit for this problem?
>>>
>>> --
>>> Петровский Александр / Alexander Petrovsky,
>>>
>>> Skype: askjuise
>>> Phone: +7 914 8 820 815
>>>
>>>
>>> _______________________________________________
>>> erlang-questions mailing list
>>> erlang-questions@REDACTED
>>> http://erlang.org/mailman/listinfo/erlang-questions
>>>
>>>
>>
>>
>> --
>> Danil Zagoskin | z@REDACTED
>>
>
>
>
> --
> Петровский Александр / Alexander Petrovsky,
>
> Skype: askjuise
> Phone: +7 914 8 820 815
>
>
> _______________________________________________
> erlang-questions mailing list
> erlang-questions@REDACTED
> http://erlang.org/mailman/listinfo/erlang-questions
>
>


-- 
J.
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://erlang.org/pipermail/erlang-questions/attachments/20160218/a643418d/attachment.htm>