Algoritma Dijkstra Adaptive Routing Pada Jaringan Komputer

Algoritma Dijkstra Adaptive Routing Pada Jaringan Komputer - Jaringan komputer terdiri dari sejumlah komputer yang terhubung satu sama lain melalui saluran komunikasi (misalnya kabel, serat optik, gelombang mikro, gelombang radio). Antara satu komputer dengan komputer lain seringkali terpisah jauh secara geografis (antar kota atau antar negara), atau berada dalam wilayah geografis yang sama (dalam satu gedung, dalam satu area, dsb). Pesan yang dikirim dari satu komputer ke komputer lainnya umumnya dipecah menjadi sejumlah paket (packet) data yang berukuran lebih kecil. Saluran komunikasi yang digunakan untuk menghantarkan paket mempunyai keterbatasan dalam hal kecepatan transmisi (umumnya kecepatan transmisi dinyatakan dalam satuan kbps – kilobit per second). Untuk menyampaikan paket data dari dari satu komputer ke komputer lainnya, sistem jaringan komputer harus dapat melakukan pemilihan rute yang tepat agar paket dapat sampai ke komputer tujuan dalam waktu yang cepat. Yang dimaksud dengan perutean (routing) adalah menentukan lintasan yang dilalui oleh paket dari komputer pengirim (asal) ke komputer penerima (tujuan).

Permasalahannya adalah bagaimana menentukan rute yang tepat sehingga paket data dapat sampai ke komputer penerima dalam waktu yang sesingkat mungkin. Dengan menggunakan rute tersebut, paket data yang sampai ke suatu komputer dapat diarahkan ke komputer tetangga yang tepat sehingga paket menuju komputer penerima dengan delai (delay) waktu yang minimum. Dengan kata lain, kita harus menentukan lintasan terpendek yang akan dilalui oleh paket tersebut dari komputer pengirim ke komputer penerima.

Perutean yang diharapkan adalah perutean adaptif (adaptive routing). Perutean adaptif berarti sistem jaringan komputer dapat menentukan rute baru apabila terjadi perubahan topologi jaringan (misalnya ada penambahan router baru, kerusakan pada suatu router sehingga router tersebut tidak bisa dilalui, atau perubahan kecepatan transmisi antar router).

Jaringan komputer dapat dimodelkan sebagai sebuah graf terhubung, dengan setiap simpul menyatakan sebuah komputer (bisa berupa terminal komputer atau sebuah router. Router adalah komputer yang didedikasikan untuk mengarahkan pesan. Di dalam tugas ini, kita mengasumsikan simpul menyatakan router, sedangkan terminal komputer – yang merupakan komputer end user - dianggap cabang dari router). Sisi di dalam graf menyatakan saluran komunikasi (sering disebut link). Setiap sisi di-assign dengan sebuah label nilai (yang disebut bobot atau weight). Bobot tersebut dapat menyatakan jarak geografis (dalam kilometer), kecepatan transfer data, atau delai transmisi (waktu pengiriman) (lihat Gambar 1 di Lampiran 1). Setiap router memelihara sebuah tabel yang disebut tabel rute (routing table). Tabel rute berisi router asal, router tujuan, dan simpul antara (via) yang dilalui (lihat Gambar 2 di Lampiran 1).

Mencari lintasan terpendek dari router asal ke router tujuan dapat diartikan sebagai menentukan lintasan terpendek dari simpul asal ke simpul tujuan di dalam graf yang merepresentasikan jaringan komputer tersebut. Algoritma Dijkstra adalah algoritma yang banyak digunakan untuk mencari lintasan terpendek. Algoritma ini didasarkan pada metode greedy, yaitu metode yang digunakan untuk memecahkan masalah optimasi.

Buatlah sebuah program aplikasi yang mengimplentasikan algoritma Dijkstra untuk merutekan pesan dari simpul asal ke simpul tujuan di dalam sebuah jaringan komputer dengan waktu transmisi sesingkat mungkin.

Spesifikasi program aplikasi tersebut adalah sebagai berikut:

1. Program menyediakan fasilitas untuk menggambarkan graf yang merepresentasikan jaringan komputer secara interaktif (menggunakan tetikus). Setiap simpul digambarkan sebagai lingkaran yang diberi nomor atau sebagai ikon komputer (lihat Gambar 1), dan setiap sisi dinyatakan sebagai garis lurus. Bobot pada setiap sisi graf menyatakan dua properti data: jarak fisik antar komputer di dalam jaringan (dalam satuan kilomter) dan kecepatan transfer data (dalam satuan kbps). Delai, atau waktu transmisi, antar dua buah simpul dihitung dengan rumus:
   Delai = jarak antara dua buah simpul/kecepatan transmisi antara 2 simpul tsb.
