Title of Invention	SCHEDULING PACKET TRANSMISSIONS
Abstract	This disclosure provides a synchronous packet manager contaning a data structure for scheduling future synchronous packet transimissions and arbitrating between synchronous and asynchronous packet transimissions. Slots required for transmitting a synchronous packet are reserved by marking the corresponding entries in a synchronous packet reservation table. Rather than writing packets to many different queues, the application software fills in a single reservation table per BTS sector.

Title of Invention

SCHEDULING PACKET TRANSMISSIONS

Abstract

This disclosure provides a synchronous packet manager contaning a data structure for scheduling future synchronous packet transimissions and arbitrating between synchronous and asynchronous packet transimissions. Slots required for transmitting a synchronous packet are reserved by marking the corresponding entries in a synchronous packet reservation table. Rather than writing packets to many different queues, the application software fills in a single reservation table per BTS sector.

Full Text	FORM 2 THE PATENTS ACT, 1970 (39 of 1970) & THE PATENTS RULES, 2003 COMPLETE SPECIFICATION (See section 10, rule 13) "SCHEDULING PACKET TRANSMISSIONS" QUALCOMM INCORPORATED, a US Company, of 5775 Morehouse Drive, San Diego, California 92121, United States of America. The following specification particularly describes the invention and the manner in which it is to be performed. WO 2005/029793 PCTYUS2004/030487 2 SCHEDULING PACKET TRANSMISSIONS Claim of Priority under 35 U.S.C. §119 [0001] The present Application for Patent claims priority to Provisional Application No. 60/503,550, entitled "SCHEDULING SYNCHRONOUS PACKET TRANSMISSIONS ON A lxEV-DO FORWARD LINK" filed September 16, 2003, and assigned to the assignee hereof and hereby expressly incorporated by reference herein. BACKGROUND Field [0002] The present invention relates generally to data packet communications and more specifically to scheduling synchronous packet transmissions on a Time-Division Multiplexed (TDM) communications system. Background [0003] Recently there is a demand for a transmission system to handle both unicast and multicast/broadcast transmission. Unicast transmission is directed to one user, whereas multicast/broadcast is directed to multiple users. In a time-division multiplexed scheme, time slots may be scheduled for unicast or multicast/broadcast packet transmissions. Multicast and broadcast packets are typically synchronous. Thus multicast and broadcast packets are transmitted in specific time slots on a periodic basis. These synchronous packets may come from one or more sources, such as synchronous control channels, sub-synchronous control channels, or multicast/broadcast channels. Unicast packets are typically asynchronous and may be transmitted in any available slot. In other words, the synchronous packets typically have less flexible scheduling requirements than unicast packets. [0004] Packets may take multiple time slots to complete transmission, so the unicast scheduler schedules a unicast packet to complete transmission before the next synchronous packet is sent. When scheduling an asynchronous/unicast packet, the scheduler must be aware of future synchronous packet transmissions. When scheduling a unicast packet, the scheduler looks ahead, for example, the scheduler may consider as many as 64 slots, for synchronous packets that would be due to transmit within that time. In many cases, synchronous packets are not available sufficiently in advance to WO 2005/029793 PCT/US2004/030487 3> allow the scheduler to plan; but the unicast scheduler must still leave the appropriate slots open for synchronous packets. There is a need, therefore, to provide a simple, generic mechanism for handling synchronous and asynchronous packet transmissions in one system. SUMMARY [0005] The embodiments disclosed herein address the above stated needs by providing a synchronous packet manager that contains a data structure for scheduling future synchronous packet transmissions. Slots required for transmitting a synchronous packet can be reserved by marking the corresponding entries in a synchronous packet . reservation table. Rather than writing packets to many different queues, the network device fills in a single reservation table per Base Station Transceiver Sub-system (BTS) sector. [0006] Each entry in the reservation table may be assigned a priority, and the synchronous packet manager ensures that a lower priority packet will not preempt or overwrite a higher priority packet [00071 Finally, the synchronous packet manager provides a mechanism to automatically reserve slots in the reservation table .on a periodic basis. This mechanism inserts placeholder reservations into the reservation tables. Each placeholder reservation has a priority to ensure the slots wont get filled by a lower priority packet ' BRIEF DESCRIPTION OF THE DRAWINGS [0008] The features, objects, and advantages of the presently disclosed method and apparatus will become more apparent from the detailed description set forth below when taken in conjunction with the drawings: [0009] FIG. 1 is a diagram showing timeslots where packet data communications are transmitted on the Forward Link (FL). [0010] FIG. 2 is a diagram showing queues for the synchronous channels in a communication system. [0011] . FIG. 3 is a diagram showing thneslots interlaced on the FL. [0012] FIG. 4 is a table representing the timeslots where packet data communications are transmitted on the FL. WO 2005/029793 PCT/US2004/030487 4 [0013] FIG. 5 is a block diagram showing the interaction between the Base Station Controller (BSC) and the Base Station Transceiver Sub-system (BTS). [0014] FIG. 6 is a table representing a packet reservation table. [0015] FIG. 7 is a table representing a synchronous packet reservation table. [0016] FIG. 8 is a representation of three tables showing periodic synchronous reservation tables being filled simultaneously. [0017] FIG. 9 is a table showing an example of a periodic synchronous packet reservation. [0018] FIG. 10 is a diagram showing synchronous packet manager processing of a command. [0019] FIG. 11 is a table showing synchronous packet scheduling. [0020] FIG. 12 is a table showing computation of the index SyncMaxNumSlots. DETAILED DESCRIPTION [0021] The following discussion provides one or more embodiments serving as examples, instances, and/or for illustration purposes and clarity of understanding. Any embodiment described herein is not necessarily to be construed as preferred or advantageous over other embodiments. [0022] Increasing demand for wireless data transmission and the expansion of services available via wireless communication technology have led to the development of specific data services. One such service is referred to as High Data Rate (HDR). An example of a HDR type system is the one proposed in the "cdma2000 High Rate Packet Data Air Interface Specification" referred to as "the HAI specification" and as "TIA/EIA/IS-856." [0023] In one embodiment, a transmission system supports the standard protocols referred to as lxEV-DO. As shown in FIG. 1, the lxEV-DO forward link is time-division multiplexed, consisting of time slots; each of duration 1.66 ms, that may be scheduled for unicast or multicast/broadcast packet transmissions. When packets are sent to a single user, this is called "unicast" and when packets are sent to multiple users, this is called "multicast." Multicast and broadcast packets are typically synchronous, meaning they have to be transmitted in specific time slots, on a periodic basis. These synchronous packets may come from one or more sources, such as synchronous control channels 10 and 15, sub-synchronous control channels, or multicast/broadcast channels. WO 2005/029793 PCT/US2004/030487 5" Unicast packets are typically asynchronous and may be transmitted in any available slot. Traffic channels are also considered "unicast." In other words, the synchronous packets from the channels mentioned above typically have less flexible scheduling requirements than unicast packets. [0024] The data on a synchronous Control Channel (CC) is sent in at least one packet every 256 slots, as shown in FIG. 1. This data may consist of information sent to the Mobile Station (MS) such as system parameters. The data on a multicast/broadcast channel is sent periodically and has less flexible scheduling requirements than unicast. This data may consist of streaming video services. Finally, the data on a sub-synchronous control channel, a subdivision of the control channel, is also periodic but has a much smaller period than 256 slots. This data may consist of pages to the MS and may be used when 256 slots is too long a period to wait [0025] The basic problem in this system is to keep the synchronous and asynchronous data packets separate. In this particular system, packet transmissions are interlaced over four timeslots. A packet mat takes multiple slots to transmit will occupy every fourth slot until it completes transmission, as shown in FIG. 3. For example, the synchronous control channel is sent on timeslots 0 and 4 because me timeslots are interlaced and these data packets are not sent consecutively. Timeslot 1 may be used for sending asynchronous data such as traffic channel data. Interlacing gives the MS time to receive and attempt to decode a multi-slot packet before all slots of the packet have been transmitted. If the MS is able to decode the packet early, then it sends an ACK back to the Base Station (BS) to acknowledge receipt and successful decoding of the data packet. [0026] Others have solved this problem by using a "smart scheduler" as shown in FIG. 2. The smart scheduler knows the timing requirements of different types of synchronous channels. In this example, there are at least three logical channels: Control Channel (CC); Broadcast Channel (BC); and Sub-synchronous Control Channel (SCC). Each logical channel has a queue 45, 50, and 55, etc., in which application software submits to the scheduler the packets that need to be transmitted on the channel. There can be a large number of these queues 45, 50, and 55 (e.g., many broadcast channels). The scheduler looks at the different synchronous packet queues and decides when each packet is to be transmitted. After deciding when the synchronous packets will be WO 2005/029793 PCT/US2004/030487 L transmitted, the scheduler can schedule unicast/asynchronous transmissions to fill the remaining time slots. [0027] In FIG. 3, a control channel packet is sent on timeslots 0, 4, and 8 and a broadcast channel packet is sent on timeslot 10. The traffic channel data, which is a unicast data packet, is sent on timeslot 1 after the control channel and broadcast channel data packets have been assigned and reserved on specific slots. If other unicast data is to be sent on timeslots 2 and 6, for example, the scheduler will look ahead four other timeslots, that is, to make sure that there is no synchronous channel data reserved on timeslot 10. hi this case, since timeslot 10 is reserved for broadcast channel data, only timeslots 2 and 6 may be used for unicast channel data. That is, we. look ahead four timeslots from timeslot 6. Since timeslot 10 is already for broadcast channel data, unicast reservation stops at timeslot 6. The "smart scheduler" approach is more complicated. It does not have a reservation table, so the way it "looks ahead" is by examining all of its synchronous packet queues to see when the next sync packet is due to transmit Then it can decide how many slots are available for unicast [0028] FIG. 4 is a table representing me timeslots described in FIG. 3. This table is an easier way to represent packets being sent on four interlaces. Each entry in the sync packet reservation table may contain one of the following two types of reservations: a physical layer packet mat should begin transmitting in the slot mat it occupies; or a placeholder for a physical layer packet that should begin transmitting in the designated slot, provided that the actual packet is submitted to the sync packet manager before the scheduled start time. The first row (row 0) of the table represents the control channel data packets. In row 1, the first slot is reserved for traffic channel data. In row 2, since broadcast channel data is reserved on slot 10, only slots 2 and 6 can be used for unicast channel data. Data packets may take anywhere from 1 to 16 slots. The system looks ahead 16 slots to make sure there is no data scheduled within this range. Low rate packets take many slots to transmit, at most 16 slots * 4 interlaces = 64 slots. When scheduling a unicast packet, the scheduler has to be able to look ahead as many as 64 slots for synchronous packets that would be due to transmit within that time. In many cases, synchronous packets are not available 64 slots in advance, but the unicast scheduler still leaves the appropriate slots open for synchronous packets. In other words, the scheduler operation is limited so as to avoid over-writing synchronous data packets. WO 2005/029793 PCT/US2004/030487 1 [0029], The scheduling of timeslots is performed in BTS 25 of FIG. 5. As illustrated in this figure, the BSC 20 sends data to the BTS 25. A Content Server (CS) 29 is illustrated as providing data to BTS 25 and may also provide data via BSC 20. A problem occurs when BSC 20 does not send synchronous data; the BTS 25 still reserves a slot for synchronous data packets. The BSC sends the sync data after unicast scheduling decisions have already been made that could potentially conflict with the sync packet. There are two aspects to the problem. First, the scheduler must ensure asynchronous packets do not over-write synchronous packets. Second, even if the BSC 20 has not sent data to the BTS 25, the BTS 25 ensures that slots are reserved for synchronous data packets. In other words, the smart scheduler must know when synchronous packets are due to transmit even if the packet has not yet been written to its queue. The BTS 25 includes a scheduler 27, a synchronous packet manager 28, and a synchronous packet reservation table 30. (0030] The scheduler 27 dedicates memory for these queues and has knowledge of the timing requirements of the broadcast channel. The scheduler 27 will typically examine the head of each queue to determine if the channel has data to send. One problem with this method is complexity. This method requires extra memory to store channel information (eg, queues). Further this method is not flexible because the scheduler is updated on introduction of each new synchronous channel. Synchronous packet management [0031] In order to solve the above-mentioned problems, the following reservation table is described, m this regard, the reservation table is a simple and flexible solution because the scheduler 27 may operate without information regarding specific types of channels. As shown in the synchronous packet reservation table 30 as in FIG. 6, the synchronous packet manager 28 simply reports how many of the subsequent slots (if . any) are available for asynchronous/unicast packets. For example, the first 5 slots in row 0 can be used for unicast packets. The synchronous packet manager 28 arrives at this slot count by examining the next one or more entries in the reservation table. If a reservation table entry is empty then the slot is made available for unicast. [0032] The placeholder reservations ensure that a multi-slot unicast packet is not scheduled which overlaps the slots required by a future synchronous packet (one that may not have been written into the table yet). The synchronous packet manager 28 has WO 2005/029793 PCT/US2004/030487 2' no knowledge of specific synchronous channels, which makes it more flexible and capable of handling a wide range of channel types. Any number of logical channels (e.g., handled by application software) can write to the synchronous packet reservation table 30. The simplicity and flexibility of the synchronous packet manager 28 or scheduler 27 make each a good candidate for hardware implementation. [0033] The synchronous packet manager 28 or scheduler 27 has the following advantages. First, the generic mechanism easily extends to new synchronous channel types without firmware/hardware modification. The synchronous packet manager 28 was originally designed to handle the synchronous control channel and broadcast/multicast channels, but it will easily handle the new sub-synchronous control channel as well. Second, it scales well to large numbers of logical synchronous channels. A logical channel is one instance of a particular type of channel. For example, a three sector BTS could have 48 logical broadcast channels, 3 synchronous control channels, and 3 sub-synchronous control channels. Finally, it is a simple design mat could easily be implemented in hardware. [0034] In one embodiment, me FL DSP supports a generic synchronous packet interface mat can be used to transmit physical layer packets at specified start times. This interface is suitable for transmitting both synchronous control channel and broadcast channel packets, since in both cases, the host driver at me BTS knows ahead of time exactly when the packets are to be transmitted. In other words, this synchronous packet interface provides a means of bypassing the unicast scheduler and requesting a physical layer packet transmission beginning in a specific time slot. Sync packet reservation table [0035] In one embodiment, the FL DSP maintains a sync packet reservation table for each sector, as shown in FIG. 7. This reservation table is basically a calendar of future sync packet transmissions. The sync packet reservation table contains SYNC_PKT_WINDOW_SIZE entries, where each entry in the table represents one slot The table may be thought of as a sliding window of reservations, such that table entry 0 always represents the current slot, and table entry SYNC_PKT_WTNDOW_SIZE-l always represents the future-most reservation in the table. [0036] An example of a sync packet reservation table is shown below in FIG. 7. The table is shown containing four rows, which represent the four physical layer interlaces. WO 2005/029793 PCT/US2004/030487 This layout makes it easier to identify the slots that a multi-slot physical layer packet will occupy. A multi-slot packet that begins transmitting in slot S will also transmit in slots iS+4, S+8, etc., which are adjacent in the table shown in FIG. 7. [0037] Each entry in the sync packet reservation table may contain one of the following two types of reservations: a physical layer packet that should begin transmitting in the slot that it occupies; or a placeholder for a physical layer packet that should begin transmitting in the designated slot, provided that the actual packet is submitted to the sync packet manager before the scheduled start time. [003S] Each sync packet reservation table entry contains the following parameters: ? Priority (0 to 15) — the priority of this sync packet reservation. The sync packet manager ensures that a lower priority sync packet will not transmit in a slot reserved by a higher priority sync packet (or placeholder). Priority 0 is the lowest (unreserved) and priority 15 is the highest. An unreserved slot will have a priority of 0. ? Medium Access Control (MAC) Index (0 to 63) -the MAC index on which the physical layer packet should be transmitted. An unreserved slot or a placeholder reservation will have a MAC index of 0. ? Rate (1 to 12) — the rate at which the physical layer packet should be transmitted. The rate values are the same as those specified for Data Rate Control (DRQ rates. Note mat physical layer packet rates other than the specific DRC rates may be achieved by adjusting "Num Slots," which is described below. An unreserved slot or a placeholder reservation will have a Rate of 0. ? Num Slots (1 to 16) — the number of slots over which the physical layer packet should be transmitted. The number of slots to be less than or equal to the maximum number of slots required for a physical layer packet at the specified rate.. An unreserved slot or a placeholder reservation will have Num Slots set to 0. WO 20057029793 PCT/US2004/030487 9- ■ Encoder Indices - array of MAX_SYNC_PKTS_PER_SLOT encoder indices (e.g., 2) that identify the MAC layer packets in this physical layer packet. If a physical layer packet at the specified rate requires fewer than MAX_SYNC_PKTS_PER_SLOT MAC layer packets, then the sync packet manager ignores the extra values. An unreserved slot or a placeholder reservation will have its encoder indices set to 0. [0039] Note, a multi-slot sync packet will occupy one entry in the sync packet reservation table (i.e., the one that corresponds with its start time). The sync packet manager resolves collisions, or overlapping sync packets, at the time of scheduling, which is approximately one slot before a sync packet's start time. Periodic sync packet reservations [0040] This section describes how and when the sync packet manager writes the 'placeholder7' reservations to the sync packet reservation tables. [0041] Most synchronous packet transmissions occur on a periodic basis. The synchronous control channel, for example, has a period of 256 slots, or 64 interlace slots on an interlace. Sync packets often aren't available until only a few slots before their scheduled start time, and without any means of reserving the slots for a sync packet transmission, an overlapping multi-slot packet could get scheduled before the sync packet write even occurs. As shown in FIG. 8, the sync packet manager provides the "placeholder" reservations as a way to hold slots open for sync packets that will be written into the reservation tables 65,70, and 75 at any time within the reservation table window. Reservation tables 65,70, and 75 are sync packet reservation tables for sectors 0,1, and 2, respectively. [0042] The sync packet manager maintains a separate list of periodic reservations 60, which trigger the placeholder writes into the sync packet reservation tables. These periodic reservations are updated by the ReserveSyncSlotsCmd and the UnreserveSyncSlotsCmd. Each periodic reservation has the following properties: ? Priority - the priority that the placeholder entry will have in the sync packet reservation table(s). ? SectorMask — the sectors) that identify the sync packet reservation table(s) that the placeholders should be written to. WO 2005/029793 PCTAJS2004/030487 * 11 ? StaxtTime — the system time that identifies the first slot that should be reserved. The sync packet manager writes all placeholders to the future-most slot of the reservation table(s)5 so the start time must be at least SYNC_PKT_W1ND0W_SIZE slots in the future. ? InterlacePeriod - the period of the reservation in units of interlace slots. ? InterlaceBurstLength - the duty cycle of the reservation in units of interlace slots (less than or equal to InterlacePeriod). ? InterlaceNumSlots - the period (in units of interlace slots) at which the placeholder reservations should be written to the sync packet reservation table(s). [0043] The sync packet manager processes all periodic reservations every slot. FIG. 8 shows the processing of the periodic reservations. Note that all placeholders are written to die future-most entries of the sync packet reservation tables to ensure that the slots won't get allocated to unicast A single reservation 60 can be sent to multiple tables 65, 70, and 75. (0044] The sync packet manager maintains counters that track the period, burst length, and num slots for each periodic reservation. Daring the first "burst length" slots of the period, the sync packet manager writes the placeholders every "num slots.** Two examples are shown in FIG. 9. The example shows two reservations flowing through the sync packet reservation table. Both periodic reservations have an interlace period of 8 slots and an interlace burst length of 6 slots. The periodic reservation on interlace 0 has InterlaceNumSlots set to 1, whereas the periodic reservation on interlace 2 has InterlaceNumSlots set to 2. Interlace 0 begins in the slot 0 (the current slot) and is a burst of 6 slots. Since the NumSlots is set to 1, the period for slot reservation is one, i.e., each consecutive slot Interlace 2 begins in the slot 0 and is a burst of 1 slot. Since the NumSlots is set to 2, the period for slot reservation is two, i.e., after every other slot [0045] Two or more periodic reservations may overlap. If a reservation table entry already has a placeholder reservation, which is recorded in the scheduler, then the sync packet manager preserves the one with the highest priority. Sync packet writes [0046] This section describes how the sync packet manager processes the SendSyncPktsCmd- Each SendSyncPkts command contains one or more physical layer WO 2005/029793 PCT/US2004/030487 'y 12 packets, which may be transmitted on one or more sectors (as specified by SectorMask). FIG. 10 shows the sync packet reservation tables for three sectors and several SendSynkPkts commands. A single command can be sent to multiple tables 85, 90, and 95. [0047] When processing a SendSyncPktsCmd, the sync packet manager iterates over the packets in the command, and performs the following for each packet 1. Validate the StartTime. The StartTime is to be within the current sync packet reservation table window of time. If StartTime is invalid, the sync packet manager issues a packet drop message for this packet for each sector present in SectorMask. 2. Find conflicting packets. At this stage, sync packet reservations only conflict if they have the same start time, hi other words, as long as the sync packet manager can write the packet to the reservation table, it doesn't care if multi-slot packets will overlap. If a sync packet already- occupies the reservation table entry, men the sync packet manager issues a packet drop message for me lower priority packet If the packets have the same priority men me sync packet manager drops me older packet If the reservation table entry contains a placeholder packet reservation, men me write will succeed only if the packet has a priority greater man or equal to the placeholder's priority. 3. Write the sync packet reservations). For each sector present in the command's SectorMask, and provided the packet was not dropped on this sector, write the packet information to the sector's reservation table entry that corresponds with the packet's start time. Sync packet scheduling [0048] The sync packet manager must look at each reservation table of a sector to see if a sync packet is to be transmitted. As shown in FIG. 11, if the sync packet manager finds a packet reservation in the "next slof' entry of a reservation table in each sector, then it ensures that the sync packet can be transmitted without colliding with a packet that is already transmitting or colliding with a higher priority sync packet (or sync packet placeholder) in subsequent slots on the interlace. For example, on interlace 1, "next slot" 1 knows that it will not collide with another slot having higher priority until WO 2005/029793 PCTAJS2004/030487 Y J3 many slots later. Therefore, all the slots that are not reserved may be used for unicast/asynchronous packets. \|0049] More specifically, the sync packet manager performs the following two tests when finding a sync packet reservation in the "next slof' reservation table entry: ? If there is already a packet transmitting on the "next slot" interlace, and this packet is due to repeat in the next slot, then the next-slot sync packet is dropped. There are two reasons why this may occur. Either the sync packet was written to the reservation table after a multi-slot unicast packet was already scheduled on the interlace (and the sync packet did not have a placeholder reservation), or an earlier higher priority multi-slot sync packet was given priority on the interlace. ? If the "next slot" sync packet will require more than one slot to transmit, then the sync packet manager looks ahead NumSlots-1 (where NumSlots is the. number of slots that the packet will require) on the interlace to make sure that the packet won't collide with any higher priority sync packet or sync packet placeholder reservation, as shown in FIG. 11. [0050] If either test tails, then the sync packet manager issues a CSDTDEFS SyncPktDroppedMsg for the "next slot" sync packet Interaction with the unicast scheduler [0051] hi one embodiment, the FL DSP gives priority to sync packets over unicast/asynchronous packets, so sync packet scheduling always occurs before unicast scheduling. However, if a "next slot" sync packet reservation table entry is free, then the slot is made available to the unicast scheduler. Furthermore, the sync packet manager looks ahead on the "next slot" interlace to see how many subsequent slots can be made available for unicast. This count is called SyncMaxNumSlots, which is provided to the unicast scheduler every slot for each sector. If SyncMaxNumSlots for a sector is zero then the next slot is not available for unicast data; otherwise, the unicast scheduler may schedule a packet that does not exceed SyncMaxNumSlots. FIG. 12 depicts the computation of SyncMaxNumSlots for a particular sector. [0052] Physical layer packets do not exceed 16 slots, so the sync packet manager examines each reservation table entry on the interlace until encountering a sync packet reservation, as shown in FIG. 12, or SyncMaxNumSlots reaches 16. WO 2005/029793 PCT/US2004/030487 43- [0053] Note, if the "next slot" reservation table entry contains a placeholder reservation, then SyncMaxNumSlots will normally be zero (i.e., not available for unicast data). The lack of an actual sync packet for the "next slot" will result in an idle slot transmission during the next slot. In many cases, this is desirable; however, the sync packet manager also supports a mode that allows unused "next slot" placeholder reservations to be released for unicast data. This mode may be useful for bursty logical synchronous channels (e.g., some types of broadcast channels), in which unicast data could be sent if the synchronous channel does not have data available. The synchronous packet manager supports this mode via a particular placeholder reservation priority level, as described below. [0054] For the purpose of updating SyncMaxNumSlots, placeholder packet reservations with a "next slot" 1 have a slightly different behavior. A "next slof' 1 placeholder reservation in table entry 1 will be considered available for unicast A priority 1 placeholder reservation in table entries greater than 1 (e.g., slots 5, 9, 13, etc. in FIG. 12) will be excluded from unicast data when updating SyncMaxNumSlots. In other words, a priority 1 placeholder in the next-slot position will be released for unicast, but a next-slot placeholder reservation with priority greater man 1 will force an idle slot transmission. [0055] Note: SYNC_PKT_WINDOW_SIZE will be at least 16*4=64 slots since SyncMaxNumSlots ranges from 1 to 16. [0056] Those of skill in the art would understand that various steps or elements in the embodiments may be altered or their order rearranged without varying from the invention that has been disclosed. [0057] Those of skill in the art would understand that information and signals may be represented using any of a variety of different technologies and techniques. For example, data, instructions, commands, information, signals, bits, symbols, and chips that may be referenced throughout the above description may be represented by voltages, currents, electromagnetic waves, magnetic fields or particles, optical fields or particles, or any combination thereof. [0058] Those of skill would further appreciate that the various illustrative logical blocks, modules, circuits, and algorithm steps described in connection with the embodiments disclosed herein may be implemented as electronic hardware, computer software, or combinations of both. To clearly illustrate this interchangeability of WO 2005/029793 PCT/US2004/030487 hardware and software, various illustrative components, blocks, modules, circuits, and steps have been described above generally in terms of their functionality. Whether such functionality is implemented as hardware or software depends upon the particular application and design constraints imposed on the overall system. Skilled artisans may implement the described functionality in varying ways for each particular application, but such implementation decisions should not be interpreted as causing a departure from the scope of the present invention [0059] The various illustrative logical blocks, modules, and circuits described in connection with the embodiments disclosed herein may be implemented or performed with a general purpose processor, a digital signal processor (DSP), an application specific integrated circuit (ASIC), a field programmable gate array (FPGA) or other programmable logic device, discrete gate or transistor logic, discrete hardware components, or any combination thereof designed to perform the functions described herein. A general purpose processor may be a microprocessor may be any conventional processor, controller, microcontroller, or state machine. A processor may also be implemented as a combination of computing devices, eg., a combination of a DSP and a microprocessor, a plurality of microprocessors, one or more microprocessors in conjunction with a DSP cove, or any other such configuration. [0060] The steps of a method or algorithm described in connection with the embodiments disclosed herein may be embodied directly in hardware, in a software module executed by a processor, or in a combination of the two. A software module may reside in RAM memory, flash memory, ROM memory, EPROM memory, , EEPROM memory, registers, hard disk, a removable disk, a CD-ROM, or any other form of storage medium known in the art. An exemplary storage medium is coupled to the processor such the processor may read information from, and write information to, the storage medium. In the alternative, the storage medium may be integral to the processor. The processor and the storage medium may reside in an ASIC. The ASIC may reside in a user terminal such as the MS or reside at the BS. In the alternative, the processor and the storage medium may reside as discrete components in a user terminal. [0061] The previous description of the disclosed embodiments is provided to enable any person skilled in the art to make or use the present invention. Various modifications to these embodiments will be readily apparent to those skilled in the art, and the generic WO 2005/029793 PCT/US2004/030487 principles defined herein may be applied to other embodiments without departing from the spirit or scope of the invention. Thus, the present invention is not intended to be limited to the embodiments shown herein but is to be accorded the widest scope consistent with the principles and novel features disclosed herein. [0062] WHAT IS CLAIMED IS: WO 2005/029793 17 PCTYUS2004/030487 CLAIMS 1. An apparatus for scheduling synchronous packet transmissions, comprising: a synchronous packet manager for scheduling synchronous packet transmissions; and a synchronous packet reservation table for storing slot reservations for the synchronous packet transmissions. 2. The apparatus in claim 1, wherein the synchronous packet manager further comprises a packet scheduler for scheduling asynchronous packet transmissions in response to the synchronous packet reservation table. 3. The apparatus in claim 1, wherein the synchronous packet reservation table is further for storing status information, wherein me status irrformation comprises: a priority of a synchronous packet reservation; and a number of slots over which the packet is transmitted. 4. The apparatus m claim 1, wherein the synchronous packet manager determines reservation to be written in the synchronous packet reservation table. 5. The apparatus in claim 1, wherein the synchronous packet manager maintains a record of a period, burst length, and num slots for each of said reservation. 6. The apparatus in claim 2, wherein the synchronous packet manager is further adapted to: validate a start time; find conflicting packets; and write a synchronous packet reservation in the synchronous packet reservation table. 7. The apparatus in claim 2, wherein the asynchronous packet transmissions are traffic data. WO 2005/029793 PCT/US2004/030487 JS XT 8. The apparatus in claim 4, wherein the reservation comprises: a priority for a placeholder entry; a Start_Time that identifies a first slot to be reserved; an Interlace_Period that indicates a period of the reservation; an Interlace_Burst_Length that indicates a duty cycle of the reservation; and an Interlace_Num_Slots index that indicates a period at which the reservation is written. 9. The apparatus in claim 4, wherein the reservation is sent to multiple synchronous packet reservation tables. 10. A method for scheduling synchronous packet transmissions, comprising: scheduling synchronous packet transmissions; and storing slot reservations for the synchronous packet transmissions. 11. The method in claim 10, wherein scheduling synchronous packet transmissions further comprises scheduling asynchronous packet transmissions in response to a synchronous packet reservation table. 12. The method in claim 10, wherein scheduling synchronous packet transmissions further comprises writing a reservation in the synchronous packet reservation table. 13. The method in claim 10, wherein scheduling synchronous packet transmissions further comprises maintaining a record of a period, burst length, and num-slots for each of said reservation. 14. The method in claim 11, wherein the asynchronous packet transmissions are traffic data. 15. The method in claim 12, wherein writing the reservation further comprises: validating a start time; finding conflicting packets; and WO 2005/029793 PCT/US2004/030487 19 writing a synchronous packet reservation in the synchronous packet reservation table. 16. The method in claim 12, wherein writing the reservation is performed on multiple synchronous packet reservation tables. 17. An apparatus for scheduling synchronous packet transmissions, comprising: means for scheduling synchronous packet transmissions; and means for storing slot reservations for the synchronous packet transmissions. 18. The apparatus in claim 17, wherein the means for scheduling synchronous packet transmissions further comprises a packet scheduler for scheduling asynchronous packet transmissions in response to a synchronous packet reservation table. 19. The apparatus in claim 17, wherein the status information comprises: a priority of a synchronous packet reservation; and a number of slots corresponding to a period of slots for the synchronous packet reservation over which the packet is transmitted. 20. The apparatus in claim 17, wherein the means for scheduling maintains a record of a period, burst length, and num-slots for each of said reservation. 21. The apparatus in claim 17, wherein the means for scheduling further determines a reservation to be written in the synchronous packet reservation table. 22. The apparatus in claim 17, wherein the means for scheduling synchronous packet transmissions is further adapted to: validate a start time; find conflicting packets; and write a synchronous packet reservation in the synchronous packet reservation table. 23. The apparatus in claim 20, wherein the reservation comprises: WO 2005/029793 PCTYUS2004/030487 2o a priority for a placeholder entry, a Start-Time that identifies a first slot to be reserved; an Interlace-Period that indicates a period of the reservation; an Interlace_Burst_Length that indicates a duty cycle of the reservation; and an lnterlace-Num-_Slots index that indicates a period at which the reservation is written. 24. The apparatus in claim 20, wherein the reservation is sent to multiple synchronous packet reservation tables. 25. An apparatus for scheduling synchronous packet transmissions, comprising: a memory storage unit; and a processor coupled to the memory storage unit and adapted for: scheduling synchronous packet transmissions; and storing slot reservations for the synchronous packet transmissions. 26. An apparatus for scheduling synchronous packet transmissions and a method for scheduling synchronous packet transmissions, 27. 28. substantially as herein described, particularly with reference to, and as illustrated in the accompanying drawings. Dated this 27th day of March 2006 RAJESHWARIH. Of K & S PARTNERS ATTORNEY FOR THE APPLICANTS 2-1 ABSTRACT This disclosure provides a synchronous packet manager containing a data structure for scheduling future synchronous packet transmissions and arbitrating between synchronous and asynchronous packet transmissions. Slots required for transmitting a synchronous packet are reserved by marking the corresponding entries in a synchronous packet reservation table. Rather than writing packets to many different queues, the application software fills in a single reservation table per BTS sector.

