Backpressure in mutually suspicious systems

[Christopher Lemmer Webber]

Backpressure comes up again as a topic on my news feed:

https://lucumr.pocoo.org/2020/1/1/async-pressure/
https://medium.com/@jayphelps/backpressure-explained-the-flow-of-data-through-software-2350b3e77ce7

I haven't seen it talked about much here, but probably it has been in
the past since I'm relatively new. Still, I thought that a number of
systems of interest here impose some constraints which may be difficult
to compose with observing backpressure. If Alice is trying to send some
messages to Bob:

- Having Bob demand Alice to pause all her activity for a bit
(blocking) obviously is not possible, and is also an obvious avenue
for attack. (A workflow that involves polite ask is another thing,
but cannot really be a system primitive.)

- System-level backpressure systems are a control flow system, and so
are ordering systems. I've thought before about how implicit flow
control could work with something like E-order and I'm not sure how
to do it in a way that's "nice".

- Store and forward can exacerbate a problem; more messages can pile up
without you realizing it and be forwarded all at once.

Implicit vs explicit?

- Explicit: You're unlikely to realize all the places you need
backpressure, but when you do maybe you can code them in more
carefully (or, maybe an api change to deal with it confuses your
existing userbase)

- Implicit: The only real nice option for implicit backpressure support
seems to be buffering for a while and then dropping messages.
"Origin-oriented" dropping of messages can only really be done to
prevent messages from an unintentionally misbehaving client; a
malicious user can do the same thing but using a DDOS, where the
"origin" is of no help.

Thoughts? Probably everything I've written above has been thought over
1 million times; sorry if I'm being obtuse or if all responses obvious.

- Chris

[Raoul Duke]

what does erlang do? ;-)

[David Nicol]

this seems more like an implementation detail than a security issue.

Traditional async unix servers organized around the "select" system call implement backpressure by rejecting further messages into the feeding TCP/IP streams until their buffers are empty, and dealing with the first thing in every stream before going back for more. The onus is on the client of such a system to expect the occasional "cannot connect out of sockets" error and back off and retry.

--
You received this message because you are subscribed to the Google Groups "cap-talk" group.
To unsubscribe from this group and stop receiving emails from it, send an email to cap-talk+u...@googlegroups.com.
To view this discussion on the web visit https://groups.google.com/d/msgid/cap-talk/87v9ptak3g.fsf%40dustycloud.org.

--

"I'm going back to New York City. I believe I've had enough."

[Tony Arcieri]

On Thu, Jan 2, 2020 at 11:45 AM Raoul Duke <rao...@gmail.com> wrote:

what does erlang do? ;-)

I can't say Erlang ever had a satisfactory solution to this problem, IMO. But what has? I can't complain too much.

The main way you could express backpressure for TCP via Erlang's gen_tcp was via the active mode parameters:

https://erlang.org/doc/man/gen_tcp.html

Notably Erlang supported {active, once} as a way to request one "chunk" of TCP data to be delivered from the ioserver to the current process as Erlang messages. It also supported {active, N} to request N such chunks, or {active, true} to unboundedly receive all incoming TCP data. In practice I think people often started with {active, once} and then after noting the performance drawbacks, moving to {active, N} or {active, true} as a way to queue up a backlog of work to process, then setting {active, false} until the backlog is processed as a means of providing backpressure.

Achieving such backpressure between Erlang processes themselves required building a sort of protocol between them. Otherwise Erlang mailboxes are unbounded, and with fire-and-forget semantics could quickly fill up and exhaust the Erlang heap.

I think the main observation I saw several people make while I was still doing Erlang was backpressure alone is insufficient. Instead, you also need "load shedding" - more or less dropping work on the floor when the system is overloaded, and ideally returning errors to senders/clients in that case. This certainly sees like the ideal way to deal with a potentially malicious client that may be DoSing you.

See also the early ICMP idea of "source quenching".

--

Tony Arcieri

[Alan Karp]

As the links you provide show, the problem back pressure addresses is a networking issue, something I've been working on for the past few years.  

