Port packet queuing

A port queue includes a first memory portion having a first memory access time and a second memory portion having a second memory access time. The first memory portion includes a cache row. The cache row includes a plurality of queue entries. A packet pointer is enqueued in the port queue by writing the packet pointer in a queue entry in the cache row in the first memory. The cache row is transferred to a packet vector in the second memory. A packet pointer is dequeued from the port queue by reading a queue entry from the packet vector stored in the second memory.

BACKGROUND OF THE INVENTION

A networking switch receives data packets from a number of ingress ports connected to the switch and provides the data packets to a number of egress ports connected to the switch. The switch determines the egress port to which the data packets are provided dependent on the destination address included in the data packet. A data packet received from an ingress port is stored in memory in the switch before being provided to the egress port.

The memory in the switch may be a common memory, in which all received data packets from all the ingress ports are stored, before being provided to the egress ports. A non-blocking switch allows all data received for all ingress ports to be provided to the egress ports. Non-blocking switches typically include a common memory in order to make the maximum amount of memory available to each port.

Typically, the switch includes a forwarding table implemented in forwarding logic in an ingress engine in the switch. The forwarding table is searched for a forwarding entry. The forwarding entry includes one or more egress ports to which the data packet is to be forwarded dependent on the destination address included in the received data packet.

As a received data packet is stored in the common memory, the location of the data packet in the common memory is stored in one or more egress port queues dependent on the selected forwarding entry. The egress port queues are stored in memory in the switch.

If the received data packet is an IP Multicast data packet, the location of the data packet in the common memory is written in the egress port queue associated with each port in the IP Multicast group. If the received data packet is a broadcast data packet, the location in the common memory is written in all egress port queues. Thus, dependent on the type of data packet received, the location of the data packet in the common memory; that is, a packet pointer may be enqueued on more than one egress port queue in the port cycle in which it is received. However, when transmitting the data packet from multiple queues, only one packet can be transmitted per port cycle. Thus, the location of the data packet in the common memory is dequeued from only one egress port queue per port cycle.

Thus the number of ports supported by the switch is limited by the speed at which the location of the data packet in the common memory can be enqueued on an egress port queue. A queue is typically implemented through a linked list in memory. Each entry in the linked list has two elements, a pointer element for storing the location of the data packet and a next pointer element for storing the location of the next entry on the linked list. Thus, two write accesses to memory are required to add the location of the data packet to the linked list, the first access writes the location of the data packet in common memory in the pointer element and the second access writes the location of the next entry in the next pointer element.

In a non-blocking switch, in which no received data packets are blocked by the switch, the memory speed is selected such that the location of a received data packet stored in common memory can be written to all the egress port queues in a port cycle. Also, a large queue is required in order to store pointers to IP Multicast and broadcast data packets stored in a common memory.

If the egress port queues are implemented in a linked list in Dynamic Random Access Memory (“DRAM”) a large queue is provided but the number of pointers that can be enqueued for a received data packet is limited by the speed of the DRAM. The number of pointers that can be enqueued for a received data packet is increased by implementing egress port queues in a Static Random Access Memory (“SRAM”) because SRAM is faster than DRAM. However, an SRAM cell is larger than a DRAM cell and therefore requires more area to provide a similar sized queue.

SUMMARY OF THE INVENTION

We present a queue with a fast enqueue. The queue includes a first memory having first memory access time and a second memory having a second memory access time. Control logic enqueues a pointer in the queue by writing the pointer to the first memory and transferring the pointer to the second memory. The first memory access time is less than the second memory access time. The first memory allows a pointer to be stored in multiple queues over multiple write cycles within a port cycle. Yet, the first memory can be relatively small since multiple pointers can be transferred together to the second memory from which only one pointer need be read per port cycle when dequeued.

The control logic enqueues the pointer in the first memory in a single write operation since a linked listed is not established until the pointers are transferred to the second memory.

The control logic may partially or fully fill a cache row in the first memory before transferring the cache row into the second memory in a single write operation. The entries in the cache row in the first memory are ordered by position in the cache row. The first memory preferably includes two cache rows.

A packet vector stored in the second memory may include a cache row entry and a count of the number of pointers stored in a cache row entry. The packet vector stored in the second memory may include a link to a next packet vector in the queue.

DETAILED DESCRIPTION OF THE INVENTION

