US8411574B2 - Starvation free flow control in a shared memory switching device - Google Patents

Abstract

A shared memory packet switching device includes: a shared memory providing a shared memory space; an input logic unit associated with at least one receive port, and being operative to determine whether the associated receive port is saturated by determining whether a number of packets received via the associated receive port and currently stored in the shared memory exceeds a drop threshold value; a packet routing control unit operative to determine a destination one of the transmit ports for each of the received data packets; and an output logic unit associated with at least one of the transmit ports, the output logic unit being communicatively coupled with the packet routing control unit, and being operative to determine whether the associated transmit port is congested by determining whether a number of packets currently stored in the shared memory that are to be transmitted via the associated transit port exceeds a congestion threshold value, and also being operative to generate an associated output full signal indicative of whether the associated transmit port is congested. The input logic unit is responsive at least in part to each of the output full signals, and further operative to cause a selected packet received via the associated receive port to be dropped if the associated receive port is currently saturated and the output full signals indicate that a destination transmit port associated with the selected packet is currently congested.

Description

REFERENCE TO RELATED APPLICATIONS

This application is a Continuation of U.S. application Ser. No. 09/650,260, filed Aug. 29, 2000, now U.S. Pat. No. 7,120,117, issued Oct. 10, 2006, which claims priority from U.S. Provisional Application No. 60/123,091, filed Mar. 5, 1999. The disclosure of the prior application(s) is hereby incorporated by reference herein in its entirety.

BACKGROUND OF THE INVENTION

1. Field of the Invention

The present invention relates generally to flow control methodologies in communications networks, and more specifically to a shared memory packet switching device providing starvation free flow control functions.

2. Description of the Prior Art

Flow control relates to point to point traffic between a sending node and a receiving node in a network. In general, flow control methodologies provide for assuring that a fast sending node does not transfer data faster than the receiver can absorb it. Flow control typically involves some direct feedback from the receiving node to the sending node to tell the sending node how things are doing at the receiving end. One type of flow control method provides for a receiving node to assert backpressure on a sending node that is sending data too fast for the receiving node to handle. Typically, upon a determination by the receiving node that the sending node is sending data too fast, the receiving node will transmit a pause message to the sending node to instruct the sending node to pause in sending data to the receiving node. Sometimes, the sending node does not respond to the pause message and continues to send data to the receiving node which can lead to problems further discussed below. Another type of flow control method is packet dropping wherein packets, received from a sending node that cannot be processed by the receiving node, are simply dropped.

FIG. 1 shows a schematic circuit block diagram illustrating a prior art shared memory packet switching device at10 operating in accordance with conventional networking management flow control methods including a conventional backpressure assertion process, and/or a conventional packet dropping process. Thedevice10 includes: a plurality of N receiveports12 designated RX₀, RX₁, RX₂, . . . RX_n-1; and a plurality ofN transmit ports14 designated TX₀, TX₁, TX₂, . . . TX_n-1. Typically, each of the receiveports12 and associated ones at thetransmit ports14 are formed by associated bi-directional ports that are communicatively coupled with associated ones of a plurality of network nodes (not shown) via associated network links (not shown).

Thedevice10 also includes: aswitch control unit16 communicatively coupled with each of the receive ports and with each of the transmit ports; and a sharedmemory unit18 communicatively coupled with thecontrol unit16 as shown by aline20. Thecontrol unit16 typically provides packet routing functions for determining destination ports for each data packet received at the received ports, and also provides for temporarily storing and accessing the received data packets to and from the sharedmemory unit18. Thecontrol unit16 also typically provides destination port arbitration, and flow control processes such as packet dropping and assertion of backpressure.

Flow control problems may arise at theswitching device10 during operation in a network of a sending note (not shown) sends data packets to the switching device at a rate that overloads the switching device. To illustrate an exemplary network flow control problem, assume that receive port RX₀has a bandwidth of 100 Mbps, transmit port TX₁has abandwidth 100 Mbps, and transmit port TX₂has a bandwidth of 10 Mbps. Consider also that half of the data packets being received at receive port RX₀are to be transmitted via port TX₁as indicated by aline24, and the other half of the packets being received at port RX₀are to be transmitted via port TX₂as indicated by aline26. In this case, the sharedmemory unit18 will be filled with a large number of packets to be transmitted via port TX₂because the bandwidth of the receive port RX₀is much greater than the bandwidth of the transmit port TX₂. Therefore, port TX₂is said to be congested. Because the memory space of the sharedmemory unit18 is limited, a fairness problem arises if an excess amount of the memory space is used for storing packets received by a particular one of thereceive ports12 because the other receiveports12 also require memory space of the shared memory unit for buffering received data packets. Therefore, the receive port RX₀will ultimately reach a “full” or “saturated” state if a threshold number of packets received at port RX₀are currently stored in the shared memory unit.

