Analisa Routing Pada Jaringan Data Multi Jalur Menggunakan Metode Ant Colony Optimization (ACO)

Analisa Routing Pada Jaringan Data Multi Jalur Menggunakan Metode Ant Colony Optimization (ACO) Agus Kurniwanto1), Eko Setijadi1), Mauridhi Hery1) 1) Jurusan Teknik Elektro ITS, Surabaya 60111, email: kurn i wa nt o@ ya h oo. c om , ek os et @ ee. i t s. a c. i d , h er y@ e e. i t s. a c. i d

Abstrak – Protokol routing berperan pada jaring data multi jalur untuk pemilihan jalur paling optimal sehingga membantu proses pengiriman data dari sumber ke tujuan menjadi lebih efektif. Jalur yang tidak optimal akan mempengaruhi proses pengiriman data baik dari sisi waktu maupun kualitas penyampaian data. Pada penelitian ini mengusulkan metoda routing berbasis metahueristik yang berdasarkan algoritma Ant Colony Optimization, yaitu AntNet. Algoritma AntNet disimulasikan pada jaring data multi jalur dengan menggunakan program simulasi NS-2. Parameterparameter yang mempengaruhi kinerja routing seperti beban packet, ukuran bandwidth serta kondisi jalur dibuat bervariasi untuk mendapat hasil kinerjanya kemudian dibandingkan dengan algoritma routing lain, yaitu algoritma berbasis LinkState. Hasil dari pengujian dengan simulasi untuk kedua algoritma memberikan hasil bahwa dari sisi throughput, LinkState lebih baik dari AntNet dengan selisih sebesar 2,6% pada scenario jalur normal. Sedangkan pada scenario jalur terputus, AntNet lebih baik dari linkstate dengan selisih 3,5%. Untuk parameter delay, hasil pengujian menunjukkan LinksState lebih baik dengan perbedaaan sebesar 26,3% . Pengujian lain berupa routing overhead menunjukkan perbedaan cukup significant yaitu sebesar 96% untuk LinkState yang lebih baik. Kata Kunci: Routing, Throughput, Delay

AntNet,

LinkState,

1. PENDAHULUAN Sebuah jaring data adalah suatu sistem komunikasi terpadu dari beberapa perangkat pendukung yang saling terhubung melalui media transmisi dan berfungsi membantu beberapa pengguna (users) untuk saling berkomunikasi atau bertukar informasi atau data. Komunikasi data antara para pengguna, yang kemungkinan besar berada di area lokasi berbeda, dibantu oleh suatu perangkat penghubung (Router) yang berfungsi untuk meneruskan paket data dari pengguna sumber ke pengguna tujuan. Tentunya Router ini juga akan saling berkomunikasi antar sesamanya untuk bertukar informasi agar bisa bersama-sama saling menunjang dalam tugasnya

