Rate shaping for wireless communication using token bucket that allows token debt

Technical Field

The request submitted by the 25 September 2009 entitled "Rate   Shaping   for Wireless   Communication   Using   Token   Debt   That   Token   Allows   Bucket" of the United States Provisional application Serial number entitled submitted 61/245933 and 22 June 2010 "Rate Shaping   for   Wireless   Communication   Using   Debt   Bucket   Allows Token   That   Token" of the United States application Serial number 12/820557 priority rights and interests, the its integrity by reference to the the present invention.

In general, the invention relates to a wireless communication network, and in particular, relates to using the modified token bucket algorithm trimming rate, which permits token bucket counter value to negative, thereby forming a token debt.

Background Art

Many wireless communication system is in the field of general have a part of modern life. The development of a plurality of different wireless communication protocol. For example, for long-term evolution of is (LTE) to support high data rate, low-latency, low and to the left and the operation cost of the wireless communication network of the seamless connection of the universal mobile telecommunications system (UMTS) a group of reinforced.

As another example, high-speed packet access (HSPA) is the expansion of band CDMA (WCDMA) protocol. The shared channel HSPA sent to the specific user of the transmitting communication data in the packet. HSPA includes the short transmission time interval (TTI), link adaptation, fast scheduling, fast retransmission and soft combined and used as the characteristic high modulation, so as to produce increased data rate, low latency time and increased system capacity.

In LTE and HSPA and in other wireless communication protocol, scheduling, dividing and link adaptation is classified as bandwidth management of the network management tasks generalized kind. High bandwidth management technology need to make the system capacity is the maximum, and maintaining the quality of services (QoS) measure of the data rate to be the maximum, therefore to the user providing optimal user experience.

Bandwidth an aspect of management referred to as rate shaping, the control data to the network through the network or in the speed or flow. Known rate shaping algorithm a token bucket algorithm is the so-called, in the 3GPP technical standards 23.107 B the appendix "  and architecture Quality   Service (QoS) concept   of" described in, and will be attached to this by reference to its integrity in herein. With reference to Figure 1 to describe the token bucket algorithm. In short, the algorithm with, for example, can be placed in order to by the service contract or other defined system corresponding to the data rate of the constant token rate r the assumption that is filled with a token bucket. In the barrel by the number of token kept token bucket (TBC) to said counter. Barrel has for example with bounded burst size b corresponding to the maximum capacity of the. Supplied to the rate shaping device to the wireless network packet is transmitted in line with the view that is, if there is at least in the barrel and with the packet size (for example, the unit is a byte) of the token of the same, the packet is transmitted together with the used for crossing over air interface of the transmission. If not, the packet delay to the barrel is filled with enough token. Therefore, if at any time-period T is not exceeded in b+rT of the data transmitted, then the data is in accordance with the. The resulting transmission data rate is on average R r token rate.

Figure 2 shows the operation of the token bucket algorithm. At the beginning, it is assumed that the barrel is full of, wherein TBC=b. Length l₁ of the packet is in the 1st (barrel of the token there is sufficient), and passes it on to the wireless network is used for transmission. In the next interval ΔT=t₂-t₁ filling of the barrel at a constant rate, until the length l₂ the 2nd packet arrival. 2nd line with the packet is also (it is less than in the barrel or the number of token l₂ <TBC), and the packet transmitted by the speed trimmer. When the barrel just contain enough token also transfer length l₃ 3rd of the packet-the barrel completely or nearly-depleted (TBC is in the 0 or close to 0), length l₃ the 3rd packet arrival. The barrel fully complemented with the token before again, length l₄ in time of packet 4th t₄ arrival. 4th packet by the rate shaping device delay to TBC>=l₄, in Figure 2 is in the "packet delay".

In one or more of the queue in the packet after the speed trimmer, until they are used for the subsequent scheduling of the transmission link. Solutions in the prior art, based on the scheduling algorithm the usability of these in the queue, that is, having gone through rate of the trimmer of selected packet to packet. Furthermore, there are the following system: in which a scheduler can not only decides to transfer the entire packet, but also can be divided prior to transmission (and connecting) packet.

