CN100579060C - Method and apparatus for controlling admission in a communication system supporting IP applications - Google Patents

Abstract

A method and apparatus for admission control in a communication system. AN Access Network element determines available resources. The AN allows a requesting application flow to enter when the available resources are sufficient to support the requirements of the application flow. The AN updates the metrics of the available resources periodically and upon the occurrence of a triggering event. The admission control may operate in conjunction with a scheduler that applies compensation factors for each flow type and for the total flow for a given user.

Description

Method and device for controlling access in a communication system supporting IP applications

Priority claims under 35 U.S.C. §119

This patent application claims priority to Provisional Patent Application No. 60/455,906, filed March 17, 2003, entitled "System for Allocating Resources in a Communication System," assigned to the assignee of the present invention, and is therefore not hereby Enter for reference.

background

1. Field of invention:

The present invention relates to communication systems. In particular, the embodiments are directed to allocating communication resources among users of a communication system.

2. Related technologies:

Several solutions have been proposed to solve the problem of allocating the limited communication resources provided by a single node in a communication system among multiple users. One goal of such systems is to provide sufficient resources at each node to satisfy the needs of all users while minimizing cost. Thus, such systems are typically designed with the goal of efficiently allocating resources among users.

Various systems have implemented Frequency Division Multiple Access (FDMA) schemes that allocate resources to each user concurrently. Communication nodes in such systems typically have limited bandwidth to send information to or receive information from each user in the network at any point in time. This scenario usually involves allocating different parts of the total bandwidth to individual users. While this scheme may be effective for systems where users require uninterrupted communication with communicating nodes, when such continuous, uninterrupted communication is not necessary, better utilization of the overall bandwidth is achievable.

Other schemes for allocating the communication resources of a single communication node among multiple users include Time Division Multiple Access (TDMA) schemes. These TDMA schemes are particularly effective at allocating the limited bandwidth resources of a single communication node among multiple users where the users do not require continuous, undisturbed communication with the single communication node. The TDMA scheme usually makes the entire bandwidth of a single communication node dedicated to each user at specified time intervals. In a wireless communication system using a code division multiple access (CDMA) scheme, this can be achieved by allocating all code channels to each user at specified time intervals on a time division multiplex basis. A communication node implements a unique carrier frequency or channel code associated with a user to allow exclusive communication with that user. TDMA schemes can also be implemented in landline systems using physical contact relay switching or packet switching.

TDMA systems typically assign equal time intervals to each user in a round-robin fashion. This may lead to underutilization of certain time intervals by some users. Similarly, other users may have demands for communication resources that exceed the allotted time interval, such that these users cannot be satisfied. System operators can choose to incur the cost of increasing node bandwidth to ensure that no users are unsatisfied, or to allow unsatisfied users to remain unsatisfied.

Accordingly, there is a need to provide a system and method for efficiently and fairly allocating communication resources among users of a communication network according to a network policy for allocating communication resources among users. Consistent with this, there is a need to maximize the number of users served by the system, including, but not limited to, providing a variety of responses to the specific requirements, constraints, and/or goals of the system, on a per-process basis and/or A mechanism for resource allocation on an aggregate basis. There is also a need for admission control and preemption methods that optimize resource allocation.

Brief description of the drawings

Fig. 1 shows a communication network according to an embodiment of the present invention.

Figure 2A shows a block diagram of a base station controller and base station equipment configured in accordance with one embodiment of the present invention.

Figure 2B shows a block diagram of a remote station device configured in accordance with one embodiment of the present invention.

Fig. 3 shows a flowchart of a scheduling algorithm implemented in the embodiment of the channel scheduler shown in Fig. 2A.

Figure 4 is a communication system supporting multimedia applications, where each application communication is represented by an application flow.

Figure 5 is an application process queue.

Figure 6 is a timing diagram depicting signal timing for part of an application flow.

Figure 7A is a timing diagram depicting jitter measurements for an application flow.

Fig. 7B is a timing diagram depicting the flow of processing an application, sending successive IP packets during several time slots.

Fig. 8 is a flowchart depicting the scheduling of several application processes in a communication system.

Figure 9 is a flow chart depicting the scheduling of several application processes with different Quality of Service (QoS) requirements.

Figure 10 is an architectural diagram showing the definition of each application process in accordance with a scheduling algorithm, according to one embodiment.

Figure 11 is a table identifying types of classifications, according to one embodiment.

Figure 12A depicts a portion of a scheduling algorithm, including initialization of the application process, according to one embodiment.

Figure 12B depicts a portion of a scheduling algorithm, including processing of application processes according to class type, according to one embodiment.

Figure 12C depicts a portion of a scheduling algorithm, including processing of Mode I application flows, processing of Mode II application flows, and processing of Mode III application flows, according to one embodiment.

Figure 12D depicts a portion of a scheduling algorithm, including processing for Mode I application flows, according to one embodiment.

Figure 12E depicts a portion of a scheduling algorithm, including adaptive weights and scheduling based thereon, according to one embodiment.

Fig. 13 shows a base transceiver system (BTS) for implementing an algorithm for scheduling application program flows using an adaptive weighting algorithm in a wireless communication system.

Figure 14 is a timing diagram plotting maximum resources such as data rate (L _MAX ), reserved resources (Res(t)), and available resources (Avail(t)) as a function of time.

Figure 15 is a timing diagram plotting data requests received from users in a high rate packet data type system and the estimated capacity L(t) to be reserved at time t as a function of time.

Figure 16 is an information flow diagram depicting a scheduler for a high-rate packet data type system supporting multiple application flows with quality of service (QoS) requirements, where the flows are scheduled applying per-flow offsets .

Figure 17 is an information flow diagram depicting a scheduler for a high rate packet data type system supporting multiple application processes with quality of service (QoS) requirements, where the processes are scheduled using aggregate offsets.

18A to 18E illustrate an algorithm for admission control in a high rate packet data type system supporting multiple application flows with quality of service (QoS) requirements.

Figure 19 shows an algorithm for preemption in a high rate packet data type system supporting multiple application flows with quality of service (QoS) requirements.

Figure 20 is a block diagram of an access network (AN) in a high rate packet data type system supporting multiple application flows with quality of service (QoS) requirements.

specific description

Various embodiments of the invention are directed to a system and apparatus for allocating resources among multiple users served by a single communication node in a communication network. During individual discrete transmission intervals, or "service intervals," a single user occupies the limited resources of a communication node to the exclusion of all other users. Individual users are selected to occupy the limited resource based on weights or scores associated with the individual users. Preferably, changes to weights associated with an individual user are based on the instantaneous rate at which the individual user is able to consume the finite resource.

Referring to the drawings, Figure 1 shows an exemplary variable rate communication system. One such system is described in U.S. Patent Application No. 08/11, filed November 3, 1997, entitled "Method and Apparatus for High Rate Packet Data Transmission," assigned to Qualcomm Incorporated. 963,386 (now US Patent No. 6,574,211 issued June 3, 2003), and incorporated herein by reference. The variable rate communication system includes a plurality of units 2A-2G. Each cell 2 is served by a corresponding base station 4 . Various remote stations are distributed throughout the communication system. In the exemplary embodiment, each remote station 6 communicates with at most one base station 4 on the forward link at arbitrary data transmission intervals. For example, on the forward link at time slot n, base station 4A transmits data exclusively to remote station 6A, base station 4B transmits data exclusively to remote station 6B, and base station 4C transmits data exclusively to remote station 6C. As shown in FIG. 1, each base station 4 preferably transmits data to a remote station 6 at any given time. In other embodiments, a base station 4 may communicate with more than one remote station 6 at certain data transmission intervals while excluding all other remote stations 6 associated with the base station 4 . In addition, the data rate is variable, and in one embodiment, the data rate is dependent on the carrier-to-interference ratio (C/I) measured by the receiving remote station 6, and the desired energy-to-noise ratio per bit (E _b /N ₀ ). For simplicity, the backward link from remote station 6 to base station 4 is not shown in FIG. 1 . According to one embodiment, the remote station 6 is a mobile unit having a wireless transceiver operated by a wireless data service subscriber.

Block diagrams illustrating the basic subsystems of an exemplary variable rate communication system are shown in Figures 2A-2B. The base station controller 10 interfaces with the packet network interface 24, the public switched telephone network (PSTN) 30, and all base stations 4 (only one base station 4 is shown in FIG. 2 for simplicity) in the communication system. Base station controller 10 coordinates communications between remote stations 6 and other users connected to packet network interface 24 and PSTN 30 in the communication network. PSTN 30 interfaces with subscribers via a standard telephone network (not shown in Figure 2).

The base station controller 10 contains a number of selector elements 14, although for simplicity only one is shown in Figure 2A. Each selector element 14 is assigned to control communications between one or more base stations 4 and one remote station 6 . If the selector element 14 is not assigned to a remote station 6, the call control processor 16 is notified of the need to page the remote station 6. Call control processor 16 then assigns base station 4 to page remote station 6 .

Data source 20 contains a large amount of data to be transmitted to remote station 6 . Data source 20 provides data to packet network interface 24 . Packet network interface 24 receives data and sends the data to selector element 14 . The selector element 14 transmits data to each base station 4 communicating with a remote station 6 . In the exemplary embodiment, each base station 4 maintains a data queue 40 which stores data to be transmitted to remote stations 6 .

Data is transferred from data queue 40 to channel element 42 in the form of data packets. In the exemplary embodiment, on the forward link, a "data packet" refers to a certain amount of data, which is at most 1024 bits, and is to be transmitted to the destination within one "slot" (such as ≈1.667 milliseconds) remote station6. For each data packet, channel element 42 inserts the necessary control fields. In the exemplary embodiment, channel element 42 CRC-encodes the data packet and control fields and inserts a set of code tail bits. Data packets, control fields, CRC parity bits, and code tail bits make up a formatted packet. In the exemplary embodiment, channel element 42 then encodes the formatted packet and interleaves (or reorders) the symbols within the encoded packet. In this exemplary embodiment, the interleaved packets are covered with Walsh codes and the interleaved packets are spread with short PNI and PNQ codes. The spread data is provided to RF unit 44 which quadrature modulates, filters and amplifies the signal. Forward link signals are transmitted through the air via antenna 46 on forward link 50 .

At remote station 6 , the forward link signal is received by antenna 60 and sent to a receiver inside front end 62 . The receiver filters, amplifies, quadrature demodulates and quantizes the signal. The digitized signal is provided to a demodulator (DEMOD) 64 where it is despread with short PNI and PNQ codes and overlaid with Walsh codes. The demodulated data is provided to a decoder 66 which performs the inverse of the signal processing functions performed at the base station 4, specifically the deinterleaving, decoding, and CRC checking functions. The decoded data is provided to a data receiver 68 .

The hardware as noted above supports variable rate transmission of data, messaging, voice, video and other communications on the forward link. The rate of data transmission from data queue 40 varies to accommodate changes in signal strength and noise environment at remote station 6 . Preferably, each remote station 6 transmits a data rate control (DRC) signal to the associated base station 4 every time slot. DRC refers to a control mechanism by which a remote station determines the desired data rate for the forward link, ie, the data rate at which data is received at the remote station. The remote station sends the desired data rate as a data rate request or instruction to the base station via a DRC message. The DRC signal provides information to the base station 4, including the identity of the remote station 6, and the rate at which the remote station is to receive data from its associated data queue. Thus, circuitry at remote station 6 measures the signal strength and estimates the noise environment at remote station 6 to determine the rate information to be transmitted in the DRC signal.

The DRC signal transmitted by each remote station 6 travels along the backward link channel 52 and is received at the base station 4 via the antenna 46 and the RF unit 44 . In the exemplary embodiment, the DRC information is demodulated in channel element 42 and provided to channel scheduler 12A located in base station controller 10 or to channel scheduler 12B located in base station 4 . In the first exemplary embodiment, the channel scheduler 12B is located in the base station 4 . In an alternative embodiment, the channel scheduler 12A is located in the base station controller 10 and is connected to all selector elements 14 inside the base station controller 10 .

In one embodiment, channel scheduler 12B receives information from data queue 40 indicating the amount of data queued for each remote station (also known as the queue size). The channel scheduler 12B then schedules based on the DRC information and the queue size of each remote station served by the base station 4 . Channel scheduler 12A may receive queue size information from selector element 14 if the scheduling algorithm used in an alternative embodiment requests a queue size.

Various embodiments of the invention are applicable to other hardware architectures that may support variable rate transmission. The invention can be easily extended to cover variable rate transmissions on the backward link. For example, instead of determining the rate at which data is received at base station 4 based on the DRC signal from remote station 6, base station 4 measures the strength of the signal received from remote station 6 and estimates the noise environment to determine the rate at which data is received from remote station 6 . The base station 4 then transmits to each associated remote station 6 the rate of data to be transmitted from the remote station 6 in the backward link. Base station 4 can then schedule transmissions on the backward link based on the different data rates on the backward link in a manner similar to that described herein for the forward link.

Likewise, the base station 4 of the embodiments discussed above transmits to a selected remote station or stations using a CDMA scheme, while rejecting the remaining remote stations associated with that base station 4 . At any given time, a base station 4 transmits to a selected remote station or stations 6 using a code assigned to the receiving base station 4 . However, the invention is also applicable to other systems that provide data using different TDMA methods to select several base stations 4 while excluding others 4 for optimal allocation of transmission resources.

Channel scheduler 12 schedules variable rate transmissions on the forward link. Channel scheduler 12 receives a queue size indicating the amount of data to be transmitted to remote station 6 and a message from remote station 6 . Preferably, the channel scheduler 12 schedules data transmissions to achieve the system goal of maximizing data throughput while respecting fairness constraints.

As shown in Figure 1, remote stations 6 are distributed throughout the communication system and can communicate with zero or one base station 4 on the forward link. In the exemplary embodiment, channel scheduler 12 coordinates forward link data transmissions throughout the communication system. A scheduling method and apparatus for high-speed data transmission is described in detail in US Patent No. 6,335,922, issued January 1, 2002, assigned to the assignee of the present invention, and incorporated herein by reference.

According to one embodiment, channel scheduler 12 is implemented in a computer system that includes a processor, random access memory (RAM), and program memory (not shown) for storing instructions to be executed by the processor. Processor, RAM and program memory may be occupied by various functions of channel scheduler 12 . In other embodiments, the processor, RAM and program memory may be part of shared computing resources used to perform other functions at the base station controller 10 .

FIG. 3 shows an embodiment of a scheduling algorithm that controls channel scheduler 12 to schedule transmissions from base station 4 to remote station 6 . As discussed above, one data queue 40 is associated with each remote station 6 . Channel scheduler 12 associates each data queue 40 with a "weight" estimated at step 110 for selecting a particular remote station 6 associated with base station 4 from which to receive data during the ensuing service interval. Channel scheduler 12 selects individual remote stations 6 to receive data transmissions during discrete service intervals. In step 102 , the channel scheduler initializes weights for each queue associated with base station 4 .

The channel scheduler 12 cycles through steps 104 to 112 in transmission intervals or service intervals. In step 104, the channel scheduler 12 determines whether there are any other queues to add due to an association between another remote station 6 and the base station 4 detected in the previous service interval. The channel scheduler 12 also initializes the weights associated with the new queue at step 104 . As discussed above, base station 4 receives DRC signals from each remote station 6 associated therewith at regular intervals, such as time slots.

This DRC signal also provides information for use by the channel scheduler at step 106 to determine the instantaneous rate at which information is consumed (or transmitted data is received) for remote stations associated with each queue. According to one embodiment, a DRC signal transmitted from any remote station 6 indicates that the remote station 6 is capable of receiving data at any one of a plurality of effective data rates.

Based on the instantaneous rate at which remote station 6 is associated with received data (as indicated in the most recently received DRC signal), channel scheduler 12 determines the length of the service interval during which data is sent to Any particular remote station6. According to one embodiment, at step 106, the instantaneous rate R _i of received data determines the service interval length L _i associated with a particular data queue.

Channel scheduler 12 selects a particular data queue for transmission at step 110 . The associated data volume to be sent is then retrieved from the data queue 40 and provided to the channel element 42 for transmission to the remote station 6 associated with that data queue 40 . As discussed below, channel scheduler 12 selects at step 110 queues to provide data for transmission in the ensuing service interval with information including each weight associated with each queue. The weights associated with the transmitted queues are then updated at step 112 .

Those skilled in the art will appreciate that the channel scheduler 12 can be implemented in various ways without departing from the invention. For example, channel scheduler 12 may be implemented with a computer system including a processor, random access memory (RAM), and program memory (not shown) for storing instructions to be executed by the processor. In other embodiments, the various functions of the channel scheduler 12 may be incorporated into shared computing resources that are also used to perform other functions at the base station 4 or base station controller 10 . In addition, the processor used to perform the function of the channel scheduler may be a general purpose microprocessor, digital signal processor (DSP), programmable logic device, application specific integrated circuit (ASIC), or be capable of performing various algorithms described herein other devices without departing from the invention.

As shown in the embodiment of FIG. 1 , the remote station 6 is mobile and can change associations between different base stations 4 . For example, remote station 6F initially receives a data transmission from base station 4F. Remote station 6F may then move out of the unit of base station 4F and into the unit of base station 4G. The remote station 6F can then start transmitting a DRC signal to alert the base station 4G, but not the base station 4F. By no longer receiving a DRC signal from remote station 6F, logic at base station 4F deduces that remote station 6F has detached and is no longer ready to receive data transmissions. The data queue associated with remote station 6F can then be transmitted to base station 4G via a landline or RF communication link.

Adaptive Weighted Scheduling Algorithm

Furthermore, there is a problem when transmitting multimedia services or other services having various transmission requirements in a wireless communication system, wherein transmission of multimedia services called "flows" causes bursty traffic. Bursty traffic is characterized by several variables, including a measure of burstiness, and average data rate. In addition, quality of service (QoS) requirements for each of the various processes in the system need to be met. Current scheduling methods, such as the proportional fair (PF) algorithm, are generally based on a metric given as the ratio of the requested data rate (called Data Rate Control Data Request or "DRC") to throughput (denoted "T"), to select the process to be served. Such calculations may not ensure the required QoS for all users. Therefore, pure PF algorithms may not provide enough complexity to meet the QoS requirements of users accessing multimedia or other applications. A scheduler that can meet these different requirements is needed.

Note that the following discussion considers a cdma2000 system supporting High Rate Packet Data (HRPD) service as described in IS-856. This system is used as an example. The invention is applicable to other systems that can select users to be served according to a scheduling algorithm.

In HRPD systems, the air interface can support up to 4 parallel application streams. The first flow carries signaling information and the other three flows can be used to carry applications or other applications with different Quality of Service (QoS) requirements.

For a clear understanding of one embodiment presented below, the following glossary is provided. The following glossary is not intended to be exhaustive. The following glossary is not intended to limit the present invention thereto, but is provided for clarity and understanding of an embodiment of a communication system supporting an adaptive weighted scheduling algorithm.

Glossary

Access Network (AN) - The network equipment that provides data connectivity between cellular networks and packet-switched data networks (commonly referred to as the Internet) and ATs. The AN in the HRPD system is equivalent to the base station in the cellular communication system.

Access Terminal (AT) - A device that provides data connectivity to a user. An AT in an HRPD system corresponds to a mobile station in a cellular communication system. The AT can be connected to a computing device such as a laptop personal computer, or it can be a self-contained data device such as a personal digital assistant (PDA).

Application Flow - The specified transmission path from source to AT for a given application flow. Each application process is identified by a source, destination, traffic profile, and quality of service profile.

Application Flow - Corresponds to the data communication of an application. Most application flows have specified quality of service requirements.

Automatic Repeat Request (ARQ) - mechanism by which a transmitter initiates data retransmission based on the occurrence or non-occurrence of an event.

Available resources (t): Unrestricted bandwidth on the forward link at time t.

Average Data Rate (r) - Average input data rate for a given application process over time.

Average Delay (AvgD) - The average delay experienced over a number of packets or bits from AN to AT.

Burstiness (σ) - A measure of the burstiness or density versus time of data packets in an application process.

Data Rate Control (DRC) - The mechanism by which the AT transmits the requested data rate to the AN.

Deficit packets (defpkts) - defined for flow k at the beginning of slot n. Deficit packets are packets that have not yet been transmitted in a flow, and defpkts is specifically defined as the number of equal-sized packets (e.g., intermediate processing packets such as Media Access Control (MAC) packets) whose dwell time at the BTS exceeds the delay threshold for flow k number.

Deficit Bits (defbits) - The number of bits corresponding to the deficient grouping.

Delay Boundary - The specified time allowed to transmit a data packet from AN to AT.

delay_threshold - function of delay bounds or jitter bounds used to calculate defpkts.

Delay Compensation Factor (Φ) - Compensation factor used to compensate for delay violations.

DRC Offset Factor (β) - An offset factor that takes into account the data request requirements associated with the user of the application process. Used for proper recovery of applications.

Enhanced Jitter Threshold (dv) - Used for the calculation of the enhanced jitter compensation function when a jitter violation between two consecutive IP packets of a flow is detected.

Process Weight (w) - The initial weight applied to each application process using the Adaptive Weighted Scheduling algorithm. The adaptive weight (aw) is the adaptive value of the weight.

Forward Link (FL) - Transport air link from AN to AT.

Head of Line (HOL) Packet - The first packet in the queue.

High Rate Packet Data (HRPD) - A data service that transports packet data communications at high data rates. Also known as High Data Rate (HDR), it is specified in the IS-856 standard entitled "cdma2000 High Rate Packet Data Air Interface Specification" (cdma2000 High Rate Packet Data Air Interface Specification).

Jitter - The variation in time between successive packets received.

JitterBound(j) - Bound on the jitter for a given application flow.

Enhanced Jitter Compensation Factor (δ) - Compensation factor to compensate for jitter violations for the process.

_Lmax - The maximum rate at which the BTS can transmit data on the forward link (eg, 2.4 Mbit/s in a cdma2000 1xEV-DO type network).

L(t) - An estimate of the reserved forward link capacity at time t based on statistics of previous QoS violations and statistics related to network load.

Normalized Deficit Packets (ndefpkts) - Normalized Deficit Packets computed using Deficit Packets and the rate requested by this process.

