Symmetric, Local Routing Proposal

routing-symmetric-local.md

Symmetric Routing with Local State

My previous symmetric routing proposal entailed building a whole reverse routing envelope into each packet. The requester would have to specify some information about the whole path before sending the packet. As ~master-morzod pointed out to me, such a design does not make for a good bottom-up, self-assembling network.

In contrast, in this proposal, each relay node only needs to know the previous node and the next, not the entire multi-hop route. The basic idea is that when a ship receives a request packet, it figures out where the next hop in the forwarding chain for that packet should be, forwards the packet to that location, and remembers the IP and port of the incoming request packet for thirty seconds, so if it hears a response packet, it can pass that response back to the previous relay.

This means that every request must be satisfied within thirty seconds, but that's a workable constraint. Note that many HTTP systems operate under this constraint. This arrangement is also similar to NDN's "pending interests" table. An NDN "interest" packet corresponds almost exactly to a Fine scry request packet, and stateful Ames request packets can behave the same with respect to routing.

In order for this to work, each node has to have some idea of the next node to try. If the node has a direct route to the receiver ship, it should send the packet there. Otherwise, if it knows the ship's sponsor, it should try that, falling back up the sponsorship chain potentially all the way to the receiver's galaxy.

The next question is how routes tighten, which requires information about lanes for ships later in the relay chain to propagate backward to ships earlier in the relay chain. A maximally tight route is a direct route between the sender ship and the receiver ship.

Each ship in the relay chain, when forwarding a response packet backward through the route, can overwrite a "next" field in the response packet to contain the relay just past it. This enables the previous relay to try the "next" relay on the next request packet, skipping the relay in between.

