Generalized processor sharing approach to flow control in integrated services networks. The multiple node case

Abstract

Worst-case bounds on delay and backlog are derived for leaky bucket constrained sessions in arbitrary topology networks of Generalized Processor Sharing (GPS) servers. When only a subset of the sessions are leaky bucket constrained, we give succinct per-session bounds that are independent of the behavior of the other sessions and also of the network topology. However, these bounds are only shown to hold for each session that is guaranteed a backlog clearing rate that exceeds the token arrival rate of its leaky bucket. When all of the sessions are leaky bucket constrained, a much larger class of networks called Consistent Relative Session Treatment (CRST) networks is analyzed. The session i route is treated as a whole, yielding tighter bounds than those that result from adding the worst-case delays (backlogs) at each of the servers in the route. The bounds on delay and backlog for each session are efficiently computed from a universal service curve, and it is shown that these bounds are achieved by 'staggered' greedy regimes when an independent sessions relaxation holds. Propagation delay is also incorporated in the model. Finally, the analysis of arbitrary topology GPS networks is related Packet GPS networks (PGPS).