Routing 2.0

Routing algorithm

This is done in two stages. First, the name is resolved into a "location" by asking the responsible name server. Name servers can use the same hierachical approach as today, so you have top-level domains and root servers who know the name servers of the next level domains and so on. The locations of (and very likely also the route to) the root servers are known.

A "location" is defined by network relationships. Since networks tend to be hierarchical, with backbones and branches, a qualified location is a hierarchy of network relations. Each part of the location contains a network id (under which the router server is reachable), the top level id will be one of the big internet backbones. This qualified location can be seen as part of a network graph, so through one network there's a route. The example below will use a name for the id; in general, the id needs to be unique, but not directly human readable (for debugging purposes, human readability is a good idea).

To calculate an actual route now is straight-forward. You ask your routing server for a route to the destination. This routing server first asks for the location of the destination. The routing server can know about peering between his network and one of the subnets in the destination, or if none exist, it knows about networks up in the hierarchy, and can ask those. They will repeat that until a peering is found. To close the path, a route through the two peering networks is queried from the relevant routing servers, and concatenated with the remainder of the hierarchy of both destination and origin. Routing and parts of routes are cached. Routes and hierarchies are not necessarily unique; cost calculations may be used to select the cheapest route.

Examples

Some examples make this easier to understand.

Route to arbitrary destination

Let's assume I want to find a route between my office workstation in Munich to a corporate web server in San Francisco, let's call the source workstation.somecompany.de, and the target www.foobar.com. This is the DNS name, not the location. The location string of my workstation is workstation.somecompany.m-net.level3, because somecomany uses m-net as network provider, and m-net peers to the top-level backbone level3. The location string for the target is different, too, let's call it foobar.webhoster.bay-net.alter-net. Since all backbones peer with each other, we know that we can connect those two strings, reverting the destination one: workstation.somecompany.m-net.level3.alter-net.bay-net.webhoster.foobar is the symbolic notation of one possible complete route.

In these strings, each .network. segment corresponds to a route. The two end points don't need a route, only for the segments between. Our original location query has given us the nets through bay-net and webhoster, so the remaining task is to ask level3 how to get from m-net to alter-net, and alter-net how to get from the level3 peering point to bay-net. This is concatenated with the known location information of my workstation, and gives one possible route.

However, this hierarchical relation only allows to find one route. There may be others, cheaper ones. So we give some opportunity here by asking each of the routing servers on the way if they know a cheaper way to the complete destination. We therefore don't ask level3 for the connection between m-net and alter-net, we first ask m-net for the connection to foobar.webhoster.bay-net.alter-net.

Now, m-net does not know how to connect webhoster or bay-net (too far away), but it knows that it peers to alter-net, as well (though not as cheap as level3). Therefore it issues two queries: One for foobar.webhoster.bay-net on alter-net, and one for foobar.webhoster.bay-net.alter-net on level3. Incidentially, bay-net also peers with level3 (but didn't tell us). Both therefore will answer, and give both routes and a "cost" number in their return value. Cost can be a complicated thing, it involves available bandwidth, latency, and actual peering costs (cents per gigabyte).

So we now have two possible routes: workstation.somecompany.m-net.level3.bay-net.webhoster.foobar, and with different routes through m-net and bay-net through alter-net instead of level3. The routing server of m-net then can choose by the cost assigned with these routes, which to pass back to us.

Routing shortcuts

Let's change the query to some webhoster in Munich, which replied with telecom as area network. m-net and telecom have direct peering, so the string could shorten to workstation.somecompany.m-net.telecom.webhoster.foobar. However, m-net knows that it peers with webhoster directly, so the string shortens to workstation.somecompany.m-net.webhoster.foobar.

More about it

These location names in reality would be the names of the routing servers of those nets. They would be unique, and also have a DNS resolvable location. To ask a routing server therefore requires first to get a route to it. The good news is: You don't need the answer of this routing server. It will be an end node, you need only routes through nets you pass through.

The route to a routing server is a vital information, it can be obtained when connecting to a network. Generally, the address 0 into any network should give a routing server or at least a redirection response. So networks that are connected together can automatically obtain the path to the routing servers of peering networks. Through recursive queries, routing servers extend their knowledge, and can find shortcuts either for computing the route (by using cached knowledge how to go on), or actual shorter routes. They can frequently ping their peers if they are still available, and prune paths from their data bases if connections get lost. Since routing tries to find the shortest path in a graph, cycles do not hurt (only local broadcast domains must avoid cycles, or at least detect them and break broadcasts).

This automatic discovery of neighbors is the preferred way to set up networks. It is also possible to automatically determine the level. Top-level networks, i.e. backbones, are so by administrative definition (it is not possible to autoconfig that), let's call their level 0. If you install a new network, it's isolated router will start up as such, knowing that it is isolated (level infinity). It will look for neighbors, and once it finds a neighbor with a known level (e.g. the ISP), it will set its own level one level above this neighbor. If further lookups for neighbor networks give one with a lower level, it will lower its own level, too, and communicate that information when asked by other neighbors. The location string that is used for identification is always obtained by asking the hierarchically higher neighbor for his location, and concatenate that with the own id.