Re: Best algorithmic way to implement MPTCP sequence number space analysis ?

[Evan Huus <eapache () gmail com>]

On Fri, Oct 2, 2015 at 12:11 PM, Matt <mattator () gmail com> wrote:
> Hi,
>
> (Question is at the end, I start with an Multipath TCP introduction (MPTCP) ).
> I would be interested in adding MPTCP sequence number analysis to
> wireshark, similar to what is done with TCP but taking into account
> MPTCP specifics:
> - MPTCP sequence number is 64 bits.
> - MPTCP uses a global sequence number (SN) space and maps this global
> SN to a TCP SN. For instance, an MPTCP socket wants to send the bytes
> 1 to 10. It may send 6 bytes on TCP subflow 1 and the 4 other bytes on
> another subflow 2. On each subflow (=TCP connection), it will send a
> mapping (via a TCP option called DSS=Data Sequence Signaling) saying
> for instance
> on subflow 1 I map MPTCP global SN 1-6 to local subflow SN 21-26,
> on subflow 2 I map MPTCP global SN 7-10 to local TCP SN 60-63.
>
> Keeping track of those DSS options/mappings would help analyzing the
> behavior of an MPTCP connection:
> - does it duplicate some packets over different paths (<=> do some DSS
> overlap on different subflows?)
> - it would allow to generate an MPTCP RTT/application latency since
> striping packets over several paths is likely to increase the
> application latency
> - also allow to deduce if we've captured all subflows or if there are
> holes in the MPTCP sequence number (maybe one subflow was emitting on
> the wifi interface and we didn't capture it)
> etc...
>
> Now here is my problem: what datastructure should I use to achieve
> what I previously describe in a way that could be accepted upstream ?
> or to put it differently how to retrieve a list of ranges (MPTCP start
> SN and end SN) from another SN range ? The interval tree sounds like a
> good solution (http://www.geeksforgeeks.org/interval-tree/) but I
> wonder if there is any advice on an alternate solution ? or ways to
> build the tree efficiently (like disabling rotations and balancing the
> tree only at the end or stuff like that, I am not an algorithmic
> expert).
>
> In any case, I plan to add an option to turn this DSS analysis on/off.

Sounds interesting. Regarding data-structures, the key thing you have
to figure out is what operations exactly you want the data-structure
to have. When you're not sure, I find it helpful to sketch out how the
code would work if you had some magic black-box that could do
anything.

For example, one operation you're probably going to want is something like:
    add_mapping(global_sn_start, global_sn_end, local_sn_start,
local_sn_end, local_id);

What else do you need to be able to do to it to be able to calculate
the things you want?
___________________________________________________________________________
Sent via:    Wireshark-dev mailing list <wireshark-dev () wireshark org>
Archives:    https://www.wireshark.org/lists/wireshark-dev
Unsubscribe: https://wireshark.org/mailman/options/wireshark-dev
             mailto:wireshark-dev-request () wireshark org?subject=unsubscribe