Packet memory system, method and device for preventing underrun

A packet memory system for selectively outputting received packets on one or more output ports. The packet memory system including a controller for controlling the output ports. Specifically, for packets of multicast or broadcast traffic that needs to be output from a plurality of the ports, the controller designates one or more reader ports that read the packet data from a packet memory such that the remainder of the ports are able to simply listen for the read packet data without performing a read operation.

FIELD OF INVENTION

The present invention relates to a packet memory system. More particularly, the present invention relates to preventing underrun in a packet memory system.

BACKGROUND OF THE INVENTION

A packet-processing device, like a switch microchip, usually needs to buffer the packets into a packet buffer memory (PM) having one or more banks while the device processes them. The size of some packets (for example Ethernet packets) is not known up-front, so the device needs to start storing the packet into the packet buffer without knowing how large the packet is. Moreover, packets arrive at the device in an interleaved fashion, so the device is simultaneously storing several incoming packets into the packet buffer. The state-of-the-art solution to store the packet in the device's packet memory is to assign multiple chunks (called pages) of packet memory to each packet, rather than a single big chunk. With this scheme, the packet is not stored consecutively in the banks of the packet memory, but rather scattered in one or more pages throughout multiple banks of the packet memory. As a result, a linked list of all the pages (and therefore banks) that a particular packet uses needs to be maintained in the switch; this linked list is then traversed to locate and read out the packet from the packet memory for transmission.

In a type of packet traffic known as broadcast traffic, all of the output ports of the device are requested to output the same packet data. Similarly, in a type of packet traffic known as multicast traffic, a plurality (but not all) of the output ports of the device are requested to output the same packet data. Therefore, for such traffic all these output ports will request the packet memory for the same packet data. This can create performance issues in the device because it causes a large number of output ports request for the same data at roughly the same time. Specifically, when this happens often a small number of banks of the packet memory will need to serve all the requests while the other banks remain idle. As a result, although some of the output ports would get the data fast, others would need to wait a relatively long time to obtain the data because the a small subset of banks needs to serialize all the requests from the output ports due to the usually small number of read ports per bank.

This waiting time for the data has two undesirable consequences. If the data corresponds to the start of the packet, the transmission of the whole packet will be delayed. This implies a degradation in bandwidth of the port since it is waiting to send data when it actually could be sending data. If the data corresponds to the middle of the packet and some of the data of the packet has already been transmitted, the output port fails to transmit at the required rate and incurs into an underrun error. This is more severe than the performance degradation described above because the packet is transmitted with an error and the receiver will have to discard the packet, causing in some cases the costly retransmission of the packet. The second case described above is most common when the switch is working in cut-thru mode. In this mode, all the output ports that need to transmit the packet will do so at roughly the same time because they are instructed to transmit the packet as soon as possible without waiting for the entire packet to be received.

BRIEF SUMMARY OF THE INVENTION

A packet memory system for selectively outputting received packets on one or more output ports. The packet memory system including a controller for controlling the output ports. Specifically, for packets of multicast or broadcast traffic that needs to be output from a plurality of the ports, the controller designates one or more reader ports that read the packet data from a packet memory such that the remainder of the ports are able to simply listen for the read packet data without performing a read operation.

