Subject: Ted's concerns about wastefulness (Accept-* problem)

From: Bill Newman <[email-masked]>
Date: Fri, 29 Jan 1999 13:26:02 -0800 (PST)

Ted wrote on 19 Jan 1999

> First, my apologies for the delay in commenting on the work Bill and
> Graham have put forward; second, my thanks to both of them for taking
> on the hardest problem this group has left to solve.

Alas, now I have to apologize for my own delayed reply.. Sorry!

I'll quote a big chunk of text, then reply to it.
 
> Having named it hard, I would like to take a crack at defining the
> problem and discussing what methods there are for solving it.  (In
> the text below, I use the term "grouping" to talk about features
> which are associated with each other, but do not fully describe
> the features of a resource or the capabilities of a device.  It's
> not a particularly great phrase, and replacement suggestions are
> welcome).
> 
> The Problem:
> 
> When there are multiple, static representations of a particular
> resource, the features which describe the differences between the
> representations are bounded and the method by which the resources can
> be distinguished are pretty clear.  In our current architecture the
> method for doing so requires, however, that the features which do not
> distinguish between them be repeated in every group.  This means that
> a representation which can be printed on a4 paper, in 16 shades of
> grey, using postscript level 2, using a times-roman 12 point font must
> be distinguished from a representation which can be printed on
> na-letter, in 16 shades of grey, using postscript level 2, using
> courier 12 point font.  (Note, by the way, that the groupings in the
> example imply that you can fit things on to na-letter only by changing
> fonts; you cannot simply vary both the paper and the font).  The
> constant features cannot be left out, because the devices need to
> compare their capabilities against them, but the waste of repeating
> them goes up enormously with the number of representations; with
> dynamic representations, this gets even worse.  Having some way to
> reference the constant features without repeating them would obviously
> be a win.  
> 
> The same is true on the flip side; there are a lot capabilities within
> devices, most of them constant.  Having some way to reference the
> constant set without repeating them is also a big win, especially
> where bandwidth is low.
> 
> 
> The Example in many of our minds:
> 
> In HTTP, sending a full set of Accept-* headers got to be so wasteful
> that many devices stopped using that method for negotiation and
> shifted to User-Agent or other methods (this was, of course, only part
> of the problem, and a full treatment would include the "Accept */*"
> problem and other things).  In a sense, User-Agent became a feature
> grouping identifier; it wasn't a good one, though, because it often
> either implied capabilities which had been disabled or did not include
> extensions.
> 
> Possibilities:
> 
> As Bill and the CCPP work implies, you can use a URI that points to a
> constant grouping.  That URI can be used as a token, for situations in
> which both negotiating parties understand the feature grouping it
> implies.  The URI token will not, sadly, be known to both parties in
> all situations.  If the URI gives a pointer to a location with a
> canonical representation of the features it implies, chances of
> success go up, but it will not always be possible to retrieve the
> representation and disaggregate the features.  (Both for the case in
> which a device cannot use the URI scheme and for the case in which the
> canonical representation of the resource is not available).  A
> traditional URI won't help in the "multiple inclusion" aspect of the
> problem, because you need to assign the groupings dynamically.  We
> could steal the work of the mhtml work and assign an "internal" URI to
> the set of constant items as part of the message, then use that
> identifier as an internal reference.

> The primary problem with the URI method is update; it requires systems
> to constantly keep up with new URIs, some of which will represent the
> same constellation of features.  On the cell phone side, for example,
> Qualcomm dhas branded the phone I have with 5 different company names
> that I am aware of, and I would bet each would require references to
> *their* URI space.

This is part of what I had in mind in when I said that nothing in the
proposal should interfere with the ability of web caches to cache
feature set resources. I believe that the ability to cache the
resources received from URLs will allow industrial-strength servers to
avoid having to do many over-the-net lookups of device capability
sets: they will have seen a PlusZoomerCorp model 44 several times in the
last hour, and the expiration time for its capability expression will
be at least a day, so they'll be able to use the local copy of its
capabilities. It seems to me that this caching behavior could achieve
efficiency within a small constant factor (1.5?) of the efficiency to
be expected from a central registry of standard feature sets.

Some web caching systems are already addressing the situation of
identical content at different URLs: they hash the contents of
everything they cache, notice the duplicate content, and store only
one copy. So, even if vendors do the relabelling that you're concerned
about, the overhead of 5 relabels for Qualcomm phones could be be as
low as 4 extra URL entries in the cache hash table -- a few hundred
bytes at most.

> Any other possible solutions that scale to the extent we need?

Given the existing HTTP caching mechanism, and assuming that device
vendors would have the good sense to use reasonable expiration times
on their capability resources (at least a day) I'd expect an
industrial-strength Web server serving thousands of hits per hour
would hit its internal cache 95+% of the time, and lesser Web servers
would hit the nearest external cache 95+% of the time. (Rationale:
I figure that 95% of the usage would come from the most-common 
500 models or so.)

