Zone-Based Hierarchical Link State Protocol

ZHLS

The Zone-Based Hierarchical Link State Protocol is based on the GPS (Global Positioning System). ZHLS is similar to the Zone Routing Protocol. It is a hybrid routing protocol acting similar like ZRP. The protocol is proactive when the destination node is in the same zone as the node which sent the request (Intrazone Clustering). On the other hand, the protocol is reactive when the destination node isn't within the zone from the source node (Interzone Clustering). But in ZHLS the network is divided in non overlapping zones. Unlike other hierarchical protocol, there is no zone head. The zone size depend on node mobility, network density, transmission power and propagation characteristics. Each node only knows the connectivity within its zone and the zone connectivity of the whole network. The node knows its position and zone ID because of the Global positioning system. It can determine its zone ID by mapping its physical location to a zone map. This zone map has to be worked out at the design stage.

Two levels of ZHLS topology

node level (low level topology)

A node level topology tells how nodes of a zone are connected to each other. A virtual link between two zones exists when at least 1 node of a zone is connected to another zone in a different zone.

zone level (high level topology)

A zone level topology tells how zone are connected to each other. The zone level topologie is distributed to all nodes.

Intrazone

Every node broadcast a link request. Nodes within its communication range answer with the link response containing their node ID and zone ID. After receiving all answers, the node generates its LSP. A LSP contains the node ID of its neighbours in the same zone and the zone ID of its neighbours in different zones. The LSP packet from a node is forwarded to all nodes in the same zone. A list of a node LSPs will be stored in every node in the same zone. Node LSPs from other zones will not be stored, because there are only propagated in their own zone. Now the node will know the node level topology of its zone. The shortest path algorithm is used to build its intrazone routing table.



Nodes : h, i, j, g are gateway nodes

Interzone

It might be that node receive link responses from nodes which aren´t in its zone. These nodes are called gateway nodes.

Each node LSPs contain the zone ID’s of the connected zones, so each node will know which zones are connected to its zone. In the picture above, zone 2, 3 and 4 are connected with zone 1. After receiving all node LSPs, each node of the same zone generates the same zone LSP. The gateway nodes send the zone LSP to every node in the network. Every zone performs this procedure. A list of zone LSPs is stored by every node. So every node will know the zone level topology of the network. A interzone routing table is built and the shortest path algorithm is used to find the shortest path.




After creating a node LSP and a zone LSP each node has full node connectivity knowledge about the nodes in its zone and only zone connectivity information about other zones in the network. Given the zone ID and the node ID of a destination, the packet is routed based on the zone ID Zone till it reaches the correct zone. Then in that zone, it is routed based on node ID.
The tables are updated periodically. The gateway nodes will not broadcast a zone LSP if its value is the same as the old one. The zone LSP is updated only when any virtual link is broken or created. It reduces the traffic in the network.
Duplicate copies of zone LSP will not be forwarded. It might be that a node receives the same zone LSP from two different gateways. The first one will be forwarded, the second one not.

Routing Mechanism'

Node a wants to send data to z. Before doing that, it checks if node z is in its zone. If yes node a knows the route to z. It finds it in the intrazone routing table. If not, node a sends a location request (a,1(a's zone ID),z, X) to every other zone X. The location request will be forwarded by the gateway nodes from zone to zone according to their interzone routing table. They look if the node is in their intrazone routing table. If the node is in its zone the gateway-node reply with a location response (z,5(z´s zone ID),a,1). Now node a can send data to node z.

References

[Joa-Ng1999] Original paper, pictures
[Joa-Ng1999a]

"Zone-Based Hierarchical Link State Protocol" is mentioned on: Ad-Hoc Protocols (History) | Ad-Hoc Workshop Winter 04/05 (Termine) | Intrazone Routing Protocol