Flexible switching hub for a communication network

Description Submit all comments and votes

BACKGROUND OF THE INVENTION

1. Field of the Invention

The present invention pertains to the field of digital communications. More particularly, this invention relates to switching hubs for high speed local area networks.

2. Background

A typical prior local area network is comprised of a set of communication agents coupled to a common communication medium. For example, an Ethernet local area network comprises a set of Ethernet compatible communication agents coupled to a coax cable or a twisted pair cable as a communication medium. In such systems a communication transaction between any two of the communication agents typically prevents communication among the other communication agents during the communication transaction.

One prior method for increasing the capacity of a local area network is to employ bridge circuits. Prior bridge circuits typically couple together segments of local area networks. Typically, each segment comprises a set of communication agents coupled to a communication medium. A bridge circuit enables communication between each of the communication mediums.

Such prior bridge circuits typically listen for communication messages on each of the communication mediums and propagates the appropriate communication messages to the other communication medium according to the network configuration. Communication messages are commonly referred to as communication frames.

Such a prior bridge circuit typically buffers communication frames that require propagation to another communication medium. Thereafter, the bridge circuit forwards the buffered communication frames to the appropriate destination communication agents. Unfortunately, such buffering and forwarding of communication frames between the communication mediums of the local area network increases the overall latency in the communication network.

Another prior method of increasing the capacity of a local area network is to employ a switched hub circuit. A switched hub circuit is typically arranged in a "star" configuration wherein each communication agent in a segment of the local area network couples to a unique serial communication port of the switched hub circuit. The switched hub circuit typically senses incoming communication frames, determines the destinations of the incoming frames, and switches the incoming communication frames to the appropriate outbound transmission paths.

Such switched hub circuits are typically faster than bridge circuits because switched hub circuits do not store and forward the incoming communication frame. Switched hub circuits instead usually start switching the incoming communication frames to the appropriate destinations immediately after determining the destinations of the incoming communication frames according the headers of the incoming communication frames. In addition, such switched hub circuits usually allow parallel data transfer between ports as long as the data transfer paths do not conflict.

Unfortunately, the switching functions performed by such prior switched hub circuits are complicated by certain types of communication traffic. For example, if more than one communication agent attempts to transmit to the same communication agent, the switched hub circuit must select one of the transmissions and delay the other transmissions. The delayed transmissions increase the latency in the network.

In addition, broadcast transmissions and multicast transmissions require a switched hub circuit to switch a single incoming communication frame to multiple destination communication agents even though conflicting traffic may be under way to the destination communication agents. The multicast transmissions typically conflict with other transmissions, thereby increasing delays in the network.

SUMMARY AND OBJECTS OF THE INVENTION

One object of the present invention is to provide a switching hub for a communication network.

Another object of the present invention is to provide a switching hub for a communication network that resolves conflicts among inbound communication frames that specify the same destination, thereby preventing collisions in the network.

Another object of the present invention is to provide a switching hub for a communication network that performs broadcast and multicast operations while avoiding collisions with conflicting communication traffic.

Another object of the present invention is to provide a switching hub for a communication network that enables system expansion through a parallel communication port to other switching hub segments in order to provide scalability.

These and other objects of the invention are provided by a communication system including a switched hub circuit that transfers incoming communication frames via a set of serial communication links. The switched hub circuit stores the incoming communication frames into a set of first-in first-out (FIFO) buffers that supply a set of outbound communication frames for transfer over the serial communication links. The switched hub circuit includes a parallel port for system expansion. The parallel port enables a communication system coupled to the parallel port to access the FIFO buffers.

Other objects, features and advantages of the present invention will be apparent from the accompanying drawings, and from the detailed description that follows below.

BRIEF DESCRIPTION OF THE DRAWINGS

The present invention is illustrated by way of example and not limitation in the figures of the accompanying drawings in which like references indicate similar elements, and in which:

FIG. 1 illustrates a communication network which comprises a set of communication agents and a communication subsystem;

FIG. 2 illustrates a communication subsystem for one embodiment which comprises a central processing unit, a bridge circuit, a DRAM subsystem, and a switched hub circuit;

FIG. 3 illustrates the switched hub circuit which comprises a set of serial communication ports for communication over the communication links and a parallel communication port for communication to other segments;