Full Text

FORM 2
THE PATENTS ACT, 1970
(39 of 1970)
&
THE PATENTS RULES, 2003
COMPLETE SPECIFICATION
(See section 10, rule 13)
"SCHEDULING PACKET TRANSMISSIONS"

QUALCOMM INCORPORATED, a US Company, of 5775 Morehouse Drive, San Diego, California 92121, United States of America.
The following specification particularly describes the invention and the manner in which it is to be performed.

WO 2005/029793

PCTYUS2004/030487

2
SCHEDULING PACKET TRANSMISSIONS
Claim of Priority under 35 U.S.C. §119
[0001] The present Application for Patent claims priority to Provisional Application
No. 60/503,550, entitled "SCHEDULING SYNCHRONOUS PACKET
TRANSMISSIONS ON A lxEV-DO FORWARD LINK" filed September 16, 2003,
and assigned to the assignee hereof and hereby expressly incorporated by reference
herein.
BACKGROUND
Field
[0002] The present invention relates generally to data packet communications and more
specifically to scheduling synchronous packet transmissions on a Time-Division
Multiplexed (TDM) communications system.
Background
[0003] Recently there is a demand for a transmission system to handle both unicast and
multicast/broadcast transmission. Unicast transmission is directed to one user, whereas multicast/broadcast is directed to multiple users. In a time-division multiplexed scheme, time slots may be scheduled for unicast or multicast/broadcast packet transmissions. Multicast and broadcast packets are typically synchronous. Thus multicast and broadcast packets are transmitted in specific time slots on a periodic basis. These synchronous packets may come from one or more sources, such as synchronous control channels, sub-synchronous control channels, or multicast/broadcast channels. Unicast packets are typically asynchronous and may be transmitted in any available slot. In other words, the synchronous packets typically have less flexible scheduling requirements than unicast packets.
[0004] Packets may take multiple time slots to complete transmission, so the unicast
scheduler schedules a unicast packet to complete transmission before the next synchronous packet is sent. When scheduling an asynchronous/unicast packet, the scheduler must be aware of future synchronous packet transmissions. When scheduling a unicast packet, the scheduler looks ahead, for example, the scheduler may consider as many as 64 slots, for synchronous packets that would be due to transmit within that time. In many cases, synchronous packets are not available sufficiently in advance to

