Subject: Re: [6lowpan] format document issues

From: Samita Chakrabarti <[email-masked]>
Date: Wed, 12 Oct 2005 13:22:51 -0700 (PDT)

Hi Gabe,

Please see my comments below.

> There is no mention of the link-layer source address changing on a hop-by-hop
> basis, only the destination address does so. So at each intermediate node, as 
well
> as at the final destination, what is known is the link-layer source address.
> What is not known is the link-layer address of the preceding hop, so a node
> knows who originated the packet it just received, but it does not know which
> node finally delivered it to it. In AODV/LOAD this is the "reverse route 
address".
> But of course, routing protocols like AODV or LOAD don't use the M bit, they 
have
> originator and destination address fields within the RREQ. This usage of only 
one
> extra address field is something I saw in 802.11 (although they do have the 
> capability of using two extra fields).
> 
> Hopefully, this clarifies the handling rules. Perhaps it's a good idea to 
state clearly
> that
> the source address does not change hop-by-hop. The main question is: are there 
any
> issues with this? It saves one address field, but are there any issues?  

Normally, in IP-routing, the ethernet (link-layer) source address is changed
at each hop and the link-layer destination address is set according to the
next-hop IP address. Thus, the link-layer chooses its source interface MAC
address at each hop while the IP-packet contains the orginal source address.

Since we are now doing something new here - i,e. route at the link-layer,
we still need to somehow know where the packet came from, i.e. the last
sender or forwarder's link-layer address. IEEE802.15.4 has ACK frames, during
data transfer, it may require a ACK from the next hop - how does the nexthop 
know
where data packet came from ?  How does it inform any error to the immediate
sender if it does not know its link-layer address?

Moreover, the previous hop may depend on receiving ACK to determine if a forward
link is broken. Thus the link-layer frame _should_ have the correct src and
dst address. That's why I mentioned in my last mail about a solution that
maps the 'reverse route' mentioned in RFC3561.

RFC3561 mentions:
The intermediate node also updates its route table entry
   for the node originating the RREQ by placing the next hop towards the
   destination in the precursor list for the reverse route entry --
   i.e., the entry for the Originator IP Address field of the RREQ
   message data.

In our case, the AODV packet in the data section will have the originator
link-layer address, thus at each intermediate node, upon RREQ, it sets
a  reverse route as following ( addresses are link-layer addresses):
 
   DEST         next hop          SEq#
  
  Originator    previous-node     originator's seq#

 This way, we can use reverse route *towards* the originator link-layer address.
 It is the same way one does at the IP-layer. The only difference here is that
 we must know our last link-layer sender's address.
 
 BTW, reverse routes are better explained in RFC3561 than in aodvbis.
 
 Thus, the format document can save one address field (for originator source
 link-layer addr) by requiring the routing protocol to provide information
 on originator address so that the intermediate node can setup reverse route.
 Alternately, the intermediate node will have to do route-discovery for the
 originator - that is certainly not effecient.
 Hope this clarifies the point.
 
 Thanks,
 -Samita

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

---

From: gabriel montenegro <[email-masked]>
Date: Wed, 12 Oct 2005 18:02:10 -0700 (PDT)

Samita,

I *think* we're repeating each other. From my post:

> But of course, routing protocols like AODV or LOAD don't use the M bit, 
> they have
> originator and destination address fields within the RREQ.

So we don't even have to require "the routing protocol to provide information
on originator address so that the intermediate node can setup reverse route."
The required info is already in the RREQ, right? 

-gabriel

---

From: "Ki-Hyung Kim" <[email-masked]>
Date: Fri, 14 Oct 2005 00:40:47 +0900

Sorry for this late reply on this issue about the source address compression
in multi-hop environment.
After raising this issue in August, our research group has studied on the
reporting of RERRs to the originators without a source address and a
precursor list.
The purpose of the research is to search a light weight RERR reporting
scheme without putting a source address in the format and maintaining
precursor lists on routing tables of every nodes.

If I say the conclusion first, the source address is at least not required
in the 6lowpan format for reporting RERRs to the originators. 

In AODV, every intermediate node on a routing path keeps a precursor list on
each routing entry for a destination. The setting up of the precursor list
is done when processing RREQ and RREP.
Thus, data packets do not need to have the originator address in AODV.

What about 6lowpan?
If a routing scheme of 6lowpan maintains precursor lists for routing as AODV
does, data packets at least do not need to have the originator address.
This issue could be handled in the routing documents.

Currently, we have submitted a paper to a conference about the RERR
reporting schemes.
In the paper, we have proposed and evaluated several RERR reporting schemes
including 1) unicasting a RERR back in one-hop only, 2) broadcasting
backward a RERR in one-hop only, 3) broadcasting backward based on the
routing table information, 4) using precursor lists, and 5) using the
originator address if it is assumed to be added to the 6lowpan format
document.

In the preliminary performance evaluation result, (1) has shown the best
result, and then (4) comes next in terms of the communication throughput.
Also (1) showed the minimal implementation complexity.

The detailed description of the schemes and performance results shall be
shown shortly.

--
Ki-Hyung Kim 
Associate Professor
Division of Information and Computer Eng., Ajou University
Wonchun-Dong, Yeongtong-Gu, Suwon, Korea 442-749
Tel: +82-31-219-2433, Cel: +82-17-760-2551,  Fax: +82-31-219-1811
http://ilab.ajou.ac.kr/kkim86/index.htm  

