A Generalized Processor Sharing Approach to Flow Control in Integrated Services Networks: The Single-Node Case

The problem of allocating network resources to the users of an integrated services network is investigated in the context of rate-based flow control. The network is assumed to be a virtual circuit, connection-based packet network. We show that the use of Generalized Processor Sharing (GPS), when combined with Leaky Bucket admission control, allows the network to make a wide range of worst-case performance guarantees on throughput and delay. The scheme is flexible in that different users may be given widely different performance guarantees, and is efficient in that each of the servers is work conserving. We present a practical packet-by-packet service discipline, PGPS (first proposed by Demers, Shenker, and Keshav [7] under the name of Weighted Fair Queueing), that closely approximates GPS. This allows us to relate results for GPS to the packet-bypacket scheme in a precise manner. In this paper, the performance of a single-server GPS system is analyzed exactly from the standpoint of worst-case packet delay and burstiness when the sources are constrained by leaky buckets. The worst-case session backlogs are also determined. In the sequel to this paper, these results are extended to arbitrary topology networks with multiple nodes.