An N-by-N "knockout" switch for a high-performance packet switching system

Claim 2

A switching arrangement employing decentralized control and distributed routing, the switching arrangement comprising: a plurality of N output terminals (12); a plurality of N input terminals (10) for receiving N separate input signals, each input signal comprising packets of information in a time division sequence; and switching means (11) disposed to receive up to N simultaneous packets of information from the N input terminals during a predetermined time period and for routing each of the packets of information to the destined one of the N output terminals in the received sequence, CHARACTERIZED IN THAT the switching means being responsive to the simultaneous reception of a plurality of packets of information destined for a particular output terminal for storing up to L of such packets of information for transmission to the destined output terminal on a first-in, first-out basis while discarding any simutaneously received packets of information above the number L, where L ≦ N.

Claim 3

A switching arrangement according to claim 1 CHARACTERIZED IN THAT the switching means comprises: a plurality of N buses (14), each bus being connected to a separate one of the N input terminals for propagating an associated received input signal therealong; and a plurality of N bus interface units (15), each bus interface unit comprising an output connected to a separate one of the N output terminals of the switching arrangement; means (20) for detecting whether any of the N concurrent packets propagating on the plurality of N buses are destined for the associated output terminal of the switching arrangement, and for passing such packets in an unchanged state to separate outputs of the detecting and passing means; means (21) for concentrating the N concurrent output signals from the detecting and passing means into L concurrent output signals which appear at separate ones of L output terminals of the concentrating means, where N ≦ L and the L output signals, during each time slot period of the time division sequence, include all of the packets destined for the associated output up to a maximum of L such packets; and buffering means (22) responsive to the L output signals from the concentrating means for temporarily storing the packets destined for the associated output and then transmitting such stored packets in a first-in, first-­out sequence.

Claim 4

A switching arrangement according to claim 2 CHARACTERIZED IN THAT the buffering means comprises: a plurality of L packet buffers (24) for temporarily storing the packets of information destined for the associated output of the switching arrangement in a circular manner among the L packet buffers, and for routing the packets stored in the plurality of L packet buffers in a circular manner onto the associated output terminal of the switching arrangement.

Claim 5

A switching arrangement according to claim 2 CHARACTERIZED IN THAT the buffering means comprises: a shifter (23) including (a) L input terminals for receiving separate ones of the L concurrent output signals from the concentrating means during each time slot period of the time division sequence, (b) L output terminals, and (c) means for routing any packets received from the concentrating means, and destined for the associated output terminal of the switching arrangement, to each of the L output terminals in a circular manner; and a plurality of L packet buffers (24) connected to corresponding ones of the L output terminals of the shifter for temporarily storing only packets destined for the associated output of the switching arrangement, and for routing the packets stored in the plurality of L packet buffers in a circular manner onto the associated output terminal of the switching arrangement to provide the first-in, first-out sequence.

Claim 6

A switching arrangement according to claim 2, 3 or 4 CHARACTERIZED IN THAT the concentrating means comprises means for concurrently outputting any packets that are destined for the associated output terminal of the switching arrangement from the L output terminals of the concentrating means in accordance with a selected order of output terminals during each time slot period of the time division sequence.

Claim 7

A switching arrangement according to claim 5 CHARACTERIZED IN THAT the outputting means of the concentrating means comprises: a plurality of L contention sections coupled in sequence, each contention section including: N-x inputs, where x=1,2,..L and is the number of the immediately previous contention section in the sequence of L contention sections, and the N inputs of the first contention section receive the N outputs from the associated detecting and passing means, an output terminal for providing a separate one of the L concentrator output signals to the buffering means, and means for routing one of the N-x input signals to the output terminal of the contention section, and each of the remaining input signals to separate ones of the N-x inputs of the next contention section in the sequence of L contention sections, the signal routed to the output terminal of the contention section being one of the packet signals destined for the output of the associated bus interface unit when any of said packet signals appear as one of the input signals.

Claim 8

A switching arrangement according to claim 6 CHARACTERIZED IN THAT the routing means in each contention section of the concentrating means comprises a plurality of approximately N-x-1 two-input, two-output contention switches (35) connected in a predetermined tree arrangement for selecting one of the input signals for transmission to the output terminal of the contention section and for transmitting the remaining input signals to the next contention section in the sequence of L contention sections; and at least one delay means for providing predetermined delays at inputs of predetermined ones of the contention switches while permitting the output signal at the L contention section to appear concurrently with the output signals from each of the other L-1 contention sections.

Claim 9

A switching arrangement according to claim 7 CHARACTERIZED IN THAT each packet includes a multibit output address (26) indicative of a particular one of the N output terminals of the switching arrangement, and an activity bit (27) following the output address which includes a first logic state when the packet includes information to be transmitted and a second logic state when the packet is empty, the detecting and passing means comprising: a plurality of N packet filters, each packet filter being connected to a separate one of the plurality of N buses and comprising: means (30-32) for comparing the multibit output address in each packet received from the associated bus with the address of the associated output terminal of the switching arrangement during the time period for such received output address, and for generating a comparing means output signal which includes the first logic state when any one of the corresponding bits in the output addresses do not match, and the second logic state when the corresponding bits of the output addresses match; and means (33-34) responsive to the comparing means output signal for passing the bits of a packet as was received by the switching arrangement until the comparing means generates an output signal including the first logic state, and for transmitting the second logic state in each of the remaining bits in a packet, including the activity bit, once the comparing means generates an output signal including the first logic state; and each of the contention switches in the concentrating means looks at the activity bit in the packet arriving at each contention switch input to determine if the packet is destined for the associated output of the switching arrangement.

