FISHEYE ROUTING PROTOCOL IN NS2

Hi guys in this post, we present a novel routing protocol for wireless ad hoc networks – Fisheye State Routing (FSR) in NS2. FSR introduces the notion of multi-level fisheye scope to reduce routing update overhead in large networks. Nodes exchange link state entries with their neighbors with a frequency which depends on distance to destination. From link state entries, nodes construct the topology map of the entire network and compute optimal routes.

MANET nodes are laptop, personal computer, personal digital assistants, mobile phones MP3 Players and these can be located in airplanes, trains, ships, cars offices and homes. A simple MANET can be designed at home to connect wirelessly the mobile nodes or it can be used in disaster hit area when a communication infrastructure collapses and there is insufficient time to install new infrastructure, MANETs are the best solution to build a fast infrastructure in disaster situation because they allow plug and play networking. Since they need no central management so they can be used in military operations where troops move in the battlefield without need of central unit for synchronization. Hence MANETs can be used in disaster recovery, mobile conferencing, battle field and emergency services. 

Wireless networking is an emerging technology that will allow users to access information and services electronically, regardless of their geographic position. The use of wireless communication between mobile users has become increasingly popular due to recent performance advancements in computer and wireless technologies. This has led to lower prices and higher data rates, which are the two main reasons why mobile computing is expected to see increasingly widespread use and applications. There are two distinct approaches for enabling wireless communications between mobile hosts. The first approach is to use a fixed network infrastructure that provides wireless access points. In this network, a mobile host communicates to the network through an access point within its communication radius. When it goes out of range of one access point, it connects with a new access point within its range and starts communicating through it. An example of this type of network is the cellular network infrastructure. A major problem of this approach is handoff, which tries to handle the situation when a connection should be smoothly handed over from one access point to another access point without noticeable delay or packet loss Another issue is that networks based on a fixed infrastructure are limited to places where there exists such network infrastructure. The second approach is to form an ad-hoc network among users wanting to communicate with each other. This means that all nodes of these networks behave as routers and take part in discovery and maintenance of routes to other nodes in the network .This form of networking is limited in range by the individual nodes transmission ranges and is typically smaller compared to the range of cellular systems. However, ad-hoc networks have several advantages compared to traditional cellular systems. The advantages include „on-demand‟ setup, fault tolerance, and unconstrained connectivity. 

A key feature that sets ad-hoc wireless networks apart from the more traditional cellular radio systems is the ability to operate without a fixed wired communications infrastructure and can therefore be deployed in places with no infrastructure. This is useful in disaster recovery, military situations, and places with non-existing or damaged communication infrastructure where rapid deployment of a communication network is needed. A fundamental assumption in ad-hoc networks is that any node can be used to forward packets between arbitrary sources and destinations. Some sort of routing protocol is needed to make the routing decisions. A wireless ad-hoc environment introduces many problems such as mobility and limited bandwidth which makes routing difficult. This thesis researches existing traditional routing protocols, examines current proposed mobile ad-hoc routing protocols, and then designs and implements a functional link-state routing protocol employing a novel “fish-eye” updating mechanism specific for a wireless infrastructure. This mechanism is then analyzed to evaluate its effectiveness and the advantages it can offer. 

FISHEYE ROUTING PROTOCOL 

Protocol Overview 

In this our main focus is on the Fisheye Routing Protocol. The goal is to provide an accurate routing solution while the control overhead is kept low. The proposed scheme is named “Fisheye Routing” due to the novel „fisheye‟ updating mechanism. Similar to Link State Routing, Fisheye Routing generates accurate routing decisions by taking advantage of the global network information. However, this information is disseminated in a method to reduce overhead control traffic caused by traditional flooding. Instead, it exchanges information about closer nodes more frequently than it does about farther nodes. So, each node gets accurate information about neighbors and the detail and accuracy of information decreases as the distance from the node increases. Fisheye Routing determines routing decisions using a table-driven routing mechanism similar to link state. The table-driven ad hoc routing approach uses a connectionless approach of forwarding packets, with no regard to when and how frequently such routes are desired. It relies on an underlying routing table update mechanism that involves the constant propagation of routing information. Fisheye routing takes advantage over Linkstate which is chosen over Distance Vector by implementing a novel updating mechanism to reduce control overhead traffic.