A first aspect is directed to a packet memory system, the system comprises a non-transitory computer-readable packet memory comprising one or more memory banks for storing packet data of a packet input by the system, wherein the packet data as stored on the memory banks is organized according to one or more pages mapped to the memory banks, a plurality of output ports coupled with the packet memory and configured to selectively read the packet data from the packet memory and output the packet data out of the system and a controller coupled with the plurality of output ports for controlling which of the ports output the packet data, wherein if the packet data is to be output from two or more of the ports, the controller commands less than all of the two or more of the ports to cause the packet data to be read out from the packet memory and transmitted to all of the two or more of the ports. In some embodiments, the plurality of output ports and the controller are operating in a cut-thru mode such that each of the plurality of output ports begin to output packet data before the entirety of the packet has been received. In some embodiments, the controller commands all of the two or more of the ports to listen for and output the packet data after the packet data is read out from the packet memory based on a packet data identifier the controller sends to all of the two or more of the ports. In some embodiments, each of the less than all of the two or more of the ports causes a different part of the packet data to be read out from the packet memory. In some embodiments, the different part of the packet data of each of the less than all of the two or more of the ports is determined by the controller based on how the packet data is apportioned between the pages. In some embodiments, a quantity of the less than all of the two or more of the ports is determined by the controller based on a quantity of the pages on which the packet data is stored. In some embodiments, the controller selects the less than all of the two or more of the ports based on a congestion level of each of the two or more of the ports. In some embodiments, each of the plurality of output ports comprise a buffer that stores a list identifying one or more packets that have been assigned to be output by the port by the controller, but have not yet been output by the port, and further wherein the congestion level of each of the two or more of the ports is based on a current quantity of packets identified by the list of the buffer of the port. In some embodiments, the less than all of the two or more of the ports is exactly one of the two or more of the ports that causes all of the packet data to be read out from the packet memory. In some embodiments, the less than all of the two or more ports is exactly a first port and a second port of the two or more of the ports, and further wherein the controller commands the first port to cause a first portion of the packet data to be read out and the second port to cause a remainder of the packet data that was not included within the first portion to be read out. In some embodiments, the first portion is stored on one or more first pages of the pages mapped to the memory banks and includes the header of the packet data, and further wherein the remainder of the packet data is stored on one or more second pages of the pages mapped to the memory banks and includes the remainder of the packet data not included within the first pages.

A second aspect is directed to a controller stored on a non-transitory computer-readable medium and coupled with a plurality of output ports that selectively read and output packet data of a packet from a packet memory, wherein the packet memory has one or more memory banks storing the packet data, and further wherein the controller is configured to, if the packet data is to be output from two or more of the ports, command less than all of the two or more of the ports to cause the packet data to be read out from the packet memory and transmitted to all of the two or more of the ports. In some embodiments, the plurality of output ports and the controller are operating in a cut-thru mode such that each of the plurality of output ports begin to output packet data before the entirety of the packet has been received. In some embodiments, the controller is configured to command all of the two or more of the ports to listen for and output the packet data after the packet data is read out from the packet memory based on a packet data identifier the controller sends to all of the two or more of the ports. In some embodiments, each of the less than all of the two or more of the ports causes a different part of the packet data to be read out from the packet memory. In some embodiments, the packet data as stored on the memory banks is organized according to one or more pages mapped to the memory banks, further wherein the different part of the packet data of each of the less than all of the two or more of the ports is determined by the controller based on how the packet data is apportioned between the pages. In some embodiments, the controller is configured to determine a quantity of the less than all of the two or more of the ports based on a quantity of the pages on which the packet data is stored. In some embodiments, the controller is configured to select the less than all of the two or more of the ports based on a congestion level of each of the two or more of the ports. In some embodiments, each of the plurality of output ports comprise a buffer that stores a list identifying one or more packets that have been assigned to be output by the port by the controller, but have not yet been output by the port, and further wherein the congestion level of each of the two or more of the ports is based on a current quantity of packets identified by the list of the buffer of the port. In some embodiments, the less than all of the two or more of the ports is exactly one of the two or more of the ports that causes all of the packet data to be read out from the packet memory. In some embodiments, the less than all of the two or more ports is exactly a first port and a second port of the two or more of the ports, and further wherein the controller is configured to command the first port to cause a first portion of the packet data to be read out and the second port to cause a remainder of the packet data that was not included within the first portion to be read out. In some embodiments, the first portion is stored on one or more first pages of the pages mapped to the memory banks and includes the header of the packet data, and further wherein the remainder of the packet data is stored on one or more second pages of the pages mapped to the memory banks and includes the remainder of the packet data not included within the first pages.

