Title of Invention	SYSTEM AND METHODS FOR RESOURCE ALLOCATION IN HETEROGENEOUS WIRELESS MULTIMEDIA NETWORKS
Abstract	In this invention, systems and methods are developed related to heterogeneous wireless multimedia network and application. In particular, in a multi-hop heterogeneous wireless network consisting of IEEE 802.11x (wireless LAN) and 3G wireless network, QoS issues related to heterogeneous applications are considered. The invention addresses the method and solves the problems related to resource allocation involved in heterogeneous wireless multimedia networks for diverse types of applications.

Title of Invention

SYSTEM AND METHODS FOR RESOURCE ALLOCATION IN HETEROGENEOUS WIRELESS MULTIMEDIA NETWORKS

Abstract

In this invention, systems and methods are developed related to heterogeneous wireless multimedia network and application. In particular, in a multi-hop heterogeneous wireless network consisting of IEEE 802.11x (wireless LAN) and 3G wireless network, QoS issues related to heterogeneous applications are considered. The invention addresses the method and solves the problems related to resource allocation involved in heterogeneous wireless multimedia networks for diverse types of applications.

Full Text	FIELD OF TECHNOLOGY This invention relates to the field of heterogeneous wireless multimedia networks. Further this invention relates to transport of traffic from heterogeneous applications in two types of wireless networks - one a wide-area wireless network where channel conditions could change rapidly (such as 3G) and another a mobile wireless local area network (such as WLAN IEEE 802.11x). In particular this invention encompasses system and method for resource allocation for transport of traffic from heterogeneous applications to and from mobile devices within a WLAN, a 3G and an integrated 3G WLAN network. PRESENT STATE OF ART There are different types of networking technologies available in the wireless market today. At some places, 3G wireless technologies like CDMA 2000 IxEV-DO, CDMA 2000 1xEV-DV and WCDMA are being standardized [3,4] and deployed [5]. On the other hand, wireless LAN technologies (IEEE 802.11 series of standards) are being standardized ([6]) and also deployed at some places. Many of these WLAN systems are being deployed in the places like hotels, airports, (usually called WLAN hotspots) etc. allowing mobile users to use WLAN services at these places. In several cases, as a mobile user moves out of these places (wlan hotspots), the MS might still want to continue running its applications (such as multimedia conferencing and/or streaming, VoIP sessions etc.) and thus would need to continue getting service via some wireless networks. As 3G networks are being deployed at some places, in many networks this service may be provided via a 3G network. Thus it becomes important to have mechanisms that allow support of multimedia and other applications over heterogeneous networks such as 3G and WLAN. Wireless local area networks (WLAN), 3G networks as well as 3G-WLAN integrated networks would potentially need to 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 micro flow or a macro flow. Here, a micro flow 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 macro flow is described via the following 3-tuple: IP source address, IP destination address, and Layer 4 protocol type. Many flows have certain quality of service (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 terms of delay bound, delay jitter, throughput and packet loss. Many of these multimedia applications use UDP/RTP protocols for transport of data. For some other TCP based applications, such as web browsing, keeping average delay below a pre-specified value is desirable. Heterogeneous Wireless Multimedia Networks Heterogeneous wireless multimedia networks are considered where one wireless network is a wide-area wireless network and another is a local area wireless network. Wide-area wireless networks provide packet data services to mobile users. There is an access point in this wireless network and all the mobile users communicate via this. Typically in a wide-area mobile wireless network, users could be pedestrian or vehicular and may move at quite different speeds. In such networks, channel conditions of users can change rapidly and the rate at which they can communicate with other nodes is also dependent over their channel conditions. In general, the access point or some sort of distributed mechanism needs to decide which nodes can transmit data at a given time. Next, a local area wireless network is considered which provides packet data service to users in an area of smaller range such as in a hotel, airport, train, bus, small building etc. Here also there is an access point for this network and users communicate via this access point. Users can directly communicate with each other, bypassing the access point, in this network. Alternatively, users can communicate with each other via the access point which relays the messages from one user to another in its own network. In such local area networks, usually user mobility is limited compared to that in wide-area wireless network. Here also, the centralized access point or a distributed mechanism needs to decide which users can transmit data at any given time. Next, a heterogeneous wireless network is considered where both of these networks need to coexist at a place. For example, user could access internet services via the local area wireless network whose access point in turn relay data via the access point of wide-area wireless network. Once that user moves out of the range of local area network or is no longer getting good quality from the access point of local area network, it could access internet services directly via the access point of wide area wireless network. Such a heterogeneous network is shown in the Figure 1. Now consider 3G networks which is an example of wide-area wireless network considered above, wireless local area networks (WLAN) which is an example of local area networks mentioned above and an integrated 3G-WLAN network which is an example of heterogeneous network considered above. 3G Networks A schematic diagram of a 30 network is shown in Figure 2 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 (ON) and can even be used for multimedia application on 3G architecture networks. Here, MS is the mobile station, BSC is the base station controller, BTS is the base transceiver system, 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 [10]. The BS (base station) essentially includes the BSC and the BTS shown in figure 2. In addition to the QoS requirements of the traffic flows, the resource allocation mechanisms also depend on the medium access control layer (MAC) and the physical layer characteristics of the network. In a 3G network, time is typically divided into fixed time periods called slots. For example, in a CDMA2000 1xEV-DO networks the time period of a slot is 1.67 milliseconds. Each mobile device informs the base station about the rate at which it can accept data in each of these slots on the forward link. This discrete time system is shown in the Figure 3 where 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. This rate can vary rapidly in a wide-area wireless network. Suppose /ij«] 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 used in [8]. It computes the following metric for each mobile: In some 3G wireless networking technologies suckle 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 system are shown in the table 1 below. Table 1. Data rates in CDMA 2000 system Data Rate (kilobits per Packet length (bytes) Number of slots second) 38.4 128 16 76.8 128 8 153.6 128 4 307.2 128 ^ 2 614.4 1^8 1 1228.8 256 1 1843.2 384 1 2457.6 512 i WLAN A schematic diagram of a WLAN network is shown in Figure 4. Here, MS is a mobile station wirelessly connected to the access point AP. Each AP provides connectivity to a set of MS called a basic service set (BSS) in IEEE 802.11 parlance. In a BSS, mobile stations are controlled by one logical function (called, "coordination function"), that decides when a station can transmit or receive. Multiple AP"s can be connected to each other using a wired or wireless backbone (distribution system) resulting in a WLAN with extended reach. This is called an extended service set (ESS) in the IEEE 802.11 parlance. One ESS has one 32-octet long service set identifier (SSID). Each BSS has a 6-octet long basic service set identifier (BSSID) which is same as the MAC address of radio in the access point. The manner in which air-link resources are allocated to different mobile users and their applications over the air interfaces in a wireless network, determines the performance of different applications and utilization of network resources. For this purpose, one needs to have efficient traffic scheduling mechanisms to control traffic flows in both directions over the air interface, i.e. from 3G BTS in the 3G network or from the WLAN AP in WLAN network, to the mobile station in one direction (called poniard link direction), and from WLAN-MS to WLAN-AP, or from a 3G-MS to a 3G BTS in the other direction (called reverse link direction). For WLAN, the popular IEEE 802.11 standard [6] defines a MAC layer which is very different from that of a 3G network. Specifically two modes of medium access are defined. The first mode called point coordination function (PCF) is a contention free mode in which medium access is controlled by AP using a polling mechanism. In this mode the AP gives permission to a MS to transmit a data frame by sending a poll message to that MS. In this mode a MS transmits only when it receives a poll message from AP giving it permission to transmit. The second mode of operation called distributed coordination function (DCF) is contention mode in which all MS and also the AP use mechanisms which are quite similar to the carrier sense multiple access with collision avoidance (CSMA/CA) technique for medium access. Each device in WLAN maintains a variable called network allocation vector (NAV) which is the remaining busy period of the shared busy channel. The protocol has some pre-defined inter-frame space (IFS) time periods with increasing duration: short IFS (SIFS), point coordination function IFS (PIFS), and distributed coordination function (DIFS). The IFSs are mandatory periods of idle time and are used to control event priorities. As per IEEE 802.11 standards, correct receipt of a packet is signaled through the ACK packet. An ACK should be returned SIFS time period after the successful reception of a packet. Time is divided into contention periods (CP) where DCF access is used and the contention free periods (CFP) where PCF access is used. DCF mode is shown in the Figure 5. Figure 6 shows the coexistence of PCF and DCF mode in a WLAN. Here "B" denotes a beacon signal that is sent periodically by the AP to signal the start of PCF mode. At the start of PCF mode the AP and all MS set their NAV to a pre-defined value which is the maximum length of contention free period (CFP). The AP and the MS synchronously decrement NAV to measure the elapsed time in slots. Thus the beacon B and NAV help to synchronize AP and the MS. Under special circumstances the AP may signal an early termination of CFP by sending "End" signal to all MS as shown in figure 6. In PCF mode a point coordinator (PC) inside the AP determines the order in which the and reverse link flows of different MS are served. This is achieved by sending a poll message to a MS along with any forward link flow data frame if available. The poll message essentially gives an MS the opportunity to transmit a reverse link flow data frame back to the MS. Thus both forward and reverse link flows are scheduled by the AP. Figure 7 shows an example of various messages exchanged between the AP and MS in the PCF mode. Here D1, D2 etc, are data frames for forward link flows to mobiles stations 1, 2 etc. The ACK frames acknowledge receipt of data frame. The frames U1, U2 etc are reverse link flow data frames from mobile stations 1, 2 etc. For efficient communication the AP can combine the poll, ACK and data frames into a single frame. Similarly on the reverse link the mobile stations can combine the ACK and data frames. The IEEE 802.11 standard permits variable length data frames to be transmitted on both foHA/ard and reverse direction. The maximum allowable size of an IEEE 802.11 frame is 2348 bytes. Figure 8 shows IEEE 802.11 frame format with details of frame control field. The Duration field gives the duration of transmission. The CRC field allows for error checking at the receiver. The time taken to transmit the data frames in forward and reverse directions varies with the size of the frames. The frame control field has 2 type bits and 4 subtype bits that identify the frame type. Type value of 00 is used to indicate management frame (such as Beacon, Probe Request, Probe Response, Authentication, De-authentication, Association Request, Association Response, Power management, Re-association etc.). Type value of 01 is used to indicate control frame such as RTS, CTS, ACK, Contention Free (CF)-End, Power save (PS)-Poll etc. Type value of 10 is used to indicate data frames. Description of address fields is given in the table 2. These addresses are interpreted using the values of the To DS and From DS bit fields. The To DS bit is set to one if a frame is destined to the AP for forwarding it to the distribution system (DS). It is also set to one when the destination is in the same BSS but the AP has to relay the frame. In all other cases, it is set to zero. The From DS bit is set to one when a frame is coming from the distribution system. SA is the source address and DA is the destination address. All stations filter on the value of the address 1 field. It is the recipient address i.e. the station on the BSS which is the immediate recipient of the packet. If the To DS bit is set to zero, the address 1 field carries address of the destination station. If the To DS bit is set to one, it is the address of the AP. Address2 identifies the transmitter address (TA) to which the ACK frame should be sent to. If From DS bit is set to one, it is the AP"s address. If the From DS bit is set to zero, it is the address of the source station. Value of Address 3 depends upon the To DS and From DS bits. In most cases, it is the remaining missing address. Address 4 is used to identify the original source of the wireless distribution system frames where frame is transmitted from one AP to another AP. The More Fragment bit is to indicate that more fragments belonging to the same frame follow the current fragment. The Retry bit is set to one if it is transmission of a previous frame. This bit is used by the receiver to identify duplicate transmission of a packet from the sender for the case when the ACK packet sent by the receiver is lost. The More Data bit implies that station has more data to send. AP can use this to indicate that there is more data buffered for this mobile station. The Power Management bit is 1 if the transmitting station is in sleep mode. The WEP bit is set to 1 if the wired equivalency protocol is implemented. The Order bit is set to 1 if any data frame is sent using the strictly ordered service. Sequence control is for numbering and reassembly. The sequence number field is made of two fields - fragment number and sequence number. It is used to represent order of different fragments belonging to the same frame. It also helps in recognizing packet duplications. Further details of IEEE 802.11 MAC layer can be found in [1,6]. ToDS From DS Address 1 Address 2 Address 3 Address 4 0 0 DA SA BSSID N/A 0 1 DA BSSID SA N/A 1 0 BSSID SA DA N/A 1 1 RA TA DA SA Table 2: Description of Address Fields in the IEEE 802.11 Frame An Integrated 3G-WLAN Network We consider a 3G-WLAN internetworking scenario as proposed in [7]. In this case, WLAN network is interconnected with the internet using a 3G radio link. It can happen for the cases where a WLAN network is located in a train and thus its WLAN access point is moving with the train. Mobile devices are allowed access to internet via a 3G-WLAN network. It is also noted in [7] that for countries with less developed fixed infrastructure, 3G networks can be used to backhaul traffic from fixed WLAN installations. In this 3G-WLAN architecture, a 3G terminal is connected to the WLAN access point. User traffic to Internet is sent via two wireless hops, first on WLAN air interface and then on a 3G air interface. A schematic of a heterogeneous 3G-WLAN network Is shown in Figure 9. Here three different kinds of mobile stations are shown. A WLAN-MS mobile station is part of the basic service set of a WLAN. It communicates with a correspondent node (CN) on the internet using two wireless hops. The first wireless hop is from WLAN-MS to the WLAN AP. The WLAN AP is connected to a 3G-MS terminal. The second wireless hop is from the 3G-MS terminal to the 3G BTS. A second type of mobile station 3G-MS communicates with the ON using a single wireless hop to the 3G-BTS. The third type of mobile station is denoted by 3G-WLAN-MS. For some application flows, it communicates via the WLAN-AP and for some other application flows, it communicates via the 3G-BTS. The manner In which alr-IInk resources are allocated to different mobile users and their applications over the two air interfaces of a 3G-WLAN network, determines the performance of different applications and utilization of network resources. For this purpose, one needs to have efficient traffic scheduling mechanisms to control traffic flows in both directions over the air interface. I.e. from 3G BTS to WLAN AP over the air interface and from WLAN AP to WLAN-MS over the air interface in one direction (called fon/vard link direction), and from WLAN-MS to WLAN-AP to a 3G BTS in the other direction (called reverse link direction). LIMITATIONS A WLAN-MS can have several application flows In forward and reverse direction with different traffic characteristics and different quality of service requirements. Each of these WLAN-MS can also experience different channel conditions which would in turn control the rate at which these mobile stations can send data to the WLAN-AP and receive data from the WLAN-AP. In a WLAN network, flows of a WLAN-MS in the forward and reverse directions compete for air-link resources with flows belonging to other WLAN-MS nodes. WLAN MAC protocol works in two modes - PCF and DCF. The PCF mode is intended to be used for real-time traffic flows. One needs efficient scheduling mechanisms to decide the polling order that can be used by the WLAN AP to poll nodes while in the PCF mode. These scheduling mechanisms should incorporate information related to forward link queues which are at the WLAN AP as well as related to reverse link queues which are at the WLAN-MS mobile stations. To meet the QoS requirements of fon/vard and reverse link flows wireless networks, per-flow scheduling mechanisms are required at the access point such as at 3G BTS in 3G networks, and at WLAN-AP in the WLAN networks. In [8] a scheduling method was used for 3G networks. In general, this method does not satisfy QoS requirements of flows with diverse performance requirements. In an integrated 3G-WLAN network, WLAN-MS nodes may have some forward link flows which are traversing two wireless hops (i.e. 3G-BTS to 3G-MS and WLAN-AP to WLAN-MS). In such cases, some of the WLAN-MS forward link flows are also competing for resources with other 3G fon/vard link flows. On the reverse link the WLAN-MS flows compete for WLAN air-link resources with other WLAN-MS nodes and for the 3G air-link resources with other 3G-MS and WLAN-MS. In an integrated 3G-WLAN network, two wireless hops may be involved for some mobile stations (i.e. WLAN-MS nodes) while there is only one wireless hop in a pure 3G network. One needs to have a queuing and associated scheduling system for integrated 3G-WLAN network that can provide efficient utilization of resources for application flows, mobile users as well as for network operators. There is also need to have efficient scheduling methods for integrated 3G-WLAN network to provide desired performance guarantees to different application flows with different fairness objectives. OBJECTS OF THE INVENTION The primary object of this invention to invent a system and methods for resource allocation in Heterogeneous Wireless Multimedia Networks. It is another object of the invention to invent a scheduling system and new adaptive scheduling methods for the PCF (point coordinated function) mode of medium access control of IEEE 802.11x (WLAN) wireless network. It is another object of the invention to invent new adaptive scheduling methods for the 3G wireless multimedia networks. It is another object of the invention to meet the required QoS related objectives of multimedia application over the heterogeneous network. It is another object of the invention to meet the required QoS related objectives of applications with average delay and rate requirements over the heterogeneous network. It is another object of the invention to invent methods by which the present difficulty of resource allocation for the multimedia application with guaranteed QoS on a two-hop heterogeneous wireless network where one hop includes 3G air-interface and another hop includes WLAN air-interface and WLAN access point communicates with 3G base station over the air-interface, is overcome. SUMMARY SUMMARY OF INVENTION This invention first proposes adaptive scheduling methods that can be used in wide-area and local wireless multimedia networks. Next, it proposes a scheduling system and associated adaptive scheduling methods for the PCF mode for the medium access control of WLAN. This system and associated methods are to be used to provide performance guarantees to forward as well as reverse link flows in a WLAN network. These also allow a WLAN network operator to specify different types of fairness objectives and associated service level agreements for mobile users. In the PCF mode, the WLAN-AP needs to decide the order in which to poll the mobile nodes (WLAN-MS). Once the AP has decided which node to poll at a given time, it sends polling message to that node in the forward direction. It can also send data for that node along with this polling message in the fonA/ard direction. It again needs to decide how much data to send for that node. If the mobile station (WLAN-MS) successfully receives this packet, it sends an ACK to the WLAN-AP. This mobile node can also send data along with this ACK to the WLAN-AP. As there could be delay, rate and delay jitter sensitive data in forward as well reverse directions, the order in which nodes are polled (and amount of data to be transmitted is determined), plays crucial role in QoS management of diverse types of applications in a WLAN network. Adaptive scheduling methods invented here can be used to satisfy performance requirements of various types of applications in WLAN networks. Accordingly the present invention comprises an adaptive scheduling method for efficient resource allocation in wide-area and local-area wireless multimedia network wherein the compensation of flows that are not achieving their desired buff _comp,[t„]-queue at time "" quality of service, is done by the adaptive scheduler, in that, for delay jitter sensitive flows, when the flows have some packets in their queue, higher compensation is given to flows that have larger buffer lengths and the compensation is computed as: for all flows k for which there is non-empty Accordingly, the present invention further comprises a scheduling system for efficient resource allocation in WLAN networks comprising: a) scheduler, SF_AP, which considers all the forward link flows and computes fonward link QoS compensation metrics for all of them; b) scheduler, SVR_AP, which works on virtual reverse link queues and computes reverse link QoS compensation metrics for all of them; and c) third level of scheduler, S_AP, which considers all the flows and uses the QoS compensation metrics computed by SF_AP and SVR_AP to select a flow and a mobile station to serve in that a QoS control packet. Is provided which MAC layer control packet conveys QoS related information from mobile station to WLAN AP. 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 depicts a heterogeneous wireless network consisting of Access point with wide area wireless network in conjunction with wireless LAN with its access point; Fig 2 depicts 3G Network Architecture consisting of Mobile station, BTS and wireless edge router with forward and reverse links; Fig 3 depicts Wireless access points of 3G network with time slots Fig. 3 Time slots of 3G wireless networks; Fig 4 depicts the co-existence of multiple wireless LAN with Extended Service Set (ESS); Fig 5 depicts the DCF mode of wireless LAN; Fig 6 depicts the co-existence of PCF and DCF modes of heterogeneous network; Fig 7 depicts the communication in PCF mode; Fig 8 depicts the field format of IEEE 802.11; Fig 9 depicts an integrated view of heterogeneous network consisting of 3G (3 Generation Wireless Network) and wireless LAN; Fig 10 depicts the scheduling system for wireless LAN with multiple MS and AP forming forward and reverse link; Fig 11 depicts the plot of traffic profile and input bits for a flow; Fig 12 depicts the flow chart for system initialization with reference to the methods for the heterogeneous network; Fig 13 depicts the flow chart of WLAN scheduling system in heterogeneous network; Figure 14 depicts Frame Body of QoS Control Packet; Figure 15 depicts Queue Management for an integrated 3G-WLAN Network. DETAILED DESCRIPTION OF THE INVENTION 1. Adaptive Scheduler for Efficient Resource Allocation in Wireless Multimedia Networks The invention first proposes adaptive scheduling methods that can be used for efficient resource allocation in wireless multimedia networks. These can be used in several different types of wireless networks including the 3G and the WLAN wireless multimedia networks. This adaptive scheduler compensates flows that are not getting their desired quality of service using several fairness criterions. These methods also do resource allocation using different types of fairness objectives when excess resources are available. Delay and Jitter Compensation Due to Buffered Packets Method I - Delay and Jitter Compensation Due To Buffered Packets We define normalized buffer size of forward link delay bound and jitter sensitive flow k at time ?„ to be rate of forward link flow k. as well as reverse directions. For example multimedia conferencing flows requires that the delay, rate and delay jitter requirements be satisfied for both forward and reverse link video and audio flows. Multimedia streaming applications would usually send data in one direction only (such as using RTP packets) but will have some control packets in the reverse direction (such as RTCP control packets). Scheduling System (ForWLAN) Flows are separated into forward link flows from the AP to MS and reverse link flows from MS to AP. The flows consist of MAC layer packets. Each MS could have multiple flows with different traffic requirements in both directions. For each forward link flow to an MS, the WLAN-AP maintains a queue of MAC layer packets. Similarly for each reverse link flow an MS maintains a queue of MAC layer packets. For each reverse link flow, we also keep a virtual queue at the WLAN-AP. Figure 10 shows the schematic representation of these flows and respective queues. For Figure 10: F(x, y): Queue corresponding to forward link flow x of WLAN-MS y at the WLAN-AP R(x, y): Queue corresponding to reverse link flow x of WLAN-MS y at the WLAN-AP Fm(x, y): Queue corresponding to forward link flow x of WLAN-MS y at the WLAN-MS y Rm(x, y): Queue corresponding to reverse link flow x of WLAN-MS y at the WLAN-MS y VR(x, y): Virtual reverse queue at the WLAN-AP, corresponding to Rm(x, y) at the WLAN-MS y SF_AP: Scheduler for forward link flows at the WLAN AP SVR_AP: Scheduler for virtual reverse link queues at the WLAN_AP S_AP: Scheduler at the AP SR_MSy: Scheduler for reverse link flows for MS y at the MS y Each flow has Its specific quality of service requirement which can be specified by some of the parameters such as delay bound, delay jitter, average delay, throughput, and packet loss. The flow requirements are negotiated between the AP and the MS on per flow basis using some protocol during the connection setup phase. One could use RSVP, described in RFC2205, www.ietf.org. for this purpose. Once the QoS requirements and traffic characteristics are known, an AP must optimize its polling scheme such that these QoS requirements are met for all flows In WLAN. In the system described here, the scheduler is located at the WLAN access point (WLAN-AP) but does scheduling for fonA/ard as well as reverse link flows. For reverse link flows, it maintains virtual reverse queues corresponding to reverse link queues at each WLAN-MS. We monitor packets corresponding to forward as well as reverse link flows at the WLAN-AP and calculate their rate and delay violation statistics. We use these to compensate flows that are not getting their required QoS guarantees. In the system described here, each reverse link flow k conform to a traffic profile /^ where /^(.) is a concave piece-wise linear function. It would typically be a function of burstiness, peak rate and long-term average rate. For such a flow k, the number of bits generated between time t^ and ?2, R^{t^,t^), satisfy the following: Ri^{t^,tj) is shown in the Figure 11. This can be enforced by either policing or shaping reverse link traffic at each WLAM MS. The WLAN-AP keeps track of number of bits transmitted by each mobile station for each flow. Let Tx^(tJ be the number of bits transmitted for flow k by its corresponding mobile station, WLAN-MS, by the time instant /„. A suitable method is chosen to give appropriate compensation or to penalize some flows depending upon their QoS characteristics. This is shown in the Figure 12. One scheduler, SF_AP, considers all the forward link flows and computes fonA/ard link QoS compensation metrics for all of them. Another scheduler, SVR_AP, works on virtual reverse link queues and computes reverse link QoS compensation metrics for all of them. A next level of scheduler, S_AP, considers all the flows and uses the QoS compensation metrics computed by SF_AP and SVR_AP to select a flow and a mobile station to serve. This is shown in the Figure 13. We also define a new MAC layer control packet which is used to convey QoS related information from mobile station to WLAN AP. We call it QoS control packet. In the system described here, a particular WLAN network may enable or disable use of this control packet. If this QoS control packet is not used, then for each reverse link flow k, compute buffer,^ (?„) = max {/?^ (0, f„) - 7x^ (?„ ),0}. For each reverse link flow k, we also allow a pre-specified upper threshold, bu/Jer thres maxi^ , and ensure that buffer^(tJ number of bits transmitted for reverse link flow k by its corresponding mobile station, WLAN-MS, by the time instant t„. This computed buffer^{tj is used to compute scheduler selection metric in WLAN networks. On the other hand, if use of the QoS control packet is enabled, this packet is used to convey QoS related information from the mobile station to WLAN AP for reverse link flows. With this information, the access point can refine its estimate of buffer^{t„) for reverse link flows. We define structure of this QoS control packet as follows: QoS Control Packet: Type = 01 (to indicate that it is a control packet) Subtype = reserve a subtype for this which is not used currently for any other purpose. To DS = 1 From DS = 0 Address 1 = BSSID (address of MAC of radio in the WLAN AP) Address 2 = SA (address of WLAN MS that is sending this control packet to AP) Address 3 = N/A (Don"t use for QoS control packet) Address 4 = N/A (is not used when To DS=1 and From DS=0) Frame body: 1 octet Flow Identifier followed by one or more QoS TLVs where the QoS TLVs are defined below. In the system described here, the WLAN-AP assigns unique 1-octet flow identifier per-flow per mobile station for fon/vard as well as reverse link flows for each mobile station in the WLAN BSS. Combination of MAC address of mobile station and flow identifier assigned by the WLAN AP identifies a flow uniquely in a BSS. Multiple flows from a mobile station can send information in the same QoS control packet. It defines the following QoS TLVs: QDepth TLV, DelayedLen TLV, and DroppedLen TLV. One or more of these could be sent. This is shown in Figure 14. Here, Type is a 3 bit field, length is 5-bit field and carries length of the value field. QDepth TLV: Type = 0x01, Length = 2 octets. Value: Length of pending packets in the queue for a reverse link flow at the mobile station which is identified by the flow id in the first octet of the frame body. Delayed Len TLV: Total length of packets that waited in the queue at the WLAN mobile station for a period which is larger than a pre-specified waiting time threshold. DroppedLen TLV: Total length of dropped packets in the queue, for reverse link flow identified by the flow id in the first octet of frame body, that was dropped before it could be transmitted due to delay or jitter violation. WLAN Scheduling System - Dynamic Mode We now propose a dynamic mode for the above WLAN scheduling system where we switch from one method another dynamically. for buffer compensation. If after some time A;, compensation. If after some time At, switch to Method XIV for compensation. If after some time A;, back to Method XII for compensation due to dropped packets. Scheduling Methods for the PCF Mode of WLAN Let Q^[t„] be the QoS compensation metrics of a uni-directional flow k at time /„ in a WLAN network. Note that this flow k could be fonA/ard or reverse direction flow in a WLAN network. Method XV - Forward Link Per-Flow QoS Compensation Metric for Flows with Delay Bound, Delay Jitter and Rate Requirements Now we consider forward link flows that need performance guarantees for delay bound, rate and delay jitter. For these flows, queues are maintained at the WLAN AP. For each such flow k, we define QoS compensation metric as follows: all time instants /"„. To compute the above, a suitable method for each compensation term is chosen based upon performance and fairness objectives. Method XVI - Forward Link Per-Flow QoS Compensation Metric for Flows with Average Delay, or Average Delay and Rate Requirements Now consider forward link flows is considered that need performance guarantees for average delay or for average delay and rate. For these flows, queues are maintained at the WLAN AP. For each such flow k, we define QoS compensation metric as follows: To compute the above, a suitable method for each compensation term is chosen based upon performance and fairness objectives. Method XVII- Reverse Link Per-Flow QoS Compensation IVIetric for WLAN Scheduler For the reverse link flows, data packets are buffered in the WLAN-MS queues first and complete information is not available at the WLAN access point. For each reverse link flow, we maintain a virtual reverse link queue at the WLAN-AP. bound, jitter and rate, c Method XVIII - Scheduling Decision for the PCF Mode of WLAN If k is a forward link flow, we denote Its QoS compensation (or scheduler selection) metric, Q^, computed by the scheduler SF_AP, by g^ „ . If j is reverse link flow, its QoS compensation (or scheduler selection) metric {Qj) is computed by considering its virtual reverse link queue using Method XVII and we denote it by Qjjfi^. We consider the case when use of the QoS control MAC packet has been disabled in the system and the access point estimates buffer^{tj as in the method XVII, for each reverse link flow k that has some requirement over delay bound, jitter or average delay. The scheduler S_AP considers all the queues corresponding to forward link flows and all the virtual queues corresponding to reverse link flows, and selects a flow to sen/e for which scheduler selection metric, Q, is equal to max imum^j {g^ ^^ [t], bj * g^ „, [/] - Oy}, Considering each forward link flows k and each reverse link flow j which has some requirement over delay bound or delay jitter or average delay. Here, bj is a finite, pre-specified, positive number, b. a J, is a pre-specified non-negative finite number. If there are multiple flows, ties are broken randomly. if no flow is selected for which there is some requirement over delay bound and jitter, or average delay, then a flow with rate requirement is chosen which is not getting its forward or reverse link, required rate guarantees. If no such flow has any packets pending at that time, any other flow is served. Method XIX - Scheduling Decision for the PCF Mode of WLAN If k is a forward link flow, we denote its QoS compensation (or scheduler selection) metric, g^, computed by the scheduler SF_AP, by g^ „ . If j is reverse link flow, its QoS compensation (or scheduler selection) metric {Qj) is computed by considering its virtual reverse link queue using Method XVII and we denote it by QuKL ■ A case is considered when use of the QoS control MAC packet has been enabled in the system. As the access point may not always have latest information about the reverse link queues at the mobile stations, the access point still estimates 6M#er^(^„) as in the method XVII, for each reverse link flow k that has some requirement over delay bound, jitter or average delay. In this case also, the scheduler S_AP considers all the queues corresponding to forward link flows and all the virtual queues corresponding to reverse link flows, and selects a flow to serve as in the Method XVIII but values of h. and a^ can change with time and their values need not be in ranges which are specified in the Method XVIII. Specifically, the scheduler selection metric, Q, is used as xmximum^.{Q^P^Xt\, 6^[^]*gy,/;i-a,[^]}, considering each forward link flows k and each reverse link flow j which has some requirement over delay bound or delay jitter or average delay. If QoS control MAC packet is received for a reverse link flow k at time s, then actual information regarding queue length etc. is used from that control packet and we use, 6j5] = l and a^\s\ = ^. There is a pre-specified time period, T(k), in the system for each reverse link flow k. If no other QoS control packet is received for flow k until the time (s+T(k)), we reset 6, \s + T{K)\ = b,, and a, [s + T(k)] = a,. 3. Scheduling Methods for 3G Wireless Multimedia Networks Method XX - Per-Flow QoS Compensation Metric for Flows with Delay Bound, Delay Jitter and Rate Requirements Now we consider flows that need performance guarantees for delay bound, rate and delay jitter in a 3G network. For each such flow k, we define QoS compensation metric as follows: hops, one in WLAN BSS and another in 3G network, use vomit (at 3G-BTS) > virater (at WLAN-AP). For Method XIII for an integrated 3G-WLAN network: To compute compensation for WLAN-MS flows that go via two wireless networks and thus two wireless hops, one in WLAN BSS and another in 3G network, use aura/e(at 3G-BTS) > a rate (at WLAN-AP). For Method XIV for an integrated 3G-WLAN network: To compute compensation for WLAN-MS flows that go via two wireless networks and thus two wireless hops, one in WLAN BSS and another in 3G network, use p rate (at 3G-BTS) > i3_rafe (at WLAN-AP). While the invention has been particularly described with reference to a preferred embodiment, it will be understood by those skilled in the art that various changes in form and detail may be made therein without departing from the spirit and scope of the invention. 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. ACK: Acknowledgement AP: Access Point BSA: Basic Service Area BSC: Base Station Controller. BSS: Basic Service Set 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 IxEV-DO: 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. CFP: Contention Free Period CP: Contention Period CSMA/CA: Carrier Sense Multiple Access with Collision Avoidance CTS: Clear To Send DCF: Distributed Coordination Function DS: Distributed System DIPS: Distributed Inter-Frame Spacing ESS: Extended Service Set EDCF: Enhanced Distributed Coordination Function 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. HDCF: Hybrid Distributed Coordination Function IP: Internet Protocol. A layer 3 protocol widely used in the internet. LOP: 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). MAC: Medium Access Control NAV: Network Allocation Vector NACK: Negative Acknowledgement. In contrast to positive acknowledgements, NACK is typically sent when a packet is not received within some expected time interval. PCF: Point Coordination Function PIFS: Point Inter-Frame Spacing 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 RTS: Request To Send RA: Receiver Address SIFS: Short Inter-Frame Spacing SA: Source Address SCP: Stream Control Protocol. This is used for sending RLP negative acknowledgements in CDI\/IA2000 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. TA: Transmitter Address TC: Traffic Category 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 WLAN: Wireless Local Area Network REFERENCES [1] Brian P. Crow, teal., "IEEE 802.11 Wireless Local Area Networks", IEEE Communications Magazine, September 1997, pp 116- 126. [2] IEEE 802.11 WLAN working group, http.7/grouper.ieee.org/groups/802/11/index.html [3] 3GPP2 Network standards: www.3qpp2.org [4] 3GPP networking Standards: www.3gpp.org [5] CDMA Development Group, www.cdg.org [6] WLAN - IEEE 802.11 series of standards, www.ieee.org [8] 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 [9] RFC 2205 - RSVP v1 Functional Specifications [10] www.3qpp2.org: 3GPP2P.S0001B, "Wireless IP standard" WE CLAIM 1) An adaptive scheduling method for efficient resource allocation in wide-area and local-area wireless multimedia network wherein the compensation of flows that are not achieving their desired quality of service, is done by the adaptive scheduler, in that, for delay jitter sensitive flows, when the flows have some packets in their queue, higher compensation is given to flows that have larger buffer lengths and the compensation is computed as: 2) A method as claimed in claim 1, wherein to give higher compensation to flows that have smaller buffer lengths and thus to satisfy their QoS requirements quickly if the corresponding mobile stations are also experiencing reasonably good channel conditions, compute compensation as follows: 4) A method as claimed in claim 3, wherein QoS Compensation in respect of total Length of Delayed Packets is computed in that the compensation is given to flows a) scheduler, SF_AP, which considers all the forward link flows and computes forward link QoS compensation metrics for all of them; b) scheduler, SVR_AP, which works on virtual reverse link queues and computes reverse link QoS compensation metrics for all of them; and c) third level of scheduler, S AP, which considers all the flows and uses the QoS compensation metrics computed by SF_AP and SVR_AP to select a flow and a mobile station to serve in that a QoS control packet. Is provided which MAC layer control packet conveys QoS related information from mobile station to WLAN AP. 25) An adaptive scheduling method for Efficient Resource Allocation in wide-area and local Wireless Multimedia Networks substantially as herein described particularly with reference to the drawings 6 to 15. 26) A scheduling system for efficient resource allocation in WLAN networks substantially as herein described particularly with reference to the drawings 6 to 15.

Full Text

FIELD OF TECHNOLOGY
This invention relates to the field of heterogeneous wireless multimedia networks. Further this invention relates to transport of traffic from heterogeneous applications in two types of wireless networks - one a wide-area wireless network where channel conditions could change rapidly (such as 3G) and another a mobile wireless local area network (such as WLAN IEEE 802.11x). In particular this invention encompasses system and method for resource allocation for transport of traffic from heterogeneous applications to and from mobile devices within a WLAN, a 3G and an integrated 3G WLAN network.
PRESENT STATE OF ART
There are different types of networking technologies available in the wireless market today. At some places, 3G wireless technologies like CDMA 2000 IxEV-DO, CDMA 2000 1xEV-DV and WCDMA are being standardized [3,4] and deployed [5]. On the other hand, wireless LAN technologies (IEEE 802.11 series of standards) are being standardized ([6]) and also deployed at some places. Many of these WLAN systems are being deployed in the places like hotels, airports, (usually called WLAN hotspots) etc. allowing mobile users to use WLAN services at these places. In several cases, as a mobile user moves out of these places (wlan hotspots), the MS might still want to continue running its applications (such as multimedia conferencing and/or streaming, VoIP sessions etc.) and thus would need to continue getting service via some wireless networks. As 3G networks are being deployed at some places, in many networks this service may be provided via a 3G network. Thus it becomes important to have mechanisms that allow support of multimedia and other applications over heterogeneous networks such as 3G and WLAN.
Wireless local area networks (WLAN), 3G networks as well as 3G-WLAN integrated networks would potentially need to 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 micro flow or a macro flow. Here, a micro flow 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 macro flow is described via the following 3-tuple: IP source address, IP destination address, and Layer 4 protocol type.
Many flows have certain quality of service (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 terms of delay bound, delay jitter, throughput and packet loss. Many of these multimedia applications use UDP/RTP protocols for transport of data. For some other TCP based applications, such as web browsing, keeping average delay below a pre-specified value is desirable.
Heterogeneous Wireless Multimedia Networks
Heterogeneous wireless multimedia networks are considered where one wireless network is a wide-area wireless network and another is a local area wireless network.
Wide-area wireless networks provide packet data services to mobile users. There is an access point in this wireless network and all the mobile users communicate via this. Typically in a wide-area mobile wireless network, users could be pedestrian or vehicular and may move at quite different speeds. In such networks, channel conditions of users can change rapidly and the rate at which they can communicate with other nodes is also dependent over their channel conditions. In general, the access point or some sort of distributed mechanism needs to decide which nodes can transmit data at a given time.

Next, a local area wireless network is considered which provides packet data service to users in an area of smaller range such as in a hotel, airport, train, bus, small building etc. Here also there is an access point for this network and users communicate via this access point. Users can directly communicate with each other, bypassing the access point, in this network. Alternatively, users can communicate with each other via the access point which relays the messages from one user to another in its own network. In such local area networks, usually user mobility is limited compared to that in wide-area wireless network. Here also, the centralized access point or a distributed mechanism needs to decide which users can transmit data at any given time.
Next, a heterogeneous wireless network is considered where both of these networks need to coexist at a place. For example, user could access internet services via the local area wireless network whose access point in turn relay data via the access point of wide-area wireless network. Once that user moves out of the range of local area network or is no longer getting good quality from the access point of local area network, it could access internet services directly via the access point of wide area wireless network. Such a heterogeneous network is shown in the Figure 1.
Now consider 3G networks which is an example of wide-area wireless network considered above, wireless local area networks (WLAN) which is an example of local area networks mentioned above and an integrated 3G-WLAN network which is an example of heterogeneous network considered above.
3G Networks
A schematic diagram of a 30 network is shown in Figure 2 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 (ON) and can even be used for

multimedia application on 3G architecture networks. Here, MS is the mobile station, BSC is the base station controller, BTS is the base transceiver system, 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 [10]. The BS (base station) essentially includes the BSC and the BTS shown in figure 2.
In addition to the QoS requirements of the traffic flows, the resource allocation mechanisms also depend on the medium access control layer (MAC) and the physical layer characteristics of the network. In a 3G network, time is typically divided into fixed time periods called slots. For example, in a CDMA2000 1xEV-DO networks the time period of a slot is 1.67 milliseconds. Each mobile device informs the base station about the rate at which it can accept data in each of these slots on the forward link. This discrete time system is shown in the Figure 3 where 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. This rate can vary rapidly in a wide-area wireless network. Suppose /ij«] 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 used in [8]. It computes the following metric for each mobile:

In some 3G wireless networking technologies suckle 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 system are shown in the table 1 below.
Table 1. Data rates in CDMA 2000 system
Data Rate (kilobits per Packet length (bytes) Number of slots
second)
38.4 128 16
76.8 128 8
153.6 128 4
307.2 128 ^ 2
614.4 1^8 1
1228.8 256 1
1843.2 384 1
2457.6 512 i
WLAN
A schematic diagram of a WLAN network is shown in Figure 4. Here, MS is a mobile station wirelessly connected to the access point AP. Each AP provides connectivity to a set of MS called a basic service set (BSS) in IEEE 802.11 parlance. In a BSS, mobile stations are controlled by one logical function (called, "coordination function"), that decides when a station can transmit or receive. Multiple AP"s can be connected to each other using a wired or wireless

backbone (distribution system) resulting in a WLAN with extended reach. This is called an extended service set (ESS) in the IEEE 802.11 parlance. One ESS has one 32-octet long service set identifier (SSID). Each BSS has a 6-octet long basic service set identifier (BSSID) which is same as the MAC address of radio in the access point.
The manner in which air-link resources are allocated to different mobile users and their applications over the air interfaces in a wireless network, determines the performance of different applications and utilization of network resources. For this purpose, one needs to have efficient traffic scheduling mechanisms to control traffic flows in both directions over the air interface, i.e. from 3G BTS in the 3G network or from the WLAN AP in WLAN network, to the mobile station in one direction (called poniard link direction), and from WLAN-MS to WLAN-AP, or from a 3G-MS to a 3G BTS in the other direction (called reverse link direction).
For WLAN, the popular IEEE 802.11 standard [6] defines a MAC layer which is very different from that of a 3G network. Specifically two modes of medium access are defined. The first mode called point coordination function (PCF) is a contention free mode in which medium access is controlled by AP using a polling mechanism. In this mode the AP gives permission to a MS to transmit a data frame by sending a poll message to that MS. In this mode a MS transmits only when it receives a poll message from AP giving it permission to transmit. The second mode of operation called distributed coordination function (DCF) is contention mode in which all MS and also the AP use mechanisms which are quite similar to the carrier sense multiple access with collision avoidance (CSMA/CA) technique for medium access.
Each device in WLAN maintains a variable called network allocation vector (NAV) which is the remaining busy period of the shared busy channel. The protocol has some pre-defined inter-frame space (IFS) time periods with increasing duration: short IFS (SIFS), point coordination function IFS (PIFS), and distributed coordination function (DIFS). The IFSs are mandatory periods of idle

time and are used to control event priorities. As per IEEE 802.11 standards, correct receipt of a packet is signaled through the ACK packet. An ACK should be returned SIFS time period after the successful reception of a packet.
Time is divided into contention periods (CP) where DCF access is used and the contention free periods (CFP) where PCF access is used. DCF mode is shown in the Figure 5. Figure 6 shows the coexistence of PCF and DCF mode in a WLAN. Here "B" denotes a beacon signal that is sent periodically by the AP to signal the start of PCF mode. At the start of PCF mode the AP and all MS set their NAV to a pre-defined value which is the maximum length of contention free period (CFP). The AP and the MS synchronously decrement NAV to measure the elapsed time in slots. Thus the beacon B and NAV help to synchronize AP and the MS. Under special circumstances the AP may signal an early termination of CFP by sending "End" signal to all MS as shown in figure 6.
In PCF mode a point coordinator (PC) inside the AP determines the order in which the and reverse link flows of different MS are served. This is achieved by sending a poll message to a MS along with any forward link flow data frame if available. The poll message essentially gives an MS the opportunity to transmit a reverse link flow data frame back to the MS. Thus both forward and reverse link flows are scheduled by the AP. Figure 7 shows an example of various messages exchanged between the AP and MS in the PCF mode. Here D1, D2 etc, are data frames for forward link flows to mobiles stations 1, 2 etc. The ACK frames acknowledge receipt of data frame. The frames U1, U2 etc are reverse link flow data frames from mobile stations 1, 2 etc. For efficient communication the AP can combine the poll, ACK and data frames into a single frame. Similarly on the reverse link the mobile stations can combine the ACK and data frames.
The IEEE 802.11 standard permits variable length data frames to be transmitted on both foHA/ard and reverse direction. The maximum allowable size of an IEEE 802.11 frame is 2348 bytes. Figure 8 shows IEEE 802.11 frame format with

details of frame control field. The Duration field gives the duration of transmission. The CRC field allows for error checking at the receiver. The time taken to transmit the data frames in forward and reverse directions varies with the size of the frames.
The frame control field has 2 type bits and 4 subtype bits that identify the frame type. Type value of 00 is used to indicate management frame (such as Beacon, Probe Request, Probe Response, Authentication, De-authentication, Association Request, Association Response, Power management, Re-association etc.). Type value of 01 is used to indicate control frame such as RTS, CTS, ACK, Contention Free (CF)-End, Power save (PS)-Poll etc. Type value of 10 is used to indicate data frames.
Description of address fields is given in the table 2. These addresses are interpreted using the values of the To DS and From DS bit fields. The To DS bit is set to one if a frame is destined to the AP for forwarding it to the distribution system (DS). It is also set to one when the destination is in the same BSS but the AP has to relay the frame. In all other cases, it is set to zero. The From DS bit is set to one when a frame is coming from the distribution system.
SA is the source address and DA is the destination address. All stations filter on the value of the address 1 field. It is the recipient address i.e. the station on the BSS which is the immediate recipient of the packet. If the To DS bit is set to zero, the address 1 field carries address of the destination station. If the To DS bit is set to one, it is the address of the AP. Address2 identifies the transmitter address (TA) to which the ACK frame should be sent to. If From DS bit is set to one, it is the AP"s address. If the From DS bit is set to zero, it is the address of the source station. Value of Address 3 depends upon the To DS and From DS bits. In most cases, it is the remaining missing address. Address 4 is used to identify the original source of the wireless distribution system frames where frame is transmitted from one AP to another AP. The More Fragment bit is to indicate that more fragments belonging to the same frame follow the current

fragment. The Retry bit is set to one if it is transmission of a previous frame. This bit is used by the receiver to identify duplicate transmission of a packet from the sender for the case when the ACK packet sent by the receiver is lost. The More Data bit implies that station has more data to send. AP can use this to indicate that there is more data buffered for this mobile station. The Power Management bit is 1 if the transmitting station is in sleep mode. The WEP bit is set to 1 if the wired equivalency protocol is implemented. The Order bit is set to 1 if any data frame is sent using the strictly ordered service. Sequence control is for numbering and reassembly. The sequence number field is made of two fields - fragment number and sequence number. It is used to represent order of different fragments belonging to the same frame. It also helps in recognizing packet duplications. Further details of IEEE 802.11 MAC layer can be found in [1,6].

ToDS From DS Address 1 Address 2 Address 3 Address 4
0 0 DA SA BSSID N/A
0 1 DA BSSID SA N/A
1 0 BSSID SA DA N/A
1 1 RA TA DA SA
Table 2: Description of Address Fields in the IEEE 802.11 Frame
An Integrated 3G-WLAN Network
We consider a 3G-WLAN internetworking scenario as proposed in [7]. In this case, WLAN network is interconnected with the internet using a 3G radio link. It can happen for the cases where a WLAN network is located in a train and thus its WLAN access point is moving with the train. Mobile devices are allowed access to internet via a 3G-WLAN network. It is also noted in [7] that for countries with less developed fixed infrastructure, 3G networks can be used to backhaul traffic from fixed WLAN installations. In this 3G-WLAN architecture, a

3G terminal is connected to the WLAN access point. User traffic to Internet is sent via two wireless hops, first on WLAN air interface and then on a 3G air interface.
A schematic of a heterogeneous 3G-WLAN network Is shown in Figure 9. Here three different kinds of mobile stations are shown. A WLAN-MS mobile station is part of the basic service set of a WLAN. It communicates with a correspondent node (CN) on the internet using two wireless hops. The first wireless hop is from WLAN-MS to the WLAN AP. The WLAN AP is connected to a 3G-MS terminal. The second wireless hop is from the 3G-MS terminal to the 3G BTS. A second type of mobile station 3G-MS communicates with the ON using a single wireless hop to the 3G-BTS. The third type of mobile station is denoted by 3G-WLAN-MS. For some application flows, it communicates via the WLAN-AP and for some other application flows, it communicates via the 3G-BTS.
The manner In which alr-IInk resources are allocated to different mobile users and their applications over the two air interfaces of a 3G-WLAN network, determines the performance of different applications and utilization of network resources. For this purpose, one needs to have efficient traffic scheduling mechanisms to control traffic flows in both directions over the air interface. I.e. from 3G BTS to WLAN AP over the air interface and from WLAN AP to WLAN-MS over the air interface in one direction (called fon/vard link direction), and from WLAN-MS to WLAN-AP to a 3G BTS in the other direction (called reverse link direction).
LIMITATIONS
A WLAN-MS can have several application flows In forward and reverse direction with different traffic characteristics and different quality of service requirements. Each of these WLAN-MS can also experience different channel conditions which

would in turn control the rate at which these mobile stations can send data to the WLAN-AP and receive data from the WLAN-AP.
In a WLAN network, flows of a WLAN-MS in the forward and reverse directions compete for air-link resources with flows belonging to other WLAN-MS nodes. WLAN MAC protocol works in two modes - PCF and DCF. The PCF mode is intended to be used for real-time traffic flows. One needs efficient scheduling mechanisms to decide the polling order that can be used by the WLAN AP to poll nodes while in the PCF mode. These scheduling mechanisms should incorporate information related to forward link queues which are at the WLAN AP as well as related to reverse link queues which are at the WLAN-MS mobile stations.
To meet the QoS requirements of fon/vard and reverse link flows wireless networks, per-flow scheduling mechanisms are required at the access point such as at 3G BTS in 3G networks, and at WLAN-AP in the WLAN networks. In [8] a scheduling method was used for 3G networks. In general, this method does not satisfy QoS requirements of flows with diverse performance requirements.
In an integrated 3G-WLAN network, WLAN-MS nodes may have some forward link flows which are traversing two wireless hops (i.e. 3G-BTS to 3G-MS and WLAN-AP to WLAN-MS). In such cases, some of the WLAN-MS forward link flows are also competing for resources with other 3G fon/vard link flows. On the reverse link the WLAN-MS flows compete for WLAN air-link resources with other WLAN-MS nodes and for the 3G air-link resources with other 3G-MS and WLAN-MS.
In an integrated 3G-WLAN network, two wireless hops may be involved for some mobile stations (i.e. WLAN-MS nodes) while there is only one wireless hop in a pure 3G network. One needs to have a queuing and associated scheduling system for integrated 3G-WLAN network that can provide efficient utilization of resources for application flows, mobile users as well as for network operators.

There is also need to have efficient scheduling methods for integrated 3G-WLAN network to provide desired performance guarantees to different application flows with different fairness objectives.
OBJECTS OF THE INVENTION
The primary object of this invention to invent a system and methods for resource allocation in Heterogeneous Wireless Multimedia Networks.
It is another object of the invention to invent a scheduling system and new adaptive scheduling methods for the PCF (point coordinated function) mode of medium access control of IEEE 802.11x (WLAN) wireless network.
It is another object of the invention to invent new adaptive scheduling methods for the 3G wireless multimedia networks.
It is another object of the invention to meet the required QoS related objectives of multimedia application over the heterogeneous network.
It is another object of the invention to meet the required QoS related objectives of applications with average delay and rate requirements over the heterogeneous network.
It is another object of the invention to invent methods by which the present difficulty of resource allocation for the multimedia application with guaranteed QoS on a two-hop heterogeneous wireless network where one hop includes 3G air-interface and another hop includes WLAN air-interface and WLAN access point communicates with 3G base station over the air-interface, is overcome.
SUMMARY

SUMMARY OF INVENTION
This invention first proposes adaptive scheduling methods that can be used in wide-area and local wireless multimedia networks. Next, it proposes a scheduling system and associated adaptive scheduling methods for the PCF mode for the medium access control of WLAN. This system and associated methods are to be used to provide performance guarantees to forward as well as reverse link flows in a WLAN network. These also allow a WLAN network operator to specify different types of fairness objectives and associated service level agreements for mobile users.
In the PCF mode, the WLAN-AP needs to decide the order in which to poll the mobile nodes (WLAN-MS). Once the AP has decided which node to poll at a given time, it sends polling message to that node in the forward direction. It can also send data for that node along with this polling message in the fonA/ard direction. It again needs to decide how much data to send for that node. If the mobile station (WLAN-MS) successfully receives this packet, it sends an ACK to the WLAN-AP. This mobile node can also send data along with this ACK to the WLAN-AP. As there could be delay, rate and delay jitter sensitive data in forward as well reverse directions, the order in which nodes are polled (and amount of data to be transmitted is determined), plays crucial role in QoS management of diverse types of applications in a WLAN network. Adaptive scheduling methods invented here can be used to satisfy performance requirements of various types of applications in WLAN networks.
Accordingly the present invention comprises an adaptive scheduling method for efficient resource allocation in wide-area and local-area wireless multimedia network wherein the compensation of flows that are not achieving their desired

buff _comp,[t„]-queue at time ""

quality of service, is done by the adaptive scheduler, in that, for delay jitter sensitive flows, when the flows have some packets in their queue, higher compensation is given to flows that have larger buffer lengths and the compensation is computed as:
for all flows k for which there is non-empty
Accordingly, the present invention further comprises a scheduling system for efficient resource allocation in WLAN networks comprising:
a) scheduler, SF_AP, which considers all the forward link flows and computes fonward link QoS compensation metrics for all of them;
b) scheduler, SVR_AP, which works on virtual reverse link queues and computes reverse link QoS compensation metrics for all of them; and
c) third level of scheduler, S_AP, which considers all the flows and uses the QoS compensation metrics computed by SF_AP and SVR_AP to select a flow and a mobile station to serve in that a QoS control packet. Is provided which MAC layer control packet conveys QoS related information from mobile station to WLAN AP.
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 depicts a heterogeneous wireless network consisting of Access point with wide area wireless network in conjunction with wireless LAN with its access point;
Fig 2 depicts 3G Network Architecture consisting of Mobile station, BTS and wireless edge router with forward and reverse links;
Fig 3 depicts Wireless access points of 3G network with time slots Fig. 3 Time slots of 3G wireless networks;
Fig 4 depicts the co-existence of multiple wireless LAN with Extended Service Set (ESS);
Fig 5 depicts the DCF mode of wireless LAN;
Fig 6 depicts the co-existence of PCF and DCF modes of heterogeneous network;
Fig 7 depicts the communication in PCF mode;
Fig 8 depicts the field format of IEEE 802.11;
Fig 9 depicts an integrated view of heterogeneous network consisting of 3G (3 Generation Wireless Network) and wireless LAN;
Fig 10 depicts the scheduling system for wireless LAN with multiple MS and AP forming forward and reverse link;
Fig 11 depicts the plot of traffic profile and input bits for a flow;

Fig 12 depicts the flow chart for system initialization with reference to the methods for the heterogeneous network;
Fig 13 depicts the flow chart of WLAN scheduling system in heterogeneous network;
Figure 14 depicts Frame Body of QoS Control Packet;
Figure 15 depicts Queue Management for an integrated 3G-WLAN Network.
DETAILED DESCRIPTION OF THE INVENTION
1. Adaptive Scheduler for Efficient Resource Allocation in Wireless Multimedia Networks
The invention first proposes adaptive scheduling methods that can be used for efficient resource allocation in wireless multimedia networks. These can be used in several different types of wireless networks including the 3G and the WLAN wireless multimedia networks. This adaptive scheduler compensates flows that are not getting their desired quality of service using several fairness criterions. These methods also do resource allocation using different types of fairness objectives when excess resources are available.
Delay and Jitter Compensation Due to Buffered Packets
Method I - Delay and Jitter Compensation Due To Buffered Packets
We define normalized buffer size of forward link delay bound and jitter sensitive flow k at time ?„ to be
rate of
forward link flow k.

as well as reverse directions. For example multimedia conferencing flows requires that the delay, rate and delay jitter requirements be satisfied for both forward and reverse link video and audio flows. Multimedia streaming applications would usually send data in one direction only (such as using RTP packets) but will have some control packets in the reverse direction (such as RTCP control packets).
Scheduling System (ForWLAN)
Flows are separated into forward link flows from the AP to MS and reverse link flows from MS to AP. The flows consist of MAC layer packets. Each MS could have multiple flows with different traffic requirements in both directions. For each forward link flow to an MS, the WLAN-AP maintains a queue of MAC layer packets. Similarly for each reverse link flow an MS maintains a queue of MAC layer packets. For each reverse link flow, we also keep a virtual queue at the WLAN-AP. Figure 10 shows the schematic representation of these flows and respective queues.
For Figure 10:
F(x, y): Queue corresponding to forward link flow x of WLAN-MS y at the WLAN-AP
R(x, y): Queue corresponding to reverse link flow x of WLAN-MS y at the WLAN-AP
Fm(x, y): Queue corresponding to forward link flow x of WLAN-MS y at the WLAN-MS y
Rm(x, y): Queue corresponding to reverse link flow x of WLAN-MS y at the WLAN-MS y

VR(x, y): Virtual reverse queue at the WLAN-AP, corresponding to Rm(x, y) at the WLAN-MS y
SF_AP: Scheduler for forward link flows at the WLAN AP SVR_AP: Scheduler for virtual reverse link queues at the WLAN_AP S_AP: Scheduler at the AP SR_MSy: Scheduler for reverse link flows for MS y at the MS y
Each flow has Its specific quality of service requirement which can be specified by some of the parameters such as delay bound, delay jitter, average delay, throughput, and packet loss. The flow requirements are negotiated between the AP and the MS on per flow basis using some protocol during the connection setup phase. One could use RSVP, described in RFC2205, www.ietf.org. for this purpose. Once the QoS requirements and traffic characteristics are known, an AP must optimize its polling scheme such that these QoS requirements are met for all flows In WLAN.
In the system described here, the scheduler is located at the WLAN access point (WLAN-AP) but does scheduling for fonA/ard as well as reverse link flows. For reverse link flows, it maintains virtual reverse queues corresponding to reverse link queues at each WLAN-MS. We monitor packets corresponding to forward as well as reverse link flows at the WLAN-AP and calculate their rate and delay violation statistics. We use these to compensate flows that are not getting their required QoS guarantees. In the system described here, each reverse link flow k conform to a traffic profile /^ where /^(.) is a concave piece-wise linear
function. It would typically be a function of burstiness, peak rate and long-term average rate. For such a flow k, the number of bits generated between time t^ and ?2, R^{t^,t^), satisfy the following: Ri^{t^,tj) is shown in the Figure 11. This can be enforced by either policing or shaping reverse link traffic at each WLAM MS. The WLAN-AP keeps track of number of bits transmitted by each mobile station for each flow. Let Tx^(tJ be the number

of bits transmitted for flow k by its corresponding mobile station, WLAN-MS, by the time instant /„.
A suitable method is chosen to give appropriate compensation or to penalize some flows depending upon their QoS characteristics. This is shown in the Figure 12. One scheduler, SF_AP, considers all the forward link flows and computes fonA/ard link QoS compensation metrics for all of them. Another scheduler, SVR_AP, works on virtual reverse link queues and computes reverse link QoS compensation metrics for all of them. A next level of scheduler, S_AP, considers all the flows and uses the QoS compensation metrics computed by SF_AP and SVR_AP to select a flow and a mobile station to serve. This is shown in the Figure 13.
We also define a new MAC layer control packet which is used to convey QoS related information from mobile station to WLAN AP. We call it QoS control packet. In the system described here, a particular WLAN network may enable or disable use of this control packet.
If this QoS control packet is not used, then for each reverse link flow k, compute buffer,^ (?„) = max {/?^ (0, f„) - 7x^ (?„ ),0}. For each reverse link flow k, we also allow
a pre-specified upper threshold, bu/Jer thres maxi^ , and ensure that
buffer^(tJ number of bits transmitted for reverse link flow k by its corresponding mobile station, WLAN-MS, by the time instant t„. This computed buffer^{tj is used to
compute scheduler selection metric in WLAN networks.
On the other hand, if use of the QoS control packet is enabled, this packet is used to convey QoS related information from the mobile station to WLAN AP for reverse link flows. With this information, the access point can refine its estimate of buffer^{t„) for reverse link flows. We define structure of this QoS control
packet as follows:

QoS Control Packet:
Type = 01 (to indicate that it is a control packet)
Subtype = reserve a subtype for this which is not used currently for any other
purpose.
To DS = 1
From DS = 0
Address 1 = BSSID (address of MAC of radio in the WLAN AP)
Address 2 = SA (address of WLAN MS that is sending this control packet to AP)
Address 3 = N/A (Don"t use for QoS control packet)
Address 4 = N/A (is not used when To DS=1 and From DS=0)
Frame body: 1 octet Flow Identifier followed by one or more QoS TLVs where the QoS TLVs are defined below. In the system described here, the WLAN-AP assigns unique 1-octet flow identifier per-flow per mobile station for fon/vard as well as reverse link flows for each mobile station in the WLAN BSS. Combination of MAC address of mobile station and flow identifier assigned by the WLAN AP identifies a flow uniquely in a BSS. Multiple flows from a mobile station can send information in the same QoS control packet.
It defines the following QoS TLVs: QDepth TLV, DelayedLen TLV, and DroppedLen TLV. One or more of these could be sent. This is shown in Figure 14. Here, Type is a 3 bit field, length is 5-bit field and carries length of the value field.
QDepth TLV: Type = 0x01, Length = 2 octets. Value: Length of pending packets in the queue for a reverse link flow at the mobile station which is identified by the flow id in the first octet of the frame body.
Delayed Len TLV: Total length of packets that waited in the queue at the WLAN mobile station for a period which is larger than a pre-specified waiting time threshold.

DroppedLen TLV: Total length of dropped packets in the queue, for reverse link flow identified by the flow id in the first octet of frame body, that was dropped before it could be transmitted due to delay or jitter violation.
WLAN Scheduling System - Dynamic Mode
We now propose a dynamic mode for the above WLAN scheduling system where we switch from one method another dynamically.
for buffer
compensation. If after some time A;,
compensation. If after some time At,
switch to Method XIV for compensation. If after some time A;,

back to Method XII for compensation due to dropped packets.
Scheduling Methods for the PCF Mode of WLAN
Let Q^[t„] be the QoS compensation metrics of a uni-directional flow k at time /„
in a WLAN network. Note that this flow k could be fonA/ard or reverse direction flow in a WLAN network.
Method XV - Forward Link Per-Flow QoS Compensation Metric for Flows with Delay Bound, Delay Jitter and Rate Requirements
Now we consider forward link flows that need performance guarantees for delay bound, rate and delay jitter. For these flows, queues are maintained at the WLAN AP. For each such flow k, we define QoS compensation metric as follows:
all time instants /"„.
To compute the above, a suitable method for each compensation term is chosen based upon performance and fairness objectives.
Method XVI - Forward Link Per-Flow QoS Compensation Metric for Flows with Average Delay, or Average Delay and Rate Requirements
Now consider forward link flows is considered that need performance guarantees for average delay or for average delay and rate. For these flows, queues are maintained at the WLAN AP. For each such flow k, we define QoS compensation metric as follows:

To compute the above, a suitable method for each compensation term is chosen based upon performance and fairness objectives.
Method XVII- Reverse Link Per-Flow QoS Compensation IVIetric for WLAN Scheduler
For the reverse link flows, data packets are buffered in the WLAN-MS queues first and complete information is not available at the WLAN access point. For each reverse link flow, we maintain a virtual reverse link queue at the WLAN-AP.
bound, jitter and
rate, c
Method XVIII - Scheduling Decision for the PCF Mode of WLAN

If k is a forward link flow, we denote Its QoS compensation (or scheduler selection) metric, Q^, computed by the scheduler SF_AP, by g^ „ . If j is reverse
link flow, its QoS compensation (or scheduler selection) metric {Qj) is computed
by considering its virtual reverse link queue using Method XVII and we denote it by Qjjfi^. We consider the case when use of the QoS control MAC packet has
been disabled in the system and the access point estimates buffer^{tj as in the
method XVII, for each reverse link flow k that has some requirement over delay bound, jitter or average delay.
The scheduler S_AP considers all the queues corresponding to forward link flows and all the virtual queues corresponding to reverse link flows, and selects a flow to sen/e for which scheduler selection metric, Q, is equal to
max imum^j {g^ ^^ [t], bj * g^ „, [/] - Oy},
Considering each forward link flows k and each reverse link flow j which has some requirement over delay bound or delay jitter or average delay. Here, bj is
a finite, pre-specified, positive number, b. a J, is a pre-specified non-negative finite number. If there are multiple flows, ties
are broken randomly.
if no flow is selected for which there is some requirement over delay bound and jitter, or average delay, then a flow with rate requirement is chosen which is not getting its forward or reverse link, required rate guarantees. If no such flow has any packets pending at that time, any other flow is served.
Method XIX - Scheduling Decision for the PCF Mode of WLAN
If k is a forward link flow, we denote its QoS compensation (or scheduler selection) metric, g^, computed by the scheduler SF_AP, by g^ „ . If j is reverse
link flow, its QoS compensation (or scheduler selection) metric {Qj) is computed

by considering its virtual reverse link queue using Method XVII and we denote it
by QuKL ■
A case is considered when use of the QoS control MAC packet has been enabled in the system. As the access point may not always have latest information about the reverse link queues at the mobile stations, the access point still estimates 6M#er^(^„) as in the method XVII, for each reverse link flow k
that has some requirement over delay bound, jitter or average delay. In this case also, the scheduler S_AP considers all the queues corresponding to forward link flows and all the virtual queues corresponding to reverse link flows, and selects a flow to serve as in the Method XVIII but values of h. and a^ can
change with time and their values need not be in ranges which are specified in the Method XVIII. Specifically, the scheduler selection metric, Q, is used as xmximum^.{Q^P^Xt\, 6^[^]*gy,/;i-a,[^]}, considering each forward link flows k
and each reverse link flow j which has some requirement over delay bound or delay jitter or average delay. If QoS control MAC packet is received for a reverse link flow k at time s, then actual information regarding queue length etc. is used from that control packet and we use, 6j5] = l and a^\s\ = ^. There is a
pre-specified time period, T(k), in the system for each reverse link flow k. If no other QoS control packet is received for flow k until the time (s+T(k)), we reset
6, \s + T{K)\ = b,, and a, [s + T(k)] = a,.
3. Scheduling Methods for 3G Wireless Multimedia Networks
Method XX - Per-Flow QoS Compensation Metric for Flows with Delay Bound, Delay Jitter and Rate Requirements
Now we consider flows that need performance guarantees for delay bound, rate and delay jitter in a 3G network. For each such flow k, we define QoS compensation metric as follows:

hops, one in WLAN BSS and another in 3G network, use vomit (at 3G-BTS) > virater (at WLAN-AP).
For Method XIII for an integrated 3G-WLAN network: To compute compensation for WLAN-MS flows that go via two wireless networks and thus two wireless hops, one in WLAN BSS and another in 3G network, use aura/e(at 3G-BTS) > a rate (at WLAN-AP).
For Method XIV for an integrated 3G-WLAN network: To compute compensation for WLAN-MS flows that go via two wireless networks and thus two wireless hops, one in WLAN BSS and another in 3G network, use p rate (at 3G-BTS) >
i3_rafe (at WLAN-AP).
While the invention has been particularly described with reference to a preferred embodiment, it will be understood by those skilled in the art that various changes in form and detail may be made therein without departing from the spirit and scope of the invention.

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.
ACK: Acknowledgement
AP: Access Point
BSA: Basic Service Area
BSC: Base Station Controller.
BSS: Basic Service Set
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 IxEV-DO: 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.
CFP: Contention Free Period
CP: Contention Period
CSMA/CA: Carrier Sense Multiple Access with Collision Avoidance
CTS: Clear To Send
DCF: Distributed Coordination Function
DS: Distributed System
DIPS: Distributed Inter-Frame Spacing
ESS: Extended Service Set
EDCF: Enhanced Distributed Coordination Function

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.
HDCF: Hybrid Distributed Coordination Function
IP: Internet Protocol. A layer 3 protocol widely used in the internet.
LOP: 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). MAC: Medium Access Control
NAV: Network Allocation Vector
NACK: Negative Acknowledgement. In contrast to positive acknowledgements,
NACK is typically sent when a packet is not received within some expected time
interval.
PCF: Point Coordination Function
PIFS: Point Inter-Frame Spacing
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
RTS: Request To Send
RA: Receiver Address
SIFS: Short Inter-Frame Spacing
SA: Source Address

SCP: Stream Control Protocol. This is used for sending RLP negative
acknowledgements in CDI\/IA2000 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.
TA: Transmitter Address
TC: Traffic Category
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
WLAN: Wireless Local Area Network

REFERENCES
[1] Brian P. Crow, teal., "IEEE 802.11 Wireless Local Area Networks", IEEE Communications Magazine, September 1997, pp 116- 126.
[2] IEEE 802.11 WLAN working group, http.7/grouper.ieee.org/groups/802/11/index.html
[3] 3GPP2 Network standards: www.3qpp2.org
[4] 3GPP networking Standards: www.3gpp.org
[5] CDMA Development Group, www.cdg.org
[6] WLAN - IEEE 802.11 series of standards, www.ieee.org
[8] 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
[9] RFC 2205 - RSVP v1 Functional Specifications
[10] www.3qpp2.org: 3GPP2P.S0001B, "Wireless IP standard"

WE CLAIM
1) An adaptive scheduling method for efficient resource allocation in wide-area
and local-area wireless multimedia network wherein the compensation of flows
that are not achieving their desired quality of service, is done by the adaptive
scheduler, in that, for delay jitter sensitive flows, when the flows have some
packets in their queue, higher compensation is given to flows that have larger
buffer lengths and the compensation is computed as:

2) A method as claimed in claim 1, wherein to give higher compensation to flows
that have smaller buffer lengths and thus to satisfy their QoS requirements quickly
if the corresponding mobile stations are also experiencing reasonably good
channel conditions, compute compensation as follows:

4) A method as claimed in claim 3, wherein QoS Compensation in respect of total Length of Delayed Packets is computed in that the compensation is given to flows

a) scheduler, SF_AP, which considers all the forward link flows and computes
forward link QoS compensation metrics for all of them;
b) scheduler, SVR_AP, which works on virtual reverse link queues and computes
reverse link QoS compensation metrics for all of them; and
c) third level of scheduler, S AP, which considers all the flows and uses the QoS
compensation metrics computed by SF_AP and SVR_AP to select a flow and a
mobile station to serve in that a QoS control packet. Is provided which MAC layer
control packet conveys QoS related information from mobile station to WLAN AP.
25) An adaptive scheduling method for Efficient Resource Allocation in wide-area and local Wireless Multimedia Networks substantially as herein described particularly with reference to the drawings 6 to 15.
26) A scheduling system for efficient resource allocation in WLAN networks substantially as herein described particularly with reference to the drawings 6 to 15.

