Subject: [6LoWPAN] Router Dynamic Advertisement Algorithm (RDA)

From: Mario Mao <[email-masked]>
Date: Mon, 30 Oct 2006 14:47:52 +0800

Hi all,

By confirming with Gabriel, I would update some results of our team's work on 6LoWPAN, please take it as a reference and give any comment needed, thanks.

Basically, our team's work follows drafts prompted by WG. however, we find something should be included when implementing. Below is one of the things beyond draft: Router Dynamic Advertisement Algorithm (RDA). 

For Chakrabarti, I know it is a really different way from the optimization in draft 6lowpan-ipv6-nd. But when we design and implement the 6LoWPAN stack, we did find it is effective and easier to implement. Hope the idea in this mail could do some help, thanks.

===========================

Router Discovery, Prefix and Parameter Discovery need RS and RA message defined in NDP. In LoWPAN environment, we need avoid the power consuming caused by broadcasting these kinds of message periodically. On the other hand, it is not a good idea to simply increase the announcement interval to a large value. It would make the network insensitive and lead some child nodes inaccessible before they could configure a ipv6 global address. To balance them, Host and Router use Router Dynamic Advertisement Algorithm (RDA) to send RS and RA.

1. Assumption

In our environment, we don't conside IPv6 routers would be known by all sensor nodes before they get their announcement explicitly. This consideration would work for multiple sink scenario. There could be more than one sink (router) to balance the load around sink (router). So, Host need to send Mulitcast RS or wait for RA.

To support IP multicast, broadcast ability in adaptation layer should be included. We have introduced a controlled flooding mechanism to supply such kind of requirment. You could get the mean idea in the mail before, I remember I have sent it to mail list about 3 months ago.

At last, there will be a little change to RFC2461 on the RA announcement interval, not more, but do have. Will it be a big problem? Our implementation support both the two way of RA sending algotithm in a single Router, one for standard, one for LoWPAN. People could confiure interface to use any of them, that means, no conflict between two different links, eg. standard for Ethernet and RDA for IEEE 802.15.4. Our test show the Route and Host would work fine when enable two advertising interfaces which use different advertising algorithm.

2. Host

When Host starts up, it hold the initial multicast RS until TIME_WAIT_FOR_RA elapseed. If Host still miss the wanted RA, a multicast RS should be sent out. For TIME_WAIT_FOR_RA, it is a random value between BASE_RA_INTERVAL and 2*BASE_RA_INTERVAL. Another, the source address of RS should use unicast address but not ::, that make Router could unicast the RA message back to Host. 

For application that want immediate access to every sensor node, TIME_WAIT_FOR_RA could use another smaller value which let RA received quickly. However, for most WSN applications that haven't such kind of requirement, 10 - 20 minutes wait time may acceptable.

3. Router

Route would no longer use a relatively fixed interval to send Unsolicited RA. As soon as one interface of Router is confiured as an Advertising Interface, the interval of sending RA would be calculated by RDA. The constants and variables maintained as follow:

    BASE_RA_INTERVAL: the basal interval of sending RA, recommended value is 10min.
    MAX_RA_FACTOR: the maxium RA factor, recommended value is 5-6.
    a: RA factor.
    interval: current RA interval.
    timeToAdv: the time to sending next RA.
    sendTimes: the times of sending RA using the same interval.
    recvRSTimes: the times of receiveing RS packet between two unsolicited RA.

The algorithm comes below, the basic idea is increasing the advertising interval to long when topology is stable and decreasing to short when the network become wavy:

(1). When advertising interface initializes, let a = 0,interval = BASE_RA_INTERVAL*2^a,sendTimes = a+1,recvRSTimes = 0,timeToAdv = interval.

(2). 
- (a) When interval time elapsed (that means timeToAdv is decreased to 0), send a Multicast Unsolicited RA and let recvRSTimes = 0;
- (b) If sendTimes > 0 and a < MAX_RA_FACTORIAL, substracte sendTimes by 1; if sendTimes is decreased to 0, let a = a+1 and recalculate sendTimes with the formula in (1);  
- (c) Recalculate interval with the formula in (1), let timeToAdv = interval, wati for sending next RA.

