I think mesh networks, such as Netsukuku or Batman, work more or less like this. But these are not internet networks anymore. They are alternative, quite experimental, networking protocols.
What I'm looking for is something that scales massively, to trillions of IP addresses at least.
The idea of decentralizing IP attribution is really interesting.
But you would force routers to perform non-constant operations (index searches) to find the correct route, wouldn't you?
Today, I think (really not sure), routers can figure out the route in constant time, just by looking at the IP.
A lookup on a bloom filter would be a constant time (relative to what?) lookup too, you hash the IP address and get a few indexes from it (10 seems to be the most efficient), and lookup the number stored in each memory location. If any of the numbers is zero, you know the IP is not accessible from that direction. Else, you just choose the one with the lowest numbers. For a new IP that would be ten seek()s on a hard drive, else it is cached in memory..
Maybe it could make routing easier if instead of generating independent keys, you use signed certificates. This way the certificates could follow some sort of hierarchy. Your cert is signed by your ISP cert which is signed by the backbones certs your ISP uses and so on...
Then routers would only have to index the certificates of the backbones... the index could get quite smaller. But anyway, routing would become a much heavier process than it is in IP.
That would work and make things more efficient as long as there is a single way into the network. However, you have to validate the signatures, start worrying about overhead. I mean, a SHA1 hash is 320 bits. That could also lead the way to filtering routers dropping packets based on ISP, or similar (not that there would be anything wrong with that).
Other considerations are economizing traffic and handling malicious routers... I imagine you would implement some sort of algorithm that would disconnect bad routers that are infecting routing tables as well as pass packets along their lowest latency path (not congesting one router if there's a less loaded one available). Malicious routers seem to be a problem even today, if an ISP create an "Internet black hole" with bad routing settings!