Minggu, 15 Desember 2013

Deteksi dan Koreksi Kesalahan ( Error )

A. Kontrol Kesalahan
Bagaimana meyakinkan semua frame akan dikirimkan dengan segera ke network layer di mesin tujuan dengan urutan yang benar ?. Beginilah caranya, Cara yang umum untuk menjamin pengiriman reliabel adalah memberikan pengirim beberapa umpan balik tentang apa yang terjadi di sisi lain dari saluran. Umumnya protokol meminta penerima untuk mengirimkan kembali frame-frame kontrol khusus yang berkaitan dengan acknowledgement positif atau negatif tentang frame yang datang. Bila pengirim menerima acknowledgement positif, maka pengirim akan mengetahui bahwa frame telah sampai dengan baik. Sebaliknya, acknowledgement negatif baerarti sesuatu yang salah, maka frame harus ditransmisikan ulang.
Kemungkinan masalah lain bisa muncul karena berasal dari hardware, dimana frame bisa musnah sama sekali. Dalam kasus ini, penerima tidak akan bereaksi sama sekali, karena tidak memiliki alasan untuk bereaksi. Kemungkinan ini berkaitan dengan pemakaian timer kedalam data link layer.
Pada saat pengirim mentransmisikan sebuah frame, pengirim juga mengaktifkan timer. Timer akan mati setelah melalaui interval yang cukup panjang bagi frame untuk mencapai mesin yang dituju, diproses disana, dan acknowledgement akan kembali sebelum timer habis. Akan tetapi, bila salah satu frame atau acknowledgment hilang, timet akan segera berhenti, memperingatkan pengirim akan terjadinya maslah penting.
Penyelesainnya adalah dengan mengirimkan kembali frame. Tetapi, bila frame dikirimkan kembali bebrapa kali terdapat bahaya yaitu penerima akan menerima dua kali atau lebih frame yang sama, dan meneruskannya ke network layer lebih dari satu kali. Untuk menjaga terjadinya hal ini, umumnya perlu diberikan nomor urut yang keluar sehingga penerima dapat membedakan transmisi ulang dari frame aslinya. Dua strategi dasar  mengenai kesalahan, yaitu:
1.  Menggunakan kode-kode pendeteksi kesalahan. 
 Yaitu dengan melibatkan redundansi secukupnya untuk menarik kesimpulan bahwa       suatu kesalahan telah terjadi, dan membiarkannya untuk meminta pengiriman ulang
2.  Menggunakan Kode-Kode pengkoreksian Kesalahan
Yaitu dengan melibatkan informasi redundan secukupnya bersama-sama dengan setiap blok data yang dikirimkan untuk memungkinkan penerima menarik kesimpulan tentang apa karakter yang ditransmisikan yang seharusnya ada.



B. Deteksi Kesalahan ( Error )

Deteksi error menambahkan bit tambahan  pada akhir setiap message (redundancy bit) oleh data link layer dari sender. Data pendeteksi dihitung berdasarkan beberapa perhitungan matematik yang dilakukan pada mesaage. Secara umum jika data yang terkirim mempunyai error yang besar maka semakin besar pula koreksinya. Walaupun proteksi meningkat, throughput dari transmisi data yang sebenarnya berkurang. Kapasitas yang tersedia untuk menstranmisi data actual berkurang karena adanya penambahan ruang yang digunakan untuk mentransmit data penedeteksi. Efisisensi dari  throughput bervariasi secara berkebalikan sebagai jumlah yang diinginkan oleh deteksi error dan koreksi ditingkatkan.
Deteksi Error dapat dibedakan menjadi tiga metode, yaitu :
1.    Vertical Redudancy Check (VRC)
2.    Longitudinal Redundancy Checking (LRC)
3.    Polinomial Checking, yang terdiri dari dua metode, yaitu :
a.    Checksum
b.    Cyclical Redundancy Chek (CRC)

B.1 Vertical Redundancy Check
Setiap   karakter  yang  dikirimkan   (7  bit) diberi  1  bit pariti. Bit pariti ini  diperiksa oleh penerima untuk mengetahui apakah karakter yang  dikirim benar atau salah. Cara ini hanya dapat melacak 1 bit dan berguna melacak kesalahan  yang  terjadi pada pengiriman  berkecepatan  menengah, karena kecepatan tinggi lebih besar kemungkinan terjadi kesalahan  banyak  bit.

Kekurangan : bila ada 2 bit yang terganggu ia tidak dapat melacaknya karena paritinya akan benar.
Contoh :                                
ASCII huruf "A" adalah 41h
  100 0001      ASCII 7 bit
1100 0001       ASCII dengan pariti ganjil
0100 0001       ASCII dengan pariti genap
Akibatnya huruf "A" kode ASCII dalam Hex :
- 41  bilamana pariti genapl
- A1 bilamana pariti ganjil


B.2 Longitudinal Redundancy Check / LRC
LRC untuk  data dikirim secara blok. Cara  ini seperti  VRC hanya saja penambahan  bit  pariti tidak saja pada akhir karakter tetapi juga pada akhir  setiap blok karakter  yang  dikirimkan.Untuk setiap bit dari seluruh blok karakter ditambahkan 1 bit pariti termasuk juga bit pariti dari masing-masing karakter.Tiap blok mempunyai satu karakter khusus  yang disebut Block Check Character (BCC) yang dibentuk dari bit uji. dan dibangkitkan dengan cara sebagai berikut :
"Tiap bit BCC merupakan pariti dari semua  bit dari blok yang mempunyai nomor bit yang sama. Jadi  bit 1 dari BCC merupakan  pariti  genap dari semua bit 1 karakter yang ada pada  blok tersebut, dan seterusnya"
Kerugian : terjadi overhead akibat penambahan  bit pariti per 7 bit untuk karakter.
B.3  Polynomial Checking 
          Metode ini menambahkan sebuah karakter atau susunan karakter pada akhir sebuah message berdasar pada algoritma matematika. Dua teknik Polynomial Checking yang sangat populer adalah Checksum dan Cyclical Redundancy (CRC). 
