Algoritma Bellman Ford

Algoritma Bellman-Ford menghitung jarak terpendek (dari satu sumber) pada sebuah graf berbobot. Maksudnya dari satu sumber ialah bahwa ia menghitung semua jarak terpendek yang berawal dari satu titik node. Algoritma Dijkstra dapat lebih cepat mencari hal yang sama dengan syarat tidak ada sisi (edge) yang berbobot negatif. Maka Algoritma Bellman-Ford hanya digunakan jika ada sisi berbobot negatif. Muncul nya Algoritma ini cukup membantu jika bobot dari suatu graf bernilai negatif.

Pengaplikasian algoritma bellman ford dalam routing:

Dalam routing algoritma Bellman-Ford adalah digunakan dalam distance vector routing protocol, misalnya Routing Information Protocol (RIP). Algoritma ini didistribusikan karena melibatkan jumlah node (router) dalam Autonomous system, koleksi jaringan IP biasanya dimiliki oleh ISP. Adapun langkah-langkah nya sebagai berikut:

• Setiap node menghitung jarak antara dirinya dan semua node lain dalam AS dan menyimpan informasi ini sebagai sebuah tabel.

• Setiap node mengirimkan tabel ke semua node tetangga.

• Ketika sebuah node menerima tabel jarak dari tetangganya, ia menghitung rute terpendek ke semua node lainnya dan update tabel sendiri untuk menggambarkan perubahan yang terjadi

Kelemahan utama dari algoritma Bellman-Ford adalah sebagai berikut:

•  Kurang baik untuk jaringan berskala besar

•  Perubahan topologi jaringan tidak berjalan dengan cepat karena update tersebar node-by-node.

• Menghitung sampai tak terhingga (jika link atau node mengalami sebuat kegagalan maka node tidak dapat dicapai dari beberapa set node lain, node yang lain dapat menghabiskan waktu untuk looping sampai tak terhingga secara bertahap meningkatkan perkiraan mereka dari kegagalan itu, dan sementara itu mungkin ada routing loop).

Contoh algoritma bellman ford :

 Langkah Pertama

Langkah Kedua

Langkah Ketiga

 

Langkah Keempat

 

Langkah Kelima

 

Langkah Keenam

 

Langkah Ketujuh

 

Referensi : http://users.informatik.uni-halle.de/~jopsi/dinf503/chap12.shtml

RIP dan OSPF

 

RIP (Routing Internet Protocol)

RIP merupakan sebuah protocol routing dinamis yang menggunakan algoritma distance vector dalam penerapannya. Versi dari RIP terdapat 2 jenis yaitu RIPv1 dan RIPv2. RIPv1 memiliki banyak kekurangan sehingga seiring berjalan nya waktu diciptakan RIPv2 yang karakteristik nya lebih baik. 

Berikut beberapa karakteristik dari RIPv1 dan RIPv2.

RIP versi 1

• RIP versi ini menggunakan classful routing sehingga tidak mendukung adanya subneting pada IP yang digunakan. 

• Pembaruan routing periodik tidak membawa subnet informasi, dukungan kurang untuk subnet mask panjang variabel (VLSM). Keterbatasan ini tidak memungkinkan untuk memiliki ukuran yang berbeda subnet yang sama dalam kelas jaringan . Dengan kata lain, semua subnet dalam jaringan kelas harus memiliki ukuran yang sama. 

• Tidak ada dukungan untuk otentikasi router, membuat RIP rentan terhadap berbagai versi RIP attacks.

•  RIP versi 1 hanya memiliki jumlah hop 16 (0-15). Jika ada lebih dari 16 hop antara dua router itu gagal untuk mengirim paket data ke alamat tujuan

 

RIP versi 2

• Dukungan untuk membawa informasi subnet, sehingga mendukung classless inter-domain routing(CIDR). Jumlah hop limit  tetap 16 hop. 

• RIPv2 memiliki fasilitas untuk sepenuhnya interoperate dengan spesifikasi awal jika semua protokol bidang Harus Zero dalam pesan RIPv1 yang benar ditentukan. Selain itu, fitur beralih kompatibilitas berbutir interoperabilitas memungkinkan penyesuaian saja. 

