Jaringan Komputer (IF8505) Data link layer
Materi • • • • • •
Prinsip dasar Peran data link layer Framing Error handling Flow control Contoh: HDLC, PPP
2
Materi • Prinsip dasar • • • • •
Peran data link layer Framing Error handling Flow control Contoh: HDLC, PPP
3
Prinsip dasar (1) • Masalah utama dalam komunikasi data: realibility. Sinyal yang dikirim melalui medium tertentu dapat mengalami pelemahan, distorsi, keterbatasan bandwidth • Data yang dikirim dapat menjadi rusak, hilang, berubah, terduplikasi • Tugas data link layer adalah menangani kerusakan dan hilangnya data antar 2 titik komunikasi yang terhubung oleh satu medium transmisi fisik 4
Prinsip dasar (2)
A
x
data
B
• A mengirim data ke B. Jalur antara A dan B tidak reliable, sehingga mungkin ada data yang rusak/hilang. • Bagaimana menjamin transmisi data A ke B tetap reliable? 5
Prinsip dasar (3)
A
x
data
B
• A mengirim data yang panjang ke B. Data dibagi menjadi frame, sehingga kerusakan sebuah frame tidak merusak keseluruhan data. • Bagaimana B dapat mendeteksi bahwa frame yang dikirim A mengalami kerusakan? • A menambahkan error check bits ke frame, sehingga B dapat memeriksa frame dan menentukan apakah telah terjadi perubahan
6
Prinsip dasar (4)
A
x
data
B
• Bagaimana A mengetahui data yang dikirimnya telah diterima B? • B dapat mengirimkan ack/pemberitahuan jika data diterima dengan benar, dan nak/pemberitahuan data salah jika data rusak • A dapat mengirimkan ulang frame yang rusak 7
Prinsip dasar (5) • Mengapa frame dapat hilang? – Bagian alamat/id/header mengalami kerusakan, sehingga frame tidak dikenali – Temporer disconnection
• Apa yg terjadi jika frame dapat hilang? – B tidak mengetahui ada pengiriman dari A, A menunggu ack dari B – B mengirimkan ack namun hilang di jalan. A menunggu ack dari B
8
Prinsip dasar (6)
A
x
data
B
• A harus memiliki timer, yang akan mengirim ulang jika tidak menerima kabar dari B • Jangka waktu timeout harus diatur. – Jika timeout terlalu cepat, A akan mengirimkan ulang sebelum ack dari B tiba. – Jika timeout terlalu lama, A akan menunggu terlalu lama jika ada frame yg hilang 9
Prinsip dasar (7)
A
x
data
B
• • • •
A mengirim frame 1 A mengalami timeout, dan mengirimkan ulang frame 1 A menerima ack, melanjutkan mengirim frame 2 A menerima ack kedua untuk frame 1, namun dianggap sebagai ack untuk frame 2 (error) • A harus memberikan frame number, sehingga B dapat memberikan ack spesifik untuk frame number tertentu 10
Materi • Prinsip dasar
• Peran data link layer • • • •
Framing Error handling Flow control Contoh: HDLC, PPP
11
Peran data link layer • Physical layer: mengkodekan data menjadi sinyal yang dikirim melalui medium transmisi • DL menangani kesalahan transmisi, dan menyediakan layanan ke network layer berupa: • • • •
Error control, error detection Flow control Link management Medium access
12
Services Provided to Network Layer
(a) Virtual communication. (b) Actual communication.
13
Services Provided to Network Layer (2)
Placement of the data link protocol. 14
Materi • Prinsip dasar • Peran data link layer
• Framing • Error handling • Flow control • Contoh: HDLC, PPP
15
Framing • DL melakukan framing untuk: • Mengurangi kemungkinan error • Menyesuaikan dengan physical layer • Kapasitas buffer penerima terbatas
• Teknik framing: • • • •
Character count Flag byte – byte stuffing Flag bits – bit stuffing Physical layer coding violation
16
Framing
Relationship between packets and frames. 17
Framing – character count • Setiap frame diawali dengan field yang menyatakan panjang frame • Jika field ini rusak, maka frame tidak dapat dikenali lagi
A character stream. (a) Without errors. (b) With one error. 18
Framing : flag byte • Awal dan akhir frame ditandai dengan byte(s) khusus • Byte penanda dapat merupakan simbol yang sama atau berbeda • Masalah: kode byte(s) yang digunakan dapat muncul di dalam data yang terkirim, sehingga dapat mengakibatkan kesalahan penentuan frame • Solusi: byte stuffing, mengganti byte serupa pada data dengan simbol lain 19
Framing : flag byte
(a) A frame delimited by flag bytes. (b) Four examples of byte sequences before and after stuffing. 20
Framing : flag bits • Serupa dengan flag bytes, namun menggunakan bit • Lebih cocok untuk data biner • Misal: flag: 01111110 • Pengirim: setiap muncul 5 bit 1 berurutan, tambahkan bit 0 • Penerima: setiap menerima 5 bit 1 berurutan: – Bit berikutnya 0: hapus – Bit berikutnya: 10: end-of-frame – Bit berikutnya: 11: error 21
Framing : flag bits
Bit stuffing (a) The original data. (b) The data as they appear on the line. (c) The data as they are stored in receiver’s memory after destuffing. 22
Materi • Prinsip dasar • Peran data link layer • Framing
• Error handling • Flow control • Contoh: HDLC, PPP
23
Error Detection and Correction • Umumnya penanganan error transmisi dilakukan pada data link layer. Error control dapat pula dilakukan pada layer lain (physical/higher layer) • Error dapat diperbaiki dan dideteksi dengan menggunakan data redundant/tambahan pada setiap pengiriman data • Jenis error: • Single bit error: hanya sebuah bit yang berubah. Disebabkan oleh white noise • Burst error: sederetan bit-bit mengalami error. Disebabkan oleh impulse noise • Makin tinggi data rate, makin besar efeknya 24
Error control • Ada 2 teknik yang digunakan: • Error-Detecting Codes • Error-Correcting Codes
• Error correcting codes memerlukan data redundant lebih besar dibandingkan dengan error detecting codes 25
Error detection: parity bit • Menambahkan sebuah bit pada setiap pengiriman sejumlah bit, sehingga jumlah bit bernilai 1 selalu genap/ganjil. • Parity bit dapat mendeteksi kesalahan 1 bit atau kesalahan bit dalam jumlah ganjil, namun tidak dapat mendeteksi kesalahan dalam jumlah genap
26
Error detection: CRC • Cyclic redundancy check (CRC) adalah method yang umum digunakan untuk mendeteksi error • CRC beroperasi pada sebuah frame/block. Setiap block berukuran m bit yang akan dikirim akan dihitung CRC checksumnya (berukuran r bit), kemudian dikirim bersama2 dengan frame (dengan ukuran m+r bit). • Pada sisi penerima, penerima akan menghitung CRC checksum pada frame yang diterima, dan dibandingkan dengan checksum yang diterima, jika berbeda, berarti frame rusak 27
CRC • CRC menggunakan prinsip modulo bilangan. • Data dianggap sebagai sebuah bilangan, dan untuk menghitung checksum, sama dengan menambahkan digit untuk data dengan digit untuk checksum (berisi 0) kemudian dibagi dengan pembilang tertentu, dan sisa pembagiannya menjadi checksum untuk data tsb • Tergantung pemilihan bilangan pembagi, CRC dapat mendeteksi single-bit error, double bit error, error berjumlah ganjil, burst error dengan panjang maks r • Bilangan pembagi disebut sebagai generator
28
CRC – modulo arithmetic • Operasi penambahan dan pengurangan = XOR 1011 1100
1100
1010
1010
0110
+
0110
101
100100 101
-
011 000 110 101 110 101 11
29
CRC • Contoh: data memiliki m bit – 1001, m = 4
• Generator memiliki panjang r bit – 101, r = 3
• Tambahkan r-1 bit 0 ke data: – 100100
• Bagi bilangan ini dengan generator, sisanya (11) adalah checksum • Tambahkan checksum ke data asal: • 100111
1011 101
100100 101 011 000 110 101 110 101 11
30
CRC • Pada sisi penerima, cukup membagi data yang diterima dengan generator. Jika sisanya bukan 0, berarti terjadi kesalahan • Jika sisanya 0, berarti tidak terjadi kesalahan, sesuai dengan kriteria generator yang digunakan
1001 101
101111 101 001 000 011 000 111 101 10
31
Hamming distance • Jumlah bit yang berbeda antara dua buah kode disebut sebagai hamming distance – 1110 dan 1111 memiliki 1 bit yang berbeda: d=1 – 1010 dan 1100 memiliki 2 bit yang berbeda: d=2
• Jika setiap kode yang valid memiliki perbedaan minimum h bit, maka setiap kesalahan yang < h bit dapat dideteksi • Kode yang error dapat diperbaiki jika ia memiliki jumlah perbedaan yang lebih sedikit ke kode valid tertentu • Untuk memperbaiki d bit error, diperlukan jarak minimum antar kode valid 2d+1
32
Hamming distance • Untuk mengkoreksi 1 bit error, diperlukan
2r ≥ 1 + m + r r=jumlah bit untuk error detection m=jumlah bit kode asal
• Dengan metode Hamming, check bits ditambahkan pada posisi bit pangkat 2: 1, 2, 4, 8 dst • Setiap bit berkontribusi kepada checkbit pembentuknya: 11=1+2+8
r
2r
m
1
2
0
2
4
1
3
8
4
4
16
11
5
32
26
6
64
57
7
128
120
8
256
247
33
Error-Correcting Codes
Use of a Hamming code to correct burst errors. 34
Materi • • • •
Prinsip dasar Peran data link layer Framing Error handling
• Flow control • Contoh: HDLC, PPP
35
Flow control • Mengendalikan aliran transmisi data, sehingga pengirim tidak membanjiri penerima • Dapat dilakukan pada layer data link maupun layer di atasnya – Stop and wait protocol – sliding window
36
Karakteristik channel transmisi • bit rate: jumlah bit yang dikirim setiap satuan waktu • transmission delay/latency: waktu yang diperlukan sebuah bit untuk mencapai tujuan • error rate: probabilitas terjadinya kesalahan saat transmisi • transmission time: waktu yang diperlukan untuk mengirim sebuah frame. Untuk frame dengan ukuran L, maka transmission time=L/bit rate 37
Stop and wait protocol • mengirim sebuah frame pada setiap saatnya, dan menunggu konfirmasi penerima (ACK) sebelum mengirimkan frame berikutnya frame ack frame ack
38
Stop and wait protocol • utilisasi kanal rendah: setiap pengiriman frame memerlukan waktu: transmission time+2*latency ttrans U= ttrans + 2 * t prop • Jika latency jauh lebih besar dari transmission time, maka utilisasinya akan sangat rendah – contoh: pada 1 Mbps link antara stasiun bumi dan satelit dengan jarak 36 km. • t trans untuk 8000 bit frame: 8000/106=8ms • latency=36km/3X108=120ms 39
sliding window protocol • pengirim dapat mengirim hingga w (ukuran window) buah frame tanpa harus menerima konfirmasi terlebih dahulu • penerima harus memiliki buffer yang mampu menampung n buah frame frame • frame memiliki nomor ack identitas (sequence number) • ack menyatakan frame ack terakhir yang diterima sesuai urutan 40
sliding window protocol • utilisasi kanal: – jika w x t trans > 2 x latency, maka dapat dicapai utilisasi 100% (pengirim dapat melakukan pengiriman frame secara kontinu – jika w x t trans < 2 x latency:
U=
w * ttrans ttrans + 2 * t prop
41
sliding window protocol • window pengirim: menyatakan frame yang telah dikirim namun masih belum menerima ack. Setiap menerima ack, batas bawah akan digeser. Setiap mengirimkan frame baru, batas atas akan bergeser. Pada unreliable link, frameframe ini harus disimpan pada buffer pengirim • window penerima: menyatakan frame yang dapat diterima. Setiap menerima frame pada batas bawah, window akan bergeser 42
sliding window protocol
0
7
1
6
4
1
6
2 5
0
7
2 5
3
4
3
window penerima
window pengirim
43
ARQ • konfirmasi/ack untuk flow control digunakan pula untuk error control: positive ack berarti data telah diterima dengan benar, negative ack berarti frame diterima rusak. • pengirim menggunakan timeout untuk pengiriman ulang frame yg belum mendapat ack, sehingga pengiriman ulang dilakukan secara otomatis, disebut sebagai protokol ARQ (automatic repeat request) 44
stop and wait ARQ • disebut juga sebagai PAR protocol (Positive Acknowledgment/Retransmission) • one bit sliding window ARQ • ACK dapat dititipkan pada frame data, disebut sebagai piggybacking • prinsip kerja: – pengirim mengirim frame, lalu menunggu ack – jika terjadi timeout, frame dikirim ulang – penerima mengabaikan frame yang terduplikasi (namun tetap mengirimkan ack) – penerima mengabaikan frame yang rusak 45
Protocol Definitions
Continued Æ Some definitions needed in the protocols to follow. These are located in the file protocol.h. 46
Protocol Definitions (ctd.)
Some definitions needed in the protocols to follow. These are located in the file protocol.h. 47
A One-Bit Sliding Window Protocol
Continued Æ
48
A One-Bit Sliding Window Protocol (ctd.)
49
A One-Bit Sliding Window Protocol (2)
Two scenarios for protocol 4. (a) Normal case. (b) Abnormal case. The notation is (seq, ack, packet number). An asterisk indicates where a network layer accepts a packet. 50
Go Back N ARQ • sliding window dengan window size pengirim N, window size penerima 1 • pengirim menyimpan semua frame yang belum mendapat ACK pada buffer • jika tidak ada error, penerima akan mengirim ACK dengan nomor frame terakhir yang telah diterima berurutan • jika terjadi error, penerima akan menolak frame hingga menerima frame yang memiliki nomor yang sesuai dengan yang diinginkan. Pengirim akan timeout dan mengirimkan ulang semua frame pada buffer • variant: saat menerima frame error, penerima mengirimkan NAK/REJ.
51
A Protocol Using Go Back N
Pipelining and error recovery. Effect on an error when (a) Receiver’s window size is 1. (b) Receiver’s window size is large. 52
Sliding Window Protocol Using Go Back N
Continued Æ
53
Sliding Window Protocol Using Go Back N
Continued Æ
54
Sliding Window Protocol Using Go Back N
Continued Æ
55
Sliding Window Protocol Using Go Back N
56
Sliding Window Protocol Using Go Back N (2)
Simulation of multiple timers in software. 57
selective repeat • sliding window dengan window size pengirim dan penerima > 1 • penerima dapat menerima frame yang tidak berurutan, sepanjang masih berada dalam window penerima. • saat menerima frame rusak, penerima akan mengirim pesan SREJ berisi nomor frame yang rusak, dan pengirim akan mengirim ulang hanya frame tersebut saja 58
selective repeat • mengurangi retransmisi, sehingga utilisasi kanal tinggi • memerlukan buffer pada pengirim dan penerima • lebih kompleks, sehingga jarang digunakan • diterapkan pada komunikasi yang memiliki latency tinggi, seperti link satelit
59
A Sliding Window Protocol Using Selective Repeat
Continued Æ
60
A Sliding Window Protocol Using Selective Repeat (2)
Continued Æ
61
A Sliding Window Protocol Using Selective Repeat (3)
Continued Æ
62
A Sliding Window Protocol Using Selective Repeat (4)
63
A Sliding Window Protocol Using Selective Repeat (5)
(a) Initial situation with a window size seven. (b) After seven frames sent and received, but not acknowledged. (c) Initial situation with a window size of four. (d) After four frames sent and received, but not acknowledged. 64
Protocol Verification
• Finite State Machined Models • Petri Net Models
65
Finite State Machined Models
(a) State diagram for protocol 3. (b) Transmissions. 66
Petri Net Models A Petri net with two places and two transitions.
67
Petri Net Models (2)
A Petri net model for protocol 3. 68
Materi • • • • •
Prinsip dasar Peran data link layer Framing Error handling Flow control
• Contoh: HDLC, PPP
69
Example Data Link Protocols • HDLC – High-Level Data Link Control • The Data Link Layer in the Internet
70
High-Level Data Link Control Frame format for bit-oriented protocols.
71
High-Level Data Link Control (2)
Control field of (a) An information frame. (b) A supervisory frame. (c) An unnumbered frame. 72
The Data Link Layer in the Internet
A home personal computer acting as an internet host. 73
PPP – Point to Point Protocol
The PPP full frame format for unnumbered mode operation. 74
PPP – Point to Point Protocol (2)
A simplified phase diagram for bring a line up and down. 75
PPP – Point to Point Protocol (3)
The LCP frame types. 76