A third aspect is directed to a method of operating a packet memory system. The method comprises storing packet data of a packet on one or more memory banks of a non-transitory computer-readable packet memory, wherein the storing of the packet data on the memory banks comprises organizing the packet data as stored on the memory banks according to one or more pages mapped to the memory banks, if the packet data is to be output from two or more of a plurality of output ports coupled to the packet memory, commanding less than all of the two or more of the ports to cause the packet data to be read out from the packet memory and transmitted to all of the two or more of the ports with a controller coupled to the output ports and outputting the packet data from each of the two or more of the ports with the two or more of the ports. In some embodiments, the plurality of output ports and the controller are operating in a cut-thru mode such that the outputting of the packet data by each of the two or more of the ports comprises beginning to output at least a portion of the packet data before the entirety of the packet has been received. In some embodiments, the method further comprises commanding all of the two or more of the ports to listen for and output the packet data after the packet data is read out from the packet memory with the controller based on a packet data identifier the controller sends to all of the two or more of the ports. In some embodiments, each of the less than all of the two or more of the ports causes a different part of the packet data to be read out from the packet memory. In some embodiments, the method further comprises determining the different part of the packet data of each of the less than all of the two or more of the ports with the controller based on how the packet data is apportioned between the pages. In some embodiments, the method further comprises determining a quantity of the less than all of the two or more of the ports with the controller based on a quantity of the pages on which the packet data is stored. In some embodiments, the method further comprises selecting the less than all of the two or more of the ports with the controller based on a congestion level of each of the two or more of the ports. In some embodiments, each of the plurality of output ports comprise a buffer that stores a list identifying one or more packets that have been assigned to be output by the port by the controller, but have not yet been output by the port, and further wherein the congestion level of each of the two or more of the ports is based on a current quantity of packets identified by the list of the buffer of the port. In some embodiments, the less than all of the two or more of the ports is exactly one of the two or more of the ports that causes all of the packet data to be read out from the packet memory. In some embodiments, the less than all of the two or more ports is exactly a first port and a second port of the two or more of the ports, further comprising commanding the first port to cause a first portion of the packet data to be read out and the second port to cause a remainder of the packet data that was not included within the first portion to be read out with the controller. In some embodiments, the first portion is stored on one or more first pages of the pages mapped to the memory banks and includes the header of the packet data, and further wherein the remainder of the packet data is stored on one or more second pages of the pages mapped to the memory banks and includes the remainder of the packet data not included within the first pages.

DETAILED DESCRIPTION OF THE INVENTION

In the following description, numerous details are set forth for purposes of explanation. However, one of ordinary skill in the art will realize that the invention can be practiced without the use of these specific details. Thus, the present invention is not intended to be limited to the embodiments shown but is to be accorded the widest scope consistent with the principles and features described herein.

Embodiments are directed to a packet memory system for selectively outputting received packets on one or more output ports. The packet memory system including a controller for controlling the output ports. Specifically, for packets of multicast or broadcast traffic that needs to be output from a plurality of the ports, the controller designates one or more reader ports that read the packet data from a packet memory such that the remainder of the ports are able to simply listen for the read packet data without performing a read operation. As a result, an essentially simultaneous attempt to accesses the packet within the packet memory by all of the output ports is prevented thereby increasing the efficiency of the system.

FIG. 1illustrates a packet memory system100on a packet processing device102according to some embodiments. As shown inFIG. 1, the packet memory system100comprises one or more output ports106coupled with a packet memory104and a controller108. The packet memory104comprises one or more memory banks110that each have one or more read and/or write ports (not shown) that enables data to be read out or written to the banks110each cycle. The banks110are coupled to each of the ports106such that each of the banks110is able to output data that is received by one, a plurality or all of the ports106. The ports106each comprise a port buffer116and are able to be a part of a packet memory access element112(e.g. a direct memory access block), wherein the packet memory access element112is able to further comprise one or more bank address elements114coupled to each of the ports106and at least one of the banks110. Specifically, the element112is able to comprise a bank address element114for each of the banks110. Alternatively, there are able to be more or less bank address elements114than the number of banks110. As a result, the each of the ports106is able to communicate with (e.g. read data from) each of the banks110via the associated bank address element(s)114and the packet memory access element112. In some embodiments, the bank address elements114are bank read address multiplexers (muxes). The controller108is able to perform any necessary modification of the packet, decide where to send the packet, and perform any traffic management necessary. The controller108is coupled with each of the ports106such that the controller108is able to send control and other types of data selectively to one or more of the ports106. Further, in some embodiments the controller108is able to monitor a status of and/or receive feedback data from the port buffer116of one or more of the ports106.