Normalized Deficit Bits (ndefbits) - The normalized deficient bits corresponding to the normalized deficient grouping.

Moving Picture Experts Group (MPEG) - A protocol for the transmission of multimedia material.

Pending Packets - pend _{k, j} [n] - number of bytes pending for IP packet j of flow k in BTS and BSC in slot n.

Proportional Fairness (PF) Algorithm - A scheduling algorithm that schedules data traffic according to a selection factor calculated for each AT as a ratio of requested data rate to throughput.

Quality of Service (QoS)-relates to requirements for packet data communication transmissions, including, but not limited to, latency, request rate, and jitter.

QoS and Network Compensation Functions (Φ, γ, α, β, δ) - Compensation functions as used in adaptive weighted scheduling algorithms.

Quality of Service Group (QSG) - A group of application types with similar QoS requirements.

Rate Compensation Factor (α) - Compensation factor calculated to compensate for rate violations.

Service Rate (R) or Requested Rate (required_rate) - The rate requested by the process.

Res(t): bandwidth reserved on the forward link at time t.

Resend Queue (Rx) - A resend queue that stores application processes scheduled for resend.

Reverse Link (RL) - Transport air link from AT to AN.

Selection Metric (Y) - The metric used to compare application processes for scheduling decisions.

Traffic Profile (σ, r) - a measure related to burstiness and data rate.

Transmit Queue (Tx) - Stores the Transmit Queue for the application process for a given BTS.

Latency parameter (γ) - A measure of the latency of the top IP packet inside the AN.

Applying Adaptive Weights to Proportional Fair Scheduling Algorithms

A proportional fair (PF) scheduling algorithm is described for the forward link of a cdma2000 1xEV-DO network, which selects the process to serve based on the metric DRC/T. The PF algorithm is designed to provide approximately the same number of transmission slots to each user. To enhance this scheduling algorithm, described in this paper is an adaptive weighted DRC/T algorithm that extends and optimizes the DRC/T algorithm to meet different QoS requirements of different types of applications. Each multimedia application has its own specific QoS requirements. The goals of the scheduling algorithm include satisfying various QoS requirements. The adaptive algorithm presented in this paper (also called adaptive w*DRC/T algorithm) provides various advantages over DRC The performance advantage of the /T algorithm. Using an adaptive algorithm, it meets the delay and jitter boundary requirements of delay and jitter sensitive applications on the forward link of cdma2000 1xEV-DO network. Additionally, an adaptive scheduling algorithm ensures rate requirements are met and average latency for multimedia applications is reduced. Although a multimedia application is provided as an example to illustrate the implementation of an adaptive scheduling algorithm, the methods and apparatus described herein are applicable to other applications that have QoS requirements or quantifiable requirements associated therewith.

For applications with rate and latency requirements such as web browsing and gaming, adaptive scheduling algorithms provide rate guarantees and reduce average latency. For other applications with only rate requirements, an adaptive weighted scheduling algorithm can be used to satisfy rate guarantees. While providing these QoS guarantees, the adaptive weighted scheduling algorithm also acts to maintain the aggregate throughput at a reasonably high level and achieve an aggregate throughput close to that achieved when using a pure PF scheduling algorithm. The pure PF scheduling algorithm refers to the algorithm using DRC/T calculation. While giving additional resources to processes with QoS violations, the adaptive weighted scheduling algorithm allocates available resources in a fair manner. Various compensation mechanisms consistent with this are provided herein.

Figure 4 shows a system 800 that supports multimedia applications. Note again that the invention is applicable to other systems with QoS requirements. System 800 includes a multimedia source 802 coupled to a Packet Data Serving Node (PDSN) 806 . PDSN 806 is also coupled to base station controller (BSC) 804, which may include multiple BSCs. The BSC 804 communicates with various ATs 812, 814, 816, 818, etc. via base transceiver systems (BTS) 808, 810. System 800 may include more BTSs and ATs than shown. The figure shows three flows: the first flow is from multimedia source 802 via PDSN 806, BSC 804, and BTS 808, to AT 812; the second flow is from multimedia source 802 via PDSN 806, BSC 804, and BTS 810, to AT 816; The third flow is from multimedia source 802 via PDSN 806, BSC 804, and BTS 810, to AT 818. Note that one AT can be the target of multiple processes. In one example, the transmission of a Moving Picture Experts Group (MPEG) type application separates audio and video into separate streams.

Each application flow to be transferred in system 800 has: an associated source address; destination address; and QoS requirements. The application flow is then scheduled for transfer from source to destination. Application flow follows a path similar to that shown in Figure 4.

Each BTS 808, 810 is adapted to maintain a process queue as shown in FIG. 5 . Note that each BTS maintains a set of queues corresponding to each application flow on its forward link (FL). One application process is for one AT. However, note that multiple processes can be targeted to one AT. Each process has a Quality of Service Group (QSG) type associated with it. Each QSG is defined by a set of QoS parameters. Each process in a given QSG has specific values corresponding to each parameter in the group. For example, a QSG can be defined by the group consisting of delay and jitter. Which flows with this QSG will specify the requirements for latency and jitter. For each process in the queue, the BTS maintains a group consisting of the following three separate queues: (1) Original Transmission Queue (Tx); (2) Retransmission Queue (Rx); and (3) Automatic Repeat Request Queue (ARQ) . In one embodiment, the ARQ queue may correspond to a queue that stores processes for any type of repetition mechanism performed between the BTS and the AT, such as prior decision ARQ. Multimedia applications may include delay-sensitive applications such as video conferencing with delay-bound requirements. The delay bound is the specified time allowed from AN transmission to AT reception. Adaptive weighting algorithms aim to meet delay bound requirements and reduce the average delay experienced by IP packets for such applications. For applications with both rate and average latency requirements, the adaptive weighting algorithm works to meet rate requirements and reduce average latency.

Another consideration for certain types of applications, such as multimedia video applications, is the "jitter" experienced between successive packets in a multimedia transmission. Jitter refers to the time variation between two received packets. Jitter occurs when successive waveforms arrive at the receiver slightly earlier or later. In wireless communications, such waveforms typically convey logic 1s or 0s, which are then decoded at the receiver. Temporal variations, defined as jitter, distort the visual appearance of received transmissions. The adaptive weighted scheduling algorithm reduces worst-case delay variation, as well as delay variation between successive packets for delay-sensitive applications.

While meeting the QoS requirements of individual users, the adaptive algorithm is also designed to meet the rate requirements of several application flows when those flows are "coincident". An application process is said to be "consistent" if it sends data according to a pre-specified traffic profile. If processes with rate requirements are inconsistent, ie they send more data than prespecified in their traffic profile, the algorithm gives higher priority to processes with lower data rates. Although the adaptive weighting algorithm is described herein in the context of cdma2000 1xEV-DO, the concepts and methods are applicable to other types of wireless networks as well.

In terms of multimedia application flows, each flow is defined by: (1) traffic profile; (2) QoS profile; (3) Internet Protocol (IP) source address; and (4) IP destination address. The process may also include: (5) L4 protocol type; (6) L4 port number; and (7) L4 destination port number, wherein L4 refers to the Transmission Control Protocol (TCP)/User Datagram Protocol (UDP) layer in the protocol stack . For example, MPEG audio and MPEG video corresponding to one MPEG application can be considered as two separate flows.

Each process is specified by a traffic profile and is monitored or shaped to ensure it conforms to that traffic profile. The traffic profile is defined by a variable denoted σ representing a measure of burstiness, and a process average data rate denoted r. Therefore, each process is described by a traffic profile (σ, r). The QoS profile is defined by at least one of the following parameters: (1) Delay boundary denoted "D", which defines the time allowed for an IP packet from transmission to reception. For multimedia application flows, the system can specify latency bounds. For some other application processes such as web browsing, the system can specify the average delay (AvgD) to replace or supplement the delay boundary; (2) the jitter boundary denoted as "j", which defines the time between two packets received at the AT. The maximum allowable time variation; and (3) the service rate (request rate) denoted "R" or "req_rate".

To define the delay boundary D, refer to FIG. 6, which is a timing diagram including various AN elements and an AT. Multimedia flows are transmitted from a multimedia source (not shown) to the AT via the PDSN, BSC, and BTS. An IP packet is sent from the PDSN at time _t0 and received at the AT at time _t3 . The parameter D defines the maximum allowable time from time t ₀ to time t ₃ , ie D specifies the limit for t ₃ -t ₀ .

To define the jitter boundary j, refer to FIG. 7A, which is a timing diagram including several AN elements and an AT. The first packet is sent from the PDSN at time _t1 and received at the AT at time _t1 '. The second packet is sent from the PDSN at time _t2 and received at the AT at time _t2 '. The jitter bound j defines the maximum allowable variation between two consecutive packets, where the variation is given as (t ₂ '-t ₁ ')-(t ₂ -t ₁ ). Figure 7B further details several consecutive IP packets transmitted over several time slots.

In one embodiment, QoS profiles are categorized into groups called QoS Scheduling Groups (QSGs). Table 1 lists these categories.

Table 1

index Delay Boundary (D) Jitter boundary (j) Service Rate (R) Average Delay (AvgD) Application example 1 x x x - MPEG conference, VoIP, video streaming 2 - - x x Network View 3 - - x - FTP

4 - - - - Best effort service

Fig. 8 shows the processing of the flow according to the adaptive weighted scheduling algorithm. Flows 900, 902, 904, and 906 are handled by a scheduling unit 908 labeled "S". The scheduling unit 908 applies an adaptive weighted scheduling algorithm using the QSG profile for each flow. The QSG profile identifies variables used to calculate adaptive weights as detailed below. The scheduling unit 908 then outputs a scheduled transmission 910 to the selected AT.

A PF scheduling algorithm called DRC/T algorithm is described, where packets are sorted into m queues, eg Q1, Q2, ..., Qm. Let DRC[k,n] be the DRC requested by the mobile station, corresponding to flow k of slot n. The scheduler selects the process with the highest selection metric, where:

$\mathrm{<span\; class="notranslate">\; Y</span>}<span\; class="notranslate">\; [</span>\mathrm{<span\; class="notranslate">\; k</span>}<span\; class="notranslate">\; ,</span>\mathrm{<span\; class="notranslate">\; no</span>}<span\; class="notranslate">\; +</span>\mathrm{<span\; class="notranslate">\; 1</span>}<span\; class="notranslate">\; ]</span><span\; class="notranslate">\; =</span>\mathrm{<span\; class="notranslate">\; DRC</span>}<span\; class="notranslate">\; [</span>\mathrm{<span\; class="notranslate">\; k</span>}<span\; class="notranslate">\; ,</span>\mathrm{<span\; class="notranslate">\; no</span>}<span\; class="notranslate">\; +</span>\mathrm{<span\; class="notranslate">\; 1</span>}<span\; class="notranslate">\; ]</span><span\; class="notranslate">\; /</span>{\mathrm{<span\; class="notranslate">\; T</span>}}_{\mathrm{<span\; class="notranslate">\; k</span>}}<span\; class="notranslate">\; [</span>\mathrm{<span\; class="notranslate">\; no</span>}<span\; class="notranslate">\; +</span>\mathrm{<span\; class="notranslate">\; 1</span>}<span\; class="notranslate">\; ]</span><span\; class="notranslate">\; ,</span><span\; class="notranslate">\; \&ForAll;</span>\mathrm{<span\; class="notranslate">\; k</span>}<span\; class="notranslate">\; ,</span><span\; class="notranslate">\; \&ForAll;</span>\mathrm{<span\; class="notranslate">\; no</span>}<span\; class="notranslate">\; .</span><span\; class="notranslate">\; -</span><span\; class="notranslate">\; -</span><span\; class="notranslate">\; -</span><span\; class="notranslate">\; (</span>\mathrm{<span\; class="notranslate">\; 1</span>}<span\; class="notranslate">\; )</span>$

Y[k,n+1] is the selection metric for queue Qk in slot (n+1), and

${\mathrm{<span\; class="notranslate">\; T</span>}}_{\mathrm{<span\; class="notranslate">\; k</span>}}<span\; class="notranslate">\; [</span>\mathrm{<span\; class="notranslate">\; no</span>}<span\; class="notranslate">\; +</span>\mathrm{<span\; class="notranslate">\; 1</span>}<span\; class="notranslate">\; ]</span><span\; class="notranslate">\; =</span><span\; class="notranslate">\; (</span>\mathrm{<span\; class="notranslate">\; 1</span>}<span\; class="notranslate">\; -</span>\frac{\mathrm{<span\; class="notranslate">\; 1</span>}}{{\mathrm{<span\; class="notranslate">\; t</span>}}_{\mathrm{<span\; class="notranslate">\; c</span>}}}<span\; class="notranslate">\; )</span>{\mathrm{<span\; class="notranslate">\; T</span>}}_{\mathrm{<span\; class="notranslate">\; k</span>}}<span\; class="notranslate">\; [</span>\mathrm{<span\; class="notranslate">\; no</span>}<span\; class="notranslate">\; ]</span><span\; class="notranslate">\; +</span>\frac{\mathrm{<span\; class="notranslate">\; 1</span>}}{{\mathrm{<span\; class="notranslate">\; t</span>}}_{\mathrm{<span\; class="notranslate">\; c</span>}}}\mathrm{<span\; class="notranslate">\; R</span>}<span\; class="notranslate">\; [</span>\mathrm{<span\; class="notranslate">\; k</span>}<span\; class="notranslate">\; ,</span>\mathrm{<span\; class="notranslate">\; no</span>}<span\; class="notranslate">\; ]</span><span\; class="notranslate">\; ,</span><span\; class="notranslate">\; -</span><span\; class="notranslate">\; -</span><span\; class="notranslate">\; -</span><span\; class="notranslate">\; (</span>\mathrm{<span\; class="notranslate">\; 2</span>}<span\; class="notranslate">\; )</span>$

$\frac{1}{t_c}\&le;1,$ and

0＜1/t _c (3)

As used herein, _tc is the time constant used to calculate the average.

Adaptive w*DRC/T algorithm

In one embodiment, an adaptive weighted scheduling algorithm called the "adaptive w*DRC/T" algorithm assigns an initial weight to each process. Assuming that the initial weight allocated to process k is denoted as w _k , the DRC requested by the AT corresponding to time slot n process k is DRC[k,n]. The adaptive w*DRC/T algorithm computes the following metrics for each process k at each time slot n:

Y _k [n]＝aw _k [n]*DRC _k [n]/T _k [n] (4)

Here, the throughput T _k [n] of process k and slot n is as defined for DRC/T in the PF algorithm. As used in the adaptive weighted scheduling algorithm, aw _k [n] is the adaptive weight of process k at slot n. The adaptive w*DRC/T scheduling algorithm works in several modes, where the modes are defined by the QSG. The adaptive weight aw _k [n] of process k at time slot n is calculated based on the scheduler mode and a set of selected policies or mechanisms as described below. Note that equation (4) is calculated for each process, where the adaptive weights will be calculated according to a formula specific to each process. In other words, the scheduling algorithm takes into account the QoS profile of a given flow and uses this QoS profile to construct the calculation of adaptive weights for that flow. In this way, different flows with different QoS requirements can have differently calculated adaptive weights. The scheduling algorithm next selects the flow with the largest value of _Yk [n] to serve in slot n.

The adaptive w*DRC/T scheduler works in the following modes:

Mode I[aw*DRC/T](r,d,j): Designed for delay and jitter sensitive applications with strict requirements on delay and jitter bounds and requiring a certain minimum rate.

Mode II[aw*DRC/T](r,d): For applications with average latency and rate requirements.

Mode III[aw*DRC/T](r): For applications that only specify rate requirements.

Mode IV[DRC/T]: for processes that do not specify any QoS plan but are served by the DRC/T algorithm. Based on QoS requirements, a specific mode of adaptive w*DRC/T algorithm can be used for a given flow. Mode II can also be applied to a process to increase the throughput given to that process by the scheduler. For example, Mode II can be used in FTP applications to potentially increase the throughput of the corresponding application process.

An example of a grouping application (ie, QSG) is given below:

Group I: Applications with strict requirements on delay bounds and delay variation similar to Voice over IP (VoIP). Note that such applications often also have rate requirements. Use scheduler pattern I.

Group II: Multimedia conferencing applications with strict requirements on latency bounds and latency variations. Even though some of these applications are adaptive, it is still desirable to ensure a service rate for consistent high quality. Use scheduler pattern I.

Group III: Video streaming applications with requirements on latency bounds, rate and latency variation. Use scheduler pattern I.

Group IV: Web browsing applications with rate and (average) latency requirements - use scheduler mode II.

Group V: FTP applications with rate requirements - use scheduler mode III. Alternatively, use Scheduler Mode II with a less strict latency bound.

Group VI: Best-effort applications—using PF algorithms without adaptive weighting, ie, DRC/T algorithms.

Note that database transactions, games, and other applications can also be sorted into appropriate groups based on QoS requirements, respectively.

Figure 9 illustrates an adaptive weighted scheduler having multiple levels including, but not limited to, level I and level II. A level I scheduler has a number of schedulers S1, S2, S3, ..., Sm, where m refers to the total number of groups. Each rank I scheduler in Figure 9 runs a specific mode of operation of the adaptive w*DRC/T scheduling algorithm and selects a process from this group. First, the class I scheduler computes the portion of Y, specifically the throughput T, and the rate compensation factor α. Next, the Tier II scheduler considers the individual flows and provides enough input to the Tier I scheduler to complete the computation of the selection metric Y by the Tier I scheduler. Once the computation of Y is complete for all pending processes, the Level I scheduler evaluates the Y value and selects the process with the highest Y value. Each class I scheduler evaluates a group of processes with similar QoS requirements. The flows selected by each level I scheduler are then provided to the level II scheduler for comparison with flows from other groups. A level II scheduler considers one selected process per group and chooses the process with the highest metric (aw*DRC/T) or Y value. This process is repeated for each slot when the scheduler needs to select a process to serve. Alternative embodiments may use a single level of schedulers, or may use more levels than shown in FIG. 9 . Alternative embodiments may include a different number of level I schedulers, where the level I schedulers correspond to process organizations.

In general, the calculation of the adaptive weight is given as a function of several parameters, and is given as:

a=f(Φ, γ, α, β, δ). (5)

The delay compensation function is denoted as Φ. The waiting time constant is denoted as γ. The rate compensation function is denoted as α. The DRC compensation function is denoted as β. The enhanced jitter compensation factor is denoted as δ. Note that not all parameters have actual values for all multimedia services. For example, when the only QoS requirement for a given flow is a specified data rate, then the variable α will be specified, (the rate parameter will have the actual value) and all other constants will be set equal to 1. In this case, only the rate parameter will be included in the adaptive weight calculation. In one embodiment, the adaptive weight is calculated as follows:

a＝Φ*γ*α*β*δ (6)

The operator is the multiplication sign. The following discussion provides details of various compensation terms that may be included in the adaptive weight calculation.

For Mode I applications, the QoS profile specifies all parameters indicated in equation (6). The adaptive weight calculation considers delay compensation due to delay threshold violations, delay compensation due to latency threshold violations, rate compensation due to rate violations, and enhanced jitter compensation due to enhanced jitter threshold violations. This concept increases the weight of processes that violate specified QoS requirements. Once triggered by a violation of QoS requirements, such processes are given credit points. The trust score is achieved by multiplying the weight of the process by the appropriate value of the delay compensation function. This result is also multiplied by rate compensation and enhanced jitter compensation.

Conversely, a process can be penalized when it appears to be receiving excess service. Processes can be penalized in any of a variety of ways. According to one approach, a process can be penalized directly by reducing its weight. According to another approach, a process can be penalized indirectly by maintaining the process weight while increasing the weight of other lagging (ie, those processes not meeting the required QoS) users.

There are various mechanisms for calculating latency compensation to account for latency threshold violations. Assume that the delay threshold of process k is denoted as dth_Φ _k , and the delay compensation of process k due to violation of the delay threshold in time slot n is denoted as Φ _k [n]. To calculate the delay compensation Φ _k [n], consider packets in all three queues (ie, Tx, RTx and ARQ) for each flow.

For each process, maximum and minimum thresholds are also specified for Φ to ensure that one process does not consume several consecutive slots and starve other processes of slots. This design also ensures that the process delay compensation term due to delay threshold violations is at least as good as the minimum threshold. Let Φ _thres,min,k and Φ _thres,max,k be the minimum and maximum thresholds specified for each process k. This (for all k and all n) results in:

${\mathrm{<span\; class="notranslate">\; \&phi;</span>}}_{\mathrm{<span\; class="notranslate">\; thres</span>}<span\; class="notranslate">\; ,</span>\mathrm{<span\; class="notranslate">\; min</span>}<span\; class="notranslate">\; ,</span>\mathrm{<span\; class="notranslate">\; k</span>}}<span\; class="notranslate">\; \&le;</span>{\mathrm{<span\; class="notranslate">\; \&phi;</span>}}_{\mathrm{<span\; class="notranslate">\; k</span>}}<span\; class="notranslate">\; [</span>\mathrm{<span\; class="notranslate">\; no</span>}<span\; class="notranslate">\; ]</span><span\; class="notranslate">\; \&le;</span>{\mathrm{<span\; class="notranslate">\; \&phi;</span>}}_{\mathrm{<span\; class="notranslate">\; thres</span>}<span\; class="notranslate">\; ,</span>\mathrm{<span\; class="notranslate">\; max</span>}<span\; class="notranslate">\; ,</span>\mathrm{<span\; class="notranslate">\; k</span>}}<span\; class="notranslate">\; ,</span><span\; class="notranslate">\; \&ForAll;</span>\mathrm{<span\; class="notranslate">\; k</span>}<span\; class="notranslate">\; ,</span><span\; class="notranslate">\; \&ForAll;</span>\mathrm{<span\; class="notranslate">\; no</span>}<span\; class="notranslate">\; .</span><span\; class="notranslate">\; -</span><span\; class="notranslate">\; -</span><span\; class="notranslate">\; -</span><span\; class="notranslate">\; (</span>\mathrm{<span\; class="notranslate">\; 7</span>}<span\; class="notranslate">\; )</span>$

