Shortest Path Routing - a type of routing algorithm

- The usage of the re-configurable logic has been increasing day by day both in scope as well as number. 

- Re-configurable computing combines both the hardware speed and the flexibility of the software. 

- This is the result of the combination of the highspeed computing and re-configurability.

- Tough requirements are posed up on the routing in a network by the increased QoS i.e., the quality of service. 

- This increase in the complexity of the computational capabilities bears an exponential relation with the increased QoS. 

- However, additional computational resources are needed for achieving a network performance level that is acceptable. 

- Re-configurable computing offers a promising solution to the issues of the computations in the routing process.

There are 3 major aspects of the shortest path routing as mentioned below:

Ø Path selection: This involves the various algorithms such as the Dijkstra’s and bellman – ford algorithms and shortest path and minimum – hop routing.

Ø Topology change: Changes in the topology are detected using the beacons.

Ø  Routing protocols: This involves routing protocols such as the link state routing protocols and distance vector protocols.

- Forwarding and routing are two different things. 

- In forwarding, the data packet is directed towards an outgoing link and an individual router is used that also maintains a forwarding table.

- Routing computes the paths that have to be followed by the packets. 

- Routers exchange the path information between themselves and the forwarding table is created by each and every router in the chain.

Routing is important for the following three main reasons:

Ø  End-to-end performance: The user performance is affected by the path quality, throughput, packet loss and delay in propagation.

Ø  Use of the network resources: The traffic has to be balanced between the several links and routers. The traffic is directed towards the links that are lightly loaded for avoiding the congestion.

Ø  Transient disruptions during changes: These disruptions include the load balancing problems, maintenance, failures etc. the packet loss as well as the delay has to be limited while the changes take effect.

- Shortest path routing is based up on a path selection model that gives more preference to the destination. 

- This type of routing is insensitive to load as in it involves the static link weights.

- Here, either the sum of the link weights or the minimum hope is considered. 

- In a shortest path problem, the link costs are given for a network topology. 

- For example, C(x,y) denotes the cost of the node x to node y. 

- If the two nodes x and y are not adjacent to each other the cost is taken to be infinity. 

- The least cost paths linking all the nodes are computed from a node taken as the source. 

- Dijkstra’s shortest path algorithm is one of the algorithms used in the shortest path routing. 

- A central role is played by the problems involving finding the shortest paths in the designing and the analyzation of the networks.

- A majority of the routing problems can be taken as the shortest path problems and solved if each link in the network has appropriate cost assigned to it. 

- This cost even reflects the bandwidth as well as the bit error ratio if required. - A number of algorithms are available for computing the shortest path.

- But these algorithms are applicable only if a single non – negative additive metric characterizes every edge in the network.

- Out of these algorithms, the Dijkstra’s algorithm is the most famous one. 

- This algorithm find its use in the OSPF (open shortest path first) routing procedure of the internet. 

- In this algorithm the number of operations carried out are proportional to the number of nodes in the network and the iteration is carried for n-1 times.