Background of the invention Wireless access is expected to be one of the key access technologies for providing seamlessly end-to-end data services to the people. The wireless network has its own unique set of complex characteristics as it has to deal with bandwidth variability and frequent packet errors due to multi-path fading and shadowing, etc. Thus, providing suitable wireless service is a great challenge.

As 3G systems will offer services with various QoS requirements, the system will need capabilities to manage the access demands of different users and different service classes. This can be achieved by using priority schemes, which can be used to prioritize the requests from different services.

QoS control belongs to resource management, which relates to channel allocation, power control, handoff, etc. Packet scheduling is a part of QoS control mechanism. According to the characteristics of wireless network, it is difficult to provide both delay-guarantees and fairness simultaneously.

Recently several proposals of packet data transfer in wireless environment were given, such as Qualcomm's HDR (High Data Rate) and Motorola's 1XTREME, etc.

In HDR, there is a'Proportional Fairness Scheduling'rule to govern the priority of data.

The algorithm uses a different notion of fairness known as'proportional fairness'.

'Proportional Fairness Scheduler maximizes the product of the throughputs delivered to all the users. lxHDR is aimed at packet data services, for which all users do not generally demand equal service. Some applications require higher data rates, while others have much lower data rate requirements. The user's channel condition (C/I) is also a primary factor. in determining the data rate that a given subscriber can attain. The lxHDR system takes advantage of the wireless channel variability, which results in variations of the requested rate over a period of time. The scheduler will serve users that are near their peaks in terms of the requested rates.

Occasionally, the users may not be served for periods of time when their requested rates are

lower. Allowing the scheduler to not serve disadvantaged users for periods of time will maximize the overall throughput.'(lxHDR Airlink Overview, QUALCOMM, Inc. April 28, 2000, Revision 3.1) In 1XTREME, two simple scheduling algorithms can be used: C/I scheduler or Round Robin scheduler. The former provides maximum system capacity at the expense, of fairness, because all frames can be devoted to a single user with best channel condition; the latter provides fair, token-ring alike way at the expense of system capacity.

With respect to the pros and cons of these methods, here we introduce a scalable scheme of packet priority control termed as HDFQ (Hybrid Dynamic Fairness Queuing). Our approach is designed to synthesis the parameters, while simultaneously giving fair opportunity to each user. The principle of the scheduling is to get maximum system resource utilization with regard to QoS requirement, service fairness and implementation complexity. The QoS objectives are satisfied without requiring complex algorithm and accurate predictions of the users'future behaviors. Algorithm concerning QoS should be adopted with regard to best efficiency and maximum traffic throughput principle.

Summary of the invention The object of present invention is to provide a method of priority control in wireless packet data communications that performed in data link layer to solve the problems remains in prior art, including error control scheme, weight calculation of packet and multi-queue traffic adjustment.

In the present invention, we consider the synthetic effect of the parameters. E. g. , take care of users'QoS and system resource utilization. Thus, we can take both the system capacity and fairness into account and assure the packet data transmission optimization of in high-speed mobility environment, and the weight calculation method is presented, too.

A method of priority control in wireless packet data communications, wherein the method includes the following steps: Prioritize the re-transmitted data in the lower layer of the protocol stacks by increasing the weight; Calculate the packet weight according to the QoS requirement, channel quality, estimated service time and re-transmission time; Place the packets into multi-queues according to the weight decided by classifier; Sorting the queue by the dynamically calculated weight; Sorting the queue according to the priority of queue, and the sorting policy (such as

sorting frequency) is varied; Fair queue adjustment to balance the queues of scheduler by computing the flow factor; Fair queue classification by adjusting the classifier criteria. wherein said lower layer of the protocol prioritizes the re-transmitted data in MAC by increasing the weight. wherein said lower layer of the protocol stacks prioritizes the re-transmitted data in RLC by increasing the weight. wherein said calculate the packet weight according to the QoS requirement, channel quality, estimated service time include: Said weight can be decided by bounded delay, BER, number of re-transmission times, throughput. I. e.

