Title of Invention	METHODS AND SYSTEM FOR EFFICIENT PER-FLOW RESOURCE ALLOCATION IN WIRELESS MULTIMEDIA NETWORKS
Abstract	The present invention relates to methods and system for efficient resource allocation to satisfy QoS requirements of diverse types of applications in 3G wireless multimedia networks. These methods also control the manner in which time slots are allocated to different flows (and associated applications). Each of these allows a different way in which time slots are allocated and results in different service behavior for the users (but still meet their QoS requirements). Network operators can formulate different types of service level agreements using these different fairness criteria for 3G wireless networks. The present invention proposes methods and an adaptive scheduling system to be used in the wireless multimedia networks. The present invention specifies adaptive QoS scheduling methods and different fairness criteria which allow to provide QoS guarantees to diverse types of applications in wireless networks and allow network operators to offer different types of service level agreements.

Title of Invention

METHODS AND SYSTEM FOR EFFICIENT PER-FLOW RESOURCE ALLOCATION IN WIRELESS MULTIMEDIA NETWORKS

Abstract

The present invention relates to methods and system for efficient resource allocation to satisfy QoS requirements of diverse types of applications in 3G wireless multimedia networks. These methods also control the manner in which time slots are allocated to different flows (and associated applications). Each of these allows a different way in which time slots are allocated and results in different service behavior for the users (but still meet their QoS requirements). Network operators can formulate different types of service level agreements using these different fairness criteria for 3G wireless networks. The present invention proposes methods and an adaptive scheduling system to be used in the wireless multimedia networks. The present invention specifies adaptive QoS scheduling methods and different fairness criteria which allow to provide QoS guarantees to diverse types of applications in wireless networks and allow network operators to offer different types of service level agreements.