meneruskan paket-paket data secara cepat dan efisien. Komunikasi antar Router untuk bisa bersama-sama menjalankan pengiriman paket data di atur oleh protokol yang dinamakan protokol routing. Routing merupakan hal yang sangat penting dalam mengontrol komunikasi pada jaring data multi jalur. Proses routing awalnya akan membentuk sebuah tabel yang berisi informasi jalur-jalur yang bisa dilewati paket data. Dari informasi tersebut dipilih salah satu jalur terbaik yang kemudian akan digunakan sebagai jalur utama pengiriman data. Pemilihan jalur terbaik yang dilakukan protokol routing didasarkan pada jalur dengan tingkat performansi yang paling baik dibanding terhadap jalur yang tersedia lainnya. Tantangan yang ada pada jaring data multi jalur adalah membuat algoritma routing yang dapat mencari jalur terpendek dan efisien, terutama saat menghadapi perubahan topologi atau perubahan nilai (cost) pada jalur. Dalam hal ini perubahan topologi jaring bisa disebabkan antara lain karena adanya kenaikan atau penurunanan kapasitas bandwidth, perubahan kondisi beban data, dan kondisi saat terjadi kegagalan pada jalur utama. Untuk itu diperlukan kinerja protocol routing yang efisien dalam memberikan solusi jalur alternatif terbaik. Beberapa penelitian sebelumnya terkait optimasi routing tersebut dengan menggunakan metode Ant Colony telah dilakukan. Masalah-masalah pemilihan jalur terpendek dan terbaik seperti pada Travelling Salesman Problem dan Data Network Routing telah dicoba diselesaikan dengan metode Ant Colony. Referensi (Sosa, 2001) yang menggunakan metode Ant Colony, mencoba membandingkan metode routing metaheuristic dengan metode routing konvensional (RIP dan OSPF). Hasil perbandingan menunjukkan bahwa metode Ant Colony lebih baik dalam kecepatan penyampaian data (Throughput) walaupun dalam hal delay masih kurang bagus disbanding yang lain. Referensi (Ducatelle, 2005) yang menerapkan metode Ant Colony pada jaring data bergerak ad hoc dengan membandingan metode AntHoc-net dengan AODV, yang hasilnya masih belum memuaskan dalam hal round trip time (RTT) dan tingkat adaptifitas yang kurang baik bila ada pengaruh perubahan seperti perubahan bandwidth. Referensi Liang (2005), melakukan perbandingan antara metode Ant Colony dengan Genetic Algorthm

yang diimplementasikan pada model jaring data NTTNET Jepang. Skenario test berupa perubahan konfigurasi node jaring NTTNET dengan mencoba menonaktifkan beberapa router dan kemudian diaktifkan kembali, lalu kemudian dilihat kinerja adaptifitas dari kedua metode tersebut. Referensi (Yakoh, 2009) yang juga mengimplementasikan Ant Colony pada jaring PlanetLab dengan menfokuskan pada tipe pengiriman data UDP, menghasilkan pengurangan packet loss sampai dengan 10% dibanding metode konvensional algoritma Dijkstra. Penelitian lebih lanjut menggunakan metode AntColony pada permasalahan Traveeling Salesman Problem (Effendi, 2010) dengan mencoba membandingkannya dengan algoritma Cheapest Insertion Heuristic dengan memberikan hasil bahwa metode Ant Colony lebih bagus pada topologi jaring dengan skala besar. Penelitian ini mencoba untuk mengusulkan algoritma routing berbasis Ant Colony yaitu AntNet untuk mendapatkan jalur terbaik untuk pengiriman paket data di sebuah topologi jaring multi jalur sebanyak 14 node, dengan disertai juga perbandingan dengan metode konvensional lain yaitu Linkstate. Bentuk implementasi dan hasil akan digambarkan dengan menggunakan aplikasi network simulator agar lebih mudah untuk melakukan perubahan-perubahan parameter-paramater yang berhubungan dengan kinerja algoritma routing.

dua yaitu routing statik (static routing) dan routing dinamik (dynamic routing). Jaring dengan jumlah gateway terbatas biasanya menggunakan statik routing yang dibangun secara manual oleh administrator. Karena bersifat statik maka perubahan yang terjadi pada jaring harus diupdate secara manual ke dalam tabel routing yang ada. Apabila jaring memiliki lebih dari satu kemungkinan rute (multi jalur) dan memiliki beberapa router gateway seperti pada Gambar 2, maka perlu menggunakan routing dinamik. Sebuah routing dinamik dibangun berdasarkan informasi yang dikumpulkan oleh protokol routing, seperti informasi bandwidth, beban trafik, kondisi jaring, jalur alternatif, dan lainnya.

Gambar 2: Jaring data multi jalur

2. ROUTING PADA JARING DATA Sebuah jaring data terpadu gambar 1 adalah suatu sistem komunikasi terpadu antara beberapa pengguna (users) untuk saling berkomunikasi atau bertukar informasi. Dalam jaring data besar yang para penggunanya berbeda area lokasi geografis, maka komunikasi antar pengguna tersebut dibantu oleh perangkat penghubung (router) yang menjalankan proses routing antar sesama perangkat.

