Assignment About Flow Control and Selective Repeat ARQ

[fajar.purnama]

Note

This is my undergraduate assignment that I translated to English myself (Bahasa Indonesia dibawah / Indonesian below) in the Data Communication course where my assignment is to write an essay on flow control, error detection and control, and selective repeat ARQ. Apart from me, this group consists of I Gede Ariana, I Made Dwi Angga Pratama, I Putu Arie Pratama, Yulianti Murprayana, I Wayan Alit Wigunawan, I Gusti Made Widiarsana, I Nym Apriana Arta Putra, Muhammad Audy Bazly, I Kadek Agus Riki Gunawan, Muhamad Nordiansyah. This task has never been published anywhere and we as the authors and the copyright holders license this task customized CC-BY-SA where anyone can share, copy, republish, and sell on condition to state our name as the author and notify that the original and open version available here.

Chapter 1 Introduction

1.1 Background

The development of computer technology is increasing very rapidly, this can be seen in the 80s that computer networks are still a puzzle that academics want to answer, and in 1988 computer networks began to be used in universities, companies, and now. Entering this millennium era, especially WWW (World Wide Web) has become the daily reality of millions of people on this earth.

In addition, network hardware and software have really changed, at the beginning of its development almost all networks were built from coaxial cables, now many of them are built from fiber optics (fiber optics) or wireless communication.

With the development of computer and communication technology, a single computer model that serves all the computing tasks of an organization has now been replaced by a collection of computers that are separate but interconnected in carrying out their duties, such a system is called a computer network.

Two computers are said to be interconnected if they can exchange information. The form of connection does not have to go through copper wire alone but can use optical fiber, microwave, or communication satellites.

In a data communication, data packets are sent through a certain medium, there will always be a difference between the sent signal and the received signal. This difference can result in an error or error in the data packet sent so that the data cannot be read properly by the recipient. To avoid errors or errors in the data packets sent, error detection (error checking), error correction (error correction) and error control (error control) are required. In error control, there are three methods that are often used in data communication, namely stop and wait requests, go back N requests, and selective requests. Error control includes the following mechanisms: ACK/NAK, timeout, and sequence number. In error control, the following processes occur: error detection, acknowledgment, transmission after timeout, and negative acknowledgment.

1.2 Problem

The formulations of the problems raised in this paper are as follows:

1. What is flow control?
2. What is error detection and correction and how to minimize it?
3. What is Selective Repeat ARQ?

1.3 Objective

The objectives of this paper are as follows:

1. Able to define the meaning of flow control.
2. Able to provide a definition of the meaning of error detection and correction, and how to minimize errors that occur.
3. Able to explain the definition of Selective Repeat ARQ.

1.4 Scope of Material

In this assignment, the scope discussed by the author is only limited to the issues discussed, which is limited to Selective Repeat ARQ in a data communication network, and also to provide an overview to readers about the process of controlling errors in data communication.

Chapter 2 Discussion

The purpose of error control is to deliver error-free frames in the correct order to the network layer. The technique commonly used for error control is based on two functions, namely:

1. Error detection, usually using the CRC (Cyclic Redundancy Check) technique.
2. Automatic Repeat Request (ARQ), when an error is detected the sender asks to resend the frame where an error occurs.

Meanwhile, error control is divided into three, namely:

1. Manual Error Control. For example, if we make a mistake in typing we correct it by deleting the wrong character, for example with the delete or backspace key.
2. Echo Checking. The same procedure is used when a terminal is connected to a remote computer, say using an analog PSTN and a modem. In addition, each character entered is displayed directly on the display terminal, the first time it is transmitted to the remote computer. The remote computer then reads and stores the characters and retransmits them to the terminal that displays them. If it is different from what has been entered the user can restart transmission for erasing incorrect characters.
3. Automatic Repeat Request. Consists of idle requests and continuous requests. We will discuss more about continuous requests, especially selective repeat.

2.1 Flow Control

Flow control is a technique for ensuring that a sending station does not flood the receiving station with data. The receiving station will typically provide a data buffer of a specified length. When the data is received, it has to do some work before it can clear the buffer and prepare for the next data reception.

A simple form of flow control known as stop and wait, it works as follows. The recipient indicates that it is ready to receive data by sending a poll or responding with select. The sender then sends the data.

This flow control is regulated/managed by Data Link Control (DLC) or commonly referred to as Line Protocol so that the sending and receiving of thousands of messages can occur in the shortest possible time. The DLC must move data in efficient traffic. Communication lines should be used as level as possible, so that no station is idle while the other stations are saturated with excess traffic. So flow control is a very critical part of a network. The following shows the Time Flow Control Diagram when communication occurs in conditions without errors and errors. Flow control mechanisms that are commonly used are Stop and Wait and Sliding window.

Figure 2.1 Time flow control diagram during transmission without errors (a) and when packet loss and error occur (b)

2.2 Error Detection and Correction

As a result, the physical processes that cause errors in some media (for example, radio) tend to occur in bursts rather than one by one. Error bursting like that has both the advantage and the disadvantage of isolated single-bit errors. On the plus side, computer data is always sent in blocks of bits. Assume the block size is 1000 bits, and the error rate is 0.001 per bit. If the errors are independent, then most blocks will contain errors. If an error occurs with 100 bursts, then only one or two blocks in 100 blocks will be affected, on average. The disadvantage of burst errors is that they are more difficult to detect and correct than isolated errors.

2.2.1 Error Correction Codes

The network designers have devised two basic strategies regarding errors. The first way is to involve sufficient redundant information together with each block of data transmitted to allow the recipient to draw conclusions about what the transmitted character should be. Another way is to involve only enough redundancy to draw the conclusion that an error has occurred, and to allow it to request retransmission. The first strategy uses error-correcting codes, while the second strategy uses error-detecting codes.