One simple rubric is that a ship should try the tightest known-good route and the next tightest route simultaneously until the tighter route has been demonstrated to be viable. This way, in case the tighter route turns out not to work (usually because it's behind a firewall and not publicly addressable), the looser route will still get the packet through.

A ship should only overwrite the "next" field when forwarding a response back to a ship that is not one of its direct sponsors (this precludes fraternization from galaxy directly to planet or moon, but I think that's ok). The following example shows how a route tightens over multiple packet roundtrips.

request:  ~rovnys -> ~syl -> ~sipsyl -> ~ritpub-sipsyl -> ~mister-ritpub-sipsyl
response: ~rovnys <- ~syl <- ~sipsyl <- ~ritpub-sipsyl <- ~mister-ritpub-sipsyl
                  ::
                  :: next: ~sipsyl@123.456.789:1234

request:  ~rovnys -> ~sipsyl -> ~ritpub-sipsyl -> ~mister-ritpub-sipsyl
response: ~rovnys <- ~sipsyl <- ~ritpub-sipsyl <- ~mister-ritpub-sipsyl
                  ::
                  :: next: ~ritpub-sipsyl@234.567.890:2345

request:  ~rovnys -> ~ritpub-sipsyl -> ~mister-ritpub-sipsyl
response: ~rovnys <- ~ritpub-sipsyl <- ~mister-ritpub-sipsyl
                  ::
                  :: next: ~mister-ritpub-sipsyl@345.678.901:3456

request:  ~rovnys -> ~mister-ritpub-sipsyl
response: ~rovnys <- ~mister-ritpub-sipsyl
                  ::
                  :: next: ~

As an aside, note that while this example was written using full Urbit ships as relays, this routing procedure would also allow any kind of program that speaks the routing protocol and knows the lanes of ships to act as a relay node, even if it does not have an Urbit address (although the system would need a new way to learn about these non-ship relays).

In order for this procedure to work, each relay must maintain a data structure:

+$  state
  $:  pending=(map request [=lane expiry=@da])
      sponsees=(map ship lane)
  ==
+$  request
  $%  [%ames sndr=ship rcvr=ship]
      [%scry rcvr=ship =path]
  ==

The expiry field is set to 30 seconds from now whenever we hear a request. Repeated requests bump the timeout, keeping the request alive.

Followup: it is important that keepalives be done per corresponding pair of ships, and not per subscription. The information you really want is "is the publisher ship still alive" and if so and you haven't gotten an update for a specific subscription from that ship, you can assume they don't have one.

Ok so there is a keepalive, but not a very scalable one. Each ping to a sponsor is an Ames message. I think this scales well enough for sponsorship, but would not for userspace publications. We agree that keepalives should be handled by the publisher's king in practice, which means publication keepalives can't impact the publisher's event log.

Unsolicited "push" packets, like a heartbeat response to a request that isn't sent, seems a bit off to me in a symmetric routing world. The subscriber should be pinging the publisher and getting acks, so that a) responsibility lies with the subscriber to trigger a response from the publisher, and b) the subscriber is continually telling the publisher where it is, so the publisher knows where to send responses.

As for your followup, the way we've designed the notifications protocol, notifications are optional. A simple runtime might not implement them. So a publisher might not push updates to you if it has such a simple runtime, in which case you need to keep re-sending scry requests indefinitely.

I suppose we could add an ack packet that says "I heard your request and will store it until Vere restarts, so you will get a response eventually if I know where you are." Then if we (the subscriber) receive one of these, we could almost switch to just sending keepalive packets, whose responses should include a nonce representing the Vere process instance.

The almost is because there's no way to know if a response packet was sent but lost over the wire. We would either need to have the subscriber ack the response, or have the subscriber retry the request on a timer until the data is delivered.

So I'm not convinced there's a better short-term solution than just retrying subscription-related scry requests every thirty seconds or so, with an added repeated keepalive scry request that gets a response each time as long as the publisher is online.

Long-term, I think we could implement something like your proposal, where subscribers could ask once for a datum, get an ack that the publisher will eventually send you the datum, then stop asking -- but only if we had TCP-style sessions in a dedicated king-to-king protocol, as I described in the Nan Madol proposal. To get that kind of behavior with the kind of performance we want, you need notifications-related acks to be stored in transient king state, not the event log.

Unsolicited "push" packets, like a heartbeat response to a request that isn't sent, seems a bit off to me in a symmetric routing world. The subscriber should be pinging the publisher and getting acks, so that a) responsibility lies with the subscriber to trigger a response from the publisher, and b) the subscriber is continually telling the publisher where it is, so the publisher knows where to send responses.

Not necessarily. The subscriber can, of course, behave this way, and may want to in order to e.g. keep NAT pinholes open.
But if the subscriber doesn't want to behave this way, we can just keep optimistically pushing heartbeats from the publisher, and the subscriber can react to timing out by sending a new subscription request.

As for your followup, the way we've designed the notifications protocol, notifications are optional. A simple runtime might not implement them. So a publisher might not push updates to you if it has such a simple runtime, in which case you need to keep re-sending scry requests indefinitely.

Again, the fallback of "resend subscribe if you don't hear the heartbeat" does this.

I suppose we could add an ack packet that says "I heard your request and will store it until Vere restarts, so you will get a response eventually if I know where you are." Then if we (the subscriber) receive one of these, we could almost switch to just sending keepalive packets, whose responses should include a nonce representing the Vere process instance.

I don't think this extra case in the state machine is necessary, see above.

I'm not sure your proposed system works as intended. I've filled in the blanks a bit for parts of the system that you've only described somewhat briefly, so let me know if I misunderstood. Consider:

Subscriber sends scry request for next datum to publisher. Publisher doesn't have the datum, so it just starts sending heartbeat responses on a timer. When the subscriber gets the first heartbeat, it stops re-sending the scry request, assuming that the publisher will notify it. Then at some point, the publisher grows a value at the requested scry path and fires off a scry response packet to the subscriber, but the packet gets lost over the wire.

I guess there are a couple cases in this situation:

1. This was the only subscription from the subscriber to the publisher, so when the publisher sends the scry response, it also stops sending heartbeats. This triggers the subscriber to time out and re-send its subscription request, which should trigger a re-send of the scry response packet, so this will eventually succeed correctly.
2. There were other subscriptions from the subscriber to the publisher, so when the publisher sends the scry response on this subscription, it keeps sending heartbeats. When the packet is lost, the subscriber has no way of knowing it should re-send the scry request packet. This is then stuck.

In fact, if there are other subscriptions, then we'd also need some sort of initial ack to each scry request, in addition to the heartbeats. Otherwise, if one subscription is already online and there are heartbeats flowing, then when the subscriber makes a request for a path in a different subscription (and the path is for the next datum and hasn't been grown yet), there's no observable change in the publisher's behavior, so the subscriber will just keep re-sending the request packet. The publisher was already sending heartbeats, and it just keeps sending heartbeats after receiving the second request. So the subscriber will never learn that it can stop re-sending this scry request.

So I don't think this works without the publisher sending some kind of ack on the initial scry request telling the subscriber that it doesn't need to keep re-sending the request, at least while the heartbeats are going. I think this ack is a little different from what I'd been thinking of as a "scry blocked" response, since it implies that the publisher is taking on the responsibility of delivering a response, as opposed to just a courtesy of informing the subscriber that its scry request failed for now.

The publisher would only send this ack if it's running the scry notifications protocol. Otherwise, it shouldn't claim responsibility for delivering the response later. This could act as a form of protocol negotiation: a subscriber polls for a scry request on a timer until it hears this initial ack; if it never comes, then it keeps pinging forever. If the subscriber isn't using the scry notifications protocol, it can drop incoming acks and keep re-sending the scry request packet as if it never heard them.

The ack needs to be authenticated, and it needs to include the sender ship's address, the scry request path, and a session id number of some sort so that if the publisher Vere restarts or the subscriber ship goes offline for a while, the session id will change, informing the subscriber that it needs to re-send all pending scry requests.

If the ack is lost over the wire, the subscriber will re-send its scry request on a timer. Each time the publisher gets a duplicate request, it sends a duplicate ack, which should include the same session id as the first ack unless the session has died.

An issue with eliding heartbeat requests and only sending heartbeat responses is: how does the publisher know to stop trying to push updates to a subscriber, if the subscriber has moved or gone offline? If heartbeats only go from the publisher to the subscriber, then the publisher doesn't know whether the subscriber is still online. It effectively has to keep its pending request table alive forever if the subscriber goes down. Again, I think it makes more sense for this responsibility to lie with the subscriber. If the publisher stops hearing keepalives from the subscriber, it deletes the request packets from that subscriber and stops trying to notify it. If the subscriber comes back online, it starts over from scratch and re-sends all its pending scry requests.

Here's a counterproposal, based on these thoughts:

The general idea is that the subscriber sends heartbeats while it has pending requests open on the publisher, which keeps those requests pinned in the publisher's pending requests table. A heartbeat can be thought of as a shorthand for a set of re-sent scry requests, one for each pending request.

The publisher acks each heartbeat request so that the subscriber can continue to tighten the route. The publisher also sends a subscription ack each time it hears a request for a scry path that doesn't yet exist. The subscriber will re-send each scry request on a timer until it hears such a subscription ack. This means that even if the first couple acks get lost over the wire, one will eventually go through and the subscriber can stop re-sending the scry request and instead switch to heartbeats -- and it might already have been sending heartbeats because of some other subscription.

A session dies either when the publisher Vere restarts or when a certain amount of time (maybe 1 minute) has gone by without the publisher hearing a heartbeat request packet. If the publisher hears a heartbeat request on an unrecognized session, it sends a heartbeat response with the new session id, creating that id if needed. If the subscriber stops hearing heartbeat responses for a certain amount of time (also a minute, let's say), it will consider the connection dead, but will continue to send heartbeats until it hears a response from the publisher. If the subscriber ever hears a new session id from the publisher, it knows it needs to re-send all pending scry requests and switch its heartbeat requests to the new session id.

A subscription ack packet contains:

• a bit pattern saying "I'm a subscription ack", ideally in the header
• subscriber ship, life, rift
• scry request path (includes publisher ship, life, rift)
• session id
• signature

A heartbeat request contains:

• a bit pattern saying "I'm a heartbeat request", ideally in the header
• subscriber ship, life, rift
• publisher ship, life, rift
• session id
• incrementing counter, starting at 1 each session
• signature

A heartbeat response contains:

• a bit pattern saying "I'm a heartbeat response", ideally in the header
• subscriber ship, life, rift
• publisher ship, life, rift
• session id
• counter (same as the one that was just heard)
• signature

Ok so there is a keepalive, but not a very scalable one. Each ping to a sponsor is an Ames message. I think this scales well enough for sponsorship, but would not for userspace publications. We agree that keepalives should be handled by the publisher's king in practice, which means publication keepalives can't impact the publisher's event log.

Huh, if we had heartbeat packets, we could just use those for sponsor pinging, instead of Ames messages. That would be nifty, since a star could potentially just store the sponsee's IP and port in the Urth process, without incurring Arvo events and disk writes. The way we do it now, the average fully-laden star would have roughly 65000/30, so 2200 disk writes per second, just to track its sponsees.

As noted in a meeting today, my counterproposal doesn't work. The notification for the new subscription datum would have to be re-sent and explicitly acked in order to make it reliable; otherwise, the notification could be lost permanently.

... that being said, we could just add acks. Sure they're a bit weird, because the ack is a request from the subscriber, acking a response, so it's arguably acking an ack -- but I think this will at least get us to a complete, workable system, which we can then discuss and tweak.

We'll add a new packet type, a subscription cancellation request. The subscriber will send this request to tell the publisher it no longer wants to hear a notification when data is grown at the specified path. This can happen if the subscriber unsubscribes, or if it receives the scry response from the publisher.

A subscription cancellation request packet contains:

a bit pattern saying "I'm a subscription cancellation request", ideally in the header
subscriber ship, life, rift
scry request path (includes publisher ship, life, rift)
session id
signature

Once the publisher has a newly grown scry path, it sends notifications to live subscribers until either it hears a cancellation request packet or the session dies.

If my understanding is correct, the key here is that pure acks don't really convey any information except that some request was received by the destination. This makes acks great for route tightening, but not much else related to subscriptions. Therefore, things like "acknowledging" a subscription should be thought of as remote scry protocol requests, not acks.
Here's my pubsub walkthrough:

1. A subscriber repeatedly sends subscription request packets to a publisher, until the publisher sends a request back to the subscriber saying "stop sending subscription requests," indicating that the publisher knows about the subscription. As @belisarius222 points out, the "stop sending subscription requests" request is arguably an ack, but we'll just say only acks are acks. I don't think the "stop spamming me" packet needs to be acked, because if it isn't received the subscriber will just keep spamming subscription requests.
2. After the subscriber receives the "stop sending subscription requests" request, the subscriber will stop spamming subscription requests and only send requests as needed to keep the route tight. I think these requests could be serf-to-king, unless they should also verify that the publisher still has the subscription. (My understanding is that most of the remote scry pubsub stuff lives in Arvo.)
3. When the scry path is grown, the publisher pushes to all of the subscribers until it receives a cancellation request from each of them. The subscriber should be receptive to push notifications whether or not it has received the "stop spamming me" packet.
   In this system we need:

• a subscription request packet.
• a keepalive/route-tightening packet - this could possibly be just more subscription request packets.
• a "stop spamming me" request packet that the publisher sends in response to subscription request packets.
• packets to push the requested data - these should be fragmented/acked as necessary.
• a subscription cancellation packet.
  I'm both an Urbit and networking noob, so hopefully I'm not entirely off base.

Thanks for taking a look at this.  It seems you have a pretty good understanding. Most of what you're describing is part of the session-based notification protocol, which is intended to be an opt-in layer on top of basic remote scry.  The comments on this gist are how we ended up with that design. Some corrections:

​After the subscriber receives the "stop sending subscription requests" request, the subscriber will stop spamming subscription requests and only send requests as needed to keep the route tight. I think these requests could be serf-to-king, unless they should also verify that the publisher still has the subscription. (My understanding is that most of the remote scry pubsub stuff lives in Arvo.)

The heartbeat packets will be king-to-king, not serf-to-king.  Arvo won't see anything about the notifications protocol, except that publisher Vere will need to scry into Arvo to know whether it can promise that it will deliver a subscription update.  As for where the pub/sub machinery lives, most of it is in Arvo, and Vere and the networking only know about individual scry paths, not subscriptions.

​When the scry path is grown, the publisher pushes to all of the subscribers until it receives a cancellation request from each of them. The subscriber should be receptive to push notifications whether or not it has received the "stop spamming me" packet.

The subscriber is the one who sends the "stop spamming me" packet, which it might need to re-send if it receives duplicate notification packets. — ~rovnys-ricfer https://urbit.org

…

On Thu, May 12, 2022 at 5:20 PM, leowini < ***@***.*** > wrote: ***@***.**** commented on this gist. If my understanding is correct, the key here is that pure acks don't really convey any information except that some request was received by the destination. This makes acks great for route tightening, but not much else related to subscriptions. Therefore, things like "acknowledging" a subscription should be thought of as remote scry protocol requests, not acks. Here's my pubsub walkthrough: * A subscriber repeatedly sends subscription request packets to a publisher, until the publisher sends a request back to the subscriber saying "stop sending subscription requests," indicating that the publisher knows about the subscription. As @ belisarius222 ( https://github.com/belisarius222 ) points out, the "stop sending subscription requests" request is arguably an ack, but we'll just say only acks are acks. I don't think the "stop spamming me" packet needs to be acked, because if it isn't received the subscriber will just keep spamming subscription requests. * After the subscriber receives the "stop sending subscription requests" request, the subscriber will stop spamming subscription requests and only send requests as needed to keep the route tight. I think these requests could be serf-to-king, unless they should also verify that the publisher still has the subscription. (My understanding is that most of the remote scry pubsub stuff lives in Arvo.) * When the scry path is grown, the publisher pushes to all of the subscribers until it receives a cancellation request from each of them. The subscriber should be receptive to push notifications whether or not it has received the "stop spamming me" packet. In this system we need: * a subscription request packet. * a keepalive/route-tightening packet - this could possibly be just more subscription request packets. * a "stop spamming me" request packet that the publisher sends in response to subscription request packets. * packets to push the requested data - these should be fragmented/acked as necessary. * a subscription cancellation packet. I'm both an Urbit and networking noob, so hopefully I'm not entirely off base. — Reply to this email directly, view it on GitHub ( https://gist.github.com/7ec6f40b3a498c38e696139d8dbd8b10#gistcomment-4165321 ) , or unsubscribe ( https://github.com/notifications/unsubscribe-auth/AAGVR5LRE3RJCJCTN2L3ZJDVJV723ANCNFSM5SDQO5JA ). You are receiving this because you were mentioned. Message ID: <belisarius222/routing-symmetric-local . md/comments/4165321 @ github. com>

Okay that makes sense to me. I spent some time looking at ames.c and ames.hoon to get a better understanding.
It sounds like the symmetric version of Ames should:
a. get rid of the origin field - no longer needed.
b. add a bit for request/response - Ames should only look at the 'next' field on response packets.
c. add the next field.
d. add 2 more bits to distinguish subscription acks, heartbeat requests, and heartbeat responses from 'regular' packets.
Initially, how will the galaxies learn to do peer discovery for stars, and how will the stars get the lanes of their sponsee planets? It seems like for every response packet, non-destination relays should check to see if they have the source lane in their sponsees map, and if not somehow request that ship's @p so that it can be added as a sponsee. Does this make sense?

Items a) through d) all look right.

Initially, how will the galaxies learn to do peer discovery for stars, and how will the stars get the lanes of their sponsee planets?

Good question. A sponsee needs to ping the sponsor repeatedly with some kind of request packet. This could be just a heartbeat packet, potentially. Current Ames sends an Ames command to the sponsee for this purpose, but with symmetric routing and remote scry, we should be able to avoid the disk writes on the sponsor by structuring the pings as reads or heartbeats.

When the sponsor hears the packet from the sponsee, it stores the sponsee's lane for some time, just like with any other ship that sent it a request. While it knows the lane, when it receives other packets intended for the sponsee, it knows where to send them. The sponsor should not need to send any requests to the sponsee for this to work.