In accordance with one solution to this problem, theswitching device10 may assert backpressure on the source nodes (not shown) sending data packets to port RX₀by sending a pause message via the associated transmit port TX₀(which is communicatively coupled with the same network link as the receive port RX₀) to the sending nodes instructing the sending nodes to pause in sending data packets. However, the sending nodes may or may not recognize the pause message in which case an excess amount of data packets received at port RX₀and destined for port TX₂will soon fill the sharedmemory unit18. Another solution to this problem provides for dropping all packets received at port RX₀after port RX₀reaches the full condition. However, by dropping all packets received at port RX₀, all of the traffic between port RX₀and port TX₁will be blocked. In this case, port TX₁is said to be starved.

What is needed is a method and apparatus for providing starvation free flow control in a shared memory switching device.

SUMMARY OF THE INVENTION

It is an object of the present invention to provide a shared memory packet switching device that provides starvation free flow control functions wherein an uncongested transmit port of the device is not starved as a result of flow control functions initiated at a saturated receive port as a result of heavy traffic through the device between the saturated receive port and a plurality of transmit ports including the uncongested transmit port and other transmit ports some of which may be congested.

Briefly, a presently preferred embodiment of the present invention provides a shared memory packet switching device having a plurality of receive ports for receiving data packets, and a plurality of transmit ports for transmitting data packets, the device providing a process of controlling the flow of data through the device.

The packet switching device includes: a shared memory providing a shared memory space for temporary storage of data packets received via the receive ports; at least one input logic unit associated with at least one of the receive ports, and being operative to determine whether the associated receive port is saturated by determining whether a number of packets received via the associated receive port and currently stored in the shared memory exceeds a predetermined drop threshold value; a packet routing control unit communicatively coupled with the at least one input logic unit, and being operative to determine a destination one of the transmit ports for each of the received data packets; and at least one output logic unit associated with at least one of the transmit ports, the output logic unit being communicatively coupled with the packet routing control unit, and being operative to determine whether the associated transmit port is congested by determining whether a number of packets currently stored in the shared memory that are to be transmitted via the associated transit port exceeds a predetermined congestion threshold value, and also being operative to generate an associated output full signal indicative of whether the associated transmit port is congested. The input logic unit is responsive at least in part to each of the output full signals, and being further operative to cause a selected packet received via the associated receive port to be dropped if the associated receive port is currently saturated and the output full signals indicate that a destination transmit port associated with the selected packet is currently congested.

In accordance with one aspect of the present invention, the switching device further includes a memory control unit for accessing data packets stored in the shared memory, and being operative to generate a count enable signal, and to assert the enable signal while a predetermined threshold portion of the shared memory space is occupied by stored packet data. The input logic unit also includes: an input counter responsive to the enable signal, and operative to provide an associated input count value indicative of the number of packets that are currently stored in the shared memory and that have been received via the associated receive port during a period wherein the enable signal is asserted, the input counter being further operative to clear the associated input count value if the enable signal is de-asserted; a first comparator unit responsive to the input count value, and operative to generate an associated select drop signal, and to assert the associated select drop signal based on a comparison between the input count value and the drop threshold value; and a drop logic unit responsive to the associated select drop signal and at least in part to the output full signals, and operative to drop a selected data packet received via the associated receive port if the associated select drop signal is asserted and the output full signals indicate that the destination transmit port associated with the selected packet is currently congested.

The input logic unit further includes: a second comparator unit responsive to the input count value, and operative to generate an associated pause signal for indicating that backpressure is to be asserted at the associated receive port, and to assert the associated pause signal based on a comparison between the associated input count value and a predetermined backpressure threshold value. The output logic unit further includes a transmit port control unit responsive to the associated pause signal, and operative to assert back pressure on an associated network link that is communicatively coupled with the associated receive port. In one embodiment, the transmit port control unit is operative to assert backpressure by transmitting a pause message via the associated network link.

In accordance with another aspect of the present invention, the input logic unit is further responsive to a drop enable signal selectively enabled by a user of the switching device to indicate whether packets may be dropped by the switching device, the input logic unit only being operative to cause the selected packet to be dropped if the drop enable signal indicates that packet dropping is enabled.

In a first embodiment of the present invention, the drop threshold value is predefined to be greater than the backpressure threshold value, whereby the switching device is operative to assert backpressure at a particular receive port before dropping packets received via the particular receive port. In a second embodiment of the present invention, the drop threshold value is defined to be less than the backpressure threshold value, whereby the switching device is operative to drop packets received via the associated receive port in order to avert the necessity of asserting backpressure at the associated receive port.

An important advantage of the starvation free flow control process of the present invention is that an uncongested transmit port of the device is not starved as a result of flow control functions initiated at a saturated receive port as a result of heavy traffic through the device between the saturated receive port and a plurality of transmit ports including the uncongested transmit port and other transmit ports some of which may be congested.

The foregoing and other objects, features, and advantages of the present invention will be apparent from the following detailed description of the preferred embodiment, which makes reference to the several figures of the drawing.

IN THE DRAWING

FIG. 1 is a schematic circuit block diagram illustrating a prior art shared memory packet switching device operating in accordance with conventional networking management flow control methods including a conventional backpressure assertion process and a conventional packet dropping process;

FIG. 2 is a schematic circuit block diagram illustrating a shared memory packet switching device in accordance with the present invention including a plurality of input logic units, a plurality of output logic units, and a packet routing/output queuing control unit, the device being operative to provide a starvation free flow control process in accordance with the present invention;

