Merged buffer signal switch

• US 5,862,128 A
• Filed: 12/29/1995
• Issued: 01/19/1999
• Est. Priority Date: 12/29/1995
• Status: Expired due to Term

• Current Assignee: GTE Laboratories Incorporated (Lumen Technologies, Inc.)
• Original Assignee: GTE Laboratories Incorporated (Lumen Technologies, Inc.)
• Inventors: Cooperman, Michael, Gee, Nee-Ben, Rathke, John Edmund
• Primary Examiner(s): Olms, Douglas W.
• Assistant Examiner(s): Patel, Ajit
• Application Number:
  US08/580,804
• Time in Patent Office: 1,117 Days
• Field of Search: 370/411, 370/412, 370/413, 370/414, 370/417, 370/418, 370/229, 370/230, 370/231, 370/232, 370/235, 370/236, 370/237
• US Class Current: 370/236
• CPC Class Codes: H04J 2203/001 using a shared central buffer
• CPC Class Codes: H04J 2203/0012 Switching modules and their interconnections
• CPC Class Codes: H04J 2203/0019 Multicast/broadcast capabilities
• CPC Class Codes: H04L 45/302 Route determination based on requested QoS
• CPC Class Codes: H04L 47/10 Flow control; Congestion control
• CPC Class Codes: H04L 47/11 Identifying congestion
• CPC Class Codes: H04L 47/2441 relying on flow classification, e.g. using integrated services [IntServ]
• CPC Class Codes: H04L 47/263 Rate modification at the source after receiving feedback
• CPC Class Codes: H04L 47/29 using a combination of thresholds
• CPC Class Codes: H04L 47/32 by discarding or delaying data units, e.g. packets or frames
• CPC Class Codes: H04L 49/101 using crossbar or matrix
• CPC Class Codes: H04L 49/3009 Header conversion, routing tables or routing tags
• CPC Class Codes: H04L 49/3027 Output queuing
• CPC Class Codes: H04L 49/555 Error detection
• CPC Class Codes: H04Q 11/0478 Provisions for broadband connections

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.

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.

2. The switch of claim 1, wherein:

said header processing means further comprises means for creating an internal routing header for each of said data packets, comprising, in combination;

means for identifying and storing in said internal routing header a priority for said data packet;

means for identifying and storing in said internal routing header the output port destination for said data packet; and

means for storing in said internal routing header said sequence number for said data packet; and

said circuit switch matrix further comprises means for relaying said plurality of data packets to said merged buffers according to said internal routing header.

3. The switch of claim 2, wherein said content-addressable memory means further comprises means for identifying and storing said priority of each of said data packets and means for routing each of said data packets according to said priority from said plurality of merged buffers to said plurality of output ports.

4. The switch of claim 3, further comprising, in combination:

clocking means with a speedup factor of at least 2; and

means for reading and writing to and from said plurality of input ports, said circuit switch matrix, said plurality of merged buffers, said content-addressable memory means, and said plurality of output ports, such that said data packets are written to said merged buffers during the first part of a time slot, said misrouted ones of said data packets are rerouted during the second part of a time slot, and the correctly routed ones of said data packets are written to said output ports during the first part of a subsequent time slot.

5. The switch of claim 4, further comprising, in combination:

an input tristate connected between each of said input ports and said circuit switch matrix; and

a feedback tristate connected between each of said feedbacks and a point between a corresponding one of said input tristates and said circuit switch matrix.

6. The switch of claim 5 wherein:

said sequence numbers increase sequentially per said priority and said output port destination to a preset maximum sequence number, said sequence numbers subsequently starting over with the first of said sequence numbers; and

said misrouted numbers increase sequentially per said output port destination to a preset maximum misrouted number, said misrouted number subsequently starting over with the first of said misrouted numbers.

7. The switch of claim 6, further comprising means for aborting said rerouting of any of said misrouted data packets if said misrouted data packet is in one of said merged buffers from which a misrouted one of said data packets has already been read during the same time period.

8. The switch of claim 7, wherein said data packets are asynchronous transfer mode cells.

9. The switch of claim 7, wherein said content-addressable memory includes a FIFO.

10. The switch of claim 7, wherein said circuit switch matrix further comprises means for tracking the utilization of said not busy ones of said merged buffers and means for changing the order in which said not busy ones of said merged buffers receive said misrouted data packets.