W = f (Delay, BER, Nrt, CQ) wherein said weight can be decided by the following formula: W= m * GoSc* Nrt + n * CQ + Ts + g (Tq) wherein said Place the packets into multi-queues according to the weight decided by classifier further including: Classifier that responsible for weight calculation and put weighted data to the right queue for transmission; Packet scheduler that manages the queues and sends the packet to lower layer. wherein said weight of packet is calculated by synthesis the factors such as QoS requirement, channel quality, estimated service time, etc.

In the present invention, further includes a method of multi-group buffer to implement priority control via ARQ control in RLC layer. wherein said a floating index of data buffer can be a pointer buffer point to the data buffer, where the data weight is sorted. wherein said fair queue adjustment to balance the queues of scheduler by computing the flow factor further including: By computing the arriving rate, service rate and the load percentage, the status of a

queue can be decided; The queue status can be mapped into a data queue load constraint: <BR> <BR> <BR> <BR> <BR> # = (#iQi - µiPi)#T<BR> <BR> <BR> <BR> <BR> (1-0)C d T denotes the average packet arriving interval; When the value of P is within a certain range, we deem the queue is balanced; When w is over certain limit, that means the queue tends to overflow; Then the packet can be transferred to other queue; The criteria to judge whether the load is balanced or not is: 0 is out of range; P is out of range; By synthesize these parameters, the queue can be judged if balanced or not. wherein said Fair queue measurement by adjusting the classifier criteria further including: In step 602, the method ascertains whether the queues in scheduler are empty or not, If yes, the method sends primitives to upper layer for data; If the queues are not empty and it is time to check the queue balance, this method checks the queue balance by computing the synthesis effect of weight and factor o in step 605; Frame 605 contains the queue balance adjustment method; If the queues are not balanced, first the method changes the arrival rate and service rate by altering the classifier's threshold and Round Robin proportion in step 608 ; Then it comes to step 609 to check the average weight of the queues, so as to see whether it is appropriate to shift the packet from one queue to another in step 610; If the weight is out of current band, then the method check if the neighboring queue with the right weight band is able to accommodate the packets by computing the factor S and P, In order to reduce the complexity, the packet may be inserted to the tail of the target queue instead of insertion; For the bottom level queue, if the weight is varying the packets may be'shift to upper queue or down to the dustbin, that is, discarded; The real time service will be discarded when the bounded delay reached; In step 612, the method check if it is time to modify the scheduler balance; If not, it will wait for a certain time and return to step 612;

When it is time to check the balance, the method calculate the factors a and P of all the queues to determine if it is right alter the polling time; When the queue difference is out of range, i. e. scheduler balance is beyond limit, the polling time should be reduced ; The maximum queue polling time must assure the minimum service QoS demand.

In the present invention, further includes: The method coordinates the transmissions of all users so that the common channel is efficiently utilized and the QoS requirement of each user is satisfied.

In the present invention, further includes: This method also applies for shared channels such as DSCH.

In the present invention, further includes: This method also applies to both TDD and FDD communications.

The aim of present invention is to solve the problems remains in prior art, including error control scheme, weight calculation of packet and multi-queue adjustment.

The present invention is designed to synthesis the parameters, while simultaneously giving fair opportunity to every user. The principle of scheduler is to get maximum system resource utilization with regard to required QoS, fair service and implementation complexity.

The QoS objectives are satisfied without requiring complex algorithm and accurate predictions of the users'future behaviors. Algorithm concerning QoS should be adopted with best efficiency and maximum traffic throughput principle.

Brief description of the drawings FIG. 1 shows a scheduling mechanism in data link layer according to the prior art.

FIG. 2 is a schematic diagram illustrating the grouped data buffer structure in RLC layer according to present invention.

FIG. 3 illustrates a method of implementing the grouped buffer structure by using indexed pointer stack according to present invention.

FIG. 4 is a plan view illustrating the packet scheduling in MAC of UTRAN according to present invention.

FIG. 5 shows the mechanism of priority control.

FIG. 6 is a flow chart illustrating the priority management according to present invention.

