Data switching arbitration arrangements
View Patent ↗There is disclosed a masking unit (REQMSK) for use in a data packet switching system. The data switching system being of the type having a memoryless cross-back switch (SM) providing cyclic connections under the control of a switch arbiter (SCARB) between ingress routers (IR 0 , IR 1 , IR 2 and IR 3 ) and egress routers (ER 0 , ER 1 , ER 2 and ER 3 ). Each of the ingress routers (IR 0 –IR 3 ) is provided with incoming packet buffering on a virtual output queue basis (VOQ 0.0 , VOQ 0.1 , VOQ 0.2 , and VOQ 0.3 for ingress router IR 0 ). Each virtual output queue also produces a connection request signal REQ 0.0 to REQ 3.3 when the corresponding queue has a data packet in it. The masking unit REQMSK is arranged to randomly mask out correlated connection requests.
1. A masking unit for use in a data packet switching system of the type having a memoryless cross-bar switch providing cyclic connections between ingress routers and egress routers, the ingress routers providing incoming packet buffering on a virtual output queue and being arranged to generate switch connection requests when a virtual output queue contains a data packet, characterised in that the masking unit is arranged to receive all of the switch connection requests and to randomly mask connection requests and wherein the masking unit includes a comparator for each virtual output queue, the masking unit is arranged to receive with each request an associated weight value, and to feed the weight values to the corresponding comparators together with a stream of randomly generated values, the comparators being arranged to produce respective random bit streams whose proportion of 1's to 0's is determined by the corresponding weight values, and the masking unit being arranged to use each random bit stream for masking out the requests from the corresponding virtual output queue.
2. A masking unit as claimed in claim 1 further comprising a two input AND gate for each comparator, one input of the AND gate being arranged to receive the corresponding connection requests and the other input of the AND gate being arranged to receive the output of the corresponding comparator.
3. A masking unit as claimed in claim 1 including an arrangement for generating an uncorrelated set of randomly generated bit streams, the arrangement comprising a single random bit stream generator clocked at frequency f and fed into the first stage of a shift register which is n bits wide, where n equals the number of bits of the weighting factor of the requests, and x+1 stages deep, where x equals the number of connections that the memoryless cross-bar switch can make, the shift register being clocked at a frequency f/n to produce at each of the stages bar the first an uncorrelated set of n bit nibble streams for application to the comparators of the masking unit.
4. A masking unit as claimed in claim 3 in which the frequency f/n is equal to the frequency of the cyclic operation of the memoryless cross-bar switch.
5. A masking unit as claimed in claim 3 in which the random bit stream generator is a linear feed back register.
6. A method of controlling a data packet switching system of the type having a memoryless cross-bar switch providing cyclic connections between ingress routers and egress routers under the control of a switch control arbiter, the ingress routers providing incoming packet buffering on a virtual output queue basis and being arranged to generate switch correction requests when a virtual output queue contains a data packet, the method being characterized by comprising:
randomly selecting ones of said switch connection requests; and
transmitting all the connection requests except said selected requests to the switch control arbiter,
wherein each request is associated with a weight value, the selection of the requests including comparing the associated weight value with a first randomly generated value to generate a second random value and selecting the requests based on the second random value.