Subject: Re: [ippm] OWDP inter-packet times (Was: IP Delay variation...)

From: Matthew Roughan <[email-masked]>
Date: Fri, 01 Jun 2001 14:01:14 -0400

Attila Pasztor wrote:
> 
> Hi Stanislav,
> 
> Please excuse me if my question is not appropriate. In your mail to
> Darryl you make the following statement:
> 
> > We need to communicate the packet send schedule beforehand to be able
> > to detect losses.
> 
> Why? I am sorry, but I don't get it.
> 
> I believe that the loss detection should be based on packet serial
> numbers. If it is a problem to detect when a measurement starts or when
> it has ended, it can be communicated with simple control messages between
> the sender and the receiver.
> 
> 1. Sender sends a "Measurement starts" message
> 2. Receiver sends back an acknowledgement
> 
> 3. If the ack is received Sender starts to send the measurement packets;
> if the ack is not received within a finite time, then it resends message
> #1
> 4. Sender continues to send packets according to his preferred timing
> schedule
> 
> 5. Sender sends an "End of measurement" message, including the serial
> number of the last packet sent
> 6. Receiver sends back an acknowledgement
> 7. If the sender does not receive an ack within a finite time the sender
> resends message #5
> 
> (Note: limit the number of resending the messages, if no ack is received
> after n trials, then the measurement has failed)
> 
> 8. If there are any packets missing, after a certain time receiver
> assumes they are lost
> 
> I think that the process described above detects the losses reliably
> (except packet delays exceeding the time outs).
> Including serial numbers in the packets is needed anyway, I don't think
> that losses could be detected reliably only based on the sending
> schedule.
> 
> Please, explain to me, why do we need to communicate the packet send
> schedule beforehand to be able to detect losses?
> 
> By the way, in RFC 2680 'A One-way Packet Loss Metric for IPPM' there is
> no mentioning of communicating the send schedule.
> 
> Thanks,
> Attila
> 

I agree. The above makes sense to me.

Matt
_______________________________________________
ippm mailing list
[email-masked]
http://mailhost.advanced.org/mailman/listinfo/ippm

---

From: stanislav shalunov <[email-masked]>
Date: 01 Jun 2001 17:04:34 -0400

Attila Pasztor <[email-masked]> writes:

> I believe that the loss detection should be based on packet serial numbers.

Attila,

The approach that you describe can work, however it doesn't appear to
solve the whole problem.  We believe communicating the send schedule
is necessary for the following reasons:

* If the receiver were to detect losses it needs to detect times when
  they occured, and not simply the fact that there were losses.  If
  the sender doesn't tell the receiver somehow when the packets were
  sent, and packets are lost, information is lost for the receiver.

* Without being able to specify what send schedule you want a client
  can't ask OWDP servers to perform measurements it wants.  So, while
  half of the problem (measurements from me to machines administered
  by other people) is solved well, the other part (measurements of the
  path back to me) is not addressed.  The server presumably could be
  configured to send me something reasonable, but what if I want
  something else?  We started by wanting to give the parties more
  control over when packets are sent; in effect, the degree of control
  is lessened for paths to the client--earlier it could at least
  request Poisson rate, now not even that.

* Having knowledge about send times allows to detect losses in a more
  timely manner.  Imagine that a (very long) session starts, goes on
  for two hours, and then connectivity is lost completely.  Neither
  the receiver nor the sender notice anything until the connectivity
  is restored and the receiver gets a packet with a sequence number
  that's much larger than what it expects.  ("When no packets are
  coming, is it the network or is it just such a send schedule?")

* Not sending the schedule in advance can require the receiver to keep
  more state.  Under normal circumstances, just a little bit more
  state; but how do you deal with a situation when somebody starts
  sessions continuously and then just abandons them without notifying
  you in any way?  Do you wait indefinitely for more packets?

We believe one really needs to communicate the send schedule somehow.
(And the manner of communication is an open question for now.)