Full Text	I FIELD OF TECHNOLOGY This invention relates to the field of Mobile Wireless Multimedia Networks. Further, this invention in general relates to the 3G Wireless Multimedia Networks. More particularly, this invention encompasses methods and system for efficient per-flow resource allocation in 3G wireless multimedia networks. PRESENT STATE OF ART Some of the 3G wireless networking technologies are CDMA2000 IxEV-DV, CDMA2000 1xEV-D0 and WCDMA. A schematic diagram of a 3G-like network is shown in Figure 1. Here, MS is the mobile station, BS is the base station, PCF is the packet control function block and WER is the wireless edge router. An IP networking architecture for this type of networks is described in "wireless IP network standard", www.3gpp2.org 3GPP2 P.S0001-B. The BS essentially includes the BSC and the BTS as shown in Figure 1 Protocol end points of a 3G network are shown in the Figure 2. As shown there, a PPP connection is established between the MS and the PDSN. It is typical to operate a 3G network with a received signal-to-noise ratio that results in a physical layer packet error rate of approximately one-percent. A negative acknowledgement (NACK) based radio link protocol (RLP) uses a form of automatic repeat request (ARQ) to achieve this. A link control protocol (LOP) is used to negotiate radio link protocols and options to control the session. A stream control protocol (SCP) is used to transmit the RLP NACKs when missing RLP data is detected. In current systems, BTS may contain a set of queues to buffer packets belonging to different flows or mobile stations. Note that IP packets in the BSC are typically segmented to Medium Access Control (MAC) packets in the BTS. There is a scheduler at the BTS that decides the manner in which these queues are served. A wireless multimedia network would typically support several types of applications such as multimedia conferencing, multimedia streaming, web browsing, wireless games, File Transfer Protocol (FTP), Voice over Internet Protocol (VoIP) etc. Some applications, such as, multimedia conferencing and streaming consist of several flows. For our purposes here, a flow can be a microflow or a macroflow. Here, a microflow is described via the following 5-tuple: IP source address, IP destination address, Layer 4 protocol type (like Transmission control Protocol (TCP), Universal Datagram Protocol (UDP) etc.), Layer 4 source port number, and Layer 4 destination port number. A macroflow is described via the following 3-tuple: IP source address, IP destination address, and Layer 4 protocol type. Multimedia applications can have the following types of flows: - Forward link data flow for audio (FLDF-A), - Forward link data flow for video (FLDF-V), - Reverse link data flow for audio (RLDF-A), - Reverse link data flow for video (RLDF-V), - Forward link control flow for audio (FLCF-A), - FoHA/ard link control flow for video (FLCF-V), - Reverse link control flow for audio (RLCF-A), - Reverse link control flow for video (RLCF-V). Here, forward link data flows (FLDFs) are FLDF-A and FLDF-V. Reverse link data flows (RLDFs) are: RLDF-A and RLDF-V. Similarly, forward link control flows (FLCF) are: FLCF-A and FLCF-V. Reverse link control flows are: RLCF-A and RLCF-V. These control packets are used to provide feedback to the source and destination nodes about the received quality of audio and video flows. They are also used to control the rate at which data is sent from the source node to the destination node. Many data (and some control) flows have certain QoS requirements that are specified via some of the following parameters: delay bound, delay jitter, average delay, throughput, and packet loss. Multimedia applications typically have requirements in the terms of delay bound, delay jitter, throughput and packet loss. These multimedia applications typically use UDP/Real time transport Protocol (RTP) protocols for transport of data. For some other TCP based applications, such as web browsing, keeping average delay below some pre-specified value is desirable. A flow's traffic can be described via its traffic profile. A flow is considered to be conforming if it obeys its traffic profile. Otherwise, it Is considered to be non-conforming. The scheduler at the BTS works on the MAC packet queues but is intended to provide QoS guarantees for the IP packets of different flows. In a 3G network, time is typically divided into fixed length time slots. Each of these slots is of same length. For example, slot length in a CDMA2000 1xEV-D0 networks is approximately 1.67 millisecond. Each mobile device informs the base station about the rate at which it can accept data in each of this slot on forward link. This rate can vary rapidly in a wide-area wireless network. Suppose A^[n] is the maximum allowed rate at which mobile device k can accept data in slot n from the base station. A forward link, scheduling method was proposed in "Proportional fairness scheduler- David Dtse". It computes the following metric for each mobile: Here, M^[n] is the metric for mobile device k, and R^^avgi^) '^ computed using an exponentially weighted moving average filter: Here, t^ ^\IT^, T^ is a time constant such that 0^ to be served in slot n, then R^[ri\ is set to zero. OthenA/ise, it is set to the rate at which mobile k was served in slot k. This scheduler selects a mobile with the maximum value of the metric, MJ«], to serve in slot n. In some 3G wireless networking technologies such as CDMA2000, the maximum allowed rate, A^[n\, is specified via two parameters: number of bytes in physical layer packet that can be sent over the air-interface starting from this slot n and the number of slots that would be taken by this packet. In this case, if mobile k is selected to be served via the forward link scheduler and the mobile has specified that it would need more than one slot for transmission, then it would be served for the specified number of slots (or until the physical layer packet transmission is over or whichever occurs earlier). Some data rates for a CDMA2000 systems are shown in the table 1 below: LIMITATIONS An application can consist of several flows and some of these flows have QoS (Quality of Service) requirements that need to be satisfied. Let arr^{p) be the arrival time of the first bit of the IP packet p of flow k at the BSC, and dep^{p) be the departure time of the last bit of the IP packet p of flow k from the BTS. Each flow k can specify some of the following QoS requirements: • Delay Bound {db^^) - Packets of each forward link flow move from the CN to the BSC and experience some queuing delay at the intermediate nodes. This part of the network is typically a wired network. After this packets get queued in the base station (first at BSC and then at the BTS), and experience variable delay before they are sent out from the BTS to the MS. The delay bound, that is considered here, is the maximum delay for any IP packet of that flow at the BSC and BTS. For flow k, it is equal to msixp{dep^{p)-arrf^(p)}. A user would typically provide bound on the end-to-end delay, and a target delay bound from the BSC to the MS can be computed from that. To do this, a network operator could specify delay bound for that flow in wired part of the network, from the CN to the BSC and subtract this from the end-to-end delay bound to compute delay bound for that flow from the BSC to the MS. • Average Delay (AvgDJ- It is the average delay experienced by the IP packets of flow k in the base station (i.e. BSC and BTS) queues. • Delay Jitter (djtr^) - It is the delay jitter experienced by packets of flow k. For flow k, djtr, ^m^x^{abs[(dep,(p)-arr,(p))-{dep,(p^l)-~arr,(p + l))]}. Here, p and p+1 are consecutive IP packets that have arrived at the BSC at time arr^ip) and arr^(p + 1)for flow k. • Required Rate {reqrate^)- It is the minimum required rate by flow k. A time scale, tSf^, is also specified for each flow k on which this rate has to be delivered to that flow. • Desired Rate {desrate^) - It is the desired rate by flow k. For some applications, such as MPEG-4. it is useful to specify two rate parameters: required rate and desired rate. Here required rate could correspond to the rate needed when only the base stream is used in an MPEG-4 flow and the desired rate can correspond to the rate when base stream as well as enhanced streams are used in MPEG-4 flow. For the simple case, when all mobile stations are experiencing same channel conditions and Af^{n] = Aj[n\yk,\/j for each slot n, and the scheduling method is used where a mobile with the maximum value of the metric MJ«] (where A \riMk[Yi\^—^^^^,VA:,Vn) is selected to be served, this scheduler would serve such that equal throughput is given to each of the mobile stations, if queues for all the mobile stations are non-empty (i.e. there are always packets to be sent). In a way, that method would allocate same number of slots to each mobile device under these conditions. This is clearly not desirable for applications which have diverse QoS (in terms of delay bound, delay jitter, average delay, throughput) requirements. In the general case, i.e. when each mobile device could be experiencing different channel conditions, this scheduling method would again fail to meet QoS requirements of diverse types of applications. In general, it is not possible to give different types of QoS guarantees (on delay bound, average delay, delay jitter, and throughput) to application flows using the above scheduling method. These QoS guarantees are important for several applications such as multimedia conferencing and streaming, VoIP, web browsing, wireless games etc. Real-time applications such as MPEG-4 conferencing and VoIP have stringent requirements on their delay bounds and delay jitter. Video streaming applications such as MPEG-4 streaming also need to have their delay bounded and have tight requirements over their delay jitter. Some other applications such as web browsing that run over HTTP/TCP perform well if average delay in the network is kept low for the corresponding packets. Applications such as FTP need some throughput guarantees from the network. The methods in which the time slots are allocated for over the air transmission (on the BTS - MS hop) to application flows, play a critical role in determining their delay bound, delay jitter, average delay and throughput. Thus it is very important to introduce new scheduling methods which would help to meet QoS requirements of diverse types of applications in 30 wireless multimedia networks. At the same time, it would be good if these methods could help in offering different schemes by which allocation of time slots is governed among competing flows with different traffic characteristics, different QoS requirements and different channel conditions of the associated mobile stations. This way, these will also help network operators in offering different types of service level agreements for QoS management in 3G wireless networks. OBJECTS OF THE INVENTION It is the primary object of the invention to provide methods and system for efficient resource allocation in 3G Mobile Wireless Multimedia Networks. It is another object of the invention to provide the scheduling methods to satisfy the QoS requirement of diverse type of application in 3G wireless multimedia networks. It is another object of the invention to provide the scheduling methods that provide multiple ways for allocating resources to different flows and their associated mobile stations to allow network operators to define different types of fairness criteria and service level agreements in 3G wireless multimedia networks. It is the another object of the invention to provide the methods that provide guaranteed Quality of service to multimedia streaming applications in 30 wireless network. It is the another object of the invention to provide the methods that provide guaranteed QoS to multimedia conferencing applications in 30 wireless networks. It is the another object of the invention to provide the scheduling methods that can improve quality of web browsing applications in 30 wireless networks. It is the another object of the invention to provide the improved methods of media transmission in 30 wireless network. SUMMARY OF THE INVENTION Consider the system as shown in Figure.4. IP packet classifier shown there classifies flows into separate queues. Each queue contains IP packets corresponding to a flow and has QoS requirements for these packets that need to be satisfied. For each queue, there is requirement on some of the following: delay bound, delay jitter, average delay, and throughput (rate). These IP packets are further segmented to MAC packets that are to be transmitted over the air to the mobile devices. An adaptive scheduler is used, as the forward link scheduler for this system that decides which packet has to be sent over the air in each slot. Such a scheduler can also be used for reverse link flows. Also, as channel conditions for mobile stations typically keep varying in a 3G wireless networks, it is quite possible that there can be multiple ways to distribute time slots so that QoS requirements of application flows are met. In such cases, these new scheduling methods provide several ways of allocating slots to application flows. These scheduling methods also provide mechanisms which allow different ways to decide which flows are to be given higher preference over other flows in case the network gets congested and several mobile stations start experiencing bad channel conditions. Thus these methods provide different fairness criteria using which network operators can offer different types of service level agreements for different mobile users (and their flows). The present invention proposes scheduling methods to be used in this fonward link adaptive scheduling module here. In the (detail description of the invention herein below), the flows that only specify their rate requirements are considered. The present invention proposes several methods for these flows. Each of these methods adopts a different design policy and a network operator can decide to use an appropriate one depending upon its objectives. Next, consider the flows that specify their delay bound and delay jitter requirements. The invention proposes methods to be used for these flows in the (detail description of the invention herein below). In the subsequent section, flows that have QoS requirements related to delay bound, delay jitter and throughput are considered. Typically, multimedia conferencing and streaming applications (such as MPEG-4, VoIP etc.) fall in this category. The present invention specifies adaptive scheduling methods that can be used for these flows in the (detail description of the invention herein below). Next the flows that have requirements related to average delay and throughput are considered. Typically, TCP applications such as web browsing (via HTTP protocol) fall in this category. These applications do not have any strict requirements over delay bound but perceived quality seen improves if the average delay of these flows can be kept low. Wireless gaming applications can use the methods described in the (detail description of the invention herein below), depending upon the type of the gaming application. If it is a highly interactive multimedia game, one should use the methods given in the section 5.1. For simple text based games, one could use the methods given in the section 5.4. Several QoS scheduling methods that allow us to provide QoS guarantees to diverse types of applications in wireless networks, are considered. Each of the scheduling method given in the (detail description of the invention herein below) provides a different fairness criteria which governs allocation of resources among competing flows and decides which flow is to be given higher or lower preference than other flows by considering the network condition (especially the channel condition of different mobile stations), QoS received by flows and QoS requirements of flows. Accordingly this invention relates to a method for per-flow QoS management in forward link adaptive scheduling module in a 3G wireless multimedia networks wherein improved per-flow QoS management in 3G wireless multimedia networks is provided, the QoS requirement of flows with rate requirements in 3G networks is satisfied, and wherein the present difficulty in satisfying rate requirements is tackled with guaranteed Quality of Service wherein to control the manner in which time slots are allocated to different flows and associated applications, wherein if a flow is lagging behind its required rate more than another flow, the flow which is lagging more is given higher compensation by computing the metric QoS_M^[n], for each flow k, in each slot n. Accordingly this invention relates to a system for per-flow efficient resource allocation in 3G wireless multimedia networks wherein an adaptive scheduler is used as the forward link scheduler for this system that decides which packet has to be sent over the air in each slot and also serves the reverse link flows, which also implements various methods to provide QoS guarantees to diverse types of applications in wireless networks, for flows with various requirements viz. required rate, delay bound, delay jitter, average delay and desired rate. The other objects, features and advantages of the present invention will be apparent from the accompanying drawings and the detailed description as follows: BRIEF DESCRIPTION OF THE ACCOMPANYING DRAWINGS Fig. 1 relates to the existing architecture of 30 like networks where forward and reverse link flows from MS, through base stations BS and vice versa is shown with there components comprising the base station controller (BSC), base transceiver system (BTS), the point coordination function (PGP), wireless edge router (WER) and the correspondent node (ON); Fig. 2: Protocol end points of a 3G network are shown in the Figure 3. A PPP connection is established between the MS and the PDSN. Physical layer terminates at the MS and the BTS. RLP terminates at the MS and the BSC; Fig, 3: shows the discrete time wireless system wherein each slot "s" each mobile that has data to send informs the access point (BTS) about the rate at which it can be served in that slot. Access point (BTS) needs to decide which mobile (and flow) to serve in each slot. Rate specified by a mobile is typically specified in terms of number of fixed size MAC packets or bytes that can be sent and the number of time slots needed by these packets; Fig. 4: shows a fonward link adaptive scheduler which classifies fiows into separate queues. Each queue contains IP packets corresponding to a flow and has QoS requirements for these packets that need to be satisfied. These IP packets are further segmented to MAC packets that are to be transmitted over the air to the mobile devices. An innovated adaptive scheduler is applied as the forward link scheduler for this system that decides which packet has to be sent over the air in each slot; Fig. 5: shows scheduler operation for flows with rate requirement only; Fig. 6: shows scheduler operation for flows with delay bound and delay jitter requirements; Fig. 7: shows scheduler operation for flows with delay bound, delay jitter and rate requirements; Fig. 8: shows scheduler operation for flows with average delay and rate requirements; Fig, 9: shows the Flow selection by the scheduler. DETAILED DESCRIPTION OF THE INVENTION 5.1. Adaptive scheduling methods for Flows with Rate Requirements only In this section, the flows that specify only the rate requirements are considered. In the system presented here, a flow can specify either only its required rate, or its required rate as well as desired rate. Required rate would typically be the minimum rate needed by an application. Desired rate could be the rate at which user would like to receive the service. This desired rate can not be less than the required rate. Each of the method presented here provide rate guarantees for flows and at the same time provide different ways of allocating resources to these flows with different fairness criteria using which network operators can offer different types of service level agreements. For each flow, a QoS compensation metric is computed. These methods are explained below. Method -1 Let reqrate^ be the required rate specified by flow k. In this method, QoS compensation metric, QoS_M k [n], is computed for each flow k, in each slot n, as follows: This fon/vard link QoS scheduler considers the flows that have non-zero queue length and selects a flow with the maximum value of the metric QoS_M k[n] in each slot n when it needs to select a mobile to serve. Note that this method compensates the flows that are lagging behind their required rate requirements. The lagging flows are compensated in proportion to the normalized difference of their required rate and served rate (normjreqratejac above). If a flow (say, f1) that is lagging (behind its required rate requirement) more than another flow (say, f2), then the flow f1 is given higher compensation (than the flow f2) and the method tends to recover this flow (i.e. f1) earlier (than f2). Method ■ II The method also works to achieve the required rate requirement as in Method - I but tends to do the opposite of what is done there while compensating lagging flows. Specifically, if a flow (say, f1) is lagging more than another flow (say, f2), then flow f2 is given higher compensation and this flow tend to recover earlier than flow f1. In wireless networks, it could happen that some flows (with required rate requirements) are initially admitted in the system after observing channel conditions of the corresponding users but as channel conditions can vary rapidly, it may become not feasible to satisfy QoS requirements of some of these flows for some period of time. In such cases, some network operators may decide to adopt a scheme where they first satisfy QoS requirements of at least those flows who are closer to their required rate requirements than the flows that are lagging more. In such cases, the method given here can be used. For this method, compute the This fonward link QoS scheduler considers the flows that have non-zero queue length and selects a flow with the maximum value of the metric QoS_M k [n] in each slot n when it needs to select a flow to serve. Method - III This method can be used for the case where each flow has specified its required rate as well as desired rate. Compute the metric QoS_M K [n], for each flow k, in each slot n, as follows: If there is at least one flow k, such that its reqrate^ >(l-^s)R^^^^in), for some small constant £>0., then QoS_M k [n] is computed as given earlier in the Method -1 for this slot. Otherwise, this metric is computed as follows: QoS __ Mf^ [n] - norm _ desrate _ fac^ \n\ M^ [/?], VA:, V« Here, norm _ desrate _ fac,^ [n] = \, if desrate^^ 0. OthenA/ise, norm_desrate_fac,^[n] = —^^^(desrate^ -R^^^g{n)\\/n. We choose a suitable value of r,^,,such that desrate, =H,'r,^^^yk. We also have, //^^ = max,{//,}. For each flow k, a threshold norm desrate_fac_th,, is specified and the following is always ensured: norm _ desrate _ fac, \n\ This forward link QoS scheduler considers the flows that have non-zero queue length and selects a flow with the maximum value of the metric QoS_M k[n] in each slot n when it needs to select a flow to serve. Method ■ IV This method should be used for the case where each flow has specified its required as well as desired rate and the network operator wants to adopt a policy where the flows that are closer to their required rate requirement should be recovered earlier than the flows that are lagging more behind their required rate QoS requirement. For this method, compute the metric QoS_M,[n], for each flow k, in each slot n, as follows: If there is at least one flow /c, such that its reqrate,^ >(! + £•)* 7?,^^^ («), for some small constant s>Q, then QoS^M^Xn] is computed as given earlier in the Method - II for this slot. Otherwise, this metric is computed as follows: QoS _ Mf^ [n\ = norm _ desrate _ fac,^ [n] * M, [«], VA:, V« Here, norm_desrate_fac^[n], is as defined in tlie Method - III. This forward link QoS scheduler considers the flows that have non-zero queue length and selects a flow with the maximum value of the metric QoS_M,^[n] in each slot n when it needs to select a flow to serve. Method ■ V In this method, compute the metric, QoS_M,^[n], for each flow k, in each slot n, as follows: If for flow k, regrate^ 0, then QoS__M,[n]=- ^'^^^ ,Vw. Otherwise, A \nQoS __ M^ [n] = norm _ reqrate _ fac,^ [w] * — , V« Here, norm_reqrate_fac,^[n], is as defined in the Method - I and A,avg[«] = ^1 * Mf^] + 0 - ^ci) * A,avg[^ -1]. for some constant r^, such that 0,, This foHA/ard link QoS scheduler considers the flows that have non-zero queue length and selects a flow with the maximum value of the metric QoS_M^[n] in each slot n when it needs to select a flow to serve. This method compensates each lagging flow in proportion to the normalized difference between the required rate and the served rate (as was done in the Method - I) but it does thus in a different manner as it doesn't use M^[n] as was done earlier. It results in a different way of allocating resources (timeslots here) to competing flows and thus in a different fairness definition. Method - VI For this method, compute the metric, QoS_M,^[n], for each flow k, in each slot n, as follows: If for flow k, reqrate^ 0, then QoS_M,{n\^ "^'^^^ ,V^. OthenA^ise, QoS_M,{n] = ? -AW_,VA2 norm _ reqrate _ fac^ [«] A^^avg \^ Here, norm reqrate_fac^\n\ is as defined in the Method -1, Z is as defined in the Method - II, and ^^^,^[«] is as defined in the Method - V. This fonA^ard link QoS scheduler considers the flows that have non-zero queue length and selects a flow with the maximum value of the metric QoS_M^\n\ in each slot n when it needs to select a flow to serve. This method tends to recover flows that are closer to their required rate QoS requirements earlier than the other flows that are lagging behind their required rate requirement (as was done in the Method II) but does not use MJw] as was done earlier. It results in a different way of allocating resources to competing flows and thus in a different fairness definition. Method ■ VII This method can be used when required rate as well as desired rate are specified for each flow. In this method, we compute the metric QoS_M^\n\, for each flow k, in each slot n, as follows: If there is at least one flow k, such that its reqrate^ > (1 + £•) i?^^,^ («), for some small constant f>0., then QoS_M^\n\ is computed as given earlier in the Method - V for this slot. Otherwise, this metric is computed as follows: A \n\ QoS _ M^ \n\ = norm _ desrate _ fac^ [n] * —^^^^, VA:, V« A,avgM Here, norm_desrate_fac^[n\ is as defined in the Method - III and ^^^^^^ is as defined in the Method - V. Method ■ Vm In this method, compute the metric, QoS_Mf^[n], for each flow k, in each slot n, as follows: A flow, f1, that is lagging more than another flow, f2, is given higher compensation than f2 and flow f1 would tend to recover faster than flow f2. Method - IX In this method, compute the metric, QoS_M,^[n], for each flow k, in each slot n, as follows: If for flow k, reqrate,^ 0, then This method results in different allocation of resources (and thus different fairness definition) than the method VIII. Method - X In this method, compute the metric, QoS_Mf^[n], for each flow k, in each slot n, as follows: If for flow k, reqrate^0, then QoS_M^[n] = Af J«],Vw. OthenA/ise, for flow k. This method uses a different compensation factor and results in different allocation of resources to flows than the earlier methods. Method" XI Here we combine the method given above. Suppose each flow has specified its required rate as well as desired rate. As long as there is at least one flow k for which reqrate,^ > 0 + ^)^A,avg(^)' ^^e either Method VIII, Method IX or Method X. Otherwise, use QoS_M,^[n] = norm_desrate_fac,^[n]'^Mf^[n]yri for flow k, where norm_desrate_fac is as defined in the Method III . Method - XII Again consider the case where each flow has specified its required rate as well as desired rate. As long as there is at least one flow k for which reqrate.>{\ + s)R.^(n), use either Method VIII, or Method IX or Method X. Othen/vise, do the following: Qo5_MJn] = MJn], if desrate^ 0. Otherwise, 5.2 Adaptive Scheduling Methods for Flows with Delay Bound and Jitter Requirements Now consider the flows that have specified their delay bound and delay jitter requirements. Multimedia conferencing, streaming and VoIP applications have QoS requirements related to delay bound and delay jitter experienced by IP packets belonging to their audio and/or video flows. Again, note that these delay bounds and delay jitter are specified for IP packets of each delay and jitter sensitive flow. These IP packets are usually segmented to small size MAC packets before transmitting these over the air. The scheduling methods given here work on these MAC packets to provide delay and jitter guarantees for the IP packets. Consider the queues at the wireless access point. In a 3G network, it is the BTS. In the system described here, one queue per-flow is maintained at the BTS. Delay bound and delay jitter requirements of the IP packets corresponding to these flows need to be satisfied. MAC packets are buffered in the BTS queues before they are scheduled to be sent out over the air interface to the mobile stations. Let w^^[«] be the number of time slots for which the MAC packet p of flow k has been in the queue by time slot n. If iv^^H > db^^, this packet is dropped. Otherwise, it is kept in the queue and counted for the purpose of the methods below. Let buff Jenf^[n] be the buffer length of queue k at the beginning of slot n. Thus buffer length could either include the length of pending packets for that flow in the BTS as well BSC queues, or could only take into account the BTS queues for that flow. If only the BTS queues are used to compute the buffer length for each flow, then one can count the number of MAC packets instead of counting length in bytes as MAC packets are of fixed size in the system considered here. We define normalized buffer length of flow k at the beginning of I i. L u L ^ r 1 buff lenAn] slot n to be buff^ [n] = "^ -—^^-^. reqrate,^ Method - XIII In this method, compute the metric, QoS_M^[n], for each flow k, in each slot n, as follows: Here, r>max^{fi?6J, buff^.^ [n] = min ^ {buff,^ [n], for those queues k such that bufff^ [n] -t- 0} and ;/:0v^^[w] we have db^ - w^ Jw] > 0. It is desirable to keep delay jitter of delay and jitter sensitive flows (such as video conferencing, VoIP etc.) quite low. To achieve this, always start compensating these delay and jitter sensitive flows as soon as they have got some MAC packets in the queues. The first compensating term, '"^^I'U/ does this at macro level. Each flow is compensated in proportion to its queue length. We only keep (and count) those packets that have not already violated their delay bounds. To compute 6i#^iJ«], only consider non-empty queues in each slot n. A flow, f1, with larger queue length than another flow, f2, would be given higher compensation via this term. Next, look at the first packet of each queue and see how far it is from the delay bound of the flow corresponding to that queue. The second compensation term, V,, r . , gives a queue higher compensation as the first packet in this queue reaches closer to the delay bound of the corresponding flow. Here, T is a scaling constant and is chosen such that r>maxj6/6J. This method would give higher value to the selection metric, QoS_M, of a flow as its pending packets reach closer to a state where they might violate their delay or jitter bounds. Once QoS_M^[n]'\s computed for each queue k in slot n, the scheduler selects the queue with the highest value of this metric, QoS_M, and starts serving from that queue in slot n. For flows that have very tight delay and jitter requirements, a stronger version of the above method is proposed. In this stronger version, allow one to look at the maximum of peek (k) (>1)packets for flow k and compute QoS_M,^[n], for each flow k, in each slot n, as follows: Here, look at the difference of the delay bound and waiting time of not just the first (head-of-line) packet but for a pre-specified number of packets, peek (k), for each flow k. Compute compensation function corresponding to each of these packets but give these different weights. The first packet (head of line packet) is assigned the highest weight and other packets are assigned decreasing weights as we traverse each queue. Suitable values of m(.) should be chosen in the condition, m{j)>m{j-\-\),\/j,\ selects a flow to serve with the maximum value of QoS_M^{n\ in slot n. For flows, with even tighter delay and jitter requirements, the following method is proposed. Compute the scheduler selection metric, QoS_M,^[n], for each flow k, in each slot n, as follows: Here, the system keeps memory of what happened in the past few slots and compensate a flow by taking into account backlog in this queue in these additional slots also. A flow for which the corresponding mobile device suddenly starts reporting very bad channel conditions, may not be selected by the earlier methods at such time periods. This version of the method works to ensure that the packets in this flow do not miss their QoS requirements in such time periods also. It does so by keeping track of what happened in the previous few slots and uses buffer length for a pre-specified number of previous slots to compensate the flows. For each flow k, we keep two pre-specified thresholds, buff compth^ and diff _db_comp_th^, SUCh that This helps to ensure that these terms do not become very large and thus no flow is allocated large number of consecutive or close-by slots unreasonably as that might not be fair to other flows. Method ■ XIV In this method, compute QoS compensation metric as follows: For each flow, start with the first version, i.e. compute QoS_M^[n], as given below: QoS^M,[n] = \ y^;^^^ * ^, ^ , J MJ«],V«,V^, Now monitor delay bound and jitter violation statistics for this flow. Let frac_ip_pkt_delay_viol^{n) be the fraction of IP packets that have missed their delay bound by the beginning of slot n, and frac__ip_pktpair_jtr_viol{n) be the fraction of IP packet pairs corresponding to flow k that have missed their jitter bounds by the beginning of slot n. Also, let frac _ delay _ viol _ 1^, frac_delay_viol_2f^, frac jtr viol \f^dX\6 frac jtr viol_2^ be four pre- speclfied parameters for each flow k. These should be such that frac_delay_viol_2^ > frac_delay viol_\^ and frac _ jtr __ viol _ 2^ > frac _ jtr _ viol _ 1^. If at the beginning of some slot n, either frac_ip_pkt__delay _viol^ > frac_delay_viol_2^ or frac_ip_pktpair_ jtr _viol{n) > frac_ jtr_viol_2^, use Thus here one dynamically switches from one mode to another depending upon the QoS state at that time. It indirectly captures the network state also, because if the channel conditions are worse or if the network gets heavily loaded, there is a higher chance that QoS would be violated for some flows. By doing this dynamic switching, one can keep aggregate throughput of the network as close to the throughput achieved by the simple method {QoS_M^[n] = M^[n]) as possible and at the same time satisfy delay bound and jitter requirements of the flows. Method - XV In Method XIII, one of the compensation terms gives higher compensation to the flows that have higher number of pending packets in its queues (over the flows that have less number of packets in the queues). In wireless networks, channel conditions of mobile users can change very rapidly and sometimes it may not be feasible to satisfy delay and jitter requirements of all the flows over the complete lifecycle of these flows. Due to this, not all network operators may want to adopt the design philosophy adopted in the Method XIII. To handle this sort of situation, one can use the method given in this section. Using the method given here, the scheduler would give higher compensation to the flows that have smaller number of packets in their queues and thus tend to satisfy those users first. 6 are pre-specified constants. As mentioned earlier, we only keep those packets in the queue for which w^ ^[n] 0. For flows that have very tight delay and jitter constraints, one can use the following stronger version of the above method: Here, m{j) > m{j +1), w(y) > 0, V/,! difference of the delay bound and waiting time of not just the first (head-of-line) packet but for a pre-specified number of packets, peek (k), for each flow k. Compute compensation function corresponding to each of these packets but give these different weights. Scheduler selects a flow to serve with the maximum value of QoS_M^[n] in slot n. For flows that have still tighter delay bound and jitter requirements, the following method can be used: g(0) > g(l) > > giprevik) > 0, g(0) > 1, buff^^ {n-z]~ max^ {bufff^ [n - z], for those queues k such that buff,^ \n-z]^Q,Q Here, the system keeps in memory of what happened in the past few slots and compensate a flow by taking into account backlog in this queue in these additional slots also. A flow for which the corresponding mobile device suddenly starts reporting very bad channel conditions, may not be selected by the earlier methods at such time periods. This version of the method works to ensure that the packets in this flow do not miss their QoS requirements in such time periods also. It does so by keeping track of what happened in the previous few slots and uses buffer length for a pre-specified number of previous slots to compensate the flows. For each flow k, there are two pre-specified thresholds, buff_comp_th\,^and diff _db_comp___th^, such that This helps to ensure that these compensation terms do not become very large and thus no flow is allocated large number of consecutive or close-by slots unreasonably as that might not be fair to other flows. Method ■ XVI In this method one switches from one version to another dynamically. For each flow, first compute QoS_Mf^[n], as given below: Now monitor delay bound and jitter violation statistics for this flow. Let frac_ip_pkt_delay_viol^{n) be the fraction of IP packets that have missed their delay bound by the beginning of slot n, and frac_ip_pktpair jtr_viol{n) be the fraction of IP packet pairs corresponding to flow k that have missed their jitter bounds by the beginning of slot n. Also, let frac_delay_viol_\\^, frac _ delay _ viol _ 22 ^, frac _ jtr _ viol 11^ and frac __ jtr __ viol _ 22 ^ be four pre- specified parameters for each flow k. These should be such that It is possible to dynamically switch from one mode to another depending upon the QoS and network states at that time. By doing this, it can be noticed to keep aggregate throughput of the network as close to the throughput achieved by the simple method {QoS_M,^[n] = M,^[n]) as possible and at the same time satisfy delay bound and jitter requirements of the flows. Method - XVII In this method, compute the metric, QoS_M,^[n], for each flow k, in each slot n, as follows: is the number of non-empty queues at the beginning of slot n. Earlier methods gave compensation using linear or polynomial functions of queue lengths. This one uses an exponential function. For each flow k, there are two pre-specified thresholds, buff _comp_th2^an6 diff _db_comp_th,^, such that This helps to ensure that these terms do not become very large and thus no flow is allocated large number of consecutive or close-by slots unreasonably as that might not be fair to other flows. This method can be used instead of the previous ones to provide delay bound and jitter guarantees for multimedia flows. Method - XVIII In this method, compute the metric, QoS_M,^[n], for each flow k, in each slot n, as follows: Here, C and T are scaling constants. This method uses an exponential function for the difference between the delay bound and waiting time. For each flow k, there are two pre-specified thresholds, buff _comp_th3f^an6 diff _db comp thl^, such that This helps to ensure that these terms do not become very large and thus no flow is allocated large number of consecutive or close-by slots unreasonably as that might not be fair to other flows. It can be used instead of the previous methods to provide delay and jitter guarantees. Method' XIX In this method, it is possible to dynamically switch from the Method XIII to the Method XVIII. For each flow, compute QoS_M^[n], as given below: Now monitor delay bound and jitter violation statistics for this flow. Let frac_ip pkt delay_violf^{n) be the fraction of IP packets that have missed their delay bound by the beginning of slot n, and frac_ip pktpair_jtr_viol(n) be the fraction of IP packet pairs corresponding to flow k that have missed their jitter bounds by the beginning of slot n. Also, let frac_delay_viol_th^, and frac_jtr_viol_t\ be four pre-specified parameters for each flow k. If at the beginning of some slot n, either frac_ip_pkt_delay__viol^ > fi-ac_delay_viol_th^ or frac ip pktpair jtr_viol{n) > frac jtr viol th^^, use In this method, one can easily try to be less aggressive as long as the flow's QoS violation statistics are within some reasonable bounds. When flow violation statistics go above these pre-specified thresholds, one tends to become more aggressive in increasing the value of its scheduler selection metric, QoS_M. This helps to keep total throughput of a cell as high as possible under any given channel condition and also ensure that QoS requirements of the admitted delay and jitter sensitive flows are met. 5.3: Methods for Flows with Delav Bound, Jitter and Rate Requirements Now consider the flows that have requirements for delay bound, jitter and throughput. For these flows, one can use combinations of the methods presented in earlier sections. First consider the case where each flow has specified required rate, delay bound and jitter requirements. Next consider the case where some flows have also specified their desired rate in addition to the required rate, delay bound and jitter requirements. Method ■ XX Combine the Method I and Method XIII here. Compute the scheduler selection metric, QoS_Mf^[n], for each flow k, in each slot n, as follows: Select a flow with the maximum value of the metric QoS_M^[n] in each slot n. Method - XXI Combine the Method I and Method XV here. Compute the scheduler selection metric, QoS _M,^[n], for each flow k, in each slot n, as follows: Select a flow with the maximum value of the metric QoS_Mf^[rt] in each slot n. Method - XXm Combine Method I and Method XVIII. Compute the scheduler selection metric, QoS_M,^[n], for each flow k, in each slot n, as follows: Select a flow with the maximum value of the metric QoS__M^[n] in each slot n. Method - XXIV Now consider the flows that have specified required rate, desired rate, delay bound and jitter requirements. We define the following: norm __ req __ des _ rate _ faCf^ [n] == norm _ reqrate __ fac,^ [«], if there is at least one flow such that reqrate^, > {\-\-e) Rj^^,g[nl Otherwise, norm _ req _ des _ rate _ fac,^ [n] = norm _ desrate _ fac^^ {ri\. Here, norm_reqrate__fac, is as defined in the Method I and normjdesratejac is as defined in the Method III. Compute the scheduler selection metric, QoS M^^n], for each flow k, in each slot n, using one of the following four methods: Mechanism -1 for Method XXIV This method uses the norm_req_cfes_rate_fac defined above and the Method XIII. Mechanism - II for Method XXIV This method uses the normjreqjdes_jateJac defined above and the method XV. Mechanism - III for Method XXIV This method uses the normjreqjies_jateJac defined above and the method XVII A flow with the maximum value of the QoS compensation metric is selected to be served. 5.4 : Method for Flows with Average Delay and Rate Requirements Method - XXV There are some TCP applications such as web browsing (via HTTP) that benefit if the average delay of those flows can be kept within reasonable limits. Some of the wireless gaming applications also require lower average delay. For this purpose, compute the scheduler selection metric, QoS_M^[n], for each flow k, in each slot n, as follows: Here, norm_reqrate_fac^[ri\ is as defined in the Method I, C is a scaling constant, and buff^\n\ is as defined in the Method XVII. As before, select a flow with the maximum value of the metric QoS _Mf\n\ in each slot n. These methods are to satisfy QoS requirements of diverse types of applications in 3G networks. These methods also control the manner in which time slots are allocated to different flows (and associated applications). Each of these allows a different way in which time slots are allocated and results in different service behavior for the users (but still meet their QoS requirements). Network operators can formulate different types of service level agreements using these for 3G wireless networks. 5,5: Scheduler System for Flows with Heterogeneous QoS Requirements For flows with rate requirements only, a method is chosen from Method I to Method XII depending upon fairness and performance objectives of a network operator. In each slot, when the scheduler needs to select a flow to serve, it applies this chosen method on all the flows with rate requirements only. Among all the flows that have rate requirements only, it selects a candidate flow, Candidate_flow_R, with the maximum value of the QoS selection metric, QoS_M. It is shown in the Figure 5. For flows with delay bound and jitter requirements, a method is chosen from Method XIII to Method XIX depending upon fairness and performance objectives of a network operator. In each slot, when the scheduler needs to select a flow to serve, it applies this chosen method on all the flows with delay bound and jitter requirements only. Among all the flows that have delay bound and jitter requirements only, it selects a candidate flow, Candidate_flow_dbound_Jtr, with the maximum value of the QoS selection metric, QoS_M. It is shown in the Figure 6. For flows with delay bound, jitter and rate requirements, a method is chosen from Method XX to Method XXIV depending upon fairness and performance objectives of a network operator. In each slot, when the scheduler needs to select a flow to serve, it applies this chosen method on all the flows with delay bound, jitter and rate requirements only. Among all the flows that have delay bound, jitter and rate requirements only, it selects a candidate flow, Candidate_flow_R_dbound_Jtr, with the maximum value of the QoS selection metric, QoS_M. It is shown in the Figure 7. For flows with average delay and rate requirements, Method XXV is used. In each slot, when the scheduler needs to select a flow to serve, it applies this chosen method on all the flows with average delay and rate requirements only. Among all the flows that have average delay and rate requirements only, it selects a candidate flow, Candidate_flow_R_AvgD, with the maximum value of the QoS selection metric, QoS_M. It is shown in the Figure 8. Next, the scheduler consider the selected candidate flows above (i.e. Candidate_flow_R, Candidate_flow_dbound__Jtr, Candidate_flow_R_dbound_Jtr and Candidate_flow_R_AvgD) and selects one which has the maximum value of the QoS selection metric, QoS_M, in that time slot. It is shown in the Figure 9. 1. If there are multiple flows with this maximum value of the QoS selection metric, a flow which has requirements over delay bound, jitter and rate is selected; 2. If there are still multiple flows which have requirements for delay bound, jitter and rate, and all have the same maximum value of the QoS selection metric. QoS_M, then out of these a flow whose head of line packet is closest to its deadline is selected to be served; 3. If there are still multiple flows, tie is broken randomly; 4. If there are multiple flows with the maximum value of the QoS selection metric, QoS_M, but none of these is a flow with delay bound, jitter and rate requirement, then tie broken randomly. In the description herein, numerous specific details are provided, such as examples of components and/or methods, to provide a thorough understanding of embodiments of the present invention. One skilled in the relevant art will recognize, however, that an embodiment of the invention can be practiced without one or more of the specific details, or with other apparatus, systems, assemblies, methods, components, materials, parts, and/or the like. In other instances, well-known structures, materials, or operations are not specifically shown or described in detail to avoid obscuring aspects of embodiments of the present invention. A "processor" or "process" includes any human, hardware and/or software system, mechanism or component that processes data, signals or other information. A processor can include a system with a general-purpose central processing unit, multiple processing units, dedicated circuitry for achieving functionality, or other systems. Processing need not be limited to a geographic location, or have temporal limitations. For example, a processor can perform its functions in "real time," "offline," in a "batch mode," etc. Portions of processing can be performed at different times and at different locations, by different (or the same) processing systems. Embodiments of the invention may be implemented by using a programmed general purpose digital computer, by using application specific integrated circuits, programmable logic devices, field programmable gate arrays, optical, chemical, biological, quantum or nano-engineered systems, components and mechanisms may be used. In general, the functions of the present invention can be achieved by any means as is known in the art. Distributed, or networked systems, components and circuits can be used. Communication, or transfer, of data may be wired, wireless, or by any other means. It will also be appreciated that one or more of the elements depicted in the drawings/figures can also be implemented in a more separated or integrated manner, or even removed or rendered as inoperable in certain cases, as is useful in accordance with a particular application. It is also within the spirit and scope of the present invention to implement a program or code that can be stored in a machine-readable medium to permit a computer to perform any of the methods described above. Additionally, any signal arrows in the drawings/Figures should be considered only as exemplary, and not limiting, unless otherwise specifically noted. Furthermore, the term "or" as used herein is generally intended to mean "and/or" unless otherwise indicated. Combinations of components or steps will also be considered as being noted, where terminology is foreseen as rendering the ability to separate or combine is unclear. As used in the description herein and throughout the claims that follow, "a", "an", and "the" includes plural references unless the context clearly dictates othenA/ise. Also, as used in the description herein and throughout the claims that follow, the meaning of "in" includes "in" and "on" unless the context clearly dictates othen/vise. The foregoing description of illustrated embodiments of the present invention, including what is described in the Abstract, is not intended to be exhaustive or to limit the invention to the precise forms disclosed herein. While specific embodiments of, and examples for, the invenfion are described herein for illustrative purposes only, vahous equivalent modifications are possible within the spirit and scope of the present invention, as those skilled in the relevant art will recognize and appreciate. As indicated, these modifications may be made to the present invention in light of the foregoing description of illustrated embodiments of the present invention and are to be included within the spirit and scope of the present invention. Thus, while the present invention has been described herein with reference to particular embodiments thereof, a latitude of modification, various changes and substitutions are intended in the foregoing disclosures, and it will be appreciated that in some instances some features of embodiments of the invention will be employed without a corresponding use of other features without departing from the scope and spirit of the invention as set forth. Therefore, many modifications may be made to adapt a particular situation or material to the essential scope and spirit of the present invention. It is intended that the invention not be limited to the particular terms used in following claims and/or to the particular embodiment disclosed as the best mode contemplated for carrying out this invention, but that the invention will include any and all embodiments and equivalents falling within the scope of the appended claims. GLOSSARY OF TERMS AND THEIR DEFINITIONS 3G: Third Generation wireless networks. These networks are to provide next generation mobile services with better quality of service and high speed internet and multimedia services. These include networks such as CDMA2000 1xEV-D0, CDMA2000 IxEV-DV, WCDMA. BSC: Base Station Controller. BTS: Base Transceiver System. Air interface in the 3G wireless networks terminates at the BTS and the mobile station. CDMA: Code Division Multiple Access. It is a spread-spectrum technology allowing many users to occupy the same time and frequency allocations in a given band/space. It assigns unique codes to each communication to differentiate it from others in the same spectrum. CDMA2000 1xEV: This includes CDMA2000 1xEV-D0 and CDMA2000 1xEV-DV. CDMA2000 1xEV-D0: CDMA2000 Single Carrier Evolution, Data Optimized. It delivers peak data rates of 2.4 Mbps and is intended to provide high performance and low cost packet data services. CDMA2000 1xEV-DV: CDMA2000, Single Carrier, Data and Voice. It provides integrated voice and simultaneous high-speed packet data multimedia services. Correspondent Node (CN): It is a node with which the MS is communicating. For example, it could be a multimedia server or some other mobile station. Forward link flows: These flows are sending data packets from CN (or WER) towards the MS. FTP: File Transfer Protocol. A widely used protocol in the internet used to transfer files from one point to another point. HTTP: Hyper-Text Transfer Protocol. A protocol widely used for web browsing applications in the internet. IP: Internet Protocol. A layer 3 protocol widely used in the internet. LCP: Link Control Protocol. It is used to negotiate radio link protocol and options to control the session in CDMA2000 wireless networks. MPEG: Moving Picture Experts Group. There are several MPEG standards such as MPEG-4, MPEG-2 etc. MS: Mobile station (or mobile device). NACK: Negative Acknowledgement. In contrast to positive acknowledgements, NACK is typically sent when a packet is not received within some expected time interval. QoS : Quality of service. Applications have different types of requirements and these should be met by the networks. These include delay bound, delay jitter, required rate, packet loss, and average delay. Reverse link flows: These flows are sending data from the MS towards the CN (or WER). RLP: Radio Link Protocol. It is a modified form of the automatic repeat request ARQ) protocol and used in 3G networks to improve reliability of the air-interface, RSVP: Resource Reservation Protocol. It is a QoS signaling protocol specified in the RFC2205 and available at www.ietf.org SCP: Stream Control Protocol. This is used for sending RLP negative acknowledgements in CDMA2000 networks when missing RLP data is detected. SIP: Session Initiation Protocol. This session level protocol is used to establish sessions for streaming/conferencing applications in internet. TCP: Transport Control Protocol. A layer 4 protocol widely used in the internet. VoIP: Voice over IP WCDMA: Wideband Code Division Multiple Access WER: Wireless Edge Router WE CLAIM 1. A method for per-flow QoS management in forward link adaptive scheduling module in a 3G wireless multimedia networks wherein improved per-flow QoS management in 3G wireless multimedia networks is provided, the QoS requirement of flows with rate requirements in 3G networks is satisfied, and wherein the present difficulty in satisfying rate requirements is tackled with guaranteed Quality of Service wherein to control the manner in which time slots are allocated to different flows and associated applications, wherein if a flow is lagging behind its required rate more than another flow, the flow which is lagging more is given higher compensation by computing the metric QoS_M,^[n], for each flow k, in each slot n, as follows: 2. A system for per-flow efficient resource allocation in 30 wireless multimedia networks wherein an adaptive scheduler is used as the forward link scheduler for this system that decides which packet has to be sent over the air in each slot and also serves the reverse link flows, which also implements various methods to provide QoS guarantees to diverse types of applications in wireless networks, for flows with various requirements viz. required rate, delay bound, delay jitter, average delay and desired rate. 3. A method as claimed in claim 1, wherein a flow which is closer to its required rate than another flow, is given higher compensation compared to a flow which is not that 4. A method as claimed in claim 1, wherein a flow which is further away from its desired rate is given higher compensation compared to a flow which is closer to its desired rate if all flows have already received their required rate, by computing the metric 6. A method as claimed in claim 1, wherein a flow which is closer to its required rate than another flow, is given higher compensation, considering the flows which have not met their required rate guarantees and . If all flows have met their required rate guarantees, then the metric is computed as 7. A method as claimed in claim 1, wherein in higher compensation is given to a mobile station, whose instantaneous channel conditions are better than its own average channel conditions and to compensate it even further when it is not able to get its required rate, the metric, QoS_Mi^[n], is computed for each flow k, in each slot n, in that If reqrate,^ ^ 0 + ^) -R^^ovg (") > for 3 small constant s whose default value satisfies 0 8. A method as claimed in claim 1, wherein higher compensation is given to a mobile station, Whose instantaneous channel conditions are better than its own average channel conditions and to compensate it even further to give higher compensation to flows that are lagging behind their required rate less than others, the metric, QoS_Mf^[n], is computed for each flow k, in each slot n, in that If reqrate^ 9. A method as claimed in claim 1, wherein higher compensation is given to a mobile station, whose instantaneous channel conditions are better than its own average channel condition and if all flows have got their required rate guarantees, to give further compensation to flow that are lagging behind their desired rate more than others, the metric is computed as follows: 10. A method as claimed in claim 1, wherein if a flow is lagging behind its required rate guarantees, the metric, QoS_M^[n], is computed for each flow k, in each slot n, in that if reqrate,^ satisfies 0 12. A method as claimed in claim 1, wherein to give compensation using a polynomial term, and to give higher compensation to flows which are lagging more than other flows, and to give further compensation when instantaneous channel conditions of a mobile station are better than its own average channel condition, the metric, QoS_M^[n], is computed for each flow k, in each slot n, in that if reqratei^ 13. A method as claimed in claim 1, wherein to give compensation using a polynomial term, the metric , QoS_M^[ri], for each flow k, in each slot n, is computed in that If reqrate,^ 15. A method as claimed in claim 1, wherein to help a flow meet its required rate as well as desired rate, to give compensation using a polynomial term, to make sure that each flow gets its required rate, if excess capacity is available and channel conditions are still favorable, to distribute excess time slots in a way that a flow which is lagging behind its desired rate more than other flows, tend to get its desired rate eariier than the other flows, the metric is QoS __M^[n] = Mj^[n], if desrate. 0.. Otherwise, 16. A method for per-flow QoS management in fonA/ard link adaptive scheduling module in a 3G wireless multimedia networks wherein to make delay and jitter sensitive flows meet QoS requirements and give compensation to these flows by considering their buffer length for some consecutive slots and by considering the time interval in which the pending packets should be served and wherein the buffer length related compensation term gives higher compensation to flows that have more number of pending packets than other, in that the metric, QoS_M,X^], for each flow k, in each slot n, is computed as 17. A method as claimed in claim 16, wherein to meet very tight delay and jitter requirements, the maximum of peek (k) (>1) packets for flow k is considered and QoS_M,^[n], for each flow k, in each slot n, is computed as 19. A method as claimed in claim 16 and 18, wherein the system keeps memory of what happened in the past few slots and uses buffer length for a pre-specified number of previous slots to compensate the flows and for each flow k, there are two pre-specified thresholds, buff _comp_thf^and diff _db comp_t\, such that 20. A method as claimed in claim 16, wherein one can switch between the one version and another in that the metric QoS_M,^[n], is computed first as and jitter violation statistics for this flow are monitored and where the fraction of IP packets that have missed their delay bound by the beginning of slot n, and the fraction of IP packet pairs corresponding to flow k that have missed their jitter bounds by the beginning of slot n, are considered, and if these fractions are above some pre-specified threshold values, the metric is then 21. A method as claimed in claim 16, wherein for the scheduler to give higher compensation to the flows that have smaller number of packets in their queues the metric, QoS_M^[n], for each flow k, in each slot n, is computed as 22. A method as claimed in claim 21, wherein for flows that have very tight delay and jitter constraints, the metric is computed as where m(j) > m{j +1), m(j) > 0, y/,1 23. A method as claimed in claim 21, wherein for flows that have still tighter delay bound and jitter requirements, the metric is computed as Qos^MM-n ui, \ \ n ir^^—T-, ^.w.v^,v^, where prev(k) is a pre-specified number of slots for flow (queue) k, prev(k) > 0, VA:, 'ftHbuff^^[n-z]^sY\fbuff^J^^^ io t buff,^[n-z] J 1^ buffi^[n] ) [ buff,[n-l] ^ Abujf^,\n-previK)\^d\ , buffk[n-prev(k)] J g(0) > g(l) > > g{prev(k) > 0, g(0) > 1, buff^^ {n-z] = max^ {buff^ [n - z], for those queues k such that bufff^ {n-z]^Q,Q 24. A method as claimed in claim 16, wherein one can switch from one version to another dynamically and for each flow, QoS MfXn], is computed initially as: QoS_M,[n]^y^^^'^^^^^^^\A ^ MJn],Vf7,VA:, and after monitoring delay bound and jitter violation statistics for this flow, and the fraction of IP packets that have missed their delay bound by the beginning of slot n, and the fraction of IP packet pairs corresponding to flow k that have missed their jitter bounds by the beginning of slot n, and if these fractions are above some pre-specified threshold values, the metric is recomputed as k, there are two pre-specified thresholds, buff _comp_th2^an6 diff dbcompjh^^, such that 27. A method as claimed in claim 16, wherein to make it possible to dynamically switch between different versions, for each flow, and to keep total throughput of a cell as high as possible under any given channel condition and also ensure that QoS requirements of the admitted delay and jitter sensitive flows are met the metric delay bound and jitter violation statistics for this flow and the fraction of IP packets that have missed their delay bound by the beginning of slot n, and the fraction of IP packet pairs corresponding to flow k that have missed their jitter bounds by the beginning of slot n, and if these fractions are above some pre-specified threshold where a flow with the maximum value of the metric QoS_M,^[n] in each slot n is selected. 30. A method as claimed in claim 28, wherein the scheduler selection metric, 31. A method as claimed in claim 28, wherein the scheduler selection metric, QoS_M^[n], for each flow k, in each slot n, is computed as: 32. A method for per-flow QoS management in forward link adaptive scheduling module in a 3G wireless multimedia networks wherein for flows that have requirements for delay bound, jitter, required rate as well as desired rate, the scheduler selection metric, QoS_M,^[n], for each flow k, in each slot n, is computed as: V where norm _ req _des _ rate _ fac,^ [n] = norm _ reqrate _ fac^ [«], if there is at least one flow such that reqrate^ >(l + ^)-RA..vgM. Otherwise, norm _ req __ des _ rate _ fac^ \n\ - norm _ desrate _ fac,^ [n]. 33. A method as claimed in claim 32, wherein the scheduler selection metric, QoS_M,^[n], for each flow k, in each slot n, is computed as 34. A method as claimed in claim 32, wherein the scheduler selection metric, QoS_Mf^[n], for each flow k, in each slot n, is computed as 36. A method as claimed in claim 1, wherein to keep the average delay of flows within reasonable limits and to maintain lower average delay the scheduler selection metric, QoS_M,n], for each flow k, in each slot n, is computed as : " "'JJ avg f 'J where, C is a scaling constant. 37. A Method for scheduler operation for per-flow QoS management in forward link adaptive scheduling module in a 3G wireless multimedia networks substantially as herein described particularly with reference to drawings. 38. A system for scheduler operation for per-flow QoS management in forward link adaptive scheduling module in a 3G wireless multimedia networks substantially as herein described particularly with reference to drawings.

