wdiff draft-thubert-tree-discovery-01.txt draft-thubert-tree-discovery-02.txt

NEMO Working Group P. Thubert
Internet-Draft Cisco
Expires: April 11, 2005 January 16, 2006 C. Bontoux
Fortinet
N. Montavont
LSIIT - ULP
October 11, 2004
July 15, 2005

Nested Nemo Tree Discovery
draft-thubert-tree-discovery-01.txt
draft-thubert-tree-discovery-02.txt

Status of this Memo

By submitting this Internet-Draft, I certify each author represents that any
applicable patent or other IPR claims of which I am he or she is aware
have been or will be disclosed, and any of which I become he or she becomes
aware will be disclosed, in accordance with
RFC 3668. Section 6 of BCP 79.

Internet-Drafts are working documents of the Internet Engineering
Task Force (IETF), its areas, and its working groups. Note that
other groups may also distribute working documents as
Internet-Drafts. Internet-
Drafts.

Internet-Drafts are draft documents valid for a maximum of six months
and may be updated, replaced, or obsoleted by other documents at any
time. It is inappropriate to use Internet-Drafts as reference
material or to cite them other than as "work in progress."

The list of current Internet-Drafts can be accessed at
http://www.ietf.org/ietf/1id-abstracts.txt.

The list of Internet-Draft Shadow Directories can be accessed at
http://www.ietf.org/shadow.html.

This Internet-Draft will expire on April 11, 2005. January 16, 2006.

Abstract

The purpose of this paper is to describe a minimum set of features
that extends the Nemo basic support [4] 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.

Table of Contents

1. Introduction . . . . . . . . . . . . . . . . . . . . . . . . . 3

2. Terms and Abbreviations . . . . . . . . . . . . . . . . . . . 3

3. Motivations . . . . . . . . . . . . . . . . . . . . . . . . . 4
3.1 Multihomed Multi-Homed nested mobile network . . . . . . . . . . . . . 4
3.2 Loops in nested Nemo . . . . . . . . . . . . . . . . . . . 5

4. Router Advertisement extensions . . . . . . . . . . . . . . . 6
4.1 Router Advertisement message . . . . . . . . . . . . . . . 6
4.2 Tree Information Option . . . . . . . . . . . . . . . . . 6 7

5. Tree Discovery . . . . . . . . . . . . . . . . . . . . . . . . 8 9
5.1 tree selection . . . . . . . . . . . . . . . . . . . . . . 9 11
5.2 Subtree Sub-tree mobility . . . . . . . . . . . . . . . . . . . . . 10 11
5.3 Tree Hop Timer DRL entries states and stability . . . . . . . . . . . . . 11
5.3.1 Held-Up . . . . . . . . . 10
5.4 Collisions and stability . . . . . . . . . . . . . . 12
5.3.2 Held-Down . . . . . 11
5.4.1 Hold down . . . . . . . . . . . . . . . . . 13
5.3.3 Collision . . . . . 12
5.4.2 . . . . . . . . . . . . . . . . . 13
5.3.4 Instability . . . . . . . . . . . . . . . . . . . . . 12
5.4.3 Collision 14
5.4 Legacy Routers . . . . . . . . . . . . . . . . . . . . . . 12
5.5 Legacy Routers 14

6. IANA Considerations . . . . . . . . . . . . . . . . . . . . . 14

7. Security Considerations . 13

6. . . . . . . . . . . . . . . . . . . 15

8. Changes . . . . . . . . . . . . . . . . . . . . . . . . . . . 14
6.1 16
8.1 Changes from version 00 to 01 . . . . . . . . . . . . . . 14

7. 16
8.2 Changes from version 01 to 02 . . . . . . . . . . . . . . 16

9. Acknowledgments . . . . . . . . . . . . . . . . . . . . . . . 14

8. 16

10. References . . . . . . . . . . . . . . . . . . . . . . . . . 17
10.1 Normative Reference . 15 . . . . . . . . . . . . . . . . . . 17
10.2 Informative Reference . . . . . . . . . . . . . . . . . . 17

Authors' Addresses . . . . . . . . . . . . . . . . . . . . . . 15 18

Intellectual Property and Copyright Statements . . . . . . . . 17 19

1. Introduction