There is another approach, credit based flow control, that might be more appropriate for ocap systems.  The idea is simple.  The receiver gives the sender a credit for something, say number of messages, number of network packets, amount of data, or whatever.  The sender then keeps track of its available credits and stops sending when they are exhausted.  (Data sent without a credit is dropped by the receiver.)  The receiver provides new credits to the sender when it can handle the traffic.

InfiniBand uses credit based flow control, because it avoids both buffer bloat and the choice of crashing or dropping packets.  (It's a bit more complicated because of something called "head of line blocking," but that's a detail not needed for this discussion.)  

--------------
Alan Karp

[Christopher Lemmer Webber]

David Nicol writes:

> this seems more like an implementation detail than a security issue.

I agree; maybe the subject wasn't great. The source of thinking about
it was in thinking about requirements that you block for a certain
period of time (which seems like a bad solution in general, but is
sometimes proposed) are not possible, and various tie-ins with things
like E-order which are underexplored outside this communitty.

[Christopher Lemmer Webber]

Alan Karp writes:

> As the links you provide show, the problem back pressure addresses is a
> networking issue, something I've been working on for the past few years.

Definitely curious! Maybe a good Friam call topic?

> There is another approach, credit based flow control, that might be more
> appropriate for ocap systems. The idea is simple. The receiver gives the
> sender a credit for something, say number of messages, number of network
> packets, amount of data, or whatever. The sender then keeps track of its
> available credits and stops sending when they are exhausted. (Data sent
> without a credit is dropped by the receiver.) The receiver provides new
> credits to the sender when it can handle the traffic.
>
> InfiniBand uses credit based flow control, because it avoids both buffer
> bloat and the choice of crashing or dropping packets. (It's a bit more
> complicated because of something called "head of line blocking," but that's
> a detail not needed for this discussion.)

This sounds appealing... in some ways it sounds like a better version of
the ticket system described in Armin's (the pocoo.org) post.

Initially I thought about something similar but using something more
along the lines of actual money, but that seemed to result in a
turtles-all-the-way-down problem, because the money system itself would
probably have to have its own protocol which may suffer from
backpressure problems.

Of course, the problem with *not* using something resembling "real
money" is that a malicious user could open up many connections from many
different machines to "get more work done". So in a sense, does the
system you're talking about require a certain amount of cooperation to
not abuse?

[David Nicol]

> There is another approach, credit based flow control, that might be more
> appropriate for ocap systems.  The idea is simple.  The receiver gives the
> sender a credit for something, say number of messages, number of network
> packets, amount of data, or whatever.  The sender then keeps track of its
> available credits and stops sending when they are exhausted.  (Data sent
> without a credit is dropped by the receiver.)  The receiver provides new
> credits to the sender when it can handle the traffic.

in the large, this becomes sender-pay e-mail 

 

Initially I thought about something similar but using something more
along the lines of actual money, but that seemed to result in a
turtles-all-the-way-down problem, because the money system itself would
probably have to have its own protocol which may suffer from
backpressure problems.

if the listener is comptrolling the scrip needed to rent their ears, there's only one turtle

 Of course, the problem with *not* using something resembling "real

money" is that a malicious user could open up many connections from many
different machines to "get more work done".  So in a sense, does the
system you're talking about require a certain amount of cooperation to
not abuse?

introducing new barriers is a marketing problem. If the new system is a drop-in replacement for something existing and broken, the audience for the sales message becomes smaller -- the implementors. Quote frankly, Joe Keyboard doesn't give a keypress about the OSI seven-layer model.

[Christopher Lemmer Webber]

David Nicol writes:

>> > There is another approach, credit based flow control, that might be more
>> > appropriate for ocap systems. The idea is simple. The receiver gives
>> the
>> > sender a credit for something, say number of messages, number of network
>> > packets, amount of data, or whatever. The sender then keeps track of its
>> > available credits and stops sending when they are exhausted. (Data sent
>> > without a credit is dropped by the receiver.) The receiver provides new
>> > credits to the sender when it can handle the traffic.
>>
>
> in the large, this becomes sender-pay e-mail

I think sender-pay e-mail also works better because there's probably a
human aware of what kinds of email they are willing to spend money on.

By contrast, part of the appeal of E is "you can talk to all these
actors and it kind of doesn't matter where they live!"