11. The switch of claim 7, wherein said content-addressable memory means further includes means for minimizing overflow of said merged buffers by comparing said sequence number of said rerouted data packet entering one of said merged buffers during the second half of a time slot to said sequence number of said correctly routed data packet leaving said merged buffer during the subsequent first half of a time slot and by not admitting additional ones of said rerouted data packets to said merged buffer until the absolute difference between said sequence numbers is less than a preset back pressure parameter.

12. The switch of claim 7, wherein the contents of each of said plurality of memory locations of said content-addressable memory means includes:

said sequence number of one of said input signals;

said corresponding output port destination of said input signal;

said corresponding priority of said input signal;

said misrouted sequence number;

the address of the one of said merged buffers containing said input signal; and

the address within said merged buffer means of said input signal.

13. The switch of claim 7, further including means for multicasting.

14. The switch of claim 13, wherein said means for multicasting comprises, in combination:

means for assigning one of said misrouted numbers to a multicast data packet, said malticast data packet being one of said data packets having more than one of said output port destination;

means for routing said multicast data packet to one of said merged buffers that did not receive a correctly routed one of said data packets;

means for rerouting said multicast data packet to multiple ones of said merged buffers during the second half of a time slot, said multiple ones of said merged buffers corresponding to said more than one output port destinations;

means for identifying not busy ones of said merged buffers after one of said multicast data packets has been rerouted to said merged buffers corresponding to said output port destinations; and

means for rerouting additional ones of said misrouted data packets to said not busy merged buffers during the same second half of a time slot.

15. The switch of claim 7, further comprising, in combination:

means for setting a predetermined buffer occupancy threshold for each of said priorities, said predetermined buffer signal occupancy threshold being lowest for the lowest of said priorities and highest for the highest of said priorities; and

means for discarding said data packets according to said priority before said data packets enter one of said merged buffers, said discarding occurring when the number of said data packets in said merged buffers reaches said predetermined buffer occupancy threshold, said discarding occurring in such a manner that said data packets with a lower of said priority are discarded first.

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.

17. The switching mechanism of claim 16, wherein said switching means includes a circuit switch fabric for relaying said plurality of signals to said buffers according to said destination addresses, said circuit switch fabric utilizing a means for at least partially sorting said plurality of signals according to said destination addresses.

18. The switching mechanism of claim 17, wherein said switching means further includes a plurality of feedbacks between said plurality of buffers and said circuit switch fabric for rerouting from said buffers those of said signals which have been misrouted, wherein each of said feedbacks is connected to a corresponding one of said buffers.

19. The switching mechanism of claim 18, wherein said switching means includes control means for routing said plurality of signals between said switching means, said buffers, and said output data pathways, comprising, in combination:

means for tracking and storing the location of each of said signals within said plurality of buffers;

means for identifying which of said signals located in said buffers have been misrouted;

means for indicating when each of said misrouted ones of said signals has been subsequently been rerouted;

means for identifying the next one of said signals to be sent to each of said output data pathways; and

means for identifying the next one of said misrouted signals to be rerouted.

20. The switching mechanism of claim 16, further including clocking means with a speedup factor of at least 2.

21. The switching mechanism of claim 17, wherein said switching means has no internal blocking.

22. The switching mechanism of claim 19, wherein said control means is a content-addressable memory comprising a plurality of memory locations and control logic.

23. The switching mechanism of claim 22, wherein said content-addressable memory includes a FIFO.

24. The switching mechanism of claim 22, wherein said signals are data packets.

25. The switching mechanism of claim 19, wherein said switching means further includes means for tracking the utilization of not busy ones of said buffers and means for cycling the order in which said not busy ones of said buffers receive said misrouted signals.

26. The switching mechanism of claim 16, further including means for multicasting.

27. The switching mechanism of claim 25, further including means for multicasting.

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.

29. The method of claim 28, further including, in combination, the steps of:

creating an internal routing header for each of said data packets;

identifying and storing in said internal routing header a priority for said data packet;

identifying and storing in said internal routing header the output port destination of said data packet;

storing in said internal routing header said sequence number of said data packet; and

relaying said data packet to said merged buffers according to said internal routing header.

30. The method of claim 29, further including, in combination, the steps of:

identifying and storing in said content-addressable memory means said priority of said data packet; and

routing each of said data packets from said plurality of merged buffers to said plurality of output ports according to said priority.

31. The method of claim 30, further including the steps, in combination, of:

clocking with a speedup factor of at least 2;

writing said data packets to said merged buffers during the first part of a time slot;

