Wireless network scheduling method and apparatus based on waiting time and queue occupancy

The present invention relates generally to the field of telecommunications, and more specifically to schedulers used to control access to limited resources.

This application relates to US Patent Application Agent Reference No. Hamilton6-2-4-3, entitled "High-Throughput Scheduler with Guaranteed Fairness for Wireless Networks and Other Applications," which was filed at the same time, and this disclosure is described herein by reference. It is incorporated in the book.

Many telecommunications applications use schedulers to resolve conflicts between competing tasks for limited resources. For example, such a scheduler is commonly used in network processors to schedule multiple traffic flows for transmission over a particular transmission bandwidth.

Network processors typically control the flow of data between physical transmission media, such as the physical layer portion of a network, and a router's switch fabric or other types of switches. An important feature of a network processor is the cells, packets, or other data blocks associated with multiple traffic flows for transmission from the physical transmission medium of the network to the switch fabric and vice versa. There is scheduling. The network processor scheduler performs this function.

An efficient and flexible scheduler architecture capable of supporting multiple scheduling algorithms was filed on November 26, 2003 under the inventor name Asif Q. Khan et al., "Processor with Scheduler Architecture Supporting Multiple". It is disclosed in US Patent Application No. 10 / 722,933, entitled "Distinct Scheduling Algorithms", which is by the same applicant and is incorporated herein by reference.

In many cases, a given scheduling algorithm implemented in a network processor or other processing device should be concise and fair. It is important that the processing equipment hardware be concise, especially in high data rate environments, as there is usually not much time to make a given scheduling decision. Also, a good scheduler must be fair. For example, the scheduler can allocate bandwidth by allowing higher priority users to acquire more bandwidth than lower priority users, depending on user weights.

An example of a concise and fair scheduling algorithm is the weighted round robin (WRR) scheduling algorithm. For a given telecommunications application, suppose there are several users competing for one resource that can handle one block of data in each time slot. The scheduler must determine which users can send one block of data to the server in each time slot. Each user has a weight indicating its priority. Users with higher weights have higher priority. Under ideal conditions, the service a user receives is proportional to the weight of the user. The WRR scheduler serves the user in a round-robin fashion in proportion to the user's weight.

The problem with WRR is that it has a long burst property. This is clearly undesirable in communication systems, as long bursts can overflow the buffer of the user's communication device. Such burstability is becoming more and more problematic in practical applications where the total number of users can be in the hundreds or more.

Alternative scheduling algorithms are known that overcome the bursting problem of WRR. Examples of this are WFQ (Weighted Fair Queuing) and WF.²There is Q (Worst-case Fair Weighted Fair Queueing). Unfortunately, these alternative algorithms are usually much more complex than WRRs and can therefore be difficult to implement in network processors and other processing equipment operating in high data rate environments.

"Frame Mapping" filed on July 30, 2004 under the inventor name Jinhui Li et al., By the same applicant and incorporated herein by reference. U.S. Patent Application No. 10 / 903,954, entitled "Scheduler," discloses, in an exemplary embodiment, a frame mapping scheduler that is as concise and fair as WRR, but without the burstiness issues commonly associated with WRR. doing. More specifically, the frame mapping scheduler of the exemplary embodiment described herein comprises a scheduling circuit that utilizes a weight table and a mapping table. The weight table contains multiple entries, each of which identifies a particular one of the transmission elements. The mapping table contains at least one entry that identifies the mapping between a particular time slot in a frame and an entry in the weight table. The scheduling circuit accesses the corresponding mapping table entry and uses the resulting values to access the wait table to determine the particular transmission element scheduled during a given time slot. The entries in the mapping table can be pre-determined according to the golden ratio policy or other types of policies.

However, for schedulers that utilize the golden ratio policy or, more generally, any policy that needs to store the mapping table, the mapping table can be large and therefore require a significant amount of memory. Generally, the memory of such a mapping table is preferably placed "on-chip", that is, on the same integrated circuit as the scheduler, in order to reduce access time. For example, such an arrangement is useful in network processing applications where data blocks need to be processed in substantially real time.

The United States named "Frame Mapping Scheduler with Compressed Mapping Table" filed on November 29, 2004 under the inventor name Jinhui Li et al., By the same applicant and incorporated herein by reference. Patent Application No. 10 / 998,686 compresses the mapping table to reduce the amount of memory required to store the table, thereby providing an integrated circuit or other network processor with a frame mapping scheduler or the like. Discloses a technology that facilitates mounting in the device.

The known arrangements described above can be used in a wide variety of telecommunications applications, including applications that require a wireless network. However, scheduling in the context of a wireless network can be particularly difficult as the channel capacity of the wireless network generally changes over time and is difficult to predict. In such situations, it is important that the wireless network scheduler not only be fair, but also provide sufficient throughput.

