Subject: [6lowpan] congestion of responses to multicast RS query from an ND host

From: Yoav Ben-Yehezkel <[email-masked]>
Date: Sun, 26 Sep 2010 14:32:38 +0200

Hi,

I have a question on 6LoWPAN-ND. I tried looking for this issue in the
mailing list, but couldn’t find anything on this.

Does the WG see a need for some kind of regulation of RA responses to host
multicast of a RS query in 6LoWPAN-ND? Unless regulated, in a large and
dense networks, this could cause excessive traffic for a meaningful period
of time.

Best regards,

Yoav

---

From: Robert Cragie <[email-masked]>
Date: Sun, 26 Sep 2010 15:44:48 +0100

Hi Yoav,

There is already a mechanism specified in rfc4861 to randomize the 
transmission of RAs - see section 6.2.6. This would apply to 6lowpan-nd 
as well. The downside of this approach is the lengthening of the whole 
RS/RA procedure.

Robert

Robert Cragie (Pacific Gas & Electric)

Gridmerge Ltd.
89 Greenfield Crescent,
Wakefield, WF4 4WA, UK
+44 1924 910888
+1 415 513 0064
http://www.gridmerge.com <http://www.gridmerge.com/>

On 26/09/2010 1:32 PM, Yoav Ben-Yehezkel wrote:
> Does the WG see a need for some kind of regulation of RA responses to 
> host multicast of a RS query in 6LoWPAN-ND? Unless regulated, in a 
> large and dense networks, this could cause excessive traffic for a 
> meaningful period of time.
>
> Best regards,
>
> Yoav
>
>
> _______________________________________________
> 6lowpan mailing list
> [email-masked]
> https://www.ietf.org/mailman/listinfo/6lowpan

---

From: Yoav Ben-Yehezkel <[email-masked]>
Date: Sun, 26 Sep 2010 17:31:40 +0200

Thanks Robert,

I am guessing you are referring to the MAX_RA_DELAY_TIME  .5 seconds?

The problem I am thinking about goes a little beyond this randomization…

The way I see it, in LLNs hidden nodes are a common case, so if two
responding routers are not within direct connectivity, their packets will
collide if randomization resolution is too small. Unless the randomization
resolution is not in the order of magnitude of L2 frame transmissions
(including overheads such as preambles, backoffs, etc.) their packets are
very likely to collide.

This is why I am concerned with the value of 0.5 seconds being a little
small, and also wonder whether defining the resolution of the randomization
is important for 6LoWPAN-ND.

Trying to illustrate below.

Consider the following topology:

R1 --> H <-- R2

        +----+

Query:  | RS |

        +----+

               +--------+

R1 Resp:       |   RA1   |

               +--------+

                 +---------+

R2 Resp:         |   RA2   |

                 +---------+

        ---------------------------------->t

Above you see the responses collide, even though R1 and R2 randomized a
different value, because their L2 could not separate their transmissions (as
they cannot hear each other).

Had the randomization was using resolution at least the size of the response
packet and R1 and R2 randomized two different values, the collision would
have been avoided.

Of course in realistic large and dense networks, you’re likely to see more
than two routers respond, which may escalate the problem.

I hope this better clarifies my concern.

Thanks,

Yoav

*From:* Robert Cragie [mailto:[email-masked]]
*Sent:* Sunday, September 26, 2010 4:45 PM
*To:* Yoav Ben-Yehezkel
*Cc:* 6lowpan
*Subject:* Re: [6lowpan] congestion of responses to multicast RS query from
an ND host

Hi Yoav,

There is already a mechanism specified in rfc4861 to randomize the
transmission of RAs - see section 6.2.6. This would apply to 6lowpan-nd as
well. The downside of this approach is the lengthening of the whole RS/RA
procedure.

Robert

Gridmerge Ltd.
89 Greenfield Crescent,
Wakefield, WF4 4WA, UK
+44 1924 910888
+1 415 513 0064
http://www.gridmerge.com

Hi,

Best regards,

Yoav

6lowpan mailing list

[email-masked]

---

From: "Colin O'Flynn" <[email-masked]>
Date: Sun, 26 Sep 2010 18:00:17 +0200

Hi Yoav,

This depends greatly on the L2 characteristics. As the RA is sent unicast
you could rely on L2 delivery, for example 802.15.4 ACKs.