Detail of the invention In wireless data communications system such as UTRAN (Universal Terrestrial Radio Access Network), the lower layer of the protocol stacks comprises: PHY or LI (Physical layer, Layer 1) MAC (Medium Access Control sub-layer, lower part of Layer 2) RLC (Radio Link Control sub-layer, upper part of Layer 2) RRC (Radio Resource Control, Layer 3) PHY offers data transfer service over the radio link for the upper layers. MAC provides data transfer service for RLC and reallocates radio resources. On request, MAC also provides the traffic volume and quality indication to the higher layers. ARQ (Automatic Repeat Request) functionality is realized in the RLC sub-layer. This retransmission protocol ensures that the optimum utilization of the available radio resources is achieved without incurring excessively long delays.

RRC allocates radio resources on a'slow'basis. It decides and assigns transport format for service bearer possibly in a service life cycle to meet individual user's QoS requirement.

MAC controls radio resource on a'fast'basis, in the sense that, given the transport format combination set assigned by RRC. MAC selects the appropriate transport format within an assigned transport format set for each active transport channel depending on source rate and total interference threshold level.

The protocol structure of data link layer is shown in FIG. 1.

QoS requirement is met through a 2-level control : at a call arrival time scale (admission control) and at a frame duration scale (flow control). In the long run, admission control assures the initial connection could satisfy the QoS requirement; in short term, the resource may not meet the basic requirement of user, and then it is needed to decide how to downgrade the service.

The admission control guarantees that the QoS requirement can be met for all users admitted in the cell. In admission control, the system load is balanced so that real time services are given certain priority, while some bounded delay specification is met for delay tolerant applications. The design of admission control has interactions with power control etc, and has direct impact on QoS guarantees for voice and data. When it comes to flow control, for low QoS packets, overflow may occur and they may be discarded when channel capacity does not meet the requirement. The QoS guarantees are implemented through flow control mechanism, which schedule the system resources among users and their applications. Flow control ensures

that a flow's bandwidth does not exceed the end-to-end bottleneck of the connection and the sending rate for a flow does not exceed the rate at which the flow can be received. This control prevents a flow from congesting the network or overwhelming a slow receiver. Packet scheduler's upper bound on bandwidth allocation for a flow is calculated as the minimum of the limit and the bandwidth requirements of the flow. When the channel quality deteriorates, the QoS may not be satisfied any more.

RLC: Re-transmission buffering As shown in FIG. 1, ARQ is performed in RLC layer lying upon the scheduler.

Nowadays HARQ (Hybrid ARQ) is commonly used.

Packets transmitted in error are explicitly rescheduled after the ARQ feedback. Two ways may be used to deal with the re-transmission for error control : either RLC or MAC serves the data with high priority. For MAC-controlled mechanism, the re-transmitted data's weight will be increased; for RLC-controlled mechanism, we can prioritize the re-transmitted data, which can be implement it as follows: Assume the maximum transmission time is three. Then we construct a 3-group buffer.

Each group stores the corresponding retransmission data, as shown in FIG. 2. Each group stores the corresponding data that has been transmitted for certain times, e. g. group 0 stores the initial data and group 1 stores the data that has been transmitted once. Confirm message (ACK) will eliminate the packet, while negative confirm (NACK or time-out) will make it step down to next group. After three times'transmission, the packet will be discarded.

To meet the requirement of delay and reduce the total transmission time, the re- transmission data should be transmitted in advance of other data. Therefore, the output sequence should be group 2 first, group 1 second and group 0 last.

The simplest form of the buffer is equal size for all the groups. This may leads to memory efficiency problems. One problem is that the size of buffer is increasing. As FER (Frame Error Rate) is often very low, it is obviously that the group size reduces greatly with the re-transmission time. To reduce the overall size of the buffer, one way is to make the lower group thinner than upper one; a better way is to use a variable depth buffer.

As shown in FIG. 3, we use a pointer stack. The data queued in the buffer in First In First Out (FIFO) order is indexed by another pointer stack. The pointer stack is divided into N groups (in FIG. 3 we assume N=3). From top to bottom, the groups are numbered as A (zero), B (once), C (twice), which denotes the number of re-transmission. Data to be sent is coming from the pointer stack from bottom to top, i. e. the re-transmission data has higher priority. The

