HK1118661A

HK1118661A - Improved data delivery in conjunction with a hybrid automatic retransmission mechanism in cdma communication systems

Info

Publication number: HK1118661A
Application number: HK08112503.7A
Authority: HK
Inventors: H 瓦亚诺斯 A; 马拉迪 D; Y D 何 S
Original assignee: 高通股份有限公司
Priority date: 2002-05-13
Filing date: 2008-11-14
Publication date: 2009-02-13

Description

Improved data transfer in a hybrid automatic retransmission mechanism in a CDMA communication system

This application has benefited from provisional U.S. application Ser. No. 60/380408 entitled "A Method and apparatus for Stall Avoidance in a Communication System", filed on 5/13.2002, which is incorporated herein by reference for all purposes.

Background

FIELD

The present invention relates generally to data communications, and more particularly to techniques for improving data transfer performance to higher layers and a hybrid automatic repeat request (HARQ) mechanism in a CDMA communication system.

Background

Wireless communication systems are widely deployed to provide various types of services such as voice, packet data, and so on. These systems may be multiple-access systems capable of supporting communication for multiple users, and may be based on Code Division Multiple Access (CDMA), Time Division Multiple Access (TDMA), Frequency Division Multiple Access (FDMA), or some other multiple access technique. CDMA systems may provide advantages over other types of systems, including increased system capacity.

To improve the reliability of data transmission, some newer generation CDMA systems use a Hybrid Automatic Repeat (HARQ) mechanism that can retransmit packets that were incorrectly decoded by the receiver. For example, in W-CDMA release 5, HARQ is included in the Medium Access Control (MAC) -hs sublayer, which resides on top of the physical layer. On the downlink, the HARQ entity at the transmitter processes the data into packets, which are assigned sequential Transmission Sequence Numbers (TSNs). These packets may then be transmitted to the receiver in order based on their TSNs.

At the receiver, the corresponding HARQ entity receives the packet transmission and attempts to decode and recover each transmitted packet. However, some packets may not be decoded correctly (i.e., erased) due to the degradation of packet transmission caused by the radio link. When this occurs, a Negative Acknowledgement (NAK) is sent back from the receiver to the transmitter to initiate retransmission of each erased packet.

The receiver HARQ entity also has the task of providing the recovered packets (i.e. those correctly decoded) to higher layers. In W-CDMA, higher layers wait for data in the correct order, as determined by the TSN of the packet. However, in the HARQ mechanism, the HARQ entity may recover out of order due to retransmissions of the packet by the receiver. The result is that a re-ordering entity is used at the receiver to buffer and re-order the packets as they are recovered by the receiver HARQ. The re-ordering entity then provides the packets in the correct order in which they are available to the higher layers.

If the packets are recovered out of order by the receiver HARQ entity, the re-ordering entity may "delay" or delay delivery of the recovered packets to higher layers. In particular, whenever a packet loss is detected, the re-ordering entity will delay delivery of data to higher layers until (1) the lost packet is recovered by the receiver HARQ, or (2) the re-ordering entity is confident that the lost packet was lost and will not be recoverable by HARQ. If the second condition is true, another retransmission mechanism at a higher layer may be relied upon to retransmit the lost data.

It is challenging to determine the appropriate amount of time to wait by the re-ordering entity before declaring that a lost packet is lost and providing the packet that has been recovered to higher layers. One goal is to avoid delaying the delivery of data to higher layers, since it is undesirable to wait for lost packets that cannot be recovered for a long time or on an irregular basis. The goal is preferably a short latency. One goal of collisions is to minimize the error declaration of lost packets to minimize unnecessary retransmissions with long delays by higher layers (if supported) or packet loss (if no retransmissions are implemented by higher layers). A long latency provides better assurance that the packet is actually lost. This problem is commonly referred to in the art as "delay avoidance".

There is therefore a need in the art for techniques to improve stall avoidance performance in CDMA systems.

SUMMARY

Techniques are provided herein to mitigate the effects of lost packets and improve stall avoidance performance. In particular, these techniques may be used to more efficiently handle situations where the delivery of data to higher layers is delayed due to the loss of payload. These techniques use information available from the HARQ process to better determine whether to transmit data to higher layers.

Various mechanisms are provided herein that may be used alone or in combination to improve stall avoidance performance. These mechanisms include (1) controlling the priority transmission of each packet over a channel instead of a packet, (2) maintaining an inactivity timer for each HARQ channel, (3) sending a flush (flush) indication to "flush" (flush) one or more HARQ channels, which in turn may result in data being flushed by the re-ordering entity to higher layers, (4) forming a set of candidate HARQ channels for each missing packet, which are channels that may be used for the missing packet, (5) determining whether the missing packet is lost based on activity or inactivity detected on the HARQ channels within the candidate set. These mechanisms are described in detail below.

In one embodiment, a method is provided for transmitting data recovered by a HARQ entity to higher layers in a correct order in a CDMA communication system. According to the method, packets are received by a re-ordering entity from a HARQ entity, and missing packets of the received packets are detected. Packets may be transmitted in order based on a Transmission Sequence Number (TSN) assigned to the packet, and missing packets may be detected based on the TSN of the received packet. Transmitting a received packet later than the lost packet is delayed because higher layers expect in-order data. It is then determined whether each missing packet is (1) subsequently received from the HARQ entity, or (2) lost, by successively removing the HARQ channels that may be used to transmit the missing packet. The received packets previously delayed for each missing packet are transmitted after the missing packet is determined to be lost or received.

A set of candidate HARQ channels may be formed for each missing packet. The candidate set may include, for example, all HARQ channels that are active (or a short time later) when a packet is detected to be lost. The HARQ channel may be removed from the set if (1) it is inactive for a certain period of time, (2) the packet is recovered from the HARQ channel, (3) a new packet is detected to be sent on the HARQ channel, or (4) an indication is received to flush the HARQ channel. An inactivity timer may be used for each HARQ channel to determine whether the channel is inactive, and may be restarted whenever a packet transmission is received on the channel.

These techniques may be used for various CDMA systems, such as W-CDMA systems implementing release 5 or beyond.

Various aspects and embodiments of the invention are described in more detail hereinafter. The invention also provides methods, processors, transmitter units, receiver units, base stations, terminals, systems and other apparatuses and elements that implement various aspects, embodiments and features of the invention, as will be described in detail below.

Detailed description of the drawings

The features, nature, and advantages of the present invention will become more apparent from the detailed description set forth below when taken in conjunction with the drawings in which like reference characters identify correspondingly throughout and wherein:

fig. 1 is a diagram of a CDMA communication system;

FIG. 2 is a diagram of the layer structure defined by W-CDMA Release 5;

fig. 3 is a diagram illustrating data encapsulation performed by a node B for High Speed Data Packet Access (HSDPA) transmissions over the HS-DSCH;

FIGS. 4A and 4B are diagrams of MAC-hs entities defined by W-CDMA Release 5 for the UTRAN side and the UE side, respectively;

fig. 5 is a diagram illustrating the timing relationship between various downlink and uplink physical channels for implementing HSDPA;

FIGS. 6A and 6B are diagrams illustrating windows maintained for a particular priority queue and by a receiver re-ordering entity, respectively;

FIGS. 7A through 7D illustrate four data transfer scenarios, wherein various mechanisms rely on flushing data from the reordering queue to a higher level;

fig. 8 is a flow diagram of a process implemented by a transmitter HARQ entity to send a packet on a particular HARQ channel;

figures 9A and 9B show a flow diagram of a process implemented by a receiver HARQ entity to receive a packet on a particular HARQ channel;

fig. 9C is a flow diagram of a process implemented by a receiver HARQ entity to maintain all inactivity timers for HARQ channels;

fig. 9D is a flow diagram of a process implemented by a receiver HARQ entity upon receiving a flushing indication on a control message;

fig. 10 is a flow diagram of a process implemented by the transmitter re-ordering entity for a particular priority queue;

11A and 11B show a process flow diagram for a receiver re-ordering entity implementation for a particular priority queue;

fig. 11C shows a flow diagram of an embodiment of a process implemented by the receiver re-ordering entity whenever a delay timer timeout indication is received.

Fig. 11D shows a flow diagram of an embodiment of a process implemented by the receiver re-ordering entity for a complete process on a particular HARQ.

Fig. 12 shows a general process flow diagram for receiving and transmitting packets from a HARQ entity to a higher layer implementation by a receiver re-ordering entity; and

fig. 13 is a block diagram of an embodiment of a node B and a UE.

Detailed Description

Fig. 1 is a diagram of a CDMA communication system 100 in which the improved delay avoidance techniques described herein may be implemented. System 100 includes a plurality of base stations 104 (only one base station and two terminals are shown in fig. 1) that communicate with a plurality of terminals 106. A base station is also called a node B, a Base Transceiver System (BTS), an access point, or some other terminology. The base station may be part of a UMTS radio access network (UTRAN). A base station and/or its coverage area are typically referred to as a cell, depending on the context in which the term is used.

A terminal may also be called a User Equipment (UE), a mobile station, a remote station, an access terminal, or some other terminology. Each terminal may communicate with one or more base stations on the downlink and/or uplink at any given moment, depending on whether the terminal is active or whether soft handoff is supported for data transmission and whether the terminal is in soft handoff. The downlink (i.e., forward link) refers to transmission from the base station to the terminal, and the uplink (i.e., reverse link) refers to transmission from the terminal to the base station.

The techniques for improving stall avoidance performance described herein may be implemented in various CDMA communication systems. Thus, CDMA system 100 may implement one or more commonly known CDMA standards, such as W-CDMA, CDMA2000, IS-856, IS-95, and others. For clarity, various aspects, embodiments, and implementation details for improving stall avoidance performance are described below for a CDMA system supporting W-CDMA release 5. Using W-CDMA terminology, the base stations, terminals, and system controllers in the following description are referred to as nodes B, UE and RNCs, respectively.

W-CDMA supports various types of services such as voice, packet data, and the like. In W-CDMA, data to be transmitted to a particular UE is processed as belonging to one or more transport channels. These transport channels are then mapped to one or more physical channels (at the physical layer) assigned to the UE. The physical channel is defined by various parameters (e.g., carrier frequency, scrambling code, channelization code, etc.).

W-CDMA release 5 further supports High Speed Downlink Packet Access (HSDPA), which is a set of transport/physical channels and procedures defined as part of the UTRAN enabling high speed transmission of data on the downlink. For HSDPA, data is processed in packets, which are then multiplexed onto a high speed downlink shared channel (HS-DSCH), which is a downlink transport channel. The HS-DSCH is then mapped to a high speed physical downlink shared channel (HS-PDSCH), which may be shared by multiple UEs. For W-CDMA, each packet transmission time interval on the HS-PDSCH is 2 milliseconds, which is referred to as a Transmission Time Interval (TTI).

The following transport and physical channels defined by W-CDMA are referred to herein as:

● DPCH-dedicated physical channel

● HS-DSCH-high speed downlink shared channel

