Subject: [BEEPwg] Asynchrony and BEEP

From: "Thomson, Martin" <[email-masked]>
Date: Fri, 16 May 2008 01:59:05 -0500

Hi All,

Since the IETF WG wrapped up, this list seems to be fairly quiet, but I
have a technical matter I'd like to discuss.

I have an asynchronous application that needs a protocol.  Similar to
the experience of RFC 3117, I did a little research on protocols in the
hopes of finding one that fits (more or less).

Until recently, I was confident that BEEP provided all that I needed.
It turns out a fundamental assumption I had made was quite wrong
(there's a lesson in that).  I had assumed that the presence of a
message number that must be unique would mean that responses to messages
were correlated based on this number.  Someone recently pointed out
Section 2.6 of RFC 3080 that disabused me of this notion - channels are
entirely serial in each direction.

Having read more material on the subject, I'd like to describe the
problem that this presents.  I'd also like to discuss a possible
solution.

The application in question (location services) requires that any
protocol it uses scales well.  Our estimates predict a wide range of
usage rates, but at the upper end the rate could be something in the
order of 100s of requests per second.  However, throughput is not the
only concern.  Requests take varying amounts of time to be processed;
current estimates are anything from milliseconds to somewhere between 10
and 20 seconds.

Case study: an unnamed protocol [1] from the same field that uses an
HTTP binding.  Similar to the application I describe, this protocol
requests can take anywhere from milliseconds to minutes to process.
Since HTTP suffers from head-of-queue blocking, in order to get
reasonable throughput, more connections are opened.  There is a very
simple formula that determines how many connections you need:

  number of connections = average response time x rate of transactions

I probably don't need to go into the details, so suffice it to say that
this is somewhat inefficient.  Grossly inefficient.  Providing a system
that serves this many connections is tricky, even though there might be
more than sufficient processing capacity to service those requests (most
of the time is spent waiting, so this isn't as hard as it sounds).

Back in the land of BEEP, channels also exhibit head-of-queue blocking.
This implies that the same solution is necessary if high throughput is
required.  It's interesting to note that some APIs provide channel
pooling features [2].  The problem is much more manageable because
channels are much cheaper than connections, however they don't cost
nothing.  And I'm not talking about system resources, but also about
development effort and maintenance.  To add to the grief, a BEEP peer
need only support 256 channels, so asking for 10000 channels is probably
pushing it.

All of this would work much more smoothly if responses could be provided
out of order.  It turns out that there is no technical or protocol
reason that forces channels to be serial.  After reading through all the
relevant documentation (all the RFCs, the BEEP book), I haven't seen any
evidence that suggests a strong technical reason for making channels
this way.  The book draws an analogy between a channel and a thread,
which is convenient for explanation but doesn't provide any
justification.

I'd like to put message numbers to use for request-response correlation.
Message number as specified only provides a means of detecting protocol
errors.  This provides a second layer of defence against a buggy peer,
after the sequence number.  Message number is not, contrary to what is
implied, used to correlate response with request; correlation can be
done by relying on response ordering alone.

I toyed with the thought of a tuning profile that enabled asynchrony,
but that has the unfortunate drawback of affecting all channels.  In
some cases the serial nature of channels is desirable.

The current solution I favour is putting the unused 'features' attribute
from the BEEP greeting to work.  If both peers provide a feature list
that includes ``async'', then they may choose to create asynchronous
channels.  A channel that is created using ``<start number="3"
async="true">...'' [3] would not be subject to the reply ordering
constraint from Section 2.6.1 of RFC 3080.  Responses sent on that
channel would be matched to their requests by the message number.

I like BEEP.  It satisfies most of the requirements.  This one small
thing is all that it lacks.  I am willing to take this to the IETF, but
I want to get a feeling for what the BEEP community thinks of the
proposal.  Would this functionality be useful where you use BEEP?  Can
you see any technical shortcomings in this proposal?

Regards,
Martin 

~~
[1]
<http://www.openmobilealliance.org/Technical/release_program/mls_v1_1.as
px>

[2]
<http://www.aspl.es/fact/files/af-arch/vortex/html/group__vortex__channe
l__pool_ga7130833a4500c9647fd84ad21dc2093.html>

[3] This wouldn't be valid XML, by the strict terms of the
specification.  Since BEEP doesn't reference the DTD, BEEP control
messages aren't valid either, so the point is probably moot.  Since BEEP
doesn't use namespaces in XML, I can't see a better way to extend the
XML syntax. 

~~
------------------------------------------------------------------------------------------------
This message is for the designated recipient only and may
contain privileged, proprietary, or otherwise private information.  
If you have received it in error, please notify the sender
immediately and delete the original.  Any unauthorized use of
this email is prohibited.
------------------------------------------------------------------------------------------------
[mf2]

_______________________________________________
BEEPwg mailing list
[email-masked]
http://drakken.dbc.mtview.ca.us/mailman/listinfo/beepwg

---

From: Francis Brosnan Blazquez <[email-masked]>
Date: Mon, 19 May 2008 15:41:01 +0200

Hi Martin,

Assuming the set of details you provided, I think you are facing a
problem which is simple to solve using features already provided by
BEEP. Here is how:

- Create two channels, one to push jobs and one to receive jobs
finished. 

- The channel to push jobs use a MSG/RPY pattern. Once the listener
receive a job request (MSG), it is queued/handled as desired, but before
doing that, a RPY must be sent to acknowledge MSG reception.

- The channel that receive jobs finished issue an initial MSG to open
the possibility to receive ANS replies that carries jobs finished. Now,
each time the listener have a job finished he send it back as an ANS
reply to the MSG received on this channel. This will allow to send in
any order jobs as quickly as they are finished.

Now, I would like to comment some assertions you have done:

1) (Please see 3.4 and 4.1 of [1]) The technical reason to make
intra-channel processing to be serial is because it is the most widely
available request/response model in use today. Thus, it is required to
be represented in BEEP, mainly because people use it. You say it is used
in some cases (????) but it is by far the most popular model used in
connection oriented escenarios (like HTTP). 

However, what makes BEEP different, is that channel pipeline is *not*
the only one invocation model. You can use several channels or use
ANS/NUL replies semantic to implement independent exchanges.

Channel pipeline is a *core* BEEP feature, well understood and well
perceived by people using BEEP. What you are proposing is a protocol
change that have also consequences in what also makes BEEP different and
useful: how it is handled session close.

2) Saying channels suffer "head-of-line" is quite inexact. I believe a
protocol can suffer "head-of-line" when there is no alternative (like
HTTP). BEEP channels have several already available and well supported
invocation options to specifically avoid "head-of-line". 