pointer is. modified when a NACK or timeout signal comes, e. g. a NACK for a data that has been transmitted twice will lead to the pointer in group C to point at it while remove the pointer in group B. The packets are kept transmitting until it is correctly received, or on the contrary, the time deadline is reached or maximum re-transmission time is reached. Then packet is deleted to make room for the coming packet data.

MAC: Scheduling Algorithm Unlike voice data that has constant QoS, packet data is bursty in nature and its QoS is changing at interval. An ideal scheduling interval is performed on a frame-by-frame basis.

A packet scheduler is a module in MAC layer that controls the allocation of radio resource to outgoing network traffic flows. By deciding which packet to be sent next, the packet scheduler not only determines how the resource is shared among flows, but also plays a key role in determining the rate and timing behavior of individual flow. The resource is shared proportionally between users'applications, ensuring the specified traffic a guaranteed portion of available resources. In order to utilize the spectrum resource efficiently for bursty transfer, a dynamic scheduling function may be applied.

We use multi-class priority queuing algorithm to provide service according to the QoS requirement on wireless link. The service classification is accomplished by providing both bounded delay and guaranteed bandwidth.

The queues represent different service classes. Each queue has its parameters such as queue size, classification, sorting schemes, etc. Each queue is scheduled according to a different policy depending on the traffic requirement. Packets from the low priority queue may only be transmitted after the high-priority queue is empty. However, in order not to starve the low priority queue, the queues are time duplex transmitted using WRR (Weighted Round Robin) periodically, i. e. the high priority queue will get more resource while the low priority queue will get less resource in the polling round. The proportion of service to each queue should be dynamically adjusted.

The queues in the scheduler can be mapped by different service classes, such as: Guaranteed services: provide a firm bound to bandwidth, delay and losses.

Controlled load services: minimize packet losses with assurance of the guaranteed services.

Best effort services: no guarantee.

In addition, we need to adjust the balance of scheduler and queues in order to fully utilize the memory of equipment and share the load among the queues, which prevent the

queue from overflow or starvation The classifier computes the packet weight and put the weighted data to the right queue for transmission. When a new packet comes with a certain priority, it will be put to the appropriate queue, and it could also be inserted to the appropriate order in the queue, which need extra operation time.

First, we compute the value of packet weight.

The purpose of weight calculation is to indicate the importance of a packet, so as to: Serve the packet with appropriate class.

Degrading the quality of service, if necessary, e. g. discarding the packet in the event of problems.

The following parameters should be taken into account: QoS requirement, bounded delay and bit error rate.

Estimated service time.

Resource utilization.

The main factor is the QoS parameters such as maximum delay, bit error rate and data rate. In addition, we need to consider other factors such as channel quality, estimated service time, etc. Weight grows with QoS, reduces with expect transmission time. Packets expected to be having less service time may have high priority to reduce the overall waiting time. Data re- transmitted has heavier weight than normal transmission. (E. g. HARQ) Control/signaling (especially link setup/release) have heavier weight than data. To increase resource utilization, traffic from a UE (User Equipment) with good channel quality may enjoy more service.

Therefore, the service mapping will not just simply map each QoS class to a fixed queue.

In summary, the weight is decided by bounded delay, BER, number of re-transmission times, throughput: W = f(Delay,BER,Nrt,CQ) (1) 'W denotes weight of priority level ;'NI'denotes number of re/transmission times; Thus, with these principles in mind, W can be determined by the following formula : W= m * GoSc*Nrt + n * CQ + Ts +g (lp (2) Where: GoS denotes grade of service, mainly affected by two factors: bounded delay and BER.

GoSc denotes the comparative GoS :

Ts denotes the estimated service time, normally decided by channel condition, packet size and modulation scheme. e. g. T, CQ ISOP, SoP stands for Size of Packet.

'Tq'denotes the packet queuing time. We use it to sort packet in queue. There is a time stamp for each packet. Depending on the scheduler used, the time stamp can be deadline, virtual finishing time or other value.