● HS-SCCH-shared control physical channel for HS-DSCH

● HS-PDSCH-high speed physical downlink shared channel

● HS-DPCCH-high speed dedicated physical control channel (on uplink)

The HS-PDSCH may be used to transmit data for multiple UEs in a time and code division multiplexed (TDM/CDM) manner. The control information for the HS-PDSCH, including various parameters for correct reception of the HS-PDSCH, is transmitted on the associated HS-SCCH. The HS-DPCCH is used to carry feedback from the UE to report correctly or incorrectly received (i.e., erased) packets.

Fig. 2 is a layer structure diagram defined by a W-CDMA release 5 layer structure 200, including a Radio Link Control (RLC) layer 210, a Medium Access Control (MAC) layer 220, and a physical layer 230. The RLC layer implements Automatic Retransmission (ARQ) of data and typically resides at a Radio Network Controller (RNC). Retransmissions over the RLC layer are generally associated with long delays due to long round-trip times between the RNC and the UE. At the RLC layer, data is processed as belonging to a logical channel.

For W-CDMA release 5, the MAC layer is further divided into a MAC-d sublayer 222 and a MAC-hs sublayer 224. The MAC-d sublayer implements a set of functions including (1) mapping logical channels onto common and dedicated transport channels, (2) multiplexing one or more logical channels onto transport channels (C/T MUX), (3) encryption/decryption, etc. The MAC-d sublayer provides data flows to the MAC-hs sublayer, each data flow being associated with certain scheduling attributes.

The MAC-hs sublayer implements the specific functions associated with HSDPA, as described below. The MAC-hs sublayer further provides an interface between the MAC-h sublayer and the physical layer.

The physical layer provides a mechanism for sending data for the MAC layer and signaling for higher layers.

The various layers and sub-layers of W-CDMA are described in various standard documents, which are publicly available.

Fig. 3 is a diagram illustrating the data encapsulation performed by the node B for transmission on the HS-DSCH. In W-CDMA, data transmitted on the downlink is provided by the RLC layer within RLC protocol data units (RLC PDUs), each of which includes a Sequence Number (SN) and data. The MAC-d sublayer receives RLC PDUs for one or more logical channels and, for each RLC PDU, inserts a (C/T) field to form a corresponding MAC-d PDU. The C/T field identifies the logical channel associated with the RLC PDU.

The MAC-hs sublayer receives the MAC-d PDUs and forms MAC-hs PDUs. For W-CDMA release 5, each MAC-d flow may include data for one or more logical channels at the RLC layer, and each MAC-d PDU may be associated with a particular priority. Since data is sent based on priority and available resources, data with different priorities is stored in different priority queues within the MAC-hs sublayer. Thereafter, data is retrieved from the appropriate priority queue, as needed, and further processed for transmission on the HS-DSCH.

To form a MAC-hs PDU, the MAC-hs sublayer first receives and serially links one or more MAC-d PDUs from a particular priority queue to form a payload for the MAC-hs PDU. Padding bits may be added to fill the payload as necessary. The MAC-hs sublayer then adds a header to the payload to form a MAC-hs PDU.

For W-CDMA release 5, the MAC-hs header includes (1) a size index id (sid) field indicating the length of each MAC-d PDU in the MAC-hs PDU, (2) an N field indicating the number of MAC-d PDUs included in the MAC-hs PDU, (3) a Transmission Sequence Number (TSN) allocated and used to uniquely identify the MAC-hs PDU, and (4) a queue id (qid) field indicating a specific priority queue from which the MAC-d PDUs included in the MAC-hs PDU are acquired. The TSN allows the UE to identify MAC-hs PDUs that have been recovered and to provide the RLC layer with MAC-d PDUs in order, which expects data to be sent to it in the correct order. A mechanism is also provided by W-CDMA to send MAC-hs PDUs of different sizes within the same packet, but is not described here for simplicity.

The MAC-hs PDUs are generated on-the-fly as needed. Each MAC-HS PDU is sent in a TTI of 2 ms, which is the transmission unit on the HS-DSCH. For simplicity, MAC-hs PDUs are referred to herein as "packets".

Control information is sent concurrently on the shared HS-SCCH with each packet transmission. The control information includes (1) HARQ process id (hid), (2) new data indicator, (3) information identifying the control information and the particular IE to which the corresponding data is transmitted, and (4) other information not described herein. The HID indicates the specific HARQ process used for the packet. Each packet may be sent and possibly retransmitted one or more times until (1) the UTRAN receives ACK feedback on the HS-DPCCH of the packet, or (2) the transmitter decides to abandon the packet transmission. Each packet is associated with a particular HARQ process, which is a stop and wait (SAW) protocol instance used to control the transmission/retransmission of that packet. Since three bits are defined for HID, there may be eight packet transactions pending at any given time. The eight HARQ processes may thus be considered as eight "HARQ channels," which may be used to transmit packets, each HARQ channel being associated with and identified by a particular HID value.

The new data indicator is used to indicate a new packet transmission on a particular HARQ channel. To improve decoding performance, the UE typically (soft) combines all received transmissions of the same packet before decoding. The new data indicator informs the UE that the current transmission is for a new packet and that all previously received transmissions for the same HARQ channel (for the previous packet) should be cleared. The new data indicator is a single bit value that toggles between "0" and "1" for consecutive packets sent on the same HARQ channel, while in fact is a 1-bit sequence number for packets sent on the HARQ channel. The UE may thus detect new data by observing the inversion of the new data indicator. The new data indicator is also referred to herein as a "color" bit.

Fig. 4A is a diagram of a MAC-hs entity 224A defined for the UTRAN side by W-CDMA release 5. There is one MAC-HS entity in UTRAN for each cell supporting HS-DSCH transmission. The MAC-HS entity processes the data sent on the HS-DSCH and further manages the physical resource allocation for HSDPA.

The UTRAN MAC-hs entity includes a scheduling/priority processing entity 410, a HARQ entity 420, and an FTRC entity 430. The scheduling/priority processing entity manages the data streams from the MAC-d entity according to its priority, determines a TSN and a priority queue for each packet to be processed, and determines transmission/retransmission of the packet. The data flows from the MAC-d entities may include data with different priorities, which may then be located in different priority queues. Data will thereafter be retrieved from the appropriate priority queue based on priority and resource availability and further processed for transmission/retransmission on the HS-DSCH.

One HARQ entity provides a function of processing HARQ for each UE. The HARQ entity enables transmission and, if necessary, retransmission of packets to ensure reliable transmission of these packets to the UE. The retransmission implementation of the packet is based on feedback from the UE. The feedback is in the form of an Acknowledgement (ACK) to indicate successful decoding of the packet or a Negative Acknowledgement (NACK) to indicate unsuccessful decoding of the packet.

The TFRC entity selects the appropriate transport format and resources for the data to be sent on the HS-DSCH.

Fig. 4B is a MAC-hs entity 224B defined by W-CDMA release 5 for the UE side. The MAC-hs entity handles HSDPA specific functions and comprises a HARQ entity 440, a reordering queue distribution entity 450 and a set of reordering buffers 462, a reordering entity 464, and a disassembly entity 466 for each queue ID configured at the UE. One reordering buffer is therefore provided and associated with each priority queue for the UE.

The UE HARQ entity handles all the tasks required for HARQ (e.g., generates the required ACK/NAK for each received packet transmission). The re-ordering queue distribution entity provides the recovered packets to the appropriate re-ordering buffer based on the queue ID sent for the packet.

The recording entity of each reorder buffer reorders the packets recovered in the buffer according to the TSN assigned to each packet. Each priority queue is associated with its own sequence of TSNs. The re-ordering entity then provides the packets with consecutive TSNs to the de-ordering entity as they are recovered. If a packet with a lower TSN is lost, the packet is not sent to the de-fragmentation entity (i.e., "stalled").

The de-fragmentation entity associated with each re-ordering buffer de-fragments packets provided to it. Disassembly is achieved by removing the header in each packet to obtain the MAC-h s payload (see fig. 3), extracting the MAC-d PDUs included in the MAC-hs payload, and discarding the padding bits (if any). The disassembly entity then provides the MAC-d PDUs to higher layers through the MAC-d sublayer.

W-CDMA release 5 allows multiple re-ordering entities and multiple HARQ processes (or HARQ channels) to operate concurrently. Each re-ordering entity processes data for a particular priority queue and uses a re-ordering buffer for the task. There is a one-to-one correspondence between the reordering queue, the priority queue and the reordering buffer. The HARQ channels are standard stop-and-wait entities and each HARQ channel can carry data (or a reordering buffer) to any priority queue.

Fig. 5 is a diagram illustrating the timing relationship between various downlink and uplink physical channels for implementing HSDPA. The timing relationship shown in fig. 5 is used to specify a particular UE receiving HSDPA transmission.

The uplink DPCCH is used by the UE to send signaling for the uplink DPCH. The timing of the uplink DPCCH is used as a reference and the timing of the other physical channels is provided relative to the timing of the uplink DPCCH.

As shown in fig. 5, the packet is transmitted on the HS-DPSCH to the UE within subframe 512. Each subframe occupies a millisecond time slot. The beginning of subframe 512 occurs at time T₁Some time later, this is the start of a slot for the uplink DPCCH. The packet is sent to the designated UE, which receives and attempts to recover the packet. Based on the results of the decoding process, the UE reports back one of the following: (1) an ACK indicates that the packet was received correctly, (2) a NAK indicates that the packet was received in error (i.e., erased), or (3) nothing (i.e., Discontinuous Transmission (DTX) bits) if it fails to detect (misses) the corresponding HS-SCCH. The feedback information is sent from the IE on the uplink HS-DPCCH within the designated subframe 514. Subframe begins at time T₂Which is defined as 7.5 slots plus a delay τ from the end of the corresponding subframe 512_x(this is a value between 0 and 255 chips). Time delay tau_xIs defined such that in the uplink DPCCH (T)₁) Start of upper slot and uplink HS-DPCCH (T)₂Time elapsed τ between the beginning of sub-frame 514 above_yIs 256 × m, where m is an integer.

The HSDPA design assumptions for control information transmission on the downlink HS-SCCH and uplink HS-DPCCH are as follows:

HS-SCCH (Down link)

● probability { lost HS-SCCH } < 10^-2

● probability { false alarm } is less than or equal to 10^-4

HS-DPCCH (uplink)

● probability { ACK → NAK } ≦ 10^-2

● probability { NAK → ACK } ≦ 10^-4

● probability { DTX → ACK } ≦ 10^-2

The foregoing illustrates that for HS-SCCH on the downlink, (1) the probability of missing a control message with packet processing needs to be less than or equal to 10^-2And (2) the probability that a control message sent to one UE is erroneously detected as being sent to another UE needs to be less than or equal to 10^-4. For the uplink HS-DPCCH, (1) the probability that the ACK sent by the UE is received by the node B as a NAK needs to be less than or equal to 10^-2(2) The probability that a NAK sent by a UE is received as an ACK by a node B needs to be less than or equal to 10^-4And (3) the probability that DTX bits sent by the UE are received by the node B as ACKs needs to be less than or equal to 10^-2。

