Method and apparatus for a traffic shaper

This invention relates to communications, and more particularly to shaping the traffic flow of information packets.

In high speed communications, and particularly a synchronous transfer mode (ATM) in the telecommunications industry, available bandwidth is at a premium. Thus, there is a continuing need to provide more and more information over a given channel. One of the issues is how the resources on a particular channel are allocated. Often different types of information have different rates and different priorities but are on the same channel. These different rates must all be serviced but may have different priorities and different rates. One technique is simply to take turns but that may be inconsistent with the data rate. Another technique is to service the higher priority. This may result in starvation for the lower priority. This may be an undesirable result, especially if there is a commitment to provide the lower priority.

Accordingly, there is a need to provide multiple queues on a single channel with service that is consistent with the priorities of the queues and not starve the queues with lower priorities.

Shown in FIG. 1 is block diagram of a circuit for controlling multiple queues according to an embodiment of the invention; and

Shown in FIG. 2 is a flow diagram describing a method for using the circuit of FIG. 1 .

Skilled artisans appreciate that elements in the figures are illustrated for simplicity and clarity and have not necessarily been drawn to scale. For example, the dimensions of some of the elements in the figures may be exaggerated relative to other elements to help improve the understanding of the embodiments of the present invention.

Described herein is a technique that provides a way to transfer packets of data from multiple queues onto a single channel. In one embodiment each has associated with it a data rate for servicing a packet within the queue. The data rate assigned is relative to the priority of that particular queue. The time for completing the transfer of the packet is calculated and normalized. Thus, each queue has an integer that, relative to the other numbers, represents the time for an access. Each queue has associated with it a counter and that is loaded with its corresponding integer. The counter values are compared, and the queue corresponding to the lowest counter value has a packet coupled to the channel. The counter of the selected queue is incremented by its integer. The next queue that is selected is the one that corresponds to the counter with the lowest count value after the counter that corresponds to the previously selected queue has been updated.

Shown in FIG. 1 is a processing system 10 comprising queue 12 , a queue 14 , and a queue 16 , a multiplexer (mux) 18 , a controller 20 , a counter 22 , a counter 24 , and a counter 26 . Queues 12 are groups of information that may be FIFoS useful in ATM systems. Also there may additional queues coupled to mix 18 . Eight total queues may be a particular effective number, but only three are fully described for ease of understanding. Queues 12 , 14 , and 16 store packets of information that may be cells of information that may be transmitted as a unit. An example of a cell is cell 28 at the front of queue 28 . There are additional cells in queue 12 and more may be loaded. Queues 12 - 16 each have an output coupled to mix 18 . Mix 18 couples one of the outputs of queues 12 - 16 to an output channel as selected by controller 20 . Controller 20 is coupled to counters 22 , 24 , and 26 for receiving a current count of each counter and for updating each counter 22 - 24 . In this processing system 10 functions as a traffic shaper.

Each queue has assigned to it an integer number that is representative of the bit rate assigned to it. The bit rate assigned to it a given queue may be based on any criteria that a user would wish. Each queue may be correlated to a particular commitment to provide a particular bit rate for some particular purpose. The sum of such commitments should not exceed the maximum bit rate of the output channel otherwise not all of the commitments could be met. The bit rates of all the queues are summed and the percentage of that sum for each queue is calculated. The inverse of the percentage for each is then a measure of the relative time for sending a packet if it were sent at the assigned bit rate. This number then is a measure of the relative frequency that the queue should be serviced. A lower number should be serviced more frequently than a higher number. These inverses of the percentage can be further multiplied by a number to obtain an integer or the numbers may be approximated.

These assigned integers are loaded into controller 20 and into the counters to which they correspond. In this case counter 22 corresponds to queue 12 , counter 24 corresponds to queue 14 , and counter 26 corresponds to queue 16 . With each of counters 22 - 26 loaded with the integer number associated with its corresponding queue 12 - 16 , controller compares these counter values and determines which is the lowest. The queue 12 - 16 that has the lowest value in its corresponding counter 22 - 26 has its output, which is the cell that is next for the queue, selected by controller 20 . This is shown as block 30 in FIG. 2 . Controller 20 provides the required signal information to mux 18 and to the selected queue 12 - 16 so that the next cell of the selected queue 12 - 16 is output to mux 18 and mux 18 couples the output of the selected queue 12 - 16 to the output channel. This is shown as block 32 in FIG. 2 .

