Back to index
The Landmark Hierarchy: A New Hierarchy for Routing in Very Large Networks
Paul F. Tsuchiya
- 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
that are <=k hops away contain routing entries to that
- 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:
- 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.
- 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
A cool hierarchy, definitely relevant for networking, although the benefits
of it over area hierarchies don't seem particularly stunning.
- 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
Back to index