WO 2005/029793 PCT/US2004/030487
3>
allow the scheduler to plan; but the unicast scheduler must still leave the appropriate slots open for synchronous packets. There is a need, therefore, to provide a simple, generic mechanism for handling synchronous and asynchronous packet transmissions in one system.
SUMMARY
[0005] The embodiments disclosed herein address the above stated needs by providing
a synchronous packet manager that contains a data structure for scheduling future synchronous packet transmissions. Slots required for transmitting a synchronous packet can be reserved by marking the corresponding entries in a synchronous packet . reservation table. Rather than writing packets to many different queues, the network device fills in a single reservation table per Base Station Transceiver Sub-system (BTS) sector.
[0006] Each entry in the reservation table may be assigned a priority, and the
synchronous packet manager ensures that a lower priority packet will not preempt or overwrite a higher priority packet
[00071 Finally, the synchronous packet manager provides a mechanism to automatically
reserve slots in the reservation table .on a periodic basis. This mechanism inserts
placeholder reservations into the reservation tables. Each placeholder reservation has a
priority to ensure the slots wont get filled by a lower priority packet '
BRIEF DESCRIPTION OF THE DRAWINGS
[0008] The features, objects, and advantages of the presently disclosed method and
apparatus will become more apparent from the detailed description set forth below when
taken in conjunction with the drawings:
[0009] FIG. 1 is a diagram showing timeslots where packet data communications are
transmitted on the Forward Link (FL).
[0010] FIG. 2 is a diagram showing queues for the synchronous channels in a
communication system.
[0011] . FIG. 3 is a diagram showing thneslots interlaced on the FL.
[0012] FIG. 4 is a table representing the timeslots where packet data communications
are transmitted on the FL.

WO 2005/029793 PCT/US2004/030487
4
[0013] FIG. 5 is a block diagram showing the interaction between the Base Station
Controller (BSC) and the Base Station Transceiver Sub-system (BTS).
[0014] FIG. 6 is a table representing a packet reservation table.
[0015] FIG. 7 is a table representing a synchronous packet reservation table.
[0016] FIG. 8 is a representation of three tables showing periodic synchronous
reservation tables being filled simultaneously.
[0017] FIG. 9 is a table showing an example of a periodic synchronous packet
reservation.
[0018] FIG. 10 is a diagram showing synchronous packet manager processing of a
command.
[0019] FIG. 11 is a table showing synchronous packet scheduling.
[0020] FIG. 12 is a table showing computation of the index SyncMaxNumSlots.
DETAILED DESCRIPTION
[0021] The following discussion provides one or more embodiments serving as
examples, instances, and/or for illustration purposes and clarity of understanding. Any embodiment described herein is not necessarily to be construed as preferred or advantageous over other embodiments.
[0022] Increasing demand for wireless data transmission and the expansion of services
available via wireless communication technology have led to the development of specific data services. One such service is referred to as High Data Rate (HDR). An example of a HDR type system is the one proposed in the "cdma2000 High Rate Packet Data Air Interface Specification" referred to as "the HAI specification" and as "TIA/EIA/IS-856."
[0023] In one embodiment, a transmission system supports the standard protocols
referred to as lxEV-DO. As shown in FIG. 1, the lxEV-DO forward link is time-division multiplexed, consisting of time slots; each of duration 1.66 ms, that may be scheduled for unicast or multicast/broadcast packet transmissions. When packets are sent to a single user, this is called "unicast" and when packets are sent to multiple users, this is called "multicast." Multicast and broadcast packets are typically synchronous, meaning they have to be transmitted in specific time slots, on a periodic basis. These synchronous packets may come from one or more sources, such as synchronous control channels 10 and 15, sub-synchronous control channels, or multicast/broadcast channels.

WO 2005/029793 PCT/US2004/030487
5"
Unicast packets are typically asynchronous and may be transmitted in any available slot.
Traffic channels are also considered "unicast." In other words, the synchronous packets
from the channels mentioned above typically have less flexible scheduling requirements
than unicast packets.
[0024] The data on a synchronous Control Channel (CC) is sent in at least one packet
every 256 slots, as shown in FIG. 1. This data may consist of information sent to the Mobile Station (MS) such as system parameters. The data on a multicast/broadcast channel is sent periodically and has less flexible scheduling requirements than unicast. This data may consist of streaming video services. Finally, the data on a sub-synchronous control channel, a subdivision of the control channel, is also periodic but has a much smaller period than 256 slots. This data may consist of pages to the MS and may be used when 256 slots is too long a period to wait
[0025] The basic problem in this system is to keep the synchronous and asynchronous
data packets separate. In this particular system, packet transmissions are interlaced over four timeslots. A packet mat takes multiple slots to transmit will occupy every fourth slot until it completes transmission, as shown in FIG. 3. For example, the synchronous control channel is sent on timeslots 0 and 4 because me timeslots are interlaced and these data packets are not sent consecutively. Timeslot 1 may be used for sending asynchronous data such as traffic channel data. Interlacing gives the MS time to receive and attempt to decode a multi-slot packet before all slots of the packet have been transmitted. If the MS is able to decode the packet early, then it sends an ACK back to the Base Station (BS) to acknowledge receipt and successful decoding of the data packet.
[0026] Others have solved this problem by using a "smart scheduler" as shown in FIG.
2. The smart scheduler knows the timing requirements of different types of synchronous channels. In this example, there are at least three logical channels: Control Channel (CC); Broadcast Channel (BC); and Sub-synchronous Control Channel (SCC). Each logical channel has a queue 45, 50, and 55, etc., in which application software submits to the scheduler the packets that need to be transmitted on the channel. There can be a large number of these queues 45, 50, and 55 (e.g., many broadcast channels). The scheduler looks at the different synchronous packet queues and decides when each packet is to be transmitted. After deciding when the synchronous packets will be

WO 2005/029793 PCT/US2004/030487
L

transmitted, the scheduler can schedule unicast/asynchronous transmissions to fill the remaining time slots.
[0027] In FIG. 3, a control channel packet is sent on timeslots 0, 4, and 8 and a
broadcast channel packet is sent on timeslot 10. The traffic channel data, which is a unicast data packet, is sent on timeslot 1 after the control channel and broadcast channel data packets have been assigned and reserved on specific slots. If other unicast data is to be sent on timeslots 2 and 6, for example, the scheduler will look ahead four other timeslots, that is, to make sure that there is no synchronous channel data reserved on timeslot 10. hi this case, since timeslot 10 is reserved for broadcast channel data, only timeslots 2 and 6 may be used for unicast channel data. That is, we. look ahead four timeslots from timeslot 6. Since timeslot 10 is already for broadcast channel data, unicast reservation stops at timeslot 6. The "smart scheduler" approach is more complicated. It does not have a reservation table, so the way it "looks ahead" is by examining all of its synchronous packet queues to see when the next sync packet is due to transmit Then it can decide how many slots are available for unicast
[0028] FIG. 4 is a table representing me timeslots described in FIG. 3. This table is an
easier way to represent packets being sent on four interlaces. Each entry in the sync packet reservation table may contain one of the following two types of reservations: a physical layer packet mat should begin transmitting in the slot mat it occupies; or a placeholder for a physical layer packet that should begin transmitting in the designated slot, provided that the actual packet is submitted to the sync packet manager before the scheduled start time. The first row (row 0) of the table represents the control channel data packets. In row 1, the first slot is reserved for traffic channel data. In row 2, since broadcast channel data is reserved on slot 10, only slots 2 and 6 can be used for unicast channel data. Data packets may take anywhere from 1 to 16 slots. The system looks ahead 16 slots to make sure there is no data scheduled within this range. Low rate packets take many slots to transmit, at most 16 slots * 4 interlaces = 64 slots. When scheduling a unicast packet, the scheduler has to be able to look ahead as many as 64 slots for synchronous packets that would be due to transmit within that time. In many cases, synchronous packets are not available 64 slots in advance, but the unicast scheduler still leaves the appropriate slots open for synchronous packets. In other words, the scheduler operation is limited so as to avoid over-writing synchronous data packets.

WO 2005/029793 PCT/US2004/030487
1
[0029], The scheduling of timeslots is performed in BTS 25 of FIG. 5. As illustrated in
this figure, the BSC 20 sends data to the BTS 25. A Content Server (CS) 29 is illustrated as providing data to BTS 25 and may also provide data via BSC 20. A problem occurs when BSC 20 does not send synchronous data; the BTS 25 still reserves a slot for synchronous data packets. The BSC sends the sync data after unicast scheduling decisions have already been made that could potentially conflict with the sync packet. There are two aspects to the problem. First, the scheduler must ensure asynchronous packets do not over-write synchronous packets. Second, even if the BSC 20 has not sent data to the BTS 25, the BTS 25 ensures that slots are reserved for synchronous data packets. In other words, the smart scheduler must know when synchronous packets are due to transmit even if the packet has not yet been written to its queue. The BTS 25 includes a scheduler 27, a synchronous packet manager 28, and a synchronous packet reservation table 30.
(0030] The scheduler 27 dedicates memory for these queues and has knowledge of the
timing requirements of the broadcast channel. The scheduler 27 will typically examine the head of each queue to determine if the channel has data to send. One problem with this method is complexity. This method requires extra memory to store channel information (eg, queues). Further this method is not flexible because the scheduler is updated on introduction of each new synchronous channel.
Synchronous packet management
[0031] In order to solve the above-mentioned problems, the following reservation table
is described, m this regard, the reservation table is a simple and flexible solution because the scheduler 27 may operate without information regarding specific types of channels. As shown in the synchronous packet reservation table 30 as in FIG. 6, the synchronous packet manager 28 simply reports how many of the subsequent slots (if . any) are available for asynchronous/unicast packets. For example, the first 5 slots in row 0 can be used for unicast packets. The synchronous packet manager 28 arrives at this slot count by examining the next one or more entries in the reservation table. If a reservation table entry is empty then the slot is made available for unicast.
[0032] The placeholder reservations ensure that a multi-slot unicast packet is not
scheduled which overlaps the slots required by a future synchronous packet (one that may not have been written into the table yet). The synchronous packet manager 28 has

WO 2005/029793

PCT/US2004/030487

2'
no knowledge of specific synchronous channels, which makes it more flexible and capable of handling a wide range of channel types. Any number of logical channels (e.g., handled by application software) can write to the synchronous packet reservation table 30. The simplicity and flexibility of the synchronous packet manager 28 or scheduler 27 make each a good candidate for hardware implementation.
[0033] The synchronous packet manager 28 or scheduler 27 has the following
advantages. First, the generic mechanism easily extends to new synchronous channel types without firmware/hardware modification. The synchronous packet manager 28 was originally designed to handle the synchronous control channel and broadcast/multicast channels, but it will easily handle the new sub-synchronous control channel as well. Second, it scales well to large numbers of logical synchronous channels. A logical channel is one instance of a particular type of channel. For example, a three sector BTS could have 48 logical broadcast channels, 3 synchronous control channels, and 3 sub-synchronous control channels. Finally, it is a simple design mat could easily be implemented in hardware.
[0034] In one embodiment, me FL DSP supports a generic synchronous packet interface
mat can be used to transmit physical layer packets at specified start times. This interface is suitable for transmitting both synchronous control channel and broadcast channel packets, since in both cases, the host driver at me BTS knows ahead of time exactly when the packets are to be transmitted. In other words, this synchronous packet interface provides a means of bypassing the unicast scheduler and requesting a physical layer packet transmission beginning in a specific time slot.
Sync packet reservation table
[0035] In one embodiment, the FL DSP maintains a sync packet reservation table for
each sector, as shown in FIG. 7. This reservation table is basically a calendar of future sync packet transmissions. The sync packet reservation table contains SYNC_PKT_WINDOW_SIZE entries, where each entry in the table represents one slot The table may be thought of as a sliding window of reservations, such that table entry 0 always represents the current slot, and table entry SYNC_PKT_WTNDOW_SIZE-l always represents the future-most reservation in the table.
[0036] An example of a sync packet reservation table is shown below in FIG. 7. The
table is shown containing four rows, which represent the four physical layer interlaces.

WO 2005/029793 PCT/US2004/030487
This layout makes it easier to identify the slots that a multi-slot physical layer packet will occupy. A multi-slot packet that begins transmitting in slot S will also transmit in slots iS+4, S+8, etc., which are adjacent in the table shown in FIG. 7.
[0037] Each entry in the sync packet reservation table may contain one of the following
two types of reservations: a physical layer packet that should begin transmitting in the slot that it occupies; or a placeholder for a physical layer packet that should begin transmitting in the designated slot, provided that the actual packet is submitted to the sync packet manager before the scheduled start time.
[003S] Each sync packet reservation table entry contains the following parameters:
? Priority (0 to 15) — the priority of this sync packet reservation. The sync packet manager ensures that a lower priority sync packet will not transmit in a slot reserved by a higher priority sync packet (or placeholder). Priority 0 is the lowest (unreserved) and priority 15 is the highest. An unreserved slot will have a priority of 0.
? Medium Access Control (MAC) Index (0 to 63) -the MAC index on which the physical layer packet should be transmitted. An unreserved slot or a placeholder reservation will have a MAC index of 0.
? Rate (1 to 12) — the rate at which the physical layer packet should be transmitted. The rate values are the same as those specified for Data Rate Control (DRQ rates. Note mat physical layer packet rates other than the specific DRC rates may be achieved by adjusting "Num Slots," which is described below. An unreserved slot or a placeholder reservation will have a Rate of 0.
? Num Slots (1 to 16) — the number of slots over which the physical layer packet should be transmitted. The number of slots to be less than or equal to the maximum number of slots required for a physical layer packet at the specified rate.. An unreserved slot or a placeholder reservation will have Num Slots set to 0.

WO 20057029793 PCT/US2004/030487
9-
■ Encoder Indices - array of MAX_SYNC_PKTS_PER_SLOT encoder
indices (e.g., 2) that identify the MAC layer packets in this physical layer
packet. If a physical layer packet at the specified rate requires fewer than
MAX_SYNC_PKTS_PER_SLOT MAC layer packets, then the sync packet
manager ignores the extra values. An unreserved slot or a placeholder
reservation will have its encoder indices set to 0.
[0039] Note, a multi-slot sync packet will occupy one entry in the sync packet
reservation table (i.e., the one that corresponds with its start time). The sync packet
manager resolves collisions, or overlapping sync packets, at the time of scheduling,
which is approximately one slot before a sync packet's start time.
Periodic sync packet reservations
[0040] This section describes how and when the sync packet manager writes the
'placeholder7' reservations to the sync packet reservation tables.
[0041] Most synchronous packet transmissions occur on a periodic basis. The
synchronous control channel, for example, has a period of 256 slots, or 64 interlace slots on an interlace. Sync packets often aren't available until only a few slots before their scheduled start time, and without any means of reserving the slots for a sync packet transmission, an overlapping multi-slot packet could get scheduled before the sync packet write even occurs. As shown in FIG. 8, the sync packet manager provides the "placeholder" reservations as a way to hold slots open for sync packets that will be written into the reservation tables 65,70, and 75 at any time within the reservation table window. Reservation tables 65,70, and 75 are sync packet reservation tables for sectors 0,1, and 2, respectively.
[0042] The sync packet manager maintains a separate list of periodic reservations 60,
which trigger the placeholder writes into the sync packet reservation tables. These periodic reservations are updated by the ReserveSyncSlotsCmd and the UnreserveSyncSlotsCmd. Each periodic reservation has the following properties:
? Priority - the priority that the placeholder entry will have in the sync packet reservation table(s).
? SectorMask — the sectors) that identify the sync packet reservation table(s) that the placeholders should be written to.

WO 2005/029793 PCTAJS2004/030487
* 11
? StaxtTime — the system time that identifies the first slot that should be reserved. The sync packet manager writes all placeholders to the future-most slot of the reservation table(s)5 so the start time must be at least SYNC_PKT_W1ND0W_SIZE slots in the future.
? InterlacePeriod - the period of the reservation in units of interlace slots.
? InterlaceBurstLength - the duty cycle of the reservation in units of interlace slots (less than or equal to InterlacePeriod).
? InterlaceNumSlots - the period (in units of interlace slots) at which the placeholder reservations should be written to the sync packet reservation table(s).
[0043] The sync packet manager processes all periodic reservations every slot. FIG. 8
shows the processing of the periodic reservations. Note that all placeholders are written to die future-most entries of the sync packet reservation tables to ensure that the slots won't get allocated to unicast A single reservation 60 can be sent to multiple tables 65, 70, and 75.
(0044] The sync packet manager maintains counters that track the period, burst length,
and num slots for each periodic reservation. Daring the first "burst length" slots of the period, the sync packet manager writes the placeholders every "num slots.** Two examples are shown in FIG. 9. The example shows two reservations flowing through the sync packet reservation table. Both periodic reservations have an interlace period of 8 slots and an interlace burst length of 6 slots. The periodic reservation on interlace 0 has InterlaceNumSlots set to 1, whereas the periodic reservation on interlace 2 has InterlaceNumSlots set to 2. Interlace 0 begins in the slot 0 (the current slot) and is a burst of 6 slots. Since the NumSlots is set to 1, the period for slot reservation is one, i.e., each consecutive slot Interlace 2 begins in the slot 0 and is a burst of 1 slot. Since the NumSlots is set to 2, the period for slot reservation is two, i.e., after every other slot
[0045] Two or more periodic reservations may overlap. If a reservation table entry
already has a placeholder reservation, which is recorded in the scheduler, then the sync packet manager preserves the one with the highest priority.
Sync packet writes
[0046] This section describes how the sync packet manager processes the
SendSyncPktsCmd- Each SendSyncPkts command contains one or more physical layer

WO 2005/029793 PCT/US2004/030487
'y 12
packets, which may be transmitted on one or more sectors (as specified by SectorMask).
FIG. 10 shows the sync packet reservation tables for three sectors and several
SendSynkPkts commands. A single command can be sent to multiple tables 85, 90, and
95.
[0047] When processing a SendSyncPktsCmd, the sync packet manager iterates over
the packets in the command, and performs the following for each packet
1. Validate the StartTime. The StartTime is to be within the current sync packet reservation table window of time. If StartTime is invalid, the sync packet manager issues a packet drop message for this packet for each sector present in SectorMask.
2. Find conflicting packets. At this stage, sync packet reservations only conflict if they have the same start time, hi other words, as long as the sync packet manager can write the packet to the reservation table, it doesn't care if multi-slot packets will overlap. If a sync packet already- occupies the reservation table entry, men the sync packet manager issues a packet drop message for me lower priority packet If the packets have the same priority men me sync packet manager drops me older packet If the reservation table entry contains a placeholder packet reservation, men me write will succeed only if the packet has a priority greater man or equal to the placeholder's priority.
3. Write the sync packet reservations). For each sector present in the
command's SectorMask, and provided the packet was not dropped on this
sector, write the packet information to the sector's reservation table entry that corresponds with the packet's start time.
Sync packet scheduling
[0048] The sync packet manager must look at each reservation table of a sector to see if
a sync packet is to be transmitted. As shown in FIG. 11, if the sync packet manager finds a packet reservation in the "next slof' entry of a reservation table in each sector, then it ensures that the sync packet can be transmitted without colliding with a packet that is already transmitting or colliding with a higher priority sync packet (or sync packet placeholder) in subsequent slots on the interlace. For example, on interlace 1, "next slot" 1 knows that it will not collide with another slot having higher priority until

