Subject: Re: [manet] [Roll] [roll] #20: Question on Metric ID

From: Omprakash Gnawali <[email-masked]>
Date: Fri, 5 Mar 2010 12:58:33 -0800

On Tue, Mar 2, 2010 at 9:28 PM, MiJeom Kim <[email-masked]> wrote:
> Hi,
>
> It’s time to summarize.
>
> - ETX >= 1, and 100 is enough for Max ETX since more than 10 ETX is
> close to infinity.
> - 8 bits are enough but need to avoid floating point format.  good to
> multiply with a constant factor (C) like 256
>
> I think Henning’s suggestion is good. But we don’t need a big range
> for ETX, but precision needs to be increased. So we can adjust it with
> 5 bit mantissa and 3 bit exponent.
>
> So, we can represent (ETX * C) as (32 + a) * 2^b where 0 <= a <= 31
> and 0 <= b <= 7. If C is 128, the max possible ETX is 63 and if C is
> 64, the max ETX is 126. So let’s try C = 64 and if ETX is bigger than
> 126, we can just make it the possible max which is 126.
>
> All the numbers can be adjustable again, so please settle down the
> issue with your ideas.
>
> I can’t understand the Overloading ETX thing. Nobody suggests
> overloading ETX, I think. What do you mean by that in this thread,
> Omprakash?

It was the suggestion that not all ETX=1 links are the same so we
should leave room in the metric to differentiate preferred ETX=1 link
from the other ETX=1 links. The example that was used was, wired ETX=1
link vs wireless ETX=1 link. If we make minimum ETX value to be 1,
then there is no room for such differentiation based on just the ETX
metric.

- om_p

---

From: Marcello Caleffi <[email-masked]>
Date: Fri, 5 Mar 2010 22:04:55 +0100

If the delivery ratios are correctly estimated, there is no difference among 1ETX links, wired wireless or anything else.
The issue is in correctly estimating the delivery ratios, but this does not need additional bits in the header.

Marcello

Il giorno 05/mar/2010, alle ore 21.58, Omprakash Gnawali ha scritto:

> _______________________________________________
> manet mailing list
> [email-masked]
> https://www.ietf.org/mailman/listinfo/manet

---

From: David Young <[email-masked]>
Date: Fri, 5 Mar 2010 16:31:13 -0600

On Fri, Mar 05, 2010 at 10:04:55PM +0100, Marcello Caleffi wrote:
> If the delivery ratios are correctly estimated, there is no difference
> among 1ETX links, wired wireless or anything else.  The issue is in
> correctly estimating the delivery ratios, but this does not need
> additional bits in the header.

Maybe I have misunderstood what you have said, but can't we think of
several circumstances where two 1-ETX links are different from each
other, especially when different media are involved, or when we consider
the fan-out effects on the network of choosing some 1-ETX link over
another.  I will give some examples.

One 1-ETX link may be on a full-duplex channel (e.g., 10baseT ethernet),
and a second 1-ETX link, on a half-duplex channel (e.g.,  802.11).
Transmitting on the half-duplex link precludes simultaneously receiving
on the same channel; it may be less preferable to use it than to use the
full-duplex alternate link.

Transmissions on either of two 1-ETX links may interfere with more than
one receiver because they are broadcast.  Broadcast transmissions on one
1-ETX link may interfere with fewer receivers than on a second link.

A transmission on a point-to-point link such as a Digital Subscriber
Line may cause no interference.

Two 1-ETX links may operate at different bit rates (1 Mbps v. 11 Mbps
v. 270 Mbps) and with different overhead (short v. long preamble, CTS
protection, RTS/CTS protection).

Two 1-ETX links may be alike except that they use two different
channels, A and B.  A router may reduce intra-flow interference by
forwarding on channel B any packet that it has receivedon channel A.

Finally, pardon the digression, but two n-ETX, multihop paths can
differ from each other in many ways.  Hopcount comes to mind.

Dave

-- 
David Young             OJC Technologies
[email-masked]      Urbana, IL * (217) 278-3933

---

From: Matteo Paris <[email-masked]>
Date: Mon, 8 Mar 2010 09:40:34 -0500

I'd prefer using a 16-bit fixed point value for ETX, with 4 bits of 
fractional part.  It's very simple, and easily covers the desirable 
ranges.

I don't think the ETX value field is the right place to try to save 
one byte.  If we need to shave bytes, there are other good 
candidates.  For example we could reduce the length fields of DIO 
suboptions and routing metric common headers from 2 bytes to 1 byte. 
We could also eliminate the byte of flags from the routing metric 
common header since that information is redundant if you know the 
Objective Function, and unused if you don't.