• Dalam upaya untuk menghindari beban yang tidak perlu di host yang tidak berpartisipasi dalam routing, multicast RIPv2 tabel routing seluruh untuk semua router berdekatan di alamat 224.0.0.9, sebagai lawan RIPv1 yang menggunakan siaran.Pengalamatan unicast masih diperbolehkan untuk aplikasi khusus.\
• RIPv2 telah mendukung adanya otentikasi router sehingga ancaman RIP attacks bisa ditanggulangi

Format paket RIPv1

 

  

Format Paket RIPv2

RIP Timer

Router-Router pada jaringan RIP membangun routing tablenya berdasarkan pengaturan informasi melalui pengiriman paket update pada tiap selang waktu tertenti(periodic update). Hasil dari pertukaran informasi ini oleh tiap-tiap router dilakukan kalkulasi untuk menetapkan jalur terbaik (the best path) dari suatu network yang mengirimkan paket data ke network.

RIP memiliki 4 jenis timer diantaranya :

• Update Timer : seberapa sering melakukan update informasi dalam hitungan detik. Selama 30 detik (waktu default update timer), untuk update routing table secara periodik, dimana sebuah router mengirimkan sebuah copy lengkap dari routing tablenya ke router tetangga .

•  Invalid Timer : digunakan untuk mempertimbangkan rute yang invalid  dan menempatkan rute tersebut ke hold down. Selama 180 detik(default) , dalam jangka waktu tersebut, jika router tidak menerima informasi baru dari router tetangga, maka router akan mengirimkan update bahwa router tetangga yang sudah 180 detik tidak update, sekarang sudah tidak valid (time out). Invalid timer merupakan seberapa lama router harus menunggu pesan routing update tentang jalur sebelum jalur tersebut invalid.

• Hold Down Timer : waktu ( default : 180 detik) untuk menahan informasi-informasi yang datang dan membantu mencegah routing loops selama topologi mengumpulkan informasi baru. Holddown timer merupakan banyaknya waktu untuk informasi tentang jalur yang dilewati.

• Flush Timer : berapa detik (default : 240 detik) sejak update terakhir yang valid, rute dibuang ke sampah. (garbage collection).Ketika rute timeout maka rute ditandai invalid dan masuk ke flush timer. Flush timer menunjukkan banyaknya waktu yang seharusnya dilewati sebelum suatu rute dihapus dari table routing.

 

Beberapa criteria yang digunakan untuk mengukur unjuk kerja sebuah router:

a.   Time to converge (Waktu Konvergensi)

Konvergensi memiliki arti kondisi atau keadaan dimana Merupakan waktu yang digunakan untuk berbagi informasi melintasi network sehingga diperoleh jalur terbaiknya(best path).Semakin cepat time to converge maka akan semakin baik.Penggunaan periode update akan menyebabkan slower converge(lambatnya konvergensi).Bahkan dengan digunakannya beberapa teknologi seperti triggered update,konvergensi secara keseluruhan masih lebih lambat dibandingkan link state protokol routing.Lambatnya konvergensi dalam perubahan jaringan menyebabkan table routing tidak konsisten atau tidak terupdate sehingga menyebabkan routing loop.

b.    Scalability (Skalabilitas)

Scalability berfungsi dalam jaringan-jaringan yang luas. Protokol distance vector memiliki skalabilitas yang terbatas.Konvergensi yang lambat membatasi ukuran suatu network/skalabilitas karena network yang besar membutuhkan waktu yang lebih untuk menyebarkan informasi routing.

c.    Resource usage

Protokol distance vector hanya membutuhkan resource requirement yang rendah.Tipe protokol distance vector tidak membutuhkan memori penyimpanan informasi yang besar juga tidak membutuhkan CPU yang powerful.Hal imi tergantung dari ukuran jaringan dan pengimplementasian IP address.Tipe protocol routing ini biasanya tidak memerlukan link bandwidth yang tinggi.Namun,hal ini akan menjadi masalah jika protokol distance vector digunakan pada jaringan yang besar.

