Systems and methods for adaptive credit-based flow

The present invention relates generally to an information handling system. Aspects of the present invention include an adaptive credit-based flow control in an information handling system. In embodiments, a request/grant credit system can be eliminated since the receiver can dynamically allocate credits based on demand at the sender. In embodiments, the sender can provide information related to its queue size to the receiver. The receiver can estimate queue size and demand based on the estimated queue size. In embodiments, the receiver allocates credits based on sender demand.

BACKGROUND

Field of Invention

The present invention relates generally to information handling systems and more particularly relates to control flow in information handling systems.

Description of the Related Art

As information handling systems provide increasingly more central and critical operations in modern society, it is important that the networks are reliable. One important element in information handling systems is flow control.

Flow control refers to the mechanism to control the transmission speed so that the transmission speed for the sender and receiver match. For example, if the sender can send information quickly, but the receiver is slower, then the fast sender can quickly overwhelm the slower receiver. Therefore, flow control can be employed so that the receiver does not become overwhelmed.

One type of flow control is credit-based flow control. Credit-based flow control uses buffers and credits. Credits indicate availability of receive buffers. In a typical prior art system, the receiver sends credits to the sender indicating the availability of receive buffers. The sender waits for the credits before transmitting messages to the receiver.

Hop-by-hop (or link level) credit-based flow control has been used in Fibre Channel and InfiniB and deployments. There are limitations to credit-based flow control where there is a lot of overhead with the request/grant approach. An alternate method for link level flow control is Priority-based Flow Control (PFC).

Examples of limitations include, once a receiver sends a credit the credit cannot be taken back. Therefore, if the sender does not use the credit, the sender still has the credit limiting the receiver. Also, buffer sharing across ports is not possible. The credits are port specific. Additional credits based on global shared buffer pool availability cannot be done apriori by the receiver because by the time the sender actually uses the credits, the congestion state in the receiver could have changed and the shared buffer pool could have run out of buffers.

Also, the receiver cannot reserve the buffers in the shared buffer pool apriori and allocate them to the sender because the sender may not use those additional credits. Since the credits have already been sent to the sender, the credits cannot be reallocated to a sender on a different port.

FIG. 1shows an example of a credit-based flow control prior art system.FIG. 1shows sender and receiver system100including sender105and receiver110. Receiver110has ports0135through port N150. Each port has an available buffer space145or155and some ports have a used buffer portion140. Receiver110can send credits to sender105. When sender105has available credits130, it can send a message to receiver110. In this example, each port in the receiver has a fixed buffer. The receiver110advertises credits based on available buffer in its fixed buffer pool. When packets egress out of the receiver110, more buffers are replenished in the fixed buffer pool145or155and more credits130can be advertised to the sender105.

The sender105can transmit data from its queue only if it has enough credits granted by the receiver130. When packets egress out of the sender105, the available credits are decremented proportionate to the amount of data transmitted.

FIG. 1illustrates some of the constraints with a credit-based flow control system. For example, the credits once allocated cannot be taken back. Also, buffer sharing across multiple ports is not possible.

Accordingly, what is needed is to overcome the constraints in a credit-based flow control system, by achieving a more efficient flow control that can achieve lossless transmission.

DESCRIPTION OF THE PREFERRED EMBODIMENTS

The use of certain terms in various places in the specification is for illustration and should not be construed as limiting. A service, function, or resource is not limited to a single service, function, or resource; usage of these terms may refer to a grouping of related services, functions, or resources, which may be distributed or aggregated. Furthermore, the use of memory, database, information base, data store, tables, hardware, and the like may be used herein to refer to system component or components into which information may be entered or otherwise recorded.

The terms “packet,” “datagram,” “segment,” or “frame” shall be understood to mean a group of bits that can be transported across a network. These terms shall not be interpreted as limiting embodiments of the present invention to particular layers (e.g., Layer 2 networks, Layer 3 networks, etc.); and, these terms along with similar terms such as “data,” “data traffic,” “information,” “cell,” etc. may be replaced by other terminologies referring to a group of bits, and may be used interchangeably.