3) Maybe this could change in the future, but at this moment, features
and profiles can only extend BEEP function giving semantic but never to
modify base BEEP protocol defined at RFC3080 (maybe I'm wrong but I
believe this is the essence).

4) Message number is not only used for protocol errors, but also to give
the notion of unique and identificable transaction (which is, again,
commonly required), and to allow APIs to reply to a particular message. 

Cheers,

[1] http://www.rfc-editor.org/rfc/rfc3117.txt
-- 
Francis Brosnan Blazquez <[email-masked]>
Advanced Software Production Line, S.L.

---

From: "Thomson, Martin" <[email-masked]>
Date: Wed, 21 May 2008 01:09:57 -0500

Hi Francis,

Thanks for the response.

I am taking an existing protocol and binding it to BEEP.  Using two
separate channels in the fashion you describe is only possible if I
wanted to (or was able to) change the protocol payload.  Currently, the
protocol is bound to HTTP.  The idea was to move to BEEP to allow for
increased throughput.  However, the method you suggest requires that
request/response correlation is performed at a higher layer than BEEP.
This either requires modification of the application protocol, or
insertion of another protocol layer.  This is either infeasible or
unpalatable.

As far as your comments go, I had a little trouble correlating each
comment with my original statements.  Apologies if I've misinterpreted
anything you've said.  I'll reply inline below.

> ANS/NUL replies semantic to implement independent exchanges.
 
In response to 1) I'd say that your reason is not technical at all.  I
have no problem with someone making the decision to be serial and for
the reason to be no more than personal preference.  As for the rest, see
my above comments.

> useful: how it is handled session close.

I examined this in some detail - there is no change required to how a
close is handled.  A peer is expected to wait until all outstanding
requests are complete before responding to a close request for each
channel.  Session/connection close is rejected when there are open
channels.  Neither would need to change if full asynchrony were enabled.

> invocation options to specifically avoid "head-of-line".

I'll restate: an individual BEEP channel suffers head-of-line in the
same way that an individual HTTP connection suffers head-of-line.  The
same workarounds apply to each.  For instance, I've seen your suggested
workaround standardized for an HTTP application.

You could consider this misleading, so I'll qualify the statement: BEEP
is less crippled by this for a number of reasons.  A BEEP channel is
more lightweight than a TCP connection and you are less susceptible to
problems like intermediate NAT.
 
> believe this is the essence).

The IANA registry lists no features, so it is hard to make any statement
about what can (or can't) be achieved with them.

If you never need to rely on modified/extended RFC 3080 behaviour,
profiles could do everything you could want to do.  Logically then,
features are reserved for where the base 3080/3081 specifications come
up short and something extra is needed; something that a profile can't
do, like changing or adding to control channel message semantics.

> commonly required), and to allow APIs to reply to a particular
message.

If message number was removed from the specification, BEEP would still
work.  Replies must be provided in the same order that the requests were
made.  Request/response correlation can be performed entirely through
message ordering.  Therefore, message number is entirely redundant.
Beep4j (the API I am most familiar with) doesn't even look at the
message number for replies, except when checking for protocol errors. 
------------------------------------------------------------------------------------------------
This message is for the designated recipient only and may
contain privileged, proprietary, or otherwise private information.  
If you have received it in error, please notify the sender
immediately and delete the original.  Any unauthorized use of
this email is prohibited.
------------------------------------------------------------------------------------------------
[mf2]

