Nalanda

Citation: Clark, D. D., Shenker, S., and Zhang, L. 1992. Supporting real-time applications in an Integrated Services Packet Network: architecture and mechanism. In Conference Proceedings on Communications Architectures & Protocols (Baltimore, Maryland, United States, August 17 - 20, 1992). D. Oran, Ed. SIGCOMM ‘92. ACM, New York, NY, 14-26. DOI= http://doi.acm.org/10.1145/144179.144199

It was odd reading this paper alongside Shenker’s. Although it is from three years earlier, it seems much more modern, almost prescient in its analysis. Clark et al., propose a unified architecture that provides different kinds of service - predicted and guaranteed - to real-time applications, in addition to supporting traditional datagram applications. In particular, a class of real-time applications called play-back applications is considered, in which data is buffered at the receiver up to a playback point (which can be thought of as a delivery deadline), and then played on the client, to reduce jitter. Assuming that the majority of future real-time applications will be of this nature, the authors use the requirements of play-back applications to drive their architecture: sensitivity to delivery delay, information about estimated delay to set playback points, indifference to delivery so long as it is before the playback point, and limited tolerance to loss.

Analysing real-time applications along two axes - tolerance to brief interruptions and rigidity of delay requirements - the authors show that the dominant classes of such applications would be intolerant/rigid and tolerant/adaptive. Intolerant/rigid applications need guaranteed service with a priori limits on delay bounds, while tolerant/adaptive applications only need predicted service, as they will dynamically adjust their playback points to suit network conditions.The discussion of the packet scheduling algorithm for this architecture is motivated by these considerations, as it points to a need to separately consider the isolation of flows (to minimise effects of one flow on another), and sharing of bandwidth (to allow operation in a unified network).

A counter-intuitive result is that FIFO queueing works better than WFQ to satisfy the sharing requirement. Where WFQ penalizes sources with bursts of packets, FIFO passes them through as a unit, providing better control of delay bounds for real-time applications, but penalizing other flows as a result. Conversely, WFQ provides better isolation than FIFO, as it minimises the effects of bursty sources on other flows. The authors propose a new scheme, FIFO+, which allows sharing of jitter across multiple hops. A new header field maintaining the difference between the delay for a packet, and the average delay for its aggregate class, is maintained by switches, allowing insertion of a packet into the queue to minimize delay.

The unified algorithm that is presented is based on timestamp-based WFQ at the highest level, to serve flows that required guaranteed service, along with a pseudo-flow encapsulating predicted service flows and datagram flows, which is managed under a FIFO+ regime. This pseudo-flow maintains multiple classes of service, shifting jitter from higher classes of predicted service to lower, with datagram flows being at the lowest level, since they are most resistant to jitter. Admission control is used within each class to maintain delay bounds. This strikes a good balance, as guaranteed flows and the different classes of predicted service and datagram flows are isolated from one another, with jitter shared by progressively shifting it down to the lowest class.

The network fixes the clock rate for each guaranteed service flow, with no further checks on behaviour. Predicted service flows must declare the parameters for their service characterization (token bucket rate and size), and request a maximum delay and tolerable loss rate, to allow the network to assign the flow to an appropriate aggregate class, and also to make admission control decisions based on whether or not a source with these declared parameters can be carried. To maintain good shared behaviour, the network enforces conformance to the service characterization for predicted service flows.

I really enjoyed the discussion in this paper, especially the separation of concerns for sharing and isolation. Most of all, I liked the FIFO+ scheme, as it recalls XCP, but at the same time has no requirements of trust on endpoints; the assumption that switches trust one another seems far more reasonable.