Proposal: use a list of addresses in priority order for autonat v2 dial requests

[sukunrt]

In discussion with @marten-seemann he suggested:

Maybe the client could send a list of addresses it wants dialed, in descending priority. The receiver would pick exactly one of them and dial it

the proposal is:

Client has a list of addresses it wants to determine reachability for. In a dialRequest they send this list of address in priority order to the autonat server. The autonat server dials the first address it is capable of dialing and reports success or failure for that address.

This will be helpful in cases where we are interested in determining reachability for a newly address transport for which support in the network is low. Many requests for this new transport address will be rejected because the server cannot dial this transport. This proposal allows us to reuse those requests to check reachability for other addresses.

For some history this suggestion is an improvement over the scheme suggested here https://github.com/libp2p/specs/pull/538#discussion_r1162730358 . This scheme aimed to solve the same problem.

[sukunrt]

I'm not entirely convinced of the benefits here. Consider the case where a Node has two addresses, a new transport address NewA and an old transport address OldA.

The node already knows the reachability of OldA. Now it is interested in determining the reachability of NewA. On dial requests for NewA the node is able to obtain confirmation of the reachability status of OldA. But these confirmations aren't very helpful since we will need to confirm the reachability of OldA again after some expiry time. Consider that we are confirming the reachability of all addresses every half an hour. We look at two 30 minute windows 0-30 and 30-60. No matter how many confirmations we get for OldA in the first slot of 0-30 we will need to check reachability once for OldA in the second slot 30-60

This argument gets weaker the more addresses the node gets. Another point in support of the proposal is this protocol will be a superset of the single address request protocol where you send exactly one address in request for reachability testing. Autonat client implementations wishing to simplify can implement a single request per address system within this scheme by sending exactly one address always.

[marten-seemann]

You’d need to be smarter than just sending your entire list of addresses. If you have enough confirmations for OldA, don’t send it.

Where this proposal leads to improvements is in situations where

• you have multiple new addresses (new transport in IPv4, IPv6, different listen addresses)
• you generate „guesses“ for new addresses (like https://github.com/libp2p/go-libp2p/pull/2251 for example)

[sukunrt]

Can you elaborate?

you generate „guesses“ for new addresses (like https://github.com/libp2p/go-libp2p/pull/2251 for example)

Why can't you verify these guesses with a single address request protocol?

[marten-seemann]

I expect us to generate a number of guesses. Not all of them will be super high priority to test them, but rather a „nice to have“. Those addresses can then be added as lower-prio addresses.

[sukunrt]

This will be helpful in cases where we are interested in determining reachability for a newly address transport for which support in the network is low. Many requests for this new transport address will be rejected because the server cannot dial this transport. This proposal allows us to reuse those requests to check reachability for other addresses.

I think my understanding here was wrong.

Should we put this new transport address in to a lower priority bucket that's added on to requests as a "nice to have"? This would reduce the number of dial requests in the network since actively verifying these new transport address might spam the network a lot?

[marten-seemann]

Should we put this new transport address in to a lower priority bucket that's added on to requests as a "nice to have"? This would reduce the number of dial requests in the network since actively verifying these new transport address might spam the network a lot?

Why would they be lower priority? You'd really want to confirm the new transport, if you manage to find a peer that speaks that transport already. Therefore, it would need to have the highest priority, wouldn't it?

[sukunrt]

How would we determine whether the peer supports a particular transport? Based on the advertised addresses in identify?

[marten-seemann]

Here's how I imagine an AutoNAT v2 client would be implemented: The client keeps a list of addresses that it's tracking.

• Some of these addresses were recently verified, and will be verified in 30 minutes. We don't send these addresses in dial requests before expiration of that timer.
• For the other addresses we calculate a "priority score". The priority score determines the order of the addresses in dial requests.
• Clients should also implement some kind of rate limiting, most likely via a leaky bucket algorithm, to allow for rapid address evaluation right after bootup, but slowing down later.

Factors that increase the priority of an address:

• It's a transport that lots of peers don't support yet (as evident from them skipping our dial request in favor of a lower priority address).
• The NAT code told us that our external address was changed, need to re-verify our most important addresses asap.

Factors that decrease the priority:

• We already have a few addresses for the same transport and they're already verified. Not much value in adding even more addresses, even if they work.

I'm sure there's more factors we can come up with to create a ranking.

[sukunrt]

This makes sense. Thanks for elaborating.

This proposal would help in cases when you have many low priority addresses.