FIG. 3 is a schematic circuit block diagram illustrating details of one of the input logic units of the switching device ofFIG. 1, the input logic unit for determining data flow conditions at an associated receive port of the switch;

FIG. 4 is a schematic circuit block diagram illustrating details of one of the output logic units of the switching device ofFIG. 1, the output logic unit for determining data flow conditions at an associated transmit port of the switch; and

FIG. 5 is a schematic circuit block diagram generally illustrating details of the packet routing/output queuing control unit of the switching device ofFIG. 2;

FIG. 6 is a block diagram illustrating relationships between a backpressure threshold value and a packet dropping threshold value in accordance with a first embodiment of the present invention; and

FIG. 7 is a block diagram illustrating relationships between a backpressure threshold value and a packet dropping threshold value in accordance with a second embodiment of the present invention.

DETAILED DESCRIPTION OF THE PREFERRED EMBODIMENTS

FIG. 2 shows a schematic circuit block diagram of a shared memory packet switching device at110 in accordance with the present invention. In the described embodiment, theswitching device110 has an output queuing architecture. Thedevice110 includes: a plurality of N receiveports112 designated RX₀, RX₁, RX₂, . . . RX_n-1; and a plurality of N transmitports114 designated TX₀, TX₁, TX₂, . . . TX_n-1. In one embodiment, each of the receiveports112 and associated ones at the transmitports114 are formed by associated bidirectional ports that are communicatively coupled with associated ones of a plurality of network nodes via associated links (not shown). In the depicted embodiment, N=4.

Theswitching device110 further includes a plurality ofinput logic units116 designated INPUT_0, INPUT_1, INPUT_2, . . . INPUT_3 each being communicatively coupled with one of the receiveports112 as further explained below. Each of the input logic units is responsive to data packets received at the associated receiveport112, and is operative to determine current data flow conditions at the associated receive port, and is also operative to initiate backpressure assertion functions and packet dropping functions in accordance with a starvation free flow control methodology of the present invention. As further explained below, a received packet is only dropped by an associated input logic unit if it is determined that the associated receive port is in a full or saturated state, and the destination transmitport114 associated with the received packet is currently in a congested state.

Each of theinput logic units116 includes: a packetdata input port118 communicatively coupled with the associated receiveport112 for receiving incoming packet data from the associated network link; a datapacket output port120; a droppacket output port121 for providing a DROP control signal as further explained below; a filtersignal input port122 for receiving an associated one of N filter signals designated FILTER[N] each indicating whether an associated one of the transmitports114 is currently congested as further explained below; an enablesignal input port124 for receiving an enable signal designated EN indicating whether a threshold portion of the shared memory space is occupied such that flow control functions need to be activated as further explained below; a pausesignal input port126 for providing an associated one of N pause signals designated PAUSE[N] for indicating that backpressure is to be asserted via the associated network link as further explained below; and aport128 for receiving an associated one of N down-count signals designated DN[N] for indicating that a packet received at the associated receive port has been transmitted via one of the transmitports114 as further explained below, theport128 also for providing destination address information associated with received data packets. Theswitching device110 further includes: a plurality of N receivebuffer queues130 each being associated with one of the receiveports112 and having an input communicatively coupled with the packetdata output port120 of the associated one of theinput logic units116, a drop signal input for receiving the DROP signal fromport121 of the associated input logic unit, and an output communicatively coupled with adata bus131 as further explained below; a sharedmemory unit132 for receiving packet data and having aport134; and amemory control unit136 having aport138 communicatively coupled withport134 of the shared memory unit, a packetdata input port140 communicatively coupled with each of the receivebuffer queues130 via thedata bus131 for receiving data packets from the receive queues, adata output port142 for providing packet data read from the shared memory, and an enablesignal output port144 for providing the enable signal EN to theinput port124 of each of the input logic units. The memory control unit is operative to access data packets, including storing and retrieving data packets, in the sharedmemory unit132. The memory control unit is also operative to determine whether the total amount of memory space occupied by packet data in the shared memory unit is greater than or equal to a memory occupancy threshold value, P. In one embodiment, the memory occupancy threshold value, P, is expressed as a percentage such as 50% of the shared memory space. In one embodiment, thecontrol unit136 asserts the EN signal when the amount of occupied shared memory space is greater than or equal to P. If a predetermined threshold portion of the total shared memory space is occupied by stored packet data, then it is assumed that flow control functions are required and the EN signal is asserted.

Theswitching device110 further includes: a packet routing/outputqueuing control unit146 having adata input port148 for receiving packet data fromport142 of thememory control unit136, aport150 for receiving destination address values from the input logic units, and for providing the down-count signals DN[N] to the associated input logic units as further explained below, a packetdata output port152 for providing data packets for transmission via associated ones of the transmitports114, a filtersignal output port154 for providing the associated filter signals FILTER[N] toport122 of each of the associated input logic units, and an output fullsignal input port156 for receiving a plurality of N output full signals designated OUTPUT_FULL each for indicating whether an associated one of the transmitports114 is currently congested as further explained below. In operation, thecontrol unit146 is responsive to destination address values (e.g. MAC address values associated with the received data packets) received from the input logic units via itsport150, and operative to determine a destination one of the transmit ports for each received data packet. The outputqueuing control unit146 also provides output arbitration functions. As further explained below, thecontrol unit146 further includes logical components used in the flow control functions of theswitching device110.