In order to understand error handling, it is necessary to take a close look at what errors are. Typically, a frame consists of m bits of data (i.e. messages) and redundant r, or check bits. Take the total length of n (that is, n = m + r). An n-bit unit of data and a checkbit is often associated with an n-bit codeword.

Two codewords are specified: 10001001 and 10110001. Here we can determine how many different corresponding bits are. In this case, there are 3 different bits. To determine it, simply perform an EXCLUSIVE OR operation on both codewords, and count the number of bits 1 in the result of the operation. The number of bit positions where the two codewords differ is called the Hamming distance (Hamming, 1950). The thing to note is that if two codewords are separated by a Hamming distance d, it will take a single bit error d to convert from one to the other.

In most data transmission applications, all 2^m of data messages are legal data. However, due to the way the check bit is calculated, not all 2ⁿ are used. If an algorithm is specified for calculating the check bits, it is possible to generate a complete list of legal codewords. From this list two codewords with the minimum Hamming distance can be found. This distance is the Hamming distance for the complete code.

The error detection and error correction properties of a code depend on the Hamming distance. To detect d errors, you need a code with a distance of d + 1 because with such a code it is impossible that a single bit error d can change one valid codeword to another valid codeword. When the receiver sees an invalid codeword, it can say that an error has occurred during transmission. Likewise, to fix error d, you need a code that is 2d + 1 apart because it says legal codewords can be separated even with a change to d, the original codeword will be closer than other codewords, so error fixes can be determined uniquely.

As a simple example of error detection code, take a code where a single parity bit is appended to the data. The parity bit is chosen so that the number of 1 bits in the codeword is even (or odd). For example, if 10110101 is sent in even parity by adding a bit at the end, the data becomes 101101011, whereas with even parity 10110001 becomes 101100010. A code with a single parity bit has a distance of 2, because any single bit error results in a codeword with parity. wrong. This method can be used to detect a single error.

As a simple example of error correction code, take a code that has only four valid codewords: 0000000000, 0000011111, 1111100000 and 1111111111. This code has a space of 5, which means that it can fix multiple errors. When the codeword 0000011111 arrives, the recipient will know that the original data should be 0000011111. However, if the triple error changes 0000000000 to 0000000111, the error cannot be corrected.

Imagine that we are going to design code with m message bits and r check bits that will allow all single errors to be fixed. Each of the 2m legal messages requires an n + 1 bit pattern. Since the total number of bit patterns is 2 ⁿ, we must have (n + 1) 2 ^m ≤ 2 ⁿ. Using n = m + r, this requirement becomes (m + r + 1) ≤ 2 ^r. When m is specified, it places a lower limit on the number of check bits required to correct a single error.

In fact, this theoretical lower limit can be obtained using the Hamming method. The codeword bits are numbered consecutively, starting with bit 1 on the far left. Bits that are powers of 2 (1,2,4,8,16 and so on) are check bits. The rest (3,5,6,7,9 and so on) are inserted with m bits of data. Each check bit forces the parity of a portion of the bit set, including itself, to be even (or odd). A bit can be included in multiple parity computations. To find the check bit to which the data bit at position k contributes, rewrite k as a sum to the powers of 2.For example, 11 = 1 + 2 + 8 and 29 = 1 + 4 + 8 + 16. A bit is checked by the check bit that occurs in its expansion. (for example, bit 11 is checked by bits 1, 2 and 8).

When a codeword arrives, the receiver initializes the counter to zero. Then the codeword checks each check bit, k (k = 1, 2, 4, 8, ...) to see if it has the correct parity. If not, the codeword will add k to the counter. If the counter equals zero after all the check bits have been tested (that is, if all the check bits are true), the codeword will be accepted as valid. If the counter is not zero, the message contains an invalid number of bits. For example, if the check bits 1, 2, and 8 have an error, then the inversion bit is 11, because that's the only one checked by bits 1, 2, and 8. Figure 2.2 illustrates some of the 7-bit encoded ASCII characters as an 11 bit codeword using Hamming code. Note that the data is in the bit positions 3, 5, 6, 7, 9, 10, 11.

Figure 2.2 Using Hamming code to correct burst errors

Hamming code can only fix a single error. However, there is a trick that can be used to allow Hamming's code to fix popping errors. A consecutive k number of codewords are arranged as a matrix, one codeword per row. Typically, data will be transmitted one codeword line at a time, from left to right. To correct popped errors, data must be transmitted one column at a time, starting with the leftmost column. When all the k bits have been sent, the second column begins sending, and so on. When the frame arrives at the receiver, the matrix is reconstructed, one column per unit time. If an error burst occurs, at most 1 bit per k codeword will be affected. However Hamming code can fix one error per codeword, so the entire block can be fixed. This method uses the kr check bit to make km of data bits immune to single error bursts of length k or less.

2.3 Selective Repeat ARQ

Selective Repeat or also known as Selective-reject. With selective reject automatic repeat request (ARQ), the frames that will be sent are only those frames that receive a negative reply, in this case called SREJ or frames whose time has expired.

The method of selective-reject ARQ in correcting errors is by at first the transmitter part sends a continuous stream of data from a continuous frame, on the receiving side the data is stored and a cyclic redundancy check (CRC) process is carried out. But this CRC process takes place on a continuous stream of data from the received frame. When an error frame is encountered, the receiver sends the information to the sender via the "return channel". The sending part then takes the frame from the data storage area and puts it in the transmission queue. There are several important points for frame readers, the first is that there must be a way to identify the frame. The second is that there has to be a good way to know if the frame is getting a positive reply or a negative one.

