Subject: [core] Header suggestion

From: Robert Quattlebaum <[email-masked]>
Date: Thu, 7 Oct 2010 14:10:37 -0700

I just wanted to suggest two new headers to help deal with handling requests with responses which are large, such as when listing the contents of a folder with a large (or even undefined) number of items. The headers are "More" (elective) and "Next" (critical).

While the initial goal of these headers was to facilitate returning the contents of folders with a large (or undefined, in the one-wire case) number of items, this mechanism could be applied to other content types just as easily. 

Quick overview: The 'More' header is used by the server when there is additional content available that is not included in the response. If supported by the client, the client would then send another request containing a 'Next' header to retrieve additional content. The server responds with the additional content and possibly another "More" header. This cycle continues until the client receives a response without a 'Next' header, indicating the end of the content.

The value of the "More" header may blank or it may contain a unique identifier of an unspecified length. If the "More" header contained a value, then this value is used for the "Next" header in the subsequent request. If the "More" header contains no value, then the "Next" header is filled with the last line of the content from the previous response. In any case, the server uses the value of the "Next" header to determine where it should continue from.

This mechanism is superior to using "page indexes" because it allows the current state of the traversal to be included with the requests. This is useful in cases where the server is returning a list of items when it does not immediately know how many are present.

For example, lets say that we have a 1Wire-to-CoAP bridge. There could be thousands of devices attached on the one-wire bus, so storing a list of the connected one-wire devices is not scalable. When a client first requests a list of the connected one-wire devices, the bridge would begin performing the one-wire device discovery traversal. Once the bridge fills up the content of the response, the current state of the one-wire discovery traversal is stored as the value of the "More" header, and the response is sent. The client receives the response, notices the "More" header, and sends another query with a "Next" header containing the value of the previous "More" header. When the server receives this request, it notices the "More" header and uses that to initialize the state of the one-wire device discovery traversal. The server then continues performing one-wire discovery from where it left off.

It may even be possible to reconstruct the state of the one-wire traversal from the value of the last device discovered. In this case, the  value of the "More" header is empty, and when the client sees it in the response it sends another query using the last line of the previous content as the value.

If "page indexes" were used(eg: the value of the 'Next' header is simply the number of packets that have been fetched in the request so far), the device would have to start the one-wire device discovery traversal over from scratch to determine where the start of the given page would be. This is not scalable to large numbers of 1Wire devices.

In the simple case where the device simply has an array of items that is too large for a single packet, it can use a simple index as the value of the "More" field. Since the value of the "More" and "Next" fields is opaque to everyone except the server that generated it, the server implementation has a lot of flexibility of how to implement large queries.

In the event that the server state has changed in such a way that an incoming request with a "Next" field is no longer relevant, a reset response should be sent to the server.

Please let me know your thoughts.

__________________
Robert Quattlebaum
Jabber: [email-masked]
eMail:  [email-masked]
www:    http://www.deepdarc.com/

---

From: Carsten Bormann <[email-masked]>
Date: Thu, 7 Oct 2010 23:42:14 +0200

Interesting.

A couple of quick comments:

-- 'More' cannot really be elective, as a client not understanding this option would think it has received the whole resource when it only received a part of the data.  Alternatively, 'More' could be part of the data (i.e., the resource representation is complete in its own right because it contains the pointer to its continuation via an embedded link).

-- 'Next' may not really be needed as an option since the client can simply use a different URI for the next request (e.g., by adding a query).  In the most RESTful case, 'More' gave the client just that URI.

What's missing for a general mechanism is a way for the client to reconstruct the entire resource from the parts received (is it just binary concatenation of the representations?).  The answer might depend on the media type of the resource.

I think having an option that acts like an HTTP Link: header, with the right relationship type, might be another approach (and might have synergy with the way we use the Link header syntax for discovery).

I like grounding this discussion in specific examples.  Can you provide more details of the 1wire example you have in mind?

Gruesse, Carsten

---

From: Robert Quattlebaum <[email-masked]>
Date: Thu, 7 Oct 2010 19:02:34 -0700

Hello Carsten!

