Subject: Re: [Roll] RPL: why not base a DAG on the min hop distance from theroot?

From: Mukul Goyal <[email-masked]>
Date: Wed, 1 Jul 2009 23:22:14 -0500 (CDT)

It is possible that I will be surprised.

But I will be really surprised if people dont care about how many hops their packets travel before they reach the root.

Thanks
Mukul

----- Original Message -----
From: "Jonathan Hui" <[email-masked]>
To: "Mukul Goyal" <[email-masked]>
Cc: "Philip Levis" <[email-masked]>, "roll" <[email-masked]>, "Omprakash Gnawali" <[email-masked]>
Sent: Wednesday, July 1, 2009 11:13:21 PM GMT -06:00 US/Canada Central
Subject: Re: [Roll] RPL: why not base a DAG on the min hop distance from theroot?

On Jul 1, 2009, at 9:11 PM, Mukul Goyal wrote:
> I am still waiting for a strong argument in favor of parents at  
> multiple depths. I have provided one in favor of same depth parents  
> - it makes the term "depth" meaningful as the number of hops the  
> packet would travel to reach the root.

But depth is often not what we really care about... ETX is just one  
example.

--
Jonathan Hui

---

From: Jonathan Hui <[email-masked]>
Date: Wed, 1 Jul 2009 21:27:48 -0700

On Jul 1, 2009, at 9:22 PM, Mukul Goyal wrote:

> But I will be really surprised if people dont care about how many  
> hops their packets travel before they reach the root.

Hops is often a factor, but I'd argue that hops alone does not lend  
itself to building robust networking. ETX, for example, reduces to  
hops when link success rates are 100% for all links. But we know link  
success rates are never 100%, hence the lossy. On lossy links, the  
number of transmissions is much more important than the number of hops  
- it is a much better indicator of end-to-end communication delay,  
channel utilization, energy consumption, etc.

--
Jonathan Hui

---

From: Richard Kelsey <[email-masked]>
Date: Thu, 02 Jul 2009 10:33:26 -0400

Date: Wed, 1 Jul 2009 23:22:14 -0500 (CDT)
   From: Mukul Goyal <[email-masked]>

I do not care how many hops packets travel to reach the
root.  I have worked on two ROLL-style protocols that have
seen years of successful commercial use.  Neither of them
uses hop count in determining routes.  Different hops are
different enough in their properties that there is little
value in a metric that considers them all equal.

Hop count may be useful for routing, but it certainly isn't
essential.
                              -Richard Kelsey

---

From: Alexandru Petrescu <[email-masked]>
Date: Thu, 02 Jul 2009 16:52:07 +0200

> Hop count may be useful for routing, but it certainly isn't

A metric is what helps a distributed algorithm to build loop-free short 
paths through a graph, especially make independent nodes to have 
precisely the same view of that network.

This is of paramount importance when the network is large and dynamic, 
where humans can't possibly understand it.

Not using metrics can be useful if the network is small, and mostly 
static, and a few humans manage it, I agree.

I am not sure what is the situation with the ROLL networks, how large 
are they, and how much connected to the Internet are they.

Alex

>                               -Richard Kelsey
> _______________________________________________
> Roll mailing list
> [email-masked]
> https://www.ietf.org/mailman/listinfo/roll
>

---

From: JP Vasseur <[email-masked]>
Date: Thu, 2 Jul 2009 16:54:58 +0200

> value in a metric that considers them all equal.

Fully agree. There are cases where indeed this might be of interest  
(for example
when node may add jitter because of queueing delays) but this is not  
one of many
factors.

---

From: Jonathan Hui <[email-masked]>
Date: Thu, 2 Jul 2009 07:55:18 -0700

On Jul 2, 2009, at 7:52 AM, Alexandru Petrescu wrote:

> A metric is what helps a distributed algorithm to build loop-free  
> short paths through a graph, especially make independent nodes to  
> have precisely the same view of that network.
>
> This is of paramount importance when the network is large and  
> dynamic, where humans can't possibly understand it.
>
> I am not sure what is the situation with the ROLL networks, how  
> large are they, and how much connected to the Internet are they.