Figure 3A shown rate shaping function 10, including the input buffer 12, speed trimmer 14, scheduling buffer 16 and the regulator 18. Figure 3B in a wireless network is shown in the representation of the transmission of the packet of the scheduling. Including any dividing and scheduling is limited to scheduling buffer 16 in the packet-i.e., after the speed trimmer 14 of those packet. Strict speed trimmer 14 limit and cause frequent small data transmission. Due to the scheduling of the granularity of the size, filling may occur, thus reducing network throughput. Therefore, frequent small data packet scheduling in a wireless communication system is not optimal.

Content of the invention

The herein described and claimed in accordance with one or more embodiments, the modified token bucket algorithm allow "borrowing" token, token foundation command TBC value of the debt or have a negative the possibility of the token bucket. In this revised in token bucket algorithm, as long as it is a positive TBC, together with the incoming packet is transmitted, even if the packet must be "borrowing" this is also true of some token, so as to drive to be the negative of the TBC. The subsequent TBC incoming packet to defer to obtain the positive value. In one embodiment, the modified token bucket algorithm is not applied to the separate speed trimmer, and the regulator which is applied to the one or a plurality of service queue queue size limiter of operation. Invention a scheduler and transfer less queue size limiter, greater for transmitting packets, the transmission of the frame so as to allow more effective packaging (reducing or eliminating the required to be filled), and allow the other service is scheduling, thus increase the system throughput.

One embodiment relates to a kind of control wireless communication traffic flow in the network method. The one or more data packet received in the service queue for transmission. The service queue queue size limiter using the modified token bucket rate shaping algorithm to monitor. The modified algorithm comprises in the barrel to maintain said the number of token token (TBC) of the counter; the TBC reduce the deployment is used for transmission of the packet size; in constant token rate and to increase the TBC. If the TBC as the positive, the report to the scheduler queue size limiter in the service queue of one or a plurality of packet size. If the TBC is negative, to the scheduler queue size limiter is the reported traffic queue is empty. The scheduler schedules the packet for transmission of the report.

Another embodiment relates to a wireless communication network in the projector can be operated in the rate shaping function. Rate shaping functions include operable to receive and store the transmitted across the air interface service queue of data packets. Rate shaping function also includes the operation in order to monitor the queue and the control data packet from the queue of the scheduler queue size limiter for the flow of, queue size limiter using the modified token bucket rate shaping algorithm. The modified algorithm comprises in the barrel to maintain said the number of token token (TBC) of the counter; the TBC reduce the deployment is used for transmission of the packet size; in constant token rate and to increase the TBC. If the TBC as the positive, the report to the scheduler queue size limiter in the service queue of one or a plurality of packet size. If the TBC is negative, to the scheduler queue size limiter is the reported traffic queue is empty. Rate shaping function also includes a scheduler, the scheduler is operable to respond to the queue size limiter scheduling data packet from the service queue used for crossing over air interface of the transmission.

Description of drawings

Figure 1 is the rate conventional command token bucket algorithm of the trimmer of the functional block diagram.

Figure 2 shows the speed trimmer in the operation of the token bucket algorithm conventional command the Figure.

Figure 3A by the rate is controlled by the trimmer and the scheduler function of the queue of the diagram.

Figure 3B is by fig. 3A speed trimmer and the scheduler in the wireless network under the control of the business graphics.

Figure 4 shows the speed trimmer with token debt in the modified token bucket algorithm of the operation of the graphic.

Figure 5A queue size limiter and is under the control of the queue of the scheduler function block diagram.

Figure 5B is by fig. 5A queue size limiter and the scheduler in the wireless network under the control of the business graphics.

Figure 6 is the token bucket conventional command algorithm and the modified token bucket algorithm, in the network protocol layer of the packet and overhead transmitted between the diagrams.

Figure 7 is a comparison of the trimmer commonly rule token bucket rate algorithm and the modified token bucket algorithm of the operation of the graphic.

Figure 8 is a kind of use, have token debt the modified token bucket algorithm of rate shaping of the downlink of the flow chart of the method.

Mode of execution

conventional command token bucket algorithm often adopt in the wireless communication network to realize the rate shaping device. As mentioned above, is the basis of this algorithm, injected at a constant rate (data volume) to allow said the assumption that data token. On the assumption that these tokens accumulated in the barrel, and the maximum allowable number of the token to the size defined by the barrel. Token by rate shaping device used for transmitting the data packet to consume, only when the barrel in the presence of at least the same number of packet size only token.