Furthermore, it shall be noted that: (1) certain steps may optionally be performed; (2) steps may not be limited to the specific order set forth herein; (3) certain steps may be performed in different orders; and (4) certain steps may be done concurrently.

The present invention relates in various embodiments to devices, systems, methods, and instructions stored on one or more non-transitory computer-readable media involving the communication of data over networks. Such devices, systems, methods, and instructions stored on one or more non-transitory computer-readable media can result in the need for an adaptive credit-based flow control system.

It shall also be noted that although embodiments described herein may be within the context of an adaptive credit-based flow control system, the invention elements of the current patent document are not so limited. Accordingly, the invention elements may be applied or adapted for use in other contexts.

FIG. 2depicts a block diagram a sender/receiver system according to embodiments in this patent document.FIG. 2shows a sender210and a receiver220.

Sender210can be any node in an information handling system that can send information, packet, frame, etc. to a receiver220. Receiver220can be any receiving node in an information handling system that receives information, packet, frame, data traffic, etc. Sender and sender node are used interchangeably herein. Receiver and receiver node are used interchangeably herein.

FIG. 2shows that the receiver220sends a credit230from the receiver220to the sender210. The sender210sends data240only if it has an available credit. In embodiments described in this patent document, the sender210does not need to ask for a credit, but the receiver220can monitor the sender's queue and determine whether a credit is needed as described in reference toFIG. 3.

FIG. 2depicts a simple system with one receiver220and one sender210. However, one of ordinary skill in the art will understand that a system can have a plurality of senders and a plurality of receivers. Furthermore, each receiver can have a plurality of ports to receive information from any of a plurality of senders. The simplified version of a sender210and a receiver220is shown for ease of explanation. One of ordinary skill in the art will appreciate that any sender in the system can send to any receiver in the system.

FIG. 3depicts an adaptive credit-based flow control system according to embodiments in this patent document.FIG. 3shows a sender305and receiver310. As in the embodiment shown inFIG. 2, the receiver310can grant available credits330to the sender305. However, the embodiment shown inFIG. 3allows for a dynamically allocated shared buffer pool360across a plurality of ports in the receiver310, ports0335to N350. Each port has a portion of available buffer space345and355that can be granted by receiver310. Each port also has access to a shared buffer pool360in a memory management unit (MMU)365.

FIG. 3shows a sender305with port0315and a used320and available325buffer. The used and available buffers are the buffers that have been used and are available.FIG. 3also shows sender305with available credits330. Sender305can only send information if it has available credits330. The available credits330are granted by the receiver310and then advertised to the sender305.

Memory management unit365can be any memory. MMU365can include a physical memory and/or a virtual memory. MMU365can also comprise the management for translation between physical and virtual memory. MMU365can include application specific integrated circuits (ASICs), programmable logic devices (PLDs), flash memory devices, read-only memory (ROM), random-access memory (RAM) devices, and virtual memory devices.

In embodiments, receiver310maintains a per port queue size estimate370,375. The queue size refers to an estimate of the queue size of the sender305. The queue size370,375may be reported automatically by sender305. Each port335,350in the receiver maintains a peer queue size. Therefore, buffer space can be allocated as a function of the sender305queue size370,375. InFIG. 3only two ports, port0335and port N350are shown. However, one of ordinary skill in the art understands that any number of ports can be used, but are not depicted in the figure for ease of explanation.

In embodiments, a fixed amount345,355of the total buffer365can be reserved for each port335,350in the receiver310. The remaining buffer can be kept in a shared buffer pool360. The shared buffer pool360can be dynamically adaptively allocated to a port based on its demand. The demand is determined by the receiver310and stored with the peer queue size370,375.

Demand estimator in receiver310can compute an estimate of each of its peer links demands and allocate buffers proportionately based on each of the peer's demands. The peer links refers to other nodes that can be sender nodes305. Receiver310can share buffers360across ports.

Sharing of the buffer360across some or all ports for allocating credits may be done in a variety of ways. One example algorithm may use the following parameters: total available buffer in the shared pool360, a configurable control of the maximum percentage of the shared buffer360a port may use, and amount of buffers already consumed340from the shared pool from each port335,350.

