A fundamental component of high-speed optical networking equipment designs are a low-cost, high-bandwidth interface for the network processors. Traditionally, designers have implemented these high-speed interfaces using per-port FIFO queues for input buffering and flow control in the ingress path. However, with the number of port increasing over comm interfaces, this form of static allocation becomes impractical due to excessively large storage requirement.
Fortunately, a solution is on the way. Through the use of a dynamic allocation scheme, designers can rework their input buffering approaches and improve the movement of data across high-speed interfaces. In this two-part series, we'll explore the new credit-based flow control scheme and buffer-management architecture. In Part 1, we'll look at the traditional methods for input buffering and the problems these methods provide. In Part 2, which will appear online tomorrow, we'll further the discussion by looking at the new dynamic input buffering architecture.
Living in a SPI World
Over the past several years, the system packet interface (SPI) has emerged as a dominant interface for connecting network processors, switch fabrics, framers, and a host of other components in a Sonet/SDH design. As such, the SPI supports transmit and receive data transfers at clock rates independent of the actual line bit rate. Additionally, it is designed for the efficient transfer of both variable-sized packet and fixed-sized cell data.1.
Figure 1 shows the model of a typical SPI bus. The fundamental requirement of the bus is to transfer data from ports on the source device to the corresponding ports on the sink device. The receptor of data (the sink) indicates the availability of space in its port FIFOs to the initiator of data transfer (the source). The source selects a particular port and initiates transfer on the bus based on the occupancy status feedback from the sink and the availability of data for that port in its local port FIFOs. The source's selection policy and sink's status indication policy are implementation specific.
Figure 1:Model of a typical SPI bus.
Traditional interfaces between chips in a Sonet/SDH system supported fewer ports and low aggregate interface bandwidth. Status feedback used either "polling" or "direct-status indication" and the selection policy was generally plain round robin. In direct status indication, the sink provides a dedicated status indication line for each of its port FIFOs. This method is impractical for large number of ports (typically more than four) because of the number of pins required from the sink to the source.
In the polling method, source cycles the port addresses on its address bus in a plain round robin or weighted round robin (WRR) order and logs the status returned by the sink on the multiplexed status line. Ready status indication by a sink port during polling indicates the sink port's ability to accept one payload transfer burst from the source. After selecting a port once, the source does not initiate another transfer for the same port until it gets the latest status update through a new polling hit for that port. The above two status indication schemes are illustrated in Figure 2.
Figure 2: Diagram showing the direct and polling status indication schemes.
Getting Credit
In general, today's OC-192 systems require interfaces between chips to feature 256 or more ports.2. Typically, these OC-192 interfaces also employ credit-based flow control.
In the credit-based flow control scheme, credits are allocated by the sink to the source for a particular port. This allocation refers to the number of payload transfer bursts that the source is allowed to send to that port. Credit allocation to the source for a particular port is done through an indication of the port's occupancy on sink. The port occupancy status directly co-relates to a quanta of transfer credit. The sink frames port status information according to a programmable rate based WRR. This ensures fair status update for all ports.
In the credit-based flow control method, both source and sink use the same WRR policy with same port rates and initial seed. This enables the source to decode the port address for each status sent from the sink. the source decodes the status information received from the sink, accumulates port credits, and performs selection of ports for transfer of data.
A memory-based, pre-programmed calendar sequence comprising of different port addresses according to WRR policy can also be used for credit allocation. This form of status indication from the sink in combination with an appropriate selection policy of ports at the source can maintain rate fairness among ports. Credit allocation allows the source to perform successive selections of a port without having to wait for a new status update for the port after every selection.
The requirement for input buffering on bus interfaces can be explained as follows. Physical ports on the interface have to be differentiated based on their rates. Per port queuing in the input buffer with associated backpressure mechanism through the status channel allows regulation of port rates on the bus. The input buffer between the SPI sink bus interface and the system allows processing order of the system to be independent of the order of data transfer on the bus. The input buffer also absorbs transient bursts on the bus interface. It may also perform the function of decoupling the operating frequency of the system logic from the frequency of the bus interface.
Sink Buffer Design Considerations
For very low number of ports, dedicated per-port FIFOs can be used for input buffering on the SPI sink interface. For large number of ports, per-port FIFO is not a viable approach due to the hardware overhead involved. Another approach is to distribute a common memory among active ports by logically partitioning the memory. Effectively each active port has a FIFO, but all of them share the read and write ports of the memory.
Both approaches described above can be grouped under "static-allocation schemes" because fixed-size buffer space is allocated to each active port during configuration. The size allocated to a port need not be dependent on its rate; it depends on the burstiness of the traffic for that port and a few other parameters, which will be introduced below. FIFO space for each port is provided a threshold. As long as the space in a port's FIFO is greater than this threshold, the sink indicates its ability to accept one threshold worth of transfer. Each port has a single bit for status indication. Figure 3 shows the organization of the buffer space and the status indication logic for a port.
Figure 3: Organization of buffer space in the statically allocated scheme.
Inefficiencies in the Static Scheme
Now that we've laid out the static-allocation method, let's look at why this scheme is inefficient implementation in some situations. Any hardware implementation of SPI will introduce some latency in the data path and status channel. This could be due to crossing of asynchronous clock boundaries, processing pipelines, and memory latencies, to name a few.
Figure 4 shows that the overall latency is made up of three components: datapath latency, status-channel latency, and scheduler-response latency. Datapath latency is the delay from the point of selection of a port at the source, to the time when the data for that port is actually written into the sink FIFO. Similarly, status-channel latency is the delay from the point of status lookup for a port at the sink FIFO interface, to the time when this status information actually appears on the status bus at the source.
Scheduler latency refers to implementation specific delays in the source's scheduling policy. This is the delay from the point of receiving a status update over the FIFO status channel, to the reaction of that update on the data path. This overall response latency will henceforth be addressed as "feedback-response latency" and the buffer equivalent of this latency will be referred to as "latency threshold".
Figure 4: Latency is made up of three components: datapath latency, status-channel latency, and scheduler-response latency. All three are depicted here.
Feedback-response latency has an impact on the performance and design of the input buffer in the sink datapath. With occasional discrepancies in read and write rates, this latency can cause queue size build up and data loss due to overruns on the port FIFOs even though a back off mechanism is provided by way of the status feedback channel.
To illustrate the problems caused by feedback-response latency, let's look at an example for a SPI interface using a credit based flow control mechanism. In our example, a single active port occupies the entire interface bandwidth. This port is allocated space worth five buffers (where one buffer is equivalent to payload transfer burst size) in its FIFO, and read out from this FIFO is disabled. Assume that the status channel frequency is such that the source receives one status update for the active port for each payload burst transfer period on the bus.
For simplicity, let's neglect the source scheduler latency. Let datapath latency, Ld, be equivalent to three buffers. Similarly let status-channel latency Ls be equivalent to two buffers. For every selection, the source sends one buffer worth of data to the sink and decrements its credit by one.
Status indication from the sink uses a single bit. When status is sampled low, the source updates its transfer credit to five buffers and when the status is sampled high, the source can transfer data using any pending credit. The timing relation in Figure 5 shows that in this scenario the sink buffer can suffer a data overrun worth the total feedback response latency of five buffers.
Figure 5: Diagram of FIFO overrun.
An ideal buffer design and flow-control mechanism should ensure that there are no data losses due to overruns. To solve this problem, designers can employ a look-ahead indication of the FIFO status. Thus, any port FIFO would indicate a full status when it is latency threshold transfers short of being actually full. Effectively we are providing an additional threshold space in the FIFO to allow us to absorb any overruns due to latency.
Buffer on the Under Run
In addition to causing overrun problems, feedback-response latency creates another phenomenon called buffer under run. A buffer on a sink port is said to have been under run when it becomes completely empty and remains in the empty state for some time even though the source has data to send for that port. This happens because the source has used up previously allocated credit and does not have a new update of the empty status of sink FIFO due to feedback response latency. In order to guard against potential buffer underflow, the lower threshold of status indication must be set high enough to allow the source to respond to the state of lowest FIFO occupancy in a reasonable length of time. Thus, additional buffer space is required to prevent buffer under run.
To prevent under run problems, designers must statistically allocate a buffer. The allocated buffer size for all the ports must be at least twice the latency threshold in order to prevent buffer under run and overrun.
A fixed set of memory must be allocated for latency threshold on all the active ports irrespective of whether there is a possibility of overrun in a given configuration. This fixed allocation amounts to a huge memory requirement. In situations where read out of the port FIFOs is happening at a high rate, or the rate distribution, rate violation and the number of active ports is such that the possibility of an overrun on the ports is reduced, the allocated threshold space remains unutilized on all ports. There could also be a situation where bursty traffic clogs up some of the ports using up their latency threshold, while some other port FIFOs remain under utilized (Figure 6).
Figure 6: Static allocation of overrun threshold.
On to Part 2
That wraps up Part 1 in our two-part series. In Part 2, we'll propose a new architecture for the design of input buffer. This new architecture, called the dynamic-allocation scheme, will overcome the limitations in the traditional static-allocation scheme. To view Part 2, click here.
References
- OIF Electrical interfaces white paper.
- Implementation Agreement OIF-SPI4-02.0
- Y. Tamir and G. L. Frasier, "Dynamically-Allocated Multi-Queue Buffers for VLSI Communication Switches," in IEEE Transactions on Computer, 41(6): 725-737, June 1996.
- G. L Frasier and Y. Tamir, "The Design and implementation of a multi-queue buffer for VLSI communication switches," in Proc. Int.Conf. Computer. Deisgn, Cambridge, MA, Oct. 1989, pp.466-471.
- R. Sivaram, C. B. Stunkel, and D. K. Panda, "HIPIQS: A High-Performance Switch Architecture using Input Queuing," in Proceedings of the IPPS/SPDP '98, Oregon, FL, Mar. 1998, pp. 134-143.
- N. Ni, M. Pirvu, and L. Bhuyan, "Circular Buffered Switch Design with Wormhole Routing and Virtual Channels", in Computer Design: VLSI in Computers and Processors, 1998. ICCD '98. Proc.Int. Conf. Comput. Design, 1998, pp. 466 -473.
- Santosh Krishnan, Abhijit K. Choudhury, Fabio M. Chiussi, "Dynamic Partitioning for Shared-Memory Management," IEEE INFOCOM '99, April 99.
- G. Kornaros, C. Kozyrakis, P. Vatsolaki, M. Katevenis: "Pipelined Multi-Queue Management in a VLSI ATM Switch Chip with Credit-Based Flow-Control," Proceedings of the 17th Conference on Advanced Research in VLSI (ARVLSI), Ann, MI, September 1997 (p.127-144).
About the Authors
Joji Philip is a senior design engineer at Paxonet Communications (India) Ltd. Joji can be reached at joji@pune.paxonet.com.
Sailesh Kumar is a senior design engineer at Paxonet Communications (India) Ltd. Sailesh can be reached at sailesh@pune.paxonet.com.
Sunil Shukla is a senior design engineer at Paxonet Communications (India) Ltd. Sunil can be reached at sunil@pune.paxonet.com.
Raja Venkatesh is a senior design engineer at Paxonet Communications (India) Ltd. Raja can be reached at raja@pune.paxonet.com.
