This paper introduces a scalable maxmin flow control protocol which guarantees the minimum rate for each connection-oriented flow without requiring per-flow information. The protocol is called MR-ASAP (minimum rate guaranteeing adaptive source-link accounting protocol). MR-ASAP is an extension of ASAP, the first exact maxmin flow control protocol for best-effort connection-oriented traffic in integrated service networks, without requiring per-flow accounting at the intermediate network node. In the classical maxmin computation, only the maximum rate constraints are considered; in this paper the minimum rate requirements are treated similarly as the maximum rate constraints. Existing protocols that achieve exact maxmin optimality with minimum rate guarantee require per-flow information and complex computation such as sorting of the minimum rates at the switch. By generalizing the concept of constraint, the complex sorting and per-flow accounting required in the existing protocols are avoided. Simulation demonstrates fast convergence to optimality.

This paper re-examines maxmin protocols for ABR traffic in ATM networks in four aspects: convergence, complexity, variations, and performance. First, the concept of "pseudo-saturation" is introduced. Most, if not all, protocols do not properly handle pseudo-saturated links, and as a result, there is no guarantee for convergence to true maxmin solutions. Second, the concept of "constraint precedence graph (CPG)" is introduced and is used to define the best possible time complexity of any maxmin protocol. The existing complexity estimates are overly conservative because they do not consider possible concurrent operations. In contrast, the CPG analysis explicitly accounts for parallelization. Third, the concept of "constraint" is generalized and this generalization is used to derive an optimality condition for the maxmin problem with nonzero minimum cell rate (MCR) requirements. This optimality condition can be used in conjunction with any maxmin protocol to handle the nonzero MCR requirements without adding excessive complexity. Finally, simulations suggest that the complexity analysis is inadequate to gauge protocol performance. A new analysis based on protocol dynamics is called for to understand the performance.

Resource allocation in complex real-time computer systems (RTCSs) cannot be adequately handled by straightforward extensions of the CPU and peripheral device scheduling techniques used in non-RTCSs. Rather, all the resources including CPUs, peripheral devices, communication channels, etc. should be handled in an integrated manner. As an idealistic framework we laid out a globally optimal resource allocation methodology based on the benefit loss function (BLF), which includes both static resource allocation and design of dynamic resource allocation algorithms. As a small experimental part of this research we also designed and implemented a BLF-driven thread scheduler (CPU scheduler) on Solaris 2.3. This experiment showed that existing processor scheduling approaches were not competitive against a quickly developed BLF-driven scheduling approach with respect to minimizing the total benefit loss. Therefore, the BLF-driven resource allocation approach opens doors for many new worthwhile research efforts.