[erlang-questions] Packets deduplication

[Alexander Petrovsky]

Yep, right now I try to do something similar with bitmap and sliding
window, that will shift. Could you explain about maps?

Thanks!

2016-02-18 16:37 GMT+03:00 Jesper Louis Andersen <
jesper.louis.andersen@REDACTED>:

> 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.
>



-- 
Петровский Александр / Alexander Petrovsky,

Skype: askjuise
Phone: +7 914 8 820 815
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://erlang.org/pipermail/erlang-questions/attachments/20160218/54bf1c39/attachment.htm>