Perbandingan Kompleksitas Algoritma A-star, Floyd-warshall, Viterbi Pada Sdn (software Defined Networking)

Abstract

Algoritma Pencarian jalur terpendek atau lebih dikenal sebagai shorterst-path dipakai dalam menentukan rute dalam sebuah graff. Ini dilakukan untuk menentukan jalur terpendek dari titik awal sampai titik tujuan dalam sebuah graff.Algoritma pencarian jalur terpendek sendiri sudah diimplementasikan didalam jaringan, ini dilakukan untuk mencari jalur atau rute terpendek dari suatu host awal ke host tujuan dengan topologi tertentu. Dengan adanya banyak algoritma pencarian jalur terpendek tentunya memberikan kita pilihan untuk menentukan algoritma mana yang ingin digunakan. Disamping itu kita harus menentukan algoritma manakah yang memiliki waktu komputasi tercepat dan penggunaan ruang memori yang efisien. 

Dalam penelitian ini dilakukan perbandingan kompleksitas algoritma pada jaringan SDN. dimana tujuannya adalah menentukan

algoritma yang paling baik dalam sebuah topologi dengan menentukan kompleksitas masing masing algoritma. Dalam penelitian ini dilakukan pengujian QoS dengan parameter delay, delay yang dimaksud adalah one way delay (latency) dan resource utilization. juga mininet dipilih sebagai emulator jaringan SDN yang yang bertindak sebagai data plane, sementara RYU dipilih sebagai controller yang bertindak sebagai control plane. Dan protokol yang dipilih adalah protokol OpenFlow. Penggunaan algoritma A-star, Floyd-warshall, dan Viterbi sebagai penjaluran yang diimplentasikan didalam controller. dengan topologi yang digunakan yaitu mesh dan tree dengan penggunaan variasi switch yang berbeda yakni 5,8, dan 11. 

Berdasarkan pengujian didapat nilai delay dan resource utilites dengan mengacu pada standarisasi ITU.T G.1010 dengan nilai rata

rata delay < 60s dan packet loss 0%. sehingga  dapat dikatakan layanan ini sudah baik menurut standarisasi ITU.T G.1010. Didapatkan juga bahwa kompleksitas total yang didapatkan dari pengujian menunjukan bahwa algoritma Floyd-warshall memiliki nilai kompleksitas paling rendah pada topologi mesh dan algoritma viterbi memiliki kompleksitas paling rendah pada topologi tree..