Subject: [ippm] The next steps for the reordering drafts.

From: Henk Uijterwaal <[email-masked]>
Date: Tue, 08 Mar 2005 18:25:22 +0100

How about this...

IPPM Group,

Back in August 2004, we wrote:

>Following the IPPM WG meeting in San Diego, the chairs of the WG met with
>(some of) the authors of the 2 reordering metrics currently under
>discussion in the IPPM WG, in order to discuss the next steps. The drafts
>are:
>
>  draft #1: draft-ietf-ippm-reordering-06.txt
>  draft #2: draft-jayasumana-reorder-density-03.txt

(Now at -08 and -04 respectively)

>We agreed that merging the 2 drafts will be close to impossible due to
>differences in the basic definitions.  We also concluded that both drafts
>contain metrics that are relevant for applications that have to deal with
>reordering.  However, in this area, more study is needed for the second
>draft.  This research is in progress.
>
>We think that the best way forward is:
>
>  1. Add a statement to the introduction of the first draft saying that
>     the current metrics are limited to those that provide some
>     clear insight into network characterization or receiver design,
>     and are not likely to be exhaustive in their coverage of the
>     applications with respect to packet reordering effects. Likewise,
>     additional measurements may be possible.
>  2. Finalize the first draft and publish as a standard track RFC
>  3. Suggest to the WG to take the second draft up as a WG item.
>  4. When the research related to the second draft is done, publish the
>     second draft as either an experimental RFC, or as a followup
>     to the first RFC.
>
>For technical details regarding this discussion, please refer to earlier
>postings.
>
>Comments to the list please,

The WG discussed the drafts in its meeting yesterday.  Of the 4 steps
mentioned above, (1) has been done.  For step 2, Draft-ietf-ippm-reordering 
has gone through several revisions since August and all issues now appear
to have been settled.  The document is expected to be ready for last
call soon.  The chairs propose to finalize this draft as planned on
short notice.

In the meantime, the authors of draft-jayasumana-reorder-density-03.txt
have continued their research, resulting in an -04 version of the
draft and some related publications.   The question is whether the WG
feels that the 2 proposed metrics (RD and RBD) are sufficiently
distinct from the metrics proposed in draft-ietf-ippm-reordering
to warrant a second RFC by this WG (step 3 above).

We would like to hear arguments, pro and con, if the working group
feels that either the RD or the RBD metric (or both, of course) from
draft-jayasumana-reorder-density should become a working group item.

Please send your comments to the list before 1 April.

The chairs,

Matt & Henk

------------------------------------------------------------------------------
Henk Uijterwaal                           Email: henk.uijterwaal(at)ripe.net
RIPE Network Coordination Centre          http://www.amsterdamned.org/~henk
P.O.Box 10096          Singel 258         Phone: +31.20.5354414
1001 EB Amsterdam      1016 AB Amsterdam  Fax: +31.20.5354445
The Netherlands        The Netherlands    Mobile: +31.6.55861746
------------------------------------------------------------------------------

Look here junior, don't you be so happy.
And for Heaven's sake, don't you be so sad.                 (Tom Verlaine)  

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

---

From: Al Morton <[email-masked]>
Date: Tue, 08 Mar 2005 13:00:54 -0500

Henk, Matt,
One small clarification:
>(Now at -08 and -04 respectively)

It's -09 now for draft-ietf-ippm-reordering, (08 was for 2nd WGLC)
and there will be another rev shortly to
capture comments at this meeting.

Al

---

From: Al Morton <[email-masked]>
Date: Mon, 21 Mar 2005 08:58:43 -0500

>draft-jayasumana-reorder-density should become a working group item.

