Adaptive ARQ feedback bandwidth allocation

[0002] The invention relates to the field of telecommunications, more precisely to ARQ actions taken in the data layer (DLC) and is related to existing features proposed in HiperLan/2 standardization.

[0003] Vocabulary

[0004] HiperLan/2 is a standard for high-speed wireless LAN network developed by the European Telecommunications Standards Institute (ETSI). It operates in the 5 GHz frequency band at a data rate up to 54 Mbit/sec. It provides high-speed and short distance connections for the office and factory environment without wired connections. Its range may be enhanced through use of active forwarding nodes. HiperLan/2 is a private system owned and operated by the user. It is an extension or replacement for fixed LANs and is primarily used indoors but it is not inherently limited to that use.

[0005] The LAN networks use digital signals to convey data. Digital messages have to contend with errors in transmission. Error control provides the means to protect transmitted data from errors. Even physical links cannot guarantee that all bits will be transferred without errors. In a communication network it is the responsibility of the error control algorithm to detect those errors and in some cases correct them to support an error free link to upper layers.

[0006] Two error control strategies have been popular. One is Forward Error Correction (FEC) that uses error correction alone. The other is Automatic Repeat Request (ARQ) that uses error detection combined with retransmission of corrupted data. The latter is preferred primarily because it uses fewer overhead bits to detect errors than to correct the error. The following algorithms are used to implement FEC and ARQ.

[0007] Cyclic Redundancy Check (CRC) is a very powerful but easily implemented technique to obtain data reliability by protecting blocks of data called Frames. The transmitter appends an extra n-bit sequence to every frame called Frame Check Sequence (FCS). The FCS holds redundant information about the Frame that helps the transmitter to detect errors in the Frame.

[0008] Computing Parity involves counting the number of ones in the unit of data, and adding a zero or one to make the count odd or even depending on whether odd or even parity is used. An example is a 4-bit unit of data of 1001. For even parity a zero is added to the unit resulting in 10010 for an even number of bits. For odd parity a 1 is added. The result is 10011 for an odd number of bits. Computing parity that is even involves XORing the bits of the data stream together. Computing odd parity XORs the bits and negates the result equivalent to XNOR (˜). The computations are as follows: Even: 1{circumflex over ( )}0{circumflex over ( )}0{circumflex over ( )}1=0; Odd: ˜(1{circumflex over ( )}0{circumflex over ( )}0{circumflex over ( )}1)=1. This system detects single bit errors. If one bit gets flipped due to line noise, there will be an incorrect number of ones in the received data.

[0009] As an example, using the above system assuming even parity, A sends a data unit 10010 and B receives 11010. B computes the parity as 1{circumflex over ( )}1{circumflex over ( )}0{circumflex over ( )}1{circumflex over ( )}=1. Since the parity bits do not match (even parity the XOR result should be 0), there is an error. Rather than computing parity on the data bits and comparing them to the parity bit, the receiver will actually XOR the data bits and the parity bit. If the result is zero the data unit passes. If a 1 results there is an error. The parity generation function is expressed as P(d1,d2,d3, . . . dn)=P and P(d1,d2,d3 . . . dn,P)=0 if no error occurs. Since there is no indication of which bit is flipped there is no way to correct it.

[0010] Unfortunately, if two bits are flipped, A sends 10010 and B receives 11000 and B computes parity as 1{circumflex over ( )}1{circumflex over ( )}0{circumflex over ( )}0{circumflex over ( )}0{circumflex over ( )}=0. The result shows no error. Therefore, to use this system you must assume a low probability of two errors in one data unit.

[0011] Another error checking procedure is Parallel Parity that is based on regular parity. It can detect whether or not there was an error and which bit is flipped. This method is implemented on a block of data that is made of sum words. Referring to FIG. 1, the parity is then added to the columns and rows. Every row has bit parity. If one block is flipped, the result is two parity errors, one in the rows and one in the column's parity. The intersection of the row and column of the flipped bit identifies the error.

[0012] Yet another way to check for errors is Check Sum. It uses modulo summation to detect errors in a stream of data. The sum operation is operated on a package of bytes where the last byte is the Check Sum number. When you add all the numbers in the package the sum should be zero. In octets the addition is modulo 256. If the sum reaches 256 it turns to zero. If it doesn't we know that there is an error. It cannot correct for errors. In the example of FIG. 2 there are blocks of octets represented in the Hexadecimal. The last number in every row is a summation. If there is no error it is zero

[0013] The invention pertains to adaptive allocation of ARQ feedback bandwidth to conserve bandwidth. The data stream scheduler is informed of the status of a PDU to be retransmitted at the receiver to allow adaptive scheduling of ARQ feedback bandwidth during data transmission. Information about the receiver is provided in the ARQ feedback PDU that may be the ABIR flag. This allows the receiver to adjust the bandwidth to meet the need to supply enough bandwidth for message retransmission traffic.

