Multiplex communications – Data flow congestion prevention or control – Control of data admission to the network
Reexamination Certificate
2000-06-21
2004-08-10
Marcelo, Melvin (Department: 2663)
Multiplex communications
Data flow congestion prevention or control
Control of data admission to the network
C370S395210
Reexamination Certificate
active
06775233
ABSTRACT:
FIELD OF THE INVENTION
The present invention relates generally to wireless communication systems and more particularly to techniques for scheduling data transmissions in wireless code division multiple access (CDMA) systems and other types of wireless systems.
BACKGROUND OF THE INVENTION
An increasingly important issue in CDMA systems and other types of wireless systems is scheduling and rate allocation for data transmissions from system base stations to mobile users, i.e., forward link data transmissions. Such systems are moving toward configurations in which mobile users will have heterogenous Quality of Service (QoS) and traffic characteristics. The problem that arises is to how to share resources between mobiles in such a way that their QoS requirements can be effectively met while operating the system with a reasonable level of efficiency. This situation is to be contrasted with that of voice traffic, for which CDMA allows statistical averaging to take place among a large number of delay intolerant users with a common requirement. For data traffic, which is typically more bursty and delay tolerant than voice traffic, scheduling can be used to manage power usage and as a mechanism to control interference.
A conventional scheduling approach used in wired systems is referred to as Generalised Processor Sharing (GPS), and is described in greater detail in, e.g., G. Kesidis, “ATM Network Performance,” Kluwer, Boston, Mass., 1996, S. Keshav, “An Engineering Approach to Computer Networking,” Addison Wesley, Reading, Mass., 1997, D. Stiliadis and A. Varma, “Rate Proportional Servers: A Design Methodology for Fair Queuing Algorithms,” IEEE/ACM Trans. Networking, 6:164-174, April 1998, and D. Stiliadis and A. Varma, “Efficient Fair Queuing Algorithms for Packet Switched Networks,” IEEE/ACM Trans. Networking, 6:175-185, April 1998, all of which are incorporated by reference herein. The GPS approach converts user QoS requirements into a minimal rate assignment which is provided with high probability, and also provides a Call Admission Control (CAC) framework. The GPS approach is based in part on statistical multiplexing, as described in, e.g., A. Elwalid and D. Mitra, “Design of Generalized Processor Sharing Schedulers which Statistically Multiplex Heterogeneous QoS Classes,” Proc. of IEEE INFOCOM'99, March 1999, pp. 1220-1230, and A. Elwalid, D. Mitra, and R. H. Wentworth. “A New Approach for Allocating Buffers and Bandwidth to Heterogenous, Regulated Traffic in an ATM Node,” IEEE Journal on Selected Areas in Communications, 13(6): 1115-1127, August 1995, both of which are incorporated by reference herein.
Despite the advantages provided by the GPS approach in wired systems, the approach is not readily applicable to wireless systems due to wireless-specific complications such as power control and user interference. Therefore, what is needed is an improved approach for scheduling data transmissions in CDMA systems and other types of wireless systems.
SUMMARY OF THE INVENTION
The invention provides methods and apparatus for scheduling data transmissions in CDMA systems and other types of wireless communication systems.
In accordance with the invention, the scheduling of data transmissions in a CDMA system or other type of wireless communication system is implemented using a rate processor sharing approach. This approach converts user Quality of Service (QoS) requirements for forward link data transmission into a rate and a corresponding violation probability, and then divides an available system resource such as transmission power among the users in accordance with the rates. For example, the approach may determine for each user i a rate R
i
to be provided for user i with a probability 1−e
−&dgr;
i
, where the &dgr;
i
may be determined independently for each of the users. The system resource may be divided among the users in a manner which satisfies a linear relationship involving the rates and corresponding cost factors of the users. The portion of the system resource allocated to a given user may be fixed for a designated scheduling interval.
In accordance with another aspect of the invention, statistical multiplexing gain may be provided for applications involving multiple bursty users by generating a characterization of the forward link data transmission activity &agr;
i
of each user i. The activity factor &agr;
i
denotes the fraction of time the user i actually uses its assigned portion of the system resource. The activity factor &agr;
i
is a function of the rate R
i
of the user i, which is preferably selected to be between a peak rate and a mean data rate for the user i. A queuing model may be used to determine a minimum rate R
i
and corresponding activity factor &agr;
i
that would meet the QoS requirement of user i with a high target probability.
In accordance with another aspect of the invention, an admission control function is provided in which an exact computation or a Chernoff bound approximation is utilized to determine rate violation probabilities for each of the users. The admission control function ensures that a given one of the users is admitted to utilize a portion of the available system resource only if its corresponding rate violation probability meets one or more established criteria.
Advantageously, the rate processor sharing approach of the present invention provides a robust means of system resource sharing in which users with heterogenous QoS requirements can be efficiently supported.
REFERENCES:
patent: 5691975 (1997-11-01), Hamada et al.
patent: 2003/0198204 (2003-10-01), Taneja et al.
G. Kesidis, “ATM Network Performance,” Kluwer, Boston, MA, 4 pages, 1996.
A. Elwalid et al., “Design of Generalized Processor Sharing Schedulers which Statistically Multiplex Heterogeneous QoS Classes,” Proc. of IEEE INFOCOM'99, pp. 1-35, Mar. 1999.
A. Elwalid et al., “A New Approach for Allocating Buffers and Bandwidth to Heterogenous, Regulated Traffic in an ATM Node,” IEEE Journal on Selected Areas in Communications, vol. 13, No. 6, pp. 1115-1127, Aug. 1995.
P. Bender et al., “CDMA/HDR: A Bandwidth Efficient High Speed Wireless Data Service for Nomadic Users,” QUALCOMM, pp. 1-34, undated.
D. Stiliadis and A. Varma, “Rate Proportional Servers: A Design Methodology for Fair Queuing Algorithms,” IEEE/ACM Trans. Networking, vol. 6, No. 2, pp. 164-174, Apr. 1998.
D. Stiliadis and A. Varma, “Efficient Fair Queuing Algorithms for Packet Switched Networks,” IEEE/ACM Trans. Networking, vol. 6, No. 2, pp. 175-185, Apr. 1998.
Kumaran Krishnan
Whiting Philip Alfred
Lucent Technologies - Inc.
Marcelo Melvin
LandOfFree
Rate processor sharing method and apparatus for scheduling... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Rate processor sharing method and apparatus for scheduling..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Rate processor sharing method and apparatus for scheduling... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3329378