Both of these important points can be solved by using sequential numbers sent and received. The sequential number that is sent is at the sender, as well as the sequential number that is received at the receiver. Received sequential numbers that are sent back on the sender's side are the sequential numbers sent by the sender side and get a positive reply from the receiving side. When the receiving side detects an error in the frame, the receiving side will send a sequential number that is sent along with the frame that is considered an error. Of course, in the end the receiving side has to rearrange the frames in the same order as the sending side before the data is passed on to the end user.

Selective-reject ARQ is more efficient against Go-Back-N as it reduces the number of retransmissions. However, selective-reject requires a larger data storage capacity for both the sender and receiver side to store the frame until the damaged frame is retransmitted. In addition, on the receiver side there must also be software that can send frames out of sequence so that data can arrive in sequence to the end user. Selective repeat can be implemented in two ways:

1. S indicates that the frame was received correctly and P determines from the received ACK sequence that a frame has been lost (implicit retransmission)
2. S returns a special negative statement due to missing frames from the sequence (explicit request)

From these two events, the frame event is received out of sequence, S holds this frame on the receiving channel until the next incoming frame sequence is received. In the case of implicit retransmission, assuming all ACK frames are received correctly, this can be explained as follows (Figure 2.3):

Figure 2.3 Implicit Retransmission corrupted I-frame

1. It is assumed that the I-frame N + 1 is damaged (missing)
2. S returns an ACK frame for each correctly received I-frame.
3. S returns ACK frames for I-frames N, N + 2, N + 3.
4. On ACK reception for I-frame N + 2, P notices that N + 1 frames were not received.
5. In order to know that more than 1 I-frame is corrupted, P enters the retransmission state of the missing (not received) frames.
6. In this condition, transmission of new frames is delayed until frames that were not received are retransmitted.
7. P removes I-frames N + 2 from the retransmission list and resends I-frames N + 1 before transmitting N + 5 frames.
8. In receiving I-frame N + 1, the contents of the queued frame on the receive list link are sent by S to LS_user in the correct order.

Whereas implicit retransmission assuming that all I-frames are received correctly except ACK frame N can be explained as follows.

Figure 2.4 Implicit Retransmission corrupted ACK-frame

1. On receiving ACK frame N + 1 P knows that I-frame N is still waiting for the statement to be received correctly. So P transmits I-frame N.
2. On reception the I-frame N which is transmitted S determines from the sequence variable that the frame has been received correctly and is therefore a duplicate.
3. S discards the frame but returns the ACK of the frame to replace it to ensure P removes the frame from the retransmission list.

The above operation relies on receiving the ACK frame associated with subsequent frames to initiate retransmission of the previous damaged frame. Another attempt is to use explicit negative acknowledgment frames to request retransmit the error frames. The negative acknowledgment is known as selective reject. On explicit requests, the assumption that acknowledgments are lost on the way can be explained as follows (see Figure 2.5 below).

Figure 2.5 Explicit Request Effect Correct Operation

1. Initially an ACK frame states that all frames in the retransmission list have been received including I-frames with the sequence number owned by the ACK
2. Assume I-frame N + 1 is broken.
3. S returns an ACK frame for I-frame N
4. When S receives an I-frame N + 2 S notices that I-frame N + 1 is missing so S sends a NAK frame containing the identifier for the missing I-frame N + 1.
5. In receiving NAK N + 1, P translates NAK N + 1 and at that time S is still waiting for I-frame N + 1 so P retransmits I-frame N + 1.
6. When S sends a NAK frame, S enters a retransmission state.
7. When in retransmission state the ACK frame returns are delayed.
8. On I-frame reception, N + 1 S leaves the retransmission state and continues to return the ACK frame.
9. N + 4 acknowledges that all frames up to I-frame N + 4 have been received correctly including N + 4 frames.
10. A timer is used with each NAK frame to ensure that a broken frame will be retransmitted.

Chapter 3 Closing

3.1 Conclusion

The conclusions that can be drawn from this paper are as follows:

1. The purpose of error control is to deliver error-free frames in the correct order to the network layer. The technique commonly used for error control is based on two functions, namely: Error detection and Automatic Repeat Request (ARQ).
2. By using the selective repeat method, data frames can be sent with a high level of efficiency because if an error occurs during transmission, only the frame that has an error will be retransmitted so that it can reduce the number of frames being transmitted. In contrast to the go back N method, which retransmits the frame starting from the frame where the error occurs to the next frame.
3. But if we use the selective repeat method, we need more storage capacity to store the retransmission state and receive lists. In addition, special software is also needed to sort the frames that have been received at the receiver.

3.2 Suggestion

After the authors have made this assignment, the suggestions the authors can suggest are, in sending data packets over a certain medium, there will always be a difference between the sent signal and the received signal. This difference can result in an error or error in the data packet sent so that the data cannot be read properly by the recipient. To avoid errors or errors in the data packet sent, error detection, error correction, and error control are required. So the reader should be able to recognize and know the errors that often occur in a data communication.

Bibliography

• ….., 2008. Laporan Selective Repeat. Avalaible in http://www.scribd.com/doc/23302439/laporan-selektif-repeat (Access 20 April 2012).
• ….., 2008. Makalah Data Link Layer. Avalaible in http://www.scribd.com/doc/24613367/Makalah-Data-Link-Layer (Access 20 April 2012).
• ….., 2011. Tugas Komunikasi Data : Teknik Encoding, Pendeteksi Error, Automatic Repeat Request (ARQ). Avalaible in http://catatan-yushiku.blogspot.com/2011/01/tugas-komunikasi-data-teknik-encoding.html (Access 20 April 2012).
• ….., 2012. Selective_Repeat_ARQ. Avalaible in http://en.wikipedia.org/wiki/Selective_Repeat_ARQ (Access 20 April 2012).