Incidentally, I'm not just showing a touching faith in human nature
when I conjecture that the vendors wouldn't mess up caching. A vendor
who messes up caching causes problems not just for the system in
general, but for his customers in particular: they're the ones who
have to wait for extra net round trips.

  Bill Newman
  [email-masked]

---

From: "Larry Masinter" <[email-masked]>
Date: Fri, 29 Jan 1999 14:49:44 PST

Suppose we defined a feature called 'fh'. The 'fh' feature
consists of the hash of a feature set. That is:

  a) take a feature set string (as in
    draft-ietf-conneg-feature-syntax)
  b) compute the MD5 hash of the feature set string,
     and represent the result as a string using base64
     encoding, as described in RFC1864, but eliding
     the trailing "==".

The 'fh' feature stands for a full feature set. It can
be combined in booleans, and fully substituted.

You could say

 Media-Accept-features: (& (fh=1ab123342341h) (pix-x<512))

or 

 Media-Accept-features: fh=31aAfXz1234

This doesn't 'waste bandwidth' because it is a very compact
and yet secure representation of what is otherwise a complex
and lengthy feature set.

On the other hand, it does leave the problem of interpretation:
it must be possible to ask someone (e.g., the sender) of a 'fh'
feature to supply the actual feature set for which the proffered
'fh' is the hash.

I could imagine doing this in HTTP using a new error code,
for example, or by adding ANOTHER header which contains the
URL of a 'fh' resolver which might be able to expand proffered
feature hashes. 

In the main case, however -- all interactions after the first,
or interactions where the content doesn't actually depend on
the recipient features -- the extra transmission bandwidth
is small.

Larry

---

From: Ted Hardie <[email-masked]>
Date: Fri, 29 Jan 1999 17:28:01 -0800 (PST)

The lookup problem bothers me, because I believe there will be
relatively few cases where the hash as given would be instantly
recognizable (since it includes both features and feature values).  In
the case of user agent features, some of the hashes could be
pre-loaded into appropriate places, but it is not clear how effective
that would be.  Bill's examples seem to indicate that the number will
be significantly above zero for some caches, but I remain convinced
that the number of cases where it is not obvious will be a large
portion of the total.

So the question for the "fh" possibility is: how and when do we allow
for the hash to be disaggregated?

I suppose we can create a feature that is, in fact, a request for fh
to be disaggregated.  So fhmiss=31aAfXz1234 would be a request that
the value of 31aAfXz1234 be disaggregated.  

Along those lines, some special value to indicate that you should
never send this device a hash could be created so that devices that
couldn't handle them could be sure to avoid them (fhmiss=ALL).

Even with that, I believe we would need to come up with some way of
sending the full set along with the hash thus created.  Perhaps a
better way to do this would be to reserve h. as a prefix and then
use

h.HASH=Yes (To indicate that feature grouping is in use)
h.HASH=No (To indicate that the hash was not understood and the disaggregated
         expression is needed)
h.HASH=Disaggregated expression (To pass the full meaning)
h.none=Yes (To indicate that no HASHes will be understood).

Any thoughts on that?
			Ted Hardie

---

From: "Larry Masinter" <[email-masked]>
Date: Fri, 29 Jan 1999 22:52:29 PST

> recognizable (since it includes both features and feature values).

   (SONY_VGA_MODELXXX) :-
      (| (& (pix-x=640)
            (pix-y=280)
            (color=256))
         (& (pix-x=1028)
            (pix-y=1028)
            (color=256)))
is equivalent in this regard to
   (fh=1aXb124AsDfg) :-
       (| (& (pix-x=640) ...)

i.e., there's a value that expands to other values, that you
either know or have to look up. The advantage of "fh" is that
if Sony's VGA display's features are the same as NEC's, you
don't need to keep both in the table.
 
> In the case of user agent features, some of the hashes could be
> that would be. 

As effective as any other 'preloaded features'.

> Bill's examples seem to indicate that the number will

Yes, but it's not so different for any of the other proposals
for aggregated feature.

> to be disaggregated.  

I think that's mixing descriptive information and protocol in
an unfortunate way. I think disaggregation is likely to be
protocol dependent, even though the semantics of "fh" is
protocol independent.

> So fhmiss=31aAfXz1234 would be a request that

Besides, your transmission is in the wrong way:

sender   <------ capabilities -------------  message recipient
         --- request for disaggregation -->  (capability expander)
         <------ capabilities expansion ---  (capability expander)
         ----------  data ---------------->  message recipient

The sender GETs capabilities (from the recipient or from
a directory describing the recipient).
If the sender requires an expansion, it has to ask the recipient,
the directory, or a service that the recipient or directory have
delegated to.

The request for expansion can't piggyback on top of a capabilities
expression since the request doesn't flow in the same direction
as capabilities themselves.

In HTTP, a 'capability expansion request' might come as
an HTTP error response.

If capabilities are in a directory, then a directory attribute
might point to a capability expansion service.

Alternatively, a capability expression that includes
a feature hash might come with the URL of the service
that is willing to expand the hash. This is similar to
the proposal that you send along a URL as well as
a hash, but turning it upside down.

Larry