Receiver310uses a demand estimator. Demand estimation for each port may be achieved by allowing each sender305to notify each receiver of its peer queue size370and375. Furthermore, each receiver port335,350has a peer queue size370associated with port0335and peer queue size375associated with port N350.

In embodiments, demand estimation for each peer can be achieved by allowing each peer to notify its queue state to receiver310. The sender305may notify its raw output queue size370and/or notify its rate of change of queue size. The peer queue size370and375may include either raw instantaneous queue size, rate of change of queue size, some other queue metrics, or any combination.

In embodiments, a notification of the queue size can occur automatically in periodic fashion. The period may be set by a system administrator or by the designer of the system. Alternatively, the notification of the queue size may be triggered when the queue size crosses a threshold. The threshold is depicted inFIG. 3by arrow380.

When the sender queue size exceeds the threshold380in either instantaneous queue size, rate of change of queue size, or both, the sender may be triggered to update the corresponding peer queue size370in receiver310.

Based on that notification, the receiver310maintains an estimate of peer queue size370and375for each of its peers. In embodiments, this estimate can be an instantaneous value derived from the latest notification. In other embodiments, the estimate can be a weighted average value derived from current and past notifications. In embodiments, the initial estimate of peer queue size can be set to the fixed amount of buffer assigned to the corresponding receiver port335.

In at least one embodiment, credit allocation is done by the receiver310for each peer. Credit allocation may be based on buffer availability345in the fixed buffer pool, estimate of peer queue size370, rate of change of peer queue size estimate, availability of the shared buffer pool360, and existing allocation and consumption of the shared buffer pool by the peer.

In embodiments, techniques from Fibre Channel credit-based flow control can be used for recovery of lost and stranded credits. For example, use timers at zero credits may be used to initiate a lost credit recovery. As another example a handshake may be used to recover stranded credits. For example, this recovery may use the following: the receiver may send a credit reclaim request, the sender may take the credits out of service and send a reclaim OK response, the credits may be returned to the credit pool.

Each sender305may transmit data from its queue only if it has enough available credits330from the receiver310. For each port335,350on the receiver310, a scheduler runs periodically to grant credits to the sender305. In one embodiment, the polling frequency of the scheduler can be at least twice as fast as the time it takes to drain the queue of its packet buffers. In other words, it should be at least equal to (2*link rate) or half the time taken to transmit data equivalent to queue size to avoid queue underruns.

In one embodiment as described above, a queue state notification is sent by the sender305once when the egress queue size crosses the congestion threshold380. In one embodiment, a default congestion threshold can be set to the value reserved as fixed buffer for the peer link in receiver310. The notification message may be sent with the same sampling frequency listed above by default as long as the queue size is above the congestion threshold. Alternatively, this could be overridden by configuration to use different notification intervals.

Receiver310updates the value of the corresponding peer queue size370estimate based on the notification message from sender305. In embodiment, receiver310advertises the credits to sender305. In embodiments, in normal operation, the sender305does not request any credits. The sender305reports the length of the queue for sender305. In embodiments, the sender305also reports the rate of increase of queue length periodically. In embodiments, the sender305can report its queue information to the receiver310only when an upper threshold380is crossed. In embodiments, the sender305can stop reporting to the receiver310when a lower threshold (not shown) is crossed.

Initially, when a sender node305and a receiver node310have a link startup, some parameters may be negotiated. These parameters include, sampling period of the queue, reporting mode and associated parameters, report queue length always or only report when the queue length crossed an upper threshold and stop when it goes below the lower threshold, report when the rate of queue length crosses an upper threshold and stop when it goes below the lower threshold. Additionally, the following parameters may be negotiated at link startup: size of each credit buffer, size of metadata used for internal functions within the receiver (for example, the results of classification and lookups) that is appended to each received packet and removed from each packet transmitted, frequency of credit advertisement, default credit units, number of credit class groups, mapping of traffic class to credit class groups, and support for implicit advertisement for default credit units.

In embodiments, the following parameters can be exchanged as part of each credit advertisement: number of credits allocated per credit class group, optional sequence number for every credit message that rolls over after a predetermined period. This sequence number may help ensure synchronization of the credits between the sender and receiver.