OSPF (Open Shortest Path First)

OSPF (Open Shortest Path First) adalah salah satu protokol pada keluarga IP, untuk routing dinamik. OSPF dikembangkan karena kebutuhan pada network yang besar dan heterogen. Beberapa keuntungan dari OSPF adalah konvergensi yang cepat, yang pada gilirannya mencegah routing loop dan menghasilkan network yang stabil.

Cara OSPF Membentuk Hubungan dengan Router Lain       

Membuat komunikasi dengan router tetangga (neighbor) dengan menggunakan mekanisme HELLO PROTOKOL yang berisi paket kecil  yang dikirim secara periodik yang dinamai dengan HELLO packet. Paket tersebut akan di broadcast dalam rentang waktu 10 detik dan 30 detik sekali dalam media Point-to-Point. Hello packet berisikan informasi seputar pernak-pernik yang ada pada router pengirim. Hello packet pada umumnya dikirim dengan menggunakan multicast address untuk menuju ke semua router yang menjalankan OSPF (IP multicast 224.0.0.5). Semua router yang menjalankan OSPF pasti akan mendengarkan protocol hello ini dan juga akan mengirimkan hello packet-nya secara berkala. Cara kerja dari Hello protocol dan pembentukan neighbour router terdiri dari beberapa jenis, tergantung dari jenis media di mana router OSPF berjalan.

Dalam proses pembentukan hubungan dengan router lain terdapat pula sebuah paket yang bernama dimana Link state advertisement (LSA) merupakan sebuah paket data yang dikirim router untuk mengenali seluruh tetangga nya dan berisi informasi routing ospf diantara router-router.

Ada 5 tipe paket yang digunakan OSPF, yaitu :

1)  Hello Packet

Hello Packet merupakan paket yang pertama kali dikirim oleh router tujuan pengiriman paket ini digunakan untuk menemukan serta membentuk suatu hubungan tetangga antara router OSPF. Untuk membentuk hubungan ini router OSPF akan mengirimkan paket berukuran kecil secara berkala ke jaringan. Paket inilah yang disebut dengan Hello packet. Paket ini juga memberitahukan router mana saja yang akan menjadi tetangganya.

2)   Database Description (DBD)

DBD digunakan selama pertukaran database. Paket DBD pertama digunakan untuk memilih hubungan master dan slave serta menetapkan urutan yang dipilih oleh master. Pemilihan master dan slave berdasarkan router ID tertinggi dari salah satu router. Router dengan router ID tertinggi akan menjadi master dan memulai sinkronisasi database. Router yang menjadi master akan melakukan pengiriman lebih dulu ke router slave. Peristiwa ini di istilahkan fase Exstart State. Setelah fase Exstart State lewat, selanjutnya adalah fase Exchange. Pada fase ini kedua router akan saling mengirimkan Database Description Packet. Bila si penerima belum memiliki informasi yang terdapat dalam paket tersebut, maka router pengirim akan memasuki fase Loading State. Dimana fase ini router akan mengirimkan informasi state secara lengkap ke router tetangganya. Setelah selesai router-router OSPF akan memiliki informasi state yang lengkap dalam databasenya, ini disebut fase Full State.

3)   Link-State Request (LSR)

LSR akan dikirim jika bagian dari database hilang atau out of date. LSR juga digunakan setelah pertukaran DBD selesai untuk meminta LSA yang telah terjadi selama pertukaran DBD.

4)   Link-State Update (LSU)

LSU mengimplementasikan flooding dari LSA yang berisi routing dan informasi metric. LSU dikirim sebagai tanggapan dari LSR.

5)   Link-State Acknowledgement (LSAck)

OSPF membutuhkan pengakuan untuk menerima setiap LSA. Beberapa LSA dapat diakui dalam sebuah paket single link-state acknowledgement. Paket ini dikirim sebagai jawaban dari packet update link state serta memverifikasi bahwa paket update telah diterima dengan sukses. LSAck akan dikirim sebagai multicast.