As per Nemo Basic support, support [4], a Mobile Router autoconfigures a
single Care of Address (CoA) to register to its Home Agent and
terminate its MR-HA Mobile Router-Home Agent tunnel. That CoA Care of Address
is the MR's Mobile Router point of attachment to the nested Nemo.

Consequently, if loops are avoided, the nested Nemo assumes the shape
of a tree. 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.

This paper provides (1) a minimum extension to IPv6 Neighbour Neighbor
Discovery Router Advertisements in order to ensure that Mobile
Routers attaching to one another actually avoid loops and end up
forming a tree, and (2) the minimum common part of all MR Mobile Router
algorithms that is required to ensure that whatever their specific
decisions, loops between MRs Mobile Routers will be avoided.

The method is based on an autonomous decision by each MR Mobile Router
with no global state convergence such as a MANET proactive routing
protocol. In fact, MRs Mobile Routers may make different decisions from
a same input, based on their own configuration and their own
algorithms.

In order to build trees of Mobile Routers, we propose an extension to
the ICMP Router Advertisement (RA) message, the Tree Information
Option (TIO). The RA/TIO RA-TIO allows MRs Mobile Routers to advertise the tree
they belong to, and to select and move to the best location within
the available trees. MRs Mobile Routers propagate the TIO down the tree,
updating some metrics such as the tree depth, leaving alone root
information such as the tree identifier, and sending the result in
RAs over the ingress interfaces.

2. Terms and Abbreviations

This document assumes that the reader is familiar with Mobile IPv6 as
defined in [3] and with the concept of Mobile Router defined in the
Nemo terminology document [6].

For the needs of this paper, the following new definitions are
introduced:

Nemo Clusterhead: clusterhead: The root of a tree of mobile routers. When the
tree of Mobile Routers is attached to the infrastructure, the
fixed Access Router may act as cluster head if it supports the
Tree Information Option described in this document. If it does
not, then the Clusterhead clusterhead coincides with the root MR Mobile Router in
NEMO terminology. A clusterhead is elected even when the tree is
not attached to the infrastructuture. infrastructure. A stand-alone MR Mobile Router
is a
Clusterhead. clusterhead.

Floating Tree: A Nested Nemo which Clusterhead clusterhead is a MR Mobile Router
that is not attached to an AR. Access Router.

Grounded Tree: A Nested Nemo whose Clusterhead clusterhead is attached to the
infrastructure. In other words, the clusterhead is either a fixed
router that supports RA/TIO Router Advertisement - Tree Information
Option or is a MR Mobile Router which attachment router is a fixed
router that does not support RA/TIO. Router Advertisement - Tree
Information Option.

Mobile Access Router: A Mobile Router that provides Access Router
services to other MRs. Mobile Routers.

Attachment Router: The Router that is selected as Access Router by a
Mobile Router, making it its parent in the nested NEMO tree.

Propagation: The action by a Mobile Router that consists in receiving
a RA/TIO Router Advertisement - Tree Information Option from its
Attachment Router, recomputing a few specific fields, removing
unknown suboption, and appending the resulting TIO to RAs sent
over the ingress interfaces.

3. Motivations

3.1 Multihomed Multi-Homed nested mobile network

