Subject: RE: [Simple] MSRP: Flow Control

From: Adam Roach <[email-masked]>
Date: Mon, 28 Apr 2003 17:58:51 -0500

> -----Original Message-----
> From: Dean Willis [mailto:[email-masked]]

>    503 Service Unavailable
> 
>    The server is currently unable to handle the request due to a
>    temporary overloading or maintenance of the server. The implication
>    is that this is a temporary condition which will be alleviated
>    after some delay.
...
> This says nothing about "too many outstanding transactions", "other
> transactions", or "other sessions" -- it's just "this request". 

Which is fine, I guess. We just need to make certain that
clients with multiple sessions through the same relay don't
draw any conclusions about what a 503 in one session means
about another session. The semantics of "wait until another
transaction completes" was an optimization to allow efficient
pipelining of requests, which is particularly important if
we're going to allow chunking.

> In the context of MSRP, whether a relay chooses to do the 
> MSRP-equivalent of
> HTTP-503 for every request on a session when downstream 
> requests on that
> session are backed up,

Which would open the door for the exact DOS attack under
discussion...

> for individual requests that would cause buffer
> capacity to be exceeded,

Which would also open the door for the DOS attack under
discussion...

> only for requests that appear to be 
> correlated with
> prior outstanding requests,

Which would work, but give bad performance, especially for
chunked transfers...

> for every request in every 
> session, 

Which would also open the door for the DOS attack under
discussion...

> or some
> other variation thereof is probably an implementation issue 
> IN THE RELAY and
> really only matters to the relay itself.

Except that the schemes you rattle off are generally
vulnerable to the DOS attack of starting up a session
and sending many MSRP messages, filling up TCP and/or
application-layer queues until no one else can use the
relay.

> All of these 
> implementations can be
> handled with a protocol semantic like that of HTTP's 503.

And this re-use of semantic buys us what over defining a
code more appropriate to the situation?

> And as 1945 points out, it may be more appropriate, in some 
> cases, to simply
> refuse a connection

We're not talking about a server-wide overload here, though.
We're talking about having too many messages in a single
session.

> or to let TCP windowing provide transport-level
> throttling.

This breaks precisely because of connection re-use between
relays. Henning explained this in an earlier message.
Keep in mind that "get rid of connection re-use" is one
of the earlier suggestions that I made. It's a nice, clean
answer to both HoLB and flow-control.

/a
_______________________________________________
Simple mailing list
[email-masked]
https://www1.ietf.org/mailman/listinfo/simple

---

From: "Dean Willis" <[email-masked]>
Date: Mon, 28 Apr 2003 20:13:05 -0500

Adam, clearly you misunderstood what I said. Please re-read, and respond
again when you've rested and thought about it. You should probably also
re-read the note from Henning that you referred to, as I believe it refutes
the argument you are extending from it.

Keep in mind that even in the absence of any connection reuse whatsoever
(ala HTTP 1.0 single-request-per-connection), a relay server may become
congested if the input rate to that server is higher than its output rate.
It's very basic queuing theory.

Let's look at this from a queing-model perspective.

Each TCP connection into a relay is essentially an input queue. Each
connection out is essentially an output queue.

The relay function provides a linkage between the input and output queues.
This function can operate according to a wide range of possible policies.
There are also acceptance policies for the input queues and transmission
policies for the output queues to consider. Furthermore, we have the
possibilities that all queues, input or output, may, as a result of the
interaction of policy, capacity, and I/O conditions, become congested.

We're really talking about four different aspects of systems operation:

1) How the relay function adapts to congestion in an output queue. It seems
likely that some sort of "pushback" to the input function and associated
queue is called for. However, direct pushback on a shared queue (holding up
the input because the output is delayed) can, especially when applied
transitvely, result in the "head of line blocking" behavior.

2) How to resolve a congested input queue. Options raised include closing
the queue, purging the queue, and signaling backward to the input(s) of the
queue, or "quenching".

3) How to quench the input to a queue. Options proposed include explicit
application level signal on a per request basis, on a per-source basis, and
on a per-queue basis. It has also been proposed that under some conditions
that transport-level signaling (TCP windowing) may provide quenching.

4) Within a queue, how to provide a segmentation function to reduce apparent
head-of-line blocking resulting from the disparate serialization delays of
differently sized messages. Since individual end-to-end sequences have an
expectaion of seriality, this sort of "HOLB" only applies when a queue has
either multiple inputs, multiple outputs, or is an an intermediary position
between other relays that have MI or MO characteristics. Current discussion
centers on a segmentation and reassembly model apparently called "chunking".

Note here that there are two different sorts of HOLB evident in the system:
1) the sort that occurs when a relay-relay connection exclusively services a
relatively large message, to the detriment of other messages transiting that
connection, and 2) the sort that occurs when an input queue to a relay
becomes congested, through the action of that relay's policy, as influenced
by the status of an output queue from that relay.