The ACK/NAK probability described above may be difficult to obtain under some channel conditions, especially when the serving node B for a particular UE is not the one with the best link conditions (as often happens when slowly handing over from one node B to another for HSDPA).

A NAK to ACK error for a given packet results in the transmitter assuming that the packet has been correctly recovered by the receiver. The transmitter may then discard the packet and begin transmission of another packet on the same HARQ. Therefore, NAK to ACK errors result in lost packets at the MAC layer. A higher probability of NAK to ACK errors corresponds to a higher incidence of lost packets at the MAC layer. This in turn leads to a higher probability of delay caused by the re-ordering entity and more retransmissions required at the RLC layer.

The MAC layer needs to ensure that data is sent to higher layers in order. Since the HARQ mechanism using multiple HARQ channels may result in data being recovered by the UE out of order, in W-CDMA release 5, a reordering sublayer is added within the MAC layer. The reordering sublayer buffers packets as it is recovered, rearranges them and delivers consecutive packets to higher layers (as determined by its TSN). If the reordering sublayer detects a lost packet, it stalls (i.e., delays) the transmission of all packets with TSNs later than the TSN of the oldest lost packet based on a gap or hole in the TSN of the recovered packet. When the lost packets are eventually recovered, the reordering sublayer then provides these newly recovered packets along with any previously recovered packets that have been delayed.

W-CDMA release 5 provides three "stall avoidance" mechanisms to allow practical implementation and to avoid the situation where the re-ordering entity waits forever for data that is not retransmitted. These stall avoidance mechanisms include:

● Window-based scheme

● timer-based scheme

● HARQ activity scheme

Each of these schemes is briefly described below.

Window-based scheme

Since each packet is marked with a specific TSN, the recovered packets can be assembled in the correct order at the UE. Although packets may be initially transmitted in order by the node B, the packets may be recovered out of order because a variable number of retransmissions may be required for each packet.

FIG. 6A is a graphical illustration of a window maintained for a particular priority queue. The data of the priority queue is transmitted within a packet identified by a 6-bit TSN. Space number TSN is 2⁶64 (i.e., from 0 to 63). To resolve the ambiguity of the TSN number space caused by the limited size of the TSN field, the receiver may use a window. The window size is typically set at less than half the TSN number space (i.e., < 32), and may be set as small as 8 to 16. Since the window size is smaller than the TSN number space, the order of the packets within the window is unambiguous. There is a tradeoff in determining the window size. If the window is small, the delay avoidance performance at the receiver increases and the receiver buffer size requirement is reduced. However, the probability of delay at the transmitter or the need to interrupt retransmission (depending onIn transmission strategies) increases.

The window advances forward as new packets are received. For the receiver, the leading edge of the window may be set equal to the "most recent" TSN of all recovered packets. The leftmost packet near the window has consecutive "earlier" TSNs. Since the TSN value may be rolled back, the most recent TSN value may actually be less than the earlier TSN whenever the TSN is rolled back. Lost packets with TSNs earlier than the trailing edge of the window are assumed to be lost (i.e., not retransmitted). Thus, as the window advances forward, packets earlier than the edge of the dragging window are "flushed" and sent to higher layers.

The window mechanism may thus be used by the transmitter to flush lost packets at the receiver. However, since the window size may need to be large enough to allow a large number of retransmissions, a large amount of data is needed to flush out the lost packet. Thus, the window-based scheme is marginally effective at the end of a data burst, which is more frequent, such as in the case of browsing generated bursty closed-loop traffic.

Timer based scheme

To address the limitations of the window-based scheme, a timer-based mechanism has also been introduced in W-CDMA release 5. For timer-based schemes, a "long" timer is started whenever a missing packet stalls transmission of a packet to a higher layer at the receiver. If no other missing packets are detected thereafter, the missing packets are assumed to have been recovered once the long timer expires, and all packets deferred by the missing packet are then sent to higher layers. This mechanism requires that a long timer be maintained for each reordering queue (i.e., a maximum of eight long timers for the eight reordering queues defined in W-CDMA release 5).

To ensure proper HARQ operation, the long timer needs to be set longer than the longest amount of time it takes to complete all retransmissions for a given packet. A large number of retransmissions may need to be performed to recover the lost packet. Furthermore, in an asynchronous scheduled retransmission system where the amount of resources available for HSDPA (e.g., as quantized channelization codes and transmit power) changes dynamically, the time required to complete all retransmissions of a lost packet can vary widely. Therefore, the timer value needs to be long. Otherwise, the retransmission of the lost packet may be terminated early due to the timer expiring, in which case the lost packet may need to be retransmitted by higher layers, which is undesirable. The re-ordering entity may need to wait a long time for the long timer to time out until all retransmissions of the missing payload are completed.

In addition to handling the large value of the long timer, if several packets within the window are detected as missing, the timers for these missing packets are effectively concatenated (i.e., the long timer restarts whenever a new missing packet is detected). This may result in an even longer delay in delivering the missing payload to higher layers (the longest possible delay may be twice the worst case long timer value).

HARQ activity scheme

A third approach to avoid delayed recovery packet delivery to higher layers is to detect activity on the HARQ channel. When no packet is expected on any one HARQ channel (i.e. all previous packet processing is completed), then the data in all re-ordering queues may be transmitted by the re-ordering entity to higher layers. This mechanism has several disadvantages. First, this scheme requires no pending packet processing on any HARQ channel to be able to flush packets to higher layers. Second, the receiver "partitions" out the HARQ channel only if the packet processing on that channel is complete. Since the receiver can wait forever for a packet to be recovered on a given HARQ channel (e.g., if the transmitter gives up packet processing), the reordering queue will never be flushed. Third, if a control message is lost (i.e., not detected by the receiver), the packet associated with the control message may be dropped by the re-ordering entity if it is subsequently recovered. This would be the case if another packet with a later TSN was recovered and provided to the re-ordering entity before the packet with the lost control message was retransmitted and the control channel was successfully decoded.

Techniques are provided herein to mitigate the effects of lost packets and improve stall avoidance performance. In particular, these techniques may be used to more efficiently handle cases where data transmission to the MAC-hs sublayer of higher layers is delayed due to lost payload. These techniques use information available from the HARQ process to better determine whether to send data to higher layers.

The following mechanisms may be used to improve stall avoidance performance:

● sending queue IDs on HS-SCCH instead of payload

● maintaining inactivity timers for each HARQ channel

● sends a flushing indication to "flush" one or more HARQ channels, which in turn results in data being flushed to higher layers for the re-ordering entity

● form a set of candidate HARQ channels for each missing packet, which are channels that may be used to send the missing packet. A delay timer may be used for candidate set formation.

● detect activity on the HARQ channel to determine if a lost packet was lost

Each of these mechanisms is described in detail below.

The following terms are used in the following description:

● packet handling-transmission of a particular packet on a particular HARQ channel and zero and multiple retransmissions.

● pending processing-packet processing where the packet is expected to have one or more additional retransmissions.

● complete the process-packet process in which the packet does not expect any additional retransmissions.

● lost packets-packets that were not recovered by the receiver and the TSN was earlier than the TSN of another packet that was already recovered (the lost packet may still be in the process of being retransmitted and may have been discarded by the transmitter).

● recovered packets-packets correctly decoded by the receiver.

● receives a packet-this term has two meanings depending on which entity is referred to. For the HARQ entity: a packet transmission received on a particular HARQ channel, which may or may not be decoded correctly. For the HARQ entity: the recovered packet is received from the HARQ entity but has not yet been delivered to higher layers.

● active HARQ channel-a type of HARQ channel in which packet processing is pending and the next transmission received on the channel applies to the retransmission of the current packet.

● Inactive HARQ channel-a HARQ channel in which packet processing is completed and the next transmission received on the channel is applied to a new packet.

● candidate HARQ channel-the HARQ channel that may be used to send the packet for which loss is detected.

Queue ID transmission on control channel

In W-CDMA release 5, a queue ID identifying a particular priority queue for a packet is sent as the header portion of the packet (see fig. 3). Thus, the priority queue to which the packet payload belongs can only be determined after the packet has been recovered. As a result, it is not possible to determine the priority queue associated with each lost packet because the packet was not recovered.

If a packet is lost and the priority queue to which it belongs cannot be determined, data transmission may be delayed for all re-ordering entities. This may deteriorate the performance.

In an aspect, a priority queue for each packet is sent on a control message along with the packet transmission. The queue ID field may be included within the control message, as shown by the dashed box in fig. 3. By sending a queue ID on the control channel, it is possible to identify for each packet a priority queue for which the associated control message is correctly detected by the receiver, regardless of whether the packet itself is correctly or incorrectly decoded. The information identifying the priority queue for each such packet may be used, along with other mechanisms described below, to further improve stall avoidance performance. For example, when used in conjunction with the mechanisms described below, it is possible to determine the priority queues that may be flushed to higher layers by identifying a priority queue for each such packet. Thus, each such packet only affects the re-ordering entity associated with the packet's priority queue and not other re-ordering entities. The stall avoidance performance can be improved.

Inactivity timer for HARQ channel

Each HARQ channel may be used to transmit one packet at any time. The packet is sent on the HARQ channel and may be retransmitted one or more times until (1) the transmitter receives an ACK for the packet or (2) the transmitter gives up transmission of the packet. In any case, the transmitter may thereafter send a new packet on the same HARQ channel and will indicate this point by triggering a new data indicator.

At the receiver, packet processing on a particular HARQ channel is considered pending until (1) the packet is correctly received by the receiver from the HARQ channel, or (2) the receiver detects a new packet transmission on the HARQ channel (based on a new data indicator within the control channel), because the transmitter does not transmit a new packet until it determines to stop the transmission of the previous packet.

At the receiver, the new data may "flush" the pending data within the receiver window, which may be discarded by the transmitter for one or other reasons. For example, if no more data is sent for priority queue a, but new data is still sent for priority queue B, the data for priority queue B may be sent on the same HARQ channel previously used for priority queue a. In this case, the data of priority queue B will effectively "overwrite" the data of priority queue A. The toggling of the new data indicator for each HARQ channel may cause the receiver to determine when a priority packet will be dropped by the transmitter.

However, if there is no more data to send, there may not be any activity on any HARQ channel. Without new activity, it is not possible for the UE to determine whether a given packet is dropped by the network or a packet retransmission is coming. For each HARQ channel that is waiting for a packet that has been dropped by the transmitter and no new packet is sent, the re-ordering entity associated with that HARQ channel must wait until the long timer maintained for the re-ordering queue expires before delivering the available data to higher layers. The HARQ process itself may wait permanently for the transmission of a new packet or retransmission of the current packet on the HARQ channel.