FIG. 1illustrates a switch100including a plurality of egress port queues124a–eaccording to the principles of the present invention. A source node102and destination nodes112a–eare shown connected to the switch100. A data packet126received by the switch100at an ingress port132from source node102is forwarded through egress ports130a–eto one or more destination nodes112a–ddependent on a destination address encoded in a header included in the data packet126.

If the received data packet126is a broadcast data packet, the data packet126is forwarded to all destinations112a–e. If the received data packet126is an IP Multicast data packet, the data packet126is forwarded to all members of the IP Multicast group which may include one or more of destinations112a–e.

Upon receiving the data packet126, the switch100first stores the data packet126in segment buffer memory108. The switch100then determines from the data packet's header to which egress ports130a–ethe data packet is to be forwarded. Having determined the egress ports130a–e, the switch100writes a pointer to the location of the data packet in segment buffer memory108; that is a packet pointer128in the respective egress port queues124a–e. The egress port queues124a–eare implemented in a memory separate from the segment buffer memory108. The packet pointer128is written to an egress port queue124a–eif the data packet126is to be forwarded to the respective egress port130a–e. As shown inFIG. 1, data packet126is a broadcast data packet and a packet pointer128for data packet126has been enqueued on each egress port queue124a–e.

Thus, the packet pointer128may be enqueued in more than one egress port queue124a–eper port cycle for a received data packet. However, the packet pointer is dequeued from only one of the egress port queues124a–eper port cycle in order to transmit the data packet from the respective egress port130a–e. Thus, the packet pointer128is enqueued on an egress port queue124a–efaster than it is dequeued from the egress port queue124a–e.

FIG. 2is a timing diagram illustrating the enqueuing and dequeuing of packet pointers in the egress port queues124a–eshown inFIG. 1. Each port in the switch100is allocated a fixed port cycle200a–fin which to enqueue a packet pointer128by writing the packet pointer128at the tail of an egress port queue124a–eor to dequeue a packet pointer128by reading the packet pointer128stored at the head of the egress port queue124a–e

Six port cycles200a–fare shown inFIG. 2, one for each ingress port132and egress port130a–ein the switch100. Each port cycle200a–fis further divided into enqueue cycles202a–e. The number of enqueue cycles202a–eis dependent on the number of egress port queues124a–ein the switch100. Thus, five enqueue cycles202a–e, are provided one for each of the egress port queues124a–eshown inFIG. 1.

A packet pointer may be enqueued on each egress port queue124a–ein the switch100in enqueue cycles202a–ein a port cycle200a–e. However, only one packet pointer is dequeued from an egress port queue124a–ein a port cycle200a–e. Thus, a packet pointer enqueue cycle time must be faster than a packet pointer dequeue cycle time. In the example shown, the dequeue cycle time is five times slower than the enqueue cycle time. Therefore, a packet pointer is enqueued in fast memory; that is memory with a fast access time. However, because only one packet pointer is dequeued from the corresponding port queue124a–ein each port cycle200a–e, the packet pointers are dequeued from slow memory; that is, memory with a slower access time than the fast memory required for enqueuing the packet pointer.

Fast memory is preferably SRAM with a fast access time. However fast memory is not limited to SRAM. It may be any other memory with a sufficiently fast access time. For example, fast memory may be DRAM with a sufficiently fast access time.

Slow memory is preferably DRAM because a DRAM requires less gates than an SRAM. However, the slow memory is not limited to DRAM. It may be any other slow memory similar to DRAM. In an embodiment in which DRAM is used for both fast memory and slow memory, the slow memory time may be equal to the fast memory access time.

FIG. 3is a block diagram of one of the port queues124a–eshown inFIG. 1. The port queues124a–einclude slow memory and fast memory. The packet vector DRAM300is slow memory. The SRAM cache302is fast memory with a faster access time than the access time of the packet vector DRAM300. In one embodiment the packet vector DRAM300is implemented in DRAM with a slow access time and the SRAM cache302is implemented in SRAM with a faster access time than the packet vector DRAM300.

Packet pointers128are enqueued in the SRAM cache302and dequeued from the packet vector DRAM300in the same order in which the packets are received at the ingress port132. The SRAM cache302includes two cache rows304a–b. Each cache row304and304bincludes a plurality of packet pointer entries306. A packet pointer128may be stored in a packet pointer entry306.

