Algoritma Greedy

 “Algoritma Greedy untuk Menentukan Lintasan Terpendek”

Permasalahan utama pencarian rute terpendek tentu saja mencari rute atau jalur terpendek yang memungkinkan. Namun untuk implementasinya, persoalan ini dapat dikembangkan lebih luas lagi diantaranya untuk mencari biaya minimum, dll. Intinya adalah mencari solusi yang palin efektiv yang dapat diterpakan dalam persoalan yang dihadapi. Perangkat pemantau jaringan (Network monitoring tools) merupakan perangkat jaringan yang bertugas melakukan pemantauan terhadap kinerja dan performa jaringan. Perangkat ini digunakan untuk membantu seorang administrator jaringan melakukan pengawasan dan manajemen terhadap keseluruhan perangkat yang terhubung ke jaringan komputer tersebut. Sebuah perangkat pemantau jaringan biasanya harus memenuhi dua hal berikut ini :

a. Lingkup (Coverage), sebuah perangkat pemantau harus mampu melakukan pemantauan terhadap keseluruhan link dan rute pada jaringan komputer.

b. Efisien, Sebuah perangkat pemantau harus mampu meminimasi kebutuhan terhadap resource untuk melakukan pemantauan. Resource dalam hal ini dapat berupa perangkat komputer, modem, router ataupun perangkat-perangkat jaringan lainnya.

Untuk memenuhi kebutuhan akan sebuah alat pemantau jaringan yang mampu memenuhi kedua persyaratan diatas, maka pendekatan pemantauan jaringan secara 2 fase ( two-phased network monitoring) dapat digunakan. Dalam penerapannya, pemantauan jaringan 2 fase menggunakan algorima greedy. Algoritma greedy digunakan sebagai algoritma utama dalam kedua fase tersebut.

1.      Algoritma Greedy

Algoritma greedy merupakan salah satu algoritma yang dapat menyelesaikan bermacam-macam permasalahan termasuk permasalahan mengoptimalkan (minimum atau maksimum) hasil yang didapat. Algoritma greedy menerapkan metode pencarian terkontrol dengan melakukan pilihan yang memberikan hasil optimal sementara. Dewasa ini, terdapat berbagai jenis algoritma yang telah diperkenalkan, seperti A bintang (A-star) atau algoritma genetik dimana inti dari semua algoritma ini adalah algoritma greedy. Memilih nilai optimal (maksimum atau minimum) dari sekumpulan pilihan merupakan konsep dasar dari algoritma greedy

Kelebihan utama dari algoritma greedy adalah :

-          Mudah diimplementasikan, algoritma greedy sangat mudah untuk diimplementasikan pada persoalan-persoalan yang ada.

-          Efisien, algoritma greedy merupakan algoritma yang sangat efisien karena algoritma ini selalu berusaha memilih hasil optimal.

2.      Network Monitoring

Network monitoring merupakan proses pemantauan terhadap kinerja, kondisi dan performa dari jaringan. Network monitoring biasanya digunakan pada jaringan berskala besar untuk mempermudah kerja dari seorang administrator jaringan. Terdapat dua metode pemantauan jaringan yang telah diterapkan:

a. Node-oriented tools dimana setiap perangkat pada jaringan masing-masing memiliki aplikasi pemantau jaringan. Sehingga dapat memberikan informasi dengan tingkat akurasi yang tinggi untuk setiap perangkat tersebut. Kekurangan utama dari metode ini adalah tidak dapat melakukan pemantauan parameter yang melibatkan lebih dari satu perangkat jaringan.

b. Path-oriented tools dilakukan dengan memanfaatkan teknik-teknik pemantauan jaringan seperti ping, traceroute, telnet, dan sebagainya. Metode ini memberikan kemampuan lebih untuk melakukan pemantauan terhadap beberapa perangkat jaringan tanpa harus melakukan instalasi aplikasi pemantau disetiap perangkat jaringan. Kelemahan utama dari metode ini adalah waktu tenggang yang sangat lama jika penempatan node pemantau (node station) tidak pada tempat yang optimal.

Kajian ini dilakukan dengan memanfaatkan path-oriented tools dan menerapkan skema 2 fase untuk mengoptimalkan hasil pemantauan.

Pemodelan Jaringan Pada Kajian

Penulis memodelkan jaringan komputer sebagai graf G(V,E), dimana node V/v pada graf merupakan representasi dari router atau perangkat komputer dan sisi E/e pada jaringan merepresentasikan komunikasi yang menghubungkan setiap node. V’/v’ merupakan rerpresentasi dari node yang bertetangga dengan sisi E/e dan E’/e’ merupakan representasi dari sisi yang bertetangga dengan V’/v’. Jumlah dari node dan sisi pada graf dinotasikan dengan |V| dan |E|. Pst merupakan rute dimana sebuah paket IP berjalan dari sumber s dengan tujuan t. Semua paket data diteruskan menggunakan protokol standard dalam pengiriman paket data. Routing tree (RT) dari s merupakan semua kemungkinan rute yang dapat dituju oleh s pada V. Setiap rute (sisi) pada pemodelan ini memiliki nilai yang nantinya berfungsi untuk memilih nilai optimal.

                                                                                            

