Subject: [6lowpan] Re: MultiHop Format document issues

From: Samita Chakrabarti <[email-masked]>
Date: Fri, 14 Oct 2005 13:53:29 -0700 (PDT)

> >   Q1: What is meant by 'used for adhoc or mesh routing' ?  I assume that it
> >   means M bit is used for both control and data path for multihop routing -
> >   is it correct?
> 
> It's meant for data delivery. You would run your favorite mesh protocol
> (aodv, dymo, olsr, etc) without using the 'M' bit, cuz these go hop-by-hop.
> One could think of ways in which one could run them even with an 'M' bit
> on, but this is perhaps more for discussion f2f.

For RREQ forward path M bit is not necessary, because all nodes use bcast.
For RREP from destination to the original sender, it might be useful
it seems.[ when AODV runs on link-layer] 

> >   It seems if we can come up with a IEEE address format for lowpan, then
> >   it can be compressed easily over a LowPAN network to include both
> >   originator address and final address.
> 
> I don't think we have the charter to define layer 2 addressing. Besides,
> I don't see the point, cuz if a PAN is using 16-bit (short) addresses
> as per 802.15.4, they would take much less space. Might as well use that.
> 
> >   

Are we re-thinking of IPv6-address format ( the low 64bit part) as well ?
fe80:0:0:<pan-id>::<16bit-addr>?

> >   ----------------------------------------
> >   9.  Packet Delivery in a Link-Layer Mesh
> > 
> >  A device that wishes
> >    to send a packet may, in such cases, use other intermediate devices
> >    as forwarders towards the final destination.  In order to achieve
> >    such packet delivery using unicast, it is necessary to include the
> >    final destination in addition to the hop-by-hop destination.  This
> >    final destination may be expressed either as a layer 2 or as an IP
> >    (layer 3) address.
> >    
> >    In the latter case, there is no need to provide any additional header
> >    support in this document (i.e., at the sub-IP layer).  The link-layer
> >    destination address points to the next hop destination address while
> >    the IP destination address points to the final destination (IP)
> >    address (that may be multiple hops away from the source).  Thus,
> >    while forwarding data, the single-hop destination address changes
> >    hop-by-hop pointing to the "best" next hop, while the destination IP
> >    address remains unchanged.
> > ----------------------------------------------   
> >    Does the above paragraph mean we could have M bit set and final 
destination
> >    address could be a 16 byte IPv6 address?  
> 
> Hmm... In the spec as it is now, it could be either a 64-bit address
> or a 16-bit (not byte) address. Only the 64-bit address is fully specified
> in the draft. I'll try to get 16-bit in by the deadline.
> 
> >    I wonder why do we need IPv6 address
> >    in M bit case? Shouldn't the final IP destination be extracted from the
> >    IPv6 header in the payload?  Not sure, what it means by 'any additional
> >    header support'.
> >    
> >    I wonder what is the need for supporting a L3 address in final 
destination
> >    field (when it talks about packet delivery in the link-layer)?
> 
> No need, and this is not what's done in the spec. I see that the above text is
> confusing. That part was meant to be a discussion of a possible alternative 
and
> an explanation of why we chose not to follow it. 
> 
> I've modified section 9 to make things a bit clearer and also to discuss the
> options we have (either the source address changes hop-by-hop or it doesn't 
change).
> It seems like both are sub-optimal. I'm currently edging to include both src 
and
> dst in the 'Final Destination Header'. If so, we'd presumably re-name to 
something
> like 'Original Endpoints Header' or 'Mesh Delivery Header' (any preferences? 
other
> suggestions?).

Currently it says 'Final destination field' - I suppose, it's going to change
to 'Final Destination header' or alike?
If we add source link-layer address as well, then I'd really like to see
a suggestion for header compression in case of 64bit addresses, even though
IETF charter may not allow to specify IEEE address format. Do you think, it
might be something that should be brought up at the IEEE meetings?

If we use 16bit short addresses only, do we see any disadvantages in 
routing directly to the Internet other than limitation of address space?