Type 1 HOLB can be mitigated by segmenting messages on a shared queue, such
that the per-fragment serialization delays through that queue become
apparently uniform. The current proposals seem to hold that fragmentation at
a 64kB threshold would be adequate.

Type 2 HOLB cannot be mitigated by segmentation except inasmuch as the
segmentation prevents congestion of the output queue. Since segmentation
alone cannot prevent output congestion (or downstream input congestion), we
require some sort of transitive output-to-input capable of propagating
backward from the node noticing the congestion to the node that can do
something about it. We also require cleverly constructed policy in the
relay, such that knowledge about the performance of the output function may
be used to select the input request whose forwarding would be most
beneficial. We have the further option of using knowledge about the
peformance of the relay and out functions to adapt the input policy.

Given that TCP provides for some level of queue management and quenching at
the transport level, let us consider what can be accomplished here. Assume a
TCP connection between an an unspecified node and a relay, where that
connection is used to send messages to the relay for transmission through an
unspcified number of outbound connections to further relays or terminal
nodes. Assume that the policy of the relay function causes the relay to stop
reading requests from the input. Eventually, the sourcing node fills its
"TCP window", and stops trasmitting new data. The amount of resource used on
the relay is not unbounded -- it is one window's worth of buffer. Even if
the sourcing node transmits further data on this connection, the TCP
acceptance function on the relay will discard that data without buffering
it. If this is a "shared" connection, with multiple original nodes or
multiple terminal nodes or multiple threads between a pair of such nodes,
AND the output path is blocked only for a SUBSET of those threads, then we
get a Type 2 HOLB as above. If it is NOT a shared connection, then we just
have plain old-fashioned congestion.

Resolving this Type 2 blockage (or POFC, plain old fashioned congestion)
requires selectively allowing the relay of messages in unblocked (freely
trasmitting downstream) threads and either holding or discarding messages in
blocked threads. Assuming that we know which threads are blocked in the
output function, we can accomplish this (as I proposed) by accepting
messages, one at a time, from the input queue. Applying our perfect
downstream knowledge to each message, we either process that message and
move it into an output queue, or reject it with a "503" and discard it. In
either case, the message is removed from the input queue, allowing
transmission of further data as limited by the TCP window size.

Now the problem with this is that if the input into a relay is on a shared
connection from another relay, and that relay is profligate in its
acceptance of input from multiple sources, that an abusive source to that
relay can construct messages which will pile-up downstream, provide it a DoS
attack opportunity against some downstream relay. This is especially
problematic if a large number of attackers are working in concert, such that
the full weight of the DoS attack does not manifest until many relays down
the path. I believe this situation accounts for most of the DoS scenarios
you raised.

Two paragraphs above, we demonstrate how the first relay node that becomes
aware of a congested output thread, presumably by observing its output queue
and function, begins to relieve the congestion by discarding messages and
returning 503 responses (presumbaly time-bounded with a Retry-After) toward
the source. Let us assume that each relay that propagates a 503 response
"back upstream" learns from the reponse that that the downstream path
associated with the original reuqest is congested and should not be retried
for the period indicated (this is equivalent to a Frame Relay backward
explicit congestion notification, or BECN operation). So the relay stores
the thread identifier (I believe the destination is adequate)  and timer
value, and if it sees an input message matching the identifier within that
time period, executes the 503 operation locally rather than passing the
message into an output queue.  Since 503 is a middle-to-end response (it
goes all the way back to the sourc), it can be seen that after the first
discard operation, every relay transitively back toward the source learns of
the downstream congestion and is able to assist in relieving it.  In short
order, the relay closest to the abuser(s) becomes enabled to deny the
abuser's requests, and the abuser or abusers are esentially limited to the
damage caused by one full window, occasionally, on some downstream box. The
"occasionally" here is controlled by the value of the Retry-After being
provided by the congestion-detecting node, and a more "aware" relay could
certainly progressively increase this, perhaps applying something like a TCP
exponential backoff. 

In short, 503 responses need to be transmitted middle-to-end (or end-to-end,
if you look at it that way), and understood and applied hop-by-hop for this
to work.

--
Dean

> From: Adam Roach [mailto:[email-masked]] 
> Sent: Monday, April 28, 2003 5:59 PM
> To: 'Dean Willis'; Adam Roach; 'Paul Kyzivat'
> Cc: 'Henning Schulzrinne'; 'James Undery'; 'Simple WG'
> Subject: RE: [Simple] MSRP: Flow Control
> 
> 
> Which would open the door for the exact DOS attack under discussion...
> 
> Which would also open the door for the DOS attack under discussion...
> 
> Which would also open the door for the DOS attack under discussion...
> 
> > or some
> application-layer queues until no one else can use the relay.
> 
> > All of these
> > implementations can be
> We're talking about having too many messages in a single session.
> 
> relays. Henning explained this in an earlier message. Keep in 
> mind that "get rid of connection re-use" is one of the 
> earlier suggestions that I made. It's a nice, clean answer to 
> both HoLB and flow-control.
> 
> /a
> 
>