What does path finding in internet routing do and how is it different from A*?
- by alan2here
Note: If you don't understand this question then feel free to ask clarification in the comments instead of voting down, it might be that this question needs some more work at the moment. I've been directed here from the Stack Excange chat room Root Access because my question didn't fit on Super User.
In many aspects path finding algorithms like A star are very similar to internet routing. For example:
A node in an A* path finding system can search for a path though edges between other nodes.
A router that's part of the internet can search for a route though cables between other routers.
In the case of A*, open and closed lists are kept by the system as a whole, sepratly from any individual node as well as each node being able to temporarily store a state involving several numbers.
Routers on the internet seem to have remarkable properties, as I understand it:
They are very performant.
New nodes can be added at any time that use a free address from a finite (not tree like) address space.
It's real routing, like A*, there's never any doubling back for example.
Similar IP addresses don't have to be geographically nearby.
The network reacts quickly to changes to the networks shape, for example if a line is down.
Routers share information and it takes time for new IP's to be registered everywhere, but presumably every router doesn't have to store a list of all the addresses each of it's directions leads most directly to.
I'm looking for a basic, general, high level description of the algorithms workings from the point of view of an individual router. Does anyone have one?
I presume public internet routers don't use A* as the overheads would be to large, and scale to poorly. I also presume there is a single method worldwide because it seems as if must involve a lot of transferring data to update and communicate a reasonable amount of state between neighboring routers.
For example, perhaps the amount of data that needs to be stored in each router scales logarithmically with the number of routers that exist worldwide, the detail and reliability of the routing is reduced over increasing distances, there is increasing backtracking involved in parts of the network that are less geographically uniform or maybe each router really does perform an A* style search, temporarily maintaining open and closed lists when a packet arrives.
