[Tinyos-devel] Feedback on TEP 124

[Martin Haenggi]

Hi Omprakash

Some further comments inline below.

Best,
Martin

-------

>> Link quality estimates obtained using LEEP are often used as a
>> bootstrapping values in the link quality table;

Typo: as (a) bootstrapping  value(s)
Suggested: are often used to bootstrap the link quality table

>> successfully
>> received packets from A among all the packets transmitted by A.

Note: 'among' sounds a bit awkward. Sentence should be reworded,  
perhaps to:
fraction of successfully received packets.

Section 2.3:

>> 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.

Rewrite: Either insert "is" after "way" or replace "as" by "is" or  
something.

>> 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).

Suggest to rewrite as: "According to this definition, the link quality  
is computed as ..."
However, the step from the definition of link quality as the  
"roundtrip" success
probability to the product of the link qualities is not correct.
As I said earlier, this would only hold if the successes of the two
transmissions were independent, and in most cases they are not. So the  
product
is a pessimistic metric, and I'd prefer to use the minimum of the two  
probabilities.
At least a remark should be included that taking the product is only  
valid assuming
independence (and does not follow directly from the definition above);  
and
perhaps a scenario can be included where independence would be justified
(I can't think if any except some far-fetched ones such as high  
mobility).


On Jan 31, 2009, at 1:49 AM, Omprakash Gnawali wrote:

> 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