Saturday, August 10, 2013
- 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.