In another aspect, an "inactivity" timer may be maintained for each active HARQ channel to avoid the situation where the HARQ entity is permanently waiting for packet retransmissions that have been dropped by the transmitter. In an embodiment, the inactivity timer monitors inactivity on the HARQ channel based on control messages received on a control channel of the HARQ channel. In an implementation, the inactivity timer for a particular active HARQ channel is restarted each time a new control message is received on the control channel for that channel. The channel is considered inactive if the inactivity timer times out before another new control message is received on the HARQ channel.

The main advantage of using an inactivity timer for each HARQ channel is that it does not need to be as long as the timer for each reordering buffer. This is because the inactivity timer only needs to cover the maximum amount of time (or two control messages, for the case if the first is lost) expected to receive control messages for the active HARQ channel. The probability of loss due to the control channel is 10^-2Order of magnitude, then the probability of losing two control channel transmissions in succession is at 10^-4An order of magnitude. Thus, if the timer is set to the maximum time required to achieve two retransmissions, the probability of erroneously dropping a packet still to be transmitted will be approximately the same as the expected probability of a NAK to ACK error, which is desirable because both have the same effect. In contrast, a long timer needs to be long enough to handle the maximum number of retransmissions for a lost packet(and not just two control message transmissions).

A locally variable CurrNewData may be maintained for each HARQ channel and set to a new data indicator received within the last transmission on the channel. If the HARQ channel is deemed inactive, the next transmission on the channel is expected to be a new packet, in which case the new data indicator for that transmission would be different from the CurrNewData value. However, if the new data indicator for this new transmission is the same as the CurrNewData value, then it may be assumed that the same packet was sent (e.g., due to an ACK to NAK error), in which case the transmission may be dropped and an ACK may be sent back to the transmitter.

Flushing indications for HARQ channels

In another aspect, the flush may simply be sent on a control channel and used to direct the HARQ entity to flush one or more HARQ channels at the UE. The flushed HARQ channel indicates that pending processing on the channel is complete. The re-ordering entity waiting on this HARQ channel may then implement the appropriate behavior based on this information, as described below.

Various flushing indications may be sent to the UE in various manners. For example, a flush indication may be sent within a control message using a reserved value within a field used to indicate a coding set or used to indicate a transport module size. If the UE receives the flushing indication, it will not attempt to decode the packet. The reason is as follows. Each flushed HARQ channel may then be placed in an inactive state to indicate that additional retransmissions are not expected to be received on that channel.

One or more HARQ channels may be flushed based on a single flushing indication. In a first embodiment, the flushing indication flushes only the particular HARQ channel it transmits, which may be identified by the HID field within the control message. For this embodiment, if multiple HARQ channels are to be flushed, multiple flushing indications may be sent. In a second embodiment, the flushing indication flushes all HARQ channels. This embodiment reduces the number of transmissions of flushing indications. However, the flushing indication availability may also be reduced to the case where no data needs to be sent on any HARQ channel for any reordering queue. In a third embodiment, the flushing indication flushes all HARQ channels expecting data for a particular priority queue, which may be indicated in a queue ID field included in the same control message used to send the flushing indication. This embodiment may be used to flush all HARQ for a particular priority queue after all data transmissions within the traffic burst for that priority queue are completed.

The transmission of the flushing indication does not require much resources and can be used to early abort the inactivity timer maintained for a particular HARQ channel. In general, the system knows that there is an increased risk of that UE losing packets in its reordering buffer. For example, a UE with a high Frame Error Rate (FER) on the uplink or DPCH better to the cell than to the serving cell is more likely to have lost packets. For these UEs, the flushing indication may be sent after the traffic burst transmission for each priority queue is complete.

Delay timer for activity detection/missing packets on HARQ channel

If the first transmission of packets occurs in order based on their TSN, the lost packet can be identified by the TSN of the recovered packet. In particular, a packet may be considered lost if another packet with a later TSN is recovered first. (the later possible value of TSN is less than the previous TSN when the TSN value is rolled back). In this case, the lost packet with the earlier TSN may be assumed to be in transmission.

At the time that a packet is detected as missing, a set of candidate HARQ channels may be identified for which the missing packet may be transmitted. Thereafter, activity on the candidate HARQ channels may be monitored to determine whether any of these channels is one used to transmit the missing packet. The candidate HARQ channels may be successively removed from the set, as described below. If all candidate HARQ channels are removed and the set is empty, the missing packet is considered lost. Appropriate action is then taken by the re-ordering entity.

The HARQ channels included in the candidate set may be selected in a variety of ways, which may depend on the available information. In a first embodiment, the candidate set is formed upon detection of a missing packet and includes all HARQ channels that may be used for packet transmission, except for the HARQ channels for the recovered packet used to detect the missing packet.

In a second embodiment, upon detection of a missing packet, a candidate set of missing packets is defined to include all active HARQ channels. At this point, if at least one control message for the missing packet is received, the snapshot of the candidate HARQ channels may be accurate because the control message would place the HARQ channel corresponding to the missing packet in an active state, and the channel would then be included in the candidate set for the missing packet.

However, this snapshot may not be accurate if all control messages for the HARQ channel used to send the missing packet are lost by the receiver. For example, if the control message of the first transmission of packet P1 sent on HARQ channel H1 is lost, the channel will remain in an inactive state. Thereafter, if another packet P2 of the same priority queue is sent on another HARQ channel and decoded correctly (before packet P1 is retransmitted on HARQ channel H1), packet P1 may be detected as lost. However, the candidate set would not include HARQ channel H1 because it was inactive when the set snapshot was taken after packet P2 was recovered. The likelihood of these times occurring may be low and the effect would be that packet P1 is dropped by the re-ordering entity when it is eventually recovered.

In a third embodiment, which avoids the problems described above, a candidate set of lost packets is formed some time after the lost packets are detected. The delay is selected to be long enough to ensure that at least one control message is received for the missing packet before forming the candidate set for the missing packet. A "delay" timer (denoted herein as TM2) may be used to track the amount of time to wait before forming a snapshot of the candidate set.

Reliability based on control channel specification, i.e. 10^-2The delay timer may only need to be long enough to receive one additional control message transmission. If a delay timer is used, the receiver may actually need to miss two consecutive control message transmissions to form an inaccurate candidate set, and therefore lose packets. Based on a control channel 10^-2Two consecutive control channel losses can occur with a probability of 10^-4This is considered acceptable. Longer values of the delay timer will degrade performance rather than affect the underlying scheme.

In a fourth embodiment, a candidate set is formed for each lost packet starting at the time the lost packet is detected and would include all HARQ channels except the HARQ channel used for the recovered packet where the lost packet was detected (as in the first embodiment). However, a delay timer is also started. The candidate HARQ channels in the set may thereafter be removed if it is subsequently determined that the channel cannot be used to send the missing packet. Upon expiration of the delay timer, the candidate set is modified and all HARQ channels that are inactive at this time are removed from the set. The modified candidate set is a subset of the initial candidate set. For the fourth embodiment, the delay timer is used to acquire the HARQ channel for which all control messages were previously lost by the receiver, similar to the third embodiment described above. However, operation of the delay timer does not affect or prevent the removal of HARQ channels from the initially formed candidate set (e.g., HARQ channels for which packets with later TSNs have been recovered).

For embodiments using a delay timer, the timer may be implemented in various ways, as described in detail below.

If the queue ID is also sent on the control channel and at least one control message is received for the missing packet, the candidate set of missing packets would only need to include the HARQ channel for that priority queue. Since the number of candidate HARQ channels can be reduced, performance can be enhanced.

The delay timer and flushing indication mechanism may help the HARQ channels enter an inactive state when forming the candidate set. For example, the inactivity timer for a given HARQ channel may elapse while the delay timer is active, in which case the HARQ channel will not be included in the candidate set. These mechanisms thus limit the set of candidate HARQ channels, which may improve the performance of the stall avoidance mechanism.

For all embodiments used to form the candidate set for the missing packet, the candidate HARQ channels are thereafter removed from the set if it is then determined that they cannot be used to send the missing packet. In particular, if the pending processes on the channel are complete, the candidate HARQ channels are removed from the set.

In an embodiment, packet processing on the HARQ channel is considered complete if any of the following conditions occur: (1) a packet is recovered from the HARQ channel, (2) the HARQ channel is active and a new packet is detected to be sent on the channel, (3) an inactivity timer for the HARQ channel expires, or (4) a flush indication is received for the HARQ channel. Condition (1) results in recovery of the lost packet, or recovery of the packet later than the lost packet. Condition (2) may be detected by observing a new data indicator change and may occur, for example, if the transmitter decides to drop a previous packet and send a new packet on the HARQ channel. Conditions (1) and (2) also assume that the initial transmission is always achieved in order and that new packets are not sent on the same HARQ channel until the pending process is completed.

For a given lost packet, each HARQ channel in the associated candidate set may be removed if any of the four conditions described above occur. When the candidate set is empty, the missing packet is assumed to be lost (i.e., not recovered by the receiver). Appropriate actions may be performed. For example, all delayed recovered packets due to the lost packet can now be sent to higher layers.

As described above, queue ID transmission on the control channel may be used in conjunction with the other mechanisms described above to improve performance. In particular, the queue ID on the control channel may (1) reduce the number of candidate HARQ channels for lost packets, (2) allow for possible adaptation of the inactivity timer to the priority queue, and (3) allow for the use of flushing indications even when other re-ordering entities are in transmission.

In the following description, the candidate set is formed after a delay timer expires, which is started after the missing packet is detected.

Example Transmission

The various mechanisms described above to improve latency avoidance are described below for some example transmissions. For these examples, the NAK/ACK feedback on the HS-DPCCH is shown to be time aligned with the packet transmission associated therewith (for simplicity). The "sent" feedback values are those sent by the UE on the uplink, and the "received" feedback values are those detected by the node B. The first transmission of the packet is in order based on the TSN of the packet. Thus, the missing packets may be determined based on the TSN of the packets recovered by the UE.

In the following example, the delay timer (TM2) is set when a packet is detected to be lost. The set of candidate HARQ channels for the missing packet is determined after the delay timer expires.

Fig. 7A illustrates that the control channel is received and relies on a new data indicator within the control message to flush data from the reordering queue to higher layers.

At time T₁Here, the packet is received on HARQ channel H1 but is not decoded correctly. For this packet transmission, the receiver sends NAK feedback, which is received by the transmitter erroneously as an ACK. The state of HARQ channel H1 is set to active and the HARQ entity restarts the inactivity timer for that channel (TM 1).

At time T₂Here, a packet with TSNx is received on HARQ channel H2 and decoded correctly, and ACK feedback is sent for the packet transmission. The state of HARQ channel H2 is set to inactive. The recovered packet is then sent to the re-ordering entity for the priority queue of the packet. The reordering entity can be based on it just-connectedTSNx of received packets and the loss of packets with TSNx-1 is detected. A delay timer (TM2) is then started for the missing packet. The recovery packet with TSNx is delayed due to the lost packet.

At time T₃Where the packet was received on HARQ channel H3 but was not decoded correctly and NAK feedback was sent for the packet transmission. The state of HARQ channel H3 is set to active and the HARQ entity restarts the inactivity timer for that channel.

