FPGA-based parallel shortest path searching processor for OSPF routing protocol
Other Title(s)
معالجة للبحث المتوازي عن المسار الأقصر لبروتوكول التوجيه (فتح المسار الأقصر أولا) باعتماد ترتيب البوابات المنطقية المبرمجة مجاليا
Dissertant
al-Abbadi, Muhammad Abd Ali Jawdah
Thesis advisor
Alwan, Majid A.
Abd al-Jabbar, Jasim M.
Comitee Members
Marhun, Ali F.
al-Saffar, Ala A.
Chail, Husayn K.
Amin, Sadiq Y.
Ali, Ramzi S.
University
University of Basrah
Faculty
Engineering College
Department
Department of Electrical Engineering
University Country
Iraq
Degree
Ph.D.
Degree Date
2016
English Abstract
In Open Shortest Path First (OSPF) routing protocol, the shortest paths from each node (router) to other nodes in an area should be determined together with the node’s routing table.
For the shortest path computations, the OSPF protocol considers the network topology as a weighted directed graph and runs the Dijkstra algorithm in all network nodes to construct their routing tables.
However, in the large scale network, the running time of the Dijkstra algorithm increases exponentially because of the Dijkstra algorithm execution time complexity is O(n2) where n is the number of network nodes.
This will slow down the overall network performance because the long delay time of the shortest path computations.
In thesis work, a hardware-based parallel shortest path search (HPSPS) algorithm is suggested for speeding up the shortest path computations by finding simultaneously multiple shortest paths from the source node to many other nodes in an OSPF area.
The HPSPS algorithm running time complexity now reduced to O(n-1).
Two hardware architectures have been proposed based on HPSPS algorithm and implemented inside a single FPGA chip as special purpose processors for improving the shortest path search computations time.
The first processor architecture, namely parallel shortest path search processor (PSPS-Processor), is designed for network sizes up to 128 nodes.
The PSPS-Processor has high performance against the conventionally microprocessor-based software Dijkstra codes in finding the network shortest paths.
Because the logical resources of the FPGA chip are limited, this architecture is no longer applicable for large network size.
To save the FPGA logical resources, a new architecture is proposed based on the HPSPS algorithm for a pipelined-parallel shortest path search processor (PPSPS-Processor) for 256-node network size.
The operation of this processor adopts the divide and conquer concept in dividing the complete 256×256 cost matrix into sixteen 256×16 sub-cost matrices inside the processor.
The shortest path computations will be done consecutively on sub-matrices in a pipelining data flow fashion.
The FPGA area consumption and the processing performance resulting from the implementation of PPSPS-Processor are efficient for large scale network.
The hardware description language VHDL and the Xilinx ISE v13.2 design suite software is used to build the processors targeted to Xilinx Virtex-7 2000T FPGA chip, and a standard PC with Intel core i7 2-GHz processor and 8 GB RAM is used to compute the running time of the software Dijkstra algorithm coded in a MATLAB m.file for the comparison purpose.
Main Subjects
Engineering & Technology Sciences (Multidisciplinary)
Electronic engineering
No. of Pages
175
Table of Contents
Table of contents.
Abstract.
Abstract in Arabic.
Chapter One : Introduction.
Chapter Two : The FPGA : architecture and design flow.
Chapter Three : Design and implementation of FPGA-based parallel shortest path search processor.
Chapter Four : FPGA-based pipelined-parallel shortest path search processor for large scale networks.
Chapter Five : Processor assessment and evaluation.
Chapter Six : Conclusions and suggestions for future works.
References.
American Psychological Association (APA)
al-Abbadi, Muhammad Abd Ali Jawdah. (2016). FPGA-based parallel shortest path searching processor for OSPF routing protocol. (Doctoral dissertations Theses and Dissertations Master). University of Basrah, Iraq
https://search.emarefa.net/detail/BIM-744763
Modern Language Association (MLA)
al-Abbadi, Muhammad Abd Ali Jawdah. FPGA-based parallel shortest path searching processor for OSPF routing protocol. (Doctoral dissertations Theses and Dissertations Master). University of Basrah. (2016).
https://search.emarefa.net/detail/BIM-744763
American Medical Association (AMA)
al-Abbadi, Muhammad Abd Ali Jawdah. (2016). FPGA-based parallel shortest path searching processor for OSPF routing protocol. (Doctoral dissertations Theses and Dissertations Master). University of Basrah, Iraq
https://search.emarefa.net/detail/BIM-744763
Language
English
Data Type
Arab Theses
Record ID
BIM-744763
