Global State Routing (GSR) is based on Link State (LS) routing.

In the LS routing method, each node floods the link state information directly
into the whole network (global flooding) once a link change between
itself and its neighbors is detected.
A node gets to know the whole topology by obtaining link information.
LS routing works well in static topology networks. If links change
quickly at high mobility, frequent global flooding will lead to huge
control overhead (large amount of small packets).

Aim:
The knowledge of full network topology as LS routing should be maintained,
but the inefficient flooding mechanism has to be avoided.


Unlike LS, GSR does not flood link state packets.
Instead, every node maintains its link state table based up-to-date
( LS information received from neighboring nodes)
It will periodically exchange its LS information with its neighbors only
(no global flooding).

This means that GSR is MAC (medium access control) layer efficient as it keeps
the overhead of control message low. GSR still finds accurate and optimal paths.
GSR could be described as being based on LS routing, which has the advantage
of routing accuracy, and the dissemination method used in DBF, to avoid
inefficient flooding like in LS routing.


Each node maintains:

a neighbor list
containing the list of nodes adjacent to the node ( hop=1 )

a topology table
containing the link state information reported by a destination and a timestamp
indicating the time at which this has been reported.

a next hop table
containing the next hop to which the packets for this destination have to be forwarded

a distance table
containing the shortest distance to each destination node


Initially, each node learns about its neighbors by examining each received packet
and thus builds up its neighbor list.
Each node updates link state information in its topology table by receiving link
state messages from its neighbors. LS packets with larger sequence numbers
replace the older ones with smaller sequence numbers.So every node learns the entire
network topology.

The entire topology map (link state table) is exchanged periodically with neighbors
only, meaning that there is no global flooding.
Then each node computes the shortest paths itself using the newly rebuild topology
map, based on Dijkstra’s algorithm.
In summary this means that based on the link state vectors, nodes maintain a global
knowledge of the network topology and take their routing decisions locally.



The following section will describe some performance measurements under different
circumstances (simulated) and compare GSR with both protocols it is partly based
on, namely LS and DBF.

Routing Inaccuracy
GSR is less accurate than LS as it updates routing information only every 3 time
slots, but it still outperforms DBF. Link State reacts fastest to topology changes.

Control Overhead
The control overhead of GSR and DBF remains constant regardless of mobility as the
routing information is exchanged periodically with adjacent neighbors only. LS has
maximum overhead since it is event triggered. This validates that LS is not
suitable for high mobility environment.

Mobility Impact
As described previously, the impact of mobility to routing inaccuracy is independent
of the impact to control overhead. Overall, higher mobility causes higher inaccuracy
for all 3 protocols.

Update Interval
The routing inaccuracy and overhead may be improved or degraded with change in update
interval for GSR and DBF.

Radio Range
A higher transmission range means that one will get a larger connectivity degree but
also a larger control packet size for GSR and LS. More nodes can be reached in one
hop without requiring routing decision at a higher transmission range. Spatial reuse
is less efficient when transmission range is high and routing inaccuracy (routing
error rate) decreases for higher transmission ranges.



Advantages
GSR greatly reduces the control overhead as it avoids flooding for disconnects/reconnects
and updates are time triggered than event triggered.
The routing accuracy of GSR is comparable to an ideal LS scheme and thus superior to
the traditional DBF. A bandwidth function can be used to realize QoS routing.

Disadvantages
The main disadvantage is the large size of the routing message. As the entire topology table
is broadcasted with each update, a considerable amount of bandwidth is consumed. The latency
of the link state change propagation depends on the update period, meaning that it has to be
carefully chosen.

Conclusion
GSR is suitable for a high mobility environment, as bandwidth consumption is
relatively low. Fisheye technology can be used to reduce the size of update
messages, as described in FSR.



Protocol Reference:
Chen1998 / gerla-gsr-icc98.pdf

Other Sources:
Chowdavarapu2000 / adhocprots.doc
Iwata1999 / jsac99.pdf

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