As for naming, I'd prefer 'Mesh Delivery header'.

> Please read the updated section 9 on mesh delivery and comment. That section
> is available here:
> 
> 
http://www.geocities.com/gabriel_montenegro_2000/draft-ietf-6lowpan-format-00a.h
tm#mesh
http://www.geocities.com/gabriel_montenegro_2000/draft-ietf-6lowpan-format-00a.t
xt
> 
> I include it below for your convenience.

Thanks so much. Please the comments in-line.

> 9.  Frame Delivery in a Link-Layer Mesh
> 
>    Even though 802.15.4 networks are expected to commonly use mesh
>    routing, the IEEE 802.15.4-2003 specification [ieee802.15.4] does not
>    define such capability.  In such cases, an ad hoc or mesh routing
>    protocol populates the devices' routing tables.  A device that wishes
>    to send a frame may, in such cases, use other intermediate devices as
>    forwarders towards the final destination.  In order to achieve such
>    frame delivery using unicast, it is necessary to include the final
>    destination in addition to the hop-by-hop destination.
> 
> 9.1.  Alternatives for Delivery of Frames in a Mesh
> 
>    Before discussing the defined mechanism for delivery in a mesh, let's
>    review some options on how to accomplish this.  The final destination
>    could be expressed either as a layer 2 or as an IP (layer 3) address.
>    In the latter case, there would be no need to provide any additional
>    header support in this document (i.e., at the sub-IP layer).  The
>    link-layer destination address would point to the next hop
>    destination address while the IP destination address would point to
>    the final destination (IP) address (that may be multiple hops away
>    from the source).  Thus, while forwarding data, the single-hop
>    destination address would change at each hop (always pointing to the
>    "best" next link-layer hop), while the destination IP address would
>    remain unchanged.  Notice that if an IP packet is fragmented, the
>    individual fragments may arrive at any node out of order.  If so, if
>    the initial frament (which contains the IP header) is delayed for
>    some reason, a node that receives a middle fragment would lack the
>    final destination address.  It would be forced to wait until this
>    information arrives (in the IP header within the first fragment)
>    before being able to forward the fragment any further.  This imposes
>    some additional buffering requirements on intermediate nodes.
>    Additionally, the above scheme would need to be adapted depending on
>    the layer 3 protocol, and would require this protocol to include its
>    own addressing information.
> 

Perhaps a subheader for 'Using L3 Final Destination field' and 'Using L2 Final
Destination Field' would look a litle clear.

As for L3 final destination address, I understand :

- The routing still happens in L3 layer; each node derives the next hop
  L2 address corresponding to the next-hop IP-address in the routing table
  given the final destination IPv6 address.
  
- The Final destination field is useful when IPv6 pkt is fragmented over the
   link.  If not fragmented, Final destination IP-address is not needed.
   
- If the IPv6 packet is not fragmented, and we use L3 routing, we don't
  need to set M bit.
  
Are the above assumptions correct?  If yes, perhaps then a clarification
on them in the above text is helpful. 

