Document

Report
Jaringan Komputer I
Materi 5
Lapis Jaringan
Lapis Jaringan (Network Layer)
Node
Link
Terminal
Jaringan
Lingkup Kerja Lapis Jaringan
Fungsi lapis 3

Memilih jalan (routing)



Default: dipilih jalan yang terpendek (Shortest Path
Algorithm) , saat ini terpendek = terkecil costnya
 Bellman-Ford
 Prim-Dijkstra
 Floyd-Warshall
RIP
BGP
Elemen Teknik Routing:
 Performansi: Hop, jarak, kecepatan, delay, cost
 Decision Time : paket, sesi
 Decision Place : terdistribusi, sentralisasi
 Informasi sumber : tidak ada, lokal, bertetangga,
sepanjang rute, semua node
 Strategi : tetap, adaptif, acak, flooding
 Waktu update routing adaptif : kontinu, periodik,
perubahan topologi, perubahan beban utama
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
2. Jarak terpendek dengan maksimum 2 arc, dst
3. Jarak terpendek dengan maksimum h arc
 SHORTEST (≤ h) path
1.
Bellman-Ford
 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
Contoh Soal Bellman-Ford:
8
4
1
2
1
2
Source
Node
4
1
2
4
3
2
5
Mencari jalur terpendek
dari Node(1) Source ke
node-node lainnya di
dalam graph
D2(1)= 1
h=1
D1(1)= 0
D4(1)= ∞
2
4
1
h=3
4
3
5
D3(2)= 2
D5(2)= 4
1
(1)
D5 = ∞
D3 = 4
D2 = 1
2
5
(1)
(3)
D4(2)= 9
h=2
D1(1)= 0
3
D2(2)= 1
(3)
D4 = 9
4
h=4
D4(4)= 8
2
4
1
2
D2(4)= 1
1
(4)
D1 = 0
3
5
D3(3)= 2
D5(3)= 4
1
Final Tree d/p
Shortest Path
4
D1(3)= 0
1
D4(3)= 8
3
2
5
D3(4)= 2
D5(4)= 4
Complexity (jumlah iterasi) algoritma B-F = Φ(N3)
Algoritma Dijkstra
 Complexity algoritma Dijkstra = Φ(N2)
 Semua jarak d/p arc harus
 Terdapat 1 set node P
positif
 Mencari jalur terpendek dari node 1 (source
node) ke setiap node lainnya didalam graph
 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
jalur terpendek dari node 1
 Step 1:
 Step 2:
Jika tidak ada hubungan, maka Dj =
i*∞€ P,
Untuk setiap
dimana: Di* = min Dj ; j € P
Set P = P U{i*}; jika P = N  stop, else
Update Dj untuk j € P
Dj = min[Dj, Di* + di*j]
Kembali ke step 1
4
4
1
2
1
2
Contoh soal:
8
1
2
4
 Inisialisasi: P = {1}
 Iterasi 1:
Step1:
Step2:
i*
D3
D4
D5
3
D1=0,D2=1,D3=4,D4=D5=∞
= 2, P={1,2}
= min(D3,D2+d23)
= min(4,1+1) = 2
= min(∞,1+8)= 9
=∞
= min(D5,D2+d25)
= min(∞, ∞)
Pilih min D  D3=2, untuk iterasi selanjutnya
2
5
8
4
1
2
Step 1:
4
 Iterasi 2:
2
1
4
1
2
3
i* = 3, P = {1,2,3}
D3 = 2, D2 = 1, D4 = 9, D5 = ∞
Step 2:
D4 = min (D4,D3+d34)
= min (9,2+∞) = 9
D5 = min (D5,D3+d35)
= min (∞,2+2)
=4
Pilih D5 untuk iterasi selanjutnya
2
5
2
4
4
2
4
i* = 5, P = {1,2,3,5}, D5 = 4
1
Update
D4 = min (9,D5+d54)
= min (9,4+4) = 8
Iterasi berakhir, karena jumlah node hanya 5.
Hasil akhir :
2
Step 1:
Step 2:
1
1
 Iterasi 3:
8
2
4
D2 = 1
4
1
1
1
Source
Node
D1 = 0
D3 = 2
D4 = 8
3
2
5
D5 = 4
3
2
5
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 sebagai 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.
Distance Vector Algorithm
 DX(Y,Z)
= jarak dari X ke Y, melalui Z
sebagai hop selanjutnya
= c(X,Z) + minwZ{D (Y,w)}
Algoritma Distance Vector
Pada semua node,X:
1.
Inisialisasi
2.
Untuk semua node bersebelahan v
3.
DX(*,v) = ∞ {* berarti untuk semua baris}
4.
DX(v,v) = c(X,v)
5.
Untuk semua tujuan, y
6.
Kirim minwXD (y,w) kesetiap tetangga
7.
loop
8.
tunggu (sampai ada perubahan cost link ke tetangga V
atau diterima update dari tetangga V)
9.
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
Segmentation And Reassembly
 Tidak setiap data (pdu) dari suatu lapis bisa