Examples of scheduling algorithms used in wireless network situations include the WRR scheduling algorithm described above and the corresponding unweighted round robin (RR), maximum carrier-to-interference ratio (Max C / I), and Proportionally Fairness. There are (PF) and Modified Largest Weighted Delay First (M-LWDF).

The drawback of the RR scheduling algorithm is that it does not consider the state of the channel. Instead, the RR scheduling algorithm simply assigns one raw user at a time, the first user to the first time slot, the second user to the second time slot, and so on for each channel capacity. Schedule regardless. This approach is fair because for a given set of N time slots, each of the N users is given exactly one chance of being serviced. However, the throughput of the RR algorithm is inferior because the RR algorithm does not check the channel capacity before making a scheduling decision. Similarly, the WRR scheduling algorithm does not consider channel capacity in scheduling decisions.

The Max C / I scheduling algorithm selects the user with the best channel capacity for a given time slot. This approach can achieve maximum total throughput, but its fairness is very poor. For example, if a given mobile user's wireless link is always weak, that user may not be scheduled.

The PF scheduling algorithm is r_iIs the channel capacity of user i, R_iIs the average rate received by user i, the maximum r_i/ R_iSelect a user with. This algorithm is R_iTo update. Therefore, mobile users with weak wireless links will have the opportunity to be scheduled. For more details on the PF scheduling algorithm, see, for example, A. Jalali et al., "Data throughput of CDMA-HDR a high efficiency high data rate personal communication wireless system", Proc.IEEE VTC 2000, pp. 1854-1858, May 2000. Can be found inside. The fairness of the PF scheduling algorithm is better than the Max C / I scheduling algorithm, but not as good as the RR or WRR scheduling algorithm. Neither the PF scheduling algorithm can guarantee fairness either.

The M-LWDF scheduling algorithm gives higher priority to users with longer latency. However, like the PF scheduling algorithm described above, it does not guarantee fairness.

As a result, Max C / I, PF, and M-LWDF scheduling algorithms offer better throughput than RR and WRR scheduling algorithms in radio situations at the expense of fairness.

The US Patent Application Agent Reference No. Hamilton6-2-4-3 described above provides an improved scheduling algorithm that provides a better balance between throughput and fairness, especially in wireless network applications. In an exemplary embodiment, this algorithm is referred to as a wireless RR (WiRR) scheduling algorithm. In this embodiment, all transmission elements are initially specified to be eligible for service in a given frame, but once a particular transmission element is fed into a time slot in a given frame, that The transmission element is considered ineligible for service in the next time slot of that frame. This process is repeated in additional frames, with each new frame all transmission elements initially designated as eligible to transmit one or more blocks of data to that frame.<patcit num="1"><text>US patent application agent reference number Hamilton6-2-4-3</text></patcit><patcit num="2"><text>U.S. Patent Application No. 10 / 722,933</text></patcit><patcit num="3"><text>U.S. Patent Application No. 10 / 903,954</text></patcit><patcit num="4"><text>US Patent Application No. 10 / 998,686</text></patcit><nplcit num="1"><text>A.Jalali et al., "Data throughput of CDMA-HDR a high efficiency high data rate personal communication wireless system", Proc.IEEE VTC 2000, pp. 1854 ~ 1858, May 2000</text></nplcit><nplcit num="2"><text>M. Andrews et al., "Providing Quality of Service over a Shared Wireless Link", IEEE Communication Magazine, Vol.39, pp. 150-154, February 2001</text></nplcit>

<p num="0021"> Despite the considerable advances brought about by the WiRR scheduling algorithm and its variants, there is still a need for further advances, especially in wireless network applications. For example, the M-LWDF algorithm described above generally has limited tolerances, but can have very large queue lengths, so this queue can be used in network processor integrated circuits or other types of hardware. Can be difficult to implement. A modified algorithm with associated queues that can be run using less memory or other hardware resources would be desired.</p>