On Oct 7, 2010, at 2:42 PM, Carsten Bormann wrote:

> -- 'More' cannot really be elective, as a client not understanding this option would think it has received the whole resource when it only received a part of the data.  

Fair enough. I was thinking more or less about the directory listing case, in which I figured understanding the first few items was better than not understanding anything.

> Alternatively, 'More' could be part of the data (i.e., the resource representation is complete in its own right because it contains the pointer to its continuation via an embedded link).

I think I'd rather make "More" be critical. Making the "More" mechanism a part of the data itself sounds like it would make things more complex.

> -- 'Next' may not really be needed as an option since the client can simply use a different URI for the next request (e.g., by adding a query).  In the most RESTful case, 'More' gave the client jus…

What if the original URL already had a query component?

Specifying a URI in the "More" field (even if it is just a path and not a full URI) could increase the packet size of the responses significantly, when they are already being clipped by this mechanism. Also, all subsequent requests via the "Next" header are conceptually just an additional part of the original request.

Large responses would be stored in a CoAP cache as a single cached item---it would combine all of the content form multiple requests and store the entire content. When requested by a client, the cache would break up the request itself. I think this approach would be better than caching individual responses. This concept would also scale well to an HTTP-CoAP gateway.

> What's missing for a general mechanism is a way for the client to reconstruct the entire resource from the parts received (is it just binary concatenation of the representations?).  The answer migh…

I think simple binary concatenation is the way to go, no matter what content-type is being used. Anything else would be problematic, IMHO.

However, one thing that I think *should* be dependent on content-type is where in the content you can break it into multiple packets. For example, when requesting a directory listing, each response must only contain full entries. A partial entry at the end of one response which would be continued from the next response would not be allowed for that content type. Without this, my rule "if More is empty, use the last line of the content for Next" wouldn't make any sense. Other content-types (maybe text/csv) may have similar rules, but in any case the client only has to do one thing: concatenate.

