Study of QB-CSMA algorithms

Etudes des protocoles d'accès QB-CSMA

Eyal Castiel (1, 2)

1 ISAE-SUPAERO - Institut Supérieur de l'Aéronautique et de l'Espace
2 IMT - Institut de Mathématiques de Toulouse UMR5219

The subject of this thesis is to provide a rigorous analysis of a communication scheme. This analysis is carried out in the mathematical context of queueing theory, the study of congestion phenomena. The model that we study is a refinement of a classical distributed scheduling algorithm. The Queue-Based Carrier Sense Multiple Access (QB-CSMA) algorithm is a distributed algorithm designed to schedule queues on a graph. From a complexity standpoint, its execution is simple and requires little cooperation between nodes. Jobs arrive at the waiting area of queues, also called servers or nodes, along a Poisson process. Each job has an exponential service time before exiting the network. Two or more nodes that are neighbors on the interference graph cannot provide service to their jobs simultaneously without interfering. The ``Carrier Sensing'' means that nodes can sense when their neighbors are already transmitting, they refrain from using the channel when that happens. The ``Queue Based'' element is the refinement from the classical CSMA algorithm: it means that the rates at which queues start and end transmissions actually evolve over time and depend on the current state of the network. The classical CSMA algorithm is quite simple: each node has a fixed ``fugacity''. When it is active, a node deactivates after an exponential time with a parameter function of the fugacity. Nodes that are not active let an exponential clock run when none of their neighbors are active and stop the clock when their neighbors activate. An activation occurs when the exponential clock ticks and the activation rate determined by the fugacity. With QB-CSMA the fugacity of each server actually depends on the number of jobs they have to process. For each value of the queue lengths, there is a different dynamic for the schedule, with a unique generator and an invariant measure associated to it. Contrary to the classical, this adaptive CSMA does not require any prior knowledge on the interference graph/arrival rates to be able to produce good service decisions. In some cases, it can be used to distributively approximate the Max-Weight algorithm, a procedure that is onerous to put in place from a complexity point of view but celebrated for its good performance. In Chapter 3, we prove some explicit bounds on the difference between the time average of the occupation measure of the schedule and its steady state average associated with the current value of the queue lengths. For each value of queue lengths, there is a dynamic for the schedule, this dynamic has a unique invariant measure. This is the time evolving steady state average that the occupation measure approaches. In order to prove this, this manuscript uses tools from functional analysis. The main concepts that we use are Poisson equations and their solutions. The solutions to Poisson equations act as an inverse application for the generator of a Markov process and give an alternate way to write the difference between a function and its average with respect to the invariant measure of the generator. To bound the time average of the difference between the service rate and its steady state average, it is sufficient to bound solutions to Poisson equations and understand their regularity in the size of queue lengths. The norm of solutions to Poisson equations can be bounded by the log-Sobolev constant of the generator of the schedule with fixed queue lengths. This quantity is closely related to the mixing time of this dynamic. Some bounds on the regularity of solution to Poisson equations are also proved in Chapter 3. The regularity of solutions essentially depends on the regularity in the size of the queues for the transition rates of the schedule and for the invariant measure. In Chapter 4, we prove a functional limit theorem. The usual fluid limit scaling of the queue lengths converges to a deterministic process governed by an ODE. The main part of the proof is a homogenization result proven from the bounds of Chapter 3. The problem is that this bound does not behave well when some coordinates are too small. Because of that the result on a general interference graph is only proved up to the time one of the queue reaches 0 in the fluid scale. The main difficulty in Chapter 4 lies on the study of the Complete Interference Graph (CIG) over any finite time interval. In this case the possible reflections at 0 are treaded separately. Three cases are distinguished between sub-critical, super-critical and critical arrival rates. In Chapter 5, in the case of a CIG with critical arrival rates a second functional limit theorem is proved. The fluid limit converges for long time to an invariant state where the process is constant because the arrival rates and the averaged departure rates coincide. Because of the distributed nature of the algorithm, there is always some non-null time where no queue is active between two activations. The idea behind the time scale in Chapter 5 is to investigate the influence of idle time to the dynamic. On this second time scale, the limit is also deterministic which is surprising. The process of queue lengths instantaneously collapses to a one dimensional manifold and the evolution of the sum of coordinates is given by an ODE determined by the idle time.

