Comment by cperciva | Hacker News Reader

Comment by cperciva | Hacker News Reader

Parent Full thread

Not sure that that user was referring to; but yes, there is a specific topological problem: Routing tables. With current internet topology, only a small number of nodes need to know how to route to everywhere; most nodes simply forward 99.9% of addresses to their default "upstream" router.

Since the vast majority of nodes are not able to keep global routing tables (both because they lack the storage, and also because they lack the bandwidth needed to keep such tables up to date) you have two choices: 1. A subset of nodes are "supernodes" which know how to get anywhere (aka. our current internet topology), or 2. Addresses carry enough semantic meaning to allow nodes to guess which way to forward them (e.g., "I don't know who this packet is going to, but it's somewhere in San Francisco").

That second option would require a complete renumbering of the Internet, and it's still not clear that it would work; purely geographic routing would result in packets from Plymouth to New York getting stuck at Land's End because they want to go West but the cables all land East of there.

Note: This problem doesn't exist with small mesh networks, because for small networks you can have every node maintain a copy of the entire routing table.

Would it not be possible to build a distributed routing table?

There is CJDNS (https://github.com/cjdelisle/cjdns/blob/master/doc/Whitepape...) which has distributed routing table and addressing based on public keys.

Traditional tables won't scale.

Have each node know it's position (lat/lon) and the position of it's nearest neighbors. When you send a packet, you send it to a lat/lon, and every node that sees your packet just tries to nudge it a little closer, until it gets there. Then to speed things up on the return trip we can ask each intermediate to add their position to a list on the packet.

Of course, moving nodes present a bit of a problem. Because they will keep attaching and detaching, there returning packets won't know where to reach them. I suppose if you knew your route through space you could send "scout" packets ahead of you, feel out the terrain, and prepend those positions to the list of your packets (so that they can find you when they return).

Dealing with changes to the (static) topology and also rogue nodes (ones that misbehave, drop packets, lying about their position, etc) are interesting problems. I think they can be solved.

I think geography is a red herring.

The addresses must have meaning and hosts must self organise into a subnet based on connectivity, which feels like a np-hard problem... That does not imply that there is no reasonably well working approximation that works more or less as good except for edge cases. (Literally, ha...)

No reason a spatial routing algorithm couldn't take connectivity into account. Indeed, this is a pretty straight-forward application of A*.

I came to think of molds and how they route networks with just local agents...

It might be, but you'd need to be smarter than me.

Maybe the problem is harder than it superficially seems, but assuming the network is not super sparse, sending things in the right geographical direction (GPS is ubiquitous) should be a very good heuristic. Couple it with exact routing information for the "neighborhood" (idk which radius would make sense) of a node, should be able to avoid going down a dead end most of the time.

here's a simple (very bad) example of distributed routing.

Addresses are simply bitstrings of some length.

If my address is a=a1a2...an, I need to store the first segment of the shortest path to each r_1=a'1a2...an, r_2=a1a'2...an all the way up to r_n=a1a2...a'2, where a'k != ak (i.e. all the addresses with a hamming distance of exactly 1 from me). I then simply route a message with an address b=b1b2...bn to r_i where i is the first non-zero bit of a xor b.

There is Kademlia, but it still needs to be improved to take geo distance and link quality into account, for it to work on a global scale.

There is Geodemlia, that routes by geographical distance and is based of Kademlia and its routing buckets.

The problem, as with most P2P-networks, is that its not resistant to high network churn.

Reply on news.ycombinator.com