Tugas Kuliah Tentang Flow Control dan Selective Repeat ARQ

Catatan

Ini merupakan tugas S1 saya di mata kuliah Komunikasi Data dimana tugasnya adalah menulis essai mengenai flow control, error detection & control, dan selective repeat ARQ. Selain saya kelompok ini terdiri dari I Gede Ariana, I Made Dwi Angga Pratama, I Putu Arie Pratama, Yulianti Murprayana, I Wayan Alit Wigunawan, I Gusti Made Widiarsana , I Nym Apriana Arta Putra, Muhammad Audy Bazly, I Kadek Agus Riki Gunawan, Muhamad Nordiansyah. Tugas ini tidak pernah dipublikasi dimanapun dan kami sebagai penulis dan pemegang hak cipta melisensi tugas ini customized CC-BY-SA dimana siapa saja boleh membagi, menyalin, mempublikasi ulang, dan menjualnya dengan syarat mencatumkan nama kami sebagai penulis dan memberitahu bahwa versi asli dan terbuka tersedia disini.

BAB 1 Pendahuluan

1.1 Latar Belakang

Perkembangan teknologi komputer meningkat dengan sangat cepat, hal ini terlihat pada era tahun 80-an jaringan komputer masih merupakan teka-teki yang ingin dijawab oleh kalangan akademisi, dan pada tahun 1988 jaringan komputer mulai digunakan di universitas-universitas, perusahaan-perusahaan, dan sekarang memasuki era milenium ini terutama WWW (World Wide Web) telah menjadi realitas sehari-hari jutaan manusia di muka bumi ini.

Selain itu, perangkat keras dan perangkat lunak jaringan telah benar-benar berubah, di awal perkembangannya hampir seluruh jaringan dibangun dari kabel koaxial, kini banyak telah diantaranya dibangun dari serat optik (fiber optics) atau komunikasi tanpa kabel.

Dengan berkembangnya teknologi komputer dan komunikasi suatu model komputer tunggal yang melayani seluruh tugas-tugas komputasi suatu organisasi kini telah diganti dengan sekumpulan komputer yang terpisah-pisah akan tetapi saling berhubungan dalam melaksanakan tugasnya, sistem seperti ini disebut jaringan komputer (computer network).

Dua buah komputer dikatakan terinterkoneksi bila keduanya dapat saling bertukar informasi. Betuk koneksinya tidak harus melalui kawat tembaga saja melainkan dapat menggunakan serat optik, gelombang mikro, atau satelit komunikasi.

Dalam suatu komunikasi data, pastinya dilakukan pengiriman paket data melalui suatu medium tertentu, akan selalu terjadi adanya perbedaan antara sinyal yang dikirim dengan sinyal yang diterima. Perbedaan tersebut dapat mengakibatkan adanya error atau kesalahan pada paket data yang dikirim tersebut sehingga data tersebut tidak dapat dibaca dengan baik oleh penerima. Untuk menghindari terjadinya error atau kesalahan pada paket data yang dikirim maka diperlukan adanya deteksi kesalahan (checking error), perbaikan kesalahan (correction error), dan pengendalian kesalahan (control error). Pada error control terdapat tiga metode yang sering dipakai dalam komunikasi data, yaitu stop and wait request, go back N request, dan selective request. Error control meliputi mekanisme-mekanisme sebagai berikut : ACK/NAK, timeout, dan sequence number. Pada error control terjadi prosesproses sebagai berikut: error detection, acknowledgment, etransmission after timeout, dan negative acknowledgment.

1.2 Rumusan Masalah

Adapun rumusan masalah yang diangkat dalam makalah ini, adalah sebagai berikut :

1. Apakah yang dimaksud dengan kontrol aliran (flow control)?
2. Apakah yang dimaksud dengan deteksi dan koreksi error? serta bagaimana cara meminimalisirnya?
3. Apakah yang dimaksud dengan Selective Repeat ARQ?

1.3 Tujuan

Adapun tujuan dari pembuatan makalah ini adalah, sebagai berikut:

1. Mampu mendefinisikan pengertian dari kontrol aliran (flow control).
2. Mampu memberikan definisi mengenai pengertian deteksi dan koreksi error, serta bagaimana cara untuk meminimalisir kesalahan-kesalahan yang terjadi.
3. Mampu menjelaskan mengenai definisi tentang Selective Repeat ARQ.

1.4 Ruang Lingkup Materi

Dalam makalah ini, ruang lingkup yang dibahas oleh penulis hanya sebatas mengenai permasalahan yang di bahas, yaitu sebatas Selective Repeat ARQ dalam suatu jaringan komunikasi data, dan juga untuk memberikan gambaran kepada para pembaca mengenai proses pengendalian kesalahan dalam komunikasi data.

BAB 2 Pembahasan

Tujuan dilakukan pengontrolan terhadap error adalah untuk menyampaikan frame-frame tanpa error dalam urutan yang tepat ke lapisan jaringan. Teknik yang umum digunakan untuk error control berbasis pada dua fungsi, yaitu:

1. Error detection, biasanya menggunakan teknik CRC (Cyclic Redundancy Check).
2. Automatic Repeat Request (ARQ), ketika error terdeteksi pengirim meminta mengirim ulang frame yang terjadi kesalahan.

Sedangkan, error control dibagi menjadi tiga yaitu:

1. Manual Error Control. Misalnya jika kita melakukan kesalahan dalam pengetikan kita koreksi dengan melakukan penghapusan terhadap karakter yang salah misalkan dengan tombol delete atau backspace.
2. Echo Checking. Prosedur yang sama digunakan ketika suatu terminal terhubung dengan remote computer katakanlah dengan menggunakan analog PSTN dan sebuah modem. Di samping tiap karakter yang dimasukkan ditampilkan secara langsung pada terminal display mula-mula ia ditransmisikan ke remote computer. Remote computer tersebut kemudian membaca dan menyimpan karakter dan mentransmisikan ulang ke terminal yang menampilkannya. Jika berbeda dengan apa yang telah dimasukkan user dapat memulai lagi transmisi untuk penghapusan karakter yang salah.
3. Automatic Repeat Request. Terdiri dari idle request dan continuous request. Kita akan membahas lebih dalam continuous request terutama selective repeat.

2.1 Kontrol Aliran (Flow Control)

Flow control adalah suatu teknik untuk menjamin bahwa sebuah stasiun pengirim tidak membanjiri stasiun penerima dengan data. Stasiun penerima secara khas akan menyediakan suatu buffer data dengan panjang tertentu. Ketika data diterima, dia harus mengerjakan beberapa poses sebelum dia dapat membersihkan buffer dan mempersiapkan penerimaan data berikutnya.

Bentuk sederhana dari kontrol aliran dikenal sebagai stop and wait, dia bekerja sebagai berikut. Penerima mengindikasikan bahwa dia siap untuk menerima data dengan mengirim sebual poll atau menjawab dengan select. Pengirim kemudian mengirimkan data.

Flow control ini diatur/dikelola oleh Data Link Control (DLC) atau biasa disebut sebagai Line Protocol sehingga pengiriman maupun penerimaan ribuan message dapat terjadi dalam kurun waktu sesingkat mungkin. DLC harus memindahkan data dalam lalu lintas yang efisien. Jalur komunikasi harus digunakan sedatar mungkin, sehingga tidak ada stasiun yang berada dalam kadaan idle sementara stasiun yang lain saturasi dengan lalu lintas yang berkelebihan. Jadi flow control merupakan bagian yang sangat kritis dari suatu jaringan. Berikut ini ditampilkan Time Diagram Flow Control saat komunikasi terjadi pada kondisi tanpa error dan ada error. Mekanisme Flow control yang sudah umum digunakan adalah Stop and Wait dan Sliding window.

Gambar 2.1 Diagram waktu flow control saat transmisi tanpa kesalahan (a) dan saat terjadi kehilangan paket dan terjadi kesalahan (b)

2.2 Deteksi dan Koreksi Error

Sebagai akibat proses-proses fisika yang menyebabkannya terjadinya error pada beberapa media (misalnya, radio) cenderung timbul secara meletup (burst) bukannya satu demi satu. Error yang meletup seperti itu memiliki baik keuntungan maupun kerugian pada error bit tunggal yang terisolasi. Sisi keuntungannya, data komputer selalu dikirim dalam bentuk blok-blok bit. Anggap ukuran blok sama dengan 1000 bit, dan laju error adalah 0,001 per bit. Bila error-errornya independen, maka sebagian besar blok akan mengandung error. Bila error terjadi dengan letupan 100, maka hanya satu atau dua blok dalam 100 blok yang akan terpengaruh, secara rata-ratanya. Kerugian error letupan adalah bahwa error seperti itu lebih sulit untuk dideteksi dan dikoreksi dibanding dengan error yang terisolasi.

2.2.1 Kode – Kode Pengkoreksian Error

Para perancang jaringan telah membuat dua strategi dasar yang berkenaan dengan error. Cara pertama adalah 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. Cara lainnya adalah dengan hanya melibatkan redundansi secukupnya untuk menarik kesimpulan bahwa suatu error telah terjadi, dan membiarkannya untuk meminta pengiriman ulang. Strategi pertama menggunakan kode-kode pengkoreksian error (error-correcting codes), sedangkan strategi kedua menggunakan kode-kode pendeteksian error (error-detecting codes).

Untuk bisa mengerti tentang penanganan error, maka perlu melihat dari dekat tentang apa yang disebut error itu. Biasanya, sebuah frame terdiri dari m bit data (yaitu pesan) dan r redundan, atau check bits. Ambil panjang total sebesar n (yaitu, n = m + r). Sebuah satuan n-bit yang berisi data dan checkbit sering kali dikaitkan sebagai codeword n-bit.

Ditentukan dua buah codeword: 10001001 dan 10110001. Disini kita dapat menentukan berapa banyak bit yang berkaitan berbeda. Dalam hal ini, terdapat 3 bit yang berlainan. Untuk menentukannya cukup melakukan operasi EXCLUSIVE OR pada kedua codeword, dan menghitung jumlah bit 1 pada hasil operasi. Jumlah posisi bit dimana dua codeword berbeda disebut jarak Hamming (Hamming, 1950). Hal yang perlu diperhatikan adalah bahwa bila dua codeword terpisah dengan jarak Hamming d, maka akan diperlukan error bit tunggal d untuk mengkonversi dari yang satu menjadi yang lainnya.

Pada sebagian besar aplikasi transmisi data, seluruh 2m pesan data merupakan data yang legal. Tetapi sehubungan dengan cara penghitungan check bit, tidak semua 2n digunakan. Bila ditentukan algoritma untuk menghitung check bit, maka akan dimungkinkan untuk membuat daftar lengkap codeword yang legal. Dari daftar ini dapat dicari dua codeword yang jarak Hamming-nya minimum. Jarak ini merupakan jarak Hamming bagi kode yang lengkap.

