Hieracical State Routing

The characteristic features of Hierarchical State Routing (HSR) are multilevel clustering
and logical partitioning of mobile network nodes.

Multilevel clustering

The physical network nodes are partitioned into clusters and clusterheads are elected as in a
clusterbased algorithm. This is comparable with clustering in CGSR.

Additionally, clusterheads at a low level become members of the next higher
level. These new virtual cluster members organize themselves again into clusters and so on,
this process leads to an hierarchical topology.



pic by Chowdavarapu2000

The figure shows an example of physical clustering.
At level 0, there are 3 physical clusters C0-1, C0-2 and C0-3.

There could be 3 different kinds of nodes in a cluster:
- clusterhead node (station 1, 4 and 6)
- gateway node (2,5)
- internal node (3,7).

The ID´s at level0 are physical addresses (similar to MAC addresses), thus unique.

Level 1 and Level 2 clusters are generated by the recursive selection of clusterheads.
Thus, those upper level clusters are only virtual with so called virtual links between
nodes.

Nodes belonging to a physical cluster broadcast their link information to each other.
Each clusterhead summarizes all information about its cluster and sends it to neighboring
clusterheads via gateway. This knowledge of neighbor clusterheads leads to the formation of
next level clusters.
As already mentioned, clusterheads are member of a virtual cluster on a next higher level and
they exchange their own link information as well as the summarized lower-level information
among each other.

A node in a virtual cluster level floods the information that it obtains to its lower level.
So the lower level will know about the hierarchical topology meaning
that each node has a hierarchical address, called HID (Hierarchical ID).

A hierarchical address is assigned by using the clusterhead (or node) ID´s on the way from
the root (top-level) down to the node (physical level). A HID can be considered as a serie of
MAC addresses.

As a gateway can be reached from the top-level via more than one path, it can have more than
one HID. A hierarchical address is enough to ensure delivery from anywhere in the network to
a specific host. Each node will dynamically keep its HID up-to-date upon receiving updates
from higher level nodes.
Packets will be routed to the destination using the HID.

HID example:
(see figure above):
- node 3 has <1,1,3> as hierarchical address.
- node2 (which is a gateway) has <1,4,2> or <1,1,2> or <6,4,2>…

Routing example:
delivery of a packet from node 3 <1,1,3> to node 7 <6,6,7>

The packet will be first forwarded to the source´s corresponding highest node in hierarchy,
which is node 1.This node forwards the packet to the destination´s top level node,
which is node 6.

Meaning that the packet goes through:
-Node 1 and node 6 in level 2 (top)
this virtual link maps to:
-node 1, node 4 and node 6 in level 1
Virtual links <1,4>, <4,6> in level 1 map to
-paths <1,2,4> and <4,5,6> in level 0

logical partitioning

Logical partitioning means that nodes are partitioned into logical subnetworks
and will get a logical address <subnet, host>.This is done in addition to the HID hierarchical
addressing scheme.
Each subnet is associated with a location management server (LMS), also called home agent,
in order to manage membership. This approach is similar to mobile IP, except that in this case
the home agent may also move.
All home agents transmit their HIDs to the top-level nodes so that they are appended to top
level routing tables. The home agent’s HIDs will be propagated downwards to all nodes.
So each member of a logical subnetwork will know its home agent’s HID as it will be listed
in the routing table.
In a next step, all nodes of a subnet have to register their logical address with their homeagent.
Registration is periodic and event driven (whenever a node moves to a new cluster). To route a
packet, the distributed location server will assist in finding the destination’s HID.

A source, wanting to send a packet, does only know the destination IP, meaning the <subnet, host>
type of address. The source extracts the Subnet address field first and looks up the HID of that
corresponding home agent in its routing table. Then, it has to send the packet to that home
agent using the home agent’s HID. The home agent will find the destination’s HID and delivers
the packet. Once the source and destination know each others HIDs, they are going to bypass the
home agents and communicate directly.

Pro´s

-adaptable to network changes
-logical address/hierarchical address is used for routing
-Find destination problem solved : home agent
-latency for access to non frequently used destinations is low
-Reducing routing table size for most nodes
-Devices with higher capabilities could act as clusterhead
-clusterheads can monitor all the traffic with in the cluster
-clusterheads can provide QoS service to real time applications

Con´s

-High overhead caused by exchange of routing packets
-multiple levels of hierarchy and leader election process
-higher average number of hops the packets take
-higher protocol complexity
-more packets dropped because of invalid routes
-worst case occurs at the top level
-top level nodes have to maintain a routing table of all their clusters at each level

HSR is unaffordable in a typical adhoc wireless network context.
It is better suited for a very high number of nodes.

Protocol Reference:
Pei1999

Other Sources:
Chowdavarapu2000 / adhocprots.doc
Iwata1999 / jsac99.pdf
Hong2002 / 01020231-from-ntmgz-hxy.pdf
Zou2002 / routing_schemes.pdf

"Hieracical State Routing" is mentioned on: Ad-Hoc Protocols (Classification) | Ad-Hoc Workshop Winter 04/05 (Termine)