Chapter 2 part 2
Getting Connected (Error Detection and Reliable Transmission) Muhammad Al Makky
Pembahasan Chapter 2 • Eksplorasi perbedaan media komunikasi yang digunakan untuk mengirimkan data • Memahami masalah pada encode di atas media transmisi sehingga dapat dimengerti oleh penerima • Mendiskusikan gambaran urutan bit saat ditransmisikan melalui link ke dalam satu kesatuan pesan yang utuh yang dapat dikirim ke node tujuan akhir • Mendiskusikan teknik-teknik untuk mendeteksi kesalahan pada transmisi data dan menentukan aksi yang tepat
Pembahasan Chapter 2 (Lanj.) • Mendiskusikan persoalan tentang kehandalan link dalam menangani masalah transmisi • Pengenalan Media Access Control Problem • Pengenalan jaringan Carrier Sense Multiple Access (CSMA) • Pengenalan jaringan tanpa kabel dengan teknologi dan protokol berbeda-beda
Outline • Error Detection – Parity – Checksum – CRC (Cyclic Redundancy Check)
• Reliable Transmission – Stop and Wait – Sliding Window
Error Detection • Error bit terjadi di dalam frame – Karena interferensi elektronika dan gangguan – Atau karena pelemahan (attenuation), penyimpangan (distortion), dan gangguan (noise)
• Single Bit Error
• Burst Error
Error Detection • Attenuation
• Distortion
• Noise
Error Detection • Ide dasar pada Error Detection – Menambahkan bit ke Frame yang dapat digunakan untuk menentukan bahwa dalam suatu Frame terdapat error
• Bit tambahan – Tidak ada informasi tambahan – Diperoleh dari pesan asal menggunakan algoritma tertentu – Baik pengirim maupun penerima harus mengetahui algoritma yang dipakai r r – Pengirim m Penerima m Penerima menghitung r menggunakan m Jika cocok maka tidak ada error
Two-dimensional parity • Berdasarkan single parity bit, dengan menambahkan bit 1 tambahan ke dalam kode 7 bit untuk menggenapkan jumlah bit 1 di dalam satu byte
Two Dimensional Parity
Internet Checksum Algorithm • Checksum dilakukan sebagai komplemen sequence dari integer 16 bit • Menambahkan komplemen dengan seluruh bit isi pesan, dihitung secara aritmatika dan mengambil hasil komplemen yang terjadi sebagai hasilnya • Hasil komplemen integer 16 bit adalah yang disebut checksum • Dalam aritmatika, integer bernilai negatif (-x) maka komplemennya adalah (x)
Internet Checksum Algorithm • Contoh: terdapat -5 dan -3 dalam satu komplemen arimatika pada integer 4 bit – Jika +5 = 0101 maka −5 = 1010; dan jika +3 = 0011 maka – 3 = 1100
• Jika menambahkan 1010 dan 1100 maka didapat 0110
Contoh Algoritma Internet Checksum Algorithm uint16_t NetIpChecksum(uint16_t const ipHeader[], int nWords) { uint32_t sum = 0; /* IP headers always contain an even number of bytes. while (nWords-- > 0) { sum += *(ipHeader++); } /* Use carries to compute 1's complement sum. sum = (sum >> 16) + (sum & 0xFFFF); sum += sum >> 16; /* Return the inverted 16-bit result. return ((unsigned short) ~sum); } /* NetIpChecksum() */
*/
*/
*/
Cyclic Redundancy Check (CRC) • Mengurangi jumlah bit tambahan dan memaksimalkan proteksi • Diberikan string bit 110001, dapat diasosiasikan sebagai polinomial dalam variabel x – 1.x5+1.x4+0.x3+0.x2+0.x1+1.x0 = x5+x4+1 maka degree adalah 5. – Suatu frame dengan k bit memiliki maksimal degree adalah k-1
Cyclic Redundancy Check (CRC)
Reliable Transmission • Kombinasi antara mekanisme: – Acknowledgements (ACK) – Timeouts
• Jika pengirim tidak menerima ACK setelah beberapa waktu maka akan mentransmisikan kembali frame yang sama • Aksi menunggu dalam satuan waktu yang telah disepakati disebut timeout • Strategi menggunakan ACK dan timeout untuk mengimplementasikan pengiriman yang handal, dapat disebut Automatic Repeat reQuest (ARQ)
Stop and Wait Protocol
Stop and Wait Protocol • 1 frame on link at a time • Terdapat link dengan bandwidth 1.5 Mbps dengan nilai RTT adalah 45 ms – Link = Delay x Bandwidth = 67.5 Kb atau 8 KB – Asumsi: besar frame adalah 1 KB – Maximum Sending rate • Bits per frame Time per frame = 1024 8 0.045 = 182 Kbps • Or about one-eighth of the link’s capacity
– Untuk dapat menggunakan link secara maksimal, pengirim harus mentransmisikan hingga 8 (delapan) frame sebelum menunggu sebuah ACK
Sliding Window Protocol • Pengirim memberikan nomor urutan yang ditunjukkan dengan nomor urut untuk setiap frame • Pengirim mengelola 3 (tiga) variabel – Sending Window Size (SWS) • Batas atas jumlah frame yang dapat ditransmisikan oleh pengirim
– Last Acknowledgement Received (LAR) • Nomor urut ACK terakhir yang diterima
– Last Frame Sent (LFS) • Nomor urut frame yang terakhir ditransmisikan
Sliding Window Protocol • Penerima mengelola 3 (tiga) variabel – Receiving Window Size (RWS) • Batas atas jumlah frame yang dapat diterima
– Largest Acceptable Frame (LAF) • Nomor urutan frame tertinggi yang dapat diterima
– Last Frame Received (LFR) • Nomor urut frame yang terakhir diterima
Sliding Window Protocol • Saat frame datang dengan nomor urut “SeqNum”, maka penerima melakukan: – If SeqNum ≤ LFR atau SeqNum > LAF • Abaikan/Buang (Frame di luar batas atas penerima)
– If LFR < SeqNum ≤ LAF • Terima, lalu penerima harus memutuskan apakah mengirimkan ACK atau tidak
– Cummulative ACK • ACK penerima ditandai dengan “SeqNumToAck” bahkan walau paket dengan nomor tertinggi sudah diterima
Sliding Window Protocol • Contoh: Asumsi, LFR = 5, RWS = 4, LAF = 9 – (ACK terakhir yang dikirim oleh penerima bernomor urut no. 5)
• Jika frame 7 dan 8 datang, akan di-buffer karena masih berada dalam “receiver window” • Tapi tidak ada ACK yang akan dikirim apabila frame no.6 belum datang • Frame 7 dan 8 out of order • Frame 6 datang (telat datang karena mungkin hilang saat dikirim dan perlu ditransmisi ulang) • Sekarang penerima mengirim ACK frame no. 8, lalu mengubah LFR = 8 dan LAF = 12
Issues with Sliding Window Protocol • Negative Acknowledgement (NAK) – Penerima mengirim NAK untuk frame no. 6 saat frame no. 7 datang
• Additional Acknowledgement – Penerima mengirim Additional ACK untuk frame no. 5 saat frame no. 7 datang – Pengirim menggunakan duplikat ACK sebagai petunjuk frame yang hilang
• Selective Acknowledgement – Penerima akan mengirim ACK sesuai sengan frame yang diterima dari pada nomor urut frame tertinggi
Issues with Sliding Window Protocol • Bagaimana cara menentukan “window size” – SWS mudah dihitung • Delay Bandwidth
– RWS dapat berapa saja, 2 (dua) cara umum • RWS = 1 Tidak ada penyangga untuk frame yang datang out of order • RWS = SWS Penerima dapat menyangga frame-frame yang ditransmisikan pengirim
Issues with Sliding Window Protocol • Melayani 3 (tiga) peran: – Reliable, mengirim frame menuju link yang tidak handal – Preserve the order • Setiap frame memiliki nomor urut
– Frame control • Penerima mampu untuk menghambat pengirim agar tidak mentransmisikan frame di luar batas atas yang dapat penerima proses