rerouting said misrouted ones of said data packets during the second part of a time slot; and

writing the correctly routed ones of said data packets to said output ports during the first part of a subsequent time slot.

32. The method of claim 31, further comprising the step of controlling said data packet entry into said circuit switch matrix through an input tristate connected between each of said input ports and said circuit switch matrix and through a feedback tristate connected between each of said feedbacks and a point between a corresponding one of said input tristates and said circuit switch matrix.

33. The method of claim 32, further comprising the steps of:

increasing said sequence numbers sequentially per said priority and said output port destination to a preset maximum sequence number;

subsequently starting said sequence numbers over at the first of said sequence numbers;

increasing said misrouted numbers sequentially per said output port destination to a preset maximum misrouted number; and

subsequently starting said misrouted numbers over at the first of said misrouted numbers.

34. The method of claim 33, further comprising the step of aborting said rerouting of any of said misrouted data packets if said misrouted data packet is in one of said merged buffers from which a misrouted one of said data packets has already been read during the same time period.

35. The method of claim 34, further comprising, in combination, the steps of:

tracking the utilization of said not busy ones of said merged buffers; and

changing the order in which said not busy ones of said merged buffers receive said misrouted data packets.

36. The method of claim 34, further including the step of minimizing overflow of said merged buffers by the steps, in combination, of:

comparing said sequence number of said rerouted data packet entering one of said merged buffers during the second half of a time slot to said sequence number of said correctly routed data packet leaving said merged buffer during the subsequent first half of a time slot;

calculating the absolute difference between said sequence numbers; and

not admitting additional ones of said rerouted data packets to said merged buffer until said absolute difference is less than a preset back pressure parameter.

37. The method of claim 34, further including steps for multicasting.

38. The method of claim 37, wherein said steps for multicasting comprise, in combination:

assigning one of said misrouted numbers to a multicast data packet, said multicast data packet being one of said data packets with more than one of said output port destination;

routing said multicast data packet to one of said merged buffers that did not receive a correctly routed one of said data packets;

rerouting said multicast data packet to multiple ones of said merged buffers during the second half of a time slot, said multiple ones of said merged buffers corresponding to said more than one output port destinations;

identifying not busy ones of said merged buffers after one of said multicast data packets has been rerouted to said merged buffers corresponding to said output port destinations; and

rerouting additional ones of said misrouted data packets to said not busy merged buffers during the same second half of a time slot.

39. The method of claim 34, further comprising the step of minimizing overflow of said plurality of merged buffers by the steps of, in combination:

setting a predetermined buffer occupancy threshold for each of said priorities, said predetermined buffer occupancy threshold being lowest for the lowest of said priorities and highest for the highest of said priorities; and

discarding said data packets according to said priority before said data packets enter one of said merged buffers, said discarding occurring when the number of said data packets in said merged buffers reaches said predetermined buffer occupancy threshold, said discarding occurring in such a manner that said data packets with a lower of said priority are discarded first.

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.

41. The method of claim 40, further including the steps, in combination, of:

providing as part of said switching means a circuit switch fabric connected between said plurality of input ports and said plurality of buffers for relaying said plurality of signals to said buffers according to said destination address; and

partially sorting, utilizing said circuit switch fabric, said plurality of signals according to said destination addresses.

42. The method of claim 41, further including the step of using a plurality of feedbacks between said plurality of buffers and said circuit switch fabric to reroute from said buffers those of said signals which have been misrouted, each of said feedbacks being connected to a corresponding one of said buffers.

43. The method of claim 42, further including the step of routing said plurality of signals between said switching means, said buffers, and said output data pathways using a control means.

44. The method of claim 43, further including the step of tagging each of said misrouted input signals.

45. The method of claim 44, further including the steps of, in combination:

providing as part of said control means a content-addressable memory;

tracking and storing in said content-addressable memory the location within said plurality of buffers of each of said signals;

identifying the next one of said signals to be sent to said destination address;

identifying which of said signals located in said buffers have been misrouted;

identifying the next one of said misrouted signals to be rerouted; and

indicating when each of said misrouted ones of said signals has subsequently been rerouted.

46. The method of claim 45, further including the steps of, in combination:

tracking the utilization of not busy ones of said plurality of buffers; and

cycling the order in which said not busy ones of said buffers receive said misrouted signals.

47. The method of claim 40, further including steps for multicasting.

48. The method of claim 45, further including steps for multicasting.