<p num="0022"> In one or more exemplary embodiments, the invention can be implemented using shorter queues than conventional scheduling algorithms such as the M-LWDF scheduling algorithm described above, and so on. It provides a wireless scheduling algorithm that reduces the amount of memory and other hardware resources.</p><p num="0023"> According to one aspect of the invention, the scheduler is adapted to schedule packets or other data blocks for transmission from multiple transmission elements in a communication system during a time slot. The scheduler determines a comparative capacitance criterion for each element of the transmission element, where each of the comparative capacitance criteria is compared by a combination of latency and occupancy for the corresponding one of the transmission elements. The scheduler selects one or more of the transmission elements to schedule in a given one of the time slots based on comparative capacity criteria. This process may be repeated for one or more additional time slots. The time slot can be a frame time slot in this communication system, but it does not have to be.</p><p num="0024"> In the first exemplary embodiment, the comparative capacitance reference is that the value of i = 1 to N, where N is the number of transmission elements, α._iAnd β_iIs a constant for the transmission element i, W_iIs the latency of a particular data block of transmission element i, O_iIs the occupancy of transmission element i, and r_iWhen is the channel capacitance of transmission element i, (α_iW_i+ β_iO_i) r_iIs sought after. Transmission element i can contain a queue, W_iIs the wait time for the first packet in the queue i column.</p><p num="0025"> In the second exemplary embodiment, the comparative capacitance reference is that the value of i = 1 to N, where N is the number of transmission elements, α._iAnd β_iIs a constant for the transmission element i, Δ_iIs the latency of the transmission element i, O_iIs the occupancy of transmission element i, and r_iWhen is the channel capacitance of transmission element i, (α_iΔ_i+ β_i) O_ir_iIs sought after. Quantity Δ_iIs T_cIs at the moment, T_lastIs the last time the transmission element i is scheduled, T_c-T_lastCan be determined. Scheduling algorithms are particularly suitable for use in wireless network applications, but can also be used in many other applications.</p><p num="0026"> According to another aspect of the invention, two or more transmission elements may be selected to schedule during a given time slot based on the transmission elements being selected having approximately the same comparative capacitance criteria. .. In such a "tie" situation, all of the two or more selected transmission elements are in a given time slot by assigning different subsets of the available set of codes to different elements of the selected transmission element. Can be scheduled. For example, this time slot can include an HSDPA time slot, each with a set of available codes. In such an arrangement, multiple users can be scheduled during a given one of the HSDPA time slots by assigning different codes to the users.</p><p num="0027"> The scheduler of the exemplary embodiment can take advantage of a wide variety of different arrangements of scheduling circuits to implement integrated circuits of communication systems or other processing devices on network processors.</p><p num="0028"> Advantageously, the scheduling algorithm described in conjunction with the exemplary embodiment overcomes the problem of too long a queue length associated with traditional M-LWDF scheduling algorithms, thereby resulting in a more hardware efficient implementation. .. In addition, exemplary embodiments reduce complexity by reducing time stamping requirements and processing ties more efficiently, for example by accommodating multiple users in a single time slot. be able to.</p>

The present invention is described herein in the context of exemplary wireless networks and other types of communication systems. An exemplary system includes each scheduler configured in a particular way to illustrate the techniques of the invention. However, it should be understood that the present invention is more widely applicable to schedulers in any communication system where it is desired to provide improved performance compared to the conventional scheduling algorithms described above.

FIG. 1 shows a schematic diagram of a communication system 100 according to an exemplary embodiment of the present invention. System 100 includes a transmitter 104 and a scheduler 102 coupled to a channel status element 106. In this embodiment, the scheduler is linked to a transmission element containing queues 110-1, 110-2, ... 110-N, respectively, for each of the N users. In this example, the N users are mobile users of the wireless network of system 100, and the devices 112-1, 112-2, ... Associated with 112-N. Transmitter 104 can include, for example, at least a portion of a base station or access point in a wireless network.

The wireless network is configured to communicate packets or other arrays of data between the transmitter 104 and the mobile user's device 112. The data in all such sequences shall be included in the term "data block" as used herein. It should be understood that the present invention does not require any particular size or composition of data blocks. For simplicity and clarity, the figure shows only downlink communication between the transmitter 104 and the mobile user's device 112, but similar techniques are used for other types of transmission. Please understand that there are cases.

System 100 of this embodiment has one queue 110 for each mobile user 112, but other types of queue arrays can be used. It is assumed that the downlink transmission takes place in the time slot. The time slot can be a frame time slot, but the present invention does not require that the time slot be a frame time slot. During each time slot, the scheduler 102 serves one or more users. It is assumed that the scheduler of this embodiment is aware of the radio channel capacity associated with each mobile user. This recognition can be provided to the scheduler by channel status element 106 or by using other techniques. As mentioned earlier, channel capacity associated with mobile users typically changes over time and is difficult to predict. As described in more detail below, along with FIGS. 3-5, the scheduler makes scheduling decisions based on actually measured channel conditions and other parameters. For a given time slot, the scheduler selects one or more of the user's queue 110, each scheduled to carry packets during that time slot. A given packet is transmitted via transmitter 104 to the corresponding one of the mobile user's device 112.