Sifat-sifat pendeteksian error dan perbaikan error suatu kode tergantung pada jarak Hamming-nya. Untuk mendeteksi d error, anda membutuhkan kode dengan jarak d + 1 karena dengan kode seperti itu tidak mungkin bahwa error bit tunggal d dapat mengubah sebuah codeword yang valid menjadi codeword valid lainnya. Ketika penerima melihat codeword yang tidak valid, maka penerima dapat berkata bahwa telah terjadi error pada transmisi. Demikian juga, untuk memperbaiki error d, anda memerlukan kode yang berjarak 2d + 1 karena hal itu menyatakan codeword legal dapat terpisah bahkan dengan perubahan d, codeword orisinil akan lebih dekat dibanding codeword lainnya, maka perbaikan error dapat ditentukan secara unik.

Sebagai sebuah contoh sederhana bagi kode pendeteksian error, ambil sebuah kode dimana parity bit tunggal ditambahkan ke data. Parity bit dipilih supaya jumlah bit-bit 1 dalam codeword menjadi genap (atau ganjil). Misalnya, bila 10110101 dikirimkan dalam parity genap dengan menambahkan sebuah bit pada bagian ujungnya, maka data itu menjadi 101101011, sedangkan dengan parity genap 10110001 menjadi 101100010. Sebuah kode dengan parity bit tunggal mempunyai jarak 2, karena sembarang error bit tunggal menghasilkan sebuah codeword dengan parity yang salah. Cara ini dapat digunakan untuk mendeteksi erro-error tunggal.

Sebagai contoh sederhana dari kode perbaikan error, ambil sebuah kode yang hanya memiliki empat buah codeword valid: 0000000000, 0000011111, 1111100000 dan 1111111111. Kode ini mempunyai jarak 5, yang berarti bahwa code tersebut dapat memperbaiki error ganda. Bila codeword 0000011111 tiba, maka penerima akan tahun bahwa data orisinil seharusnya adalah 0000011111. Akan tetapi bila error tripel mengubah 0000000000 menjadi 0000000111, maka error tidak akan dapat diperbaiki.

Bayangkan bahwa kita akan merancang kode dengan m bit pesan dan r bit check yang akan memungkinkan semua error tunggal bisa diperbaiki. Masing-masing dari 2m pesan yang legal membutuhkan pola bit n + 1. Karena jumlah total pola bit adalah 2ⁿ, kita harus memiliki (n + 1)2^m ≤ 2ⁿ. Dengan memakai n = m + r, persyaratan ini menjadi (m + r + 1) ≤ 2^r. Bila m ditentukan, maka ini akan meletakkan batas bawah pada jumlah bit check yang diperlukan untuk mengkoreksi error tunggal.

Dalam kenyataannya, batas bawah teoritis ini dapat diperoleh dengan menggunakan metoda Hamming. Bit-bit codeword dinomori secara berurutan, diawali dengan bit 1 pada sisi paling kiri. Bit bit yang merupakan pangkat 2 (1,2,4,8,16 dan seterusnya) adalah bit check. Sisanya (3,5,6,7,9 dan seterusnya) disisipi dengan m bit data. Setiap bit check memaksa parity sebagian kumpulan bit, termasuk dirinya sendiri, menjadi genap (atau ganjil). Sebuah bit dapat dimasukkan dalam beberapa komputasi parity. Untuk mengetahui bit check dimana bit data pada posisi k berkontribusi, tulis ulang k sebagai jumlahan pangkat 2. Misalnya, 11 = 1 + 2 + 8 dan 29 = 1 + 4 + 8 + 16. Sebuah bit dicek oleh bit check yang terjadi pada ekspansinya (misalnya, bit 11 dicek oleh bit 1, 2 dan 8).

Ketika sebuah codeword tiba, penerima menginisialisasi counter ke nol. Kemudian codeword memeriksa setiap bit check, k (k= 1, 2, 4, 8,....) untuk melihat apakah bit check tersebut mempunyai parity yang benar. Bila tidak, codeword akan menambahkan k ke counter. Bila counter sama dengan nol setelah semua bit check diuji (yaitu, bila semua bit checknya benar), codeword akan diterima sebagai valid. Bila counter tidak sama dengan nol, maka pesan mengandung sejumlah bit yang tidak benar. Misalnya bila bit check 1,2, dan 8 mengalami kesalahan (error), maka bit inversinya adalah 11, karena itu hanya satu-satunya yang diperiksa oleh bit 1,2, dan 8. Gambar 2.2 menggambarkan beberapa karakter ASCII 7-bit yang diencode sebagai codeword 11 bit dengan menggunakan kode Hamming. Perlu diingat bahwa data terdapat pada posisi bit 3, 5, 6, 7, 9, 10, 11.

Gambar 2.2 Penggunaan kode Hamming untuk mengkoreksi burst error

Kode Hamming hanya bisa memperbaiki error tunggal. Akan tetapi, ada trick yang dapat digunakan untuk memungkinkan kode Hamming dapat memperbaiki error yang meletup. Sejumlah k buah codeword yang berurutan disusun sebagai sebuah matriks, satu codeword per baris. Biasanya, data akan ditransmisikan satu baris codeword sekali, dari kiri ke kanan. Untuk mengkoreksi error yang meletup, data harus ditransmisikan satu kolom sekali, diawali dengan kolom yang paling kiri. Ketika seluruh k bit telah dikirimkan, kolom kedua mulai dikirimkan, dan seterusnya. Pada saat frame tiba pada penerima, matriks direkonstruksi, satu kolom per satuan waktu. Bila suatu error yang meletup terjadi, paling banyak 1 bit pada setiap k codeword akan terpengaruh. Akan tetapi kode Hamming dapat memperbaiki satu error per codeword, sehingga seluruh blok dapat diperbaiki. Metode ini memakai kr bit check untuk membuat km bit data dapat immune terhadap error tunggal yang meletup dengan panjang k atau kurang.

