Hi Mario,
Please see my comments below.
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.
Did you also have an implementation of our 6lowpan-ipv6-nd draft ?
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.
Are you saying that you implemented RDA algorithm instead ? How did
you use multicast and controlled flooding at the link-layer(802.15.4)
? Have you
used a simulation or set of real sensors to implement and take measurements?
The main idea of our 6lowpan-nd draft is to minimize the broadcast or all-node
multicast messages to the low-powered nodes in order to save energy while
maintaining the efficiency of the initiating node. Thus we optimize for unicast
messaging and sometimes use the existing algorithm in IPv6 ND - so it should
be simple to implement. The idea could be applicable beyond 6lowpan scenarios,
i.e to any network that wants to run energy-efficient IPv6 ND protocol.
Thanks,
-Samita
===========================
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 PROTECTED]
_______________________________________________
6lowpan mailing list
[email protected]
https://www1.ietf.org/mailman/listinfo/6lowpan
_______________________________________________
6lowpan mailing list
[email protected]
https://www1.ietf.org/mailman/listinfo/6lowpan