(3). 
- (a) If Router received a valid RS, let a = a/2, recvRSTimes = recvRSTimes+1, sendTimes = a+1;
- (b) Recalculate current timeToAdv: if a is even before receiving RS, let timeToAdv = timeToAdv/2^a [see annotation 1]; if it is odd, let timeToAdv = timeToAdv/2^(a+1) [see annotation 2];
- (c) if recvRSTimes < 3, send Unicast Solicited RA with the way defined in RFC2461; if recvRSTimes = 3, let timeToAdv = 0, send a Multicast Solicited RA immediately and carry out all relative operation in (2); if recvRSTimes > 3, nothing else need to do (it is possible Router receive a new RS before the scheduled RA sending out, so just let Hosts wait for the scheduled Multicast RA).

[Annotation 1]
timeToAdv = timeToAdv * (newInterval / oldInterval)
                = timeToAdv * (BASE_RA_INTERVAL*2^a / BASE_RA_INTERVAL*2^(2a) )
                = timeToAdv * 2^(-a)
                = timeToAdv / 2^a
[Annotation 2]
timeToAdv = timeToAdv * (newInterval / oldInterval)
                = timeToAdv * (BASE_RA_INTERVAL*2^a / BASE_RA_INTERVAL*2^(2a+1) )
                = timeToAdv * 2^(-(a+1))
                = timeToAdv / 2^(a+1)

When advertising interface use RDA, Host will not send RS but wait for possible RA when it startup. If it get nothing within TIME_WAIT_FOR_RA, a RS would be sent out to solicit RA. This process could reduce the broadcast flow of RS when Hosts bootstrap. Meanwhile, Router would send multicast RA with a small interval at the begining and increase the sending interval gradually. That could satisfy the requirement for RA from Host when 802.15.4 nodes constructing network. For TIME_WAIT_FOR_RA is a random value between BASE_RA_INTERVAL and 2*BASE_RA_INTERVAL, it is highly possible that most of the Hosts needn't to send RS when nodes in the same PAN start to construct network topology. After the topology has been stable (most of nodes have joined into the PAN), interval of RA will increase to a large value which alleviate the energy wastage by broadcasting RA message frequently.

When the network become unstable (eg. some nodes lose synchronization with beacon, they would start orphan scan and try to re-join the network. At this time, node might need to request a new RA message for address autoconfiguration) or new node try to join PAN, Host would send RS to Router. Router answer the solicitation with Unicast RA and reduce RA interval exponentially to response the change of network rapidly. If the PAN is suffering a serious undulation (eg. a parent node with several children or grandchildren failed, all of children need to re-join the network. The result of this scenario is lots of RS messages appearing on the channel), Router response this situation by sending a Multicast RA immediately as soon as more than 3 RS received between two adjacent unsolicited RA. Now, RA factor and RA interval have decreased to small value, Router begin to send RA frequently and enters a fast advertising period to accommodate the change of network.

When network topology comes stable after gone through the wavy period, RA interval would increase again with the RA factor. At last, it reachs a large enough value and enters the slow advertising period.

Below table show the change of RA interval (BASE_RA_INTERVAL = 10 min,MAX_RA_FACTOR = 6). RA interval will increase to 10.3h if the network topology stays stable (it is also the character of WSN: topology wouldn't take frequent change after the initial network organization). Such a long interval only take little negative effect to the power consumption.
=====================================================
a    interval   sendTimes   Time to achieve the intvl
0    10m          1                 0
1    20m          2                 10m
2    40m          3                 50m
3    80m          4                 2.8h
4    160m         5                 8.2h
5    320m         6                 21.5h
6    640m         7                 53.5h
=====================================================

Regards,

Mario Mao
[email-masked]

_______________________________________________
6lowpan mailing list
[email-masked]
https://www1.ietf.org/mailman/listinfo/6lowpan