(19) United States
`(12) Patent Application Publication (10) Pub. No.: US 2007/0263528 A1
`
`(43) Pub. Date: NOV. 15, 2007
`Mukherjee
`
`US 20070263528A1
`
`(54) METHODS AND SYSTEMS FOR
`SCHEDULING OFDM FRAMES
`
`(75)
`
`Inventor:
`
`Biswaroop Mukherjee, Ottawa
`(CA)
`
`Correspondence Address:
`SMART & BIGGAR
`P.O. BOX 2999, STATION D
`900-55 METCALFE STREET
`OTTAWA, ON K1P5Y6
`
`(73) Assignee:
`
`NORTEL NETWORKS
`LIMITED
`
`(21) Appl. No.:
`
`11/540,571
`
`(22)
`
`Filed:
`
`Oct. 2, 2006
`
`Related US. Application Data
`
`(60) Provisional application No. 60/799,314, filed on May
`10, 2006.
`
`Publication Classification
`
`(51)
`
`Int. Cl.
`(2006.01)
`H04J 11/00
`(2006.01)
`H04L 12/56
`(52) use. ..................................... 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.
`
`Frame30
`
`\‘
`
`
`
`M83
`14
`
`Network
`
`
`
`M84
`26
`
`SAMSUNG 1014
`
`SAMSUNG 1014
`
`1
`
`

`

`Patent Application Publication
`
`Nov. 15, 2007 Sheet 1 0f 8
`
`US 2007/0263528 A1
`
`9102
`
` up]
`
`0195
`
`42::
`
`M81
`
`M82
`
`M33
`
`M34
`26
`
`FIG. 1
`
`2
`
`

`

`Patent Application Publication
`
`Nov. 15, 2007 Sheet 2 0f 8
`
`US 2007/0263528 A1
`
`2—1
`
`Receive incoming packet
`
`2—2
`
`
`Classify each packet
`according to connection
`
`
`
`
`2-3
`
`Mark packet with one or
`more scheduling metrics
`
`FIG. 2
`
`-Earliest time for departure
`—Deadline for departure
`—Userloperator priority
`—Link connection
`(eg. RSSI, CINR, Clli
`
`—Power save mode
`considerations
`—Frame iitability.
`
`3
`
`

`

`Patent Application Publication
`
`Nov. 15, 2007 Sheet 3 0f 8
`
`US 2007/0263528 A1
`
`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 0f 8
`
`US 2007/0263528 A1
`
`Traffic Descriptor
`
`120
`
`
` Pointer to next packet in
`
`Location of
`Packet
`framezflucket
`
`22
`
`
`
`
`FIG. 4A
`
`Frame Bucket 1
`
`Last Frame Bucket
`
`
`
`FIG. 4B
`
`
`
`FIG. 4C
`
`5
`
`

`

`Patent Application Publication
`
`Nov. 15, 2007 Sheet 5 0f 8
`
`US 2007/0263528 A1
`
`188
`
`FIG. 4D
`
`186
`
`FIG. 4E
`
`6
`
`

`

`//__J/
`/
`
`=
`
`M” ZEDJIIIIEI1IIIIIIIM4m3IIIIIIIIII
`
`PriorityofI am4IIIIIIIM1mm2IIIIIIIIII
`
`
`
`7/////////
`M“
`
`FIG.5‘
`
`
`
`II
`1:
`-
`>.
`E
`-
`E‘.
`*5
`-
`E
`>
`=
`‘5
`'5
`-
`é /°=_le
`
`8/
`202
`
`7
`
`

`

`Patent Application Publication
`
`Nov. 15, 2007 Sheet 7 0f 8
`
`US 2007/0263528 A1
`
`6-1
`
`Find connection ID to get an index into the table
`of all the properties of this connection (like 008
`parameters);
`
`
`
`
`
`
`
`Using the connection parameters calculate STATIC
`and COMPULSARY metrics (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 Step 6-] for the next arriving
`,
`packet
`
`6—4
`
`FIG. 6
`
`8
`
`

`

`Patent Application Publication
`
`Nov. 15, 2007 Sheet 8 0f 8
`
`US 2007/0263528 A1
`
`
`Using the already created indexs leg. earliest departure time
`index) and groups, get a set of packets that may be sent in the
`
`current frame;
`
`
`
`
`
`
` 7-1
`
`Calculate compulsory dynamic indexes for packets in the group
`above (e.g. link condition index, which in this case would be frame
`
`bucket wide);
`
`
`
`Read existing conditions (like current system load, percent of
`frame filled etc.) and pick appropriate objective function;
`
`Calculate the rank of the packets based on the objective function;
`
`7_2
`
`7-3
`
`7-4
`
`For the next highest ranked packet, convert the packet into a
`burst and find the most appropriate place for the same;
`
`7—5
`
` If collaborative MlMU is possible regions of the frame with
`existing bursts as well as empty regions are checked to find best 7—6
`
`placement. Using the link condition index, existing bursts that are
`c ec e ;
`likely to have an orthogonal cganfleljto 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;
`
`
`Repeat until next packet doesn't fit because either there are no
`more packets or frame is full. Save result;
`
`7—8
`
`
`
`
`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
`new packet. If so repeat from Step 7-3
`
`7-10
`
`FIG. 7
`
`CHIE-
`
`9
`
`

