WO2005041502A1

WO2005041502A1 - Packet scheduling system and method in mobile communication system

Info

Publication number: WO2005041502A1
Application number: PCT/KR2004/000432
Authority: WO
Inventors: Dong-Hoi Kim; Byung-Han Ryu
Original assignee: Electronics and Telecommunications Research Institute ETRI
Current assignee: Electronics and Telecommunications Research Institute ETRI
Priority date: 2003-10-27
Filing date: 2004-02-28
Publication date: 2005-05-06
Anticipated expiration: 2006-04-27
Also published as: KR100523996B1; KR20050040012A

Abstract

Disclosed is a scheduling system and method in a mobile communication system for servicing non-realtime traffic data. In the scheduling method, a per-subchannel bit rate for each user is calculated based on a bit length of non-realtime packet data and a standby time of the packets. As the calculated per-subchannel bit rate becomes lower, a higher priority metric is provided, and the packet scheduling is performed according to the provided priority metric, thereby satisfying the minimum bit rate and increasing the system capacity.

Description

PACKET SCHEDULING SYSTEM AND METHOD IN MOBILE COMMUNICATION SYSTEM

CROSS REFERENCE TO RELATED APPLICATION This application claims priority to and the benefit of Korea Patent Application No. 2003-75114 filed on October 27, 2003 in the Korean Intellectual Property Office, the content of which is incorporated herein by reference.

BACKGROUND OF THE INVENTION

(a) Field of the Invention The present invention relates to a packet scheduling system and method. More specifically, the present invention relates to a packet scheduling system and method for servicing non-realtime traffic data in a mobile communication system.

(b) Description of the Related Art

To effectively utilize restricted resources in radio communication environments, studies on packet scheduling algorithms for equivalently

providing radio resources to a plurality of users have been activated. That

is, as multimedia services that require various QoS (qualities of service)

have been realized, many methods of fairly allocating bandwidths of

output links of a packet scheduler for efficiently using the restricted radio resources have been proposed. In particular, an algorithm for effectively using the restricted resources, satisfying MBR (minimum bit rate) requirements, and increasing the whole capacity of a system is needed in the mobile communication system that services non-realtime traffic data. A PF (proportionally fair) algorithm has recently been proposed as a packet scheduling algorithm for non-realtime traffic data in addition to currently studied packet scheduling algorithms. The PF algorithm first of all allocates a subchannel to a user who

has the top priority based on a priority metric μ.(i) . In detail, following the PF algorithm, the priority metric μ_t(t) is

given in Equation 1 , and a service is provided to the user having the top

priority metric μ,(t) .

Equation 1 r, (t) where r,(t) is a data rate of transmission from a channel, and η(t)

is a mean data rate received by a user i to a slot t (i.e., a serviced mean

data rate). The serviced mean data rate is updated by Equation 2. Equation 2

where T_c is a time constant for exponential filtering, and for

example, T_c = 1 ,000 slots (1 second), and p_t.(t) is a current data rate of the user at the time t . Therefore, p_t(t) = 0 when the user currently

receives no service. However, when the conventional packet scheduler realized with

the PF algorithm schedules the non-realtime traffic data, part of the non-

realtime traffic data is frequently transmitted to each user terminal while

failing to satisfy the MBR.

Further, the conventional packet scheduler is limited in increasing

the total capacity of the system because of the outage probability of the

packets that are transmitted without satisfying the MBR.

SUMMARY OF THE INVENTION

It is an advantage of the present invention to provide a scheduling

method and system for satisfying the MBR and increasing the system

capacity. In one aspect of the present invention, a packet scheduling

method of a mobile communication system comprises:

(a) calculating a per-subchannel bit rate for each user based on a

bit length of input non-realtime packet data and a standby time of the

packet; (b) determining a priority metric by considering the calculated per-

subchannel bit rate; and

(c) performing packet scheduling according to the priority metric determined in (b). In another aspect of the present invention, a packet scheduling system in a mobile communication system comprises: a QoS (quality of service) manager for storing non-realtime traffic data from among the data received from an upper layer in an input buffer, and managing QoS information corresponding to the stored traffic data; a per-subchannel bit rate calculator for calculating the per- subchannel bit rate of the stored non-realtime traffic data; and a packet scheduler for determining priority metrics based on the per-subchannel bit rate calculated by the per-subchannel bit rate calculator and a user's channel transmission environment, and performing

packet scheduling based on the priority metrics. In still yet another aspect of the present invention, a packet scheduling method in an OFDMA/FDD (orthogonal frequency division multiplexing access/frequency division duplex) mobile communication system comprises: (a) storing non-realtime traffic data from among the packet data received from an upper layer in an input buffer; (b) calculating the per-subchannel bit rate for each user based on

the bit length of the non-realtime packet data stored in the input buffer and

