Subject: [nemo] Announcing Tree Discovery

From: "Pascal Thubert \(pthubert\)" <[email-masked]>
Date: Mon, 17 May 2004 14:07:49 +0100

Hi:

Please note that a new draft has been published:
http://www.ietf.org/internet-drafts/draft-thubert-tree-discovery-00.txt

Summary:
   The purpose of this paper is to describe a minimum set of features
   that extends the Nemo basic support in order to avoid loops in the
   nested Nemo case. As a result, Mobile Routers assemble into a tree
   that can be optimized based on various metrics.

NEMO basic support does not address the formation of loops as MRs attach
to other MRs indiscriminately. This draft proposes a solution to that
problem, primarily as a complement for NEMO basic support, as opposed to
an RO solution. Nevertheless, shaping the tree optimally is critical for
the forthcoming RO solution.

Pascal

---

From: "Pascal Thubert \(pthubert\)" <[email-masked]>
Date: Mon, 17 May 2004 16:12:50 +0100

Hi Marcelo 
> 
> - about the clusterhead: why is it useful to include the fixed AR as
the
> clusterhead when it is possible. I mean, this would imply that every
time
> the nemo moves, you have to rebuild the tree. OTOH, if the clustehead
is the
> root MR, the tree could be preserved through movement. After all, the
sub MR
> are just MNN of the parent nemo, so they shouldn't be aware of the
parent
> movement, right?
Seems you are assuming the specific case of group mobility. If this
happens, I expect that the TIO will carry a GID and that the members of
the group will prefer a tree sourced at GID as one metric. In that case,
the root MR may omit forwarding the TIO from AR and set itself
clusterhead. This policy is allowed by the draft. 
 
On the other hand, it may happen that MRs move arbitrarily regarding
each other, e.g. cars in a city. In that case, you may want the
clusterhead to be a fixed antenna.

> - about the nodes and leafs of the tree. It is stated in the draft
that:
>    " The nodes of the tree are Mobile Routers, the root is
>    either a fixed or a Mobile Router, called in the latter case the
root
>    Mobile Router in NEMO terminology [6]. The leaves are mobile or
fixed
>    hosts, called Local Fixed Nodes, Local Mobile Nodes and Visiting
>    Mobile Nodes in the NEMO terminology."
> 
> My first point here is that there is an IMHO important difference
between
> fixed hosts and Local Fixed Nodes (and also between mobile hosts and
LMN and
> VMN) and that is that AFAIU, MNN can be routers while fixed and mobile
hosts
> can only be hosts (i guess)
> IMHO this is important in this case, because i clearly see that MR are
nodes
> of the tree and that hosts are leaves of the tree, but what about MNN
that
> are routers, that is a fixed router within the nemo, is this a node or
a
> leaf of the tree?
> This is also relevant in the case that for instance the access router
of a
> nemo is not a MR, for instance.
> 
> If fixed router within the nemo are not part of the tree, then i am
not sure
> how useful is this approach to fulfill the first goal stated in the
draft:
> 
> "  One of the usage of the new option introduced in this document is
to
>    distribute information on the hierarchy of MRs. This information
can
>    be distributed to ARs, MRs and MNNs as well in order to allow
better
>    route selection and to increase the knowledge of the Nemo topology
on
>    each node."
> 
> I mean the tree will not contain all the hops in the path, but only
the MR
> in the path, so, the shortest path according the tree may not be the
> shortest path in terms of hops, for instance.
> 
Right, we have to discuss the role of local fixed nodes that are
routers. A plain router like that will not know about the TIO and will
drop it. In turn, it may be mistaken for a fixed AR by a roaming MR. So
I guess this limits the role of such routers as stubs. This is the
assumption in the draft, they are leaves. But maybe we could devise a
new class of lfn routers, that would propagate TIOs... To be discussed. 

This is not core I believe. I expect that the most desired situation is
a MR attaching to an other MR, not a MR attaching to a LFN-router that
is attached to an MR.

> - about the support of non-MR. I guess that by non-MR you mean fixed
routers
> within the nemo, right?
> The proposed solution that uses an extension of the RA, requires that
all
> the routers within the nemo are upgraded, right? i mean, MR are part
of the
> tree so they need to build it, so they need to be upgraded, but non-MR
also
> need to be upgraded, since the need to copy the option, right?
Yes

