26.2 Usage of Hierarchical routing

Hierarchical routing requires some additional features and mechanisms for the simualtion. For example, a new node object called HierNode is been defined for hier rtg. Therefore the user must specify hierarchical routing requirements before creating topology. This is done as shown below:

First, the address format (  ) or the address space used for node and port address, needs to be set in the hierarchical mode. It may be done in one of the two ways:

  set ns [new Simulator]
  \$ns set-address-format hierarchical

This sets the node address space to a 3 level hierarchy assigning 8 bits in each level.

or,

  \$ns set-address-format hierarchical \ \<\# bits in
  level 1\> ...\<\# bits in nth level\>

which creates a node address space for n levels of hierarchy assigning bits as specified for every level.

This other than creating a hierarchical address space also sets a flag called EnableHierRt_ and sets the Simulator class variable node_factory_ to HierNode. Therefore when nodes are created by calling Simulator method ``node'' as in :

$ns node 0.0.1, a HierNode is created with an address of 0.0.1;

Class AddrParams is used to store the topology hierarchy like number of levels of hierarchy, number of areas in each level like number of domains, number of clusters and number of nodes in each cluster.

The API for supplying these information to AddrParams is shown below:

AddrParams set domain_num_ 2
lappend cluster_num 2 2
AddrParams set cluster_num_ \$cluster_num
lappend eilastlevel 2 3 2 3
AddrParams set nodes_num_ \$eilastlevel

This defines a topology with 2 domains, say D1 and D2 with 2 clusters each (C11 & C12 in D1 and C21 & C22 in D2). Then number of nodes in each of these 4 clusters is specified as 2,3,2 and 3 respectively.

The default values used by AddrParams provide a topology with a single domain with 4 clusters, with each cluster consisting of 5 nodes.

Appropriate mask and shift values are generated by AddrParams for the hierarchical node address space.

Each HierNode at the time of its creation calls the method `mk-default-classifier '' to setup n numbers of address classifiers for n levels of hierarchy defined in the topology.

  HierNode instproc mk-default-classifier {} {
    \$self instvar np_ id_ classifiers_ agents_ dmux_ neighbor_ address_ 
    # puts "id=\$id_"
    set levels [AddrParams set hlevel_]
    for {set n 1} {\$n \<= \$levels} {incr n} {
      set classifiers_(\$n) [new Classifier/Addr]
      \$classifiers_(\$n) set mask_ [AddrParams set NodeMask_(\$n)]
      \$classifiers_(\$n) set shift_ [AddrParams set NodeShift_(\$n)]
      }
    }

At the time of route computation, a call is made to add-hroute instead of the conventional add-route used for flat-routing. Add-hroute populates classifiers as shown in the otcl method below:

HierNode instproc add-hroute { dst target } {
  \$self instvar classifiers_ rtsize_
  set al [\$self split-addrstr \$dst]
  set l [llength \$al] 
  for {set i 1} {\$i \<= \$l} {incr i} {
    set d [lindex \$al [expr \$i-1]]
    if {\$i == \$l} {
      \$classifiers_(\$i) install \$d \$target
      } else {
      \$classifiers_(\$i) install \$d \$classifiers_([expr \$i + 1])
      }
    }
  # increase the routing table size counter - keeps track of rtg 
  # table size for each node
  
  set rtsize_ [expr \$rtsize_ + 1]
 }

For an example of 3 level of hierarchy, the level 1 classifier demuxes for domains, level 2 for all clusters inside the node's domain and finally classifier 3 demuxes for all nodes in the particular cluster that the node itself resides. For such a topology, a HierNode with address of 0.1.2 looks like the figure below:

  

Figure 26.1: Hierarchical classifiers

hier-classifier

Thus the size of the routing tables are considerably reduced from n² as seen for flat routing where each node had to store the next_hop info of all other nodes in the topology. Instead, for hierarchical routing, a given node needs to know about its neighbours in its own cluster, about the all clusters in its domain and about all the domains. This saves on memory consumption as well as run-time for the simulations using several thousands of nodes in their topology.