The packet processing device102is able to be a packet processing circuit and/or microchip. For example, the device102is able to be a switch microchip (e.g. top of rack switch) for a data center or other type of packet processing circuit or application specific integrated circuit. In some embodiments, the device102is a software defined network programmable microchip that is able to be programmed/customized to adjust the manner in which packets are processed. Alternatively, the device102is able to be other types of packet processing devices known in the art. The ports106, controller108and address elements114are able to comprise hardware, software or a combination of hardware and software, wherein the software is stored on a non-transitory computer readable medium of the device102. The packet memory104is able to comprise a non-transitory computer-readable medium such as ternary content-addressable memory. Alternatively, the packet memory104is able to comprise other types of memory known in the art or combinations thereof. The system100and/or device102is able to operate in a normal mode and a cut-thru mode. In the normal mode, the system/device wait until an entire packet is received before starting to output it. In cut-thru mode, the controller108and/or the output ports106transmit the packet as soon as possible without waiting for the entire packet to be received.

FIG. 2illustrates a link list of pages202for a packet and an exemplary mapping of the link list202to the memory banks110of the packet memory104according to some embodiments. As shown inFIG. 2, packet data of a packet is stored on one or more pages202mapped to the banks110of the packet memory104. In particular, each of the pages202is able to represent (or be mapped to) one or more entries of a plurality of the banks110. As a result, when a packet or a portion thereof is stored on one of the pages202, it results in the packet being stored in a plurality of non-sequential locations distributed across the banks110within the packet memory104that are mapped to that page. Often a packet will require multiple pages202in order to store the entirety of the packet. This list of pages202is known as a link list and is able to be used as a map or list of pointers that point to the locations where the packet is stored on the banks110of the packet memory104. Generally, a first set202aof one or more pages of the link list202will include the header of the packet whereas a second set202bof one or more pages of the link list202will store the body of the packet. Specifically, the header pages contain the header data that the control block processes and the body pages contain the body of the packet which is generally not altered by the device102. As the result, the pages202enable the packet data of each packet to be distributed across the banks110such that reading or writing the packet data from or to the banks110is more efficient.

Although as shown inFIG. 2, the header pages202aare mapped across two banks110and the body pages202bare mapped across three banks110, the pages202are each able to be mapped across more or less banks. For example, a page is able to be mapped to non-sequential entries of a single bank110or entries of any number of a plurality of banks110. Alternatively, a page202is able to be mapped to sequential entries of a single bank110A packet has associated a descriptor or token that in its basic form is able to be a pointer to the first page of the link list of pages202storing the packet. With this initial pointer, all the pages used by the packet are able to be retrieved in the same order they were used by traversing the link list202as each subsequent page includes a pointer to the location of the next page in the list202.

In operation, when the device/system102/100is in cut-thru mode, the controller108determines if a packet is a unicast traffic packet destined for output by a single target port of the ports106or a multicast/broadcast traffic packet destined for output by a plurality of target ports of the ports106. If it is determined that the packet is multicast/broadcast, instead of commanding all of the target ports106to attempt to read the packet data of the packet from the memory104, the controller108selects and commands only a subset of the target ports106to attempt to read the packet data. In some embodiments, the subset is only a single port106of the target ports106such that the single selected port106is commanded to access all of the packet data from the packet memory104. Alternatively, the subset is able to be a plurality (but not all) of the target ports106. In such embodiments, the selected ports106are able to each be commanded by the controller108to access a different portion of the packet data such that only after all of the port106have issued their requests is all of the packet data read out of the packet memory104. In particular, the packet data is able to be divided and/or allocated amongst the subset of ports on a page by page of the link list202basis such that each of the subset is assigned one or more pages of the link list202associated with the packet. For example, if the subset is two ports106, the controller108is able to allocate the pages202astoring header data of the packet to the first port106of the subset and pages202bstoring body data (or the remainder) of the packet to the second port106of the subset.