Richard wasn't arguing for no metrics at all - just that hop count as  
a metric wasn't very useful to him.

--
Jonathan Hui

---

From: JP Vasseur <[email-masked]>
Date: Thu, 2 Jul 2009 16:56:10 +0200

> static, and a few humans manage it, I agree.

I do not think Richard is suggesting not to use metrics ...

---

From: Richard Kelsey <[email-masked]>
Date: Thu, 02 Jul 2009 11:21:59 -0400

Date: Thu, 02 Jul 2009 16:52:07 +0200
   From: Alexandru Petrescu <[email-masked]>

We use metrics, but hop count is not one of them.  The
networks are up to several thousand nodes in size and have
little or no human management.  The nodes use 802.15.4
radios and the links are quite dynamic, even for those nodes
that have static locations.
                                  -Richard Kelsey

---

From: Alexandru Petrescu <[email-masked]>
Date: Thu, 02 Jul 2009 17:31:27 +0200

> that have static locations.

Hmmm... does it have a notion of universal reachability, like any node 
must reach any other node at any time?

Alex

---

From: [email-masked]
Date: Thu, 2 Jul 2009 10:48:01 -0500

Using low data rate 802.15.4 radios
in commercial buildings we design our deployments

to minimize hops and that has
been an essential part of the success of our networks. The result of

excessive hops is higher latency and
higher probability of collisions which leads to devices timing out and
going

offline. This is an essential customer
requirement for us.  We also have data showing that when you do over
the air downloads,

minimizing hops is key to meeting our
timing requirements.

Regards,

Yusuf

From:

Richard Kelsey <[email-masked]>

To:

Mukul Goyal <[email-masked]>

Cc:

[email-masked], [email-masked]

Date:

07/02/2009 09:37 AM

Subject:

Re: [Roll] RPL: why not base a DAG on
the min hop distance from theroot?

Date: Wed, 1 Jul 2009 23:22:14 -0500
(CDT)

essential.

-Richard Kelsey

Roll mailing list

[email-masked]

---

From: Jonathan Hui <[email-masked]>
Date: Thu, 2 Jul 2009 09:27:35 -0700

On Jul 2, 2009, at 8:48 AM, [email-masked] wrote:
>
> Using low data rate 802.15.4 radios in commercial buildings we  
> design our deployments
>  to minimize hops and that has been an essential part of the success  
> of our networks. The result of
> excessive hops is higher latency and higher probability of  
> collisions which leads to devices timing out and going
> offline. This is an essential customer requirement for us.  We also  
> have data showing that when you do over the air downloads,
> minimizing hops is key to meeting our timing requirements.

But would you agree that minimizing the number of transmissions on a  
path is a better metric than hops in your case?

--
Jonathan Hui

---

From: Richard Kelsey <[email-masked]>
Date: Thu, 02 Jul 2009 15:41:28 -0400

Date: Thu, 02 Jul 2009 17:31:27 +0200
   From: Alexandru Petrescu <[email-masked]>

   > that have static locations.

   Hmmm... does it have a notion of universal reachability, like any
   node must reach any other node at any time?

Yes and no.  Any node can reach any other node at any time,
as long as only a few nodes actually try to do so.  The
network has only a small, fixed bandwidth available for
arbitrary any-to-any messages.  For the relevent
applications, traffic is mostly many-to-one or one-to-many,
and often there is some degree of locality as well.

Why do you ask?
                             -Richard Kelsey

---

From: "Don Sturek" <[email-masked]>
Date: Thu, 2 Jul 2009 12:51:22 -0700

Hi Jonathan,

I think the example Yusuf may be referring to involves data link level
security where packets are encrypted/decrypted hop by hop (please correct me
if I am wrong).  In that scenario, it is good to minimize the number of hops
(within reason of course).  If that involves a few extra re-transmissions
then you probably still end up with a more efficient packet delivery from a
latency point of view.

Don