After a received data packet126(FIG. 1) is stored in segment buffer memory108(FIG. 1), the packet pointer is forwarded to the egress port queue124a–eon packet pointer data_in308. The packet pointer128is written to the next sequential packet pointer entry306in the cache row304aor304bwhich is currently being filled.

Only one write cycle is necessary to enqueue the packet pointer128in a packet pointer entry306at the tail of the egress port queue124a–e. No link pointer is necessary because the packet pointer128is written to the next sequential packet pointer entry306. Thus, the packet pointers are ordered by position in the cache row304aor304b.

In an alternative embodiment, the SRAM cache302may be implemented in DRAM with an access time at least as fast as SRAM in order to reduce the size of the port queues124a–e. The access time of packet vector DRAM300may be equal to the access time of the SRAM cache302. The advantage implementing the port queue124a–ewith two separate DRAMs with the same access time is that a packet pointer can be added to the link list in a single memory access and an enqueue operation and dequeue operation can be performed in parallel by having a separate enqueue and dequeue memory.

The minimum enqueue cycle202a–e(FIG. 2) is dependent on the minimum memory access cycle for the SRAM cache302. For example, if a port cycle is 120 ns and SRAM cache302includes 5 egress port queues124a–e, each enqueue cycle202a–eis 120/5=24 ns and each dequeue cycle is 120 ns. In a dequeue cycle the packet pointer128is read and the pointer to the next packet pointer128is updated. Thus a read memory access cycle and a write memory access cycle is performed in each dequeue cycle requiring a packet vector DRAM300with a 60 ns memory access time. One write memory cycle access memory is performed in each enqueue cycle requiring an SRAM cache302with a 24 ns access time.

After a packet pointer128has been written to the last packet pointer entry306in the current cache row304a–b; that is, the row is filled, the full current cache row304aor304bstoring a plurality of packet pointers128is transferred to a cache row entry320in an empty packet vector310in packet vector DRAM300in a single transfer cycle. To transfer the current cache row304aor304bto packet vector DRAM300, the current cache row304aor304bis read from SRAM cache302, transferred on cache row data312to packet vector DRAM300and written in a cache row entry320in a packet vector310in packet vector DRAM300.

The transfer of the current cache row304aor304bto packet vector DRAM300is performed using a single SRAM cache read cycle. Thus, a plurality of packet pointers128stored in packet pointer entries306in the current cache row304aor304bare transferred in a single SRAM cache read cycle. For example, if the current cache row304aor304bhas twelve packet pointer entries306and each packet pointer entry306is 17 bits wide, 204 bits are transferred on cache row data312in a single transfer cycle. Only one transfer cycle is required to transfer twelve packet pointers128stored in the cache row304aor304b. Thus, the transfer of the current cache row304aor304bfrom SRAM cache302uses only a small portion of the bandwidth of the SRAM cache302and the packet vector DRAM300.

While one cache row304aor304bis waiting to be transferred to packet vector DRAM300, further packet pointers128can be enqueued in the other cache row304aor304b. Thus, a packet pointer128is individually enqueued in a packet pointer entry306in the SRAM cache302and a cache row304a–cincluding a plurality of packet pointers128stored in packet pointer entries306is written to packet vector DRAM300in a single transfer cycle.

The packet vector310also includes a link field316and a count field318. The count field318stores the number of packet pointers128stored in the cache row entry320. The link field316is provided for storing a pointer to the next packet vector310in the linked list of packet vectors.

Thus, packet pointers128are enqueued in SRAM and dequeued in DRAM, allowing packet pointers128to be queued quickly in fast SRAM and stored in slow DRAM.

FIG. 4is a block diagram including the port queue124shown inFIG. 3and associated control logic for enqueuing, dequeuing, and transferring packet pointers128.

A set of port registers associated with the egress port queue124are stored in port registers406. The port registers406are described in conjunction withFIG. 7. The set of port registers stored in port registers406are accessible by the enqueue engine404through SRAM enqueue port registers410, by dump engine402through dump port registers414and by dequeue engine400through DRAM dequeue port registers412.

The enqueue engine404controls the enqueuing of packet pointers128in SRAM cache302. To enqueue, the enqueue engine404forwards the segment buffer write memory address416on packet pointer data_in308. The enqueue engine writes the packet pointer data_in308in a packet pointer entry306(FIG. 3) in a cache row304a–bin SRAM cache302.

