| The main goal of this thesis is to propose a new approach to offering guarantees on quality of service in distributed systems. We articulate our proposal by first formulating a design principle: the system under consideration should allow the implementation of a priority interface between users and resources. The resource allocation in each network element is determined only by the values of the priorities of the users accessing the element. The essential feature of priority-based systems is that of competitiveness: if a user increases his priority he will receive a higher service level, while the service level of other users will not increase.; In our resource allocation and admission control for our algorithm, users measure their QoS and update their priorities based on the measured QoS. The new priorities are then used by the network elements for relative resource allocation among users. The rule differs between admitted users and candidate users. On the one hand, candidate users update their priorities according to a “slow start” updating rule, not unlike the slow start increase of the window size of TCP. New users are admitted if their measured QoS exceeds the minimal required bound. On the other hand, admitted users use a “sense and respond” policy: they set a target QoS level that is slightly greater than their minimum bound and decrease (increase) their priority whenever their observed QoS is above (below) the target level. In the light of the previous description, the algorithm is distributed because measurements, controls and admission decisions are taken by each user based on local information, and closed-loop, because each user changes her priorities and admission status based on previous QoS measurements. We first use stochastic approximation theory to show that the evolution of priorities can be approximated by the solution of a system of ordinary differential equations. In this limiting regime, we prove that the algorithm makes correct decisions admission decisions. We validate these results in the simulated environment of an IP network. The numerical experiments are encouraging, and indicate that the algorithm is robust with respect to the statistical properties of the flows. |
