Attamimi, Ibrahim (2017) Analisis Perbandingan Algoritma Floyd-Warshall Dan Dijkstra Untuk Menentukan Jalur Terpendek Pada Jaringan Openflow. Sarjana thesis, Universitas Brawijaya.
Abstract
Software Defined Network (SDN) merupakan suatu pemodelan jaringan yang memisahkan antara control plane dan data plane dengan menggunakan standar komunikasi protocol Openflow untuk menghubungkan keduanya. SDN mulai dikembangkan beberapa tahun terakhir ini dan sudah banyak diimplementasikan salah satunya adalah untuk routing jaringan. Terdapat dua algoritma routing dalam penelitian ini yaitu Algoritma Dijkstra dan Algoritma Floyd-Warshall. Kedua Algoritma tersebut memiliki cara pencarian yang berbeda, pada Algoritma Floyd-Warshall menggunakan pencarian jalur all pair shortest path yang artinya pencarian jalur terpendek dapat ditentukan antara semua pasangan simpul, sedangkan pada Algoritma Dijkstra yang menggunakan pencarian jalur single source shortest path yang artinya pencarian jalur terpendek dapat ditentukan dari simpul tertentu ke semua simpul yang lain. Kedua algoritma ini akan diimplementasikan menggunakan emulator Mininet dan Ryu sebagai controller nya. Pengujian yang akan dilakukan meliputi parameter antara lain convergence time, throughput, link failure, resource usage. Pada pengujian convergence time, Algoritma Dijkstra lebih unggul dengan rata-rata sekitar 9,08- 16,03ms dibandingkan dengan algoritma Floyd-Warshall dengan rata-rata sekitar 14,51-38,63ms. Berdasarkan hasil pengujian throughput, kedua algoritma tidak terlalu memiliki perbedaan yang signifikan. Pada Algoritma Floyd-warshall memiliki rata-rata throughput sekitar 12,7-29,54 Gbps sedangkan Algoritma Dijkstra memiliki rata-rata sekitar 12,89-29,22 Gbps. Untuk hasil pengujian dari Link failure, Algoritma Floyd-Warshall lebih unggul Karena memiliki recovery time lebih cepat dengan rata-rata sekitar 30,34-38,51 detik dibandingkan dengan algoritma Dijkstra dengan rata-rata 37,65-44,92 detik. Untuk hasil dari pengujian resource usage, pada pengukuran memory usage kedua algoritma sama-sama mengkonsumsi memory sama besar namun pada pengukuran CPU Usage, Algoritma Floyd-Warshall mengkonsumsi daya CPU lebih besar dibandingkan dengan Algoritma Dijkstra.
English Abstract
Software Defined Network (SDN) is a network modeling that separates between control plane and data plane by using Openflow protocol communication standard to connect both of them. SDN began to be developed in recent years and has been widely implemented, one of them is for network routing. There are two routing algorithms in this research which are Dijkstra Algorithm and Floyd- Warshall Algorithm. Both algorithms have different search methods, the Floyd- Warshall algorithm uses the search path of all pair shortest path which means that the shortest path search can be determined between all pairs of nodes, while in Dijkstra algorithm the searching process uses single source shortest path means that the shortest path search can be determined from a particular node to all other nodes. Both of these algorithms will be implemented using Mininet emulator and Ryu as its controller. Tests that performed in this research include parameters such as convergence time, throughput, link failure, and resource usage. The result of convergence time test from this research showed that Dijkstra's algorithm is superior to an average of about 9,08 to 16,03 milliseconds compared with the Floyd-Warshall algorithm with an average of about 14,51 to 38,63 milliseconds. Based on the results of throughput testing, both algorithms do not have significant differences. The Floyd-warshall Algorithm had an average throughput of 12.7- 29.54 Gbps while Dijkstra's Algorithm had an average of about 12.89-29.22 Gbps. For the test results from the Link failure, the Floyd-Warshall Algorithm is superior because it had a faster recovery time with an average of about 30.34-38.51 seconds compared to Dijkstra's algorithm with an average of 37.65-44.92 seconds. The usage resource test showed that memory usage measurements for both algorithms share the same memory, but the CPU usage measurements showed the Floyd-Warshall algorithm consumes more CPU power compared to Dijkstra's Algorithm.
| Item Type: | Thesis (Sarjana) |
|---|---|
| Identification Number: | SKR/FTIK/2017/360/051706873 |
| Uncontrolled Keywords: | SDN, OpenFlow, Mininet, Ryu, Dijkstra, Floyd-Warshall |
| Subjects: | 000 Computer science, information and general works > 004 Computer science > 004.2 System analysis and design, computer architecture, performance evaluation |
| Divisions: | Fakultas Ilmu Komputer > Teknik Informatika |
| Depositing User: | Budi Wahyono Wahyono |
| Date Deposited: | 16 Aug 2017 01:32 |
| Last Modified: | 05 Nov 2024 02:09 |
| URI: | http://repository.ub.ac.id/id/eprint/1370 |
![[thumbnail of Ibrahim Attamimi.pdf]](http://repository.ub.ac.id/style/images/fileicons/text.png) |
Text
Ibrahim Attamimi.pdf Download (4MB) |
Actions (login required)
 |
View Item |