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

From: gabriel montenegro <[email-masked]>
Date: Fri, 14 Oct 2005 01:15:40 -0700 (PDT)

Hi Samita,

--- Samita Chakrabarti <[email-masked]> wrote:

> 
> Hi Gabe,
> 
> I have some questions regarding the M bit in lowpan.
> 
>  The draft says in pg 5:
> The LoWPAN payload (e.g., an
>    IPv6 packet) follows this encapsulation header.  Alternatively, if
>    the 'M' bit is on, before this actual payload, a "Final Destination"
>    field will be present (Section 9).
> 
> On pg 6   
>   M: This bit is used to signal whether there is a "Final Destination"
>       field as used for ad hoc or mesh routing.  If set to 1, a "Final
>       Destination" field precedes the IPv6 packet  (Section 9). 
>   
>   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.

Your routing protocol would use hop-by-hop to find routes (RREQ/RREP) and populate
routing tables along the way. Once the routing tables are set up, then your data
forwarding can take place. You would use the 'M' bit and section 9 for the data
delivery.

>   
>   If it's used for data routing in mesh-network, then I see why the draft
>   wanted to keep original MAC source address field unchanged. But I beleive
>   the MAC implementation sets its own MAC address anyway when it transmits
>   a packet. ( I don't know of all implementations though). 

Yeah, this is a bit problematic (also with ACKs). 

>   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.

>   
>   ----------------------------------------
>   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?).

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.htm#mesh
http://www.geocities.com/gabriel_montenegro_2000/draft-ietf-6lowpan-format-00a.txt

I include it below for your convenience.

-gabriel

---------------------------------------------------------

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.

   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.

   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