the standby time of the packets, considering the calculated per-

subchannel bit rate, and determining a priority metric; (c) determining whether a number of subcarriers of a packet serviced per user is greater than a maximum number of subcarriers; (d) comparing the size of the remaining packets that are not processed before a scheduling update time of a first user having the high priority metric determined in (b) with the size of transmission data, when the number of the subcarriers of the serviced packet is not greater than the maximum number of subcarriers; and (e) performing the service by the size of the transmission data to

the first user and increasing the number of subcarriers by 1 when the size

of the remaining packets is greater than or equal to the size of the

transmission data, and performing the service by the size of the packets to

the first user and increasing the number of subcarriers by 1 when the size

of the remaining packets is less than the size of the transmission data.

In still yet another aspect of the present invention, in a recording

medium for recording a program having a realtime packet scheduling

function of a mobile communication system, the program comprises: calculating a per-subchannel bit rate for each user based on a bit

length of input non-realtime packet data and a standby time of the

packets; determining a priority metric by considering the calculated per-

subchannel bit rate; and performing packet scheduling according to the determined priority metric. BRIEF DESCRIPTION OF THE DRAWINGS

The accompanying drawings, which are incorporated in and

constitute a part of the specification, illustrate an embodiment of the

invention, and, together with the description, serve to explain the

principles of the invention: FIG. 1 shows a packet scheduling system according to a

preferred embodiment of the present invention;

FIG. 2 shows an exemplified web (WWW) service model using

non-realtime traffic data according to a preferred embodiment of the

present invention;

FIG. 3 shows an operational flowchart for a packet scheduling system according to a preferred embodiment of the present invention; and

FIG. 4 shows an operational flowchart when a packet scheduling

algorithm according to a preferred embodiment of the present invention is

installed in an OFDMA/FDD system.

DETAILED DESCRIPTION OF THE PREFERRED EMBODIMENTS

In the following detailed description, only the preferred

embodiment of the invention has been shown and described, simply by

way of illustration of the best mode contemplated by the inventor(s) of

carrying out the invention. As will be realized, the invention is capable of

modification in various obvious respects, all without departing from the

invention. Accordingly, the drawings and description are to be regarded as illustrative in nature, and not restrictive. A packet scheduling algorithm according to a preferred embodiment of the present invention will now be described. When non-realtime traffic data are not transmitted at the minimum guaranteed data rate, transmission loss occurs. Therefore, it is needed for the data to satisfy the QoS of the required minimum data rate in the non-realtime traffic data service. (1) Per-subchannel bit rate

The per-subchannel bit rate R,(t) for the user i at the slot time t

is given as Equation 3. Equation 3

R_l(t) = L_l(t)IW_l(t) where E,(t) is a total bit length of packets backlogged in a queue

at the slot time t with respect to the user / , and W_t (t) is a standby time of

the HOL (head of line) packets of the user per subchannel.

Conceptually, the per-subchannel bit rate is a valid bit rate for

actually guaranteeing that the user / can receive a per-subchannel

service at the current slot time t .

It is known from Equation 3 that it is a very important performance

measuring method to consider a relatively short standby time with respect

to the length of the backlogged packets per subchannel. (2) MBR-based scheduling algorithm A mean bit rate A of packet calls is given in Equation 4. Equation 4

A = Alτ where τ is a duration of the packet call, and A is a total sum of bits actually serviced to the user / during the packet call. Each non- realtime service user is to be serviced with a new QoS parameter, that is,

the minimum guarantee data rate R^' . The scheduling algorithm aims at

finding a new priority metric for increasing a number of the non-realtime service users satisfying the MBR requirements. For ease of description, it is assumed in the below that all data users have the same MBR requirements. It is desirable to share a predetermined data rate and provide a higher priority metric to a user of the lower bit rate so as to increase the number of web users satisfying the MBR requirements. The priority metric for the subchannels is defined as Equation 5, and the scheduling process is performed following the priority metric. Equation 5

