A Hybrid Arq Protocol With Improved Performance

In recent past several new and modified ARQ protocols are studied in literature in order to achieve higher throughput. Packet combining scheme, Modified Packet Combining scheme, Truncated Packet Transmission Scheme, Bit Oriented XOR based packet transmission scheme are well defined ARQ protocol for error correction either by retransmission or by processing at the receiver. For retransmission, Satry’s multi copies technique was extensively studied by Bhunia whereby it was established to fix multiple copies with number of times retransmission are requested. For correction at the receiver, packet combining scheme suggested by Chakraborty and Multiple Packet Combining scheme introduced by Bhunia are understood. In the paper we propose a hybrid ARQ technique made of multi copies retransmission with packet combining & Multiple packet combining scheme and study its performance in terms of throughput.

Introduction: Packet combining (PC) scheme for correction of bit error using erroneous copies of packet at receiver was introduced by Chakraborty[1,2]. In the scheme two erroneous copies are XORed for locating the position of bit(s) in error of the packet, so that the receiver can correct the error rather than requesting transmitter to retransmit the packet. The correction process proposed is the brute force bit by bit inversion of the located bit error positions and followed by FCS (frame check sequence) check. The scheme of Chakraborty fails: (i) when bit error locations in erroneous copies are same and (ii) when multiple bit errors occur as then the application of brute force bit inversion for correcting will be huge and complex. For n bits in error (n>1), on average 2n-1 trails of attack are required. A scheme called Packet Reversed Packet Combining (PRPC) has been studied[3] to tackle the first problem of PC Modified Packet Combining (MPC)[4,5] was reported to tackle the multiple bit errors in the received erroneous copies of packet. MPC can not also tackle error if occurs at the same location until odd number of erroneous copies are available that too only when transmitted bit 0 is converted to 1 in all copies in same location but not when transmitted bit 1 is converted to 0 in all copies in same location. Both PRPC and MPC scheme individually or in combination are believed to offer higher throughput than that of basic ARQ. This is studied in[6]. In this paper we propose a simple scheme of packet combining that will correct error(s) at the receiver as well will provide better throughput.

2.    Basic Idea: The idea is that a receiver when receives an erroneous packet and requests for retransmission to a transmitter, the transmitter will transmit a processed packet and not another copy of the previously sent packet. The processed packet will be made of bits obtained by bit oriented exclusive or (XOR) operation of two consecutive bits of original packet.

*Director, SMIEEE, Bengal Institute of Technology & Management, Orrisa
 
Example: 1.Say the original packet is, 00110101. Say on first transmission the receiver receives the packet as 00111101 (call it first copy) (error location is marked bold, 5th bit from left). Receiver requests for retransmission. Transmitter transmits a copy made of XORed bits as:  0011 (bit wise XOR operation of two consecutive bits of original packet) obtained as illustrated in table I:

Table I: Illustration of obtaining XORed bits from original packet /Packet to be transmitted by transmitter after first transmission failure
Bits of original packets    Bits obtained on XOR operation of two consecutive bits of original packet
0    0
0   
1    0
1   
0    1
1   
0    1
1   

It is assumed with reasonable assumption (discussed later in the section of analysis) that packet with XORed bits is received at the receiver without error. With this error free packet, receiver will reconstruct packet(s) as illustrated in table II:

Table II: Illustration of reconstructed packet(s) at receiver
Erroneous packet  at receiver    Packet with XORed bits    Reconstructed packet(s)
0    0    0
0        0
1    0    1
1        1
1    1    10
1        01
0    1    0
1        1

When XOR bit meets the rule with received bits in the erroneous packet, the received bits are accepted as they were received. When the rule fails, possible options are listed. In case of fifth and sixth bits, the two options are shown in the table II. On comparison with the reconstructed packet (s) with the earlier received erroneous copy will indicate the bit error location(s) as below:

A. Option 1
Erroneous copy :         00111101
Reconstructed copy 1: 00111001
.                                   00000100
Indicates sixth bit as error

B. Option 2      
Erroneous copy :         00111101
Reconstructed copy 2: 00110101
.                                   00001000
Indicates fifth bit as error

Receiver applies the bit inversion at sixth and then fifth location followed by FEC to correct the error. Thus error is now corrected at the fifth bit which is the exact bit location.

 Say the original packet is, 111111111. Say on first transmission the receiver receives the packet as 11110110 (error locations are marked bold). Receiver requests for retransmission. Transmitter transmits a packet made of XORed bits as 0000. Receiver reconstructs packet(s) as:
 Reconstructed copy 1: 11110011               