The enqueue engine404selects the cache row304aor304bin which to write the packet pointer entry dependent on the state of cache row428. The state of cache row428is dependent on enqueue row422forwarded through SRAM address multiplexer430. The state of enqueue row422is dependent on the state of port registers406.

The enqueue engine404selects the packet pointer entry306in the cache row304a–bdependent on packet pointer entry enable420. The state of the packet pointer entry enable420is dependent on the state of the SRAM enqueue port registers410.

The dump engine402controls the transferring of a cache row304aor304bfrom SRAM cache302to packet vector DRAM300. To transfer, the dump engine402first performs a memory read cycle through SRAM_RD424to enable the contents of an SRAM cache row304aor304b(FIG. 3) in SRAM cache302to be forwarded on cache row data312. Next, the dump engine402performs a memory write cycle through DRAM-WR426to enable cache row data312to be written into a cache row entry320(FIG. 3) in a packet vector310(FIG. 3) in a packet vector DRAM300.

The dequeue engine400controls the dequeuing of packet pointers128from packet vector DRAM300. To dequeue, the dequeue engine400reads a packet pointer128stored in a packet pointer entry306(FIG. 3) in a cache row field320(FIG. 3) in a packet vector310(FIG. 3) in packet vector DRAM300and forwards the packet pointer128on segment buffer read memory address408.

FIG. 5is a block diagram illustrating a linked list of packet vectors310a–cin the packet vector DRAM300shown inFIG. 3. The linked list includes three packet vectors310a–c. Packet vector310ais the first packet vector in the linked list. The link field316astores the address of next packet vector310bin packet vector DRAM300. Packet vector310bis the second packet vector310bin the linked list. The link field316bin packet vector310bstores the address of next packet vector310cin packet vector DRAM300. Packet vector310cis the third packet vector in the linked list. The link field316cin the packet vector310cstores the address of the next packet vector310in packet vector DRAM300in which a cache row304aor304bmay be written.

Packet vector310cis the last packet vector310in the linked list even though it includes a pointer to the next packet vector because the contents of the count field318, link field316and cache row entry320store invalid data. For example, the invalid data stored in the count field318may be zero indicating that there are no packet pointers128stored in the cache row entry320. In order to add another packet vector to the linked list, the cache row entry320, count field318aand link field316of the next packet vector are written with valid data in a single packet vector DRAM memory write access.

Each cache row entry320a–cin the packet vector310a–cincludes twelve packet pointer entries306. The number of packet pointer entries306is not limited to twelve, the number of packet pointer entries306is dependent on the memory access time of the SRAM cache302; that is, the time to transfer a cache row304aor304bto packet vector DRAM300. By transferring twelve packet pointers128per transfer cycle instead of one packet pointer per transfer cycle reduces the band width of the SRAM cache302consumed by the transfer cycle and allows more port queues124a–eto be provided in the same SRAM cache302.

The size of the count field318a–cis dependent on the number of packet pointer entries306in the cache row entry320. For twelve packet pointer entries306the count field318a–cis four bits wide. The size of the link field316is dependent on the size of packet vector DRAM300. The link field316stores of a pointer to the next packet vector310. With a 12-bit link field, the linked list may include up to 4096 packet vector entries310.

One memory write operation to the packet vector DRAM300is required to add a packet vector310to the linked list because the next packet vector310has been prefetched and the address of the next packet vector310has been written in the link field316of the last packet vector310in the linked list. The write operation copies the cache row304a–b(FIG. 3) in SRAM cache302(FIG. 3) to the cache row entry320in packet vector DRAM300and writes the number of packet pointers128stored in the cache row entry320into the count field318. The number of packet pointers128stored in the cache row entry is also stored in the port registers406(FIG. 4). The port registers406are described later in conjunction withFIG. 7.

FIG. 6is a block diagram of the SRAM cache302including two cache rows304aand304bwith each cache row including 12 packet pointer entries306. The enqueue engine404(FIG. 4) forwards the packet pointer128to be written to a packet pointer entry306on packet pointer data_in308. The cache row304aor304bto which the packet pointer128is to be written in a packet pointer entry306is selected dependent on the state of cache row428forwarded through SRAM address multiplexer430(FIG. 4) from the enqueue engine404. Having selected the cache row304aor304bin SRAM cache302, the packet pointer entry enable420selects a packet pointer entry306in the selected cache row304a–b. The packet pointer data_in308is written to the selected packet pointer entry306in the selected cache row304a–b.

