Back to results
US 4,893,304 AGranted
Broadband packet switch with combined queuing
AssigneeBell Communications Research, Inc.
InventorsJames N. Giacopelli, Morgan Littlewood
Life of this patent
Estimating the term…
Abstract
A novel packet switch architecture is disclosed. The packet switch utilizes internal queuing (i.e. recirculation loops) and output queuing (i.e. multiple paths to each destination) to provide a packet switch which offers superior performance in comparison to a packet switch which utilizes either of these queuing strategies alone. The combination of recirculation and output queues have complimentary effects. The output queuing reduces the number of recirculation loops needed and recirculation reduces the bandwidth requirements for an output buffered switch.
Claims20
A packet switch comprising:
- a plurality of inputs and a plurality of outputs,
- a sorting network connected to said inputs for sorting data packets to be routed through said switch,
- a trap network connected to said sorting network for identifying said data packets as exiting packets or recirculating packets,
- a plurality of recirculation loops connected to at least some of said inputs,
- a plurality of distinct routing networks for providing a plurality of routing paths to each of said plurality of outputs, and
- a selector network for applying said identified recirculating packets to said recirculation loops and said identified exiting packets to said routing networks.
3 more elements
A packet switch comprising
- a plurality of inputs and a plurality of outputs,
- a sorting network connected to said inputs for sorting data packets to be routed through said switch,
- a trap network connected to said sorting network for identifying said data packets as exiting packets or recirculating packets,
- a plurality of recirculation loops connected to at least some of said inputs,
- a plurality of distinct routing networks for providing a plurality of routing paths to each of said plurality of outputs, and
- a selector network for applying said identified recirculating packets to said recirculation loops and said identified exiting packets to said routing networks,
- wherein said switch further includes a concentrator network located between said trap network and said selector network.
4 more elements
A packet switch comprising
- a plurality of inputs and a plurality of outputs,
- a sorting network connected to said inputs for sorting data packets to be routed through said switch,
- a trap network connected to said sorting network for identifying said data packets as exiting packets or recirculating packets,
- a plurality of recirculation loops connected to at least some of said inputs,
- a plurality of distinct routing networks for providing a plurality of routing paths to each of said plurality of outputs, and
- a selector network for applying said identified recirculating packets to said recirculation loops and said identified exiting packets to said routing networks,
- wherein each of said routing networks is a banyan network, and
- wherein said banyan networks and said selector network are connected by means of an inverse perfect shuffle wiring pattern.
5 more elements
A packet switch comprising
- a plurality of inputs and a plurality of outputs,
- a first sorting network connected to said inputs for sorting data packets to be routed through said switch,
- a trap network connected to said sorting network for identifying said data packets as exiting packets or recirculating packets,
- a plurality of recirculation loops connected to at least some of said inputs,
- a plurality of distinct routing networks for providing a plurality of routing paths to each of said plurality of outputs, and
- a selector network for applying said identified recirculating packets to said recirculation loops and said identified exiting packets to said routing networks,
- wherein a second sorting network is connected between said trap network and said selector network for ordering said recirculating packets according to priority.
4 more elements
A packet switch comprising
- a sorting network connected to said inputs for sorting data packets to routed through said switch,
- a trap network for receiving said data packets sorted by said sorting network and for identifying said data packets as exiting packets or recirculating packets,
- a plurality of recirculation loops connected to at least some of said inputs,
- a plurality of distinct routing networks for providing a plurality of routing paths to each of said plurality of outputs, and
- a selector network for applying said identified recirculating packets to said recirculation loops and said identified exiting packets to said routing networks,
- wherein said data packets include logical addresses and said switch includes means for generating control packets, and
- wherein said trap network identifies data packets as recirculating or exiting packets by comparing said data packets with said control packets.
4 more elements
A packet switch comprising
- a plurality of inputs for receiving data packets to be routed through said switch
- a plurality of outputs,
- means for resolving conflicts among data packets addressed to the same output at the same time by designating the data packets as exiting or recirculating packets,
- network means for routing said exiting packets to said outputs, said network means permitting at least two packets to be simultaneously routed to each of said outputs, and
- means for providing a plurality of recirculation loops via which said recirculating packets are routed back to said inputs.
2 more elements
A packet switch comprising
- a plurality of inputs for receiving data packets to be routed through said switch,
- a plurality of outputs,
- means for resolving conflict among data packets addressed to the same output at the same time so as to designate the data packets as exiting or recirculating packets,
- means for providing a plurality of routing paths to each output via which said exiting packets are routed to said outputs, and
- means for providing a plurality of recirculation loops via which said recirculating packets are routed back to said inputs,
- wherein said packet switch includes means for ordering said recirculating packets according to priority so that if the number of recirculating packets exceeds the number of recirculating loops only packets of lower priority will be lost.
3 more elements
A packet switch comprising
- a plurality of inputs for receiving data packets to be routed through said switch,
- a plurality of outputs,
- means for resolving conflicts among data packets addressed to the same output at the same time so as to designate the data packets as exiting or recirculating packets,
- means for providing a plurality of routing paths to each output via which said exiting packets are routed to said outputs, and
- means for providing a plurality of recirculation loops via which said recirculating packets are routed back to said inputs,
- wherein said data packets contain logical addresses and wherein said switch includes means for generating control packets, said conflict resolving means utilizing said control packets to identify exiting and recirculating packets and to translate said logical addresses to physical addresses.
3 more elements
A packet switch comprising
- a plurality of inputs for receiving data packets to be routed through said switch,
- a plurality of outputs,
- means for designating the data packets as exiting packets or recirculating packets,
- a plurality of distinct routing networks via which each of said exiting packets can be routed to a particular one of said outputs,
- means for queuing said exiting packets at said outputs, and
- a plurality of recirculating loops including queuing means via which said recirculating packets are routed to said inputs.
3 more elements
A packet switch comprising
- a plurality of outputs,
- a plurality of inputs for receiving packets to be routed through said switch to said outputs,
- means for designating each of said packets as a recirculating packet or an exiting packet
- recirculation means for routing at least a fraction of said packets designated recirculating packets back to said inputs, and
- a plurality of distinct routing networks via which each of said exiting packets can be routed to a particular one of said outputs.
2 more elements
A packet switch comprising
- a plurality of outputs,
- a plurality of inputs for receiving packets to be routed through said switch to said outputs,
- means for designating each of said packets as a recirculating packet or an exiting packet,
- recirculation means for routing at least a fraction of said recirculating packets back to said inputs, and
- network means for routing said exiting packets to said outputs, said network means enabling at least two exiting packets to be routed simultaneously to the same output.
2 more elements
Dependencies are inferred from the claim text.