_Λ( sfiU_ where the per-subchannel bit rate R, (t) tends to show

instantaneous resource overallocation. Therefore, as known by Equation 5, when the packets are scheduled so that the packets may have a higher

priority metric as the per-subchannel bit rate R, (t) becomes lower, the number of the non-realtime service users satisfying the MBR requirements is increased. That is, as known from Equations 3 and 5, according to the packet scheduling algorithm, a chance for scheduling the packets

becomes greater when the total bit length L,(t) of the packets backlogged

in the queue becomes shorter, and the standby time W,(t) of the HOL

packets becomes longer (i.e., the lower the per-subchannel bit rate becomes). r(f) Also, by additionally reflecting the value - - defined in Equation r,(?)

1 , the priority metric is provided to a good channel user, thereby

increasing the throughputs and improving the fairness between users. The

packet scheduling algorithm satisfies the MBR in the non-realtime traffic

data and increases system capacity.

FIG. 1 shows a detailed configuration of the packet scheduling

system according to the preferred embodiment of the present invention.

As shown, the packet scheduling system 100 is provided in a

base station 200 which provides information on channel states to the

packet scheduling system 100 through data communication with at least

one user terminal 301 through 300n. The packet scheduling system 100

determines priority metrics of the non-realtime traffic data to be

transmitted to the user terminals 301 through 300n.

The packet scheduling system 100 in the base station 200 schedules non-realtime traffic data from among the data received from an upper layer in the preferred embodiment, but without being restricted to

this, the packet scheduling system 100 can be included in various mobile

communication systems to schedule the non-realtime traffic data. The packet scheduling system 100 comprises a QoS manager

1 10, a per-subchannel bit rate calculator 120, and a packet scheduler 130. The QoS manager 1 10 stores the non-realtime traffic data from

among the IP (Internet packet) data received from the upper layer in an

input buffer (not illustrated), and manages corresponding QoS information. The per-subchannel bit rate calculator 120 calculates the per-

subchannel bit rates R,(t) of the packets stored in the QoS manager 1 10

based on Equation 3 for each user.

The packet scheduler 130 determines the priority metrics defined

in Equation 5 and performs packet scheduling based on the per¬

subchannel bit rates R,(t) , the data rates r₍(t) , and the serviced mean

data rates η(t) . In detail, the packet scheduler 130 assigns a high priority

metric to a user who has a less per-subchannel bit rate R,(t) and a good

channel state.

FIG. 2 shows an exemplified web (WWW) service model using non-realtime traffic data according to a preferred embodiment of the

present invention.

As shown, the non-realtime traffic data include sessions 210 determined by a temporal interval caused by using the WWW (world wide

web) service, and each session includes at least one packet call 21 1.

Each packet call 21 1 has a plurality of packets having the burst characteristic. An important phenomenon of the non-realtime traffic data is to configure a single packet call with a plurality of burst packets.

In this instance, the size of the packets in a WWW application

service can be modeled by the Pareto distribution. That is, each packet

and the number of packet calls have a geometrical distribution, and a

mutual arrival time 201 of the packets and a reading time 202 between the

packet calls have an exponential distribution. The above-generated non- realtime traffic data on the WWW service are input in the data buffer

classified per user, and then accumulated therein.

An operational process of the scheduling system for scheduling

the non-realtime traffic data will now be described.

FIG. 3 shows an operational flowchart for a packet scheduling

system according to a preferred embodiment of the present invention.

As shown, the QoS manager 1 10 in the packet scheduling system

100 stores non-realtime traffic data from among the IP (Internet packet)

data received from the upper layer in the input buffer, and manages QoS

information per stored non-realtime traffic data in step S310.

The per-subchannel bit rate calculator 120 calculates average

per-subchannel bit rates of the packets standing by in the input buffer, based on Equation 3 in step S320, to thus calculate per-subchannel bit rates for each user. The packet scheduler 130 compares ratios of the average per-

subchannel bit rates R,(t) , the data rates r,(t) , and the serviced mean

data rates r_t(t) to calculate the priority metrics according to the

comparison ratios for each user in step S330, and schedules the users

based on the calculated priority metrics in step S340.

FIG. 4 shows an operational flowchart when a packet scheduling

algorithm according to a preferred embodiment of the present invention is

installed in an OFDMA/FDD (orthogonal frequency division multiplexing

access/frequency division duplex) system, assuming that a number of subcarriers Nsubchannels for each frequency axis is 0, and the number

can be set as 12 to the maximum.

As shown, the OFDMA/FDD system determines whether the data

to be serviced are non-realtime traffic data in step S520.

When the data are found as the non-realtime traffic data, the

OFDMA/FDD system determines the priority metric based on the average

per-subchannel bit rates R,(t) , the data rates r_;(t) , and the serviced mean

data rates r;(t) , and determines whether the number of subcarriers in a

single packet serviced per user is greater than the number of the

maximum subcarriers (the number is 12 in FIG. 4) in step S540.

When the number of subcarriers in the serviced packet exceeds

the number of the maximum subcarriers, the OFDMA/FDD system terminates provision of the service. When the number of subcarriers in the serviced packet does not exceed the number of the maximum subcarriers,

the OFDMA/FDD system determines whether the size L^a(t) of the

remaining packets that are not processed before the scheduling update time t on the user a having a high priority metric is greater than or equal

to the transmit data size T^a(t) that follows a transmission method

determined by a signal to interference ratio value in step S550.

When the size L^a(t) is greater than or equal to the transmit data

size T^a(t) , the OFDMA/FDD system provides the service by the transmit

data size T^a(t) to the user , and increases the number of subcarriers by

1 in step S560.

When the packet size E°(t) is less than the transmit data size

T"(t) , the OFDMA/FDD system provides the service by the packet size

L^a(t) to the user a , and increases the number of subcarriers by 1 in step

S570. As described, the scheduling algorithm satisfies the MBR and

increases the system capacity.

While this invention has been described in connection with what is presently considered to be the most practical and preferred embodiment,

it is to be understood that the invention is not limited to the disclosed

embodiments, but, on the contrary, is intended to cover various

modifications and equivalent arrangements included within the spirit and scope of the appended claims.

Claims

WHAT IS CLAIMED IS:

1. A packet scheduling method of a mobile communication system, comprising: (a) calculating a per-subchannel bit rate for each user based on a bit length of input non-realtime packet data and a standby time of the packet; (b) determining a priority metric by considering the calculated per- subchannel bit rate; and (c) performing packet scheduling according to the priority metric determined in (b).

2. The method of claim 1 , wherein the per-subchannel bit rates

R,(t) is calculated by the equation: R_l(t) = L_l(t)IW,(t) where E,(t) is a total

bit length of packets backlogged in a queue at the slot time t , and W_t(t) is

a standby time of the HOL (head of line) packets of the user / per subchannel.

3. The method of claim 2, wherein the priority metric is established higher, the lower the per-subchannel bit rate becomes.

4. The method of claim 1 , wherein (b) comprises determining the

priority metric by additionally using a user's channel transmission

environment.

5. The method of claim 4, wherein the channel transmission

environment is determined by the ratio of a data rate r,(t) transmittable at a channel to a mean data rate r,(t) serviced to the user.

6. The method of one of claims 1 through 5, wherein the priority

metric is calculated by the equation μ,(t) where it is satisfied

that R_;(t) = E_;(t)/^,(t) , and E,(t) is a total bit length of packets backlogged

in a queue at the slot time t, W,(t) is a standby time of the HOL (head of

line) packets of the user / per subchannel, r,(t) is a data rate

transmittable at a channel, and r;(t) is a serviced mean data rate.

7. A packet scheduling system in a mobile communication system, comprising: a QoS (quality of service) manager for storing non-realtime traffic data from among data received from an upper layer in an input buffer, and managing QoS information corresponding to the stored traffic data; a per-subchannel bit rate calculator for calculating a per- subchannel bit rate of the stored non-realtime traffic data; and a packet scheduler for determining priority metrics based on the per-subchannel bit rate calculated by the per-subchannel bit rate calculator and a user's channel transmission environment, and performing

packet scheduling based on the priority metrics.

8. The system of claim 7, wherein the per-subchannel bit rate is determined based on a total bit length of packets backlogged in a queue of the input buffer and a standby time of HOL (head of line) packets of a user i per subchannel.

9. The system of claim 8, wherein the packet scheduler establishes the priority metrics to be higher as the total bit length of the packets backlogged in the queue of the input buffer becomes shorter and the standby time of the HOL packets of a user per subchannel becomes longer.

10. The system of one of claims 7 through 9, wherein the packet scheduling system is applied to an OFDMA/FDD (orthogonal frequency division multiplexing access/frequency division duplex) system.

11. A packet scheduling method in an OFDMA/FDD (orthogonal frequency division multiplexing access/frequency division duplex) mobile communication system, comprising: (a) storing non-realtime traffic data from among the packet data received from an upper layer in an input buffer; (b) calculating the per-subchannel bit rate for each user based on the bit length of the non-realtime packet data stored in the input buffer and the standby time of the packets, considering the calculated per- subchannel bit rate, and determining a priority metric; (c) determining whether a number of subcarriers of a packet serviced per user is greater than a maximum number of subcarriers; (d) comparing the size of the remaining packets that are not processed before a scheduling update time of a first user having the high priority metric determined in (b) with the size of transmission data, when the number of the subcarriers of the serviced packet is not greater than the maximum number of subcarriers; and (e) performing the service by the size of the transmission data to the first user and increasing the number of subcarriers by 1 when the size of the remaining packets is greater than or equal to the size of the transmission data, and performing the service by the size of the packets to the first user and increasing the number of subcarriers by 1 when the size of the remaining packets is less than the size of the transmission data.

12. The method of claim 11 , wherein (b) comprises establishing the priority metric to be higher as the bit length of the packet data stored in the input buffer becomes shorter and the standby time of the packet becomes longer.

13. A recording medium for recording a program having a realtime packet scheduling function of a mobile communication system,

the program comprising: calculating a per-subchannel bit rate for each user based on a bit

length of input non-realtime packet data and a standby time of the

packets; determining a priority metric by considering the calculated per-

subchannel bit rate; and performing packet scheduling according to the determined priority metric.