2. Program mampu menyimpan graf yang digambar ke dalam arsip (file). 
3. Program mampu membaca graf yang tersimpan di dalam arsip dan menampilkannya ke layar. 
4. Program mampu membangkitkan tabel rute untuk setiap simpul dengan menggunakan algoritma Dijkstra (lihat gambar 2 di Lampiran 1). Cost yang diminimumkan adalah delai. 
5. Program mampu menerima masukan dari pengguna, yaitu simpul asal dan simpul tujuan, dan menggambarkan lintasan terpendek yang dilalui pesan dari simpul asal ke simpul tujuan sebagai garis yang warnanya berbeda dengan warna sisi lainnya. (Bonus: mampu memperlihatkan animasi sederhana yang berupa pergerakan paket – dinyatakan sebagai segiempat kecil – dari simpul asal ke simpul tujuan melalui lintasan terpendek yang dihasilkan). Lihat Gambar 3 di Lampiran 1. 
6. Program mampu memungkinkan pengguna untuk melakukan perubahan sbb:
   a. Menambahkan sebuah simpul baru dan sisi baru.
   b. Menghapus sebuah simpul (jika sebuah simpul dihapus, maka semua sisi yang bersisian dengan simpul tersebut otomatis terhapus).
   c. Mengubah bobot pada suatu sisi di dalam graf. 

Perubahan tersebut hendaklah interaktif. Bila perubahan yang disebutkan di atas dlakukan oleh pengguna, maka program harus dapat melakukan perutean ulang (membentuk tabel rute yang baru). Inilah yang dimaksudkan dengan perutean adaptif.

Bonus: Program mampu menampilkan tabel rute jika pengguna meng-klik sembarang simpul, menampilkan kecepatan transfer dan jarak antar simpul jika pengguna meng-klik sisi.

Perhatikan, karena adanya spesifikasi nomor 6 ini, maka anda harus dapat memilih struktur data yang tepat untuk merepresentasikan graf. Struktur matriks ketetanggaan yang statik kurang cocok untuk masalah ini, karena elemn matriks tidak dapat ditambah atau dihapus). Stuktur data yang cocok untuk representasi graf adalah senarai ketetanggan (lihat diktat kuliah Matematika Diskrit pada Bab Graf).

Prosedur Pengerjaan

1. Tugas dikerjakan secara berkelompok (1 kelompok @ 3 orang).
2. Bahasa pemrograman yang digunakan bebas, tapi salah satu dari: Bahasa Pascal, Bahasa C/C++, Bahasa Basic, dan Java, dengan kakas pengembangan program yang berbasis GUI, seperti Borland Delphi, Borland C++ Bulder, Visual C, Visual Basic, dll). 
3. Lingkungan (platform) pengembangan program adalah Windows. 
4. Yang diserahkan pada saat pengumpulan antara lain: Disket atau CD yang berisi berisi: program sumber (source code), arsip siap eksekusi (exe), contoh data masukan (graf), dan laporan (dalam format pdf). 

Laporan yang memiliki sistematika sebagai berikut :

i. Deskripsi tugas (dapat diambil dari soft copy tugas ini).

ii. Teori singkat (algoritma greedy, algoritam Dijkstra, dll yang relevan).

iii. Perancangan dan Implementasi, termasuk : algoritma yang dibuat (dalam notasi bahasa pemrograman yang anda gunakan), struktur data, antarmuka, hubungan antar modul, lingkungan pengembangan, dll. Cantumkan juga pembagian tugas setiap anggota di dalam kelompok.

iv. Pengujian program dan analisis hasil. Uji program dengan bermacam-macam contoh data yang disediakan di dalam tugas ini (lihat lampiran). Lakukan juga pengujian bila spesifikasi nomor 6 dilakukan.

v. Kesimpulan dan saran. Berisi kesimpulan dari hasil implementasi program dan saran pengembangan jika ada.

vi. Lampiran berisi: print out layar (yang penting-penting saja), print out gambar graf dan lintasan terpendek antara dua buah simpul, tabel rute, dll.

Laporan dikumpulkan dalam bentuk hard copy dan soft copy (di dalam disket atau CD) dengan format pdf .

Lain-lain

1. Struktur menu minimal di dalam program adalah kira-kira sebagai berikut (anda dapat menambahkan menu lain jika perlu)

Keterangan :

• Jika menu “Pembangkitan tabel rute” rute diaktifkan, maka program menghitung tabel rute untuk setiap simpul. Program tidak perlu menampilkan hasil dari pembangkitan tabel rute ini. 
• Jika menu “Lintasan terpendek”, maka program menampilkan kotak dialog yang meminta pengguna memasukkan simpul asal dan simpul tujuan, lalu tombol <OK> untuk menggambarkan lintasan terpendek, atau tombol <Batal> untuk membatalkan proses. 
• Beri nama program anda dengan nama yang menarik tapi mencerminkan kegunaan program. 

Lampiran 1

Gambar 1. Contoh sebuah jaringan komputer sebelum dibentuk tabel rute

Jaringan komputer (simpul-simpul terminal komputer end user tidak digambarkan):

Lintasan terpendek yang dihasilkan dari algoritma Dijkstra (berdasarkan delai):

Hasil pembentukan tabel rute (berdasarkan hasil algoritam Dijkstra):

Gambar 2 : Contoh sebuah jaringan komputer dengan tabel rute pada setiap simpul

Contoh:

• Simpul asal: router 1
• Simpul tujuan: router 5

Lintasan yang dilalui oleh paket data (berdasarkan tabel rute):

Gambar 3 : Lintasan tersingkat yang dilalui oleh paket data dari router 1 ke router 5

Lampiran 2

Contoh graf untuk pengujian program:

• Graf jaringan pada Gambar 1 di Lampiran 1. 
• Graf jaringan pada Gambar 4 di Lampiran 2 (di bawah ini). 

Gambar 4: Contoh Graf 2 untuk pengujian

Sekian artikel Algoritma Dijkstra Adaptive Routing Pada Jaringan Komputer.