Cara Kerja

Pada bagian ini akan dijelaskan secara ringkas cara pemantauan jaringan dengan menggunakan metode path-oriented yang diterapkan dalam kajian. Pertama kali, akan dilakukan test untuk menentukan monitoring station dari RTs, yaitu dengan melakukan pengecekan terhadap node yang ada pada RTs dan hubungannya terhadap node lain. Pengecekan dilakukan dengan cara mengirimkan pesan terhadap setiap node yang ada pada jaringan. Seperti pada gambar 2, pengecekan akan dimulai dari node A yang mengirimkan pesan ke semua node yang ada di RTs tersebut (BCDEFGH), dan seterusnya sampai ditemukan node yang memiliki delay minimal ke semua node yang ada di RTs.

Gambar 2 Pemilihan Monitoring Station

Jika monitoring station telah ditemukan, maka selanjutnya akan dilakukan fase ke-2. Pada fase ke-2, sebuah monitoring station RTs yang ingin melakukan pemantauan terhadap jaringan, akan mengirimkan pesan ke semua node yang ada pada RTs melalui node s(sebagai monitoring station). Kemudian node-node yang ada pada RTs akan mengirimkan kembali pesan secara langsung kepada s. Monitoring station akan melakukan analisis terhadap pesan-pesan yang dibalas oleh node yang adapada RTs sesuai dengan protokol TCP/IP

Gambar 3 Fase 2, Melakukan Pemantauan Terhadap Setiap node

Terdapat beberapa ketentuan untuk kedua fase ini :

a. Sebuah monitoring station harus mampu mencakup semua link dan node yang ada pada RTs-nya (monitoring group)

b. Fase kedua memastikan bahwa setiap link yang ada pada jaringan dipantau oleh paling sedikit satu buah monitoring station.

Dengan menggunakan skema dua fase, permasalahan pemasangan dan perbaikan terhadap monitoring station dan juga pengiriman pesan terhadap banyak node dapat dihindari. Karena pada setiap fase ini dicari solusi optimal untuk mengoptimalkan kinerja dari pemantauan jaringan, yaitu dengan mengurangi sebanyak mungkin monitoring station yang mungkin muncul dan juga mengoptimasi jumlah maksimal node yang mungkin ditangani oleh sebuah monitoring station.

Algoritma Greedy untuk Penentuan Monitoring station

Dengan merepresentasikan permasalahan sebagai graf G(V,E) penulis dapat mendefinisikan permasalahan set cover (SC). Sekumpulan sisi E, mendefinisikan semua elemen yang ada pada graf Z. Kumpulan set Q termasuk subset-nya Qv = {e│e ∈ Tv} untuk semua node v ∈ V, dimana cost /weight dari setiap sisi e pada subset didefinisikan sebagai wv. Algoritma greedy merupakan algoritma yang memanfaatkan iterasi dimana setiap iterasi dilakukan pemilihan terhadap nilai paling optimal. Kita misalkan C ⊆ Z sebagai kumpulan dari elemen yang belum termasuk dalam monitoring station. Sebagai tambahan, nv = {Qv ∩ C} sebagai jumlah dari elemen C untuk setiap v ∈ V pada setiap permulaan iterasi.

Cara kerja algoritma ini adalah dengan memilih set Qv pada setiap iterasi. Kemudian dilakukan seleksi terhadap rasio minimum dan menghilangkan setiap elemen dari C sampai C menjadi kosong. Kompleksitas waktu optimal dari penggunaan algoritma ini adalah O(ln |V|) dan kasus terburuk O(│V│3).

Algoritma ini mampu memberikan solusi mendekati optimal untuk permasalahan pencarian monitoring station. Dalam setiap iterasinya dilakukan pencarian node yang memiliki delay paling kecil terhadap semua node yang ada pada jaringan.

Algoritma Greedy untuk Penentuan Penugasan Probe/Node

Berdasarkan hasil penelitian, untuk penugasan probe diperlukan pengiriman 2 pesan. Pesan itu digunakan untuk melakukan pemantauan tenggang waktu terhadap link yang ditentukan. Algoritma ini mendefinisikan hubungan monitoring station dan sisi sebagai (s, e), e ∈ Ts, dan dalam setiap iterasi algoritma dilakukan pemilihan terhadap pasangan(s’,e’) dengan nilai paling minimal dan menambahkan pesan sebagai penugasan untuk melakukan analisis. Jika terdapat pasangan yang memiliki nilai yang sama, mak dipilih berdasarkan jumlah hop yang dilalui untuk mencapai pasangan tersebut. Algoritma ini dilakukan sampai semua sisi telah termonitor. Berikut algorima greedy yang diterapkan.

Algoritma diatas dimulai dengan melakukan penugasan terhadap node yang paling dekat dengan monitoring station. Kemudian penugasan akan dilakukan terhadap link yang berdekatan dengan node sebelumnya. Hal ini dilakukan untuk menghindari situasi dimana terdapat node yang ditangani oleh dua monitoring station yang berbeda.

Gambar 4 r sebagai monitoring station melakukan penugasan