Reconstructed copy 2: 11111111
Reconstructed copy 3: 11110000
and so on
On comparison with the erroneous copy and reconstructed copies, the correction is done as described in example 1.

3.     Throughput Analysis: Throughput of all ARQ techniques depends on the average number (n) of times a packet needs transmission (including retransmission) for successful reception by the receiver. As n decreases, throughput increases, and when n=1 throughput is 100%. We propose to study the gain of the proposed scheme over that of the i)PRPC and ii)the normal stop and wait ARQ. The gain will be measured by the parameter, n as defined. In normal stop and wait ARQ[7-10]:
                              (1)
where P=packet error probability,
= 
and  bit error rate and k is the packet size in bits.
In PRPC, all single bit errors will be corrected. The probability that a packet is with single bit error is
                    (2)
Thus the probability of packet in error except single bit error is:
                                          (3)
In PRPC, for correction of single bit error, twice a packet is transmitted: first original and next reversed. Thus in PRPC when implemented in stop and wait ARQ protocol, the average number of times,  a packet needs transmission (including retransmission) for successful delivery is:
             (4)
First part of right hand side of equ(4) is for correction in normal stop and wait ARQ for bit errors other than single bit error, and second part is for PRPC in correcting single bit error.

The proposed scheme is based on the assumption that the packet made of XORed bits is error free. This is a reasonable assumption. When the original packet is of k bits, the packet made of XORed bit is k/2 bits. The probability of packet error when packet is of k/2 bits is much lesser than that of the packet of k bits.  In the proposed scheme the correction process will be cumbersome when bit errors will be more than double bit errors. It is also a reasonable assumption that the probability of more than two bits error in a packet is negligible. Thus we limit the application of the proposed scheme up to two bits error. Then the average number of times,  a packet needs transmission for successful transmission in the proposed scheme is:

   (5)
where:
 

First part of the equ(5) is applicable when there is more than two bits error. Second part of the equ(5) is applicable when single or double bit error occurs. 1.5 is for first full packet transmission followed by the transmission of half packet made of XORed bits. Equ(5) changes as below when the proposed scheme is made for correction of single bit error:

         (6)

4.    Conclusion: In[6], throughput advantage of PRPC over basic ARQ protocols is  studied. Comparing equ(4) with equ(6), the throughput advantage of the proposed scheme over PRPC is evident. Thus throughput gain of the proposed scheme over the PRPC and over the normal stop & wait ARQ is established.

Besides, the proposed scheme will correct single and double bit errors without concerning about bit location(s) of error(s).

   
5.    References:
1.    Shayam S Chakraborty,(1995) “An ARQ scheme with packet combining”,  IEEE Communication Letters, Vol 2, No 7, pp200-202, July.
2.    Shyam S Chakraborty, (1999)“An Adaptive ARQ scheme with Packet Combining for time varying channels”, IEEE Communication Letters, Vol 3, No 2, pp 52-54.
3.    Chandan T Bhunia, Packet Reversed Packet Combining Scheme, Pre print ICTP/2006/46 046, pp1-7, Italy.
4.    Chandan T Bhunia, (2005) “Modified packet Combining Scheme” Proc. ICITA, IEEE Comp. Soc., Vol 2, pp 641-646.
5.    Chandan T Bhunia, (2005)“Information Technology, Networks and Internet”, New Age International Publishers, New Delhi.
6.    Chandan T Bhunia, “Comparing Basic GBN with Packet Reversed Packet Combining Scheme, Modified Packet Combining Scheme and the Combination”, ICTP, Italy, Pre Print, IC/2007/43.
7.    Chandan T Bhunia, (2001)“ARQ-Review and Modifications”, J IETE Tech Rev. Vol 18, pp381-401, Sept.
8.    Chandan T Bhunia, (2006) “New and Modified ARQ Schemes and their performance analysis, Int’l J HIT Transaction on ECCN, No 1, Vol 1, pp1-26,  HIT , India
9.    E J Weldon Jr, An Improved Selective Repeat ARQ Strategy, IEEE Trans Comm, Vol 30, No 3, March'82, pp 480-486.
10.    Yu Dong Yao, An Effective Go-Back-N ARQ Scheme for Variable Error Rate Channels, Vol 43, No 1, Jan’95, pp 20-23.