DJK 10 - Epulvis/Rangkuman_Materi GitHub Wiki

Protokol routing bertujuan untuk menentukan jalur "terbaik" dari pengirim ke penerima melalui jaringan router. Jalur "terbaik" ini bisa berarti biaya terendah, tercepat, atau paling tidak padat. Ada dua pendekatan utama untuk struktur bidang kontrol jaringan: kontrol per-router (tradisional) dan kontrol terpusat secara logis (Software Defined Networking).

Ada dua klasifikasi utama algoritma routing:

• Global (Link State): Semua router memiliki informasi topologi dan biaya tautan yang lengkap¹.
• Decentralized (Distance Vector): Router hanya mengetahui biaya tautan ke tetangga yang terhubung langsung dan bertukar informasi secara iteratif².

---

Algoritma Link-State adalah protokol di mana setiap router membangun "peta" lengkap atau topologi seluruh jaringan. Setiap router kemudian secara independen menghitung jalur terpendek dari dirinya ke setiap router lain dalam jaringan.

• Informasi Global: Semua router mengetahui topologi jaringan dan biaya setiap tautan³. Informasi ini disebarkan ke semua router melalui proses yang disebut "link state broadcast"⁴.
• Algoritma Dijkstra: Protokol LS umumnya menggunakan algoritma Dijkstra untuk menghitung jalur berbiaya terendah dari satu node sumber ke semua node lain dalam jaringan⁵.
  • Cara Kerja: Algoritma ini bersifat iteratif. Setelah k iterasi, ia akan mengetahui jalur berbiaya terendah ke k tujuan⁶.
  • Kompleksitas: Kompleksitas algoritma ini adalah O(n²) atau O(n log n) dengan implementasi yang lebih efisien, di mana n adalah jumlah node. Kompleksitas pesannya adalah O(n²)⁷.
• Contoh Implementasi: OSPF (Open Shortest Path First) adalah protokol routing intra-AS yang menggunakan link-state. Setiap router menyebarkan iklan status tautan ke semua router lain di AS yang sama⁸.

• Osilasi: Jika biaya tautan bergantung pada volume lalu lintas, bisa terjadi osilasi rute. Perubahan rute dapat menyebabkan perubahan biaya, yang pada gilirannya menyebabkan perubahan rute lagi, dan seterusnya⁹.

---

Dalam algoritma Distance-Vector, setiap router tidak perlu mengetahui seluruh topologi jaringan. Sebaliknya, ia hanya berkomunikasi dengan router tetangganya secara langsung, bertukar informasi tentang jarak (biaya) ke tujuan lain.

• Informasi Terdesentralisasi: Router hanya mengetahui biaya tautan ke tetangga yang terhubung langsung¹⁰.
• Persamaan Bellman-Ford: Algoritma ini didasarkan pada persamaan Bellman-Ford, di mana setiap node memperbarui perkiraan jaraknya berdasarkan informasi yang diterima dari tetangganya¹¹.
  • Cara Kerja: Secara berkala, setiap node mengirimkan perkiraan vektor jaraknya sendiri ke tetangganya. Ketika sebuah node menerima vektor jarak baru dari tetangganya, ia memperbarui vektor jaraknya sendiri menggunakan persamaan Bellman-Ford¹². Proses ini berlanjut sampai perkiraan konvergen ke biaya terendah yang sebenarnya¹³.
• Iteratif & Asynchronous: Pembaruan terjadi secara iteratif, dipicu oleh perubahan biaya tautan lokal atau pesan pembaruan dari tetangga. Ini adalah proses terdistribusi dan berhenti sendiri¹⁴.

• Count-to-Infinity: "Berita buruk" (seperti peningkatan biaya tautan atau kegagalan tautan) menyebar dengan lambat. Hal ini dapat menyebabkan router terus-menerus meningkatkan perkiraan biaya mereka ke tujuan yang tidak dapat dijangkau, menciptakan loop perutean sementara¹⁵. Sebaliknya, "berita baik" (seperti penurunan biaya tautan) menyebar dengan cepat¹⁶.

---

Fitur | Link-State (LS) | Distance-Vector (DV) -- | -- | -- Kompleksitas Pesan | O(n²) pesan dikirim oleh n router17. | Bervariasi; pertukaran hanya terjadi antara tetangga18. Kecepatan Konvergensi | Kompleksitas O(n²), tetapi bisa terjadi osilasi19. | Waktu konvergensi bervariasi dan bisa lambat karena masalah "count-to-infinity"20. Ketahanan | Lebih tangguh. Router yang salah hanya dapat mengiklankan biaya tautan yang salah. Setiap router menghitung tabelnya sendiri21. | Kurang tangguh. Router DV dapat mengiklankan biaya jalur yang salah, dan kesalahan ini dapat menyebar ke seluruh jaringan karena setiap router bergantung pada tabel tetangganya22.