CS-534: Packet Switch Architecture
Spring 2003		 Department of Computer Science
© University of Crete, Greece

6.3   Per-Flow versus Indiscriminate Flow Control

[Up: Table of Contents]
[Prev: 6.2 Credit-Based FC]
[Next: 6.4 Backpressure in Fabrics]

6.3.1   Problems with Indiscriminate Flow Control or Queueing:

Indiscriminate Lossless FC => Head-of-Line Blocking

Indiscriminate (FIFO) Queueing is Unfair (the parking lot problem)

Shared (FIFO) Queueing with Fair (per-flow) Rate Control is slow in enforcing fairness

6.3.2   Per-Flow Queueing and Flow Control:

Solution: Per-Connection (per-flow) Queueing & Flow Control

Communication Cost versus Buffer/Logic Cost

How Many Windows of Buffer Space?

Static Allocation of Windows to Connections:
The simplest organization for lossless flow control without HOL blocking, --i.e. per-connection queueing and per-connection (credit) FC-- is to statically dedicate one window's worth of buffer space to each and every connection that passes through the switch. Given the above figures, this is economically viable if the number of connections is relatively restricted (e.g. up to a few thousand), or if the ratio of peak to average throughput per connection does not exceed a few thousand. The numbers go as follows in this latter case: call PAR this peak-to-average ratio, and assume for simplicity that it is the same for all connections on the given link (i.e. consider the largest of these ratios, among all connections). Then, the window size for connection VCi is: RTT * peakThroughput(VCi) = RTT * PAR * avgThroughput(VCi). The sum of the average throughput of all connections passing through a given link cannot exceed the throughput of the link. Hence, the total size of all of the above windows, for all connections VCi, is no greater than RTT * PAR * throughput(Link) = PAR * windowL, in the above terminology. If PAR is no more than a few thousand, this scheme is economically viable according to the figures presented above.

Dynamically Sharing the Buffer Space among the Connections:
Even though the static allocation scheme above is economically viable in many or most practical situations, it is usually possible to achieve comparably good performance using even less memory space for buffering. This is achieved by dynamically sharing the available buffer space among all active connections, according to various management algorithms. All such algorithms restrict each connection VCi to never use more than windowSize(VCi) = RTT * peakThroughput(VCi) space in the shared buffer. However, given that not all windows of all connections can fit in the available buffer space at the same time, the management algorithms place additional restrictions on the use of buffer space when the total buffer starts filling up. Two such management algorithms that have appeared in the literature are:

[OzSV95] C. Ozveren, R. Simcoe, G. Varghese: ``Reliable and Efficient Hop-by-Hop Flow Control'', IEEE Journal on Sel. Areas in Communications, vol. 13, no. 4, May 1995, pp. 642-650.

[KuBC94] H.T. Kung, T. Blackwell, A. Chapman: ``Credit-Based Flow Control for ATM Networks: Credit Update Protocol, Adaptive Credit Allocation, and Statistical Multiplexing'', Proceedings of the ACM SIGCOMM '94 Conference, London, UK, 31 Aug. - 2 Sep. 1994, ACM Comp. Comm. Review, vol. 24, no. 4, pp. 101-114.

The [OzSV95] is the simpler of the two proposals; it calls for two window sizes for each connection, one equal to the full RTT * peakThroughput(VCi) which is applied when the total buffer is relatively empty, and another, reduced window size that is applied when the buffer starts filling up.

Subsequent to the above two studies, an alliance of some 20 commercial companies was formed, who developed and published a specification for a credit-based flow control protocol on a per-connection basis, with dynamically shared buffer space. This is known as the QFC ("Quantum Flow Control") protocol. A number of companies in the QFC alliance have incorporated the QFC protocol in products of theirs. Standardization work for this protocol is under way, through the ITU-T; within the ITU-T, this protocol is known as "Controlled Dynamic Transfer" (CDT). The QFC protocol and various documentation related to it can be found at the following web site:

[QFC95] Quantum Flow Control Alliance: ``Quantum Flow Control: A cell-relay protocol supporting an Available Bit Rate Service'', version 2.0, July 1995; http://www.qfc.org

The QFC protocol is even simpler than the [OzSV95] proposal: it specifies a window per connection, whose size stays fixed independent of the overall buffer occupancy. In addition to the per-connection windows, QFC, like [OzSV95], uses a ``global window'' per link to make sure that the overall buffer does not overflow. In order for a cell to depart, it must acquire both a credit for its own connection's window, and a credit for the overall global window. Normally, the global window is smaller than the sum of the windows of all connections that traverse the link.

[Up: Table of Contents]
[Prev: 6.2 Credit-Based FC]
[Next: 6.4 Backpressure in Fabrics]
Up to the Home Page of CS-534
 		 © copyright University of Crete, Greece.
Last updated: 16 May 2003, by M. Katevenis.