Fisheye State Routing

From Wikipedia, the free encyclopedia
Jump to: navigation, search

Fisheye State Routing (FSR) is an implicit hierarchical routing protocol. Also considered a proactive protocol and is a link state based routing protocol that has been adapted to the wireless ad hoc environment. Relays on link state protocol as a base, and it has the ability to provide route information instantly by maintaining a topology map at each node. Thus will maintain updated information from the neighbor node through a link state table. In each node the network, a full topology map is stored then utilized (List of ad hoc routing protocols).

According to Kleinrock and Stevens , FSR uses the "fisheye" technique where the technique was used to reduce the size of information required to represent graphical data. The eye of a fish captures with high detail the pixels near the focal point. The detail decreases as the distance from the focal point increases.

In routing, the fisheye approach translates to maintaining accurate distance and path quality information about the immediate neighborhood of a node, with progressively less detail as the distance increases.

Algorithm[edit]

FSR is based on a link-state foundation updating mechanism. Which has the following feature: maintaining a topology map at each node. this mechanism reduces the control overhead by disseminating topology information using the fisheye technique, where routing information is updated at different rates depending on the distance from the source.and it can be broken down into :


Node stores the Link State for every destination in the network
Node periodically broadcast update messages to its neighbors
Updates correspond to closer nodes propagate more frequently

Pseudocode[edit]

In this routing protocol , there are three major tasks

1) Neighbor Discovery: responsible for establishing and maintaining neighbor relationships.
2) Information Dissemination: responsible for disseminating Link State Packets(LSP), which contain neighbor link information, to other nodes in the network.
3) Route Computation: responsible for computing routes to each destination using the information of the LSPs.

Initially every node starts has an empty topology table and an empty neighbor list. Invoking the Neighbor discovery mechanism in order to acquire neighbors and to maintain current neighbor relationships After its local variables are initialized. By using the Information Dissemination mechanism, the distribution of LSP in the network is produced. Each node has a database consisting of the collection of LSPs originated by each node in the network. From this database, the node uses the Route Computation mechanism to yield a routing table for the protocol. This process is periodically repeated.

Applications[edit]

One use of the FSR is reducing overhead control traffic. It has also shown a good performance in terms of successful packet delivery in the presence of low mobility. During the case of high mobility ;In order to get a successful packet delivery , The update interval time must be properly selected

Related algorithms[edit]

A similar algorithm to FSR is the Link-state routing protocol . It has a different approach in which routing information are updated Entries in routing , FSR uses the fisheye technique which allows considering a fractions of the scope of the eye , leading to reduction in the message size thus routing update overhead is reduced.

References[edit]

1 - http://nrlweb.cs.ucla.edu/publication/download/203/05_75_fisheye-state-routing-in.pdf
2 - Ad Hoc Mobile Wireless Networks: Principles, Protocols and Applications By Subir Kumar Sarkar, T.G. Basavaraju
3 - http://pure.ltu.se/portal/files/1059266/Paper.pdf
4 - http://tools.ietf.org/html/draft-ietf-manet-fsr-03