A nested mobile network that is made of multiple MRs Mobile Routers
having a direct connection to the Internet is said to be multihomed. multi-homed.
Multihoming in Nemo offers useful properties to MNNs. Mobile Network Nodes.
The NEMO multihoming issues
[8] [9] draft lists potential multihomed multi-homed
configurations for Nemo and explains the different problems and
advantages that some configurations may introduce. Multihoming
offers three main abilities to the Nemo: it allows route recovery on
failure, redundancy and load-sharing between MRs Mobile Routers (or
between MRs'interfaces). interfaces of a given Mobile Router). However, for the moment
moment, there are is no requirements nor protocol
defining how to use that would define in
interaction between several egress interfaces inside a Nemo.

In a nested Nemo, the hierarchy of MRs Mobile Routers increases the
complexity of the route and/or router selection for MNNs. Mobile Network
Nodes. Each level of a Nemo implies the usage of a new tunnel
between the MR Mobile Router and its home agent. Thus if a MNN Mobile
Network Node connects to a sub-Nemo which is also a sub-Nemo, packets
from the MNN Mobile Network Node will be encapsulated three times.

When the Nemo where the MN is connected to is multihomed, multi-homed, the MN may
have the choice between several AR Attachment Router to be its default
router. Reference [9] [7] introduces new options in Router Advertisement
to allow any node on a link to choose between several routers. This
option mainly consists of a 2-bits flag that indicates the preference
of the router (low, medium or high). Furthermore, the same flag can
be set in the Route Information option indicating the preference of a
specific prefix. Therefore, any node can determine its best default
router(s) according to a given destination and its best router for
default, which will be used by default.

However this preference is only useful in a flat topology; It gives a
way to the node to choose between different access attachment routers
advertising prefixes on the node link. But if the node is inside a
hierarchical topology (some access routers are not at the same level) the node can not learn the level depth of each access router.
attachment router, and might not select the most efficient path.

One of the usage of the new option introduced in this document is to
distribute information on the hierarchy of MRs. Mobile Routers. This
information can be distributed to ARs, MRs Attachment Routers, Mobile Routers
and MNNs Mobile Network Nodes as well in order to allow better route
selection and to increase the knowledge of the Nemo topology on each
node.

3.2 Loops in nested Nemo

When several MRs Mobile Routers attach to each other to form a nested
Nemo, loops can be created if they are not explicitely explicitly avoided. In
the simplest case, when egress and ingress interfaces of an MR Mobile
Router are all wireless, a mobile router may be listening to Router
Advertisement from its own ingress interface, creating a confliction
problem. In the general case, arbitrary attachment of MRs Mobile Routers
will form graphs that are not exempt of loops. For instance: Assume
a nested Nemo where MR1 Mobile Router1 is connected to the
infrastructure, and MR3 Mobile Router3 is attached to MR2. Mobile Router2.
Say that MR2 Mobile Router2 can hear both MR3 Mobile Router3 and MR1 Mobile
Router1 over its wireless egress interface. If MR2 Mobile Router2 select MR1,
Mobile Router1, the connectivity to the infrastruture infrastructure is provided
for all. But if MR2 Mobile Router2 selects MR3, MR2 Mobile Router3, Mobile
Router2 and MR3 Mobile Router3 end up forming a loop and are disconnected
from their Home Agents.

With Nemo basic support, a MR Mobile Router uses a single primary CareOf Care
Of Address to attach to the nested structure. As a result, if loops
are avoided, the nested NEMO end up forming a tree. It is beneficial
to be able to form that tree in an optimum fashion for a given set of
metrics such as tree depth.

The shape of a nested Nemo may change rapidly due to MRs Mobile Routers
movement. It is thus impractical to expect each MR Mobile Router to be
able to maintain states about the whole tree structure in a link
state fashion. On the contrary, it is also beneficial to allow each MR
Mobile Router to make its own independent selection based on a
minimum information about its immediate neighbors, in order to
reestablish the tree quickly upon erratic movements.

Each MR Mobile Router should be able to make its own attachment router
selection based on its own condition (eg battery level), its own set
of constraints that may not apply to other MRs Mobile Routers in the
tree, and in general its own algorithm. As a result, the
standardization effort should concentrate on a common minimum set of
rules that must be common to all MRs Mobile Routers in order to prevent
routing loops in the nested NEMO while leaving MRs Mobile Routers
independent in their AR Attachment Router selection algorithms.

4. Router Advertisement extensions

New extensions of Router Advertisement are proposed to distribute the
knowledge of the MR Mobile Router hierarchy inside a nested Nemo. These
extensions are defined in different options/sub-options: a flag bit
from the reserved flag field of Router Advertisement message is used
to indicate whether the sending router is a MR Mobile Router or not; a
new option is defined to transport minimum information on the tree to
avoid loops generation;

4.1 Router Advertisement message

We propose to use a reserved flag of the Router Advertisement message
to inform whether the sending router is a MR Mobile Router or not.

0 1 2 3
0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Type | Code | Checksum |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Cur Hop Limit |M|O|H|N|Reservd| Router Lifetime |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Reachable Time |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Retrans Timer |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Options ...
+-+-+-+-+-+-+-+-+-+-+-+-

Figure 1: Router Advertisement

Nemo enabled router (N)

The Nemo enabled router (N) bit is set when the sending router is a
Mobile Router.

4.2 Tree Information Option

The following option regroups the minimum information that allows a
MR
Mobile Router to discover a tree and select its point of attachment
while avoiding loop generation. It can also be used by MNNs Mobile
Network Nodes to select their best default router. If the default
router of a non-MR non-Mobile Router sends Router Advertisements with a tree
discovery option, the non-MR non-Mobile Router MUST set the N flag of its
own Router Advertisement to 0 and copy the Tree Discovery Option in
its own Router Advertisement.

0 1 2 3
0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Type | Length |G|H| Reserved |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| TreePref. | Preference | BootTimeRandom |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| TreeDepth | TreePref. Reserved | TreeDelay |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| PathDigest |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| |
+ +
| TreeID |
+ +
| |
+ +
| |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| sub-option(s)...
+-+-+-+-+-+-+-+-+-+-+-+-+-+

Figure 2. 2: Tree Information Option

Type 8-bit unsigned integer set to 10 by the Clusterhead. clusterhead. Value is
"TBD".

Length 8-bit unsigned integer set to 4. The length of the option
(including the type and length fields) in units of 8 octets.

Grounded (G) The Grounded (G) flag is set when the Clusterhead clusterhead is
attached to a fixed network infrastructure (such as the Internet).

Home (H) The Home (H) flag is set when the Clusterhead clusterhead is attached to
its home network.

Reserved 16-bit unsigned integer set to 0 by the Clusterhead. clusterhead.

TreePreference 8-bit unsigned integer set by the clusterhead to its
preference and unchanged at propagation. Default is 0 (lowest
preference).

Preference The administrative preference of that (mobile) Access
Router. Default is 0. 255 is the highest possible preference.
Set by each MR Mobile Router at propagation time.

BootTimeRandom A random value computed at boot time and recomputed in
case of a duplication with another AR. Attachment Router. The
concatenation of the Preference and the BootTimeRandom is a 32-bit
extended preference that is used to resolve collisions. It is set
by each MR Mobile Router at propagation time.

TreeDepth 8-bit unsigned integer. The tree depth of the clusterhead
is 0 if it is a fixed router and 1 if it is a Mobile Router. The
tree Depth of a tree Node is the depth of its attachment router as
received in a TIO, incremented by one. All nodes in the tree
advertise their tree depth in the Tree Information Options that
they append to the RA messages over their ingress interfaces as
part of the propagation process.

TreePreference 8-bit unsigned integer set by the Clusterhead to its
preference and unchanged at propagation. Default is 0 (lowest
preference).

TreeDelay 16-bit unsigned integer set by the Clusterhead clusterhead indicating
the delay before changing the tree configuration, in milliseconds.
A default value is 128ms. It is expected to be an order of
magnitude smaller than the RA-interval so if the clusterhead has a
sub-second RA-interval, the Tree delay may be shorter than 100ms.
It is also expected to be an order of magnitude longer than the
typical propagation delay inside the nested Nemo.

PathDigest 32-bit unsigned integer CRC, updated by each MR. Mobile
Router. This is the result of a CRC-32c computation on a bit
string obtained by appending the received value and the MR Mobile
Router Care of Address.
Clusterheads clusterheads use a 'previous value' of
zeroes to initially set the PathDigest.

TreeID 128-bit unsigned integer which uniquely identify a tree tree. This
value is set by the Clusterhead. clusterhead. The global IPv6 home address of
the Clusterhead clusterhead can be used.

The following values MUST not change during the propagation of the
TIO down the tree: Type, Length, G, H, TreePreference, TreeDelay and
TreeID. All other fields of the TIO are updated at each hop of the
propagation.

5. Tree Discovery

Here follows a set of rules and definitions that MUST be followed be by
all Mobile Routers:

1. An MR Mobile Router that is not attached to an AR Attachment Router is
the Nemo Clusterhead clusterhead of its own, own floating tree. It's depth is 1.

2. An MR Mobile Router that is attached to an AR Attachment Router that
does not support TIO, is the clusterhead of its own, own grounded
tree. It's depth is 1.

3. A router sending a RA without TIO is considered a grounded AR
Attachment Router at depth 0. Thus, a MR that attaches to an AR that does not include
a TIO in its RA becomes a Clusterhead of depth 1.

4. The Nemo ClusterHead clusterhead of a tree exposes the tree in the RA/TIO Router
Advertisement - Tree Information Option and
MRs Mobile Routers
propagate the TIO down the tree with the RAs that they forward
over their ingress links.

5. An MR Mobile Router that is already part of a tree MAY move at any
time and with no delay in order to get closer to the clusterhead
of its current tree - i.e. in order to reduce its own tree depth.
But an MR Mobile Router MUST NOT move down the tree that it is
attached to. MRs Mobile Routers MUST ignore RAs that are received
from other routers located deeper or at the same depth within the
same tree.

6. An MR Mobile Router may move from its current tree into any
different tree at any time and whatever the depth its reaches in
the new tree, but it may have to wait for a Tree Hop timer to
elapse in order to do so. The MR Mobile Router will join that other
tree if it is more preferable for reasons of connectivity,
configured preference, size, security, bandwidth, tree depth, or
whatever metrics the MR Mobile Router cares to use.

7. If a MR Mobile Router has selected a new attachment router but has
not moved yet (because it is waiting for Tree Hop timer to
elapse), the MR Mobile Router is unstable and refrains from sending RATIOs.
Router Advertisement - Tree Information Options.

8. When an MR Mobile Router joins a tree, moves within its tree, or
when it receives a modified TIO from its current access attachment
router, the MR Mobile Router sends an unsolicited Router
Advertisement message on all its mobile networks (i.e. all its
ingress interfaces). The RA contains a TIO that propagates the
new tree information. At the same time, the MR Mobile Router MAY
send a Binding Update to its home agent or a local proxy of some
sort, because the tree it is attached to has changed. If the MR
Mobile Router fails to reach its HA, Home Agent, it MAY attempt to
roll back the movement or to retry the HA Home Agent discovery
procedure.

9. This allows the new higher parts of the tree to take place first
eventually dragging their sub-tree with them, and allowing
stepped sub-tree reconfigurations, limiting relative movements.

5.1 tree selection

The tree selection is implementation and algorithm dependent. In
order to limit erratic movements, and all metrics being equal, MRs Mobile
Routers SHOULD stick to their previous selection. Also, MRs Mobile
Routers SHOULD provide a mean to filter out candidate ARs Attachment
Routers whose availability is detected as fluctuating, at least when
more stable choices are available. For instance, the MR Mobile Router
MAY place the failed AR Attachment Router in a Hold Down mode that
ensures that the AR Attachment Router will not be reused for a given
period of time.

The known trees are associated with the AR Attachment Router that
advertises them and kept in an ordered list, per order of preference, a list by extending the Default Router
List. DRL entries are extended to store the information received
from the last TIO, TIO. These entries are managed by states and a timer ID -and related
data- to delay the reaction to a better RA message, the tree hop
timer, as timers
described in the next section.

When connection to a fixed network is not possible or preferable for
security or other reasons, scattered trees should aggregate as much
as possible into larger trees in order to allow inner connectivity.
How to balance these trees is implementation dependent, and MAY use a
specific visitor-counter suboption in the TIO.

5.2 Subtree Sub-tree mobility

It might be perceived as beneficial for a subtree sub-tree to move as a
whole. The way it would work is for a MR Mobile Router to stay root-MR root-
Mobile Router even if itself is attached into a parent tree. But the
loop avoidance is based on the knowledge of the tree that the MR Mobile
Router visit, preventing a MR Mobile Router to move down a same tree.
So without additional support, tree-level loops could form.

To avoid this, it is possible to add a path vector suboption to the
TIO that reflects the nesting of trees. If a root-MR root-Mobile Router
joins a parent tree, then it needs to add its treeID to the path
vector, but it can not join if the treeID is already listed.

A specific case is the root-MR root-Mobile Router of a tree that attaches to
a fixed Access Router. That root-MR root-Mobile Router might omit to
consider a TIO that comes from the new AR Attachment Router and decide
to stay root, in order to keep the tree consistency from the nested MRs
Mobile Routers standpoint. This does not create loops, even if the
path vector is not present

5.3 Tree Hop Timer DRL entries states and stability

Attachment routers in the DRL may or may not be usable for roaming
depending on runtime conditions. The following states are defined:

Current This Attachment Router is used for roaming

Candidate This Attachment Router can be used for roaming.

Held-Up This Attachment Router can not be used till tree Hop hop timer
elapses. This does not occur for a fixed Attachment Router that
does not send a TIO since the tree delay is null in that case.

Held-Down This Attachment Router can not be used till hold down timer
elapses. At the end of the hold-down period, the router is
removed from the DRL, and will be reinserted if it appears again
with a RA.

Collision This Attachment Router can not be used till its next RA.

5.3.1 Held-Up

This state is managed by the tree Hop timer, it serves 2 purposes:

Delay the reattachment of a subtree sub-tree that has been forced to
detach. This allows to make sure that when a subtree sub-tree has
detached, the RATIO Router Advertisement - Tree Information Option that
is initiated by the new clusterhead has spread down the subtree sub-tree
so that two different trees have formed.

Limit RA/TIO Router Advertisement - Tree Information Option storms when
two trees collide. The idea is that between the nodes from tree A
that wish to move to tree B, those that see the highest place in
tree B will move first and advertise their new locations before
other nodes from tree A actually move.

A new tree is discovered upon a router advertisement message with or
without a RA/TIO. Router Advertisement - Tree Information Option. The MR Mobile
Router joins the tree by selecting the source of the RA message as
its access attachment router (default gateway) and propagating the TIO
accordingly.

When a new tree is discovered, the candidate AR Attachment Router that
advertises the new tree is placed in a held up state for the duration
of a Tree Hop timer. If the new AR Attachment Router is more preferable
than the current one, the MR Mobile Router expects to jump and becomes
unstable.

A MR Mobile Router that is unstable may discover other ARs Attachment
Routers from the same new tree during the instability phase. It
needs to start a new Tree Hop timer for all these. The first timer
that elapses for a given new tree clears them all for that tree,
allowing the MR Mobile Router to jump to the highest position available
in the new tree.

The duration of the Tree Hop timer depends on the tree delay of the
new tree and on the depth of AR Attachment Router that triggers it:

(AR's depth + random) * AR's tree_delay (where 0 <= random < 1). It
is randomized in order to limit collisions and synchronizations.

5.4 Collisions and stability

Attachment routers in the DRL may or may not be usable for roaming
depending on runtime conditions. The following states are defined:

Current This AR is used for roaming

Candidate This AR can be used for roaming. Typically, an initial
held-up period is over but the candidate is not preferred over the
current AR.

Held-Up This AR can not be used till tree hop timer elapses. This
does not occur for a fixed AR that does not send a TIO since the
tree delay is null in that case..

5.3.2 Held-Down This AR can not be used till hold down timer elapses. At
the end of the hold-down period, the router is removed from the
DRL, and will be reinserted if it appears again with a RA.

Collision This AR can not be used till its next Router Advertisement

5.4.1 Hold down

When a router is 'removed' from the Default Router List, it is
actually held down for a hold down timer period, in order to prevent
flapping. This happens when an AR Attachment Router disappears (upon
expiration timer), and when an AR Attachment Router is tried but can not
reach the HA Home Agent (upon expiration of another AR, Attachment Router,
or upon tree hop for that AR). Attachment Router).

An Attachment Router that is held down is not considered for the
purpose of roaming. When the hold down timer elapses, the AR Attachment
Router is removed from the DRL.

5.4.2 Instability

A MR is instable when a Held-Up AR is placed before the current AR.
Instability is transient (In the order of tree hop timers). When a
MR is instable, it MUST NOT send RAs with TIO. This avoids loops
when MR A wishes to attach to MR B and MR B wishes to attach to MR A.
Unless RA cross (which is a short window of time), a MR receives TIO
from stable ARs, which do not plan to attach to itself, so the MR can
safely attach to them.

A MR is instable when it is prepared to move shortly to another AR.
This happens typically when it discovers a new and more preferred
candidate AR, for the duration of the tree hop timer. During that
time, the new candidate is placed in Held-up state. Instability may
also occur when the current AR is lost and the next best is still
held up. Instability is resolved when the tree hop timer of all the
AR (s) causing instability elapse. Such AR is changes state to
Current or Held-Down.

5.4.3

5.3.3 Collision

A race condition occurs if 2 MRs Mobile Routers send RA/TIO Router Advertisement
- Tree Information Option at the same time and wish to join each
other. In order to detect the situation, MRs Mobile Routers time stamp
the sending of RA/TIO. Router Advertisement - Tree Information Option. Any RA/TIO
Router Advertisement - Tree Information Option received within a
short media-dependant period introduces a risk. To divide the risk,
A 32bits extended preference is added in the TIO. The first byte is
the AR clusterhead preference, then the router own preference (default 0),
is 0 for both), the rest remaining 16 bits is a boot time computed
random.