Suddenly things have changed. Say Alice on Vat A is talking to Bob on
Vat B. If Bob says, I want you to talk to Carol, Carlos, and Christian
on Vat C, if Alice is an automated program she might not think much
about it and just do it. But say Bob controls Vat C and is trying to
get money out of Alice, just for communicating with other objects. How
aware should Alice be of this? Suddenly Alice needs to think about how
much money she has in the bank, what prices she's normally willing to
pay for objects, etc. If Alice is a program and is programmed with
fiscal sense, she will pause a lot more and be willing to communicate
less than before. If not, she will be tricked into spending all her
money.

By contrast, if Alice is a person putting stamps on an envelope to talk
to correspondents, she is able to reason about how much money she is
spending and what's worth spending stamps on.

A cooperative approach, by contrast, makes a lot of sense... Vat A would
like to talk to Vat C, Vat C gives Vat A 30 tokens to spend on messages
before it can send more messages. *That* makes a lot of sense to me
without a "shoulder accountant angel/demon" watching over every message
sent and can be done automatically. It is vulnerable to a DDOS (but so
is link saturation by brute force overloading with garbage packets) but
it does help for scheduling cooperation.

[David Nicol]

On Fri, Jan 3, 2020 at 12:00 PM Christopher Lemmer Webber <cwe...@dustycloud.org> wrote:

A cooperative approach, by contrast, makes a lot of sense... Vat A would
like to talk to Vat C, Vat C gives Vat A 30 tokens to spend on messages
before it can send more messages.  *That* makes a lot of sense to me
without a "shoulder accountant angel/demon" watching over every message
sent and can be done automatically.  It is vulnerable to a DDOS (but so
is link saturation by brute force overloading with garbage packets) but
it does help for scheduling cooperation.

in other words, Vat C gives Vat A an ear that will expire after thirty messages go through it.

 

[Alan Karp]

Christopher Lemmer Webber <cwe...@dustycloud.org> wrote:

Of course, the problem with *not* using something resembling "real

money" is that a malicious user could open up many connections from many

different machines to "get more work done".  So in a sense, does the

system you're talking about require a certain amount of cooperation to

not abuse?

Credit based flow control is most commonly used in datacenter networks, where the switches are cooperating to get the traffic through.  Any kind of abuse is typically handled by throttling at the ingress point.  In your example, getting credits could involve presenting some kind of credential.  That credential could be an authentication, but there are other possibilities, such as money.  Ocaps could be even better.  For example, Alice could give Bob an ocap allowing him to send 30 messages.  Bob can connect to Alice on as many channels as he likes, but he only gets 30 messages.

--------------
Alan Karp

[Christopher Lemmer Webber]

That makes a lot of sense! Can be combined with Horton sensibly, too.

[Mark S. Miller]

I was thinking that too. The Horton sense of reputation-credit can be directly repurposed for incoming-buffer-budget credit.

--
You received this message because you are subscribed to the Google Groups "cap-talk" group.
To unsubscribe from this group and stop receiving emails from it, send an email to cap-talk+u...@googlegroups.com.

To view this discussion on the web visit https://groups.google.com/d/msgid/cap-talk/87k1689vj6.fsf%40dustycloud.org.

[Rob Markovic]

There is a lot of pressure-mediation happening in the physical world which is handled auto-magically in the universe.

Perhaps taking inspiration from there is another possibility. For ex. magnetism.

The crude analogy being your shower head and the corresponding drain at say, 20,000ft.

++ Rob

About me

To view this discussion on the web visit https://groups.google.com/d/msgid/cap-talk/CAK-_AD7yMmUu%2BDusTrFfqG_xOD5VvM06y3b7Z9WxTiUzhDxwnA%40mail.gmail.com.

[Tony Arcieri]

On Fri, Jan 3, 2020 at 1:46 PM Alan Karp <alan...@gmail.com> wrote:

Credit based flow control is most commonly used in datacenter networks, where the switches are cooperating to get the traffic through.  Any kind of abuse is typically handled by throttling at the ingress point.

