Re: [ippm] draft-jayasumana-reorder-density-03.txt

[Anura Jayasumana <[e-mail]>]

Hi Al.
The responses to the points you raised are given below:
Al Morton wrote:

> At 06:27 PM 07/22/2004, Anura Jayasumana wrote:
>
>> We have posted a revised version of our draft on metrics to measure 
>> packet reordering: 
>> http://www.ietf.org/internet-drafts/draft-jayasumana-reorder-density-03.txt
>
>
> Hi Anura,
>
> Thanks for the pointer to your latest draft. 
> This new version of Reordering Density continues to use
> a unique definition for reordered or "late" packets, 

We do distinguish between late and early packets. Reordered does not 
mean a packet is late, it could be early as well.
Consider the following two examples:
Ex. 1: Sequence 1,3,4,5,6,7,8,9, 10,2,11,12,13,14,....
Ex. 2: Sequence 1,10, 2, 3,4,5,6,7,8,9, 11,12,13,14,....
Ex. 3: Sequence 1,2,3,5,4,6,7,8,...
It is very likely that sequence in ex. 1 is caused by  packet 2 arriving 
late rather than packets 3-10 arriving early,
although latter is a plausible scenario.
Similarly, it is very likely that ex. 2 is caused by packet 10 arriving 
early rather than any of the packets 2-9 arriving late, although it is 
also plausible. (Here arriving late means taking more time than what is 
reasonable for inorder delivery).
In case of Ex. 3, packet 5 is earlier than usual and packet 4 is later 
than usual in sequence.
Thus, defining only late packets or only the early packets as reordered 
provides only a partial picture.
Also note the dependency between late and early packets. in case of ex. 
3, packet 4 would not be late without packet 5 being early.
By  accommodating that reordered packets can either be late or early, 
we  provide a more comprehensive picture.

In section 13.1.1 of Paxson's Ph.D. dissertation, the author has recognized the difference
between late arrivals and premature arrivals. However, to measure the
percentage reordering, he had made a choice.   If the goal is to provide a measure of percentage reordering, a measure that considers only the late packets is OK. However, one can make similar arguments about basing the percentage only on early packets, which would be OK as well.  However the two measures will be different.
We found that a definition based only on lateness or only on earliness is limiting in many ways. 
Some of the results that we have derived based on RD (to be published), do show the relationships between lateness and earliness. 


> and
> a definition of packet loss that deviates from RFC 2680,
> if I understand it correctly. 


RFC 2680, section 2.5, states the need for having a threshold:
      "A given methodology will have to include a way to distinguish
      between a packet loss and a very large (but finite) delay.  As
      noted by Mahdavi and Paxson [3], simple upper bounds (such as the
      255 seconds theoretical upper bound on the lifetimes of IP
      packets [4]) could be used, but good engineering, including an
      understanding of packet lifetimes, will be needed in practice.
      {Comment: Note that, for many applications of these metrics, there
      may be no harm in treating a large delay as packet loss.  An audio
      playback packet, for example, that arrives only after the playback
      point may as well have been lost.}"
Granted that it talks about threshold based on time as opposed to a number of packets (DT), still it looks like 
this RFC makes a clear case for use of a threshold as we do. 
Although we have not discussed it in the draft, RD can easily accommodate a time threshold as well.
(If this is important, we can add a section to the draft).




>
>
> Since your method requires that lost packets be identified
> before reordering evaluation, let's look at your definition
> of loss in section 5.  "...a packet is not considered lost until
> it is late beyond DT, ..." where DT is the Displacement Threshold
> in units of packets.  So, at least DT packets must arrive
> following a lost packet to classify it correctly. But what if
> I send 100 packets, and the last 50 never arrive?  RFC 2680 would
> designate the last 50 packets as lost after a time-out, and
> does not require successful arrivals after a loss to do so.
> This definition has roots in the fact that all packets have a
> useful lifetime in the context of their protocol or application. 

Although we have not addressed this specifically in the text, the 
algorithms presented in the draft
consider such cases, i.e., when there are no more incoming packets, it 
goes through the remaining packets
and completes the computation. However, considering this comment, we 
will update the definition to read as follows:

"...a packet is not considered lost until it is late beyond DT or there are no
more arriving packets.."

We also mention that the metrics can be calculated in two ways: Stay-back and Go-back. 
We have included only the stay-back versions of algorithms, where the computation lags the packet arrivals.
In the go-back approach, the computation keeps up with the latest arrival, but goes back and makes corrections 
when losses are detected. 


>
> (The sensitivity of the results to choice of DT is another
> issue, but let's set that aside for now.)

See comment related to RFC 2680. Also, DT can be set to N (number of 
packets) if this is a problem.
Wrong selection of DT does affect the resolution accuracy, but this 
would be the case with any measurement
tool. In fact the ability to change DT provides the flexibility 
necessary for balancing accuracy vs measurement complexity (ex. use of a 
yard stick vs a vernier caliper).

>
>
> Here's a new example to illustrate the difference between
> the reordering definitions (with no loss or duplication):
>
>    Arrived sequence:    1   2   3   7    5    6   4   8
>    Receive_index:       1   2   3   4    5    6   7   8
>    Displacement:        0   0   0  -3    0    0   3   0
>
> In this example, your definitions designate packet 7 as early,
> and packet 4 as late, and we're in agreement this far. But
> ippm-reordering's non-reversing sequence criterion designates
> packets 5 and 6 as reordered (they are clearly late, arriving behind 7).
> Your metric appears to enforce the original sequence in this example
> (elsewhere, it corrects the original sequence for lost packets).

 As stated earlier, imposing a criteria such as non-reversing sequence 
is not necessary  for measurement of reordering,
and in fact it impedes the use of reorder metric for  many purposes: 
being able to model reordering of interconnected subnets etc.

>
>
> The example also raises an issue for your definition of
> Buffer Occupancy (B) in section 2.9.
>    "An arrived packet with a sequence number greater than that of
>    expected packet is considered to be stored in a hypothetical buffer
>    long enough to recover from reordering. At any packet arrival, the
>    buffer occupancy is equal to the number of such out-of-order packets
>    in the buffer including the arrived packet (assuming one buffer for
>    each packet)."
>
> Using the same example arrival sequence:
>
>    Arrived sequence:    1   2   3   7    5    6   4   8
>    Receive_index:       1   2   3   4    5    6   7   8
>    Buffer Occupancy:    0   0   0   1    1    1   0   0
> but a real buffer would hold:
>    Real Buffer:         0   0   0   1    2    3   0   0
>
> I tried this example on your web site, and obtained the
> "real buffer" result for RBD, so it appears that your algorithm
> differs from your text definition.
> The Displacement result above was also confirmed.

It appears that  we have failed to  explicitly state that the expected 
sequence number
is different from receive_index. We will make a note to change this in 
the next version.
For RBD computation, we use expected sequence number and not receive_index.
Thus the above example will corresponds to:

Arrived sequence : 1 2 3 7 5 6 4 8
Receive index    : 1 2 3 4 5 6 7 8
Expected         : 1 2 3 4 4 4 4 8
Buffer Occupancy : 0 0 0 1 2 3 0 0


> A few of us who read the -02 version of your draft, the
> one that tracked buffer occupation for loss and reordering
> combined, thought it might be useful as a general "derived
> metric". (see ippm-list discussion a few weeks ago).

Based on the feedback at the IETF meeting in MN, we did modify the 
metric to make it orthogonal to losses.
Perhaps we need to keep the version without loss detection as well.


>
> Perhaps we can discuss this further in San Diego.
>
> regards,
> Al

I look forward to meeting you. Thanks for all the comments.
Regards!
Anura


-- 
Anura P. Jayasumana <http://www.engr.colostate.edu/%7Eanura>
Professor, Electrical & Computer Engineering
                           and Computer Science
Department of Electrical and Computer Engineering
Colorado State University
Fort Collins, CO 80523
Phone: [phone]
Fax: [phone]
Email: <[e-mail]>

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