FIG. 4 illustrates the control and arbitration circuit for one embodiment which comprises a bus interface circuit, a control circuit, an arbitration circuit and a content addressable memory (CAM) circuit;

FIG. 5 illustrates the parallel communication port for one embodiment which comprises pairs of transmit and receive direct memory access (DMA) circuits, a transmit first in first out (FIFO) memory, and a receive FIFO memory;

FIG. 6 illustrates a serial communication port for one embodiment which includes a physical layer circuit and a communication control circuit;

FIG. 7a is a logical representation of a set of memory structures in the DRAM subsystem including a set of virtual transmit FIFO's (VTFs) that correspond to the serial communication ports;

FIG. 7b is a physical representation the virtual transmit FIFO's (VTFs) that correspond to of the serial communication ports;

FIG. 8 illustrates a communication subsystem which comprises a CPU, a DRAM subsystem, and a set of switched hub circuits all of which communicate over a system interconnect bus and provide serial scalability;

FIG. 9 illustrates a communication subsystem which comprises a set of CPUs, a set of DRAM subsystems, and a set of switched hub circuits that provide both serial and parallel scalability;

FIG. 10 illustrates a communication subsystem which comprises a pair of CPUs, a corresponding pair of DRAM subsystems, and a set of switched hub circuits;

FIG. 11 illustrates the routing schemes one and two wherein a communication frame is routed through same switched hub circuit;

FIG. 12 illustrates routing schemes three and four wherein a communication frame is routed through switched hub circuits on different communication segments;

FIG. 13 illustrates a row of an address translation table for one embodiment.

DETAILED DESCRIPTION

FIG. 1 illustrates a communication network 90. The communication network 90 comprises a set of communication agents 130-141 and a communication subsystem 10. The communication agents 130-141 are coupled to the communication subsystem 10 through a set of serial communication links 31-42.

The communication subsystem 10 functions as a switched hub for the communication network 90. The communication subsystem 10 enables communication between pairs of the communication agents 130-141. In addition, the communication subsystem 10 enables concurrent communication between multiple pairs of the communication agents 130-141.

FIG. 2 illustrates the communication subsystem 10 for one embodiment. The communication subsystem 10 comprises a central processing unit (CPU) subsystem 12, a bridge circuit 14, a DRAM subsystem 16, and a switched hub circuit 18. The CPU 12 through the bridge circuit 14, the DRAM subsystem 16, and the switched hub circuit 18 communicate over a system interconnect bus 20. The CPU 12, the DRAM subsystem 16, the switched hub circuit 18 and the system interconnect bus 20 are referred to as a communication segment.

The switched hub circuit 18 contains a set of serial communication ports and a parallel communication port. The serial communication ports of the switched hub circuit 18 are coupled to the serial communication links 31-42. The switched hub circuit 18 enables communication among the communication agents 130-141 over the serial communication links 31-42. The parallel port of the switched hub circuit 18 is coupled to a system interconnect bus 22. The switched hub circuit 18 communicates with other communication segments over the system interconnect bus 22.

FIG. 3 illustrates the switched hub circuit 18 for one embodiment. The switched hub circuit 18 comprises a set of serial communication ports 201-212. The serial communication ports 201-212 enable communication over the communication links 31-42.

The switched hub circuit 18 further comprises a parallel communication port 220 and a control and arbitration circuit 106. The parallel port communication port 220 enables communication to agents on other communication segments coupled to the system interconnect bus 22.

FIG. 4 illustrates the control and arbitration circuit 106 for one embodiment. The control and arbitration circuit 106 comprises a bus interface circuit 46, a control circuit 44, an arbitration circuit 42 and a content addressable memory (CAM) circuit 40.

The CAM circuit 40 contains an address translation table for the switched hub circuit 18. The CAM circuit 40 is organized as a 4 way set associative cache. Each row in the address translation table comprises a serial port number field, a parallel port number field, and a medium attachment controller (MAC) address field.

The bus interface circuit 46 enables the control circuit 44 to perform bus transactions over the system interconnect bus 20. The arbitration circuit 42 performs arbitration functions for accesses over the system interconnect bus 20.

The arbitration circuit 42 controls the access of the DMA circuits of the communication port 201-212 and 220 to a parallel bus 120. The arbitration circuit 42 also handles external requests for access to the parallel bus 120.