If the system adopts the RLC controlled mechanism (ARQ scheme of n-layer buffer as stated before), we could omit the ARQ effect, i. e. Nrt = 1. Otherwise, with MAC-controlled mechanism, the re-transmitted data weight is increased.

The coefficients m, n should be carefully selected to reflect the principles.

With the weight of packets computed, the classifier then groups the packets to different queues according to the'weight band'.

Each queue is associated with a range of weight value. The classifier calculates the weight with a series of threshold to decide to which queue the packet should be placed.

Suppose we the divide the band equally, i. e. queue P is associated with the weight in the range [min (P) + (P-1) A, min (P) + P A], where A denotes the steps of neighboring queues'weight difference. So the total range of weight s with P queues is given by ! (P), min (P) +P dz Each packet that arrives to the scheduler is weighted. A newly arrived packet is inserted to queue P if its weight is in (P-1) d, P d J.

The classifiers in UE and UTRAN are different. In UE, the classifier maps the packet of different QoS to different service classes. A mobile can set up multiple applications simultaneously, each having its own service characteristics (e. g. offering different error correction capability). Each application can be used for information transfer of one radio bearer for layer 2 and higher layer signaling messages. The multiplexing of these applications onto the same or different physical channels is carried out by layer 1. The TFCI (Transport Format Combination Indication) field uniquely identifies the transport format used by each transport channel. UTRAN has to resolve contention between mobiles accessing'the same physical resources and has to manage the packet access procedure. So the channel quality and priority of each UE should be taken into account and the weight be dynamically adjusted.

In order to provide QoS guarantee to all the users, traffic classifier and shaping modules are built into the MAC layer of UE and UTRAN. The protocol structure is shown in FIG. 4.

Priority control in UE is shown in FIG. 4 (a). Packet streams 401 come from data link layer enter Classifier 402, then go to the queues 403 inside scheduler 404. There are multiple queues 403 in the scheduler 404. The packets are put to the queues 403 according to their weight, e. g. top priority packets are put to the queue 403 (a), and so on. The packets come from the queues 403 then go to packet dispatcher 406.

Priority control in UTRAN is shown in FIG. 4 (b). Packet stream from either wire-lined terminal 409 or wireless terminals UEs 410 are scheduled respectively, and then enter UTRAN scheduler 413. The output. packets then go to the queues 414 inside scheduler 413.

There are multiple queues in the scheduler 413. Here we take 4 queues as an example. The packets are put to the queues 414 according to their weight. The packets also can be schedules between queues through channel 415, just like in UE.

Packet data streams from different application and users have various QoS requirement.

3GPP defined 4 distinct QoS classes (or traffic classes) for UMTS (Universal Mobile Telecommunications System): Conversational, Streaming, Interactive and Background. Each has its requirement of QoS: BER (Bit Error Rate), delay/jitter, etc. The main distinguishing factor of the QoS class is how delay sensitive the traffic is.

As in FIG. 5, when the network layer packets for a particular flow arrives, the QoS mapping block peeks into packet header to determine the flow characteristics and the class of service associated with it (if available, otherwise it is treated as best effort class by default).

Packets are served based on their service label.

The classifier is responsible for weight calculation and put the weighted data to the right queue for transmission. Then the packet scheduler manages the queues and sends the packet to lower layer.

The status of queues is dynamically varying due to the packet arrival rate and service rate of each queue. Another factor is that the weight of packets is not fixed, e. g. weight grows with queuing time, the queue need to be sorted periodically. If the weight is out of the band of current queue, the packet may transfer from one queue to another. The scheduler is also in charge of sorting the queues. Here we use different sorting policies for each queue. For high priority queues, e. g. guaranteed services queue, it is dynamically sorted at high frequency; for medium priority queue, the sort interval is longer; for low QoS requirement, it is just FIFO and no sorting at all.

We define three status of a queue:

Balanced Overload Under-load There are three parameters affecting the balance: Load proportion of queue, affected by length of the queue Input data rate (average), affected by the overall packet arrival rate and the packet classification portion Qi divided by the classifier Output data rate (average), affected by the service rate, WRR service portion Pi, overflow and discard scheme By computing the arriving rate, service rate and the load percentage, we can get the status of a queue.