B.3.1 Checksum 
         Dengan teknik checksum, sebuah checksum ditambahkan pada akhir dari sebuah message. Receiver menghitung checksumnya dengan cara yang sama dan membandingkannya dengan checksum yang ditransmisi sender. Jika dua nilai tersebut sama, maka message diduga tidak ada error.Sebagai contoh untuk checksum dari 8 bit data 10101001 00111001 maka proses checksumnya adalah sebagai berikut :
v  Sender
  • Checksum of 8 bits
  • Data
Ü10101001 00111001
Addition using one’s complement
10101001
00111001
Sum              11100010
Checksum    00011101
Pattern sent
U10101001 00111001 00011101
v  Receiver
  • Received data
10101001 00111001 00011101
Addition using one’s complement
10101001
00111001
00011101
Sum                    11111111
Complement       00000000
 



Kelemahan dari metode checksum ini adalah tidak dapat mendeteksi error jika terdapat satu atau lebih segmen bit yang rusak dan bit yang berhubungan atau bit yang berlawanan nilainya pada segmen kedua juga mengalami kerusakan. Checksum mendeteksi sampai 95% dari error, tetapi tidak dapat memperbaiki error.
B.3.2 Cyclical Redundancy Check (CRC)
         Metode CRC merupakan metode yang dapat menangani deteksi error yang paling baik diantara metode-metode yang telah dibahas sebelumnya. Metode ini pada prinsipnya menggunakan pembagian bilangan biner dengan CRC checker dan pembagian biner dengan CRC generator. Operasi ini didasarkan atas pembagian deretan bit  dengan sebuah fungsi khusus. Hasil bagi pembagian diabaikan. Sisanya disalurkan  sebagai BCS (Block Check  Sequence).Fungsi khusus tersebut disebut generator polynominal.

  Sifat dari polynomial adalah :  
1. Tidak dapat dibagi dengan x
2. Dapat dibagi dengan x + 1
Kemampuan dari CRC adalah :
1. Dapat mendeteksi semua burst error yang mengakibatkan jumlah bit ganjil
2. Dapat mendeteksi semua burst error yang panjangnya kurang dari atau sama dengan pangkat dari polynomial. 
3. Mendeteksi dengan burst error yang mempunyai  mempunyai pangkat yang lebih besar atau sama dengan pangkat dari polynomial.


C.       Koreksi Error

Koreksi error dapat dibedakan menjadi C.1 Retransmissiondua metode, yaitu :
1.Retransmission
a.          Stop and Wait ARQ (Automatic Repeat Request)
b.          Continuous ARQ
2.Forward Error Corection
1. Bose-Chaudhuri Algoritm
2. Hagelbarger Algoritm
3. Hamming Algoritma

C.1 Retransmission
    Metode koreksi erros yang paling sederhana, paling efektif, tidak mahal, dan yang  paling umum digunakan adalah metode retransmission. Dengan metode ini reciver yang mendeteksi sebuah error sederhana dapat meminta sender untuk mentransmisi ulang message sampai message yang diterime receiver tanpa error. Ini sering disebut Automatic Repeat request (ARQ). Ada dua type ARQ yaitu :

a.      Stop and Wait ARQ
Dengan metode Stop and Wait ARQ sender menghentikan dan menunggu respon dari receiver setelah mengirimkan message atau paket data. Setelah menerima message atau paket data receiver mengirimkan acknowledgment (ACK), jika message yang diterima tanpa error atau receiver mengirimkan negative acknowledgment (NAK) jika message yang diterima mengandung error. Jika yang dikirimkan adalah NAK, sender mengirim ulang data sebelumnya. Sedangkan jika ACK sender mengirimkan message selanjutnya. Stop and wait ARQ adalah half duplex transmission.

b.     Continuous ARQ
Dengan continuous ARQ sender tidak menunggu acknowledgment setelah mengirimkan message dan langsung mengirimkan message yang berikutnya. Ketika message sedang ditransmisikan sender menganalisa arus datangnya acknowledgment. Jika yang diterima adalah NAK sender mengirim ulang message yang dibutuhkan. Paket data yang ditransmisikan tersebut kemungkinan hanya mengandung satu error. Contnuous ARQ adalah Full Duplex Transmission.
  C.2. Forward Error Correction 
         Forward Error Correction menggunakan kode-kode yang mengandung redundant yang cukup untuk mengatasi error-error dengan mendeteksi dan mengoreksi error tersebut pada akhir pengiriman message tanpa transmisi ulang dari message asli. Terdapat 3 algoritma koreksi error yang digunakan dalam metode forward error correction, yaitu : 
C.2.1 Algoritma  Bose – Chaudhuri
Algoritma Bose –Chaudhuri menggunakan 10 bit check untuk setiap 21 bit data dan mampu menkoreksi semua error bit ganda dan mendeteksi sampai 4 bit error yang berurutan.
C.2.2 Algoritma Hagelbarger
Algoritma Hagelbalger dapat mengkoreksi samapi 6 bit error yang berurutan jika group dari bit error diikuti sedikitnya 19 valid bit data, sebelum bit error yang lebih banyak terjadi.
C.2.3 Algoritma Hamming Code
Algoritma Hamming mempunyai 7 bentuk bit, yang mampu menkoreksi error single bit pada setiap karakter.