Integrated memory for storing egressing packet data, replay data and to-be egressed data

An integrated egress/replay memory structure is provided with split rate write and read ports and means for managing at least three types of data moving into, through and/or out of the integrated memory structure, namely: (1) currently egressing packet data; (2) replay data; and (3) to-be egressed data. Additionally, a shared free space (4) is managed between the storage areas of the (2) replay data and (3) the to-be egressed data. The to-be egressed data (PdBx) is allowed to enter into (to be written into) a front-end raceway portion of the integrated memory structure at a rate which can be substantially greater than that allowed for corresponding egressing packet data (PdUx). Thus, even when egressing packet data that is ahead in line is shifting out toward a slow rate egress port, this slowing factor does not slow the speed at which the to-be egressed data (PdBx) can be shifted into the front-end raceway portion. A shared free space memory area is maintained between the storage areas of the replay data (PdAx) and to-be-egressed data (PdBx). When a positive acknowledgement (ACK) is received from the destination of already-egressed data (of the After-Transmission Data, or PdAx), the corresponding replay storage area (the area storing the acknowledged PdAx data) can be reallocated for use as an empty part of the raceway portion.

FIELD OF DISCLOSURE

The present disclosure of invention relates generally to networks that transmit information in packet format. The disclosure relates more specifically to systems and network devices that can employ ingress and egress flow rates of differing values for different communication channels and yet more specifically to a head-of-line blocking problem which may occur in such multi-rate systems and to a delayed nullification notice defect which may also arise in such multi-rate systems.

CROSS REFERENCE TO CO-OWNED APPLICATION

The following copending U.S. patent application is owned by the owner of the present application, and its disclosure is incorporated herein by reference:

DESCRIPTION OF RELATED ART

Use of digitally-encoded packets in data communication and network systems is well known. Typically each packet signal that is being transmitted over a network link is layered like an onion to have header-type outer shell sections, a payload or message core section and one or more error correction sections that cover various parts of the core or outer shells. Packets may be transmitted individually or as parts of relatively continuous streams or bursts depending on quality of service requirements and/or availability of transmission links. When packet signals are transmitted from a source device to a receiving device, the packet signals that arrive at the receiving device typically progress within the receiving device through a physical interface layer (PL—e.g., one including a SERDES interface), and then through one or both of a data link layer (DL) and a transaction layer (TL). The physical interface layer (PL) may include means for serializing and deserializing data signals (SERDES) and means for recognizing the start and end of each ingressing packet. The data link layer (DL) may include means for managing error checking, error correction (e.g., CRC, ECC, etc.) and/or managing packet ordering and verifying completion of sequences of interrelated packets. Among the functions normally included in the DL is that of verifying that an egress side link partner (a receiving device) correctly received a transmission sent from the DL of a current source device. The transaction layer (TL) may include means for parsing (peeling the onion skin layers of) different parts of each kind of post-DL packet so as to get to desired portions of the payload data or message data for respective processing. Specific processing of TL output data may be carried out by a so-called, File Data Processing Layer. Before it is sent to the File Data Processing Layer, payload and/or message data from sequentially ingressing packets may sometimes need to be reordered for purposes of reconstructing an original data sequence different from the ingress sequence, where the original data sequence may, for example, be required for reconstituting a rasterized graphic image. To this end, unique sequence numbers are often embedded in successive ones of ingressing or egressing packets so that desired ordering of data can be achieved in the receiving device even though some packets may have arrived out of order, for example due to link error and subsequent replay (re-transmission) of an error-infected one or more packets.

Packet signals leaving a source device typically progress in the reverse order within the source device, namely, first by moving outgoing payload data from the file layer of the device and through the transaction layer (TL) of the device for attachment of transaction control code to the file layer code, then through the data link layer (DL) for attachment of code such as sequence number code and error check code thereto, and finally through the sender's physical interface layer (PL) for encoding into a predefined serial transmission format and for output onto a physical transmission media (e.g., a high frequency cable or printed circuit strip or an optical fiber or wireless transmission in some cases).

Because an egressing packet may fail to reach its targeted destination (i.e., its link partner) intact for any of a number of reasons (i.e., noise on the link flips one or more bits and thus induces error), a backup copy of each egressing packet is often temporarily stored in a retry buffer (RB) located in the DL layer of the source device for a short while. If the destination device sends a retry request (i.e., a NAK signal such as a NAK data link packet) and/or fails to timely acknowledge receipt, the backup copy is resent (replayed) from the retry buffer (replay buffer).

A common design configuration structures each retry buffer as a one speed buffer. Packet data (Pd)151bthat is being transmitted out of the egress port (i.e.,171) advances through a short rate-matching FIFO151aand then through a data-copying structure151hand a multiplexer151con it way out to the corresponding egress port (i.e.,171). The average advancement rate of this “being-transmitted” data signal151b(also described here as “under transmission” or Ux signal) through the rate-matching FIFO151amatches the egress rate (i.e., 1 B/cc) out of the corresponding egress port (i.e.,171). The rate-matching FIFO151amerely smoothes out any burstiness that might be present when the data comes out of the switch fabric150. The data-copying structure151hcopies passing through data151binto a replay-storing memory buffer151d. Data stored in buffer151dmay be referred to as packet data after transmission, or PdAx. If a negative acknowledge signal (NAK) later comes back from the link partner of port171, a copy of the backup data that had been saved in the replay-storage memory151dis output therefrom at the port's egress rate (without yet emptying out the replay memory151d). When a positive acknowledge signal (ACK) comes back from the link partner, the original backup data that had been saved in the replay-storing memory151dis erased thus freeing up space in the replay buffer151da next stream of “being-transmitted” packet data (PdUx) to be copied into the replay-storage memory151dto thereby become replay backup data (PdAx).

Two back pressuring structures,151fand151g, are shown associated with the rate-matching FIFO151aand the replay-storing memory151d. The first back pressuring structure151fsends back pressure signals to dispatch scheduler170if the corresponding rate-matching FIFO151afills to beyond a predefined safe capacity. The second back pressuring structure151gsends back pressure signals to replay controller155if the corresponding replay buffer memory151dfills to beyond a predefined safe capacity.

A problem known as head-of-line blocking can develop as follows. If a first-in-queue packet is to egress out of a slow egress port and a next-in-queue packet is scheduled to egress next out of, for example, a faster second egress port (where that second egress port could possibly one that is empty because it ran out of packet data and thus the second port uselessly idling), the next-in-queue packet must wait for the slower packet to finish moving out first at its port-dictated slow rate before the next-in-queue packet has its turn. The slower packet steps out at its relatively slow rate into and through the “being-transmitted” rate-matching FIFO151aand through copier151hfor copying into respective replay buffer memory151d, and only then, when the end of the slower packet has cleared out of the ingress-side queue131, can the next-in-queue packet move out at its faster rate to and through its respective replay buffer structure (e.g.,152) for egress through its respective and faster destination port (which second port172could have been empty and uselessly idling up until now). In other words, the slowest tortoise in the queue delays all the hares (rabbits) waiting behind him. It is to be understood that this problem regarding head-of-line blocking is not limited to situations where the second-in-queue packet is going to the fastest egress port and the first-in-queue packet is going to the slowest egress port. That is an extreme situation. The problem is present to one degree or another any time a first-in-queue packet is heading towards a relatively slow egress port and there are one or more next-in-queue packets being held up by the slowness of egress of the first-in-queue packet. Network efficiency is decreased when the head-of-line blocking problem prevents or slows down the rate at which currently empty egress ports (and thus uselessly idling egress ports as well as their associated network links) are supplied with new data.

A related drawback of systems such as the one (100) shown to allow for variable egress rates may be termed as a late notification of nullity defect. Error checking conventionally does not take place until the last part (115c) of a packet ingresses into an ingress receiving side (i.e., ingress buffer) of a packet processing device. If an error infected packet happens to be of a slow tortoise variety due to the relative slowness of its destination link (in other words, because it is being routed out through an egress pipe of narrow bandwidth) the report regarding detection of error at the end of that slow moving packet does not get relayed through the routing fabric (e.g., switch fabric) and to the egress side of the device any faster than the rate of the relatively narrow egress pipe. Thus, even though knowledge of the error might exist at the ingress side, that information is not immediately relayed to the egress side, but instead waits till the tail end remainder (115c) of the slow tortoise packet makes its way across the routing fabric to the egress side. This is generally not recognized as being a defect, but it is one, as shall become apparent from the following detailed discussion.

SUMMARY

Structures and methods may be provided in accordance with the present disclosure of invention for improving over one or more of the above-described, head-of-line blocking problem and slow notice of nullification defect.

In one embodiment, an integrated egress/replay memory structure is provided with split rate write and read ports and means for managing at least three types of data moving into, through and/or out of the integrated memory structure, namely: (1) egressing packet data—also referred to herein as PdUx; (2) replay data that is temporarily saved “After” transmission—also referred to herein as PdAx; and (3) to-be egressed packet data that is saved “Before” transmission—also referred to herein as PdBx. Additionally, a shared free space (4) is managed between the storage areas of the (2) replay data—the PdAx and (3) to-be egressed data—the PdBx. The to-be egressed packet data (PdBx) is allowed to enter into (to be written into) a front-end raceway portion of the integrated memory structure at a rate which can be substantially greater than that allowed for egressing packet data (PdUx). Thus, even when egressing packet data that is ahead in line is shifting out toward a slow rate egress port, this slowing factor does not slow the speed at which the to-be egressed data (PdBx) can be shifted into and saved in the front-end raceway portion. A shared free space memory area is maintained between the storage areas of the replay packet data (PdAx) and to-be-egressed packet data (PdBx). When a positive acknowledgement (ACK) is received from the destination of already-egressed data (of the “After”-Transmission Packet Data, or PdAx), the corresponding replay storage area (the area storing the acknowledged PdAx) can be erased (optional) and reallocated for use as an empty part of the raceway portion, thereby increasing the length of the raceway portion and allowing more to-be-egressed data (PdBx=Packet Data “Before” Transmission) to enter into the raceway portion at relatively high speed. Also, if to-be-egressed-but-subsequently-nullified data (null-PdBx) enters into the raceway portion, the corresponding raceway storage area can be erased (optional) and reallocated for use as an empty part of the raceway portion even before such garbage PdBx material is allowed to egress, thereby increasing the empty length of the raceway portion and allowing yet more to-be egressed data (which subsequent PdBx is typically not nullified) to enter into the raceway portion at relatively high speed. This high speed write-in option helps to alleviate a head-of-line blocking problem that may otherwise arise in ingress-side FIFO's as shall be seen from the below detailed description.

An ancillary benefit to having rapid ingress through the switch fabric despite the fact that the egress bandwidth may be much slower is that notification of error in an ingressing packet gets through to the egress side much quicker; and then an early termination of transmission may be effected at the egress side.