Full Text

I
FIELD OF TECHNOLOGY
This invention relates to the field of Mobile Wireless Multimedia Networks. Further, this invention in general relates to the 3G Wireless Multimedia Networks. More particularly, this invention encompasses methods and system for efficient per-flow resource allocation in 3G wireless multimedia networks.
PRESENT STATE OF ART
Some of the 3G wireless networking technologies are CDMA2000 IxEV-DV, CDMA2000 1xEV-D0 and WCDMA. A schematic diagram of a 3G-like network is shown in Figure 1. Here, MS is the mobile station, BS is the base station, PCF is the packet control function block and WER is the wireless edge router. An IP networking architecture for this type of networks is described in "wireless IP network standard", www.3gpp2.org 3GPP2 P.S0001-B. The BS essentially includes the BSC and the BTS as shown in Figure 1
Protocol end points of a 3G network are shown in the Figure 2. As shown there, a PPP connection is established between the MS and the PDSN. It is typical to operate a 3G network with a received signal-to-noise ratio that results in a physical layer packet error rate of approximately one-percent. A negative acknowledgement (NACK) based radio link protocol (RLP) uses a form of automatic repeat request (ARQ) to achieve this. A link control protocol (LOP) is used to negotiate radio link protocols and options to control the session. A stream control protocol (SCP) is used to transmit the RLP NACKs when missing RLP data is detected.
In current systems, BTS may contain a set of queues to buffer packets belonging to different flows or mobile stations. Note that IP packets in the BSC are typically segmented to Medium Access Control (MAC) packets in the BTS. There is a scheduler at the BTS that decides the manner in which these queues are served.