WO 2005/029793 PCTAJS2004/030487
Y J3
many slots later. Therefore, all the slots that are not reserved may be used for
unicast/asynchronous packets.
|0049] More specifically, the sync packet manager performs the following two tests
when finding a sync packet reservation in the "next slof' reservation table entry:
? If there is already a packet transmitting on the "next slot" interlace, and this packet is due to repeat in the next slot, then the next-slot sync packet is dropped. There are two reasons why this may occur. Either the sync packet was written to the reservation table after a multi-slot unicast packet was already scheduled on the interlace (and the sync packet did not have a placeholder reservation), or an earlier higher priority multi-slot sync packet was given priority on the interlace.
? If the "next slot" sync packet will require more than one slot to transmit, then the sync packet manager looks ahead NumSlots-1 (where NumSlots is the. number of slots that the packet will require) on the interlace to make sure that the packet won't collide with any higher priority sync packet or sync packet placeholder reservation, as shown in FIG. 11.
[0050] If either test tails, then the sync packet manager issues a
CSDTDEFS SyncPktDroppedMsg for the "next slot" sync packet
Interaction with the unicast scheduler
[0051] hi one embodiment, the FL DSP gives priority to sync packets over
unicast/asynchronous packets, so sync packet scheduling always occurs before unicast scheduling. However, if a "next slot" sync packet reservation table entry is free, then the slot is made available to the unicast scheduler. Furthermore, the sync packet manager looks ahead on the "next slot" interlace to see how many subsequent slots can be made available for unicast. This count is called SyncMaxNumSlots, which is provided to the unicast scheduler every slot for each sector. If SyncMaxNumSlots for a sector is zero then the next slot is not available for unicast data; otherwise, the unicast scheduler may schedule a packet that does not exceed SyncMaxNumSlots. FIG. 12 depicts the computation of SyncMaxNumSlots for a particular sector.
[0052] Physical layer packets do not exceed 16 slots, so the sync packet manager
examines each reservation table entry on the interlace until encountering a sync packet reservation, as shown in FIG. 12, or SyncMaxNumSlots reaches 16.