The system 100 of FIG. 1 can be implemented, for example, as a conventional general purpose mobile communication system (UMTS) or wideband code division multiplexing access (WCDMA) wireless mobile phone communication system in other cases. In such an implementation, system 100', as shown in FIG. 2, comprises a radio network controller (RNC) 120 connected to base stations 122, 124, and 126 as shown. Base stations 122, 124, and 126 are referred to as node B elements according to known UMTS and WCDMA terminology. These elements communicate with the mobile user's device 112, which in the UMTS and WCDMA context is called the User Device (UE) element. The system scheduler 102 and channel status element 106 of Figure 1 can be incorporated into RNC120 or replicated to node B elements 122, 124, and 126, respectively. For example, if a UMTS or WCDMA system 100'is configured to provide High Speed Downlink Packet Access (HSDPA) functionality, a scheduler is typically placed on each node B element to enable fast scheduling. Will be done.

The HSDPA feature described above utilizes a time slot called the Transmission Time Interval (TTI) to serve one or more users within each TTI. HSDPA functionality can be provided in Frequency Division Duplex (FDD) mode or Time Division Duplex (TDD) mode. In FDD mode, a given TTI has a duration of 2 milliseconds (ms), and in TDD mode, a given TTI can be 5 ms or 10 ms. These and other TTIs shall be included in the term "time slot" as used herein.

In the UMTS or WCDMA context, the communication system channel typically used by HSDPA to send data from a given node B to the UE is called the High Speed Downlink Shared Channel (HS-DSCH).

For simplicity and clarity, the scheduler 102 described below assumes that it serves only one user per time slot, but the technique described is simple, as described in conjunction with Figure 5. It should be understood that it can be extended to HSDPA and other deployments where multiple users can be scheduled in a single time slot.

Note that the specific placement of the elements shown in Figures 1 and 2 is merely a descriptive example. More specifically, as described above, the present invention can be implemented in any type of wireless network or other communication system and is not limited to any particular communication application.

The scheduler 102 is configured to schedule packets or other data blocks for transmission from the user's queue 110 during the time slot. The scheduler of the exemplary embodiment implements a scheduling algorithm that considers both latency and queue occupancy at the same time, thereby advantageously reducing the size of the queue and thus memory and other hardware resources. Can be saved.

In general, the scheduler 102 determines a comparative capacity criterion for each of the N queues 110 in FIG. 1, and each of these comparative capacity criteria waits and occupies a corresponding one of the queues. It is compared by the combination with. The scheduler then selects one or more queues to schedule in a given one of the time slots based on comparative capacity criteria. These operations are typically repeated for additional time slots. In an alternative embodiment, transmission elements other than queues can be used. The transmission element may also be referred to herein as a "user" in the description of the following exemplary scheduling algorithms. Therefore, the following actions performed on the user can be considered to be performed on the associated transmission element and vice versa.

The scheduling algorithm of the exemplary embodiment is similar to the conventional M-LWDF scheduling algorithm described above in some respects. The M-LWDF scheduling algorithm is explained in detail by M. Andrews et al., "Providing Quality of Service over a Shared Wireless Link", IEEE Communication Magazine, Vol. 39, pp. 150-154, February 2001. It is incorporated herein by reference.

In each time slot, the M-LWDF scheduling algorithm is α_iIs the bandwidth allocation constant for user i, W_iIs the wait time for the first packet in column i of queue i, and r_iMaximum (α) when is the channel capacity associated with user i_iW_ir_i) Is selected. Traditional M-LWDF scheduling algorithms are known to be "throughput optimization", which means that bounded or finite queue lengths can be guaranteed. This throughput optimization characteristic is W_iThe queue occupancy is O_iIt is kept even if it is replaced with. As mentioned earlier, the problem with M-LWDF is that the queue length is often bounded but very long, which consumes excessive memory and other hardware resources in a given implementation. Is that there is a possibility of doing.

The present invention of the exemplary embodiment overcomes this problem of conventional M-LWDF by simultaneously considering both latency and queue occupancy when making scheduling decisions. As mentioned above, this can reduce the size of the queue and thus save memory and other hardware resources.

Next, a more detailed example of the improved scheduling algorithm will be described with reference to the flow diagrams of FIGS. 3 and 4. The scheduling algorithms in these examples have about the same fairness and throughput performance as traditional M-LWDF scheduling algorithms, but with reduced queue lengths.

In the examples described in connection with FIGS. 3 and 4, the time slot is assumed to be a frame time slot without limitation. However, as shown earlier, the time slot does not have to be part of the frame, but rather can be a completely separate and independent time slot. In the scheduling algorithm of the exemplary embodiment, the scheduling decisions are made independently for each of the time slots, and the time slots do not require any type of framing.

First, see FIG. 3 to show the behavior of the first version of the improved scheduling algorithm performed by scheduler 102 in system 100 of FIG. At step 300, the scheduling process for the new frame begins.

In step 302, for the time slot available next to the frame, the scheduler 102 sets the value of i = 1 to N and α_iAnd β_iIs a constant for queue i, W_iIs the wait time for the first packet in the queue i column, O_iIs the occupancy of queue i, and r_iMaximum (α) from N users when is the channel capacity of queue i_iW_i+ β_iO_i) r_iSelect a specific person who has.