A wireless multimedia network would typically support several types of applications such as multimedia conferencing, multimedia streaming, web browsing, wireless games, File Transfer Protocol (FTP), Voice over Internet Protocol (VoIP) etc. Some applications, such as, multimedia conferencing and streaming consist of several flows. For our purposes here, a flow can be a microflow or a macroflow. Here, a microflow is described via the following 5-tuple: IP source address, IP destination address, Layer 4 protocol type (like Transmission control Protocol (TCP), Universal Datagram Protocol (UDP) etc.), Layer 4 source port number, and Layer 4 destination port number. A macroflow is described via the following 3-tuple: IP source address, IP destination address, and Layer 4 protocol type. Multimedia applications can have the following types of flows:
- Forward link data flow for audio (FLDF-A),
- Forward link data flow for video (FLDF-V),
- Reverse link data flow for audio (RLDF-A),
- Reverse link data flow for video (RLDF-V),
- Forward link control flow for audio (FLCF-A),
- FoHA/ard link control flow for video (FLCF-V),
- Reverse link control flow for audio (RLCF-A),
- Reverse link control flow for video (RLCF-V).
Here, forward link data flows (FLDFs) are FLDF-A and FLDF-V. Reverse link data flows (RLDFs) are: RLDF-A and RLDF-V. Similarly, forward link control flows (FLCF) are: FLCF-A and FLCF-V. Reverse link control flows are: RLCF-A and RLCF-V. These control packets are used to provide feedback to the source and destination nodes about the received quality of audio and video flows. They are also used to control the rate at which data is sent from the source node to the destination node. Many data (and some control) flows have certain QoS requirements that are specified via some of the following parameters: delay bound, delay jitter, average delay, throughput, and packet loss. Multimedia applications typically have requirements in the terms of delay bound, delay jitter, throughput and packet loss. These multimedia applications typically use UDP/Real time transport Protocol (RTP) protocols for transport of data. For some other TCP based applications, such as web browsing, keeping average delay

