Subject: Re: [core] HREF compression encoding

From: Carsten Bormann <[email-masked]>
Date: Wed, 6 May 2020 14:19:06 +0200

Hi Jim,

This is an interesting proposal.
Klaus and I had a chat about it now, which led to the following straw man grammar:

CRI-Reference = [
  (?scheme, ?(host, ?port) // path.type),
  *path,
  ? (QUERY, +query)
  ? (FRAGMENT, fragment)
]

scheme    = ((SCHEMETEXT, text .regexp "[a-z][a-z0-9+.-]*") 
            // COAP // COAPS // HTTP // HTTPS)
host      = ((HOSTTEXT, text) // bytes .size 4 // bytes .size 16)
port      = 0..65535
path.type = 0..127
path      = text
query     = text
fragment  = text

SCHEMETEXT = -1
COAP = -2 COAPS = -3 HTTP = -4 HTTPS = -5
HOSTTEXT = true
QUERY = -6
FRAGMENT = -7

Obviously, the specific marker values we use could be shuffled a bit, but it seems we can cover the entire spectrum that is covered by the existing syntax.
There are a few things that need to be decided base on perceived frequency of use (e.g., are text-valued host names the likely or the unlikely case — depending on that, the marker is placed on the host text or on the path sequence, or the absent host could be represented by `false`), so we should come up with some rough estimations here.

Comments welcome...

Grüße, Carsten

> On 2020-04-22, at 20:20, Jim Schaad <[email-masked]> wrote:
> 
> I had a slightly different proposal to what Klaus presented at the last interim in terms of doing href compression.  It is based on the fact that URIs have a relatively fixed pattern and keeps the CBOR coding directly rather than moving to some type of binary encoding.
>  
> The standard pattern for a URI is scheme://hostname/path/path/…  Using this for compression purposes by removing all of the tagging which keeps to the same pattern you would compress coap://example.com/foo/abc…xyz to
>  
> [ “coap”, “example.com”, “foo”, “abc…xyz”]
> 1    1          1          1          2     = 6 bytes of padding
>  
> This is the same amount of padding as his binary compression method.  There is a slight loss over his method when you want to do port numbers, queries or fragments as they would need to have a integer tag inserted so you get
>  
> [ “coap”, “example.com”, “foo”, “bar”, Query, “a=b”, “c=d”, Fragment, “gohere”]
> 1    1          1           1      1     1       1     1       1        1        = 10 bytes
>  
> In the binary encoding this would only require 9 bytes
>  
> Moving to an IP address adds no additional padding as the difference between a text string, a byte string of length either 4 or 8 can easily be detected.  Relative URIs are encoded using similar tagging so you end up with
>  
> [ Absolute, “foo”, “bar” ]
> 1   1          1      1   =  4 byte
>  
> [ Relative, 2, “foo”, “bar” ]
> 1   1        1   1     1        = 5 bytes
>  
> Using the binary mode these would be 4 bytes and  4 bytes respectively (I think as no examples are in the slides)
>  
> I believe that the advantage of this proposal is that there is no new encoder/decoder needed as this is pure CBOR.  The compressed outputs are of similar lengths as the binary version and processing them I believe will result in near identical code sizes.  The code to do absolute and relative processing as well as generating CBOR options is going to be very similar.
>  
> Jim
>  
> _______________________________________________
> core mailing list
> [email-masked]
> https://www.ietf.org/mailman/listinfo/core

---

From: Thomas Fossati <[email-masked]>
Date: Wed, 6 May 2020 13:31:13 +0000

> COAP = -2 COAPS = -3 HTTP = -4 HTTPS = -5

Very smooth, I like it.

> Obviously, the specific marker values we use could be shuffled a bit,
> but it seems we can cover the entire spectrum that is covered by the
> existing syntax.  There are a few things that need to be decided base
> on perceived frequency of use (e.g., are text-valued host names the
> likely or the unlikely case - depending on that, the marker is placed
> on the host text or on the path sequence, or the absent host could be
> represented by `false`), so we should come up with some rough
> estimations here.

A quick question on "perceived frequency of use": how do we plan to
evaluate that?  Is there a representative corpus that can be mined?

cheers, thanks!

IMPORTANT NOTICE: The contents of this email and any attachments are confidential and may also be privileged. If you are not the intended recipient, please notify the sender immediately and do not disclose the contents to any other person, use it for any purpose, or store or copy the information in any medium. Thank you.

---

From: Jim Schaad <[email-masked]>
Date: Wed, 6 May 2020 07:42:01 -0700

-----Original Message-----
From: Carsten Bormann <[email-masked]> 
Sent: Wednesday, May 6, 2020 5:19 AM
To: Jim Schaad <[email-masked]>
Cc: [email-masked] WG <[email-masked]>
Subject: Re: [core] HREF compression encoding

Hi Jim,

This is an interesting proposal.
[JLS]  I do hope you are not implying that most of my proposals are uninteresting 😉

CRI-Reference = [

[JLS]  I think that from the other work Klaus and I have been sending back and forth, it might be that this should be
path.type = ABSOLUTE | 0..127
I at least found it much easier to completely separate the absolute path from relative path when doing processing.

path      = text
query     = text
fragment  = text

SCHEMETEXT = -1
COAP = -2 COAPS = -3 HTTP = -4 HTTPS = -5 HOSTTEXT = true QUERY = -6 FRAGMENT = -7
[JLS] I am glad we finally have gotten around to the idea that we should be using abbreviated schemes.  It might be that we want to make the schemes at the end of the list so that other could be registered and it would be easy to determine which are schemes and which are not as they would be a single range.

[JLS] Yes this needs to be done, and I don't know have any good idea of how to do this.  It seems it is going to be heavily influenced by the set of applications that you choose to look at and how they are weighted.  An RD is going to be heavily into absolute paths.  On the other hand, from what I remember, the coffee pot is build almost entirely from relative paths.  One of the nice things from the proposal is that we no longer need to worry about the relative frequencies on the balance between text and numeric addresses.  

Comments welcome...

Grüße, Carsten

> The standard pattern for a URI is scheme://hostname/path/path/…  Using 
> this for compression purposes by removing all of the tagging which 
> keeps to the same pattern you would compress 
> coap://example.com/foo/abc…xyz to
>  
> This is the same amount of padding as his binary compression method.  
> There is a slight loss over his method when you want to do port 
> numbers, queries or fragments as they would need to have a integer tag 
> inserted so you get
>  
> Moving to an IP address adds no additional padding as the difference 
> between a text string, a byte string of length either 4 or 8 can 
> easily be detected.  Relative URIs are encoded using similar tagging 
> so you end up with
>  
> Using the binary mode these would be 4 bytes and  4 bytes respectively 
> (I think as no examples are in the slides)
>

---

From: Christian Amsüss <[email-masked]>
Date: Mon, 11 May 2020 13:21:23 +0200

Hello,

> This is an interesting proposal.

I like that too.

> [JLS] [...] An RD is going to be heavily into absolute paths.

Even that depends on how the RD is used. When querying for resources of
a specific type across a network, it will largely consist of one full
CRI ([COAP, ...]) for the anchor and one relative ([PATH-..., ...]) for
the target. Queries that yield multiple records from the same server can
make use of CoRAL's base directive.

Kind regards
Christian

-- 
To use raw power is to make yourself infinitely vulnerable to greater powers.
  -- Bene Gesserit axiom

---

From: Jim Schaad <[email-masked]>
Date: Mon, 25 May 2020 09:33:32 -0700

For some reason I was thinking about the issue of what should be the default
marker value.  While doing so I realized that I had been stuck in a train of
thought guided by the text version of decomposing URIs and it does not
really apply for this encoding.

Consider the URI "coap://localhost/a/b/c", in text one could decompose this
as "coap://localhost" and "/a/b/c" representing this as
[ "coap", "localhost"]   [ABSOLUTE, "a", "b", "c"]

However, this could just as easily be represented as
["coap", "localhost"] [APPEND, "a", "b", "c"]

I therefore propose the following as a list of usual things:

1.  Absolute URIs with and without having a predefined scheme:  The former
needs no leading marker and the latter would need a marker that it is a
schema.  
2.  Base URI of authority and relative URI of absolute path:  As noted above
this can use the append marker or absolute path marker.
3.  Base URI of authority + path and relative URI of absolute path:  Needs
an absolute path maker.
4.  Base URI of authority + path with implicit end path segment  and
relative URI:  ("http://localhost/a/" and "b/c") Can use the append marker
5.  Base URI ending in a "file name" path segment and relative URI:
("http://localhost/a/home.html" and "./b/c") This needs to use the Up One
marker.
6.  Base URI ending in a path segment where there is no difference between
last and intermediate names and a relative URI: ("coap://localhost/a" and
"./a/b/c") Can use the append marker while omitting the first path segment
of the relative path ([APPEND, "b", "c"])

I think that if we combine group 2 and group 6, this will be far more
prevalent than group 5 would be for the IoT world and potentially in
general.  I have used both 3 and 5 for html but don't ever use 5 for coap.
The use of 2 and 6 are going to be the most common for both .well-known/core
and a resource directory (which is allowed to control both the base URI and
the relative URI).

Jim

-----Original Message-----
From: Christian Amsüss <[email-masked]> 
Sent: Monday, May 11, 2020 4:21 AM
To: Jim Schaad <[email-masked]>
Cc: 'Carsten Bormann' <[email-masked]>; [email-masked]
Subject: Re: [core] HREF compression encoding

Hello,

I like that too.

> [JLS] [...] An RD is going to be heavily into absolute paths.

Even that depends on how the RD is used. When querying for resources of a
specific type across a network, it will largely consist of one full CRI
([COAP, ...]) for the anchor and one relative ([PATH-..., ...]) for the
target. Queries that yield multiple records from the same server can make
use of CoRAL's base directive.

Kind regards
Christian

--
To use raw power is to make yourself infinitely vulnerable to greater
powers.
  -- Bene Gesserit axiom