>    On the other hand, in order to create a mesh at the link-layer (layer
>    2), one would need to include the link-layer final destination
>    address within the layer 2 frame.  This would enable mesh delivery
>    for any protocol or application layering itself on top of the
>    adaptation layer defined above (Section 4).  For IPv6 as supported in
>    this document, another advantage of expressing the final destination
>    as a layer 2 addresses is that the IPv6 destination address can be
>    compressed as per the header compression specified in Section 8, thus
>    saving 8 octets.  Another advantage is that the the number of octets
>    needed to maintain routing tables is reduced due to the smaller size
>    of 802.15.4 addresses (either 64 bits or 16 bits) as compared to IPv6
>    addresses (128 bits).  A disadvantage is that applications on top of
>    IP do not address packets to link-layer destination addresses, but to
>    IP (layer 3) destination addresses.  Thus, given an IP address, there
>    is a need to resolve the corresponding link-layer address.  A mesh
>    routing specification would need to clarify the Neighbor Discovery
>    implications, although in some special cases, it may be possible to
>    derive a device's address at layer 2 from its address at layer 3 (and
>    viceversa).  Such complete specification is outside the scope of this
>    document.
> 
> 9.2.  Mechanism for Packet Delivery in a Mesh
> 
>    This section defines how to effect delivery of layer 2 frames in a
>    mesh, given a target link-layer address.  It does so via a layer 2
>    approach, as discussed in the previous section.
> 
>    Mesh delivery is enabled by setting the 'M' bit that immediately
>    follows the 'prot_type' field.  If the 'M' bit is set, there is a
>    "Final Destination" field included in the frame immediately following
>    the current header (e.g., possibly preceding any existing header
>    compression fields).  This implies that the "Final Destination" field
>    will immediately follow an unfragmented packet as per Figure 1 (i.e.,
>    preceding the IPv6 Header), or immediately following the first
>    fragment header as per Figure 2.
> 
>    If a node wishes to use a forwarder to deliver a packet, it puts the
>    forwarder's link-layer address in the link-layer destination address
>    field.  It must also set the 'M' bit, and include a "Final
>    Destination" field with the final destination's link-layer address.
>    Similarly, if a node receives a frame with the 'M' bit set, it must
>    look at the "Final Destination" field to determine the real
>    destination.  Upon consulting its routing table, it determines what
>    the next hop towards that destination should be.  The node then
>    reduces the "Hops Left" field.  If the result is zero, the node
>    discards the packet.  Otherwise, it puts the next hop's address in
>    the link-layer destination address field, and transmits the packet.
>    If upon examining the "Final Destination" field the node determines
>    that it has direct reachability, it removes the "Final Destination"
>    field, sets that final address as the link-layer destination address,
>    and transmits the packet.  Notice that whereas the destination link-
>    layer address changes at every hop, no such change applies to the
>    source link-layer address.  The latter always points at the initial
>    originator of the frame being forwarded.
> 

I assume the following NOTE is for temporary discussion. The rest looks good.

Thanks again.
-Samita

>    NOTE: The mesh delivery mechanism defined here only allows for a
>    final destination link-layer address, but not for an original
>    destination link-layer address.  This saves space, but then one must
>    decide how to use the only existing source link-layer address (that
>    in the 802.15.4 header).  There are pros and cons to not having the
>    source link-layer address change at every hop, as per the current
>    specification.  This is a pure layer 2 mesh delivery solution, so
>    even middle fragments can be forwarded as soon as they are received.
>    Even though which node sent a given frame is not immediately obvious,
>    this information can be inferred from the precursor list information
>    in its routing table.  If more than one precursor are possible, the
>    node would not necessarily know which of those actually sent it the
>    frame in question.  In order to send back an RERR, for example, it
>    might have to send it to all possible precursors.  Given that such
>    error conditions may be rare as compared to data forwarding events,
>    this may not be a large cost to pay.  However, the acknowledge mode
>    of data delivery in 802.15.4 sends back an ACK whenever a frame is
>    received.  Typically, this operation is implemented in hardware very
>    efficiently.  With the current scheme, one would have to turn off
>    this option on the chipset, and instead do it in a much less
>    efficient manner in software.  Data forwarding in this case incurs
>    the cost of examining the routing table in order to infer the link-
>    layer address of the device that is expecting the ACK.
>    Unfortunately, a device that does not implement this specification
>    would proceed as per the usual 802.15.4 procedures and send back an
>    ACK to the address contained in the source link-layer address.  Such
>    an ACK would be erroneously addressed to the initial originator of
>    the frame, and would most probably remain undelivered.  Because of
>    these considerations it may be inevitable to add the original link-
>    layer source address as an explicit field in mesh delivery.  The
>    alternative, of course, is to have the source link-layer address
>    change at every hop.  In this case, the original link-layer address
>    is lost.  It may be possible to recover it if the IP source address
>    is present and if there is a clearly defined way to derive the former
>    from the latter (as per the header compression considerations in this
>    document).  This poses the issues that this ceases being a mesh
>    delivery solution at layer 2, with the considerations raised in the
>    previous section.
> 
>    Whereas a node must participate in a mesh routing protocol to be a
>    forwarder, no such requirement exists for simply using mesh
>    forwarding.  Only "Full Function Devices" (FFDs) are expected to
>    participate as routers in a mesh.  "Reduced Function Devices" (RFDs)
>    limit themselves to discovering FFDs and using them for all their
>    forwarding, in a manner similar to how IP hosts typically use default
>    routers to forward all their off-link traffic.  For an RFD using mesh
>    delivery, the forwarder is always the appropriate FFD.
> 
>    The "Final Destination" 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| Hops Left   |   Link-layer Address of final destination     |
>       +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
> 
>    Figure 9: Final Destination Field
> 
>    Field definitions are as follows:
> 
>    S: This bit field SHALL be zero.  Future revisions will use this bit
>       to signal the use of an 802.15.4 short 16 bit address instead of
>       the default IEEE extended 64 bit address format.
> 
>    Hops Left: This 7 bit field SHALL be decremented by each forwarding
>       node before sending this packet towards its next hop.  The packet
>       is discarded if Hops Left is decremented to 0.
> 
>    Address: This is the final destination's link-layer address.  This
>       document assumes that this field is 64 bits long, but a future
>       revision may add support for short addresses (16 bits).

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

