[Tinyos-devel] Feedback on TEP 124

[Omprakash Gnawali]

Thanks Martin for your comments. I committed a new version, which is
available here:
http://tinyos.cvs.sourceforge.net/viewvc/tinyos/tinyos-2.x/doc/txt/tep124.txt?revision=1.9&view=markup

Please see my comments inline.

On Fri, Jan 30, 2009 at 3:08 PM, Martin Haenggi <mhaenggi at nd.edu> wrote:
> Hi Omprakash
>
> Here are our (Daniele's, Peter Vizi's, David Tisza's, and mine) fused
> comments on TEP 124.
>
> Best,
> Martin
>
> -----------
> Definition of Link Quality:
>
> 1. In 2.1 you say this is the probability that a packet will be successfully
> transmitted.
> In 2.2 and 2.3, you say it may be based on RSSI and LQI also. This is
> inconsistent.
> I suggest to adopt the general definition but specify that in LEEP, the PRR
> is used
> as the *empirical* probability that a packet will be successfully received.

It is possible some reviewers looked at the TEP from prior to Nov 21.
On that day, I committed changes to the TEP that removes the reference
to LQI and RSSI for the same concern. Here is the updated text:

"In a node pair (A,B), with B as the node of reference, in-bound link
quality is a value in the range of 0 to 255 that describes the quality
of the link from A to B estimated by B by counting the successfully
received packets from A among all the packets transmitted by A. Thus,
in-bound link quality is the empirical probability that a packet will
be successfully received on a given link. A value of 255 represents a
probability of 1 and a value of 0 represents a probability of 0 of
successfully receiving a packet on a given link."

My concern here is we are prescribing how to compute link quality
rather than focusing on how to represent it and exchange it which is
what LEEP is all about.

> 2. Bidirectional link quality. You take the product of the two PRRs and
> explain that
> this definition assumes independent link losses. Well, its a definition, so
> it does not assume anything.
> However, if the product of the link qualities should express the probability
> that a packet can
> be received *and* successfully ACKed, then this is only true if the forward
> and backward
> link are independent. Now, in reality, they're quite likely strongly
> correlated. Now the question
> is if this matters. If the forward transmission is not successful, it does
> not matter. If it is, the
> reverse one will likely be successful as well. Then the bidirectional link
> quality is simply given by the PRR
> (over the forward path). Alternatively, the minimum of the two PRRs could be
> taken, which would
> better account for link asymmetries: For example, if p1=p2=1/2, then the
> expected total number
> of transmissions for successful roundtrip communication is 4, which is lower
> than for p1=1/4 and p2=1,
> yet the product is the same. So your metric does not distinguish the
> symmetric and asymmetric
> cases, but the minimum would, which makes it a better indicator than the
> product in many cases.

In the new text, I made it clear that LEEP is not about a specific way
of computing bi-directional link quality. Here is the new text on
bi-directional link quality:

"2.3 Bi-directional Link Quality
--------------------------------------------------------------------

LEEP does not define or compute bi-directional link quality. LEEP
provides a way to exchange sufficient information to compute in-bound
and out-bound link qualities. These two link qualities can be used to
compute the bi-directional link quality. One popular way to define the
bi-directional link quality between a node pair (A,B) as the
probability that a packet transmitted by A will be successfully
received and acknowledged by B. This approach computes the
bi-directional link quality of a node pair (A,B) as the product of the
link quality of (A,B) and (B,A)."

We can probably even delete everything starting "One popular..."
because that does not describe LEEP. Although, there needs to be some
basic information to clarify why we are talking about in-bound or
out-bound link quality.


> 3. Encoding. The PRR is a real value between 0 and 1. In the TEP it is an
> integer between 0 and
> 255. How is the encoding done? Also there appears to be an inconsistency
> with the interface
> definition, where it is a two-byte value.

Here is an excerpt from the new 2.1:

"A value of 255 represents a
probability of 1 and a value of 0 represents a probability of 0 of
successfully receiving a packet on a given link."

See the comment below about the interface.

> Implementation:
>
> 1. You do not specify the time window over which PRR is averaged. If this
> window
> spans the entire period from the initialization of the network until "now",
> the PRR is a long-term
> average that quite likely has little predictive power over what may happen
> in the near future.
> Or did you implement a finite time window or a "forgetting factor"? Probably
> the latter would
> perform better; you essentially give more weight to more recently
> transmitted packets. This is
> typically done using an exponential. If you have a rough idea about the
> coherence times in
> the network (i.e., the times over which the short-term PRRs remain
> approximately constant),
> you can optimize this forgetting factor to get the most up-to-date PRR
> values.
>
> 2. A suggestion: If there is not enough room to fit all Link Information
> entries: Alternatively to
> the round-robin policy, I could imagine including only the k entries with
> the highest values.
> If a node is well connected, there is probably no reason to use links with
> low PRRs.
>
>
> Minor Remarks:
> - It appears that a detailed description of the LinkEstimator interface is
> missing.
> - What does the estimator do when asked for the link quality to a node that
> is unknown?

These are very good comments on the interface and implementation. We
will definitely keep them in mind when we describe the estimator
implementation or the interface but that will be a topic for a
different TEP. The focus of this TEP is just the protocol to compute
and exchange in-bound link quality and some required background
information (such as definition and representation of link quality). I
hope the first sentence of 2.3 also makes this emphasis clear.


> - Be consistent with "bi-directional" vs. "bidirectional".

I am using bi-directional now.

- om_p