below some pre-specified value is desirable. A flow's traffic can be described via its traffic profile. A flow is considered to be conforming if it obeys its traffic profile. Otherwise, it Is considered to be non-conforming.
The scheduler at the BTS works on the MAC packet queues but is intended to provide QoS guarantees for the IP packets of different flows.
In a 3G network, time is typically divided into fixed length time slots. Each of these slots is of same length. For example, slot length in a CDMA2000 1xEV-D0 networks is approximately 1.67 millisecond. Each mobile device informs the base station about the rate at which it can accept data in each of this slot on forward link. This rate can vary rapidly in a wide-area wireless network. Suppose A^[n] is
the maximum allowed rate at which mobile device k can accept data in slot n from the base station. A forward link, scheduling method was proposed in "Proportional fairness scheduler- David Dtse". It computes the following metric for each mobile:

Here, M^[n] is the metric for mobile device k, and R^^avgi^) '^ computed using an exponentially weighted moving average filter:

Here, t^ ^\IT^, T^ is a time constant such that 0^ to be served in slot n, then R^[ri\ is set to zero. OthenA/ise, it is set to the rate at
which mobile k was served in slot k. This scheduler selects a mobile with the maximum value of the metric, MJ«], to serve in slot n.
In some 3G wireless networking technologies such as CDMA2000, the maximum allowed rate, A^[n\, is specified via two parameters: number of bytes in physical
layer packet that can be sent over the air-interface starting from this slot n and the number of slots that would be taken by this packet. In this case, if mobile k is selected to be served via the forward link scheduler and the mobile has specified that it would need more than one slot for transmission, then it would be served for

the specified number of slots (or until the physical layer packet transmission is over or whichever occurs earlier). Some data rates for a CDMA2000 systems are shown in the table 1 below:

LIMITATIONS
An application can consist of several flows and some of these flows have QoS (Quality of Service) requirements that need to be satisfied.
Let arr^{p) be the arrival time of the first bit of the IP packet p of flow k at the BSC, and dep^{p) be the departure time of the last bit of the IP packet p of flow k from the BTS. Each flow k can specify some of the following QoS requirements:
• Delay Bound {db^^) - Packets of each forward link flow move from the CN
to the BSC and experience some queuing delay at the intermediate nodes. This part of the network is typically a wired network. After this packets get queued in the base station (first at BSC and then at the BTS), and experience variable delay before they are sent out from the BTS to the MS. The delay bound, that is considered here, is the maximum delay for any IP packet of that flow at the BSC and BTS. For flow k, it is equal to

msixp{dep^{p)-arrf^(p)}. A user would typically provide bound on the end-to-end delay, and a target delay bound from the BSC to the MS can be computed from that. To do this, a network operator could specify delay bound for that flow in wired part of the network, from the CN to the BSC and subtract this from the end-to-end delay bound to compute delay bound for that flow from the BSC to the MS.
• Average Delay (AvgDJ- It is the average delay experienced by the IP packets of flow k in the base station (i.e. BSC and BTS) queues.
• Delay Jitter (djtr^) - It is the delay jitter experienced by packets of flow k.
For flow k, djtr, ^m^x^{abs[(dep,(p)-arr,(p))-{dep,(p^l)-~arr,(p + l))]}.
Here, p and p+1 are consecutive IP packets that have arrived at the BSC at time arr^ip) and arr^(p + 1)for flow k.
• Required Rate {reqrate^)- It is the minimum required rate by flow k. A time
scale, tSf^, is also specified for each flow k on which this rate has to be
delivered to that flow.
• Desired Rate {desrate^) - It is the desired rate by flow k. For some
applications, such as MPEG-4. it is useful to specify two rate parameters: required rate and desired rate. Here required rate could correspond to the rate needed when only the base stream is used in an MPEG-4 flow and the desired rate can correspond to the rate when base stream as well as enhanced streams are used in MPEG-4 flow.
For the simple case, when all mobile stations are experiencing same channel conditions and Af^{n] = Aj[n\yk,\/j for each slot n, and the scheduling method is
used where a mobile with the maximum value of the metric MJ«] (where
A \riMk[Yi\^—^^^^,VA:,Vn) is selected to be served, this scheduler would serve

such that equal throughput is given to each of the mobile stations, if queues for all the mobile stations are non-empty (i.e. there are always packets to be sent). In a way, that method would allocate same number of slots to each mobile device under these conditions. This is clearly not desirable for applications which have diverse QoS (in terms of delay bound, delay jitter, average delay, throughput) requirements. In the general case, i.e. when each mobile device could be experiencing different channel conditions, this scheduling method would again fail to meet QoS requirements of diverse types of applications.
In general, it is not possible to give different types of QoS guarantees (on delay bound, average delay, delay jitter, and throughput) to application flows using the above scheduling method. These QoS guarantees are important for several applications such as multimedia conferencing and streaming, VoIP, web browsing, wireless games etc. Real-time applications such as MPEG-4 conferencing and VoIP have stringent requirements on their delay bounds and delay jitter. Video streaming applications such as MPEG-4 streaming also need to have their delay bounded and have tight requirements over their delay jitter. Some other applications such as web browsing that run over HTTP/TCP perform well if average delay in the network is kept low for the corresponding packets. Applications such as FTP need some throughput guarantees from the network.
The methods in which the time slots are allocated for over the air transmission (on the BTS - MS hop) to application flows, play a critical role in determining their delay bound, delay jitter, average delay and throughput. Thus it is very important to introduce new scheduling methods which would help to meet QoS requirements of diverse types of applications in 30 wireless multimedia networks. At the same time, it would be good if these methods could help in offering different schemes by which allocation of time slots is governed among competing flows with different traffic characteristics, different QoS requirements and different channel conditions of the associated mobile stations. This way, these will also help network operators in offering different types of service level agreements for QoS management in 3G wireless networks.

OBJECTS OF THE INVENTION
It is the primary object of the invention to provide methods and system for efficient resource allocation in 3G Mobile Wireless Multimedia Networks.
It is another object of the invention to provide the scheduling methods to satisfy the QoS requirement of diverse type of application in 3G wireless multimedia networks.
It is another object of the invention to provide the scheduling methods that provide multiple ways for allocating resources to different flows and their associated mobile stations to allow network operators to define different types of fairness criteria and service level agreements in 3G wireless multimedia networks.
It is the another object of the invention to provide the methods that provide guaranteed Quality of service to multimedia streaming applications in 30 wireless network.
It is the another object of the invention to provide the methods that provide guaranteed QoS to multimedia conferencing applications in 30 wireless networks.
It is the another object of the invention to provide the scheduling methods that can improve quality of web browsing applications in 30 wireless networks.
It is the another object of the invention to provide the improved methods of media transmission in 30 wireless network.

SUMMARY OF THE INVENTION
Consider the system as shown in Figure.4. IP packet classifier shown there classifies flows into separate queues. Each queue contains IP packets corresponding to a flow and has QoS requirements for these packets that need to be satisfied. For each queue, there is requirement on some of the following: delay bound, delay jitter, average delay, and throughput (rate). These IP packets are further segmented to MAC packets that are to be transmitted over the air to the mobile devices. An adaptive scheduler is used, as the forward link scheduler for this system that decides which packet has to be sent over the air in each slot. Such a scheduler can also be used for reverse link flows. Also, as channel conditions for mobile stations typically keep varying in a 3G wireless networks, it is quite possible that there can be multiple ways to distribute time slots so that QoS requirements of application flows are met. In such cases, these new scheduling methods provide several ways of allocating slots to application flows. These scheduling methods also provide mechanisms which allow different ways to decide which flows are to be given higher preference over other flows in case the network gets congested and several mobile stations start experiencing bad channel conditions. Thus these methods provide different fairness criteria using which network operators can offer different types of service level agreements for different mobile users (and their flows).
The present invention proposes scheduling methods to be used in this fonward link adaptive scheduling module here. In the (detail description of the invention herein below), the flows that only specify their rate requirements are considered. The present invention proposes several methods for these flows. Each of these methods adopts a different design policy and a network operator can decide to use an appropriate one depending upon its objectives. Next, consider the flows that specify their delay bound and delay jitter requirements. The invention proposes methods to be used for these flows in the (detail description of the invention herein below). In the subsequent section, flows that have QoS requirements related to delay bound, delay jitter and throughput are considered. Typically, multimedia conferencing and streaming applications (such as MPEG-4,

VoIP etc.) fall in this category. The present invention specifies adaptive scheduling methods that can be used for these flows in the (detail description of the invention herein below). Next the flows that have requirements related to average delay and throughput are considered. Typically, TCP applications such as web browsing (via HTTP protocol) fall in this category. These applications do not have any strict requirements over delay bound but perceived quality seen improves if the average delay of these flows can be kept low. Wireless gaming applications can use the methods described in the (detail description of the invention herein below), depending upon the type of the gaming application. If it is a highly interactive multimedia game, one should use the methods given in the section 5.1. For simple text based games, one could use the methods given in the section 5.4. Several QoS scheduling methods that allow us to provide QoS guarantees to diverse types of applications in wireless networks, are considered. Each of the scheduling method given in the (detail description of the invention herein below) provides a different fairness criteria which governs allocation of resources among competing flows and decides which flow is to be given higher or lower preference than other flows by considering the network condition (especially the channel condition of different mobile stations), QoS received by flows and QoS requirements of flows.
Accordingly this invention relates to a method for per-flow QoS management in forward link adaptive scheduling module in a 3G wireless multimedia networks wherein improved per-flow QoS management in 3G wireless multimedia networks is provided, the QoS requirement of flows with rate requirements in 3G networks is satisfied, and wherein the present difficulty in satisfying rate requirements is tackled with guaranteed Quality of Service wherein to control the manner in which time slots are allocated to different flows and associated applications, wherein if a flow is lagging behind its required rate more than another flow, the flow which is lagging more is given higher compensation by computing the metric QoS_M^[n],
for each flow k, in each slot n.

Accordingly this invention relates to a system for per-flow efficient resource allocation in 3G wireless multimedia networks wherein an adaptive scheduler is used as the forward link scheduler for this system that decides which packet has to be sent over the air in each slot and also serves the reverse link flows, which also implements various methods to provide QoS guarantees to diverse types of applications in wireless networks, for flows with various requirements viz. required rate, delay bound, delay jitter, average delay and desired rate.
The other objects, features and advantages of the present invention will be apparent from the accompanying drawings and the detailed description as follows:
BRIEF DESCRIPTION OF THE ACCOMPANYING DRAWINGS
Fig. 1 relates to the existing architecture of 30 like networks where forward and reverse link flows from MS, through base stations BS and vice versa is shown with there components comprising the base station controller (BSC), base transceiver system (BTS), the point coordination function (PGP), wireless edge router (WER) and the correspondent node (ON);
Fig. 2: Protocol end points of a 3G network are shown in the Figure 3. A PPP connection is established between the MS and the PDSN. Physical layer terminates at the MS and the BTS. RLP terminates at the MS and the BSC;
Fig, 3: shows the discrete time wireless system wherein each slot "s" each mobile that has data to send informs the access point (BTS) about the rate at which it can be served in that slot. Access point (BTS) needs to decide which mobile (and flow) to serve in each slot. Rate specified by a mobile is typically specified in terms of number of fixed size MAC packets or bytes that can be sent and the number of time slots needed by these packets;
Fig. 4: shows a fonward link adaptive scheduler which classifies fiows into separate queues. Each queue contains IP packets corresponding to a flow and has QoS requirements for these packets that need to be satisfied. These IP

packets are further segmented to MAC packets that are to be transmitted over the air to the mobile devices. An innovated adaptive scheduler is applied as the forward link scheduler for this system that decides which packet has to be sent over the air in each slot;
Fig. 5: shows scheduler operation for flows with rate requirement only;
Fig. 6: shows scheduler operation for flows with delay bound and delay jitter requirements;
Fig. 7: shows scheduler operation for flows with delay bound, delay jitter and rate requirements;
Fig. 8: shows scheduler operation for flows with average delay and rate requirements;
Fig, 9: shows the Flow selection by the scheduler.
DETAILED DESCRIPTION OF THE INVENTION
5.1. Adaptive scheduling methods for Flows with Rate Requirements only
In this section, the flows that specify only the rate requirements are considered. In the system presented here, a flow can specify either only its required rate, or its required rate as well as desired rate. Required rate would typically be the minimum rate needed by an application. Desired rate could be the rate at which user would like to receive the service. This desired rate can not be less than the required rate. Each of the method presented here provide rate guarantees for flows and at the same time provide different ways of allocating resources to these flows with different fairness criteria using which network operators can offer different types of service level agreements. For each flow, a QoS compensation metric is computed. These methods are explained below.

Method -1
Let reqrate^ be the required rate specified by flow k. In this method, QoS
compensation metric, QoS_M k [n], is computed for each flow k, in each slot n, as follows:

This fon/vard link QoS scheduler considers the flows that have non-zero queue length and selects a flow with the maximum value of the metric QoS_M k[n] in each slot n when it needs to select a mobile to serve. Note that this method compensates the flows that are lagging behind their required rate requirements. The lagging flows are compensated in proportion to the normalized difference of their required rate and served rate (normjreqratejac above). If a flow (say, f1) that is lagging (behind its required rate requirement) more than another flow (say, f2), then the flow f1 is given higher compensation (than the flow f2) and the method tends to recover this flow (i.e. f1) earlier (than f2).
Method ■ II
The method also works to achieve the required rate requirement as in Method - I but tends to do the opposite of what is done there while compensating lagging

flows. Specifically, if a flow (say, f1) is lagging more than another flow (say, f2), then flow f2 is given higher compensation and this flow tend to recover earlier than flow f1. In wireless networks, it could happen that some flows (with required rate requirements) are initially admitted in the system after observing channel conditions of the corresponding users but as channel conditions can vary rapidly, it may become not feasible to satisfy QoS requirements of some of these flows for some period of time. In such cases, some network operators may decide to adopt a scheme where they first satisfy QoS requirements of at least those flows who are closer to their required rate requirements than the flows that are lagging more. In such cases, the method given here can be used. For this method, compute the

This fonward link QoS scheduler considers the flows that have non-zero queue length and selects a flow with the maximum value of the metric QoS_M k [n] in each slot n when it needs to select a flow to serve.
Method - III
This method can be used for the case where each flow has specified its required rate as well as desired rate. Compute the metric QoS_M K [n], for each flow k, in each slot n, as follows:

If there is at least one flow k, such that its reqrate^ >(l-^s)*R^^^^in), for some
small constant £>0., then QoS_M k [n] is computed as given earlier in the Method -1 for this slot. Otherwise, this metric is computed as follows:
QoS __ Mf^ [n] - norm _ desrate _ fac^ \n\ * M^ [/?], VA:, V«
Here,
norm _ desrate _ fac,^ [n] = \, if desrate^^ 0.
OthenA/ise,
norm_desrate_fac,^[n] = —^^^(desrate^ -R^^^g{n)\\/n. We choose a suitable value
of r,^,,such that desrate, =H,'r,^^^yk. We also have, //^^ = max,{//,}. For each flow k, a threshold norm desrate_fac_th,, is specified and the following is
always ensured:
norm _ desrate _ fac, \n\ This forward link QoS scheduler considers the flows that have non-zero queue length and selects a flow with the maximum value of the metric QoS_M k[n] in each slot n when it needs to select a flow to serve.
Method ■ IV
This method should be used for the case where each flow has specified its required as well as desired rate and the network operator wants to adopt a policy where the flows that are closer to their required rate requirement should be recovered earlier than the flows that are lagging more behind their required rate QoS requirement. For this method, compute the metric QoS_M,[n], for each
flow k, in each slot n, as follows:
If there is at least one flow /c, such that its reqrate,^ >(! + £•)* 7?,^^^ («), for some
small constant s>Q, then QoS^M^Xn] is computed as given earlier in the Method
- II for this slot. Otherwise, this metric is computed as follows:
QoS _ Mf^ [n\ = norm _ desrate _ fac,^ [n] * M, [«], VA:, V«

Here, norm_desrate_fac^[n], is as defined in tlie Method - III.
This forward link QoS scheduler considers the flows that have non-zero queue length and selects a flow with the maximum value of the metric QoS_M,^[n] in
each slot n when it needs to select a flow to serve.
Method ■ V
In this method, compute the metric, QoS_M,^[n], for each flow k, in each slot n, as follows: If for flow k, regrate^ 0, then
QoS__M,[n]=- ^'^^^ ,Vw. Otherwise,
A \nQoS __ M^ [n] = norm _ reqrate _ fac,^ [w] * — , V«
Here, norm_reqrate_fac,^[n], is as defined in the Method - I and A,avg[«] = ^1 * Mf^] + 0 - ^ci) * A,avg[^ -1]. for some constant r^, such that 0,, This foHA/ard link QoS scheduler considers the flows that have non-zero queue length and selects a flow with the maximum value of the metric QoS_M^[n] in
each slot n when it needs to select a flow to serve. This method compensates each lagging flow in proportion to the normalized difference between the required rate and the served rate (as was done in the Method - I) but it does thus in a different manner as it doesn't use M^[n] as was done earlier. It results in a
different way of allocating resources (timeslots here) to competing flows and thus in a different fairness definition.
Method - VI