In these and other examples described herein, it is always assumed that all N users are unprocessed for the sake of simplicity and clarity. A user is considered unprocessed if he has at least one packet to transmit. With reference to the figure in FIG. 1, it can be understood that each of the illustrated users, namely users 1, 2, 3, and N, is unprocessed because each has at least one packet in its associated queue.

The unprocessed user assumptions described above, and the other assumptions made here, need not be applied to other embodiments. For example, in an alternative embodiment, as will be appreciated by those skilled in the art, a user who is not unprocessed in the current time slot can be excluded from consideration of the scheduling process for that time slot. However, it should be understood that a user who is not unprocessed in the current time slot may be unprocessed in the next time slot, from the consideration of scheduling such user in the current time slot. Exclusion should not be construed as excluding from consideration of the rest of the frame.

In step 304, the selected user is serviced in the available time slot. The selected user is "serviced" by scheduling packets from the corresponding user's queue 110 for transmission to the time slots available in this example.

In step 306, it is determined if more time slots are available in the current frame. If not available, the process goes back to step 300 and starts a new frame. However, if there are additional time slots available in the current frame, the process returns to step 302 to schedule one or more users during the additional time slots in the current frame.

As shown above, the scheduling decision in step 302 is made independently for each time slot, and the time slot need not consist of frames. Thus, steps 300 and 306 can be omitted in alternative embodiments, or frames can be considered to have a frame size = 1 where each frame contains a single time slot. ..

In the given case of step 302, the scheduler 102 causes two or more users to have the same maximum (α)._iW_i+ β_iO_i) r_iWhen determined to have, the tie can be randomly divided or a user with a smaller subscript i can be selected. Another technique for handling such ties, suitable for use in the above HSDPA situations or other situations where multiple users can be serviced in a given time slot, is described in conjunction with Figure 5. Thus, servicing multiple users at the same time in a given time slot.

Constant β in the scheduling algorithm of Figure 3_iIt can be seen that when is set to zero, the algorithm in Figure 3 changes to the traditional M-LWDF algorithm. As mentioned earlier, the algorithm in Figure 3 offers about the same fairness and throughput performance as that of the traditional M-LWDF algorithm, but also favorably reduces the required queue length. The reduced queue length can be expressed as a reduction in the average queue length, that is, the average length required for N queues 110 in the system of FIG. The algorithm in Figure 3 is also throughput optimized.

Quantity (α) in the above-described embodiment_iW_i+ β_iO_i) r_iIs an example of what is more commonly referred to herein as a comparative capacity reference. Those skilled in the art will appreciate that other types of comparative capacity criteria can be utilized that incorporate comparisons based on both latency and occupancy. Another example will be described with reference to the flow diagram of FIG.

Α used in a given implementation_iAnd β_iSpecific values of may vary depending on the scheduling needs of the implementation, and suitable values can be determined in a simple way. As an example, both can be set to 1 or 0.5, but of course other values can be used. One set of the same α_iAnd β_iThe value of can be used for all values of i, or at least some of the values of i can be set to different values.

As mentioned above, in the algorithm of Figure 3, W_iIs the wait time for the first packet in the queue i column. The first packet in the column is the time point T_inSuppose it was enqueued in. Given current time point T_cIn, the packet wait time is T_c-T_inObtained by Therefore, the algorithm in Figure 3 generally requires that all packets be time stamped upon arrival in their respective queues, with a wait time of W._iTo be able to decide. The algorithm in Figure 4 is a simplified version of the algorithm in Figure 3 that avoids the need to time stamp each packet.

The algorithm in Figure 4 is T_lastIs the last time the queue i is scheduled, the quantity Δ_i= T_c-T_lastTo determine. Quantity Δ_iRepresents the latency of queue i, but does not require time stamping of all arriving packets. Instead, a single timestamp needs to be associated with each of the queues. The simplified algorithm in Figure 4 is the product Δ_iO_iUsing the algorithm W in Figure 3_iReplace with. Therefore, in each time slot the scheduler is the largest (α)_iΔ_i+ β_i) O_ir_iSelect a user with. Only the queue is time stamped, not every packet, which significantly reduces complexity.

Next, with reference to FIG. 4, the operation of a simplified version of the improved scheduling algorithm executed by the scheduler 102 of the system 100 of FIG. 1 is shown. At step 400, the scheduling process for the new frame begins.

In step 402, the scheduler 102 sets the value of i = 1 to N for the time slot available next to the frame, and α_iAnd β_iIs a constant for queue i, Δ_iWaiting time of queue i defined above, O_iIs the occupancy of queue i, and r_iMaximum (α) from N users when is the channel capacity of queue i_iΔ_i+ β_i) O_ir_iSelect a specific person who has.

