Hierarchical routing was mainly devised, among other things, to reduce
memory requirements of simulations over very large topologies. A
topology is broken down into several layers of hierarchy, thus
downsizing the routing table. The table size is reduced from
, for flat routing, to about log n for
hierarchical routing. However some overhead costs results as
number of hierarchy levels are increased. Optimum results were found for
3 levels of hierarchy and the current ns implementation supports upto a
maximum of 3 levels of hierarchical routing.
To be able to use hierarchical routing for the simulations, we need to
define the hierarchy of the topology as well as provide the nodes with
hierarchical addressing. In flat routing, every node knows about every
other node in the topology, thus resulting in routing table size to the
order of
. For hierarchical routing, each node knows only about
those nodes in its level. For all other destinations outside its level
it forwards the packets to the border router of its level. Thus the
routing table size gets downsized to the order of about log n.
Tom Henderson 2011-11-05