as) United States
`a2) Patent Application Publication 10) Pub. No.: US 2007/0263528 Al
`Mukherjee Nov. 15, 2007 (43) Pub. Date:
`
`
`
`US 20070263528A1
`
`(54) METHODS AND SYSTEMS FOR
`SCHEDULING OFDM FRAMES
`
`(75)
`
`Inventor:
`
`Biswaroop Mukherjee, Ottawa
`(CA)
`
`Correspondence Address:
`P.O.BOX2989,STATION D
`.
`.
`$
`900-55 METCALFE STREET
`OTTAWA, ON K1P5Y6
`
`(73) Assignee: PRDWORKS
`
`(21) Appl. No.:
`
`11/540,571
`
`(22)
`
`Filed:
`
`Oct. 2, 2006
`
`Related U.S. Application Data
`
`(60) Provisional application No. 60/799,314, filed on May
`10, 2006
`;
`
`Publication Classification
`
`(51)
`
`Int. Cl.
`(2006.01)
`Ho4] 11/00
`(200601)
`Hoan 186
`.
`(52) U.S. Che i ccccsescrsseneeeseenees 370/208; 370/395.4
`(57)
`ABSTRACT
`
`System and methods for scheduling OFDM frames are
`
`provided. Each packet is assigned to a frame bucket, this
`
`amounting to a temporary decision of when to transmit the
`packet. Each packet is marked with one or more metrics. The
`metrics are used to sort packets and make scheduling
`decisions. Packets are analyzed to determine their suitability
`for MIMO transmission.
`
` Network
`
`i
`MS2
`MS3
`MS1
`
`20|44"|22 24
`
`MS4
`26
`
`1
`
`SAMSUNG 1014
`
`SAMSUNG 1014
`
`1
`
`

`

`Patent Application Publication
`
`Nov. 15,2007 Sheet 1 of 8
`
`US 2007/0263528 Al
`
`Network
`18
`
`P
`
`19
`
`
`
`
`
`BTS
`10
`
`Scheduler
`12
`
`FIG. 1
`
`2
`
`

`

`Patent Application Publication
`
`Nov. 15,2007 Sheet 2 of 8
`
`US 2007/0263528 Al
`
`2-1
`
`Receive incoming packet
`
`
`Classify each packet
`according to connection
`
`2-2
`
`
`
`
`
`2-3
`
`Mark packet with one or
`more scheduling metrics
`
`FIG.2
`
`-Earliest time for departure
`-Deadline for departure
`-User/operator priority
`-Link connection
`(e.g. RSSI, CINR,C/I)
`
`-Power save mode
`considerations
`-Framefitability.
`
`3
`
`

`

`Patent Application Publication
`
`Nov. 15, 2007 Sheet 3 of 8
`
`US 2007/0263528 Al
`
`Classifier
`
`& Marker
`
`Frame
`Buckets
`
`
`
`Frame bucket
`wide parameter
`indexes
`
`
`
`wide parameter
`indexes
`
`All packets wide
`parameter indexes
`
`4
`
`

`

`Patent Application Publication
`
`Nov. 15,2007 Sheet 4 of 8
`
`US 2007/0263528 Al
`
`
`
`120
`
`Traffic Descriptor
`
`Location of
`Packet
`22
`
`
`Pointer to next packetin
`frame bucket
`24
`
`
`FIG. 4A
`
`Frame Bucket 1
`
`Last Frame Bucket
`
`FIG. 4C
`
`5
`
`

`

`Patent Application Publication
`
`Nov. 15,2007 Sheet 5 of 8
`
`US 2007/0263528 Al
`
`FIG. 4D
`
`188
`
`
`FIG. 4E
`
`6
`
`

`

`ication Publication
`
`Nov. 15,2007 Sheet 6 of 8
`
`US 2007/0263528 Al
`
`
`
`
`2L[TTIIITh|WELTTL|4[[ITITT|SELTTTLLLh|
`iorinde
` (LETTTTTTsJ2LTTTTTT|b| ArTTTTT|
`
`3{TITTLE]
`FIG.5.
`PriorityofIndexesWLLLJ2LTTT|sLTTTTITTsJ4,TUTETTte
`
`
`
`aNAlmostEmptyFrame
`
`NS
`
`202
`
`
`
`206
`
`
`
`7
`
`

`