WO 2005/029793

PCT/US2004/030487

43-
[0053] Note, if the "next slot" reservation table entry contains a placeholder reservation,
then SyncMaxNumSlots will normally be zero (i.e., not available for unicast data). The lack of an actual sync packet for the "next slot" will result in an idle slot transmission during the next slot. In many cases, this is desirable; however, the sync packet manager also supports a mode that allows unused "next slot" placeholder reservations to be released for unicast data. This mode may be useful for bursty logical synchronous channels (e.g., some types of broadcast channels), in which unicast data could be sent if the synchronous channel does not have data available. The synchronous packet manager supports this mode via a particular placeholder reservation priority level, as described below.
[0054] For the purpose of updating SyncMaxNumSlots, placeholder packet reservations
with a "next slot" 1 have a slightly different behavior. A "next slof' 1 placeholder reservation in table entry 1 will be considered available for unicast A priority 1 placeholder reservation in table entries greater than 1 (e.g., slots 5, 9, 13, etc. in FIG. 12) will be excluded from unicast data when updating SyncMaxNumSlots. In other words, a priority 1 placeholder in the next-slot position will be released for unicast, but a next-slot placeholder reservation with priority greater man 1 will force an idle slot transmission.
[0055] Note: SYNC_PKT_WINDOW_SIZE will be at least 16*4=64 slots since
SyncMaxNumSlots ranges from 1 to 16.
[0056] Those of skill in the art would understand that various steps or elements in the
embodiments may be altered or their order rearranged without varying from the invention that has been disclosed.
[0057] Those of skill in the art would understand that information and signals may be
represented using any of a variety of different technologies and techniques. For example, data, instructions, commands, information, signals, bits, symbols, and chips that may be referenced throughout the above description may be represented by voltages, currents, electromagnetic waves, magnetic fields or particles, optical fields or particles, or any combination thereof.
[0058] Those of skill would further appreciate that the various illustrative logical
blocks, modules, circuits, and algorithm steps described in connection with the embodiments disclosed herein may be implemented as electronic hardware, computer software, or combinations of both. To clearly illustrate this interchangeability of