For this method, compute the metric, QoS_M,^[n], for each flow k, in each slot n, as follows: If for flow k, reqrate^ 0, then
QoS_M,{n\^ "^'^^^ ,V^. OthenA^ise,
QoS_M,{n] = ? *-AW_,VA2
norm _ reqrate _ fac^ [«] A^^avg \^
Here, norm reqrate_fac^\n\ is as defined in the Method -1, Z is as defined in the
Method - II, and ^^^,^[«] is as defined in the Method - V. This fonA^ard link QoS
scheduler considers the flows that have non-zero queue length and selects a flow with the maximum value of the metric QoS_M^\n\ in each slot n when it needs to
select a flow to serve. This method tends to recover flows that are closer to their required rate QoS requirements earlier than the other flows that are lagging behind their required rate requirement (as was done in the Method II) but does not use MJw] as was done earlier. It results in a different way of allocating resources
to competing flows and thus in a different fairness definition.
Method ■ VII
This method can be used when required rate as well as desired rate are specified for each flow. In this method, we compute the metric QoS_M^\n\, for each flow k,
in each slot n, as follows:
If there is at least one flow k, such that its reqrate^ > (1 + £•) * i?^^,^ («), for some
small constant f>0., then QoS_M^\n\ is computed as given earlier in the Method - V for this slot. Otherwise, this metric is computed as follows:
A \n\ QoS _ M^ \n\ = norm _ desrate _ fac^ [n] * —^^^^, VA:, V«
A,avgM
Here, norm_desrate_fac^[n\ is as defined in the Method - III and ^^^^^^ is as defined in the Method - V.

Method ■ Vm
In this method, compute the metric, QoS_Mf^[n], for each flow k, in each slot n, as follows:

A flow, f1, that is lagging more than another flow, f2, is given higher compensation than f2 and flow f1 would tend to recover faster than flow f2.
Method - IX

In this method, compute the metric, QoS_M,^[n], for each flow k, in each slot n, as follows: If for flow k, reqrate,^ 0, then

This method results in different allocation of resources (and thus different fairness definition) than the method VIII.
Method - X
In this method, compute the metric, QoS_Mf^[n], for each flow k, in each slot n, as
follows:
If for flow k, reqrate^0, then
QoS_M^[n] = Af J«],Vw. OthenA/ise, for flow k.

This method uses a different compensation factor and results in different allocation of resources to flows than the earlier methods.
Method" XI
Here we combine the method given above. Suppose each flow has specified its required rate as well as desired rate. As long as there is at least one flow k for which reqrate,^ > 0 + ^)*^A,avg(^)' ^^e either Method VIII, Method IX or Method X.
Otherwise, use QoS_M,^[n] = norm_desrate_fac,^[n]'^Mf^[n]yri for flow k, where
norm_desrate_fac is as defined in the Method III .
Method - XII
Again consider the case where each flow has specified its required rate as well as desired rate. As long as there is at least one flow k for which reqrate.>{\ + s)*R.^(n), use either Method VIII, or Method IX or Method X.
Othen/vise, do the following:
Qo5_MJn] = MJn], if desrate^ 0.
Otherwise,

5.2 Adaptive Scheduling Methods for Flows with Delay Bound and Jitter Requirements
Now consider the flows that have specified their delay bound and delay jitter requirements. Multimedia conferencing, streaming and VoIP applications have QoS requirements related to delay bound and delay jitter experienced by IP packets belonging to their audio and/or video flows. Again, note that these delay bounds and delay jitter are specified for IP packets of each delay and jitter sensitive flow. These IP packets are usually segmented to small size MAC packets before transmitting these over the air. The scheduling methods given here work on these MAC packets to provide delay and jitter guarantees for the IP packets.
Consider the queues at the wireless access point. In a 3G network, it is the BTS. In the system described here, one queue per-flow is maintained at the BTS. Delay bound and delay jitter requirements of the IP packets corresponding to these flows need to be satisfied. MAC packets are buffered in the BTS queues before they are scheduled to be sent out over the air interface to the mobile stations. Let w^^[«] be the number of time slots for which the MAC packet p of
flow k has been in the queue by time slot n. If iv^^H > db^^, this packet is
dropped. Otherwise, it is kept in the queue and counted for the purpose of the methods below. Let buff Jenf^[n] be the buffer length of queue k at the beginning

of slot n. Thus buffer length could either include the length of pending packets for that flow in the BTS as well BSC queues, or could only take into account the BTS queues for that flow. If only the BTS queues are used to compute the buffer length for each flow, then one can count the number of MAC packets instead of counting length in bytes as MAC packets are of fixed size in the system considered here. We define normalized buffer length of flow k at the beginning of
I i. L u L ^ r 1 buff lenAn] slot n to be buff^ [n] = "^ -—^^-^.
reqrate,^
Method - XIII
In this method, compute the metric, QoS_M^[n], for each flow k, in each slot n, as follows:

Here, r>max^{fi?6J,
buff^.^ [n] = min ^ {buff,^ [n], for those queues k such that bufff^ [n] -t- 0} and ;/:0v^^[w] we have db^ - w^ Jw] > 0.
It is desirable to keep delay jitter of delay and jitter sensitive flows (such as video conferencing, VoIP etc.) quite low. To achieve this, always start compensating these delay and jitter sensitive flows as soon as they have got some MAC packets
in the queues. The first compensating term, '"^^I'U/ does this at macro
level. Each flow is compensated in proportion to its queue length. We only keep (and count) those packets that have not already violated their delay bounds. To compute 6i#^iJ«], only consider non-empty queues in each slot n. A flow, f1, with
larger queue length than another flow, f2, would be given higher compensation via this term. Next, look at the first packet of each queue and see how far it is from

the delay bound of the flow corresponding to that queue. The second
compensation term, V,, r . , gives a queue higher compensation as the
first packet in this queue reaches closer to the delay bound of the corresponding flow. Here, T is a scaling constant and is chosen such that r>maxj6/6J. This
method would give higher value to the selection metric, QoS_M, of a flow as its pending packets reach closer to a state where they might violate their delay or jitter bounds. Once QoS_M^[n]'\s computed for each queue k in slot n, the
scheduler selects the queue with the highest value of this metric, QoS_M, and starts serving from that queue in slot n.
For flows that have very tight delay and jitter requirements, a stronger version of the above method is proposed. In this stronger version, allow one to look at the maximum of peek (k) (>1)packets for flow k and compute QoS_M,^[n], for each
flow k, in each slot n, as follows:

Here, look at the difference of the delay bound and waiting time of not just the first (head-of-line) packet but for a pre-specified number of packets, peek (k), for each flow k. Compute compensation function corresponding to each of these packets but give these different weights. The first packet (head of line packet) is assigned the highest weight and other packets are assigned decreasing weights as we traverse each queue. Suitable values of m(.) should be chosen in the condition, m{j)>m{j-\-\),\/j,\ selects a flow to serve with the maximum value of QoS_M^{n\ in slot n.

For flows, with even tighter delay and jitter requirements, the following method is proposed. Compute the scheduler selection metric, QoS_M,^[n], for each flow k,
in each slot n, as follows:

Here, the system keeps memory of what happened in the past few slots and compensate a flow by taking into account backlog in this queue in these additional slots also. A flow for which the corresponding mobile device suddenly starts reporting very bad channel conditions, may not be selected by the earlier methods at such time periods. This version of the method works to ensure that the packets in this flow do not miss their QoS requirements in such time periods also. It does so by keeping track of what happened in the previous few slots and uses buffer length for a pre-specified number of previous slots to compensate the flows. For each flow k, we keep two pre-specified thresholds, buff compth^ and
diff _db_comp_th^, SUCh that

This helps to ensure that these terms do not become very large and thus no flow is allocated large number of consecutive or close-by slots unreasonably as that might not be fair to other flows.

Method ■ XIV
In this method, compute QoS compensation metric as follows:
For each flow, start with the first version, i.e. compute QoS_M^[n], as given
below:
QoS^M,[n] = \ y^;^^^ * ^, ^ , J *MJ«],V«,V^,
Now monitor delay bound and jitter violation statistics for this flow. Let frac_ip_pkt_delay_viol^{n) be the fraction of IP packets that have missed their
delay bound by the beginning of slot n, and frac__ip_pktpair_jtr_viol{n) be the
fraction of IP packet pairs corresponding to flow k that have missed their jitter bounds by the beginning of slot n. Also, let frac _ delay _ viol _ 1^,
frac_delay_viol_2f^, frac jtr viol \f^dX\6 frac jtr viol_2^ be four pre-
speclfied parameters for each flow k. These should be such that
frac_delay_viol_2^ > frac_delay viol_\^ and
frac _ jtr __ viol _ 2^ > frac _ jtr _ viol _ 1^.
If at the beginning of some slot n, either
frac_ip_pkt__delay _viol^ > frac_delay_viol_2^ or
frac_ip_pktpair_ jtr _viol{n) > frac_ jtr_viol_2^, use