2.3 Selective Repeat ARQ

Selective Repeat atau dikenal juga sebagai Selective-reject. Dengan selective reject ARQ, frame-frame yang akan dikirimkan hanya frame-frame yang mendapat balasan negatif, dalam hal ini disebut SREJ atau frame-frame yang waktunya sudah habis.

Cara selective-reject ARQ dalam memperbaiki kesalahan adalah dengan cara, mulanya bagian transmitter mengirim stream data kontinyu dari frame yang kontinyu, pada sisi penerima data tersebut disimpan dan dilakukan proses CRC. Tapi proses CRC ini berlangsung pada stream data yang kontinyu dari frame yang diterima. Ketika dijumpai frame yang error, penerima mengirim informasi pada sisi pengirim melalui “return channel”. Bagian pengirim kemudian mengambil frame tersebut dari tempat penyimpanan data, lalu dimasukkan dalam antrian transmisi. Ada beberapa poin penting bagi pembaca frame, yang pertama adalah harus ada cara untuk mengidentifikasi frame. Yang kedua adalah harus ada cara yang baik untuk mengetahui frame mendapat balasan positif atau balasan negatif.

Kedua poin penting tersebut bisa di atasi dengan menggunakan angka sekuensial yang dikirim dan yang diterima. Angka sekuensial yang dikirim ada pada pengirim, begitu juga dengan angka sekuensial yang diterima berada pada penerima. Angka sekuensial yang diterima yang dikirim kembali pada sisi pengirim adalah angka sekuensial yang dikirim oleh sisi pengirim dan mendapat balasan positif dari sisi penerima. Ketika sisi penerima mendeteksi kesalahan pada frame, maka sisi penerima akan mengirimkan angka sekuensial yang dikirim bersama frame yang dianggap error. Tentu daja pada akhirnya sisi penerima harus menata kembali frame sesuai urutannya seperti pada sisi pengirim sebelum data diteruskan ke pengguna akhir.

Selective-reject ARQ lebih efisien terhadap Go-Back-N karena mengurangi jumlah retransmisi. Namun selective-reject memerlukan kapasitas penyimpanan data yang lebih besar baik disisi pengirim dan penerima untuk menyimpan frame sampai frame yang rusak diretransmisi. Selain itu disisi penerima juga harus terdapat software yang dapat mengirim frame diluar urutan agar data bisa sampai secara urut pada pengguna akhir. Selective repeat dapat diimplementasikan dengan dua cara:

1. S menyatakan bahwa frame telah diterima dengan benar dan P menentukan dari sequence ACK yang diterima bahwa sebuah frame telah hilang (implicit retransmisi)
2. S mengembalikan pernyataan negative khusus dikarenakan ada frame hilang dari sequence (explicit request)

Dari kedua event tersebut kejadian frame diterima di luar sequence, S menahan frame ini di saluran penerima sampai sequence frame masuk berikutnya diterima. Pada kasus implicit retransmission dengan asumsi semua frame ACK diterima dengan benar dapat dijelaskan sebagai berikut (Gambar 2.3):

Gambar 2.3 Implicit Retransmission corrupted I-frame

1. Diasumsikan I-frame N + 1 rusak (hilang)
2. S mengembalikan frame ACK untuk tiap-tiap I-frame yang telah diterima dengan benar.
3. S mengembalikan frame ACK untuk I-frame N, N + 2, N + 3.
4. Pada penerimaan ACK untuk I-frame N + 2, P menngetahui bahwa frame N + 1 tidak diterima.
5. Untuk dapat mengetahui bahwa lebih dari 1 I-frame yang rusak, P memasukkan retransmission state pada frame yang hilang (tidak diterima).
6. Dalam kondisi ini, transmisi frame baru ditunda sampai frame yang tidak diterima ditransmisikan ulang.
7. P menghilangkan I-frame N + 2 pada daftar retransmisi dan mengirimkan ulang I-frame N + 1 sebelum mentransmisikan frame N + 5.
8. Dalam penerimaan I-frame N + 1, isi dari frame antrian pada link receive list dikirimkan oleh S ke LS_user pada urutan yang benar.

Sedangkan pada implicit retransmission dengan asumsi bahwa semua I-frame diterima dengan benar kecuali ACK frame N dapat dijelaskan sebagai berikut.

Gambar 2.4 Implicit Retransmission corrupted ACK-frame

1. Pada penerimaan ACK frame N + 1 P mengetahui bahwa I-frame N masih menunggu pernyataan telah diterima dengan benar. Jadi P mentransmisikan I-frame N.
2. Saat penerimaan I-frame N yang diretransmisi S menentukan dari sequence variable bahwa frame tersebut telah diterima dengan benar dan oleh karena itu merupakan sebuah duplikat.
3. S membuang frame tapi mengembalikan ACK frame untuk menggantikannya untuk memastikan P menghilangkan frame dari daftar retransmisi.

Operasi di atas bergantung pada penerimaan frame ACK yang berhubungan dengan frame-frame berikutnya untuk menginisiasi retransmisi frame sebelumnya yang rusak. Usaha yang lain adalah dengan menggunakan explicit negative acknowledgment frame untuk meminta trasnmisi ulang frame yang error. Negative acknowledgment tersebut dikenal dengan selective reject. Pada explicit request dengan asumsi bahwa acknowledgments hilang dalam perjalanan dapat dijelaskan sebagai berikut (lihat Gambar. 2.5 di bawah ini).

