Subject: [ippm] thoughts on reordering draft (-08)

From: Mark Allman <[email-masked]>
Date: Tue, 25 Jan 2005 16:53:24 -0500

Folks-

I read through the reordering i-d again today and have some comments (to
followup my comments from November).  Some of them are small, some less
small.

Section 2:

  * I'd really like to see the word "successfully" removed from the
    first sentence.  It's just confusing, IMO.

  * Second sentence: "Internet Protocol" --> "The Internet Protocol"

  * "other protocols" --> "protocols at higher layers of the stack than
    IP"

Section 2.2:

  * I like point #2, but I think it could be made a bit more crisp.
    Something like: We define a number of methods for quantifying
    reordering because various applications are impacted by packet
    reordering in different ways and the characteristics of the metric
    must be well matched with the application's behavior.  (Or,
    something a little more like that than what's in the document.)

  * I still don't like the "relevance to TCP" bullet.  (More below.)

Section 3.2:

  * This just doesn't look like it was buffed to talk about only message
    numbers (and not bytes or time).  E.g., the definition of NextExp is
    bogus.  And, it would seem as if SrcByte and PayloadSize and SrcTime
    should be noted as optional.

Section 3.4:

  * I'd like to see a small note that indicates that loss and reordering
    cannot be completely untangled without observing the packets at each
    hop along the path.  E.g., a packet could be reordered and then
    lost.  I don't think there is really much one can do about this, but
    I think it should be explicitly called out so that people are aware
    of this form of skewing.

Section 4:

  * This entire section needs a scrubbing.  The section is pretty
    haphazard in its definitions.  Some definitions are pretty informal
    (like the ratio) and some are very formal (like the extent) -
    forgetting all about the notation developed in the previous section
    and some definitions are given in pseudo-code (reordering free run).
    Sometimes we see s[i] and sometimes s(i).  Etc., etc.  It looks like
    this was written by committee.  I'd suggest that one person takes a
    pass at this section and makes it a bit more uniform and a bit
    easier for the reader to follow.

Section 4.2.4:

  * "A receiver must possess storage to restore order to packets that
    are reordered."  I think this needs tamed a bit.  *IF* an
    application cares to keep all data in order they need buffer.  But,
    late packets might be as good as lost.

Section 4.3:

  * One could argue for or wonder about interpolation here.  I.e., if I
    see 1,10,5 then the amount of lateness is really not quite right as
    measured from either of the known arrivals.  I would think a note
    would at least be in order here --- if not thinking about trying to
    add a little cleverness.

Section 4.6.4:

  * I am not sure I would consider this a discussion.  It's more of an
    example.

Section 5:

  * Well, I still really think this section is sort of bogus.  It's not
    as bogus as in the last version since requiring BTC.  But, the
    document basically argues that this is important for a couple of
    reasons.  First, because it will help us "[determine] the portion of
    reordered packets that can or cannot be restored to order in a
    typical TCP receiver buffer based on their arrival order alone".
    But, since we require BTC the sending is all window-based.  We can
    certainly tell if the reordering puzzles itself out within that
    window.  But, we cannot tell how big the window would need to be to
    disambiguate things because we don't have such a window.  I am
    pretty skeptical that there is a solid inference algorithm you could
    use, but the document needs that algorithm if its going to make this
    claim because otherwise it's a big damn handwave.  And, what's more
    we don't need n-reordering to tell this.  We just have to look at
    the BTC stream and figure it out.

    Second, the document says that by looking at n=3 reordering we can
    figure out how often we needlessly trigger fast retransmit.
    However, BTC can measure this directly because it *will* botch fast
    retransmit.  All we have to do is to count the number of times we
    botch fast retransmit.  We don't need the reordering algorithm to
    get this information.

    I basically buy neither of these.  Below I provide something I do
    buy in this space.

  * The document notes that n-reordering is nice because it's less
    complicated than a TCP.  But, once you layer it on top of BTC (which
    is necessary) I don't think it is much less complicated.  I'd remove
    this statement.

  * "For n=3..." the document should cite RFC2581 (about halving the
    cwnd and the three duplicate ACKs).  NewReno also uses three
    duplicate ACKs, but the definition comes from the base CC spec.  I'd
    also note that n=3 is the "magic number" for SCTP and DCCP, as well.

  * In this space I would buy one application of n-reordering.  I think
    it'd be fine to rip out the explanation that is there and leave one
    thing.  The one thing is that it'd be nice to assess the duplicate
    ACK threshold that would have kept the TCP from spuriously
    retransmitting.  E.g., if we see no n=6 reordering events, but lots
    of n=1--5 events then n=6 seems like the magic number.  This, in
    some sense, gives an idea about how far the path is "off" from being
    able to stay out of TCP's way.

Section 6:

  * I don't buy the notion that test packets should be emitted as fast
    as possible to catch reordering to the "greatest extent".  I would
    very much rather the document advocated sending in a pattern as
    similar to the particular application one cares about as possible.
    Measuring reordering to the greatest extent possible by sending
    every millisecond doesn't really help dimension buffers in an app
    that sends every 10msec.  I don't think the goal should be some
    somehow "catch" reordering, but rather to accurately assess
    reordering in a situation someone cares about.

  * This section also has some old artifacts about clocks and bytes that
    are no longer required.

  * I like the note that with TCP one could use time to help
    disambiguate reordering and retransmits.  I would suggest mention
    the TCP timestamp option and citing it (RFC1323).

  * Again, "some in-order packet arrivals may not be useful to TCP" is
    bogus in the context of using a BTC stream to measure reordering.