After the queue selection, the counter 22 - 26 that corresponds to the selected queue 12 - 16 is incremented with its corresponding integer. In effect, each counter thus has a corresponding integer, the integer of its corresponding queue. This incrementing counter by its corresponding integer is shown as block 34 in FIG. 2 . Thus, prior to the next selection of a queue 12 - 16 , the previously selected queue has a corresponding counter with a higher value than it did at the time of the prior selection. Controller 20 then performs another comparison with the updated count and makes a new selection. After that selection the counter is updated for that corresponding counter and then a new comparison is continued. This process continues in this manner. Eventually, as the process continues, a counter of counters 22 - 26 for a selected queue will be in an overflow situation.

When this happens, which is shown as blocks 36 and 38 in FIG. 2 , all of the counters are reduced by the amount in the selected counter, which is the counter in the overflow situation. The amount of the integer which corresponds to the selected counter is carried over into the selected counter, and the other counters have their count reduced by the amount of the selected counter prior to the overflow situation arising. The selected counter of counters 22 - 26 always has the lowest count because that is the basis for it being selected. After the subtraction of the count of the selected counter of counters 22 - 26 from the non-selected counters of counters 22 - 26 and the selected counter of counters 22 - 26 has been loaded with the amount of its corresponding integer, the process continues. Thus, after each incrementing of the selected counter, there is a determination if that counter is in an overflow situation. Thus the traffic generated by queues 12 - 16 provide traffic that is shaped to provide a balanced result that is consistent with the bit rates and does not create starving for the queues that may have low bit rates.

For an example of the process assume that queue 12 has an assigned rate of 50 k bits/sec, queue 14 has an assigned rate of 40 k bits/sec, and queue 16 has an assigned rate of 10 k bits/sec. In such a case the total bits/sec is 100K bits/sec with queue 12 having 50%, queue 14 having 40%, and queue 16 having 10%. Thus, the inverse of these percentages are 2 for queue 12 , 2.5 for queue 14 , and 10 for queue 16 . A convenient multiplier of 2 for these results in 4 for queue 12 , 5 for queue 14 , and 20 for queue 16 . Thus queue 12 would be chosen first and counter 22 would be incremented by 4. The table below shows how this would progress.

This shows the progression of the incrementing of the respective counters as the selected queues provide the cells of data. As seen, the result after the transmission of 10 cells is that five cells from queue 12 , four cells from queue 14 and one from queue 16 were selected. This is the same as the percentage calculated of 50%, 40%, and 10%, respectively. In the case of a tie, as in the case for cells 8 and 9, the selected cell is a matter of design choice. In this case the tie was broken by the queue that had the lowest number.

This selection process has the advantage of spreading out the transmissions from the various queues while maintaining the relative data rates, but not starving any of the recipients of the queues. Thus, a recipient expecting the relatively slow rate would periodically receive a cell and not go long periods without any cells then suddenly receive many packets in a row to get caught up.

In the foregoing specification, the invention has been described with reference to specific embodiments. However, one of ordinary skill in the art appreciates that various modifications and changes can be made without departing from the scope of the present invention as set forth in the claims below. Accordingly, the specification and figures are to be regarded in an illustrative rather than a restrictive sense, and all such modifications are intended to be included within the scope of present invention.

Benefits, other advantages, and solutions to problems have been described above with regard to specific embodiments. However, the benefits, advantages, solutions to problems, and any element(s) that may cause any benefit, advantage, or solution to occur or become more pronounced are not to be construed as a critical, required, or essential feature or element of any or all the claims. As used herein, the terms “comprises,” “comprising,” or any other variation thereof, are intended to cover a non-exclusive inclusion, such that a process, method, article, or apparatus that comprises a list of elements does not include only those elements but may include other elements not expressly listed or inherent to such process, method, article, or apparatus.