The control circuit 44 initializes and manages the DMA channels provided by the DMA circuits of the communication port 201-212 and 220, and also manages the address translation table. For one embodiment, the control circuit 44 is implemented as a micro coded controller.

FIG. 5 illustrates the parallel communication port 220 for one embodiment. The parallel communication port 220 comprises a transmit direct memory access (DMA) circuit 82, a receive DMA circuit 86, a transmit first in first out (FIFO) memory 66, and a receive FIFO memory 68. The transmit DMA circuit 82 performs DMA transfers between the DRAM subsystem 16 and the transmit FIFO memory 66 over the system interconnect bus 20. The receive DMA circuit 86 performs DMA transfers between the receive FIFO memory 68 and the DRAM subsystem 16 over the system interconnect bus 20.

The parallel communication port 220 further comprises a transmit DMA circuit 62, and a receive DMA circuit 64. The transmit DMA circuit 62 performs DMA transfers between the transmit FIFO memory 66 and another DRAM subsystem coupled to the system interconnect bus 22. The receive DMA circuit 64 performs DMA transfers between the DRAM subsystem coupled to the system interconnect bus 22 and the receive FIFO memory 68.

The bus interface circuit 86 enables the transmit DMA circuit 62 and the receive DMA circuit 64 to perform DMA communication transactions over the system interconnect bus 22. The transmit and receive DMA circuits 62 and 64 transfers data in burst transfers over the system interconnect bus 22.

FIG. 6 illustrates the serial communication port 201 for one embodiment. The serial communication port 201 is substantially similar to the serial communication ports 202-212. The serial communication port 201 comprises a physical layer circuit 50 and a communication control circuit 52.

The serial communication port 201 further comprises a transmit FIFO memory 54 and a receive FIFO memory 56, a transmit DMA circuit 58 and a receive DMA circuit 60. The transmit FIFO memory 54 buffers outbound communication frames for transfer over the serial communication link 31. The receive FIFO memory 56 buffers incoming communication frames received over the serial communication link 31.

The receive DMA circuit 60 accesses the received communication frames from the received FIFO memory 56 and transfers the received communication frames over the system interconnect bus 20 to the DRAM subsystem 16. The transmit DMA circuit 58 accesses outbound communication frames from the DRAM subsystem 16 over the system interconnect bus 20. The transmit DMA circuit 58 transfers the outbound communication frames into the transmit FIFO memory 54. The transmit and receive DMA circuits 58 and 60 transfer data in a continuous transactions comprising burst transfers over the system interconnect bus 20 until the transmit FIFO memory 54 is filled, or the receive FIFO memory 56 is emptied, respectively.

The communication control circuit 52 receives inbound communication frames from the serial communication link 31 through the physical layer circuit 50, and transfers the inbound communication frames to the receive FIFO memory 56. The communication control circuit 52 accesses outbound communication frames from the transmit FIFO memory 54, and transmits the outbound communication frames over the serial communication link 31 through the physical layer circuit 50.

The transmit and receive FIFO memories in the switched hub circuit 18 compensate for access latencies to the system interconnect busses 20 and 22. The transmit and receive FIFO memories compensate for delays between access requests to the system interconnect bus 20 and access grants, thereby preventing an underrun/overrun condition. For one embodiment, each transmit and receive FIFO memory contained in the switched hub circuit 18 holds 128 bytes.

The size of the transmit and receive FIFO memories is a function of the bit rate on the communication links 31-42, the bandwidth of the system interconnect bus 20, and the bus request/bus grant latency. The bus request/bus grant latency is also affected by the ratio of the bandwidth of the CPU 12 and the switched hub circuit 18 bandwidth requirements from the system interconnect bus 20. The size of the transmit and receive FIFO memories is defined such that underrun/overrun situations are held below a predefined threshold even in the worst case combinations.

For one embodiment, the physical layer circuit 50 and the communication control circuit 52 enable communication over the serial communication link 31 according to the Ethernet protocol. A token ring serial communication link can also be processed by such an architecture with a few modifications.