[0014] A platform for implementing the invention is the HIPERLAN/2 protocol developed by the European Telecommunications Standards Institute (ETSI). In the ARQ protocol of HIPERLAN/2, data PDUs are selectively acknowledged by using an ARQ feedback message. Such an ARQ feedback message contains three bitmaps with eight bits each. The receiver and transmitter windows are divided into blocks each the same size as a bitmap. The bitmaps can be shifted over the window so that a bit therein belongs to a particular data PDU. If a bit is set to 1, the assigned data PDU is acknowledged. If the bit is set to zero the assigned PDU has to be retransmitted.

[0015] A data PDU consists of a 48-byte payload field. The number of acknowledged data PDUs is limited per ARQ feedback message resulting in variance in the number of feedback messages. In the HIPERLAN/2 protocol, the scheduler is responsible for granting transmission capacity for the ARQ feedback messages. A robust scheduling algorithm adapts the feedback bandwidth to the current transmission rate. The transmission rate of ARQ feedback messages depends on factors such as negotiated window size, round trip time and fading behavior of the physical indoor channel that results in burst errors.

[0016] In the HiperLAN/2 protocol the receiver of data PDUs (i.e. the transmitter of ARQ feedback messages) may request an increase in the ARQ signaling bandwidth. One bit is available for the request that is the ABIR. The state of the ABIR bit determines the need for bandwidth. A null indicates no need for more bandwidth and 1 indicates the need for more bandwidth. This implementation eliminates the need for a sophisticated scheduler algorithm

[0017] Accordingly, it is an object of the Invention to preserve bandwidth when missing data units are retransmitted to a bitmap.

[0018] It is another object of the invention to decrease the number of retransmissions of data units missing from a bitmap.

[0019] It is yet another object of this invention to eliminate the need for algorithms to detect the errors in data units.

[0020] FIG. 1 is a table showing how Parallel Parity tables are computed to detect errors in data unit transmission.

[0021] FIG. 2 is a table showing how Check Sum numbers are computed to detect errors in data unit transmissions.

[0022] FIG. 3 is a graph showing an example of the adaptive ARQ feedback.

[0023] It is a goal of wireless LAN networks to keep high message throughput. One way to do that is to keep ARQ feedback small. In the existing ARQ HIPERLAN/2 protocol the data PDUs are selectively acknowledged and the missing data PDUs are retransmitted. In order to keep continuous data flow the receiver acknowledges missing PDUs to continuously update the sliding windows. Because the number of data PDUs that can be acknowledged in one ARQ feedback message is limited and the packet error rate varies, variable allocation of ARQ feedback messages is required. The solution is adaptive ARQ bandwidth allocation in the uplink channel.

[0024] In a wireless LAN network it is difficult to design a scheduling algorithm that allows for efficient adaptive ARQ feedback message scheduling. Such an algorithm needs to take into consideration information on the rapidly varying characteristics such as the interface channel and the mobile phone, etc. This invention presents an alternative way to update the varying needs of ARQ feedback bandwidth allocation by informing the scheduler of the current error status at the receiver. Accordingly the scheduler updates the ARQ feedback bandwidth as required. The advantage of this solution is no complicated algorithms. The ARQ feedback bandwidth allocation is adapted to the current message state at the receiver and does not depend on theoretical predictions and it is simple to implement.

[0025] At present, in a wireless LAN network using the HIPERLAN/2 protocol, when new data PDUs are ready to be transmitted, the transmitter requests a connection with a remote host. Based on the number of PDUs advertised by the transmitter and the level of activity of the other MTs associated with the AP, the scheduler grants channel resources to the initiating entity that may be either a MT or AP. At this time an algorithm evaluates the ARQ bandwidth needed to acknowledge the new data. In case the update of the transmit window is stalled an algorithm distinguishes between an urgent necessity for ARQ feedback or a minimal ARQ feedback bandwidth that is sufficient in a stable environment. A stable environment is one in which no deep fading or interference is experienced.

[0026] The receiver is aware of the maximum number of ARQ feedback messages granted by the scheduler. The receiver does not advertise how many PDUs have actually been sent in one frame. The receiver assumes that it has received all PDUs that are sent. If many PDUs are missing and no new PDUs have been detected yet, the receiver has no means of differentiating among a PDU that got lost and one that has not been received or one not yet transmitted. Therefore, the receiver's strategy is to acknowledge all PDUs up to the top edge of the receive window as long as bitmap space is available in the granted ARQ feedback. When all PDUs are used, the receiver stops acknowledging new received PDUs and stores them in the Rx buffer if they are contained in the receive window. The result is the allocation of extra bandwidth.