Other aspects of the disclosure will become apparent from the below detailed description.

DETAILED DESCRIPTION

FIG. 1is a block diagram of a conventional packet switching device100that may be embedded within a network or communications system (not explicitly shown) for selectively routing packets between 3 or more ports of the device (i.e., ports171-174). The conventional packet switching device100has a packet data dispatching unit140which is intentionally drawn out of its actual position in the illustrated circuitry so as to help explain a root cause of a head-of-line blocking problem that may occur for example between packets131aand131bof an ingress FIFO131. Details regarding this head-of-line blocking problem will be provided shortly.

Major sections of the illustrated device100are: a plurality of ingress data pipes (110, optionally with each having a variable ingress rate); an ingress data buffering memory (130); a switch fabric (a packet routing fabric,150); a plurality of replay buffers (151-154); and a plurality of egress data pipes (160) coupling to a respective set of I/O ports171-174. At least the egress data pipes160are of a variable bandwidth type. Typically the ingress data pipes110will also be of a variable bandwidth type, and in typical cases the ingress data pipes110and egress data pipes160will pairwise share respective bidirectional I/O ports. Alternatively, the egress ports171-174may be unidirectional output ports.

Packet data that is ingressing into a data receiving part of the device100will typically get routed into a parallel set of ingress buffers (e.g., First-In, First-Out buffers)131-133before being further processed and then being output via one or more egress pipes161-164to respective ports171-174. The ingress buffers131-133act somewhat like shock absorbers in that each absorbs and smoothes out the often-bursty nature of ingressing packet streams on each respective channel of ingressing data and then the respective FIFO stores the data until the ingressed data is ready to be processed (i.e., dispatched through the switch fabric150) and thereafter egressed. Such a shock absorbing operation does not however, alter the average rate at which packet data enters each given ingress buffer131-133. Ingress rate is generally controlled by the link partner (not shown) at the ingress side and by back pressure or credit tokens sent back in return-flow packet s (116) to the link partner from the data receiving device (100) based on the amount of free space available in its ingress buffer131-133. A conventional paradigm configures all the ingress receiving buffers of a communications device (i.e.,100) to be of the same depth and width. A conventional paradigm does not account for the possibility of variable bandwidths on the ingress and/or egress channels. In other words, all the ingress buffers of a conventional approach have a same data length per stored word (number of bits per word) and a same number of storage locations between ends (a same depth for each of the plural buffers) irrespective of channel or pipe bandwidth. Also, conventional egress processing assumes that all egress channels have roughly the same output rate and all egressing packet blocks or streams will exit the front-end FIFO's131-133at relatively same, smooth and continuous rates rather than as sporadic bursts each having a different egress rate depending on the egress pipe or egress channel to which the ingressing packets are directed (or on the egress pipe or egress channel to which post-processing packets are directed, where the post-processing packets are derived from the ingressing packets).

Recently, a number of communication protocols have started gaining favor wherein programmably or dynamically variable data rates are supported for plural channels. Included among these emerging protocols are the PCI-Express™ protocol and the HyperTransport™ protocol. These relatively new, industry standardized protocols allow different logical channels to each have a different, programmably-established or dynamically-defined channel configuration, including a different maximum data transmission rate. For example, one logically-configured communication channel may be programmably or dynamically formed as an aggregation of many, relatively slow sub-channel resources (i.e., PCI-Express “lanes”) while another logically-configured channel may be variably formed to have one or just a few, such slow or basic sub-channel resources (i.e., lanes). The data bandwidth of the channel containing a greater number of basic sub-channel resources (such as egress pipe162which is shown to have 16 lanes—in other words, to have a “by 16” bandwidth configuration which is denoted as Ebw=×16) will generally be substantially larger than the data bandwidth of another channel having just one or few sub-channel resources aggregated together (e.g., egress pipe161which is shown to have a “by 1” configuration denoted as Ebw=×1). A trade off is typically made between the number of sub-channel resources allocated to each communication channel, the bandwidth of each such channel and the number of channels (virtual or hard) that device100supports. In the realm of PCI-Express™, the aggregated variable bandwidth channel resources are sometimes referred to as logical “ports” or “links” and the lowest common speed, sub-channel resource at the physical layer level is often referred to as a “lane”. Lanes may be selectively aggregated together to define higher speed ports in PCI-Express systems. Ports may be selectively bifurcated to define larger numbers of virtual channels per port albeit with lower bandwidths per virtual channel. A packet routing device will generally have a finite number of lowest common speed, sub-channel resources (i.e., lanes) and configuration software may be used to determine how to allocate this finite number of resources to different ports so as to thereby optionally provide some device ports with more bandwidth than others.

More specifically, when a PCI-Express™ network is being adaptively configured or re-configured during network bring-up or reboot for example, the associated software determines how many lanes (subchannel resources) to assign to each PCI-Express™ “port” or PCIe logical “link” (—the terms PCIe port and PCIe link are sometimes used interchangeably although here “port” per se will refer to an input and/or output terminus of either a communications device or a memory unit—) so as to thereby define the maximum data rate supported by that PCI port. For example, a first PCIe port (e.g., port173ofFIG. 1which is shown to include a ×8 egress pipe162) may be programmably configured to consist of an aggregation of 8 basic hardware lanes with a lowest common bandwidth per lane being 2.5 Gb/s (Giga-bits per second), thus giving the ×8 first Port an aggregated bandwidth of 20 Gb/s. That first port (173) can support a corresponding single channel of 20 Gb/s bandwidth or multiple virtual channels with lower bandwidths that can add up to as much as 20 Gb/s. At the same time, a second PCIe port (e.g., port174which has a ×2 egress pipe164) can be programmably configured during network reconfiguration to consist of an aggregation of just 2 basic lanes, thus giving that ×2 second Port174an aggregated bandwidth of 5 Gb/s. A third PCIe port (e.g., port171which has ×1 egress pipe161) can be programmably configured during the same network reconfiguration to consist of just one lane; thus giving that ×1 Port171a bandwidth of just 2.5 Gb/s. In a subsequent reconfiguration, the illustrated first through fourth ports171-174may be reconfigured differently due to flexible resource negotiations that can take place during each network reconfiguration session.

In a conventional PCI-e design that is directed to management of egressing packet traffic, it is often assumed that all egress channels are of roughly the same bandwidth and all egressing packets are egressing out on a roughly smooth, same rate basis through their respective egress channels. This can create inefficiencies and problems as will become clearer shortly.

Represented along row110(bottom left corner ofFIG. 1) is a first plurality of logical transmission pipes111-11N that are each associated with a respective aggregation of physical transmission media. Ingress pipes111-11N respectively conduct signals from the respective data source devices (external link partner devices similar to100, but not shown inFIG. 1) to an ingressing-data side (data receiving side) of the data buffering memory area130of device100. In practice the aggregated physical transmission media and/or logical data transfer pipes111-11N may appear united as a single coaxial cable or a single optical fiber or a high frequency transmission strip on a printed circuit board coupled to a physical media interface circuit followed by SERDES circuitry (serializing and de-serializing circuitry—not shown). Data transmission may be multiplexed spatially, temporally and/or by code division multiplexing over the unified media so as to implement plural transmission channels. In one embodiment, all the illustrated data pipes111-11N,161-164can carry data that is multiplexed over a single, bidirectional optical transmission line prior to being demultiplexed and de-serialized into parallel electrical signal flows. In order to graphically illustrate certain aspects, however, the transmission media/pipes111-11N and161-164(which can be bidirectional media/pipes that are pairwise merged together) are schematically shown as being separate wide, narrow or medium width data pipes. Width on the egress side ofFIG. 1(the right side) indicates bandwidth in this schematic representation. Transmission pipe162for example is shown to be a relatively “fat” data flow pipe which means that pipe162has been configured to handle a large output bandwidth from device100. In contrast, transmission pipe161is shown as a comparatively thinner data flow pipe which means that pipe161handles no more than the smaller ×1 output bandwidth for data egressing out of device100. Similarly, transmission pipe163is shown as a medium width data flow pipe that is configured to handle a relatively medium, ×8 output bandwidth for data egressing out of device100. The fourth egress pipe164is shown as another relatively thin data flow pipe (a ×2 lanes configuration). Ingress pipes111-11N may be similarly configured in a variable manner to have respective narrow or wide ingress bandwidths, IBW1-IBWNalthough this is not shown by pipe width. In one embodiment there is a physical match in terms of lanes assigned to a given ingress pipe (i.e.,111) and to its counterpart egress pipe (i.e.,161). The bandwidths of virtual ingress and egress channels may still differ however. Bus118provides coupling between the ingress pipes111-11N and real or virtual write ports121-123of respective ingress FIFO's such as131-133.

