Flow Control and Routing
High Speed Networks
A Research Project Funded by the National Science Foundation
(Presidential Young Investigator Grant, 1991-1997)

Principal Investigator: R. L. Cruz
Project Summary

Summary of Results

  • Deterministic Service Definition. The notion of a traffic envelope, introduced by the PI, has been widely adopted by the networking research community. Briefly, a traffic envelope is a function f(t) which bounds the amount of traffic crossing a boundary in all intervals of time of length t. The most popular example is where f(t) is equal to a constant plus a term proportional to t, which corresponds to a so-called "leaky bucket" traffic shaper. The notion of a traffic envelope has been incorporated into networking "standards," for example within the context of UPC (Usage Parameter Control) of the ATM standard, within the so-called "T-Spec" of the "Guaranteed" and "Controlled Load" service classes proposed by the integrated services (IntServ) working group of the IETF, and within the Differentiated Services (DiffServ) working group of the IETF. Related to acceptance of this traffic model, there has been a widespread interest in development of scheduling algorithms for provision of quality of service. For example, the popularity of the so-called "Weighted Fair Queueing" (WFQ) class of schedulers is attributable to the fact that hard delay bounds can be obtained if the arriving traffic is conformant to an envelope. One of the most important contributions obtained during the course of the project was the development of the concept of a service curve. Early developments were reported in [2], and this was refined in [3] and [7]. This, in turn, has led to a more modern definition of a service curve, which is central to a mathematical framework that some have called "network calculus." The modern concept of a service curve is somewhat analogous to the concept of the impulse response of a linear time invariant system. In particular, the departure process of a network element is bounded by the arrival process to the network element "convolved" with the service curve, where the convolution is defined within the so-called "min-plus" algebra. Essentially any scheduling algorithm can be described in terms of a service curve, and conversely scheduling algorithms can be synthesized to meet a service curve specification [11]. The IntServ working group of the IETF has proposed using two parameter service curves within IP routers, configured using the RSVP protocol for signalling. The service curve concept may also prove useful within the context of DiffServ, where the service curve definition may be applied to traffic aggregates.
  • Closed Loop Flow Control. Analysis of tandem queues with finite buffers and blocking is a challenging mathematical problem, because of the interaction between queues caused by the blocking. This problem is central to closed loop flow control algorithms, such as window flow control. Reference [1] reported results for this problem using a deterministic traffic model as described above. In particular, lower bounds on buffering requirements to attain maximum throughput were derived. Subsequently, it was realized that the service curve concept could be applied to this problem. In particular, in [14],[15], the service curve of a closed loop flow control system is derived in terms of the service curves of constituent network elements, which model propagation delay and scheduler latency. A conceptually elegant result is that the system service curve is analogous to the impulse response of a linear feedback system, within the context of classical linear system theory. These results have lead to a better understanding of window flow control. Hopefully, this will lead to the design of protocols which utilize network resources more efficiently.
  • Probabilistic Extensions of Deterministic Approaches. This project also considered how sample-path based results can be used to obtain results with probabilistic models. In [4], a novel closed form expression for the loss process of a single server queue was obtained. This sample path result was then used to obtain bounds on the loss rates. This was obtained assuming a stochastic traffic envelope for arriving traffic, which bounds the Laplace transform of the distribution of the amount of traffic arriving over intervals of time. This model, developed by C. S. Chang (and related to work by J. Kurose, O. Yaron, and M. Sidi), is a natural stochastic extension of a deterministic traffic envelope. In a similar manner, reference [3] discusses bounds on the statistical distribution of end-to-end queueing delay in ATM networks.
  • High Speed Switching and Routing. This project has included work on the subject of "deflection", or "hot-potato" routing, where routes are dynamically adjusted based on congestion on a short time scale. References [8] and [10] concern maximum and average delay for deflection routing in regular topologies. References [6],[9],[12] are concerned with synthesis of interconnection network topologies for which deflection routing is efficient.
  • Polling Systems. Reference [5] concerns sample path analysis of exhaustive service polling systems. Bounds on buffer requirements and maximum delay are obtained in terms of the solution to a linear optimal control problem.
  • Curriculum Development. Many of results obtained during the project have been incorporated within the syllabus of an undergraduate course sequence on the subject of Data Networks (ECE 158AB) taught at UCSD. A set of course notes is under development. As the theory of ``network calculus" matures further, it is likely that these notes will be developed into a textbook oriented towards quantitative analysis of data networks.