-----Original Message-----
From: [email-masked] [mailto:[email-masked]] On Behalf Of
Jonathan Hui
Sent: Thursday, July 02, 2009 9:28 AM
To: [email-masked]
Cc: [email-masked]; [email-masked]; [email-masked]
Subject: Re: [Roll] RPL: why not base a DAG on the min hop distance from
theroot?

--
Jonathan Hui

---

From: JP Vasseur <[email-masked]>
Date: Thu, 2 Jul 2009 22:01:24 +0200

Hi Don,

I think that we are on the same page here: the number of hops should  
not be *the* only metric but *could* be a metric.

Agree ?

Thanks.

JP.

---

From: "Don Sturek" <[email-masked]>
Date: Thu, 2 Jul 2009 13:05:54 -0700

Hi JP,

Absolutely correct.  Number of hops is not *the* metric.  It just cannot be
completely ignored and in some cases (like the data link security example)
it does have a direct affect on latency.

Don

-----Original Message-----
From: JP Vasseur [mailto:[email-masked]] 
Sent: Thursday, July 02, 2009 1:01 PM
To: [email-masked]
Cc: 'Jonathan Hui'; [email-masked]; [email-masked];
[email-masked]; [email-masked]
Subject: Re: [Roll] RPL: why not base a DAG on the min hop distance from
theroot?

Hi Don,

Agree ?

Thanks.

JP.

---

From: [email-masked]
Date: Thu, 2 Jul 2009 15:22:04 -0500

Hi JP and Don,

You are both correct. The number of
hops should be one of the metrics not "the metric".

Regards,

Yusuf

From:

"Don Sturek" <[email-masked]>

To:

"'JP Vasseur'" <[email-masked]>

Cc:

[email-masked], [email-masked], [email-masked],
[email-masked]

Date:

07/02/2009 03:12 PM

Subject:

Re: [Roll] RPL: why not base a DAG on
the min hop distance        from
theroot?

Hi JP,

Absolutely correct.  Number of hops is not *the* metric.  It
just cannot be

Don

-----Original Message-----

To: [email-masked]

theroot?

Hi Don,

Agree ?

Thanks.

JP.

> security where packets are encrypted/decrypted hop by hop (please

> correct me

> if I am wrong).  In that scenario, it is good to minimize the
number

> of hops

> (within reason of course).  If that involves a few extra re-

> transmissions

> then you probably still end up with a more efficient packet delivery

> from a

> From: [email-masked] [mailto:[email-masked]]
On Behalf

> Of

> Subject: Re: [Roll] RPL: why not base a DAG on the min hop distance

> from

Roll mailing list

[email-masked]

---

From: Alexandru Petrescu <[email-masked]>
Date: Thu, 02 Jul 2009 22:35:42 +0200

JP - what is a metric?

I consider the depth used by the DAG to be a metric - a hop count 
metric.  When a node joins a DAG below a certain depth, it is using a 
metric: the number of hops between self and topmost node (LBR, DAG Root).

As it stands now, the hopcount is _the_ metric of RPL.

Alex

JP Vasseur a écrit :
> Hi Don,
> 
> I think that we are on the same page here: the number of hops should not 
> be *the* only metric but *could* be a metric.
> 
> Agree ?
> 
> Thanks.
> 
> JP.
>

---

From: [email-masked]
Date: Thu, 2 Jul 2009 15:44:59 -0500

I agree that hops may not be the do all and end all.  Maybe overall 
transmissions (e.g. ETRX) is a better primitive metric.  We'll work this 
out. 

However, it's also important that nodes can talk directly to other nodes 
within the LLN for fault tolerance purposes.  We don't want to force 
communication up through the DAG when the destination is in the LLN; 
especially if the destination is within direct radio range as the source. 
Moving data up and back down the DAG only makes higher layer nodes more 
critical to system operation than others.

So when some of us talk about reducing hops, it's not only to reduce 
latency but also to increase redundancy and fault tolerance of the overall 
LLN.

Jerry

"Don Sturek" <[email-masked]> 
Sent by: [email-masked]
07/02/2009 03:12 PM
Please respond to
[email-masked]

