- \n
- Pengetahuan tentang lingkungan sekitar:<\/strong>\u00a0Daripada mengirimkan tabel routingnya, router hanya mengirimkan informasi tentang lingkungannya saja. Sebuah router menyiarkan identitasnya dan biaya link yang terhubung langsung ke router lain.<\/li>\n\n\n\n
- Flooding:<\/strong>\u00a0Setiap router mengirimkan informasi ke setiap router lain di internetwork kecuali tetangganya. Proses ini dikenal sebagai Banjir. Setiap router yang menerima paket mengirimkan salinannya ke semua tetangganya. Akhirnya, setiap router menerima salinan informasi yang sama.<\/li>\n\n\n\n
- Berbagi informasi:<\/strong>\u00a0Sebuah router mengirimkan informasi ke setiap router lainnya hanya ketika terjadi perubahan informasi.<\/li>\n<\/ul>\n\n\n\n
Router Link State memiliki dua fase:<\/h2>\n\n\n\n
Banjir yang Dapat Diandalkan<\/h3>\n\n\n\n
- \n
- Keadaan awal:<\/strong>\u00a0Setiap node mengetahui biaya node tetangganya.<\/li>\n\n\n\n
- Keadaan akhir:<\/strong>\u00a0Setiap node mengetahui keseluruhan grafik.<\/li>\n<\/ul>\n\n\n\n
Perhitungan Rute<\/h3>\n\n\n\n
Setiap node menggunakan algoritma Dijkstra pada grafik untuk menghitung rute optimal ke semua node.<\/p>\n\n\n\n
- \n
- Algoritma routing Link state disebut juga dengan algoritma Dijkstra yang digunakan untuk mencari jalur terpendek dari satu node ke setiap node lainnya dalam jaringan.<\/li>\n\n\n\n
- Algoritme Dijkstra bersifat iteratif, dan memiliki properti bahwa setelah k\u00a0iterasi<\/sup>\u00a0algoritma, jalur dengan biaya terkecil diketahui untuk k node tujuan.<\/li>\n<\/ul>\n\n\n\n
Mari kita jelaskan beberapa notasi:<\/h2>\n\n\n\n
- \n
- c( i , j):<\/strong>\u00a0Biaya tautan dari node i ke node j. Jika node i dan j tidak terhubung langsung, maka c(i , j) = \u221e.<\/li>\n\n\n\n
- D(v):<\/strong>\u00a0Mendefinisikan biaya jalur dari kode sumber ke tujuan v yang memiliki biaya paling sedikit saat ini.<\/li>\n\n\n\n
- P(v):<\/strong>\u00a0Ini mendefinisikan node sebelumnya (tetangga dari v) bersama dengan jalur biaya terendah saat ini dari sumber ke v.<\/li>\n\n\n\n
- N:<\/strong>\u00a0Ini adalah jumlah total node yang tersedia di jaringan.<\/li>\n<\/ul>\n\n\n\n
Algoritma<\/h2>\n\n\n\n
- \n
- Inisialisasi<\/strong> <\/li>\n\n\n\n
- N = {A} \/\/ A adalah simpul akar<\/strong> . <\/li>\n\n\n\n
- untuk semua node v <\/li>\n\n\n\n
- jika v berdekatan dengan A <\/li>\n\n\n\n
- maka D(v) = c(A,v) <\/li>\n\n\n\n
- else D(v) = infinity loop<\/strong> <\/li>\n\n\n\n
- carilah w tidak di N sehingga D(w) adalah minimum. <\/li>\n\n\n\n
- Tambahkan w ke N <\/li>\n\n\n\n
- Perbarui D(v) untuk semua v yang berdekatan dengan w dan bukan di N: <\/li>\n\n\n\n
- D(v) = min(D(v) , D(w) + c(w,v)) <\/li>\n\n\n\n
- Hingga semua node di N<\/li>\n<\/ul>\n\n\n\n
Dalam algoritma di atas, langkah inisialisasi diikuti oleh loop. Berapa kali loop dieksekusi sama dengan jumlah total node yang tersedia di jaringan.<\/p>\n\n\n\n
Mari kita pahami melalui contoh:<\/strong><\/p>\n\n\n
\n![\"\"](\"https:\/\/b581640.smushcdn.com\/581640\/wp-content\/uploads\/2024\/05\/image-24.png?lossy=1&strip=1&webp=1\")
<\/a><\/figure>\n<\/div>\n\n\nPada gambar di atas, titik sumbernya adalah A.<\/strong><\/p>\n\n\n\n
Langkah 1:<\/h3>\n\n\n\n
Langkah pertama adalah langkah inisialisasi. Jalur berbiaya terendah yang diketahui saat ini dari A ke tetangganya yang terhubung langsung, B, C, D masing-masing adalah 2,5,1. Biaya dari A ke B diatur ke 2, dari A ke D diatur ke 1 dan dari A ke C diatur ke 5. Biaya dari A ke E dan F diatur hingga tak terhingga karena tidak terhubung langsung ke A.<\/p>\n\n\n
\n![\"\"](\"data:image\/svg+xml;base64,PHN2ZyB3aWR0aD0iMSIgaGVpZ2h0PSIxIiB4bWxucz0iaHR0cDovL3d3dy53My5vcmcvMjAwMC9zdmciPjwvc3ZnPg==\")
<\/a><\/figure>\n<\/div>\n\n\nLangkah 2:<\/h3>\n\n\n\n
Pada tabel di atas, kita mengamati bahwa simpul D berisi jalur dengan biaya terkecil pada langkah 1. Oleh karena itu, ditambahkan pada N. Sekarang, kita perlu menentukan jalur dengan biaya terkecil melalui simpul D.<\/p>\n\n\n\n
a) Menghitung jalur terpendek dari A ke B<\/strong><\/p>\n\n\n\n
<\/a><\/a><\/a><\/p>\n\n\n\n
- \n
- v = B, w = D\u00a0\u00a0<\/li>\n\n\n\n
- D(B) = menit( D(B) , D(D) + c(D,B) )\u00a0\u00a0<\/li>\n\n\n\n
- \u00a0\u00a0\u00a0\u00a0\u00a0= menit(\u00a0\u00a02\u00a0,\u00a0\u00a01\u00a0+\u00a02\u00a0)>\u00a0\u00a0<\/li>\n\n\n\n
- \u00a0\u00a0\u00a0\u00a0\u00a0= menit(\u00a0\u00a02\u00a0,\u00a0\u00a03\u00a0)\u00a0\u00a0<\/li>\n\n\n\n
- Nilai minimumnya adalah\u00a0\u00a02\u00a0. Oleh karena itu, jalur terpendek saat ini dari A ke B adalah\u00a0\u00a02\u00a0.\u00a0\u00a0<\/li>\n<\/ul>\n\n\n\n
b) Menghitung jalur terpendek dari A ke C<\/strong><\/p>\n\n\n\n
- \n
- v = C, w = D\u00a0\u00a0<\/li>\n\n\n\n
- D(B) = menit( D(C) , D(D) + c(D,C) )\u00a0\u00a0<\/li>\n\n\n\n
- \u00a0\u00a0\u00a0\u00a0\u00a0= menit(\u00a0\u00a05\u00a0,\u00a0\u00a01\u00a0+\u00a03\u00a0)\u00a0\u00a0<\/li>\n\n\n\n
- \u00a0\u00a0\u00a0\u00a0\u00a0= menit(\u00a0\u00a05\u00a0,\u00a0\u00a04\u00a0)\u00a0\u00a0<\/li>\n\n\n\n
- Nilai minimumnya adalah\u00a0\u00a04\u00a0. Oleh karena itu, jalur terpendek saat ini dari A ke C adalah\u00a0\u00a04\u00a0.<\/p>\u00a0\u00a0<\/li>\n<\/ul>\n\n\n\n
c) Menghitung jalur terpendek dari A ke E<\/strong><\/a><\/a><\/a><\/p>\n\n\n\n
- \n
- v = E, w = D\u00a0\u00a0<\/li>\n\n\n\n
- D(B) = menit( D(E) , D(D) + c(D,E) )\u00a0\u00a0<\/li>\n\n\n\n
- \u00a0\u00a0\u00a0\u00a0\u00a0= menit( \u221e,\u00a0\u00a0\u00a01\u00a0+\u00a01\u00a0)\u00a0\u00a0<\/li>\n\n\n\n
- \u00a0\u00a0\u00a0\u00a0\u00a0= menit(\u221e,\u00a0\u00a02\u00a0)\u00a0\u00a0<\/li>\n\n\n\n
- Nilai minimumnya adalah\u00a0\u00a02\u00a0. Oleh karena itu, jalur terpendek saat ini dari A ke E adalah\u00a0\u00a02\u00a0.\u00a0\u00a0<\/li>\n<\/ul>\n\n\n\n<\/a><\/figure>\n<\/div>\n\n\n
Langkah 3:<\/h3>\n\n\n\n
Pada tabel di atas, kita mengamati bahwa E dan B memiliki jalur biaya terkecil pada langkah 2. Mari kita perhatikan simpul E. Sekarang, kita menentukan jalur biaya terkecil dari simpul-simpul yang tersisa melalui E.<\/p>\n\n\n\n
a) Menghitung jalur terpendek dari A ke B.<\/strong><\/a><\/a><\/a><\/p>\n\n\n\n
- \n
- v = B, w = E\u00a0\u00a0<\/li>\n\n\n\n
- D(B) = menit( D(B) , D(E) + c(E,B) )\u00a0\u00a0<\/li>\n\n\n\n
- \u00a0\u00a0\u00a0\u00a0\u00a0= menit(\u00a0\u00a02\u00a0\u00a0,\u00a0\u00a02\u00a0+ \u221e )\u00a0\u00a0<\/li>\n\n\n\n
- \u00a0\u00a0\u00a0\u00a0\u00a0= menit(\u00a0\u00a02\u00a0, \u221e)\u00a0\u00a0<\/li>\n\n\n\n
- Nilai minimumnya adalah\u00a0\u00a02\u00a0. Oleh karena itu, jalur terpendek saat ini dari A ke B adalah\u00a0\u00a02\u00a0.\u00a0\u00a0<\/li>\n<\/ul>\n\n\n\n
b) Menghitung jalur terpendek dari A ke C.<\/strong><\/a><\/a><\/a><\/p>\n\n\n\n
- \n
- v = C, w = E\u00a0\u00a0<\/li>\n\n\n\n
- D(B) = menit( D(C) , D(E) + c(E,C) )\u00a0\u00a0<\/li>\n\n\n\n
- \u00a0\u00a0\u00a0\u00a0\u00a0= menit(\u00a0\u00a04\u00a0\u00a0,\u00a0\u00a02\u00a0+\u00a01\u00a0\u00a0)\u00a0\u00a0<\/li>\n\n\n\n
- \u00a0\u00a0\u00a0\u00a0\u00a0= menit(\u00a0\u00a04\u00a0,\u00a03\u00a0)\u00a0\u00a0<\/li>\n\n\n\n
- Nilai minimumnya adalah\u00a0\u00a03\u00a0. Oleh karena itu, jalur terpendek saat ini dari A ke C adalah\u00a0\u00a03\u00a0.\u00a0\u00a0<\/li>\n<\/ul>\n\n\n\n
c) Menghitung jalur terpendek dari A ke F.<\/strong><\/a><\/a><\/a><\/p>\n\n\n\n
- \n
- v = F, w = E\u00a0\u00a0<\/li>\n\n\n\n
- D(B) = menit( D(F) , D(E) + c(E,F) )\u00a0\u00a0<\/li>\n\n\n\n
- \u00a0\u00a0\u00a0\u00a0\u00a0= menit( \u221e ,\u00a0\u00a02\u00a0+\u00a02\u00a0\u00a0)\u00a0\u00a0<\/li>\n\n\n\n
- \u00a0\u00a0\u00a0\u00a0\u00a0= menit(\u221e ,\u00a04\u00a0)\u00a0\u00a0<\/li>\n\n\n\n
- Nilai minimumnya adalah\u00a0\u00a04\u00a0. Oleh karena itu, jalur terpendek saat ini dari A ke F adalah\u00a0\u00a04\u00a0.\u00a0\u00a0<\/li>\n<\/ul>\n\n\n\n<\/a><\/figure>\n<\/div>\n\n\n
Langkah 4:<\/h3>\n\n\n\n
Pada tabel di atas, kita mengamati bahwa simpul B memiliki jalur dengan biaya terkecil pada langkah 3. Oleh karena itu, ditambahkan dalam N. Sekarang, kita menentukan jalur dengan biaya terkecil dari simpul-simpul yang tersisa melalui B.<\/p>\n\n\n\n
a) Menghitung jalur terpendek dari A ke C.<\/strong><\/p>\n\n\n\n
- \n
- v = C, w = B\u00a0\u00a0<\/li>\n\n\n\n
- D(B) = menit( D(C) , D(B) + c(B,C) )\u00a0\u00a0<\/li>\n\n\n\n
- \u00a0\u00a0\u00a0\u00a0\u00a0= menit(\u00a0\u00a03\u00a0\u00a0,\u00a0\u00a02\u00a0+\u00a03\u00a0\u00a0)\u00a0\u00a0<\/li>\n\n\n\n
- \u00a0\u00a0\u00a0\u00a0\u00a0= menit(\u00a0\u00a03\u00a0,\u00a05\u00a0)\u00a0\u00a0<\/li>\n\n\n\n
- Nilai minimumnya adalah\u00a0\u00a03\u00a0. Oleh karena itu, jalur terpendek saat ini dari A ke C adalah\u00a0\u00a03\u00a0.\u00a0\u00a0<\/li>\n<\/ul>\n\n\n\n
b) Menghitung jalur terpendek dari A ke F.<\/strong><\/a><\/a><\/a><\/p>\n\n\n\n
- \n
- v = F, w = B\u00a0\u00a0<\/li>\n\n\n\n
- D(B) = menit( D(F) , D(B) + c(B,F) )\u00a0\u00a0<\/li>\n\n\n\n
- \u00a0\u00a0\u00a0\u00a0\u00a0= menit(\u00a0\u00a04\u00a0, \u221e)\u00a0\u00a0<\/li>\n\n\n\n
- \u00a0\u00a0\u00a0\u00a0\u00a0= menit(\u00a04\u00a0, \u221e)\u00a0\u00a0<\/li>\n\n\n\n
- Nilai minimumnya adalah\u00a0\u00a04\u00a0. Oleh karena itu, jalur terpendek saat ini dari A ke F adalah\u00a0\u00a04\u00a0.\u00a0\u00a0<\/li>\n<\/ul>\n\n\n\n<\/a><\/figure>\n<\/div>\n\n\n
Langkah 5:<\/h3>\n\n\n\n
Pada tabel di atas, kita mengamati bahwa simpul C memiliki jalur dengan biaya terkecil pada langkah 4. Oleh karena itu, ditambahkan dalam N. Sekarang, kita menentukan jalur dengan biaya terkecil dari simpul-simpul yang tersisa melalui C.<\/p>\n\n\n\n
a) Menghitung jalur terpendek dari A ke F.<\/strong><\/p>\n\n\n\n
- \n
- v = F, w = C\u00a0\u00a0<\/li>\n\n\n\n
- D(B) = menit( D(F) , D(C) + c(C,F) )\u00a0\u00a0<\/li>\n\n\n\n
- \u00a0\u00a0\u00a0\u00a0\u00a0= menit(\u00a0\u00a04\u00a0,\u00a0\u00a03\u00a0+\u00a05\u00a0)\u00a0\u00a0<\/li>\n\n\n\n
- \u00a0\u00a0\u00a0\u00a0\u00a0= menit(\u00a04\u00a0,\u00a08\u00a0)\u00a0\u00a0<\/li>\n\n\n\n
- Nilai minimumnya adalah\u00a0\u00a04\u00a0. Oleh karena itu, jalur terpendek saat ini dari A ke F adalah\u00a0\u00a04\u00a0.\u00a0\u00a0<\/li>\n<\/ul>\n\n\n
- N = {A} \/\/ A adalah simpul akar<\/strong> . <\/li>\n\n\n\n
- D(v):<\/strong>\u00a0Mendefinisikan biaya jalur dari kode sumber ke tujuan v yang memiliki biaya paling sedikit saat ini.<\/li>\n\n\n\n
- c( i , j):<\/strong>\u00a0Biaya tautan dari node i ke node j. Jika node i dan j tidak terhubung langsung, maka c(i , j) = \u221e.<\/li>\n\n\n\n
- Keadaan akhir:<\/strong>\u00a0Setiap node mengetahui keseluruhan grafik.<\/li>\n<\/ul>\n\n\n\n
- Flooding:<\/strong>\u00a0Setiap router mengirimkan informasi ke setiap router lain di internetwork kecuali tetangganya. Proses ini dikenal sebagai Banjir. Setiap router yang menerima paket mengirimkan salinannya ke semua tetangganya. Akhirnya, setiap router menerima salinan informasi yang sama.<\/li>\n\n\n\n