30-10-2012, 04:53 PM
Dijkstra’s Shortest Path Routing Algorithm in Reconfigurable Hardware
Reconfigurable Hardware.pdf (Size: 102.42 KB / Downloads: 39)
Abstract.
This paper discusses the suitability of reconfigurable computing
architectures to different network routing methods. As an example
of the speedup offered by reconfigurable logic, the implementation
of Dijkstra’s shortest path routing algorithm is presented and its performance
is compared to a microprocessor-based solution.
Introduction
The uses of reconfigurable logic have increased both in number and scope. The
combination of reconfigurability and high-speed computing has given birth to a
new field of engineering: reconfigurable computing which ideally combines the
flexibility of software with the speed of hardware. [1]
Increased Quality of Service (QoS) poses tough requirements on network
routing. The increase in computational complexity is exponentially related to
an increase in QoS, and to achieve acceptable network performance, additional
computing resources are required [2]. A promising solution to computational
bottlenecks in network routing is reconfigurable computing.
This paper presents a brief overview of the applications of reconfigurable computing
in network routing. As a case study, an FPGA-based version of Dijkstra’s
shortest path algorithm is presented and the performance differences between
the FPGA-based and a microprocessor-based versions of the same algorithm are
compared.
2 Classification of Routing Methods and Suitability to
Reconfigurability
There are a number of ways to classify routing algorithms [3,4]. One of the
simplest routing strategies is static routing, where the path used by the sessions
of each origin-destination pair is fixed regardless of traffic conditions.
Most major packet networks use adaptive routing, where the paths change
occasionally in response to congestion. The routing algorithm should change its
routes and guide traffic around the point of congestion.
Dijkstra’s Shortest Path Algorithm in Route
Computation
The problem of finding shortest paths plays a central role in the design and
analysis of networks. Most routing problems can be solved as shortest path
problems once an appropriate cost is assigned to each link, reflecting its available
bandwidth, delay or bit error ratio, for example.
There are various algorithms for finding the shortest path if the edges in a
network are characterized by a single non-negative additive metric. The most
popular shortest path algorithm is Dijkstra’s algorithm [6], which is used in
Internet’s Open Shortest Path First (OSPF) routing procedure [7].
FPGA-Based Dijkstra’s Shortest Path Algorithm
A parameterizable version of Dijkstra’s shortest path algorithm was designed in
VHDL [10] with Synopsys’ FPGA Express design software version 3.4 [11]. The
design was targeted for Altera’s FLEX10K device family [12] with the Quartus
design software [13].
The parameterizable features of Dijkstra’s shortest path algorithm were compiled
into a separate VHDL package which was included in the main design file.
This way the design of other versions of Dijsktra’s algorithm with different accuracy
and for networks of different sizes is made easier, since all the changes
are made only in the VHDL package.
The block diagram of the FPGA-based Dijkstra’s shortest path algorithm
is presented in Fig. 1. The network structure is presented in the internal ROM
block of the logic device. In the block diagram of Fig. 1, there are six address
lines. This is sufficient to represent all node-to-node links of networks of size
upto eight nodes, if the network is represented as an adjacency matrix [9]. The
internal RAM blocks of the logic device represent the known status of nodes,
the distance to this node and the previous node.
Conclusions
Reconfigurable architectures have many applications in network routing. Depending
on the routing algorithm or method, reconfigurability may assist in
speeding up network routing.
The FPGA-based version of Dijkstra’s shortest path algorithm was tens of
times faster than a microprocessor-based version. This can be attributed to the
following factors: multiple assignments to variables are executed concurrently,
multiple arithmetic operations, including comparisons, are executed in parallel
and the data structures and tables are implemented in the internal memory
blocks.