[0027] In the present invention, the HIPERLAN/2 protocol has an ARQ feedback that contains a bit (ABIR flag) used by the receiver to increase ARQ signaling bandwidth. The ABIR-bit, when set to 1, indicates that more bandwidth is needed for the receiver to allow ARQ feedback. When the bit is set to 0 it indicates no need for extra bandwidth. This bit is only used for downlink traffic. In uplink traffic when the AP is the receiver, this bit could be internal to an AP. The ABIR flag is used to provide feedback of the receiver's current status that will be used by the scheduler to allocate enough ARQ feedback bandwidth.

[0028] The receiver buffers all PDUs received within its receive window. The bottom edge of the received window is updated to the cumulative acknowledged PDU, that is the first missing PDU. All following PDUs are stored. Because there is a limit on the number of data PDUs that can be acknowledged it is possible that not all PDUs can be acknowledged depending on the number of ARQ feedbacks granted. The receiver measures the delay between the last buffered PDU (highest sequence number in the Rx buffer) and the last acknowledged PDU in the previous feedback frame. Therefore, once a certain threshold is detected the receiver requires more ARQ feedback messages. The ABIR flag is set and with that, the receiver catches up by acknowledging more PDUs within the next feedback frame. Once the ABIR flag is not set, the initial feedback bandwidth grant reverts to its previous condition.

[0029] The working assumption on the receiver side is that the receiver considers only the Highest Acknowledged Sequence Number (HASN) that is the highest sequence number that was acknowledged in the previous feedback frame. The highest PDU sequence number that is the sequence number, is the sequence number of the last received data PDU. Meanwhile, PDUs not acknowledged are stored in the Rx buffer. The receiver evaluates whether or not more ARQ is required in the next feedback frame based on the following rule:

[0030] # unacknowledged PDUs=Highest PDU sequence number—HASN;

[0031] if (# unacknowledged PDUs>threshold)

[0032] ABIR=1;

[0033] Else

[0034] ABIR=0,

[0035] Where # means ‘number of’ and threshold is the maximum number of non-acknowledged received PDUs. Furthermore, the threshold is related to the roundtrip time (rtt) and is specified by an integer number of PDUs. This allows for reasonable QoS specified by characteristics such as high throughput and continuous data flow as used for instance in windows updating.

[0036] Referring to FIG. 3, the working assumption of the scheduler is that during the connection time the transmit window size is negotiated. Therefore, the scheduler gets some information about the number of PDUs that can be sent without an acknowledgement. According to a mapping list it will grant the minimum number of ARQ feedback messages required. For instance, a measure is the transmit window size versus the number of ARQ feedback messages. The mapping list should be chosen such that a high throughput is guaranteed. If the communication channel is such that there is minor data corruption, then only a few ARQ feedback messages are needed.

[0037] As long as the ABIR Flag is not set, the receiver maintains a certain QoS by acknowledging enough PDUs for the minimal number of ARQ feedback messages. However, if the difference between the acknowledged and received unacknowledged PDUs reaches a critical point the receiver will set the ABIR flag. Then for the next feedback frame the scheduler may double the feedback bandwidth. The goal is to have an exponential increase in bandwidth to catch up acknowledging PDUs as fast as possible in order to restore the minimal bandwidth status. Accordingly, if the experienced number of non-acknowledged data PDUs is below the threshold during the next check, the ABIR flag is not set and the number of ARQ feedback message is returned to its initial value, or it may be halved to get an exponential decrease. The scheduler keeps track of the ARQ feedback bandwidth it has granted in the previous feedback frame.

[0038] Still referring to FIG. 3, based on a mapping list a certain number of ARQ feedback messages are granted by the scheduler at time t0. Then at time t2 the receiver detects that the acknowledgements are lagging and that it should acknowledge more PDUs during the next feedback frame. To update the sliding window only one ARQ feedback is needed. The smallest not received sequence number is used to update the window. In response, the ABIR flag is set in the corresponding ARQ feedback message. At time t3, the scheduler doubles the original feedback bandwidth. In this example the receiver is still not able to catch up acknowledging PDUs compared to the number received. Therefore, the receiver applies for more bandwidth and sets the ABIR flag accordingly. If conditions allow, the scheduler again doubles the number of ARQ feedback messages granted at t4. The receiver has caught up at t5 and the ABIR flag is not set and minimal bandwidth is granted. It should be noted that the allocation sequence of ARQ feedback messages does not need to be sequential. It may be irregular. Another way to manage the PDU stream to update for errors is to decrease the number of ARQ feedback messages by reducing the number of ARQ feedback messages to the state of the frame until the initial number of ARQ feedback messages is reached as measured during connection setup.

[0039] The description of the invention is by way of illustration and does not limit its scope. Alternative implementations may be employed to achieve the invention.