Theswitching device110 further includes a plurality ofoutput logic units160 each being associated with one of the transmitports114 and being designated OUTPUT_0, OUTPUT_1, OUTPUT_2, . . . OUTPUT_3. Each of theoutput logic units160 includes: an output fullsignal output port162 for providing an associated one of N output full signals designated OUTPUT_FULL[N] toport156 of the packet routing/outputqueuing control unit146 via an N bitOUTPUT_FULL signal bus163; a pausesignal input port164 communicatively coupled with the pausesignal output ports126 of an associated one of theinput logic units116 for receiving an associated one of the N pause signals designated PAUSE[N] for indicating that backpressure is to be asserted via the associated transmit port; adata input port166 communicatively coupled with the packetdata output port152 of the packet routing/outputqueuing control unit146 for receiving packet data; and adata output port168.

Theswitching device110 further includes a plurality of N transmitbuffer queues170 each having an input port communicatively coupled with thedata output port168 of the associated one of theoutput logic units160, and an output port communicatively coupled with an associated one of the transmitports114 of thepacket switching device110. In one embodiment, each of the receivequeues130, and each of the transmitqueues170 is a first-in-first-out memory unit (FIFO).

Each of theoutput logic units160 is operative to determine whether the associated transmitport114 is currently in a state of congestion based on the number of data packets currently stored in the sharedmemory unit132 that are destined to be transmitted via the associated transmit port as further described below. If the associated transmit port is determined to be congested, the output logic unit asserts the associated one of the OUTPUT_FULL[N] signals. The outputqueuing control unit146 is responsive to the OUTPUT_FULL[N] signals and operative to assert associated ones of the FILTER[N] signals to indicate that associated packets may be dropped by associated ones of theinput logic units116 if the associated OUTPUT_FULL[N] signal is asserted and other conditions are satisfied as further explained below. Operation of thedevice110 is further explained below.

FIG. 3 shows a schematic circuit block diagram illustrating details of one of the input logic units116 (FIG. 2) at180 in accordance with the present invention. In the depicted embodiment, the input logic unit116 includes: a parsing unit182 having an input port184 for receiving packet data via the associated one of the receive ports112 (FIG. 2), an output port186 communicatively coupled with the associated one of the receive buffer queues130 (FIG. 2) via port120 of the input logic unit, a port187 for providing an up count signal designated UP for indicating that a data packet has been received at the associated receive port, and a destination address output port188 for providing the destination addresses (e.g. destination MAC addresses) of associated received packets; a drop logic unit190 having a port199 for providing the DROP signal to the associated one of the receive queues130 (FIG. 2) via port121 of the input logic unit, an input port194 for receiving the associated one of the filter signals FILTER[N] via port122 of the input logic unit, a port196 for receiving a select drop signal designated SELECT_DROP as further explained below; an input counter200 having an enable input port202 for receiving the EN signal from the memory control unit136 (FIG. 2) via port124 of the input logic unit, a down-count signal input port204 for receiving the associated one of the down-count signals DN[N] from the packet routing/output queuing control unit146 (FIG. 2), an up-count signal input port206 for receiving the up-count signal UP from port187 of the parsing unit182, and a count signal output port208 for providing an associated input count value designated C_IN[N] indicative of a number of packets that are currently stored in the shared memory and that have been received via the associated receive port during a period in which the EN signal is asserted; a pause comparator210 having a first input port212 for receiving the input count value C_IN[N] from port208 of the input counter, a second input port214 for receiving a backpressure threshold value designated B_THas further explained below, and an output port216 for providing the associated one of the pause signals PAUSE[N] to the output logic units160 (FIG. 2) via port126 of the input logic unit; and a drop threshold comparator218 having a first input port220 for receiving the input count value C_IN[N], a second input port222 for receiving a drop threshold value designated D_TH, and an output port224 for providing the SELECT_DROP signal to port196 of the drop logic unit190.

As mentioned above, the enable signal EN is asserted by the memory controller136 (FIG. 2) while the predetermined threshold portion P of the shared memory space is occupied by stored packet data. Also the down-count signal DN[N] is asserted by the packet routing/output queuing control unit146 (FIG. 2) when a data packet originating at the associated receive port112 (FIG. 2) is transmitted via the associated transmit port114 (FIG. 2). Theparsing unit182 is operative to assert the up-count signal UP when a packet is received at the associated receive port112 (FIG. 2). Therefore, theinput counter200 is operative to determine a number of packets that have been received at the associated receive port since the enable signal EN was asserted, and which are currently stored in the shared memory unit132 (FIG. 2) because they have yet to be transmitted via one of the transmit ports. Theinput counter200 is operative to clear the input count value when the EN signal is de-asserted.

