Selective repeat ARQ with efficient utilization of bitmaps

• US 6,778,501 B1
• Filed: 04/04/2000
• Issued: 08/17/2004
• Est. Priority Date: 04/07/1999
• Status: Expired due to Term

• Current Assignee: Wi-Fi One, LLC (Inception Holdings, LLC)
• Original Assignee: Telefonaktiebolaget LM Ericsson
• Inventors: Rydnell, Gunnar, Nilsson, Fredrik, Miklos, György, Li, Hui, Lindskog, Jan, Malmgren, Göran
• Primary Examiner(s): VANDERPUYE, KENNETH N
• Application Number:
  US09/543,156
• Time in Patent Office: 1,596 Days
• Field of Search: 714/748, 714/749, 370/394, 370/242, 370/310, 370/473, 370/236
• US Class Current: 370/236
• CPC Class Codes: H04L 1/1614 using bitmaps
• CPC Class Codes: H04L 1/1809 Selective-repeat protocols
• CPC Class Codes: H04L 1/187 Details of sliding window management

Abstract

In a wireline or wireless telecommunications system or data network, which employs a Selective Repeat Automatic Repeat Request (ARQ) to convey data packet reception status for a sequence of data packets grouped together into a number of blocks of data packets, partial bit mapping is employed to improve efficiency, particularly with respect to bandwidth. This may be accomplished, more specifically, by including in the ARQ message that is sent from the receiver to the sender, a number of partial bitmaps, along with a corresponding number of bitmap block numbers, where a first bitmap block number identifies a particular one of the blocks of data packets and the corresponding bitmap defines the reception status of the data packets in that block. Each of the remaining bitmap block numbers identify an additional block of data packets relative to the first block of data packets. Accordingly, the remaining bitmap block numbers require fewer bits to identify their corresponding data packet blocks.

Claims

1. A method for acknowledging data packet reception status, in accordance with a Selective Repeat ARQ scheme, for a sequence of data packets being transmitted from a sending node to a receiving node in a telecommunications network, wherein each data packet is assigned a sequence number indicating an order of transmission, and wherein the sequence of data packets are grouped into blocks of data packets, said method comprising the steps of:

generating a first bitmap number which identifies a first block of data packets by defining the sequence number of the first data packet in the first block of data packets;

generating a first bitmap which defines the reception status for the data packets associated with the first block of data packets;

generating a second bitmap number which identifies a second block of data packets relative to the first block of data packets;

generating a second bitmap which defines the reception status for the data packets associated with the second block of data packets; and

transmitting the first bitmap number, the first bitmap, the second bitmap number and the second bitmap from the receiver to the sender.

2. The method of claim 1, wherein the first bitmap number comprises a first number of bits required to distinguish the sequence number associated with the first data packet in the first block of data packets from the sequence number associated with the first data packet in all remaining blocks of data packets.

3. The method of claim 2, wherein the second bitmap number identifies the second block of data packets by defining the sequence number of the first data packet in the second block of data packets, as a function of the sequence number associated with the first data packet in the first block of data packets.

4. The method of claim 3, wherein the second bitmap number comprises a second number of bits required to identify the sequence number associated with the first data packet in the second block of data packets as a function of the sequence number of the first data packet in the first block of data packets.

5. The method of claim 4, wherein the second number of bits associated with the second bitmap number is less than the first number of bits associated with the first bitmap number.

6. A method for acknowledging protocol data unit (PDU) reception status in accordance with a Selective Repeat ARQ scheme, wherein the PDUs are grouped into a first number of blocks of PDUs, and each PDU is assigned a sequence number indicating an order of transmission, and wherein the Selective Repeat ARQ scheme employs a transmission window that defines an interval of PDUs that are eligible for transmission from a sender to a receiver, said method comprising the steps of:

generating a first bitmap block number, said first bitmap block number identifying a first block of PDUs wherein said first block of PDUs, defined by said first bitmap block number, is any one of the second number of blocks of PDUs;

generating a first bitmap, wherein said first bitmap defines the reception status for the PDUs in the first block of PDUs;

generating a second bitmap block number, said second bitmap block number identifying a second block of PDUs relative to said first block of PDUs;

generating a second bitmap, wherein said second bitmap defines the reception status for the PDUs in the second block of PDUs; and

transmitting a control PDU from the receiver to the sender, wherein the control PDU contains the first bitmap block number, the first bitmap, the second bitmap block number and the second bitmap.

7. The method of claim 6, wherein the transmission window comprises a second number of blocks of PDUs, said second number of blocks of PDUs being no greater than one-half of said first number of blocks of PDUs.

8. The method of claim 7, wherein said first bitmap block number comprises a first number of bits required to distinguish the sequence number associated with the first PDU in the first block of PDUs from the sequence number associated with the first PDU in all remaining blocks of PDUs;

and wherein said second bitmap block number comprises a second number of bits required to identify the sequence number associated with the first PDU in the second block of PDUs as a function of the sequence number of the first PDU in the first block of PDUs; and

wherein said first number of bits associated with said first bitmap block number is greater than said second number of bits associated with said second bitmap block number.

9. The method of claim 6 further comprising the step of:

setting a control bit in the control PDU, wherein the control bit, when set, indicates that said first bitmap identifies a PDU in the first block of PDUs as not being successfully received, wherein the PDU was transmitted from the sender to the receiver before any other PDUs currently in the transmission window that have not been successfully received.

10. The method of claim 6 further comprising the step of:

setting a control bit in the control PDU, wherein the control bit, when set, indicates a STOP condition, and wherein the receiver, while the control bit is set, cannot accept PDUs that have not been transmitted previously.

11. A method for determining reception status, in accordance with a Selective Repeat ARQ scheme, for a number of protocol data units (PDUs) that have been transmitted from a sender to a receiver, said PDUs being grouped into a first number of blocks of PDUs, wherein each of the PDUs are identified by a corresponding sequence number, and wherein the Selective Repeat ARQ scheme employs a transmission window that defines an interval of PDUs that are currently eligible for transmission, said interval of PDUs being grouped into a second number of blocks of PDUs, which is a subset of said first number of blocks of PDUs, said method comprising the steps of:

receiving, at the sender, a control PDU transmitted by the receiver, wherein the control PDU contains a first bitmap block number, a second bitmap block number, a first bitmap, and a second bitmap;

identifying a first block of PDUs, from amongst the second number of blocks of PDUs that are associated with the transmission window, based on the value of the first bitmap block number;

determining the reception status for the PDUs associated with the first block of PDUs, as a function of the first bitmap;

identifying a second block of PDUs, from amongst the second number of blocks of PDUs that are associated with the transmission window, based on the value of the second bitmap block number and the value of the first bitmap block number, wherein the second bitmap block number identifies the second block of PDUs relative to the first block of PDUs; and

determining the reception status for the PDUs associated with the second block of PDUs, as a function of the second bitmap.

12. The method of claim 11, wherein the first bitmap block number defines the sequence number of the first PDU in the first block of PDUs;

and wherein the second bitmap block number defines the sequence number of the first PDU in the second block of PDUs.

13. The method of claim 12, wherein the first bitmap block number comprises a first number of bits required to distinguish the sequence number of the first PDU in the first block of PDUs from the sequence number of the first PDU in any of the remaining first number of blocks of PDUs;

and wherein the second bitmap block number comprises a second number of bits required to identify the sequence number of the first PDU in the second block of PDUs as a function of the sequence number of the first PDU in the first block of PDUs; and

wherein the first number of bits associated with the first bitmap block number is greater than the second number of bits associated with the second bitmap block number.

14. The method of claim 11 further comprising the step of:

determining whether a control bit in the control PDU is set; and

if the control bit is set, identifying the first block of PDUs as containing a PDU that has not been successfully received, which also has a sequence number indicating the PDU was transmitted before any other PDUs in the transmission window that have not yet been successfully received.

15. The method of claim 11 further comprising the step of:

determining whether a control bit in the control PDU is set, wherein the control bit, when set, indicates a STOP condition, during which, the receiver cannot accept any PDU that has not been previously transmitted.

16. The method of claim 15 further comprising the steps of:

prohibiting the transmission of PDUs to the receiver that have not been previously transmitted, if it is determined that the control bit is set.

17. In a telecommunication system a control protocol data unit sent by a receiver to a sender in said telecommunication system for conveying reception status in accordance with a Selective Repeat ARQ scheme, for a number of protocol data units (PDUs) that have been transmitted from the sender to the receiver, the PDUs being grouped into a first number of blocks, said control protocol data unit comprising:

a transmission window for defining an interval of PDUs eligible for transmission;

a first bitmap block number, for identifying a first block of PDUs;

a first bitmap, for conveying the reception status for a number of PDUs in the first block of PDUs;

a second bitmap block number, for identifying a second block of PDUs relative to said first block of PDUs; and

a second bitmap, for conveying the reception status for a number of PDUs in with the second block of PDUs.

18. The control protocol data unit of claim 17, wherein the PDUs eligible for transmission are grouped into a second number of blocks, said second number of blocks being a subset of said first number of blocks.

19. The control protocol data unit of claim 18, wherein said first bitmap block number comprises a first number of bits required to uniquely identify the first block of PDUs;

and wherein said second bitmap block number comprises a second number of bits required to uniquely identify the second block of PDUs, relative to the identity of the first block of PDUs, and wherein the first block of PDUs and the second block of PDUs are part of the second number of blocks that make up the transmission window.

20. The control protocol data unit of claim 19, wherein the first number of bits associated with said first bitmap block number is greater than the second number of bits associated with said second bitmap block number.

21. The control protocol data unit of claim 17 further comprising:

a CumAck bit, for notifying the sender that said first block of PDUs contains a PDU that was not successfully received, which also has a sequence number indicating that the PDU was transmitted before any other PDUs associated with the transmission window that have not been successfully received.

22. The control protocol data unit of claim 17 further comprising:

a flow control bit, for notifying the sender of a STOP condition, during which the receiver cannot accept PDUs that have not previously been transmitted.

23. The control protocol data unit of claim 22, wherein the sender, upon receiving the notification that a STOP condition exists, suspends the transmission of any PDU that has not been previously transmitted.

24. The control protocol data unit of claim 17 further comprising:

a resource request bit, for notifying the sender that additional bandwidth is required by the receiver to provide sufficient reception status feedback for the sender.

25. The control protocol data unit of claim 17 further comprising:

a third bitmap block number, for identifying a third block of PDUs relative to said second block of PDUs; and

a third bitmap, for conveying the reception status for a number of PDUs in the third block of PDUs.

26. The control protocol data unit of claim 17 further comprising:

a third bitmap block number, for identifying a third block of PDUs relative to said first block of PDUs; and

a third bitmap, for conveying the reception status for a number of PDUs in the third block of PDUs.