At time T₄The delay timer for the missing packet is expired and the set of candidate HARQ channels for the missing packet is determined. The candidate set of missing packets includes all HARQ channels that are active at the time the delay timer expires and that may be used to send the missing packet. The candidate set thus includes H1 and H3.

At time T₅A packet with TSNx +1 is received and decoded correctly on HARQ channel H3, and ACK feedback is sent for the packet transmission. The HARQ channel H3 state is set to inactive and the HARQ entity restarts the inactivity timer for that channel. The recovered packets with TSNx +1 are delayed due to lost packets. Since the packet processing of HARQ channel H3 is done for packets later than the missing packet, this channel may not be the channel used to send the missing packet. H3 is thus removed from the candidate set, which now includes only H1.

At time T₆New packets are received on HARQ channel H1, and the new data indicator flips from D0 to D1. The new packet is sent by the transmitter on this channel because it is erroneously at time T₁Where an ACK for the previous packet transmission is received. This change in the new data indicator means that pending packet processing on HARQ channel H1 is complete and the missing packet will not be sent on this channel. H1 is thus removed from the candidate set, which is now empty. The two delayed packets with TSNx and TSNx +1 are then sent to higher layers.

FIG. 7B illustrates a situation where a control channel is received anddata is flushed from the reordering queue to higher layers by means of an inactivity timer (TM 1). The packet transmission in FIG. 7B is similar to that shown in FIG. 7A, except that the packet transmission is not at time T₆Is received. At time T₇At this point, the inactivity timer for HARQ channel H1 expires. This indicates that the missing packet is not expected to be received on this channel. H1 is thus removed from the candidate set, and the set becomes empty. The two delayed packets with TSNx and TSNx +1 are then sent to higher layers.

Fig. 7C illustrates a scenario in which a control channel is received and a flushing indication sent on the control channel is relied upon to flush data from the reordering queue to higher layers. The packet transmission in FIG. 7C is similar to that shown in FIG. 7A except at time T₆A flush indication is received (rather than a packet transmission). For this example, the flushing indication covers all HARQ channels for the priority queue identified within the control message. H1 and H3 would be flushed because they are used for the identified priority queue. The candidate set of lost packets would then be empty. The delayed packet with TSNx and TSNx +1 is then sent to higher layers.

Fig. 7D illustrates a case where the control channel is not received and a DTX to NAK error is received by the transmitter. Fig. 7D also shows a case where the use of a delay timer enables the correct determination of the candidate set for a lost packet that would otherwise be lost.

At time T₁The packet is sent on HARQ channel H1, but the control channel is not received (i.e., lost). The receiver is unaware of the existence of the packet transmission and sends a DTX (i.e., no feedback), which is received by the transmitter erroneously as a NAK. Since the receiver is unaware of the packet transmission, the HARQ channel H1 state remains set to inactive and the inactivity timer for that channel is not restarted.

At time T₂A packet with TSNx is received on HARQ channel H2 and decoded correctly, and ACK feedback is sent for the packet transmission.The state of HARQ channel H2 is set to inactive and the inactivity timer for that channel is restarted (not shown in fig. 7D). The recovered packet is then sent to the re-ordering entity for the priority queue of the packet. The re-ordering entity can detect packet loss for TSNx-1 based on the TSNx of the packet it just received. A delay timer is then started for the missing packet.

At time T₃For by the transmitter at time T₁The detected NAK receives a packet retransmission on HARQ channel H1. The packet is not decoded correctly and a NAK feedback is sent for the packet transmission. The HARQ channel H1 state is set to active and the HARQ entity restarts the inactivity timer for that channel (not shown in fig. 7D).

At time T₄At this point, a new packet with TSNx +1 is received on HARQ channel H2, and the new data indicator changes to a new value (i.e., from D0 to D1). The packet is decoded correctly and ACK feedback is sent for the packet transmission. The state of HARQ channel H2 is set to inactive and the HARQ entity cancels the inactivity timer for that channel.

At time T₅At this point, the delay timer for the missing packet expires. At this point, there is one active HARQ channel H1. The candidate set then comprises only HARQ channel H1.

As shown in this example, the use of a delay timer enables the correct candidate set to be determined for the missing packet. Without a delay timer, the candidate set would be an empty set because packets with TSNx-1 are lost at time T₁A control message of (c). With the delay timer, the second transmission within the delay timer window enables HARQ channel H1 to be included in the candidate set.

At time T₆The missing packet with TSNx-1 is received on HARQ channel H1 and decoded correctly, and ACK feedback is sent for this packet transmission, the packet with TSNx-1 and TSNx is then sent to higher layers.

At time T₇Is prepared fromThe packet with TSNx +1 receives the packet retransmission on HARQ channel H2, which is at time T₄Has been NAK-ed. The packet is decoded correctly and sent by the re-ordering entity to higher layers. ACK feedback is also sent for the packet.

Specific implementation

For clarity, specific implementations of the processing performed by the HARQ entity and the re-ordering entities at the transmitter and receiver are described below. This implementation maintains a delay timer for lost packets to enable a more accurate candidate set to be formed for the lost packets. However, the delay timer is not strictly necessary as described above. If the delay timer is not used, then generating the action is equivalent to setting the delay timer to 0.

In the following implementation, it is assumed that the queue ID is sent on the control channel and that the priority queue of a given packet is unknown to the HARQ entity before the packet is decoded correctly. In this case, the HARQ entity notifies all re-ordering entities when packet processing is completed, since the lost packet may be for any priority queue. Also, when the delay timer times out, the re-ordering entity does not know which HARQ channel carries its data, and therefore includes all active HARQ channels within the candidate set for the missing packet.

Transmitter HARQ

Fig. 8 is a flow diagram of an embodiment of a process 800 implemented by a transmitter HARQ entity for transmitting a packet on a particular HARQ channel. For this embodiment, a locally variable NewData is maintained for each HARQ channel. This variable is toggled for the first transmission of a new packet when the payload to be sent changes. The variable is initialized to "1".

Initially, a determination is made as to whether there is a packet to be transmitted (step 812). If the answer is no, the process proceeds to step 822. Otherwise, it is determined whether this is the first transmission of the packet (step 814). If the answer is also yes, then the NewData variable is toggled (i.e., set to "0" for the first new packet), and the new data indicator within the control message for that packet is also toggled because it is set to the NewData value (step 816). Otherwise, if a packet is sent, step 816 is skipped and the NewData variable is not flipped. The queue ID in the packet's control message (if it is sent there) is set to the packet priority queue being sent (step 818). The packet and control message (which includes HID, queue ID, new data indicator, etc.) are then forwarded to the physical layer for transmission (step 820).

In step 822, it is determined whether an ACK (if any) for the current packet transmission is received from the UE on the HARQ channel. If the answer is yes, then the current packet sent on that channel is dropped (step 824) and the scheduler is informed that the HARQ channel is available to be sent to another packet (step 826). After step 826, or if an ACK is not received in step 822, the process returns to step 812.

Receiver HARQ

Fig. 9A and 9B show a flow diagram of an embodiment of a process 900 implemented by a receiver HARQ entity to receive a packet on a particular HARQ channel. Three local variables, CurrNewData, CurrQueueID, and CurrState, are maintained for each HARQ channel. The CurrNewData variable maintains the value of the new data indicator for the current transmission on the HARQ channel, and the CurrQueueID variable maintains the value of the queue ID for the current transmission. The CurrState variable indicates the current state of the HARQ channel and is inactive or active.

An inactivity timer is also maintained for each HARQ channel. In an embodiment, the inactivity timer is set long enough so that there is a high probability that two packet transmissions will occur on the HARQ channel before the inactivity timer expires. However, other values may also be used for the inactivity timer, and this is within the scope of the invention.

Each HARQ channel variable is initialized by setting CurrNewData to "1" and CurrState to inactive (step 910). A determination is made for the UE whether a control message is received on the control channel (step 912). If the answer is no, the process returns to step 912 and waits. Otherwise, a determination is made as to whether the control message includes a flush indication (step 914). If the answer is yes, one or more HARQ channels are flushed, depending on the particular flushing scheme implemented (step 916). The flush may be implemented as described below in FIG. 9D. As part of the flushing process, the re-ordering entity of each flushed HARQ channel is informed that the packet processing is completed on that channel. Since the control message with the flushing indication is sent only for flushing the HARQ channel and is sent with the control message without a packet burst, the process then returns to step 912 to wait for the next control message.

If the received control message is not sent to flush the HARQ channels, as determined in step 914, it is sent for packet transmission on the HS-DSCH. In this case, the particular HARQ channel used for the current packet transmission is determined from within the HID field within the control message (step 922). The inactivity timer for that HARQ channel is then restarted (step 924). As described above, the inactivity timer for the HARQ channel is restarted, whenever a control message is received for that channel, and if no activity is detected for the channel at the time the inactivity timer expires, the channel is considered inactive and appropriate actions may be performed. The inactivity timer is used to avoid a situation where the HARQ entity always waits for a packet transmission on a particular HARQ channel, which is not sent for any reason. The processing implemented when the inactivity timer times out is described below.

The current state of the HARQ channel is then determined based on the CurrState variable (step 926), and the process implemented for the HARQ channel depends on the current state.

If the HARQ channel is in an inactive state indicating completion of the priority packet processing, then the current transmission is expected to be the first transmission of a new packet. In this case, a determination is made as to whether or not CurrNewData is equal to the new data indicator within the control message for the packet transaction (step 930). If they are the same, indicating that the current transmission is not a new packet, the received packet is discarded (step 932), an ACK is sent back to the transmitter (step 934), and processing returns to step 912 to wait for the next control message. For example, if the receiver sends an ACK for a previous packet transmission, the previous packet may have been sent, but the transmitter incorrectly received a NAK, and the previous packet is retransmitted.

Otherwise, if the CurrNewData value is not equal to the new data indicator, indicating that the current transmission is for a new packet, the variables of the HARQ channel are updated by setting CurrState to active (step 942), CurrNewData to the new data indicator in the control message (step 944), and CurrQueueID to the queue ID value in the control message (if it is sent there) (step 946). The new packet received on the HS-DSCH is then stored in a soft buffer for the priority queue identified by the CurrQueueID value (step 948). The process then proceeds to step 958.

Returning to step 926, if the HARQ channel is in the active state, then the current transmission is expected to be a retransmission of the current packet because the process is still pending. In this case, a determination is made as to whether or not CurrNewData is equal to the new data indicator within the control message (step 950). If they are the same, indicating that the current transmission is indeed a retransmission, the received packet is combined with the previous transmission of the packet (step 952), and the process proceeds to step 958.