I've observed something a little bit different than this in the datacenter environments we host in. Throttling generally occurs at (for lack of a better term) ISP/SDN "concentrators".

That is to say the switches that provide immediate connectivity have backplanes and trunks sufficient to handle the full traffic volume on all ports, but these are only a few hops away from the systems doing the actual metering, which discourage overuse by e.g. metered virtual circuits, which have big up-front costs, but will also bill you based on the traffic volume.

In such situations, the backpressure mechanism is money, and if enough clients are paying them, they will reinvest that money into upgrading their infrastructure.

Fortunately decent ISP connections are still blissfully unmetered, but still have a cap on the full bandwidth of the circuit which you can upgrade for more money, and if you exhaust the physical bandwidth of the circuit, pay a higher flat cost for a faster port.

In other words, what you pay for a port, bandwidth cap, or metered virtual circuit figures into their overall capacity planning, and decisions about what upgrades they should (or should not) invest in based on real-world usage.

--

Tony Arcieri

[Baldur Jóhannsson]

Hmm... this reminds me of an idea I have only
physical notes of and described a while back on
#erights on irc.freenode.net

The idea was regarding resource consumption on run
hosts. Basically an run host is a vat host where
the vats are each metered on cpu time, memory usage
over time and outgoing bandwith.
Incomming messages also have postage.
(the stamps used are basically macaroons whose
initial issuer is the runhost itself. Due to
expury/only-before on those there is a demurrage
effect, so long term hoarding for later DOSing is
quite mitigated)
Each run host is also a mint of tokens/units/whathaveyou which is the only acceptable currency
to pay these costs.
Runhosts trade those token between themselfs andor
kiosks (service directories).

With upcomming extensions to Tor hidden services
one could use the stamps used in incomming messages
described above to do connection establishment rate
limiting. (The extended auth portion of tor INTRO cells can carry those stamps. Meaning that the hidden
service server can check them before building a circuit back to the Rendevouz Points given in the INTRO cells)

So, ear of limted uses seem to be (r)emergent idea
in this kind of context.

[Bill Frantz]

The backpressure issue in the E system is a bit different than
in the general IP world. In E, there is only one TCP connection
between two vats, ensured by using the VATids during connection
setup. If private keys are shared, only one of the VATs sharing
a specific key can make a connection at a time.

There are some issues with the E system that fall into the class
of issues that can be fixed with backpressure.

(1) The E system reads the TCP connections whenever it can and
queues the messages on the VAT input queue. This approach can
obviously cause and out of memory condition. The E system could
implement a "fairness" system where each connection has a
maximum number of messages and when at the maximum, reads are
not issued using TCP backpressure. A ticket/money system could
also be used here. Since we have reliable identity for the other
end, we can enforce some rules and punish abusers.

(2) Some obvious ways of programming in E will cause significant
problems in messaging. For example, say I want to use remote
calls to calculate the square roots of all the numbers from one
to a million. (If you don't like square root, substitute
something else. If you don'l lie a million substitute something
else, like a google.)

The obvious way to code this is to set up a loop that does a
remote call for each number. But this approach will produce a
lot of messages in one VAT turn, filling up buffers somewhere
until an out of memory condition exists. Also, the returned
results will queue up since the generating VAT is not processing them.

I don't have a good solution for this problem except, "If it
hurts, don't do it.", which isn't really a good answer for
mutually suspicious systems.

Cheers - Bill

-----------------------------------------------------------------------
Bill Frantz | Truth and love must prevail | Periwinkle
(408)356-8506 | over lies and hate. | 16345
Englewood Ave
www.pwpconsult.com | - Vaclav Havel | Los Gatos,
CA 95032

[Raoul Duke]

re: if it hurts...

as with all such issues, a big problem with it is that it might be hard to figure out why my system is slow. :/

[David Nicol]

sounds like unless the whole vat is willing to share their commons nicely, the intervat message multiplexing protocol needs to grow some flow control ops.

On Sat, Jan 4, 2020 at 3:35 PM Bill Frantz <fra...@pwpconsult.com> wrote:

The backpressure issue in the E system is a bit different than
in the general IP world. In E, there is only one TCP connection
between two vats, ensured by using the VATids during connection
setup.

--