The Reorder Buffer Density (RBD) metric retains the foundation of
a general buffer occupancy calculation. This was the original form
of reordering density in earlier versions of this draft, including
the fact that it records buffer occupancy with loss alone
(no reordering needed to grow the buffer, and the normalization
for lost packets doesn't reduce the occupation to zero).
See section 7, example b. for a scenario with loss, no reordering.

This behavior doesn't seem to fit a reordering metric.

draft-ippm-reordering-09 deals with buffer size more effectively,
in that it only produces values when reordered packets arrive,
in the dimension of bytes.  See the Section on Byte Offset.

Al

P.S. We've been here before...

>At 11:57 AM 02/17/2003 +0100, Henk Uijterwaal (RIPE-NCC) wrote:
>>Nischal,
>>...
>>
>>2. Can you include the same examples as in the other reordering metrics
>>    so one can compare the algorithms?
>>
>>Henk
>
>Case b, packet loss (1,2,4,5,6,7) is sufficient for comparison.
>No reordered packets arrive, yet this metric reports reordering
>density.  The existing metrics maintain orthogonality between
>loss and reordering. Perhaps this algorithm would be better
>characterized as a receiver buffer occupation function.
>
>Al
>

---

From: "Nischal M. Piratla" <[email-masked]>
Date: Mon, 21 Mar 2005 14:21:37 -0700

> The Reorder Buffer Density (RBD) metric retains the foundation of a 
> general buffer occupancy calculation. This was the original form of 
> reordering density in earlier versions of this draft, including the 
> fact that it records buffer occupancy with loss alone (no reordering 
> needed to grow the buffer, and the normalization for lost packets 
> doesn't reduce the occupation to zero). See section 7, example b. for 
> a scenario with loss, no reordering.

To recall, example b from section 7:

"Consider a sequence of 6 packets (1, 2, 4, 5, 6, 7) with DT = BT = 3." 

In this sequence, a measurement needs to buffer packets until the loss 
threshold is reached or sequence has ended. Only at this point the 
packet can be treated as lost. So, the occupancy of buffer is 
intentional to emulate buffering at the receiver and make it useful to 
the application. For reference, please read the message:
http://www1.ietf.org/mail-archive/web/ippm/current/msg00316.html

> draft-ippm-reordering-09 deals with buffer size more effectively, in 
> that it only produces values when reordered packets arrive,
> in the dimension of bytes.  See the Section on Byte Offset. This 
> behavior doesn't seem to fit a reordering metric. 

As you mentioned, we use the term RBD from -02 draft onwards  as it is more descriptive. However, the basic concept appeared in our original paper and draft (Nov. LCN 2002, and Feb. 2003 RD draft). We observe the change in definition of the ByteOffset metric in ippm draft02 (Mar. 2003) and subsequent drafts, which try to account for the buffer size requirement as in RBD. Prior ippm drafts defined ByteOffset metric that 
included inorder packets in buffer requirements. Previous definition of ByteOffset metric (see the >>>>comment section):

*****************
4.3.2 Metric Name: Type-P-packet-Byte-Offset-Poisson/Periodic-Stream

   Metric Parameters: We use the same parameters defined above.

   Definition: Byte stream offset is the sum of the payload sizes of
   all intervening packets between the reordered packet and the
   discontinuity (including the packet at the discontinuity).

   For reordered packet i
   ByteOffset(i) = Sum[in-order packets to start of the reordering
   event]
                 = Sum[PayloadSize(packet at i-1),
                        PayloadSize(packet at i-2), ...
                        PayloadSize(packet at i-n)]

   Alternatively, if all payload sizes are equal:
   ByteOffset(i) = n * PayloadSize  where n is the reordering extent.
   >>>>Comment: Previous comments on the accuracy of extent n apply
   here as well.

4.3.3 Discussion

   The Offset metrics can predict whether reordered packets will be
   useful in a general receiver buffer system with finite limits.  The
   limit may be the number of bytes or packets the buffer can store, or

Morton, et al.      Standards Track exp. Sept 2003              Page 9
Packet Reordering Metric for IPPM                             Mar 2003 

   the time of storage prior to a cyclic play-out instant (as with de-
   jitter buffers).
**********************************

Moreover, there is an issue with the definition of ByteOffset metric itself. For example, consider the sequence (1, 6, 7, 8, 9, 10, 11, 12, 2). Before the arrival of packet with sequence number 2, the buffer size requirement is zero and then it suddenly changes to 7. Thus, there is no use to the application of such a measurement. Obviously, one has to  keep track of these early arrivals to assign 7 as buffer requirement for the last arrival. It means that we do not call this tracking buffer as reorder buffer-occupancy, but still perform the same operation, as in RBD. Moreover, this size could go as big as 'N' due to the absence of threshold. Unless there is a better method stated, this increases the computation complexity of ByteOffset further.

In turn, RBD has more usefulness associated with it, and also emulates dereordering without exceptions. At one point of time, ippm was very concerned about buffer requirements. For example: 

> *********************************************************************
> List-Archive: <http://mailhost.advanced.org/archives/ippm/>
> Date: Mon, 17 Feb 2003 11:57:03 +0100 (CET)
>
> Nischal,
>
>> We have come up with a new metric to measure packet reordering. We have
>> posted a ID and here is the link:
>>
>> http://www.ietf.org/internet-drafts/draft-jayasumana-reorder-density-00.txt 
>>
>>
>> This draft may interest you all. Please feel free to send any
>> comments/suggestions.
>
>
> 1. If I understand the algorithm correctly, then it needs an array
>   in_buffer[N] with N the number of packets in a stream. This is not
>   very practical, when I make a VoIP phonecall, then I never know how
>   long it is going to last in advance and thus how I should dimension
>   this array.
>
> 2. Can you include the same examples as in the other reordering etrics

*********************************************************************************

Threshold value encounters such huge buffer requirements. However, 
we do not seem to be discussing about these requirements anymore! 
Unless, we have missed something, these requirements are very vital for 
real-time measurements.

- Nischal
****************************************************
Research Assistant
Computer Networking Research Laboratory (CNRL)
C203,Dept. of Electrical & Computer Eng.
Colorado State University,
Fort Collins, CO 80523
Voice: 970-491-7067/7974
Fax:   970-491-2249
http://www.cnrl.colostate.edu
http://lamar.colostate.edu/~nischal
****************************************************

---

From: Al Morton <[email-masked]>
Date: Mon, 28 Mar 2005 15:24:43 -0500

At 04:21 PM 03/21/2005, Nischal M. Piratla wrote:
>>Al wrote:
>>reordering density in earlier versions of this draft, including the fact 
>>that it records buffer occupancy with loss alone (no reordering needed to 
>>grow the buffer, and the normalization for lost packets doesn't reduce 
>>the occupation to zero). See section 7, example b. for a scenario with 
>>loss, no reordering.
>
>threshold is reached or sequence has ended. Only at this point the packet 
>can be treated as lost. So, the occupancy of buffer is intentional to 
>emulate buffering at the receiver and make it useful to the application.

Every lost packet causes your buffer to grow until it is declared lost.
That might be something useful, but RBD is not a reordering metric
in a strict sense, because there will always be ambiguity:
Did lost packets or reordered packets (or both) cause buffer growth?

A key point of standardizing a reordering metric is to distinguish
reordering from loss - they have different causes and cures.

If I look at the RBD buffer occupation frequencies,
there will be many sizes encountered as the buffer is growing.
But only one of the sizes is relevant to buffer design in this context,
the size needed to restore a reordered packet to order.
One could look at a histogram of buffer sizes after a measurement,
but the RDB frequencies alone are not sufficient to say whether a
specific buffer size can mitigate reordering and to what extent
(as a fraction of reordered packets).

>For reference, please read the message:

I did in 2004, and I incorporated several of Michal's comments in
the draft (Section 6 on Measurement and Implementation Issues).
We recently refined the text there through comment and review.

>>Al wrote:
>>draft-ippm-reordering-09 deals with buffer size more effectively, in that 
>>it only produces values when reordered packets arrive,
>>in the dimension of bytes.  See the Section on Byte Offset. This behavior 
>>doesn't seem to fit a reordering metric.

Hmmm.  Your mail tool seems to be reordering sentences.
The last sentence above applies to RBD, and was prior to the others
in my original message.  The archive has the text in-order:
http://www1.ietf.org/mail-archive/web/ippm/current/msg00605.html

Al

---

From: "Nischal M. Piratla" <[email-masked]>
Date: Wed, 30 Mar 2005 16:26:25 -0700

Al Morton wrote:

>>> doesn't reduce the occupation to zero). See section 7, example b. 
>>> for a scenario with loss, no reordering.
>>
>>
>> In this sequence, a measurement needs to buffer packets until the 
>> loss threshold is reached or sequence has ended. Only at this point 
>> the packet can be treated as lost. So, the occupancy of buffer is 
>> intentional to emulate buffering at the receiver and make it useful 
>> to the application.
>
>
> Every lost packet causes your buffer to grow until it is declared 
> lost. That might be something useful, but RBD is not a reordering metric

I thought, IPPM agreed on having multiple definitions of reordering, if  
there is a use. As I pointed out in 62nd IETF meeting, n-reordering does 
not measure reordering, as in sequence (1, 4, 5, 6, 2, 3), it shows 2 as 
reordered but not 3. "That might be something useful, but n-reordering 
is not a reordering metric in a strict sense, because there will always 
be ambiguity: " However, it was the consensus at IPPM meeting that we 
should explore multiple definitions to extract broader usefulness from 
the metrics.

> (as a fraction of reordered packets).

Loss Orthogonal RBD or L-RBD is a modification to RBD that eliminates 
its sensitive behavior to buffering while waiting for lost packets. We 
suggested stay-back and go-back implementations for the same. If the 
objective is solely to make RBD sensitive to reordering and not losses 
as you suggest, L-RBD is capable of that and we can put it back. But we 
(and others (msg00316) feel that RBD is more useful in its current 
form.But it does not mean that we cannot have both of them if you 
convince us it is necessary.

I am not sure whether we are trying to demerit/merit same points at 
different instances! (It seems that same people argue for and against 
same feature at different times..)

> http://www1.ietf.org/mail-archive/web/ippm/current/msg00605.html

I responded to each point you made in that e-mail, not necessarily in 
the same order that you raised them. The chronology of the drafts still 
remains valid, i.e., RBD (then RD) was first introduced in Nov. 2002 
followed by our draft in Feb. 2003 and the concept had later appeared in 
March 2003 IPPM draft.
- Nischal

---

From: Henk Uijterwaal <[email-masked]>
Date: Thu, 31 Mar 2005 15:16:14 +0200

Nischal,

>I thought, IPPM agreed on having multiple definitions of reordering, 
>if  there is a use.

It is more the other way around: we would like to see 1 metric, but realized
quite early on in the discussion that depending on the application some
definitions make more sense than others.  So, we agreed to include >1 metric
in the draft.

>  As I pointed out in 62nd IETF meeting, n-reordering does not measure 
> reordering, as in sequence (1, 4, 5, 6, 2, 3), it shows 2 as reordered 
> but not 3. "That might be something useful, but n-reordering is not a 
> reordering metric in a strict sense, because there will always be ambiguity:

I think this shows that there is no intuitive definition of reordering.
Take the sequence (1, 4, 2, 3).  This sequence is reordered with respect
to the original (1, 2, 3, 4).

It is not that clear for the individual packet.  For packet 3, I can argue
that it is still in the same order w.r.t. packet 2 (and packet 1) as they
were sent, so packet 3 is not reordered.  OTOH, it is out of order w.r.t.
packet 4, so it is reordered.   So, is packet 3 reordered or not? We can
probably argue on this forever, but I don't think that will get us
anywhere.

Rather, I think we should simply define metrics, understand what they
do in certain cases, and see if this returns a useful number to measure.

Henk