The calculation for delay compensation will be derived using the following definitions:

D[n]: Defines the set of flows that experience a delay threshold violation at the start of slot n (i.e., each such flow has at least one packet at the start of slot n that exceeds the delay threshold for that flow).

defpkts _k [n]: Defines the "deficit" packets for flow k at the start of slot n. Deficient packets are packets that have not been transmitted in the flow, and defpkts is specifically defined as the number of equal-sized (MAC) packets whose stay time in the BTS exceeds the delay threshold of flow k.

required_rate _k : Defines the request rate for process k.

ndefpkts _k : Define the number of normalized deficit groupings of process k, specifically defined as:

${\mathrm{<span\; class="notranslate">\; ndefpkts</span>}}_{\mathrm{<span\; class="notranslate">\; k</span>}}<span\; class="notranslate">\; =</span>\frac{{\mathrm{<span\; class="notranslate">\; defpkts</span>}}_{\mathrm{<span\; class="notranslate">\; k</span>}}}{\mathrm{<span\; class="notranslate">\; required</span>}<span\; class="notranslate">\; \_</span>{\mathrm{<span\; class="notranslate">\; rate</span>}}_{\mathrm{<span\; class="notranslate">\; k</span>}}}<span\; class="notranslate">\; -</span><span\; class="notranslate">\; -</span><span\; class="notranslate">\; -</span><span\; class="notranslate">\; (</span>\mathrm{<span\; class="notranslate">\; 8</span>}<span\; class="notranslate">\; )</span>$

Note that the packets in BTS, BSC and PDSN may be of unequal size, therefore, it is beneficial to count the number of deficit bits instead of the number of packets here.

If the HOL packet of a process stays in the BTS queue for a period of time greater than a pre-specified threshold, the following mechanism can be used to compensate the process. The latency threshold used for this purpose should be greater than or equal to the threshold used for computing Φ. For process k, the waiting time threshold is denoted as dth_γ _k , where the waiting time threshold is affected by $\mathrm{dth}\_{\mathrm{\&gamma;}}_k\&Greater\; Equal;\mathrm{dth}\_{\mathrm{\&phi;}}_k,\&ForAll;k$ constraints. To select a flow's HOL packet, first consider the HOL packets from the flow's Tx, RTx and ARQ queues and choose one of them based on the waiting time at the BTS, ie choose the one that has waited the longest in the BTS. Let _γk [n] be the latency compensation of flow k at the beginning of slot n, and Sk _[ n] be the time that flow k's HOL packet stays in the BTS queue at slot n. For each process k, the minimum threshold S _thres,min,k and the maximum threshold S _thres,max,k are also specified, satisfying $S_{\mathrm{thres},\min ,k}\&le;S_k\left[\mathrm{no}\right]\&le;S_{\mathrm{thresh},\max ,k},\&ForAll;k,\&ForAll;\mathrm{no}.$

According to one embodiment, delay compensation is applied when a process experiences a delay threshold violation or a latency threshold violation. This mechanism applies DRC data rate requests to adaptive weights. Let _βk [n] be the DRC adjustment function for flow k in slot n. Specify minimum threshold β _{min, thres, k} and maximum threshold β _{max, thres, k} for each process k, satisfying β _{min, thres, k} ≤ β _k [n] ≤ β _{max, thres, k} .

Although for some applications such as video/audio conferencing, it may be desirable for the compensation mechanism described above to help reduce delay variation in the process, including more effective delay variation (jitter) control and further reduction of delay variation. The following mechanisms provide effective latency variation control by reducing the latency variation between pairs of successive packets of a process. Processes with larger IP packet sizes benefit more from this compensation mechanism.

Suppose at(k, j) is the arrival time of IP packet j of flow k at the entrance of BSC. Let dt(k, j) be the time when this IP packet leaves the BTS, ie, the time until which all fragments of this IP packet have been transmitted by the forward link scheduler at the BTS. Let pend _k,j [n] be the total length in bytes of IP packet j of flow k at BTS and BSC. Assume that dv _k,target is the target delay variation (jitter) between two successive IP packets of process k, dv _k,thres is a pre-defined enhanced jitter threshold for this process, and make dv _k,thres <dv _k,target . In one embodiment, when the delay variation between two successive IP packets exceeds dv _k,thres , the algorithm triggers an enhanced delay variation compensation mechanism for flow k.

Figure 10 provides an architectural diagram corresponding to one embodiment. Each application flow is described by a traffic profile, a QoS profile, and a DRC request (ie, request data rate). Each traffic profile includes a measure of burstiness and average data rate. Each QoS profile includes class types and parameter boundaries. A class type can be one of schema I, schema II, schema III, or schema IV. bounds specifies the bounds for latency, jitter, and the requested data rate. Some applications, such as web browsing, specify average latency instead of latency bounds. Select mode I with a delay threshold smaller than the jitter bound; for mode II, select a delay threshold less than the average delay. Select Enhanced Jitter Threshold to be smaller than Jitter Boundary. Alternative embodiments may apply more or less information to each application flow, where QoS requirements may be network and configuration specific.

Figure 11 is a table specifying QoS requirements and QoS parameters for each class type. As shown, Mode I corresponds to the strictest requirements, while Mode IV corresponds to a best-effort type that does not specify any QoS requirements. Alternative embodiments may include other QoS requirements, QoS parameters and/or modes.

12A to 12E illustrate the processing of an application flow and the scheduling of the application flow as part of an active application flow. Figure 12A shows a flowchart for initializing and setting up a single application process. The process begins at step 1100 to select a mechanism for each compensation parameter. Compensation parameters include, but are not limited to: delay (Φ); pending time (γ); DRC (β), jitter (δ), and rate (α). Thresholds are selected at step 1102 for applicable compensation parameters. Note that compensation parameters may include any parameters of the application process that are important to the AN. In step 1104 an algorithm is selected for calculating the intermediate weights used to calculate the adaptive weights used for scheduling. A scale parameter (C) and a priority factor (Z) are set at step 1106, both of which are used to calculate adaptive weights. Initial weights are set for this application flow at step 1108 . At step 1110, the QoS requirements of the application process are evaluated. If there are no QoS requirements specified other than the rates identified by the DRC requirements, default conditions apply. The default condition is "best effort" as described above. In this case, the default processing sets all compensation factors equal to 1 for this application flow. For the present embodiment, in this case the calculation of equation (6) applies a multiplicative operator, so setting factors to 1 effectively ignores those factors, ie those factors do not affect the weighting. Note that alternative embodiments may implement other mechanisms and functions, and thus adapt other mechanisms to ignore specific or all compensation factors.

Best effort processing continues at steps 1112 and 1116 . The resulting scheduling factor calculation is consistent with the proportional fair calculation. If the application flow has QoS requirements, then processing proceeds to step 1114 . Steps 1114 and 1116 indicate that processing continues in the following figures.

FIG. 12B continues the process of FIG. 12A from step 1114 onwards. Processing begins at step 1120 for the current time slot. In step 1122 the class type of the application process is determined. Mode I is processed at step 1128 , mode II is processed at step 1126 , and mode III is processed at step 1124 . Mode I QoS parameters are monitored at step 1128; Mode III QoS parameters are monitored at step 1124. A check for QoS violations is then performed at steps 1130, 1140 and 1150, which are further detailed in Figures 12C and 12D.

For Mode I, II or III applications, processing of the application flow continues at step 1130 of FIG. 12C. At step 1132, the algorithm periodically monitors for rate violations. Note that rate compensation calculations are performed periodically and used in subsequent time slots. If a rate violation is detected at step 1134, then processing proceeds to step 1138 to calculate the rate compensation factor (α). Otherwise, the rate compensation factor (α) is set equal to one at step 1136 . Processing then proceeds to step 1160, which is further detailed in Figure 12E.

For Mode I or II applications, processing of the application flow continues at step 1140 of FIG. 12C. At step 1142 the method monitors for delay and jitter violations at each time slot. If a delay and/or jitter violation is detected at step 1144, then processing proceeds to 1148 to calculate a delay compensation factor (Φ) according to the mechanism selected at initialization. For Mode I flows with enhanced shake compensation requested, then the enhanced shake compensation factor (δ) is also calculated. δ is set to 1 for Mode I procedures without requested enhanced jitter compensation and for Mode II procedures. Otherwise, the delay compensation factor (Φ) is set equal to 1 and δ is set equal to 1 at step 1146 . Processing then proceeds to step 1160, which is further detailed in FIG. 12E. Note that violation checking can be done in tandem or in parallel for Mode I or Mode II application flow. In other words, the rate violation and delay/jitter violation checks can be performed sequentially in time or in parallel.

For Mode I applications, processing of the application flow continues at step 1150 of Figure 12D. At step 1152 the method monitors for latency violations. If a latency violation is detected at step 1154, then processing proceeds to step 1158 to calculate a latency compensation factor (γ) according to the mechanism selected at initialization. Otherwise, the latency compensation factor (γ) is set equal to one at step 1156 . Processing then proceeds to step 1160, which is further detailed in FIG. 12E. Note that for Mode I application flow, violation checking can be done in tandem or in parallel. In other words, checking for rate violations, delay/jitter violations, and latency violations may be done sequentially in time or in parallel, as shown in steps 1170 and 1172 .

FIG. 12E shows the processing from steps 1160 and 1116. In step 1162, an adaptive weight is calculated for the application process according to the QoS parameters and compensation factors, given as:

aw=f(Φ, γ, α, β, δ) (9)

In step 1164, the scheduling factor or scheduling metric is calculated as follows:

Scheduling factor = aw*(DRC)/T (10)

In step 1166, the scheduling algorithm then schedules the application process according to the calculated scheduling factor for each active application process.

Figure 13 illustrates a BTS 1200 suitable for applying a scheduling algorithm, according to one embodiment. BTS 1200 includes a scheduling unit 1202, an application process processor unit 1206, a QoS parameter estimation unit 1204, an adaptive weight calculation unit 1212, and a CPU 1208, each coupled to a communication bus 1210. The scheduling unit 1202 performs scheduling by preparing scheduling factors for each application process, and then selecting among valid application processes according to these scheduling factors. The policies and goals of a given system are incorporated into the scheduling algorithm. QoS parameter estimation 1204 monitors for QoS violations and provides information to scheduling unit 1202 and weight calculation unit 1212 . The application flow process performs processing including, but not limited to, directing packets to the target AT, receiving QoS information from the target AT for scheduling, and providing this information to QoS parameter estimates 1204 . BTS 1200 also includes memory 1214 for storing intermediate information, and maintaining data for calculating averages, process queues, and the like. Violation checks are performed at the BTS. One embodiment keeps count of the number of bytes emitted for each flow and uses this information for rate violation checks. When each packet arrives at the BSC, it is time stamped. The time continues to increment as long as the packet remains at the AN, BSC or BTS. The BTS uses this time to detect threshold violations and then calculates delay, latency or enhanced jitter compensation functions depending on the process.

access control

Admission control refers to the decision-making process in the admission of users requesting data services. When a new user requests a data service such as an application with QoS requirements, the AN determines whether there are resources available to support the usage. The admission process takes into account the requested application, current usage, and QoS and network statistics. If the AN determines that the new user can be supported, then the corresponding application flow is allowed. Otherwise, if no resources are currently available, the application process is rejected or placed in a queue to wait for a change of state. Note that the new user may actually have a currently active application process requesting an additional service, ie an additional application process.

In addition to, and as part of, admission control, a preemptive process for terminating active application flow can be implemented, where current operating conditions are evaluated to make preemptive decisions. In this case, each current flow is evaluated for QoS violation as well as data rate.

This section presents an adaptive per-sector admission control algorithm. The admission control algorithm decides whether to admit (or preempt) a flow in a given wireless multimedia network. It may thus be possible to determine the allowable number of flows (of each class) in a given network. Several embodiments of the admission control algorithm presented herein include mechanisms to perform both inter-user and intra-user QoS monitoring, and then apply this information to admission and/or preemption decisions. These embodiments are designed to ensure that per-flow and per-user QoS requirements are met for admitted flows and users. These mechanisms help coordinate the admission control algorithm and the hierarchical scheduling algorithm.

Scheduling and admission control are part of forward link (FL) QoS management in wireless networks, where such management is a complex problem. QoS management is an important consideration in the design and operation of communication networks. Application processes are classified according to criteria such as defined by the system. In one embodiment, classification is based on QoS requirements. First, admission control determines the number of processes that can be admitted under the current operating conditions. The number of processes is then divided into the number of processes per class. The system then operates to meet the QoS requirements of each admitted flow. Note that the number of processes can change dynamically over time and with the type of application. For example, at a first time, the access network (AN) may support a first scenario where a specific number of flows are granted for each type of application. At a second time, the AN may support a second scenario that allows a different number of flows for at least one of the types of applications.

The scheduler (ie, scheduling algorithm) implements a fairness policy among the allowed flows. The scheduler also attempts to properly recover processes with QoS violations. The operator's income and benefits depend on the effectiveness of the scheduling algorithm used. More efficient and feature-rich algorithms offer opportunities to increase these benefits.

As far as admission control is concerned, one embodiment implements a subscription based approach. Note that subscription-based methods are often used in admission control algorithms for wired networks. In a wireless network, the channel conditions for each user are constantly changing, and thus the forward link capacity as seen by the BTS scheduler is also constantly changing. Algorithms based on wired subscription factors assume a fixed link capacity and are therefore not directly applicable to wireless networks.

For wireless networks, one embodiment provides an Adaptive Subscription Factor Base (ASF) admission control algorithm for FL management, where the network supports multiple application flows with QoS requirements. ASF admission control in wireless networks dynamically updates subscription factors by monitoring QoS statistics and network statistics. Various mechanisms may be used to perform the update function. Corrective action can thus be taken using adaptive booking factors. In addition, ASF is also used to implement preemptive methods.

Compute the ASF at each time t, AS(t). This process determines the minimum threshold AS _{min_prespecified} , and the maximum threshold AS _{max_prespecified} for AS(t) such that $1\&le;{\mathrm{AS}}_{\min \_\mathrm{prescribed}}\&le;\mathrm{AS}\left(t\right)\&le;{\mathrm{AS}}_{\max \_\mathrm{prescribed}}<\&infin;,\&ForAll;t.$ Initially, the ASF is assigned the value S _initial such that AS(0)=S _initial .

Figure 14 is a timing diagram plotting maximum data rate, reserved bandwidth, and available bandwidth as a function of time. The maximum rate at which a BTS can transmit data on the forward link (L _max ) provides an upper bound on resource allocation. Evaluate the active application flow to determine the reserved bandwidth Res(t). The calculation of the adaptive reservation factor and the estimation of the forward link capacity L(t) desired to be reserved at time t are performed using the statistics related to the QoS violation and the network load. Note that it is possible that L(t) ≤ Res(t). For example, assume that the allowed processes experience very good channel conditions when they are admitted. Now, the channel conditions for several flows deteriorate and some flows do not achieve the associated QoS guarantees. In this case, the system may wish to be more conservative in allowing more flows, and set Avail(t)=0. On the other hand, if L(t)>Res(t), the system can set Avail(t)=L(t)-Res(t). The value L(t) is based on previous QoS violations and network load-related statistics, and estimates the forward link capacity that is expected to be reserved at time t, and is calculated according to _Lmax and ASF, as follows:

$\mathrm{<span\; class="notranslate">\; L</span>}<span\; class="notranslate">\; (</span>\mathrm{<span\; class="notranslate">\; t</span>}<span\; class="notranslate">\; )</span><span\; class="notranslate">\; =</span>\frac{{\mathrm{<span\; class="notranslate">\; L</span>}}_{\mathrm{<span\; class="notranslate">\; max</span>}}}{\mathrm{<span\; class="notranslate">\; AS</span>}<span\; class="notranslate">\; (</span>\mathrm{<span\; class="notranslate">\; t</span>}<span\; class="notranslate">\; )</span>}<span\; class="notranslate">\; ,</span><span\; class="notranslate">\; \&ForAll;</span>\mathrm{<span\; class="notranslate">\; t</span>}<span\; class="notranslate">\; ,</span><span\; class="notranslate">\; -</span><span\; class="notranslate">\; -</span><span\; class="notranslate">\; -</span><span\; class="notranslate">\; (</span>\mathrm{<span\; class="notranslate">\; 11</span>}<span\; class="notranslate">\; )</span>$

Its constraints are:

$L\left(t\right)\&le;\frac{L_{\max }}{{\mathrm{AS}}_{\min \_\mathrm{prescribed}}}<L_{\max }$ and (12)

$\mathrm{<span\; class="notranslate">\; L</span>}<span\; class="notranslate">\; (</span>\mathrm{<span\; class="notranslate">\; t</span>}<span\; class="notranslate">\; )</span><span\; class="notranslate">\; \&Greater\; Equal;</span>\frac{{\mathrm{<span\; class="notranslate">\; L</span>}}_{\mathrm{<span\; class="notranslate">\; max</span>}}}{{\mathrm{<span\; class="notranslate">\; AS</span>}}_{\mathrm{<span\; class="notranslate">\; max</span>}<span\; class="notranslate">\; \_</span>\mathrm{<span\; class="notranslate">\; prescribed</span>}}}<span\; class="notranslate">\; ></span>\mathrm{<span\; class="notranslate">\; 0</span>}<span\; class="notranslate">\; .</span><span\; class="notranslate">\; -</span><span\; class="notranslate">\; -</span><span\; class="notranslate">\; -</span><span\; class="notranslate">\; (</span>\mathrm{<span\; class="notranslate">\; 13</span>}<span\; class="notranslate">\; )</span>$

The available bandwidth Avail(t) is calculated as follows:

Avail(t)＝maximum(L(t)-Res(t), 0) (14)

Metrics for various resources as shown in FIG. 14 are determined by data rate control (DRC) data requests received from users. Each user sends a DRC data request on the backward link. In cdma2000 1xEV-DO or other HRPD type systems, users send DRC data requests on each time slot transmitted by RL. As shown in Figure 15, the data request from User 1 (DRC1) and the data request from User 2 (DRC2) change over time. These data requests and the required QoS determine the reserved bandwidth (Res). Note that the relationship between the DRC value and Res is provided as an example. Alternative embodiments and situations may result in different relationships.

Each application process has a specified traffic profile in terms of average rate and burstiness, where the traffic profile of process f _k is given by (σ _k , r _k ). Here, r _k is the average request rate of flow f _k and σ _k is a measure of burstiness, where the requested rate of flow f _k is given as req_rate(f _k ) = r _k .

According to one embodiment, the admission control evaluates the flow f _k on admission. Admission control first applies the observed DRC corresponding to the flow f _k for the user, u(f _k ), to satisfy the requested rate, where the observed DRC is less than or equal to the average DRC data requirement for that user, as follows :

req_rate(f _k )≦Avg(DRC(u(f _k ))). (15)

Immediately carry out ASF calculation AS(t), and use it to calculate Avail(t) according to the following formula:

$\mathrm{<span\; class="notranslate">\; Avail</span>}<span\; class="notranslate">\; (</span>\mathrm{<span\; class="notranslate">\; t</span>}<span\; class="notranslate">\; )</span><span\; class="notranslate">\; =</span>\mathrm{<span\; class="notranslate">\; max</span>}\mathrm{<span\; class="notranslate">\; imum</span>}<span\; class="notranslate">\; (</span>\frac{{\mathrm{<span\; class="notranslate">\; L</span>}}_{\mathrm{<span\; class="notranslate">\; max</span>}}}{\mathrm{<span\; class="notranslate">\; AS</span>}<span\; class="notranslate">\; (</span>\mathrm{<span\; class="notranslate">\; t</span>}<span\; class="notranslate">\; )</span>}<span\; class="notranslate">\; -</span>\mathrm{<span\; class="notranslate">\; Res</span>}<span\; class="notranslate">\; (</span>\mathrm{<span\; class="notranslate">\; t</span>}<span\; class="notranslate">\; )</span><span\; class="notranslate">\; ,</span>\mathrm{<span\; class="notranslate">\; 0</span>}<span\; class="notranslate">\; )</span><span\; class="notranslate">\; -</span><span\; class="notranslate">\; -</span><span\; class="notranslate">\; -</span><span\; class="notranslate">\; (</span>\mathrm{<span\; class="notranslate">\; 16</span>}<span\; class="notranslate">\; )</span>$

Finally, the admission decision for flow f _k is considered at time t:

req_rate(f _k )≦Avail(t). (17)

If the flow f _k is allowed to enter, the resource metric as shown in Figure 14 is updated as follows:

Res(t)=Res(t)+req_rate(f _k ) 18)

Avail(t)=Avail(t)-req_rate(f _k ) (19)

AN continues to monitor QoS statistics for all incoming flows and monitors network-related statistics. Monitoring provides feedback for adapting booking factors.

An adaptive approach to AS(t): per-sector QoS and network statistics

18A through 18E provide a flowchart of a method 300 of admission control for a system supporting multiple application processes with QoS requirements. In FIG. 18A , when a request for a new flow is received at decision diamond 302AN, an admission control procedure is applied at step 304 . Otherwise, the process waits for new process requests. Note that during this time, the AN continues to monitor the current operating conditions for QoS statistics for currently active flows and network statistics for flows. The admission control program determines whether resources are available to support the new process. Resource metrics such as those shown in FIG. 14 are updated at step 305 . If at decision diamond 306 a new flow is admitted, then processing proceeds to 307 to apply the adaptive scheduling process.

The admission control procedure of step 304 is further detailed in FIG. 18B. At decision diamond 308, if the request rate for flow _fk is greater than the average DRC data requirement for flow _fk , then processing proceeds to step 312 to deny entry for flow _fk . Otherwise, processing returns to decision diamond 312 to determine whether the request rate of flow _fk is greater than the available resource Avail at time t. If the requested rate is less than Avail, then at step 314 the flow is admitted, otherwise at step 312 the flow is denied.

The updating of the resource metrics at step 305 is further detailed in Figure 18C. In step 320, resource metrics Avail and Res are updated. In step 322 the QoS statistics are updated and monitored. At step 324 the ASF is updated based on the results of steps 320 and 322 . At step 326, the estimated resource level L is recalculated. If a new flow is requested at step 328, then processing returns to processing at step 304 of FIG. 18A. If at step 328 no new flow is requested, then at step 330 for each user the presence of the user in that sector is determined. At step 332 a sampling duration is determined.

