Merged buffer signal switch
First Claim
1. A switch for receiving a plurality of data packets as input signals through a plurality of input ports and for providing said data packets as output signals through a selected plurality of output ports, wherein each of said data packets has a corresponding output port destination, said switch comprising, in combination:
- header processing means connected to said plurality of input ports for assigning a sequence number to each of said data packets;
a plurality of merged buffers, each comprising a plurality of memory locations, for receiving and temporarily storing said plurality of data packets, wherein each of said merged buffers is connected to a corresponding one of said output ports;
a circuit switch matrix connected between said plurality of input ports and said plurality of merged buffers for relaying said plurality of data packets to said merged buffers, comprising, in combination;
means for partially sorting said plurality of data packets according to said output port destination;
means for routing each of said data packets to the one of said merged buffers which is connected to the one of said output ports which corresponds to said output port destination of said data packet if said merged buffer is not busy;
means for resolving contention among said plurality of data packets for any of said output ports by misrouting all but the first contending one of said data packets to one of said merged buffers that is not busy;
means for assigning a misrouted number to each of said misrouted data packets; and
means for accepting rerouted ones of said data packets;
a plurality of feedbacks between said plurality of merged buffers and said circuit switch matrix for rerouting from said merged buffers those of said data packets which have been misrouted, wherein each of said feedbacks is connected to a corresponding one of said merged buffers; and
content-addressable memory means connected to said circuit switch matrix and said plurality of merged buffers for routing said plurality of data packets between said circuit switch matrix, said merged buffers, and said output ports, comprising, in combination;
means for tracking and storing the location within said plurality of merged buffers of each of said data packets;
means for identifying which of said data packets located in said merged buffers have been misrouted;
means for indicating when each of said misrouted ones of said data packets has subsequently been rerouted;
means for identifying by utilizing said sequence number the next one of said data packets to be sent to each of said output port destinations;
means for identifying by utilizing said misrouted number the next one of said misrouted data packets to be rerouted;
means for rerouting to said circuit switch matrix said misrouted ones of said data packets according to said misrouted number and said output port destination; and
means for routing each of said plurality of data packets according to said sequence number and said output port destination from said plurality of merged buffers to said plurality of output ports.
2 Assignments
0 Petitions
Accused Products
Abstract
A signal switch with merged buffer architecture has multiple input ports connected to a circuit switch matrix which partially sorts the input signals based on output port destination. The circuit switch matrix is connected to multiple merged buffers, each in turn connected to a corresponding output port and feedback. Input signals entering the circuit switch matrix are normally sent to the buffer attached to the destination output port of the input signal, but, if more than one input signal is contending for an output port, all but the first contending input signal are misrouted to merged buffers that are not busy. The location in memory of all of the correctly routed and misrouted input signals in the switch is tracked by a control, which also routes input signals to their output port destinations from the merged buffers, and reroutes misrouted input signals to the correct buffers. The control does not reroute a misrouted signal until its intended buffer is no longer busy, so that each input signal is rerouted at most once. The control can also track the priority, sequence number, and output port destination of each input signal, in order to give preference to the higher priority input signals going to a particular output port. Buffer overflow can be minimized and switch resources more efficiently utilized by denying rerouted input signals access to a output buffer until the number of cells potentially waiting in that output buffer has dropped below a predetermined threshold. Buffer usage is balanced across the switch by changing the order in which buffers receive misrouted input signals. At the onset of congestion, signals are discarded when necessary at predetermined priority-dependent buffer signal occupancy thresholds. Multicasting can be handled by initially treating a multicast signal as a misrouted signal. The multicast signal is first routed to a merged buffer which did not receive a correctly routed signal, then it is rerouted simultaneously to all of the merged buffers corresponding to its output port destinations, so that all signals can be then sent to the appropriate output ports during a subsequent time period.
-
Citations
48 Claims
-
1. A switch for receiving a plurality of data packets as input signals through a plurality of input ports and for providing said data packets as output signals through a selected plurality of output ports, wherein each of said data packets has a corresponding output port destination, said switch comprising, in combination:
-
header processing means connected to said plurality of input ports for assigning a sequence number to each of said data packets; a plurality of merged buffers, each comprising a plurality of memory locations, for receiving and temporarily storing said plurality of data packets, wherein each of said merged buffers is connected to a corresponding one of said output ports; a circuit switch matrix connected between said plurality of input ports and said plurality of merged buffers for relaying said plurality of data packets to said merged buffers, comprising, in combination; means for partially sorting said plurality of data packets according to said output port destination; means for routing each of said data packets to the one of said merged buffers which is connected to the one of said output ports which corresponds to said output port destination of said data packet if said merged buffer is not busy; means for resolving contention among said plurality of data packets for any of said output ports by misrouting all but the first contending one of said data packets to one of said merged buffers that is not busy; means for assigning a misrouted number to each of said misrouted data packets; and means for accepting rerouted ones of said data packets; a plurality of feedbacks between said plurality of merged buffers and said circuit switch matrix for rerouting from said merged buffers those of said data packets which have been misrouted, wherein each of said feedbacks is connected to a corresponding one of said merged buffers; and content-addressable memory means connected to said circuit switch matrix and said plurality of merged buffers for routing said plurality of data packets between said circuit switch matrix, said merged buffers, and said output ports, comprising, in combination; means for tracking and storing the location within said plurality of merged buffers of each of said data packets; means for identifying which of said data packets located in said merged buffers have been misrouted; means for indicating when each of said misrouted ones of said data packets has subsequently been rerouted; means for identifying by utilizing said sequence number the next one of said data packets to be sent to each of said output port destinations; means for identifying by utilizing said misrouted number the next one of said misrouted data packets to be rerouted; means for rerouting to said circuit switch matrix said misrouted ones of said data packets according to said misrouted number and said output port destination; and means for routing each of said plurality of data packets according to said sequence number and said output port destination from said plurality of merged buffers to said plurality of output ports. - View Dependent Claims (2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15)
-
-
16. A switching mechanism for concurrently routing each given one of a plurality of signals to a selected one of plural output data pathways in accordance with a destination address, said mechanism comprising, in combination:
-
a plurality of input ports for concurrently receiving said signals; a plurality of buffers, each capable of storing at least one of said signals and each provided with a signal input and further provided with a signal output connected to a corresponding one of said output data pathways; and switching means connected between said input ports and said buffers, said switching means comprising, in combination; means responsive to said destination address of each of said given signals for identifying a destination one of said plurality of buffers connected to the one of said output data pathways specified by said destination address; means for routing said given signal to said destination buffer for immediate transfer to said destination output data pathway when said destination buffer is not busy; and means for misrouting and temporarily storing said given signal in a not busy one of said buffers when said destination buffer is busy, and for thereafter rerouting said misrouted and temporarily stored signal to said destination buffer when said destination buffer becomes not busy. - View Dependent Claims (17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27)
-
-
28. A method for receiving a plurality of data packets from a plurality of input ports and for providing said data packets as output signals through a selected plurality of output ports, comprising, in combination, the steps of:
-
assigning a sequence number to each of said data packets; providing a plurality of merged buffers, each comprising a plurality of memory locations, wherein each of said merged buffers is connected to a corresponding one of said output ports, for receiving, and temporarily storing said plurality of data packets; partially sorting, utilizing a circuit switch matrix connected between said plurality of input ports and said plurality of merged buffers, said plurality of data packets according to said output port destinations; routing each of said data packets to the one of said merged buffers which is connected to the one of said output ports which corresponds to said output port destination of said data packet if said merged buffer is not busy; resolving contention among said plurality of data packets for any of said output ports by misrouting all but the first contending one of said data packets to those of said merged buffers that are not busy; assigning a misrouted number to each of said misrouted data packets; rerouting, using a plurality of feedbacks between said plurality of merged buffers and said circuit switch matrix, from said merged buffers those of said data packets which have been misrouted, wherein each of said feedbacks is connected to a corresponding one of said merged buffers; providing a content-addressable memory means connected to said circuit switch matrix and said plurality of merged buffers for routing said plurality of data packets between said circuit switch matrix, said merged buffers, and said output ports; tracking and storing in said content-addressable memory means the location within said plurality of merged buffers of each of said data packets; identifying by utilizing said sequence number the next one of said data packets to be sent to each of said output port destinations; identifying which of said data packets located in said merged buffers have been misrouted; identifying by utilizing said misrouted number the next one of said misrouted data packets to be rerouted; indicating when each of said misrouted ones of said data packets has subsequently been rerouted; rerouting to said circuit switch matrix said misrouted ones of said data packets according to said misrouted number and said output port destination; accepting rerouted ones of said data packets into said circuit switch matrix; and routing each of said plurality of data packets according to said sequence number and said output port destination from said plurality of merged buffers to said plurality of output ports. - View Dependent Claims (29, 30, 31, 32, 33, 34, 35, 36, 37, 38, 39)
-
-
40. A method for concurrently routing each given one of a plurality of signals to a selected one of plural output data pathways in accordance with a destination address comprising the steps of, in combination:
-
concurrently receiving said signals at a plurality of input ports; providing a plurality of buffers, each capable of storing at least one of said signals and each provided with a signal input and further provided with a signal output connected to a corresponding one of said output data pathways; identifying the destination buffer connected to the one of said output data pathways specified by said destination address; routing said given signal to said destination output buffer for immediate transfer to said destination output data pathway when said destination buffer is not busy; misrouting and temporarily storing said given signal in one of said plurality of buffers that is not busy when said destination buffer is busy; and
transferring the misrouted and temporarily stored signal to said destination buffer when said destination buffer becomes not busy. - View Dependent Claims (41, 42, 43, 44, 45, 46, 47, 48)
-
Specification