In embodiments, optional implicit credit advertisement can be implemented. In order to reduce chattiness on the link an optional extension may treat the advertisement of default queue size (from sender to receiver) and/or default credit units (from receiver to sender) as implicit and not to transmit them on the wire. The sequence number may be tracked for such implicit messages to distinguish between lost credits versus implicit credits.

FIG. 4depicts a flow chart showing a process of adaptive credit-based flow control from the perspective of the receiver according to embodiments.FIG. 4shows a receiver waiting for a time slot in the credit advertisement window405. The receiver may implement the process of adaptive credit-based flow control using various variables stored in a memory. In embodiments, different variable names may be selected.

The receiver sets the credit used equal to an updated value of the credits currently in use by that port (e.g., CreditUsed=UpdateCreditUsed(Port))410. In embodiments, the credit used can be incremented when a packet is received on the port and decremented when a packet is transmitted out its destination port(s). In embodiments, credit allocated is the amount of credit allocated. In embodiments, the port fixed buffer available is the amount of the fixed buffer that is available for that port. In embodiments, credit allocated can be set equal to a port fixed buffer available (e.g., CreditAllocated=Port.FixedBufferAvailable)410. The amount of port fixed buffer available can be set to zero (e.g., Port.FixedBufferAvailable=0)410. The port maximum shared pool buffer available can be set equal to the shared buffer pool allocated to this port based on factors such as the port's occupancy and total occupancy of the shared buffer pool as well as the activity of other ports in the system (e.g., Port.MaxSharedPoolBufferAvail=SharedPoolBufferAllocate(Port.SharedPoolBufferUsed))410. The receiver determines demand by looking at the port peer queue estimate and credit allocated415(e.g., Demand=Port.PeerQueueEstimate−CreditAllocated). In embodiments, the peer queue estimate is an estimate of the peer queue length.

The receiver determines if there is demand by seeing if demand is less than or equal to 0 (e.g., is Demand≤0?)420. If demand is less than or equal to zero, then the receiver determines if there are credits435, by seeing if credit is greater than or equal to zero (e.g., Is Credit>0?)435.

If demand is not less than or equal to zero, then the receiver checks to see if demand is less than the maximum shared pool buffer available for this port (e.g., Is Demand<Port.MaxSharedPoolBufferAvail?)425. If the demand is less than the port maximum shared pool buffer available, then credit allocated is set to the port peer queue estimate (e.g., CreditAllocated=Port.PeerQueueEstimate) and the port shared pool used is set to the shared pool buffer used by the port plus the demand (e.g., Port.SharedPoolUsed=Port.SharedPoolBufferUsed+Demand)455. In embodiments, Credit is the credit that will be advertised to the remote peer. Credit is set to credit allocated minus credit used (e.g., Credit=CreditAllocated−CreditUsed)460. The receiver also checks if credit is greater than or equal to zero435.

If the demand is not less than the maximum shared pool buffer available for that port, then credit allocated is set to credit allocated plus the maximum shared pool buffer available for that port (e.g., CreditAllocated=CreditAllocated+Port.MaxSharedPoolBufferAvail)430. Also, the port maximum shared pool buffer available is set to zero (e.g., Port.MaxSharedPoolBufferAvail=0)430.

The receiver also checks if credit is greater than or equal to zero (e.g., Is Credit>0?)435.

If the demand is less than or equal to zero, then the receiver also checks if credit is greater than or equal to zero (e.g., Is Credit>0?)435. If the credit is not greater than zero, then the receiver waits for a time slot in the credit advertisement window405.

If the credit is greater than zero, then the receiver checks to see if the credit is not equal to default credit unit (e.g., Is Credit not equal to Default Credit unit?)440. If not, an implicit advertisement may be used, and then the receiver waits for a time slot in the credit advertisement window405. If so, then the receiver grants credit units to a peer445. The receiver also advertises credit units to the peer450. The receiver also waits for a time slot in the credit advertisement window405.