> I think having an option that acts like an HTTP Link: header, with the right relationship type, might be another approach (and might have synergy with the way we use the Link header syntax for disc…

This breaks the idea that this is really just one big request, and would make caching and HTTP proxies more complicated, IMHO.

> I like grounding this discussion in specific examples.  Can you provide more details of the 1wire example you have in mind?

I'm not sure exactly what part to elaborate on, so if I don't cover what you were interested in let me know and I'll be happy to go into more detail.

I'm a big fan of the 1wire bus. It has a lot of great features such as a practically unbounded limit of devices on a single bus, device discovery, and alarm discovery. For example, you could put hundreds of temperature sensors on a single 1wire bus, each with their own high and low temperature alarm values stored in non-volatile memory. You could periodically scan the bus for temperature changes and alarm conditions, with the only state being what action to take for a given device.

What I'm imagining is a stateless 1wire-CoAP bridge that has a completely dynamic file structure. When you query the devices folder, the device starts doing a "Search ROM" procedure on the 1wire bus to start enumerating the devices. Each device would appear to be a directory, named by the unique device id. When you get the contents of the directory, items are automatically generated and returned based on what type of 1wire device it is. For example, when you do a GET request for <coap://one-wire-bridge.local./devices/0123456789abcdef/temp>, it will start attempting to read the temperature from device 0123456789abcdef on the 1wire bus. Adding more temperature sensors, or switches, or digital-pots, or A/D converters, is as simple as adding the appropriate device to the 1wire bus.

In order to keep things stateless, I tried to make the More/Next mechanism as flexible as possible without making things excessively complex. Starting the traversal over from scratch every time a next request came in seemed very wasteful, so being able to carry around the state of the traversal inside of the message itself is essential. The bridge never really knows how many devices are connected to the 1-wire bus at any given moment, and it doesn't need to. 

IMHO, the most important case that this mechanism allows is cases where you have a large number of items to return in response to listing the contents of a folder. Using this for retrieving other content types may be useful, but I think we should avoid any urge to turn this into some sort of general case for large transactions. (eg: This mechanism does not address a way to make large PUTs, nor do I think that would be a good idea)

Let me know if you would like any additional clarification.

__________________
Robert Quattlebaum

---

From: Carsten Bormann <[email-masked]>
Date: Sun, 10 Oct 2010 21:22:31 +0200

> I'm a big fan of the 1wire bus.

Actually, I think you will find quite a few 1-wire fans in the IETF...

I unfortunately don't know much about 1-wire, but let me speculate a bit.

The enumeration only tells you about the existence of the devices (and
their type), not what they actually do/are sensing -- is the sensor
measuring the refrigerator or the outdoor temperature?  So I'd assume
you will do an enumeration only during commissioning/bootstrap, i.e.,
relatively infrequently.  I'm therefore happy with something that is
not extremely efficient (but of course has to be reasonable,
i.e. still in the same order of magnitude a very efficient
version would be).

If the problem is just sending responses larger than you are
comfortable with in one packet (MTU, delivery probability of
adaptation-layer-fragmented packets, etc.), then the block option
gives you a quite efficient way of doing this -- the total overhead is
two bytes (three bytes if there are many blocks).  Note that, for GET
requests, there is never a need to keep per-client state at the server.

But I think you are interested in *semantic* fragmentation.  That
needs to be discussed in the context of the specific semantics.  So
how would the enumeration access look like?  CoAP has
/.well-known/core for discovery, which is pretty much what enumeration
would be about here.

So I'd expect a stateless, minimal 1-wire/CoAP Gateway to have a
/.well-known/core that looks approximately like:

</0699127fb0e66679>;type="application/1wire";n="HU10",
</4633d965cc03b08b>;type="application/1wire",
</77000000023CEC12>;rel="section";type="application/link-format"
</78cdd38e7ab74e39>;type="application/1wire",
</.well-known/core?after=78cdd38e7ab74e39>;rel="section";type="application/link-format"

(Of course, there may be other useful metadata here -- I know too
little about 1-wire to fill this in properly.  And we might have a
numeric ct for application/1wire, if that is even a meaningful
concept.)

/77000000023CEC12 points to a 1-wire switch, which again can be
queried for its description (it itself is represented by another
link-format document).

The last link, /.well-known/core?after=78cdd38e7ab74e39, is pretty
much what your "more" option would be, except that it is on a semantic
level in the resource representation.  Note that the *server* decides
how this link looks like -- there is no "link arithmetic" in REST.

Yes, this approach needs more bits than an optimized one.  What you
gain is more flexibility.  I'm not going to do the "Hypermedia as the
Engine of Application State" spiel here right now, but this is a
powerful concept that we might want to make use of.

Gruesse, Carsten

---

From: Robert Quattlebaum <[email-masked]>
Date: Sun, 10 Oct 2010 15:25:24 -0700

Hello Carsten!

> Actually, I think you will find quite a few 1-wire fans in the IETF...

Good to hear. It's a clever protocol. Too bad Dallas-Semiconductor/Maxim own it, but it's just too useful to ignore.

> measuring the refrigerator or the outdoor temperature?  

You are correct: the type of the sensor is encoded as a part of it's 64-bit ID, so what the device is and how to use it is discoverable. You could also perform discovery for specific classes of devices. For example, you could have a folder for temperature sensors, a folder for ADCs, a folder for digital switches, a folder for real-time clocks, etc.

As for attaching specific human-readable labels (like "Bedroom temp", or "Basement temp"), yes, you would need a separate database to look up what the names of the devices are. But I think such functionality is not necessarily a requirement.

> So I'd assume

It is true that in general you don't need to list devices very often. More often they will be referenced directly.

In terms of big-O notation, the efficient traversal would be O(n), whereas a traversal which would require that the "Search ROM" process start over from scratch would be O(N^2).

> requests, there is never a need to keep per-client state at the server.

My concern is partially packet size, but it is also the ability to parse larger amounts of data at layer 7. If we let Layer 3 (IP) or Layer 2 (802.15.4+6LoWPAN) do the fragmentation, then we need to have enough RAM to hold a single large packet. Using the method I was describing, processing can be performed on large amounts of data (much larger than 64k, the packet size limit for non-jumbo IPv6) incrementally by constrained devices with little RAM at whatever pace they can work at.

> queried for its description (it itself is represented by another

I would imagine that all 1wire devices would be of type "application/link-format", with specific attributes enumerated therein. At least, that's how I'm building it right now. Overall what you are describing looks reasonable, except for the last entry, which I will elaborate on below. :)

> powerful concept that we might want to make use of.

It actually seems less flexible to me, because it only works for the "application/link-format" content-type. Support using other content-types would have to be implemented specifically for that content-type. The More/Next headers I am suggesting works transparently with every content-type, uses less bits, and gives a large amount of implementation flexibility. For what it's worth, I'm using them right now in my test implementation, and they work great.

The More/Next headers don't break REST. Caches would fetch and cache an entire document and break it up into chunks when queried. CoAP-only proxies can ignore the headers entirely. CoAP-HTTP proxies also have a clear way to work:

For HTTP->CoAP: you make an HTTP request and the proxy sends out a CoAP request. It notices a More header, sends out the content to the HTTP connection (but doesn't close it), and then sends out another CoAP request with the Next header. This process would continue until the entire content is retrieved, after which the connection is closed. To the HTTP client it appeared to be a single request which loaded gradually.

For CoAP->HTTP: the proxy would receive the CoAP request and translate that into an HTTP request. As the content comes in from the HTTP response, the CoAP content buffer fills up and a CoAP response is sent, along with a More header containing an Id to reference the current connection. When the HTTP proxy receives the CoAP request with the appropriate Next header, it dumps more http response content into the CoAP response and sends that back to the CoAP client, including another More header if necessary.

__________________
Robert Quattlebaum

---

From: Carsten Bormann <[email-masked]>
Date: Mon, 11 Oct 2010 01:04:08 +0200

> My concern is partially packet size, but it is also the ability to parse larger amounts of data at layer 7. If we let Layer 3 (IP) or Layer 2 (802.15.4+6LoWPAN) do the fragmentation, then we need t…

Yes, that is one of the reasons the block option was invented (have you looked at draft-bormann-core-coap-block-00.txt?), which works on slices of resource representations, not on packets.
Semantic fragmentation may or may not simplify the handling of the boundaries between the fragments; that depends a lot on a common understanding of what good boundaries would be between client and server.
In the end you need a media type specification if you want that agreement.

> It actually seems less flexible to me, because it only works for the "application/link-format" content-type.

The intention is certainly not that link-format is the only type that carries links, so I don't understand why we would have that limitation.  XML/EXI and JSON certainly can carry links.  Any new format you invent can, too.

>  Support using other content-types would have to be implemented specifically for that content-type.

Yes, that's kind of implied if you really want *semantic* fragmentation.

> The More/Next headers don't break REST. Caches would fetch and cache an entire document and break it up into chunks when queried.

That is certainly the intention with the block option.

> CoAP-only proxies can ignore the headers entirely. CoAP-HTTP proxies also have a clear way to work:
> 

The proxy would need to understand how to aggregate the semantic fragments into a larger representation.
I don't know how to do this in the general case (although I might be able to cook up rules that work in certain cases for XML/EXI and JSON).

> For CoAP->HTTP: the proxy would receive the CoAP request and translate that into an HTTP request. As the content comes in from the HTTP response, the CoAP content buffer fills up and a CoAP respons…

All this is done nicely on a sequence-of-bytes level by the block option.
(Again, I don't know how to do this on a semantic level without interpretation of the media type by the proxy.)

I think some of the disconnect here is that you seem to have a very specific idea of the media types that you want to handle (e.g., there is no concept of "lines" in JSON or EXI, so I wouldn't even know what "More" would mean).
Maybe we need to look into this interesting class of media types some more and see how CoAP could support them better.

Gruesse, Carsten

---

From: Robert Quattlebaum <[email-masked]>
Date: Sun, 10 Oct 2010 17:10:07 -0700

> Yes, that is one of the reasons the block option was invented (have you looked at draft-bormann-core-coap-block-00.txt?), which works on slices of resource representations, not on packets.

I was not previously aware of draft-bormann-core-coap-block-00.txt. I've had a look, and it looks like it is trying to solve the same problem, but going about it in a different way. The block spec assumes that the resource being requested can be accessed in a random-access fashion. This would require a stateless 1wire traversal to be O(N^2) instead of the more optimal O(N). My More/Next headers would allow parsing of a 1wire traversal with O(n), but does not allow for random access. Both mechanisms avoid creating conversation state on the server. 

I'll examine the block spec in more detail, thanks for bringing it to my attention. Perhaps there is some synergy in the approaches.

> In the end you need a media type specification if you want that agreement.

My hope was to avoid any changes at all to the actual content. As for where to break up the original content, I suggest (for text formats) the closest newline prior to the end of max size of content, and for binary formats simply anywhere convenient. But even if we dropped the whole "break things up by newlines" concept and go with simple break-on-max-size, it would still be very useful.

> The intention is certainly not that link-format is the only type that carries links, so I don't understand why we would have that limitation.  XML/EXI and JSON certainly can carry links.  Any new f…

What about formats already invented? What about images, or other pre-existing binary formats? (Granted, the "Block" attribute is just as suitable for images)

> I don't know how to do this in the general case (although I might be able to cook up rules that work in certain cases for XML/EXI and JSON).

With More/Next headers, aggregating the fragments into a larger representation is easy: simple binary concatenation. Works for all content-types. The only question is where do you define the boundaries to be for splitting up large content. Originally my thought was to use newlines for text files, and use the nearest byte boundary for binary files. A single fragment doesn't need to be individually parsable because you would never get an individual fragment without having parsed all of the fragments before it. 

> I think some of the disconnect here is that you seem to have a very specific idea of the media types that you want to handle (e.g., there is no concept of "lines" in JSON or EXI, so I wouldn't even…

"More" in that case would always have a defined value by the server and would never be empty. The case where the "More" header is empty is an optimization that the server may or may not choose to use, and it would only use it if it made sense for the given content type.

__________________
Robert Quattlebaum

---

From: Robert Quattlebaum <[email-masked]>
Date: Mon, 11 Oct 2010 12:02:02 -0700

So I've taken a closer look at draft-bormann-core-coap-block-00, and I have some observations.

It would appear that both the Block header and my More/Next proposal(1) have the same goals, but have different strengths and weaknesses. The key differences are:

	• draft-bormann-core-coap-block-00 has only one header, whereas my More/Next proposal used two. (Although the More/Next mechanism could easily be changed to require only one)
	• draft-bormann-core-coap-block-00 has strictly defined block sizes, whereas my More/Next proposal does not (it is up to the server to decide).
	• draft-bormann-core-coap-block-00 appears to have an upper limit on the size of a single transfer, whereas my More/Next proposal does not.
	• draft-bormann-core-coap-block-00 would appear to allow for random access, although this is not covered or even mentioned in the internet-draft. My More/Next proposal does not allow random access.
	• My More/Next proposal allows the server to store some client-opaque state in the messages itself, freeing it from possibly needing to store (or restore) state on the server. draft-bormann-core-coap-block-00 does not allow this.

Unless random access is an important feature, it seems like a more flexible approach for dealing with result messages with large amounts of content would be for the value of the block header to be entirely opaque to the client. It's presence would indicate the existence of additional content, and to retrieve that content an additional request containing the block header and value from the previous response would be sent. This approach would:

	• Allow for unbounded content-sizes.
	• Marginally simplify client implementation.
	• Give maximum flexibility to the server implementation.
	• Allow traversal state to be stored inside of the requests themselves. (e.g.,this allows for O(n) 1-wire discovery; compared to O(n^2) for the current block proposal)
	• Allow for arbitrary block sizes, at the discretion of the server implementation.

If random access turns out to be desirable for certain applications, perhaps we could implement a "Range" header, analogous to that specified in (2), specifically for the purpose of allowing random access.

Thoughts?

(1) <http://www.ietf.org/mail-archive/web/core/current/msg00764.html> : [core] Header Suggestion
(2) <http://www.w3.org/Protocols/rfc2616/rfc2616-sec14.html#sec14.35> : HTTP/1.1 Header Field Definitions, Sec 14.35 Range

__________________
Robert Quattlebaum