dibawa utuh oleh lapis berikutnya
 Perlu ada layanan untuk membagi data tersebut
kedalam ukuran yang bisa diterima oleh lapis
berikutnya disisi pengirim
 Dan perlu ada layanan untuk menyatukan
kembali data tersebut menjadi data utuh pada
sisi penerima
 Proses ini dinamakan : fragmentation (atau
segmentation) & reassembly
Fragmentasi
dan
Reassembly
 Header IP harus
memuat field
berikut:
 Penanda unit
data (ID)
 Panjang data
 Offset
 More
22
Jaringan Komputer I
=1480
=1480
IP
 Internet Protocol
 Protokol paling populer dijagatraya
 Kelebihan:
 Mempunyai alamat sedunia/global (tidak ada alamat
yang sama, unik) = 4 G = 2^32
 Mendukung banyak aplikasi (protokol lapis 7: FTP,
HTTP, SMNP, dll)
 De facto standar protokol lapis 3 (mulai digunakan
tanpa protokol aplikasi standar: XoIP )
Format paket IP
1
2
3
Version
4
5
6
7
8
Header length
9
10
11
12
13
14
Priority (0-7)
low
high
high
 “1”
Precedence
D
T
R
unused
Total length
Identification
D
M
Fragment offset
Time to live (seconds)
Protocol
Header checksum
Source IP address (4 Byte)
Destination IP address (4 Byte)
Option (0 word atau lebih)
Data
 64 kBData
15
16
Fungsi-fungsi Header IP
Version
Header length
Precedence
D T
R
X X
Total length
Identification
 Version (4 bit) menyatakan versi IP yang digunakan : 0100 (4) =







IPv4, memungkinkan evolusi protokol
Header length (4 bit) menyatakan panjang header IP dalam dword :
0101 (5) = 20 byte
Precedence (3 bit) =service type
Delay : D=1  low delay ; segera dikirim
Throughput : T=1  high throughput ;
Reliability : R=1  high reliability ; paket tidak boleh di drop
X = future used ; default = 0
Total length = panjang total datagram dalam ukuran byte
(datagram=paket IP)
Identification
D
M
Fragment offset
 Identification = identifikasi nomor paket IP secara unik
(berurut, dimulai random oleh protokol IP)
 Flag (3bit) yang dipakai hanya 2 bit, yaitu:
1. Don’t Fragment : D = 1  tidak boleh dilakukan
framentasi untuk paket ini
2. More Fragment : M = 1  masih ada paket berikutnya,
M = 0  potongan paket terakhir
 Fragment Offset : berisi nomor byte awal dari potongan
paket ini, contoh : FO= 20 berarti paket ini dimulai dari
byte ke 20 paket asal (paket sebelum
difragmentasi/disegmentasi)
Time to live (seconds)
Protocol
 Time to live : Membatasi lamanya paket berada dijaringan,
dalam detik atau hop, contoh : TTL=128  paket hanya
boleh ada dijaringan selama maksimum 128 detik atau hop
 Protokol : indikasi protokol lapis 4 yang akan menerima isi
data dari paket IP,
contoh :
 TCP : 06
 UDP : 17
Alamat IP
 Ada 2 jenis IP : IP standar atau IP versi 4
(sejak 1970) dan IPv6 (mulai 199x)
 IPv4 : 32 bit ≈ 4G alamat
202.134.21.3 = CA.22.15.03
 IPv6 : 128 bit ≈ 256 exa2
FF:01:07::::::::::CA:22:15:03
 2^32 bit = 1m  2^128 bit = lebar galaxy
bimasakti
Alamat IP
31
Jaringan Komputer I
IPv4
 Punya 32 bit alamat = 4G alamat
 Format DDD.DDD.DDD.DDD
 Dibagi menjadi kelas-kelas (kelompok):
 A anggota : 2G ciri
0xxxxxxx.xxxxxxxx.xxxxxxxx.xxxxxxxx
0.0.0.0 sd 127.255.255.255
 B anggota : 1G ciri
10xxxxxx.xxxxxxxx.xxxxxxxx.xxxxxxxx
128.0.0.0 sd 191.255.255.255
 C anggota : 0.5 G ciri
110xxxxx.xxxxxxxx.xxxxxxxx.xxxxxxxx
192.0.0.0 sd 223.255.255.255
Grouping IP
 Grup A anggota 2G terbagi menjadi:
 Mask : 11111111.000000000.00000000.00000000
 128 subnetwork dengan 16M host
 Grup B anggota 1G terbagi menjadi:
 mask : 11111111.11111111.00000000.00000000
 16k subnetwork dengan 64k host
 Grup C anggota 512M terbagi menjadi:
 Mask : 11111111.11111111.11111111.00000000
 2M subnetwork dengan 256 host
IP reserved
 #




