Title of Invention | METHODS AND SYSTEM FOR FORWARD LINK RESOURCE ALLOCATION IN 3G WIRELESS MULTIMEDIA NETWORKS |
---|---|
Abstract | The present invention relates to efficient resource allocation to different application flows and mobile stations in 3G wireless multimedia networks. Here, an adaptive hierarchical scheduling system and its associated methods are proposed for forward-link flows. Here, a scheduler is split into two levels. One level of the scheduler is used at the base station to decide which mobile station to serve in a given slot and the next level of the scheduler is used to choose a flow to serve for the selected mobile station in that slot. This hierarchical scheduler provides OoS guarantees for different kind of flows in wireless networks and at the same time, control the amount of resources that are allocated to different mobile stations (or user). In addition to meeting OoS requirements of different flows and performance requirements of users, these methods allow a network operator to create different types of per-flow and per-user service level agreements and enforce those for forward link flows via the adaptive hierarchical scheduling system and its methods presented here. The methods take into account the various parameters like rate requirements served rate, required rate, buffer, delay bound, jitter, average delay and waiting time in the system and compensate flows and users using various means. |
Full Text | FIELD OF TECHNOLOGY This invention relates to the field of Wireless Multimedia Networks. Further this invention in general relates to the 3G Wireless Multimedia Networks. More particularly this invention encompasses methods and system for forward link resource allocation in 3G wireless multimedia networks. PRESENT STATE OF ART Some of the 3G wireless networking technologies are CDMA2000 1xEV-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 the 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 (LCP) 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, games, FTP, 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 (TCP, 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), - Forward 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, fonward 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/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 station informs the base station about the rate at which it can accept data in each of this slot on fonA/ard link. This rate can vary rapidly in a wide-area wireless network. Suppose Aj^[n] is the maximum allowed rate at which mobile station k can accept data in slot n from the base station. A forward link scheduling method was used in A. Jalali, R. Padovani, and R. Pankaj, "Data Throughput of CDMA-HDR a High Efficiency High-Data Rate Personal Communication Wireless System", in Proc. of IEEE VTC'OO, May 2000, Vol. 3. It computes the following metric for each mobile: Here, MJn] is the metric for mobile station k, and R.avM) 's computed using an exponentially weighted moving average filter: Here, r, =l/r, where r is a time constant such that 0 selected to be served in slot n, then Rf^[n\ is set to zero. Otherwise, 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, MJn], to serve in slot n. In some 3G wireless networking technologies such as CDMA2000, the maximum allowed rate, ^JA?], 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 CDMA 2000 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 idbj[MS^]) - Packets of each fonA/ard link flow move from the CN to the BS 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 and experience variable delay before they are sent out from the BS to the MS. The delay bound that we consider here is the maximum delay for any IP packet of that flow at the BSC and BTS. For forward link flow k, meiXp{depj(p)-arrj(p)}. dbj[MS^]\s the delay bound for flow j of the MS MS^. 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 (^vgD^[MS'J)- For forward link flow k, it is the average delay experienced by IP packets of flow k on the wireless hop from the base station to the mobile station (i.e. average queuing delay in the BSC and BTS for flow k). For flow j of the MS MS^, it is AvgDj[MS^] • Delay Jitter ( by IP packets of forward link flow k. For forward link flow k, djtr^ = maXp{abs[(dep,^ (p) - arr^ (p)) - {dep^ (/? + !)- arr, (p +1))]}. Here, p and p+1 are consecutive IP packets that have arrived at the BSC at time arrj^(p) and arr^(/? + l)for flow k. • Required Rate {reqratef^)- It is the minimum required rate by flow k. A time scale, ts,^, 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 is used in MPEG-4 flow. For the simple case, when all mobile stations are experiencing same channel conditions and Af^[n] = Aj[n],^k,\/j for each slot n, and the scheduling method is used where a mobile with the maximum value of the metric MJn] (where A \n\ M,^[n] = —^^-^,VA:,Vw) 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 station 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 station 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 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. A mobile station could be running multiple applications at a time. Thus it can have multiple flows with different QoS requirements. These flows could also have different traffic characteristics but the channel conditions associated with all the flows of a mobile station are same. Per-flow QoS is provided to different flows in a network, but at the same time also control the per-mobile station (or per-user) allocation of time slots. As each mobile station could be running multiple applications at a time, per-flow and per-user (or per-mobile station) allocation of time slots would help us to differentiate service given to each mobile station also (in addition to each flow of each mobile station). Thus it is very important to introduce new scheduling methods which would help to meet QoS requirements of applications in 3G wireless multimedia networks and at the same time control the allocation of time slots to each mobile station. Also, as channel conditions for mobile stations typically keep varying in a 3G wireless networks, it is also important that these methods should govern allotment of time slots when some flows are lagging behind their QoS requirements, allocation of time slots when flows start recovering potentially due to better channel condition and/or less load in the network, allocation of excess time slots when all flows are already meeting their QoS requirements and allocation of time slots per-user (or per-mobile station). Thus it is important that new methods should make sure that QoS requirements of applications are satisfied in 3G wireless network and at the same time, these methods should help in offering different schemes by which allocation of time slots would be governed for each flow and each mobile station. This way, these will also help network operators in offering different types of per-flow and per-user service level agreements for QoS management in wireless networks. OBJECTS OF THE INVENTION It is the primary object of the invention to provide methods and system for efficient resource allocation for applications and mobile users in 3G Mobile Wireless Multimedia Networks. It is another object of the invention to invent the adaptive hierarchical scheduling system and resource allocation methods that that can satisfy QoS requirements of diverse types of applications and mobile users in 3G networks. It is the another object of the invention to invent methods to control the manner in which time slots are allocated for different flows and for different mobile users. It is another object of the invention to provide methods that provide performance guarantees not only to application flows but also to mobile users. It is the another object of the invention to provide the methods that provide guaranteed QoS to multimedia streaming applications in 3G 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. SUMMARY OF THE INVENTION The present invention proposes adaptive hierarchical scheduling system and associated methods for forward-link flows and mobile stations for a 30 wireless multimedia network. Here, a scheduler is split into two levels. One level of the scheduler is used at the base station to decide which mobile station to serve in a given slot and the next level of the scheduler is used to choose a flow to serve for the selected mobile station in that slot. This hierarchical scheduler provides QoS guarantees for different kind of flows in wireless networks and at the same time, controls the amount of resources that are allocated to different mobile stations and application flows. In addition to meeting QoS requirements of different flows and users, these methods allow a network operator to create different types of service level agreements for flows as well as mobile users and enforce those for fonA/ard link flows via the methods presented here. Though these are presented for 3G network here, they can also be applied for some other wireless networks. Accordingly, the present invention comprises a method for forward link resource allocation and QoS management in 3G wireless multimedia network using an adaptive hierarchical scheduling system satisfying QoS requirements of diverse applications in the said network, the said method comprising the steps of: a) carrying out QoS management by adaptive hierarchical scheduling; b) scheduling the forward link flows in the base station using a two level hierarchical scheduler wherein it includes i) selecting a flow to serve for the selected mobile by level.I scheduler for each mobile station at the base station; and ii) computing the QoS selection metric by the level II scheduler for all the mobile stations at the base station taking into account buffer, delay bound, average delay and rate related statistics for each mobile station; and c) selecting a mobile station based on the above QoS selection metric computed by the level II scheduler. Accordingly, the present invention further comprises a method for forward link QoS management and resource allocation for different mobile stations and satisfy QoS requirements of flows with rate requirements only in 3G like networks, wherein to control the manner in which time slots are allocated for different flows and for different mobile stations and to allow a different way in which time slots are allocated and thereby result in different service behavior for the users but still meet their per-flow QoS requirements wherein aggregate required rate and aggregate served rate for each mobile station is computed and if a mobile station is lagging behind its aggregate required rate more than another mobile station, the mobile station which is lagging more is given higher compensation in that where all flows have specified required rate requirement only the scheduler selection metric for the forward link level II scheduler is computed as QoS_M_II[MS^,n\, for each MS MSf^ at the beginning of each slot n, as follows: 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 Figure 1 relates to the existing architecture of SGIike networks. Figure 2 shows the protocol end points of a 3G network. Figure 3 shows discrete time wireless system. Figure 4 shows a forward link adaptive hierarchical scheduler of the present invention. Figure 5 shows hierarchical scheduler operation for flows with rate requirements only. Figure 6 shows hierarchical scheduler operation for flows with requirements on delay bound and jitter only. Figure 7 shows hierarchical scheduler operation for flows with requirements on delay bound, jitter and rate. Figure 8 shows hierarchical scheduler operation for flows with requirements on average delay and rate. Figure 9 shows hierarchical scheduler operation for flows and mobile users with diverse performance requirements. DETAILED DESCRIPTION OF THE ACCOMPANYING DRAWINGS Figure 1: The existing 3G network architecture is illustrated where forward and reverse link flows from mobile stations MS, through base stations BS and vice versa is shown comprising the base station catalyst BSC and base transceiver system BTS and through the point coordination function (PCF) and wireless edge router (WER) to the correspondent node (CN) and can even be used for multimedia application on 3G architecture networks. Figure 2: Protocol end points of a 3G network are shown in the Figure 2. 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. Figure 3: Time slots of 3G wireless networks are shown. In each slot "s" each mobile that has data to send informs the access point about the rate at which it can be served in the next slot "s+1". Access point needs to decide which mobile (and flow) to serve in each slot. Rate specified by a mobile could be specified in terms of number of fixed size packets or bytes that can be sent and the number of slots taken by these packets. Figure 4: The forward link adaptive hierarchical scheduler is shown comprising of two level hierarchical scheduler for forward link flows at the base station in that level I scheduler for each mobile station at the base station is provided for selecting a flow to serve for the selected mobile and level II scheduler for all the mobile stations at the base station which level II scheduler takes into account buffer, delay and rate related statistics for each mobile station and computes a QoS selection metric using several different methods and a mobile station to serve is selected based on this QoS selection metric computed by the level II scheduler. Figure 5: illustrates the operation of forward link adaptive hierarchical scheduler for flows with rate requirements only. Figure 6: illustrates the operation of forward link adaptive hierarchical scheduler for flows with delay bound and jitter requirements only. Figure 7: illustrates the operation of forward link adaptive hierarchical scheduler for flows with delay bound, jitter and rate requirements only. Figure 8: illustrates the operation of forward link adaptive hierarchical scheduler for flows with average delay and rate requirements only. Figure 9: illustrates the operation of fonward link adaptive hierarchical scheduler for flows and mobile users with heterogeneous performance requirements. DETAILED DESCRIPTION OF THE INVENTION A preferred embodiment of the present invention will now be explained with reference to the accompanying drawings. It should be understood however that the disclosed embodiment is merely exemplary of the invention, which may be embodied in various forms. The following description and drawings are not to be construed as limiting the invention and numerous specific details are described to provide a thorough understanding of the present invention, as the basis for the claims and as a basis for teaching one skilled in the art how to make and/or use the invention. However in certain instances, well-known or conventional details are not described in order not to unnecessarily obscure the present invention in detail. The present invention proposes an adaptive hierarchical forward link scheduling system and associated methods for efficient resource allocation and QoS management for forward link flows and mobile stations in 3G wireless networks. In the system described here, each mobile station can have multiple forward link flows and the base station keeps one queue for each forward link flow that has some QoS requirements. For example, a mobile could be running two applications - one VoIP session and other MPEG-4 conferencing. In this case, for forward link flows, the base station maintains one queue for VoIP packets, one queue for MPEG-4 video flow, and one queue for MPEG-4 audio flow. It would typically also maintain one separate queue for control packet flows. Hierarchical forward link scheduler selects a mobile station and an associated flow that can send data in each slot towards an MS. There are two levels of forward link schedulers shown in the Figure 4. These two works together to decide which mobile and which flow should be allowed to send data in each slot on the fonA^ard link (i.e. from the BS to an MS) A): Adaptive Hierarchical Scheduler for Flows with Rate Requirements only In this section, the forward link flows that specify only the rate requirements are considered. In the system presented here, a flow can specify either its required rate or 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 have service for better or faster service. This desired rate can not be less than the required rate. The operation is illustrated in figure 5. For the case, when all flows have rate requirements only, the level I forward link scheduler aggregates rate requirements of all the flows for each mobile station and also computes aggregate served rate for each mobile station. Suppose reqrate{MS^,f) is the required rate of forward link flow f of the MS MS^. Define aggregate required rate of the MS MS^ to be agg_reqrate{MSf^) = ^reqrate{MS,^,f), where the MS MS^ has J^ forward link flows. Similarly, define the aggregate served rate of the MS MS^^ to be agg _ servedrate{MSj^' ^) ~ X ^^^^drate{MS,^»/, '^). where servedrate{MS,^, /, n) Is the served rate of forward link flow f of the MS M5^ at the beginning of the slot n, Jj^ is the total number of forward link flows of the MS MS^ and servedrate{MS^ J^n)^ i?^^,^ {n) for flow f Of the MS MS^. Method -1 (For Level II Scheduler) Here first consider the case where all flows have specified required rate requirement only. In this method, the level I forward link scheduler (as shown in the Figure 5) at the BTS computes agg_servedrate{MSf^,n) for each mobile MS,^ at the beginning of each slot n. It uses agg _ servedrate{MS^, n) and agg_regrate(MS^) to compute the scheduler selection metric for the forward link level II scheduler, QoS_M_II[MS,^,n], for each MS MS^ at the beginning of each slot n, as follows: norm _ agg _ reqrate _ fac{MS^ ,«] = !, agg _ reqrate{MSf^) Otherwise, norm __ agg _ reqrate _ fac[MS^, n] ~ ""^-"^^ * (agg _ reqrate{MSf^) - agg _ servedrate{MS,^,«)). We choose a suitable value of r^^^,^ such that agg_re9ra^e(MS,) = 5(M5',)*r,,,,_,^^, ^^CMS,) > l,r,,,,_,^^ > 0,V^. It also has. 5n.ax_.,,-max,{S(M5,)}. For each MS MS^, a threshold norm_agg_reqrate_fac_th{MS^), is specified and following is always ensured: norm _ agg _ reqrate _ fac[MS^, n] In each slot n when the scheduler needs to select a flow to serve, the fon/vard link level II scheduler first considers the mobile stations that have at least one nonempty queue and for which agg_reqrate{MS^) > agg_servedrate{MS,^,n). If there is at least one such mobile station, it selects an MS with the maximum value of the metricgo5'_M_//[MS'^,/7]. Let the selected MS by the level II scheduler at the beginning of slot n be denoted byMS^^, jj[n]. The forward link level I scheduler of the selected MS, MS^^, jj[n], considers all the flows of this mobile and selects a flow to serve based upon its own selection metric that it calculates separately. On the other hand, if no mobile station was selected by the level II scheduler in the above step, we have agg_reqrate(MS,^) select the one with the maximum value of QoS_M_II[MS^,n]. Once a mobile station has been selected via the level II scheduler, a flow to serve for that mobile station is selected using mechanism I or II as given below. Mechanism -1 (For Level I Scheduler) The level I scheduler (corresponding to each MS at the BTS) keeps track of the average served rate of each of its flow. Let F{MS^.^i fj[n],\), ,F(MS^^,_jj[n],J^^ijj) be the J^.^, j, flows of the MS MS^^,_j,[n]. Further suppose that reqratef^{MS^^1 ;/[«]) be the required rate and servedrate^iMS^^, //[«],«) be the served rate of flow k of the MS MS^^f_jj[n] at the beginning of slot n. Compute the following selection metric: QoS__M_I,[MS^.^, ,j[nln] = = -—— ~- = , considering each flow k (with non-empty queue) of the MS MS^.^, jj[n] and select a flow with the maximum value of QoS_M_I,^[MS^^i jj[n],n]. If there is at least one flow such that reqrate^iMS^^^ jj[n])> servedrate^{MS^^, jj[n],n), it would select a flow that is lagging behind its required rate by a higher fraction than other flows for the MS MS^.^, jj[n]. On the other hand, if reqrate,^ (MS^^,_ii [n]) MS^^i jj [n], it would select a flow that has the minimum value of servedrate,{MS^^^ ,j{nln)~reqrate,{MS^^, ,\ri\) .,,.-.^... ^ = at the beginning of slot n. reqrate^(MS^^ij^[n]) Mechanism - II (For Level I Scheduler) In mechanism I, the level I scheduler in the selected MS MS^.^, jj[n], selects a flow that is lagging more than other flows for that MS. The mechanism II given here does the opposite and selects a flow that is lagging less than the other flows. If channel conditions of a mobile becomes very bad and it is not possible to serve all the flows (or recover all the lagging flows), then this mechanism gives an option where at least some flows of that mobile which have been doing relatively better than other flows, can be kept in good condition and these flows are recovered sooner than other flows. Consider the set of flows for the MS MS^^^ jj[n\ for which reqrate^{MS^^f jj[n])> serv€drate,^{MS^^i jj[n],n). For these flows, compute the following selection metric: out of these flows, select a flow with the minimum value of QoS_M_Ij^[MS^^, JJ[«],«]. On the other hand, if reqrate^ (MS^^, jj [/?]) MS^^i ii[n], then compute the following selection metric: ^ c AY r r.Yc r i ^ ^ervedrate,{MS^^j jj[nlri)-reqrate,{MS^^^ jj[n\) the level I scheduler selects a flow with the minimum value of QoS_M__I,[MS,,, jj[nln]. Method - II (For Level II Scheduler) The method also works to achieve the required rate requirement as in the Method I but tends to do the opposite of what is done there while compensating lagging mobile stations. Specifically, if an MS (say M5,) is lagging more than another MS (say, MS'J, then the MS MS^ is given higher compensation than the MS MS^ and the MS MS2 tends to achieve its aggregate rate earlier than the MS MS,. In wireless networks, it could happen that some users are initially admitted in the system after observing their channel conditions but as channel conditions can vary rapidly, it may become not feasible to satisfy QoS requirements of some of the flows (and corresponding users) 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 users (and thus of their flows) who are closer to their required rate requirements than the users that are lagging more. In such cases, the method given here can be used. For this method, compute the metric, QoSM_II[MS,^,n\, for each MS MSf^ at the beginning of each slot n, as follows: QoS_M __II[MS,,ri\ = ^^ ,VA:,V«, if agg _ servedraie(MS ^, n) agg _ reqrate(MSf^) Otherwise, QoS_M_II[MS,,n] = * ^^^ ,VA:,Vn norm _ agg _ reqrate _ fac[MS,^, n] agg _ servedrate{MS j^, n) Here, norm_agg_reqrate_fac[MS,^,n], Is as defined in the Method (I) and Z is chosen such that Z > "'"^-'^^ * agg _ reqrate{MS^), for each MS A/S^. For each r base _ agg MS MSf^, a \hxes,\\Q\6 norm agg ^reqrate _fac _th\{MS^), is specified and following is always ensured: Z norm _ agg _ reqrate _ fac[MS^, n] The foHA/ard link level II scheduler considers the mobile stations that have at least one non-empty queue and out of these considers only those mobile stations for which agg_reqrate(MSf^)>agg_servedrate(MS^,n), If there is at least one such mobile station, it selects an MS with the maximum value of the metric QoS_M_II[MS,^,n], in each slot n when it needs to select a mobile station to serve. If no mobile station has been selected in this step, we have agg_reqrate{MS,^) QoS_M_II[MS,,n] = ^^^ ,VA:,Vw, and an MS with the agg _ servedrate{MS j^, n) maximum value of QoS_M_II[MS^,n] is selected to be served in this slot. Once an MS has been selected by the level II scheduler using this method, the level I scheduler of this MS selects a flow to serve using either Mechanism I or Mechanism II given earlier. Method - III (For Level II Scheduler) This method can be used for the case where at least one flow has specified required rate as well as desired rate. For flows that have not specified their desired rate, it is assumed that their desired rate is equal to their required rate. In the system presented here, a network operator would charge on the basis of the required rate as well as the desired rate specified by each mobile station. Do as follows: 1. At the beginning of some slot n when the level II scheduler needs to select a mobile to serve, consider the set of mobile stations for which the aggregate served rate is less than the aggregate required rate and agg _ reqrate{MSf^) > agg _ servedrate{MS^, n). While taking scheduling decisions, we only consider those mobile stations that have at least one non-empty queue each. If this set is empty, go to step 2. Otherwise, do as specified in this step. Compute the metric QoS_M_II[MSj^,n\ for the mobile stations in this set as follows: 2. If no mobile station was selected in step 1, we have agg _ reqrate(MSj^) which there is at least one non-empty queue at the base station at the beginning of slot n. Consider the set of mobile stations for which agg_servedrate{MSj^) an MS to serve, that has maximum value of the metric QoS_M_II[MS,^,n Once an MS has been selected via the level II scheduler as described in the above steps, select a flow to serve for this MS using level I scheduler (as per Mechanism I and II described earlier). Method - IV (For Level II Scheduler) The level II scheduler of this method works as follows: 1. Here first consider the mobile stations that have some packets enqueued at the base station for them and agg_reqrate{MS^) > agg_servedrate(MS,^,n), at the beginning of slot n, when the hierarchical scheduler needs to decide a mobile station and a flow to serve. If there is at least one such mobile station, compute the following metric for these mobile stations: 2. If no mobile station was selected in step 1, we have agg_reqrate{MSf^) Once an MS has been selected via the level II scheduler as described in the above steps, select a flow to serve for this MS using level I scheduler (as per Mechanisms I or II described earlier). Method - V (For Level II Scheduler) This method uses a different compensation factor than used in the earlier methods and results in different allocation of resources to mobile users. The level II scheduler of this method works as follows: 1. First consider the mobile stations that have some packets enqueued at the base station for them and agg_reqrate{MS^)>agg_servedrate(MSf^,n), at the beginning of slot n, when the hierarchical scheduler needs to decide a mobile station and a flow to serve. If there is at least one such mobile station, compute the following metric for these mobile stations: If there is at least one such mobile station, pick up one with the maximum value of the metric QoS_M_II[MS,^,n]. Otherwise, go to the step 2 below. 2. Same as step 2 in the method given in the Method IV. 3. Same as step 3 in the method given in the Method IV. Once an MS has been selected via the level II scheduler as described in the above steps, select a flow to serve for this MS using level I scheduler (as per Mechanisms I or II described earlier.) B): Hierarchical Scheduler for Flows with Delay Bound and Jitter Requirements Now the flows that have specified their delay bound and jitter requirements are considered Multimedia conferencing, streaming and VoIP applications have QoS requirements related to delay bound and delay jitter experienced by IP packets belonging to the 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 in 3G networks. The hierarchical scheduling methods given here work on these MAC packets but provide delay and jitter guarantees for the IP packets. The operation is illustrated in figure 6. Consider the queues at the BTS in a 3G wireless network. Here one queue per-flow is maintained. We need to give delay bound and jitter guarantees to the IP packets corresponding to these flows. Packets in these BTS queues are usually smaller size MAC packets. Let Wj^[MS,^,n] be the number of time slots for which the (MAC) packet p of flow j of the MS MS^ has been in the queue by time slot n. If Wj^[MSk,n]>dbj(MSf^), this packet is dropped. Here, dbj{MS,^), is the delay bound of flow j of the MS MS^. Otherwise, it is kept in the queue and counted for the purpose of the methods below. Let buff.{MS^,n\ be the buffer length of queue corresponding to flow j of the MS MS^^ at the beginning of slot n, in the BTS. This buffer length could be counted either in bytes or using the number of MAC packets if same size MAC packets are used in the system. Using the notations defined earlier, F(MSj^J) is the jth flow of the MS MS^ and this MS has total of J^ forward link flows. Method -VI (For Level II Scheduler) In this method, the level II scheduler computes the metric, QoS_M_II[MS,^,n], for each MS MS^, at the beginning of each slot n, as follows: First consider the first term (related to agg__buff) above. To keep delay jitter of delay and jitter sensitive flows (such as video conferencing, VoIP etc.) quite low, start compensating mobile stations with delay and jitter sensitive flows as soon as they have got some MAC packets in their queues at the base station. The first compensating term does this at macro level. Consider all the fonA/ard link flows of each MS and compute a compensation term that uses normalized aggregate buffer of each MS and gives higher compensation to that MS which has higher value of this term. The packets that have not already violated their delay bounds is only kept and counted. If a mobile, MS",, has larger aggregate queue lengths (as defined below) than another MS, MS^, the MS MS*! would be given higher compensation via this term. We not only look at the current slot n, but also look at the previous prev(k) slots for the MS MS^, while computing this compensation term. agg_buff[MS^,n-z] is the aggregate buffer length of the MS MS^, at the beginning of the slot (n-z), and is defined as: length of flow j of the MS MS^at the beginning of the slot (n-z), and m_rate[MSi^J] is the input rate of flow j of the MS MS^. This input rate could be a pre-specified average input rate or could be set equal to effective bandwidth of that flow, prev(k) is the pre-specified (non-negative) number of slots for the MS MS,^ for which buffer lengths is taken into account while computing compensation for delay and jitter flows for each mobile station. Now the second term is considered that is used while computing the metric QoS_M_II[MSf^,n\. There are multiple queues for the MS MS^ at the base station, each carrying delay and jitter sensitive packets. The higher compensation is given to the mobile stations that have higher number of packets waiting in the base station closer to their delay bounds. To compute the second term of the compensation above, look at a total of peek (k) packets for the MS MS^. Select those peek (k) packets whose waiting time in the base station (i.e. at the BSC and the BTS) is closer to their delay bounds than other packets. Note that these peek (k) packets could belong to different flows for the MS MS^. To find these peek(k) packets, the base station keeps a list of peek(k) packets for each MS that are in the ascending order of the difference between their delay bound and the time spent by that packet in the base station (i.e. at the BSC and the BTS). Suppose that the hth packet belongs to the flow F{MSf^j{h)) ,\ Here, t/Z?^^^j[MS'J is the delay bound of the flow F(MS^,j(h)), Wj^^^f,[MS^,n] is the time spent by the hth packet of the MS MS,^ in the base station. Note that this hth packet belongs to the flow F{MSf^J{h)) but is not necessarily the hth packet of the flow F{MSf^, j{h)). The constants m(h) are pre-specified such that m{h) > 0, m{h) > m(h +1),1 This helps to ensure that these terms do not become very large and thus no mobile (and flow) is allocated large number of consecutive or close-by slots unreasonably as that might not be fair to other flows. The level II scheduler selects a mobile to serve that has the maximum value of the metric QoS_M_II[MS,^,n]. Once an MS has been selected by the level II scheduler, the level I scheduler decides which flows to start serving in that slot for that MS. To do this, it uses Mechanism III described below. Mechanism III (For Level I Scheduler): Level I scheduler considers those delay and jitter sensitive flows of the selected MS (i.e. the MS that was selected by the level II scheduler) that have non-empty queues at the beginning of the slot n. Next, it selects a flow to serve whose first packet in the queue (head-of-line packet) has been in the base station (i.e. at the BSC and the BTS) for a period that is closest to its delay bound. Specifically, the level I scheduler of the selected MS selects that flow j for this MS for which {db^-Wj,[MS^^^^_^^,_jj,n]} Is minimum. Here, MS^^,_^^,_jj[n] is the MS that was selected by the level II scheduler at the beginning of the slot n. Method - VII (For Level II Scheduler) In the Method VI, one of the compensation terms gives higher compensation to the MS that has higher number of pending packets in the queues corresponding to its queues (over the mobile stations 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 VI. To handle this sort of situation, one can use the method proposed here. Using the method given here, the scheduler would give higher compensation to the mobile stations that have smaller number of packets in their queues and thus tend to satisfy those users first. In this method, the level II scheduler computes the metric, QoS_M_II[MS,^,n], for each MS A/S^, at the beginning of each slot n, as follows: as defined in the Method I. Once an MS has been selected, the level I scheduler selects a flow to serve using Mechanism III as described earlier. Method -Vlil (For Level II Scheduler) The level II scheduler computes the metric, QoS_M_II[MSf^,n], for each MS MSf^. at the beginning of each slot n, as follows: and Nbuff[n] is the number of mobile stations that have at least one non-empty queue at the base station 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, we keep two pre-specified thresholds, ogg_buff _comp_th2,^Bn6 diff _agg_db_comp_th,^, such that diff _agg_db_comp_thf^ and other terms are as explained in the Method VI. This helps to ensure that these terms do not become very large and thus no MS is allocated large number of consecutive or close-by slots unreasonably as that might not be fair to other mobile stations (and their flows). The level II scheduler selects an MS that has the maximum value of the metric QoS_M_II[MS,^,n]. Once an MS has been selected by the level II scheduler, the level I scheduler selects a flow to serve for that MS using the method described in the Mechanism III. Method - IX (For Level II Scheduler) In this method, the level II scheduler computes the metric, QoS_M_II[MS,^,n], for each MS MS^, at the beginning of each slot n. as follows: r Here, C and Tj are scaling constants (for j\\ has non-empty queue at the beginning of the slot n. As mentioned earlier, the MS MSj^ has total of J^ forward link flows. For each MS MS^, we keep two pre- specified thresholds, agg_buff_comp_th3,^ar\d diff_db_comp_agg_th\,^, such that The level II scheduler selects an MS that has the maximum value of the metric QoS_M_II[MS^,n]. Once an MS has been selected by the level II scheduler, the level I scheduler selects a flow to serve for that MS using the Mechanism III C): Hierarchical Scheduler for Flows with Delay Bound, Jitter and Rate Requirements Now the flows that have requirements on delay bound, jitter and throughput (i.e. rate) are considered. The operation is illustrated in figure 7. Method - X (For Level II Scheduler) Level II scheduler computes the following QoS selection metric: Here, norm_agg_reqrate_fac[MS^,n] is as defined in the Method I. Other compensation terms are as defined in the Method VI. The level II scheduler selects an MS that has the maximum value of the metric QoS_M_II[MS,^,n]. Mechanism IV: (For Level I Scheduler) The level I scheduler of the selected MS selects that flow j for this MS for which {dbj-Wj,[MS^^^,^^,jj,n]} is minimum. Here, M5,,,^,, ,;M is the MS that was selected by the level II scheduler at the beginning of the slot n. Method - XI (For Level II Scheduler) Here, norm_agg_reqrate_fac[MS,^,n] and Z are as defined in the Method II. Other compensation terms are as defined in the Method VI. The level II scheduler selects an MS that has the maximum value of the metric QoS_M_II[MSf^,n]. The level I scheduler of the selected MS selects that flow j for this MS using Mechanism IV. Method - XII (For Level II Scheduler) Methods I and VIII are combined and modified here. In this method, the level II scheduler computes the metric, QoS_M_II[MSi^,n], for each MS M5^, at the beginning of each slot n, as follows: Here, norm_agg_reqrate_fac[MS,^,n] is as defined in the Method I. Other compensation terms are as defined in the Method VIII. The level II scheduler selects an MS that has the maximum value of the metric QoS_M_II[MS,^,n]. The level I scheduler of the selected MS selects a flow to serve for this selected MS using Mechanism IV. Method - Xiil (For Level II Scheduler) Method I and Method IX are combined and modified here. In this method, the level II scheduler computes the metric, QoS_M_II[MS^,n], for each MS MS^, at the beginning of each slot n, as follows: Here, norm_agg_reqrate_fac[MS^,n] is as defined in the Method I. Other compensation terms are as defined in the Method I and Method IX. The level II scheduler selects an MS that has the maximum value of the metric QoS_M_II[MS,^,n]. The level I scheduler of the selected MS uses Mechanism IV to select a flow to serve for that MS. D): Hierarchical Scheduler for Flows with Average Delay and Rate Requirements Method - XIV (For Level II Scheduler) 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. Consider the scenario when all the flows in a network have requirements over average delay and rate only. In this method, the level II scheduler computes the metric, QoS_M_II{MS^,n\, for each MS MS^, at the beginning of each slot n, as follows: QoS__M_II[MS,,n] = norm_agg_reqrate_ fac[MS,,n]* ^^^-^"-^[^"^^'"J * agg _ buff^^ [n] - T] * ^^ —,V)t,V« agg _ serve drate(MSf^, n) Here, agg_buff is as defined in the Method I. The level II scheduler selects an MS that has the maximum value of the metric QoS_M_II[MS,^,n]. The level I scheduler of the selected MS selects a flow to serve using the mechanism V. The operation is illustrated in figure 8. Mechanism V: (For Level I Scheduler) The level I scheduler of the selected MS selects a flow to serve for this MS using Mechanism I or II described earlier. E): Adaptive Hierarchical Scheduling System for Heterogeneous Flows and Mobile Users with Diverse Performance Reguirements In general, there could be some flows that have rate requirements only, some flows that are delay and jitter sensitive (and have delay bound, jitter and/or rate requirements) and some other flows that have average delay requirements. In this situation, use the adaptive hierarchical scheduling system as below: The operation is illustrated in figure 9. Suppose the MS MS^ has A'^^ flows that have only the rate requirements, A^^ ^,^ flows that have requirements over delay bound and jitter, A^^ ^, ^ ^ flows that have requirements over delay bound, jitter and rate, andA^^,^^ ,^ flows that have requirements for average delay and rate. There could also be some other best effort flows that do not have any QoS requirements. As the total number of QoS aware flows for the MS MS,^ is J^ at the beginning of some slot n, we have ^r,k '^ ^d_ji,k '^ ^d_jt_r,k "*" ^avgd_r,k ~ ^k ' Do as follows for level II scheduler: - For N^j^ flows with rate requirements only, choose one of the method for level II scheduler from Method I to Method V, depending upon performance objectives of flows and mobile stations. Also, choose either Mechanism I or Mechanism II depending upon performance objectives. Compute the metric QoS_M_II[MS^,n] using this selected method. Denote this by {QoS_M_II[MS^,n])^. If all such flows have empty queues at the beginning of the slot n for the MS MS,, set (QoS _M _II[MS,,n])^=0. - For N^ j,f^ delay bound and jitter sensitive flows, choose one of the methods for level II scheduler from Method VI to Method IX, depending upon performance objectives of flows and mobile stations. Compute the metric QoS_M_II[MS,^,n] for each of these delay and jitter sensitive flows as per this selected method. Denote this by {QoS_M_II[MS^,n])^ j^. If all such flows have empty queues at the beginning of the slot n for the MS MS,, set {QoS_^M_II[MS,,n]), j,=0, - For N^ j^ ^, delay, jitter and rate sensitive flows, choose one of the methods for level II scheduler from Method X to Method XIII, depending upon performance objectives of flows and mobile stations. Compute the metric QoS_M__II[MS^,n] as per this selected method. Denote this by {QoS_M_II[MSj^,n])^ ^, ^. If all such flows have empty queues at the beginning oftheslotnforthe MS MS,,set (eo5_M_//[M5,,w])^ j, ,=0. - For A'^^^,^^ ^, flows that have average delay and rate requirements, compute the metric QoS_M_II[MS,^,n] using the Method XIV. Denote this by {QoS_M_II[MS^,n])^^g^ ^. If all such flows have empty queues at the beginning of the slot n, set (go5_M_//[MS,,w])^^g^^=0. - Selection metric for the level II scheduler for the MS M^,, QoS _M _II _hetew[MS^,n], is computed to be equal to {QoS_M_II[MS,,n])/iQoS^M JI[MS,,n]), / {QoS_M_II[MS,,n]), J, ^*(QoS^M_II[MS,,n])^,^, ^. Select an MS that has maximum value of this metric, QoS_M 11 _hetero[MS^,n], at the beginning of the slot n. Once an MS has been selected by the level II scheduler, level I scheduler of that MS selects a flow to serve in that slot. It first considers the delay and jitter (and/or rate) sensitive flows (only the ones with non-empty queues) and chooses one whose first (i.e. head-of-line) packet has been in the base station for a time period which is closest to its delay bound. If there is no such flow, it considers other QoS-aware flows and picks up one to serve using either Mechanism I or Mechanism II. Here an adaptive hierarchical scheduling system and several methods have been proposed to satisfy QoS requirements of diverse types of applications in 3G networks. These methods also control the manner in which time slots are allocated for different flows (and associated applications) and for different mobile stations (or users). Each of these allows a different way in which time slots are allocated. As mobile stations also ask for different data rate in each slot (based upon their channel conditions) and have applications with different traffic characteristics, these results in different service behavior for the users (but still meet per-flow QoS requirements). Network operators can formulate different types of per-flow and per-user service level agreements using these for 3G wireless networks It will also be obvious to those skilled in the art that other control methods and apparatuses can be derived from the combinations of the various methods and apparatuses of the present invention as taught by the description and the accompanying drawings and these shall also be considered within the scope of the present invention. Further, description of such combinations and variations is therefore omitted above. It should also be noted that the host for storing the applications include but not limited to a computer, printer or a multi function device. Although the present invention has been fully describecl in connection with the preferred embodiments thereof with reference to the accompanying drawings, it is to be noted that various changes and modifications are possible and are apparent to those skilled in the art. Such changes and modifications are to be understood as included within the scope of the present invention as defined by the appended claims unless they depart therefrom. 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 1xEV-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 (orWER). 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 atwww.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 forward link resource allocation and QoS management in 3G wireless multimedia network using an adaptive hierarchical scheduling system satisfying QoS requirements of diverse applications in the said network, the said method comprising the steps of: a) carrying out QoS management by adaptive hierarchical scheduling; b) scheduling the forward link flows in the base station using a two level hierarchical scheduler wherein it includes iii) selecting a flow to serve for the selected mobile by level.I scheduler for each mobile station at the base station; and iv) computing the QoS selection metric by the level II scheduler for all the mobile stations at the base station taking into account buffer, delay bound, average delay and rate related statistics for each mobile station; and c) selecting a mobile station based on the above QoS selection metric computed by the level II scheduler. 2. A method for forward link QoS management and resource allocation for different mobile stations and satisfy QoS requirements of flows with rate requirements only in 3G like networks, wherein to control the manner in which time slots are allocated for different flows and for different mobile stations and to allow a different way in which time slots are allocated and thereby result in different service behavior for the users but still meet their per-flow QoS requirements wherein aggregate required rate and aggregate served rate for each mobile station is computed and if a mobile station is lagging behind its aggregate required rate more than another mobile station, the mobile station which is lagging more is given higher compensation in that where all flows have specified required rate requirement only the scheduler selection metric for the forward link level II scheduler is computed as QoS_M_II[MS^,n], for each MS MS,^ at the beginning of each slot n, as follows: where for each MS MS^, a threshold norm_agg_reqrate_fac_th{MS^), is specified such that: norm _ agg _ reqrate __ fac[MSj^, n] 3. A method as claimed in claim 2, wherein when a flow that is lagging more than other flows for that MS is given higher compensation, the selection metric of level I scheduler is computed as considering each flow k (with non-empty queue) of the MS MS^^i jj[n] and a flow with the maximum value of QoS_M_I^[MS^^^ u[^].n\ is selected wherein if there is at least one flow such that reqrate^{MS^^^ /^[«]) > servedrate^(MS^^j ij[n],n) ,a flow that is lagging behind its required rate by a higher fraction than other flows for the 4. A method as claimed in claim 2, wherein when channel conditions of a mobile station becomes very bad and it is not possible to serve all the flows or recover all the lagging flows, then at least some flows of that mobile which have been doing relatively better than other flows, are kept in good condition and these flows are recovered sooner than other flows, in that a flow that is lagging less than the other flows is selected and where reqratef^(MS^^, jj[n])>servedrate^(MS^^, ji[n],n), the selection metric of the level I scheduler is computed as 5. A method as claimed in claim 2, wherein when it is no longer possible to satisfy rate requirement of all the users for some time period if some of them experience very bad channel conditions during that period, to satisfy requirement of at least some users, a mobile station which is closer to its aggregate required rate than another mobile station, is given higher compensation compared to a mobile station which is not so close to its aggregate required rate in that a flow to serve for the selected mobile station is selected and the metric, QoS_M_II[MSf^,n], for each MS MS,^ at the beginning of each slot n, is computed as : 6. A method as claimed in claim 2, wherein for a flow to meet its required rate as well as desired rate requirements in a 3G wireless network, and to ensure that each mobile station gets its aggregate required rate and each flow gets its required rate and where excess slots are available, to provide aggregate desired rate for each mobile station and desired rate for each flow and where if the mobile stations have at least one non-empty queue each, and if there is at least one mobile station whose average aggregate served rate is less than its aggregate required rate, then the metric QoS_M_II[MS^,n] for the mobile stations in this 8. A method as claimed in claim 2, wherein to allow a flow to meet its required rate requirements in a 3G wireless network and to give higher compensation to a mobile station, and to achieve its required rate sooner than other mobile stations in that when there is at least one mobile station that has some packets enqueued at the base station, the metric for these mobile stations is computed as agg_reqrate{MS^) > and where a mobile station, with the maximum value of the metric QoS_M_II[MS,^,n] is selected. 9. A method as claimed in claim 8, wherein when agg_reqrate{MSf^) n, and if this set is non-empty, an MS that has maximum value of the metric QoS _M _ II[MSf^, n] is selected where 10. A method as claimed in claim 2, wherein to allow a flow to meet its required rate requirements in a 3G wireless network to have different allocation of time slots for each mobile station and for each flow to satisfy QoS requirements, and considering the mobile stations that have some packets enqueued at the base station for them when agg _ reqrate{MS^) > agg _ servedrate(MSj^, w), at the beginning of slot n, and if there is at least one such mobile station, metric for these 11. A method for forward link QoS management and to satisfy QoS requirements of applications with delay bound and jitter requirements in 3G networks, wherein to control the manner in which time slots are allocated for different flows and for different mobile stations and to allow a different way in which time slots are allocated and thereby result in different service behavior for the users but still meet their per-flow QoS requirements wherein, to give compensation to flows for delay bound and jitter, the compensation factors are increased in that delay and jitter sensitive flows can meet their QoS requirements in that the level II scheduler computes the metric, QoS_M_II[MS^,n], for each MS MS,^, at the beginning of each slot n, as follows: * 12. A method as claimed in claim 11, wherein to allow delay and jitter sensitive flows to meet their QoS requirements, the scheduler would give higher compensation to the mobile stations that have smaller number of packets in their queues and thus tend to satisfy those mobile stations first in that the level II scheduler computes the metric, QoS_M_II[MS,^,n], for each MS MS,^, at the beginning of each slot n, as follows: constant and Nbufffn] is the number of mobile stations that have at least one nonempty queue at the base station at the beginning of slot n and in that it is ensured that no MS is allocated large number of consecutive slots unreasonably and the level II scheduler selects an MS that has the maximum value of the metric QoS_M_II[MS,,n]. 14. A method as claimed in claim 11, wherein to allow delay and jitter sensitive flows to meet their QoS requirements, the level II scheduler computes the metric, QoS_M_II[MSf^,n], for each MS MSj^, at the beginning of each slot n, as follows: where, C and Tj are scaling constants (for j:\ 15. A method for forward link QoS management and to satisfy QoS requirements of applications with delay bound, jitter and rate requirements in 3G networks, wherein to control the manner in which time slots are allocated for different flows and for different mobile stations and to allow a different way in which time slots are allocated and thereby result in different service behavior for the users but still meet their QoS requirements wherein, to allow a flow to meet its delay bound, jitter and rate requirements the metric is computed as where, the level II scheduler selects an MS that has the maximum value of the metric QoS_M_II[MSi^,n] and the level I scheduler of the selected MS selects that flow j for this MS for which {dbj -w^^lMS^^j ^^^ ,j,n]} is minimum and in that, ^^sei mob ij[^] is the MS that was selected by the level II scheduler at the beginning of the slot n. 16. A method as claimed in claim 15, wherein to allow a flow to meet its delay bound, jitter and rate requirements, the metric is computed as where the level II scheduler selects an MS that has the maximum value of the metric QoS_M_II[MS,^,n]an6 the level I scheduler of the selected MS selects that flow] for this MS for which {dbj -WJ^[MS^^, ^^^ jj,n]} is minimum and in that, MS^^i ^^^ ii[n] is the MS that was selected by the level II scheduler at the beginning of the slot n. 17. A method as claimed in claim 15, wherein to allow a flow to meet its delay bound, jitter and rate requirements, the level II scheduler computes the metric, QoS_M_II[MS,^,n], for each MS MS^, at the beginning of each slot n, as follows: where, the level II scheduler selects an MS that has the maximum value of the metric QoS_M_II[MS^,n]Br\6 the level I scheduler of the selected MS selects that flow j for this MS for which {dbj ~Wj^[MS^^i ^^^ jj,n\} is minimum and where, ^^sei mobjii^] 's the MS that was selected by the level II scheduler at the beginning of the slot n. 18. A method as claimed in claim 15, wherein to allow a flow to meet its delay bound, jitter and rate requirements, the level II scheduler computes the metric, QoS_M_II[MSf^,n\, for each MS MS^, at the beginning of each slot n, as follows: where, the level II scheduler selects an MS that has the maximum value of the metric QoS_M_II[MS,^,n]ar\d the level I scheduler of the selected MS selects that flow j for this MS for which {dbj -w.^[MS^.^, ^^^ jj,n\} is minimum and in that, MS^^f ff,o6 //[^] is the MS that was selected by the level II scheduler at the beginning of the slot n. 19. A method for forward link QoS management and to satisfy QoS requirements of applications with average delay and rate requirements in 3G networks, wherein to control the manner in which time slots are allocated for different flows and for different mobile stations and to allow a different way in which time slots are allocated and thereby result in different service behavior for the users but still meet their QoS requirements wherein to allow a flow to meet its lower average delay and rate requirements, the level II scheduler computes the metric, QoS_M_II{MSf^,n\, for each MS MSj^, at the beginning of each slot n, as follows: where, the level II scheduler selects an MS that has the maximum value of the metric QoS_M_II[MS,^,n\.ar\6 the level I scheduler of the selected MS selects a flow to serve for this MS . 20. A method for operating an adaptive hierarchical scheduling system using resource allocation methods where for forward link QoS management and to satisfy performance requirements of flows as well as mobile users, the level I scheduler computes QoS selection metric for flows belonging to different classes. Viz. rate and average delay; delay bound and delay jitter rate etc either singularly or in combination and then selects a mobile station to serve and further it selects a flow to serve for that mobile station using an appropriate mechanism for level 1 scheduler. 21. A method for fon/vard link resource allocation and QoS management in 3G wireless multimedia network using an adaptive hierarchical scheduling system satisfying QoS requirements of diverse applications in the said network such as substantially herein described and claimed particularly with reference to the drawings. |
---|
887-che-2003-claims duplicate.pdf
887-che-2003-claims original.pdf
887-che-2003-correspondence others.pdf
887-che-2003-correspondence po.pdf
887-che-2003-description complete duplicate.pdf
887-che-2003-description complete original.pdf
Patent Number | 203489 | ||||||||
---|---|---|---|---|---|---|---|---|---|
Indian Patent Application Number | 887/CHE/2003 | ||||||||
PG Journal Number | 05/2007 | ||||||||
Publication Date | 02-Feb-2007 | ||||||||
Grant Date | 20-Nov-2006 | ||||||||
Date of Filing | 03-Nov-2003 | ||||||||
Name of Patentee | M/S. SAMSUNG INDIA SOFTWARE OPERATIONS PRIVATE LIMITED | ||||||||
Applicant Address | BAGMANE LLAKEVIEW, BLOCK 'B', NO. 66/1, BAGAMANE TECH PARK, C V RAMAN NAGAR BYRASANDRA, | ||||||||
Inventors:
|
|||||||||
PCT International Classification Number | G08B 25/10 | ||||||||
PCT International Application Number | N/A | ||||||||
PCT International Filing date | |||||||||
PCT Conventions:
|