In step 404, the selected user is serviced in the available time slot. Again, the selected user is "serviced" by scheduling packets from the corresponding user's queue 110 for transmission to the time slots available in this example.

In step 406, it is determined if more time slots are available in the current frame. If not available, the process goes back to step 400 and starts a new frame. However, if there are additional time slots available in the current frame, the process returns to step 402 to schedule one or more users during the additional time slots in the current frame.

As shown in FIG. 3, the scheduling decision of step 402 is made independently for each time slot, and the time slot does not have to consist of frames. Thus, steps 400 and 406 can be omitted in alternative embodiments, or frames can be considered to have a frame size = 1 where each frame contains a single time slot. .. The tie that occurs in the given case of step 402 can also be processed using the techniques described above.

An alternative version of the scheduling algorithm in Figure 4 is the constant β_iCan be generated by setting to zero. In this variant, the comparative capacitance criterion used to make the scheduling decision in step 402 is (α)._iΔ_iO_ir_i). This is yet another example of a comparative capacity criterion that is compared by both latency and occupancy.

As mentioned above, the tie can be dealt with in some embodiments by scheduling multiple users in the same time slot. For example, if in the given case of step 302 or 402 it is determined that two or more users have approximately the same comparative capacity criteria, then two or more users can be selected for scheduling and selected above. All of the users can schedule during a given time slot by assigning different subsets of the available set of code to different users of the selected user. The set of codes available can include a set of HSDPA codes.

Figure 5 shows an example of scheduling multiple users in each of several different HSDPA time slots. In this example, the set of codes available includes a set of 10 codes representing codes 1 to 10. Each time slot contains a TTI in FDD mode with a duration of 2 ms. The different shades in the figure represent different users. By assigning one or more codes to each user, up to 10 different users can be scheduled for a given one of the time slots.

Note that the particular number of codes used in this example is for illustration purposes only and it is possible to use more or less code in other embodiments. As mentioned above, HSDPA typically uses the HS-DSCH channel to send data from a given node B to the mobile user. You can assign up to 15 codes to this channel. Therefore, the 10 codes shown in Figure 5 represent just one example of a set of codes that can be used.

In the first time slot shown in the figure, three users are scheduled, one assigned four codes and the other two assigned three codes each. In the second and third time slots, only one user is scheduled and each time slot is assigned all 10 codes. In the fourth time slot, two users are scheduled, each assigned five of the ten available codes. The remaining time slots shown in the figure are similarly scheduled.

As mentioned above, scheduling multiple users in a single time slot can be applied in situations other than HSDPA, and when performed with time slots and other arrangements of code. There is also.

In a typical wireless network, mobile users often deviate from or join the network or a particular cell or other receivable range of the network. The scheduler 102 can be configured to deal with users who fall off or join a given frame or otherwise. For out-of-users, the scheduler may simply indicate these users as ineligible or otherwise exclude them from the consideration of the scheduling process. For new users joining, the scheduler may, for example, wait until a new frame begins, or set the eligibility status of the new user relatively (proportionally), randomly, or using other techniques. it can.

Advantageously, the scheduling algorithms described in conjunction with the exemplary embodiments of FIGS. 3-5 overcome the problem of too long queue lengths associated with traditional M-LWDF scheduling algorithms, thereby reducing hardware efficiency. Brings a better implementation. In addition, exemplary embodiments reduce complexity, for example by reducing time stamping requirements and by accommodating multiple users in a single time slot to handle ties more efficiently. can do.

The scheduler 102 can be implemented, at least in part, in the form of an integrated circuit, as described in more detail below . Such an integrated circuit can include a network processor or other type of processor, or a processor mounted on a given communication system element, eg, a base station or access unit associated with transmitter 104 of the system of FIG. A point, or the RNC or node B element of the system in Figure 2.

The scheduler 102 can be, for example, the type of frame mapping scheduler described in US Patent Application Nos. 10 / 903,954 and 10 / 998,686 described above. By using these techniques, the amount of memory required to store the mapping table for the golden ratio policy or other policies that need to store the mapping table can be substantially reduced. it can.

The scheduling techniques of the present invention, on top of or without alternatives, are flexible scheduler architectures capable of supporting multiple scheduling algorithms, such as those disclosed in US Patent Application No. 10 / 722,933 above. Please note that it can be used in combination with.

As shown above, the scheduling algorithms described herein can be implemented in many other types of communication systems. Next, another example system will be described with reference to FIGS. 6 to 8. In these figures, the scheduling algorithm is implemented in the network processor scheduler. Such a network processor can be used in systems including the wireless networks shown in FIGS. 1 and 2, but can also be used in other types of systems such as communication system 600 shown in FIG.