To
"'JP Vasseur'" <[email-masked]>
cc
[email-masked], [email-masked], [email-masked], 
[email-masked]
Subject
Re: [Roll] RPL: why not base a DAG on the min hop distance      from 
theroot?

Hi JP,

Absolutely correct.  Number of hops is not *the* metric.  It just cannot 
be
completely ignored and in some cases (like the data link security example)
it does have a direct affect on latency.

Don

-----Original Message-----
From: JP Vasseur [mailto:[email-masked]] 
Sent: Thursday, July 02, 2009 1:01 PM
To: [email-masked]
Cc: 'Jonathan Hui'; [email-masked]; [email-masked];

Hi Don,

Agree ?

Thanks.

JP.

---

From: Jonathan Hui <[email-masked]>
Date: Thu, 2 Jul 2009 14:21:36 -0700

Agree with you and JP that hop count could be a metric. But lumping  
the cost of encryption/decryption into hop count doesn't seem like the  
right approach to me...

Just for my information, what is the cost of encryption/decryption? I  
tend to view retransmissions as fairly costly operations in terms of  
energy and latency, so it help me to know the relative cost between  
different operations.

--
Jonathan Hui

---

From: Alexandru Petrescu <[email-masked]>
Date: Thu, 02 Jul 2009 23:28:53 +0200

[email-masked] a écrit :
> especially if the destination is within direct radio range as the 
> source.  Moving data up and back down the DAG only makes higher layer 
> nodes more critical to system operation than others.

I fully agree it's also important nodes to talk directly to each other, 
not necessarily up through the LBR (sink, DAG root).

Alex

> latency but also to increase redundancy and fault tolerance of the 
> overall LLN.
> 
> Jerry
> 
> 
> 
> 
> *"Don Sturek" <[email-masked]>*
> ------------------------------------------------------------------------
>

---

From: "Don Sturek" <[email-masked]>
Date: Thu, 2 Jul 2009 14:37:27 -0700

Hi Jonathan,

I did not mean to lump encryption/decryption with the hop count discussion
for routing metrics, only cite it as an example where hop count matters.
Clearly the encryption/decryption cited in the example is a layer 2 issue.

For our application, when we use data link security and encrypt/decrypt per
hop, we use AES-128 encryption/decryption for each neighbor transmission
(this was using IEEE 802.15.4-2003 with data link security applied above the
MAC).  I think if you turn on IEEE 802.15.4-2006 MAC security you get the
same hop by hop encryption/decryption (maybe someone can correct me if I am
wrong on this).  I believe the encrypt/decrypt operation per hop is on the
order of 10s of milliseconds (which is why this makes hop count relevant).

As noted in several places, hop count is not the only consideration as a
routing metric.  I just wanted to point out (and I think others with
experience using data link security like this as well) that hop count does
matter in some routing situations.

Don

-----Original Message-----
From: Jonathan Hui [mailto:[email-masked]] 
Sent: Thursday, July 02, 2009 2:22 PM
To: [email-masked]
Cc: [email-masked]; [email-masked]; [email-masked];
[email-masked]

--
Jonathan Hui

---

From: Jonathan Hui <[email-masked]>
Date: Thu, 2 Jul 2009 14:44:33 -0700

Hi Don,