FIG. 7a-7b provide a logical and a physical representation of a set of memory structures in the DRAM subsystem 16 for one embodiment. The DRAM subsystem 16 contains a set of virtual transmit FIFOs (VTFs) 301-312. Each VTF 301-312 correspond to one of the serial communication ports 201-212. The DRAM subsystem 16 also contains a VTF 320 that corresponds to the parallel communication port 220. Each VTF 301-312 and 320 comprises a set of frame buffers and a back pressure buffer. Each frame buffer has the capacity to buffer a full length communication frame for the communication network 90, according to the relevant protocol (i.e., Ethernet).

The DRAM subsystem 16 also contains a broadcast memory structure 330. The broadcast memory structure is employed during broadcast operations and multicast operations through the switched hub circuit 18. The DRAM subsystem 16 further comprises a control memory block 332. The control memory block 332 contains a request queue for each VTF 301-312 and 320.

The CPU subsystem 12 contains a cache controller, and an internal memory. The cache controller and the internal memory in the CPU subsystem 12 reduces the bandwidth requirements of the CPU from the system interconnect bus 20 and the bridge circuit 14. The CPU subsystem 12 mainly performs communication management functions for the communication system 10.

For one embodiment, the system interconnect buses 20 and 22 are standardized peripheral component interconnect (PCI) buses for communication among a variety of input/output components such as communication and graphics co-processors. The system interconnect buses 20 and 22 each comprise a 32 bit bus portion that accommodates multiplexed address and data signals and an arbitration mechanism.

The communication agents 130-141 correspond to the VTFs 301-312. The VTFs 301-312 are managed by the internal logic of the switched HUB circuit 18 and by the CPU subsystem 12. The VTFs 301-312 are extensions of the corresponding transmit FIFO memories contained in the serial communication ports 201-212.

Each VTFs 301-312 and 320 comprises a series of frame buffers for buffering communication frames and a back pressure buffer. For one embodiment, each frame buffer includes a data portion that accommodates the maximum Ethernet frame length of 1520 bytes for double word alignment. Each buffered frame includes a control header.

Each serial communication port 201-212 receives incoming communication frames over the corresponding serial communication links 31-42, determines a destination communication port for each incoming communication frame, and transfers the incoming communication frames to the appropriate destination VTFs 301-312 and 320. The order of buffered frames in the VTFs 301-312 and 320 represent the order of arrival of the corresponding communication frames.

The frame buffer at the top of each VTF 301-312 and 320 is transferred to the transmit FIFO memory in the corresponding communication ports 201-212 and 220 by the transmit DMA circuits in the corresponding communication ports 201-212 and 220. Each transmit FIFO memory in the corresponding communication ports 201-212 and 220 is filled in one bus acquisition session using burst transfers over the system interconnect bus 20.

For one embodiment, the physical layer interface circuits in the serial communication ports 201-212 each support TPE and AUI Ethernet interfaces. The communication control circuits in the serial communication ports 201-212 each modify the original Ethernet protocol for the backoff algorithm. The communication control circuits in the serial communication ports 201-212 do not participate in the collision resolution protocol as a fair player, but always draws a zero thereby significantly increasing chances to win the collision resolution process.

The parallel communication port 220 enables communication between the system interconnect buses 20 and 22. The system interconnect bus 22 enables communication to another communication segment. Alternatively, the system interconnect bus 22 enables communication to another type of communication system that implements other protocols. The communication subsystem 10 may be connected to a file server through either the system interconnect bus 20 or the system interconnect bus 22.

The bus interface circuits 46 and 86 control the interface signals and access protocol to the system interconnect buses 20 and 22. For one embodiment, the interface signals for each system interconnect bus 20 and 22 include 36 data/address signals, 5 interface control signals, 4 arbitration and selection signals, 3 error detection signals and 2 system signals.

The CAM circuit 40 contains an address translation table for the switched hub circuit 18. Each row in the address translation table comprises a serial port number field, a parallel port number field, and an address field. The serial port number field is employed by the communication ports 201-212 and 220 to select one of the VTFs 301-312 and 320 in the DRAM subsystem 16. The parallel port number field is employed by the parallel communication port 220 to select a VTF in another communication segment coupled to the system interconnect bus 22.

