Subject: Re: [6lowpan] Edge router crash, reboot or new edge router

From: Pars Mutaf <[email-masked]>
Date: Sat, 1 Aug 2009 13:38:23 +0300

Hi,

On Mon, Jul 27, 2009 at 3:01 PM, Zach Shelby<[email-masked]> wrote:
> Hi Pars,
>
> Pars Mutaf wrote:
>
>> I believe understand the motivations behind avoiding broadcast NS messages
>> upon incoming session. However, what happens if the whiteboard approach
>> fails
>> i.e. if whiteboard bindings are lost due to edge router crash, reboot
>> or changing
>> the edge router for whatever administrative reason?
>
> This is a good question. As whiteboards have soft state, and nodes refresh
> the addresses they are using periodically, a whiteboard failure is not a
> disaster to the network. If an Edge Router crashes:
>
> 1. If the ER reboots without state - the next NR message will refresh the
> entries. It could be nice if the LoWPAN somehow knew that this happened
> (how?) to avoid waiting up to NR_PERIOD. At least its default route will
> stop working, that is an indication.
>
> 2. If the ER reboots and kept its whiteboard state (recommended) - then of
> course the ER can't forward on behalf of the node while down. Same for any
> router, so this isn't a whiteboard problem.
>
> 3. If the ER goes down permanently, then the node will detect this because
> its default route no longer works or the NR can no longer be sent to the ER.
> It either starts using an alternative ER or continues operating until a new
> ER comes on-line.
>
> In any case the LoWPAN can continue to operate while an ER is down (routing
> within the LoWPAN). In an extended LoWPAN nodes will start using alternative
> ERs automatically. Several techniques could be used by an ER vendor to
> automatically switch state to an alternative ER, use non-volatile memory for
> Whiteboard state, use secondary bindings etc.

Using non-volatile memory would solve the problem perhaps.
Btw, how much information you can store in non-volatile memory?
I think this solution should be explicitly described in the document.
This is a major
difference from standard neighbor discovery which does not require
that neighbor
cache state be stored in non-volatile memory.

And, I am still not sure that this approach is completely reliable,
even with non-volatile
memory. What if, for some reason, the node believes that its address
was registered,
but it is not yet, and incoming packet arrives? This is a race
condition. Standard
neigbor discovery does not have this problem.

In addition, non-volatile memory does not handle the case where the
administrator
wants to change or upgrade the edge router. In this case whiteboard
state would be lost,
all idle nodes would be unreachable for NR_PERIOD which should be long
for preserving
energy. Standard neighbor discovery does not have this problem.

What about the following solution?

1. Use standard neighbor discovery.
2. Increase the number of edge routers,  i.e. decrease the number of
nodes per edge
router. This will very much reduce the rate of incoming sessions from
the Internet
(per edge router)  and hence the rate of broadcast Neighbor Solicitations.
3. Increase the neighbor cache lifetime. This will further reduce the
Neighbor Solicication
rate.

Standard neighbor discovery may induce high neighbor solicitation
signaling cost, yes.
But, this looks like a network management problem to me. Not
necessarily a protocol
design problem.

Regards,

pars

>
> Section 7.9 of nd-04 deals with this partially:
>
> http://tools.ietf.org/html/draft-ietf-6lowpan-nd-04#section-7.9
>
>> A related question: how frequent you believe broadcast NS messages
>> (i.e. incoming
>> sessions) will be in a 6lowpan network? Or, sessions will be mostly
>> initiated by
>> 6lowpan nodes?
>
> We aren't using NS messages at all inside the LoWPAN. Node Registration
> messages are always node initiated.
>
> - Zach
>
>> Regards,
>>
>> pars
>> _______________________________________________
>> 6lowpan mailing list
>> [email-masked]
>> https://www.ietf.org/mailman/listinfo/6lowpan
>
> --
> http://www.sensinode.com
> http://zachshelby.org - My blog “On the Internet of Things”
> Mobile: +358 40 7796297
>
> Zach Shelby
> Head of Research
> Sensinode Ltd.
> Kidekuja 2
> 88610 Vuokatti, FINLAND
>
> This e-mail and all attached material are confidential and may contain
> legally privileged information. If you are not the intended recipient,
> please contact the sender and delete the e-mail from your system without
> producing, distributing or retaining copies thereof.
>

---

From: Pars Mutaf <[email-masked]>
Date: Sat, 1 Aug 2009 13:43:53 +0300

Hi,

Using non-volatile memory would solve the problem perhaps.
Btw, how much information you can store in non-volatile memory?
I think this solution should be explicitly described in the document.
This is a major difference from standard neighbor discovery which does
not require that neighbor cache state be stored in non-volatile memory.