Matteo

At 10:38 AM +0900 3/8/10, MiJeom Kim wrote:
>Thank you for clearing the issue.
>
>So, we don't need the overloading ETX, then.
>How do you think about my suggestion:
>
>we can represent (ETX * C) as (32 + a) * 2^b where 0 <= a <= 31 and 0
><= b <= 7. If C is 128, the max possible ETX is 63 and if C is 64, the
>max ETX is 126. So let's try C = 64 and if ETX is bigger than 126, we
>can just make it the possible max which is 126.
>
>Other better ideas?
>let's close the ticket soon.
>
>Mijeom.
>
>
>On Sat, Mar 6, 2010 at 6:04 AM, Marcello Caleffi
><[email-masked]> wrote:
>>  If the delivery ratios are correctly estimated, there is no 
>>difference among 1ETX links, wired wireless or anything else.
>>  The issue is in correctly estimating the delivery ratios, but this 
>>does not need additional bits in the header.
>>
>>  Marcello
>>
>>
>>>>  It's time to summarize.
>>>>  - 8 bits are enough but need to avoid floating point format. ? good to
>>>>  I think Henning's suggestion is good. But we don't need a big range
>>>>  64, the max ETX is 126. So let's try C = 64 and if ETX is bigger than
>>>>  I can't understand the Overloading ETX thing. Nobody suggests
>Roll mailing list
>[email-masked]
>https://www.ietf.org/mailman/listinfo/roll

---

From: "Ramrekha, Arvind" <[email-masked]>
Date: Wed, 10 Mar 2010 02:36:53 +0000

I understand that the ETX value of a link A<=>B,depends on the product of the loss rates R_etx*D_etx. And the path ETX value is the summation of ETX for participating links:

Which path SHOULD a source node choose if two paths have the same ETX values?

Is successful packet delivery the right metric to be used to estimate the "link quality" and consequently route quality? What about other route quality metrics such as delay, jitter and throughput?    

Can we access any of the results for ETX metric implementation in the Funkfeuer network and the scenario under which it was tested (could help for future experimentations)?

Regards

Arvind.

________________________________________
From: [email-masked] [[email-masked]] On Behalf Of Matteo Paris [[email-masked]]
Sent: 08 March 2010 14:40
To: [email-masked]
Cc: manet
Subject: Re: [manet] [Roll]   [roll] #20: Question on Metric ID

Matteo

This email has been scanned for all viruses by the MessageLabs Email
Security System.

This email has been scanned for all viruses by the MessageLabs Email
Security System.

---

From: Henning Rogge <[email-masked]>
Date: Wed, 10 Mar 2010 16:00:49 +0100

Am Mittwoch 10 März 2010 03:36:53 schrieb Ramrekha, Arvind:
> I understand that the ETX value of a link A<=>B,depends on the product of
> the loss rates R_etx*D_etx. And the path ETX value is the summation of ETX
> for participating links:
> 
I think the dijkstra algorthm should have a "tie breaker" for paths with the 
same metric cost. One way would be to choose the path with the next hop has 
the "lowest" IP. Just to make sure that the algorithm does not begin to switch 
between both paths constantly.

> Is successful packet delivery the right metric to be used to estimate the
> "link quality" and consequently route quality?
It works... and it's much better than hopcount.

> What about other route quality metrics such as delay, jitter and throughput?
ETX is the "most simple" metric that seem to work. There are better ones, but 
most of them are more difficult to implement. I'm looking forward to see more 
metric drafts.
 
> Can we access any of the results for ETX metric implementation in the
> Funkfeuer network
You will find the complete sourcecode in our repository at http://olsr.org/git

> and the scenario under which it was tested (could help for future
> experimentations)?
The funkfeuer network (and the Freifunk networks) are real world community 
networks used by people to share internet access. So the metric to measure 
success is something like "amount of complains you receive about the network". 
We can say ETX works because hundreds of people get their internet to OLSR(v1) 
based networks with ETX as a routing metric.

Henning Rogge

---

From: "Ramrekha, Arvind" <[email-masked]>
Date: Wed, 10 Mar 2010 22:59:07 +0000

However, this tie breaker with "lowest" IP would not give us any added advantage apart from being a tie breaker? Maybe we could use a more "useful" metric such as battery level of the node for the next hop or such metrics.