Claim 10

A switching arrangement according to claim 2, 3 or 4 CHARACTERIZED IN THAT each packet includes a multibit output address (26) indicative of a particular one of the N output terminals of the switching arrangement, and an activity bit (27) following the output address which includes a first logic state when the packet includes information to be transmitted and a second logic state when the packet is empty, the detecting and passing means comprising: a plurality of N packet filters (20), each packet filter being connected to a separate one of the plurality of N buses and comprising: means (30-32) for comparing the multibit output address in each packet received from the associated bus with the address of the associated output terminal of the switching arrangement during the time period for such received output address, and for generating a comparing means output signal which includes the first logic state when any one of the corresponding bits in the compared output addresses do not match, and the second logic state when the corresponding bits of the compared output address match: and means (33-34) responsive to the comparing means output signal for passing the bits of a packet as received by the switching arrangement until the comparing means generates an output signal including the first logic state, and for transmitting the second logic state for each of the remaining bits in a packet, including the activity bit, once the comparing means generates an output signal including the first logic state; and the concentrating means looks at the activity bit in each received packet from the detecting and passing means for determining if the packet is in contention for one of the L output signals of the concentrating means.

Claim 11

A first-in, first-out buffering arrangement comprising: an output terminal; N input terminals for receiving up to N separate concurrent packets of information during each time period of a time division sequence of time periods; CHARACTERIZED IN THAT the arrangement further comprises means connected to the N input terminals for detecting which of the N received concurrent packets of information during each time period are destined for the output terminal, and for passing each of such packets in an unchanged state to a separate one of N outputs of the detecting and passing means; means for concentrating the N concurrent outputs appearing at separate ones of the N outputs of the detecting and passing means into L concurrent output signals which appear at separate ones of L output terminals of the concentrating means, where L ≦ N and the L output signals, during each time period of the time division sequence of time periods, include all of the packets destined for the buffering arrangement output terminal up to a maximum of L such packets of information; and buffer means responsive to packets of information concurrently appearing at the L outputs of the concentrating and for temporarily storing the packets of information in separate storage locations and then transmitting such stored packets of information in a first-in, first-out sequence to the buffering arrangement output terminal.

Claim 12

A first-in, first-out buffering arrangement comprising: an output terminal; N input terminals for receiving up to N separate concurrent packets of information during each time period of a time division sequence of time periods; CHARACTERIZED IN THAT the arrangement further comprises means connected to the N input terminals for detecting which of the N received concurrent packets of information during each time period are destined for the output terminal, and for passing each of such packets in an unchanged state to a separate one of N outputs of the detecting and passing means; means for concentrating the N concurrent outputs appearing at separate ones of the N outputs of the detecting and passing means into L concurrent output signals which appear at separate ones of L output terminals of the concentrating means, where L ≦ N and the L output signals, during each time period of the time division sequence of time periods, include all of the packets destined for the buffering arrangement output terminal up to a maximum of L such packets of information; and buffer means responsive to packets of information concurrently appearing at the L outputs of the concentrating and for temporarily storing the packets of information in separate storage locations and then transmitting such stored packets of information in a first-in, first-out sequence to the buffering arrangement output terminal.

Claim 13

A buffering arrangement according to claim 10 CHARACTERIZED IN THAT the buffer means comprises: a plurality of L packet buffers for temporarily storing the packets of information from the concentrating and shifting means in a circular manner among the L packet buffers, and for routing the packets stored in the plurality of L packet buffers in a circular manner to the buffering arrangement output terminal.

Claim 14

A buffering arrangement according to claim 10 CHARACTERIZED IN THAT the buffer means comprises: a shifter including (a) L input terminals for receiving separate ones of the L concurrent output signals from the concentrating means during each time period of the time division sequence of time periods, (b) L output terminals, and (c) means for routing any packets received from the concentrating means, and destined for the buffering arrangement output terminal, to each of the L output terminals in a circular manner; and a plurality of L packet buffers connected to corresponding ones of the L output terminals of the of the shifter for temporarily storing only packets of information destined for the buffering arrangement output terminal, and for routing the packets of information stored in the plurality of L packet buffers in a circular manner to the buffering arrangement output terminal to provide the first-in, first-out sequence.

Claim 15

A buffering arrangement according to claim 10, 11 or 12 CHARACTERIZED IN THAT the concentrating means comprises: means for concurrently outputting any packets of information that are destined for the buffering arrangement output terminal from the L output terminals of the concentrating means in accordance with a selected order of output terminals during each time period of the time division sequence of time periods.