Tesis
OPTIMASI ROUTING PADA JARING DATA MULTI JALUR MENGGUNAKAN METODE ANT COLONY OPTIMIZATION (ACO)
Nama NIM
: Agus Kurniwanto : 2209206803
PROGRAM STUDI MAGISTER BIDANG KEAHLIAN TELEMATIKA JURUSAN TEKNIK ELEKTRO FAKULTAS TEKNOLOGI INDUSTRI INSTITUT TEKNOLOGI SEPULUH NOPEMBER SURABAYA 2012
2
Latar Belakang • Routing pada jaring data adalah sebuah mekanisme penyampaian trafik data dari sumber ke tujuan. Protokol Routing melakukan pemilihan jalur terbaik antara sumber ke tujuan pada topologi multi jalur • Salah satu tantangan yang ada terkait kinerja routing di sebuah topologi jaring multi jalur adalah pemilihan jalur yang paling optimal saat proses pengiriman data dari sumber ke tujuan. • Pada tesis ini akan dilakukan penelitian terhadap algoritma routing berbasis Ant Colony, yaitu AntNet yang diterapkan pada sebuah jaring multi jalur. • Dari penelitian ini diharapkan dapat melihat sampai sejauh mana algoritma AntNet dapat melakukan pemilihan jalur yang paling optimal bila diterapkan pada jaring multi jalur.
3
Perumusan Masalah Beberapa masalah yang akan dipecahkan terkait optimasi routing atau dalam hal ini pemilihan jalur terbaik adalah : 1. Bagaimana algoritma routing AntNet dapat mengoptimalkan pemilihan jalur terbaik pada jaring data multi jalur. 2. Akan dilakukan perbandingan kinerja (performansi), yaitu antara algoritma AntNet dengan algoritma LinksState untuk mendapatkan nilai Throughput dan Packet delay yang terbaik.
4
Tujuan Penelitian • Sesuai dengan pokok bahasan, pada penelitian ini akan didesain dan dilakukan pengujian penggunaan algoritma routing AntNet pada jaring data multi jalur dengan tujuan untuk mendapatkan jalur terbaik paling optimal dalam proses pengiriman data. •Tercapainya tujuan penelitian ini diharapkan dapat memberikan manfaat untuk penerapan metoda yang sama pada model topologi jaring yang berbeda lainnya.
5
Batasan Masalah • Untuk proses implementasi, analisa dan perbandingan algoritma routing AntNet dan algoritma pembanding (LinkState) akan digunakan aplikasi network Simulator NS-2. •Topologi jaring yang akan digunakan untuk pengujian routing tersebut menggunakan topologi jaring data PT.CPI yang mempunyai 14 node yang saling terhubung multi jalur. •Parameter-parameter yang mempengaruhi kinerja protokol routing (bandwith, load, dan jumlah node) juga akan disesuaikan dengan kondisi atau status yang ada di PT.CPI dengan disertai beberapa variasi ukuran. •Hasil keluaran yang akan diukur dan dianalisa dari implementasi antara lain adalah nilai Throughput dan Packet delay. 6
Penelitian Sebelumnya Beberapa penelitian sebelumnya yang mencoba menggunakan algoritma AntNet dan juga membandingkan dengan algortima lain adalah sebagai berikut: • Distad Chirnanthavat & Takahiro Yakoh, mengunakan algoritma Ant Colony pada jaring multi jalur, yang memperkenalkan mekanisme pencarian jalur terbaik berdasarkan perhitungan RTT (Round Trip Time) dan pengukuran bandwidth. • Baran, B., Sosa, yang mencoba membandingkan kinerja algoritma AntNet dengan algoritma routing OSPF dan RIP pada jaring data multi jalur.Parameter yang diukur adalah nilai Troughput dan Delay Packet.
7
8
Jaring Data Multi Jalur Jaring Data Multi Jalur adalah suatu topologi jaring data yang terdiri dari beberapa perangkat router yang antara satu dengan sama lain dihubungkan oleh beberapa jalur dan berfungsi sebagai sarana penyaluran trafik data dari sumber ke tujuan. Kelebihan : 1. Tersedia beberapa alternatif jalur untuk komunikasi antar router atau users tingkat ketersediaan layanannya tinggi. Tantangan: 1. Kinerja routing yang efektif dan optimal sehingga dapat : • Dapat melayani lalu-lintas data setiap saat dengan efisien dan optimal (waktu cepat, no delay, no error) • Dengan sendirinya dapat memilih jalur yang terbaik dan optimal • Kemampuan recovery yang cepat saat terjadi gangguan 9
Protokol Routing Routing adalah inti dari semua kontrol jaring, yaitu mekanisme yang digunakan untuk mengirimkan paket serta mengarahkan dan menentukan jalur yang akan dilewati paket dari sumber ke tujuan. Inti dari fungsi routing adalah Fungsi protokol routing adalah: • Diistribusi informasi lalu lintas pemakai dan status kondisi jaring. • Penggunaan informasi tersebut untuk membangkitkan kemungkinan rute – rute yang paling optimal untuk dilewati. • Meneruskan lalu lintas trafik data pengguna ke rute – rute optimal tersebut.
10
Protokol Routing Routing adalah inti dari semua kontrol jaring, yaitu mekanisme yang digunakan untuk mengirimkan paket serta mengarahkan dan menentukan jalur yang akan dilewati paket dari sumber ke tujuan. Inti dari fungsi routing adalah Fungsi protokol routing adalah: • Diistribusi informasi lalu lintas pemakai dan status kondisi jaring. • Penggunaan informasi tersebut untuk membangkitkan kemungkinan rute – rute yang paling optimal untuk dilewati. • Meneruskan lalu lintas trafik data pengguna ke rute – rute optimal tersebut.
11
Protokol Routing (cont) Elemen penting dari routing terbagi sebagai berikut : • Algoritma, sebagai penentu cara kerja routing, dimana setiap algoritma memiliki karakteristik yang berbeda sehingga penerapannya dapat kita sesuaikan dengan kondisi jaring data yang kita miliki. •Database (Tabel Routing), dalam hal ini adalah database dari table routing yang ada pada router sebagai pedoman untuk router tersebut dalam meneruskan paket data yang akan dikirimkan. •Protokol, dalam hal ini adalah sebuah cara berkomunikasi antar router untuk saling mengumpulkan, mendistribusikan, dan memperbaharui informasi routing masing-masing. 12
Routing LinkState • Protokol routing LinkState didasarkan pada algoritma Shortest Path First (SPF) untuk menemukan jalur terbaik ke tujuan. Algoritma Shortest Path First (SPF) algoritma ini juga dikenal sebagai algoritma Dijkstra. • Dalam algoritma Shortest Path First (SPF), setiap kali ada perubahan kondisi sebuah link, router akan mengirim paket update routing yang disebut Link-State Advertisement (LSA) dan kemudian dipertukarkan antara router. • Paket LSA routing update digunakan untuk menghitung ulang jalan terpendek ke arah tujuan. Setiap router akan selalu membangun peta jaring atau tabel routing yang lengkap, terutama setelah ada perubahan kondisi link. • • Contoh dari protokol Link State adalah OSPF (Open Shortest Path First) 13
Routing LinkState (cont) Algoritma Routing LinkState : • Router berusaha mencari dan mempelajari alamat semua router tetangga dalam area jaring yang sama • Router kemudian mengukur nilai (cost) yang dibutuhkan ke semua tetangga router tersebut. • Hasil pengukuran disimpan dalam sebuah paket yang kemudian di kirim kembali ke semua router tetangga (LSA) •Router akan selalu membangun peta jaring atau tabel routing yang lengkap, terutama setelah ada perubahan kondisi link.
14
Routing LinkState (cont) Keuntungan : • Waktu convergence lebih cepat karena update diforward segera • Tidak rentan terhadap routing loops • Tidak rentan terhadap informasi yang salah karena hanya informasi tangan pertama saja yang di broadcast Kelemahan : • Algoritma Link State memerlukan power CPU dan memory yang tinggi untuk melakukan kalkulasi topology jaringan dan memilih route • Menaikkan traffic jika terjadi perubahan topology
15
Ant Colony Ant Colony Optimization (ACO) merupakan suatu metodologi yang dikemukakan pada tahun 1991 oleh Marco Dorigo. ACO telah diterapkan di banyak permasalahan optimisasi seperti: traveling salesman problem, job-scheduling, vehicle routing, network routing dan lainnya
16
Ant Colony (cont.) r
Probabilitas langkah semut untuk bergerak ke node berikutnya :
Dimana :
17
AntNet AntNet adalah algoritma routing berbasis Ant Colony. AntNet terbagi menjadi dua agen mobile disebut dengan forward ant dan backward ant. Tugas dari setiap forward ants adalah untuk mencari jalur dengan delay minimum antara titik sumber dan tujuan. Tugas backward ants adalah memperbaharui informasi routing pada setiap node, yaitu diantaranya informasi mengenai: waktu perjalanan, table pheromone, dan table routing.
18
Algoritma AntNet 1. Forward Ant, dinotasikan Fsd , dimana akan berjalan dari sumber s menuju tujuan d. 2. Kemudian forward ant akan memilih rute berdasarkan probabilitas, P’nd, sebanding dengan table probabilitas routing dan banyaknya hubungan yang bersesuaian, ln.
Dengan : P’nd adalah probabilitas pemilihan node sebagai rute yang berikutnya. α adalah suatu bobot yang diberikan panjangnya antrian. Ln adalah sebanding kepada kebalikan panjangnya antrian pada tujuan d yang dinormalisir kepada interval unit. Nk adalah banyaknya node k 19
3. Selama perjalanan, agen Forward ants mengumpulkan informasi besar nya 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. 4. Setelah agen Forward Ant sampai ke tujuan d, kemudian memindahkan memory tentang perjalanan ke Backward Ant. 5. Agen Backward Ant dinotasikan Bds adalah agen yang dibangkitkan oleh forward ant setelah sampat ke tujuan d. Backward ant akan kembali ke sumber node s mengikuti jalur yang dilewati oleh forward ant dengan tujuan mengupdate table routing
20
AntNet Model perjalanan agen ant :
21
Diagram Alir Algoritma AntNet Node Sumber Mulai
Node Tengah
Node Tujuan
Inisialisasi parameter Bagkitkan Agen FA Kirim FA Terima FA Pilih node
Sumber ≠ tujuan ?
Eliminasi FA
Selesai
Baca dan tulis tabel routing dan informasi trafik
Ant 22
Diagram Alir Algoritma AntNet Node Sumber
Node Tengah Ant
Node Tujuan Terima FA Bangkitan agen FA
Simpan Kirim memory FA -> BA Sumber ≠ tujuan ?
Kirim BA ke jalur kebalikan dari FA
Eliminasi FA Kirim FA berdasarkan Feromone
Terima BA Update Tabel Node Eliminasi BA
Eliminasi FA
Selesai Terima BA Update Tabel Node
Selesai
Kirim BA
23
24
Skema Penelitian Mulai Studi Literatur : • Sistem jaring Data CPI • Algoritma routing AntNet • Riset terkait
Membangun Algoritma pemilihan jalur berbasis AntColony (AntNet)
Simulasi Algoritma Routing Linkstate pada NS2 dengan topologi PT. CPI
Simulasi Algoritma AntNet pada NS2 dengan topologi PT. CPI Trafik Data : UDP, TCP, RTP Pengukuran dan Pengambilan Data
Pengukuran dan Pengambilan Data
Perbandingan dan Analisa Data (Throughput, Delay, Jitter dan Konvergensi)
Kesimpulan
Selesai
25
Topologi Jaring Data Topologi yang digunakan pada pemodelan simulasi adalah menggunakan topologi jaring multi jalur di PT. CPI Router F (node 5)
Router G (node 6) 1 Gbps 1 Gbps
Router B (node 1) Router A (node 0)
1 Gbps
1 Gbps
1 Gbps
Router J (node 9)
Router D (node 3)
1 Gbps
Router L (node 11) Router N (node 13)
1 Gbps
1 Gbps 1 Gbps
1 Gbps
1 Gbps 1 Gbps
1 Gbps
1 Gbps 1 Gbps Router C (node 2)
1 Gbps
1 Gbps
Router E (node 4)
Router K (node 10)
1 Gbps I
Router M (node 12)
1 Gbps
1 Gbps Router H (node 7)
Router I (node 8)
26
Skenario Proses Pengujian dan Simulasi • • • • • •
Simulasi menggunakan simulator NS2.34 pada Sistem Operasi Ubuntu 10.04 Variasi besar ukuran paket adalah antara 128KBps s/d 2048KBps dan simulasikan pengiriman paket dari Router A ke Router N Variasi ukuran bandwidth link yang digunakan adalah 128Kbps dan 512Kbps Waktu yang digunakan untuk pengujian dan simulasi algoritma adalah 100 detik Pegiriman paket setiap 0.01 detik, sehingga total paket yang dikirim 10.000 paket Pada skenario link drop, dilakukan pada detik ke 50.
27
28
Simulasi dengan NS-2
29
NS-2 TCL sample script Inisiailiasi awal : Jumlah node, tampilan node, & file output Membuat jalur antar node
30
NS-2 TCL sample script Membuat dan mengaktifkan agen semut
Parameter proses simulasi AntNet
Generator paket sebesar 1024
31
Hasil Trace file dari NS-2 Contoh hasil keluaran dari simulasi N2-2 yang masih berupa raw data.
32
Tabel Routing dari Algoritma AntNet Routing table at node 0 dest
next
1
2
1
phvalue
Routing table at node 1 dest
next
0.080099
0
3
1
0.919901
0
2
2
0.8148
2
1
3
phvalue
Routing table at node 2 dest
next
phvalue
0.000068
0
4
0.000008
2
0.129352
0
1
0.000235
0
0
0.87058
0
0
0.999758
0.1852
2
3
0.000009
1
4
0.000007
2
0.1023
2
2
0.759219
1
1
0.842453
3
1
0.8977
2
0
0.240771
1
0
0.15754
4
2
0.650283
3
3
0.973257
3
4
0.221466
4
1
0.349717
3
2
0.026717
3
1
0.605897
5
2
0.214137
3
0
0.000026
3
0
0.172637
5
1
0.785863
4
3
0.307791
4
4
0.998934
6
2
0.438736
4
2
0.592377
4
1
0.001066
6
1
0.561264
4
0
0.099831
4
0
0
7
2
0.714951
5
3
0.959484
5
4
0.391565
7
1
0.285049
5
2
0.0344
5
1
0.410278
8
2
0.501675
5
0
0.006116
5
0
0.198157
8
1
0.498325
6
3
0.755782
6
4
0.886846
9
2
0.306593
6
2
0.182634
6
1
0.106498
9
1
0.693407
6
0
0.061584
6
0
0.006656
10
2
0.370146
7
3
0.353052
7
4
0.982667
33
Perbandingan Hasil Simulasi Tabel Hasil simulasi dengan skenario tidak ada link drop Skenario
Protocol
Tipe Data
Antnet
No link drop
Packet Size (KBytes
Bandwidth (Kbps)
Throughput (Kbps)
Packet Delivery Ratio (%)
1024
128
49.09
99.97
1280
128
51.46
99.36
1536
128
53.28
99.23
1792
128
56.82
98.78
1024
128
51.59
99.94
1280
128
52.38
99.59
1536
128
54.91
99.61
1792
128
57.23
99.43
CBR
LinkState
34
Perbandingan Hasil Simulasi Grafik Hasil simulasi dengan skenario tidak ada link drop
35
Perbandingan Hasil Simulasi Tabel Hasil simulasi dengan skenario dengan ada link drop
Skenario
Protocol
Tipe Data
Antnet
Link drop
Packet Size (KBytes
Bandwidth (Kbps)
Throughput (Kbps)
Packet Delivery Ratio (%)
1024
128
35.18
99.35
1280
128
37.55
99.71
1536
128
38.47
98.97
1792
128
41.86
98.81
1024
128
34.68
99.11
1280
128
35.29
99.03
1536
128
37.82
99.79
1792
128
39.77
98.49
CBR
LinkState
36
Perbandingan Hasil Simulasi Grafik Hasil simulasi dengan skenario dengan ada link drop
37
Kesimpulan dan Saran 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 scenario jalur normal. Sedangkan pada scenario jalur terputus, AntNet lebih baik dari linkstate dengan selisih 3,5%. 3. Pengujian pada waktu delay paket, hasinya menunjukkan bahwa algoitma LinksState lebih baik disbanding algoritma AntNet dengan perbedaaan sebesar 26,3%. 4. Pengujian lain berupa routing overhead menunjukkan perbedaan cukup significant yaitu sebesar 96% dengan algoritma LinkState yang lebih baik dibanding AntNet. 38
Kesimpulan dan Saran Saran Berdasarkan hasil penelitian dan kesimpulan, maka saran akhir dari penelitian ini adalah : 1. Disarankan untuk mengembangkan penelitian terkait algoritma routing AntNet ini lebih lanjut, terutama pengujian untuk melihat kemampuannya dalam proses pembaharuan atau pemulihan ulang routing saat terjadi kegagalan jalur utama. 2. Selanjutnya disarankan pula mencoba algoritma routing AntNet ini pada kondisi jaring sebenarnya dengan mengimplementasikan langsung pada perangkat keras router
39