Thefirst comparator210 is operative to assert the PAUSE[N] signal when the input count value C_IN[N] is greater than or equal to the backpressure threshold value B_TH. Thesecond comparator218 is operative to assert the SELECT_DROP signal when the input count signal C_IN[N] is greater than or equal to the drop threshold value D_TH. Thedrop logic unit190 is operative to assert the DROP signal when the SELECT_DROP signal and the associated FILTER[N] signal are both asserted. The associated receive queue130 (FIG. 2) is responsive to the DROP signal, and operative to drop a received packet stored therein when the DROP signal is asserted.

In accordance with the flow control methodology of the present invention, a packet is only dropped if: (1) the associated receive port is in a “full” or “saturated” state as indicated by the SELECT_DROP signal being asserted when C_IN[N]≧D_TH; and (2) the transmit port114 (FIG. 2) to which the packet is destined is in a congested state as indicated by the associated one of the FILTER[N] signals being asserted as further explained below. Depending on the selected values for D_THand B_TH, backpressure may be asserted for a receive port, either before or after packets are dropped at the associated receive port as further explained below.

FIG. 4 shows a schematic circuit block diagram generally illustrating details of one of the output logic units160 (FIG. 2) at240. In the depicted embodiment, the output logic unit160 includes: a transmit port control unit242 having a port244 for receiving the associated one of the PAUSE [N] signals via port164 of the output logic unit, an input port246 for receiving packet data and associated OUTPUT_UP_COUNT signal (for indicating that a packet destined for the associated transmit port has been stored in the shared memory unit) from port152 of the packet routing/output queuing control unit146 (FIG. 2), a port250 for providing the OUTPUT_UP_COUNT signal, and a port252 for providing an output down-count signal DN for indicating that a packet is being transmitted via the associated transmit port, and a port254 for providing packet data and PAUSE messages to the associated one of the transmit buffer queues170 (FIG. 2) via port168 of the output logic unit; an output counter264 having an up-count signal input port266 for receiving the OUTPUT_UP_COUNT signal from port250 of the control unit242, a down-count port268 for receiving the output queue down-count signal from port252 of the control unit242, and an output port270 for providing an output count value designated C_OUT[N] indicative of a total number of received data packets currently stored in the shared memory unit132 (FIG. 2) that are destined for the associated transmit queue; and a comparator274 having a first input port276 for receiving the output count value C_OUT[N] from port270 of the output counter, a second input port278 for receiving an output congestion threshold value designated B_TOTAL/N (wherein B_TOTALis equal to the total amount of shared memory space provided by the memory unit132 ofFIG. 2) as further explained below, and an output port280 for providing the associated one of the OUTPUT_FULL[N] signals to port156 of the packet routing/output queuing control unit146 (FIG. 2).

Thecomparator unit274 is operative to assert the OUTPUT_FULL[N] signal when the output count value C_OUT[N] is greater than or equal to the output congestion threshold value B_TOTAL/N. As mentioned above, the OUTPUT_FULL[N] signal is asserted, to indicate that the associated one of the transmit ports is “congested”.

The transmitport control unit242 is operative to assert backpressure by generating a PAUSE message to be provided to the associated transmit queue170 (FIG. 2) when the associated PAUSE[N] signal received at itsport244 is asserted.

FIG. 5 shows a schematic circuit block diagram generally illustrating details of the packet routing/output queuing control unit146 (FIG. 2) at300. In the depicted embodiment, thecontrol unit146 includes: acontrol unit buffer320 for buffering packet data read from the shared memory by the memory control unit136 (FIG. 2), and having aninput port324 for receiving the packet data, and anoutput port322; apacket routing unit312 having aport313 for receiving information from each of the input logic units116 (FIG. 2), the information including requests for access to associated ones of the transmit ports114 (FIG. 2) and destination address information that is parsed from the associated received data packets by the parsing unit182 (FIG. 2), a plurality ofN ports314 each providing an associated one of a plurality of N transmit signals designated TX_0, TX_1, TX_2, . . . TX_N-1, and aport316 for providing information indicative of selected data packets to be read from the shared memory unit and transferred to the associated destination transmit ports; and a data distribution andcontrol unit330 having a plurality ofN ports302 each for providing packet data to port166 of an associated one of the output logic units160 (FIG. 2) viaport152 of thecontrol unit146, aninput port332 for receiving packet data fromoutput port322 of thebuffer320, and a port333 for receiving destination port information determined by thepacket routing unit312 for each data packet to be transmitted. The datadistribution control unit330 further provides the OUTPUT_UP_COUNT[N] signals to each of the output logic units170 (FIG. 2) to indicate when packets destined for associated ones of the transmit ports114 (FIG. 2) are received and stored in the shared memory unit132 (FIG. 2).

The packet routing and outputqueuing control unit146 further includes a plurality of N ANDgates340. Each of the ANDgates340 includes: afirst input port342 for receiving an associated one of the OUTPUT_FULL_N signals viaport156 of thecontrol unit146 from an associated one of the output logic units160 (FIG. 2); asecond input port344 for receiving a drop enable signal designated DROP_ENABLE which may be selected by a user to enable or disable dropping of packets by the switching device as further explained below; a third input port346 for receiving an associated one of the transmit signals TX_N; and anoutput port348 for providing an associated one of the FILTER[N] signals to port122 of an associated one of the input logic units116 (FIG. 2).