Continuing with the discussion of FIG. 18D , at step 340 QSG parameters are selected for each flow. Consider two parallel processing paths, where the first path handles rate violations at step 342 over rate sample intervals. Note that the rate sampling interval is greater than the sampling duration calculated at step 332 . The second path specifies the processing of each active flow. For a given flow, the process determines at step 344 the rate of IP packets with delay violations during the sample duration. In step 346, the ratio of IP packets with jitter violations during the sampling duration is calculated for the flow under consideration. The fraction of time slots used by the process during the sample duration is then calculated at step 348 . In step 350 the process determines the fraction of timeslots to give to flows with QoS requirements during the sample duration. At step 352, the process checks for QoS violations and at step 354 determines the QoS packet ID.

Processing proceeds to Figure 18E, step 360 calculates the number of flows for each QoS packet. The process then calculates a score for the QoS flow corresponding to each QoS statistic at step 362 . The results of steps 360 and 362 are then compared at step 364 to a predetermined threshold. Note that thresholds can be dynamically updated during operation. In step 366 the ASF is adjusted accordingly.

Figures 18A through 18E provide one embodiment of an access control method. Additional details of the admission control method are discussed below. AN elements such as BTS collect per-sector statistics for each process and use this information for per-sector admission control and preemption algorithms. Statistics for each sector are collected only during the period that the user corresponding to the process is in that partition. The BTS periodically collects QoS and network-related statistics. Let T be the period of time before this information is collected, where Z is the sample index, t=Z*T.

Consider a flow _fk in sector s, where u( _fk ) is the user corresponding to flow _fk . The user enters sector s at time t _enter . Inside the sector s, resources are reserved for this process for the duration [t _reserve (f _k , s), t _free (f _k , s)], where the resources are reserved at time t _reserve . Resources are reserved when users request application services. User u(f _k ) enters sector s for the jth time at t _{enter, j} (f _k , s) within the above duration, and leaves for the jth time at t _{leave, j} (f _k , s). Therefore, t _reserve (f _k , s)≤t _{enter, first} (f _k , s) and t _free (f _k , s)≥t _{leave, last} (f _k , s). Note that, in anticipation that the user may move to this sector at some future point in time, it is possible for the AN to be informed via the QoS signaling protocol to reserve resources for the process. Here, t _{enter, first} (f _k , s) is the time when user u(f _k ) enters this sector s for the first time, and t _{leave, last} (f _k , s) is the lifetime of process f _k During the last time this user left sector s.

The algorithm takes QoS and network-related performance statistics into consideration at time t only if the following three conditions are met at time t:

t _reserve (f _k , s)≤t≤t _free (f _k , s) (20)

t _{enter_latest} (f _k , s)+δ(f _k )≤t≤t _{leave_latest} (f _k , s), and (21)

IN_IP_PKTS(f _k , t, s)>θ(f _k ) (22)

where δ(f _k ) and θ(f _k ) are pre-specified for process f _k , IN_IP_PKTS(f _k , t, s) is in sector s at time period (max(tT, t _{enter_latest} (f _k , s)), the number of input IP packets of the flow f _k scheduled by the BTS forward link scheduler for transmission during t). If the last bit of an IP packet is transmitted in sector s, that bit is counted in the IN_IP_PKTS for that sector. The variable δ(f _k ) refers to the time before occurrences in this sector are considered significant. In other words, once the user stays in sector s for δ seconds, the process begins to value resources. Note that once permitted, the user does not need to request re-permission to leave and re-enter the sector immediately.

QoS and network statistics are then used to evaluate admission criteria for each process requesting application services. During the time period (max(tT, t _{enter_latest} (f _k , s)), t), the delayed IP packet corresponding to flow f _k in sector s is calculated as follows:

$\mathrm{<span\; class="notranslate">\; Frac</span>}<span\; class="notranslate">\; \_</span>\mathrm{<span\; class="notranslate">\; delayed</span>}<span\; class="notranslate">\; \_</span>\mathrm{<span\; class="notranslate">\; IP</span>}<span\; class="notranslate">\; \_</span>\mathrm{<span\; class="notranslate">\; Pkts</span>}<span\; class="notranslate">\; (</span>{\mathrm{<span\; class="notranslate">\; f</span>}}_{\mathrm{<span\; class="notranslate">\; k</span>}}<span\; class="notranslate">\; ,</span>\mathrm{<span\; class="notranslate">\; t</span>}<span\; class="notranslate">\; ,</span>\mathrm{<span\; class="notranslate">\; the\; s</span>}<span\; class="notranslate">\; )</span>$

$<span\; class="notranslate">\; =</span>\frac{\mathrm{<span\; class="notranslate">\; DELAYED</span>}<span\; class="notranslate">\; \_</span>\mathrm{<span\; class="notranslate">\; IP</span>}<span\; class="notranslate">\; \_</span>\mathrm{<span\; class="notranslate">\; PKTS</span>}<span\; class="notranslate">\; (</span>{\mathrm{<span\; class="notranslate">\; f</span>}}_{\mathrm{<span\; class="notranslate">\; k</span>}}<span\; class="notranslate">\; ,</span>\mathrm{<span\; class="notranslate">\; t</span>}<span\; class="notranslate">\; ,</span>\mathrm{<span\; class="notranslate">\; the\; s</span>}<span\; class="notranslate">\; )</span>}{\mathrm{<span\; class="notranslate">\; IN</span>}<span\; class="notranslate">\; \_</span>\mathrm{<span\; class="notranslate">\; IP</span>}<span\; class="notranslate">\; \_</span>\mathrm{<span\; class="notranslate">\; PKTS</span>}<span\; class="notranslate">\; (</span>{\mathrm{<span\; class="notranslate">\; f</span>}}_{\mathrm{<span\; class="notranslate">\; k</span>}}<span\; class="notranslate">\; ,</span>\mathrm{<span\; class="notranslate">\; t</span>}<span\; class="notranslate">\; ,</span>\mathrm{<span\; class="notranslate">\; the\; s</span>}<span\; class="notranslate">\; )</span>}<span\; class="notranslate">\; -</span><span\; class="notranslate">\; -</span><span\; class="notranslate">\; -</span><span\; class="notranslate">\; (</span>\mathrm{<span\; class="notranslate">\; twenty\; three</span>}<span\; class="notranslate">\; )</span>$

Where DELAYED_IP_PKTS(f _k , t, s) corresponds to the number of IP packets delayed beyond the delay boundary corresponding to flow f _k at the BTS of sector s until time t. Once a delay violation of an IP packet is detected in sector s, the count of delay violations for that sector is incremented. The fraction of IP packet pairs with jitter boundary violations for flow f _k up to time t is calculated as:

$\mathrm{<span\; class="notranslate">\; Frac</span>}<span\; class="notranslate">\; \_</span>\mathrm{<span\; class="notranslate">\; jitter</span>}<span\; class="notranslate">\; \_</span>\mathrm{<span\; class="notranslate">\; viol</span>}<span\; class="notranslate">\; (</span>{\mathrm{<span\; class="notranslate">\; f</span>}}_{\mathrm{<span\; class="notranslate">\; k</span>}}<span\; class="notranslate">\; ,</span>\mathrm{<span\; class="notranslate">\; t</span>}<span\; class="notranslate">\; ,</span>\mathrm{<span\; class="notranslate">\; the\; s</span>}<span\; class="notranslate">\; )</span><span\; class="notranslate">\; =</span>\frac{\mathrm{<span\; class="notranslate">\; JIR</span>}<span\; class="notranslate">\; \_</span>\mathrm{<span\; class="notranslate">\; VIOL</span>}<span\; class="notranslate">\; \_</span>\mathrm{<span\; class="notranslate">\; PKT</span>}<span\; class="notranslate">\; \_</span>\mathrm{<span\; class="notranslate">\; PAIRS</span>}<span\; class="notranslate">\; (</span>{\mathrm{<span\; class="notranslate">\; f</span>}}_{\mathrm{<span\; class="notranslate">\; k</span>}}<span\; class="notranslate">\; ,</span>\mathrm{<span\; class="notranslate">\; t</span>}<span\; class="notranslate">\; ,</span>\mathrm{<span\; class="notranslate">\; the\; s</span>}<span\; class="notranslate">\; )</span>}{\mathrm{<span\; class="notranslate">\; IN</span>}<span\; class="notranslate">\; \_</span>\mathrm{<span\; class="notranslate">\; IP</span>}<span\; class="notranslate">\; \_</span>\mathrm{<span\; class="notranslate">\; PKTS</span>}<span\; class="notranslate">\; (</span>{\mathrm{<span\; class="notranslate">\; f</span>}}_{\mathrm{<span\; class="notranslate">\; k</span>}}<span\; class="notranslate">\; ,</span>\mathrm{<span\; class="notranslate">\; t</span>}<span\; class="notranslate">\; ,</span>\mathrm{<span\; class="notranslate">\; the\; s</span>}<span\; class="notranslate">\; )</span><span\; class="notranslate">\; -</span>\mathrm{<span\; class="notranslate">\; 1</span>}}<span\; class="notranslate">\; ,</span><span\; class="notranslate">\; -</span><span\; class="notranslate">\; -</span><span\; class="notranslate">\; -</span><span\; class="notranslate">\; (</span>\mathrm{<span\; class="notranslate">\; twenty\; four</span>}<span\; class="notranslate">\; )</span>$

where JTR_VIOL_PKT_PAIRS(f _k , t, s) corresponds to the number of IP packet pairs (of consecutive IP packets) for which flow f _k has a jitter boundary violation up to time slot t. This count is done for a sector when two consecutive IP packets of a flow are transmitted on the sector.

The rate violation of flow f _k during time period (t _{enter_latest} (f _k , s), t),

$\mathrm{<span\; class="notranslate">\; Rate</span>}<span\; class="notranslate">\; \_</span>\mathrm{<span\; class="notranslate">\; viol</span>}<span\; class="notranslate">\; (</span>{\mathrm{<span\; class="notranslate">\; f</span>}}_{\mathrm{<span\; class="notranslate">\; k</span>}}<span\; class="notranslate">\; ,</span>\mathrm{<span\; class="notranslate">\; t</span>}<span\; class="notranslate">\; ,</span>\mathrm{<span\; class="notranslate">\; the\; s</span>}<span\; class="notranslate">\; )</span><span\; class="notranslate">\; =</span>\frac{\mathrm{<span\; class="notranslate">\; req</span>}<span\; class="notranslate">\; \_</span>\mathrm{<span\; class="notranslate">\; rate</span>}<span\; class="notranslate">\; (</span>{\mathrm{<span\; class="notranslate">\; f</span>}}_{\mathrm{<span\; class="notranslate">\; k</span>}}<span\; class="notranslate">\; )</span><span\; class="notranslate">\; -</span>\mathrm{<span\; class="notranslate">\; served</span>}<span\; class="notranslate">\; \_</span>\mathrm{<span\; class="notranslate">\; rate</span>}<span\; class="notranslate">\; (</span>{\mathrm{<span\; class="notranslate">\; f</span>}}_{\mathrm{<span\; class="notranslate">\; k</span>}}<span\; class="notranslate">\; ,</span>\mathrm{<span\; class="notranslate">\; t</span>}<span\; class="notranslate">\; ,</span>\mathrm{<span\; class="notranslate">\; the\; s</span>}<span\; class="notranslate">\; )</span>}{\mathrm{<span\; class="notranslate">\; req</span>}<span\; class="notranslate">\; \_</span>\mathrm{<span\; class="notranslate">\; rate</span>}<span\; class="notranslate">\; (</span>{\mathrm{<span\; class="notranslate">\; f</span>}}_{\mathrm{<span\; class="notranslate">\; k</span>}}<span\; class="notranslate">\; )</span>}<span\; class="notranslate">\; -</span><span\; class="notranslate">\; -</span><span\; class="notranslate">\; -</span><span\; class="notranslate">\; (</span>\mathrm{<span\; class="notranslate">\; 25</span>}<span\; class="notranslate">\; )</span>$

where req_rate(f _k )>served_rate(f _k , t, s). Otherwise compute served_rate ₍ f k , t, s) of process f _k in sector s during time (t _{enter_latest} (f _k , s), t) when process f _k has no rate violation at time t.

Note that for rate violations the procedure applies the time period (t _{enter_latest} (f _k , s), t) as the sample duration, but for delay and jitter violations the procedure applies the time period (max(tT, t _{enter_latest} (f _k , s)), t) are applied as sampling duration.

The fraction of slots used by process f _k during time period (max(tT, t _{enter_latest} (f _k , s)), t) is calculated as follows:

$\mathrm{<span\; class="notranslate">\; Frac</span>}<span\; class="notranslate">\; \_</span>\mathrm{<span\; class="notranslate">\; slots</span>}<span\; class="notranslate">\; \_</span>\mathrm{<span\; class="notranslate">\; flow</span>}<span\; class="notranslate">\; (</span>{\mathrm{<span\; class="notranslate">\; f</span>}}_{\mathrm{<span\; class="notranslate">\; k</span>}}<span\; class="notranslate">\; ,</span>\mathrm{<span\; class="notranslate">\; t</span>}<span\; class="notranslate">\; ,</span>\mathrm{<span\; class="notranslate">\; the\; s</span>}<span\; class="notranslate">\; )</span><span\; class="notranslate">\; =</span>\frac{\mathrm{<span\; class="notranslate">\; SERVED</span>}<span\; class="notranslate">\; \_</span>\mathrm{<span\; class="notranslate">\; SLOTS</span>}<span\; class="notranslate">\; (</span>{\mathrm{<span\; class="notranslate">\; f</span>}}_{\mathrm{<span\; class="notranslate">\; k</span>}}<span\; class="notranslate">\; ,</span>\mathrm{<span\; class="notranslate">\; t</span>}<span\; class="notranslate">\; ,</span>\mathrm{<span\; class="notranslate">\; the\; s</span>}<span\; class="notranslate">\; )</span>}{\mathrm{<span\; class="notranslate">\; IN</span>}<span\; class="notranslate">\; \_</span>\mathrm{<span\; class="notranslate">\; SECTOR</span>}<span\; class="notranslate">\; (</span>{\mathrm{<span\; class="notranslate">\; f</span>}}_{\mathrm{<span\; class="notranslate">\; k</span>}}<span\; class="notranslate">\; ,</span>\mathrm{<span\; class="notranslate">\; t</span>}<span\; class="notranslate">\; ,</span>\mathrm{<span\; class="notranslate">\; the\; s</span>}<span\; class="notranslate">\; )</span>}<span\; class="notranslate">\; -</span><span\; class="notranslate">\; -</span><span\; class="notranslate">\; -</span><span\; class="notranslate">\; (</span>\mathrm{<span\; class="notranslate">\; 26</span>}<span\; class="notranslate">\; )</span>$

where SERVEL_SLOTS(f _k , t, s) is the number of slots in which process f _k is served during the time period defined by (max(tT, t _{enter_latest} (f _k , s)), t), IN_SECTOR(f _k , t, s) is the total number of slots during (max(tT, t _{enter_latest} (f _k , s)), t). The fraction of timeslots given to processes with QoS requirements in sector s during the time period (tT, t) is given by:

Dynamic Process Classification

For each flow f _k , the following four thresholds are pre-specified and used to perform QoS and channel condition related checks for each flow:

Frac_delayed_IP_pkts_thres(f _k ), (fraction delayed IP packet threshold(f _k ))

Frac_jitter_viol_IP_pkts_thres(f _k ), (fraction jitter violation IP packet threshold(f _k ))

rate_viol_thres(f _k ), (rate violation threshold(f _k )) and

Frac_slots_viol_thes(f _k ), (fraction slot violation threshold(f _k )).

The system periodically adapts the ASF after every time T, where T is a pre-specified value. At a given time t when the adaptive check is performed for the Zth time (i.e., t=Z*T), the process considers those flows in sector s that have some resource reserved, i.e., satisfying t _reverse (f _k , s )≤t≤t _free (f _k , s) process. For each flow f _k from this set of flows, checks are made to evaluate the following "per-flow threshold checks":

Frac_delayed_IP_Pkts(f _k , t, s) > Frac_delayed_IP_pkts_thres(f _k ) (28)

(Fractionally Delayed IP Packet (f _k , t, s) > Fractionally Delayed IP Packet Threshold (f _k ))

Frac_jitter_viol_IP_pkts(f _k )>Frac_jitter_viol_IP_pkts_thres(f _k , t, s) (29)

(Fractional Jitter Violation of IP Packet (f _k ) > Fractional Jitter Violation of IP Packet Threshold (f _k , t, s))

Rate_viol(f _k , t, s) > rate_viok_thres(f _k ) (30)

(rate violation (f _k , t, s) > rate violation threshold (f _k ))

Frac_slots_flow(f _k , t, s) > Frac_slots_viol_thes(f _k ) (31)

(fractional slot flow (f _k , t, s) > fractional slot violation threshold (f _k ))

The above four checks are performed on the process f _k if the following two conditions are met:

t _{enter_latest} (f _k , s)+δ(f _k )≤t≤t _{leave_latest} (f _k , s), and (32)

IN_IP_PKTS(f _k , t, s)>θ((f _k )) (33)

When at least one of the conditions (32) and (33) is not satisfied for a process, but t _reserve (f _k , s)≤t≤t _free (f _k , s) is true, each The result of the process's threshold check is marked as NA.

This procedure calculates the fraction of slots used by flows with QoS requirements during the sampling duration, and also calculates the threshold value of this fraction, where Frac_slot_thres_qos_flows(s) is the number of slots allocated to flows with QoS requirements during time period T in sector s The upper threshold of the fraction of slots for the process. The value of Frac_slot_thres_qos_flows(s) is used to check whether the following formula holds true:

frac_slots_qos_flows(t, s)>Frac_slots_thres_qos_flows(s). (34)

This process classifies the current flow into one of the following QoS Scheduling Groups (QSG):

QSG I or Q_DJR: Processes with latency, jitter and rate requirements,

QSG II or Q_RavgD: processes with rate and average latency requirements,

QSG III or Q_R: Processes with rate requirements.

Consider a set of processes belonging to class Q_DJR. If a given flow f _k is ineligible for the NA category and either:

Frac_delayed_IP_Pkts(f _k , t, s) > Frac_delayed_IP_pkts_thres(f _k ), (35)

or meet

Frac_jitter_viol_IP_pkts(f _k , t, s) > Frac_jitter_viol_IP pkts_thres(f _k ), (36)

This flow is specified as having delay_or_jitter_viol(f _k , t, s) = Y (delay or jitter violation (f _k , t, s) = Yes). Otherwise, the procedure sets delay_or_jitter_viol(f _k , t, s) = N (delay or jitter violation (f _k , t, s) = No) for this flow. On the other hand, if qualified in the NA category, then delay_or_jitter_viol(f _k , t, s)=NA.

Table 2

QoS state group ID (QS_GID) QoS class delay_or_jitter_viol(f_k, t, s) rate_viol(f_k,t,s)>rate_viol_thres(f_k) 1 For the Q_DJR process yes yes 2 For the Q_DJR process yes no 3 For Q_DJR, Q_RavgD, Q_R process no yes 4 For Q_DJR, Q_RavgD, Q_R process No (or NA) No (or NA)

At each time t, the process classifies QoS flows (ie, flows with QoS requirements) as shown in Table 2 when performing adaptive inspection of AS(t). Each flow is assigned a QoS state group ID (QS_GID).

QS_GID=1: Q_DJR-like flow with rate and delay (or jitter) violations.

QS_GID=2: Q_DJR-like flows with delay (or jitter) violations but no rate violations.

QS_GID=3: Flows of the Q_DJR class without delay and jitter violations, but with rate violations.

This situation can arise for adaptive applications. Also, flows corresponding to Q_R and Q_RavgD classes with rate violations are assigned to this group.

QS_GID=4: Flows without QoS (rate, delay and jitter) violations. Processes in the NA category as described above are also placed in this group.

Adaptation of booking factors

Let N _k (t, s) be the number of processes corresponding to QSG k at time t, and N(t, s) be the total number of processes that have some resources reserved in sector s at time t.

$\mathrm{<span\; class="notranslate">\; N</span>}<span\; class="notranslate">\; (</span>\mathrm{<span\; class="notranslate">\; t</span>}<span\; class="notranslate">\; ,</span>\mathrm{<span\; class="notranslate">\; the\; s</span>}<span\; class="notranslate">\; )</span><span\; class="notranslate">\; =</span>\underset{\mathrm{<span\; class="notranslate">\; k</span>}}{\mathrm{<span\; class="notranslate">\; \&Sigma;</span>}}{\mathrm{<span\; class="notranslate">\; N</span>}}_{\mathrm{<span\; class="notranslate">\; k</span>}}<span\; class="notranslate">\; (</span>\mathrm{<span\; class="notranslate">\; t</span>}<span\; class="notranslate">\; ,</span>\mathrm{<span\; class="notranslate">\; the\; s</span>}<span\; class="notranslate">\; )</span><span\; class="notranslate">\; -</span><span\; class="notranslate">\; -</span><span\; class="notranslate">\; -</span><span\; class="notranslate">\; (</span>\mathrm{<span\; class="notranslate">\; 37</span>}<span\; class="notranslate">\; )</span>$

Let M denote the QoS state group ID (QS_GID), the result is:

${\mathrm{<span\; class="notranslate">\; N</span>}}_{\mathrm{<span\; class="notranslate">\; Q</span>}<span\; class="notranslate">\; \_</span>\mathrm{<span\; class="notranslate">\; DJR</span>}}<span\; class="notranslate">\; (</span>\mathrm{<span\; class="notranslate">\; t</span>}<span\; class="notranslate">\; )</span><span\; class="notranslate">\; =</span>\underset{\mathrm{<span\; class="notranslate">\; m</span>}<span\; class="notranslate">\; =</span>\mathrm{<span\; class="notranslate">\; 1</span>}}{\overset{\mathrm{<span\; class="notranslate">\; 4</span>}}{\mathrm{<span\; class="notranslate">\; \&Sigma;</span>}}}{\mathrm{<span\; class="notranslate">\; N</span>}}_{\mathrm{<span\; class="notranslate">\; Q</span>}<span\; class="notranslate">\; \_</span>\mathrm{<span\; class="notranslate">\; DJR</span>}}<span\; class="notranslate">\; (</span>\mathrm{<span\; class="notranslate">\; t</span>}<span\; class="notranslate">\; ,</span>\mathrm{<span\; class="notranslate">\; m</span>}<span\; class="notranslate">\; )</span><span\; class="notranslate">\; -</span><span\; class="notranslate">\; -</span><span\; class="notranslate">\; -</span><span\; class="notranslate">\; (</span>\mathrm{<span\; class="notranslate">\; 38</span>}<span\; class="notranslate">\; )</span>$

${\mathrm{<span\; class="notranslate">\; N</span>}}_{\mathrm{<span\; class="notranslate">\; Q</span>}<span\; class="notranslate">\; \_</span>\mathrm{<span\; class="notranslate">\; wxya</span>}}<span\; class="notranslate">\; (</span>\mathrm{<span\; class="notranslate">\; t</span>}<span\; class="notranslate">\; )</span><span\; class="notranslate">\; =</span>\underset{\mathrm{<span\; class="notranslate">\; m</span>}<span\; class="notranslate">\; =</span>\mathrm{<span\; class="notranslate">\; 3</span>}}{\overset{\mathrm{<span\; class="notranslate">\; 4</span>}}{\mathrm{<span\; class="notranslate">\; \&Sigma;</span>}}}{\mathrm{<span\; class="notranslate">\; N</span>}}_{\mathrm{<span\; class="notranslate">\; Q</span>}<span\; class="notranslate">\; \_</span>\mathrm{<span\; class="notranslate">\; wxya</span>}}<span\; class="notranslate">\; (</span>\mathrm{<span\; class="notranslate">\; t</span>}<span\; class="notranslate">\; ,</span>\mathrm{<span\; class="notranslate">\; m</span>}<span\; class="notranslate">\; )</span><span\; class="notranslate">\; -</span><span\; class="notranslate">\; -</span><span\; class="notranslate">\; -</span><span\; class="notranslate">\; (</span>\mathrm{<span\; class="notranslate">\; 39</span>}<span\; class="notranslate">\; )</span>$

${\mathrm{<span\; class="notranslate">\; N</span>}}_{\mathrm{<span\; class="notranslate">\; Q</span>}<span\; class="notranslate">\; \_</span>\mathrm{<span\; class="notranslate">\; R</span>}}<span\; class="notranslate">\; (</span>\mathrm{<span\; class="notranslate">\; t</span>}<span\; class="notranslate">\; )</span><span\; class="notranslate">\; =</span>\underset{\mathrm{<span\; class="notranslate">\; m</span>}<span\; class="notranslate">\; =</span>\mathrm{<span\; class="notranslate">\; 3</span>}}{\overset{\mathrm{<span\; class="notranslate">\; 4</span>}}{\mathrm{<span\; class="notranslate">\; \&Sigma;</span>}}}{\mathrm{<span\; class="notranslate">\; N</span>}}_{\mathrm{<span\; class="notranslate">\; Q</span>}<span\; class="notranslate">\; \_</span>\mathrm{<span\; class="notranslate">\; R</span>}}<span\; class="notranslate">\; (</span>\mathrm{<span\; class="notranslate">\; t</span>}<span\; class="notranslate">\; ,</span>\mathrm{<span\; class="notranslate">\; m</span>}<span\; class="notranslate">\; )</span><span\; class="notranslate">\; -</span><span\; class="notranslate">\; -</span><span\; class="notranslate">\; -</span><span\; class="notranslate">\; (</span>\mathrm{<span\; class="notranslate">\; 40</span>}<span\; class="notranslate">\; )</span>$

In QoS state group M at time t (in sector s), the fraction of a flow in QSG k corresponding to flow k is given by:

${\mathrm{<span\; class="notranslate">\; f</span>}}_{\mathrm{<span\; class="notranslate">\; k</span>}}<span\; class="notranslate">\; (</span>\mathrm{<span\; class="notranslate">\; t</span>}<span\; class="notranslate">\; ,</span>\mathrm{<span\; class="notranslate">\; m</span>}<span\; class="notranslate">\; ,</span>\mathrm{<span\; class="notranslate">\; the\; s</span>}<span\; class="notranslate">\; )</span><span\; class="notranslate">\; =</span>\frac{{\mathrm{<span\; class="notranslate">\; N</span>}}_{\mathrm{<span\; class="notranslate">\; k</span>}}<span\; class="notranslate">\; (</span>\mathrm{<span\; class="notranslate">\; t</span>}<span\; class="notranslate">\; ,</span>\mathrm{<span\; class="notranslate">\; m</span>}<span\; class="notranslate">\; ,</span>\mathrm{<span\; class="notranslate">\; the\; s</span>}<span\; class="notranslate">\; )</span>}{{\mathrm{<span\; class="notranslate">\; N</span>}}_{\mathrm{<span\; class="notranslate">\; k</span>}}<span\; class="notranslate">\; (</span>\mathrm{<span\; class="notranslate">\; t</span>}<span\; class="notranslate">\; ,</span>\mathrm{<span\; class="notranslate">\; the\; s</span>}<span\; class="notranslate">\; )</span>}<span\; class="notranslate">\; -</span><span\; class="notranslate">\; -</span><span\; class="notranslate">\; -</span><span\; class="notranslate">\; (</span>\mathrm{<span\; class="notranslate">\; 41</span>}<span\; class="notranslate">\; )</span>$

The fraction of processes with delay (or jitter) and rate violation at time t is given by:

Frac_flows_DJR_viol (t, s) = F _{Q_DJR} (t, M = 1, s) (42)

The fraction of processes with delay (or jitter) violations but no rate violations at time t is given by:

Frac_flows_DJ_viol(t, s) = F _{Q_DJR} (t, M = 2, s) (43)

The fraction of only rate-violating processes at time t is given by:

$\mathrm{<span\; class="notranslate">\; Frac</span>}<span\; class="notranslate">\; \_</span>\mathrm{<span\; class="notranslate">\; flows</span>}<span\; class="notranslate">\; \_</span>\mathrm{<span\; class="notranslate">\; R</span>}<span\; class="notranslate">\; \_</span>\mathrm{<span\; class="notranslate">\; only</span>}<span\; class="notranslate">\; \_</span>\mathrm{<span\; class="notranslate">\; viol</span>}<span\; class="notranslate">\; (</span>\mathrm{<span\; class="notranslate">\; t</span>}<span\; class="notranslate">\; ,</span>\mathrm{<span\; class="notranslate">\; the\; s</span>}<span\; class="notranslate">\; )</span><span\; class="notranslate">\; =</span>$

$\frac{{\mathrm{<span\; class="notranslate">\; N</span>}}_{\mathrm{<span\; class="notranslate">\; Q</span>}<span\; class="notranslate">\; \_</span>\mathrm{<span\; class="notranslate">\; DJR</span>}}<span\; class="notranslate">\; (</span>\mathrm{<span\; class="notranslate">\; t</span>}<span\; class="notranslate">\; ,</span>\mathrm{<span\; class="notranslate">\; m</span>}<span\; class="notranslate">\; =</span>\mathrm{<span\; class="notranslate">\; 3</span>}<span\; class="notranslate">\; ,</span>\mathrm{<span\; class="notranslate">\; the\; s</span>}<span\; class="notranslate">\; )</span><span\; class="notranslate">\; +</span>{\mathrm{<span\; class="notranslate">\; N</span>}}_{\mathrm{<span\; class="notranslate">\; Q</span>}<span\; class="notranslate">\; \_</span>\mathrm{<span\; class="notranslate">\; wxya</span>}}<span\; class="notranslate">\; (</span>\mathrm{<span\; class="notranslate">\; t</span>}<span\; class="notranslate">\; ,</span>\mathrm{<span\; class="notranslate">\; m</span>}<span\; class="notranslate">\; =</span>\mathrm{<span\; class="notranslate">\; 3</span>}<span\; class="notranslate">\; ,</span>\mathrm{<span\; class="notranslate">\; the\; s</span>}<span\; class="notranslate">\; )</span><span\; class="notranslate">\; +</span>{\mathrm{<span\; class="notranslate">\; N</span>}}_{\mathrm{<span\; class="notranslate">\; Q</span>}<span\; class="notranslate">\; \_</span>\mathrm{<span\; class="notranslate">\; R</span>}}<span\; class="notranslate">\; (</span>\mathrm{<span\; class="notranslate">\; t</span>}<span\; class="notranslate">\; ,</span>\mathrm{<span\; class="notranslate">\; m</span>}<span\; class="notranslate">\; =</span>\mathrm{<span\; class="notranslate">\; 3</span>}<span\; class="notranslate">\; ,</span>\mathrm{<span\; class="notranslate">\; the\; s</span>}<span\; class="notranslate">\; )</span>}{{\mathrm{<span\; class="notranslate">\; N</span>}}_{\mathrm{<span\; class="notranslate">\; Q</span>}<span\; class="notranslate">\; \_</span>\mathrm{<span\; class="notranslate">\; DJR</span>}}<span\; class="notranslate">\; (</span>\mathrm{<span\; class="notranslate">\; t</span>}<span\; class="notranslate">\; ,</span>\mathrm{<span\; class="notranslate">\; the\; s</span>}<span\; class="notranslate">\; )</span><span\; class="notranslate">\; +</span>{\mathrm{<span\; class="notranslate">\; N</span>}}_{\mathrm{<span\; class="notranslate">\; Q</span>}<span\; class="notranslate">\; \_</span>\mathrm{<span\; class="notranslate">\; wxya</span>}}<span\; class="notranslate">\; (</span>\mathrm{<span\; class="notranslate">\; t</span>}<span\; class="notranslate">\; ,</span>\mathrm{<span\; class="notranslate">\; the\; s</span>}<span\; class="notranslate">\; )</span><span\; class="notranslate">\; +</span>{\mathrm{<span\; class="notranslate">\; N</span>}}_{\mathrm{<span\; class="notranslate">\; Q</span>}<span\; class="notranslate">\; \_</span>\mathrm{<span\; class="notranslate">\; R</span>}}<span\; class="notranslate">\; (</span>\mathrm{<span\; class="notranslate">\; t</span>}<span\; class="notranslate">\; ,</span>\mathrm{<span\; class="notranslate">\; the\; s</span>}<span\; class="notranslate">\; )</span>}<span\; class="notranslate">\; -</span><span\; class="notranslate">\; -</span><span\; class="notranslate">\; -</span><span\; class="notranslate">\; (</span>\mathrm{<span\; class="notranslate">\; 44</span>}<span\; class="notranslate">\; )</span>$

The score for a process with no QoS violation (or in the NA category) is given by:

$\mathrm{<span\; class="notranslate">\; Frac</span>}<span\; class="notranslate">\; \_</span>\mathrm{<span\; class="notranslate">\; flows</span>}<span\; class="notranslate">\; \_</span>\mathrm{<span\; class="notranslate">\; no</span>}<span\; class="notranslate">\; \_</span>\mathrm{<span\; class="notranslate">\; na</span>}<span\; class="notranslate">\; \_</span>\mathrm{<span\; class="notranslate">\; viol</span>}<span\; class="notranslate">\; (</span>\mathrm{<span\; class="notranslate">\; t</span>}<span\; class="notranslate">\; ,</span>\mathrm{<span\; class="notranslate">\; the\; s</span>}<span\; class="notranslate">\; )</span><span\; class="notranslate">\; =</span>$

$\frac{{\mathrm{<span\; class="notranslate">\; N</span>}}_{\mathrm{<span\; class="notranslate">\; Q</span>}<span\; class="notranslate">\; \_</span>\mathrm{<span\; class="notranslate">\; DJR</span>}}<span\; class="notranslate">\; (</span>\mathrm{<span\; class="notranslate">\; t</span>}<span\; class="notranslate">\; ,</span>\mathrm{<span\; class="notranslate">\; m</span>}<span\; class="notranslate">\; =</span>\mathrm{<span\; class="notranslate">\; 4</span>}<span\; class="notranslate">\; ,</span>\mathrm{<span\; class="notranslate">\; the\; s</span>}<span\; class="notranslate">\; )</span><span\; class="notranslate">\; +</span>{\mathrm{<span\; class="notranslate">\; N</span>}}_{\mathrm{<span\; class="notranslate">\; Q</span>}<span\; class="notranslate">\; \_</span>\mathrm{<span\; class="notranslate">\; wxya</span>}}<span\; class="notranslate">\; (</span>\mathrm{<span\; class="notranslate">\; t</span>}<span\; class="notranslate">\; ,</span>\mathrm{<span\; class="notranslate">\; m</span>}<span\; class="notranslate">\; =</span>\mathrm{<span\; class="notranslate">\; 4</span>}<span\; class="notranslate">\; ,</span>\mathrm{<span\; class="notranslate">\; the\; s</span>}<span\; class="notranslate">\; )</span><span\; class="notranslate">\; +</span>{\mathrm{<span\; class="notranslate">\; N</span>}}_{\mathrm{<span\; class="notranslate">\; Q</span>}<span\; class="notranslate">\; \_</span>\mathrm{<span\; class="notranslate">\; R</span>}}<span\; class="notranslate">\; (</span>\mathrm{<span\; class="notranslate">\; t</span>}<span\; class="notranslate">\; ,</span>\mathrm{<span\; class="notranslate">\; m</span>}<span\; class="notranslate">\; =</span>\mathrm{<span\; class="notranslate">\; 4</span>}<span\; class="notranslate">\; ,</span>\mathrm{<span\; class="notranslate">\; the\; s</span>}<span\; class="notranslate">\; )</span>}{{\mathrm{<span\; class="notranslate">\; N</span>}}_{\mathrm{<span\; class="notranslate">\; Q</span>}<span\; class="notranslate">\; \_</span>\mathrm{<span\; class="notranslate">\; DJR</span>}}<span\; class="notranslate">\; (</span>\mathrm{<span\; class="notranslate">\; t</span>}<span\; class="notranslate">\; ,</span>\mathrm{<span\; class="notranslate">\; the\; s</span>}<span\; class="notranslate">\; )</span><span\; class="notranslate">\; +</span>{\mathrm{<span\; class="notranslate">\; N</span>}}_{\mathrm{<span\; class="notranslate">\; Q</span>}<span\; class="notranslate">\; \_</span>\mathrm{<span\; class="notranslate">\; wxya</span>}}<span\; class="notranslate">\; (</span>\mathrm{<span\; class="notranslate">\; t</span>}<span\; class="notranslate">\; ,</span>\mathrm{<span\; class="notranslate">\; the\; s</span>}<span\; class="notranslate">\; )</span><span\; class="notranslate">\; +</span>{\mathrm{<span\; class="notranslate">\; N</span>}}_{\mathrm{<span\; class="notranslate">\; Q</span>}<span\; class="notranslate">\; \_</span>\mathrm{<span\; class="notranslate">\; R</span>}}<span\; class="notranslate">\; (</span>\mathrm{<span\; class="notranslate">\; t</span>}<span\; class="notranslate">\; ,</span>\mathrm{<span\; class="notranslate">\; the\; s</span>}<span\; class="notranslate">\; )</span>}<span\; class="notranslate">\; -</span><span\; class="notranslate">\; -</span><span\; class="notranslate">\; -</span><span\; class="notranslate">\; (</span>\mathrm{<span\; class="notranslate">\; 45</span>}<span\; class="notranslate">\; )</span>$

The adaptation of S(t) is performed periodically after each time period T, which is pre-specified. For the purpose of adaptation, the above groups can be considered as follows.

table 3

QSG Score of processes with QS_GID=1 Score with QID=2 Score with QID=3 Score with QID=4 QSG_DJR Frac_flows_DJR_viol(t, s) Frac_flows_DJ_viol(t, s) Combined with Frac_flows_R_only_viol(t, s) Combined with Frac_flows_no_na_viol(t, s) QSG_RavgD not applicable Unused Combined with Frac_flows_R_only_viol(t, s) Combined with Frac_flows_no_na_viol(t, s) QSG_R not applicable not applicable Combined with Frac_flows_R_only_viol(t, s) combined with Frac_flows_no_na_viol(t, s)

The following thresholds are pre-specified and used in the adaptive method shown below.

Frac_flows_thres_DJR: Threshold on fraction of flows with latency (or jitter) and rate violations

Frac_flows_thres_DJ: Threshold on the fraction of flows with delay (or jitter) violations and no rate violations

Frac_flows_thres_R: Threshold on fraction of flows with rate violations (and no latency or jitter violations)

Frac_flows_thres_ok_qos: Threshold on the fraction of flows with no QoS violations

Immediately after each adaptive check for AS(t), the process continues in the following order:

Step 1: If Frac_flows_DJR_viol(t, s) ≥ Frac_flows_thres_DJR:

AS(t ⁺ )=f _qos *AS(t)+x _qos , so that AS(t ⁺ )≧AS(t). Here, f _qos and x _qos are pre-specified. otherwise,

Step 2: If Frac_flows_DJ_viol(t, s) ≥ Frac_flows_thres_DJ:

Then AS(t ⁺ )=f _{delay_jitter} *AS(t)+x _{delay_jitter} , so that AS(t ⁺ )≥AS(t). Here, f _{delay_jitter} and x _{delay_jitter} are pre-specified. otherwise,

Step 3: If Frac_flows_R_only_viol(t, s) ≥ Frac_flows_thres_R:

Then AS(t ⁺ )=f _rate *AS(t)+x _rate , so that AS(t ⁺ )≥AS(t). Here, f _rate and x _rate are pre-specified.

otherwise,

Step 4: If Frac_flows_no_na_viol(t, s) ≥ Frac_flows_thres_ok_qos:

Then AS(t ⁺ )= _{fall_qos_flows} *AS(t)+x _{all_qos_flows} , so AS(t ⁺ )≥AS(t). Here, f _{all_qos_flows} and x _{all_qos_flows} are pre-specified. otherwise,

Step 5: If Frac_flows_no_na_viol(t, s) ≥ Frac_flows_thres_ok_qos, and if

Frac_slots_qos_flows(t, s) < Frac_thres_slots_qos_flows:

Then AS(t ⁺ )=f _ok *AS(t)+x _ok , so AS(t ⁺ )≦AS(t). Here, f _ok and x _ok are pre-specified. otherwise,

Step 6: If Frac_flows_no_na_viol(t, s) ≥ Frac_flows_thres_ok_qos, and if

Frac_slots_qos_flows(t, s) ≥ Frac_thres_slots_qos_flows:

Then AS(t ⁺ )=AS(t).

preemptive scheme

Figure 19 illustrates a method 400 of preempting, according to one embodiment. Method 400 begins by determining whether ASF has been increased at decision diamond 402 . When an increase in ASF is detected, processing proceeds to step 404 to determine the flow with the highest number of rate violations. In other words, preemption method 400 begins identifying those processes to preempt as the ASF increases. In this embodiment, flows with rate violations are indicated as the best candidates for preemption. Alternative embodiments may give priority to other processes, and may dynamically change the priority scheme.

If at decision diamond 406 a preempted maximum value P _MAX (described in detail below) is reached, then processing proceeds to step 408 to preempt the flow of the highest number of delay violations. Otherwise processing returns to decision diamond 402 . After preempting a flow at step 408, processing proceeds to decision diamond 410 to determine if there are multiple flows with the highest number of delay violations. For multiple flows, processing proceeds to step 412 to preempt the flow using the most slots. Typically, this flow will have a very low data rate and thus consume the most slots during a given period of time. Processing then returns to decision diamond 402 .

In one embodiment, the preemption method 400 is applied, where P_max is the maximum number of processes allowed to be preempted at any given point in time. Consider the subset of processes that satisfy the conditions of the two preemption groups shown in Table 3. Specifically, preemptive group 1 contains processes belonging to QSG_R or QSG_RavgD and has