---

From: Francis Brosnan Blazquez <[email-masked]>
Date: Wed, 21 May 2008 23:47:47 +0200

Hi Martin,

> insertion of another protocol layer.  This is either infeasible or

Certainly. Maybe you can use a MIME header to flag the payload with a
transaction number.

> anything you've said.  I'll reply inline below.

Ok.

> the reason to be no more than personal preference.  As for the rest,

Ok. Looking at the request/response model as a natural evolution from
the local function invocation, it is clear that order matter.

You invoke the function/service looking for some result/resource, which,
with great probabilities will be used for next invocations, or to stop
current flow if an error occur. That's why you need the serial nature
(and the reason why it is widely present in other protocols). 

More than a technical reason, I see an implementation issue. Most of
languages used to write networked applications do it by invoking
functions in order and according to the results they perform. 

Now, moving the focus to the other side. Assuming an our of order
scenario, this will require the caller to push its request into
something like a pool of pending request, and to poll frequently if the
request was satisfied. I don't know how do you see this, but I found
quite complex and unnatural to make it as the default behaviour, not
only in BEEP, but in any connection oriented protocol.

More than a technical reason, I find here a practical implementation
decision.

> channels.  Neither would need to change if full asynchrony were

Again, this is a implementation issue which is not considering practical
consequences for a BEEP stack. 

Currently, an easy approach for a BEEP stack is to have the
last_{replied,received,etc} value to guide the connection close process,
which involves all channels opened at the moment. 

Your proposal will cause that all channels over all connections to have
to keep track of virtually 2^31 items (either because they are missing
or because there were received). This applies not only to messages
pending, but for pending replies.

> You could consider this misleading, 

Certainly...

> so I'll qualify the statement: BEEP

... this is not the point.

> about what can (or can't) be achieved with them.

Ok, but BEEP isn't a special case. As other RFCs, most of
changes/extensions I've found, they were done in a way previous
implementations remains working. A particular interesting case is MIME
(See historical note, page 3, from RFC2045).

> do, like changing or adding to control channel message semantics.

Ok.

> message number for replies, except when checking for protocol

I don't agree. In fact the limitation for replying in order only applies
to BEEP internal function. 

User application on top of a BEEP stack should be able to reply in any
other (another question is that the reply may be retained until
condition is meet, but definitely this should be handled by the BEEP
implemetation). 

Again, this is an implementation issue which is not considering
practical consequences. 

An API not allowing to reply to a particular message using a particular
msgno is causing to shift the logic of keeping track about the moment a
reply can be done from the BEEP stack into the user application. That
is, the application on top of such stack will have to ask the API "can I
reply?"; if not, the application will have to store the reply for later
delivery. I find this quite problematic.

Cheers!

---

From: "Thomson, Martin" <[email-masked]>
Date: Wed, 21 May 2008 19:42:19 -0500

More inline,

> functions in order and according to the results they perform.

Debating the advantages of serial processing, while entertaining, isn't
relevant to the discussion.  I am putting forward a different use case.

I'm not attempting to invalidate serial processing; far from that.  I am
only pointing out that it isn't always the best approach.

> More than a technical reason, I find here a practical implementation

I don't see how polling is necessary - I have implemented out of order
receipt of messages in beep4j with a change of only about 5 lines of
code without a need for polling.

> pending, but for pending replies.

That's not the case.  The number of items that would need to be tracked
is exactly the same number as the number of channels required if channel
pooling were used:

  N = number of requests each section * average time required to process
requests.

No matter what protocol option you choose, the state maintained at the
serving peer doesn't change - it still has to process all those
requests.  Therefore, tracking is only necessary at the requesting end.
Of course, it would also be reasonable to place an upper bound on the
total number of outstanding request.  New requests could block or be
rejected locally when this limit is reached.

<snip>

> (See historical note, page 3, from RFC2045).

Feature negotiation guarantees that backward compatibility is retained.
Unless both peers understand (and accept) the changed functionality,
nothing different happens.  No "baroque" mechanisms or other strangeness
would be necessary.
 
> > > 4) Message number is not only used for protocol errors, but also
to
> > > give

I think that you have missed my point.

How an API tracks message number is not really relevant to the
discussion.

Regardless of what the replying peer does, the requesting peer sees all
replies in the same order as the requests it sent.  Request/response
correlation can be performed by matching the order of replies to the
order of requests.  Therefore, the message number is not useful for
anything other than error detection.

> condition is meet, but definitely this should be handled by the BEEP

I'll agree.  But that's purely an implementation consideration.  Of
course, allowing this makes the API implementation more complex.  A
complexity that wouldn't be necessary if out of order responses were
allowed.  Interesting data point: beep4j doesn't enforce ordering of
replies at the replying peer; it's actually easier this way.

> delivery. I find this quite problematic.

No tracking would be necessary if out of order responses were allowed.
The application is (and should always be) unaffected by the change.

Allowing out of order responses actually makes the logic at the replying
peer simpler.

Ta,
Martin