Otherwise, if the CurrNewData value is not equal to the new data indicator determined in step 950, then the current transmission is for a new packet. A new packet may have been sent, for example, if the transmitter decides to discard it before the pending process is completed or an ACK is received in error for a sent NAK. In this case, the previous packet in the soft buffer is cleared (step 954). If the priority queue of the previous packet is known (e.g., identified by a CurrQueueID value, which may be obtained from a queue ID included in the control message), the re-ordering entity of the priority queue is notified that processing of the previous packet is complete (step 956). If the priority queue of the previous packet is not known (e.g., not sent within a control message), all reordering may be signaled for the completed process on that HARQ channel. The variables for the HARQ channel are then changed by setting CurrNewData to the new data indicator in the control message (step 944) and setting CurrQueueID to the queue ID value in the control message (if it is sent there) (step 946). The new packet received on the HS-DSCH is then stored on a soft buffer (step 948), which has just been cleared of previous packets. The process then proceeds to step 958.

In step 958, the just-received packet may have been combined with the transmission previously received for the packet (if any), which is then decoded in an attempt to recover the packet. If the packet is not recovered, as determined in step 960, NAK feedback is sent to the transmitter (step 962) and the process returns to step 912. Otherwise, if the packet is successfully recovered, ACK feedback is sent (step 964), the current state of the HARQ channel is set to inactive to indicate that the current packet processing is complete and no additional transmissions are expected on the HARQ channel (step 966), and the recovered packet is sent to the re-ordering entity for the priority queue identified by the CurrQueueID value (step 968). The process then returns to step 912 to wait for the next control message.

Fig. 9C is a flow diagram of an embodiment of a process 970 implemented by a receiver HARQ entity to maintain the inactivity timer for a HARQ channel. The steps within the process may be implemented for each TTI.

Initially, a determination is made as to whether the inactivity timer has expired (step 972). Typically, only one inactivity timer, if any, expires within any given TTI, because each timer restarts at a different time whenever a control message is received for the HARQ channel associated with the timer. If no inactivity timer has expired, the process returns to step 972 and waits. Otherwise, the data in the soft buffer of the HARQ channel with the expired inactivity timer is discarded (step 974). The re-ordering entity processes the priority queue for the last packet transmission on the HARQ channel with the expired inactivity timer, and the entity is notified that packet processing is complete (step 976). The HARQ channel state with the expired inactivity timer is then set to inactive (step 978) and the process returns to step 972.

Fig. 9D is a flow diagram of an embodiment of a process implemented by a receiver HARQ entity upon receiving a flushing indication within a control message. This process may be implemented for step 916 in FIG. 9A. Initially, the HARQ channel to be flushed is identified (step 982). In one embodiment, these HARQ channels are identified for a particular priority queue, which is identified by a queue ID value included in the control message itself. In other embodiments, the flushing indication may flush a particular HARQ channel, all HARQ channels, or some determinable set of HARQ channels. In any case, the data in the soft buffer in each identified HARQ channel is discarded (step 984). The state of each identified HARQ channel is then set to inactive (step 986). The re-ordering entity handling each identified HARQ channel is then informed that packet processing on that channel is complete (step 988). The process then terminates.

Transmitter reordering entity

The transmitter may maintain a window for each priority queue. The window is the same size as the window used by the receiver and is used to flush old data that will not be sent, since the receiver will always discard the data, as described above. At the transmitter, if packets of a given priority queue are transmitted in order based on their TSNs, the leading edge of the window may be set to the nearest TSN of the transmitted packets. Thereafter, as each new packet is sent, the window leading edge is moved to the TSN of that packet. As the window moves forward for each new packet transmission, all packets with TSNs earlier than the trailing edge of the window are discarded.

At the transmitter end, a "transmitter reordering entity" is responsible for determining the packets sent on the HS-DSCH for each priority queue. The transmitter reordering entity is a protocol peer of the reordering entity at the transmitter end. The transmitter re-ordering entity maintains a window for the associated priority queue. The local variable TxLeadWinEdge is used to designate the leading edge of the window and is initially set to "0". The size of the window is represented by the local variable WindowSize.

Fig. 10 is an embodiment of a process 1000 implemented by a transmitter re-ordering entity for a particular priority queue. The steps shown in fig. 10 are performed whenever a new packet is scheduled to be sent for that priority queue.

For a new packet to be sent, the transmitter re-ordering entity first slides the window forward by incrementing the TxLeadWinEdge variable (step 1012). The TSN of the new packet is then set to the updated TxLeadWinEdge value (step 1014). Any pending packets with TSNs outside the window are then discarded (step 1016). In particular, packets with TSN ≦ (TxLeadWinEdge-Windows size) may fall outside the window and be discarded. The reason for dropping these packets is because they would fall outside the window at the receiver and would be dropped if received (step 1018).

If the channel condition of the receiver is poor, a flushing indication may be sent to the receiver upon completion of all data transmissions within a data burst of a particular priority queue. The flushing indication may be used to flush all HARQ channels for the priority queue, as described above. For example, if the serving cell is not the cell with the best uplink to the UE, a flushing indication may be sent and there is a greater likelihood that NAK/ACK feedback cannot be correctly received from the UE.

Receiver reordering entity

At the receiver, a receiver re-ordering entity is responsible for processing data for each priority queue. The receiver re-ordering entity receives the packets recovered by the HARQ entity for the associated priority queue, re-orders the packets, and delivers the packets in order to higher layers. These re-ordering entities maintain a window, the size of which is replicated at the transmitter. The local variable RxLeadWindEdge is used to indicate the most recent TSN received for the priority queue and is initially set to "0". The size of the window is represented by the local variable windowsize. Packets with TSNs in the range { (rxleadwindowsize +1) }.

In one embodiment, each receiver reordering entity can start a plurality of delay timers, one for each hole detected within the window. The delay timer is set long enough to have a higher probability of causing at least one control message transmission to be sent for the HARQ channel used to send the missing packet before the timer expires. Each delay timer is associated with a particular lost packet.

Fig. 6B is a diagram illustrating a window maintained by the receiver re-ordering entity. The packet is identified and referenced by its TSN. In one embodiment, each packet within the TSN number space is associated with one of four possible states from the receiver reordering entity perspective: transmitted, received, lost, and expected. A packet is considered (1) transmitted if it has been received from the HARQ entity and sent to higher layers, (2) received if it has been received from the HARQ entity but not yet sent to higher layers, (3) lost if it is part of a hole within a window, and (4) expected if it falls outside the window. A packet is considered lost if another packet with a later TSN is received before it. A hole occurs whenever there are one or more consecutive missing packets within the window. There are zero, one, or multiple apertures within the window at any given moment. Initially, the state of all packets within the window is set to transmitted and those outside the window are set to expected.

In an embodiment, for each packet in the lost state (i.e., the missing packet), the receiver re-ordering entity maintains a MaskVector to flag candidate HARQ channels for the missing packet. MaskVector is thus used to indicate whether each of the HARQ channels is used to send a missing packet. The MaskVector has a size equal to the number of HARQ channels for transmission of all priority queues and includes one element per possible HARQ channel.

The MaskVector for each missing packet is "initialized" when the missing packet is first detected. The initial candidate set would have the elements of each HARQ channel set to "1" except for the element of the HARQ channel used to detect the received packet for the missing packet, which is set to "0". A value of "1" indicates that the associated HARQ channel can be used to send the missing packet, and a value of "0" indicates that the channel cannot be used to send the missing packet. Thus, the initial candidate set includes all HARQ channels except one HARQ channel that is known to be unavailable for transmitting the missing packet. Thereafter, the element of each candidate HARQ channel may be set to "0" if it is determined that the channel cannot be used to transmit the missing packet. This may be the case if (1) a new packet is sent on the HARQ channel, as determined by a change in the new data indicator for the channel, (2) the inactivity timer for the channel expires, or (3) a flush indication is received for the channel.

The MaskVector for each missing packet is also "modified" when the delay timer applicable to the missing packet times out. The modified candidate set is cleared for all HARQ channels that are inactive when the delay timer expires (by setting the element in the MaskVector for these HARQ channels to "0"). The process of removing the remaining HARQ channels from the candidate set may proceed as described above.

Fig. 11A and 11B show a flow diagram of an embodiment of a process 1100 implemented by a receiver re-ordering entity for a particular priority queue. Initially, the receiver re-ordering entity receives a packet with TSNr from the HARQ entity on HARQ channel Hx (step 1112). A determination is then made as to whether the packet just received (i.e., the current packet) is a new packet (step 1114). If TSNr falls outside the window, the current packet is considered a new packet and if TSNr falls within the window, it is considered a retransmission of the pending packet. If the current packet is a new packet, the process proceeds to step 1140.

Otherwise, if TSNr falls within the window, the current packet is either (1) a copy of a previously received packet, or (2) a packet of a missing packet that would partially or completely fill a hole within the window. It is then determined whether the current packet is a packet that has been received or transmitted (step 1116). If the answer is yes, the current packet is a duplicate and is discarded (step 1118), and the process terminates.

Otherwise, if the answer is no in step 1116, the current packet is for a lost packet within the window. In this case, each previously missing maskvectors (i.e., those with TSN earlier than TSNr) is updated by setting the element corresponding to HARQ channel Hx to "0" (step 1120). This is because a later packet with TSNr is received on the channel and cannot be the one used to send the earlier lost packet. Each time MaskVector is updated, a check is also made to determine if all elements of MaskVector are "0", indicating that the candidate set is empty and that the missing packet is lost. If the MaskVector includes all "0 s", all received packets delayed by the missing packet are sent to higher layers and all packets earlier than the packet are set to have been transmitted.

The state of the current packet is then set to received (step 1122). All received packets (if any) that are currently delayed by one hole are passed to higher layers (1124). In particular, consecutively received packets starting from the leftmost of the window and continuing until the first hole (or missing packet) is detected are identified and sent to higher layers. The status of these transmitted packets is also set to have been transmitted.

In one embodiment, a delay timer is maintained for the last packet in each "original" hole, which is a hole that occurs whenever a new packet is received by the re-ordering entity and there are one or more expected packets earlier than (or to the left of) the new packet. The state of the desired packet within the hole is changed to lost. This is described in detail below. A packet may then be received by the re-ordering entity for the missing packet in the hole. If the hole is as wide as one packet, the received packet will completely cover the hole and the delay timer is cancelled. Otherwise, if the hole covers multiple packets and the current packet is the last missing packet in the hole, the delay timer is moved to the (new) last missing packet in the partially covered hole. And if the hole covers multiple packets and the current packet is not the last missing packet in the hole, the delay timer is not affected. In this implementation, only one delay timer needs to be maintained for all missing packets in the original hole (since they were detected at the same time), even if the hole is then split into multiple holes by packets received by a later re-ordering entity.

Accordingly, a determination is made as to whether the delay timer is started for the current packet (step 1126). If the answer is no, the process terminates. Otherwise, it is determined whether there is a hole to the left of the current packet (step 1128). If the answer is yes, the delay timer for the current packet is cancelled, since this indicates that the current packet completely fills the hole, in which case the delay timer need not be maintained (step 1130). Otherwise, if the current packet does not fill a hole, no action is taken with respect to the delay timer. In both cases, the process terminates.

