Data output dispatching device and method

Patent metadata

Field	Value
Publication number	US-10025733-B2
Application number	US-201615265450-A
Country	US
Kind code	B2
Filing date	Sep 14, 2016
Priority date	Oct 14, 2015
Publication date	Jul 17, 2018
Grant date	Jul 17, 2018

Abstract

The present invention discloses a data output dispatching device and method capable of reducing the probability of packets from the same queue being transmitted sequentially. An embodiment of the method comprises the following steps: providing a plurality of buffers capable of storing the data of Q queues respectively while each queue is associated with a weighting and the sum Ws of all the weightings is between 2(M−1) and 2M and not greater than a maximum sum in which Q is an integer greater than 1, M is a positive integer and N is an integer not less than M; providing a binary bit reverse count value not greater than 2N; and assigning a token to one of the Q queues for data output according to the reverse count value.

First claim

What is claimed is:

1. A data output dispatching device configured to reduce a probability that packets from a same queue are transmitted sequentially, the data output dispatching device comprising:
Q buffers configured to store data of Q queues respectively while the Q queues are associated with Q weightings respectively and each of the Q weightings is not greater than a maximum weighting which is equal to or less than 2 N , in which the Q is an integer greater than one and the N is a positive integer;
a weighting allocator configured to allocate the Q weightings according to a binary bit reverse sequence so as to distribute a K th weighting among the Q weightings and make the K th weighting be logically associated with T queue point(s) of 2 N queue points, in which the K is a positive integer not greater than the Q, the T is an integer not less than zero and not greater than the maximum weighting, the value of the K th weighting is the T, and an order of the 2 N queue points is in incremental order; and
a polling circuit configured to poll the Q buffers according to at least a part of the order of the 2 N queue points, and when the polling circuit polls the Q buffers during a current polling cycle, the polling circuit allows a buffer of the Q buffers in association with the K th weighting to obtain a token for data output if the current polling cycle is logically associated with one of the T queue point(s) of the 2 N queue points.

2. The data output dispatching device of claim 1 , wherein the weighting allocator logically associates integer(s), which is/are less than the K th weighting and not less than zero, with corresponding number(s) of a K th binary bit reverse sequence to thereby distribute the K th weighting.

3. The data output dispatching device of claim 2 , wherein when the weighting allocator distributes a (K+1) th weighting among the Q weightings, the weighting allocator logically associates integer(s), which is/are less than the (K+1) th weighting and not less than zero, with corresponding number(s) of a (K+1) th binary bit reverse sequence which is a shift version of the K th binary bit reverse sequence.

4. The data output dispatching device of claim 1 , wherein the weighting allocator includes:
a first level allocator configured to process each of the Q weightings with a first level allocation process so as to logically associate the K th weighting with R region(s) of 2 X regions, in which the 2 X regions are logically associated with the 2 N queue points, the 2 X regions are in association with 2 X round weightings respectively while each of the 2 X round weightings is not greater than the T, the sum of R round weighting(s) associated with the R region(s) is equal to the T, the X is a positive integer less than the N, the R is equal to 2 X if the T is not less than 2 X , and the R is equal to the T if the T is less than 2 X ; and
a second level allocator configured to process each of the 2 X round weightings derived from the Q weightings with a second level allocation process so as to logically associate an S th round weighting among the R round weighting(s) with Y queue point(s) of 2 (N−X) queue points, in which the Y queue point(s) pertain(s) to the T queue point(s), the S is an integer not less than zero and not greater than the R, and the Y is equal to the S th round weighting.

5. The data output dispatching device of claim 4 , wherein the difference between any two of the 2 X round weightings is not greater than one.

6. The data output dispatching device of claim 4 , wherein the first level allocator includes:
a first level shift register including 2 X shift register units configured to store and shift a first level binary bit reverse sequence; and
Q round weighting output units coupled with the first level shift register and configured to respectively output Q round weightings of the 2 X round weightings according to the first level binary bit reverse sequence and the Q weightings during a token output cycle.

7. The data output dispatching device of claim 6 , wherein the second level allocator includes:
a second level shift register including 2 (N−X) shift register units configured to store and shift a second level binary bit reverse sequence; and
Q token-indication output units configured to generate Q token indications according to the second level binary bit reverse sequence and the Q round weightings during the token output cycle, in which a first token indication of the Q token indications is used for notifying the polling circuit whether a first buffer of the Q buffers in association with the first token indication obtains the token for data output.

8. The data output dispatching device of claim 7 , wherein when the second level shift register shifts the second level binary bit reverse sequence for 2 (N−X) times or stops shifting the second level binary bit reverse sequence, the first level shift register shifts the first level binary bit reverse sequence.

9. A data output dispatching method configured to reduce a probability that packets from a same queue are transmitted sequentially, the data output dispatching method comprising the following steps:
providing a plurality of buffers configured to store data of Q queues respectively while the Q queues are associated with Q weightings respectively and a sum Ws of the Q weightings is between 2 (M−1) and 2 M and not greater than a maximum sum which is not greater 2 N , in which the Q is an integer greater than one, the M is a positive integer, and the N is an integer not less than the M;
generating a binary bit reverse count value not greater than 2 N ; and
assigning a token to one of the Q queues for data output according to the binary bit reverse count value.

10. The data output dispatching method of claim 9 , wherein a K th queue and a (K+1) th queue among the Q queues are respectively associated with a K th weighting and a (K+1) th weighting, the K th weighting and the (K+1) th weighting define a (K+1) th region, and the step of assigning the token includes: when the binary bit reverse count value falls within the (K+1) th region, assigning the token to the (K+1) th queue of the Q queues.

11. The data output dispatching method of claim 10 , wherein when the K is equal to one, a number zero and the K th weighting define a first region, and the step of assigning the token includes: when the binary bit reverse count value falls within the first region, assigning the token to the K th queue of the Q queues.

12. The data output dispatching method of claim 9 , wherein the step of generating the binary bit reverse count value includes:
storing a counting value according to an addition value and forward storage order, and outputting the counting value;
adding up the counting value and a predetermined number to generate the addition value; and
storing the addition value according to reverse storage order, and outputting the addition value as the binary bit reverse count value.

13. The data output dispatching method of claim 12 , wherein the predetermined number is a first shift number to make the binary bit reverse count value not greater than 2 M , or the predetermined number is one.

14. The data output dispatching method of claim 13 , wherein when the predetermined number is one, the sum Ws is constant and equal to the maximum sum.

15. The data output dispatching method of claim 9 , wherein the step of generating the binary bit reverse count value includes:
storing a counting value according to an addition value and forward storage order, and outputting the counting value;
adding up the count

Assignees

• Realtek Semiconductor Corp

Inventors

• Zhu Jian-Yin

Classifications

• G06F13/1673

  using buffers · CPC title

• G06F13/37

  using a physical-position-dependent priority, e.g. daisy chain, round robin or token passing · CPC title

• G06F5/015

  having at least two separately controlled shifting levels, e.g. using shifting matrices (G06F5/012 takes precedence) · CPC title

• G06F13/22 Primary

  using successive scanning, e.g. polling (G06F13/24 takes precedence) · CPC title

• H04L47/50 Primary

  Queue scheduling · CPC title