Overall, I think it's getting better.  Good work!

allman

--
Mark Allman -- ICIR -- http://www.icir.org/mallman/

_______________________________________________
ippm mailing list
[email-masked] 
https://www1.ietf.org/mailman/listinfo/ippm

---

From: Michał Przybylski <[email-masked]>
Date: Wed, 26 Jan 2005 09:40:51 +0100

Dear Mark,

>     reordering in a situation someone cares about.

This is the comment resulting from our practical study. I understand 
that for the particular application *reordering buffer tuning* one would 
want to simulate an application stream (we have tested this as well and 
it helps a lot).

On the other hand the "line speed" sending helps to reveal many  sources 
of reordering that would probably not influence this application, but 
may have impact on another, for example faster. This is especially 
useful for estimating the reordering for highly demanding applications, 
such as those of HEP or VLBI, using >1Gbit/s datastreams. It allows to 
have some insight into future network use, providing the information on 
"what is the worst reordering scenario that may happen to me?".

So this is not intended to dimension reordering buffers but to establish 
the "reordering fingerprint" of the network, which helps to understand 
how to use it with future applications.

Regards,

Michal

-- 
______________________________________________________________________
Michal Przybylski         Network Research and Development
[email-masked]     Poznan Supercomputing and Networking Center
+48 61 858 20 27          http://www.man.poznan.pl
______________________________________________________________________

---

From: Mark Allman <[email-masked]>
Date: Wed, 26 Jan 2005 08:58:12 -0500

> So this is not intended to dimension reordering buffers but to
> establish the "reordering fingerprint" of the network, which helps to
> understand how to use it with future applications.

I am not sure I buy all of this.  Determining a worst case reordering
may, indeed, have some benefit.  But, there is also cost.  What I don't
buy is that one could somehow easily extrapolate how some other app
would work based on such a test.  I think I would like to see more
explanation of this in the document.  I.e.,

  * Not a recommendation to send as fast as possible.  One could offer
    that as a possibility to stress test a path.  And, certainly that
    could help tease out all the reordering that a path is capable of.
    However, you have to be pretty careful here because I don't think we
    want to advocate blasting test streams across the big-I Internet at
    arbitrarily high rates.  And, we want the reader to understand that
    such a sending pattern is not terribly acceptable.  So, it seems to
    me this is sort of thorny.

  * A clear recommendation that says that to gauge reordering for any
    particular application the best way to do that is to send using the
    same pattern as that application.  E.g., using a BCP scheme for
    assessing how reordering impacts bulk FTP transfers.  Or, a periodic
    sending rate that mirrors real-time apps.  Or, whatever.  Basically,
    it's better to *measure* than to try to *infer* because inference is
    really, really difficult to get right.

Thanks!

allman

---

From: Michał Przybylski <[email-masked]>
Date: Wed, 26 Jan 2005 15:12:43 +0100

>     I don't think we

Well, if you are interested in measuring the reordering extent up to 10 
positions, you have to send only 10 packets at a full speed - not much, 
but still abusive if measurement continued in longer intervals or too 
often. Anyway, sending at full rate was very usefull for us - even for 
finding out the equipment "impairments" that we were not aware of before 
measuring.
And if the end user (FEth? ADSL?) sends across Big-I Internet (10Gbit/s) 
his maximum speed stream, probably noone will notice.

>     same pattern as that application.  

I also think that this is the best way for measuring the *possible 
reordering* for particular applications.

All the best,

Michal

---

From: Mark Allman <[email-masked]>
Date: Mon, 31 Jan 2005 11:08:10 -0500

> >     I don't think we want to advocate blasting test streams across
> >     the big-I Internet at arbitrarily high rates.  And, we want the
> >     reader to understand that such a sending pattern is not terribly
> >     acceptable.  So, it seems to me this is sort of thorny.
> 
> Well, if you are interested in measuring the reordering extent up to
> 10 positions, you have to send only 10 packets at a full speed - not
> much, but still abusive if measurement continued in longer intervals
> or too often.

Exactly.  If you send only one volley of 10 packets then that's fine - I
have no problem with it.  But, the trouble is that's not a very solid
assessment of the network.  And, given that this is intended to be a
standard way to assess reordering I think there should be some words to
the effect that one needs to be quite careful.

> Anyway, sending at full rate was very usefull for us - even for
> finding out the equipment "impairments" that we were not aware of
> before measuring.  And if the end user (FEth? ADSL?) sends across
> Big-I Internet (10Gbit/s) his maximum speed stream, probably noone
> will notice.

I think it would be fine to divided things into application-oriented
assessment and stress testing and discuss each in more detail than
either is touched upon now.

> reordering* for particular applications.

I disagree with that phrasing (but, maybe not the intent).  If my
application only sends one packet every 10 seconds then there is no way
that a stress test can predict the "possible" reordering my application
will observe.  I would buy that sending at line rate may provide an
upper bound on the amount of reordering that *some* application could
conceivably observe.  And, that might be useful.  But, I think trying to
tie such a notion to any "particular application" is very thorny and
quite tenuous. 

allman