The Landmark Hierarchy: A New Hierarchy for Routing in Very Large Networks

One-line summary:

Overview/Main Points

• Area Hierarchy: in the (old) area hierarchy, a set of routers are grouped into a level 0 area, a set of level 0 areas are grouped into a level 1 area, a set of level 1 areas are grouped into a level 2 area, etc. The only constraint on the grouping is that between every level k-1 area in a level k area, a path must exist which does not leave the level k area. Network addresses are simply (level k area).(level k-1 area)....(level 0 name). Level k routers keep routing information on all other level k areas within its own level k+1, and all level k-1 areas within itself. This means routes are not necessarily the shortest path routes.
• Landmark Hierarchy overview:
  • A landmark of radius k is a router whose neighbour routers that are <=k hops away contain routing entries to that landmark router.
  • We can build a hierarchy out of landmarks. LMi[id] refers to a landmark of level i, with unique identifier id. Each LMi[id] has a radius ri[id]. Every router in the network is a LM0[id] of some small radius r0[id]. Some LM0[id]'s are also LM1[id]'s, with r1[id] > r0[id], with the constraint that at least one LM1[id] is within r0[id] hops of each LM0[id]. This means for every level 0 landmark, at least one level 1 landmark knows how to route to that level 0 landmark. The top-level landmarks have radii greater than the diameter of the network, so all routers in the network can see the top-level landmarks.
  • Each router keeps a table of the next hop on the shortest path to each landmark for which it has entries; so each router will have entries for all LM0[id] within a radius of r0[id] of itself, all LM1[id] within a radius of r1[id] of itself, etc.
  • Addressing is done the obvious way: LMk[id].LMk-1[id]....LM0[id].
  • Routing is done the obvious way. To find a path from source to some destination LMk[id].LMk-1[id]...LM0[id], at each hop along the way the router looks in its table and finds an entry for the lowest landmark that it and the destination share, and sends the packet towards that landmark. Again, we don't get shortest paths.
• Dynamic algorithms:
  • This paper does the old punteroo on dynamic algorithms (routing updates, dynamic address assignment, etc).
  • Landmark assignment: each node starts as a level 0, and advertises itself to peers within k hops. If node hears a level 1 router, it uses it, otherwise it and peers do an election.
  • routing algorithm: use distance-vector peer exchange. Link-state won't work, because full topologies are not available using landmark. Only modification is that an additional field (time-to-live) is needed in peer-exchanged updates, which is initialized to the landmark radius and decremented each exchange.
  • address assignment: somthing called assured destination binding is mentioned but never explained.
  • administration: boundaries set up by hand.
• Performance:
  • Landmark hierarchy beats out area hierarchy in routing table size, path lengths. Simulations and numbers pulled out of the air (references to other papers) are used to justify this.
  • The placement of landmarks is shown to be the key, critical component to the performance of a landmark network, as it ultimately determines routing table sizes and the path length : shortest possible path length ratios.

Relevance

Flaws

• The hierarchy concept is clear, but the devil is in the details and all of the details are omitted from this paper, particularly the dynamic algorithm details.
• The performance numbers all seem to stem from small simulations, which is unfortunate. What about huge networks (i.e. internet sized)?