High speed weighted fair queuing system for ATM switches
View Patent ↗Methods and apparatus for an ATM network for implementing a fair servicing of all connections during a back-logged condition through the use of a weighted fair queuing technique. The system is particularly suited for systems where the packets/cells are of a fixed size. Although some important approximations are made in the proposed implementation, all of the properties of an ideal weighted fair queuing algorithm are preserved. The sorting methods and apparatus are advantageous in that it is possible to maintain appropriate servicing of connections without sorting all of the individual connections. This may be accomplished by pre-sorting each of the individual virtual circuit connections into a finite number of predetermined bins according to a weight associated with the connection. Thereafter, only the bins need be sorted without having to sort each of the individual connections. Further aspects of the invention include storing the bins in a matrix with an offset value dependent upon the current potential of the bin. In this manner, the overall sorting required to determine the next connection to service is substantially reduced. Accordingly, the invention is suitable for implementations having transmission speeds of multiple gigabits-per-second.
1. A method of transmitting packets comprising:
sorting packets associated with a plurality of virtual circuits into a plurality of bins using a two-dimensional matrix, where each of the plurality of bins corresponds to one of a plurality of weights and all of the sorted packets in each of the bins have the same weight, the weight of each of the sorted packets dependent upon the weights associated with the plurality of virtual circuits;
sorting the bins based on connection potentials associated with the plurality of bins to determine which packets to transmit, wherein at least one of the connection potentials is defined as an amount of service that an associated bin has received normalized to the weight of the associated bin, where the amount of service is a variable according to the backlogged status of a circuit and each of the connection potentials are adjusted based on the weight of the associated bin; and
servicing all non-empty virtual circuits within a first of the plurality of bins according to the connection potentials prior to sorting the plurality of bins.
2. The method of claim 1 , further comprising:
storing the connection potential for each of the bins which contain at least one backlogged virtual circuit.
3. The method of claim 1 , further comprising:
initializing a newly backlogged virtual circuit to a connection potential matching connection potentials of other virtual circuits having the same weight.
4. The method of claim 1 , further comprising:
servicing all non-empty virtual circuits within a second of the plurality of bins when the connection potential of the second bin is the same as the connection potential of the first bin.
5. The method of claim 1 , further comprising:
adjusting the connection potential of the first bin by an amount proportional to an inverse of its weight.
6. The method of claim 1 , wherein each of the connection potentials indicates an amount of service received by one or more of the packets in the associated bin.
7. The method of claim 1 , wherein each of the bins is associated with two or more of the virtual circuits.
8. A packet network comprising:
a plurality of packet switches interconnected via a plurality of connections, each connection having one or more virtual circuits, each packet switch having a processor and a memory configured to sort incoming packets associated with the plurality of virtual circuits into a plurality of virtual circuit queues and for sorting the plurality of virtual circuit queues into a plurality of bins using a two-dimensional matrix enterable by row, where each of the plurality of bins corresponds to one of a plurality of weights and all of the sorted packets in each of the bins have the same weight, the weight of each of the sorted packets dependent upon the weights associated with the plurality of virtual circuits, where bins are organized according to their associated connection potentials, wherein
at least one of the connection potentials is defined as an amount of service that an associated bin has received normalized to the weight of the associated bin, wherein
the amount of service is a variable according to the backlogged status of a circuit and each of the connection potentials are adjusted based on the weight of the associated bin, and wherein
packets are output from each of the packet switches in accordance with connection potentials associated with the bins.
9. The packet network of claim 8 , wherein the processor and memory are configured to service all virtual circuits associated with a single bin having the lowest connection potential.
10. The packet network of claim 9 , wherein the processor and memory are configured to sort the bins to determine a new first bin with a connection potential lower than all other bins after at least one packet is sent from each virtual circuit within a first bin which currently has a connection potential lower than or equal to all other bins.
11. The packet network of claim 9 , wherein the processor and memory are configured to adjust the connection potential of the single bin by an amount proportional to an inverse of its weight.
12. The packet network of claim 8 , wherein each of the connection potentials indicates an amount of service received by one or more of the packets in the associated bin.
13. The packet network of claim 8 , wherein each of the bins is associated with two or more of the virtual circuits.
14. A packet switch, comprising:
a processor and a memory configured to sort incoming packets associated with a plurality of virtual circuits into a plurality of virtual circuit queues and for sorting the plurality of virtual circuit queues into a plurality of bins using a two-dimensional matrix enterable by row, where each of the plurality of bins corresponds to one of a plurality of weights and all of the sorted packets in each of the bins have the same weight, the weight of each of the sorted packets dependent upon the weights associated with the plurality of virtual circuits, where bins are organized according to their associated connection potentials, wherein
at least one of the connection potentials is defined as an amount of service that an associated bin has received normalized to the weight of a the associated bin, where the amount of service is a variable according to the backlogged status of a circuit and each of the connection potentials are adjusted based on the weight of the associated bin, and wherein
packets are output from each of the packet switches in accordance with connection potentials associated with the bins.
15. The packet switch of claim 14 , wherein each of the connection potentials indicates an amount of service received by one or more of the packets in the associated bin.
16. The packet switch of claim 14 , wherein each of the bins is associated with two or more of the virtual circuits.
17. The packet switch of claim 14 , wherein the processor and memory are configured to service all virtual circuits associated with a single bin having the lowest connection potential.
18. The packet switch of claim 17 , wherein the processor and memory are configured to adjust the connection potential of the single bin by an amount proportional to an inverse of its weight.