Gambar 2.5 Explicit Request Effect Correct Operation

1. Mula-mula sebuah ACK frame menyatakan telah diterima semua frame di retransmission list termasuk I-frame dengan sequence number yang dimiliki ACK
2. Asumsikan I-frame N + 1 rusak.
3. S mengembalikan sebuah ACK frame untuk I-frame N
4. Ketika S menerima I-frame N + 2 S mengetahui bahwa I-frame N + 1 hilang jadi S mengirim NAK frame yang mengandung identifier untuk I-frame N + 1 yang hilang tersebut.
5. Dalam penerimaan NAK N + 1, P menterjemahkan NAK N + 1 dan saat itu S masih menunggu I-frame N + 1 sehingga P mentransmisikan ulang I-frame N + 1.
6. Ketika S mengirim NAK frame S memasukkan retransmission state.
7. Ketika dalam retransmission state pengembalian ACK frame ditunda.
8. Saat penerimaan I-frame N + 1 S meninggalkan retransmission state dan melanjutkan pengembalian ACK frame.
9. N + 4 mengakui bahwa semua frame sampai I-frame N + 4 telah diterima dengan benar termasuk frame N + 4.
10. Timer digunakan dengan masing-masing NAK frame untuk memastikan bahwa suatu frame rusak akan ditransmisikan ulang.

BAB 3 Penutup

3.1 Kesimpulan

Adapun kesimpulan yang dapat ditarik dari makalah ini, adalah sebagai berikut:

1. Tujuan dilakukan pengontrolan terhadap error adalah untuk menyampaikan frame-frame tanpa error dalam urutan yang tepat ke lapisan jaringan. Teknik yang umum digunakan untuk error control berbasis pada dua fungsi, yaitu : Error detection dan Automatic Repeat Request (ARQ).
2. Dengan menggunakan metode selective repeat maka frame data dapat dikirim dengan tingkat efisiensi yang tinggi karena jika terjadi error pada saat pengiriman maka hanya frame yang mengalami error yang akan diretransmisi sehingga dapat mengurangi jumlah frame yang diretransmisi. Berbeda dengan metode go back N yang meretransmisikan frame mulai dari frame yang terjadi error hingga frame yang selanjutnya.
3. Tapi jika kita menggunakan metode selective repeat, kita membutuhkan kapasitas penyimpanan yang lebih besar untuk menyimpan retransmission state dan receive list. Selain itu juga dibutuhkan software khusus untuk mengurutkan frame-frame yang telah diterima pada penerima.

3.2 Usul dan Saran

Setelah penulis membuat makalah ini, maka usul dan saran yang dapat penulis sarankan. Dalam pengiriman paket data melalui suatu medium tertentu, akan selalu terjadi adanya perbedaan antara sinyal yang dikirim dengan sinyal yang diterima. Perbedaan tersebut dapat mengakibatkan adanya error atau kesalahan pada paket data yang dikirim tersebut sehingga data tersebut tidak dapat dibaca dengan baik oleh penerima. Untuk menghindari terjadinya error atau kesalahan pada paket data yang dikirim maka diperlukan adanya deteksi kesalahan (checking error), perbaikan kesalahan (correction error), dan pengendalian kesalahan (control error). Maka hendaknya pembaca mampu mengenali serta mengetahui kesalahan-kesalahan yang sering terjadi dalam suatu komunikasi data.

Daftar Pustaka

• ….., 2008. Laporan Selective Repeat. Terdapat di http://www.scribd.com/doc/23302439/laporan-selektif-repeat (diakses tanggal 20 April 2012).
• ….., 2008. Makalah Data Link Layer. Terdapat di http://www.scribd.com/doc/24613367/Makalah-Data-Link-Layer (diakses tanggal 20 April 2012).
• ….., 2011. Tugas Komunikasi Data : Teknik Encoding, Pendeteksi Error, Automatic Repeat Request (ARQ). Terdapat di http://catatan-yushiku.blogspot.com/2011/01/tugas-komunikasi-data-teknik-encoding.html (diakses tanggal 20 April 2012).
• ….., 2012. Selective_Repeat_ARQ. Terdapat di http://en.wikipedia.org/wiki/Selective_Repeat_ARQ (diakses tanggal 20 April 2012).

Mirror

• https://www.publish0x.com/fajar-purnama-academics/assignment-about-flow-control-and-selective-repeat-arq-xvwelpr?a=4oeEw0Yb0B&tid=hive
• https://0fajarpurnama0.github.io/bachelor/2020/12/02/assignment-flow-control-error-and-selective-repeat-arq
• https://0fajarpurnama0.medium.com/assignment-about-flow-control-and-selective-repeat-arq-7f417e5cb5db
• https://hicc.cs.kumamoto-u.ac.jp/~fajar/bachelor/assignment-flow-control-error-and-selective-repeat-arq
• https://0darkking0.blogspot.com/2020/12/assignment-about-flow-control-and.html
• https://0fajarpurnama0.cloudaccess.host/index.php/9-fajar-purnama-academics/130-assignment-about-flow-control-and-selective-repeat-arq
• http://0fajarpurnama0.weebly.com/blog/assignment-about-flow-control-and-selective-repeat-arq
• https://0fajarpurnama0.wixsite.com/0fajarpurnama0/post/assignment-about-flow-control-and-selective-repeat-arq
• https://read.cash/@FajarPurnama/assignment-about-flow-control-and-selective-repeat-arq-e52037f7
• https://www.uptrennd.com/post-detail/assignment-about-flow-control-and-selective-repeat-arq~ODI0ODA0