> -----Original Message-----
> From: [email-masked] [mailto:[email-masked]] On Behalf
> Of gabriel montenegro
> Sent: Thursday, October 13, 2005 10:02 AM
> To: Samita Chakrabarti; [email-masked]; itijibox-
> [email-masked]
> Cc: [email-masked]
> Subject: Re: [6lowpan] format document issues
> 
> Samita,
>

---

From: gabriel montenegro <[email-masked]>
Date: Thu, 13 Oct 2005 09:51:57 -0700 (PDT)

Prof Kim,

This is great: results! 

Q1: Are these experimental or simulation results?

Q2: Did you use the handling rules as per the draft, or did you modify the link-layer 
    source address at every hop, as implied by your post a while back?

-gabriel

---

From: "Ki-Hyung Kim" <[email-masked]>
Date: Fri, 14 Oct 2005 02:33:07 +0900

Please look at the replies below.
> From: gabriel montenegro [mailto:[email-masked]]
> Sent: Friday, October 14, 2005 1:52 AM
> To: Ki-Hyung Kim; 'Samita Chakrabarti'; [email-masked]
> Cc: [email-masked]
> Subject: RE: [6lowpan] format document issues
> 
> Prof Kim,
> 
> This is great: results!
> 
That is simulation results.
About the Q1:
Currently, we are implementing the formatting document and LOAD on a sensor
platform.
After finishing the implementation, the experimental results will be
available.

> Q2: Did you use the handling rules as per the draft, or did you modify the
> link-layer source address at every hop, as implied by your post a while
back?
I didn't change anything of the format document on the simulation. Also the
link-layer source address is changed at every hop as everybody expected.

> > > >  Thus, the format document can save one address field (for
> originator
> > > source
> > > >  on originator address so that the intermediate node can setup
> reverse
> > > route.
> > > >  Alternately, the intermediate node will have to do route-discovery
> for
> > > the

---

From: gabriel montenegro <[email-masked]>
Date: Thu, 13 Oct 2005 11:31:02 -0700 (PDT)

thanks, comment below...

> link-layer source address is changed at every hop as everybody expected.

As I explained before, this departs from the handling rules in the format draft.
According to those rules (I won't send them again), the source address does not
change hop-by-hop. The assumption is that if an intermediate node wants to send an 
RERR to its previous hop, it would do a reverse forwarding decision. To be clear,
if multiple paths were kept, presumably an intermediat node would have more than one
reverse path to the originator of a message. In this case, it is not clear to which of
the possible predecessors should the RERR be sent. Perhaps to all of them, which costs
a bit more.

You say that the "link-layer source address is changed at every hop as everybody
expected".

One conclusion is that given that this contradicts the current handling rules, then it is

clear that they need to be clarified by explicitly mentioning that no such thing is done.

Another possible conclusion of your "as everybody expected" is that between these
choices:

a) link-layer source address is changed at every hop
b) link-layer source address is not changed at every hop

the draft has obvioiusly made the wrong choice in going with "b". You have verified that
having only one link-layer source address (the one in the 802.15.4 header)
works under handling rule "a". Have you also evaluated under handling rule "b" in order
to compare
both? Or is "b" obviously wrong for some reason?

-gabriel

---

From: "Ki-Hyung Kim" <[email-masked]>
Date: Fri, 14 Oct 2005 04:39:49 +0900

Hi Gabriel,
Please see the comments below.

> Sent: Friday, October 14, 2005 3:31 AM

I have looked at your description about the handling rules of the format
right before.
(Sorry, I had no time to look at the mailing list in these days.)
I believe that (a) is right because it is MAC address. I have also double
checked it by the packet sniffer of IEEE802.15.4. That is, (b) is not
correct.

---

From: "Ki-Hyung Kim" <[email-masked]>
Date: Fri, 14 Oct 2005 04:59:38 +0900

Hi Samita,

> Of Samita Chakrabarti
> Sent: Thursday, October 13, 2005 5:23 AM
> To: [email-masked]; [email-masked];
> [email-masked]
> Cc: [email-masked]
> they

I want to clarify about reporting RERR to the originator in AODV.

AODV does not rely on the reverse route path for reporting RERR to the
originator even though it could.
Moreover, the reverse route path in the routing table could not be used for
unicasting back a RERR in 6lowpan because a data packet does not contain the
originator address.
That is, even though a routing table contains a reverse route to the
originator, the route could not be found by just looking at a data packet.

Instead of the reverse route, AODV uses a precursor list attached on the
routing entry for the unreachable destination. The list contains neighbor
nodes in previous hop. Also, AODV could even utilize a reverse route path to
the originator instead.

The precursor list was set up when a node processing a RREQ and a RREP.
If the list contains a neighbor, the upstream node just unicasts a RERR to
the neighbor (that is, previous hop node). Otherwise, if the list has
multiple neighbors, the node may broadcast a RERR or unicast a RERR
one-by-one to each neighbor.

The precursor list might be utilized in 6lowpan also for the RERR reporting,
but have to pay some expense for maintaining it.
That is one of the reasons why we are trying to find alternate lightweight
solutions in 6lowpan.