In some embodiments, the controller108selects which and/or the quantity of the plurality of target ports106to include in the subset randomly or according to a round robin protocol. Alternatively, the controller108is able to select which and/or how many of the plurality of target ports106are included in the subset based on a current congestion level of the target ports106. For example, the target ports106with the lowest levels of congestion are selected as reader ports to form the subset. In particular, the controller108is able to monitor, request and/or be transmitted feedback from each of the target ports106indicating a current level of traffic congestion. In some embodiments, the congestion level of each port106is based on a quantity of pending packets that have been assigned to be output by the port by the controller, but have not yet been output by the port as indicated by the port buffers116which store the command messages or tokens from the controller108indicating packet data that needs to be output from the port106. For example, the port buffers116are able operate according to a first in first out protocol, wherein identifiers (e.g. descriptors or tokens) of packets or packet data to be output is received by the buffer116and then only removed from the buffer116when the associated packet or packet data has been received and output by the port106. Thus, the quantity of identifiers stored in the buffer116represents a current backlog or congestion level of the port106. Alternatively, the congestion level is able to be based on other metrics and/or factors.

In some embodiments, the controller108is able to determine the quantity of ports (of the target ports) that are to be designated as the subset of reader ports106based on a size of the packet (e.g. number of pages storing packet, number of bytes), a number of different types of data of the packet and/or based on the current congestion level of the target ports106. For example, based on a congestion level of a first selected port106, the controller108is able to limit a number of pages of the packet assigned to the first port106and determine that one or more additional ports106are needed, wherein the same page number limitation and/or addition of selected ports106is able to be performed for each additional port106until all of the packet data has been assigned to a target port106thereby forming the subset. In other words, the higher the congestion level, the lower the number of pages and/or quantity of packet data that will be assigned to a selected target port106, wherein if not all of the data is able to be allocated amongst the currently selected ports106due to the congestion constraints, one or more ports106are able to be added as selected reader ports106.

Once the subset of target ports106has been determined by the controller108, the controller108sends a reader message to each of the subset. The reader message comprises a reader identifier, a packet identifier (e.g. descriptor or token), a port identifier, and/or a packet data identifier. The reader identifier indicates to the port106that it needs to issue a read access request to read out the packet data indicated by the packet data indicator from the location within the entries of the banks110of the packet memory104indicated by the packet data indicator. The port identifier identifies the port106to which the reader message is directed and thereby enables the port106to know the message is intended for that port106. The packet identifier uniquely identifies the packet and the packet data identifier identifies the packet data or portion thereof that the port106is being directed to read out from the packet memory104. For example, the packet data identifier is able to identify one or more of the pages of the link list202associated with the packet such that based on the locations within the banks110pointed to by the pages, the selected reader ports106are able to issue read access messages that cause the packet data stored on the identified pages to be read out from the packet memory104. In some embodiments, the port identifier is able to be omitted and/or the packet identifier and the packet data identifier are able to match or be only a single identifier. For example, if the subset is only a single port106, the packet identifier itself is able to be used to identify the packet data (e.g. via the associated link list202). Additionally, the packet identifier is able to be attached to all of the access requests and then all of the packet data as the data is read out and transmitted to all of the ports106on the device102such that all the target ports106are able to identify and output the packet data based on the attached packet identifier when it is received.

The controller108is also able to send listener messages to each of the target ports106that were not included within the selected subset. These listener messages are similar to the reader message except that the packet data identifier is able to be omitted and the reader identifier is able to be omitted and/or indicate that the port106is not a reader and instead only needs to monitor/listen to the output from the packet memory104for the packet data having an attached packet identifier that matches the identifier indicated in the listener message. As a result, the non-selected or remainder of the target ports106will not attempt to read the packet data from the packet memory104and instead will only listen/monitor for the packet data when it is read out from the memory104to all of the ports106based on the access attempts of the subset.

