OPTIMASI WAKTU TUNDA MENGGUNAKAN SWARM INTELLIGENCE UNTUK PENGIRIMAN PAKET DATA PADA JARINGAN TELEKOMUNIKASI DENGAN ALGORITMA BEEHIVE Rangga Permana Putra, Nurlita Gamayanti, Abdullah Alkaff Jurusan Teknik Elektro – FTI, Institut Teknologi Sepuluh Nopember Kampus ITS, Keputih – Sukolilo, Surabaya – 60111
didesain untuk menentukan rute mana yang terbaik untuk mencapai tujuan tersebut. Dalam jaringan, routing berarti kegiatan pemilihan salah satu jalur yang ada dari kemungkinan jalur yang tersedia untuk pengiriman data traffik dari node sumber ke node tujuan, secara keseluruhan routing sangat menentukan dalam performansi jaringan yang berhubungan dengan kualitas dan jumlah layanan jaringan yang ditawarkan. Pada umumnya, algoritma routing untuk pengiriman traffik data dalam jaringan dilakukan dengan meminimalkan beberapa fungsi biaya berupa waktu tunda yang terdiri dari delay propagasi, delay transmisi dan delay antrian sehingga dapat memaksimalkan trouhgput. Metode-metode optimasi dengan menggunakan algoritma-algoritma yang ada telah dilakukan untuk meningkatkan kinerja jaringan. Metode yang umumnya dipakai saat ini yaitu Routing Information Protocol (RIP) dan Open Shortest Path First (OSPF). Kedua contoh algoritma dasar yang digunakan oleh RIP maupun OSPF kinerjanya memang cukup baik, tetapi dalam penerapan masing-masing algoritma tersebut masih terdapat beberapa kelemahan. Sebagai contoh RIP (Routing Information Protokol) misalnya, algoritma dasarnya menggunakan metode distance-vektor, kekurangan utama pada algoritma routing ini yaitu kinerjanya yang sangat sederhana dan lambat dalam mengetahui perubahan kondisi jaringan. OSPF (Open Shortest Path First) algoritma yang sepenuhnya digunakan di internet, menggunakan metode link state. Algoritma ini sangatlah kompleks, setiap router yang menjalankan OSPF menyimpan peta jaringan dan menghitung jarak terpendek ke semua tujuan di jaringan berdasarkan peta tersebut, walaupun kinerja algoritma ini agak lebih baik dari RIP namun kelemahan algoritma ini terletak pada resource (perangkat keras) yang dibutuhkan. Dalam penggunaan algoritma ini, ketika topologi jaringan semakin besar maka akan membutuhkan routing table yang besar, sehingga membutuhkan kemampuan CPU yang tinggi dan memori yang besar. Dalam pengembangan algoritma routing, banyak penelitian dilakukan untuk mengatasi kekurangan dan kelemahan algoritma yang umumnya dipakai saat ini. Dalam penulisan Tugas Akhir ini algoritma BeeHive ditawarkan sebagai solusi untuk tujuan optimasi routing. BeeHive merupakan algoritma routing yang terinspirasi dari cara dan perilaku lebah madu dalam mencari makan dengan mengestimasi jarak, mempertimbangkan kualitas makanan serta mengevaluasi cara kerja koloni.
Internet sudah menjadi kebutuhan masyarakat dan pengguna terus meningkat. Semakin banyak pengguna internet berakibat semakin padat lalu lintas pada media transmisi pengiriman paket. Salah satu penyebab lambatnya koneksi internet, dapat dikarenakan metode routing yang umum digunakan pada saat ini cenderung lambat dalam mengetahui perubahan kondisi jaringan. Routing merupakan aktivitas yang menuntun perjalanan informasi data dengan menentukan rute perjalanan dari sumber asal ke titik tujuan berdasarkan informasi yang terkandung dalam routing table. Pada Tugas Akhir ini penelitian dilakukan dengan mengimplementasikan Algoritma BeeHive untuk mengoptimalkan waktu tunda sehingga dapat memaksimalkan throughput. BeeHive merupakan Algoritma yang mempertimbangkan delay antrian dalam pengambilan keputusan pembagian jalur distribusi. Cara kerja BeeHive terinspirasi perilaku lebah dalam mencari makan dengan menjelajah lokasi makanan kemudian mengkomunikasikan pada lebah lain yang berada di sarang lebah dengan menggunakan tarian kibasan untuk mengestimasi jarak dan mempertimbangkan kualitas makanan, sehingga pada proses memilih jalur algoritma BeeHive melakukan update kualitas jaringan sebagai pertimbangan dalam membagi jalur yang akan dilewati untuk mendistribusikan paket. Hasil percobaan menunjukkan BeeHive mampu mengoptimalkan waktu tunda pada kondisi lalu lintas dengan tingkat kepadatan tinggi ataupun tingkat kepadatan rendah sehingga BeeHive dapat memaksimalkan throughput. Kata Kunci: Routing , Waktu Tunda, Algoritma BeeHive
I
I. PENDAHULUAN
nternet sudah menjadi kebutuhan masyarakat sehingga, pengguna akan terus meningkat. Semakin banyak pengguna internet berakibat semakin padat lalu lintas pada media transmisi pengiriman paket. Salah satu penyebab lambatnya koneksi internet, dapat dikarenakan metode routing yang umum digunakan pada saat ini cenderung lambat dalam mengetahui perubahan kondisi jaringan. Routing merupakan hal yang sangat penting dalam kontrol jaringan komunikasi. Routing sendiri merupakan pelaksanaan dari penyampaian datagram berdasarkan informasi yang terkandung dalam routing table. Protokol routing mengatasi situasi routing yang kompoleks secara cepat dan akurat. Algoritma routing didesain tidak hanya untuk mengubah ke rute bila rute utama tidak berhasil, namun juga
1
5. Ukuran table routing dari BeeHive harus sama seperti OSPF. 6. BeeHive harus mampu digunakan dalam topologi jaringan yang besar. 7. BeeHive harus sanggup mengatasi kegagalan pada router/link dari suatu jaringan. 8. Performa BeeHive harus lebih bagus dibanding dengan algoritma AntNet pada saat tingkat kepadatan lalu lintas jaringan tinggi dan lebih baik dari OSPF pada saat tingkat kepadatan lalu lintas jaringan rendah. Dalam pembuatan simulasi algoritma BeeHive, lebah madu dimodelkan dengan dirancang sebagai agen lebah cerdas, yang mampu membuat keputusan routing dalam skala besar dan topologi yang kompleks [1]. Agen lebah ini yang nantinya akan mengirim paket data serta mengupdate informasi dari setiap node pada jaringan yang ada. Algoritma ini membutuhkan dua jenis agen lebah yaitu agen lebah jarak pendek dan agen lebah jarak panjang. Topologi jaringan dalam algoritma BeeHive dibagi-bagi menjadi beberapa bagian yang dinamakan foraging region. Batas paling luar dari foraging region dinamakan foraging zone. Langkah-langkah dari pembentukan sampai proses kerja algoritma BeeHive dapat dijabarkan sebagai berikut; 1. Langkah awal dimulai dari pembentukan foraging region. Dengan mengirimkan agen lebah generasi pertama dari tiaptiap node yang ada. Agen lebah dikirimkan ke node tetangga sekitar mereka, yang berisi IP masing-masing node pengirim. 2. Tahap pembentukan node representatif. Node representatif adalah node yang memiliki IP terkecil yang diketahui dari hasil pengiriman agen lebah generasi pertama. 3. Node nonrepresentatif mengirimkan agen jarak pendek ke node tetangga untuk meng-update routing table pada masing-masing node. Node representatif meng-update informasi semua node dengan cara mengirimkan agen jarak panjang ke tiap2 node representatif lainnya. Pengriman paket data dilakukan dengan cara melewati arc menuju node representatif dari foraging region node sumber, kemudian dilanjutkan dikirim ke node representatif foraging region node tujuan. Setelah dari node representaif tujuan, paket data dikirim ke node tujuan.
II. TINJAUAN PUSTAKA A. Swarm Intelligence Swarm Intelligence dapat diartikan sebagai kumpulan atau kelompok agen yang saling bekerja sama dengan pola perilaku tertentu untuk mencapai tujuan dari sistem. Swarm Intelligence dapat dianggap sebagai cabang dari Artifisicial Intelligence yang umumnya terinspirasi dari cara perilaku sosial serangga dalam berkomunikasi. Dari sudut pandang komputasi, pemodelan Swarm Intelligence adalah algoritma komputasi yang berguna sebagai solusi optimasi dalam memecahkan masalah distribusi. Prinsip dasar dari Swarm Intelligence adalah probabilitas dari algoritma pencarian[2]. Kerja sama antar agen diwujudkan dengan cara didistribusikan tanpa mekanisme control terpusat. B. AntNet. AntNet adalah algoritma pembuatan rute yang digunakan pada jaringan datagram berkabel berdasarkan pada prinsip Ant Colony Optimization (ACO). Namun AntNet paling mirip dekat dengan perilaku semut dalam menginspirasi pembuatan ACO heuristics ini daripada algoritma ACO. Pada AntNet, tiap node menjaga routing table dan tabel tambahan yang berisi statistik mengenai keadaan disribusi lalu lintas pada suatu jaringan. Routing table menjaga untuk tiap tujuan dan untuk tiap ukuran kebijakan untuk pemilihan next hops berdasarkan probabilitasnya yang digunakan untuk mengalirkan paket data menuju tujuan. Kebijakan yang diukur ini adalah variabel feromon. C. BeeHive Algoritma BeeHive merupakan metode routing yang terinspirasi dari cara dan perilaku lebah dalam mencari makan. Lebah mengkoordinasikan kegiatan mencari makan mereka sebagai usaha sosial dan komunikatif [3]. Prinsip kerja lebah yaitu dengan mengestimasi jarak, mempertimbangkan kualitas makanan serta mengevaluasi cara kerja koloni. Cara kerja lebah madu dalam mencari makan diawali dengan survei tempat makanan oleh lebah penjelajah. Kemudian lebah penjelajah kembali ke sarang untuk mengkomunikasikan hasil survei makanan yang berupa arah dan estimasi jarak lokasi makanan dengan cara yang unik, yaitu melalui tarian yang dinamakan waggle dance dan round dance. Lebah pengamat (scout bee) akan mengamati nektar yang dibawa oleh lebah penjelajah dengan mempertimbangkan jarak, kualitas, dan proses waktu dalam mengumpulkan nektar. Selanjutnya scout bee akan mengeksplor tempat mencari makan tersebut, yang cenderung memilih tempat terdekat sebagai tempat yang menguntungkan koloninya. Dari pengamatan prinsip kerja lebah madu maka ditentukan syarat-syarat dari algoritma BeeHive berupa; 1. BeeHive hanya akan menggunakan agen gerak forward saja untuk menyelesaikan routing. 2. Proposi dari bee agent harus tidak boleh lebih 1% dari bandwidth. 3. Algoritma tidak harus mempertahankan setiap statistik variabel untuk menghitung kualitas link. 4. Waktu yang digunakan untuk proses bee agent harus dijaga seminimum mungkin.
III. PERANCANGAN SISTEM A. Pembentukan Agen Algoritma BeeHive terdiri dari dua jenis agen yaitu agen jarak pendek dan agen jarak panjang. Kedua melaksanakan tanggung jawab yang sama: menjelajahi jaringan dan mengevaluasi kualitas jalan yang mereka melintasi. Namun, agen lebah jarak pendek hanya diperbolehkan untuk mengambil lompatan sebesar 17 hops mulai dari router dimana mereka diciptakan. Sementara agen jarak panjang bertugas mengumpulkan dan menyebarkan informasi routing ke semua jaringan dengan lompatan 30 hops. Langkah kerja algoritma BeeHive dijelaskan sebagai berikut: 1. Membentukan foraging region dengan cara mengirimkan generasi agen lebah pertama dari tiap-tiap node yang ada kemudian agen lebah dikirimkan ke node tetangga sekitar mereka berisi IP masing-masing node pengirim. 2
2. Tahap pembentukan node representatif. Node representatif adalah node yang memiliki IP terkecil yang diketahui dari hasil pengiriman agen lebah generasi pertama. 3. Saat setiap agen melakukan perjalanan, mereka mengumpulkan, membawa informasi jalur, dan menyebarkannya, di setiap node yang dikunjungi. Dengan estimasi waktu perjalanan sebagai berikut
tis qin
txin
p kd q kd
B. Perhitungan Time Delay Dalam menghitung time delay, perhitungan dilakukkan dengan menjumlahkan delay-delay yang ada pada tiap node dan tiap link yang telah dilewati pada saat pengiriman paket dengan menggunakan persamaan.
qlin txin pd in t ns bin
ql in tx in pd in bin ql qin in merupakan delay antrian bin
t in
qlin merupakan delay antrian. bin
= delay propagasi.
txin
pd in = delay transmisi.
t ns
Dimana
4. Node nonrepresentatif mengirimkan agen jarak pendek ke node tetangga untuk mempebaruhi informasi kualitas jalan pada routing table pada masing-masing node. Node representatif mempebaruhi informasi kualitas jalan semua node pada jaringan. 5. Ketika sudah mencapai node tujuan, maka agen lebah akan dimusnahkan supaya tidak memenuhi antrian pada buffer yang terdapat didalam router. 6. Dalam BeeHive, jaringan dibagi menjadi foraging zones dan foraging regions. Foraging zone didefinisikan sebagai node dengan wilayah di bagian tepi foraging region. Foraging region yaitu wilayah kumpulan dari beberapa node yang terletak di sekitar node nonrepresentatif. Foraging region memiliki representative node, yang adalah IP addres terendah di wilayah tersebut. 7. Pengriman paket data dilakukan dengan cara melewati arc menuju node representatif dari foraging region node sumber, kemudian dilanjutkan dikirim ke node representatif foraging region node tujuan. Dari node representatif foraging region tujuan akan diteruskan menuju node tujuan 8. Paket data akan dikirim dengan petunjuk dari routing table yang sudah disediakan agen lebah dan akan diperbaruhi secara terus menerus. 9. Untuk hop berikutnya data paket memilih jalur yang akan dilewati secara stokastik menurut ukuran kualitas dari node tetangga. Dengan petunjuk dari delay propagasi dan delay antrian dalam routing table.
tin
time delay dari node i ke node s. Setelah
perhitungan dilakukan pada masing-masing link dan node pada jalur yang telah dilewati, delay-delay pada paket dari semua node tujuan dijumlahkan sehingga terkumpul nilai time delay dari sistem. C. Gambar Rancangan Parameter Masukan Router Topologi
Kapasitas buffer, Topology
MSIA Panjang Sesi Ukuran Paket
Penghasil Tingkat Kepadatan pada Jaringan
Calon Algoritma
Kerangka Kerja
g jd
1 p jd q jd n 1 k 1 ( p q ) kd jd
No. 1. 2. 3. 4. 5.
g jd = bobot yang digunakan sebagai pertimbangan dalam p jd
= delay propagasi.
pd in = delay transmisi.
= lama perjalanan paket dari n ke s.
g jd
delay propagasi dari banyaknya gate pada router = delay antrian dari banyaknya gate pada router =
6. 7.
pemilihan rute paket. (mencari kualitas tetangga terbaik) = delay propagasi dari node j ke node d.
Hasil Keluaran
Parameter Hasil (Throughput, Delay)
1 p jd q jd n 1 k 1 ( p q ) kd jd
Parameter Jumlah Node Periode Simulasi Periode Training Ukuran Paket Data Interval Pembuatan Paket Session Size Kapasitas buffer
AntNet 66 500 50 1 MB 0,005 s
BeeHive 66 500 30 1 MB 0,005 s
50 Mb 1000 paket
50 Mb 1000 paket
Topologi berisi parameter masukan dari calon algoritma yang akan digunakan. Berupa delay propagasi dan kapasitas dari buffer router. Dalam perancangan parameter masukkan
q jd = delay antrian dari node j ke node d. 3
dari delay propagasi bernilai tetap, sebesar 0.001 ms dan kapasitas buffer sebesar 1000 paket. Parameter pendukung penghasil tingkat kepadatan jaringan berupa MSIA (mean session inter-arrival times), panjang sesi, ukuran paket. MSIA memiliki pengertian waktu yang diperlukan untuk melakukan satu sesi pengiriman. Panjang sesi yaitu kapasitas bit dikirim dalam satu sesi, dalam percobaan ini satu sesi router diharuskan mengirim sebesar 50 Mb. Ukuran paket dapat diartikan panjang paket yang bisa ditransmisikan oleh tiap router. Kerangka kerja berisi cara kerja agen dalam member info kapasitas jaringan dan juga menentukan probabilitas jalur yang akan digunakan dalam mendistribusikan paket data. Sehingga ketika semua elemen pendukung antara topologi, penghasil kepadatan jaringan dan kerangka kerja sudah saling berinteraksi maka akan menjadi calon dari algoritma.
yaitu waktu pengiriman selama satu sesi dan variasi MSIA yang digunakan yaitu MSIA 0.2, 0.5, 0.7, 0.9, 1.3, 1.5, 1.7, 2, dan 2.5. Jadi semisal MSIA 0.2 maka satu sesi pengiriman diharuskan terjadi dalam 0.2 s, sehingga dalam 1 s bisa terjadi sampai 5 kali pengiriman.
Gambar 4.1: Perbandingan delay packet Algoritma BeeHive dan AntNet
IV. IMPLEMETASI DAN PENGUJIAN SISTEM
Dari grafik gambar 4.2 dapat dilihat, untuk MSIA 0.2 s. Sistem menghasilkan paket sebesar 1.155.000 paket data dengan ukuran sebesar 9.240.000 Mb selama periode simulasi yaitu 500s. Dengan tingkat kepadatan yang sangat tinggi pada MSIA 0.2 Algoritma BeeHive mampu menghasilkan throughput lebih baik yaitu 14.231 Mbps daripada Algoritma AntNet yang menghasilkan throughput 13.104 Mbps. Untuk MSIA 0.9 berarti satu sesi pengiriman harus dilakukan dengan waktu 0.9 s, dalam kondisi ini lalu lintas paket dapat dikatakan cukup padat dengan menghasilkan paket sebesar 256.872 paket data yang berukuran sebesar 2.054.976 Mb. Throughput dari Algoritma BeeHive sebesar 3.684 Mbps lebih bagus 4 Mbps jika dibandingkan dengan troughput yang dihasilkan Algoritma AntNet sebesar 3.680 Mbps.
Simulasi dilakukan pada topologi jaringan dengan 66 node, beban jalur meliputi delay propagasi dengan nilai tetap yaitu 10 ms dan kapasitas bandwidth tiap jalur bergantung pada bahan dari media transmisinya, yaitu fiber optik. Fiber optic yang digunakan memiliki kapasitas bandwidth sebesar 1 Gbps dan 10 Gbps. Pada Tugas Akhir ini akan digunakan dua algoritma yang sama-sama menggunakan swarm intelligence antara AntNet dan BeeHive. Pada implementasi algoritma AntNet dan BeeHive, periode simulasi (PS) terdiri dari periode training (PT) dan periode pengujian (PP). AntNet akan menggunakan PS ditentukan selama 500 s. PT ditentukan selama 50 s. Sedangkan BeeHive akan menggunakan (PS) selama 500s dengn (PT) sebesar 30 s. Tiap titik menghasilkan paket dengan interval time 0.005 s. Jumlah total paket data yang dikirim bervariasi sesuai dengan nilai MSIA (mean of session interarrival times) pada parameter. Untuk beban lalu lintas dengan tingkat kepadatan sangat tinggi ditentukan nilai MSIA = 0.2, sedangkan untuk beban kepadatan lalu lintas relatif rendah nilai diatur dengan MSIA sebesar 2.5.
Tabel 4.2 Hasil Perbandingan running simulasi Algoritma AntNet dan BeeHive. MSIA Throughput (Mbps) Delay Packet (s) AntNet BeeHive AntNet BeeHive 0.2 13104 14087 1.427 1.22069 0.5 6622 6626 0.193 0.13104 0.7 4732 4732 0.191 0.14194 0.9 3680 3684 0.192 0.13463 1.3 2549 2550 0.196 0.13441 1.5 2204 2213 0.196 0.12710 1.7 1945 1952 0.202 0.13123 2 1654 1656 0.202 0.12822 2.5 1323 1325 0.202 0.12615
Gambar 4.1: Perbandingan Throughput Algoritma BeeHive dan AntNet
Untuk MSIA 0.2, delay packet sangat tinggi. Lintasan yang sangat padat mengakibatkan besarnya delay antrian pada paket sehingga sangat berpengaruh pada time delay yang dihasilkan. Dalam percobaan dengan MSIA 0.2 time delay yang dihasilkan Algoritma BeeHive sebesar 1.22069 s. Time delay ini adalah hasil time delay dari semua router tiap detiknya.
Gambar 4.1 adalah grafik hasil simulasi perbandingan throughput antara kedua algoritma dalam waktu 500 s simulasi, dengan balok warna biru sebagai hasil throughput dari AntNet dan merah sebagai hasil throughput dari BeeHive. Definisi dari throughput adalah jumlah paket terkirim (bit) tiap satu second. Untuk kepadatan lalu lintas digunakan percobaan menggunakan MSIA (mean of session inter-arrival times)
V. KESIMPULAN Pada jaringan yang sangat padat MSIA 0.2 Algoritma BeeHive dapat mengoptimalkan throughput 14.087 Mb 4
dengan waktu tunda sebesar 1,22 s dimana sistem terdiri dari 66 router dengan tingkat kepadatan sangat tinggi yaitu selama 0.2 s tiap router diharuskaan mengirimkan satu sesi pengiriman data sebesar 50 Mb dan ukuran paket 8Mb. Dengan membuat agen yang berukuran sangat kecil yaitu 484 bit, algoritma BeeHive mampu memperbarui informasi update kualitas jaringan tanpa mengganggu tingkat kepadatan lalu lintas pengiriman paket data. Bekerja dengan menggunakan dua agen sebagi agen fordward saja dan langsung memberikan informasi pada routing table membuat algoritma BeeHive mampu memilih jalur dengan probabilitas pemilihan rute sangat baik tanpa harus menunggu agen backward seperti pada AntNet.
RIWAYAT PENULIS
Rangga Permana Putra lahir bulan Desember 1988 di Surabaya Jawa Timur, merupakan putra dari pasangan Suparno dan Lilik Ekowarni. Menamatkan pendidikan dasar di SD Negeri Bulak Banteng I Surabaya dan melanjutkan ke SMP Negeri 7 Surabaya Jawa Timur hingga lulus pada tahun 2004. Pada tahun 2007 menamatkan pendidikan dari SMA Negeri 1 Surabaya dan melanjutkan ke jenjang strata 1 di Jurusan Teknik Elektro, FTI-ITS dan pada tahun 2011 mengikuti seminar dan ujian lisan Tugas Akhir di bidang Teknik Sistem Pengaturan, Jurusan Teknik Elektro, FTI-ITS.
DAFTAR PUSTAKA [1] M. Farooq, From the Wisdom of the Hive to IntelligentRouting in Telecommunication Networks.2006. Dissertation. [2] Zengin, A., Sarjoughian H. dan Ekiz, H. . Discrete event modeling of swarm intelligence based routing in network systems.2008. Journal of Operation Research [3] M. Farooq, Bee-Inspired Protocol Engineering, From Nature to Networks, Springer, 2009. [4] Horst, F., M., Farooq dan Y., Zhang. BeeHive : An Efficient Fault-Tolerant Routing Algorithm Inspired by Honey Bee Behavior.2004. Journal of systems architecture. [5] Dorigo, M., & Stutzle, T. (2004). Ant Colony Optimization. Massachusets Institute Technology. [6] Horst F. Wedde, Muddassar Farooq, Alexander Harsch, Bee inspired linux routing framework: a step from swarm intelligence to natural engineering. Technical Report 803, University of Dortmund, October 2005. [7] Albert Y. Zomaya, Stephan Olariu (Eds.), Handbook of Bioinspired Algorithms and Applications, Chapman & Hall/CRC Computer and Information Science, 2005G. 6. [8] Y. Zhang, Design and implementation of bee agents based algorithm for routing in high speed, adaptive and fault-tolerant networks. Master thesis, LSIII, The University of Dortmund, Germany, 2004. [9] Horst F. Wedde, Muddassar Farooq, A comprehensive review of nature inspired routing algorithms for fixed telecommunication networks,The University of Dortmund, Germany, 2006 [10] Horst F. Wedde, Muddassar Farooq, BeeHive: New ideas for developing routing algorithms inspired by honey bee, University of Dortmund, 2005. [11] Raharjo, B. (2009). Pemrograman C++. Bandung: Informatika. [12] Vargas, A., & Ltd, O. (2010). OMNET++ User Manual. www.omnetpp.org. [13] Vargas, A., & Ltd., O. (2010). OMNET++ Installation Guide. www.omnetpp.org.
5