Shown at115, next to the ingress pipes110, is an exemplary data packet having a header section115a, a payload section115band an error checking and/or correcting section (i.e., CRC or ECC)115c. Typically the header section115acontains length information indicating the length of the packet data to follow behind up to and possibly including the tail end error checking and/or correcting section115c. Typically such an error checking and/or correcting section115cis located at or very near the tail end of the packet body115so that an on-the-fly generated error syndrome can be compared with the last arriving CRC or ECC code115c. It is to be understood that each of pipes111-11N and161-164carries digital data packets similar to115except that the specific structures, lengths and/or other attributes of packets in each pipe may vary from application to application. (For example, some packets may not include a CRC or ECC section like115c. Moreover, some packets may be used for providing messaging only between the data link layers (DL) or transaction layers (TL) of link partner devices and may not simultaneously carry payload data for the file data layers.) Under some communication protocols, a source device (not shown, but understood to be a link partner with device100and connected to100via pipes111and161for example) first requests access to a network pathway that can couple the source device to the corresponding ingress pipe (e.g.,111) of device100. A system domain controller (not shown) grants that request, and the source device then streams a continuous sequence of packets (for example, packets131a,131bcarrying respective payloads of source data) through the granted network pathway. When finished, the source device (not shown) will typically relinquish its use of the pathway so that other source devices (or reply-completion devices) can request and obtain use of the relinquished network resources for their transmissions. As such, it is advantageous to have a packet processing device (i.e.,100) that finishes its part of a packet routing and/or other packet processing operation as quickly as possible so that network resources can be quickly relinquished for time-shared use by other routing and/or processing jobs. However, it will be shortly seen that the architecture of device100can disadvantageously create a roadblock to such quick processing. Device100has a replay buffer structure defined by replay buffer structures151-154(wherein incidentally, memory cells of the rate matching FIFO's151a-154do not provide any storage for replay data) whose limited pass-through rates—through copying structures151h-154h—can lead to the undesirable head-of-line blocking problem. The replay buffer structures can also give rise to a phenomenon known as late notification of error as will also be explained.

Data packets (e.g.,131a,131b, . . . ,133b) that are received from the respective ingress pipes111-11N appear at a data-input side of memory region130as respective write data flows121-123for example. An ingress routing means (not shown, but understood to couple to a write address port of unit130) may be provided for directing the respective data flows121-123to corresponding FIFO buffers131-133within memory region130. In accordance with conventional FIFO configuration schemes, each of FIFOs131-133has a same data width (bits per storage location) and a same depth (total storage capacity). In accordance with the above cited and co-pending patent application (U.S. Ser. No. 11/390,754 whose disclosure is incorporated here by reference), each of FIFOs131-133is a virtual FIFO with a variable memory capacity (e.g., elastic depth) that adaptively conforms at least to the bandwidth of a specific ingress pipe111-11N serviced by that FIFO. The depth numbers (#1, #2, #3) given for FIFO's131-133inFIG. 1represent corresponding numerical values which can be the same or different from one another. The optional elasticity of FIFOs131-133(and thus optional variation of values #1, #2, #3) per U.S. Ser. No. 11/390,754 will generally not affect the egress operations described herein. However, the converse is not true. The egress operations described herein with regard toFIG. 2may advantageously reduce the amount of ingress depth (if any) that is needed for a given ingress FIFO (e.g., the Depth=#4memory space used by FIFO233ofFIG. 2as compared to the Depth=#3memory space needed by FIFO133ofFIG. 1) and therefore this interplay between ingress FIFO depth and use of the integrated memories approach ofFIG. 2is mentioned here as a beneficial aside that can arise from use of the integrated egress/replay memory structure described herein. Also, a so-called cut-through operation of the ingress side FIFOs131-133may give rise to a late error notification defect as shall be detailed below. Thus operations of the ingress and egress sides of device100can affect one another and it is worthwhile to understand both sides.

In the illustrated example ofFIG. 1, it is assumed that the respective depth values, #1-#3of respective ingress FIFO's131-133have been fixedly designed or adaptively reconfigured to be roughly “just right” (neither too much nor too little) for matching the expected data input rates seen on their respective ingressing data flow pipes111-11N. However, this alone does not prevent a head-of-line blocking problem that can develop in each of the ingress FIFO's131-133.

More specifically and for purpose of example, it is assumed that packet131acontains header information routing it to egress point E1(associated with narrow egress pipe161) and that the next-in-queue packet131bof FIFO131contains header information routing it to egress point E2(associated with the much wider egress pipe162). Assume further, although it is not shown, that first packet131ahas a relatively long payload section (like115b) with its ECC or CRC code (115c) very far back in FIFO131or not yet even ingressed into FIFO131while the second packet131b(when it finally gets into FIFO131behind the tail end115cof packet131a) has a substantially shorter payload section. However, because the first packet131a(the one destined for slower egress point E1) is ahead in the queue (in FIFO131) of the next-in-line packet131bwhere the latter is destined for the faster egress point E2, the substantially shorter payload data of the second packet131bwill have to wait until the entirety of the longer payload of first packet131atrickles slowly out of FIFO131at the tortoise-like rate dictated by narrow egress pipe161before the payload data of the second packet131bcan zoom out at the substantially faster, rabbit-like egress rate allowed by the configuration of wide egress pipe162. This is an example of head-of-line blocking. The packet131awhich is shifting out for egress from the relatively low bandwidth port171(Ebw=×1) blocks the next-in-line one or more packets (i.e.,131bwhich is to shift out to the relatively higher bandwidth port172having an Ebw=×16) and thus all the back of line packets in FIFO131have to suffer a prolonged waiting period just because the front-of-line packet131ahas been directed toward egress from a relatively low bandwidth port (i.e.,171whose egress bandwidth in one embodiment is 1 byte per clock cycle or 1 B/cc).

FIG. 1is strange in that often the packet data dispatcher140is positioned between the ingress memory130and the switch fabric150. Unit140was drawn outside of its usual position to better illustrate a point. Dispatcher140is controlled (via line179) by an egress dispatch scheduler170where the latter scheduler determines when and at what rate data will be dispatched from the output side (data reading side) of ingress memory130for subsequent routing through switch fabric150and delivery to a respective one of replay buffer structures (retry buffer structures)151-154. Dispatcher140is shown connecting to the read address input of memory unit130by way of line139for determining which data will be dispatched and also by way of line138for providing read enable and/or other controls to memory unit130. The average rate of dispatch conventionally matches the average rate of egress. Back pressure signals151f-154foutput by the rate matching FIFO's151a-154aand supplied to the dispatcher170as signals151f-4fhelp to guarantee that the dispatcher170will not outpace the bandwidths of the respective egress ports171-174.FIG. 1shows the packet dispatcher140as if it were positioned between the switch fabric150and the rate matching FIFO's151a-154a(although this is not usually the case) so that the conventionally required match of average throughput bandwidths between dispatch switch147and replay read switches157-159, etc., can be better seen. Both data sampling switches,147and157, are operated at the same average egress bandwidth (i.e., =×1 in the illustrated case). Post-routing egress data that passes through sampling switch147enters the short, rate-matching FIFO151aof replay buffer structure151at the ×1 bandwidth rate and exits as a Packet-Data-Under-Transmission signal (PdUx151b) by way of a data-routing multiplexer output path151cfor coupling to egress point E1at the same ×1 bandwidth rate. To emphasize the point, the second sampling switch is shown at157and understood to be operating at the same Ebw=×1 average bandwidth. During transmission, the same read-out data (e.g.,141) is copied at the Ebw=×1 average bandwidth rate into a replay buffering memory denoted as151d. Packet data that is temporarily stored in this replay buffering memory is referred to herein as Packet-Data-After-Transmission (PdAx) and it too is identified by reference numeral151d. If the egress-side link-partner (not shown) of port171sends back a negative acknowledgement (NAK) to device100, after the initial packet data signal (PdUx151b) went out, the temporarily stored PdAx back up data151dis copied out (not erased just yet) from the replay buffering memory151dand transmitted via path151eand via multiplexer151c(which mux has an output line designated by the same151creference number) for coupling to the egress point E1and repeated output at the ×1 bandwidth rate through pipe161and port171to the link-partner that sent the NAK signal. In this way, if noise or some other anomaly momentarily infected the network link that connects port171to the link-partner (not shown), the copy151dof the earlier played data151b(the first-played PdUx signal151b) can be easily replayed out of the egress pipe without consuming switch fabric bandwidth.

Although operation of replay buffer structure151has been described in terms of the data itself moving into and through the replay buffering memory151d, artisans skilled in the art will appreciate that more typically the same effect may be accomplished by advancing read and write pointers at same rates around a circular buffer while the data stays put in its original storage location in memory151duntil overwritten by new data. The replay buffers controller unit155is operatively coupled by way of control line155ato the replay buffer structures151-154for managing the read and write pointers of playback memory151das well as the data read and write operations and the selective data routing through multiplexer151c. The replay buffers controller unit155will additionally receive the back-pressure signals151g-4gfrom the replay memory buffers151d-154d. If egressed data has not been ACK'ed by the link partner of port171and buffer151dfor example fills to beyond its predefined safe capacity, the controller unit155will receive the back-pressure flags151gand instruct the replay buffer151dto not accept the writing of new data (151b) into it until the data backup problem is resolved. As is known by those skilled in the art, in place of back-pressure flags, signals151fmay instead constitute slack space advisements (free space credit values) indicating how much free space is available in corresponding replay buffer151d. Such slack space advisements are typically used in PCI-Express systems.

A similar arrangement is shown for the case of the second replay buffer structure152. The Packet-Data-Under-Transmission signal (PdUx2, also denoted as152b) enters the rate-matching FIFO152aat the same rate (Ebw=×16) that data exits from the data-routing multiplexer output path152cfor coupling via sampling switch158to egress point E2. During the first time read-out, a copy of the same data signal, PdUx2 is stored into the replay buffering memory denoted as152dand thus becomes denoted as the saved Packet-Data-After-Transmission (PdAx2) that remains stored in the replay storage area152dat least until a positive acknowledgement of receipt (ACK) is received from the link-partner (not shown) that couples to device port172. If on the other hand, that link-partner sends back a negative acknowledgement (NAK) to device100, then a copy of the still stored PdAx2 data (152d) is routed via path152eand via mux152cat the Ebw=×16 rate to egress point E2for a second time output through pipe162and through port172to the link-partner that sent the NAK signal. In this way, if noise or some other anomaly momentarily infects the network link that connects port172to the link-partner (not shown), a copy of the earlier egressed packet signal PdUx2 (152b) can be easily replayed out of the egress pipe without consuming switch fabric bandwidth. Line155bof controller155carries the ACK and NAK signals from the respective link partners to the replay buffers controller unit155. In one embodiment, if a given link partner fails to send an ACK within a predetermined time-out period, the replay buffers controller unit155treats that situation as if a NAK had been received and proceeds to replay a copy of the saved PdAx data out to the link partner that failed to provide a timely ACK signal.

Operations for the third and fourth replay buffer structures153-154are substantially similar except that structure153operates at the Ebw=×8 bandwidth rate and structure154operates at the Ebw=×2 bandwidth rate as is indicated inFIG. 1.

For purpose of completeness, two other attributes should be mentioned; nullifications (155c) and return packets116returned by link partners. Return packets116may contain slack advisement signals instead of back-pressure flags for signaling how much storage slack is left in the ingress side of the slack advising device (e.g.,100). With regard to late nullification, consider the case where an unusually long ingressing packet (i.e.,132a) enters the ingress data buffering memory130. It is typically necessary for the whole of that extra-long packet, including its tail end (132err/115c) to have entered through its respective ingress pipe (i.e.,112, not shown) before error checking can be performed at the ingress side of device100and it can be determined if the packet (132a) contains an uncorrectable error. If yes, a true nullification flag is generated for that error infected packet at the time the tail end (132err) ingresses into its respective ingress FIFO (i.e.,132). The then-generated nullification flag travels with the tail end data of the packet through the switch fabric150and into the replay buffer structure (i.e.,154) associated with egress of that error-infected packet (132a) through its corresponding destination pipe (i.e.,164where Ebw=×2). By the time the nullification flag is generated however, and passed through the switch fabric150to the egress side of the device100, much of the error-infected packet data may have already been transmitted out through the relatively slow egress pipe (i.e.,164), particularly if an early cut-through operation is in progress. (Early cut-through is routinely used to transmit not-yet checked packet data when unusually long packets i.e.,132a, are moving through and the egress side link partner has free space for absorbing the not-yet checked packet data.) This transmission of error infected packet data will ultimately be seen; when the late arriving nullification flag finally arrives at line155cof controller155, to have been a waste of energy and time because the transmitted data is garbage. In a conventional device, when a true nullification flag finally arrives at the egress side controller155it causes the PdAx copy of the same packet to be dropped or purged from the replay buffer (154d) because it is finally known that this PdAx portion (154d) is garbage. However, during the time before the asserted nullification flag finally arrives at the egress side controller155, the garbage data (i.e.,154d) sits in storage space of its respective replay buffer structure (i.e.,154) and thereby consumes storage area that might have been put to better use over that prolonged duration. In the conventional design, it is too late and/or too cumbersome to try and terminate transmission of the errant tail end data portion PdUx4 then passing through the rate-matching FIFO154aand heading154btowards the link partner. It is easier to just let that error-infected tail end (132err) simply flow through. As such, even after it is known the data has failed the error check (CRC or ECC), the limited bandwidth of slow egress pipe164is nonetheless further wasted for transmitting more garbage data, typically to the time that the bitter tail end (132err) of the error-infected packet132aflows through. The limited bandwidth of egress pipe164is thus not used for a potentially better purpose of transmitting the potentially valid next packet,132b, until all of the first-in-line but defective packet132ahas been fully transmitted out to the link partner on the other end of egress pipe164.

Consider next the case of wide pipe162. Assume that the destination link partner device (not shown) has many such wide pipes feeding into it and only a few narrow pipes feeding out. The destination device may become overwhelmed if data ingresses into it faster than the data can egress out of that link partner. Before that happens, the about-to-be overwhelmed link partner typically starts sending true backpressure flags (or slack tokens with low or zero credit amounts) to device100in feedback packets like116and via feedback path156. The backpressure flags or credit tokens flow to scheduler170for example via connection138. In response, the scheduler170reduces the number of dispatches it grants per unit time to packets (i.e.,131b) heading towards the about-to-be overwhelmed link partner. Similarly, if the scheduler170detects via connection138that one of FIFO's131-133is about-to-be overwhelmed by too much incoming data, scheduler170will cause true backpressure flags (or low credit slack advisements)156ato be inserted into feedback packets (116) heading back to the respective ingress-side link partner that is feeding data towards the about-to-be overwhelmed ingress FIFO (i.e.,132). One or both of buffer slack advisements and backpressure flags may be used to dynamically control traffic flow densities heading towards various buffers. In PCI-Express systems, a so-called flow-control credit exchange process is used to dynamically manage data flow rates between link partners.

One way to reduce the frequency at which true backpressure flags (and/or credit-reducing slack advisements)156aare sent from device100to its ingress side link partner is to provide deeper ingress FIFO's in within memory region130. However this consumes scarce memory space. An alternate way is too output data from the read ports141-143of the FIFO's131-133at a faster rate so that data does not accumulate excessively and/or too often in the ingress FIFO's131-133. It will now be shown how the latter operation of speeding up data output from the ingress FIFO's131-133can be accomplished even if the corresponding egress pipe (i.e.,161or164) to which packet data is being directed is a relatively narrow and thus slow one.

Referring toFIG. 2, shown is a packet switching device200in accordance with the present disclosure. Where practical, like reference symbols and numbers in the “200” century series are used for elements ofFIG. 2which correspond to but are not necessarily the same as the elements represented by similar symbols and reference numbers of the “100” century series inFIG. 1. As such, an introductory description of many elements already described inFIG. 1is omitted here. Device200is understood to include a plurality of ingress data pipes like110, and optionally with each having a variable ingress rate, although the plurality of ingress data pipes is not fully shown inFIG. 2Just ingress pipe213′ having variable ingress bandwidth IBW3is shown. Device200is understood to optionally also include an ingress data buffering memory like130although not fully shown inFIG. 2; where the ingress data buffering memory has its data read lines (i.e.,244) coupling into a packet dispatching unit like240. Dispatcher output lines242-243of the dispatcher240couple to the switch fabric module(s)250. In one embodiment, although not shown, there is second dispatcher on the right side of switch fabric250for managing the flow of backflowing packets that carry back-pressure or slack credit tokens from the egress-side of device100to the ingress side of that device. Continuing with the description of packet flow from the ingress side to the egress side, it is seen that post-routing output lines of the switch fabric250couple to integrated egress/replay memory structures251-254(Only two of these four structures are shown more fully. The integrated egress/replay memory structures251-254are at times also referred to herein as integrated play/replay memory structures where the play portion of the name refers to a first time play out (i.e.,251b′) of data that had been injected at relatively high speed (i.e.,251a′) into the integrated memory structure (i.e.,251).)

Unlike the replay buffer arrangement (i.e.,151a/151d) ofFIG. 1where data passes at an egress-matching rate through a rate-matching FIFO (151a) and is copied (151h) in the process into a replay buffer memory (151d), inFIG. 2; integrated circular buffer structures (i.e.,251) are used for receiving processed packet data (e.g., routed packet data)251a′ at a first, relatively high bandwidth rate (e.g., Ebw≧×16) and for metering out egress data (251b′) at a potentially much lower bandwidth rate (e.g., Ebw=×1 for the ×1 port271). Respective data-router output lines251c-254cof the integrated egress/replay memory structures couple to their respective egress pipes261-264. (Note: Although data routers251c-254care schematically shown as simple multiplexers, in one class of embodiments they define more complex arbiters. SeeFIGS. 3A-3B.) The average data egress bandwidths at the entrances (E1-E4) of the egress pipes261-264still match the average egress bandwidths of the corresponding ports271-274. However, such matching of bandwidths is not required in this structure200for the packet data241-243leaving the ingress side FIFO's (i.e.,233) and routing through the switch fabric250for rapid injection into so-called, entry raceway sections251a-254aof the integrated egress/replay memory structures251-254. Packet data (251a′) that is absorbed at a first relatively high speed into the respective entry raceway sections251a-254ais later metered out at the egress bandwidth matching rates to first-play lines251b′-254b′ and into replay storage areas251d-254dof the integrated egress/replay memory structures251-254. In one embodiment, the respective entry raceway sections251a-254acan receive data (i.e.,251a′) at a first relatively high speed corresponding at least to the highest bandwidth allowed among egress ports271-274(e.g., Ebwmax=×16 in this example). In a second embodiment, the respective entry raceway sections251a-254acan receive data at a first relatively high speed corresponding at least to the highest instantaneous bandwidth at which such packet data can be transmitted through the packet data processing unit (i.e., switch fabric unit)250. The highest instantaneous bandwidth of the packet data processing unit250is often greater than (e.g., >×16 in this example) the highest bandwidth allowed among all the egress ports271-274of the device200because the packet data processing unit250may need some additional time slots for managing its processing of the packet data beyond the time slots consumed for routing the packet data to the targeted one or more egress pipes261-264. Accordingly, the respective entry raceway sections251a-254aare structured to receive the processed packet data at a rate which at least matches the highest instantaneous bandwidth of the packet data processing unit250if not exceeding it. It is within the contemplation of the disclosure that packet data processing unit250may provide additional or alternate packet data processing functions aside from selectively routing the ingress side blocks of data to the integrated egress/replay memory structures251-254on the egress side. The additional or alternate packet data processing functions may include altering control and/or payload data within the passing through packets or inserting additional data where for example, the on-the-fly alterations are carried out for purpose of conforming with a communication protocol present on the egress side but not on the ingress side of device200.

Although the integrated egress/replay memory structures251-254are not drawn as simple circular buffers, at the end of the day structures251-254can be implemented as circular buffers, albeit with the ability to read and write data at different rates. One aspect lies in how data is organized inside the integrated egress/replay memory structures251-254and how the bandwidth rates at which data is written into (rapidly injected into), and read out of structures251-254can differ. More specifically, in one embodiment, each of integrated egress/replay memory structures251-254stores three types of data: (1) egressing packet data that is currently being transmitted—also referred to herein as PdUx; for example such as the Packet-Data-Under-Transmission data shown circulating at251band being copied out of memory as PdUx signal251b′; (2) replay packet data—also referred to herein as PdAx; for example such as the Packet-Data-After-Transmission shown circulating at251dand optionally being output along playback line251e; and (3) to-be egressed packet data—also referred to herein as PdBx; for example such as the Packet-Data-Before-Transmission data251a′ shown to have been rapidly injected (at for example an Ebw≧×16 rate) into raceway memory region251a.

Additionally, a shared free space for example such as shown at251fis managed between the storage areas of the circulating PdAx data251dand of the rapidly-injected PdBx data251a. The to-be egressed data (PdBx-1) is allowed to enter into (to be written into, or injected into) the front-end raceway portion251aof integrated memory structure251at a rate (e.g., Ebw≧×16) which can be substantially greater than that (e.g., Ebw=×1) allowed for the corresponding egressing packet data signal215b′ (PdUx1). Although the techniques of pointer rotation and read-out via the rotating pointer are more typically used in embodiments of the present disclosure, the PdUx1 data can be thought of as if it were circulating (251b) inside its section of integrated egress/replay memory structures251at a rate matching the bandwidth of the data stepping out through corresponding egress pipe261. The -circulating PdUx1 data251bbecomes PdAx data251dafter the corresponding PdUx1 data signal215b′ has egressed out of the respective port271. Given that the to-be egressed data (PdBx-1) is injected into the front-end raceway portion251aat full speed (e.g., at the Ebw≧×16 bandwidth rate), the slowness of the destination port (271) no longer limits the speed at which the to-be egressed packet data (PdBx-1251a) can be shifted out of a corresponding ingress queue (e.g.,233), through the packet processor/switch fabric250and into the front-end raceway portion (e.g.,251a) of the corresponding integrated egress/replay memory structure251. Thus, even when egressing packet data (e.g.,133′aof FIFO233) is positioned at the head of a queue for shifting out toward a slow rate egress port (e.g.,271), head of queue blocking no longer occurs.

As mentioned, a shared free space memory area251fis maintained between the storage areas of the replay packet data (PdAx, i.e.251d) and to-be-egressed packet data (PdBx i.e.251a). When a positive acknowledgement (ACK) is received from the destination of the already-egressed data (of the After-Transmission Data, or PdAx), the corresponding replay storage area (the area storing the acknowledged PdAx data251d) can be allocated as free (where data erasure is optional but not necessary for freeing the space) and thus the space can be reallocated for use as an empty part of the raceway portion251a, thereby increasing the length of the raceway portion251aand allowing more to-be-egressed data (PdBx=Packet-Data Before Transmission) to enter into the raceway portion251aat relatively high speed.

Also, if to-be-egressed-but-subsequently-nullified packet data (null-PdBx) enters into the raceway portion251aat high speed (i.e., at an Ebw≧×16 rate), the corresponding raceway storage area251acan be cleared (optional) of this nullified PdBx data and reallocated for use as an empty part of the raceway portion, thereby increasing the empty length of the raceway portion251aand allowing yet more to-be egressed data251a′ (which subsequent PdBx is typically not nullified) to enter into the raceway portion251aat relatively high speed. If the nullification flag for an error infected packet (i.e.,132a) arrives at the egress side while the entirety of the packet is still within the PdBx raceway area (i.e.,251a) then that entire packet can be automatically purged form the raceway (i.e., from251a) to thereby transparently remove the error infected packet (i.e.,132a) before any of it manages to circulate into the PdUx section251band/or out of the packet data play out line251c. An important but subtle consequence of being able to receive the end of an erroneous packet more quickly (earlier in time than what is necessary for egressing the end-of-packet data out of its slow egress pipe i.e.,261) is that ECC nullification flags generated by the ingress side circuitry are able to more quickly traverse through the packet processor and/or switch fabric250and to get to the null-receiving lines of the replay buffer controller255. The replay buffer controller255can then responsively invoke a raceway purge of the packet data if all of the packet data still sits in the raceway215a. This subtle aspect particularly relates to the so-called cut-through operation mentioned above and this will be detailed even further momentarily. To recap what has been described, the high speed write-in option that is made possible by the high speed raceways251a-254aof the integrated egress/replay memory structures251-254helps to alleviate the head-of-line blocking problem that may otherwise arise in ingress-side FIFO's (e.g.,233) due to slow egress rates at the targeted egress pipe (i.e.,261) and it helps to reduce the wait time for the corresponding nullification flag to arrive on the egress side of the circuitry in cases where the respectively ingressing packet (i.e.,132a) is found to be error infected when the tail end of that packet finally passes into error checking circuitry at the ingress side of the device200. Note that the depth of FIFO233(Depth=depth value #4) is denoted as being different than that of corresponding FIFO133inFIG. 1(Depth=depth value #3). In some embodiments the depth of FIFO233(Depth=#4) can be made smaller than the depth of FIFO133(Depth=#3) because packet data generally dispatches out of FIFO233(Depth=#4) and through the switch fabric at the maximum allowed bandwidth of the fast raceways (i.e.,251a-254a) of the integrated egress/replay memory structures251-254. By contrast inFIG. 1, packet data may dispatch out of FIFO133(Depth=#3) and through the switch fabric at potentially the minimum egress bandwidth (e.g., Ebw=×1) depending on how narrow the targeted egress pipe is for that packet. Thus FIFO133will often have a depth (Depth=#3) long enough to accommodate the worst case scenario wherein all its egress data is being targeted toward the slowest of the egress pipes.

Referring still toFIG. 2and in terms of more specifics, assume that an ingressing first packet133′ashows up on the queue line of FIFO233as heading towards (being targeted to) the relatively low bandwidth egress point E1and an ingressing second packet133′bshows up next on the queue line of FIFO233behind133′aand as heading towards the relatively higher bandwidth egress point E3. In such a case, the first-in-queue packet133′awill not unduly increase the duration of in-queue waiting for the next-in-line second packet133′bbecause the first-in-queue packet133′awill zoom out through the dispatcher240and switch fabric and/or data processor250at the maximum bandwidth (e.g., Ebw≧×16 in the illustrated embodiment) that is allowed on the egress receiving raceways251a-254a, provided there is enough free space251f-254fallocatable to the receiving raceway (251a-254a) to accommodate the first-in-queue packet (e.g.,133′a) in the corresponding destination buffer251-254. In one embodiment, the amount of allocatable free space251f-254fis signaled back to the dispatch scheduler270by way of back-pressure flags or credit tokens254g.

An important aspect to note when studying the egress buffer raceways (251a-254a) is that, under normal conditions, control line255bof the replay buffers controller frequently receives ACK's that are quickly returned from the link partners of device200and very infrequently receives a NAK or detects a timed-out failure due to a link partner's failure to return an ACK. Thus under normal conditions where the links of respective egress ports271-274are healthy, additional storage area is frequently returned very quickly to the free space areas251f-254fas a result of corresponding ones of once-played-out packets (PdUx) having successfully made it through the network and as a result of receipt of corresponding confirmations coming back quickly from the corresponding link partners. Accordingly, the storage area (251d-254d) occupied by replayable data of the once-played out, and now acknowledged (ACK'ed) packet is quickly reallocated for use by free space area251f-254f. And this repeatedly replenished free space area251f-254fcan then be used as raceway injection area251a-254afor each accommodating a next routed block of packet data that enters the replay buffer structure251-254at the predetermined maximum bandwidth rate (i.e., Ebw≧×16). Thus the free space areas251f-254fare routinely made empty and made sufficiently long to easily accommodate receipt of a next routed block of packet data (e.g.,233b) as soon as that latter block of packet data is given an egress time slot by the scheduler270.

An optimization feature that is commonly found in conventional systems (e.g.,100ofFIG. 1) is known as early cut-through. Referring toFIG. 1, assume that the data ingress bandwidth on line121is equal to or larger (e.g., IBW1≧EBWE1) than the egress bandwidth of the pipe the current first-in-line packet (e.g.,131a) is heading to. Assume also that current first-in-line packet (e.g.,131a) is very long and its entirety has not yet finished shifting into ingress pipe131. Thus it is not yet known whether error checking of the packet131awill produce a valid data flag or an error flag. Assume further that the link partner (not shown) at the other end of egress pipe171is close to empty or signals (with use of credit tokens) that it has enough slack room to receive more ingress data (i.e. a cutting through packet). In order avoid having the link partner (not shown) run dry and the possibility of the link of port271having nothing to do, it is conventional in such cases (where IBW1≧EBWE1and the link partner having accommodation room) to allow the head-end portion of incomplete and unchecked packet131ato “cut-through” the switch fabric and thereby fill the ingress buffer (not shown) of the link partner while also making more room available in the ingress buffer131of device100for the data ingressing into that FIFO at bandwidth IBW1). This same early cut-through operation is used in device200ofFIG. 2. The problem with early cut-through when used in the conventional device100(FIG. 1) is that sometimes the ingress side error checking circuitry (not shown) of device100produces a true error flag (also sometimes presented as an invalid data flag). In that case, the early cutting-through but error-infected packet data is already streaming out of the egress pipe161and being buffered into the ingress buffer of the link partner at the other end of pipe161. As a consequence, a result exactly opposite to what was intended is achieved. Instead of being gainfully used, the limited bandwidth of slow pipe161is being wasted on the transmitting of garbage data. Moreover, bandwidth in the link partner is being wasted in receiving garbage data.

By contrast, in the device200ofFIG. 2, if data from an early cutting-through packet is sitting in the raceway (e.g.,251a) when the true error flag (also sometimes presented as a nullification flag) comes through at high speed (e.g., via coupling255cci.e., having a bandwidth of Ebw≧×16 and into null receiving line255cof the controller), the buffer controller255can early terminate transmission of the erroneous packet data by purging the erroneous packet data still residing in the raceway (e.g.,251a), thereby making free space room available for the data of a next packet (i.e.,132b) to enter the raceway (215a) and start egressing out of the corresponding pipe (i.e.,261) where the likelihood is that this next-in-line packet132bwill be found to be valid. The length of raceway data belonging to the error infected and cutting-through packet is known because the packet header provides length information for its body. As a result of such removal of infected data from the raceway (251a), less bandwidth is wasted on the transmitting of known garbage data through a low bandwidth egress pipe (261) as may otherwise occur with an early cut-through operation. The receiving link partner (not shown) is thus saved from spending excessive time receiving and processing more of the garbage data than has already been received.

Although operation of integrated egress/replay buffer structure251-254has been described in terms of the data itself racing or injecting quickly into the straight raceway (i.e.,251a) and thereafter possibly circulating more slowly around the circular path portions (i.e.,251b,251d; an exception being where the egress pipe bandwidth equals the maximum raceway bandwidth), artisans skilled in the art will appreciate that more typically the same effect can be accomplished by advancing read and write pointers at appropriate rates while the actual data stays put in its original storage location until overwritten by new data. In this regard, reference is now made toFIGS. 3A-3Bwhere a particular embodiment300that uses a variety of pointers, counters and counter-reloading registers will be detailed. For purpose of making the logical connection betweenFIG. 2andFIGS. 3A-3Beasier to spot, four pointer dots are drawn in around the circular buffer structure of replay buffer structure254and these are respectively denoted as: {B}, {U}, {A} and {N}. InFIG. 3A, four corresponding pointers: PtrB (381), PtrU (383), PtrA (384), and PtrN (386), are depicted within memory unit350.FIGS. 3A-3Bare to be understood as showing one possible species300of the generic solution provided byFIG. 2and they are not to be construed as limiting the disclosure associated withFIG. 2.

Referring toFIG. 3A, shown is a packet switching device300in accordance with the disclosure. Where practical, like reference symbols and numbers in the “350” decade series are used for replay buffer elements ofFIG. 3Awhich correspond to but are not necessarily the same as the elements represented by similar symbols and reference numbers of the “250” decade series inFIG. 2. Due to the detailed nature ofFIGS. 3A-3B, various elements already described inFIG. 1andFIG. 2are omitted from the illustration ofFIGS. 3A-3B. What is shown inFIGS. 3A-3Bis an upper sub-layer portion of a Data Link layer (DL) that receives data and control signals from a TL layer bus305and outputs results to a lower sub-layer portion of the Data Link layer by way of bus362. It is to be understood that device300may include a plurality of ingress data pipes like110,213′ and optionally with each having a variable ingress rate. It is to be understood that device300may include an ingress data buffering memory like130or233where the ingress data buffering memory has its data read lines (like244) operatively coupling to switch fabric module(s) like150,250of respectiveFIGS. 1-2. It is to be understood that post-routing output lines of the switch fabric (not shown) of device300couple to a transaction layer circuit (not shown) where the latter TL part is used for attaching transaction control code to file layer code output by the switch fabric. This post transaction layer data then arrives on bus305ofFIG. 3Aand carries both TLP payload data and TLP control data in respective sub-buses. In the illustrated embodiment TLP control data is carried on sub-buses305aand305cwhile TLP payload data is carried on a parallel sub-bus305b. Sub-buses305band305ccouple in parallel or on a time multiplexed basis into memory write port393. Also in this particular embodiment, TLP payload data305bmay be supplied at an average delivery rate corresponding to a device-wide maximum bandwidth of Ebw≧×16. (In one embodiment, the device-wide maximum bandwidth corresponds to the maximum payload bandwidth of the switch fabric250. SeeFIG. 2.) In other embodiments the device-wide maximum bandwidth may be higher or lower than ×16, for example in one alternate embodiment it is Ebw=×8.) When the TLP payload data305benters an integrated egress/replay memory structure350for storage therein through write data receiving port393, a corresponding write address is provided by way of PdBx write address bus391and corresponding write control signals such as write enable and write clock are provided by way of write control bus392. In an alternate embodiment, there is only one clock signal for both read and write operations. However, for purpose of illustration it is easier here to present memory unit350as having independent write and read clocks wherein the write clock operates at a frequency corresponding to the device-wide maximum bandwidth (e.g., EbWMAX≧×16) and the read clock (395) operates at a frequency corresponding to a variable bandwidth (e.g., Ebw=Var≦EbWMAX) so as to thereby match the egress rate of a variably configured egress pipe or port (not shown). WhileFIG. 3Aemphasizes that TLP payload data305bis written into memory unit350by way of write port393, in one embodiment various TLP control signals305csuch as relative SOF addresses (starts of packet frames), relative EOF addresses (ends of packet frames), and relative Nullify start and end addresses are also written into memory unit350by way of write port393for purpose of later transfer to a replay control module320by way of read port396and also for later transfer to egress control module310also by way of read port396. Data throughput rates at write port393and read port396will typically differ from one another. In that regard, memory350may be viewed as a rate smoothing buffer for SOF and EOF data entries that enter via write port393and are later forwarded from read port396to the egress control module310and to the replay control module320.

With regard to the data reading output port396, a respective read address is provided to memory unit350by way of a PdUx/−PdAx read address bus394where the type of read address supplied depends on (and defines) whether the read port396is respectively outputting first-time play-out data (PdUx) of a packet or second-time packet data that has been first-time played out and now is being replayed as replay data (PdAx). Corresponding read control signals such as read enable and/or read clock are provided by way of read control bus395.

The first-time play-out data (PdUx) or replay data (PdAx) ultimately exits via bus362for further processing by a lower sub-layer of the data link layer (not shown) of device300. That lower sub-layer of the DL (not shown) may attach further DL code signals to packet signals output via line362, such as sequence number codes and error check codes (i.e., a cyclic redundancy check such as LCRC32 for example). The DL-processed play-out packet signals may then move through the device's physical interface layer (PL) for encoding into a predefined serial transmission format and for output onto a physical transmission media (not shown) and subsequent receipt by a link partner (not shown). A back-pressure signal368(or another vacancy indicating signal) from the lower sub-layer of the DL (not shown) couples to an arbiter330of the illustrated circuitry for indicating to the arbiter330when the lower sub-layer of the DL has buffer space available for receiving more data via egress output bus362. The arbiter330makes sure there is sufficient vacancy room in the lower sub-layer of the DL before allowing read address signal394to advance for a next block of entry data.

Referring to the buffer structure shown inside the integrated egress/replay buffer structure350, it can be readily seen that regions351fand351f′ correspond to the free space area251fofFIG. 2, PdBx area351aofFIG. 3Acorresponds to the raceway section251aofFIG. 2, PdUx area351bcorresponds to the Data-Under-Transmission area251bofFIG. 2, and PdAx area351dcorresponds to the Data-After-Transmission area251dofFIG. 2. A number of pointers may be used to keep track of starts and/or ends of various parts of each circular buffer (only one such circular buffer shown, although plural ones are understood to be present) in the integrated egress/replay memory unit350. Upon start up when the buffer is empty and there is only free space351f-351f′, all pointers collapse to the position of the end-of-PdAx pointer386(PTRN). Next as PdBx information enters for storage in the raceway area351a, pointer381(PTRB) separates away from the position of the end pointer PTRN(386) and pointer381(PTRB) advances upwardly for keeping track of the latest PdBx byte(s) just written into memory. A register315in egress controller310stores a copy of the PTRBpointer (381). Yet later as some PdBx data is redefined as being PdUx data that is part of a packet being currently read out in blocks (where generally the blocks won't be read out until after a complete and validated full packet has been assembled in area351a—the exception being a cutting through packet), additional pointers383b(PTRU),383c(SOF3), and384(PTRA) separate away from the position of PTRN(386) for keeping track of the current read-out span which is allocated as being the current Packet-Under-Transmission (PdUx). In one embodiment, the stored data (i.e. plural bytes) that is bounded in the address range defined between the SOF3 pointer383cand the PTRUpointer383bdefines that portion of a full packet that has already been read out (played out for the first time) thus far. The PTRApointer384points to the end of the last full packet that was defined as having been fully played out at least once to the link partner. Only when the span between the SOF3 pointer383cand the PTRUpointer383bdefines a full packet that has been read out (played out for the first time) and has been validated as not being infected by a CRC-identified error or by another type of error does the PTRApointer384pop up to the PTRUlevel383bto thereby redefine the data stored between383c(start-of-frame now under transmission) and383ba replayable packet ( a part of the PdAx area351d). The SOF3 pointer pops up in unison with the PTRApointer384so that SOF3 now points to the start-of-frame of the next packet under transmission. In one embodiment, data being read out as blocks from the PdUx area is coagulated into a parallel output word (long word) of 16 Bytes length and output as such in one clock cycle from data output port396(read output) of the memory unit350. In other embodiments, the read-out block size can be smaller or larger, 4 Bytes, 8 Bytes or 32 Bytes per block for example.

When the last block of a current packet-under-transmission (PdUx) data has been read out (that is, PTRUis pointing to the end of frame of the current packet-under-transmission) then that full-packet's worth of data is redefined as PdAx data belonging to area351d. This is done by the popping the PTRApointer384to the last just-read out entry in memory350, and causing each of SOF3 pointer383cand PTRUpointer383bto point to the start of frame of the next packet in the PdBx area351a(if there is any such next packet). This has the effect of shrinking the length of the PdBx data (if any) remaining in raceway area351a. The position of PTRN(386) generally does not advance in direction386auntil an ACK (a valid DL-level acknowledgement) is received from the link partner of the corresponding and already once-played packet. When the ACK arrives, PTRN(386) jumps to the start-of-frame (SOF1) of the next in-PdAx packet that has not yet been acknowledged by its link partner. In one embodiment, a plurality of once-played-out packets may be acknowledged simultaneously with a single ACK signal that identifies the youngest of acknowledged packets by that packet's sequence number. In such a case the amount of PdAx memory space that is simultaneously reallocated to free space (351f′) can be quite large. And that in turn frees up a large amount of memory for use as raceway scratch area351f. In one embodiment, the location of the SOF1 pointer385after a multi-packet acknowledge is obtained from a lookup table324provided within replay controller section320. The lookup table324sorts its entries according to sequence numbers. Each time PTRN(386) jumps up to the new SOF1385of the next not yet-acknowledged but first-time already played-out packet, the amount of free space in regions351f′-351fcan increase by an amount equal to the length of just acknowledged packet or packets as measured in bytes or in short words (quadruple byte words).

As already mentioned, every so often the ingress side of the device300may supply a natural nullification flag to the egress circuitry where the natural nullification flag indicates that a current packet (i.e., a cutting through packet) whose data resides in raceway area351aand whose data is already being first-time played out as PdUx data (or is about to be played out) is garbage. In such a case it is desirable to perform an early termination operation and not waste time starting to or continuing to output the data which is designated as garbage data over the link. In one embodiment, such an early termination operation comprises an effective discarding of whatever portion of the bad packet (or packets) still reside(s) in the PdBx raceway area351a, namely, the data stored between the PtrB pointer381and the SOF2pointer382; where in the case of a cutting through packet, SOF2 and SOF3 will point to the same spot, one entry above where the PtrA pointer384points to. A discarding operation that discards packet data from the PdBx area351acan include one or more of the following steps of: (a) collapsing the PtrB pointer381down to the level of the SOF2pointer382because data stored therebetween is deemed invalid; and (b) collapsing the SOF2pointer382and the PtrB pointer381both down to the level of the SOF3pointer383cbecause cutting-through data stored therebetween is deemed invalid. Then, when new PdBx data is written into memory unit350, the new PdBx data overwrites the data of the discarded packet data. As a result, the system will begin to instead play out data belonging to this overwriting next, and not-yet-nulled packet starting at the SOF3position rather than the invalidated data. In one embodiment, a copy of the SOF2 pointer382is kept in a register317of the egress controller section310. The SOF2 memory address value is loaded into register317from the PdBx counter311avia line319bwhen the TLP bus305aflags the presence of a start of frame (SOF) for a currently being written packet. In one embodiment, for purpose of early termination operations, the value of pointer383c(SOF3) is stored in a register318where the latter is included within the egress controller portion310of device300. Register318is loaded from a data distribution bus365whose data originates from memory read port396. The reason why register317(SOF2) loads in response to bus305asignaling an SOF while register318(SOF3) loads from bus396/365is because the respective address counters311aand312aof those registers317and318are operating in different time frames and usually at different throughput rates. Address counter312a(the PdUx counter) is incrementing at the average egress output rate of the egress pipe (i.e.,264ofFIG. 2) and waiting for repeated approvals from the arbiter330that there is vacancy (368) in the lower DL sub-layer (to which bus362connects). Contrastingly, address counter311a(the PdBx counter) can be incrementing at the higher burst speed rate of the TLP bus305and it is therefore not necessarily synchronized to the read-side arbiter330. Stated otherwise, it should be remembered that the effective write clock CLK(Wrt)392a(which may be considered as driving PdBx counter311a) is often operating at a different, usually faster average writing rate and generally a different phase than the effective read clocks CLK(Rd)395a,b(where the latter two signals may be considered as driving the PdUx counter312aand the PdAx counter321per vacancy synchronization commands provided by the read-side arbiter330). Although the write and read counters,311a,312aand321generally operate independently of one another and at different rates, during an early termination operation, buses319c(ET1) and319d(ET2) are used for sharing information between the respective write and read controllers311,312and320as shall be detailed below. One or both of buses319dand319can carry a flag to the arbiter330indicating that area351b(PdUx) contains data from a currently cutting-through packet.

At least two different kinds of packet payload data can be read out from the read data output port396of the integrated egress/replay memory structure350as well as other data (relative SOF's) to be described below. The two different kinds of packet data are: (1) first time playing-out data being read from the PdUx expanding window area351bduring a first-time egress operation and (2) replay data being extracted from the PdAx area351dduring a packet data replay operation. Arbiter330manages the read pointers for both types of data and makes sure that there is vacancy room in the lower DL sub-layer that bus362feeds into. The predominant activity is that of forwarding a current PdUx block of data by supplying corresponding read address signals and associated control signals319from an egress read controller312within section310respectively to the PdUx/PdAx read address bus394and to the read control bus395of memory unit350.

During an egress operation, a PdUx counter312ainside egress controller portion310is stepping forward through a sequence of counts that cause the PtrU pointer383bto advance by single steps corresponding to the current egress bandwidth (on bus396) towards the position of the SOF2 pointer382. When the PtrU pointer383bcatches up to a position just below the SOF2 pointer position382, the PtrA pointer384is automatically popped up to the position just below the SOF2 pointer position382(This new PtrA position corresponds to the end of the packet whose EOF has been just detected on TLP bus305.) Next, the SOF3 pointer383cis automatically popped up to the SOF2 pointer position382and the PtrA pointer384is automatically popped up to the position just below. This causes the not-nullified and just fully played-out packet (PdUx) to become part of the replay section351d.

At this stage, with the just played out packet having successfully played out for a first time without encountering a nullification flag and it having been re-designated as a valid packet inside the PdAx area351d, the system reaches an arbitration decision point for determining what next full or partial (if cutting through) packet to read out. The arbiter330may now elect to begin playing out the accumulating data of the next full or partial packet residing in the PdBx raceway area351aor the arbiter330may elect to begin replaying a packet residing in PdAx area351d. In one embodiment, a request for replay (333) always has higher priority than a competing request for egress (331). Intermixed with the play out of packet data, the arbiter330may also cause the memory350to read out other kinds of data (e.g., relative SOF and EOF data that is distributed by data distributor360into various registers such as318of unit310and324of unit320by way of buses365and363.) Generally, if there is no packet replay request, the arbiter330is biased towards electing to play out all packets already residing in the PdBx area351a. At the same time that the arbiter330is causing already-received (and usually validated) packet data to be read out from memory read port396when there is room for it in the lower DL sub-layer (bus362) and at a rate corresponding to the egress pipe bandwidth (e.g., Ebw=×2 for pipe264), new packet data is usually being written much faster into (appended to) the PdBx area351aat a throughput rate equal to or less than the device-wide EbwMAXrate (i.e., ≧×16). The memory write-in operation is under independent control of a PdBx write counter311aprovided inside egress controller portion310.

Detector314determines if pointer PTRU(383b) has advanced so as to catch up with PtrB (381) and thereby exhaust the PdBx raceway area351a. If it has not (if PTRUdoes not yet equal PTRB), that means there is still more first-time data to play out in the raceway area351a. In response to detection that the PTRUminus PTRBvalue is not zero, the PdUx counter control unit312sends an egress request signal331to arbiter330asking for permission to transmit more packet data out of the PdBx raceway area351a. The PdUx counter control unit312then waits for an active enable (a bus grant)332from the arbiter330before firing up the PdUx counter312ato begin outputting a next stream of addresses, which stream can cover one or more full packets or even a cutting-through partial packet residing in PdBx area351aup to a position just below PtrB381.

The stream of sequential addresses output by PdUx counter312acan be interrupted and stopped if an early termination operation is initiated due to receipt of a natural nullification flag while a cutting-through play-out operation is on going. In such a case (where an early termination occurs for a cutting-through packet) a number of different things will happen. First, detector313will indicate a true condition for the test, SOF2=SOF3? because SOF2 and SOF3 point to the same memory location when a cutting-through packet is present. Second, the SOF3 address stored in register318will be loaded into counter312a. This has the effect of pulling the PtrU pointer383bback down to the SOF3 level. Third, the SOF2 address stored in register317will be loaded into counter311a. This has the effect of pulling the PtrB pointer381also back down to the SOF2=SOF3 level. New raceway incoming data will then overwrite the old and nullified cutting through data while the old and nullified cutting through data is not redefined as PdAx data, but rather is discarded.

The outputting of successive full packets from the PdBx raceway area351acan be temporarily interrupted between such first-time playouts if a NAK is received from the link partner or the link partner does NOT send an ACK for a packet within a predefined timeout period. In that case, a replay is called for. Due to timing and data storage issues, it is desirable to preserve the output value of the PdUx counter312awhen it outputs the address of the last block in a first-time playout packet just before a potential replay begins. The PdUx counter312ais controlled to keep advancing to the next data entry to be played out rather than dwelling on the one that was last played out. To this end, bus312bcouples to data load terminal316cof register316a. Register316ais clocked at an appropriate clock cycle so as to store the last value of PTRU(383b) just prior to the beginning of the interrupting Replay operation. This way the end of packet (EOF) address of the last-fully read out first-time playout packet is preserved without having to perform mathematical calculations. After the interrupting event of a NAK or a late ACK is serviced by a complete replay, the next first-time play out operation can then be seamlessly commenced by using the data stored in register316aand the pointer in PdUx counter312awhich has already advanced to the next data entry to be played out as first-time playout data.

More generally, arbiter330can be switched into performing a replay operation when replay controller section320receives a NAK signal over line328aor fails to receive a timely ACK (decides a replay operation is needed due to a timeout). In that case, replay controller section320sends a replay request signal over line333to the arbiter330. The arbiter330can then provide a corresponding replay enable signal over line334just as soon as a currently egressing packet (from PdBx are351a) completes or if there is none egressing. When the arbiter330asserts the replay enable signal over line334, the PdAx counter321responds by initiating a counting through of address values in PdAx area351d. In the case of no timely ACK, the addresses swept through are from that of pointer PTRN(386) to that of the PtrA (384). In the case of a NAK from the link partner, the SOF1 pointer (385) is found in lookup table324and loaded into PdAx counter321and the latter counts from SOF1 (385) to the PtrA location (384). Immediately after the replay of a complete one or more packet finishes out of the PdAx area351d, play out of a next complete new packet from the PdBx raceway area351amay be seamlessly commenced because the PdUx counter312ais already pointing one ahead of the old PTRU value saved in register316a.

If pointer PTRU(383) catches up to pointer PTRB(381) then that means the egress engine (312) has finished playing out all the new data that has entered the front-end raceway region351a(PdBx) of the circular buffer and there is nothing more for the egress engine (312) to do. Accordingly, the egress engine controller (312) does not send an egress request331to the arbiter330under this circumstance. If an EOF has not been received over the TLP bus305then the arbiter330will still be waiting for such an end of packet signal (EOF) to emerge from memory output bus396and to be signaled as such via line335before the arbiter enters idle mode. If the end of packet signal (EOF) has been received, then the arbiter330will enter idle mode and await either new data from the TLP bus305or a NAK from the link partner or an indication that an expected ACK has not been timely received

When new payload data305barrives and starts to fill up the PdBx raceway area351a, the egress write controller311activates its internal PdBx counter311awhile saving certain pieces of information for later use. One piece of information that controller311saves is the address (SOF2) of where a new incoming packet begins. The identity of this SOF2 address is flagged by an SOF indicator signal included in the TLP control stream305a. In response, the egress write controller311strobes register317at the appropriate clock cycle to save the SOF address of the current packet that is being written into the PdBx area351a. If a nullification flag later comes in for the current packet (as writing of that packet completes), the SOF2 address value in register317is reloaded into PdBx counter311ato thereby, in essence, erase the nullified packet and begin writing the data of the next, not-nullified (the new incoming) packet from the SOF2 position (382) and upwards, thus overwriting over the nullified data.

After each write of a byte or quad-byte word, the PdBx counter311ashould be pointing to the next empty space in free space area351fso that it is ready to immediately store the next incoming piece of payload data305bor control data305cas received over bus305. However, for timing reasons, it is desirable to keep track of where the last piece of payload data was previously written and to save this information (PtrB at time of last writing) in register315. The egress write controller311therefore strobes register315at the appropriate clock cycle when line319bcarries the PtrB address at time of a latest payload data writing so as to save this information for use by the sameness detector314of the PdUx address controller312. The reason that such synchronization into register315is performed is because the effective write clock CLK(Wrt)392awhich can be considered as driving the PdBx counter31la is often operating at a different rate and generally different phase than the effective read clock CLK(Rd)395a,bthat can be considered to be driving the PdUx counter312a.

Yet another address which the egress write controller311needs to keep track of is the location of the free space end pointer386(PTRN). Signal323provides this information. As the write pointer381(PTRB) advances up in direction381ait can wrap around and hit against end pointer386(PTRN) thus threatening to overwrite replay data351dthat has not yet been ACK'ed by the link partner. In one embodiment, and as a safety feature, write controller311is configured to stop the advancement of PdBx counter311aand reload the SOF2 address from register317into the PdBx counter311aso as to thereby drop an incoming packet (one incoming into raceway area351a) if that incoming packet that threatens to overrun the bottom (PTRN) of the replay storage area351d. The replay storage area351dis thus protected until an ACK comes back from the link partner. The PdBx counter311amay be started up again towards incrementing the PtrB pointer381upwards after a post-replay ACK comes back from the link partner and the PtrN pointer386pops up (in direction386a) so as to thereby create new free space351f′-351f. Should new TLP data have come in over bus305during the time there is no free space, the outcome will be that the system will have dropped one or more packets (usually no more than one) out of the raceway area351awhile preserving the integrity of the data that is already in the replay buffer area351d. The signal323which provides the end of free space information is supplied from the replay controller320. (See alsoFIG. 3B.) A good design of device300will include means in the TLP layer (not shown) for preventing such an undesirable situation. A credit counter327(described below) is provided for communicating with the TLP layer to help prevent such an overrun case.

Although the memory write-in port393and memory read-out port396generally operate at different bandwidths, their operations may need to overlap (as mentioned above) when a cutting-through packet is being processed. In such a case, PtrB is pointing to a currently-being written, back part of the cutting-through packet while PtrU is pointing to a currently-being read-out earlier part of the same cutting-through packet. Sameness detector313flags the cutting-through packet condition to controller311. If an early termination flag comes in during such a situation, and the sameness detector313indicates SOF2=SOF3, controller311responsively halts its current writing operation and copies the content of register317(SOF2) into counter311a(PdBx). This has the effect of pulling the PtrB pointer381back down to the memory address level of the SOF2 pointer382. The PdBx counter311ais then ready to immediately write in the next block of new packet data (not invalidated data) into PdBx region351a. In general, the PdBx counter311ais pointing to the first empty spot in free space351f, where that first empty spot will be filled with the next block of new packet data coming in from TLP sub-bus305b.

At the same time that the write controller311responsively halts its own current writing operation upon receipt of an early termination flag (from bus305) it should signal the independently operating read controller312to halt its reading out of the same cutting-through but defective packet. It should also signal the arbiter330to switch out of its current egress read-out mode. In one embodiment, these early termination synchronization operations are carried out with use of early termination lines319c(ET1) and319d(ET2). Upon receipt of an early-termination command over line319c(ET1), the read controller312halts its internal PdUx counter312a. It then loads the contents of register318into the PdUx counter312a. This has the effect of lowering the PtrU pointer (383b) back to pointing to the SOF3 location383c. At that time, register316acontains a value equal to the address pointed to by PtrA (384) plus one entry, in other words, the SOF3 address value equals the PtrU address value. If PtrB next jumps ahead of PtrU, detector314will correctly indicate that there is new data in the raceway section351a. Read controller312will ask the arbiter330to grant it an egress read-out session. If PtrB instead remains unchanged, then the read controller312will not request an egress read-out session. The arbiter330will remain in idle mode waiting for a DL-Ack or a DL NAK from the link partner or waiting for another activating event (i.e., failure to receive a timely ACK). The arbiter330is in idle mode at this stage because upon receipt of the early-termination command on line319c(ET1), the read controller312not only halted its internal PdUx counter312a, it also sent a command over line319d(ET2) to the arbiter330for causing the arbiter330to halt its current egress read-out session and enter idle mode. When in idle mode, the arbiter330is ready to receive one or more new requests such as over request lines331and333and to arbitrate between them if they occur simultaneously and to then grant a read session to the winning request. (In one embodiment, an active replay request333always has highest priority.) After servicing a first winning request, the arbiter330grants a next read session to a next requestor on a round robin or other fairness-based prioritization scheme. During a granted read session, the arbiter330synchronizes its activities with the buffer vacancy indicating signals received from the lower DL sub-layer over line368. In this way, the arbiter330protects the receiving buffer (not shown) in the lower DL sub-layer from overflowing.

It should be noted that the request lines331and333going into the arbiter330are not limited to carrying read-out session requests only for the purposes of first-time play-out of packet data (PdUx content) or for subsequent replay of at least once-played out packet data (PdAx content). Read-out session requests may be transmitted over request line333for purposes of locating special SOF, EOF and/or nullify characters and storing their respective addresses in a lookup table (LUT)324ofFIG. 3B.

It should be further noted that the memory locations pointed to by the address values of the SOF2 (382) and SOF3 (383c) pointers are not necessarily the only start-of-frames in that memory span SOF2-SOF3. There can be plural numbers of whole packets stored in the memory span SOF2-SOF3. The PdBx raceway351ashould be designed with sufficient space to store plural whole packets because TLP bus305can unload a burst of such packets quickly into the PdBx raceway area351awhereas playout bus396may be constrained to outputting stored packet data at a relatively much slower rate due to current thinness of the corresponding egress pipe (i.e.,264).FIG. 3Ashows only the SOF2 pointer (382) and the SOF3 pointer (383c) because that part of the design needs to keep track only of the start-of-frame of the currently being read packet (occupying the span pointed to by SOF3-PtrU) and of the currently being written packet (occupying the span pointed to by SOF2-PtrB).

Referring toFIG. 3B, register316bis essentially a copy of register316aand stores the last value of PTRU(383b) just before an interrupting Replay operation began. In this situation, PTRU(383b) points to the end of the last block of the once played packet that was just read out. If a DL NAK comes back for any not-yet acknowledged packet (where the NAK328ais received by controller328), the PdAx replay counter321awill step through the address space located between the addresses pointed to by pointers385(SOF1) and register316b(whose current contents correspond to PTRU(383b) which also happens at this time to equal PTRA(384)). In this way, the PdAx replay counter321acan quickly replay not-yet acknowledged packets residing in the replay area351d. Output329′ of PdAx replay counter321acouples to input329of arbiter330(FIG. 3A). SOF addresses are obtained by the replay controller320via lines363′ and363″ which couple to bus363ofFIG. 3A. The obtained SOF addresses can be redistributed to the egress controller310by way of lines364′ (FIG. 3B),364(FIG. 3A), through distributor360and then bus365.

Sometimes a replay condition arises that calls for replay of more than one packet at a time. For example, if a DL ACK has not been timely received for a plurality of packets stored in memory area351d; because for example the link temporarily went down, then in one embodiment the start-of-frame for the first of the not yet acknowledged packets is obtained form a lookup table324held within replay controller320′. The PdAx replay counter321awill then step through the address space located between the addresses pointed to by SOF pointer fetched from lookup table324and register316bunder the assumption that the link went down during the entire time and thus all the packets in that range need to be replayed.

If a DL ACK is timely received for one or more packets (where in this embodiment the one or more packets includes the packet whose start-of-frame is pointed to by the PtrN pointer386ofFIG. 3A), then a reallocation of replay buffer area to free space351f′ is performed. Address register327a(in controller327) stores the current PtrN value. Line323couples the PtrN signal to unit311ofFIG. 3A. Line324afeeds the current PtrN signal value into address register327afrom lookup table324. Controller327further contains a credit counter whose output327bcouples to the dispatch scheduler (see270ofFIG. 2) of device300. The credit count tells the dispatch scheduler how much free space is presently available in memory area351f′-351f. When replay buffer area is reallocated to free space351f′ because the packets stored in that replay buffer area have been affirmatively acknowledged (ACK'd) by the link partner, the value stored into address register327ais bumped up to the start-of-frame of the next packet that has not yet been affirmatively acknowledged (ACK'd). That new PtrN value comes from lookup table324by way of line324a.

Data distributor360ofFIG. 3Adoes more than just distribute data read out from memory bus396to further buses362,363and365. One of its functions is that of detecting special characters such as SOF characters and EOF characters appearing on memory output bus396. If distributor360detects an SOF character on bus396, the distributor360responsively causes a corresponding read address that had been output on PdUx counter line321b/319(corresponding to the detected SOF character) to be copied via lines335and363/363″ into the SOF lookup table324ofFIG. 3B. In this way the lookup table324is able to capture the memory addresses of various TLP control signals including the start-of-frame addresses (SOF's) of all valid packets stored in memory350(stored both in the PdAx area and the PdUx area). These memory addresses (which could be absolute or relative) are initially established by the PdBx counter311awhen the corresponding SOF or other special packet framing characters appear on TLP bus305and are written into memory350via write port393. Later, when the PdUx counter addresses the same memory location and causes the SOF or other special packet framing character to re-appear on the memory read bus396, the data distributor captures the corresponding output of the PdUx counter312afrom line335(which couples via the arbiter to line319) and distributes the captured address signal via line363″ (FIG. 3B) for storage into lookup table324. A lookup table write controller326manages where in the lookup table324these various captured addresses (363″) will be written. In one embodiment, the write controller326sorts the to-be-written data according to unique packet sequence numbers associated with their respective packets. Details regarding this process extend beyond the scope of the present disclosure. It is sufficient for purposes of this disclosure simply to note that any appropriate means may be used for keeping track of where in lookup table324, the start-of-frame address of a given packet is stored where the given packet may be identified by any of a variety of equally usable techniques.

A read controller325is further provided in replay controller module320′ for reading out the stored SOF address signals from lookup table324in accordance with an appropriate packet identifying technique. One of the SOF address signals loadable into PdAx counter321afrom lookup memory324is the SOF1 address (385). Another is the PtrN address value (386) which is also loadable into register327afrom lookup memory324. Loading of one or the other of SOF1 and PtrN (or of another SOF address stored in lookup memory324) into the PdAx counter321aallows the PdAx counter321ato begin a replay count out starting at the earliest part of the one or more packets (e.g., the one starting at SOF1) that is deemed as needing to be replayed at the moment. The halt of count address (PtrA) comes from register316binto sameness detector336who's other input couples to line329′ and whose output couples to a stop terminal of control module321′. In one embodiment, if no DL ACK's are received within a predefined timeout, the lookup memory324loads the PtrN start-of-frame address into PdAx counter321aand thereby allows the PdAx counter321ato begin a replay count out starting at the earliest part of a contiguous plurality of packets that have not been timely acknowledged where the plurality includes the last played out whole packet (385-384). The stop terminal (the output of sameness detector336) also couples to the replay request line333′ for blocking assertion of replay requests once the address on counter output329′ equal the PtrA value output by register316b.

When a data-link layer acknowledge signal (DL ACK) or negative acknowledge (DL NAK) signal comes in via bus328a, the ACK or NAK indicates which one or more of the once-played packets it covers among the packets stored in replay area351d. If it is a DL NAK, the lookup table324, if necessary, forwards the corresponding SOF address signal into PdAx counter321a. Additional signals are coupled into replay address controller321′ by way of bus363′. These are SOF, EOF and various notification signals that have been stored in memory350at the time of their receipt on TLP bus305. As mentioned the special optical framing characters (i.e., SOF, EOF) are detected by distributor360when they are read out from memory350and their corresponding addresses are fed through lines312b,319, through the arbiter330, through line335and through the distributor360into bus363when the replay controller320is ready to use them. One of the memory stored notifications that is fed into controller320by way of bus363′ is a so-called late error notification which occurs when a soft error is detected in memory350after a given packet had been stored into memory350but experiences a soft storage error. Packets with soft-errors are not replayed but are instead purged out of the replay buffer area351din a manner similar to how acknowledged (ACK'd) packets are purged. This level of hyper detail is not needed here however for understanding the primary thrust of the present disclosure which deals with how the fast raceway section351ais integrated with the replay buffer storing area351dand how the two cooperate with one another. Bus328acouples control signals from the ACK/NAK purge controller328to units327and321′. The control signals (328a) indicate whether and when respective ACK or NAK or lack-of-timely ACK events occur.

The present disclosure is to be taken as illustrative rather than as limiting the scope, nature, or spirit of the subject matter claimed below. Numerous modifications and variations will become apparent to those skilled in the art after studying the disclosure, including use of equivalent functional and/or structural substitutes for elements described herein, use of equivalent functional couplings for couplings described herein, and/or use of equivalent functional steps for steps described herein. Such insubstantial variations are to be considered within the scope of what is contemplated here. Moreover, if plural examples are given for specific means, or steps, and extrapolation between and/or beyond such given examples is obvious in view of the present disclosure, then the disclosure is to be deemed as effectively disclosing and thus covering at least such extrapolations.

Reservation of Extra-Patent Rights, Resolution of Conflicts, and Interpretation of Terms

After this disclosure is lawfully published, the owner of the present patent application has no objection to the reproduction by others of textual and graphic materials contained herein provided such reproduction is for the limited purpose of understanding the present disclosure of invention and of thereby promoting the useful arts and sciences. The owner does not however disclaim any other rights that may be lawfully associated with the disclosed materials, including but not limited to, copyrights in any computer program listings or art works or other works provided herein, and to trademark or trade dress rights that may be associated with coined terms or art works provided herein and to other otherwise-protectable subject matter included herein or otherwise derivable herefrom.

Unless expressly stated otherwise herein, ordinary terms have their corresponding ordinary meanings within the respective contexts of their presentations, and ordinary terms of art have their corresponding regular meanings within the relevant technical arts and within the respective contexts of their presentations herein.

Given the above disclosure of general concepts and specific embodiments, the scope of protection sought is to be defined by the claims appended hereto. The issued claims are not to be taken as limiting Applicant's right to claim disclosed, but not yet literally claimed subject matter by way of one or more further applications including those filed pursuant to 35 U.S.C. §120 and/or 35 U.S.C. §251.