Returning to step 1114, if the current packet is a new packet, the state of the packet is set to received (step 1140). The MaskVector for each missing packet within the window is updated and checked and as a result the packet may be flushed to higher layers by the re-ordering entity as described above for step 1120 (step 1142). The window is then moved forward to TSNr by setting the leading edge of the window, RxLeadWinEdge (step 1144). The status of all packets received outside the window is passed to higher layers (step 1146), the status of all packets outside the window is set to expected (step 1148), and all delay timers that have been set for packets outside the window are stopped (step 1150). Received packets (if any) that are not currently delayed for a hole are passed to higher layers (step 1152). This may be performed as described above for step 1124.

It is then determined whether a hole exists on the left side of the current packet (step 1154). This may be determined by checking whether the packet status with TSNr-1 is expected. If the answer is no, the process terminates. Otherwise, if there is a hole, a delay timer (i.e., with TSNr-1) is started for the last packet in the hole (step 1156). Each expected packet within the hole is then set to lost and the MaskVector for each such packet is initialized by setting the element for the corresponding HARQ channel Hx to "0" and all other elements to "1" (step 1158). The process then terminates.

For the above embodiment, one delay timer is used for all missing packets in each original hole (i.e., a hole detected with a new packet that moves the window forward). This timer is associated with the last lost packet in the hole, but is applicable to (or referenced by) all lost packets in the hole. In one implementation, a timer over flag is used for each missing packet to indicate whether its available delay timer (i.e., the first delay timer to the right of the packet) has expired. When the original hole is detected, the timer over flag for each missing packet in the hole may be set to "0" to indicate that the applicable delay timer has not expired (step 1158). And when the delay timer times out, the timer over flag for all missing packets covered by the timer is set to "1" and the MaskVector for all these missing packets is also modified as described above to be inactive at this time or used for HARQ channels with other priority queues removed. This implementation is described in detail below.

The MaskVector for a lost packet is updated/modified based on various events, such as (1) whenever the HARQ entity indicates that packet processing on a given HARQ channel is complete, and (2) when each delay timer maintained for the associated lost packet expires.

Fig. 11C shows a flow diagram of an embodiment of a process 1160 implemented by the receiver re-ordering entity whenever an indication is received that the delay timer has expired. Initially, a determination is made as to whether the delay timer has expired (step 1162). If the answer is no, the process terminates. Otherwise, if the delay timer times out, the TSN of the missing packet associated with the expired delay timer is determined and denoted as TSNe (step 1164). Multiple missing packets may rely on the delay timer because only one is maintained for all missing packets in each original hole, as described above. The timer over flag for each missing packet covered by the expired delay timer is then set to "1" to indicate that the timer for the packet has expired (step 1166). The missing packets covered by the timeout delay timer include those with TSNs earlier than TSNe. The MaskVector for each missing packet covered by the delay timer is then "modified" (i.e., the candidate set for the missing packet is modified) (step 1168). To modify the MaskVector for lost packets, each HARQ channel is considered, and if the channel is inactive, or the channel is used for another priority queue, the corresponding element within the MaskVector is set to "0". The HARQ channels corresponding to the elements within the MaskVector that are still set to "1" are the candidate HARQ channels remaining at this time. If the MaskVector is modified, it is checked to determine if the packet should be flushed to higher layers. The process then terminates.

Figure 11D shows a flow diagram of an embodiment of a process 1170 implemented by a receiver re-ordering entity for a process completed on a particular HARQ channel. Initially, a determination is made as to whether an indication has been received from the receiver HARQ entity indicating that packet processing has been completed on the HARQ channel (step 1172). If the answer is yes, then for each missing packet for which the applicable delay timer has expired (i.e., the timer over flag is reset to "0"), the element in the MaskVector corresponding to the HARQ channel is set to "0" (step 1174). Likewise, if the MaskVector is updated, a check is made to determine if the packet should be flushed to a higher layer. The processes to be implemented for the processes done on the HARQ channel are described in the pseudo-code below. The process then terminates.

In the above embodiment, each receiver reordering entity can start a plurality of delay timers, one for each original hole detected within a window. In other embodiments, each re-ordering entity may have a delay timer running at any given time. Whenever an original hole is detected, if it is not currently running, the delay timer for the re-ordering entity can be started, and at that point the delay timer is not started for the missing packet in the second original hole. If the delay timer expires thereafter, the missing packets covered by the delay timer (i.e., missing packets having a TSN earlier than the TSNe of the missing packet associated with the delay timer) are updated as shown in steps 1162 through 1166 in fig. 11C. Additionally (after step 1166), it is determined whether there are any missing packets with TSNs later than TSNe. If the answer is yes, the delay timer is restarted and associated with the last lost packet.

This alternative embodiment reduces the number of delay timers that each re-ordering entity needs to maintain to one. However, this embodiment may double the delay timer value for the lost packet in the worst case. For example, the delay timer may start for a first missing packet and a second missing packet may be detected in the next transmission interval. The delay timer for the second missing packet cannot be started until the delay timer for the first missing packet expires. The second missing packet would then need to wait for the expiration of the delay timer for the first missing packet plus the second missing packet. This other embodiment is described in detail in the pseudo code shown below.

Fig. 12 shows a flow diagram of an overall process 1200 implemented by a re-ordering entity for receiving packets from a HARQ entity and transmitting packets to higher layers. Initially, a correctly decoded packet is received from the HARQ entity (step 1212). Missing packets between the received packets are then detected (step 1214). This may be obtained based on the TSN in the received packet, as described above. If a missing packet is detected, the delivery of received packets later than the detected missing packet to higher layers is delayed (step 1216). It is then determined for each missing packet whether (1) it is subsequently received from the HARQ entity or (2) it is missing by successively removing HARQ channels that may be used to send the missing packet, as described above (step 1218). The received packets that have been delayed for each missing packet are then delivered to higher layers after the missing packet is determined to be lost or received from the HARQ entity (step 1220).

Pseudo code for the process-specific implementation described above with respect to FIGS. 8 through 11C is shown below.

Transmitter HARQ entity

When scheduling (re) for a particular priority queueDuring transmission, the transmitter：

1-if this is the first transmission of the packet;

2-flip new data indicator;

1-set the queue ID field to the priority queue of the packet being sent;

1-end of the process.

When ACK is received

1-drop the current packet being sent;

1-indicating to the scheduler that the HARQ entity is available;

1-end of the process.

Receiver HARQ entity

Upon receiving a control channel transmission sent for a receiver：

1-if the control message includes a flush indication:

2-processing the flush indication for the priority queue indicated in the queue ID field (see below);

and 2-finishing the process.

1-start/restart inactivity timer (TM1) for HARQ channel identified by control message;

1-if the identified HARQ channel is in an inactive state;

2-if CurrNewData has the same value as the new data indicator;

3-drop the received packet;

3-sending ACK on the uplink;

and 3-finishing the process.

2-otherwise:

3-setting the HARQ channel to active state;

3-set CurrNewData to the new data indicator value;

3-setting CurrQueueID to the value of the queue ID field;

3-storing the received packet transmission in a soft buffer;

1-else (if HARQ channel is active)'

2-if CurrNewData is new data indicator;

3-soft combining the received packet with the previous transmission accumulated in the soft buffer;

2-otherwise:

3-discard the data currently in the soft buffer;

3-indicate packet processing completion to the re-ordering entity corresponding to Curr queue ID (see below);

3-set CurrNewData to the new data indicator value;

3-setting the Curr queue ID as a queue ID field value;

3-storing the received packet transmission in a soft buffer;

1-attempt to decode the packet in the soft buffer;

1-if the decoding is successful:

2-sending ACK on the uplink;

2-setting the HARQ channel to inactive state;

2-transmit the recovered packet to a re-ordering entity corresponding to CurrQueueID (see below);

1-else:

2-sending NAK on uplink;

1-end of the process.

Upon expiration of an inactivity timer (TM1) for a given HARQ channel：

1-discard the data currently in the soft buffer;

1-indicate packet processing completion to the re-ordering entity corresponding to CurrQueueID (see below);

1-setting HARQ channel to inactive state;

1-end of the process.

Upon receiving a flush indication for a given priority queue：

1-for each HARQ channel, where its CurrQueueID is equal to the queue ID value within the control message of the flushing indication:

2-do not attempt to receive data;

2-discard the data in the soft buffer;

2-setting the HARQ channel to inactive state;

2-indicate packet processing completion to the re-ordering entity corresponding to CurrQueueID;

1-end of the process.

Transmitter reordering entity

Transmitter reordering entities when scheduling associated priority queues for transmissions：

1-increment TxLeadWinEdge;

1-set the TSN of the new packet to TxLeadWinEdge;

1-discard any pending packets with TSN ≦ TxLeadWinEdge-Windows size;

1-submitting the new packet to the scheduler specified HARQ entity;

1-end of the process.

Receiver reordering entity

For this embodiment, one delay timer is maintained for each raw well.

When a new packet with TSNr is transmitted by the HARQ entity, the receiver re-ordering entity:

1-if the received packet is within the receive window

(RxLeadWinEdge-WindowSize≤TSNr＜RxLeadWinEdge)；

2-for each TSNi in the lost state;

3-if TSNi < TSNr:

4-set the element in MaskVector corresponding to this HARQ channel to "0";

4-if all elements within the MaskVector are equal to 0:

5-implementation of the flush procedure for TSNi (see below)

2-if the TSNr status is received or transmitted;

3-drop the received packet;

2-else (state of TSNr is lost);

3-if all packet states within the receive window with TSN < TSNr are transmitted:

4-if the delay timer (TM2) associated with TSNr starts, the read timer is stopped;

4-deliver the packet to higher layers;

4-set the state of TSNr to transmitted;

4-for each TSNj within the receive window, start at TSNr + 1;

5-if the state of TSNj is expected or lost;

6-stop iteration on TSNj.

5-else, if the TSNj status is received;

6-transfer data for TSNj to higher layers;

6-set the state of TSNj to transmitted;

6-if the delay timer is associated with TSNj, stop the timer;

6-to the next TSNj;

3-otherwise:

4-set the state of TSNr as received;

1-else (received packet outside of receive window);

2-for each TSNi in the lost state;

3-set the element in the MaskVector corresponding to this HARQ channel to "0";

3-if all elements within the MaskVector are equal to "0";

4-perform a flush procedure on TSNi;

2-set RxLeadWinEdge to TSNr;

2-sending all data associated with TSNs outside the receiver window with received status to higher layers;

2-stop the delay timer TM2 associated with the TSN outside the receiver window;

2-set all TSN states outside the receiver window to expected;

2-if all packet states within the receive window with TSN < TSNr are received or transmitted:

3-sending the packet to higher layers;

3-set the state of TSNr to transmitted;

2-otherwise:

3-set the state of TSNr as received;

3-start the delay timer TM2 associated with TSNr-1;

3-for each TSNj within the receive window with the expected state at TSNj < TSNr:

4-set TSNj state to lost;

4-reset timer _ over flag to "0";

4-within the MaskVector associated with TSNj;

5-set the element corresponding to the HARQ channel to "0";

