RIJAL FADILAH S.Si
Routing adalah proses dimana suatu router mem-forward paket ke jaringan yang dituju. Suatu router membuat keputusan berdasarkan IP address yang dituju oleh paket. Semua router menggunakan IP address tujuan untuk mengirim paket. Agar keputusan routing tersebut benar, router harus belajar bagaimana untuk mencapai tujuan
Layer Data Link: Internetwork merupakan kumpulan LAN atau link point-topoint atau switched networks yang dihubungkan oleh router
IP
Pada Layer IP:
IP
Ada 2 perbedaan proses dalam pengiriman datagram IP : Forwarding: Bagaimana melewatkan suatu paket dari interface input ke interface output. Routing: Bagaimana menemukan dan setup routing table (Keputusan jalur mana yang akan diambil).
PerbedaanUtama:
“IP forwarding” enable di router dan disable di host
1. Pindah paket dari antrian input
2. Periksa kebijakan, kurangi TTL
4. Tempatkan paket pada antrian output yg tepat
Proses Forwarding 3. Cocokkan tujuan paket pada data tabel
Tabel IP Forwarding Router
Tujuan Net A Net B Net C, Host 3 Default
Tujuan dapat berupa jaringan, host, atau “gateway persinggahan terakhir”
Next Hop Router 1 Direct Router 2 Router 1
Next hop dapat berupa Jaringan yang terhubung langsung atau Router pada jaringan yang terhubung langsung
Interface INT 7 INT 4 INT 3 INT 7
Interface Fisik
Statis Administrator Mengonfigurasi manual data tabel + Lebih terkendali + Mengijinkan utk forwarding berbasis tujuan
Dinamis Router bertukar informasi menggunakan ROUTING PROTOCOL yang menghitung jalur “terbaik” + Dapat secara cepat beradaptasi pada perubahan topologi jaringan
- Lambat utk beradaptasi pada jaringan yg jelek -
Algoritma terdistribusi komplek Memakan CPU, Bandwidth, Memori Sulit Debugging Protocol saat ini berbasis tujuan
Dest. Default ke upstream router
A
B R R2 R
D
R3 R
R1
R4
A B C D E default
Nxt Hop R1 Direct R3 R1 R3 R1
C
R5
E
Dest. A B C D E default
Dest.
Nxt Hop
A B C D E default
R4 R3 R3 R4 Direct R4
Nxt Hop R2 R2 Direct R5 R5 R2
Dest. A :
Nxt Hop R1 :
R2
R1 Dest.
A :
Nxt Hop
R2 :
Looping merupakan masalah Routing, bukan masalah forwarding
Konfigurasi Manual
import informasi dari Router lain
Proses Routing
Protocol-Specific Routing Table
export informasi ke Router lain
Tabel IP Forwarding Router
Routing protocol Tujuan: menetapkan jalur yg “bagus” (dari serangkaian router) melewati jaringan dari sumber ke tujuan.
5 2
A
Abstraksi dengan Graph untuk algoritma routing: Titik di graph adalah router. Garis di graph adalah link fisik. o Biaya link: delay, harga biaya, atau tingkat kepadatan.
B 2
1
D
3
C 3
1
5
F
1
E
2
• Jalur “bagus”: – Biasanya berarti biaya minimum dari suatu jalur
Untuk dapat memforward paket dengan tepat, router harus mempelajari arah/jalan ke jaringan lainnya. Ada dua jenis Routing Dynamic routing - informasi dipelajari dari router lainnya, dan routing protocol secara otomatis menyesuaikan. Static routing - network administrator mengonfigurasi secara manual informasi tentang jaringan lainnya. Hal ini dilakukan untuk mengurangi biaya dan untuk keamanan. Pada kebanyakan jaringan, static routing sering dikombinasikan dengan dynamic routing.
to: 20.2.1.2
BGP
RIP Cisco proprietary
TCP
UDP
IP
OSPF IS-IS EIGRP
(and ICMP)
Routing protocol saling bertukar informasi ttg jaringan yang dapat dijangkau antar Router
Temukan jalur dari titik awal ke semua titik yang ada yang mempunyai jumlah panjang jalur yang minimal
B 50 100
20 100
20
80
A
Source
C
30 80
20
10
20
10 10
10
10
20
30 10
D
E
16
Menentukan
jalur (route) Router tujuan
Router first-hop default router
Host tujuan
5 Host sumber 2
3
B 2
A 1
Router sumber
C
D
3 1
5 1
E
Jalur biaya terkecil
F 2
Technology : Distance Vector vs Link State Protocol Solusi untuk masalah jalur terpendek
=
Bagaimana penghitungan jalur terpendek dapat di desentralisasi dan dilaksanakan oleh banyak router yang saling bekerja sama
Data Struktur Graf jalur, titik, bobot jalur
+ Algoritma Dijkstra atau Bellman-Ford
Distance Vector
Link State
Penghitungan jalur terdistribusi.
Mendistribusikan semua link data.
Hanya menyimpan link data lokal.
Melakukan penghitungan jalur Secara lokal
RIP, EIGRP, BGP
OSPF, IS-IS, IDPR
18
Autonomous
System adalah suatu daerah di Internet yang di administrasi/diatur oleh entitas tunggal. Contoh daerah Autonomous: • Jaringan kampus • Jaringan backbone Telkom • Internet Service Provider daerah Routing
dikerjakan dengan cara yang berbedabeda dalam suatu Autonomous System (intradomain routing) dan antar Autonomous System (interdomain routing).
Ethernet
Router
Ethernet
Ethernet
Autonomous System 1
Router
Router
Router Ethernet Router
Ethernet
Autonomous System 2
Router Ethernet
Intradomain Routing
Routing di dalam suatu AS Mengabaikan Internet di luar AS Protocol untuk Intradomain routing disebut dengan Interior Gateway Protocol atau IGP. Protocol yang populer adalah o RIP (sederhana, tua) o OSPF (lebih baik)
Interdomain Routing
Routing antar AS Diasumsikan Internet merupakan kumpulan AS yang saling terhubung Normalnya, ada satu router dedicated di setiap AS yang mengangani traffic interdomain. Protocol untuk interdomain routing disebut dengan Exterior Gateway Protocols atau EGP. Routing protocol: o EGP
Ada dua dasar algoritma routing yang ditemukan di Internet. 1. Distance Vector Routing Setiap node mengetahui jarak/distance (=cost) ke tetangga-tetangganya yang secara langsung terhubung. Suatu node mengirim secara periodik suatu update daftar routing ke tetangganya. Jika semua node meng-update jaraknya, tabel routing akhirnya akan konvergen. Node baru mengumumkan dirinya sendiri ke tetangganya. 2. Link State Routing Setiap node mengetahui jarak/distance ke tetangga-tetangganya. Informasi jarak/distance (=link state) di-broadcast ke semua node dalam jaringan. Setiap node menghitung tabel routing secara independen
Distance Vector
Routing Information Protocol (RIP)
Gateway-to-Gateway Protocol (GGP)
Exterior Gateway Protocol (EGP)
Interior Gateway Routing Protocol (IGRP)
Link State
Intermediate System Intermediate System (ISIS)
Open Shortest Path First (OSPF)
Jaringan digambarkan sebagai suatu Graph: o Node terhubung dengan networks • Jaringan dapat suatu link atau LAN o Interface jaringan punya cost o Jaringan merupakan tujuan o Net(v,w) merupakan IP address suatu jaringan Untuk memudahkan notasi, terkadang awan antar node diganti dengan link sederhana. c(v,w) Net(v,w)
w
v
Net c(v,n)
Net(v,n) n
c(v,w): cost untuk transmit pada interface di jaringan Net(v,w) Net(v,w): alamat jaringan dari jaringan antara v dan w Jaringan dapat berupa link, tapi dapat juga berupa LAN RoutingTable of node v Dest
v
Net(v,w) c(v,w) Net(v,n) c(v,n)
via (next hop)
cost
w
Net n
Net
n
D(v,Net)
RoutingTable of node v Dest
Net
via (next hop)
n
cost
D(v,Net)
• Node mengirim pesan ke tetangga2 nya yang berisi entri table routing.
v
[Net , D(v,Net)]
n
•Format pesan: [Net , D(v,Net)] berarti“Biayaku untuk pergi ke Net adalah D (v,Net)”
RoutingTable of node v Dest
via (next hop)
cost
Net1
m
D(v,Net1)
Net2
n
D(v,Net2)
NetN
w
D(v,NetN)
Secara periodik, setiap node v mengirim isi tabel routingnya ke para tetangganya :
m
[Net1,D(v,Net1)]
[Net1,D(v,Net1)]
[NetN,D(v,NetN)]
[NetN,D(v,NetN)]
v
w [Net1,D(v,Net1)] [NetN,D(v,NetN)]
n
Andaikan node baru v aktif. Biaya/cost untuk mengakses jaringan yang terhubung secara langsung adalah nol: • D (v, Net(v,m)) = 0 • D (v, Net(v,w)) = 0 • D (v, Net(v,n)) = 0
RoutingTable c(v,m) Net(v,m) m
c (v,w) Net(v,w) v
via (next hop)
cost
w c(v,n) Net(v,n)
n
Dest Net(v,m)
m
0
Net(v,w)
w
0
Net(v,n)
n
0
RoutingTable Dest
(next hop)
cost
Net(v,m)
m
0
Net(v,w)
w
0
Net(v,n)
n
0
Node baru v mengirim isi tabel routing ke semua tetangganya: [n,0] [Net(v,n),0] [w,0] [Net(v,w),0]
m
via
[n,0] [Net(v,n),0] [m,0] [Net(v,m),0]
v
w [m,0] [Net(v,m),0] [w,0] [Net(v,w),0]
n
Node v menerima tabel routing dari node lain dan membuat tabel routing nya [Net1,D(m,Net1)]
[Net1,D(w,Net1)]
[NetN,D(m,NetN)]
[NetN,D(w,NetN)]
m
v
w [Net1,D(n,Net1)] [NetN,D(n,NetN)]
n
• Andaikan node v menerima pesan dari node m: [Net,D(m,Net)] [Net,D(m,Net)]
Net
m
c(v,m) Net(v,m)
v
w
n
Node v meng-update tabel routing nya dan mengirim pesan selanjutnya jika pesan mengurangi biaya route: if ( D(m,Net) + c (v,m) < D (v,Net) ) { Dnew (v,Net) := D (m,Net) + c (v,m); Update tabel routing; Kirim pesan [Net, Dnew (v,Net)] ke semua tetangga }
• Sebelum menerima pesan:
RoutingTable
[Net,D(m,Net)]
Net
m
c(v,m) Net(v,m)
Dest v
w
via (next hop)
Net
??
cost D(v,Net)
n
• Andaikan D (m,Net) + c (v,m) < D (v,Net): new
[Net,D
Net
m
c(v,m) Net(v,m)
v
RoutingTable
(v,Net)] w
[Net,Dnew (v,Net)]
n
Dest Net
via (next hop)
m
cost Dnew(v,Net)
Asumsi : - link cost 1, mis., c(v,w) = 1 - semua update berjalan simultan - awalnya, setiap router hanya tahu cost dari interface yang terhubung
10.0.3.0/24
10.0.4.0/24
.1
.1
.1
Net
via
cost
Router A
t=0: 10.0.1.0 10.0.2.0 -
0 0
t=1: 10.0.1.0 10.0.2.0 10.0.3.0 10.0.2.2 t=2: 10.0.1.0 10.0.2.0 10.0.3.0 10.0.4.0
10.0.2.2 10.0.2.2
.2
Router B Net
via
.2
Router C Net
via
0 0
t=0: 10.0.3.0 10.0.4.0 -
0 0
0 0 1
t=1: 10.0.1.0 10.0.2.0 10.0.3.0 10.0.4.0
1 0 0 1
t=1: 10.0.2.0 10.0.3.0 10.0.4.0 10.0.5.0
1 0 0 1
0 0 1 2
t=2: 10.0.1.0 10.0.2.0 10.0.3.0 10.0.4.0 10.0.5.0
1 0 0 1 2
t=2: 10.0.1.0 10.0.2.0 10.0.3.0 10.0.4.0 10.0.5.0
10.0.2.1 10.0.3.2 10.0.3.2
10.0.3.1 10.0.4.2 10.0.3.1 10.0.3.1 10.0.4.2
.1
Router D
t=0: 10.0.2.0 10.0.3.0 -
10.0.2.1 10.0.3.2
10.0.5.0/24
2 1 0 0 1
Net
via
cost
.2
cost
.2
10.0.2.0/24
cost
10.0.1.0/24
t=0: 10.0.4.0 10.0.5.0 -
0 0
t=1: 10.0.3.0 10.0.4.1 10.0.4.0 10.0.5.0 -
1 0 0
t=2: 10.0.2.0 10.0.3.0 10.0.4.0 10.0.5.0
2 1 0 0
10.0.4.1 10.0.4.1 -
10.0.3.0/24
10.0.4.0/24
.1
.1
.1
Net t=2: 10.0.1.0 10.0.2.0 10.0.3.0 10.0.4.0
t=3: 10.0.1.0 10.0.2.0 10.0.3.0 10.0.4.0 10.0.5.0
via 10.0.2.2 10.0.2.2
10.0.2.2 10.0.2.2 10.0.2.2
Router B
cost
Router A
.2
Net
0 0 1 2
0 0 1 2 3
via
.2
Router C
t=2: 10.0.1.0 10.0.2.0 10.0.3.0 10.0.4.0 10.0.5.0
10.0.2.1 10.0.3.2 10.0.3.2
1 0 0 1 2
t=3: 10.0.1.0 10.0.2.0 10.0.3.0 10.0.4.0 10.0.5.0
10.0.2.1 10.0.3.2 10.0.3.2
1 0 0 1 2
Net t=2: 10.0.1.0 10.0.2.0 10.0.3.0 10.0.4.0 10.0.5.0
t=3: 10.0.1.0 10.0.2.0 10.0.3.0 10.0.4.0 10.0.5.0
via 10.0.3.1 10.0.3.1 10.0.4.2
10.0.3.1 10.0.3.1 10.0.4.2
10.0.5.0/24
.1
Router D
2 1 0 0 1
2 1 0 0 1
Sekarang tabel routing menjadi konvergen !
Net
via
cost
.2
cost
.2
10.0.2.0/24
cost
10.0.1.0/24
t=2: 10.0.2.0 10.0.3.0 10.0.4.0 10.0.5.0
10.0.4.1 10.0.4.1 -
2 1 0 0
t=3: 10.0.1.0 10.0.2.0 10.0.3.0 10.0.4.0 10.0.5.0
10.0.4.1 10.0.4.1 10.0.4.1 -
3 2 1 0 0
Periodic Updates: Update tabel routing dikirim pada akhir periode waktu tertentu, biasanya 90 detik. Triggered Updates: Jika suatu ukuran berubah pada suatu link, router segera mengirim suatu update tanpa menunggu berakhirnya suatu periode update. Full Routing Table Update: Sebagian besar protokol distance vector routing mengirim tetangganya semua tabel routing (tidak hanya entry yang berubah). Route invalidation timers: Isi tabel routing menjadi invalid jika tidak di-refresh. Biasanya nilai untuk invalidate suatu entry adalah jika tidak ada update yang diterima setelah 3-6 periode update.
Protokol
intradomain yang sederhana Implementasi langsung dari Distance Vector Routing Setiap router mengumumkan distance vector nya setiap 30 detik (atau ketika tabel routing berubah) ke semua tetangganya RIP selalu menggunakan 1 sebagai ukuran link Perhitungan maximum hop adalah 15, dengan “16” adalah “” Route akan timeout (diset ke 16) setelah 3 menit jika tidak diupdate
RIP
membutuhkan waktu lama untuk stabil
o Bahkan untuk jaringan kecil, RIP membutuhkan
beberapa menit sampai tabel routing tetap/settle setelah perubahan RIP
mempunyai semua masalah yang ada pada algoritma distance vector Maximum path pada RIP adalah 15 hop