.

Gambar 1: Jaring data terpadu

Routing adalah proses pemilihan salah satu jalur terbaik dari kemungkinan beberapa jalur yang tersedia pada sebuah jaring data, kemudian jalur tersebut digunakan untuk pengiriman data traffik dari node sumber ke node tujuan. Secara keseluruhan routing sangat menentukan dalam performansi jaring yang berhubungan dengan kualitas layanan jaring yang ditawarkan. Secara umum mekanisme routing dapat dibedakan atas

Protokol routing didesain untuk mendistribusikan informasi yang secara dinamis mengikuti perubahan kondisi jaring. Protokol routing mengatasi situasi routing yang kompoleks secara cepat dan akurat. Protokol routing didesain tidak hanya untuk mengubah ke rute alternatif bila rute utama tidak berhasil, namun juga didesain untuk menentukan rute mana yang terbaik untuk mencapai tujuan Elemen penting dari routing terbagi sebagai berikut : 1. Algoritma, dalam hal ini ada beberapa algoritma routing yang tersedia dan telah banyak diterapkan pada protocol routing. Masing-masing algoritma memiliki karakteristik yang berbeda sehingga penerapannya dapat kita sesuaikan dengan kondisi jaring data yang kita miliki. 2. Database (Tabel Routing), dalam hal ini adalah database dari table routing yang ada pada router sebagai pedoman untuk router tersebut sebelum meneruskna paket data yang akan dikirimkan. 3. Protokol, dalam hal ini adalah sebuah cara berkomunikasi antar router untuk saling mengumpulkan, mendistribusikan, dan memperbaharui informasi routing masing-masing. Sebuah jalur data yang optimal mempunyai perspektif yang luas bergantung pada penggunaan jalur data tersebut sebagai media pengiriman data pada sebuah topologi jaring data. Umumnya jalur data yang optimal adalah memiliki karakteristik sebagai berikut : 1. Memiliki kapasitas atau ukuran bandwidth besar sehingga dapat mengirimkan paket data dalam ukuran besr pula. 2. Memiliki tingkat ketersediaan (availability) layanan yang tinggi, sehingga tidak

3.

menggangu proses pengiriman data. Secara fisik memiliki tingkat kesalahan (error rate) yang sangat rendah, sehingga paket dapat sampai ke tujuan dengan utuh.

Namun pada praktek kesehariannya, pemilihan dan penggunaan jalur optimal bergantung penuh pada seorang administrator jaring data. Pada saat melakukan rekayasa lalu-lintas data (Data Traffic Engineering), seorang administrator melakukan pengelompokan tipe-tipe data yang akan melewati suatu jaring data, dikelompokkan sesuai tingkat kepentingannya (Traffic Policy), kemudian disalurkan ke jalur data yang sesuai dengan kebutuhan model data tadi. Sehingga dapat disimpulkan bahwa, jalur data optimal merupakan jalur data yang paling efektif dari sisi penggunaannya untuk model data yang akan dilewatinya

Keterangan: 1) Graf dengan jarak D – H = H – B = 1, dan D – C = C – B = 0.5. E adalah sarang dan A adalah sumber makanan. 2) Pada saat t=0 belum terdapat jejak, semut memilih untuk bergerak kearah kiri atau kekanan dengan probabilitas 3) Pada saat t=1, jejak feromon lebih kuat pada jarak yang lebih pendek, sehingga lebih banyak semut memilih jalur tersebut untuk dilewati. Pada ant system dikenal istilah random propotional rule yang merupakan probabilitas dari semut pada node r yang menuju node s, dan hal ini dapat dituliskan sebagai berikut:

[ ( , )] . [ ( , )]