WO 2005/029793 PCT/US2004/030487
hardware and software, various illustrative components, blocks, modules, circuits, and
steps have been described above generally in terms of their functionality. Whether such
functionality is implemented as hardware or software depends upon the particular
application and design constraints imposed on the overall system. Skilled artisans may
implement the described functionality in varying ways for each particular application,
but such implementation decisions should not be interpreted as causing a departure from the scope of the present invention
[0059] The various illustrative logical blocks, modules, and circuits described in
connection with the embodiments disclosed herein may be implemented or performed with a general purpose processor, a digital signal processor (DSP), an application specific integrated circuit (ASIC), a field programmable gate array (FPGA) or other programmable logic device, discrete gate or transistor logic, discrete hardware components, or any combination thereof designed to perform the functions described herein. A general purpose processor may be a microprocessor may be any conventional processor, controller, microcontroller, or state machine. A processor may also be implemented as a combination of computing devices, eg., a combination of a DSP and a microprocessor, a plurality of microprocessors, one or more microprocessors in conjunction with a DSP cove, or any other such configuration.
[0060] The steps of a method or algorithm described in connection with the
embodiments disclosed herein may be embodied directly in hardware, in a software
module executed by a processor, or in a combination of the two. A software module
may reside in RAM memory, flash memory, ROM memory, EPROM memory,
, EEPROM memory, registers, hard disk, a removable disk, a CD-ROM, or any other
form of storage medium known in the art. An exemplary storage medium is coupled to
the processor such the processor may read information from, and write information to,
the storage medium. In the alternative, the storage medium may be integral to the
processor. The processor and the storage medium may reside in an ASIC. The ASIC
may reside in a user terminal such as the MS or reside at the BS. In the alternative, the
processor and the storage medium may reside as discrete components in a user terminal.
[0061] The previous description of the disclosed embodiments is provided to enable any
person skilled in the art to make or use the present invention. Various modifications to
these embodiments will be readily apparent to those skilled in the art, and the generic