Operation of the shared buffer packet switching device110 (FIG. 2) is described with reference toFIGS. 2-5. Data packets are received at each of the receive ports112 (FIG. 2) and the parsing unit182 (FIG. 3) associated with each receive port parses the receive data packets and provides the destination address information (e.g. a MAC destination address) to the packet routing/output queuing control unit146 (FIG. 2). Simultaneously, theparsing unit182 of the input logic unit provides the receive data packet to the associated one of the receive queues130 (FIG. 2) for temporary storage. Theparsing unit182 asserts the associated UP signal upon receiving the data packet currently stored in the associated one of the receive queues130 (FIG. 2) and the input count value determined by theinput counter200 will be increased. While the data packet is temporarily stored in the receive queue, the packet routing control unit212 (FIG. 5) determines a destination one of the transmit ports114 (FIG. 2) from which the data packet is to be transmitted based on its destination address. Also, based on the destination address received atport313 of the packet routing control unit212 (FIG. 5), thecontrol unit212 asserts one of the transmit signals TX₀, TX₁, TX₂, . . . TX_N-1provided at its ports314 (FIG. 5). Meanwhile, if it has been determined that an indicated one of the transmit ports is congested, then the associated one of the OUTPUT_FULL[N] signals will be asserted by the associated output logic unit. As described above, one of the transmit ports114 (FIG. 2) is determined to be congested by the associated one of the output logic units160 (FIG. 4) if the comparator274 (FIG. 4) determines that the output count value C_OUT[N] is greater than or equal to the output congestion threshold value B_TOTAL/N in which case the associated OUTPUT_FULL[N] signal is asserted to indicate that the associated transmit port is congested. With reference toFIG. 5, if the DROP_ENABLE signal is enabled by a user of the device to drop selected packets, and if the OUTPUT_FULL[N] signal associated with the transmit port to which the receive packet is destined is asserted, and if the associated one of the TX_Nsignals is asserted, then the associated one of the AND gates340 (FIG. 5) will assert the associated one of the FILTER[N] signals.

If the input count value C_IN[N] is determined by the comparator210 (FIG. 3) to be greater than or equal to the back pressure threshold value B_TH, then thecomparator210 asserts the PAUSE[N] signal. The transmit port output control unit242 (FIG. 4) of the associated one of the output logic units s responsive to the asserted PAUSE[N] signal, and is operative to assert back pressure by generating a pause message which is provided viaport168 of the output logic unit (FIG. 2) to the associated one of the transmitqueues170 which transmits the pause message via the associated one of the network links (not shown).

If the input count value C_IN[N] is determined by the comparator218 (FIG. 3) to be greater than the drop threshold value D_TH, then thecomparator218 asserts the SELECT_DROP signal provided at itsoutput224. The drop logic unit190 (FIG. 3) is responsive to the SELECT_DROP signal and to the FILTER[N] signals. As described above, the FILTER[N] signal is asserted when the associated one of the OUTPUT_FULL[N] signals is asserted to indicate that the associated one of the transmit ports is congested, and the DROP_ENABLE signal is asserted to indicate that packet dropping function is enabled, and the associated one of the TX[N] signals is asserted. The drop logic unit190 (FIG. 3) is operative to assert the DROP signal provided at itsoutput199 if the SELECT_DROP signal is asserted and the associated FILTER[N] signal is asserted. If the drop logic unit190 (FIG. 3) asserts the DROP signal, then the receive data packet stored in the associated one of the receive queues130 (FIG. 2) is dropped by the associated receive queue in response to the DROP signal.

To summarize, in accordance with the present invention, a receive data packet is dropped if the transmit port to which the receive data packet is destined is determined to be congested, and the receive port at which the packet has been received is determined to be saturated, or full (that is the input count value C_IN[N] is greater than or equal to the predefined drop threshold value D_TH). Therefore, in accordance with the flow methodology of the present invention, a received data packet is dropped at the associated receive port if the associated destination transmit port is congested, and if the associated receive port is determined to be saturated. So in accordance with the present invention, a packet is only dropped if the input port is determined to be saturated (that is, a number of data packets previously received at that receive port are stored in the shared memory unit), and the associated destination transmit port is determined to be congested. This is in contrast with prior art packet dropping schemes wherein a receive data packet is dropped based only on whether the associated receive port is determined to be saturated. Therefore, a receive port that is receiving data packets destined for different ones of the transmit ports will not drop data packets destined for transmit ports that are not congested. Therefore, uncongested transmit ports will not be starved while packets received at the same receive port and destined for congested transmit ports will be dropped. In prior art shared memory packet switching devices, packets are dropped without consideration of whether the associated one of the destination transmit ports is congested. By dropping packets without regard for whether the associated destination transmit port is congested or not, even uncongested transmit ports will be starved.