A MR Mobile Router that decides to join an AR Attachment Router will do so
between (AR (Attachment Router depth) and (AR (Attachment Router depth + 1)
times the AR Attachment Router tree delay. But since a MR Mobile Router is
unstable as soon as it receives the RA/TIO Router Advertisement - Tree
Information Option from the preferred AR, Attachment Router, it will
restrain from sending a RA/TIO Router Advertisement - Tree Information
Option between the time it receives the RA and the time it actually
jumps. So the crossing of RA may only happen during the propagation
time between the AR Attachment Router and the MR, Mobile Router, plus some
internal queuing and processing time within each machine. It is
expected that one tree delay normally covers that interval, but
ultimately it is up to the implementation and the configuration of
the AR Attachment Router to define the duration of risk window.

There is risk of a collision when a MR Mobile Router receives an RA, for
an other mobile router that is more preferable than the current AR,
Attachment Router, within the risk window. In the face of a
potential collision, the Mobile Router with the lowest extended
preference processes the RA/TIO Router Advertisement - Tree Information
Option normally, while the router with the highest preference places
the other in collision state, does not start the tree hop timer, and
does not become instable. It is expected that next RAs between the
two will not cross anyway.

5.5

5.3.4 Instability

A Mobile Router is instable when it is prepared to move shortly to
another Attachment Router. This happens typically when the Mobile
Router has selected a more preferred candidate Attachment Router and
has to wait for the tree hop timer to elapse before roaming.
Instability may also occur when the current Attachment Router is lost
and the next best is still held up. Instability is resolved when the
tree hop timer of all the Attachment Router (s) causing instability
elapse. Such Attachment Router is changes state to Current or Held-
Down.

Instability is transient (in the order of tree hop timers). When a
Mobile Router is unstable, it MUST NOT send RAs with TIO. This
avoids loops when Mobile Router A wishes to attach to Mobile Router B
and Mobile Router B wishes to attach to Mobile Router A. Unless RA
cross (see Collision section), a Mobile Router receives TIO from
stable Attachment Routers, which do not plan to attach to itself, so
the Mobile Router can safely attach to them.

5.4 Legacy Routers

A legacy router sends its Router Advertisements without a TIO.
Consequently, a legacy router can be mistaken for a fixed Access
Router when it is placed within a nested NEMO structure, and defeat
the loop avoidance mechanism. Consequently, it is important for the
administrator to prevent address autoconfiguration by visiting MRs Mobile
Routers from such a legacy router.

6. IANA Considerations

Section 4.2. requires the definition of a new option to Neighbor
discovery [1] messages, the Router Advertisement - Tree Information
Option (RA-TIO). The Router Advertisement - Tree Information Option
has been assigned the value TBD within the numbering space for IPv6
Neighbor Discovery Option Formats.

7. Security Considerations

At the current level of this draft, the TIO bears the security level
of the RA and the link. Nothing is added to it. A deeper threat
analysis would be required to eventually propose additional security.

8. Changes

6.1

8.1 Changes from version 00 to 01

Added text on subtree sub-tree mobility from the discussion with Marcelo.

Added text on nested legacy routers from the discussion with
Marcelo.

8.2 Changes from version 01 to 02

Improved text on instability

Changed the formula for the 4 bytes number used in collision
avoidance

9. Acknowledgments

The authors wish to thank Marco Molteni and Patrick Wetterwald
(cisco) for their participation to this design and the review of the
document, and Massimo Villari (university of Messina), for his early
work on simulation and research on the subject. This work is also
based on prior publications, in particular HMRA [7] [8] by Hosik Cho and
Eun-Kyoung Paik from Seoul National University and other non IETF
publications coauthored with Thierry Ernst and Thomas Noel. Finally,
thanks to Marcelo Bagnulo Braun for his constructive review.

10. References

10.1 Normative Reference

[1] Narten, T., Nordmark, E. E., and W. Simpson, "Neighbor Discovery
for IP Version 6 (IPv6)", RFC 2461, December 1998.

[2] Thomson, S. and T. Narten, "IPv6 Stateless Address
Autoconfiguration", RFC 2462, December 1998.

[3] Johnson, D., Perkins, C. C., and J. Arkko, "Mobility Support in
IPv6", draft-ietf-mobileip-ipv6-24 (work in progress), July
2003. RFC 3775, June 2004.

[4] Devarapalli, V., Wakikawa, R., Petrescu, A., and P. Thubert,
"Network Mobility (NEMO) Basic Support Protocol", draft-ietf-nemo-basic-support-03 (work in progress),
June 2004. RFC 3963,
January 2005.

[5] Ernst, T., "Network Mobility Support Goals and Requirements",
draft-ietf-nemo-requirements-02
draft-ietf-nemo-requirements-04 (work in progress),
February
2004. 2005.

[6] Ernst, T. and H. Lach, "Network Mobility Support Terminology",
draft-ietf-nemo-terminology-01
draft-ietf-nemo-terminology-03 (work in progress),
February
2004. 2005.

[7] Draves, R. and D. Thaler, "Default Router Preferences and More-
Specific Routes", draft-ietf-ipv6-router-selection-07 (work in
progress), January 2005.

10.2 Informative Reference

[8] Cho, H., "Hierarchical Mobile Router Advertisement for nested
mobile networks", draft-cho-nemo-hmra-00 (work in progress),
January 2004.

[8]

[9] Ernst, T., "Analysis of Multihoming in Network Mobility
Support", draft-ietf-nemo-multihoming-issues-00 draft-ietf-nemo-multihoming-issues-02 (work in
progress), July 2004.