rate_viol(f _k , t, s)＞rate_viol_thres((f _k ), and (46)

Frac_slot_flow(f _k , t, s)>frac_thres_slots_flow(f _k ). (47)

Preempting group 2 contains processes belonging to Q_DJR QSG, and said processes contain

Frac_delayed_IP_Pkts(f _k , t, s) > Frac_delayed_IP_pkts_thres(f _k ) and (48)

Frac_slots_flow(f _k , t, s)>frac_thres_slots_flow(f _k ). (49)

Table 4

Preemption group ID QSG QoS Violation Slot Threshold Violation 1 Q_R, Q_RavgD rate_viol(f_k, t, s)>rate_viol_thres((f_k) Frac_slot_flow(f_k, t, s)＞frac_thres_slots_flow(f_k) 2 Q_DJR Frac_delayed_IP_Pkts(f_k, t, s)＞Frac_delayed_IP_pkts_thres(f_k) Frac_slots_flow(f_k, t, s)＞frac_thres_slots_flow(f_k)

Step 1: If at some point in time AS(t) is increased (as in the adaptive method of AS(t)), the process checks to see if one or several flows are eligible to preempt. Note that no flow is preempted when AS(t) is not incremented.

Step 2: Consider the subset of processes corresponding to preemptive group 1. From these processes, select the P_max processes with the largest rate_viol value. If there is a tie, the flow with the larger Frac_slots_flow value is preempted. If P_max processes are preempted, no more processes are preempted for rate violations.

Step 3: Consider the subset of processes corresponding to preemptive group 2. These flows have delay and jitter requirements with Frac_delayed_IP_Pkts(f _k , t, s) > Frac_delayed_IP_pkts_thres(f _k ) and Frac_slots_flow(f _k , t, s) > frac_thres_slots_flow(f _k ). From these processes, select P_max minus the number of processes preempted in step 2 with the largest Frac_delayed_IP_Pkts. If there is a tie, the flow with the larger Frac_slots_flow value is preempted.

Intra-user and inter-user QoS

A mobile user may have multiple processes at the same time, that is, multiple applications. As presented in this article, the user may specify the following:

An indication of each process as to whether it is sensitive to latency and jitter. If it is sensitive to delay and jitter, specify delay and jitter bounds.

Total Target Rate (ATR) for each user. This is the target rate that the scheduler of the forward link hierarchy intends to give to this user.

access control

Given R(t) users at time t, denoted as U ₁ , U ₂ ,..., U _R(t) , regard num_flows(U _j , t) as the number of flows of user U _j at time t . Suppose, at time t, user U _j has (k-1) flows allowed to enter, that is, num_flows(U _j , t)=k-1. To decide to admit a new flow f _k,j of user U _j at time t, the process uses the observed DRC of user U _j to check the following:

$\underset{\mathrm{<span\; class="notranslate">\; c</span>}<span\; class="notranslate">\; =</span>\mathrm{<span\; class="notranslate">\; 1</span>}}{\overset{\mathrm{<span\; class="notranslate">\; k</span>}}{\mathrm{<span\; class="notranslate">\; \&Sigma;</span>}}}\mathrm{<span\; class="notranslate">\; req</span>}<span\; class="notranslate">\; \_</span>\mathrm{<span\; class="notranslate">\; rate</span>}<span\; class="notranslate">\; (</span>{\mathrm{<span\; class="notranslate">\; f</span>}}_{\mathrm{<span\; class="notranslate">\; k</span>}<span\; class="notranslate">\; ,</span>\mathrm{<span\; class="notranslate">\; j</span>}}<span\; class="notranslate">\; )</span><span\; class="notranslate">\; \&le;</span>\mathrm{<span\; class="notranslate">\; Avg</span>}<span\; class="notranslate">\; (</span>\mathrm{<span\; class="notranslate">\; DRC</span>}<span\; class="notranslate">\; (</span>{\mathrm{<span\; class="notranslate">\; u</span>}}_{\mathrm{<span\; class="notranslate">\; j</span>}}<span\; class="notranslate">\; )</span><span\; class="notranslate">\; )</span><span\; class="notranslate">\; .</span><span\; class="notranslate">\; -</span><span\; class="notranslate">\; -</span><span\; class="notranslate">\; -</span><span\; class="notranslate">\; (</span>\mathrm{<span\; class="notranslate">\; 50</span>}<span\; class="notranslate">\; )</span>$

When performing ASF adaptation as described above, the number of time slots taken by the process and its corresponding DRC are also taken into consideration. The process calculates AS(t) and Avail(t) as follows:

$\mathrm{<span\; class="notranslate">\; Avail</span>}<span\; class="notranslate">\; (</span>\mathrm{<span\; class="notranslate">\; t</span>}<span\; class="notranslate">\; )</span><span\; class="notranslate">\; =</span>\mathrm{<span\; class="notranslate">\; max</span>}\mathrm{<span\; class="notranslate">\; imum</span>}<span\; class="notranslate">\; (</span>\frac{{\mathrm{<span\; class="notranslate">\; L</span>}}_{\mathrm{<span\; class="notranslate">\; max</span>}}}{\mathrm{<span\; class="notranslate">\; AS</span>}<span\; class="notranslate">\; (</span>\mathrm{<span\; class="notranslate">\; t</span>}<span\; class="notranslate">\; )</span>}<span\; class="notranslate">\; -</span>\mathrm{<span\; class="notranslate">\; Res</span>}<span\; class="notranslate">\; (</span>\mathrm{<span\; class="notranslate">\; t</span>}<span\; class="notranslate">\; )</span><span\; class="notranslate">\; ,</span>\mathrm{<span\; class="notranslate">\; 0</span>}<span\; class="notranslate">\; )</span><span\; class="notranslate">\; -</span><span\; class="notranslate">\; -</span><span\; class="notranslate">\; -</span><span\; class="notranslate">\; (</span>\mathrm{<span\; class="notranslate">\; 51</span>}<span\; class="notranslate">\; )</span>$

The process allows flow f _{k, j} to enter at time t if the following holds:

req_rate(f _{k, j} )≤Avail(t) (52)

If the flow is allowed in, update as follows:

Res(t)=Res(t)+req_rate(f _{k, j} ), (53)

Avail(t)=Avail(t)-req_rate(f _{k, j} ), (54)

ATR(U _j , t)=ATR(U _j ,t)+req_rate(f _k,j ), (55)

The process continues to monitor QoS statistics for all admitted processes and users, and monitors network-related statistics. Use this information to continue to adapt booking factors. The ASF AS(t) is then calculated and applied.

Hierarchical Scheduler

Compensation per process and per user:

Each latency- and jitter-sensitive process is assigned a jitter threshold. For each delay- and jitter-sensitive flow fx of user _Uk , the process calculates the corresponding delay and jitter compensation Φ. If the process does not have any packets in a queue that exceed the latency threshold, then

φ(fx(U _k ))=1. (56)

Otherwise, calculate

$\mathrm{<span\; class="notranslate">\; \&phi;</span>}<span\; class="notranslate">\; (</span>\mathrm{<span\; class="notranslate">\; fx</span>}<span\; class="notranslate">\; (</span>{\mathrm{<span\; class="notranslate">\; u</span>}}_{\mathrm{<span\; class="notranslate">\; k</span>}}<span\; class="notranslate">\; )</span><span\; class="notranslate">\; )</span><span\; class="notranslate">\; =</span>{\mathrm{<span\; class="notranslate">\; C</span>}}_{\mathrm{<span\; class="notranslate">\; delay</span>}}<span\; class="notranslate">\; (</span>\mathrm{<span\; class="notranslate">\; fx</span>}<span\; class="notranslate">\; (</span>{\mathrm{<span\; class="notranslate">\; u</span>}}_{\mathrm{<span\; class="notranslate">\; k</span>}}<span\; class="notranslate">\; )</span><span\; class="notranslate">\; )</span><span\; class="notranslate">\; *</span>\frac{\mathrm{<span\; class="notranslate">\; ndefpkts</span>}<span\; class="notranslate">\; (</span>\mathrm{<span\; class="notranslate">\; fx</span>}<span\; class="notranslate">\; (</span>{\mathrm{<span\; class="notranslate">\; u</span>}}_{\mathrm{<span\; class="notranslate">\; k</span>}}<span\; class="notranslate">\; ,</span>\mathrm{<span\; class="notranslate">\; no</span>}<span\; class="notranslate">\; )</span><span\; class="notranslate">\; )</span>}{{\mathrm{<span\; class="notranslate">\; ndefpkts</span>}}_{\mathrm{<span\; class="notranslate">\; min</span>}}<span\; class="notranslate">\; (</span>\mathrm{<span\; class="notranslate">\; no</span>}<span\; class="notranslate">\; )</span>}<span\; class="notranslate">\; -</span><span\; class="notranslate">\; -</span><span\; class="notranslate">\; -</span><span\; class="notranslate">\; (</span>\mathrm{<span\; class="notranslate">\; 57</span>}<span\; class="notranslate">\; )</span>$

here,

$\mathrm{<span\; class="notranslate">\; ndefpkts</span>}<span\; class="notranslate">\; (</span>\mathrm{<span\; class="notranslate">\; fx</span>}<span\; class="notranslate">\; (</span>{\mathrm{<span\; class="notranslate">\; u</span>}}_{\mathrm{<span\; class="notranslate">\; k</span>}}<span\; class="notranslate">\; ,</span>\mathrm{<span\; class="notranslate">\; no</span>}<span\; class="notranslate">\; )</span><span\; class="notranslate">\; =</span>\frac{\mathrm{<span\; class="notranslate">\; defpkts</span>}<span\; class="notranslate">\; (</span>\mathrm{<span\; class="notranslate">\; fx</span>}<span\; class="notranslate">\; (</span>{\mathrm{<span\; class="notranslate">\; u</span>}}_{\mathrm{<span\; class="notranslate">\; k</span>}}<span\; class="notranslate">\; ,</span>\mathrm{<span\; class="notranslate">\; no</span>}<span\; class="notranslate">\; )</span>}{\mathrm{<span\; class="notranslate">\; req</span>}<span\; class="notranslate">\; \_</span>\mathrm{<span\; class="notranslate">\; rate</span>}<span\; class="notranslate">\; (</span>\mathrm{<span\; class="notranslate">\; fx</span>}<span\; class="notranslate">\; (</span>{\mathrm{<span\; class="notranslate">\; u</span>}}_{\mathrm{<span\; class="notranslate">\; k</span>}}<span\; class="notranslate">\; )</span><span\; class="notranslate">\; )</span>}<span\; class="notranslate">\; -</span><span\; class="notranslate">\; -</span><span\; class="notranslate">\; -</span><span\; class="notranslate">\; (</span>\mathrm{<span\; class="notranslate">\; 58</span>}<span\; class="notranslate">\; )</span>$

For each flow fx of user U _k ,

ndefpkts _min (n) = minimum value of ndefpkts (59)

Consider all flows (of all users) at time slot n,

defpkts(fx(U _k , n) = number of pending MAC packets whose flow fx of user U _k violated its delay threshold at time slot n. (60)

For rate compensation for user U _k at slot n, define,

$\mathrm{<span\; class="notranslate">\; \&alpha;</span>}<span\; class="notranslate">\; (</span>{\mathrm{<span\; class="notranslate">\; u</span>}}_{\mathrm{<span\; class="notranslate">\; k</span>}}<span\; class="notranslate">\; ,</span>\mathrm{<span\; class="notranslate">\; no</span>}<span\; class="notranslate">\; )</span><span\; class="notranslate">\; =</span>\frac{\mathrm{<span\; class="notranslate">\; ATR</span>}<span\; class="notranslate">\; (</span>{\mathrm{<span\; class="notranslate">\; u</span>}}_{\mathrm{<span\; class="notranslate">\; k</span>}}<span\; class="notranslate">\; )</span>}{\mathrm{<span\; class="notranslate">\; ASR</span>}<span\; class="notranslate">\; (</span>{\mathrm{<span\; class="notranslate">\; u</span>}}_{\mathrm{<span\; class="notranslate">\; k</span>}}<span\; class="notranslate">\; ,</span>{\mathrm{<span\; class="notranslate">\; no</span>}}_{\mathrm{<span\; class="notranslate">\; prev</span>}}<span\; class="notranslate">\; (</span>\mathrm{<span\; class="notranslate">\; no</span>}<span\; class="notranslate">\; )</span><span\; class="notranslate">\; )</span>}<span\; class="notranslate">\; -</span><span\; class="notranslate">\; -</span><span\; class="notranslate">\; -</span><span\; class="notranslate">\; (</span>\mathrm{<span\; class="notranslate">\; 61</span>}<span\; class="notranslate">\; )</span>$

here,

ASR(U _k , n _prev (n)) = total service rate of user U _k in time slot n _prev , and (62)

n _prev ≤ n. (63)

Slot number n _prev is the last slot on or before n when monitoring rates for scheduling algorithm purposes.

This procedure defines the total delay compensation for user U _k at any time slot n. Consider all flows that this user has latency requirements, and look at the head-of-line (HOL) MAC packets for each of these latency-sensitive flows. If none have been in the system longer than their latency thresholds, then:

agg_delay_comp(U _k , n)=1. (64)

Otherwise, the user considers for this the subset of processes that have HOL packets staying in the system longer than a latency threshold. For this user, for all the flows fx of the user U _k whose HOL MAC packets stay in the system for a period exceeding the delay threshold of these flows, calculate:

$\mathrm{<span\; class="notranslate">\; agg</span>}<span\; class="notranslate">\; \_</span>\mathrm{<span\; class="notranslate">\; delay</span>}<span\; class="notranslate">\; \_</span>\mathrm{<span\; class="notranslate">\; comp</span>}<span\; class="notranslate">\; (</span>{\mathrm{<span\; class="notranslate">\; u</span>}}_{\mathrm{<span\; class="notranslate">\; k</span>}}<span\; class="notranslate">\; ,</span>\mathrm{<span\; class="notranslate">\; no</span>}<span\; class="notranslate">\; )</span><span\; class="notranslate">\; =</span>\underset{\mathrm{<span\; class="notranslate">\; x</span>}}{\mathrm{<span\; class="notranslate">\; \&Sigma;</span>}}\mathrm{<span\; class="notranslate">\; w</span>}<span\; class="notranslate">\; (</span>\mathrm{<span\; class="notranslate">\; fx</span>}<span\; class="notranslate">\; (</span>{\mathrm{<span\; class="notranslate">\; u</span>}}_{\mathrm{<span\; class="notranslate">\; k</span>}}<span\; class="notranslate">\; )</span><span\; class="notranslate">\; )</span><span\; class="notranslate">\; *</span>\mathrm{<span\; class="notranslate">\; \&phi;</span>}<span\; class="notranslate">\; (</span>\mathrm{<span\; class="notranslate">\; fx</span>}<span\; class="notranslate">\; (</span>{\mathrm{<span\; class="notranslate">\; u</span>}}_{\mathrm{<span\; class="notranslate">\; k</span>}}<span\; class="notranslate">\; )</span><span\; class="notranslate">\; ,</span>\mathrm{<span\; class="notranslate">\; no</span>}<span\; class="notranslate">\; )</span><span\; class="notranslate">\; ,</span><span\; class="notranslate">\; -</span><span\; class="notranslate">\; -</span><span\; class="notranslate">\; -</span><span\; class="notranslate">\; (</span>\mathrm{<span\; class="notranslate">\; 65</span>}<span\; class="notranslate">\; )</span>$

Here, w(fx(U _k )) is the initial weight assigned to the flow fx of user U _k .

Adaptive Weight Calculation

In order to compute adaptive weights for this user, the procedure checks for delay threshold violations at each time slot for each process for each user with at least one delay-sensitive process. The procedure computes for each such user U _k :

agg_delay_comp(U _k , n) (66)

If agg_delay_comp(U _k , n) > 1, the procedure calculates adaptive weights for user U _k as follows:

aw ^t (U _k , n)=agg_delay_comp(U _k , n)*aw ^t (U _k , n-1) (67)

On the other hand, if agg_delay_comp(U _k ,n)=1, the process calculates:

aw ^t (U _k , n)=α(U _k , n _prev (n))*w(U _k ) (68)

Here, nprev _,k (n) is the value above or before n when ASR( _Uk , _nprev (n)) is monitored (and thus α( _Uk , _nprev (n)) is calculated) last time slot. The process continues to compute the final adaptive weights for this user as follows:

aw(U _k , n)=Z(U _k ,n)*aw ^t (U _k ,n) (69)

Here, Z(U _k , n)=1 if user U _k does not have any packet in the RTx or DARQ queue of any delay-sensitive process. Otherwise, Z(U _k , n)=C(U _k ). Here, C(U _k ) is a predetermined constant.

User and Process Selection Methods

The procedure computes the following metric in slot n for each user that has at least one packet in its queue,

Y(U _k ,n)=aw(U _k ,n)*DRC(U _k ,n)/T(U _k ,n) (70)

here, $T(u_k,\mathrm{no})=\underset{\mathrm{fz}}{\mathrm{\&Sigma;}}T(\mathrm{fz}(u_k,\mathrm{no})$ is the average service rate for user U _k (ie including all corresponding flows). The process selects the user with the largest Y(U _k ,n) value. Once a user is selected with this scheduler, the process selects a flow for that user to serve according to each of the following schemes.

Consider processes that fall into the following groups:

Group 1: QSG_DELAY_JITTER. VoIP process.

Group 2: QSG_DELAY_JITTER. Video conferencing process.

Group 3: QSG_DELAY_JITTER. The flow of video streaming.

Group 4: QSG_RATE_AVERAGE_DELAY. A process with rate and average latency requirements.

Group 5: QSG_Rate. Processes with only rate requirements.

In performing the scheduling algorithm described herein, the following steps may be followed.

Step 1: Consider all backup flows for the selected user in that time slot.

Step 2: Consider the process where this user corresponds to groups 1 and 2. Select a process whose delay threshold has been violated by the HOL packet and which is closest to the delay boundary of the process. If a process is found, it is served. Otherwise, go to step 3.

Step 3: Consider the flows corresponding to group 3 in which the HOL packets have exceeded the delay threshold, and select the flow in which the HOL packets are closest to the delay boundary. If a process is found, it is served. Otherwise, proceed to the next step.

Step 4: Consider the flows corresponding to group 4 in which the HOL packets have exceeded the delay threshold, and select the flow in which the HOL packets are closest to the delay boundary. If a process is found, it is served. Otherwise, proceed to the next step.

Step 5: Select a backup process from groups 1 to 4 to serve. Priority is given to the process with the lowest group number. If a process has been selected, it is served. Otherwise, proceed to the next step.

Step 6: Consider the backup flow for this user corresponding to group 5. The one with the largest requested rate/service rate value is chosen. Serve this process. If none is selected, proceed to the next step.

Step 7: Best-effort process for serving the user. If there is more than one, choose the one with the smallest service rate value.

Figure 16 shows a two-level scheduler applying per-flow and per-user compensation. The schedulers shown in Figures 16 and 17 are hierarchical schedulers for inter-user and intra-user QoS compensation as described herein. As shown in Fig. 16, the first level, denoted level 1, comprises a plurality of scheduling elements or nodes S1, S2, ..., SM, where each node handles a different QSG. In this example, M is the number of QSG packets to process. For example, dispatch node S1 handles application flow of the Voice over IP (VoIP) type. Although IP telephony is given as an example, any application flow classified as QSG 1 will be handled at S1. These flows have delay and jitter boundaries specified for evaluating QoS requirements. Flows of multiple application IP telephony types are handled at dispatch element S1. Similarly, each scheduling element is a designated QSG processing flow. Note that alternative embodiments may provide multiple QSG's application flows to one scheduling element. Note that multiple scheduling elements can be used to process the same QSG group.

Level I of the scheduler shown in Figure 16 calculates a portion of the compensation for each process. Multiple application flows per user are shown in FIG. 16 . Computation of compensation for each flow is performed by the Level II scheduling element.

Fig. 17 shows a scheduler with scheduling nodes S1 , S2 , ..., Sz . In this step, z is the number of users. Note that the number of users is dynamic, so the number of current scheduling nodes can be changed dynamically. Each scheduling node S1 , S2 , ..., Sz is adapted to receive multiple flows from a given user. Scheduling node S1 receives flows F1 to Fk for user 1 (U1). Here k is the total number of application processes currently processed for user1. Using the per-flow compensation calculated by the Level I and Level II schedulers in Figure 16, the Level II scheduler in Figure 17 calculates the total user compensation for each user. The Level II scheduler then selects the users to be served in the slots according to the adaptive weighted DRC/T algorithm described above for the user selection method. The Tier II scheduler then chooses between the weighted values received from the Tier I scheduler. As indicated, W(Uk) is the initial weight assigned to user Uk and ATR(Uk) is the total target rate for user Uk. Once a user is selected, the class I scheduler corresponding to the user selects the flow to be served in the time slot for the user according to the flow selection method described above.

A forward link scheduler may allow each user to specify a price to bear for a process to be served at a given DRC value in a time slot. Once the price is specified, the adaptive frame structure scheduler operates to meet the QoS requirements of different types of applications. The corresponding scheduling mechanism allows the service provider to find a good balance between increasing benefits and meeting the QoS requirements of the application. This scheduling mechanism also provides dynamic cost control for end users and can be used for applications with rate and/or average latency requirements or for streaming applications, etc. One embodiment provides a pricing option where each flow specifies a price per slot when it is served. This price depends on the DRC value requested by the user for the process in that time slot. The price that process j (that is, the user accessing process j) is willing to pay at time slot m is denoted as c[j, m, DRC[j, m]]. Here DRC[j,m] denotes the rate at which this user is served in slot m. A user may statically specify a price, such as pre-specifying a price for each DRC value. Alternatively, the user may specify the price dynamically, such as changing the price during the lifetime of the application. This allows the user some degree of control over the price to respond to changing channel conditions and achieve the desired QoS. Operators can use such a scheduler along with schedulers given for inter-user and intra-user QoS. This allows the operator to specify at least two types of pricing schemes. For the inter-user and intra-user QoS schedulers, the operator can specify a static pricing scheme (based on a static service level agreement), and at the same time allow a dynamic pricing scheme based on an adaptive frame structure based scheduler. Users can choose to use different schemes for different processes.

One embodiment divides time into frames and makes scheduling decisions for each time slot based on DRC values, QoS requirements, QoS violation statistics, and prices specified by each user. The frame structure basically gives the order of the queue of users that should be served in a round. In each round of scheduling, the network decides which process/user to serve in a given time slot in order to achieve the desired goal. The frame structure, ie the order of the service flow in each round, changes continuously and is called based on the AFS algorithm.

The following definitions explain some of the symbols used in the calculations. Given N queues (one queue per process), assume that if process j is served at rate r[j], its QoS requirements are satisfied. The initial weight w[j] and time scale ts[j] are also pre-specified for each process j. This procedure aims to provide rate guarantees for process j, which is monitored at timeslots that are integer multiples of each time scale (ie, at every m*ts[j] timeslots, where m is an integer).

Let start[j] be the time slot when process j is initially considered to be serviced in a round. By the end of slot z, the system wishes to serve S[j, z] = r[j]*(z-start[j]) bits, where z = m*ts[j] for some integer m. Using a scheduling mechanism, the system is able to balance the number of slots desired to be allocated to a given flow with the number of bits desired to serve that flow.

In addition, other parameters for the AFS scheduler are as follows:

slots_alloc[j, n]: the number of time slots allocated to queue (process) j in round n.

slot_served[j, n]: the number of slots when queue (process) j is served in round n.

S_r[j,n]: number of bits to serve flow j until the end of round n.

round_len[n]: The length of the nth round of time slots.

round_len_thres: The length of a round is bounded by this threshold.

B[n]: list of backup queues at the beginning of slot n.

R _{out_round} [j,n]: Number of bits served by the scheduler for queue j in round n.

R _out [j, n, g]: number of bits served for queue j during time interval [n, g], where g ≥ n.

Using the description given above, the deficit bits of queue j at the beginning of round n are given by:

$\mathrm{<span\; class="notranslate">\; def</span>}<span\; class="notranslate">\; \_</span>\mathrm{<span\; class="notranslate">\; bits</span>}<span\; class="notranslate">\; \_</span>\mathrm{<span\; class="notranslate">\; r</span>}<span\; class="notranslate">\; [</span>\mathrm{<span\; class="notranslate">\; j</span>}<span\; class="notranslate">\; ,</span>\mathrm{<span\; class="notranslate">\; no</span>}<span\; class="notranslate">\; ]</span><span\; class="notranslate">\; =</span>\mathrm{<span\; class="notranslate">\; max</span>}<span\; class="notranslate">\; (</span>\mathrm{<span\; class="notranslate">\; S</span>}<span\; class="notranslate">\; \_</span>\mathrm{<span\; class="notranslate">\; r</span>}<span\; class="notranslate">\; [</span>\mathrm{<span\; class="notranslate">\; j</span>}<span\; class="notranslate">\; ,</span>\mathrm{<span\; class="notranslate">\; no</span>}<span\; class="notranslate">\; -</span>\mathrm{<span\; class="notranslate">\; 1</span>}<span\; class="notranslate">\; ]</span><span\; class="notranslate">\; -</span>\underset{\mathrm{<span\; class="notranslate">\; k</span>}<span\; class="notranslate">\; =</span>\mathrm{<span\; class="notranslate">\; 1</span>}}{\overset{\mathrm{<span\; class="notranslate">\; no</span>}<span\; class="notranslate">\; -</span>\mathrm{<span\; class="notranslate">\; 1</span>}}{\mathrm{<span\; class="notranslate">\; \&Sigma;</span>}}}{\mathrm{<span\; class="notranslate">\; R</span>}}_{\mathrm{<span\; class="notranslate">\; out</span>}<span\; class="notranslate">\; \_</span>\mathrm{<span\; class="notranslate">\; round</span>}}<span\; class="notranslate">\; [</span>\mathrm{<span\; class="notranslate">\; j</span>}<span\; class="notranslate">\; ,</span>\mathrm{<span\; class="notranslate">\; k</span>}<span\; class="notranslate">\; ]</span><span\; class="notranslate">\; ,</span>\mathrm{<span\; class="notranslate">\; 0</span>}<span\; class="notranslate">\; )</span><span\; class="notranslate">\; ,</span><span\; class="notranslate">\; \&ForAll;</span>\mathrm{<span\; class="notranslate">\; no</span>}<span\; class="notranslate">\; ,</span><span\; class="notranslate">\; \&ForAll;</span>\mathrm{<span\; class="notranslate">\; j</span>}<span\; class="notranslate">\; -</span><span\; class="notranslate">\; -</span><span\; class="notranslate">\; -</span><span\; class="notranslate">\; (</span>\mathrm{<span\; class="notranslate">\; 71</span>}<span\; class="notranslate">\; )</span>$

When the deficit bit is positive, the corresponding process is behind in service and needs to be compensated. On the other hand, extra service received by a process is not explicitly penalized, but is penalized indirectly, since this process will not be compensated, while other processes falling behind in service will be.

Furthermore, the normalized deficit bits for the beginning process j at round n is given by:

$\mathrm{<span\; class="notranslate">\; ndef</span>}<span\; class="notranslate">\; \_</span>\mathrm{<span\; class="notranslate">\; bits</span>}<span\; class="notranslate">\; \_</span>\mathrm{<span\; class="notranslate">\; r</span>}<span\; class="notranslate">\; [</span>\mathrm{<span\; class="notranslate">\; j</span>}<span\; class="notranslate">\; ,</span>\mathrm{<span\; class="notranslate">\; no</span>}<span\; class="notranslate">\; ]</span><span\; class="notranslate">\; =</span>\frac{\mathrm{<span\; class="notranslate">\; def</span>}<span\; class="notranslate">\; \_</span>\mathrm{<span\; class="notranslate">\; bits</span>}<span\; class="notranslate">\; \_</span>\mathrm{<span\; class="notranslate">\; r</span>}<span\; class="notranslate">\; [</span>\mathrm{<span\; class="notranslate">\; j</span>}<span\; class="notranslate">\; ,</span>\mathrm{<span\; class="notranslate">\; no</span>}<span\; class="notranslate">\; ]</span>}{\mathrm{<span\; class="notranslate">\; S</span>}<span\; class="notranslate">\; \_</span>\mathrm{<span\; class="notranslate">\; r</span>}<span\; class="notranslate">\; [</span>\mathrm{<span\; class="notranslate">\; j</span>}<span\; class="notranslate">\; ,</span>\mathrm{<span\; class="notranslate">\; no</span>}<span\; class="notranslate">\; -</span>\mathrm{<span\; class="notranslate">\; 1</span>}<span\; class="notranslate">\; ]</span>}<span\; class="notranslate">\; ,</span><span\; class="notranslate">\; \&ForAll;</span>\mathrm{<span\; class="notranslate">\; j</span>}<span\; class="notranslate">\; ,</span><span\; class="notranslate">\; \&ForAll;</span>\mathrm{<span\; class="notranslate">\; no</span>}<span\; class="notranslate">\; .</span><span\; class="notranslate">\; -</span><span\; class="notranslate">\; -</span><span\; class="notranslate">\; -</span><span\; class="notranslate">\; (</span>\mathrm{<span\; class="notranslate">\; 72</span>}<span\; class="notranslate">\; )</span>$

The deficit slot of start queue j in round n is given by:

$\mathrm{<span\; class="notranslate">\; def</span>}<span\; class="notranslate">\; \_</span>\mathrm{<span\; class="notranslate">\; slots</span>}<span\; class="notranslate">\; \_</span>\mathrm{<span\; class="notranslate">\; r</span>}<span\; class="notranslate">\; [</span>\mathrm{<span\; class="notranslate">\; j</span>}<span\; class="notranslate">\; ,</span>\mathrm{<span\; class="notranslate">\; no</span>}<span\; class="notranslate">\; ]</span><span\; class="notranslate">\; =</span>\mathrm{<span\; class="notranslate">\; max</span>}<span\; class="notranslate">\; (</span>\underset{\mathrm{<span\; class="notranslate">\; k</span>}<span\; class="notranslate">\; =</span>\mathrm{<span\; class="notranslate">\; 1</span>}}{\overset{\mathrm{<span\; class="notranslate">\; no</span>}<span\; class="notranslate">\; -</span>\mathrm{<span\; class="notranslate">\; 1</span>}}{\mathrm{<span\; class="notranslate">\; \&Sigma;</span>}}}\mathrm{<span\; class="notranslate">\; slots</span>}<span\; class="notranslate">\; \_</span>\mathrm{<span\; class="notranslate">\; alloc</span>}<span\; class="notranslate">\; [</span>\mathrm{<span\; class="notranslate">\; j</span>}<span\; class="notranslate">\; ,</span>\mathrm{<span\; class="notranslate">\; k</span>}<span\; class="notranslate">\; ]</span><span\; class="notranslate">\; -</span>\underset{\mathrm{<span\; class="notranslate">\; k</span>}<span\; class="notranslate">\; =</span>\mathrm{<span\; class="notranslate">\; 1</span>}}{\overset{\mathrm{<span\; class="notranslate">\; no</span>}<span\; class="notranslate">\; -</span>\mathrm{<span\; class="notranslate">\; 1</span>}}{\mathrm{<span\; class="notranslate">\; \&Sigma;</span>}}}\mathrm{<span\; class="notranslate">\; slots</span>}<span\; class="notranslate">\; \_</span>\mathrm{<span\; class="notranslate">\; served</span>}<span\; class="notranslate">\; [</span>\mathrm{<span\; class="notranslate">\; j</span>}<span\; class="notranslate">\; ,</span>\mathrm{<span\; class="notranslate">\; k</span>}<span\; class="notranslate">\; ]</span><span\; class="notranslate">\; ,</span>\mathrm{<span\; class="notranslate">\; 0</span>}<span\; class="notranslate">\; )</span><span\; class="notranslate">\; ,</span><span\; class="notranslate">\; \&ForAll;</span>\mathrm{<span\; class="notranslate">\; no</span>}<span\; class="notranslate">\; ,</span><span\; class="notranslate">\; \&ForAll;</span>\mathrm{<span\; class="notranslate">\; j</span>}<span\; class="notranslate">\; -</span><span\; class="notranslate">\; -</span><span\; class="notranslate">\; -</span><span\; class="notranslate">\; (</span>\mathrm{<span\; class="notranslate">\; 73</span>}<span\; class="notranslate">\; )</span>$

The process defines the normalized deficit slots of the starting queue j of the nth round as follows:

$\mathrm{<span\; class="notranslate">\; ndef</span>}<span\; class="notranslate">\; \_</span>\mathrm{<span\; class="notranslate">\; slots</span>}<span\; class="notranslate">\; \_</span>\mathrm{<span\; class="notranslate">\; r</span>}<span\; class="notranslate">\; [</span>\mathrm{<span\; class="notranslate">\; j</span>}<span\; class="notranslate">\; ,</span>\mathrm{<span\; class="notranslate">\; no</span>}<span\; class="notranslate">\; ]</span><span\; class="notranslate">\; =</span>\frac{\mathrm{<span\; class="notranslate">\; def</span>}<span\; class="notranslate">\; \_</span>\mathrm{<span\; class="notranslate">\; slots</span>}<span\; class="notranslate">\; \_</span>\mathrm{<span\; class="notranslate">\; r</span>}<span\; class="notranslate">\; [</span>\mathrm{<span\; class="notranslate">\; j</span>}<span\; class="notranslate">\; ,</span>\mathrm{<span\; class="notranslate">\; no</span>}<span\; class="notranslate">\; ]</span>}{\underset{\mathrm{<span\; class="notranslate">\; k</span>}<span\; class="notranslate">\; =</span>\mathrm{<span\; class="notranslate">\; 0</span>}}{\overset{\mathrm{<span\; class="notranslate">\; no</span>}<span\; class="notranslate">\; -</span>\mathrm{<span\; class="notranslate">\; 1</span>}}{\mathrm{<span\; class="notranslate">\; \&Sigma;</span>}}}\mathrm{<span\; class="notranslate">\; slots</span>}<span\; class="notranslate">\; \_</span>\mathrm{<span\; class="notranslate">\; alloc</span>}<span\; class="notranslate">\; [</span>\mathrm{<span\; class="notranslate">\; j</span>}<span\; class="notranslate">\; ,</span>\mathrm{<span\; class="notranslate">\; k</span>}<span\; class="notranslate">\; ]</span>}<span\; class="notranslate">\; ,</span><span\; class="notranslate">\; \&ForAll;</span>\mathrm{<span\; class="notranslate">\; j</span>}<span\; class="notranslate">\; ,</span><span\; class="notranslate">\; \&ForAll;</span>\mathrm{<span\; class="notranslate">\; no</span>}<span\; class="notranslate">\; .</span><span\; class="notranslate">\; -</span><span\; class="notranslate">\; -</span><span\; class="notranslate">\; -</span><span\; class="notranslate">\; (</span>\mathrm{<span\; class="notranslate">\; 74</span>}<span\; class="notranslate">\; )</span>$

Let lslot[n] be the last slot of round n and fslot[n] be the first slot of round n. Let aw[j,n] denote the (adaptive) weight assigned to process j in round n. This weight determines the number of time slots allocated to process j in round n.

Sort the DRC values requested by the user. Specifically, if DRC ₁ [B, S] is better than DRC ₂ [B, S], then (B/S) ₁ >(B/S) ₂ . Here B is the number of bits per packet and S is the number of slots.

For each round of scheduling of the AFS scheduler, the process calculates the state variables given above for each round, and then calculates the weight for each process at the beginning of each round to allocate a certain amount to this process in this round time slot. For this purpose, the process uses an adaptive weight computation mechanism and computes the frame structure for each round with a round-by-round service law.

Adaptive weight calculation mechanism

Let ndef_bits_r _thres,min be the pre-specified ndef_bits_r threshold. The process defines an array ndefbits_set[n] at the beginning of round n as follows:

ndefbits_set[n] = {k: ndef_bits_r _k ≥ ndef_bits_r _{thres, min} }. (75)

Let S_I[n] be the number of processes in the array at the beginning of round n. Similarly, ndef_slots_r _thres,min is the pre-defined ndef_slots_r threshold. The process defines ndefslots_set[n] at the beginning of round n as follows:

ndefslot_set[n] = {k: ndef_slots_r _k ≥ ndef_slots_r _{thres, min} }. (76)

Let S_II[n] be the number of processes in this array at the beginning of round n.

For any process j, at the beginning of the nth round, the corresponding slot compensation function is defined as follows:

If ndef_bits_r _j ≥ ndef_bits_r _{thres, min}

Then slot_comp[j, n]=slot_comp_I[j, n]*slot_comp_II[j, n], (77)

If ndef_bits_r _j < ndef_bits_r _thres,min ,

Then, slot_comp[j, n]=1. (78)

here,

if ndef_bits_r _j ≥ ndef_bits_r _thres,min ,

but $\mathrm{slot}\_\mathrm{comp}\_I[j,\mathrm{no}]=\frac{\mathrm{ndef}\_\mathrm{bits}\_r_j}{\mathrm{ndef}\_\mathrm{bits}\_r_{\mathrm{avg}}\left[\mathrm{no}\right]},---\left(79\right)$

For all k: k ∈ ndefbits_set[n], $\mathrm{ndef}\_\mathrm{bits}\_r_{\mathrm{avg}}\left[\mathrm{no}\right]=\frac{\underset{k}{\mathrm{\&Sigma;}}\mathrm{ndef}\_\mathrm{bits}\_r_j}{S\_I\left[\mathrm{no}\right]}---\left(80\right)$

If ndef_bits_r _j < ndef_bits_r _thres,min ,

Then slot_comp_I[j, n]=1. (81)

For each process j, define two thresholds, slot_comp_I _{thres, min} [j] and slot_comp_I _{thres, max} [j], so that:

$\mathrm{<span\; class="notranslate">\; slot</span>}<span\; class="notranslate">\; \_</span>\mathrm{<span\; class="notranslate">\; comp</span>}<span\; class="notranslate">\; \_</span>{\mathrm{<span\; class="notranslate">\; I</span>}}_{\mathrm{<span\; class="notranslate">\; thres</span>}<span\; class="notranslate">\; ,</span>\mathrm{<span\; class="notranslate">\; min</span>}}<span\; class="notranslate">\; [</span>\mathrm{<span\; class="notranslate">\; j</span>}<span\; class="notranslate">\; ]</span><span\; class="notranslate">\; \&le;</span>\mathrm{<span\; class="notranslate">\; slot</span>}<span\; class="notranslate">\; \_</span>\mathrm{<span\; class="notranslate">\; comp</span>}<span\; class="notranslate">\; \_</span>\mathrm{<span\; class="notranslate">\; I</span>}<span\; class="notranslate">\; [</span>\mathrm{<span\; class="notranslate">\; j</span>}<span\; class="notranslate">\; ,</span>\mathrm{<span\; class="notranslate">\; no</span>}<span\; class="notranslate">\; ]</span><span\; class="notranslate">\; \&le;</span>\mathrm{<span\; class="notranslate">\; slot</span>}<span\; class="notranslate">\; \_</span>\mathrm{<span\; class="notranslate">\; comp</span>}<span\; class="notranslate">\; \_</span>{\mathrm{<span\; class="notranslate">\; I</span>}}_{\mathrm{<span\; class="notranslate">\; thres</span>}<span\; class="notranslate">\; ,</span>\mathrm{<span\; class="notranslate">\; max</span>}}<span\; class="notranslate">\; [</span>\mathrm{<span\; class="notranslate">\; j</span>}<span\; class="notranslate">\; ]</span><span\; class="notranslate">\; ,</span><span\; class="notranslate">\; \&ForAll;</span>\mathrm{<span\; class="notranslate">\; j</span>}<span\; class="notranslate">\; ,</span><span\; class="notranslate">\; \&ForAll;</span>\mathrm{<span\; class="notranslate">\; no</span>}<span\; class="notranslate">\; -</span><span\; class="notranslate">\; -</span><span\; class="notranslate">\; -</span><span\; class="notranslate">\; (</span>\mathrm{<span\; class="notranslate">\; 82</span>}<span\; class="notranslate">\; )</span>$

Using these thresholds in conjunction with the adaptive weight computation mechanism described here prevents any process from unfairly consuming a large number of slots in a round, while at the same time not penalizing that process for exceeding a given limit.

if ndef_slots_r _j ≥ ndef_slots_r _thres,min ,

but $\mathrm{slot}\_\mathrm{comp}\_\mathrm{II}[j,\mathrm{no}]=\frac{\mathrm{ndef}\_\mathrm{slots}\_r_j}{\mathrm{ndef}\_\mathrm{slots}\_r_{\mathrm{avg}}\left[\mathrm{no}\right]}---\left(83\right)$

If ndef_slots_r _j < ndef_slots_r _thres,min ,

Then slot_comp_II[j, n]=1. (84)

For each process j, define two thresholds, slot_comp_II _{thres, min} [j] and slot_comp_II _{thres, max} [j], so that:

$\mathrm{<span\; class="notranslate">\; slot</span>}<span\; class="notranslate">\; \_</span>\mathrm{<span\; class="notranslate">\; comp</span>}<span\; class="notranslate">\; \_</span>{\mathrm{<span\; class="notranslate">\; II</span>}}_{\mathrm{<span\; class="notranslate">\; thres</span>}<span\; class="notranslate">\; ,</span>\mathrm{<span\; class="notranslate">\; min</span>}}<span\; class="notranslate">\; [</span>\mathrm{<span\; class="notranslate">\; j</span>}<span\; class="notranslate">\; ]</span><span\; class="notranslate">\; \&le;</span>\mathrm{<span\; class="notranslate">\; slot</span>}<span\; class="notranslate">\; \_</span>\mathrm{<span\; class="notranslate">\; comp</span>}<span\; class="notranslate">\; \_</span>\mathrm{<span\; class="notranslate">\; II</span>}<span\; class="notranslate">\; [</span>\mathrm{<span\; class="notranslate">\; j</span>}<span\; class="notranslate">\; ,</span>\mathrm{<span\; class="notranslate">\; no</span>}<span\; class="notranslate">\; ]</span><span\; class="notranslate">\; \&le;</span>{\mathrm{<span\; class="notranslate">\; slot</span>}<span\; class="notranslate">\; \_</span>\mathrm{<span\; class="notranslate">\; comp</span>}<span\; class="notranslate">\; \_</span>\mathrm{<span\; class="notranslate">\; II</span>}}_{\mathrm{<span\; class="notranslate">\; thres</span>}<span\; class="notranslate">\; ,</span>\mathrm{<span\; class="notranslate">\; max</span>}}<span\; class="notranslate">\; [</span>\mathrm{<span\; class="notranslate">\; j</span>}<span\; class="notranslate">\; ]</span><span\; class="notranslate">\; ,</span><span\; class="notranslate">\; \&ForAll;</span>\mathrm{<span\; class="notranslate">\; j</span>}<span\; class="notranslate">\; ,</span><span\; class="notranslate">\; \&ForAll;</span>\mathrm{<span\; class="notranslate">\; no</span>}<span\; class="notranslate">\; -</span><span\; class="notranslate">\; -</span><span\; class="notranslate">\; -</span><span\; class="notranslate">\; (</span>\mathrm{<span\; class="notranslate">\; 85</span>}<span\; class="notranslate">\; )</span>$

At the beginning of each round, the processes are divided into four groups as given in Table 5.

table 5

Group ndef_bits_r_flow≥ ndef_slots_r_flow≥

ndef_bits_r_{thres, min} ndef_slots_r_{thres, min} Group I yes no Group II no yes Group III yes yes Group IV no no

At the beginning of any round n, for each process j belonging to group II or IV, use slot_comp[j,n]=1. At the beginning of round n, for each process j belonging to group I, apply the following formula:

slot_comp[j,n]=slot_comp_I[j,n]. (86)

If the starting process j at round n belongs to group III, the following formula applies:

slot_comp[j, n]=slot_comp_I[j, n]*slot_comp_II[j, n] (87)

The process then calculates the adaptive weight of process j, where the adaptive weight of the non-empty queue in the nth round is as follows:

$\mathrm{<span\; class="notranslate">\; aw</span>}<span\; class="notranslate">\; [</span>\mathrm{<span\; class="notranslate">\; j</span>}<span\; class="notranslate">\; ,</span>\mathrm{<span\; class="notranslate">\; no</span>}<span\; class="notranslate">\; ]</span><span\; class="notranslate">\; =</span>\mathrm{<span\; class="notranslate">\; slot</span>}<span\; class="notranslate">\; \_</span>\mathrm{<span\; class="notranslate">\; comp</span>}<span\; class="notranslate">\; [</span>\mathrm{<span\; class="notranslate">\; j</span>}<span\; class="notranslate">\; ,</span>\mathrm{<span\; class="notranslate">\; no</span>}<span\; class="notranslate">\; ]</span><span\; class="notranslate">\; *</span>\mathrm{<span\; class="notranslate">\; w</span>}<span\; class="notranslate">\; [</span>\mathrm{<span\; class="notranslate">\; j</span>}<span\; class="notranslate">\; ]</span><span\; class="notranslate">\; *</span>\frac{\mathrm{<span\; class="notranslate">\; r</span>}<span\; class="notranslate">\; [</span>\mathrm{<span\; class="notranslate">\; j</span>}<span\; class="notranslate">\; ]</span>}{{\mathrm{<span\; class="notranslate">\; r</span>}}_{\mathrm{<span\; class="notranslate">\; min</span>}<span\; class="notranslate">\; ,</span>\mathrm{<span\; class="notranslate">\; no</span>}}}<span\; class="notranslate">\; ,</span><span\; class="notranslate">\; \&ForAll;</span>\mathrm{<span\; class="notranslate">\; j</span>}<span\; class="notranslate">\; \&Element;</span>\mathrm{<span\; class="notranslate">\; B</span>}<span\; class="notranslate">\; [</span>\mathrm{<span\; class="notranslate">\; no</span>}<span\; class="notranslate">\; ]</span><span\; class="notranslate">\; -</span><span\; class="notranslate">\; -</span><span\; class="notranslate">\; -</span><span\; class="notranslate">\; (</span>\mathrm{<span\; class="notranslate">\; 88</span>}<span\; class="notranslate">\; )</span>$

Here, r _min,n = min{r[k]; k: k∈B[n]}. For each flow j, define a threshold aw _thres,max [j] and use this threshold to ensure:

$\mathrm{<span\; class="notranslate">\; aw</span>}<span\; class="notranslate">\; [</span>\mathrm{<span\; class="notranslate">\; j</span>}<span\; class="notranslate">\; ,</span>\mathrm{<span\; class="notranslate">\; no</span>}<span\; class="notranslate">\; ]</span><span\; class="notranslate">\; \&le;</span>{\mathrm{<span\; class="notranslate">\; aw</span>}}_{\mathrm{<span\; class="notranslate">\; thres</span>}<span\; class="notranslate">\; ,</span>\mathrm{<span\; class="notranslate">\; max</span>}}<span\; class="notranslate">\; [</span>\mathrm{<span\; class="notranslate">\; j</span>}<span\; class="notranslate">\; ]</span><span\; class="notranslate">\; ,</span><span\; class="notranslate">\; \&ForAll;</span>\mathrm{<span\; class="notranslate">\; j</span>}<span\; class="notranslate">\; ,</span><span\; class="notranslate">\; \&ForAll;</span>\mathrm{<span\; class="notranslate">\; no</span>}<span\; class="notranslate">\; .</span><span\; class="notranslate">\; -</span><span\; class="notranslate">\; -</span><span\; class="notranslate">\; -</span><span\; class="notranslate">\; (</span>\mathrm{<span\; class="notranslate">\; 89</span>}<span\; class="notranslate">\; )</span>$

Next, these adaptive weights are applied to calculate the number of slots that will be allocated to each process and the length of each round such that:

$\mathrm{<span\; class="notranslate">\; sloc</span>}<span\; class="notranslate">\; \_</span>\mathrm{<span\; class="notranslate">\; alloc</span>}<span\; class="notranslate">\; [</span>\mathrm{<span\; class="notranslate">\; j</span>}<span\; class="notranslate">\; ,</span>\mathrm{<span\; class="notranslate">\; no</span>}<span\; class="notranslate">\; ]</span><span\; class="notranslate">\; \&Proportional;</span>\mathrm{<span\; class="notranslate">\; aw</span>}<span\; class="notranslate">\; [</span>\mathrm{<span\; class="notranslate">\; j</span>}<span\; class="notranslate">\; ,</span>\mathrm{<span\; class="notranslate">\; no</span>}<span\; class="notranslate">\; ]</span><span\; class="notranslate">\; ,</span><span\; class="notranslate">\; \&ForAll;</span>\mathrm{<span\; class="notranslate">\; j</span>}<span\; class="notranslate">\; ,</span>\mathrm{<span\; class="notranslate">\; j</span>}<span\; class="notranslate">\; :</span>\mathrm{<span\; class="notranslate">\; j</span>}<span\; class="notranslate">\; \&Element;</span>\mathrm{<span\; class="notranslate">\; B</span>}<span\; class="notranslate">\; [</span>\mathrm{<span\; class="notranslate">\; no</span>}<span\; class="notranslate">\; ]</span><span\; class="notranslate">\; -</span><span\; class="notranslate">\; -</span><span\; class="notranslate">\; -</span><span\; class="notranslate">\; (</span>\mathrm{<span\; class="notranslate">\; 90</span>}<span\; class="notranslate">\; )</span>$

$\underset{\mathrm{<span\; class="notranslate">\; j</span>}<span\; class="notranslate">\; :</span>\mathrm{<span\; class="notranslate">\; j</span>}<span\; class="notranslate">\; \&Element;</span>\mathrm{<span\; class="notranslate">\; B</span>}<span\; class="notranslate">\; [</span>\mathrm{<span\; class="notranslate">\; no</span>}<span\; class="notranslate">\; ]</span>}{\mathrm{<span\; class="notranslate">\; \&Sigma;</span>}}\mathrm{<span\; class="notranslate">\; slot</span>}<span\; class="notranslate">\; \_</span>\mathrm{<span\; class="notranslate">\; alloc</span>}<span\; class="notranslate">\; [</span>\mathrm{<span\; class="notranslate">\; j</span>}<span\; class="notranslate">\; ,</span>\mathrm{<span\; class="notranslate">\; no</span>}<span\; class="notranslate">\; ]</span><span\; class="notranslate">\; \&le;</span>\mathrm{<span\; class="notranslate">\; round</span>}<span\; class="notranslate">\; \_</span>\mathrm{<span\; class="notranslate">\; len</span>}<span\; class="notranslate">\; [</span>\mathrm{<span\; class="notranslate">\; no</span>}<span\; class="notranslate">\; ]</span><span\; class="notranslate">\; \&le;</span>\mathrm{<span\; class="notranslate">\; round</span>}<span\; class="notranslate">\; \_</span>\mathrm{<span\; class="notranslate">\; len</span>}<span\; class="notranslate">\; \_</span>\mathrm{<span\; class="notranslate">\; thres</span>}<span\; class="notranslate">\; ,</span><span\; class="notranslate">\; \&ForAll;</span>\mathrm{<span\; class="notranslate">\; no</span>}<span\; class="notranslate">\; .</span><span\; class="notranslate">\; -</span><span\; class="notranslate">\; -</span><span\; class="notranslate">\; -</span><span\; class="notranslate">\; (</span>\mathrm{<span\; class="notranslate">\; 91</span>}<span\; class="notranslate">\; )</span>$

Scheduling rules for each round

Once each process has been assigned, the number of slots in a round and the length of the round have been calculated. The next step is to select the processes to be served in any given time slot. In any given time slot m in round n, if a packet selected in one of the previous time slots is still being served, then there is no need to select a new flow to serve. On the other hand, if no packet is being served in this time slot m of round n, the flow to be served is selected as follows. For each slot m for which the scheduler needs to select a new process to serve, and for each process j, compute the selection metric for slot m of the nth round of process j as follows,

$\mathrm{<span\; class="notranslate">\; YY</span>}<span\; class="notranslate">\; [</span>\mathrm{<span\; class="notranslate">\; j</span>}<span\; class="notranslate">\; ,</span>\mathrm{<span\; class="notranslate">\; no</span>}<span\; class="notranslate">\; ,</span>\mathrm{<span\; class="notranslate">\; m</span>}<span\; class="notranslate">\; ]</span><span\; class="notranslate">\; =</span>\mathrm{<span\; class="notranslate">\; c</span>}<span\; class="notranslate">\; [</span>\mathrm{<span\; class="notranslate">\; j</span>}<span\; class="notranslate">\; ,</span>\mathrm{<span\; class="notranslate">\; m</span>}<span\; class="notranslate">\; ,</span>\mathrm{<span\; class="notranslate">\; DRC</span>}<span\; class="notranslate">\; [</span>\mathrm{<span\; class="notranslate">\; j</span>}<span\; class="notranslate">\; ,</span>\mathrm{<span\; class="notranslate">\; m</span>}<span\; class="notranslate">\; ]</span><span\; class="notranslate">\; ]</span><span\; class="notranslate">\; *</span>\mathrm{<span\; class="notranslate">\; wait</span>}<span\; class="notranslate">\; \_</span>\mathrm{<span\; class="notranslate">\; comp</span>}<span\; class="notranslate">\; [</span>\mathrm{<span\; class="notranslate">\; j</span>}<span\; class="notranslate">\; ,</span>\mathrm{<span\; class="notranslate">\; no</span>}<span\; class="notranslate">\; ,</span>\mathrm{<span\; class="notranslate">\; m</span>}<span\; class="notranslate">\; ]</span><span\; class="notranslate">\; *</span>\mathrm{<span\; class="notranslate">\; DRC</span>}<span\; class="notranslate">\; [</span>\mathrm{<span\; class="notranslate">\; j</span>}<span\; class="notranslate">\; ,</span>\mathrm{<span\; class="notranslate">\; m</span>}<span\; class="notranslate">\; ]</span><span\; class="notranslate">\; ,</span><span\; class="notranslate">\; \&ForAll;</span>\mathrm{<span\; class="notranslate">\; no</span>}<span\; class="notranslate">\; ,</span><span\; class="notranslate">\; -</span><span\; class="notranslate">\; -</span><span\; class="notranslate">\; -</span><span\; class="notranslate">\; (</span>\mathrm{<span\; class="notranslate">\; 92</span>}<span\; class="notranslate">\; )</span>$

So that j∈B[n] and slots_served[j,n]<θ(j)*slots_alloc[j,n], here, θ(j) is pre-specified for each process j, and wait_comp is given to the process Improve wait compensation for its latency bounds. Let wait[j,n,m] be the waiting time of the top packet of the start flow j in the slot m of the nth round.

$\mathrm{<span\; class="notranslate">\; wait</span>}<span\; class="notranslate">\; \_</span>\mathrm{<span\; class="notranslate">\; comp</span>}<span\; class="notranslate">\; [</span>\mathrm{<span\; class="notranslate">\; j</span>}<span\; class="notranslate">\; ,</span>\mathrm{<span\; class="notranslate">\; no</span>}<span\; class="notranslate">\; ,</span>\mathrm{<span\; class="notranslate">\; m</span>}<span\; class="notranslate">\; ]</span><span\; class="notranslate">\; =</span>\frac{\mathrm{<span\; class="notranslate">\; wait</span>}<span\; class="notranslate">\; [</span>\mathrm{<span\; class="notranslate">\; j</span>}<span\; class="notranslate">\; ,</span>\mathrm{<span\; class="notranslate">\; no</span>}<span\; class="notranslate">\; ,</span>\mathrm{<span\; class="notranslate">\; m</span>}<span\; class="notranslate">\; ]</span>}{\mathrm{<span\; class="notranslate">\; wait</span>}<span\; class="notranslate">\; \_</span>\mathrm{<span\; class="notranslate">\; avg</span>}<span\; class="notranslate">\; [</span>\mathrm{<span\; class="notranslate">\; no</span>}<span\; class="notranslate">\; ,</span>\mathrm{<span\; class="notranslate">\; m</span>}<span\; class="notranslate">\; ]</span>}<span\; class="notranslate">\; ,</span><span\; class="notranslate">\; \&ForAll;</span>\mathrm{<span\; class="notranslate">\; j</span>}<span\; class="notranslate">\; ,</span>\mathrm{<span\; class="notranslate">\; j</span>}<span\; class="notranslate">\; :</span>\mathrm{<span\; class="notranslate">\; j</span>}<span\; class="notranslate">\; \&Element;</span>{\mathrm{<span\; class="notranslate">\; B</span>}}_{\mathrm{<span\; class="notranslate">\; j</span>}}<span\; class="notranslate">\; -</span><span\; class="notranslate">\; -</span><span\; class="notranslate">\; -</span><span\; class="notranslate">\; (</span>\mathrm{<span\; class="notranslate">\; 93</span>}<span\; class="notranslate">\; )</span>$

And at the beginning of time slot m of round n, process j has at least one packet pending. Next, compute for process k:

$\mathrm{<span\; class="notranslate">\; wait</span>}<span\; class="notranslate">\; \_</span>\mathrm{<span\; class="notranslate">\; avg</span>}<span\; class="notranslate">\; [</span>\mathrm{<span\; class="notranslate">\; no</span>}<span\; class="notranslate">\; ,</span>\mathrm{<span\; class="notranslate">\; m</span>}<span\; class="notranslate">\; ]</span><span\; class="notranslate">\; =</span>\frac{\underset{\mathrm{<span\; class="notranslate">\; k</span>}}{\mathrm{<span\; class="notranslate">\; \&Sigma;</span>}}\mathrm{<span\; class="notranslate">\; wait</span>}<span\; class="notranslate">\; [</span>\mathrm{<span\; class="notranslate">\; k</span>}<span\; class="notranslate">\; ,</span>\mathrm{<span\; class="notranslate">\; no</span>}<span\; class="notranslate">\; ,</span>\mathrm{<span\; class="notranslate">\; m</span>}<span\; class="notranslate">\; ]</span>}{\mathrm{<span\; class="notranslate">\; wait</span>}<span\; class="notranslate">\; \_</span>\mathrm{<span\; class="notranslate">\; num</span>}<span\; class="notranslate">\; [</span>\mathrm{<span\; class="notranslate">\; no</span>}<span\; class="notranslate">\; ,</span>\mathrm{<span\; class="notranslate">\; m</span>}<span\; class="notranslate">\; ]</span>}<span\; class="notranslate">\; ,</span><span\; class="notranslate">\; -</span><span\; class="notranslate">\; -</span><span\; class="notranslate">\; -</span><span\; class="notranslate">\; (</span>\mathrm{<span\; class="notranslate">\; 94</span>}<span\; class="notranslate">\; )</span>$

So that k∈B[n], and the number of these processes is wait_num[n, m]. For each process j, the two thresholds of wait_comp _{thres, min} [j] and wait_comp _{thres, max} [f] are assigned and used to ensure

$\mathrm{<span\; class="notranslate">\; wait</span>}<span\; class="notranslate">\; \_</span>{\mathrm{<span\; class="notranslate">\; comp</span>}}_{\mathrm{<span\; class="notranslate">\; thres</span>}<span\; class="notranslate">\; ,</span>\mathrm{<span\; class="notranslate">\; min</span>}}<span\; class="notranslate">\; [</span>\mathrm{<span\; class="notranslate">\; j</span>}<span\; class="notranslate">\; ]</span><span\; class="notranslate">\; \&le;</span>\mathrm{<span\; class="notranslate">\; wait</span>}<span\; class="notranslate">\; \_</span>\mathrm{<span\; class="notranslate">\; comp</span>}<span\; class="notranslate">\; [</span>\mathrm{<span\; class="notranslate">\; j</span>}<span\; class="notranslate">\; ,</span>\mathrm{<span\; class="notranslate">\; no</span>}<span\; class="notranslate">\; ,</span>\mathrm{<span\; class="notranslate">\; m</span>}<span\; class="notranslate">\; ]</span><span\; class="notranslate">\; \&le;</span>\mathrm{<span\; class="notranslate">\; wait</span>}<span\; class="notranslate">\; \_</span>{\mathrm{<span\; class="notranslate">\; comp</span>}}_{\mathrm{<span\; class="notranslate">\; thres</span>}<span\; class="notranslate">\; ,</span>\mathrm{<span\; class="notranslate">\; max</span>}}<span\; class="notranslate">\; [</span>\mathrm{<span\; class="notranslate">\; j</span>}<span\; class="notranslate">\; ]</span><span\; class="notranslate">\; ,</span><span\; class="notranslate">\; \&ForAll;</span>\mathrm{<span\; class="notranslate">\; m</span>}<span\; class="notranslate">\; ,</span><span\; class="notranslate">\; \&ForAll;</span>\mathrm{<span\; class="notranslate">\; no</span>}<span\; class="notranslate">\; ,</span><span\; class="notranslate">\; \&ForAll;</span>\mathrm{<span\; class="notranslate">\; j</span>}<span\; class="notranslate">\; .</span><span\; class="notranslate">\; -</span><span\; class="notranslate">\; -</span><span\; class="notranslate">\; -</span><span\; class="notranslate">\; (</span>\mathrm{<span\; class="notranslate">\; 95</span>}<span\; class="notranslate">\; )</span>$

The flow with the largest selection metric YY is selected by the AFS scheduler to serve in any given time slot.

An AN element according to one embodiment is shown in FIG. 20 . The AN element 500 receives application process data and processes the data for transmission to the user. The AN element 500 schedules multiple application processes, each of which has QoS requirements. Note that, as noted above, application processes may include best-effort processes. The AN element 500 includes a process classification unit 502 adapted to identify traffic profiles and QoS profiles associated with processes, and to map processes to class (or QSG) processes. Flow classifier unit 502 is coupled to scheduler 504 , admission control unit 510 and QoS monitor 506 . The scheduler 504 may implement any of various scheduling algorithms, including, but not limited to, proportional fair (PF) algorithms and adaptive weighted PF algorithms. The admission control unit 510 applies an admission control scheme to the application flows received by the AN 500. Admission control unit 510 evaluates each new flow requested based on QoS and network statistics, and determines whether sufficient resources are available to support the new flow. The adaptation unit is coupled to the admission control unit, where the ASF is updated. Adaptation unit 512 is adapted to make preemption decisions on currently active application processes. Preemption takes into account the performance of a given flow with respect to data rate, time slot used, and other QoS and network statistics flow. The QoS monitor is suitable for monitoring the QoS requirements of incoming application flows. Note that the AN element 500 typically receives multiple flows and selects between them for transmission to the user. The scheduler 504 receives information from the admission control unit 510 on whether a new flow is admitted or not. The scheduler 504 receives QoS statistics and other information from the QoS monitor 506, wherein the scheduler 504 applies the QoS information to select a flow for transmission.

Presented herein are methods and apparatus for admission control, preemption and scheduling of application flows in a wireless communication system. Admission control takes into account the data rate requested by the new process and compares this to available resources. Once admitted, the flows are presented to the scheduler, which is adapted to perform per-flow and per-user analysis to select users for transmission in each time slot or specified time period.

Those of skill in the art would understand that information and signals may be represented in a variety of different ways and techniques. For example, data, instructions, commands, information, signals, bits, symbols, and chips that may be referenced throughout the above description may be represented by voltages, currents, electromagnetic waves, magnetic fields or particles, optical fields or particles, or any combination thereof.

In addition, those skilled in the art would appreciate that the various illustrative logical blocks, modules, circuits, and algorithm steps described in connection with the various embodiments explained herein may be implemented as electronic hardware, computer software, or both. combination. To clearly illustrate this interchangeability of hardware and software, various illustrative components, blocks, modules, circuits, and steps have been described above generally in terms of their functionality. Whether such functionality is implemented as hardware or software depends upon the particular application and design constraints governing the overall system. Skilled artisans may implement the described functionality in varying ways for each particular application, but such implementation decisions should not be interpreted as causing a departure from the scope of the present invention.

The various exemplary logical blocks, modules, and circuits described in connection with the various embodiments disclosed herein may be implemented with general purpose processors, digital signal processors (DSPs), application specific integrated circuits (ASICs), field programmable gate arrays (FPGAs), ) or other programmable logic devices, discrete gate or transistor logic, discrete hardware components, or any combination thereof designed to perform the various functions described herein are implemented or performed. A general-purpose processor may be a microprocessor, but in the alternative, the processor may be any conventional processor, controller, microcontroller, or state machine. A processor may be implemented as a combination of several computing devices, eg, a combination of a DSP and a microprocessor, multiple microprocessors, one or more microprocessors in conjunction with a DSP core, or any other such configuration.

The steps of the methods or algorithms described in conjunction with the various embodiments disclosed herein may be embodied directly in hardware, in software modules executed by a processor, or in a combination of both. A software module may reside in RAM memory, flash memory, ROM memory, EPROM memory, EEPROM memory, registers, hard disk, a removable disk, a CD-ROM, or any other form of storage medium known in the art. An exemplary storage medium is coupled to the processor such that the processor can read information from, and write information to, the storage medium. Alternatively, the storage medium may be integrated into the processor. The processor and storage medium can reside in an ASIC. The ASIC may reside in a user terminal. Alternatively, the processor and storage medium may reside in the user terminal as discrete components.

The above description of the disclosed embodiments is provided to enable any person skilled in the art to make or use the 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 departing from the spirit and scope of the invention. Thus, the intention is not to limit the present invention to the embodiments shown herein but to accord it the widest scope consistent with the principles and novel features disclosed herein.

Claims (8)

1. A method of admission control in a communication system supporting applications of Internet Protocol IP, said communication system comprising an access network AN and a plurality of access terminals AT, each of said ATs sending The AN sends a request data rate, the communication system supports an application flow with QoS requirements for the AT, the method comprising: determining available resources in the communication system; receiving a request for a first application flow having a first traffic profile and a first QoS profile; determining whether the available resources support the request for the first application process; rejecting the first application process if the first application process has a corresponding data rate greater than an average requested data rate; and If the corresponding data rate is not greater than the average requested data rate, and if the available resources support the request for the first application process, allowing access to the first application process, determining the communication system Available resources in include: determining reserved resources in the communication system; comparing the reserved resources to the capacity of the communication system; and The available resources are determined as the difference between the capacity and the reserved resources. 2. The method of claim 1, further comprising: An adaptive subscription factor for the first application process is determined. 3. The method of claim 2, further comprising: The adaptive subscription factor is updated based on the QoS statistics of the first application process. 4. The method of claim 3, further comprising: determining QoS statistics for the first application process; comparing the QoS statistics of the first application process with other current processes in a sector; and The available resources and reserved resources are updated responsive to a comparison of the QoS statistics of the first application process with other current processes in the sector. 5. The method of claim 4, further comprising: determining whether a user of the first application process is present in a sector of the communication system; and determining a sampling duration for said first application process, Wherein, determining the QoS statistics of the first application process includes: Determining QoS statistics for the first application process during the sampling duration. 6. The method of claim 5, wherein a first sampling duration is associated with a rate violation and a second sampling duration is associated with a delay violation. 7. The method of claim 5, wherein comparing the QoS statistics of the first application process with other current processes in the sector comprises: calculating the fraction of first slots used by flows with QoS requirements during a sampling period; calculating a second fraction of slots used by the first application process during the sampling period; calculating a third score for a QoS process corresponding to the QoS statistic of said first application process; comparing the third score to a corresponding threshold; and The adaptive subscription is evaluated in response to comparing the third score to a corresponding threshold. 8. An apparatus for admission control in a communication system supporting Internet Protocol IP applications, said communication system comprising an access network AN and a plurality of access terminals AT, each of said ATs sending a request data rate to the AN, the communications system supporting an application flow with a QoS requirement for the AT, the device comprising: means for determining available resources in said communication system; means for receiving a request for a first application flow having a first traffic profile and a first QoS profile; means for determining whether the available resources support the request for the first application process; means for rejecting said first application flow if said first application flow has a corresponding data rate greater than said average requested data rate; means for allowing entry to the first application process if the corresponding data rate is not greater than the average requested data rate and the available resources support the request for the first application process, Wherein the means for determining available resources in the communication system include: means for determining reserved resources in said communication system; means for comparing the reserved resources with the capacity of the communication system; and means for determining said available resources as the difference between said capacity and said reserved resources.

Images