In the present invention, the function of the output logic unit160 (FIG. 2) and the functions provided by the packet routing and output queuing control unit146 (FIG. 2), specifically the provision of the FILTER[N] signals for filtering out or dropping receive data packets that are destined for congested transmit ports, provide for alleviating starvation of uncongested transmit ports by not dropping receive data packets destined for an uncongested transmit ports, and only dropping data packets at receive ports that are saturated if the associated destination transmit port is congested.

If a data packet received by an associated one of the input logic units116 (FIG. 2) is not dropped, as a result of either the receive port not being full or the associated destination transmit port not being congested, then the associated receive queue130 (FIG. 2) forwards the received data packet to the memory control unit136 (FIG. 2) which stores the received data packet in the shared memory unit132 (FIG. 2). Subsequently, the packet routing and control unit212 (FIG. 5) receives a request for access to the associated destination transmit port on behalf of the receive data packet, and the packetrouting control unit212 also receives the destination address information associated with the receive data packet from the parsing unit182 (FIG. 3), and the packetrouting control unit212 determines the associated destination transmit port. In accordance with arbitration methods, after the receive data packet is selected to be transmitted via the associated destination transmit port, thecontrol unit212 provides information to the memory control unit136 (FIG. 2) indicating that the associated received data packet is to be accessed from a sharedmemory unit132, and provided to the temporary FIFO320 (FIG. 5), and then provided to the data distribution and control unit330 (FIG. 5) which forwards the data packet to the associated one of the output logic units160 (FIG. 2). Theoutput logic unit160 then provides the data packet to the associated one of the transmit queues170 (FIG. 2) for transmission to the associated network link via the associated transmit port114 (FIG. 2).

FIG. 6 shows a block diagram illustrating a shared memory space at400 of the shared memory unit132 (FIG. 2) as managed in accordance with a first embodiment of the flow control process of the present invention. In this embodiment, the drop threshold value D_THis greater than the backpressure threshold value B_TH. As described above, when an occupied portion of the shared memory space exceeds thepredetermined threshold portion402 of the shared memory space (equal to P % of the total shared memory space, B_TOTAL*P, as mentioned above), the memory control unit136 (FIG. 2) asserts the EN signal to enable the input counters200 (FIG. 3) of each of the input logic units to begin counting packets received via the associated receive port. As shown, areserved portion404 of the shared memory space (equal to B_TOTAL*(1−P)) is divided into N allocated reserve portions406 of the shared memory, one for each of the N receive ports of the switching device. When the input count value C_IN[N] associated with a particular receive port exceeds B_TH, back pressure is asserted by sending a pause message as explained above. If one or more sending nodes (not shown) continue sending data packets to the particular receive port, the associated input count value C_IN[N] will eventually exceed D_TH, and therefore packets received via the particular receive port will be dropped.

An INPUT_FULL value defines a maximum amount of data that may be stored in the shared memory unit132 (FIG. 2) based on an assumption that an equal amount of memory space is allocated for each of the N receive ports (above the predetermined threshold portion P of shared memory space). The value of INPUT_FULL is defined by relationship (1), below.
B_TOTAL*(1−P)/N  (1)
wherein B_TOTALis the total amount of shared memory space in the shared memory unit132 (FIG. 2), P is the occupied memory space threshold value expressed as a percent value for defining the predetermined threshold portion of memory space as described above, and N is the number of bi-directional ports of the device110 (FIG. 2).

In the depicted embodiment of the present invention, D_THis set equal to a value between B_THand INPUT_FULL. In this embodiment, because D_TH>B_TH, backpressure is asserted for a receive port before any packets may be dropped. In accordance one embodiment of the present invention, the drop threshold value D_THis set equal to a value INPUT_FULL.

Also, in an embodiment, the relationship between INPUT_FULL and B_THis defined by relationship (2) below.
INPUT_FULL−B_TH≧N  (2)

When the values of D_THand B_THare set in accordance with relationship (2), it is ensured that the shared memory unit132 (FIG. 2) provides at least enough memory space for storing at least one received data packet for each receive port after backpressure is asserted for the associated receive port.

FIG. 7 shows a block diagram illustrating a shared memory space at410 of the shared memory unit132 (FIG. 2) as managed in accordance with a second embodiment of the flow control process of the present invention. In this embodiment, the drop threshold value D_THis less than the backpressure threshold value B_TH. When the input count value C_IN[N] associated with a particular receive port exceeds D_TH, packets are dropped at the particular receive port. If the associated input count value C_IN[N] continues to increase and exceeds B_TH, back pressure is asserted at the particular receive port by sending a pause message as explained above.

In the depicted embodiment, the relationship between D_THand B_THis defined by relationship (3) below.
B_TH−D_TH≧N  (3)

In this embodiment of the present invention defined by relationship (3), packets received at saturated receive ports are dropped before backpressure is applied. “Because the pause message is port based, when the switch sends a pause message, all external sources must be stopped. Some applications are sensitive to time delay. Therefore a flow control pause message could cause quality problems for some traffic streams. By selecting D_THto be less than B_TH, packets going to congested transmit ports earlier . . . ”.

Although the present invention has been particularly shown and described above with reference to a specific embodiment, it is anticipated that alterations and modifications thereof will no doubt become apparent to those skilled in the art. It is therefore intended that the following claims be interpreted as covering all such alterations and modifications as fall within the true spirit and scope of the invention.