After receiving the reader messages, the selected target ports106issue a packet data request for the data at the entries of the banks110indicated by the packet data identifier and/or packet identifier as including the needed packet data. As described above, these reader access requests are able to include the packet identifier such that the packet data, when read out from the packet memory104, is able to have the packet identifier attached such that all of the target ports (the subset and the remainder) can receive and output the read out packet data by matching the packet identifier attached to the data to the packet identifier in the received reader/listener message. The selected subset of the ports106are able to issue as many read access requests to the packet memory104as needed to retrieve the packet data indicated by the controller108. For example, for the pages assigned to each port106, the port106is able to start with a first location within the memory104indicated by the first page of the assigned pages, and then proceed to a next location within the packet memory104indicated by the next page in the link-list202until all of the pages assigned to the port106have been issued access/read requests.

These requests are able to occur inside the access element112. Specifically, the request are transmitted from the subset of ports106to the bank address elements114associated with the bank110where the needed packet data is stored (as indicated by the pages202). The bank address elements114then arbitrate which ports106who issued a read access request will get access to the one or more read ports of associated bank110for that cycle. This arbitration is able to be independent or to occur independently for each address element114and therefore for each bank110. Subsequently, as described above, the read port of the accessed bank110propagates the packet identifier of the request to the packet data read out and this read out packet data is transmitted to all of the ports106on the device102. Thus, upon receiving the packet data, each port106is able to compare packet identifiers assigned to the port106with the propagated packet identifier attached to the packet data, and if they match, consume and output the data. As a result, all of the target ports106will consume the multicast/broadcast packet data and output the data directed by the controller108despite only the subset ports106actually requesting the data from the packet memory104. Thus, the system100provides the advantage of the contention to the banks110is decreased in multicast traffic and therefore the probability of packet underruns is removed or minimized especially during a cut-thru mode.

FIG. 3illustrates a method of preventing underrun in a packet memory system according to some embodiments. As shown inFIG. 3, the packet processing device102stores one or more packets on one or more memory banks110of the packet memory104at the step302. As described above, each packet is able to be stored on one or more pages of a link list202mapped to a plurality of locations in the packet memory104. The controller108determines if a packet is a multicast/broadcast packet that needs to be output from a plurality of target ports106at the step304. If the packet is multicast or broadcast, the controller108sends a reader command to a selected subset of the target ports106that instructs the each of the subset to read a portion or all of the packet data from the packet memory104at the step306. All of the target output ports106output the packet data upon receipt from the packet memory103at the step308. In some embodiments, the device102is in a cut-thru mode such that the outputting of the packet data by the target ports106comprises beginning to output at least a portion of the packet data before the entirety of the packet has been received. In some embodiments, the method further comprises, if the packet is multicast or broadcast, the controller108sends a listener command to a remainder of the target ports106that are not selected and instructs the each of the remainder to listen/monitor for and input the packet data when it is read out from the packet memory104by the subset. Thus, the method provides the advantage of reducing the read access traffic sent to the banks110of the packet data for multicast/broadcast packet data.

The packet memory system described herein has numerous advantages. In particular, the system provides the advantage of reducing the number of packet memory accesses to read the packet that need to be sent from the ports and thereby reducing contention for the bank read ports. Indeed, this in turn reduces the potential for packet underruns and helps port bandwidth performance. Further, the bandwidth of the packet memory is increased when a plurality but not all of the target ports are designated as readers such that an appropriate amount of parallel data accesses are able to be performed. In particular, the division of the packet data amongst the plurality of ports is able to help prevent even all of the selected ports from needing to access the same bank at the same time. Moreover, by utilizing congestion feedback from the ports, the controller is able to provide the benefit of better distributing the read access load amongst the target ports in addition to determining what quantity of ports are needed. Thus, the system again is able to reduce the potential for packet underruns and help port bandwidth performance.

While the invention has been described with reference to numerous specific details, one of ordinary skill in the art will recognize that the invention can be embodied in other specific forms without departing from the spirit of the invention. For example, although the different methods and operations described herein describe a particular order of steps, other orders are contemplated as well as the omission of one or more of the steps and/or the addition of one or more new steps. Moreover, although the methods and operations above are described herein separately, one or more of the methods and operations are able to be combined (in whole or part). Thus, one of ordinary skill in the art will understand that the invention is not to be limited by the foregoing illustrative details, but rather is to be defined by the appended claims.