Subject: Re: [6lowpan] hc-01

From: "Pascal Thubert (pthubert)" <[email-masked]>
Date: Thu, 9 Oct 2008 01:31:21 +0200

Hi Julien:

I think you're right, we need to dig a little bit more.

So starting from Jonathan's encoding, maybe we can refine was was CTX

     0   1   2   3   4   5   6   7   8   9   0   1   2   3   4   5
   +---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+
   | 0 | 1 | 0 | 0 | 1 |  DDF  |  TF   |NH | HLIM  |  SAM  |  DAM  |
   +---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+

- Dispatch: 8-15
- DDF: Destination dependant fiels
  - 00: Destination is global (or ULA), no context byte after the HC field
  - 01: Destination is global (or ULA), one byte context byte after the HC field
  - 10: Destination is Link local
  - 11: Destination is multicast scoped address

- TF: Traffic Class, Flow Label
  - 00: 4-bit Pad + Traffic Class + Flow Label (4 bytes)
  - 01: ECN + 2-bit Pad + Flow Label (3 bytes)
  - 10: Traffic Class (1 byte)
  - 11: No Traffic Class and Flow Label

- NH: Next Header compression

- HLIM: Hop Limit
  - 00: uncompressed
  - 01: 1
  - 10: 64
  - 11: 255

When destination is link local:
-------------------------------
prefix is FC80::/64 when compressed

- SAM: Source Address Mode - prefix is link-local, when compressed
  - 00: 128 bits
  - 01: 64 bits
  - 10: 16 bits 
  - 11: 0 bits
- DAM: Destination Address Mode - prefix is link-local, when compressed
  - 00: 128 bits
  - 01: 64 bits
  - 10: 16 bits
  - 11: 0 bits 

When destination is multicast:
-------------------------------
prefix is FF02::/64 when compressed

- SAM: Source Address Mode
  - 00: 0 bits, unspecified address
  - 01: 64 bits, prefix is link local
  - 10: 16 bits, prefix is link local
  - 11: 0 bits, derived from the IID, prefix is link local
- DAM: Destination Address Mode - prefix is link-local, when compressed
  - 00: 8 bits,  prefix is compressed, suffix is 7 octets of zeroes, then this octet
  - 01: 24 bits, prefix is compressed, suffix is 4 octets of zeroes, then one octet 0xFF then this octet
  - 10: 16 bits. 4 bits flags, 4 bits scope, 1 byte suffix.
Prefix as defined in RFC 4291, suffix is 7 octets of zeroes, then this suffix octet
  - 11: 24 bits  4 bits flags, 4 bits scope, 2 bytes suffix 
Prefix as defined in RFC 4291, suffix is 6 octets of zeroes, then those suffix octets 

When destination is ULA or global: 
-------------------------------
The prefix is found from the context table. 
If there is no context octet after the HC field then this is the default prefix.

- SAM: Source Address Mode
  - 00: 128 bits
  - 01: 64 bits
  - 10: 16 bits
  - 11: 0 bits
- DAM: Destination Address Mode
  - 00: 128 bits
  - 01: 64 bits
  - 10: 16 bits
  - 11: 0 bits

Notes:

With this change, the 16 bits format of Link local and ULA and global really means the last 16 bits ( apposed to 15 in http://tools.ietf.org/html/draft-ietf-6lowpan-hc-00 2.2.  IPv6 Unicast Address Compression. 

With this change, we have the most useful mcast cases covered:
DAM of 00 compresses FF02::XX, so you get all routers on link, etc...
DAM of 01 compresses FF02::FFXX:YYZZ, sollicited node mcast address
DAM of 10 and 11 compress all permanently-assigned multicast addresses defined today for all scopes

What do you think?

Pascal
________________________________________
From: Julien Abeille (jabeille) 
Sent: mercredi 8 octobre 2008 17:51
To: Jonathan Hui
Cc: Pascal Thubert (pthubert)
Subject: hc-01

Hi Jonathan,
 
I send unicast because my thought will not be clear, and to make a quick presentation and bind it to "cisco sensor team".
I did my master thesis in 2005 at Cisco in Sophia Antipolis. My project manager was Patrick Wetterwald (IPSO president) and I worked with Pascal on tree discovery and bubbles protocols. I joined Cisco as employee in july last year, and have been working on sensors with Patrick as project manager, Pascal and a few others as engineers. I met JP Vasseur a year ago and we have frequent calls and meetings, as he recently moved 150km from switzerland where my office is. I work most closely with Mathilde Durvy whom you met for IPSO interop calls.
 
after discussion with Pascal about address compression, I try to clarify my thoughts:
- 64 last bits compression in unicast address compression is only feasible if last 64 bits are based on IID (either 64 bit MAC address or PAN ID+0+16bit address). I thought it would be nice to be able to compress as well addresses with bytes 8 to 13 = 0. (e.g. a::1)
- could be nice as well to compress the IID only when the prefix is not compressable?
- for multicast address compression, i thought stateless compression could be nice. This works well with permanently assigned addresses (Pascal, the link i promissed: http://www.iana.org/assignments/ipv6-multicast-addresses), as many bytes are 0 after the two first ones
- for multicast again, it would be nice to be able to compress addresses with more than 9-bit non 0 (a few permanently assigned ones apply there, like all-dhcp-agents)
- regarding the 16-bit compressed format, i would prefer not having one bit or more in the compressed field with a special meaning (first bit 0 = unicast, 3 first bits 101 = multicast), but keep all these bits in the encoding
- I was wondering if assuming flags are 0 cannot be an issue. 
 
These are just thoughts, as i am not extremely clear on the important scenarios where we want to compress (e.g. solicited node multicast compression might not be needed as with ND optimizations, there will not be many NS), and am not clear either about multicast addresses except permanently assigned ones. More preciely i do not know if we want to support unicast prefix based multicast addresses or rendez vous point addresses, and what they look like.
 
hope this helps in the discussion,
regards,
Julien
 
_______________________________________________
6lowpan mailing list
[email-masked]
https://www.ietf.org/mailman/listinfo/6lowpan

---

From: Jonathan Hui <[email-masked]>
Date: Wed, 8 Oct 2008 16:49:38 -0700

Hi Pascal,

I think this looks great. It covers the cases we care about (unicast  
and multicast) without using any extra bits that my initial proposal.  
The small thing I would change is moving the "DDF" field to bits 10-11  
(shifting TF and NH 2 bits to the left). Then TF would not span a byte  
boundary.

     0   1   2   3   4   5   6   7   8   9   0   1   2   3   4   5
   +---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+
   | 0 | 1 | 0 | 0 | 1 |  TF   |NH | HLIM  |  DDF  |  SAM  |  DAM  |
   +---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+

--
Jonathan Hui

On Oct 8, 2008, at 4:31 PM, Pascal Thubert (pthubert) wrote:

> With this change, the 16 bits format of Link local and ULA and  
> global really means the last 16 bits ( apposed to 15 in http://tools.ietf.org/html/draft-ietf-6lowpan-hc-00 
>  2.2.  IPv6 Unicast Address Compression.
>
> I send unicast because my thought will not be clear, and to make a  
> quick presentation and bind it to "cisco sensor team".
> I did my master thesis in 2005 at Cisco in Sophia Antipolis. My  
> project manager was Patrick Wetterwald (IPSO president) and I worked  
> with Pascal on tree discovery and bubbles protocols. I joined Cisco  
> as employee in july last year, and have been working on sensors with  
> Patrick as project manager, Pascal and a few others as engineers. I  
> met JP Vasseur a year ago and we have frequent calls and meetings,  
> as he recently moved 150km from switzerland where my office is. I  
> work most closely with Mathilde Durvy whom you met for IPSO interop  
> calls.
>
> - 64 last bits compression in unicast address compression is only  
> feasible if last 64 bits are based on IID (either 64 bit MAC address  
> or PAN ID+0+16bit address). I thought it would be nice to be able to  
> compress as well addresses with bytes 8 to 13 = 0. (e.g. a::1)
> - for multicast address compression, i thought stateless compression  
> could be nice. This works well with permanently assigned addresses  
> (Pascal, the link i promissed: http://www.iana.org/assignments/ipv6-multicast-addresses) 
> , as many bytes are 0 after the two first ones
> - for multicast again, it would be nice to be able to compress  
> addresses with more than 9-bit non 0 (a few permanently assigned  
> ones apply there, like all-dhcp-agents)
> - regarding the 16-bit compressed format, i would prefer not having  
> one bit or more in the compressed field with a special meaning  
> (first bit 0 = unicast, 3 first bits 101 = multicast), but keep all  
> these bits in the encoding
> These are just thoughts, as i am not extremely clear on the  
> important scenarios where we want to compress (e.g. solicited node  
> multicast compression might not be needed as with ND optimizations,  
> there will not be many NS), and am not clear either about multicast  
> addresses except permanently assigned ones. More preciely i do not  
> know if we want to support unicast prefix based multicast addresses  
> or rendez vous point addresses, and what they look like.
>

---

From: "Julien Abeille (jabeille)" <[email-masked]>
Date: Thu, 9 Oct 2008 14:45:29 +0200

Hi Pascal, Jonathan,

For addresses I see an issue with a few scenarios:
- dest multicast, source global non compressable (SAM does not define
128 bits format)
- some dest multicast are not in either of the 4 DAM cases, e.g
FF3E:0040:aaaa:a:a:a:1:1 (address based on prefix aaaa:a:a:a::/64, with
32 bit group id = 1:1)

Pascal, can you clarify the DDF = 01 case

I tried to make my ideas clear by listing all current multicast
scenarios , based on
http://www.iana.org/assignments/ipv6-multicast-addresses and RFC 3306 +
3956 (unicast prefix based multicast addresses)

A 128, not compressed
B FF02::XX 1 byte needed
C FF0X::00XX:XXXX 4 bytes needed
D FF0X::00XX:XXXX:XXXX 6 bytes needed
E unicast prefix based address, not embedding rendez vous point: 5 bytes
needed
F unicast prefix based address, embedding rendez vous point: 6 bytes
needed

A covers unicast prefix based multicast addresses with prefix not in
context
B covers most useful link local cases (see IANA) e.g. LL all nodes,
FF02::1
C covers longer well known cases (see IANA) e.g. all-dhcp-servers
FF05::1:3
D covers solicited node and node information queries FF02::1:FFXX:XXXX
and FF02::2:FFXX:XXXX
E covers format defined in RFC3306, when the prefix used is in the
default context.

|   8    |  4 |  4 |   8    | 8  |       64       |    32    |
+--------+----+----+--------+----+----------------+----------+
|11111111|flgs|scop|reserved|plen| network prefix | group ID |  
+--------+----+----+--------+----+----------------+----------+
Here flags are 0011 (e.g. not embedding rendez vous point, unicast
prefix based, non permanently assigned)
We only need to send flags, scope, group ID (5 bytes)

F covers format defined in RFC3956, when the prefix used is in the
default context.

|   8    |  4 |  4 |  4 |  4 | 8  |       64       |    32    |
+--------+----+----+----+----+----+----------------+----------+
|11111111|flgs|scop|rsvd|RIID|plen| network prefix | group ID |
+--------+----+----+----+----+----+----------------+----------+
Here flags are 0111 (e.g. embedding rendez vous point, unicast prefix
based, non permanently assigned)
We only need flags, scope, reserved + RIID, group ID (6bytes)

Questions: 
- do we want to support all this?
- do we want to group some cases: we could group C and D, E and F, then
we have 4 cases only
- what do we do for dest multicast, source non compressable. 
- Do we keep unspecified support?
- do we afford one more bit (this would be 7 bits for addresses) and use
dispatch e.g. 1101xxxx?
- do we keep src and dest encoding linked. For now we have 2 bits common
to src and dest (DDF), plus SAM and DAM. This makes 16 cases for both
src and dest, 32 in total.

Cheers,
Julien

-----Original Message-----
From: Jonathan Hui [mailto:[email-masked]] 
Sent: jeudi 9 octobre 2008 01:50
To: Pascal Thubert (pthubert)
Cc: Julien Abeille (jabeille); [email-masked]
Subject: Re: hc-01

Hi Pascal,

I think this looks great. It covers the cases we care about (unicast and
multicast) without using any extra bits that my initial proposal.  
The small thing I would change is moving the "DDF" field to bits 10-11
(shifting TF and NH 2 bits to the left). Then TF would not span a byte
boundary.

--
Jonathan Hui

On Oct 8, 2008, at 4:31 PM, Pascal Thubert (pthubert) wrote:

>  - 01: Destination is global (or ULA), one byte context byte after the

> HC field
> Prefix as defined in RFC 4291, suffix is 7 octets of zeroes, then this

> suffix octet
>  - 11: 24 bits  4 bits flags, 4 bits scope, 2 bytes suffix Prefix as 
> defined in RFC 4291, suffix is 6 octets of zeroes, then those suffix 
> octets
>
> With this change, the 16 bits format of Link local and ULA and global 
> really means the last 16 bits ( apposed to 15 in 
> http://tools.ietf.org/html/draft-ietf-6lowpan-hc-00
> DAM of 10 and 11 compress all permanently-assigned multicast addresses

> defined today for all scopes
>
> What do you think?
>
> Pascal
> with Pascal on tree discovery and bubbles protocols. I joined Cisco as

> employee in july last year, and have been working on sensors with 
> met JP Vasseur a year ago and we have frequent calls and meetings, as 
> he recently moved 150km from switzerland where my office is. I work 
> most closely with Mathilde Durvy whom you met for IPSO interop calls.
>
> (Pascal, the link i promissed: 
> http://www.iana.org/assignments/ipv6-multicast-addresses)
> addresses with more than 9-bit non 0 (a few permanently assigned ones 
> apply there, like all-dhcp-agents)
> one bit or more in the compressed field with a special meaning (first 
> bit 0 = unicast, 3 first bits 101 = multicast), but keep all these 
> bits in the encoding
> These are just thoughts, as i am not extremely clear on the important 
> scenarios where we want to compress (e.g. solicited node multicast 
> compression might not be needed as with ND optimizations, there will 
> not be many NS), and am not clear either about multicast addresses 
> except permanently assigned ones. More preciely i do not know if we 
> want to support unicast prefix based multicast addresses or rendez 
> vous point addresses, and what they look like.
>

---

From: "Pascal Thubert (pthubert)" <[email-masked]>
Date: Thu, 9 Oct 2008 16:52:30 +0200

Hi Julien:

We used 3 compression mechanisms for the addresses in this spec:

- compress specific types of addresses that are commonly when a large
part of the address is a constant. This is applies to link local and
some multicast addresses. We can only go that far with that model
because of the explosion of cases. So we covered only the most commonly
used and did not attempt to be exhaustive and we applied that to Link
Local and some multicast addresses

- use a stateless mechanism when part of field can be inferred from
another part (e.g. when the IP address is formed out of the EUI-64 or
EUI-48 address)

- use a stateful mechanism when none of the above applies or if
preferred for a even better compression.

And: we default to no compression when none of the above applies, using
the global format. 

Motes do not have to implement all the compression mechanisms but they
should be able to decompress everything.

This is the part where we need to modify / refine the draft:

- The text seems to imply that if the destination is multicast then DDF
is 11. The compression mechanism does not really care about routing,
whether an address is unicast, multicast or anycast. All it cares for
multicast is if there is a sufficiently large part that is a well known
constant and if that case is sufficiently used to deserve some specific
code in a mote to compress it.

- So, if the destination is multicast, the sender SHOULD attempt to
apply DDF 01 or 11. If it has no context for the destination and none of
the covered cases in 11 applies, then he will resort to use DDF 01, and
in the worst case none of the addresses will be compressed. 

The text could thus be a bit more clear on the following rules:

- If there is nothing more specific that fits, last resort is to
compress an address as if it was global. So there's always a way.

- if you do not want to compress, you do not have to. For instance, a
mote that will never or almost never send a multicast packet does not
have to support DDF of 11 in its compression algorithm. We are making a
lot of efforts to propose a ND mechanism in 6LoWPAN that doesn't need
multicast.

- still a mote should be able to decompress everything specified here.
But that seems a bit easier then compressing, is that right?

Pascal

>Sent: jeudi 9 octobre 2008 14:45
>To: Jonathan Hui; Pascal Thubert (pthubert)
>Cc: [email-masked]
>Subject: RE: hc-01
>
>Hi Pascal, Jonathan,
>
128 bits format)
>- some dest multicast are not in either of the 4 DAM cases, e.g
FF3E:0040:aaaa:a:a:a:1:1 (address
>based on prefix aaaa:a:a:a::/64, with 32 bit group id = 1:1)
>
scenarios , based on
>http://www.iana.org/assignments/ipv6-multicast-addresses and RFC 3306 +
3956 (unicast prefix based
>multicast addresses)
>E unicast prefix based address, not embedding rendez vous point: 5
bytes needed
needed
context
FF02::1
FF05::1:3
and FF02::2:FFXX:XXXX
default context.
prefix based, non permanently
>assigned)
default context.
based, non permanently
>assigned)
we have 4 cases only
>- do we afford one more bit (this would be 7 bits for addresses) and
use dispatch e.g. 1101xxxx?
>- do we keep src and dest encoding linked. For now we have 2 bits
common to src and dest (DDF), plus
>SAM and DAM. This makes 16 cases for both src and dest, 32 in total.
>
>Cheers,
>Julien
>
>
and multicast) without using any
>extra bits that my initial proposal.
(shifting TF and NH 2 bits to
>the left). Then TF would not span a byte boundary.
>
as

---

From: Jonathan Hui <[email-masked]>
Date: Thu, 9 Oct 2008 12:00:46 -0700

Hi Julien,

Your comments are valid. By adding a single bit, I think we can  
support all the cases you mention without compromising any of the  
cases we currently support. So here is a proposed modification:

     0   1   2   3   4   5   6   7   8   9   0   1   2   3   4   5
   +---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+
   | X | X | X | X |  TF   | HLIM  |NH |  CTX  |  SAM  | M |  DAM  |
   +---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+

- CTX (context identifier for both source and destination addrs, if  
applicable):
  - 00: Link-local
  - 01: Unspecified Address (valid only for source addr with mcast)
  - 10: Global w/ Default
  - 11: Global w/ Context Identifier Extension

- SAM:
  - 00: 128-bit
  - 01: 64-bit
  - 10: 16-bit
  - 11: 0-bit

- M: Multicat
  - 0: Unicast Destination
  - 1: Multicast Destination

- DAM:
  - When M = 0:
    - 00: 128-bit
    - 01: 64-bit
    - 10: 16-bit
    - 11: 0-bit
  - When M = 1:
    - 00: 128-bit
    - 01: 48-bit (FFXX:XXplen::prefix:XXXX:XXXX)
    - 10: 48-bit (FF0X::XX:XXXX:XXXX)
    - 11: 8-bit (FF02::XX)

This covers all the multicast cases you care about. It also covers  
multicast with a global source address. And it covers all the unicast  
formats that we've supported since the beginning (link-local, global  
with default context, global with other contexts). Whether or not we  
want to support all of the cases you outlined is a question, but given  
that it only adds a single bit to the format, I think it's little  
added overhead.

How does that look to you?

--
Jonathan Hui

On Oct 9, 2008, at 5:45 AM, Julien Abeille (jabeille) wrote:

> bytes
> common
> and

---

From: Jonathan Hui <[email-masked]>
Date: Thu, 9 Oct 2008 20:05:02 -0700

Hi Julien,

I realized that the 128-bit case for both unicast and multicast is  
redundant. So I made a minor change to add extra support for multicast  
compression. See below:

> - M: Multicat Compression
> - 0: Prefix Compression
> - 1: Multicast Compression
>
> - DAM:
> - When M = 0:
>   - 00: 128-bit
>   - 01: 64-bit
>   - 10: 16-bit
>   - 11: 0-bit
> - When M = 1:
>   - 00: 48-bit (FFXX:XXplen::prefix:XXXX:XXXX)
>   - 01: 48-bit (FF0X::XX:XXXX:XXXX)
>   - 10: 32-bit (FF0X::XX:XXXX)
>   - 11: 8-bit (FF02::XX)

--
Jonathan Hui

> multicast with a global source address. And it covers all the  
> unicast formats that we've supported since the beginning (link- 
> local, global with default context, global with other contexts).  
> Whether or not we want to support all of the cases you outlined is a  
> question, but given that it only adds a single bit to the format, I  
> think it's little added overhead.
>
>>> global
>>> (first
>>> important

---

From: "Pascal Thubert (pthubert)" <[email-masked]>
Date: Fri, 10 Oct 2008 18:26:30 +0200

Hi Jonathan:

The way I see it, comparing to
http://tools.ietf.org/html/draft-ietf-6lowpan-hc-01 

- This is cleaner and more readable 

- but consumes an additional bit, that is 8 more dispatches that can not
be used for something

- this is done to simplify the code for multicast addresses that will be
little to not used if the whiteboard ND is generalized.

- and at the end of the day there is nothing that is really useful and
compressed better here (do I miss something here?)

I am fine with moving to this proposal if implementors (Julien?) confirm
that the implementation is really simpler and worth the cost of 8
consecutive dispatch values.

If not, please consider the response I made to Julien. We are NOT
missing cases; but there are cases we do not compress because they are
deemed rare enough.

Let me try to defend the formats we have for the sake of the discussion
and the stability of the draft. I think the bigger inadequacy in hc-01
(my fault I assume it) is the name DDF (Zach seems to confirm that) and
the description of the field that is oriented on the type of address
(causing Julien's concerns). 

When I look at it what do we do with this DDF field, what's really
behind it is the method of compression being applied. Renaming DDF to CM
we'd get:

Compression Method (CM):

00 = Stateless compression using MAC address and inline values. Also
uses a default context state for full compression. Includes the "no
address compression" last resort.
01 = Stateful compression using contextual states, context byte follows
10 = Stateless compression (using well known prefix and MAC address) for
Link local addresses
11 = Stateless compression (using well known prefix and inline values)
for multicast addresses

With that description, it appears more clearly that multicast address
may be compressed using 00:
- there is no address pair that can not be described with the format (00
covers all)
- the stateless mechanism can not compress all cases. In particular if
source and destination have different scope (but is that worth spending
bits and code space?)
- implementation do not have to compress multicast addresses using
method 11 though they have to decompress that method.

What do you think?

Pascal

>Sent: jeudi 9 octobre 2008 21:01
>To: Julien Abeille (jabeille)
>Cc: Pascal Thubert (pthubert); [email-masked]
>Subject: Re: hc-01
>
>
>Hi Julien,
>
global
as
>>> addresses with more than 9-bit non 0 (a few permanently assigned
ones
(first
important