FPGA-based parallel shortest path searching processor for OSPF routing protocol

العناوين الأخرى

معالجة للبحث المتوازي عن المسار الأقصر لبروتوكول التوجيه (فتح المسار الأقصر أولا)‎ باعتماد ترتيب البوابات المنطقية المبرمجة مجاليا

مقدم أطروحة جامعية

al-Abbadi, Muhammad Abd Ali Jawdah

مشرف أطروحة جامعية

Alwan, Majid A.
Abd al-Jabbar, Jasim M.

أعضاء اللجنة

Marhun, Ali F.
al-Saffar, Ala A.
Chail, Husayn K.
Amin, Sadiq Y.
Ali, Ramzi S.

الجامعة

جامعة البصرة

الكلية

كلية الهندسة

القسم الأكاديمي

قسم الهندسة الكهربائية

دولة الجامعة

العراق

الدرجة العلمية

دكتوراه

تاريخ الدرجة العلمية

2016

الملخص العربي

باستخدام بروتوكول التوجيه (فتح المسار الاقصر اولا Open Shortest Path First (OSPF)) يتم حساب المسارات الاقصر من اي عقدة (موجهrouter) )) الى باقي العقد و تكوين جدول التوجيه (Routing Table) لكل عقدة.

و لحساب المسارات الاقصر، تمثل الشبكة في بروتوكول OSPF بمخطط اتجاهي موزون (weighted directed graph) ويستخدم البروتوكول خوارزمية جكسترا Dijkstra Algorithm) ) في كل العقد لتوليد جداول التوجيه.

مع ذلك، ففي الشبكات واسعة النطاق يزداد وقت تنفيذ خوارزمية جكسترا اضعافا بسبب تعقيد زمن التنفيد لخوارزمية جكسترا هو O(n²) لشبكة مكونة من n عقدة مما يؤدي الى انحدار الاداء العام للشبكة بسبب الوقت الطويل لحساب المسارات الاقصر.

في هذه الاطروحة، تم اقتراح خوارزمية بحث متوازي عن المسارات الاقصر اعتمادا على التنفيذ المادي بدلا من التنفيذ البرم جي Hardware-based parallel shortest path search (HPSPS) algorithm) لتسريع حساب المسارات الاقصر بواسطة ايجاد اكثر من مسار اقصر من عقدة المصدر الى اكثر من عقدة هدف في نفس الوقت.

تمتاز خوارزمية HPSPS بتعقيد زمن تنفيذ (1- .O(nتم اقتراح معماريتين لمعالجين اعتمادا على خوارزمية HPSPS للتنفيذ باستخدام رقاقة FPGA كمعالج خاص لتحسين زمن حساب المسارات الاقصر.

معمارية المعالج الاول، والتي سميت )معالج البحث المتوازي عن المسار الاقصر Parallel Shortest (Path Search Processor PSPS-Processor، تم تصميمها لشبكات يصل حجمها الى ۱۲۸ عقدة.

اتسم المعالج باداء عالي مقارنة مع خوارزمية جكسترا منفذة على معالج تسلسلي تقليدي لحساب المسارات الاقصر في الشبكة.

وبسبب محدودية المصادر المنطقية لرقاقة FPGA اصبحت المعمارية غير قابلة للتنفيذ لشبكات اكبر.

وللحفاظ على المصادر المنطقية لرقاقة FPGA، تم اقتراح معمارية مادية جديدة اعتمادا على خوارزمية HPSPS لمعالج يعمل بتقنية خط انابيب للبحث المتوازي عن المسار الاقصر (pipelined-parallel shortest path search processor PPSPS-Processor) لشبكة مكونة من ٢٥٦ عقدة.

عمل هذا المعالج تبنى نضرية فرق تسد في تقسيم مصفوفة التكاليف 256x256 (cost matrix)الى ستة عشر مصفوفة جزئية 25616 x داخل المعالج.

حسابات البحث عن المسارات الاقصر تتم بالتوالي على المصفوفات الجزئية وبطريقة سير البيانات بخط انابيب ( (pipeliningمصادر رقاقة FPGA واداء المعالجة الناتجة من تنفيذ المعالج Processor PPSPS-كان كفوءا لشبكات واسعة النطاق.

تم استخدام لغة وصف البناء المادي VHDL وبرنامج التصميم 13.2 Xilinx ISE لبناء المعالجات على رقاقة Xilinx Virtex-7 2000T FPGA ، كما استخدمت حاسبة بمعالج Intel Core i7 GHz و ذاكرة عشوائية GB 8 لحساب وقت تنفيذ خوارزمية جكسترا مبرمجة بتطبيق MATLAB لإغراض المقارنة.

الملخص الإنجليزي

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.

التخصصات الرئيسية

العلوم الهندسية والتكنولوجية (متداخلة التخصصات)
الهندسة الكهربائية

عدد الصفحات

175

قائمة المحتويات

• APA
• MLA
• AMA

لغة النص

الإنجليزية

نوع البيانات

رسائل جامعية

رقم السجل

BIM-744763