Method and apparatus for using multiple FIFOs to improve flow control and routing in a communications receiver

• US 5,777,987 A
• Filed: 12/29/1995
• Issued: 07/07/1998
• Est. Priority Date: 12/29/1995
• Status: Expired due to Term

• Current Assignee: Avago Technologies General IP PTE Limited (Broadcom, Inc.)
• Original Assignee: Symbios Inc (Broadcom, Inc.)
• Inventors: Reber, Mark A., Johnson, Stephen M., Adams, John M., Hoglund, Timothy E., Weber, David M.
• Primary Examiner(s): Patel, Ajit
• Application Number:
  US08/580,947
• Time in Patent Office: 921 Days
• Field of Search: 370/229, 370/230, 370/231, 370/235, 370/236, 370/410, 370/428, 370/429, 370/426, 395/250
• US Class Current: 370/336
• CPC Class Codes: H04L 47/10 Flow control; Congestion control
• CPC Class Codes: H04L 47/26 using explicit feedback to the source, e.g. choke packets
• CPC Class Codes: H04L 47/30 in combination with information about buffer occupancy at either end or at transit nodes

Abstract

A method and associated apparatus for using a primary FIFO and one or more secondary FIFOs in parallel to simplify flow control and routing in packet communication operations wherein at least one FIFO (buffer) is associated with each of a plurality of receiving nodes or components within a receiving node. The present invention applies received packets simultaneously to a primary FIFO and to all associated secondary FIFOs in the receiver of a packet communications link. After receipt of a packet, the packet is removed from any secondary FIFOs which correspond to receiver nodes or components to which the packet was not routed. For all receiving nodes or components to which the packet was routed, if the packet was stored in each associated secondary FIFO without overflow, then the packet is also purged from the primary FIFO. If any secondary FIFO overflowed by storage of the received packet, then the packet is purged from the overflowed FIFO and the packet remains stored in the primary FIFO for further processing. Flow control signals are generated and applied to the transmitting source as required in accordance with the status of the primary FIFO. The secondary FIFOs are not directly relevant to flow control logic. The receiving component corresponding to each secondary FIFO locates the next packet for processing by inspecting the associated secondary FIFO as well as the primary FIFO if the secondary FIFO overflowed. These methods and apparatus simplify flow control and routing control in packetized communication receivers.

Claims

1. A flow control method, operable in a receiving node of a packetized communication system, comprising the steps of:

applying a received packet from a transmitting node to a primary FIFO in said receiving node and to a secondary FIFO in said receiving node;

determining whether said received packet is successfully applied to said secondary FIFO;

purging said received packet from said secondary FIFO responsive to a determination that said received packet was not successfully applied to said secondary FIFO;

purging said received packet from said primary FIFO responsive to a determination that said received packet was successfully applied to said secondary FIFO;

determining the readiness of said receiving node to receive another packet in accordance with status of said primary FIFO; and

applying a flow control signal to said transmitting node indicative of the readiness of said receiving node to receive another packet.

2. The method of claim 1 wherein the step of determining successful application of said received packet to said secondary FIFO includes the step of:

detecting an overflow condition of said secondary FIFO by the application of said received packet.

3. The method of claim 1 wherein the step of determining readiness includes the steps of:

determining that said receiving node is ready to receive a packet when sufficient space is available in said primary FIFO to store a received packet; and

determining that said receiving node is not ready to receive a packet when sufficient space is not available in said primary FIFO to store a received packet.

4. A flow and routing control method, operable in a receiving node of a packetized communication system having a plurality of receiving components each associated with one of a plurality of FIFOs including a primary FIFO and a plurality of secondary FIFOs, said method comprising the steps of:

applying a received packet from a transmitting node simultaneously to said primary FIFO and to at least one of said plurality of secondary FIFOs to which said received packet is routed;

determining a status of said Primary FIFO;

determining the readiness of said receiving node to receive another packet in accordance with said status of said primary FIFO; and

applying a flow control signal to said transmitting node indicative of the readiness of said receiving node to receive another packet.

5. The method of claim 4 further comprising the step of:

purging said received packet from said primary FIFO in response to a determination that said received packet is not routed to said primary FIFO and that none of said at least one of said plurality of secondary FIFOs overflowed.

6. The method of claim 4 wherein the application of a received packet includes the steps of:

applying said received packet to said primary FIFO;

applying said received packet to said plurality of secondary FIFOs; and

purging said received packet from any of said plurality of secondary FIFOs to which said received packet is not routed.

7. The method of claim 4 wherein the step of determining readiness includes the step of:

determining that said receiving node is ready to receive a packet if sufficient space is available in said primary FIFO to store a received packet; and

determining that said receiving node is not ready to receive a packet if sufficient space is not available in said primary FIFO to store a received packet.

8. A flow control apparatus in a receiving node of a packetized communication system comprising:

means for applying a received packet from a transmitting node to a primary FIFO in said receiving node and to a secondary FIFO in said receiving node;

means for determining whether said received packet is successfully applied to said secondary FIFO;

means for purging said received packet from said secondary FIFO responsive to a determination that said received Racket was not successfully applied to said secondary FIFO;

means for purging said received Racket from said primary FIFO responsive to a determination that said received packet was successfully applied to said secondary FIFO;

means for determining the readiness of said receiving node to receive another packet in accordance with status of said primary FIFO; and

means for applying a flow control signal to said transmitting node indicative of the readiness of said receiving node to receive another packet.

9. The apparatus of claim 8 wherein the means for determining successful application of said received racket to said secondary FIFO includes:

means for detecting an overflow condition of said secondary FIFO by the application of said received packet.

10. The apparatus of claim 8 wherein the means for determining:

means for determining that said receiving node is ready to receive a packet when sufficient space is available in said primary FIFO to store a received packet; and

means for determining that said receiving node is not ready to receive a packet when sufficient space is not available in said primary FIFO to store a received packet.

11. A flow and routing control apparatus in a receiving node of a packetized communication system having a plurality of receiving components each associated with one of a plurality of FIFOs including a primary FIFO and a plurality of secondary FIFOs, said apparatus comprising:

means for applying a received packet from a transmitting node simultaneously to said primary FIFO and to at least one of said plurality of secondary FIFOs to which said received packet is routed;

means for determining a status of said primary FIFO;

means for determining the readiness of said receiving node to receive another packet in accordance with said status of said primary FIFO; and

means for applying a flow control signal to said transmitting node indicative of the readiness of said receiving node to receive another packet.

12. The apparatus of claim 11 further comprising:

means for purging said received packet from said primary FIFO in response to a determination that said received packet is not routed to said primary FIFO and that none of said at least one of said plurality of secondary FIFOs overflowed.

13. The apparatus of claim 11 wherein the means for application of a received packet includes:

means for applying said received packet to said primary FIFO;

means for applying said received packet to said plurality of secondary FIFOs; and

means for purging said received packet from any of said plurality of secondary FIFOs to which said received packet is not routed.

14. The apparatus of claim 11 wherein the means for determining readiness includes:

means for determining that said receiving node is ready to receive a packet if sufficient space is available in said primary FIFO to store a received packet; and

means for determining that said receiving node is not ready to receive a packet if sufficient space is not available in said primary FIFO to store a received packet.

15. A flow control method, operable in a receiving node of a packetized communication system, comprising the steps of:

receiving data, from a transmitting node, simultaneously, in a primary FIFO and a secondary FIFO;

determining the readiness of said receiving node to receive another packet based upon space available in either of said primary FIFO and said secondary FIFO; and

applying a flow control signal to said transmitting node, responsive to the determination of readiness, indicative of the readiness of said receiving node to receive another packet.

16. A flow control apparatus in a receiving node of a packetized communication system comprising:

a primary FIFO connected to a transmission source to receive transmitted packets;

a secondary FIFO connected to said transmission source to receive transmitted packets simultaneously with said primary FIFO; and

flow control logic circuits, associated with said primary FIFO and with said secondary FIFO, for generating a flow control signal indicative of the readiness of said receiving node to receive another packet based upon space available in either of said primary FIFO and said secondary FIFO and applying said flow control signal to said transmission source.