Pengembangan Mekanisme Route Discovery Untuk Menghindari Congestion Menggunakan Algoritma Johnson Pada Software Defined Network

Segara, Akbar Pandu (2020) Pengembangan Mekanisme Route Discovery Untuk Menghindari Congestion Menggunakan Algoritma Johnson Pada Software Defined Network. Masters thesis, Institut Teknologi Sepuluh Nopember.

[thumbnail of 05111850010009-Master_Thesis.pdf]
Preview
Text
05111850010009-Master_Thesis.pdf

Download (2MB) | Preview

Abstract

Software Defined Network (SDN) merupakan paradigma baru arsitektur jaringan yang menawarkan konsep control plane yang terpisah dengan data plane. Pada control plane diimplementasikan sebuah controller yang secara terpusat berfungsi untuk melakukan control terhadap perilaku jaringan komputer. Sedangkan perangkat jaringan seperti switch atau router pada sisi data plane menjadi perangkat untuk forwarding paket. Dengan model control plane terpusat SDN sangat rentan akan terjadinya congestion dikarenakan model komunikasi one-to-many. Salah satu cara untuk menghindari kongesti adalah dengan menentukan routing paket menggunakan suatu algoritma routing tertentu.
Penelitian ini bertujuan untuk mengembangkan metode route discovery saat untuk menghindari congestion pada pada SDN. Dengan menggunakan Algoritma Johnson untuk mencari rute alternatif dengan cost yang paling minim saat terjadi congestion. Dimana algoritma Johnson memiliki sifat all-pair shortest path dengan membandingkan seluruh pasang node pada topologi untuk menentukan rute terpendek. Karena algoritma Johnson merupakan penggabungan 2 algoritma shortest path, hal ini dapat mempercepat response time saat pertama kali algoritma melakukan pencarian rute.
Berdasarkan hasil uji coba, pada skenario topologi mesh mengalami penurunan latency 0.459 ms menjadi 0.406 ms dan pada topologi fat-tree mengalami penurunan 0.781 ms menjadi 0.236 ms setelah diimplentasikannya metode. Hasil uji coba throughput skenario topologi mesh mengalami kenaikan 8.4% sedangkan pada topologi fat-tree mengalami peningkatan 11.6%. Pada uji coba response time pada kedua buah skenario menunjukkan algoritma johnson memiliki kecepetan yang baik dibanding hasil response time algoritma OSPF Dijkstra. Hal ini dikarenakan sifat all-pair shortest path yang membandingkan seluruh pasang node untuk menentukan rute terpendek sedangkan Dijkstra adalah termasuk algoritma greedy dimana algoritma ini akan mencari nilai sementara antar node pada setiap langkahnya.

==================================================================================================================

Software Defined Network (SDN) is a new paradigm of network architecture that offers a separate control plane concept with a data plane. In the control plane a controller is centrally implemented which functions to control the behavior of a computer network. While network devices such as switches or routers on the data plane side become devices for packet forwarding. With a centralized control plane model SDN is very vulnerable to congestion due to the one-to-many communication model. One way to avoid congestion is to determine packet routing using a particular routing algorithm.
This study aims to develop a method of route discovery in SDN. By using Johnson's Algorithm to find alternative routes with the least cost when there is congestion. Where Johnson's algorithm has the nature of all-pair shortest path by comparing all node pairs in the topology to determine the shortest route. Because the Johnson algorithm is a combination of two shortest path algorithms, this can speed up response time the first time the algorithm does a route search.
Based on the test results, in the mesh topology skenario the latency decreased 0.459 ms to 0.406 ms and the fat-tree topology decreased from 0.781 ms to 0.236 ms after the method implementation. Result of throughput in the mesh topology increased by 8.4% while in the fat-tree topology increased by 11.6%. The response time trials in both skenarios show that the Johnson algorithm has a good response time comparing the results of the Dijkstra OSPF Algorithm. This is due to the nature of the all-pair shortest path that compares all pairs of nodes to determine the shortest route while Dijkstra is a greedy algorithm where this algorithm will look for temporary values between nodes at each step.

Item Type: Thesis (Masters)
Uncontrolled Keywords: johnson, routing, shortest path, SDN, congestion avoidance
Subjects: T Technology > TK Electrical engineering. Electronics Nuclear engineering > TK5105.585 TCP/IP (Computer network protocol)
T Technology > TK Electrical engineering. Electronics Nuclear engineering > TK5105.5956 Quality of service. Reliability Including network performance
Divisions: Faculty of Intelligent Electrical and Informatics Technology (ELECTICS) > Informatics Engineering > 55101-(S2) Master Thesis
Depositing User: Akbar Pandu Segara
Date Deposited: 13 Aug 2020 03:56
Last Modified: 03 Jun 2023 15:04
URI: http://repository.its.ac.id/id/eprint/77987

Actions (login required)

View Item View Item