> order of 10s of milliseconds (which is why this makes hop count  

Is this assuming a software implementation of security? 10s of  
milliseconds is quite a lot. Utilizing hardware encryption engines  
built into many 802.15.4 radios/SoCs we typically achieve encryption/ 
decryption times better than a few hundred microseconds. Or is there  
something else I am missing?

> matter in some routing situations.

Agree.

--
Jonathan Hui

---

From: "Don Sturek" <[email-masked]>
Date: Thu, 2 Jul 2009 14:50:06 -0700

Hi Jonathan,

We actually saw such long latencies (10s of milliseconds) even for AES-128
engines built in hardware.  It was actually quite surprising.  We even
measured with multiple vendors just to see if we might be dealing with an
implementation issue.

Don

-----Original Message-----
From: Jonathan Hui [mailto:[email-masked]] 
Sent: Thursday, July 02, 2009 2:45 PM
To: [email-masked]
Cc: [email-masked]; [email-masked]; [email-masked];
[email-masked]

Hi Don,

Agree.

--
Jonathan Hui

---

From: Jonathan Hui <[email-masked]>
Date: Thu, 2 Jul 2009 14:55:16 -0700

> measured with multiple vendors just to see if we might be dealing  

That's certainly interesting to me. Care to share which ones? :-)

The CC2420 datasheet claims 222us with I(a) = 50, I(m) = 69, and  
I(MIC) = 8. Even if you took the worst-case values for each, you  
wouldn't get anywhere near 10s of milliseconds. Our implementation  
does not show any discrepancy with the quoted timing numbers.

--
Jonathan Hui

---

From: "Don Sturek" <[email-masked]>
Date: Thu, 2 Jul 2009 14:56:41 -0700

By the way, for the numbers I was citing, here was the processing:
1)  Receive message from your neighbor, decrypt (AES-128 with 32 bit MIC)
2)  Perform network layer processing on the packet, determine next neighbor
to send it to
3)  Encrypt message for transmission to next neighbor (AES-128 with 32 bit
MIC).

In our case, there was a need in performing the above processing at each hop
(including validating the MIC from your upstream neighbor and creating a new
MIC for your downstream neighbor).

Don

-----Original Message-----
From: Don Sturek [mailto:[email-masked]] 
Sent: Thursday, July 02, 2009 2:50 PM
To: 'Jonathan Hui'
Cc: [email-masked]'; [email-masked]'; [email-masked]';
[email-masked]'
Subject: RE: [Roll] RPL: why not base a DAG on the min hop distance from
theroot?

Hi Jonathan,

Don

-----Original Message-----
From: Jonathan Hui [mailto:[email-masked]] 
Sent: Thursday, July 02, 2009 2:45 PM
To: [email-masked]
Cc: [email-masked]; [email-masked]; [email-masked];
[email-masked]

Hi Don,

Agree.

--
Jonathan Hui

---

From: Jonathan Hui <[email-masked]>
Date: Thu, 2 Jul 2009 15:03:54 -0700

Hi Don,

> MIC for your downstream neighbor).

Have you profiled the relative cost of 1, 2, and 3? From my  
experience, I'd guess the vast majority of your time is spent in 2. If  
that is the case, then minimizing hops doesn't do much if you want to  
allow for next-hop lookups for each (re)transmission. There seems to  
be consensus within this working group that allowing next-hop lookups  
when performing retransmissions (at least a subset of them) is a  
useful thing.

--
Jonathan Hui

---

From: "Don Sturek" <[email-masked]>
Date: Thu, 2 Jul 2009 15:11:52 -0700

Hi Jonathan,

For the next generation Smart Metering application it would be nice to use
some network layer security which can be deployed over IEEE 802.15.4-2006
and allowed us to turn off data link layer security.  I think the hop count
issue may go away if we had such a solution (back to your original DT
assumptions then.....)

Don

-----Original Message-----
From: Jonathan Hui [mailto:[email-masked]] 
Sent: Thursday, July 02, 2009 3:04 PM
To: [email-masked]
Cc: [email-masked]; [email-masked]; [email-masked];
[email-masked]

Hi Don,

--
Jonathan Hui

---

From: Mukul Goyal <[email-masked]>
Date: Thu, 2 Jul 2009 17:25:12 -0500 (CDT)

Jerry has raised a very important question. RPL supports only tree-based routing. Do we need a _plugin_ to support P2P routing?

Mukul
----- Original Message -----
From: "Jerald P Martocci" <[email-masked]>
To: "d sturek" <[email-masked]>
Cc: [email-masked], [email-masked], "Yusuf Bashir" <[email-masked]>, [email-masked]
Sent: Thursday, July 2, 2009 3:44:59 PM GMT -06:00 US/Canada Central
Subject: Re: [Roll] RPL: why not base a DAG on the min hop distance	from	theroot?

