- 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.