`Patent Application Publication
`
`Nov. 15, 2007 Sheet 7 of 8
`
`US 2007/0263528 Al
`
`parameters);
`
`Find connection ID to get an index into the table
`of all the properties of this connection (like QoS
`
`
`6-1
`
`
`
`Using the connection parameters calculate STATIC
`and COMPULSARYmetrics (e.g. earliest time of
`
`
`departure, deadline time). For the remaining
`
`
`metrics mark with default values;
`
`
`
`6-2
`
`For each metric place add the packet descriptor to 6-3
`the corresponding indexes or groups (e.g. a frame
`
`
`bucket index based on earliest time of departure);
`
`Repeat from Sfeg 6-7 for the next arriving
`.
`packet.
`
`6-4
`
`FIG.6
`
`8
`
`

`

`Patent Application Publication
`
`Nov. 15, 2007 Sheet 8 of 8
`
`US 2007/0263528 Al
`
`
`
`Using the already created indexs (e.g. earliest departure time
`index) and groups, get a set of packets that may be sent in the
`
`current frame;
`
`
`Calculate compulsory dynamic indexes for packets in the group
`above (e.g. link condition index, which in this case would be frame
`
`7-2
`
`
` 7-1
`bucket wide);
`
`
`Calculate the rank of the packets based on the objective function; ra
`
`Read existing conditions (like current system load, percent of
`framefilled etc.) and pick appropriate objective function;
`
`[7-3
`
`For the next highest ranked packet, convert the packet intoa
`burst and find the most appropriate place for the same;
`
`{7-5
`
`
`If collaborative MIMO is possible regions of the frame with
`existing bursts as well as empty regions are checkedto find best 7-6
`
`placement. Using the link condition index, existing bursts that are
`
`likely to have an orthogonal channelto the burst being placed are
`
`
`If no suitable MIMO pair is found or if collaborative MIMO is not 7-7
`applicable: the burst is placed in a part of the frame that is
`
`currently unoccupied;
`
`
`checked;
`
`
`Repeat until next packet doesn’t fit because either there are no|7-8
`more packets or frameis full. Save result;
`
`
`
`
`If frame is full- for all packets in the frame calculate non-
`compulsory metrics as well as intraframe-indexes(like sleep
`index} that allow better packing of frame, if not available already;
`
` 7-9
`
`
`Perform multipass fitter using until there is enough room for a|7-10
`new packet.
`If so repeat from Sfep 7-2
`
`FIG.7CEnd)
`
`9
`
`

`

`US 2007/0263528 Al
`
`Nov. 15, 2007
`
`METHODS AND SYSTEMS FOR
`SCHEDULING OFDM FRAMES
`
`RELATED APPLICATION
`
`[0001] This application claims the benefit of prior U.S.
`Provisional Application No. 60/799,314 filed May 10, 2006.
`
`FIELD OF THE INVENTION
`
`[0002] The invention relates to methods and systems for
`scheduling OFDM frames.
`
`BACKGROUND OF THE INVENTION
`
`[0003] Many schedulers have been defined that are suit-
`able for scheduling sequential transmission of resources on
`a single transmission medium that has common channel
`conditions. These schedulers are not, in general, applicable
`to OFDMA scheduling in which there is a two dimensional
`resource (time and frequency) for use in transmitting to
`multiple users that will experience different channel condi-
`tions at different times, and for different frequencies within
`the available frequency resource.
`
`SUMMARY OF THE INVENTION
`
`[0004] According to one broad aspect, the invention pro-
`vides a method of scheduling OFDM frames, each frame
`comprising at least one OFDM symbol, each OFDM symbol
`comprising a plurality of subcarriers, the method compris-
`ing: for each packet to be scheduled assigning the packet a
`plurality of scheduling metrics; producing at
`least one
`ordering of packets using the metrics; using the at least one
`ordering to select a set of packets to send in a current frame;
`for each OFDM frame, constructing the OFDM frame from
`packets assigned to the frame by placing each packet in a
`respective rectangular
`time-frequency burst within the
`OFDMframe, at least some of the OFDM frames including
`packets for multiple users; transmitting the OFDM frames
`using at least one transmit antenna.
`[0005]
`In some embodiments, the at least one ordering
`comprises: at least one compulsory ordering that is always
`performed;at least one ordering that is performed only some
`of the time.
`
`In some embodiments, the method further com-
`[0006]
`prises: performingat least one partial ordering of the packets
`that treats groups of packets equally in the partial ordering.
`[0007]
`In some embodiments, the method further com-
`prises: determining groups of packets that are more optimal
`than others for transmission in a single frame, and taking
`into account such groups in making scheduling decisions.
`[0008]
`In some embodiments, the method further com-
`prises:
`temporarily assigning each packet to a particular
`frame using a deadline for departure for the packet.
`[0009]
`In some embodiments, the method further com-
`prises: where all packets assigned to a frame to be trans-
`mitted fit in the frame, selecting at least one packet from a
`later frame bucket using one or more of the orderings.
`[0010]
`In some embodiments, the metrics include at least
`one metric selected from a group comprising: earliest time
`of departure, deadline for departure, user/operator priority,
`link condition, power save mode considerations,
`frame
`fitting information.
`[0011]
`In some embodiments, the geometrical restriction
`comprise a list of possible rectangular resourcesizes that can
`be used to transmit the packet.
`
`In some embodiments, the method further com-
`[0012]
`prises updating the geographical restriction if there is a
`change in robustness of data transmission to be used for the
`packet.
`the indexes comprise at
`In some embodiments,
`[0013]
`least one: head ofline ordering that defines an ordering of a
`most recent packet for each CID; frame bucket wide order-
`ing that defines an ordering of all packets temporarily
`assigned to a given frame; all packets wide ordering that
`defines an ordering of all packets.
`[0014]
`In some embodiments, the method further com-
`prises: for at least some future frames, allocating resources
`for the retransmission of packets that may require multiple
`transmissions.
`
`the amount of resources
`In some embodiments,
`[0015]
`allocated for future transmissionsis a function ofa statistical
`
`likelihood of retransmission being required.
`[0016]
`In some embodiments, the method further com-
`prises: for a frame to be transmitted, performing multiple
`passes to find improved frame packing of bursts in the
`frame; stopping performingthe passesat a time that ensures
`the best frame as of that
`time can be constructed and
`transmitted on time.
`
`In some embodiments, the method further com-
`[0017]
`prises allocating at least some bursts for simultaneoustrans-
`mission using MIMO.
`least some
`[0018]
`In some embodiments, allocating at
`bursts for simultaneous transmission using MIMOis per-
`formed for UL collaborative MIMO.
`
`least some
`In some embodiments, allocating at
`[0019]
`bursts for simultaneous transmission using MIMO com-
`prises: determining sets of bursts that are appropriate for
`simultaneous transmission using MIMO.
`[0020]
`In some embodiments, determining sets of bursts
`that are appropriate for simultaneous transmission using
`MIMO comprises: determining sets of wireless stations with
`sufficient orthogonality of channel conditions for MIMO
`and, for such determined sets of wireless stations, determin-
`ing a numberof symbols that can be saved by using MIMO
`as opposed to not using MIMOforsets of bursts.
`[0021]
`In some embodiments, the method further com-
`prises: selecting the sets that maximize the savings for UL
`collaborative MIMO.
`
`In some embodiments, the method further com-
`[0022]
`prises: altering modulation and error coding to be more
`robustif there is room in the frame; altering modulation and
`error coding to be less robust if there is less room in the
`frame.
`
`In some embodiments, the method further com-
`[0023]
`prises: receiving packets for transmission; performing the
`scheduling for the packets received for transmission.
`[0024]
`In some embodiments, the method further com-
`prises: receiving requests for uplink transmission resources;
`performing scheduling for the requests for uplink transmis-
`sion resources.
`
`[0025] According to another broad aspect, the invention
`provides an OFDMtransmitter for transmitting OFDM
`frames, each frame comprising at least one OFDM symbol,
`each OFDM symbol comprising a plurality of subcarriers,
`the scheduler comprising: at least one transmit antenna; a
`classifier and marker that assigns each packet to be sched-
`uled a plurality of metrics; a multi-parameter frame opti-
`mizer adaptedto: a) produceat least one ordering of packets
`using the metrics; b) use the at least one ordering to select
`
`10
`
`10
`
`

`

`US 2007/0263528 Al
`
`Nov. 15, 2007
`
`a set of packets to send in a current frame over the at least
`one transmit antenna,at least some frames containing pack-
`ets of multiple users.
`[0026]
`In some embodiments, a base station comprises:
`the OFDM transmitter as summarized above.
`
`In some embodiments, said at least one transmit
`[0027]
`antenna comprises at least two transmit antennas.
`
`BRIEF DESCRIPTION OF THE DRAWINGS
`
`[0028] Embodiments of the invention will now be
`described with reference to the attached drawings in which:
`[0029]
`FIG. 1 is a block diagram of an OFDM commu-
`nications system;
`[0030]
`FIG. 2 is a flowchart of a methodofclassifying and
`marking packets in accordance with an embodiment of the
`invention;
`[0031]
`FIG. 3 is a schematic diagram of a scheduler
`provided by an embodimentof the invention;
`[0032]
`FIGS. 4A through 4E are data structure diagrams
`for various data structures used to perform traffic classifi-
`cation and sorting;
`[0033]
`FIG. 5 is a schematic diagram showingreprioriti-
`zation of indexes as a framefills up;
`[0034]
`FIG. 6 is a flowchart of a method of processing
`packets prior to scheduling; and
`[0035]
`FIG. 7 is a flowchart of a method of scheduling
`packets processed using the method of FIG. 6.
`
`DETAILED DESCRIPTION OF THE
`PREFERRED EMBODIMENTS
`
`FIG. 1 is a simplified block diagram of an example
`[0036]
`of an OFDM communications system. In some embodi-
`ments, this might be compliant with one or moreiterations
`of one IEEE 802.16 e,
`the mobile wireless broadband
`standard established by the IEEE and utilized by the
`WiMAX forum. Shown is a base station 10 having a
`scheduler 12. The basestation has a set of antennas 14,16.
`In the illustrated example, two antennas are shown; more
`generally, for SISO applications, there is one antenna, and
`for MIMOapplications, there is more than one antenna. The
`BTS 10 is shown connected to a network 18. The network
`18 can be considered to include any network from which/
`over which packets 19 are delivered to/from the BTS 10.
`Also shownis a plurality of mobile stations MS1 20, MS2
`22, MS3 24, MS4 26. Given that these stations are mobile,
`the set of mobile stations that will be in the coverage area of
`BTS 10 will change over time and will vary in number.
`Alternatively, nomadic or fixed wireless devices may be
`used. Each mobile station 20,22,24,26 communicates with
`the BTS 10 in respect of at least one logical connection
`identified by a CID (connection identifier). In a particular
`instance illustrated, MS1 20 is shown having logical con-
`nections with CID1 36, CID2 38. MS2 22 is shown with
`logical connection having CID3 40. MS3 24 is shown with
`logical connection 42 having CID4. Finally, MS4 26 is
`shown with logical connection 44 having CID5. More
`generally, any appropriate numberof logical connections for
`each of the mobile stations within the coverage area of the
`BTS 10 may be established. Multi-access OFDM systems
`such as shown in FIG. 1 are also referred to as OFDMA
`systems. In such systems, frames are transmitted that include
`content for multiple receivers.
`
`[0037] The BTS 10 transmits using an OFDM transmis-
`sion format. With OFDM, there is a set of OFDM sub-
`carriers that are closely spaced in frequency. A single OFDM
`symbol includes the contents of all of these OFDM sub-
`carriers over a symbol transmission duration. The format of
`an OFDMsignal transmitted by the first antenna 14 is
`generally indicated by 26. This is shown to consist of a
`sequence of frames 30,32,34 where frequency is shown in
`the vertical direction and time is shown in the horizontal
`
`direction. Each small circle in frame 30 represents what is
`transmitted on a single sub-carrier for a single symbol
`duration. Each frame includes k OFDM symbols, where
`k=2. A similar OFDM format is shown for the second
`antenna 16 generally indicated at 28 with the first frame
`indicated at 31. More generally, a similar format is employed
`for each antenna of the BTS 10. The OFDM framesrepre-
`sent the two-dimensional resource that can be allocated for
`transmission to mobile stations (downlink transmission). A
`similar frame format may be used to uplink transmission. In
`that case, each mobile station is allocated a burst, and
`multiple mobile stations transmit their bursts so as tofill up
`the frame. In some embodiments, detailed below, there is
`overlap between the bursts transmitted by two or more
`mobile stations in certain circumstances, this being referred
`to as collaborative MIMO. It is assumed that any transmis-
`sion for a given mobile station is to be allocated a rectan-
`gular portion of a frame, hereinafter referred to as a burst. In
`other words, the contents for a given mobile station will be
`within a frame, and will be contained within an N by M
`resource where N is a number of sub-carriers and M is a
`
`number of OFDM symbol durations. Example allocations
`during the first frame 30,31 transmitted by two antennas
`14,16 showsallocations 43,44,45,46 for MS1 20, MS2 22,
`MS3 24 and MS426 respectively.
`
`Classification and Marking
`
`FIG. 2 is a flowchart of a method of packet
`[0038]
`classification and marking that is executed for each packet
`19 that is received by the BTS 10. An incoming packet is
`received at step 2-1. The packet is classified according to
`connection at step 2-2. This might for example involve
`examining a CID (connection identifier) within a packet.
`The CID can be used an index to a table that acts as a virtual
`repository of information pertaining to a connection andall
`packets associated to it.
`It can be used as key to the
`information that
`the BTS has for all connections. For
`
`instance it might contain QoS (quality of service) parameters
`such as maximum and minimum committed rates and/or
`channel quality measurements such as CINR (carrier to
`interference and noise ratio) the receiver reports about the
`state of the physical conditions in the radio path to the
`mobile station. Each packet is marked with one or more
`scheduling metrics in step 2-3. Note that the scheduling
`metrics that can be applied for different connections can be
`different. Various examples of scheduling metrics are shown
`generally indicated at 48 and include: earliest
`time of
`departure, this indicating the earliest frame that a packet may
`be sent to meet certain QoS or functional requirement;
`deadline for departure,
`this indicating a latest frame by
`which the packet needs to be transmitted to meet QoS
`requirements; user/operator priorities,
`this representing a
`priority that can be used to rank certain users above certain
`other users and/or certain operators above certain other
`operators; link condition—this can be used to store one or
`
`11
`
`11
`
`

`

`US 2007/0263528 Al
`
`Nov. 15, 2007
`
`more parameters that represent the link over which that
`particular packet will be transmitted, particular examples
`including RSSI
`(received signals
`strength indication),
`CINR, and C/I (carrier to interference ratio); power save
`mode considerations—this can be used to store parameters
`that represent whethera particular packet is being transmit-
`ted to a mobile station that has power save mode; frame
`fitting metric—this is a parameter that captures geometrical
`restrictions the frame may impose on how the packets are
`packed in. Details of many of these metrics are provided
`below.
`
`Framefitting is a term to describe how suitable a
`[0039]
`packet is to be put in a frame when considering its dimen-
`sions, assuming each packet
`is to occupy a rectangular
`resource. In some embodiments, a packet is tagged with a set
`of possible rectangular resource sites that can be used to
`transmit the packet, and these tags constitute frame fitting
`metric.
`
`For example, in a 2-dimensional resource a packet
`[0040]
`of size 32 can be placed as 2x16 rectangle or a 4x8
`rectangle. A packet that needs 32 symbols is tagged at this
`time with its possible dimensions ((2,16), (4,8)). At some
`later point the number of symbols may be changed (e.g.
`when the radio conditions worsen a decision may be made
`to use more symbols to send the same amount of data for
`more robustness or if two packets are to be combined and
`sent together in a burst) the set of possible dimensions is
`updated as well. The use of the frame fitting metric in
`packing a frameis detailed below.
`[0041]
`In some embodiments scheduling using the meth-
`ods described herein is only performed in the downlink
`direction. The actual packets to be scheduled are available in
`this case. In some embodiments, scheduling using the meth-
`ods described herein is performed in the uplink direction,
`and in further embodiments scheduling using the methods
`described herein is performed in both the uplink and down-
`link directions.
`
`For embodiments in which uplink scheduling is to
`[0042]
`be performed, the scheduler deals with grant-requests which
`are sent to the scheduler requesting space in the UL frameto
`send a packet in the UL direction. The scheduler can process
`the grant requests much like they are actual packets, by
`using its CID to retrieve the connection parameters and
`calculating the appropriate metrics.
`[0043]
`In some embodiments, scheduling the transmission
`of signalling information for the uplink and/or downlink) is
`treated in the same way. In case of signalling howevera real
`connection ID may not available or applicable. In some
`embodiments, non-data, signalling specific keys are used in
`the same fashion as the CIDs used for data connections.
`
`Furthermore, sometraffic metrics that are applicable to data
`traffic may not be available for signalling. As such special
`parameters for signalling such as earliest frame to send, and
`last frame to send may be substituted. Other parameters like
`position in the frame andpriority relative to other signalling
`and data are examples that may be specific to signalling.
`[0044] Various implementations may perform the sched-
`uling using the methods described for any combination of
`one or more of downlink packets, uplink grant requests,
`signalling for UL, signalling for DL. References to “pack-
`ets” in the following refer generally to whatever set of
`resources are to be scheduled in this manner.
`
`[0045] Referring now to FIG. 3, shown is a schematic
`diagram of an example implementation of the scheduler 12.
`
`The scheduler can be implemented in hardware, software in
`which caseit is deliverable as computer readable medium,
`or a combination of hardware and software, such a combi-
`nation including at least one circuit such as a microproces-
`sor, DSP, ASIC, FPEA to name a few examples. Incoming
`packets 19 are classified and marked with one or more
`scheduling metrics by classifier and marker 50. After clas-
`sification and marking, the packets are assigned to one of a
`plurality of frame buckets. Each frame bucket represents a
`future frame to be scheduled and transmitted. Assigning a
`packet to a frame bucket amounts to a temporary assignment
`of the packet to be transmitted in that frame when the time
`arrives. In the illustrated example there are five frame
`buckets 52,54,56,58,60. The number of frame buckets can
`be arbitrarily selected subject to the limitation that most
`packets will have a deadline for departure and as such cannot
`be scheduled further in the future than this deadline. Note
`that assignment to a frame bucket can be logically per-
`formed or physically performed. For example, the packet
`can be physically moved into a memory location associated
`with a frame bucket. In another example, the packet can be
`stored in an arbitrary location, with pointers to the packets
`stored in the frame buckets.
`
`In some embodiments, each incoming packet has a
`[0046]
`packet descriptor, this being a data structure that can travel
`with the packet or be stored separately. The packet descrip-
`tor contains information identifying the physical location of
`the packet and other parameters associated with the packet
`such as the scheduling metrics. In a particular example, the
`frame buckets are implemented by using a linked list of
`pointers between these packet descriptors. An example of
`such a packet descriptor is indicated at 180 in FIG. 4A. This
`particular packet descriptor has a field 82 for the location of
`the packet and a field 84 to point to the next packet in the
`same frame bucket. This is also illustrated in FIG. 3 where
`
`packet descriptors are shown generally at 62. For frame
`bucket 56, there is a pointer to a first packet descriptor 64
`which in turn points to a second packet descriptor 66. In a
`similar manner, the packet descriptors for each frame bucket
`can be identified. The packet descriptor can also include the
`various metrics determined during packetclassification and
`marking.
`that are
`the packets
`In some embodiments,
`[0047]
`assigned to a given frame bucketare not ordered, but rather
`are all considered equal.
`[0048] Having determined a frame bucket for each packet
`and one or more metrics, packets are now ordered according
`to their rank on these metrics. Various types of ordering can
`be performed, and examples of each of these will be given
`below. Some orderings are performed across all packets that
`have been received and are awaiting transmission, also
`referred to as “all packets wide”. Someorderings take place
`only for the oldest packets for each CID (also referred as
`“head of line’). Some orderings take place on the basisofall
`packets temporarily assigned to a given frame, also referred
`to as “frame bucket wide”.
`
`[0049] Referring now to FIG. 3 again, frame bucket wide
`parameter indexes that might be used to establish frame
`bucket wide ordering are shown at 72,74,76,78,80 for frame
`buckets 52,54,56,58,60 respectively. Each frame bucket
`wide parameter index has a form shown by way of example
`in FIG. 4B generally indicated at 182. This shows pointers
`PD,, PD,, .. . PDx to all of the packet descriptors for the
`packets stored in each frame bucket where PD, points to the
`
`12
`
`12
`
`

`

`US 2007/0263528 Al
`
`Nov. 15, 2007
`
`packet descriptor of the highest rank packet according to a
`particular criteria, and PD, pointsto the packet descriptor of
`the lowest rank packet according to that criteria. Note that
`there can be multiple different frame bucket wide parameter
`indexes. Frame bucket wide indexes are useful
`to find
`
`packets that may be promoted or demoted to an earlier or
`later frame respectively. For example, a radio condition
`index (which specifies the present condition of the link to a
`mobile station) may be used to promote packets that have
`better radio conditions now or demote the packets that have
`poorradio conditions now, the heuristic being that delaying
`a packet with poor conditions may allow it to be sent later
`when the conditions improve. The same heuristic can be
`applied to the case when promoting a packet with good
`current radio conditions. Note that if the radio conditions
`
`vary randomly then sending according to the radio condi-
`tionsat their peaks will increase aggregate throughput of the
`system. Other possible frame bucket wide indexes could
`include fitting metrics like possible dimensions that were
`defined earlier.
`
`FIG. 4B is a very specific structure for implement-
`[0050]
`ing the frame bucket wide parameter index. In another
`example, the traffic descriptor of FIG. 4A can be supple-
`mented with anotherfield that allows for an ordering accord-
`ing to frame bucket wide parameter index.
`[0051] With further reference to FIG. 3, an example of a
`connection set wide parameter index that might be used to
`establish connection set wide ordering is indicating gener-
`ally at 90. A connection set wide parameter index allows for
`an ordering of the oldest packets associated with each
`connection identifier.
`
`[0052] An example of such a connection set wide ordering
`is shown in FIG. 4C. This is the same format as the frame
`
`bucket wide parameter index of FIG. 4B, with a set of
`indexes 1 through Ny¢zp (where Nyczp this is the number
`of ClIDs being indexed) and pointers PD,, ..., PDy_czp to
`respective packet descriptors. There can be multiple such
`connection set wide orderings implemented. In FIG. 3,
`connection set wide parameter index 90 is shown with
`pointers 92 pointing to various packet descriptors according
`to their order as determined by a connection set wide
`parameter ranking.
`[0053]
`Finally, an example of an all packets wide param-
`eter index that might be usedto establish an all packets wide
`ordering is indicated at 94. With such an index, all of the
`packets that have been received are indexed together. An
`example ofthe structure this might take is shown in FIG. 4D
`where the ordering of all the packets 1 through N75; is
`shown with a pointer to a respective packet descriptor for
`each index. Once again, multiple such orderings can be
`implemented.
`[0054] The above discussed fitting metric, in the form of
`one or more sets of dimensions, can be used to generate an
`index of dimensions, either for all packets, on a frame-wide
`basis, or head ofline basis.
`[0055] The frame bucket wide parameter indexes, connec-
`tion set wide parameter indexes, andall packet wide param-
`eter indexes are maintained on an ongoing basis. As packets
`are received,
`they are added to the appropriate indexes.
`Sunilarly, as packets are transmitted, they are removed from
`
`the appropriate indexes. Other mechanisms of generating
`and maintaining orderings are contemplated.
`
`Partial Ordering
`
`in addition to the above
`In some embodiments,
`[0056]
`indexing, the scheduler also performs partial ordering of
`packets, again based on one or more of the metrics. By
`partial ordering,it is meant that groups of packetsare treated
`as equal as opposedto ranking the packets where indexes are
`used. An example of this is the ordering that is done when
`packets are put into respective frame buckets. The deadline
`time for a given packet specifies which frame a packet is to
`go out on (in other words which bucket). Many packets can
`be in the same frame and are therefore equal in this partial
`ordering scheme. Thus, as mentioned above, all packets
`assigned to a given frame bucket are considered equalin this
`partial ordering. The processing cost
`to perform partial
`ordering compared to maintaining an ordered queueforall
`packets is muchless. A partial ordering can be maintained in
`a similar manner to the above discussed indexes, the only
`difference being that the orderof the packets is not given any
`significance.
`
`Grouping of Packets
`
`Instead of or in addition to trading off one packet
`[0057]
`against another using the above indexing approaches,
`in
`some embodiments groups of packets are traded off against
`each other. In particular, some groupings of packets can be
`determined to be more optimal than others. For example, a
`particular set of packets being packed together in a single
`frame may be moreefficient in terms of transmit resource
`utilization than another set of packets. The following are
`three different examples of such packet groupings that can
`be generated:
`[0058]
`a) packets that fit perfectly (or more perfectly) in a
`burst within a frame, are more efficient than such a packet
`that leave holes. For example a packet of 100 bytes when
`modulated may need 20 symbols (depending upon the
`modulation chosen). These 20 symbols are allocated into a
`frame. The region that these 20 symbols occupyis called the
`burst that correspondsto the original packet. The scheduler
`creates bursts for all packets in the frame and tags them
`appropriately. The modem takes the bits in the packets and
`modulates them to fit them in the burst inside the frame.
`
`b) bursts destined for a set of mobile stations that
`[0059]
`have higher orthogonality in terms of radio conditions are
`better for simultaneous transmission on multiple antennas.
`For example, in a MIMO BTShaving twoantennas, if a
`BLAST transmission format
`is employed,
`then the best
`performance is realized if the two antennas are used to
`transmit to mobile stations that are physically spaced as far
`apart as possible;
`[0060]
`c) sets of bursts that satisfy certain modulation
`conditions may allow for better power spread over the
`frame;
`in one embodiment, all packets having the same
`modulation type are grouped together in a common frame;
`in other embodiments, a range of different modulation types
`within each frame can result in better performance. The
`particular combination of modulation type or types that will
`produce the best performance is an implementation specific
`detail.
`
`[0061] The scheduler’s primary function is to find “suit-
`able packets” under various conditions. At any time the
`
`13
`
`13
`
`

`

`US 2007/0263528 Al
`
`Nov. 15, 2007
`
`which may be frame specific, some of which may span
`several frames, some of which maybe based on head ofline
`packets (connection set wide) some of which may spanall
`packets. Any of the metrics can then be used in order to
`decide which frames to moveinto a subsequentframeorinto
`a previous frame.
`
`Use of Frame Fittability when Packing a Frame
`
`suitability of the packet depends upon various factors that
`are represented by its metrics. For example a packet P that
`may be more suitable to be sent in the next frame than
`another packet Q because it is higher on an increasing index
`of deadlines may not be suitable because of its dimensions
`(indicated by the dimension index). In this case the sched-
`uler may decide to search the index of dimensions to find
`packets thatfit the available space and then pick the packet
`with the earliest deadline among them. Depending upon the
`conditions and the configuration provided to the scheduler,
`the scheduler will use various partial orderings and indexes
`to pick packets. For example, given indexes {I_1, I_2,...
`} and Partial Orderings {P_1, P_2,}, the scheduler maystart
`with P_1 to pick the first set of packets