Sebelumnya telah dijelaskan tentang algoritma djikstra. Selanjutnya pada artikel ini kita akan mempelajari tentang algoritma yang digunakan oleh OSPF, yaitu algoritma SPF.
Algoritma SPF ini merupakan sebuah algoritma yang mengadopsi djikstra. Jadi bisa dikatakan bahwa SPF ini merupakan turunan dari algoritma djikstra.
Sesuai dengan namanya short path first, algoritma ini akan mencari jalur terpendek untuk dijadikan best path.
Dalam hal ini, jalur terpendek yang dimaksud bukan berdasarkan hop count seperti yang digunakan pada distance vector routing protocol, melainkan berdasarkan cost.
Algoritma Shortest Path First
Cost adalah sebuah angka yang menggambarkan bandwidth yang dimiliki oleh sebuah link. Untuk menghitung cost sebuah link, ada rumus tersendiri yang bisa kita gunakan.
Saat link state routing protocol diaktifkan, maka setiap router akan mengumpulkan informasi tentang seluruh directly connected network (network yang terhubung secara langsung).
Kemudian setiap router akan mengirim informasi tersebut ke seluruh router yang juga menjalankan link state routing protocol.
Dari topologi diatas, maka R1 akan membuat informasi tentang directly connected networknya seperti berikut. Informasi ini disebut dengan LSA (Link State Advertisement).
Bukan hanya R1 yang membuat informasi tentang directly networknya, melainkan seluruh router.
Berikut infomasi yang dibuat oleh R2.
Setelah seluruhrouter membuat LSA, maka LSA tersebut akan dikirimkan (flooding) keseluruh router. Karena seluruh router mengirimkan masing-masing LSA nya, maka setiap router akan menerim LSA dari seluruh router.
Kumpulan LSA yang diterima dari router lain tersebut akan disimpan oleh setiap router kedalam sebuah database yang biasa disebut LSDB (Link State Database). Berikut LSDB yang dimiliki oleh R1.
Dengan bermodalkan LSBD tersebut, maka R1 akan menjalankan algoritma SPF untuk menentukan jalur terbaik (Best Path) untuk mencapai suatu network. Berikut tahap proses algoritma SPF berjalan.
Pertama R1 akan membaca LSA yang dibuat oleh dirinya sendiri.
Dari informasi tersebut, maka R1 akan membuat sebuah topologi seperti berikut.
Selanjutnya R1 akan membaca LSA yang dibuat oleh R2 dan menetukan LSA mana yang bisa digunakan dan LSA mana yang tidak di perlu digunakan.
Dari LSA yang dibuat oleh R2, terlihat bahwa ada satu informasi yang diperlukan di satu informasi yang tidak diperlukan.
Informasi tentang network 12.12.12.0/24 tidak diperlukan karena network ini sudah ada pada LSA yang dibuat oleh R1 itu sendiri.
Berikut topologi yang dibuat oleh R1 setelah memperhitungkan LSA dari R2.
Tahap selanjutnya, R1 akan membaca LSA yang dibuat oleh R3.
Pada tahap ini, R1 akan menghapus informasi tentang network 13.13.13.0/24 karena network ini sudah ada pada LSA yang dibuatnya sendiri.
Berikut topologi yang dibuat oleh R1 setelah memperhitungkan LSA dari R3.
Tahap terakhir, R1 akan membaca LSA yang dibuat oleh R4.
Disini R1 akan menghapus network 24.24.24.0/24 dan 34.34.34.0/24 karena kedua network ini sudah ada pada LSA R2 dan R3.
Sampai saat ini R1 sudah memiliki informasi yang lengkap tentang topologi seluruh jaringan yang ada. Setelah R1 mengetahui bentuk topologi jaringan secara keseluruhan, maka algoritma SPF akan menghitung jumlah cost untuk menuju suatu network.
Berikut tabel yang menunjukan cost yang dibutuhkan R1 untuk menuju network 192.168.4.0/24 .
Perhatikan bahwa R1 mempunyai dua jalur untuk menuju network 192.168.4.0/24 . Dengan menggunkan algoritma SPF, maka R1 akan memilih best path untuk menuju network tersebut.
Link state routing protocol akan menggunakan cost terkecil sebagai best path. Sehingga jalur melewati R2 akan menjadi best path untuk menuju network 192.168.4.0/24 .
Setelah R1 mengetahui best path untuk menuju network 19.168.4.0/24, maka R1 akan mengcopy best path tersebut kedalam table routing.
Sedangkan jalur lain hanya digunakan untuk backup link dan tidak akan dicopykan ke table routing.