Suppose that the packet arriving rate is 1 i, service rate is W i, the capacity of the queue is C, the occupied proportion of the queue is #.

Arrival rate: Qi* A X Service rate: Pi* W i The queue status can be mapped into a data queue load constraint : <BR> <BR> <BR> <BR> # = (#iQi - µiPi)#T<BR> <BR> <BR> (1-0)C A denotes the average packet arriving interval.

When the value of P is within a certain range, we deem the queue is balanced. When P is over certain limit, that means the queue tends to overflow. Then we can transfer the packet to other queue.

The criteria to judge whether the load is balanced or not is: zu is out of range P is out of range By synthesize the parameters we can tell if the queue is balanced or not.

When the difference of # and P between queues exceeds certain limit we deem it out of balance.

The measures could be either adjusting the arrival or service rate or sharing the load to other queues. There are various methods to dispose the balance problem such as RPQ (Rotating Priority Queue), RPQ+ (Priority queue schedulers with approximate sorting in output-buffered switches, IEEE Journal on selected areas in communications, VOL. 17, NO.

June 1999.) The key idea of RPQ is rotating the queues. Here we monitor the queue status periodically to check the status and periodically move the low priority packet up to high priority queue, when the weight of the packet exceeds the current band caused the queuing time growing.

We should pay attention to scheduler balance, including: The arrive/service rate balance of each queue The queue load balance between queues If necessary, adjust (e. g. downgrade) the service.

For the two kinds of balance, we can take the following measures: FIG. 6 illustrates in detail of the balance adjustment. In step 602, the method ascertains whether the queues in scheduler are empty or not. If yes, the method sends primitives to upper layer for data. If the queues are not empty and it is time to check the queue balance, this method checks the queue balance by computing the synthesis effect of weight and factor P in step 605. Frame 605 contains the queue balance adjustment method. If the queues are not balanced, first the method changes the arrival rate and service rate by altering the classifier's threshold and Round Robin proportion in step 608. For instance, if the queue is starving and the weight w (w is the average weight of the packets) is high, then the incoming classifier threshold should be lowered to expand the range of the weight. Then it comes to step 609 to check the average weight of the queues, so as to see whether it is appropriate to shift the packet from one queue to another in step 610. If the weight is out of current band, then the method check if the neighboring queue with the right weight band is able to accommodate the packets by computing the factor 0 and P. In order to reduce the complexity, the packet may be inserted to the tail of the target queue instead of insertion. For the bottom level queue, if the weight is varying the packets may be shift to upper queue or down to the dustbin, that is, discarded. The real time service will be discarded when the bounded delay reached.

In step 612, the method check if it is time to modify the scheduler balance. If not, it will wait for a certain time and return to step 612. When it is time to check the balance, the method calculate the factors 0 and P of all the queues to determine if it is right to alter the polling time. When the queue difference is out of range, i. e. scheduler balance is beyond limit, the polling time should be reduced. The maximum queue polling time must assure the minimum service QoS demand.

Together with the weight calculation, this could be called'Hybrid Dynamic Fairness Queuing. 'Three points are taken into account :'priority schedule','resource utility'and'equal opportunity'. The method coordinates the transmissions of all users so that the common channel is efficiently utilized and the QoS requirement of each user is satisfied. This method also applies for shared channels such as DSCH (Downlink Shared Channel), and applies to both TDD and FDD communications.

The aim of present invention is to solve the problems remains in prior art, including error control scheme, weight calculation of packet and multi-queue adjustment.

The present invention is designed to synthesis the parameters, while simultaneously giving fair opportunity to every user. The principle of scheduler is to get maximum system resource utilization with regard to required QoS, fair service and implementation complexity.

The QoS objectives are satisfied without requiring complex algorithm and accurate predictions of the users'future behaviors. Algorithm concerning QoS should be adopted with best efficiency and maximum traffic throughput principle.

Although the invention has been described in detail with reference only to a preferred embodiment, those skilled in the art will appreciate that various modifications can be made without departing from the invention. Accordingly, the invention is defined only by the following claims, which are intended to embrace all equivalents thereof.