I agree that hops may not be the do all and end all.  Maybe overall transmissions (e.g. ETRX) is a better primitive metric.  We'll work this out. 

However, it's also important that nodes can talk directly to other nodes within the LLN for fault tolerance purposes.  We don't want to force communication up through the DAG when the destination is in the LLN; especially if the destination is within direct radio range as the source.  Moving data up and back down the DAG only makes higher layer nodes more critical to system operation than others. 

So when some of us talk about reducing hops, it's not only to reduce latency but also to increase redundancy and fault tolerance of the overall LLN. 

Jerry 

07/02/2009 03:12 PM 
Please respond to 
[email-masked] 
	
To 	"'JP Vasseur'" <[email-masked]> 

cc 	[email-masked], [email-masked], [email-masked], [email-masked] 

Subject 	Re: [Roll] RPL: why not base a DAG on the min hop distance        from        theroot? 

Hi JP, 

Don 

-----Original Message----- 
From: JP Vasseur [mailto:[email-masked]] 
Sent: Thursday, July 02, 2009 1:01 PM 
To: [email-masked] 
Cc: 'Jonathan Hui'; [email-masked]; [email-masked]; 

Hi Don, 

Agree ? 

Thanks. 

JP.

---

From: "Pascal Thubert (pthubert)" <[email-masked]>
Date: Fri, 3 Jul 2009 08:24:32 +0200

Hi:

Actually the draft recognizes that there are tons of metrics and then
algorithms to sort out those metrics.

The draft also recognizes that the perfect one-fit-it-all scalar metric
for all is an illusion amongst a number of other illusions, I'm sure
I'll have ample chances to come back to those.

The net result is that RPL extracts the metrics and their handling in a
specific component that selects a (set of) preferred  parent(s). That
component will vary. From use case to use case. From device generation
to the next.

The draft focuses on the generic operations that happen after the
preferred parent(s?) is selected. The draft then proposes a number of
simple laws to organize the society of machines with different and
somewhat conflicting objective. 