Documents:

1078-che-2004 abstract-duplicate.pdf

1078-che-2004 abstract.pdf

1078-che-2004 claims-duplicate.pdf

1078-che-2004 claims.pdf

1078-che-2004 correspondences-others.pdf

1078-che-2004 correspondences-po.pdf

1078-che-2004 description (complete)-duplicate.pdf

1078-che-2004 description (complete).pdf

1078-che-2004 drawings-duplicate.pdf

1078-che-2004 drawings.pdf

1078-che-2004 form-1.pdf

1078-che-2004 form-13.pdf

1078-che-2004 form-26.pdf

« Previous Patent

Next Patent »

Patent Number

216469

Indian Patent Application Number

1078/CHE/2003

PG Journal Number

13/2008

Publication Date

31-Mar-2008

Grant Date

13-Mar-2008

Date of Filing

31-Dec-2003

Name of Patentee

SAMSUNG ELECTRONICS CO. LTD.

Applicant Address

J.P TECHNO PARK, 3/1, MILLERS ROAD, BANGALORE-560 052,

Inventors:

#	Inventor's Name	Inventor's Address
1	TANEJA,DR.MUKESH	SAMSUNG ELECTRONICS CO LTD, INDIA SOFTWARE OPERATIONS (SISO), J.P TECHNO PARK,3/1, MILLERS ROAD, BANGALORE-560 052,

PCT International Classification Number

H04L 12/28

PCT International Application Number

N/A

PCT International Filing date

PCT Conventions:

#	PCT Application Number	Date of Convention	Priority Country
1			NA