The VTFs 301-312 and 320 in the DRAM subsystem 16 are managed by the internal logic of the switched HUB circuit 18 and by the CPU subsystem 12. The VTFs 301-312 and 320 are each cyclic. Each VTF 301-312 and 320 is a logical entity constructed from a list of frame buffers. For one embodiment, each frame buffer accommodates a maximum length Ethernet frame. Each frame buffer in the VTFs 301-312 and 320 includes a frame buffer header. The frame buffer header contains address pointers and flags.

When an incoming communication frame is received by one of the communication ports 201-212 and 220, the destination address of the incoming communication frame is used as an index to the address translation table in the CAM circuit 40. A destination port number that identifies one of the communication ports 201-212 and 220 is read from the address translation table in the CAM circuit 40. The receive DMA circuit in the communication port that receives the incoming communication frame then retrieves a pointer to the next available free frame buffer entry in the VTF that corresponds to the destination port number.

A get.sub.-- vtf.sub.-- ptr(i) function is employed to retrieve a pointer to the next free (available) frame buffer in the VTF of communication port number i, where i=1 . . . 12 corresponds to the communication ports 201-212. For one embodiment, the get.sub.-- vtf.sub.-- ptr(i) function is performed by the CPU 12. For another embodiment, the get.sub.-- vtf.sub.-- ptr(i) function is performed by the control circuit 44 which implements a micro coded micro machine. The CPU 12 or the control circuit 44 performs the get.sub.-- vtf.sub.-- ptr(i) function by accessing the control memory block 332 of the communication segment. The control memory block 332 contains a request queue for each of the communication ports 201-212 and 220 that indicates available frame buffers in the corresponding VTFs 301-312 and 320.

The get.sub.-- vtf.sub.-- ptr(i) returns a pointer to the next available frame buffer of the VTF number i, where i=1 . . . 12 corresponds to the VTFs 301-312. The receive DMA circuit in the communication port that receives the incoming communication frame then transfers the received communication frame to the destination VTF number i. The receive DMA circuit transfers the received communication frame to the destination VTF number i in blocks equal to the length of the corresponding internal transmit FIFO memory. The receive DMA circuit transfers the received communication frame in an interleaved fashion over the system interconnect bus 20 to allow interleaved transfers by other communication ports. After each time a block the size of the internal transmit FIFO is transferred to the destination VTF number i, the control circuit 44 sets an IFL flag in the frame buffer header.

The transmit DMA circuits in the communication ports 201-212 and 220 access data from the beginning of the corresponding VTFs 301-312 and 320. The transmit DMA circuits in the communication ports 201-212 and 220 do not start data transfer from frame buffers of the corresponding VTFs 301-312 and 320 until the number of bytes in a frame buffer is greater than or equal to the length of the corresponding transmit FIFO memory as indicated by at least one asserted IFL flag in the frame buffer header. The control circuit 44 clears the IFL flag which corresponds to a completed transfer.

The header of each frame buffer in the VTFs 301-312 and 320 includes a receive data transfer completed (RDTC) flag. The RDTC flag indicates that the receive operation on the incoming communication frame is complete and that the data transfer to that frame buffer is completed. The RDTC flag is asserted by the appropriate receive DMA circuit.

The header of each frame buffer in the VTFs 301-312 and 320 includes an internal FIFO length (IFL) field. The number of bits in the IFL field is determined by dividing the maximum frame length by the length of the internal FIFO memories in the communication ports 201-212 and 220. For one embodiment, the IFL field comprises 12 bits for 1518 byte Ethernet flames and 128 byte internal FIFO memories.

Each asserted bit in the IFL field indicates that a number of bytes equal to the internal FIFO length have been stored into the corresponding frame buffer. An IFL bit is also asserted if a complete communication frame shorter than the internal FIFO length has been stored in the corresponding frame buffer.

The IFL field mechanism permits unrestricted arbitration priority schemes for the VTFs 301-312 and 320. If all the VTFs 301-312 and 320 have the same priority and if access to the system interconnect bus 20 is granted in a "round robin" fashion, then only one IFL bit is required in the frame headers. The input bit rate of the receiving serial communication port is substantially equal to the output bit rate of the transmitting serial communication port. In addition, the internal FIFO memories provide a buffer between the input and output streams, thereby precluding an underrun situation in the transmitting communication port.