System 600 includes a network processor 602 with internal memory 604. Network processor 602 is connected to external memory 606 as shown and is configured to provide an interface for communicating packets or other data arrays between network 608 and switch fabric 610. As mentioned above, all such data sequences shall be included in the term "data block" as used herein. The network 608 can be a wireless network that corresponds to one part of the wireless network of the systems in Figures 1 and 2, and the network processor 602 and switch fabric 610 can be the base station, network controller of such system. , Or can be implemented in other elements.

The network processor 602 and its associated external memory 606 can be implemented, for example, as one or more integrated circuits embedded in a line or port card of a router, switch, or other system element.

FIG. 7 shows an example of a partial line card embodiment of the system 600 of FIG. In this embodiment, the system includes a line card 700 having at least one integrated circuit 702 incorporated therein. The integrated circuit 702 includes a network processor 602 with internal memory 604. Network processor 602 interacts with external memory 606 on line card 700. The external memory 606 can serve, for example, as an external static random access memory (SRAM) or dynamic random access memory (DRAM) for the integrated circuit 702 of the network processor. Such memory can be configured in a conventional manner and can be used to store scheduling information such as the comparison capacity criteria described above or related comparison elements. Also, to incorporate a suitable host processor on the line card 700 to program and otherwise control the operation of the integrated circuits of one or more network processors on the line card 700. Can be used.

The parts of the communication system shown in Figures 6 and 7 have been considerably simplified for clarity. However, the system can include routers, switches, or other elements that include multiple line cards, such as the line card shown in Figure 7, and each line card has multiple integrated circuits. Please understand that it can be included. Similar embodiments can be implemented in the form of port cards. However, the present invention does not require a card-based implementation of routers, switches, or other elements.

It should also be understood that the specific placement of the elements shown in Figures 6 and 7 is merely an explanatory example. More specifically, as described above, the present invention can be implemented in any type of processor or processing device of other communication systems and is not limited to processing applications of any particular network infrastructure.

As used herein, the term "processor" is, but is not limited to, generally used as a microprocessor, a central processing unit (CPU), a digital signal processor (DSP), an application specific integrated circuit (ASIC), and the like. Alternatively, it can be implemented using elements such as elements associated with other types of data processing units, as well as some of such elements and combinations of such elements.

Also, as shown in Figures 6 and 7, the system 600 and network processor 602 are one of the types commonly found in traditional implementations of such systems and network processors, in addition to or in place of the elements shown in detail. It can contain other elements, including one or more elements. For example, a network processor includes a sorter, queuing and dispatch logic, one or more memory controllers, an interface circuit for connecting the network processor to network 608, a switch fabric 610, and a host. It can include a processor or other external device, as well as other conventional elements not specified in the figure. These and other conventional elements are known to those of skill in the art and are not described in detail herein.

The functionality of the network processor 602 described herein can be implemented at least partially in the form of software program code. For example, the elements involved in performing network processor scheduling operations utilize instructionally programmable elements or other software that can be provided to the network processor via an external host processor or other suitable mechanism. Can be implemented at least partially. For example, information demonstrating the characteristics of a particular scheduling algorithm, or associated traffic shaping information, can be provided to a network processor by the associated host processor or other suitable mechanism.

FIG. 8 shows a more detailed view of the network processor 602 of an exemplary embodiment of the invention. The network processor 602 of this embodiment includes a scheduler 800, a transmit queue 802, a traffic shaper 804, a wait table 810, and a mapping table 812. During operation, the scheduler 800 schedules the transmit queue 802 and associated data blocks to be transmitted by one or more unspecified transmission media. Scheduling wait table 810 and mapping table with or without traffic shaping information from traffic shaper 804 when scheduling data blocks associated with transmit queue 802 for transmission. Use 812.

As indicated above, the network processor 602 may include, for example, additional elements of the type described in the US patent application above, or conventional types of additional elements known to those skilled in the art. , As described elsewhere, are not further described herein.

The wait table 810 and the mapping table 812 can be at least partially stored in the internal memory 604 of the network processor 602, and on top of or at least in part of the network processor 602. It can be stored in the external memory 606. When stored using internal memory, at least a portion of such memory may be internal to the scheduler 800 or other scheduling circuitry.

In addition to table elements 810 and 812, the scheduler 800 is a static or dynamic table of some additional time slot table or of the type described in the US patent application above, or of the type known in conventional practice. Can include or be associated with other types of table elements suitable for use in scheduling based on.

The transmit queue 802 can be considered to contain a plurality of transmission elements. For example, a transmit queue can include a plurality of transmit queues and associated control logic, each of which corresponds to a transmit element. However, as used herein, the term "transmission element" is more general to include the source of one or more blocks of data, or other elements, that can be scheduled to network processor 602 for transmission. Please note that it should be interpreted as