According to the embodiment of the invention, using the modified token bucket algorithm to realize the rate shaping, wherein the introduction of the concept of using the token. Under the revised in token bucket algorithm, allowing the packet to foundation command card debt, thereby generating counter token bucket negative command value (TBC). In the creation of the after token debt, speed trimmer will not transfer any other packet, resumption of positive value until the TBC. Therefore, the use of the next is allowed creates delay prior to transmission. The lower limit of the TBC is-c, the TBC is in range [-c, b] within. In some embodiments, can be also TBC can be used for radio channel to limit.

In one exemplary embodiment, the TBC r per unit time increase, until the bucket size b. In another embodiment, increased TBC Δt·r, wherein Δ t of the TBC is before the current time and the time difference between the updated once.

When the length is l_i section i when a packet arrives, the algorithm checks whether value TBC is equal to or greater than zero. If that is the case, the service is in line with, and reduce TBC l_i (even TBC<l_i). If the TBC is less than zero, then grouping delay to the TBC is equal to or greater than zero.

This revised the operation of the token bucket algorithm as shown in Figure 4. Has length l₁, l₂, l₃ and l₄ the four packet arrival, wherein the front of the two is in line with, and thus is immediately processing, as token bucket conventional command as in the algorithm. 3rd in the modified token bucket algorithm is in line with the under, but it makes the TBC to less than zero. When the grouping of 4th t4 arrive, TBC <0, so packet delay to the TBC is greater than zero, this in Figure 4 by the "packet delay" in time.

In one embodiment, as shown in Figure 5A illustrated, rate shaping function 20 in the queue size limiter 26, rather than the Figure 3A independent of the speed of the shown in the trimmer 14 to realize the modified token bucket algorithm. In this embodiment, there is no separate input buffer 12 or the independent speed trimmer 14, rather, they exist in a single service queue 22. In other embodiments, the regulator 24 from the plurality of queues to the business of the rate shaping, every one of them can have independently queue size limiter, shared or public queue size limiter. Service queue 22 to accept all incoming packet, and also serve the outgoing link. Scheduler 24 no service queue 22 in direct knowledge of the quantity of the data, but from the queue size limiter 26 get this information. When TBC≥ 0 each time, the modified token bucket algorithm the actual queue size report (or in one embodiment, the upper limit of c). Otherwise, queue size limiter 26 to the scheduler 24 the reported traffic queue 22 is empty, and therefore prevent any transmission.

The field of the technical staff is easy to know, rate shaping function 20 scheduler 24 and queue size limiter 26 can be through a dedicated hardware, with the appropriate firmware programmable logic, operation in a controller or processor (such as a digital signal processor, or DSP) software to realize or a combination of these. Service queue 22 is realized or can be used as a hardware register in the memory. The control queue 22 or scheduler 24 or queue size limiter 26 firmware or software can be stored in the non-temporary computer readable medium, such as solid-state memory (for example flash RAM, DRAM, such as ROM), magnetic or optical medium, etc. the upper. Firmware or software can be accessed directly by the controller or processor, such as a memory controller or via disk drive controller to the controller, such as, from or cross wired or wireless network to access remote computer-readable medium.

Figure 5B graphics shown rate shaping function 20 of the trimmer rate than the prior art (e.g. FIG 3A) more efficiently utilize the wireless network resource. TBC value shown in the upper Figure (dashed-line) and the service queue of the report 22 large and small (solid-line). Note, the TBC nonnegative when only when, actual service queue just report 22 size; otherwise, it reports an air service queue 22. The lower part of the regulator showing the pattern in order to be used for the transmitted across the air interface transmission service. Note, with diagram 3B compared with the pattern, with the modified token by the token bucket algorithm trimming function of the rate of 20 transfer less transmission, every one of them is relatively large, and therefore require little or no filling. By allowing this, in part, the transmission resource allocation to other queue or the user, to increase the system throughput.

Furthermore, chart 5A illustrated embodiment allows more simple to realize, because it requires only a single service queue 22. The queue management (AQM) such as activities such as with the other control algorithm is particularly desirable. By contrast, Figure 3A shown in the solutions of the prior art require two independent AQM mechanism, a control rate trimmer 14 upstream queue 12, and a control regulator 18 upstream queue 16.

Under the revised in token bucket algorithm, a maximum number of the token by the parameter b bucketTime[s] to determine, the b=r ·bucketTime. Parameters corresponding to the possible bucketTime will be preserved without causing any debt in the burst of time of the token consumption. In other words, by adopting the modified token bucket algorithm trimming device allows to include a rate of the long when the R at a constant rate in the steady state transmission of the same number of data the data burst.