-- 
Stanislav Shalunov		http://www.internet2.edu/~shalunov/

"I didn't attend the funeral, but I sent a nice letter saying that I
approved of it."				-- Mark Twain
_______________________________________________
ippm mailing list
[email-masked]
http://mailhost.advanced.org/mailman/listinfo/ippm

---

From: Attila Pasztor <[email-masked]>
Date: Mon, 04 Jun 2001 12:01:44 +1000

Hi Stanislav,

Thanks for your comments, I have some more questions. Just before replying to
your comments, I would like to repeat the statement which you made earlier, and

>   sent, and packets are lost, information is lost for the receiver.

If you want to detect times when losses occur, the only way to do it is to make
the nodes report when they drop a packet ( I don't think that anyone would
really want to do this).
The next best estimate of the time of the packet loss is an interval given by
the send time and the loss detection time-out.
I agree that to get this information (by the way, what is it good for?), the
send time has to be known.  If one really wants to get this information it could
easily be generated by the server (who is contacted anyway by the
retrieve-client, to provide him with the results).
So for this reason I don't think that it is necessary to send the sender
schedule to the Session-receiver.

>   request Poisson rate, now not even that.

I fully agree that the schedule has to be sent to the Session-sender, but I
don't think, as I have earlier mentioned, that there is a need to send the
schedule to the receiver. There are several ways to do it, send a compressed
table of the measurement start time, packet inter departure times and sizes,or
just definitions of patterns which should be repeated with spacing according to
some statistical distributions, or one could even imagine sending applets (or
any similar kind of (more?) secure active agents) to generate the stream at the
sender.

>   coming, is it the network or is it just such a send schedule?")

A very simple solution to this case is to send the sending time (or rather the
expected duration of the the measurement session (it might by more useful with
not too reliably synchronised hosts)) of the last packet to be sent to the
receiver (include it in the session start message).

>   you in any way?  Do you wait indefinitely for more packets?

The same solution applies as in the previous case.

> (And the manner of communication is an open question for now.)

As I mentioned above I agree, that it has to be communicated with the
Session-Sender, but I don't think that it should be communicated to the
receiver, and I definitely don't think that the receiver needs this information
to be able to detect losses.

By the way, why is this protocol called One-Way delay measurement protocol?
Based on what is described in the draft and on the comments from the ongoing
discussion I think it would be much more appropriate to call it Active
measurement protocol (or something similar, but definitely more general than
one-way delay) as using the time stamps and serial numbers recorded during these
measurements much richer set of metrics can be obtained than just the one-way
delay.

Regards,
Attila

---

From: stanislav shalunov <[email-masked]>
Date: 04 Jun 2001 11:53:09 -0400

Attila Pasztor <[email-masked]> writes:

> If you want to detect times when losses occur, the only way to do it
> is to make the nodes report when they drop a packet ( I don't think
> that anyone would really want to do this).  The next best estimate
> of the time of the packet loss is an interval given by the send time
> and the loss detection time-out.

It's my understanding of RFC2679 that the time that is reported with a
loss is the time when the sender has transmitted the first bit of the
packet in question (and certainly not the time when some router has
decided to discard it from the queue or whatever).

Quoting RFC2679 section 3.4:
#   >>The *Type-P-One-way-Delay* from Src to Dst at T is undefined
#   (informally, infinite)<< means that Src sent the first bit of a
#   Type-P packet to Dst at wire-time T and that Dst did not receive that
#   packet.

> I agree that to get this information (by the way, what is it good
> for?), the send time has to be known.

Usefulness of loss timestamps (and precise timestamps) is really an
RFC2679 question.  A practical situation where you'd want this:
You have a mesh of test streams between various sites; each stream is
some random stream with an average of 1pps; you suspect that egress
side of a certain site's connection experiences burst loss (high loss
probability during a period of time of a few milliseconds every few
seconds); you want to figure out the average duration of the loss; you
get all three dozens of measurement sessions from that site to anywhere
and correlate loss times.

