Subscribe by Email

Saturday, August 10, 2013

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. 

No comments:

Facebook activity