The switched hub circuit 18 enables multiple inbound communication frame transfers to the same VTF in the DRAM subsystem 16 while avoiding collisions. Each of the VTFs 301-312 and 320 accommodates more than one communication frame. A frame buffer has a fixed length equal to the maximum size communication frame of the specific protocol. For one embodiment, each frame buffer comprises 1520 bytes plus header overhead for an Ethernet communication link.

Alternatively, a pointer mechanism for a linked list structure of the frame buffers in the VTFs 301-312 and 320 may be used to eliminate the requirement for fixed length frame buffers.

For example, assume that the serial communication port(j) receives a frame with a destination of serial communication port(i), where i, j=1 . . . 12 corresponds to the communication ports 201-212. The get.sub.-- vtf.sub.-- ptr(i) function is performed and a pointer to the next free frame buffer of the VTF(i) is returned, where i=1 . . . 12 corresponds to the VTFs 301-312. The receive DMA circuit of port(j) starts to transfer the incoming frame to the frame buffer specified by the pointer returned by the get.sub.-- vtf.sub.-- ptr(i) function. Assume further that before the receive operation of the serial communication port(j) is completed, the serial communication port(k) receives a frame destined for the serial communication port(i). The get.sub.-- vtf.sub.-- ptr(i) function is performed again and a pointer to the next free frame buffer of the VTF(i) is returned. The receive DMA circuit for the serial communication port(k) starts to transfer the received frame to the frame buffer specified by the get.sub.-- vtf.sub.-- ptr(i) function.

The two data transfer operations to the VTF(i) from the serial communication port(j) and the serial communication port(k) are performed in parallel. The two data transfer operations to the VTF(i) are interleaved over the system interconnect bus 20. Additional data transfer operations for other serial communication ports (1 . . . 12) to the VTF(i) may also occur in parallel if the VTF(i) has available frame buffers. In each case, the received data is transferred in to consecutive frame buffers of the VTF(i), according to the order of arrival at the serial communication ports (1 . . . 12).

The parallel operation described above for the serial communication ports (1 . . . 12) that receive frames destined for the same VTF avoids collisions during transmissions by multiple communication agents to the same communication agent. The transmitting communication agents and the receiving communication agent do not sense delay in the transmission process.

The control memory block 332 contains a VTF.sub.-- full flag for each of the VTFs 301-312 and 320. Each VTF.sub.-- full flag indicates the free space status of the corresponding VTF. The VTF.sub.-- full flag is set if less than one free frame buffer is available in the corresponding VTF. If the VTF.sub.-- full flag is set, then a received frame destined for the corresponding VTF is not transferred to the corresponding VTF. Instead, the control circuit 44 applies back pressure on the incoming communication link and places a received frame header in the request queue of the corresponding VTF.

The VTF.sub.-- full flag for a VTF is reset when the corresponding transmit DMA circuit transfers enough data from the VTF to provide at least one free frame buffer. For one embodiment, the VTF.sub.-- full flags are maintained by the control circuit 44. For another embodiment, the VTF.sub.-- full flags are maintained by the CPU 12.

If a frame is destined for a VTF having a corresponding VTF.sub.-- full flag set, then the receiving serial communication port emulates a collision on the incoming communication link. The collision emulation is referred to as applying "back pressure" that maintains the transmitting communication agent in a deferred state until the VTF can accommodate another full communication frame. The incoming communication frame is then transferred to the VTF of the destination serial communication port.

For another embodiment, which allows multiple end-stations to connect to a single switched HUB port, the collision is dropped after the standard JAM time to permit other stations on the communication link to communicate.

The CPU 12 maintains a request queue for each of the VTFs 301-312 and 320. The request queues are located in the control memory block 332. Each request queue is accessible by all switched hub circuits coupled to the system interconnect bus 20, i.e. switched hub circuits on the same communication segment.

Each VTF.sub.-- full flag in the control memory block 332 indicates the status of the request queue of the corresponding VTF. If a request queue is not empty, then the CPU 12 maintains the corresponding VTF.sub.-- full flag set. A serial communication port that receives a communication frame destined for a VTF tests the corresponding VTF.sub.-- full flag. The serial communication port starts transfer of the incoming communication frame to the specified VTF only if the corresponding VTF.sub.-- full flag is not set. If the corresponding VTF.sub.-- full flag is set, then the control circuit 44 stores a receive header and the corresponding serial communication port number (1 . . . 12) in the request queue of the corresponding VTF.

