Ph.D. Thesis: Control of Network Resources over Multiple Time-Scales

Matthias Grossglauser, April 1998

Abstract

Real-time multimedia applications require resource allocation because of their quality of service (QoS) requirements. On the other hand, network efficiency depends crucially on the degree of resource sharing inside the network. A key problem in concurrently achieving both goals is caused by the fluctuation over multiple time-scales of the traffic bandwidth emitted by these applications, because it makes it hard to predict resource requirements with sufficient accuracy. This in turn requires a careful design of control mechanisms so that they cover all time-scales.

In this thesis, we examine resource control over three natural time-scales. On the packet time-scale, we evaluate the performance of traffic smoothing as a mechanism to accommodate bandwidth fluctuation. We show that there exists a correlation horizon that separates relevant from irrelevant fluctuation time-scales for the purpose of performance prediction. This illustrates the general principle that the traffic, system, and performance metric time-scales together determine the set of candidate traffic models.

On the burst time-scale, we advocate renegotiation as an efficient mechanism to accommodate fluctuations over time-scales beyond the correlation horizon. A new network service model called RCBR (Renegotiated Constant Bit Rate) combines network simplicity with desirable quality of service guarantees, while achieving much of the potential statistical multiplexing gain of bursty traffic.

On the flow time-scale, we discuss measurement-based admission control as a means of relieving the application of the burden of a-priori traffic specification. The impact of measurement uncertainty and the interplay of burst and flow time-scale dynamics are captured in a single analytical model. This model provides useful guidelines for robust admission control in the presence of unknown traffic statistics. A key result shows that robustness can be achieved by matching the traffic measurement time-scale to the critical time-scale of the system, which depends on the average flow holding time and the system size.

We then address two issues in multicast transmission. First, we extend the RCBR service model to multicast flows to illustrate the tradeoff between network and application complexity. In particular, we compare the complexity of applications in a best effort network and in a network offering controlled sharing through renegotiation. For hierarchically encoded flows, we examine the issue of making the network aware of the dependencies between flows that make up the layers of a single session. Second, we address the problem of feedback implosion in multicast. One approach to feedback implosion avoidance relies on delaying feedback at the receivers. We present a distributed algorithm to compute optimal deterministic timeouts for each receiver in a multicast tree as a function of the tree topology and the sender-to-receiver round-trip delays. This algorithm is fully distributed, because it relies only on local topology information and local communication for the timeout computation. Furthermore, the set of timeouts is optimal with respect to the maximum response time.

Contrôle des Ressources de Réseaux sur des Échelles Temporelles Multiples

Résumé

Les applications multimédia ont des besoins de qualité de service qui nécessitent l'utilisation de réseaux permettant l'allocation de ressources. Cependant, l'efficacité d'un réseau dépend de façon cruciale du degré de partage des ressources. Satisfaire ces deux contraintes est difficile à cause des fluctuations à multiples échelles temporelles du débit du trafic généré par ces applications. En effet, cela complique la prédiction des demandes en ressources avec une précision suffisante. Il faut mettre en oeuvre des mécanismes de contrôle de façon à couvrir toutes les échelles temporelles.

Dans cette thèse, nous étudions le contrôle de ressources sur trois échelles temporelles naturelles. A l'échelle du paquet, nous évaluons la performance du lissage du trafic comme mécanisme pour accommoder les fluctuations de débit. Nous montrons l'existence d'un horizon de corrélation; seules les échelles temporelles plus courtes que cet horizon de corrélation sont pertinentes pour la prédiction de performance. Ceci illustre le principe plus général que le trafic, le système, et la métrique de performance doivent être pris en compte pour déterminer l'ensemble de modèles de trafic possibles.

A l'échelle de la rafale, nous proposons la renégociation comme mécanisme pour accommoder les fluctuations sur une échelle temporelle plus longue que l'horizon de corrélation. Un nouveau modèle de service appelé RCBR (``Renegotiated Constant Bit Rate'') combine la simplicité du réseau avec un contrôle efficace de la qualité de service, tout en extrayant la quasi totalité du gain de multiplexage statistique du trafic.

A l'échelle du flux (ou de la connexion), nous décrivons le contrôle d'admission basé sur les mesures, qui simplifie le problème de la spécification du trafic pour l'application ou pour l'utilisateur. Nous proposons un modèle qui prend en compte l'impact de l'incertitude dans les mesures et l'interférence de l'échelle temporelle de rafale et de flux. Ce modèle permet d'obtenir des résultats fondamentaux pour la conception de mécanismes de contrôle d'admission basé sur les mesures robuste. Un résultat important issu de cette étude est que cette robustesse peut être atteinte en faisant correspondre l'échelle temporelle de la mesure (la longueur de la fenêtre d'estimation) à l'échelle temporelle critique du système, qui dépend de la durée moyenne des flux ainsi que de la taille du système.

Finalement, nous étudions deux problèmes dans la communication multipoint. Premièrement, nous étendons le modèle de service RCBR au cas des flux multipoint pour illustrer le compromis entre la complexité dans le réseau et la complexité dans les applications. Nous comparons la complexité d'une application qui utilise un réseau ``best effort'' avec celle d'une application qui utilise un réseau offrant des garanties renégociables. Nous nous intéressons aussi au problème de la dépendance des flux qui résulte de la compression en couches hiérarchiques d'une source d'information.

Deuxièmement, nous abordons le problème de l'implosion de l'information de contre-réaction dans la communication multipoint. Une approche pour éviter ce problème est de retarder l'envoi de l'information aux destinations. Nous présentons un algorithme distribué pour calculer un délai fixe pour chaque destination dans un arbre multipoint, qui est une fonction de la topologie de l'arbre est des délais source-destination. Cet algorithme est entièrement distribué car chaque noeud de l'arbre a seulement besoin d'informations locales et de communication entre noeuds voisins. De plus, l'ensemble des délais calculés par cet algorithme est optimal dans le sens qu'il minimise le temps de réponse maximal.