L'objet de cette thèse est de présenter une analyse rigoureuse d'un algorithme de communication. Elle est menée dans le cadre mathématique de la théorie des files d'attente, l'étude des phénomènes de congestion. Le modèle que nous présentons est un raffinement d'un algorithme classique d'ordonnancement. QB-CSMA (Queue-Based Carrier Sense Multiple Access) est un algorithme simple et distribué, créé pour ordonnancer des files d'attente placées sur un graphe. De nouvelles requêtes arrivent aux points d'un processus de Poisson dans les files d'attente des serveurs. Elles requièrent un temps de service exponentiel avant de quitter le réseau. Des nœuds voisins sur le graphe ne peuvent pas servir leurs requêtes simultanément sans interférence. Les termes ``Carrier Sense'' indique que les serveurs sont capables d'écouter le canal pour voir si leurs voisins sont actifs et évitent de transmettre quand c'est le cas. L'amélioration du CSMA vient de ``Queue Based'', signifiant que les taux auxquels les serveurs commencent et arrêtent leurs transmissions dépendent de l'état du réseau. L'algorithme CSMA est simple: chaque noeud a une ``fugacité'' fixée. Quand il est actif, un noeud se désactive après un temps exponentiel avec paramètre fonction de la fugacité. Les nœuds qui ne sont pas actifs laissent tourner une horloge exponentielle qui s'arrête quand des voisins s'activent. Un nœud s'active quand l'horloge sonne et le taux d'activation est une fonction de la fugacité. Avec QB-CSMA, la fugacité de chaque nœud dépend du nombre de requêtes que le serveur doit traiter. Pour chaque taille des files, il y a une dynamique et une mesure invariante différente pour l'ordonnanceur. Contrairement aux algorithmes CSMA classiques, QB-CSMA n'a pas besoin d'information sur le graphe d'interférence où les taux d'arrivé pour produire de bons choix d'ordonnancement. Dans certains cas, cet algorithme adaptatif peut être utilisé pour approcher Max-Weight, un algorithme coûteux à mettre en place d'un point de vue complexité mais avec de bonnes performances. Dans le Chapitre 3, nous prouvons des bornes explicites sur la différence entre les moyennes en temps des décisions d'ordonnancement et leurs moyennes pour l'équilibre de la dynamique associée à la taille courante des files. Pour chaque valeur des files d'attente, il y a une dynamique pour l'ordonnanceur et une unique mesure invariante associée à cette dynamique. C'est cette distribution évoluant avec le temps que la mesure d'occupation de l'ordonnanceur approche. Pour prouver ce genre de résultat, ce manuscrit utilise des notions d'analyse fonctionnelle. Les concepts au cœur du raisonnement sont l'équation de Poisson et sa solution. Les solutions de ces équations agissent comme un inverse pour le générateur de processus markoviens et donnent une façon alternative d'écrire la différence entre une fonction et sa moyenne à l'équilibre. Pour borner la moyenne temporelle de la différence entre le taux de service et sa moyenne, il est suffisant de borner la norme des solutions de l'équation de Poisson et connaître leurs régularités par rapport à la taille des files. La norme de la solution à une équation de Poisson est bornée par la constante de log-Sobolev du générateur correspondant. Cette quantité est reliée au temps de mélange de la dynamique associée à ce générateur. Nous prouvons également dans le Chapitre 3 une borne sur la régularité de ces solutions dans la taille des files. Elle dépend essentiellement de la régularité des taux de transitions et de la mesure invariante par rapport à la taille des files. Dans le Chapitre 4, nous prouvons un théorème limite fonctionnel. La renormalisation fluide usuelle du processus de file d'attente converge vers une fonction déterministe solution d'une equation différentielle ordinaire. L'étape principale de la preuve repose sur un résultat d'homogénéisation, conséquence des bornes du chapitre précédent. Le problème est que nos bornes se comportent mal quand une taille de file est trop faible. Nous ne sommes pas capables de prouver la convergence que jusqu'au temps où une des files atteint 0 sur l'échelle fluide. La difficulté principale du Chapitre 4 est l'étude des limites fluides pour n'importe quel horizon fini dans le cas du graphe complet (GC). Dans ce cas, il est possible de gérer les réflexions en 0 séparément. Dans le chapitre 5, pour un GC et un taux d'arrivée critique, nous prouvons un deuxième théorème limite fonctionnel. La limite fluide converge en temps long temps vers un état invariant ou la limite reste constante car les taux d'arrivée et les taux de service moyennés sont en équilibre. A cause de la nature distribuée de QB-CSMA, il y a forcément un temps non nul où aucun des serveurs n'est actif. Le but de l'échelle de temps du Chapitre 5 est d'étudier l'influence de ce temps de repos sur la dynamique des files d'attente. Sur cette deuxième échelle de temps, la limite est également déterministe, ce qui peut être surprenant. Le processus de files d'attente s'effondre instantanément sur une variété de dimension 1 et l'évolution de la somme des coordonnées est donnée par une EDO déterminée par la fraction du temps où aucune file n'est active.

Mots clés: convergence and long time behavior of Markov processes; functional limit theorems; homogenization; stochastic networks; distributed scheduling; independent sets

Mots clés: Convergence et comportement en temps long de chaînes et processus de Markov; théorèmes limite fonctionnels; réseaux stochastiques; ensembles indépendants; homogénéisation

Domaines: Probabilités [math.PR]

Eyal Castiel. Study of QB-CSMA algorithms. Probability [math.PR]. Institut Supérieur de l'Aéronautique et de l'Espace (ISAE), 2019. English. ⟨NNT : ⟩. ⟨tel-02964354⟩