The 'depth' metric is the lingua franca that the draft requires to
enable comparison between nodes and establish a graph with the required
properties of loop avoidance and stability (we're doing a routing
protocol) while optimizing the desired property multiple feasible
successors for all (that's one of the LLN specific things).

That 'depth' must have a number of properties. It MUST be:

-          Scalar for simple comparison

-          Strictly monotonous to orient the parent links and sort out
siblings

-          Universal thus very abstract

-          Coarse grained to enable multiple parents and siblings

-          Constrained in range to count rapidly to infinity if that can
happen in the protocol

So it DOES NOT have to be a simple increment by one. Expected
Transmission Count is certainly a better approximation of what's needed
in a radio mesh and is widely used there. The only trouble with pure ETX
is that is makes a lot less sense in wired environment.

My sense is that we should abstract something that could be implemented
by ETX - or something else - by the node to characterize its hop to
parent. That value would be a scalar link rate, like 1, best can do for
that type of link, to 8 for the worst acceptable for that type of link.
This abstraction fits the MUSTs of the depth and can be derived from an
ETX.

Pascal

From: [email-masked] [mailto:[email-masked]] On Behalf Of
[email-masked]
Sent: jeudi 2 juillet 2009 22:22
To: [email-masked]
Cc: [email-masked]; [email-masked]; [email-masked]
Subject: Re: [Roll] RPL: why not base a DAG on the min hopdistance from
theroot?

Hi JP and Don, 
You are both correct. The number of hops should be one of the metrics
not "the metric". 

Regards, 
Yusuf 

From: 

To: 

Cc: 

Date: 

07/02/2009 03:12 PM 

Subject: 

________________________________

Hi JP,

Absolutely correct.  Number of hops is not *the* metric.  It just cannot
be
completely ignored and in some cases (like the data link security
example)
it does have a direct affect on latency.

Don

-----Original Message-----
From: JP Vasseur [mailto:[email-masked] <mailto:[email-masked]>
] 

Hi Don,

Agree ?

Thanks.

JP.

On Jul 2, 2009, at 9:51 PM, Don Sturek wrote:

> From: [email-masked] [mailto:[email-masked]
<mailto:[email-masked]> ] On Behalf  
> path is a better metric than hops in your case?
<https://www.ietf.org/mailman/listinfo/roll> 
<https://www.ietf.org/mailman/listinfo/roll> 

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

---

From: JP Vasseur <[email-masked]>
Date: Fri, 3 Jul 2009 08:56:08 +0200

On Jul 2, 2009, at 10:35 PM, Alexandru Petrescu wrote:

> metric.  When a node joins a DAG below a certain depth, it is using  
> a metric: the number of hops between self and topmost node (LBR, DAG  
> Root).
>

You can use another metric than the hop count, which is then used to  
avoid loops.

Cheers.

JP.

>
> Alex
>
> JP Vasseur a écrit :
>> Hi Don,
>> I think that we are on the same page here: the number of hops  
>> should not be *the* only metric but *could* be a metric.
>> Agree ?
>> Thanks.
>> JP.
>>> number of hops

---

From: Alexandru Petrescu <[email-masked]>
Date: Fri, 03 Jul 2009 10:50:10 +0200

JP Vasseur a écrit :
>> a metric: the number of hops between self and topmost node (LBR,
>> DAG Root).
>> 

Hmm... I can't see a loop in terms of an energy metric, so I can't see
how an energy metric solely would help avoid building loops.

A loop-free path with a finite number of hops could be a loop path in
terms of energy needed, if one of the links requires a huge amount of
energy to send the packet (larger than the max bit encoded value).

    20 nJ       2^20 J
0-----------0---------0

It is obvious what a loop means in terms of hop count, but unclear what
a loop means in terms of other metrics, and even less clear in terms of
a combination of metrics.

Alex

---

From: JP Vasseur <[email-masked]>
Date: Fri, 3 Jul 2009 10:52:06 +0200

the concept of loop is not related to the metric used to compute the  
path

JP.

---

From: Alexandru Petrescu <[email-masked]>
Date: Fri, 03 Jul 2009 10:54:46 +0200

>  algorithms to sort out those metrics.

In the section where it lists other metrics it doesn't list the hopcount
metric, which is the most widely used.

> 4.1.  Routing Metrics
> 
> Routing metrics are used by the routing protocol to compute the 
> shortest path according to one of more defined metrics.  IGPs such as
>  IS-IS ([RFC5120]) and OSPF ([RFC4915]) compute the shortest path 
> according to a Link State Data Base (LSDB) using link metrics 
> configured by the network administrator.  Such metrics can represent 
> the link bandwidth (in which case the metric is usually inversely 
> proportional to the bandwidth), delay, etc.  Note that in some cases 
> the metric is a polynomial function of several metrics defining 
> different link characteristics.  The resulting shortest path cost is 
> equal to the sum (or multiplication) of the link metrics along the 
> path: such metrics are said to be additive or multiplicative metrics.
>  Some routing protocols support more than one metric: in the vast 
> majority of the cases, one metric is used per (sub)topology.  Less 
> often, a second metric may be used as a tie breaker in the presence 
> of ECMP (Equal Cost Multiple Paths).  The optimization of multiple 
> metrics is known as an NP complete problem and is sometimes supported
>  by some centralized path computation engine.

This paragraph should say which is the most used metric.  That is from
RIP, OSPF and BGP.  That is a metric which is hop count, or number of IP
hops.  This should be cited.

> Such metrics can represent the link bandwidth (in which case the
> metric is usually inversely proportional to the bandwidth), delay,
> etc.

I.e. in the above paragraph, the hop count could be mentioned explicitely.

Alex

---

From: Alexandru Petrescu <[email-masked]>
Date: Fri, 03 Jul 2009 11:06:41 +0200

JP Vasseur a écrit :
> the concept of loop is not related to the metric used to compute the path

The concept of loop is even less related to the effects of link loss 
ratio, asymmetry in the loss ratios between the two directions of each 
link, and interference among the successive links of a path (aka ETX).

I am wondering which metric other than hopcount could help build 
loop-free trees and paths spanning a graph...

Alex