For the 6lowpan-ND you don't need to receive every reply anyway though. You
just need one router that connects to the prefix you want, so in a dense
network you may have more collisions, but you should also have enough
successes that it doesn't matter. 

Note that in 6lowpan-nd-13 MAX_RA_DELAY_TIME is redefined to 2 seconds by
default, which in terms of most link layers a very long time!

I think it's best to leave the random delay granularity as define in
RFC4861: something implementation defined. There is an unknown processing
delay between receiving the RS and internally generating/queuing the RA.
Thus even if you use a random granularity that matches the L2 packet length,
you could still have collisions. And if two nodes have both sent a RA this
again all goes out the window.

And I don't think anything would stop an extension of 6lowpan-ND being added
in the future using for example something like the trickle timer for sending
RA's, where if nodes see a lot of other routers advertising it doesn't send
its own RA. Or adjusting power of sending RS to solicit fewer responses,
etc. But I think these should remain optimizations that can be explored only
if required in dense networks, and keep 6lowpan-nd as simple as possible.

Regards,

  -Colin

From: [email-masked] [mailto:[email-masked]] On Behalf
Of Yoav Ben-Yehezkel
Sent: September 26, 2010 5:32 PM
To: [email-masked]
Cc: 6lowpan
Subject: Re: [6lowpan] congestion of responses to multicast RS query from an
ND host

Thanks Robert,

The problem I am thinking about goes a little beyond this randomization.

R1 --> H <-- R2

        +----+

Query:  | RS |

        +----+

               +--------+

R1 Resp:       |   RA1   |   

               +--------+

                 +---------+

R2 Resp:         |   RA2   |

                 +---------+

Of course in realistic large and dense networks, you're likely to see more
than two routers respond, which may escalate the problem.

Thanks,

Yoav

From: Robert Cragie [mailto:[email-masked]] 
Sent: Sunday, September 26, 2010 4:45 PM
To: Yoav Ben-Yehezkel
Cc: 6lowpan
Subject: Re: [6lowpan] congestion of responses to multicast RS query from an
ND host

Hi Yoav,

Robert

Gridmerge Ltd.
89 Greenfield Crescent,
Wakefield, WF4 4WA, UK
+44 1924 910888
+1 415 513 0064

Hi,

I have a question on 6LoWPAN-ND. I tried looking for this issue in the
mailing list, but couldn't find anything on this.

Best regards,

Yoav

---

From: Yoav Ben-Yehezkel <[email-masked]>
Date: Sun, 26 Sep 2010 18:12:54 +0200

Thanks Colin,

Your points below indeed cover my concerns.

Regards,

Yoav

*From:* Colin O'Flynn [mailto:[email-masked]]
*Sent:* Sunday, September 26, 2010 6:00 PM
*To:* 'Yoav Ben-Yehezkel'; [email-masked]
*Cc:* '6lowpan'
*Subject:* RE: [6lowpan] congestion of responses to multicast RS query from
an ND host

Hi Yoav,

For the 6lowpan-ND you don’t need to receive every reply anyway though. You
just need one router that connects to the prefix you want, so in a dense
network you may have more collisions, but you should also have enough
successes that it doesn’t matter.

I think it’s best to leave the random delay granularity as define in

And I don’t think anything would stop an extension of 6lowpan-ND being added
in the future using for example something like the trickle timer for sending
RA’s, where if nodes see a lot of other routers advertising it doesn’t send
its own RA. Or adjusting power of sending RS to solicit fewer responses,
etc. But I think these should remain optimizations that can be explored only
if required in dense networks, and keep 6lowpan-nd as simple as possible.

Regards,

  -Colin

*From:* [email-masked] [mailto:[email-masked]] *On
Behalf Of *Yoav Ben-Yehezkel
*Sent:* September 26, 2010 5:32 PM
*To:* [email-masked]
*Cc:* 6lowpan
*Subject:* Re: [6lowpan] congestion of responses to multicast RS query from
an ND host

Thanks Robert,

R1 --> H <-- R2

        +----+

Query:  | RS |

        +----+

               +--------+

R1 Resp:       |   RA1   |

               +--------+

                 +---------+

R2 Resp:         |   RA2   |

                 +---------+

Thanks,

Yoav

Hi Yoav,

Robert