[9] Draves, R. and R. Hinden, "Default Router Preferences and
More-Specific Routes", draft-ietf-ipv6-router-selection-03 (work
in progress), December 2003. February 2005.

Authors' Addresses

Pascal Thubert
Cisco Systems
Village d'Entreprises Green Side
400, Avenue de Roumanille
Batiment T3
Biot - Sophia Antipolis 06410
FRANCE

Phone: +33 4 97 23 26 34
EMail:
Email: pthubert@cisco.com

Caroline Bontoux
Fortinet
Sophia Antipolis
Biot 06410
FRANCE

Email: cbontoux@fortinet.com

Nicolas Montavont
LSIIT - Univerity Louis Pasteur
Pole API, bureau C444
Boulevard Sebastien Brant
Illkirch 67400
FRANCE

Phone: (33) 3 90 24 45 87
EMail:
Email: montavont@dpt-info.u-strasbg.fr
URI: http://www-r2.u-strasbg.fr/~montavont/

Intellectual Property Statement

The IETF takes no position regarding the validity or scope of any
Intellectual Property Rights or other rights that might be claimed to
pertain to the implementation or use of the technology described in
this document or the extent to which any license under such rights
might or might not be available; nor does it represent that it has
made any independent effort to identify any such rights. Information
on the procedures with respect to rights in RFC documents can be
found in BCP 78 and BCP 79.