> Wouldn't it be possible to use other ICMP message with a broader scope
so
> that you don't need support from non-MR? this would, IMHO, simplify
adoption
> but it would also provide a more robust solution, since in the present
> proposal, if one of the router within the nemo doesn't support the
protocol,
> this would mean that the tree information is lost and the loop
prevention
> mechanism can fail, right?
Sure. I'm not sure how your proposal really fixes any of this but I'm
interested in discussing it. As of now, LFN routers are leaves. I'm
missing a use case where there's value doing otherwise.

> - Finally, there are several fields in the proposed TIO format that i
am not
> sure what they are used for:
> The G and the H bits, the Path digest. And what is the difference of
the
> Boottime random and the treeid? i mean why cannot be the treeid be
used
> instead of the boottiemrandom

Boot time random is used for collision avoidance but can not be used to
identify a root MR. On the other hand, the tree id is a constant so
other routers may be configured to prefer that tree, referenced by ID.

Path digest changes if the list above you has changed, even if the depth
and tree id did not. This is useful to trigger a BU for instance.

The G bit guarantees the connectivity to the infrastructure. An
Algorithm that requires internet connectivity will prioritize a G bit on
in AR selection. Now what the infrastructure is context dependent. Same
context as that allowing the L2 access, hopefully. 

The H bit is informational for the time being. We have to discuss if a
MR with H on actually incremements the depth. But there's no practical
use for it for the time being...

Thanks for your comments :)

Pascal

---

From: "Pascal Thubert \(pthubert\)" <[email-masked]>
Date: Tue, 18 May 2004 08:47:18 +0100

> -----Original Message-----
> From: marcelo bagnulo [mailto:[email-masked]]
> Sent: lundi 17 mai 2004 17:49
> To: Pascal Thubert (pthubert); [email-masked]; [email-masked]
> Subject: RE: [nemo] Announcing Tree Discovery
> 
> 
> Ok, i didn't read the draft that way...
Actually you're right, 

the draft is not too clear about that. I have to fix it. Any router can
be clusterhead if it finds that the available clusters are not good
enough. And if a root MR has internet connectivity to an AR, it can
forward packets to the infrastructure. I hope that this much is clear
enough.

But you are right that a MR can not be clusterhead and then attach
anywhere in a tree without joining that tree, otherwise it would create
loops. The only case where it's valid for sure is when the clusterhead
attaches to a fixed AR, whether that fixed AR advertises itself as
clusterhead or not. This needs additional wording. Thanks :)

> This is the case that i don't understand why would you want that?
> I mean, if the clusterhead is a fixed AR then when the nemo moves it
has
> rebuild the tree, right?
> So what is the benefit of doing so? I am not saying that the draft
should
> prevent this situation, but it seems to me that you may have
considered some
> scenario where this configuration may be useful and provide some
benefits,
> if this is so, could you describe it?
> 
In fact, yes, very much so. Some is related to RO but I do not want such
discussions to cloud tree discovery and make it look like it's an RO
feature, since it's required for nemo basic, imho.

The classical use case is cars in a city. Cars do not move as a group,
so if a car drags a tree, the other (not necessarily moving) cars will
have to jump all the time. Having a fixed AR as clusterhead stabilizes
the situation and enables parked cars to relay for moving ones.

As for RO, once a tree is built around a fixed antenna, you may use the
antenna for Local mobility management. For instance, a fixed clusterhead
is ideally placed to be the DHCP-PD + Home Agent in our nemo LMM draft
http://www.ietf.org/internet-drafts/draft-droms-nemo-dhcpv6-pd-01.txt .

Finally, a car may stay for a while in a radius around a few blocks,
even if the immediate vicinity with other cars changes rapidly. So a car
may be able to stay within the same tree if that tree is based on a
fixed antenna; this enables all sorts of routing, within the tree and
between clusterheads. In fact, this is why I call these clusterheads in
the first .

> [...]
> > drop it. In turn, it may be mistaken for a fixed AR by a roaming MR.
> 
> I an not parsing the last sentence, sorry...
Just acknowledging your words. A legacy router will be mistaken for a
fixed router even if it is permanently attached to a MR and moving with
it. So I guess a roaming MR should always prefer an Attachment Router
with TIO, be it fixed or mobile. But in order to prevent loops, it is
also recommended that legacy MR be configured not to accept roaming MRs,
what can we do, right?