In one embodiment, the segment buffer memory108(FIG. 1) may store up to 65536 data packets, thus each packet pointer128is 16-bits wide. A one-bit error field (not shown) is stored with the 16-bit packet pointer128in a packet pointer entry306. The state of the error bit determines whether the data packet stored in segment buffer memory108at the location specified by the packet pointer128is a valid data packet. With seventeen bits per packet pointer entry306, the width of a cache row304a–bis 204 bits (12 packet pointers×17 bits).

FIG. 7is a block diagram of the port registers406associated with the port queue124shown inFIG. 4. The port registers406include SRAM port registers700and DRAM port registers702. The SRAM port registers700include a dump row number register704, a fill row number register706, a packet pointer entry number register708, a cache full register710and a cache empty register712.

The DRAM port registers702include a current enqueue pointer714, a next enqueue pointer716, a number of packet vectors on queue register718, a no packet vectors register720, a current dequeue pointer register722, and a next dequeue packet pointer register724.

The enqueue engine404(FIG. 4) uses the contents of the SRAM port registers700to determine the packet pointer entry306(FIG. 6) in a cache row304aor304bin SRAM cache302(FIG. 4) in which to enqueue a packet pointer128. The dump engine402(FIG. 4) uses the contents of the SRAM port registers700to determine which cache row304aor304bin SRAM cache302(FIG. 4) from which to transfer the packet pointers128to a cache row entry320to packet vector DRAM300(FIG. 4).

The dump engine402(FIG. 4) determines from the contents of the DRAM port registers702the location in packet vector DRAM300(FIG. 5) of the next packet vector310(FIG. 3) to be enqueued. The dequeue engine400(FIG. 4) determines from the contents of the DRAM port registers702the location in packet vector DRAM300(FIG. 5) of the packet vector310(FIG. 3) from which to dequeue the next packet pointer128.

The port registers406are described in more detail in conjunction withFIGS. 9A,9B,10, and11.

FIG. 8is a block diagram of a switch100including a forward vector810for determining the egress port queue124a–eon which to enqueue a packet pointer128. The switch100includes an ingress ports engine800, a packet storage manager802, a segment buffer memory108, and an egress ports engine804. A data packet received by the ingress ports engine800at an ingress port132is forwarded to the packet storage manager802. The packet storage manager802forwards the data packet to segment buffer memory108with associated control signals on segment buffer memory address812. The received data packet forwarded on ingress data808by the ingress ports engine800is written in segment buffer memory108at the location indicated by a packet pointer128. The writing and reading of data packets in segment buffer memory108including the algorithm for locating packets in memory and thus generating pointers is described in co-pending patent application U.S. patent application Ser. No. 09/386,589 filed on Aug. 31, 1999 entitled “Method and apparatus for an Interleaved Non-Blocking Packet Buffer,” by David A. Brown, the entire teachings of which are incorporated herein by reference.

After the data packet has been written to segment buffer memory108, the packet storage manager802enqueues the packet pointer128in one or more egress port queues124dependent on the state of the forward vector810. The forward vector810includes a bit for each egress port in the switch100. The enqueue engine404(FIG. 4) determines the ports on which to enqueue a packet pointer128dependent on the state of the corresponding port bit in the forward vector810.

For example, if the switch has 27 ports, the forward vector810is 27-bits wide. If the bit in the forward vector810corresponding to an egress port130in the switch100is set ‘1’ the packet pointer128is enqueued in the corresponding egress port queue124. Alternatively, in an alternative embodiment, if the state of the bit is ‘0’ in the forward vector810the packet pointer128is enqueued in the corresponding egress port queue124.

The select signal814forwarded from the egress port engine804determines from which egress port queue124, a packet pointer128is dequeued. The packet pointer128is dequeued and forwarded on segment buffer memory address812to read the data packet stored in segment buffer memory108. The data packet stored at the location in segment buffer memory108corresponding to the packet pointer128stored in the selected egress port queue124is forwarded on egress data806to the egress port engine804. The egress port engine804forwards the data packet on the corresponding egress port130.

FIG. 9Ais a flow chart illustrating the steps performed in the enqueue engine404shown inFIG. 4for enqueuing a packet pointer128in a port queue124.