WO 2005/029793 PCT/US2004/030487
principles defined herein may be applied to other embodiments without departing from
the spirit or scope of the invention. Thus, the present invention is not intended to be
limited to the embodiments shown herein but is to be accorded the widest scope
consistent with the principles and novel features disclosed herein.
[0062] WHAT IS CLAIMED IS:

WO 2005/029793

17

PCTYUS2004/030487

CLAIMS
1. An apparatus for scheduling synchronous packet transmissions, comprising:
a synchronous packet manager for scheduling synchronous packet transmissions;
and
a synchronous packet reservation table for storing slot reservations for the synchronous packet transmissions.
2. The apparatus in claim 1, wherein the synchronous packet manager further comprises a packet scheduler for scheduling asynchronous packet transmissions in response to the synchronous packet reservation table.
3. The apparatus in claim 1, wherein the synchronous packet reservation table is further for storing status information, wherein me status irrformation comprises:
a priority of a synchronous packet reservation; and a number of slots over which the packet is transmitted.
4. The apparatus m claim 1, wherein the synchronous packet manager determines
reservation to be written in the synchronous packet reservation table.
5. The apparatus in claim 1, wherein the synchronous packet manager maintains a record of a period, burst length, and num slots for each of said reservation.
6. The apparatus in claim 2, wherein the synchronous packet manager is further adapted to:
validate a start time; find conflicting packets; and
write a synchronous packet reservation in the synchronous packet reservation table.
7. The apparatus in claim 2, wherein the asynchronous packet transmissions are
traffic data.

