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.

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.