whether it itself is on the path. This drawback is common in the DV routing
technique, and all DV-based routing protocol designers should consider this
issue and find a mechanism to avoid it.
(b) Link State Proactive Routing
Distance vector routing was used in ARPANET until 1979, when it was replaced
by link state routing. The objective of LS routing is to provide an alternative to
DV that avoids routing loops and the subsequent ''count-to-infinity'' problem.
LS routing overcomes this by maintaining global network topology information
at each node.
In LS routing, each node periodically sends information about the cost to reach
each of its direct neighbors and it includes this information in what is known as
the link state packet. This link state packet is sent to all the other nodes in the
network by flooding. Each node does the same link state flooding procedure and,
eventually, each node will have link state packets from all other nodes, so each
node will have information about the complete topology and costs of all the links
in the network. Then Dijkstra's algorithm [ 3 ] can be run locally to construct the
shortest path to all possible destinations. The results of this algorithm can be
stored in the routing tables for later use [ 2 ].
Although LS routing avoids some problems with DV routing, it has a problem
with its storage requirements.
As an advantage, proactive route discovery incurs almost no delay as routes are
calculated in advance and are available in the routing table. However, it has a
disadvantage that may hamper its use in large networks. It incurs an overhead
related to the periodic routing updates which may cause congestion for the
network when it has a large number of nodes. Therefore, in most cases, the
proactive route discovery has problems with network scalability.
Reactive route discovery is also known as on-demand route discovery. As the
name implies, the route is discovered on demand. When a source has a packet to
be sent, it initiates a route discovery process to set up a path to the intended
destination. Many approaches can be followed for path setup where the most
common one is having the source node broadcast a route request packet carrying
the destination address and asking for a route to that destination. When the route
request reaches the destination or an intermediate node that knows a route to that
destination, a route reply packet is sent back to the source carrying details about
the discovered route.
Some protocols perform route discovery on the fly, hop-by-hop. When a node
receives a packet to be forwarded to another node, it decides to which neighbor it
should forward this packet. This type of routing is known as self-routing and it
falls under the category of reactive routing as the route is established on demand.
An example of this type of routing is geographical routing where a node picks
the next hop based on the locations of its neighbors and their distances to the
destination. The self-routing based protocols usually require a form of neighbor
discovery to know about the potential forwarding nodes that the current node
will choose from to be the next hop.