Routing Algorithm* *J.F Kurose and K.W. Ross, All Rights Reserved
Industrial Engineering Faculty System Information Program 2015
Outline • Introduction • Link State • Distance Vector
Introduction Routing adalah proses dimana suatu router memforward paket ke jaringan yang dituju. Suatu router membuat keputusan berdasarkan IP address yang dituju oleh suatu paket. Algoritma routing pada suatu jaringan adalah suatu mekanisme untuk menentukan rute yang harus dilalui oleh paket yang berasal dari suatu node sumber ke node tujuan pada jaringan tersebut. Tujuan utama dari algoritma routing adalah memilih rute, yang menghubungkan node awal dengan node akhir, dengan total delay setiap paket paling minimal.
Dasar-Dasar Routing
• • • •
Router menyimpan routing table yang menggambarkan bagaimana menemukan networknetwork remote. Untuk bisa melakukan routing paket, ada hal-hal yang harus diketahui yaitu: Alamat tujuan Router-router tetangga dari mana sebuah router bisa mempelajari tentang network remote Route yang mungkin ke semua network remote Route terbaik untuk setiap network remote
Jenis Konfigurasi Routing a.
b.
c.
Routing Statis: Routing statis terjadi jika Admin secara manual menambahkan route-route di routing table dari setiap router. Routing Default: Default routing digunakan untuk merutekan paket dengan tujuan yang tidak sama dengan routing yang ada dalam table routing. Secara tipikal router dikonfigurasi dengan cara routing default ke trafik internet. Routing Dinamis : Routing dinamis adalah ketika routing protocol digunakan untuk menemukan network dan melakukan update routing table pada router. Dan ini lebih mudah daripada menggunakan routing statis dan default, yang membedakan dalam hal proses-proses di CPU router dan penggunaan bandwidth dari link jaringan
• Dua cara yang dibahas dalam membangun tabel Routing : – Static Routing • Dibangun berdasarkan definisi dari administrator • Administrator harus cermat, satu saja tabel routing salah jaringan tidak terkoneksi
– Dynamic Routing • Secara otomatis router jalur routingnya, dengan cara bertukar informasi antar router menggunakan protokol tftp • Kategori algoritma dinamik : – Distance Vector – Link State – Hybrid
Statik Routing
Statik Routing • rute atau jalur spesifik yang ditentukan oleh user untuk meneruskan paket dari sumber ke tujuan. Rute ini ditentukan oleh administrator untuk mengontrol perilaku routing dari IP. • Merupakan sebuah mekanisme pengisian tabel routing yg dilakukan oleh admin secara manual pd tiap2 router Keuntungan • Meringankan kerja prosesor yg ada pd router • Tidak ada Bandwidth yang digunakan untuk pertukaran informasi isi tabel routing antar router • Tingkat keamanan lebih tinggi vs mekanisme lainnya
Kerugian • Admin harus mengetahui informasi tiap2 router yg terhubung jaringan • Jika terdapat penambahan/perubahan topologi jaringan admin harus mengubah isi tabel routing • Tidak cocok untuk jaringan yang besar
Contoh
Routing Protokol • Routing protocol adalah komunikasi antara router-router. Routing protocol mengijinkan router-router untuk sharing informasi tentang jaringan dan koneksi antar router. Router menggunakan informasi ini untuk membangun dan memperbaiki table routingnya
Administrative Distance Pada umumnya protocol routing mempunyai struktur metric dan algoritma yang berbeda dengan protocol yang lain. Pada jaringan yang memiliki beberapa routing protocol, pertukaran informasi routing dan kemampuan untuk memilih jalur terbaik sangatlah penting. Administrative distance (AD) adalah fitur yang dimiliki oleh router untuk memilih jalur terbaik ketika terdapat dua atau lebih jalur menuju tujuan yang sama dari dua routing protocol yang berbeda. Administrative distance menyatakan “reliability” dari sebuah routing protocol. Tiap routing protocol diprioritaskan terhadap yang lain dengan bantuan besaran/nilai Administrative Distance (AD).
Pemilihan Jalur Tebaik [The Best Path] Administrative distance adalah kriteria pertama yang digunakan oleh router untuk menentukan routing protocol yang harus dijalankan, jika terdapat dua routing protocol yang menyediakan jalur untuk tujuan yang sama. AD adalah sebuah ukuran “trustworthiness” dari source of routing information. AD hanya mempunyai local significance, dan tidak melakukan advertise dalam routing update. Nilai AD yang lebih kecil, lebih dipercaya/reliable. Contoh, Jika sebuah router menerima informasi tentang jalur menuju jaringan tertentu dari Open Shortest Path First (OSPF) (default administrative distance - 110) dan Interior Gateway Routing Protocol (IGRP) (default administrative distance 100), Router akan memilih IGRP karena IGRP lebih dipercaya/reliable karena memiliki AD yang lebih kecil dibandingkan OSPF. Jika source address untuk IGRP hilang atau tidak dikenal, maka router akan memilih/menjalankan routing OSPF sampai IGRP aktif kembali.
Tabel Nilai Default Administrative Distance (AD) pada Router Cisco
A Link-State Routing Algorithm Dijkstra’s algorithm • net topology, link costs known to all nodes – accomplished via “link state broadcast” – all nodes have same info • computes least cost paths from one node (‘source”) to all other nodes – gives forwarding table for that node • iterative: after k iterations, know least cost path to k dest.’s
Notation: • c(x,y): link cost from node x to y; = ∞ if not direct neighbors
• D(v): current value of cost of path from source to dest. v
• p(v): predecessor node along path from source to v
• N': set of nodes whose least cost path definitively known
Dijkstra’s algorithm: example Step 0 1 2 3 4 5
N' u ux uxy uxyv uxyvw uxyvwz
D(v),p(v) D(w),p(w) 2,u 5,u 2,u 4,x 2,u 3,y 3,y
D(x),p(x) 1,u
2
u
2 1
x
3
w 3
1
5
z
1
y
D(z),p(z) ∞ ∞
4,y 4,y 4,y
5
v
D(y),p(y) ∞ 2,x
2
Dijkstra’s algorithm: example (2) Resulting shortest-path tree from u:
v
w
u
z x
Resulting forwarding table in u: destination
link
v x
(u,v) (u,x)
y
(u,x)
w
(u,x)
z
(u,x)
y
Distance Vector Algorithm Bellman-Ford Equation (dynamic programming) Define dx(y) := cost of least-cost path from x to y
Then dx(y) = min {c(x,v) + dv(y) } v
where min is taken over all neighbors v of x
Bellman-Ford example 5 2
u
v 2
1
x
3
w 3
1
Clearly, dv(z) = 5, dx(z) = 3, dw(z) = 3 5
z
1
y
2
B-F equation says: du(z) = min { c(u,v) + dv(z), c(u,x) + dx(z), c(u,w) + dw(z) } = min {2 + 5, 1 + 3, 5 + 3} = 4
Node that achieves minimum is next hop in shortest path ➜ forwarding table
Distance Vector Algorithm • Dx(y) = estimate of least cost from x to y • Node x knows cost to each neighbor v: c(x,v) • Node x maintains distance vector Dx = [Dx(y): y є N ] • Node x also maintains its neighbors’ distance vectors – For each neighbor v, x maintains Dv = [Dv(y): y є N ]
node x table
Dx(y) = min{c(x,y) + Dy(y), c(x,z) + Dz(y)} = min{2+0 , 7+1} = 2
from
x 0 2 7 y ∞∞ ∞ z ∞∞ ∞ node y table cost to x y z
cost to x y z from
cost to x y z
Dx(z) = min{c(x,y) + Dy(z), c(x,z) + Dz(z)} = min{2+1 , 7+0} = 3
x 0 2 3 y 2 0 1 z 7 1 0
2
x ∞ ∞ ∞ y 2 0 1 z ∞∞ ∞ node z table cost to x y z from
from
x
x ∞∞ ∞ y ∞∞ ∞ z 7 1 0
time
y 7
1
z
from
x ∞∞ ∞ y ∞∞ ∞ z 7 1 0
cost to x y z
x 0 2 3 y 2 0 1 z 7 1 0
x 0 2 3 y 2 0 1 z 3 1 0
from
cost to x y z
cost to x y z
cost to x y z
x 0 2 7 y 2 0 1 z 7 1 0
x 0 2 3 y 2 0 1 z 3 1 0
from
from
from
x ∞ ∞ ∞ y 2 0 1 z ∞∞ ∞ node z table cost to x y z
from
from
x 0 2 7 y ∞∞ ∞ z ∞∞ ∞ node y table cost to x y z
from
cost to x y z
cost to x y z
cost to x y z
x 0 2 7 y 2 0 1 z 3 1 0
x 0 2 3 y 2 0 1 z 3 1 0
from
node x table
Dx(z) = min{c(x,y) + Dy(z), c(x,z) + Dz(z)} = min{2+1 , 7+0} = 3
Dx(y) = min{c(x,y) + Dy(y), c(x,z) + Dz(y)} = min{2+0 , 7+1} = 2
time
2
x
y 7
1
z
Distance Vector: link cost changes Link cost changes: node detects local link cost change updates routing info, recalculates
distance vector if DV changes, notify neighbors
“good news travels fast”
1 4
x
y
1
50
z
At time t0, y detects the link-cost change, updates its DV, and informs its neighbors. At time t1, z receives the update from y and updates its table. It computes a new least cost to x and sends its neighbors its DV. At time t2, y receives z’s update and updates its distance table. y’s least costs do not change and hence y does not send any message to z.
Distance Vector: link cost changes Link cost changes: good news travels fast bad news travels slow - “count
to infinity” problem! 44 iterations before algorithm stabilizes: see text
Poisoned reverse: If Z routes through Y to get to X
:
Z tells Y its (Z’s) distance to X is infinite (so Y won’t route to X via Z)
will this completely solve count
to infinity problem?
60 4
x
y 50
1
z
Comparison of LS and DV algorithms Message complexity • LS: with n nodes, E links, O(nE) msgs sent • DV: exchange between neighbors only – convergence time varies
Robustness: what happens if router malfunctions? LS: – node can advertise incorrect link cost – each node computes only its own table
Speed of Convergence • LS: O(n2) algorithm requires O(nE) msgs – may have oscillations • DV: convergence time varies – may be routing loops – count-to-infinity problem
DV: – DV node can advertise incorrect path cost – each node’s table used by others • error propagate thru network
Pengukuran level daya sinyal
TERIMA KASIH
Thank you very much for your kind attention