Gridmerge Ltd.
89 Greenfield Crescent,
Wakefield, WF4 4WA, UK
+44 1924 910888
+1 415 513 0064
http://www.gridmerge.com

Hi,

Best regards,

Yoav

6lowpan mailing list

[email-masked]

---

From: Robert Cragie <[email-masked]>
Date: Sun, 26 Sep 2010 18:20:37 +0100

It's probably also worth mentioning that it is legitimate to do a 
unicast RS if the destination address can be appropriately 
autoconfigured from the link layer address. The link layer address would 
have been found by some L2 management mechanism, e.g. 802.15.4 scanning. 
This would shorten the join time as well.

Robert

Gridmerge Ltd.
89 Greenfield Crescent,
Wakefield, WF4 4WA, UK
+44 1924 910888
+1 415 513 0064

On 26/09/2010 5:12 PM, Yoav Ben-Yehezkel wrote:
> *From:* Colin O'Flynn [mailto:[email-masked] 
> <mailto:[email-masked]>]
> <mailto:[email-masked]>
> *Cc:* '6lowpan'
> *Subject:* RE: [6lowpan] congestion of responses to multicast RS query 
> from an ND host
>
> Hi Yoav,
>
> This depends greatly on the L2 characteristics. As the RA is sent 
> unicast you could rely on L2 delivery, for example 802.15.4 ACKs.
>
> For the 6lowpan-ND you don’t need to receive every reply anyway 
> though. You just need one router that connects to the prefix you want, 
> so in a dense network you may have more collisions, but you should 
> also have enough successes that it doesn’t matter.
>
> Note that in 6lowpan-nd-13 MAX_RA_DELAY_TIME is redefined to 2 seconds 
> by default, which in terms of most link layers a very long time!
>
> RFC4861: something implementation defined. There is an unknown 
> processing delay between receiving the RS and internally 
> generating/queuing the RA. Thus even if you use a random granularity 
> that matches the L2 packet length, you could still have collisions. 
> And if two nodes have both sent a RA this again all goes out the window.
>
> And I don’t think anything would stop an extension of 6lowpan-ND being 
> added in the future using for example something like the trickle timer 
> for sending RA’s, where if nodes see a lot of other routers 
> advertising it doesn’t send its own RA. Or adjusting power of sending 
> RS to solicit fewer responses, etc. But I think these should remain 
> optimizations that can be explored only if required in dense networks, 
> and keep 6lowpan-nd as simple as possible.
>
> Regards,
>
>   -Colin
>
> *From:* [email-masked] <mailto:[email-masked]> 
> [mailto:[email-masked] <mailto:[email-masked]>] 
> *On Behalf Of *Yoav Ben-Yehezkel
> *To:* [email-masked] <mailto:[email-masked]>
> *Cc:* 6lowpan
> *Subject:* Re: [6lowpan] congestion of responses to multicast RS query 
> from an ND host
>
> Thanks Robert,
>
> I am guessing you are referring to theMAX_RA_DELAY_TIME  .5 seconds?
>   
>
> responding routers are not within direct connectivity, their packets 
> will collide if randomization resolution is too small. Unless the 
> randomization resolution is not in the order of magnitude of L2 frame 
> transmissions (including overheads such as preambles, backoffs, etc.) 
> their packets are very likely to collide.
>
> This is why I am concerned with the value of 0.5 seconds being a 
> little small, and also wonder whether defining the resolution of the 
> randomization is important for 6LoWPAN-ND.
>
> Above you see the responses collide, even though R1 and R2 randomized 
> a different value, because their L2 could not separate their 
> transmissions (as they cannot hear each other).
>
> Had the randomization was using resolution at least the size of the 
> response packet and R1 and R2 randomized two different values, the 
> collision would have been avoided.
>
> Of course in realistic large and dense networks, you’re likely to see 
> more than two routers respond, which may escalate the problem.
>
> *From:* Robert Cragie [mailto:[email-masked] 
> <mailto:[email-masked]>]
> *Subject:* Re: [6lowpan] congestion of responses to multicast RS query 
> from an ND host
>
> Hi Yoav,
>
> transmission of RAs - see section 6.2.6. This would apply to 
> 6lowpan-nd as well. The downside of this approach is the lengthening 
> of the whole RS/RA procedure.
>
> Robert
>
> [email-masked]  <mailto:[email-masked]>