---

From: gabriel montenegro <[email-masked]>
Date: Wed, 19 Oct 2005 18:30:37 -0700 (PDT)

Here's another preliminary version of the doc:

http://www.geocities.com/gabriel_montenegro_2000/draft-ietf-6lowpan-format-00b.htm
http://www.geocities.com/gabriel_montenegro_2000/draft-ietf-6lowpan-format-00b.txt

Please look it over, specially as related to the changes:

Appendix B.  Changes

   Changes from version draft-ietf-6lowpan-format-00.txt to version
   draft-ietf-6lowpan-format-01.txt are as follows:

      TODO: Add support for 16-bit "short" addresses.

      TODO: Added 'Ver' field, and one more bit to datagram tag (from 15
      to 16 bits). protocol_type and datagram offset both went from 11
      to 8 bits (which is still enough for the format, and which implies
      counting offset in units of 8 octets for the latter).

      Changed both fragmentation formats, moved the datagram tag towards
      the end, and increased its length from 7 to 15 bits.

      Addition of the originator's link-layer source address to the
      "Mesh Delivery" header.

      Changed name of "Final Destination" header to "Mesh Delivery"
      header.

      Further clarification on mesh delivery.

      Sundry editorial changes.

As for your message, please find some answers below...

-gabriel

> it seems.[ when AODV runs on link-layer] 

ah, yes, ok.

> fe80:0:0:<pan-id>::<16bit-addr>?

ah, i see. you're talking about the interface identifier (IID) format based on
the link-layer address. yes, that's one of the things that an ip-over-foo
is expected to specify. we already did for the 64-bit format. for the
16-bit 15.4 link-layer format, your suggestion is the simplest, yes.
we're already suggesting adding a <pan-id> to a /48 to obtain a prefix identifier
so this would play into that as well. but for IIDs we can actually mandate
the above format. going through the draft and adding support for short bit
addresses is still on the TODO list, hopefully we can do it before the cut-off.

> ...

not sure what you mean here.

> routing directly to the Internet other than limitation of address space?

not sure why. any link-layer addresses are supposed to be used on your local link.
so routing to the internet only plays in that you must find a router to send stuff
off-link. this router would be on your local link, of course, so it would an
address on that link just like anybody else (e.g., short 16-bit address if on a
15.4 link). perhaps i misunderstood the question.

> As for naming, I'd prefer 'Mesh Delivery header'.

ok.

> Destination Field' would look a litle clear.

I just moved the above section into an appendix. 

> on them in the above text is helpful. 

This was one option we did not choose, so I've left the text pretty much unchanged
(with some minor edits, perhaps it's clearer).
We might want to remove this altogether before publicatino.

-gabriel