At step900, the enqueue engine404(FIG. 4) determines whether a data packet received at an ingress port132(FIG. 1) has been written to segment buffer memory108(FIG. 1). If so, processing continues with step902. If not, processing continues with step900.

At step902, the enqueue engine404(FIG. 4) initializes a port number variable (not shown) to the first port number in a group of port numbers associated with the enqueue engine404. The ports associated with the enqueue engine404may be all the ports in the switch or a portion of the ports in the switch100. For example, a27port switch (P1–P27) may include four enqueue engines with three of the enqueue engines each enqueuing packet pointers128for eight ports (P1–P8, P9–15, P17–24) and the fourth enqueue engine enqueuing packet pointers128for three ports (P25–27). The enqueue engine404is not limited to eight ports or three ports described; any number of ports may be enqueued by an enqueue engine404. The memory access time of the SRAM cache302determines the number of egress port queues that an enqueue engine404can enqueue.

At step904, the enqueue engine404(FIG. 4) determines from the forward vector810forwarded from the ingress ports engine800whether a packet pointer128is to be enqueued in the port queue124corresponding to the current port number. If so, processing continues with step910. If not, processing continues with step906.

At step906, the enqueue engine404(FIG. 4) determines if the current port is the last port in the group of ports controlled by the enqueue engine404(FIG. 4). If so, enqueuing of data packet pointers128for the received data packet is complete and processing continues with step900. If not, processing continues with step908.

At step908, the current port number is incremented in order to enqueue the packet pointer128in the next egress port queue124controlled by the enqueue engine404. Processing continues with step904.

At step910, the enqueue engine404(FIG. 4) reads the contents of the port registers406(FIG. 4) associated with the current port number. Processing continues with step912.

At step912, the enqueue engine404(FIG. 4) examines the contents of the cache full register710(FIG. 7). If the contents of the cache full register710(FIG. 7) indicate that SRAM cache302is full; that is cache rows304aand304bfor the current port are full, processing continues with step914. If not, processing continues with step916.

At step914, a system failure message is generated because the SRAM cache302for the current port is full and no further packet pointers128may be enqueued in the egress port queue124for the current port.

At step916, the packet pointer128is stored in a packet pointer entry306(FIG. 6) in SRAM cache302(FIG. 6) for the current port dependent on the contents of the SRAM port registers700(FIG. 7). The cache row304aor304bin which to store the packet pointer128is dependent on the contents of the fill row number register706(FIG. 7), and the packet pointer entry306(FIG. 6) in the selected cache row304a–bin which to store the packet pointer128is dependent on the contents of the packet pointer entry number register708(FIG. 7).

The contents of the fill row number register706(FIG. 7) are forwarded on enqueue row422(FIG. 4) to an SRAM address multiplexer430(FIG. 4) and forwarded on cache row428(FIG. 4) to the SRAM cache302(FIG. 4) dependent on the state of a select signal432. The state of the select signal432(FIG. 4) determines whether SRAM cache302(FIG. 4) is being written to enqueue a packet pointer128or read to transfer a cache row.

The contents of the packet pointer entry number register708(FIG. 7) determine the packet pointer entry306in the selected cache row302(FIG. 4) in which to store the packet pointer128. The enqueue engine404selects a packet pointer entry306dependent on the contents of the packet pointer entry number register708(FIG. 7) and forwards the selected packet pointer entry on packet pointer entry enable420(FIG. 4) to SRAM cache302(FIG. 4). The packet pointer128is forwarded on packet pointer data_in308to the selected packet pointer entry306in SRAM cache302(FIG. 4).

Having selected the cache row304a–b(FIG. 6) and the packet pointer entry306(FIG. 6) in SRAM cache302(FIG. 3), the enqueue engine404(FIG. 4) enqueues the packet pointer128in the egress port queue by writing the packet pointer128in the selected packet pointer entry306(FIG. 6). Processing continues with step918.

At step918, the enqueue engine404updates the contents of the SRAM port registers700(FIG. 7). The steps to update the contents of the SRAM port registers700are described in conjunction withFIG. 9B. After the contents of the SRAM port registers700(FIG. 7) are updated, processing continues with step906.

FIG. 9Bis a flow chart illustrating the steps performed to update the SRAM port registers700(FIG. 7) by the enqueue engine404(FIG. 4).