Each header in the request queue for a VTF functions as a place holder for an incoming communication frame destined for that VTF. The arrival order of the incoming communication frames destined for a communication port is indicated by the ordering of headers in the corresponding request queue. After a VTF.sub.-- full flag is reset, the CPU 12 notifies the communication port specified by the first header in the request queue that a frame buffer is available in that required VTF. After the transfer of the incoming communication frame to the VTF is initiated, the CPU 12 removes the header from the corresponding request queue.

After a receive DMA circuit transfers an incoming communication frame to a VTF, the CPU 12 removes the corresponding service request from the corresponding request queue. The CPU 12 then initiates the receive DMA circuit of the next communication port specified in the request queue of that VTF to maintain the order of incoming communication frame arrivals to the communication system 10. The last frame buffer in a VTF is referred to as a back pressure buffer.

A receiving communication port seeking to transfer an incoming communication frame to a VTF tests the VTF.sub.-- full flag of that VTF. If the VTF.sub.-- full flag is set, then the receiving communication port applies "back pressure" on the incoming communication link. The back pressure places the transmitting communication agent coupled to the communication link in a differed state. The deferred state of the transmitting communication agent is dropped after sufficient space becomes available in the VTF to accommodate the incoming communication frame. For one embodiment, the back pressure is applied only for the permitted Ethernet JAM period.

A VTF.sub.-- full flag is asserted if less than one frame buffer is available in the corresponding VTF to prevent the possibility of a late collision situation, which may happen if the receive DMA channel finds that no more buffer space is available in the VTF and more than 512 bits have already been transferred. Late collision is not allowed by the Ethernet protocol.

The CPU 12 executes a congestion control process that gathers statistics on the request queues and the available empty space for the VTFs 301-312 and 320. The congestion control process determines the most congested of the VTFs 301-312 and 320. The CPU 12 then modifies the space allocation of the VTFs 301-312 and 320 according to that determination. The congestion control process changes the number of frame buffers available to each of the VTFs 301-312 and 320. The dynamic buffer allocation provided by the congestion control process increases the efficiency of memory usage in the DRAM subsystem 12 and improves the overall performance of the communication system 10.

Consider the following situation. The serial communication port 201 receives a communication frame destined for serial communication port 204. The VTF 304 is full as indicated by the corresponding VTF.sub.-- full flag. The serial communication port 201 then applies back pressure on the incoming communication link 31 which causes the transmitting communication agent 130 to enter a differed state.

Assume that the VTF 304 remains filled for a long period of time. Assume further that the serial communication port 206 receives a communication frame destined for the serial communication port 201. The incoming communication frame is placed into the VTF 301. However, that communication frame in the VTF 301 is not transmitted to the destination communication agent 130 because the serial communication port 201 is busy applying the JAM pattern in order to prevent the communication agent 130 from transmitting to the serial communication port 204.

Such a phenomenon is not desirable because the performance of the communication system 10 is reduced. In addition, the incoming communication frame through the serial communication port 206 is delayed by unrelated transactions to the serial communication port 204.

The following algorithm provides a solution to the problem. The serial communication port that is busy transmitting JAM pattern, the serial communication port 201, stops the JAM signal, thereby starting a collision resolution process. The contending stations, which are the serial communication port 201 and the communication agent 130, draw numbers beginning from a range of 0,1 and proceeding in powers of 2. After waiting the resulting slot times, the serial communication port 201 and the communication agent 130 try to transmit again.

The control circuit of the serial communication port 201 plays an unfair game in the collision resolution process, and always draws a 0. As more iterations of collision resolution process occur, the winning probability of the communication agent 130 decreases exponentially. Eventually, the serial communication port 201 wins and obtains the right to transmit the pending communication frame (the communication frame originated through serial communication port 206) from the VTF 301 to the communication agent 130. After transmission of the pending communication frame, the serial communication port 201 resumes the JAM transmission, thereby restoring the previous back pressure process.

For broadcast and multicast processing, the broadcast memory structure 330 comprises a collection of frame buffers. Each frame buffer includes a special header which indicates whether the frame buffer corresponds to a broadcast or multicast frame. The special header al