Controlled-feedback packet switching system

• US 5,416,769 A
• Filed: 07/13/1993
• Issued: 05/16/1995
• Est. Priority Date: 07/13/1993
• Status: Expired due to Term

• Current Assignee: AT&T IPM Corp. (AT&T, Inc.)
• Original Assignee: AT&T Corporation (AT&T, Inc.)
• Inventors: Karol, Mark J.
• Primary Examiner(s): Hsu, Alpus
• Application Number:
  US08/090,732
• Time in Patent Office: 672 Days
• Field of Search: 370/15, 370/16, 370/54, 370/56, 370/60, 370/60.1, 370/61, 370/65, 370/65.5, 370/85.2, 370/85.6, 370/94.1, 340/825.5, 340/825.51, 340/825.52, 359/115, 359/117, 359/135, 359/140, 395/425
• US Class Current: 370/414
• CPC Class Codes: H04L 2012/565 Sequence integrity
• CPC Class Codes: H04L 2012/5651 Priority, marking, classes
• CPC Class Codes: H04L 2012/5679 Arbitration or scheduling
• CPC Class Codes: H04L 49/15 Interconnection of switching modules
• CPC Class Codes: H04L 49/20 Support for services
• CPC Class Codes: H04L 49/254 Centralised controller, i.e. arbitration or scheduling
• CPC Class Codes: H04L 49/30 Peripheral units, e.g. input or output ports
• CPC Class Codes: H04L 49/3081 ATM peripheral units, e.g. policing, insertion or extraction
• CPC Class Codes: H04L 49/508 Head of Line Blocking Avoidance

Abstract

Packets or cells received from different input ports of a switch and destined for a common output port of that switch, are analyzed to determine their priority level. Lower-priority packets or cells are buffered in recirculation delay lines of appropriately-selected lengths, and thereafter scheduled for transmission to the output port based on their level of priority.

Claims

1. A packet switching system comprising:

at least one switching block having a plurality of input and output ports;

a control circuit for determining a) priority levels of packets received by the input ports and b) delivery time of packets to the output ports;

a plurality of recirculation delay elements, each one of which is connected to a dedicated input port and a dedicated output port; and

means for buffering a lower-priority packet which is contending for an output port with one or more higher-priority packets, in a selected one of the recirculation delay elements based on the priority level of the lower-priority packet as determined by the control circuit.

2. The invention of claim 1 wherein said buffering means comprises:

means for routing the lower-priority packet to one or more recirculation delay elements until the lower-priority packet is no longer in contention for the output port with at least one higher-priority packet; and

means for keeping track of all packets routed to all recirculation delay elements.

3. The invention of claim 2 further comprising:

means for limiting the number of times a lower-priority packet is routed to one or more recirculation delay elements.

4. The invention of claim 1 wherein when two packets of identical priority levels are a) received concurrently from two separate input ports, and b) destined for a single output port, one of the two packets is arbitrarily chosen to be buffered in a selected recirculation delay element.

5. The invention of claim 1 wherein the recirculation delay elements have differing lengths and wherein a particular recirculation delay element is selected to buffer a packet based on the priority level of the packet and the length of the recirculation delay element.

6. The invention of claim 5 wherein lower-priority packets are buffered in longer recirculation delay elements and higher-priority packets are buffered in shorter recirculation delay elements.

7. The invention of claim 1 further comprising

means for keeping all packets routed to an output port of the switching block in a first-in-first-out sequence.

8. Apparatus for use in a packet switching system comprising:

means for determining the level of priority of incoming packets received from different input ports of the packet switching system and destined for a common output port of the packet switching system;

means for routing the highest priority packet to the output port;

means for buffering in selected ones of a plurality of recirculation delay lines lower-priority packets; and

means for scheduling delivery to the output port of the lower-priority packets buffered in the recirculation delay lines based on their determined level of priority.

9. The apparatus of claim 8 wherein the buffering means comprises:

means for routing at least once the lower-priority packets to one or more recirculation delay lines.

10. The invention of claim 8 further comprising:

means for limiting the number of times a lower-priority packet can be routed to one or more recirculation delay lines.

11. A method of routing packets in a switch comprising:

determining levels of priority of incoming packets received from different input ports of the switch and destined for a common output port of the switch;

routing the highest priority packet to the output port;

buffering in selected ones of a plurality of recirculation delay lines lower-priority packets; and

scheduling delivery to the output port of the lower-priority packets buffered in the recirculation delay lines based on their determined level of priority.

12. A packet switching system comprising:

a switching fabric having at least one switching block with a plurality of input and output ports;

a plurality of recirculation delay elements, each one of which is connected to a dedicated input port and a dedicated output port of the switching fabric;

a control circuit for a) determining levels of priority of packets received from the input ports, and b) selecting one of the recirculation delay elements through which, one or more lower-priority packets contending for one of the output ports with one or more higher priority packets is returned to the switching fabric at least once.

13. The invention of claim 12 further comprising:

means for routing a packet to an output port when the packet is in contention for the output port with another packet of equal priority level.

14. The invention of claim 12 further comprising:

means for routing a packet to an output port based on the position of the input port from which said packet is received when said packet is in contention with another packet of equal priority level.