At step920, the enqueue engine404(FIG. 4) sets the contents of the cache empty register712to ‘0’ indicating that the SRAM cache302(FIG. 3) is not empty. The cache empty register712is monitored by the dump engine402to determine if there are packet pointers128to be transferred to packet vector DRAM300. The cache empty register712is used if packet vector DRAM300is empty in order to determine if there are packet pointers128stored in SRAM cache302. If the SRAM cache302is not empty, the packet pointer128may be moved to packet vector DRAM300before a cache row304aor304bis full in order to reduce the latency incurred by the switch100in forwarding a data packet126from an ingress port132(FIG. 1) to an egress port130a–e(FIG. 1). Processing continues with step922.

At step922, the enqueue engine404(FIG. 4) determines from the contents of the packet pointer entry number register708(FIG. 7) whether the current row is full. If so, processing continues with step924. If not, processing continues with step926.

At step924, the enqueue engine404(FIG. 4) toggles the state of the contents of the fill row number register706(FIG. 7) to move to the next cache row304aor304b(FIG. 6) processing continues with step928.

At step926, the enqueue engine404(FIG. 4) increments the contents of the packet pointer entry number register708(FIG. 7) in the current cache row304aor304b(FIG. 6).

At step928, the enqueue engine404(FIG. 4) determines from the contents of dump row number register704(FIG. 7) if the next row has been transferred by comparing the contents of dump row number register704(FIG. 7) and the fill row number register706(FIG. 7). If the contents are the same, the current row has not been transferred yet. If the current row has not been transferred, the enqueue engine404(FIG. 4) sets the contents of the cache full register710(FIG. 7) to ‘1’. The contents of the cache full register710are monitored by the dump engine402to determine if there is a cache row304aor304bto be transferred to packet vector DRAM300.

FIG. 10is a flow chart illustrating the steps performed in the dump engine402shown inFIG. 4for transferring a cache row304(FIG. 6) from SRAM cache302(FIG. 3) to a packet vector310(FIG. 5) in packet vector DRAM300(FIG. 5). The dump engine402also adds the packet vector310in which the transferred cache row304aor304bis stored to the linked list of packet vectors310stored in packet vector DRAM300(FIG. 5) for the egress queue124a–e.

At step1000, the dump engine402(FIG. 4) determines if a transfer cycle may be started. If so, processing continues with step1002.

At step1002, the dump engine402(FIG. 4) reads the SRAM port registers700(FIG. 7) and the DRAM port registers702(FIG. 7) corresponding to the port queue for the current port. Processing continues with step1004.

At step1004, the dump engine402(FIG. 4) determines if the contents of dump row number register704(FIG. 7) are not equal to the contents of the fill row number register706(FIG. 7). If so, processing continues with step1018. If not, processing continues with step1006.

At step1006, the dump engine402(FIG. 4) determines if the cache is full from the contents of the cache full register710(FIG. 7). If the cache is full, processing continues with step1018. If not, processing continues with step1008.

At step1008, the dump engine402(FIG. 4) determines from the contents of the packet pointer entry number register708(FIG. 7) if the number of packet pointers stored in cache row304aor304bis greater than a predefined transfer threshold. If so, processing continues with step1014. If not, processing continues with step1010.

At step1010, the dump engine402(FIG. 4) determines from the contents of the no packet vectors register720(FIG. 7) if there are packet vectors310(FIG. 3) stored in packet vector DRAM300(FIG. 3) for the current port. If so, processing continues with step1012. If not, processing continues with step1000.

At step1012, the dump engine402(FIG. 4) determines from the contents of the packet pointer entry number register708(FIG. 7) if there are packet pointer entries306(FIG. 3) stored in the current row. If so, processing continues with step1014. If not, processing continues with step1000.

At step1014, the dump engine402(FIG. 4) sets the count field318(FIG. 3) in the next available packet vector310(FIG. 3) in packet vector DRAM300(FIG. 3) to the number of packet pointers128written in the partially filled cache row304aor304b(FIG. 3) to be transferred to packet vector DRAM300(FIG. 3). The contents of the fill row number register706(FIG. 7) are toggled to the next cache row number. For example, if the current cache row number is 1, the contents of the fill row number register706(FIG. 7) are toggled to ‘2’. The contents of the packet pointer entry number register708are initialized to ‘1’. Processing continues with step1016.