Copies of IPR disclosures made to the IETF Secretariat and any
assurances of licenses to be made available, or the result of an
attempt made to obtain a general license or permission for the use of
such proprietary rights by implementers or users of this
specification can be obtained from the IETF on-line IPR repository at
http://www.ietf.org/ipr.

The IETF invites any interested party to bring to its attention any
copyrights, patents or patent applications, or other proprietary
rights that may cover technology that may be required to implement
this standard. Please address the information to the IETF at
ietf-ipr@ietf.org.

Disclaimer of Validity

This document and the information contained herein are provided on an
"AS IS" basis and THE CONTRIBUTOR, THE ORGANIZATION HE/SHE REPRESENTS
OR IS SPONSORED BY (IF ANY), THE INTERNET SOCIETY AND THE INTERNET
ENGINEERING TASK FORCE DISCLAIM ALL WARRANTIES, EXPRESS OR IMPLIED,
INCLUDING BUT NOT LIMITED TO ANY WARRANTY THAT THE USE OF THE
INFORMATION HEREIN WILL NOT INFRINGE ANY RIGHTS OR ANY IMPLIED
WARRANTIES OF MERCHANTABILITY OR FITNESS FOR A PARTICULAR PURPOSE.

Copyright (C) The Internet Society (2004). (2005). This document is subject
to the rights, licenses and restrictions contained in BCP 78, and
except as set forth therein, the authors retain all their rights.

Acknowledgment

Funding for the RFC Editor function is currently provided by the
Internet Society.