FIG. 5depicts a flow chart showing a process of adaptive credit-based flow control from the perspective of the sender according to embodiments in this patent document.FIG. 5shows a sender checking to see if a queue is non empty510. If a queue is not non empty, then the sender continues to check to see if the queue is non empty510.

If the queue is non empty510, then the sender gets the packet size for the next packet to be dequeued (e.g., Packet.size=Get packet size for the next packet to be dequeued)520. The sender checks to see if the packet size is less than or equal to the credits available for the queue (e.g., Is Packet.size≤credit available for the queue?)530. If the packet size is less than or equal to the credits available, then the sender adjusts the number of credits (e.g., Credit=credit−Packet.size)550and transmits the packet560. The sender then checks the queue to see if it is non-empty510.

If the packet size is not less than or equal to the credits available530, the sender waits for credits to be granted540and checks the queue size to see if it is non-empty510.

In embodiments, the adaptive credit-based flow described in this patent document can be used for multiple classes of traffic per port. In those embodiments, the adaptive credit-based flow would be used for each class of traffic on each port. For example, in a system with p ports and n classes of traffic per port, the algorithm would run as if it had (p*n) ports.

FIG. 6depicts a flow chart of an algorithm for estimating peer queue size according to embodiments in this patent document. In embodiments, there can be different algorithms used to compute a peer queue estimate. In embodiments, the peer queue estimate may be based on an instantaneous queue size from peer queue length reports as shown inFIG. 6. For example, a receiver may receive a peer queue estimate report from a peer. The receiver can use the algorithm:
PeerQueueEstimate=(1−w)*OldPeerQueueEstimate+w*CurrentQueueLength

where PeerQueueEstimate is an estimate for queue size, OldPeerQueueEstimate is the previous peer queue estimate, CurrentQueueLength is the queue size currently reported, and w is a user configurable weight for deciding how much weight the current value of the queue length has on an estimated value.

FIG. 6shows initializing a previous queue estimate by setting previous queue estimate to zero (e.g., OldPeerQueueEstimate=0)610. In embodiments, a receiver waits for a queue length report from a peer620. The current queue length is set to be read from the current queue report (e.g., CurrentQueueLength=Read current queue length from report)630. The above peer queue estimate can be used (e.g., PeerQueueEstimate=(1−w)*OldPeerQueueEstimate+w*CurrentQueueLength)640.
PeerQueueEstimate=(1−w)*OldPeerQueueEstimate+w*CurrentQueueLength

where PeerQueueEstimate is an estimate for queue size, OldPeerQueueEstimate is the previous peer queue estimate, CurrentQueueLength is the queue size currently reported, and w is a user configurable weight for deciding how much weight the current value of the queue length has on an estimated value.

The previous peer estimate may be set to the current peer queue estimate (e.g., OldPeerQueueEstimate=PeerQueueEstimate)650. The receiver then waits for the queue length report from a peer620.

FIG. 7depicts a flow chart for peer queue size estimation according to embodiments in this patent document. In embodiments, another algorithm may be used to compute estimated queue length. That algorithm is based on instantaneous queue size and rate of change of queue size from peer length reports.

FIG. 7shows initializing a previous peer queue estimate and previous queue rate of change by setting them equal to zero (e.g., OldPeerQueueEstimate=0 and OldPeerQueueRateChange=0)710. Also, a minimum queue size that can always be guaranteed for each port is set, for example, setting minimum queue size to the fixed buffer reserved for each port (e.g., MinQueueSize is set to a value that can always be guaranteed for each port)710. The receiver waits for a queue length report from a peer720. In embodiments, the receiver sets the current queue length to read current queue length from the report from the peer (e.g., CurrentQueueLength=Read current queue length from report)730.

In embodiments, the current queue rate of change is set to the queue difference from the report (e.g., CurrentQueueRateChange=Read queue delta from report)730. In embodiments, the algorithm740used to compute the queue length estimate is similar to the algorithm disclosed inFIG. 6:
AvgPeerQueueEstimate=(1−w)*OldPeerQueueEstimate+w*CurrentQueueLength

where OldPeerQueueEstimate is the previous peer queue estimate, CurrentQueueLength is the queue size currently reported, and w is a user configurable weight for deciding how much weight the current value of the queue length has on an estimated value.