Figure 6 show queue size limiter 26 based on the modified token bucket algorithm method of modifying a rate of 100. At the beginning, token bucket counter (TBC) is set to signify the token can be preserved the greatest number of b (frame 102). TBC in a constant incremental r token rate (frame 104). The TBC [...] of discrete frame 104 ; however, those of skill in the art will know, TBC is incremented at a constant rate, and with the Figure 14 to a flow chart of the control process. In one embodiment, for example, incremental TBC each TTI. Single service queue 22 receiving a user service of one or a plurality of data packet (frame 106). If the TBC is greater than or equal to zero (frame 108), the packet is considered to be in line with, and the size of the queue is transmitted to the scheduler 24, is used for scheduling the transmission of the network (frame 112). TBC degressive packet size (frame 114), even if it is reduced to the TBC that the "borrowed" negative value of the token. If the received one or more service packet (frame 106) and the TBC is negative (frame 108), queue size limiter 26 to the scheduler 24 the reported traffic queue 22 is empty, and thus no packet is scheduled for transmission.

The possibility of using token with the modified token bucket algorithm unnecessary packet in order to prevent the small size from a network layer is transmitted to another network layer. Scheduling many small packet instead of the packet is of a small number of large, such as the physical downlink control channel (PDCCH) and the physical uplink control channel (PUCCH) inefficient use of resources.

Figure 7 shows a token bucket algorithm using conventional command (upper) and allows the use of the token token bucket algorithm conventional command the speed of the (lower) trimming the effect of the inter-layer data transfer. Borrowing capacity of the token at the same time allowing a lot of packets transmitted to the lower layer. This has many advantages. First of all, the major source of performance degradation is mainly scheduling overhead; as shown in Figure 6 is shown at the lower part of, when a number of packets is included in the transmission, to reduce the percentage of the as a transmission scheduling overhead. Secondly, through the will be sent to or from a plurality of grouping UE collected in a TTI, release other TTI (or time slot, or other defined transmission duration) in order to carry other UE sent to or from the service.

Figure 8 shows a token bucket algorithm conventional command with the modified token bucket algorithm of the difference between the value of TBC, at the beginning, when the barrel is full (TBC=b), algorithm similar operation. However, when the token count depletion attack, conventional algorithm (dashed-line) for scheduling a plurality of short data transmission is transmitted to the UE. This is necessary, because (length of l) each data packet must wait for collecting enough token count. By contrast, in the modified token bucket algorithm in (solid-line), queue size limiter 26 can use the token, thereby allowing the regulator 24 for scheduling the 2l the half number of the transmission. The whole transmission in both cases is completed, that is, at the same time, two kinds of solutions implementation of the anticipated speed trim, but with different resource cost to implement.

The key terms are defined as follows, and the designated use herein has the meaning:

Speed reinforcing: rate enhancement is used for rate shaping and rate control (rate   policing) of the integrated term.

Rate control: in accordance with the service distribution from the discarded packet of the traffic flow of the process referred to as rate control or traffic control. The reasons for the application rate control can be to protect the network from bombing attack, realizing hierarchical reservation and block-cheating, for example, VoIP CODEC rate-upgrading the user beyond the network has authorized outside the VoIP CODEC rate.

Rate shaping: delay in the traffic flow in the packet in order to make it a certain defined service distribution referred to as rate shaping or business process of trimming. Application rate shaping of the reasons for entering the network can be smooth in time when in service. The reasons for the application rate control is also effective here. Rate shaping can realize improvement of to the scheduler.

Trim rate: generating for a token rate with the rate of the rate of use of trimmer. Should on average finishing rate is a token rate.

Service control: refer to rate control.

Service trim: refer to rate shaping.

Token: as other certain aspects of some aspect of the expression of the. Here, the token is the minimum information units corresponding to the size of virtual symbol. Token in a token rate r in the barrel.

Token rate: for the token filling rate of the system.

The invention of course can be realized in not deviate from the essence of the present invention through the characteristics of the different specific herein to carry out the other way. The embodiment of the invention in all its aspects is to be considered illustrative rather than restrictive, and falls into the attached claims and equivalent within the scope of the meaning of all of the alteration should be contained therein.