`

`US 2007/0263528 A1
`
`Nov. 15, 2007
`
`METHODS AND SYSTEMS FOR
`SCHEDULING OFDM FRAMES
`
`RELATED APPLICATION
`
`[0001] This application claims the benefit of prior US.
`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
`OFDM frame, 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: performing at 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 resource sizes 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 of line 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 transmissions is a function of a 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 performing the passes at 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 simultaneous trans-
`mission using MIMO.
`least some
`[0018]
`In some embodiments, allocating at
`bursts for simultaneous transmission using MIMO is 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 number of symbols that can be saved by using MIMO
`as opposed to not using MIMO for sets 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
`robust if 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 OFDM transmitter 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 adapted to: a) produce at least one ordering of packets
`using the metrics; b) use the at least one ordering to select
`
`10
`
`10
`
`

`

`US 2007/0263528 A1
`
`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 method of classifying and
`marking packets in accordance with an embodiment of the
`invention;
`[0031]
`FIG. 3 is a schematic diagram of a scheduler
`provided by an embodiment of the invention;
`[0032]
`FIGS. 4A through 4E are data structure diagrams
`for various data structures used to perform traflic classifi-
`cation and sorting;
`[0033]
`FIG. 5 is a schematic diagram showing reprioriti-
`zation of indexes as a frame fills 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 more iterations
`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 base station 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 MIMO applications, 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 shown is a plurality of mobile stations M81 20, M82
`22, M83 24, M84 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, M81 20 is shown having logical con-
`nections with CID1 36, CID2 38. M82 22 is shown with
`logical connection having CID3 40. M83 24 is shown with
`logical connection 42 having CID4. Finally, MS4 26 is
`shown with logical connection 44 having CID5. More
`generally, any appropriate number of 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 OFDM signal
`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
`kiZ. 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 frames repre-
`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 to fill 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 shows allocations 43,44,45,46 for M81 20, M82 22,
`M83 24 and M84 26 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 and all
`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 conditionithis can be used to store one or
`
`11
`
`11
`
`

`

`US 2007/0263528 A1
`
`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 considerationsithis can be used to store parameters
`that represent whether a particular packet is being transmit-
`ted to a mobile station that has power save mode; frame
`fitting metricithis 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.
`
`Frame fitting 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 frame is 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 frame to
`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 however a 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, some traffic 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 and priority 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 case it 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 packet classification and
`marking.
`that are
`the packets
`In some embodiments,
`[0047]
`assigned to a given frame bucket are 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”. Some orderings take place
`only for the oldest packets for each CID (also referred as
`“head of line”). Some orderings take place on the basis of all
`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], PDZ,
`.
`.
`. PDK to all of the packet descriptors for the
`packets stored in each frame bucket where PD 1 points to the
`
`12
`
`

`

`US 2007/0263528 A1
`
`Nov. 15, 2007
`
`packet descriptor of the highest rank packet according to a
`particular criteria, and PDK points to 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
`poor radio 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-
`tions at 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 another field 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 NALCID (where NALCID this is the number
`of CIDs being indexed) and pointers PDl, .
`.
`.
`, PDALCID 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 used to 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 of the structure this might take is shown in FIG. 4D
`where the ordering of all the packets 1 through NTOT 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 of line basis.
`[0055] The frame bucket wide parameter indexes, connec-
`tion set wide parameter indexes, and all packet wide param-
`eter indexes are maintained on an ongoing basis. As packets
`are received,
`they are added to the appropriate indexes.
`Similarly, 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 packets are treated
`as equal as opposed to 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 equal in this
`partial ordering. The processing cost
`to perform partial
`ordering compared to maintaining an ordered queue for all
`packets is much less. A partial ordering can be maintained in
`a similar manner to the above discussed indexes, the only
`difference being that the order of 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 more efficient 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 occupy is called the
`burst that corresponds to 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 BTS having two antennas, 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 A1
`
`Nov. 15, 2007
`
`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 that fit 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_l, P_2,}, the scheduler may start
`with P_l to pick the first set of packets and then remove
`packets which are above a certain value in the index I_1,
`then pick all packets in P_3 and so on. Which partial
`ordering or index to pick will depend upon the trade-off or
`optimization the scheduler is trying to make at a particular
`point.
`In some embodiments, there is