Fisheye State Routing (FSR) is an improvement of GSR (both are based on the link state protocol). The large size of update messages in GSR uses a considerable amount of bandwidth.



picture by: Iwata1999

General:
An example of a fisheye’s scope is shown above for the (red) center node.
The scope is defined in terms of the number of hops needed to reach a certain node.

In FSR, every update message doesn’t contain information about all nodes in the network. Instead, information about closer nodes is exchanged more frequently than it is done about farther nodes, thus reducing the update message size.
The center node has most up to date information about all nodes in the inner circle and the accuracy of information decreases as the distance from node increases.

This procedure of dividing the network into different scope levels is done at each node, meaning that it is independent on a central entity.

Even if a node doesn’t have accurate information about far away nodes, the packets will be routed correctly because the route information becomes more and more accurate as the packet gets closer to the destination.
This means that FSR scales well to large networks as the overhead is controlled.

Protocol Operation:
Fisheye State Routing is a table-driven or proactive routing protocol.
As mentioned, FSR is based on link state routing and it is able of immediately providing route information when needed.
FSR is functionally similar to LS as it maintains a full topology map at each node.

The link state packets are exchanged periodically instead of event driven.
The topology tables are send to local neighbours only ( instead of flooding the entire network) Sequence numbers are used for entry replacements as well as for providing loop-free routing.

The fisheye scope message updating scheme is highly accurate for inner scope nodes as entries in the routing table corresponding to nodes within the smallest scope are send to the neighbors with the highest frequency. For outer scope nodes, information may blur due to longer exchange interval but there is no need to "find" the destination firstly (as in on-demand routing).

The fisheye scope technique allows exchanging link state messages at different intervals for nodes within different fisheye scope distance, leading to a reduction of the link state message size.



picture by: Iwata1999

The bold entries in figure 2 are propagated to the neighbors at the highest frequency, as they have low hop counts.The GST entry shows the neighbors corresponding to each node in the network.

In FSR, each node keps:

Topology Table
The Topology table is created by using the topology information obtained from the link state messages. Each destination has an entry in the table (full topology map).
An entry conists of two parts: the link state information and a destination sequence number.
Based on this table, the routing table will be calculated. The distance information will then be obtained from the routing table calculation. It is used to classify the node to a fisheye scope.
The topology table has following entries for every link state entry:
- Destination Address
- Destination sequence number
- Link State List

Neighbor Link State List
On receiving a link state message, a node records/updates the sender in its neighbor list.
If nothing is received for a timeout interval, the corresponding station will be removed from the neighbor list.
The following information is maintained for each neighbor node:
- Neighbor Node Link State
- Latest timestamp

Routing Table
The routing table provides next hop information to forward a packet to a destinations in the network. The entries are updated on a topology table change. The routing table consists of the following fields:
- Destination Address
- Next hop address
- Distance

The inaccuracy for far away nodes will increase in a mobile environment but a packet approaching its destination finds more and more accurate routing instructions as it enters sectors with higher refresh rates.

Pro´s
FSR is suitable for large and highly mobile network environments as it triggers no control messages on link failures. Broken links won´t be included in the next link state message exchange. This means that a change on a link far away does not necessarily cause a change in the routing table.

FSR is mainly based on simplicity, as it uses up-to-date shortest routes, it is robust to host mobility as it exchanges partial routing update information with neighbours only, thus reducing routing update traffic.
FSR is QoS ready, which means that it is possible to extend the definition of link state by adding bandwidth and channel quality information to the link entry.

Con´s
It is easy to locate destinations due to the flat addressing scheme and topology map, but this also limits scalability.
Other negative points are the routing table storage complexity and the processing overhead.
FSR doesn’t provide any form of security, as most other protocols.

Protocol Reference:
[Pei2000] [Pei2000a] [Pei2000b] / manet-fsr-00.htm

Other sources:
[Iwata1999] / jsac99.pdf
[Hong2002] / 01020231-from-ntmgz-hxy.pdf
[Chowdavarapu2000] / adhocprots.doc

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