A non-per-VC accounting max-min protocol for ABR flow control (ASAP) and its multiple-time-scale extension

This dissertation introduces a new rate-based (RB) max-min flow control protocol for ABR traffic, which is called Adaptive Source-link Accounting Protocol or ASAP for short. ASAP is the FIRST RB proper max-min protocol which DOES NOT require per-VC-accounting. Extensive simulations of ASAP and other popular RB max-min protocols demonstrate the significant advantages of ASAP as follows: (1) Since ASAP does not rely on per-VC-accounting, the protocol is very simple and scalable; (2) ASAP is based on the Bottleneck ID (BID) scheme first introduced in this dissertation, which makes the protocol very stable during transient periods; (3) ASAP converges very fast to the max-min optimality; (4) ASAP is robust in the presence of various network disturbances such as dynamic changes in background traffic and dynamic creation and termination of ABR VC's.; Secondly, ASAP is extended by adding the Multiple-Time-Scale (MTS) property which was first introduced in our earlier publications [Hu98a, Hu98b, Tsa98c]. The fundamental principle of the MTS approach is that the available bandwidth should be allocated only to those VC's that can utilize it in a timely manner. A new MTS protocol is proposed and incorporated into ASAP resulting in a protocol called ASAP-MTS. In ASAP-MTS, a new scheme is used to classify VC's into short-latency and long-latency classes in order to maximize utilization of transient bandwidth while the rate calculation is explicitly aimed at achieving max-min fairness in the steady state. Simulation shows that ASAP-MTS further improves the link utilization (over that of ASAP) up to almost 100% in typical WAN's while maintaining very small queues.; Finally, a theoretical framework is established for the study of stability of RB ABR flow control schemes. The framework uses the concepts of control theory but the formulation is based on a combinatorial analysis of the distributed asynchronous operations of the protocols. The study shows that inconsistency in the global state can cause the protocols to become unstable. Three control laws are analyzed. Simulation shows that the bang-bang control with the absolute form and the BID scheme (ASAP) is found to be the most stable control law.