Subject: Re: Pipelining in HTTP 1.1

From: Jamie Lokier <[email-masked]>
Date: Wed, 1 Apr 2009 11:23:59 +0100

Roy T. Fielding wrote:
> or even extend HTTP
> such that the request/response contains some form of matching ID.

I did this in an application-specific extension of HTTP, and learned
something not obvious to me.

Beware if you allow reordering and really use it, you can get into
deadlock or unbounded-buffer-needed scenarios, unless you also
implement some kind of per-ID flow control.

I found interleaving HTTP-style chunks, labelled with a
request-response ID, and per ID receive windows, works well.  Many of
the annoying problems of HTTP pipelining go away.

However, without per-ID flow control, if a process consuming one of
the requests or responses stalls, it forces all the others to stall
too.  This is because the other only flow control signal is the TCP
receive window closing, which blocks the whole transport.

BEEP over TCP shows how to solve this, though the spec leaves you to
figure out for yourself why.  BEEP itself is a protocol to multiplex
logical streams over a single transport stream.  The BEEP over TCP
spec adds a bit more syntax, so each logical stream advertises its own
independent receive window.  This prevents a single slow process from
stalling the streams of others.

Unfortunately BEEP is a bit heavy as it stands for extending HTTP like
this, because BEEP relies on XML, and because the channel setup cost
is not particularly cheap either in bytes or round trips.

In my own extended-HTTP-like, I've adopted "fire and forget" lazy
stream creation whenever a new request is sent, subject to flow
control for the transport stream as a whole (window of max requests in
flight) and per channel (window of bytes in flight per channel, no
window required when there's only one in flight).  It sounds like the
SCTP negotiated number of channels is similar, especially with the
extension to let that number be increased.

-- Jamie

---

From: "Steingruebl, Andy" <[email-masked]>
Date: Wed, 1 Apr 2009 10:00:40 -0600

> -----Original Message-----
> From: [email-masked] [mailto:[email-masked]]
On
> Behalf Of Jamie Lokier
> Sent: Wednesday, April 01, 2009 3:24 AM
> To: Roy T. Fielding
> Cc: Preethi Natarajan; [email-masked]; Jonathan Leighton; Paul D.
> Amer; Fred Baker (fred)
> Subject: Re: Pipelining in HTTP 1.1
> 
> Roy T. Fielding wrote:
> > or even extend HTTP
 
Out of curiosity did you just use sequential ID's to track this, or
something more like a GUID?  Several folks have been toying around with
protocol-level changes to mitigate/prevent Response-Splitting attacks
and being able to tie request+response is critical.

Not that webapps should have this vulnerability, but it wouldn't really
be possible with strict 1:1 correlation between request and response.

- Andy

---

From: "Preethi Natarajan (prenatar)" <[email-masked]>
Date: Wed, 1 Apr 2009 17:27:52 -0400

> From: Jamie Lokier [mailto:[email-masked]] 
> Cc: Preethi Natarajan (prenatar); [email-masked]; 
> Jonathan Leighton; Paul D. Amer; Fred Baker (fred)
> Beware if you allow reordering and really use it, you can get 
> into deadlock or unbounded-buffer-needed scenarios, unless 
> you also implement some kind of per-ID flow control.
> 
> request-response ID, and per ID receive windows, works well.  
> Many of the annoying problems of HTTP pipelining go away.
> 
> However, without per-ID flow control, if a process consuming 
> one of the requests or responses stalls, it forces all the 
> others to stall too.  This is because the other only flow 
> control signal is the TCP receive window closing, which 
> blocks the whole transport.
> 
> BEEP over TCP shows how to solve this, though the spec leaves 
> you to figure out for yourself why.  BEEP itself is a 
> protocol to multiplex logical streams over a single transport 
> stream.  The BEEP over TCP spec adds a bit more syntax, so 
> each logical stream advertises its own independent receive 
> window.  This prevents a single slow process from stalling 
> the streams of others.

I assume by "stall" you mean that the transport is ready to deliver data
but the application process is busy doing something else. 

If yes, wouldn't this problem go away when a single thread/process reads
data from the socket and moves the data to appropriate response buffers
(as done in Firefox) instead of multiple threads/processes, one per
response, reading from the socket? 

Still, I think that the BEEP approach would suffer from head-of-line
blocking during packet losses, which is what SCTP streams solve. In
BEEP, the logical streams are multiplexed over a single TCP bytestream
-- if a TCP PDU is lost, successive TCP PDUs (belonging to different
responses) will not be delivered to BEEP/app. 

Preethi

---

From: Jamie Lokier <[email-masked]>
Date: Sat, 4 Apr 2009 03:58:18 +0100

> but the application process is busy doing something else.

Yes.

> response, reading from the socket? 

Yes but that requires unbounded buffering in the receiving
demultiplexer.  That's why the problem is _either_ stalling the
transport or unbounded buffering required.

That's ok for a applications like Firefox, when all the received data
is stored in the application anyway.  If the server sends too much in
one response, the application will complain anyway.

But imagine a proxy which is forwarding the individual responses to
different processes each with independent behaviours.  (It's a
requirement that processes can consume independently - otherwise
what's the point in multiplexing different responses anyway?)

One of the process might be consuming a very large stream (even
infinite), at its own rate.  If that process stops reading, the proxy
must buffer that large stream to continue forwarding responses to the
other processes.

I said it's ok for applications like Firefox.  But even Firefox may
have internal processes, with one of them consuming a large or
infinite stream of data in one response, while other internal
processes handle other responses.  This happens in certain AJAX models.

So you need to handle this even for things like Firefox.  And hence,
you need to handle this for an extension to HTTP which multiplexes
different messages out of order.

The basic issue is that rate at which some abstract process consumes
data must be conveyed to the sender somehow to avoid unbounded
intermediate buffering or head of line blocking.  Per stream flow
control when there's more than one stream achieves this, although it
might not be the optimal solution.  With just one stream at a time,
the TCP window does this by itself - and ordinary HTTP implementations
rely on this.

> responses) will not be delivered to BEEP/app. 

Yes.  SCTP is superior in this respect.  But inferior in the sense
that I've never seen a NAT or firewall which will forward SCTP :-)
You'll need SCTP-over-UDP to get anywhere with that nowadays.

BEEP also suffers from excessive round trips to set up new streams.

There's a BEEP extension proposal to support lightweight substreams
within streams to get around this, but that proposal suffers from not
letting you arbitrarily interleave messages of substreams in the same
stream, making it somewhat pointless for what we're talking about.

-- Jamie

---

From: Jamie Lokier <[email-masked]>
Date: Sat, 4 Apr 2009 04:15:42 +0100

Steingruebl, Andy wrote:
> Jamie Lokier wrote:
> something more like a GUID?

I use client-selected IDs per request, and I let them be alphanumeric
(token syntax).  So you could use GUIDs if you wanted, but my
implemention just uses numbers :-)

