Protokol Routing (tugas jarkom 4)

1. RIP (Routing Information Protocol)

1. Berbasis algoritma distant vector (vektor jarak ke tujuan)

2. Dibatasi maksimum 15 hop

3. Bertukar jarak vektor setiap 30 detik melalui Response Message yang biasa juga disebut denganistilh advertisement

4.Setiap advertisement bisa membawa informasi routing sampai 25 tujuan

—RIP

2.Exterior Gateway Protocol (EGP)

3.Border Gateway Protocol (BGP)

4. BGP4

5. Protocol Independent Multicast (PIM)

6. Intermediate System – Intermediate System (IS-IS)

7. Next Hop Routing Protocol (NHRP)

Algorithma Shortest Path pada Jarkom

1.Bellman-Ford

Mencari jalur terpendek antara 1 source node ke titik-titik lainnya didalam jaringan

—Jarak dapat positif atau negatif

—Diasumsikan tidak ada cycle dengan jarak negatif

—di,j = ∞, jika (i,j) bukan arc dari graph

—Didalam algoritma B-F, yang dicari mula-mula adalah

Jarak terpendek dengan maksimum 1 arc

Jarak terpendek dengan maksimum 2 arc, dst

Jarak terpendek dengan maksimum h arc

à SHORTEST (≤ h) path

—Di(h) adalah jalur terpendek (≤h) dari node 1 (source node) ke node I

—= 0, untuk semua h

—Start : Di(0) = ∞, untuk semua I ≠ 1.

—Untuk setiap successive h ≥ 0,

Di(h+1) = minj[Dj(h) + dji], untuk semua I ≠ 1

—

—jumlah step maks = |N| - 1

—dij = jarak dari source i ke destination j

—

—dij = 0 ® i=j

—dij = ~ ® i ≠ j

—dij = 0 ® i=j

2.Algoritma Dijkstra

—Complexity algoritma Dijkstra = Φ(N2)

—Semua jarak d/p arc harus positif

—Terdapat 1 set node P

—Mencari jalur terpendek dari node 1 (source node) ke setiap node lainnya didalamgraph

—Estimasi jalur terpendek di update setiap kali, dan jika estimasi sudah mencapai actual distance, masukkan node dalam set P

—Kondisi mula:

P = {1}, D1 = 0, Dj = dij, j ≠ 1

—Step 1: Untuk setiap i* € P,

dimana: Di* = min Dj ; j € P

set P = P U{i*}; jika P = N à stop, else

—Step 2: Update Dj untuk j € P

Dj = min[Dj, Di* + di*j]

Kembali ke step 1

3. Algoritma Floyd-Warshall

— Mencari jalur terpendek diantara semua pasangan node secara bersama-sama —Jarak arc dapat positif atau negatif, tetapi tidak ada cycle dengan jarak negatif —Algoritma F-W melakukan iterasi pada set node, yang diperbolehkan sebaga intermediate nodes (titik-titik antara) didalam graph —Start dengan arc tunggal (tanpa intermediate nodes) —Selanjutnya jarak terpendek dihitung dengan batasan hanya node 1 (asumsi sebagai souce node) yang dapat digunakan sebagai intermediate node, diteruskan dengan batasan bahwa hanya node 1 dan node 2 yang dapat digunakan sebagai intermediate node, dst.

—Definisi : Dij(n) = jalur terpendek antara node i dan node j dengan batasan (ketentuan) bahwa hanya node 1,2,…..,n yang dapat digunakan sebagai intermediate nodes —Step (1): Start à Dij(0) = dij, untuk semua i,j; i≠j —Step (2): Untuk n=0,1,…,N-1 Dij(n+1) = min [Dij(n),Di(n+1)(n) + D(n+1)j(n)] untuk semua i≠j dst. Algoritma stop setelah n = N – 1, dimana N = jumlah node dalam jaringan —Kompleksitas algoritma F-W adalah Φ(N3) àkarena N step dalam algoritma F-W harus dieksekusi untuk setiap node. = jika algoritma Dijkstra diulang untuk setiap pilihan yang mungkin untuk source node.

4.Distance Vector Algorithm

ada semua node,X: Inisialisasi Untuk semua node bersebelahan v DX(*,v) = ∞ {* berarti untuk semua baris} DX(v,v) = c(X,v) Untuk semua tujuan, y Kirim minwXD (y,w) kesetiap tetangga loop tunggu (sampai ada perubahan cost link ke tetangga V atau diterima update dari tetangga V) If (c(X,V) berubah dengan d) 10. then untuk semua tujuan y: DX(y,V) = DX(y,V) + d 11. Else if (diterima update dari V dengan tujuan Y) 12. then untuk tujuan tunggal y: DX(Y,V) = c(X,V) + nilai baru 13. IF ada nilai baru minwDX(Y,w) untuk semua tujuan Y 14. then kirim nilai baru minwDX(Y,w) ke semua tetangga 15.terus menerus