> If one really wants to get this information it could easily be
> generated by the server (who is contacted anyway by the

Retrieve-Client today only talks to the Server (which may represent
Session-Receiver only).  Informally, you don't need to ask the sender
any questions to get the results.

> I fully agree that the schedule has to be sent to the
> Session-sender, but I don't think, as I have earlier mentioned, that
> there is a need to send the schedule to the receiver.

See previous sentence.

> There are several ways to do it, send a compressed table of the
> measurement start time, packet inter departure times and sizes,or
> just definitions of patterns which should be repeated with spacing
> according to some statistical distributions, or one could even
> imagine sending applets (or any similar kind of (more?) secure
> active agents) to generate the stream at the sender.

These are all being considered.  A way to compress the send schedule
so that:

1. It's relatively simple
2. It compresses most common cases into O(1) bytes
3. It allows to send arbitrary schedule

is required.  Sending Turing-complete description (such as a Java
applet or a vax binary) is provably the best way to do that
(asymptotically best after an additive constant).  Unfortunately,
executing the instructions is cumbersome and there's no way to tell
whether something is a valid time schedule specification.

> A very simple solution to this case is to send the sending time (or
> rather the expected duration of the the measurement session (it
> might by more useful with not too reliably synchronised hosts)) of
> the last packet to be sent to the receiver (include it in the
> session start message).

Doesn't appear to solve the problem.  A session that's expected to
last a week starts.  Two hours into the session, 7000 packets are
received.  During the next day no packets are received (this is
actually due to a network outage).  Then packet trickle resumes.  When
does the receiver learn that there was packet loss?  When connectivity
is resumed and it sees the first packet with the wrong sequence
number.  Sender knows it sends one packet per second on average, but
it never during the session learns what packets the receiver sees.
If the function of the session were to alert somebody to connectivity
loss, the function isn't fulfilled.

If send schedule were known in advance to the receiver, then it would
detect that losses are occuring after a timeout would expire after
connectivity loss.

> By the way, why is this protocol called One-Way delay measurement

Maybe a poor name choice indeed (essentially a codename; I don't know
when it started).  I'm not sure if we're stuck with the name now.

Beware of Programmers who carry screwdrivers.    -- Leonard Brandwein
_______________________________________________
ippm mailing list
[email-masked]
http://mailhost.advanced.org/mailman/listinfo/ippm

---

From: "Henk Uijterwaal (RIPE-NCC)" <[email-masked]>
Date: Tue, 5 Jun 2001 13:38:13 +0200 (CEST)

Attila,

> schedule beforehand to be able to detect losses?

Suppose a destination has received packets 1 to N from a source and after
that nothing.  There are now 2 possibilities: packet N+1 was never
scheduled to be sent _or_ N+1, N+2, ... have all been lost.

With just sequence numbers, there is no way dest can know if N+1 was
scheduled to be sent.

With a schedule, the destination knows that N+1 was scheduled to be sent,
so if it didn't arrive, it either must have been lost _or_ something is
wrong with the source.  

How useful the second scenario is, depends on the reliability of the
source and the packet-rate, but I don't think we should exlude this 
in the design.

Henk

------------------------------------------------------------------------------
Henk Uijterwaal                    Email: [email-masked]
RIPE Network Coordination Centre     WWW: http://www.ripe.net/home/henk
Singel 258                         Phone: +31.20.5354414
1016 AB Amsterdam                    Fax: +31.20.5354445 
The Netherlands                   Mobile: +31.6.55861746  
------------------------------------------------------------------------------

As long as you don't tell your friends how I played the hand,
then I won't tell my friends how you defended it.                 (Anonymous)

---

From: Attila Pasztor <[email-masked]>
Date: Tue, 05 Jun 2001 22:09:04 +1000

Henk,

> so if it didn't arrive, it either must have been lost _or_ something is

To do this it is sufficient to know the number of  packets to be sent (the
highest serial number to expect), the schedule is not needed for this purpose.
As I mentioned earlier, if the session start message would include the number of
packets and the duration of the test, both losses could be detected reliably and
receiver time-out could be handled properly.

The case described by Stanislav is also interesting:

> A session that's expected to
> number.

According to the draft the parameters of the retrieve-session command include the
begin and end seq numbers of the requested packets. The draft says " If an
incomplete session is requested, all packets received so far that fall into the
requested range SHOULD be returned.".
In the case described by Stanislav, the server can respond all the requests on
the second day with the so far received 7000 packets and comply 100% with the
draft without requiring the receiver having any information about the send
schedule.
In the case of a complete session, based on the highest serial number all the
losses can be reported.

Attila

---

From: Matthew Roughan <[email-masked]>
Date: Tue, 05 Jun 2001 12:15:24 -0400

> source and the packet-rate, but I don't think we should exlude this

Hi

What about including a max-interval time threshold, either statistical,
or absolute. Rather than specify everything, specify the longest
interval between packets. In many cases, this would not be too large.
Certainly small enough to allow fast detection of the sort of event you
describe. Sending one number is a lot easier than sending a schedule.

Matt

---

From: "Henk Uijterwaal (RIPE-NCC)" <[email-masked]>
Date: Wed, 6 Jun 2001 09:59:09 +0200 (CEST)

> describe. Sending one number is a lot easier than sending a schedule.

That requires a small modification in the scheduling but otherwise would
work, I think.

In the current Poisson process, one can theoretically get an interval
between packets that is infinitely long.  This has to be restricted, (for
example) to 10 times the average interval between packets.  This avoids
that the maximum interval becomes infinitely long but won't distort the
Poisson distribution.

Henk

---

From: Matthew Roughan <[email-masked]>
Date: Wed, 06 Jun 2001 10:30:21 -0400

> that the maximum interval becomes infinitely long but won't distort the

I was thinking that a statistical bound could be set. For instance, the
probability that an interval in a Poisson process is greater than N
times the mean interval is exp(-N), from memory. So set the bound such
that this probability is small relative to the length of measurement to
be performed.

Obviously this would be more difficult to calculate, and might be much
larger for some theoretical processes (multifractals?). However it might
make sense when designing these processes to build in a maximum interval
between packets. If you want to rapidly detect a loss event, this would
be a requirement in any case.

Matt

---

From: stanislav shalunov <[email-masked]>
Date: 06 Jun 2001 10:43:25 -0400

Matthew Roughan <[email-masked]> writes:

> What about including a max-interval time threshold, either
> statistical, or absolute.

This would address one of the problems with receiver not knowing the
schedule I have listed (timely loss detection).

Inability of the receiver to tie loss events to specific times, as
required by the standard remains.  So, you'd need to collect results
both from the sender and from the receiver (which may be operationally
inconvenient--data retention has to be synchronized, you need more
connectivity to fetch results, you need to correlate).

Inability to ask a sender to send you some specific test stream
remains as well.

Democracy is a form of government that substitutes election by the incompetent
many for appointment by the corrupt few.                         -- G. B. Shaw
_______________________________________________
ippm mailing list
[email-masked]
http://mailhost.advanced.org/mailman/listinfo/ippm

---

From: Andy Scherrer <[email-masked]>
Date: Wed, 6 Jun 2001 10:03:08 -0500 (CDT)

> that this probability is small relative to the length of measurement to

The Exponential interpacket times already set a (low) probability on these
very long delays. To modify that, you can simply truncate the distribution
by imposing a max value, or you can combine/condition it with yet another
distribution, so that in effect you have 2 or more different
distributions. E.g., if you generate a delay greater than X, then
regenerate it according to some other dist.

That simply makes the whole task that much more complicated, and remember
that such complication shows up at the other end after it's been further
perturbed by the network (which is what you're actually trying to
measure). 

> be a requirement in any case.

That much sounds reasonable; but it is equivalent to truncation of the
distribution. 

Andy