3. ALGORITMA ANT COLONY UNTUK OPTIMASI ROUTING Ant Colony Optimization (ACO) merupakan suatu metodologi yang dikemukakan pada tahun 1991 oleh Marco Dorigo. Tahun 1997, Dorigo dan Gambardella memperkenalkan Ant Colony System (ACS) (Refianti, 2005). Ant system telah diterapkan di banyak permasalahan optimisasi kombinatorial, sebagai contoh traveling salesman problem, quadratic assignment problem, jobscheduling, vehicle routing, graph coloring,network routing (Dorigo, 1999). Secara alamiah koloni semut mampu menemukan rute terpendek dalam perjalanan dari sarang ke tempattempat sumber makanan. Semut dapat bekerja sama dengan koloninya dan bertukar informasi secara tidak langsung yang disebut dengan stigmergy. Pada saat melakukan suatu rute perjalanan, semut meletakkan sejumlah informasi pada daerah yang dilaluinya yaitu feromon yang merupakan zat yang dikeluarkan oleh semut untuk mendeteksi dan merespon keberadaan dari semut Dengan feromon ini, semut menandai daerah yang dilaluinya. Semut berikut yang melalui jalur tersebut akan mengidentifikasikan feromon yang diletakkan oleh semut sebelumnya dan memutuskan dengan probabilitas yang tinggi untuk mengikutinya dan menguatkan jalur yang dipilihnya dengan feromon miliknya. Proses dari stigmergy ini dapat diilustrasikan seperti pada gambar 2.4

Gambar 3: Proses stigmergy agen semut

( , )=

∑ ( )[ ( , )].[ ( , )]

∈

( )

(1)

0

Dengan: τ = feromone μ = = merupakan visibilitas (invers dari jarak δ(r,s) ) δ(r,s) = kumpulan node yang dikunjungi semut k δ(r, s) = [(x − x ) + (y − y ) ]

(2)

Jk(r) = kumpulan node yang akan dikunjungi oleh semut k yang sedang berada pada node r β = parameter yang mengontrol bobot relatif dari feremon terhadaf jarak relatif (β >0). A. Algoritma AntNet Algoritma routing AntNet adalah system mobile agent yang merupakan pengembangan penelitian dari metode Ant Colony. AntNet tetap menggunakan metode komunikasi stigmergy yang merupakan ciri khas dari artificial ant colony dalam menyelesaikan permasalahan path routing yang adaptif pada jaring multi jalur. Pada AntNet, semut mengikuti proses yang iteratif, setiap semut membangun solusi dengan menggunakan dua tipe informasi lokal yaitu informasi kondisi jaring (seperti bandwith dan delay) dan informasi baru yang ditambah oleh semut selama iterasi algoritma sebelumnya. Ketika membangun solusi, setiap semut membangun informasi pada karakteristik permasalahan dan performansinya, yang kemudian menggunakan informasi ini untuk memodifikasi representasi masalah yang dilihat oleh semut lainnya. Representasi masalah yang dimodifikasi mengandung informasi solusi yang lebih baik pada masalah sebelumnya dan dapat dibangun solusi

baru yang lebih baik lagi.

Gambar 5: Agen semut Forward dan Backward

Gambar 4: Proses stigmergy agen semut

Pada Gambar 4 menunjukan struktur node yang digunakan oleh mobile agent di AntNet untuk contoh dari node dengan L (neighbors) dan jaring dengan N node. Tabel routing terbentuk dalam algoritma vector-distance, tapi masukannya adalah nilai-nilai probabilistic. Struktur yang berisi statistic mengenai trafik menggunakan role dari model yang adaptif untuk trafik kearah tujuan masing-masing. AntNet terbagi menjadi dua agen mobile yang homogen yang disebut dengan forward ant dan backward ant (Gambar 5). Agen tesebut memiliki sifat yang sama hanya saja berbeda penempatan situasi dan lingkungannya, sehingga mereka dapat menerima input yang berbeda dan menghasilkan output yang berbeda pula. Agoritma AntNet dapat dirangkum sebagai berikut: 1. Agen semut bergerak pada interval regular dan bersamaan dengan data trafik, dari tiap node – node sumber (s) menuju node tujuan (d). Agen yang bergerak dari sumber ke tujuan ini dinamakan forward ant dengan diwakili notasi →

