Hi Chakrabarti,
Thanks for you feedback.
> Did you also have an implementation of our 6lowpan-ipv6-nd draft ?
We don't implement 6lowpan-ipv6-nd draft. Actually, we did consider the
6lowpan-ipv6-nd method carefully when designing. However, after evaluation, we
considered there are some problem to implement it. For example,
Code space limitation: the MCU we use have around 27k free for Adaptation
Layer, IPv6/ND, TCP/UDP and application. Full implementation of 6lowpan-ipv6-nd
(especial address resolution) will need a lot of code space, normal sensor node
couldn't afford it.
Another, there still needs some other mechanism beyond draft's definition, as
an instance, see section 5.1,
"In a mesh topology, when such a packet is received by a co-ordinator, it will
look at the IPv6 header and if that is destined to the all-routers IPv6
multicast address, then it will relay that packet (without decrementing the
IPv6 hop limit) to its co-ordinator. This will deliver the RS towards the PAN
co-ordinator."
When mesh delivery, medi-node need to check the IPv6 header to decide how to
forward frames. There must be more code to implement such a adaptation-layer
route algorithm and make adaptation-layer too complex. Moreover, how about the
IPv6 header compression, should every medi-node do the header decompression
before deciding how to forward a frame?
At last, there are some assumptions like "PAN co-ordinator is also the IPv6
router", in the mail before, I describe the reason why we can't accept it
(multiple sink scenario). So, we have to give up 6lowpan-ipv6-nd and try to
find another way.
> 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?
Yes, real sensors work in our environment. The multicast and controlled
flooding have been given out some days before, that's also the reason why we
have the "B" bit argument recently. Please see it below, I cut it from the
previous mail (there are some change, but main idea is stable).
Router = co-ordinator
===========================
The flooding way is simple: all IP packet with multicast destination address
will
be encapsuled in an adaptation Broadcast Frame. However, the format of
adaptation Broadcast Frame is somewhat different from the standard header
format. The modified format showed below.
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
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| LF| prot_type |M|B| rsv |Payload (or MD/Broadcast Hdr)...
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
As the figure showed, a "B" bit is added(replacing one rsv bit). When the "B"
bit is set, a Broadcast Field will be included in the frame immediately
following
the LoWPAN header. If there is a Broadcast Field, we will call the
adaptation frame as a Broadcast Frame. The "Broadcast" field is defined as
follows
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
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
|S|Broad Radius |Sequence Number|Source Address, followed by...
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
S: 0 if use EUI-64 address, or 1 if use 16-bit address.
Broad Radius: Broadcast Radius, 7 bits, should be decrement by each
broadcast relay node, if it is decremented to 0, discard the frame.
Sequence Number: A 8-bit number to identify different Broadcast Frame from
the same source node. The originator will increment the field after each
sending.
Source Address: The Originator's MAC address.
With the support of the "Broadcast" field, an originator or a relay node will
send the Broadcast Frame like that: first, deliver the frame to all Pan
Coordinator
and Routers around using MAC broadcast(with the MAC destination address
set to 0xFFFF, just need broadcast once), then, if there are End Devices in
the node's neighbor table, unicast the frame to them one by one. Besides, to
avoid broadcast storm, a Broadcast Record Table will be needed. The table will
record the Source Address and Sequence Number in "Broadcast" field of each
received Broadcast Frame after re-broadcasting it first(End Device don't need
to re-broadcasting). Sequentially, a Broadcast Valid Time will be initialized
for
the newly added Broadcast Record Entry. Then, before the entry is timed out
(Broadcast Valid Time is decremented to 0), all Broadcast Frame with the same
Source Address and Sequence Number should be discarded but not relayed.
================================
Best Regards,
Mario Mao
[EMAIL PROTECTED]
----- Original Message -----
From: "Samita Chakrabarti" <[EMAIL PROTECTED]>
To: "Mario Mao" <[EMAIL PROTECTED]>
Cc: <[email protected]>
Sent: Monday, November 06, 2006 7:09 AM
Subject: Re: [6LoWPAN] Router Dynamic Advertisement Algorithm (RDA)
> 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