At step1016, the dump engine402(FIG. 4) sets the cache empty register712(FIG. 7) to ‘1’ indicating that the SRAM cache302(FIG. 3) is empty. Processing continues with step1022.

At step1018, the dump engine402(FIG. 4) sets the count field318(FIG. 3) in the next available packet vector310(FIG. 3) in packet vector DRAM300(FIG. 3) to 12 (the maximum number of packet pointers128stored in packet pointer entries306(FIG. 3) in a cache row304aor304b(FIG. 3)). Processing continues with step1016.

At step1020, the dump engine402(FIG. 4) reads the contents of the packet pointer entry number708(FIG. 7). If the contents are set to the first packet entry (packet entry1), processing continues with step1016which has previously been described. If not, processing continues with step1022.

At step1022, the dump engine402(FIG. 4) transfers the contents of the cache row304a–b(FIG. 4) selected by the dump row number register704(FIG. 7) into the current packet vector310(FIG. 3) in packet vector DRAM300(FIG. 3). The address of the current packet vector is stored in the current enqueue pointer714(FIG. 7) in DRAM port registers702(FIG. 7). The selected cache row304a–b(FIG. 3) is transferred by reading the contents of the cache row304aor304b(FIG. 3) in SRAM cache300(FIG. 3) and writing the contents to a cache row entry320(FIG. 3) in the current packet vector310(FIG. 3) in packet vector DRAM300(FIG. 3). In the same packet vector DRAM access, the address of the next packet vector stored in the next enqueue pointer register716(FIG. 7) in the DRAM port registers702(FIG. 7) is written to the link field316(FIG. 3) of the current packet vector310and the count of the number of packet pointers stored in the cache row304aor304bis written to the count field318(FIG. 3). Processing continues with step1024.

At step1024, the contents of the SRAM port registers700and DRAM port registers702(FIG. 7) are updated as follows: the current enqueue pointer register714(FIG. 7) contents are set to the contents of the next enqueue pointer716. A next enqueue pointer obtained from a free list of pointers (not shown) is stored in the next enqueue pointer register716(FIG. 7). The cache full register710is set to not full. The no packet vectors register720(FIG. 7) is set to ‘0’ and the dump row number register704FIG. 7) is changed to the number of the next cache row304a–b(FIG. 7) to be transferred.

FIG. 11is a flow chart illustrating the steps performed in the dequeue engine400shown inFIG. 4for dequeuing a packet pointer128from a port queue124.

At step1100, the dequeue engine400determines if a packet pointer128should be dequeued. If so, processing continues with step1102. If not, processing continues with step1100.

At step1102, the dequeue engine400(FIG. 4) reads the contents of the no packet vectors register720(FIG. 7). The contents of the no packet vectors register720indicate whether there is a packet vector available. If no packet vectors are available, processing continues with step1104. If packet vectors are available, processing continues with step1106.

At step1104, a system failure is generated because there are no packet vectors available. Processing is complete.

At step1106, the dequeue engine400reads the packet vector310(FIG. 3) from packet vector DRAM300(FIG. 3) at the address in packet vector DRAM300(FIG. 3) stored in the current dequeue pointer register722(FIG. 7). The current packet pointer entry306(FIG. 3) in the current dequeue packet vector310is selected dependent on the contents of the next dequeue packet pointer register724(FIG. 7). The selected packet pointer128(FIG. 1) is forwarded on packet pointer data out322. Processing continues with step1108.

At step1108, the contents of the next dequeue packet pointer register724are incremented to point to the next packet pointer entry306(FIG. 3) in the current dequeue packet vector310(FIG. 3). Processing continues with step1110.

At step1110, the dequeue engine400(FIG. 4) determines by comparing the contents of the next dequeue packet pointer register724(FIG. 7) with the count field318in the current dequeue packet vector310if the current packet pointer entry306stores the last packet pointer128in the current dequeue packet vector310. If so, processing continues with step1112. If not, processing continues with step1100.

At step1112, the dequeue engine400(FIG. 4) sets the contents of the next dequeue packet pointer724(FIG. 7) to ‘1’ to select the first packet pointer entry306in a packet vector, removes the current packet vector from the linked list of packet vectors in packet vector DRAM300, returns the current dequeue packet vector310to a free list of packet vectors (not shown) and sets the contents of the current dequeue pointer register722to the contents of the link field316in the current dequeued packet vector310(FIG. 3). Processing continues with step1100.