2.

5.

6.

dengan i adalah identitas dari agen ant.

Setiap forward ant tersebut bisa disebut sebagai agen eksperimen acak yang bertujuan mengumpulkan informasi tentang jalur dan pola trafik data dari setiap hop yang dilaluinya sampai tiba di tujuan. Selama pergerakannya, agen ants merupakan agen bebas yang bergerak secara bersamaan dan tidak bergantung antara satu dengan yang lainnya. forward ant memilih rute berdasarkan probabilitas, P’nd, sebanding dengan table probabilitas routing dan banyaknya hubungan yang bersesuaian, ln

=

3.

4.

. (∣

∣

)

(3)

Setiap agen ants bergerak melewati beberapa node sampai ke node tujuan. Pada pertengahan node tiap agen membuat suatu keputusan probabilitas yaitu memilih node selanjutnya

untuk berpindah, dengan beberapa penilaian yaitu nilai variable pheromone, status dari jalur, dan informasi jalur yang telah dilewati (untuk menghindari loop). Selama perjalanan, agen ants mengumpulkan informasi waktu yang dijalani mulai dari awal bergerak dari node sumber, status kongesti atau loop dari jalur-jalur yang dilewati dan identifikasi node pada jalur yang telah dilewati. Identitas tiap node yang telah dikunjungi k dan waktu yang digunakan dari node sumber ke node k tersebut, dimasukkan ke memory stack S(s→d)(k) yang dibawa oleh forward ant. Ketika agen ants telah sampai di node tujuan, maka forward ant berubah menjadi backward ants → , memindahkan semua memori dari forward ant ke backward ant, dan kembali ke node sumber dengan bergerak ke jalur yang sama tetapi berlawanan arah. Selama perjalanan pulang, agen ants akan memperbaharui informasi routing pada setiap node, yaitu diantaranya informasi waktu perjalanan, table pheromone, dan table routing. Pembaharuan pheromone dan table routing berdasarkan pada kebaikan (goodness) dari jalur yang dilewati agent ants. Pada masing-masing node yang dikunjungi oleh backward ant, table probabilitas routing akan diupdate menngunakan aturan berikut

= 7.

. (∣

∣

)

(4)

Setelah table routing sudah terbaharui, maka paket data berikutnya akan berjalan dari sumber ke tujuan dengan jalur mengikuti table routing tersebut. 4.

SIMULASI DAN PEMBAHASAN

Pada pengujian ini dilakukan perbandingan kinerja algoritma routing Antnet dan LinkState yang diimplementasikan pada jaring data multi jalur. Pengujian kedua algoritma tersebut dengan cara melakukan simulasi menggunakan aplikasi simulasi jaring Network Simulator 2 (NS-2) ver. 2.34 yang dijalankan pada komputer dengan sistem operasi Linux Ubuntu 10.04. Model jarring data mulit jalur yang digunanakan adalah seperti pada Gambar 2. Proses komunikasi berlangsung antara Router A dan

Router B, dengan memberikan trafik paket yang bervariasi dan juga diuji dengan kapasitas bandwidth yang berbeda. 128Kbps dan 512Kbps.. A. Skenario 1 Pada pengujian pertama, diuji dengan menggunakan paket CBR (constant Bit Rate) pada kapasitas bandwidth 128Kbps. Hasil yang diberikan seperti pada Table 1 dan Gambar 6 dan 7. Hasil perbandingan tersebut menunjukkan bahwa tingkat keseksesan pengiriman packet data antara kedua algoritma adalah sama baiknya berkisar pada nilai 99%. Kemudian juga dihasilkan pengujian nilai Throughput, yaitu nilai aktual kecepatan pengiriman data dari sumber ke tujuan. Hasil perbandingan menunjukkan bahwa nilai throughput dari algoritma LinkState sedikit lebih baik dibandingkan dengan algoritma AntNet, dengan presentase selisih perbandingan sebesar 2.6%.