> > So
> > new class of lfn routers, that would propagate TIOs
> 
> I understood that this is what it is required in order the mechanism
to
> work, as described in section 4.2 when talking about non-MR... So just
to
> clarify the discussion what do you mean by a non-MR in section 4.2?
> 
> My concer regarding this point and the next one is how does the TD
works
> when a router LFN exists in the nemo

Understood and agreed with the concern, though I saw it as secondary for
the lack of use cases.

This is one discussion where help from the group would be appreciated.
We already simulated that draft, and actually that was a concern. We
ended up moving the TIO support from a MR feature to a ND optional
feature for all routers. It may be harder to move it to IETF that way,
though.
 
The same question arises for a MR that is at home in a tree. Should it
propagate TIO? Should it increase the depth? We started with no for both
and ended up with yes for both. Really we have to weight this as a group
and make a decision.

> 
> IMHO I guess that there are two cases here:
> 
> - when a router LFN doesn't support the TD in any form
> - When a router LFN supports the TD
> 
  and when a MR is at home in a tree (mobile home stuff) as a third

> According to the draft the TD has two goals,:
> - Loop prevention
> - enhanced route selection
> 
> IMHO the loop prevetnion is critical, while the enhanced route
selection is
> one of those nice-to-have features.
Yes

Actually we try to avoid the enhanced thing. We intend to present just
the mere common part, not a specific route selection. We have a number
of algorithms for various use cases. One is cars (again) where all you
want is minimizing the depth with optionally some stickiness to a given
antenna, one is the fleet where the infrastructure connectivity is
secondary, but you want a managed tree (thus the preference), an other
one is a group of tourist where a group ID is critical... But all those
need to share the core presented in the draft.
> 
> IMHO the support when there are router LFN in the nemo would be that:
> 
> - the loop prevention doesn't breaks
> - get as much as possible of the enhanced route selection as possible
cool

> As far as is understand in its current form, the proposed TD
mechanisms
> breaks if a router LFN that doesn't supports TD exists in the nemo,
right? 
> This is beacuse, the the non upgraded router LFN won't forward the TIO
> opction so, the tree discovery mechanism will be broken, right?

Well, they are supposed to reject visitors (eg no RA or M bit),
otherwise yes, exactly.

> 
> I guess that it would be better to have a more robust TD mechanism
that
> supports non upgraded router LFN in the nemo. This would require using
some
> other signaling instead of using a RA option. The new signaling
message
> shouldn't be link scoped but its scope should be the nemo.
Not too easy to do. And remember you want to be damn quick and
efficient. Sometimes, an apparent beauty results in a living nightmare.
My proposal is to leave those as leaves and see what we can do for case
2 (LFN Router with TD) and 3 (MR at home within tree).

> But before discusin options about how to do this, do you agree that it
would
> be intersting that the TD mechanism can support non upgraded routers
LFN?
Not really. Being a MR is pretty cool. Can add features like RO to the
picture. Again I need a convincing use case. TD builds the tree
dynamically and is you support RRH, you can source route down that tree.
TD on MRs (even more with an RO solution like RRH in place) results in a
pretty efficient feature and I would definitely enable MR on all boxes
in a roaming cloud.

> 
> The other issue is about enahnced route selection.
> I am not sure that we can do much when we have to deal with non
upgraded
> router LFN in this case, but i guess that including upgraded router
LFN in
> the tree topology would provide more information about intermediate
hosts,
> so the selection would be improved. So i guess that all the routers
that
> support the TD mechanisms could be included in the tree as a form to
provide
> more detailed information for route selection support.
Yes, this seems reasonable and we have to figure that out. I believe we
should concentrate on that case as opposed to legacy LFN routers. If we
do so, again, this impacts all routers, making it harder to move forward
at IETF...

> [...]
> I may have missed some of this stuff, but if they are not in the
draft,
> including them would provide clearer view of the mechanisms.

Well, chapter 5 explains the collision stuff. In particular 5.3.3 gives
you the extended preference stuff based on the Boot time random. This
seems almost impossible in real life but it is the first thing you get
in a simulation :)

> My pleasure, nice draft.

:)

Pascal