Claims (15)

We claim:

1. A flow control method in a network device, comprising:

receiving a data packet at a receive port in the network device;

incrementing a receive port counter only when a count of previously received data packets stored in a shared memory exceeds a predetermined value;

determining, using a comparator, whether the receive port counter is greater than a first threshold;

determining a transmit port for transmitting the received data packet to its destination;

incrementing a transmit port counter for the transmit port;

determining whether the transmit port counter is greater than a second threshold, which, when the transmit port counter is greater than the second threshold, defines the transmit port as congested;

dropping the data packet if the receive port counter is greater than the first threshold and the transmit port counter is greater than the second threshold such that only selected packets received at the receive port, which are destined for a congested transmit port, are dropped; and

processing the data packet if the receive port counter is greater than the first threshold and the transmit port counter is less than the second threshold such that data packets received at the receive port, which are destined for an uncongested transmit port, are not dropped.

2. The flow control method ofclaim 1, further comprising:

determining whether a user programmable drop enable signal has been asserted; and

dropping the data packet only when the user programmable drop enable signal has been asserted.

3. The flow control method ofclaim 1 wherein determining whether the transmit port counter is greater than a second threshold comprises determining, using a comparator, whether the transmit port counter is greater than the second threshold.

4. The flow control method ofclaim 1 wherein the first threshold is proportional to a value determined by dividing the shared memory into N parts.

5. The flow control method ofclaim 1 wherein the first threshold is substantially equal to a number of data packets capable of being stored in a maximum portion of the shared memory.

6. A network device, comprising:

a shared memory configured to store received data packets;

a plurality of receive ports configured to receive data packets and to store the received data packets in the shared memory;

a plurality of transmit ports configured to transmit data packets that are stored in the shared memory to their respective destinations; and

receive port flow control logic, implemented in at least one of the receive ports, comprising:

a receive port counter configured to be incremented only when a predetermined portion of the shared memory is used to store previously received data packets;

circuitry to determine whether the receive port counter is greater than a backpressure threshold; and

circuitry to send a pause control signal to at least one of the transmit ports when the receive port counter is greater than the backpressure threshold; and

transmit port flow control logic, implemented in at least one of the plurality of transmit ports, comprising: a transmit port counter configured to be incremented and circuitry to determine whether the transmit port counter is greater than a first threshold, which, when the transmit port counter is greater than the first threshold, defines the transmit port as congested; and

circuitry within the receive port flow control logic to determine whether the receive port counter is greater than a drop threshold and to send a packet drop signal if the receive port counter is greater than the drop threshold and the transmit port counter is greater than the first threshold such that only selected packets received at the receive port, which are destined for a congested transmit port, are dropped, wherein the backpressure threshold and the drop threshold are configurable relative to each other to determine whether data packets are dropped before or after the pause control signal is sent.

7. The network device ofclaim 6, wherein the circuitry within the receive port flow control logic to determine whether the receiver port counter is greater than the backpressure threshold comprises a first comparator.

8. The network device ofclaim 6, wherein the circuitry within the receive port flow control logic to determine whether the receive port counter is greater than the drop threshold comprises a second comparator.

9. The network device ofclaim 6, wherein the circuitry within the transmit port flow control logic to determine whether the transmit port counter is greater than the first threshold comprises a third comparator.

10. The network device ofclaim 6 wherein the backpressure threshold is proportional to a value determined by dividing the shared memory into N parts.

11. The network device ofclaim 6 wherein the backpressure threshold is substantially equal to a number of data packets capable of being stored in a maximum portion of the shared memory.

12. A network device, comprising:

a plurality of receive ports, configured to receive data packets;

a shared memory, configured to store the received data packets;

a plurality of transmit ports, configured to transmit received data packets stored in the shared memory to their respective destinations;

transmit port flow control logic, implemented in at least one of the plurality of transmit ports, comprising: a transmit port counter configured to be incremented, and circuitry, including a first comparator, to determine whether the transmit port counter is greater than a first threshold; and

receive port flow control logic, implemented in at least one of the receive ports, comprising:

a receive port counter configured to be incremented when a predetermined portion of the shared memory is used to store previously received data packets;

circuitry to determine whether the receive port counter is greater than a second threshold; and

circuitry to:

send a packet drop signal if the transmit port counter is greater than the first threshold, which, when the transmit port counter is greater than the first threshold, defines a transmit port as congested, and the receive port counter is greater than the second threshold such that only selected packets received at the receive port, which are destined for a congested transmit port, are dropped, and

process received data packets if the transmit port counter is less than the first threshold and the receive port counter is greater than the second threshold such that data packets received at the receive port, which are destined for an uncongested transmit port, are not dropped.

13. The network device ofclaim 12, wherein the circuitry within the receive port flow control logic to determine whether the receive port counter is greater than the second threshold comprises a second comparator.

14. The network device ofclaim 12 wherein the second threshold is proportional to a value determined by dividing the shared memory into N parts.

15. The network device ofclaim 12 wherein the second threshold is substantially equal to a number of data packets capable of being stored in a maximum portion of the shared memory.

Images