Thus here one dynamically switches from one mode to another depending upon the QoS state at that time. It indirectly captures the network state also, because if the channel conditions are worse or if the network gets heavily loaded, there is a higher chance that QoS would be violated for some flows. By doing this dynamic switching, one can keep aggregate throughput of the network as close to the throughput achieved by the simple method {QoS_M^[n] = M^[n]) as possible and
at the same time satisfy delay bound and jitter requirements of the flows.
Method - XV
In Method XIII, one of the compensation terms gives higher compensation to the flows that have higher number of pending packets in its queues (over the flows that have less number of packets in the queues). In wireless networks, channel conditions of mobile users can change very rapidly and sometimes it may not be feasible to satisfy delay and jitter requirements of all the flows over the complete lifecycle of these flows. Due to this, not all network operators may want to adopt the design philosophy adopted in the Method XIII. To handle this sort of situation, one can use the method given in this section. Using the method given here, the scheduler would give higher compensation to the flows that have smaller number of packets in their queues and thus tend to satisfy those users first.

6 are pre-specified constants. As mentioned earlier, we only keep those packets in the queue for which w^ ^[n] 0.
For flows that have very tight delay and jitter constraints, one can use the following stronger version of the above method:

Here, m{j) > m{j +1), w(y) > 0, V/,! difference of the delay bound and waiting time of not just the first (head-of-line) packet but for a pre-specified number of packets, peek (k), for each flow k. Compute compensation function corresponding to each of these packets but give these different weights. Scheduler selects a flow to serve with the maximum value of QoS_M^[n] in slot n. For flows that have still tighter delay bound and jitter
requirements, the following method can be used:

g(0) > g(l) > > giprevik) > 0, g(0) > 1,
buff^^ {n-z]~ max^ {bufff^ [n - z], for those queues k such that buff,^ \n-z]^Q,Q Here, the system keeps in memory of what happened in the past few slots and compensate a flow by taking into account backlog in this queue in these additional slots also. A flow for which the corresponding mobile device suddenly starts reporting very bad channel conditions, may not be selected by the earlier methods

at such time periods. This version of the method works to ensure that the packets in this flow do not miss their QoS requirements in such time periods also. It does so by keeping track of what happened in the previous few slots and uses buffer length for a pre-specified number of previous slots to compensate the flows.
For each flow k, there are two pre-specified thresholds, buff_comp_th\,^and
diff _db_comp___th^, such that

This helps to ensure that these compensation terms do not become very large and thus no flow is allocated large number of consecutive or close-by slots unreasonably as that might not be fair to other flows.
Method ■ XVI
In this method one switches from one version to another dynamically. For each flow, first compute QoS_Mf^[n], as given below:

Now monitor delay bound and jitter violation statistics for this flow. Let frac_ip_pkt_delay_viol^{n) be the fraction of IP packets that have missed their
delay bound by the beginning of slot n, and frac_ip_pktpair jtr_viol{n) be the
fraction of IP packet pairs corresponding to flow k that have missed their jitter bounds by the beginning of slot n. Also, let frac_delay_viol_\\^,
frac _ delay _ viol _ 22 ^, frac _ jtr _ viol 11^ and frac __ jtr __ viol _ 22 ^ be four pre-
specified parameters for each flow k. These should be such that

It is possible to dynamically switch from one mode to another depending upon the QoS and network states at that time. By doing this, it can be noticed to keep aggregate throughput of the network as close to the throughput achieved by the simple method {QoS_M,^[n] = M,^[n]) as possible and at the same time satisfy
delay bound and jitter requirements of the flows.
Method - XVII
In this method, compute the metric, QoS_M,^[n], for each flow k, in each slot n, as follows:

is the number of non-empty queues at the beginning of slot n. Earlier methods gave compensation using linear or polynomial functions of queue lengths. This one uses an exponential function. For each flow k, there are two pre-specified thresholds, buff _comp_th2^an6 diff _db_comp_th,^, such that

This helps to ensure that these terms do not become very large and thus no flow is allocated large number of consecutive or close-by slots unreasonably as that might not be fair to other flows. This method can be used instead of the previous ones to provide delay bound and jitter guarantees for multimedia flows.
Method - XVIII
In this method, compute the metric, QoS_M,^[n], for each flow k, in each slot n, as follows:

Here, C and T are scaling constants. This method uses an exponential function for the difference between the delay bound and waiting time. For each flow k, there are two pre-specified thresholds, buff _comp_th3f^an6 diff _db comp thl^, such
that

This helps to ensure that these terms do not become very large and thus no flow is allocated large number of consecutive or close-by slots unreasonably as that might not be fair to other flows. It can be used instead of the previous methods to provide delay and jitter guarantees.
Method' XIX
In this method, it is possible to dynamically switch from the Method XIII to the Method XVIII. For each flow, compute QoS_M^[n], as given below:

Now monitor delay bound and jitter violation statistics for this flow. Let frac_ip pkt delay_violf^{n) be the fraction of IP packets that have missed their
delay bound by the beginning of slot n, and frac_ip pktpair_jtr_viol(n) be the
fraction of IP packet pairs corresponding to flow k that have missed their jitter bounds by the beginning of slot n. Also, let frac_delay_viol_th^, and
frac_jtr_viol_t\ be four pre-specified parameters for each flow k. If at the
beginning of some slot n, either frac_ip_pkt_delay__viol^ > fi-ac_delay_viol_th^
or frac ip pktpair jtr_viol{n) > frac jtr viol th^^, use

In this method, one can easily try to be less aggressive as long as the flow's QoS violation statistics are within some reasonable bounds. When flow violation statistics go above these pre-specified thresholds, one tends to become more

aggressive in increasing the value of its scheduler selection metric, QoS_M. This helps to keep total throughput of a cell as high as possible under any given channel condition and also ensure that QoS requirements of the admitted delay and jitter sensitive flows are met.
5.3: Methods for Flows with Delav Bound, Jitter and Rate Requirements
Now consider the flows that have requirements for delay bound, jitter and throughput. For these flows, one can use combinations of the methods presented in earlier sections. First consider the case where each flow has specified required rate, delay bound and jitter requirements. Next consider the case where some flows have also specified their desired rate in addition to the required rate, delay bound and jitter requirements.
Method ■ XX
Combine the Method I and Method XIII here. Compute the scheduler selection metric, QoS_Mf^[n], for each flow k, in each slot n, as follows:

Select a flow with the maximum value of the metric QoS_M^[n] in each slot n.
Method - XXI
Combine the Method I and Method XV here. Compute the scheduler selection metric, QoS _M,^[n], for each flow k, in each slot n, as follows:

Select a flow with the maximum value of the metric QoS_Mf^[rt] in each slot n.
Method - XXm
Combine Method I and Method XVIII. Compute the scheduler selection metric, QoS_M,^[n], for each flow k, in each slot n, as follows:

Select a flow with the maximum value of the metric QoS__M^[n] in each slot n.
Method - XXIV
Now consider the flows that have specified required rate, desired rate, delay bound and jitter requirements. We define the following:

norm __ req __ des _ rate _ faCf^ [n] == norm _ reqrate __ fac,^ [«], if there is at least one flow such that reqrate^, > {\-\-e)* Rj^^,g[nl
Otherwise,
norm _ req _ des _ rate _ fac,^ [n] = norm _ desrate _ fac^^ {ri\.
Here, norm_reqrate__fac, is as defined in the Method I and normjdesratejac is as defined in the Method III.
Compute the scheduler selection metric, QoS M^^n], for each flow k, in each slot n, using one of the following four methods:
Mechanism -1 for Method XXIV
This method uses the norm_req_cfes_rate_fac defined above and the Method XIII.

Mechanism - II for Method XXIV
This method uses the normjreqjdes_jateJac defined above and the method XV.

Mechanism - III for Method XXIV
This method uses the normjreqjies_jateJac defined above and the method XVII

A flow with the maximum value of the QoS compensation metric is selected to be served.
5.4 : Method for Flows with Average Delay and Rate Requirements
Method - XXV
There are some TCP applications such as web browsing (via HTTP) that benefit if the average delay of those flows can be kept within reasonable limits. Some of the wireless gaming applications also require lower average delay. For this purpose, compute the scheduler selection metric, QoS_M^[n], for each flow k, in each slot
n, as follows:

Here, norm_reqrate_fac^[ri\ is as defined in the Method I, C is a scaling constant, and buff^\n\ is as defined in the Method XVII. As before, select a flow with the maximum value of the metric QoS _Mf\n\ in each slot n.

These methods are to satisfy QoS requirements of diverse types of applications in 3G networks. These methods also control the manner in which time slots are allocated to different flows (and associated applications). Each of these allows a different way in which time slots are allocated and results in different service behavior for the users (but still meet their QoS requirements). Network operators can formulate different types of service level agreements using these for 3G wireless networks.
5,5: Scheduler System for Flows with Heterogeneous QoS Requirements
For flows with rate requirements only, a method is chosen from Method I to Method XII depending upon fairness and performance objectives of a network operator. In each slot, when the scheduler needs to select a flow to serve, it applies this chosen method on all the flows with rate requirements only. Among all the flows that have rate requirements only, it selects a candidate flow, Candidate_flow_R, with the maximum value of the QoS selection metric, QoS_M. It is shown in the Figure 5.
For flows with delay bound and jitter requirements, a method is chosen from Method XIII to Method XIX depending upon fairness and performance objectives of a network operator. In each slot, when the scheduler needs to select a flow to serve, it applies this chosen method on all the flows with delay bound and jitter requirements only. Among all the flows that have delay bound and jitter requirements only, it selects a candidate flow, Candidate_flow_dbound_Jtr, with the maximum value of the QoS selection metric, QoS_M. It is shown in the Figure 6.
For flows with delay bound, jitter and rate requirements, a method is chosen from Method XX to Method XXIV depending upon fairness and performance objectives of a network operator. In each slot, when the scheduler needs to select a flow to serve, it applies this chosen method on all the flows with delay bound, jitter and rate requirements only. Among all the flows that have delay bound, jitter and rate requirements only, it selects a candidate flow, Candidate_flow_R_dbound_Jtr,

with the maximum value of the QoS selection metric, QoS_M. It is shown in the Figure 7.
For flows with average delay and rate requirements, Method XXV is used. In each slot, when the scheduler needs to select a flow to serve, it applies this chosen method on all the flows with average delay and rate requirements only. Among all the flows that have average delay and rate requirements only, it selects a candidate flow, Candidate_flow_R_AvgD, with the maximum value of the QoS selection metric, QoS_M. It is shown in the Figure 8.
Next, the scheduler consider the selected candidate flows above (i.e. Candidate_flow_R, Candidate_flow_dbound__Jtr, Candidate_flow_R_dbound_Jtr and Candidate_flow_R_AvgD) and selects one which has the maximum value of the QoS selection metric, QoS_M, in that time slot. It is shown in the Figure 9.
1. If there are multiple flows with this maximum value of the QoS selection metric, a flow which has requirements over delay bound, jitter and rate is selected;
2. If there are still multiple flows which have requirements for delay bound, jitter and rate, and all have the same maximum value of the QoS selection metric. QoS_M, then out of these a flow whose head of line packet is closest to its deadline is selected to be served;
3. If there are still multiple flows, tie is broken randomly;
4. If there are multiple flows with the maximum value of the QoS selection metric, QoS_M, but none of these is a flow with delay bound, jitter and rate requirement, then tie broken randomly.
In the description herein, numerous specific details are provided, such as examples of components and/or methods, to provide a thorough understanding of embodiments of the present invention. One skilled in the relevant art will recognize, however, that an embodiment of the invention can be practiced without

one or more of the specific details, or with other apparatus, systems, assemblies, methods, components, materials, parts, and/or the like. In other instances, well-known structures, materials, or operations are not specifically shown or described in detail to avoid obscuring aspects of embodiments of the present invention.
A "processor" or "process" includes any human, hardware and/or software system, mechanism or component that processes data, signals or other information. A processor can include a system with a general-purpose central processing unit, multiple processing units, dedicated circuitry for achieving functionality, or other systems. Processing need not be limited to a geographic location, or have temporal limitations. For example, a processor can perform its functions in "real time," "offline," in a "batch mode," etc. Portions of processing can be performed at different times and at different locations, by different (or the same) processing systems.
Embodiments of the invention may be implemented by using a programmed general purpose digital computer, by using application specific integrated circuits, programmable logic devices, field programmable gate arrays, optical, chemical, biological, quantum or nano-engineered systems, components and mechanisms may be used. In general, the functions of the present invention can be achieved by any means as is known in the art. Distributed, or networked systems, components and circuits can be used. Communication, or transfer, of data may be wired, wireless, or by any other means.
It will also be appreciated that one or more of the elements depicted in the drawings/figures can also be implemented in a more separated or integrated manner, or even removed or rendered as inoperable in certain cases, as is useful in accordance with a particular application. It is also within the spirit and scope of the present invention to implement a program or code that can be stored in a machine-readable medium to permit a computer to perform any of the methods described above.

Additionally, any signal arrows in the drawings/Figures should be considered only as exemplary, and not limiting, unless otherwise specifically noted. Furthermore, the term "or" as used herein is generally intended to mean "and/or" unless otherwise indicated. Combinations of components or steps will also be considered as being noted, where terminology is foreseen as rendering the ability to separate or combine is unclear.
As used in the description herein and throughout the claims that follow, "a", "an", and "the" includes plural references unless the context clearly dictates othenA/ise. Also, as used in the description herein and throughout the claims that follow, the meaning of "in" includes "in" and "on" unless the context clearly dictates othen/vise.
The foregoing description of illustrated embodiments of the present invention, including what is described in the Abstract, is not intended to be exhaustive or to limit the invention to the precise forms disclosed herein. While specific embodiments of, and examples for, the invenfion are described herein for illustrative purposes only, vahous equivalent modifications are possible within the spirit and scope of the present invention, as those skilled in the relevant art will recognize and appreciate. As indicated, these modifications may be made to the present invention in light of the foregoing description of illustrated embodiments of the present invention and are to be included within the spirit and scope of the present invention.
Thus, while the present invention has been described herein with reference to particular embodiments thereof, a latitude of modification, various changes and substitutions are intended in the foregoing disclosures, and it will be appreciated that in some instances some features of embodiments of the invention will be employed without a corresponding use of other features without departing from the scope and spirit of the invention as set forth. Therefore, many modifications may be made to adapt a particular situation or material to the essential scope and spirit of the present invention. It is intended that the invention not be limited to the particular terms used in following claims and/or to the particular embodiment

disclosed as the best mode contemplated for carrying out this invention, but that the invention will include any and all embodiments and equivalents falling within the scope of the appended claims.

GLOSSARY OF TERMS AND THEIR DEFINITIONS
3G: Third Generation wireless networks. These networks are to provide next
generation mobile services with better quality of service and high speed internet and
multimedia services. These include networks such as CDMA2000 1xEV-D0,
CDMA2000 IxEV-DV, WCDMA.
BSC: Base Station Controller.
BTS: Base Transceiver System. Air interface in the 3G wireless networks terminates
at the BTS and the mobile station.
CDMA: Code Division Multiple Access. It is a spread-spectrum technology allowing
many users to occupy the same time and frequency allocations in a given
band/space. It assigns unique codes to each communication to differentiate it from
others in the same spectrum.
CDMA2000 1xEV: This includes CDMA2000 1xEV-D0 and CDMA2000 1xEV-DV.
CDMA2000 1xEV-D0: CDMA2000 Single Carrier Evolution, Data Optimized. It
delivers peak data rates of 2.4 Mbps and is intended to provide high performance
and low cost packet data services.
CDMA2000 1xEV-DV: CDMA2000, Single Carrier, Data and Voice. It provides
integrated voice and simultaneous high-speed packet data multimedia services.
Correspondent Node (CN): It is a node with which the MS is communicating. For
example, it could be a multimedia server or some other mobile station.
Forward link flows: These flows are sending data packets from CN (or WER)
towards the MS.
FTP: File Transfer Protocol. A widely used protocol in the internet used to transfer
files from one point to another point.
HTTP: Hyper-Text Transfer Protocol. A protocol widely used for web browsing
applications in the internet.
IP: Internet Protocol. A layer 3 protocol widely used in the internet.
LCP: Link Control Protocol. It is used to negotiate radio link protocol and options to
control the session in CDMA2000 wireless networks.
MPEG: Moving Picture Experts Group. There are several MPEG standards such as
MPEG-4, MPEG-2 etc.
MS: Mobile station (or mobile device).
NACK: Negative Acknowledgement. In contrast to positive acknowledgements,

NACK is typically sent when a packet is not received within some expected time
interval.
QoS : Quality of service. Applications have different types of requirements and
these should be met by the networks. These include delay bound, delay jitter,
required rate, packet loss, and average delay.
Reverse link flows: These flows are sending data from the MS towards the CN (or
WER).
RLP: Radio Link Protocol. It is a modified form of the automatic repeat request ARQ)
protocol and used in 3G networks to improve reliability of the air-interface,
RSVP: Resource Reservation Protocol. It is a QoS signaling protocol specified in the
RFC2205 and available at www.ietf.org
SCP: Stream Control Protocol. This is used for sending RLP negative
acknowledgements in CDMA2000 networks when missing RLP data is detected.
SIP: Session Initiation Protocol. This session level protocol is used to establish
sessions for streaming/conferencing applications in internet.
TCP: Transport Control Protocol. A layer 4 protocol widely used in the internet.
VoIP: Voice over IP
WCDMA: Wideband Code Division Multiple Access
WER: Wireless Edge Router

WE CLAIM
1. A method for per-flow QoS management in forward link adaptive scheduling
module in a 3G wireless multimedia networks wherein improved per-flow QoS
management in 3G wireless multimedia networks is provided, the QoS requirement
of flows with rate requirements in 3G networks is satisfied, and wherein the present
difficulty in satisfying rate requirements is tackled with guaranteed Quality of Service
wherein to control the manner in which time slots are allocated to different flows and
associated applications, wherein if a flow is lagging behind its required rate more
than another flow, the flow which is lagging more is given higher compensation by
computing the metric QoS_M,^[n], for each flow k, in each slot n, as follows:

2. A system for per-flow efficient resource allocation in 30 wireless multimedia networks wherein an adaptive scheduler is used as the forward link scheduler for this system that decides which packet has to be sent over the air in each slot and also serves the reverse link flows, which also implements various methods to provide QoS guarantees to diverse types of applications in wireless networks, for flows with various requirements viz. required rate, delay bound, delay jitter, average delay and desired rate.
3. A method as claimed in claim 1, wherein a flow which is closer to its required rate than another flow, is given higher compensation compared to a flow which is not that

4. A method as claimed in claim 1, wherein a flow which is further away from its desired rate is given higher compensation compared to a flow which is closer to its desired rate if all flows have already received their required rate, by computing the metric

6. A method as claimed in claim 1, wherein a flow which is closer to its required rate
than another flow, is given higher compensation, considering the flows which have
not met their required rate guarantees and . If all flows have met their required rate
guarantees, then the metric is computed as

7. A method as claimed in claim 1, wherein in higher compensation is given to a
mobile station, whose instantaneous channel conditions are better than its own
average channel conditions and to compensate it even further when it is not able to
get its required rate, the metric, QoS_Mi^[n], is computed for each flow k, in each
slot n, in that If reqrate,^ ^ 0 + ^) *-R^^ovg (") > for 3 small constant s whose default

value satisfies 0
8. A method as claimed in claim 1, wherein higher compensation is given to a mobile
station, Whose instantaneous channel conditions are better than its own average
channel conditions and to compensate it even further to give higher compensation to
flows that are lagging behind their required rate less than others, the metric,
QoS_Mf^[n], is computed for each flow k, in each slot n, in that If
reqrate^
9. A method as claimed in claim 1, wherein higher compensation is given to a mobile
station, whose instantaneous channel conditions are better than its own average
channel condition and if all flows have got their required rate guarantees, to give
further compensation to flow that are lagging behind their desired rate more than
others, the metric is computed as follows:

10. A method as claimed in claim 1, wherein if a flow is lagging behind its required
rate guarantees, the metric, QoS_M^[n], is computed for each flow k, in each slot n,
in that if reqrate,^ satisfies 0

12. A method as claimed in claim 1, wherein to give compensation using a polynomial term, and to give higher compensation to flows which are lagging more than other flows, and to give further compensation when instantaneous channel conditions of a mobile station are better than its own average channel condition, the metric, QoS_M^[n], is computed for each flow k, in each slot n, in that if
reqratei^

13. A method as claimed in claim 1, wherein to give compensation using a polynomial term, the metric , QoS_M^[ri], for each flow k, in each slot n, is
computed in that If reqrate,^
15. A method as claimed in claim 1, wherein to help a flow meet its required rate as well as desired rate, to give compensation using a polynomial term, to make sure that each flow gets its required rate, if excess capacity is available and channel conditions are still favorable, to distribute excess time slots in a way that a flow which is lagging behind its desired rate more than other flows, tend to get its desired rate eariier than the other flows, the metric is QoS __M^[n] = Mj^[n], if

desrate. 0.. Otherwise,

16. A method for per-flow QoS management in fonA/ard link adaptive scheduling module in a 3G wireless multimedia networks wherein to make delay and jitter sensitive flows meet QoS requirements and give compensation to these flows by considering their buffer length for some consecutive slots and by considering the time interval in which the pending packets should be served and wherein the buffer length related compensation term gives higher compensation to flows that have more number of pending packets than other, in that the metric, QoS_M,X^], for each
flow k, in each slot n, is computed as

17. A method as claimed in claim 16, wherein to meet very tight delay and jitter requirements, the maximum of peek (k) (>1) packets for flow k is considered and
QoS_M,^[n], for each flow k, in each slot n, is computed as

19. A method as claimed in claim 16 and 18, wherein the system keeps memory of what happened in the past few slots and uses buffer length for a pre-specified number of previous slots to compensate the flows and for each flow k, there are two pre-specified thresholds, buff _comp_thf^and diff _db comp_t\, such that

20. A method as claimed in claim 16, wherein one can switch between the one
version and another in that the metric QoS_M,^[n], is computed first as

and jitter violation statistics for this flow are monitored and where the fraction of IP packets that have missed their delay bound by the beginning of slot n, and the fraction of IP packet pairs corresponding to flow k that have missed their jitter bounds by the beginning of slot n, are considered, and if these fractions are above some pre-specified threshold values, the metric is then

21. A method as claimed in claim 16, wherein for the scheduler to give higher
compensation to the flows that have smaller number of packets in their queues the
metric, QoS_M^[n], for each flow k, in each slot n, is computed as

22. A method as claimed in claim 21, wherein for flows that have very tight delay and
jitter constraints, the metric is computed as

where m(j) > m{j +1), m(j) > 0, y/,1 23. A method as claimed in claim 21, wherein for flows that have still tighter delay
bound and jitter requirements, the metric is computed as

Qos^MM-n ui, \ \ *n ir^^—T-, *^.w.v^,v^,
where prev(k) is a pre-specified number of slots for flow (queue) k, prev(k) > 0, VA:,
'ftHbuff^^[n-z]^sY\fbuff^J^^^
io t buff,^[n-z] J 1^ buffi^[n] ) [ buff,[n-l] ^
* Abujf^,\n-previK)\^d\ , buffk[n-prev(k)] J
g(0) > g(l) > > g{prev(k) > 0, g(0) > 1,
buff^^ {n-z] = max^ {buff^ [n - z], for those queues k such that bufff^ {n-z]^Q,Q 24. A method as claimed in claim 16, wherein one can switch from one version to another dynamically and for each flow, QoS MfXn], is computed initially as:
QoS_M,[n]^y^^^'^^^^^^^\A ^ *MJn],Vf7,VA:, and after monitoring
delay bound and jitter violation statistics for this flow, and the fraction of IP packets that have missed their delay bound by the beginning of slot n, and the fraction of IP packet pairs corresponding to flow k that have missed their jitter bounds by the beginning of slot n, and if these fractions are above some pre-specified threshold values, the metric is recomputed as

k, there are two pre-specified thresholds, buff _comp_th2^an6 diff dbcompjh^^, such that

27. A method as claimed in claim 16, wherein to make it possible to dynamically switch between different versions, for each flow, and to keep total throughput of a cell as high as possible under any given channel condition and also ensure that QoS requirements of the admitted delay and jitter sensitive flows are met the metric

delay bound and jitter violation statistics for this flow and the fraction of IP packets that have missed their delay bound by the beginning of slot n, and the fraction of IP packet pairs corresponding to flow k that have missed their jitter bounds by the beginning of slot n, and if these fractions are above some pre-specified threshold

where a flow with the maximum value of the metric QoS_M,^[n] in each slot n is selected.
30. A method as claimed in claim 28, wherein the scheduler selection metric,

31. A method as claimed in claim 28, wherein the scheduler selection metric,
QoS_M^[n], for each flow k, in each slot n, is computed as:

32. A method for per-flow QoS management in forward link adaptive scheduling
module in a 3G wireless multimedia networks wherein for flows that have
requirements for delay bound, jitter, required rate as well as desired rate, the
scheduler selection metric, QoS_M,^[n], for each flow k, in each slot n, is computed
as:

V
where
norm _ req _des _ rate _ fac,^ [n] = norm _ reqrate _ fac^ [«], if there is at least one flow such that
reqrate^ >(l + ^)*-RA..vgM.
Otherwise,
norm _ req __ des _ rate _ fac^ \n\ - norm _ desrate _ fac,^ [n].
33. A method as claimed in claim 32, wherein the scheduler selection metric,
QoS_M,^[n], for each flow k, in each slot n, is computed as

34. A method as claimed in claim 32, wherein the scheduler selection metric,
QoS_Mf^[n], for each flow k, in each slot n, is computed as

36. A method as claimed in claim 1, wherein to keep the average delay of flows
within reasonable limits and to maintain lower average delay the scheduler selection
metric, QoS_M,n], for each flow k, in each slot n, is computed as :
" "'JJ avg f 'J
where, C is a scaling constant.
37. A Method for scheduler operation for per-flow QoS management in forward link adaptive scheduling module in a 3G wireless multimedia networks substantially as herein described particularly with reference to drawings.
38. A system for scheduler operation for per-flow QoS management in forward link adaptive scheduling module in a 3G wireless multimedia networks substantially as herein described particularly with reference to drawings.

Documents:

886-che-2003-abstract.pdf

886-che-2003-claims duplicate.pdf

886-che-2003-claims original.pdf

886-che-2003-correspondence others.pdf

886-che-2003-correspondence po.pdf

886-che-2003-description complete duplicate.pdf

886-che-2003-description complete original.pdf

886-che-2003-drawings.pdf

886-che-2003-form 1.pdf

886-che-2003-form 19.pdf

886-che-2003-form 26.pdf

« Previous Patent

Next Patent »

Patent Number

201071

Indian Patent Application Number

886/CHE/2003

PG Journal Number

08/2007

Publication Date

23-Feb-2007

Grant Date

28-Jun-2006

Date of Filing

03-Nov-2003

Name of Patentee

M/S. SAMSUNG INDIA SOFTWARE OPERATIONS PRIVATE LIMITED

Applicant Address

SAMSUNG ELECTRONICS COMPANY LIMITED, KOREA BAGMANE LAKEVIEW, BLOCK 'B', NO.66/1, BAGMANE TECH PARK, C V RAMAN NAGAR, BYRASANDRA, BANGALORE-560093, KARNATAKA, INDIA

Inventors:

#	Inventor's Name	Inventor's Address
1	MUKESH, TANEJA	SAMSUNG ELECTRONICS COMPANY LIMITED, KOREA BAGMANE LAKEVIEW, BLOCK 'B', NO.66/1, BAGMANE TECH PARK, C V RAMAN NAGAR, BYRASANDRA, BANGALORE-560093, KARNATAKA, INDIA

PCT International Classification Number

G06F015/16

PCT International Application Number

N/A

PCT International Filing date

PCT Conventions:

#	PCT Application Number	Date of Convention	Priority Country
1			NA