WO 2005/029793 PCT/US2004/030487
JS XT
8. The apparatus in claim 4, wherein the reservation comprises:
a priority for a placeholder entry;
a Start_Time that identifies a first slot to be reserved; an Interlace_Period that indicates a period of the reservation; an Interlace_Burst_Length that indicates a duty cycle of the reservation; and an Interlace_Num_Slots index that indicates a period at which the reservation is written.
9. The apparatus in claim 4, wherein the reservation is sent to multiple
synchronous packet reservation tables.
10. A method for scheduling synchronous packet transmissions, comprising:
scheduling synchronous packet transmissions; and
storing slot reservations for the synchronous packet transmissions.
11. The method in claim 10, wherein scheduling synchronous packet transmissions further comprises scheduling asynchronous packet transmissions in response to a synchronous packet reservation table.
12. The method in claim 10, wherein scheduling synchronous packet transmissions further comprises writing a reservation in the synchronous packet reservation table.
13. The method in claim 10, wherein scheduling synchronous packet transmissions further comprises maintaining a record of a period, burst length, and num-slots for each of said reservation.
14. The method in claim 11, wherein the asynchronous packet transmissions are traffic data.
15. The method in claim 12, wherein writing the reservation further comprises:
validating a start time;
finding conflicting packets; and

WO 2005/029793 PCT/US2004/030487
19
writing a synchronous packet reservation in the synchronous packet reservation table.
16. The method in claim 12, wherein writing the reservation is performed on
multiple synchronous packet reservation tables.
17. An apparatus for scheduling synchronous packet transmissions, comprising:
means for scheduling synchronous packet transmissions; and
means for storing slot reservations for the synchronous packet transmissions.
18. The apparatus in claim 17, wherein the means for scheduling synchronous packet transmissions further comprises a packet scheduler for scheduling asynchronous packet transmissions in response to a synchronous packet reservation table.
19. The apparatus in claim 17, wherein the status information comprises:
a priority of a synchronous packet reservation; and
a number of slots corresponding to a period of slots for the synchronous packet reservation over which the packet is transmitted.
20. The apparatus in claim 17, wherein the means for scheduling maintains a record of a period, burst length, and num-slots for each of said reservation.
21. The apparatus in claim 17, wherein the means for scheduling further determines a reservation to be written in the synchronous packet reservation table.
22. The apparatus in claim 17, wherein the means for scheduling synchronous packet transmissions is further adapted to:
validate a start time; find conflicting packets; and
write a synchronous packet reservation in the synchronous packet reservation table.
23. The apparatus in claim 20, wherein the reservation comprises:

WO 2005/029793

PCTYUS2004/030487

2o
a priority for a placeholder entry,
a Start-Time that identifies a first slot to be reserved;
an Interlace-Period that indicates a period of the reservation;
an Interlace_Burst_Length that indicates a duty cycle of the reservation; and
an lnterlace-Num-_Slots index that indicates a period at which the reservation is
written.
24. The apparatus in claim 20, wherein the reservation is sent to multiple synchronous packet reservation tables.
25. An apparatus for scheduling synchronous packet transmissions, comprising:
a memory storage unit; and
a processor coupled to the memory storage unit and adapted for: scheduling synchronous packet transmissions; and storing slot reservations for the synchronous packet transmissions.
26. An apparatus for scheduling synchronous packet transmissions and a method for scheduling synchronous packet transmissions,
27.
28. substantially as herein described, particularly with reference to, and as illustrated in the accompanying drawings.
Dated this 27th day of March 2006

RAJESHWARIH.
Of K & S PARTNERS
ATTORNEY FOR THE APPLICANTS

2-1
ABSTRACT
This disclosure provides a synchronous packet manager containing a data structure for scheduling future synchronous packet transmissions and arbitrating between synchronous and asynchronous packet transmissions. Slots required for transmitting a synchronous packet are reserved by marking the corresponding entries in a synchronous packet reservation table. Rather than writing packets to many different queues, the application software fills in a single reservation table per BTS sector.

Documents:

372-mum-2006-form-2.doc

372-mumnp-2006-abstract-1.jpg

372-mumnp-2006-abstract.doc

372-mumnp-2006-abstract.pdf

372-mumnp-2006-cancelled pages(23-10-2008).pdf

372-mumnp-2006-claims(granted)(23-10-2008).pdf

372-mumnp-2006-claims.pdf

372-mumnp-2006-correspondance-received.pdf

372-mumnp-2006-correspondence(23-10-2007).pdf

372-mumnp-2006-correspondence(ipo)-(22-12-2008).pdf

372-mumnp-2006-description (complete).pdf

372-mumnp-2006-drawing(23-10-2008).pdf

372-mumnp-2006-drawings.pdf

372-mumnp-2006-form 1(23-10-2008).pdf

372-mumnp-2006-form 18(15-09-2006).pdf

372-mumnp-2006-form 2(granted)-(23-10-2008).pdf

372-mumnp-2006-form 26(23-10-2008).pdf

372-mumnp-2006-form 3(03-04-2006).pdf

372-mumnp-2006-form 3(16-09-2006).pdf

372-mumnp-2006-form 3(23-10-2008).pdf

372-mumnp-2006-form 5(03-04-2006).pdf

372-mumnp-2006-form-1.pdf

372-mumnp-2006-form-2.pdf

372-mumnp-2006-form-3.pdf

372-mumnp-2006-form-5.pdf

372-mumnp-2006-form-pct-isa-210(23-10-2008).pdf

372-mumnp-2006-petition under rule 137(23-10-2008).pdf

abstract1.jpg

« Previous Patent

Next Patent »

Patent Number

226631

Indian Patent Application Number

372/MUMNP/2006

PG Journal Number

10/2009

Publication Date

06-Mar-2009

Grant Date

22-Dec-2008

Date of Filing

03-Apr-2006

Name of Patentee

QUALCOMM INCORPORATED

Applicant Address

5775 MOREHOUSE DRIVE, SAN DIEGO, CALIFORNIA 92121

Inventors:

#	Inventor's Name	Inventor's Address
1	CARLSON, NEIL, CHARLES	7382 LOS BRAZOS, SAN DIEGO,CA 92127
2	PANKAJ RAJESH K	7356 PARK VILLAGE ROAD, SAN DIEGO, CA 92129

PCT International Classification Number

H04L12/56

PCT International Application Number

PCT/US2004/030487

PCT International Filing date

2004-09-16

PCT Conventions:

#	PCT Application Number	Date of Convention	Priority Country
1	10/942,214	2004-09-15	U.S.A.
2	60/503,550	2003-09-16	U.S.A.