1.1 Different Types of Existing Error Detection Techniques

There are different types of existing errors detection schemes such as parity checker, checksum and cyclic redundancy check (CRC) [19].

1.1.1 Parity Checking

The parity checking is generally used for single bit error detection. Either even parity or odd parity checking is generally used for single bit error detection. The sending code word is N+R bits, where R and N is the parity bit and main data bits respectively. On the receiver side accept the data bits if the parity bit is valid otherwise rejected.

Suppose k data bits of a message are D1, D2 ……. appended a parity bit p and n=k+1 is the length of a codeword. Parallel XOR operations generate parity P =D₁ D₂ ….... [19]_.

1.1.2 Two-dimensional Parity Checking

Parity check bits are calculated to generate single bit for each row and each column as shown in Figure 2.6. Parity is created for each row and each column. The row wise streams are appended and sent to receiver. After receiving, these data are compared using two-dimension parity [19]. The limitation of it is given below:

Ø When two bits in one data are occurred error and same position in another data unit of two bits are also occurred, this parity checker is unable to detect the error.

Ø It is unable to detect the four bits errors or more.

Figure 2.6: Two-dimensional parity checking.

1.1.3 Checksum Technique

The checksum method is based on binary addition of all the sub partition of the data. The summation of data in the blocks is calculated. Then one’s complement of the summation is computed. The summation and it’s one’s complement are added to the end of the data units as a redundancy which is defined as checksum. The extended redundancy field with data are sent to the receiver as given in Equation 2.1. On the receiver side, the summation of all blocks and 1`s complement of this result is computed. Finally accept the pattern if the one’s complement of summation is zero otherwise sending for re-execution as given in Equation 1.2 [19].

Suppose, total binary bits = n and k is the number of segments of n data and block of messages come from original data of m. Summation of all blocks (S), One’s Complement of Checksum , Generated Codeword , and Summation of all blocks after appended Checksum .

Summation of all blocks S = (2.1)

One’s Complement of summation of blocks = . Generated codeword = number of n binary stream and appended with .

On the receiving side, the is a block from the codeword of checksum.

Summation on receiving side = (2.2)

Accept the result if it is = 0, otherwise it is neglected in Equation 2.2. The Time complexity = O(S + ) of checksum [22].

1.1.4 Cyclic Redundancy Checking

CRC error detection technique is mainly based on the binary division as shown in Figure 2.7. The polynomial divisor G(x) operates on the binary division with original data and appends a sequence of redundant extra zero and added the remainder is called the CRC. If the length of polynomial divisor G(x) is n, the extra (n-1) zeros are appended with original data. On the receiver side, the received codeword is divided by the same polynomial divisor G(x). Finally accept if the remainder is zero otherwise requesting for resending or re-execution as shown in Figure 2.8 [19].

Figure 2.7: Cyclic redundancy checking technique [19] [58].

Let G(x) is the CRC polynomial divisor and the maximum degree of polynomial code n-1 indicates the polynomial W= + + + ……+ where, W and x is coefficient and variable respectively [75].

W(x) = (2.3)

Figure 2.8: CRC error detection technique using binary division [19] [58].

On the receiving side, when the codeword is not divided by polynomial G(x), it may be changed to E(x) error bits. R(x) is the receiving data in Equation 2.5. So we can find an easy way [75].

R(x) = + (2.4)

If error E(x) is zero, then data are received error-free.

R(x) = + 0

Complexity = O (2× + ) (2.5)

So, the time complexity of CRC is more than other as given in Equation 2.5 [22] [58].

1.1.5 Hamming Code Mechanism

Hamming code is a mechanism for error detection and correction. When the huge data are transmitted from the sender to the receiver, it may be errors occurred. Redundant extra bits are generated and added with the information bits of data. It ensures error free data transmission from source to destination [19].

The formula of redundant bits is calculated ≥ m + r + 1, here r is the redundant bits, m is used for data bits. For an example number of data bits is 8, the amount of redundant bits is calculated by formula ≥ 8 + 4 + 1 and the amount of redundant bits are 4 [19].

1.2 Problems Statement of Existing Systems

Many researchers are working on fault detection and recovery mechanism. Their functionalities and architecture are related to cloud system.

The limitation of existing works are given below:

1) The reactive fault tolerant technique has limitations (i) wastage of more resources. (ii) rescheduling the failed tasks are in available VM [75].

2) The CRC is unable to detect the burst length errors maximum degree of divisor > r (r=16, 17,…64) [19].

3) The probability of undetectable errors of CRC is 1 – [19] [75].

4) Checksum technique only detects single bit and multiple bits errors. But burst bits are not detected [19].

5) The CRC and checksum techniques [19]:

Ø CRC uses complex shift register and checksum uses binary adder circuit [19].

Ø Detect the errors after multiple steps.

6) Are reactive fault tolerance.