Algorithm 

There are 3 main tasks in the routing protocol: 

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

Each node initially starts with an empty neighbor list and an empty topology table. After its local variables are initialized, it invokes the Neighbor Discovery mechanism to acquire neighbors and maintain current neighbor relationships. LSPs in the network are distributed using the Information Dissemination mechanism. 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. Kleinroch and Stevens proposed the fisheye technique to reduce the size of information required to represent graphical data. The original idea of fisheye was to maintain high resolution information within a range of a certain point of interest and lower resolution further away from the point of interest. For routing, this fisheye approach can be interpreted as maintaining a highly accurate network information about the immediate neighborhood of a node and becomes progressively less detailed as it moves away from the node. Figure 2 illustrates the application of fisheye in a mobile wireless network. The figure defines the scope of fisheye for the center node. The scope is defined in terms of the nodes that can be reached in a certain number of hops. The center node has most accurate information about all nodes in the first circle, and becomes less accurate with each outer circle. Even though a node does not have accurate information about distance nodes, the packets are routed correctly because the route information becomes more and more accurate as the packet moves closer to the destination.

The reduction of routing messages is achieved by updating the network information for nearby nodes at a higher frequency and remote nodes at a lower frequency. As a result, considerable amount of LSPs are suppressed. When a node receives a LSP, it calculates a time to wait before sending out the LSP from the following equation: 

UpdateInterval = ConstantTime * hopcount^alpha 

ConstantTime is the user defined default refresh period to send out LSPs(in the first scope), hopcount is the number of hops the LSP has traversed, alpha is a parameter that determines how much effect each scope has on the Update Interval. Values for alpha are zero(same as no fisheye) and greater than or equal to one(fisheye). A maximum value of Update Interval is established to prevent an effective complete suppression of LSP messages(when calculated UpdateInterval is too large). 

When a router accepts a LSP from a faraway node, and has not yet sent out the LSP in memory, the next time it will send out the LSP will be the minimum of the time left to wait in memory and the new calculated UpdateInterval based on the new LSP: 

UpdateInterval(new) = MIN(UpdateInterval(memory), UpdateInterval(LSP)) 

This is to prevent a router from waiting indefinitely to send out a LSP when a new LSP arrives before the one in memory is sent out for that node.

Route Computation 

Once the router has a database of LSPs, it computes the routes based on the Djikstra‟s algorithm which computes all shortest paths from a single vertex. The link metric used for path cost is the hop count. The algorithm uses 3 databases:

1) Link State Database- Contains the LSPs the node received. 

2) PATH- contains ID, path cost, forwarding direction tuples. Holds the best path found. 

3) TENT- contains ID, path cost, forwarding direction tuples. Holds possible best paths. 

The Djikstra algorithm is as follows: 

1) Start with “self” as the root of a tree by putting (myID, 0, 0) in PATH.

2) For node N just place in PATH, examine N‟s LSP. For each of N‟s neighbors, add the total path cost at N to the cost path of each neighbor. If the new total path of the node is better than the value for that node in PATH or TENT, put into TENT. 

3) If TENT is empty, terminate the algorithm. Otherwise, find the minimal cost in TENT, move into PATH, and go to Step 2. 

One the algorithm completes, PATH now contains the shortest next-hop information for each destination. The protocol can now use the PATH database as a routing table to forward packets toward their destinations. 

Implementation

Please download files from following links;

FSR NS2.35 Patch

FSR Examples

Enjoy!!! Happy Coding.