B. Skenario 2 Pada pengujian kedua, juga diuji dengan menggunakan paket CBR (constant Bit Rate) pada kapasitas bandwidth 512Kbps. Hasil yang diberikan seperti pada Table 2 dan Gambar 8 dan 9. Hasil pengujian tersebut menunjukkan bahwa tingkat keseksesan pengiriman packet masih tetap sama besar antara kedua algoritma, yaitu sama baiknya berkisar pada nilai 99%. Hasil perbandingan nilai throughput menunjukkan bahwa algoritma LinkState sedikit lebih baik dibandingkan dengan algoritma AntNet, dengan presentase selisih perbandingan sebesar 2.6%. Tabel 2: Hasil pengujian dengan bandwidth 512kbps

Tabel 1: Hasil pengujian dengan bandwidth 128kbps

Gambar 8: Hasil pengujian nilai Throughput

Gambar 6: Hasil pengujian nilai Throughput

Gambar 9: Hasil pengujian nilai Packet Delivery Ratio

Gambar 7: Hasil pengujian nilai Packet Delivery Ratio

4. KESIMPULAN Berdasarkan pengamatan dan analisa data hasil penelitian, maka sebagai hasil penelitian ini dapat dibuat beberapa kesimpulan sebagai berikut : 1. Dari nilai throughput paket dan delay paket dan dibandingkan kinerjanya dengan algoritma konvensional LinkState, Algortima AntNet yang berbasis metaheuristic dapat digunakan sebagai protokol routing pada jaring data multi jalur. 2. Hasil dari pengujian dengan simulasi untuk kedua algoritma memberikan hasil bahwa dari sisi throughput, LinkState lebih baik dari AntNet dengan selisih sebesar 2,6% pada bandwidth 128Kbps dan selisih sebesar 1,3 pada bandwidth 512Kbps 3. Dari hasil pengujian pada Packet delivery Ratio, kedua algoritma menunjukkan kinerja yang sangat baik dengan memberikan kemampuan pengiriman rata-rata sebesar 99% . DAFTAR REFERENSI [1] Baran, B., Sosa, r.(2001), AntNet: Routing algorithm for data networks based on mobile agents. Inteligencia Artificial, Revista Iberoamericana de Inteligencia Artificial, 3(12):75-84 [2] Distad Chirnanthavat (2009) ,Takahiro Yakoh, Hybrid Multipath Routing for Packet Distribution using Ant Colony Optimization, The 6th International Conference on Information Technology and Applications (ICITA) [3] Gianni Di Caro (2004), Ant Colony Optimization and its Application toAdaptive Routing in Telecommunication Networks, Dissertation pr´esent´ee en vue de l'obtention du grade deDocteur en Sciences Appliqu´ees, Bruxelles. [4] Kanyapat Watcharasitthiwat (2009), Paramote Wardkein, Reliability optimization of topology communication network designusing an improved ant colony optimization, Elsevier Journal [5] Marco DorigoThomas Stutzle, Ant Colony Optimization, A Bradford Book The MIT Press Cambridge, Massachusetts London, England. [6] Nader F Mir, 2006, Computer and Communication Networks, Prentice Hall, [7] S. Liang, A.N. Zincir-Heywood, M.I. Heywood (2005), Adding more intelligence to the uting problem: AntNet and Ga-agents, NIMS Group, Faculty of Computer Science, Dalhousie University, 6050 University Avenue, Halifax, NS, Canada B3H 1W5 [8] Vincent Verstraete, Matthias Strobbe, Erik

Van Breusegem, Jan Coppens, Mario Pickavet, Piet Demeester (2005), AntNet: ACO routing algorithm in practice, Ghent University IBBT - IMEC, Department of Information Technology,Gaston Crommenlaan 8 bus 201, 9050 Gent, Belgium

[9]

Teerawat

Issariyakul, Ekram Hossain , Introduction to Network Simulator NS2, Department of Electrical Computer Engineering University of Manitoba 75A Chancellor’s Circle Winnipeg MB R3T 5V6 Canada, 2009