And, I am still not sure that this approach is completely reliable,
even with non-volatile memory. What if, for some reason, the node
believes that its address was registered, but it is not yet, and
incoming packet arrives? This is a race condition. Standard neigbor
discovery does not have this problem.

In addition, non-volatile memory does not handle the case where the
administrator wants to change or upgrade the edge router. In this case
whiteboard state would be lost, all idle nodes would be unreachable for
NR_PERIOD which should be long for preserving energy. Standard neighbor
discovery does not have this problem.

1. Use standard neighbor discovery.
2. Increase the number of edge routers,  i.e. decrease the number of
nodes per edge router. This will very much reduce the rate of incoming
sessions from the Internet (per edge router)  and hence the rate of
broadcast Neighbor Solicitations.
3. Increase the neighbor cache lifetime. This will further reduce the
Neighbor Solicitation rate.

Standard neighbor discovery may induce high neighbor solicitation
signaling cost, yes. But, this looks like a network management problem
to me. Not necessarily a protocol design problem.

Regards,

pars

---

From: Pars Mutaf <[email-masked]>
Date: Mon, 3 Aug 2009 20:08:25 +0300

> stop working, that is an indication.

Idle nodes need to preserve energy, and in order to reduce the bandwidth cost,
NR_PERIOD should be large. In this case, idle nodes will be unreachable
for a long time without knowing it.

If the WG does not prefer standard neighbor discovery, the following solution
comes to mind for handling reboot with loss of state:

When the router boots up and its whiteboard is empty, it periodically
broadcasts an
alert message indicating that all nodes should register within T seconds.

In order to avoid neighbor registration storms, upon receipt of the of
this message, a node should wait a random amount of time between 0 and T seconds
and register. The bandwidth consumed during this period depends on T and the
number of nodes.

This assumes that if whiteboard state is lost, all of them is lost.
This assumption
holds in case of reboot with loss of state, or edge router upgrade.

If NR_PERIOD is much longer than T/2 (average registration time), this will be
advantageous in case of reboot with loss of state. But if T is too
small, there will
be a registration storm.

There is also no guarantee that a node will hear the alert message and
register in time.

This solution can work well if the number of nodes in the subnet is
small. In this case
however, stateless neighbor discovery also can work well without
inducing too much
signaling cost and it perfectly handles loss of state.

> 2. If the ER reboots and kept its whiteboard state (recommended) - then of

I guess here you suggest storing the whiteboard state in non-volatile memory.
This may be clarified in the document. Routers in general store the
routing tables
in volatile memory. OS and configuration files only are stored in non-volatile
memory.

So I guess, reboot with loss of state is not a negligible scenario,
unless explicit
solution in the document.

Regards,

pars

---

From: Zach Shelby <[email-masked]>
Date: Tue, 04 Aug 2009 11:15:40 +0300

Pars,

Sorry it took some time to reply. We are recovering from IETF meeting 
hangover. Thanks a lot for you thought here - you just hit on a point we 
have been wanting to fix. See below.

>> stop working, that is an indication.

Another thing to consider is that Neighbor Discovery is only one part of 
the formula. If you have an ER crash - your routing algorithm (probably 
the DAG root in RPL) has to start from scratch as well.

> for a long time without knowing it.

And this is not a problem, as sleeping nodes can't (not considering 
low-power wakeup of course) be reached anyways.

It is a problem for nodes that stay awake. It would be nice if a node 
that is awake between NR messages figures out that its current primary 
ER is no longer available.

> There is also no guarantee that a node will hear the alert message and

This is an interesting idea. The DT has been playing with the idea of 
allowing an ER or a router to send an unsolicited NC to the network in 
order to tell that it has reset, or that an ER is no longer available.

In ticket #48 (http://trac.tools.ietf.org/wg/6lowpan/trac/ticket/48) we 
already propose a status "Please re-register" for an NC that a router 
can send to a node. If we let this be sent from any ER or router then it 
serves the purpose above well. The random delay could be between 0 and 
(NR_PERIOD + NR_PERIOD/2) to keep the average as you suggest.

> signaling cost and it perfectly handles loss of state.

The reason we don't use RFC4861 is not just because of state. It just 
doesn't work with non-transitive links where nodes are mostly sleeping. 
RFC4861 was designed for Ethernet-like links.

> in volatile memory. OS and configuration files only are stored in non-volatile

This is an implementation issue, I just used it as an example. We should 
not expect that a router is able to do this in the protocol design.

> solution in the document.

Thanks!
Zach

Zach Shelby
Head of Research
Sensinode Ltd.
Kidekuja 2
88610 Vuokatti, FINLAND