Also, the algorithm740used to compute the average queue rate of change is:
AvgQueueRateChange=(1−m)*OldQueueRateChange+m*CurrentQueueRateChange

where AvgQueueRateChange is an estimate for rate of change of the peer queue, OldQueueRateChange is the previous queue rate of change, CurrentQueueRateChange is the queue rate of change currently reported, and m is a user configurable weight that determines the sensitivity of the current sample of the rate of change of queue size to its historical values with respect to the estimated value.

In embodiments, the peer queue estimate is set to the average peer queue estimate and the average peer queue rate of change (e.g., PeerQueueEstimate=AvgPeerQueueEstimate+AvgPeerQueueRateChange)750. If the peer queue estimate is less than minimum queue size (e.g., PeerQueueEstimate<MinQueueSize?)760, then the peer queue estimate is set equal to a minimum queue size (e.g., PeerQueueEstimate=MinQueueSize)770. If the peer queue size estimate is not less than minimum queue size760, then the previous peer queue size is set equal to the peer queue estimate (e.g., OldPeerQueueEstimate=PeerQueueEstimate)780. Also, the previous peer queue rate of change is set equal to the average queue rate of change (e.g., OldPeerQueueRateChange=AvgQueueRateChange)780. In embodiments, the receiver then waits for the queue length report from a peer720again.

FIG. 8depicts a plot of average queue size for varying weight, w, according to embodiments in this patent document.FIG. 8shows four plots showing a different for varying weight, w. Plot810shows current queue size and is show in a dotted line. Plot820shows an average queue size for w=0.5 and is shown in a solid line inFIG. 8. Plot830shows average queue size for w=0.75 and is shown in a dashed, dotted line inFIG. 8. Plot840shows an average queue size for w=0.25 and is shown in a dashed line inFIG. 8.

FIG. 9depicts a plot of average queue size for varying weight, m, according to embodiments in this patent document.FIG. 9shows four plots of instantaneous queue size and average queue size for varying weights, w and m. Plot910shows average queue size for m=0.5 and w=0.2 shown inFIG. 9as a dashed line. Plot920shows average queue size for m=0.75 and w=0.2 shown inFIG. 9as a solid line. Plot930shows average queue size for m=0, w=0.2 and is shown as a short dashed line inFIG. 9. Plot940shows current instantaneous queue size and is shown inFIG. 9as a long dashed line. As one of ordinary skill in the art will appreciate, a larger value of m or a larger value of w will put more weight on the current queue length or change in queue length than the weighted average. These parameters offer tuning knobs.

FIG. 10depicts a block diagram of an information handling system1000according to embodiments in this patent document.FIG. 10depicts a block diagram of an information handling system1000according to embodiments of the present disclosure. It will be understood that the functionalities shown for system1000may operate to support various embodiments of an information handling system—although it shall be understood that an information handling system may be differently configured and include different components. As illustrated inFIG. 10, system1000may comprise a plurality of I/O ports605, a data processing and fabric component or processor1015, tables1020, and a switch control functionality processor1025. In embodiments, the I/O ports1005are connected to one or more nodes. The data processing functionality1015may use information included in the network data received at the device1000, as well as information stored in the tables1020, to identify a next hop for the network data, among other possible activities. In embodiments, the switching fabric then schedules the network data for propagation through the device to an egress port for transmission to the next hop.

Embodiments in this patent document address key limitations of the prior art credit-based flow control mechanism. In embodiments, the need to have a request/grant mechanism is removed. Delays due to the synchronization requirements are removed and thereby not impacting the ability to meet line rate forwarding requirements for his speed links. Thus, latency is improved.

In embodiments, a mechanism to provide visibility of queue state of the sender is enabled and buffer sharing across all ports can be implemented on systems that use shared output buffer model.

One of ordinary skill in the art will appreciate that various benefits are available as a result of the present invention.

It shall be noted that elements of the claims, below, may be arranged differently including having multiple dependencies, configurations, and combinations. For example, in embodiments, the subject matter of various claims may be combined with other claims.