>>It works... and it's much better than hopcount.

I understand that this could be used in OLSRv2.

Is the problem of hop count applicable to DYMO where RREP is unicast along a route of lowest hop count (through which RREQ is first received, am I right?)?   

>>>You will find the complete sourcecode in our repository at http://olsr.org/git

I will have a look.

Do people use streaming multimedia content from the internet and do they move around or is it more like a mesh architecture?

Thanks

Arvind
________________________________________
From: Henning Rogge [[email-masked]]
Sent: 10 March 2010 15:00
To: Ramrekha, Arvind; manet
Subject: Re: [manet] [Roll]   [roll] #20: Question on Metric ID

Henning Rogge

---

From: Henning Rogge <[email-masked]>
Date: Thu, 11 Mar 2010 16:20:13 +0100

Am Mittwoch 10 März 2010 23:59:07 schrieb Ramrekha, Arvind:
> > I think the dijkstra algorthm should have a "tie breaker" for paths with
> > the same metric cost. One way would be to choose the path with the next
> > hop has the "lowest" IP. Just to make sure that the algorithm does not
> > begin to switch between both paths constantly.
> 
> However, this tie breaker with "lowest" IP would not give us any added
> advantage apart from being a tie breaker? Maybe we could use a more
> "useful" metric such as battery level of the node for the next hop or such
> metrics.
The tie breaker should only apply if both routes have the same path cost. If 
you include battery level into the metric and both routes have different 
battery levels, they have a different path cost and the tie breaker does not 
apply.

The tie breaker is needed because without a tie breaker you can get a 
fluctuating route in a totally stable topology (without the tie breaker you 
cannot define a strict order on the path costs).

> Is the problem of hop count applicable to DYMO where RREP is unicast along
> a route of lowest hop count (through which RREQ is first received, am I
> right?)?
In AODV/DYMO the loss rate of the link prevents routes over lot's of high-loss 
rate links (at least on a long time average), because the route responses are 
just lost most times.
 
> > The funkfeuer network (and the Freifunk networks) are real world
> > community networks used by people to share internet access. So the metric
> > to measure success is something like "amount of complains you receive
> > about the network". We can say ETX works because hundreds of people get
> > their internet to OLSR(v1) based networks with ETX as a routing metric.
> 
> Do people use streaming multimedia content from the internet and do they
> move around or is it more like a mesh architecture?
I have done a skype video connection to people in the Berlin and Vienna meshs.

But most/all Freifunk/Funkfeuer networks are immobile meshs. We have done 
experiments with mobile meshs and ETX at work, but not on the scale as 
Freifunk/Funkfeuer.

Henning Rogge

---

From: "Ramrekha, Arvind" <[email-masked]>
Date: Thu, 11 Mar 2010 23:50:30 +0000

If path costs in terms of ETX are equal (equal packet loss expected in 2 paths), the battery power of the next hop nodes (whole paths?) for such paths could be used as the tie breaker?

Arvind.
________________________________________
From: Henning Rogge [[email-masked]]
Sent: 11 March 2010 15:20
To: Ramrekha, Arvind
Cc: manet
Subject: Re: [manet] [Roll]   [roll] #20: Question on Metric ID

Henning Rogge

---

From: Henning Rogge <[email-masked]>
Date: Fri, 12 Mar 2010 07:42:39 +0100

On Fri March 12 2010 00:50:30 Ramrekha, Arvind wrote:
> > The tie breaker should only apply if both routes have the same path
> > cost. If you include battery level into the metric and both routes have
> > different battery levels, they have a different path cost and the tie
> > breaker does not apply.
> 
> If path costs in terms of ETX are equal (equal packet loss expected in 2
> paths), the battery power of the next hop nodes (whole paths?) for such
> paths could be used as the tie breaker?
I'm not sure this is a good idea to us only the next hop, better integrate the 
battery levels of all nodes on the path into the cost and use this as a 
combined metric.

If this metrics needs a tiebreaker, use the IP.

Henning Rogge

-- 
Diplom-Informatiker Henning Rogge , Fraunhofer-Institut für
Kommunikation, Informationsverarbeitung und Ergonomie FKIE
Kommunikationssysteme (KOM)
Neuenahrer Straße 20, 53343 Wachtberg, Germany
Telefon +49 228 9435-263,   Fax +49 228 9435 685
mailto:[email-masked] http://www.fkie.fraunhofer.de
GPG: E1C6 0914 490B 3909 D944 F80D 4487 C67C 55EC CFE0