Packets or other data blocks, not explicitly shown in the figure, can be enqueued to the transmission elements of transmit queue 802 from the data path of the associated network processor. This happens as packet enqueue messages and associated data blocks are received from such data paths. Similarly, at the time of transmission, a packet or other data block can be dequeued from a transmission element to the data path, for example, a packet dequeue message and associated data blocks are sent to the data path.

The traffic shaper 804, in one example, establishes one or more traffic shaping requirements in a known way to carry a block of data from the transmission elements of the transmit queue 802, otherwise conventional traffic. -It can be implemented as a shaping engine. The traffic shaper 804 can receive information about the status of the queue and the scheduler from the send queue 802 via the scheduler 800. Traffic shapers prioritize queue transmission intervals to establish a grade of service (CoS) or other desired level of service for one or more of the transmission elements or their corresponding network connections. Can generate traffic shaping information such as.

As mentioned above, in the context of network processors, transmission elements, i.e. scheduled entities, can include queues. However, the present invention can be used to schedule any type of element in which a data block is transmitted, and more generally any type of element that can be scheduled in the processing equipment of a communication system. Such an element shall be included in the general term "transmission element" used in the present specification, and may be referred to here as a "user" as described above.

The scheduler 800 of the embodiment of FIG. 8 is configured to implement a scheduling algorithm such as the scheduling algorithms of FIGS. 3 and 4 described above. The schedulers 102 and 800 are descriptive examples of what is more commonly referred to herein as a "scheduling circuit." In other embodiments, the scheduling circuit is one or more tables on which the scheduling techniques described herein can be implemented, or other arrangements consisting of one or more of hardware, software, and firmware. Can be included. Thus, although shown separately from the scheduler 800 in the figure, the wait table 810 and mapping table 812 or any suitable portion thereof can be at least partially incorporated into the scheduling circuit or associated memory in accordance with the present invention.

The schedulers 102 and 800 may utilize any arrangement of logic gates, processing elements, or other circuit configurations that can provide the type of scheduling functionality described herein. Scheduling circuits according to the invention can therefore include conventional general purpose network processor circuits that can be adapted under software control to provide at least some of the scheduling functionality according to the invention. The arrangement of many such circuits is not described in detail herein because it is readily apparent to those skilled in the art.

As mentioned above, a given embodiment of the invention can be implemented as one or more integrated circuits. In such an arrangement, a plurality of identical dies are typically formed in a repeating pattern on the surface of the wafer. Each die can include the equipment described herein and can also include other structures or circuits. The individual dies are cut or die-cut from the wafer and packaged as an integrated circuit. Those skilled in the art will understand how wafers are cut and dies are packaged to manufacture integrated circuits. The integrated circuit manufactured in this way is considered to be a part of the present invention.

Furthermore, it should be emphasized that the embodiments of the present invention described above are merely explanatory. For example, the exemplary embodiment of FIG. 8 utilizes a scheduler separated from the associated table, but these elements or parts thereof can be incorporated into the scheduling circuit according to the present invention. Similarly, the transmit queue 802 and the traffic shaper 804 are depicted separately from the scheduler 800 in connection with the embodiment of FIG. 8, but the related functionality is at least partially implemented in the scheduling circuit according to the present invention. can do. Other embodiments can use different types or arrangements of processing elements to implement the above-mentioned functionality. For example, a table can be implemented in internal memory, external memory, or a combination of internal and external memory. In the case of internal memory, at least a portion of such memory may be inside the scheduling circuit. The particular process stage of the scheduling algorithm can be modified in alternative embodiments to accommodate a wide variety of different scheduling methods. These and many other alternative embodiments within the scope of the appended claims will be apparent to those skilled in the art.

<figref num="1">FIG. 5 is a simplified block diagram of a communication system including a wireless network according to an exemplary embodiment of the present invention.</figref><figref num="2">It is a figure which shows at least one possible implementation of the communication system of FIG.</figref><figref num="3">It is a flow chart of the improved radio scheduling algorithm implemented in the scheduler of the communication system of FIG. 1 of one Embodiment of this invention.</figref><figref num="4">It is a flow chart which shows the alternative version of the scheduling algorithm of FIG.</figref><figref num="5">It is a table which shows an example of the operation of the radio scheduling algorithm of FIGS. 3 and 4 in the application of HSDPA.</figref><figref num="6">FIG. 5 illustrates another possible implementation of at least some of the communication systems of FIG.</figref><figref num="7">FIG. 6 is a block diagram of a network processor in the system of FIG. 6 shown as an integrated circuit mounted on a router or switch line card.</figref><figref num="8">It is a more detailed view of the network processor of the system of FIG. 6 configured according to the technique of this invention.</figref>