Le Network Calculus est une théorie visant à calculer des bornes pire-cas sur les performances des réseaux de communication. Le réseau est modélisé par un graphe orienté où les noeuds représentent des serveurs, et les flux traversant le réseau doivent suivre les arcs. S'ajoutent à cela des contraintes sur les courbes de trafic (la quantité de données passées par un point depuis la mise en route du réseau) et sur les courbes de service (la quantité de travail fournie par chaque serveur). Pour borner les performances pire-cas, comme la charge en différents points ou les délais de bout en bout, ces enveloppes sont combinées à l'aide d'opérateurs issus notamment des algèbres tropicales : min, +, convolution-(min, +)... Cette thèse est centrée sur l'algorithmique du Network Calculus, à savoir comment rendre effectif ce formalisme. Ce travail nous a amené d'abord à comparer les variations présentes dans la littérature sur les modèles utilisés, révélant des équivalences d'expressivité comme entre le Real-Time Calculus et le Network Calculus. Dans un deuxième temps, nous avons proposé un nouvel opérateur (min, +) pour traiter le calcul de performances en présence d'agrégation de flux, et nous avons étudié le cas des réseaux sans dépendances cycliques sur les flux et avec politique de service quelconque. Nous avons montré la difficulté algorithmique d'obtenir précisément les pires cas, mais nous avons aussi fourni une nouvelle heuristique pour les calculer. Elle s'avère de complexité polynomiale dans des cas intéressants. / Network Calculus is a theory aiming at computing worst-case bounds on performances in communication networks. The network is usually modelled by a digraph : the servers are located on the nodes and the flows must follow path in the digraph. There are constraints on the trafic curves (how much data have been through a given point since the activation of the network) and on the service curves (how much work each server may provide). To derive bounds on the worst-case performances, as the backlog or the end-to-end delay, these envelopes are combined thanks to tropical algebra operators: min, +, convolution... This thesis focuses on Network Calculus algorithmics, that is how effective is this formalism. This work led us to compare various models in the litterature, and to show expressiveness equivalence between Real-Time Calculus and Network Calculus. Then, we suggested a new (min, +) operator to compute performances bounds in networks with agregated flows and we studied feed-forward networks under blind multiplexing. We showed the difficulty to compute these bounds, but we gave an heuristic, which is polynomial for interesting cases.

本論文は,様々なネットワーク最適化問題の数学的構造について様々な観点から調べたものである.主たる結果はネットワーク最適化問題の代表例である最大流問題に,関するいくつかの結果と,Min-Plus代数に値をもつ行列の固有値と固有ベクトルに関する特徴づけに関する結果からなっている. / 博士(理学) / Doctor of Philosophy in Science / 同志社大学 / Doshisha University

On appelle suite récurrente stochastique (SRS) dirigée par une suite de matrices aléatoires une suite de variables aléatoires telles que le terme de rang n+1 est obtenu en multipliant celui de rang n par la enième matrice. Cette thèse porte sur le comportement asymptotique de telles suites. Dans la première partie, les matrices sont inversibles et on donne un critère de séparation des exposants de Lyapunov quand la suite de matrices suit une mesure de Gibbs sur un sous-shift de type fini. Dans la seconde partie, les produits se font au sens max-plus. On montre que le comportement des SRS au premier ordre est essentiellement déterminé par celui de certains blocs diagonaux et que la propriété de perte de mémoire, qui assure la stabilité des SRS, est générique. Si une suite de matrices (ou d'applications topicales) aléatoires est i.i.d. et a la propriété de perte de mémoire, alors les SRS qu'elle dirige vérifient des théorèmes limites. Ce résultat est obtenu par la méthode du trou spectral.