5-set the elements corresponding to the other HARQ channels to "1";

1-finishing the process;

when the HARQ entity indicates that the packet processing for a particular HARQ channel is complete：

1-for each TSNi of the lost state, its timer _ over flag is set to 1;

2-set MaskVector internal element corresponding to the HARQ channel to "0";

2-if all elements within the MaskVector equal to "0";

3-implementation of the flushing procedure of TSNi

1-end of the procedure

When the delay timer (TM2) times out：

1-consider each TSN in the lost state, the TSN being less than or equal to the TSN associated with the timer;

2-set the timer _ over flag to "1";

2-consider the MaskVector variable for this TSN;

2-for each HARQ entity:

3-if the HARQ entity is not in active state or CurrQueueID is different from the priority queue of the re-ordering entity;

4-set MaskVector element corresponding to HARQ channel to "0";

1-end of the procedure

Flush procedure-when all elements within MaskVector of TSNi are equal to "0；

1-for each TSNj within the receive window and TSNj earlier than or equal to TSNi;

2-if the state of TSNj is received, transmitting the associated data to higher layers;

2-set the state of TSNj to sent;

1-for each TSNj within the receive window, starting at TSNi + 1;

2-if the state of TSNj is expected or lost:

3-stop the iteration of TSNj.

2-else, if the state of TSNj is received:

3-passing the associated data to higher layers;

3-set the state of TSNj to transmitted;

3-to the next TSNj;

1-returning;

for one embodiment, one delay timer is maintained for each re-ordering entity.

Receiver re-ordering entity when new packet with TSNr is transmitted by HARQ entity：

1-if the received packet is within the receive window

(RxLeadWinEdge-WindowSize＜TSNr＜RxLeadWinEdge)；

2-for each TSNi within the lost state;

3-if TSNi < TSNr:

4-set MaskVector internal element corresponding to the HARQ channel to "0";

4-if all elements within the MaskVector are equal to 0:

5-implementation of the flush procedure for TSNi (see below)

2-if the status of TSNr is received or transmitted:

3-drop the received packet;

2-else (state of TNSr is lost):

3-if all packet states with TSN < TSNr within the receive window are transmitted:

4-if the delay timer (TM2) associated with TSNr has started, stop the timer;

4-delivery of packets to higher layers;

4-set the state of TSNr to transmitted;

4-for TSNj within each receive window, start at TSNr + 1;

5-if the state of TSNj is expected or lost;

6-stop iteration on TSNj;

5-else, if the state of TSNj is received;

6-transfer data for TSNj to higher layers;

6-set the state of TSNj to transmitted;

6-if the delay timer is associated with TSNj, stop the timer;

6-to the next TSNj;

3-otherwise:

4-set the state of TSNr as received;

1-else (received packet outside of receive window):

2-for each TSNi in the lost state:

3-set the element in the MaskVector corresponding to this HARQ channel to "0";

3-if all elements within the MaskVector equal to "0";

4-implementation of flush procedure for TSNi

2-setting TxLeadWinEdge as TSNr;

2-transmitting all data associated with the TSN received in the out-of-window state of the receiver to higher layers;

2-stop all delay timers TM2 associated with TSNs outside the receiver window;

2-set all TSN states outside the receiver window to expected;

3-deliver the packet to higher layers;

3-set the state of TSNr to transmitted;

2-else

3-set the state of TSNr as received;

3-if the delay timer TM2 of the re-ordering entity is not running; then:

4-start the delay timer TM2 associated with TSNr-1;

3-for each TSNj < TSNr having a state within the desired receive window TSNj:

4-set TSNj state to lost;

4-reset timer _ over flag to "0";

4-within the MaskVector associated with TSNj:

5-set the element corresponding to the HARQ channel to "0";

5-set the elements corresponding to the other HARQ channels to "1";

1-end of the procedure

When the HARQ entity indicates packet processing completion for a particular HARQ channel：

1-for each TSNi in the lost state, its timer _ over flag is set to 1;

2-set MaskVector internal element corresponding to the HARQ channel to "0";

2-if all elements within the MaskVector equal to "0";

3-implementation of the flush procedure on TSNi

1-end of the procedure

When the delay timer (TM2) times out：

2-consider each TSN in the lost state, the TSN being less than or equal to the TSN associated with the timer;

2-set the timer _ over flag to "1";

2-consider the MaskVector variable for this TSN;

2-for each HARQ entity:

4-set MaskVector element corresponding to the HARQ channel to "0";

1-if there are any TSNs in the lost state:

2-start the delay timer and associate it with the TSN of the last packet in the lost state;

1-end of the procedure

Flush clearingProcess-when all elements within the MaskVector of TSNi are equal to "0；

2-for each TSNj within the receive window and TSNj earlier than or equal to TSNi;

2-set the state of TSNj to sent;

1-for each TSNj within the receive window, starting at TSNi + 1;

2-if the state of TSNj is expected or lost:

3-stop iteration on TSNj.

2-else, if the state of TSNj is received:

3-passing the associated data to higher layers;

3-set the state of TSNj to transmitted;

3-to the next TSNj;

1-returning;

pseudocode for a particular implementation is shown above to provide a clearer understanding of the processes implemented by the various entities at the transmitter and receiver. Other implementations are also contemplated, as those skilled in the art may describe based on the above principles, and these various other implementations are also within the scope of the invention.

The techniques described herein may be used to provide improved stall avoidance performance for systems with basic retransmission mechanisms (e.g., HARQ) and higher layers requiring data to be in order. The techniques may be used for various communication systems such as, for example, W-CDMA systems, CDMA2000 systems, and so on. These techniques may also be used for other types of communication systems (e.g., TDMA and FDMA systems).

Fig. 13 is a block diagram of an embodiment of a node B104 and a UE 106. On the downlink, HS-DSCH and HS-SCCH data for a particular UE designated to receive HSDPA transmissions is received and processed (e.g., formatted, encoded, and so on) by a Transmit (TX) data processor 312. The processing of HS-DSCH and HS-SCCH may be implemented as described in applicable W-CDMA release 5 standard documents, including ts.25-321 V5.0.0, ts.25-308 V5.2.0, and 25-212 V5.0.0, which are all incorporated herein by reference. These and other documents of W-CDMA release 5 are commonly available.

The processed data is then provided to a Modulator (MOD)1314 and further processed (e.g., channelized, spread, and so on) to provide modulated data. A transmitter (TMTR) unit 1316 then converts the modulated data into one or more analog signals, which are conditioned (e.g., amplified, filtered, and frequency upconverted) to provide a downlink signal. The downlink signal is routed through a duplexer (D)1322 and transmitted via an antenna 1324 to the designated UE.

At the UE, the downlink signal is received by an antenna 1352, routed through a duplexer 1354, and provided to a receiver (RCVR) unit 1356. Receiver unit 1356 conditions (e.g., filters, amplifies, and frequency downconverts) the received signal and further digitizes the conditioned signal to provide samples. A demodulator 1358 then receives and processes (e.g., despreads, channelizes, and data demodulates) the samples to provide symbols. Demodulator 1358 may implement a rake receiver that may process multiple instances (i.e., multipath components) of the received signal to provide combined symbols. A Receive (RX) data processor 1360 then decodes the symbols, checks the received packet, and provides decoded data. The processing by demodulator 1358 and RX data processor 1360 is complementary to the processing by modulator 1314 and TX data processor 1312, respectively.

In an embodiment, RX data processor 1360 performs processing for the physical and partial MAC layers (e.g., HARQ entities), and controller 1370 performs some processing for the MAC layer (e.g., re-ordering entities) and further performs portions of HARQ. For this embodiment, RX data processor 1360 may provide (1) decoded data for each packet that is decoded correctly, (2) the status of each packet transmission (e.g., ACK or NAK), (3) inactivity and delay timers that indicate a timeout, and so on. Controller 1370 then detects the lost packet and provides it to higher layers when the packet is received and available. Controller 1370 also provides the appropriate ACK/NAK feedback for HARQ operations to TX data processor 1382.

On the uplink, uplink data and ACK/NAK feedback information are processed (e.g., formatted, encoded, and so on) by a TX data processor 1382, further processed (e.g., channelized, spread, and so on) by a modulator 1384, and conditioned (e.g., converted to analog signals, amplified, filtered, and frequency upconverted) by a transmitter unit 1386 to provide an uplink signal. The uplink signal is then routed through duplexer 1354 and transmitted via antenna 1352 to the base station.

At node B, the uplink signal is received by antenna 1324, routed through duplexer 1322, and provided to a receiver unit 1342. Receiver unit 1342 conditions (e.g., downconverts, filters, and amplifies) the received signal and further digitizes the conditioned signal to provide a stream of samples. A demodulator 1344 then processes (e.g., despreads, channelizes, and so on) the samples to provide symbols, and an RX data processor 1346 further processes the symbols to provide decoded data for the UE. The data processing for the downlink and uplink is described by W-CDMA standard documents.

A controller 1330 receives ACK/NAK feedback from RX data processor 1346 and directs packet retransmission for HARQ, as necessary. Controllers 1330 and 1370 may also control corresponding processing at the node B and the UE. Each controller may also be designed to implement all or portions of the HARQ transmission/retransmission techniques described herein. Program codes required by controllers 1330 and 1370 may also be stored in memory units 1332 and 1372, respectively.

The techniques described herein for improving stall avoidance performance may be implemented in various ways. For example, these techniques may be implemented in hardware, software, or a combination thereof. For a hardware implementation, the elements used for the present implementation techniques (e.g., the elements that may implement the processes of fig. 8-11A) may be implemented with the following elements: one or more Application Specific Integrated Circuits (ASICs), Digital Signal Processors (DSPs), Digital Signal Processing Devices (DSPDs), Programmable Logic Devices (PLDs), Field Programmable Gate Arrays (FPGAs), processors, controllers, micro-controllers, other electronic units designed to perform the functions described herein, or a combination thereof.

For a software implementation, the techniques may be implemented with modules (e.g., procedures, functions, and so on) that perform the functions described herein. The software codes may be stored in memory units (e.g., memory units 1332 and 1372 in fig. 13) and executed by processors (e.g., controllers 1330 and 1370). The memory unit may be implemented within the processor or external to the processor, in which case it can be communicatively coupled to the processor via various means as is known in the art.

The previous description of the preferred embodiments is provided to enable any person skilled in the art to make or use the present invention. Various modifications to these embodiments will be readily apparent to those skilled in the art, and the generic principles defined herein may be applied to other embodiments without the use of the inventive faculty. Thus, the present invention is not intended to be limited to the embodiments shown herein but is to be accorded the widest scope consistent with the principles and novel features disclosed herein.

Claims

1. A method for transmitting packet data in a CDMA communication system, comprising:

determining a priority for each packet to be transmitted;

forming a control message for each packet and including therein the priority of the packet;

transmitting the packet on a data channel; and

the control message is sent on a control channel accompanying the data channel.

2. The method of claim 1, wherein the packets of each priority are transmitted in sequence.