Sequential numeric IDs are simpler, but I didn't want to imply an
arbitrary limit where they wrapped around or something.

The client is free to reuse IDs which are no longer in flight.

In fact the client can reuse IDs which are already in flight, and this
has the effect of forcing the response ordering to be retained, the
same as HTTP pipelining (just for that ID).

Absence of an ID is treated as just another ID value, so the ordering
rule means it degrades gracefully to HTTP pipelining when you don't
send the ID header.

> Several folks have been toying around with

That's a different requirement, but you can obviously use the same
mechanism.

I don't have response-splitting attacks in my application which uses
this ID extension because (a) it's all private stuff at the moment,
and (b) every message has a clearly defined length, set in a header or
a chunk header.

I suspect avoiding Response-Splitting cannot be solved by tying
requests to responses with a simple ID.  If you can fake protocol in
the body, you can fake IDs too.  Randomised IDs (the reason you might
be using GUIDs, but the important part is unpredictability isn't it?).

But even randomised IDs won't prevent attacks which trick a receiver
into receiving some chunks of a different response as content, parsing
it on the receiver (e.g. in Javascript in a browser) to get the other
response's ID, sending that ID somewhere malicious, which then knows
the ID to attach to other chunks for malicious injection later in the
same stream.

If the protocol level is to be modified, then just do it properly: fix
pipelining to do out-of-order chunk multiplexing properly and safely
with clearly defined message boundaries, probably using chunks.  Really.

> be possible with strict 1:1 correlation between request and response.

Indeed it's not.  But if you're seeing the existing well-defined
message boundary rules subverted, a server or proxy is at fault
somewhere for not enforcing the rules.  If you can't solve that
problem, how will adding ID headers make it work?  At most they'll
improve the reliability of detecting a mistake, but I suspect
malicious attacks will still find ways around it, although they'll be
more difficult.

-- Jamie

---

From: Salvatore Loreto <[email-masked]>
Date: Sun, 05 Apr 2009 12:05:49 +0300

> the TCP window does this by itself - and ordinary HTTP implementations
first I think that the major benefit that could come from using SCTP 
instead that TCP is
in the Proxy to Proxy or Proxy to Server side, where a Proxy can use 
separate streams
to handle different requests coming from different clients.
so if we suppose that a Proxy X receives requests from N clients that 
all want to contact Server Y,
then Proxy X instead of opening N TCP connection, it will open one 
single SCTP association with
N streams and it will use one specific stream to handle in order 
request/response coming from each specific client.

I am still not convinced in using SCTP in the client-proxy or 
client-server side.

about the "stall" problem Jamie is raising, I agree that the fact that 
SCTP use a single receive buffer
per Association is a problem, one possibility I can immagine in SCTP is 
to use the
"Ancillary Data" to communicate to the Sending side to slow done or even 
stop sending data on a specific stream.

> You'll need SCTP-over-UDP to get anywhere with that nowadays.
yes, I agree that SCTP does not work with NAT nowadays!
but hopefully the situation will improve in the near feature.