10.0.0.0 - 10.255.255.255
- reserved for intranet local networks
# 127.0.0.0 - 127.255.255.255
- reserved for local loop on each computer
# 172.16.0.0 - 172.31.255.255
- reserved for intranet local networks
# 192.168.0.0 - 192.168.255.255
- reserved for intranet local networks
# 224.0.0.0 - 239.255.255.255
- used for multicast routing
Alokasi Alamat Kelas C
Alamat kelas C
Alokasi
194.0.0.0 s/d 195.255.255.255
Eropa
198.0.0.0 s/d 199.255.255.255
Amerika Utara
200.0.0.0 s/d 201.255.255.255
Amerika Tengah dan Selatan
202.0.0.0 s/d 203.255.255.255
Asia Pasifik
PR 30-4-7 dibahas 2-5-7
 Suatu jaringan dengan IP 10.14.15.xxx mask
255.255.255.240
 Pertanyaan:
 Berapa subnet di jaringan tersebut?
 Jika ingin mengirim semua anggota subnet ke 4, berapakah
alamat IP yang harus dituju?
Subnet
Teknik peminjaman bagian host untuk dijadikan bagian network sehingga
memperbanyak jumlah network dan mengurangi jumlah host
 Alasan :
 Mengurangi trafik jaringan
 Meyederhanakan managemen, lebih mudah mengidentifikasi dan
mengisolasi masalah dalam jaringan, kemudahan pengelolaan dan
pengaturan routing
 Meningkatkan performansi jaringan akibat berkurangnya trafik


10.14.64.255 mask 255.255.255.128 
00001010.00001110.01000000.11111111
11111111.11111111.11111111.10000000  mask
Hasil operasi and  10.14.64.128
Hasil operasi xor (dgn bit 0 di mask)  127
 10.14.64.255/25 : subnet 10.14.64.128 dengan host 127

10.14.64.64 mask 255.255.255.128 
00001010.00001110.01000000.01000000
11111111.11111111.11111111.10000000  mask
Hasil operasi and  10.14.64.0
Hasil operasi xor (dgn bit 0 di mask)  64
 10.14.64.64/25 : subnet 10.14.64.0 dengan host 64
 Kesimpulan : mask /25 membagi menjadi 2 kelompok
Subnet
 10.14.64.xxx/25 akan membagi menjadi 2 kelompok:
 10.14.64.0 (lokal 10.14.64.0, broadcast 10.14.64.127)
 10.14.64.128  (lokal 10.14.64.128, broadcast 10.14.64.255)
 10.14.64.xxx/26 akan membagi menjadi 4 kelompok:
 10.14.64.0 (lokal 10.14.64.0, broadcast 10.14.64.63)
 10.14.64.64  (lokal 10.14.64.64, broadcast 10.14.64.127)
 10.14.64.128 (lokal 10.14.64.128, broadcast 10.14.64.191)
 10.14.64.192  (lokal 10.14.64.192, broadcast 10.14.64.255)
IP
Subnet mask
Network number
Host
Broadcast
10.14.201.3
255.255.255.0
10.14.201.0
3
10.14.201.255
10.14.201.3
255.255.240.0
10.14.192.0
9.3
10.14.207.255
10.14.201.3
255.255.128.0
10.14.128.0.0
0.0.73.3
10.14.255.255
10.14.201.3
255.255.224.0
10.14.192.0
9.3
10.14.223.255
10.14.201.3
Ada 3
10.14.192.0
9.3
Ada 3
10.14.201.3
Ada 3
10.14.200.0
1.3
Ada 3
10.14.201.3
255.255.0.0
10.14.0.0
201.3
10.14.255.255
IP Routing Protocol
RIP (Routing Information Protocol)
 Berbasis algoritma distant vector (vektor jarak
ke tujuan)
 Dibatasi maksimum 15 hop
 Bertukar jarak vektor setiap 30 detik melalui
Response Message yang biasa juga disebut
dengan istilah advertisement
 Setiap advertisement bisa membawa informasi
routing sampai 25 tujuan
Contoh : Isi Tabel Router A
S
Network
Tujuan
Router
Selanjutnya
Jumlah Hop ke
tujuan
W
-
1
S
D
2
Y
D
3
Z
D
>3
Latihan : Isi tabel router dibawah ini
Port
add
FR0
201
X25.1 202
203
204
205
200
Eth2 200
203
202
204
205
hop
201
FR0
X25.1
202
eth2
eth1
dsl0
205
200
Port
dsl0
Eth1
Atm2
add
200
201
202
205
203
204
203
204
201
202
205
hop
atm2
204
203
Protokol Routing Lainnya
 RIP2
 Exterior Gateway Protocol (EGP)
 Border Gateway Protocol (BGP)
 BGP4
 Protocol Independent Multicast (PIM)
 Intermediate System – Intermediate
System (IS-IS)
 Next Hop Routing Protocol (NHRP)

similar documents