Cette thèse propose un cadre mathématique pour la modélisation de la dynamique du prix et du flux d'ordres dans un marché électronique ou' les participants achètent et vendent un produit financier en soumettant des ordres limites et des ordres de marche à haute fréquence à un carnet d'ordres centralisé. Nous proposons un modèle stochastique de carnet d'ordres en tant que système de files d'attente représentant la totalité des ordres d'achat et de vente au meilleur niveau de prix (bid/ask) et nous montrons que les principales caractéristiques de la dynamique du prix dans un tel marche peuvent être comprises dans ce cadre. Nous étudions en détail la relation entre les principales propriétés du prix et la dynamique du processus ponctuel décrivant l'arrivée et l'exécution des ordres, d'abord dans un cadre Markovien (Chapitre 2) puis, en utilisant des méthodes asymptotiques, dans le cadre plus général d'un processus ponctuel stationnaire dans sa limite heavy traffic, pour lequel les ordres arrivent fréquemment, comme c'est le cas pour la plupart des marches liquides (Chapitres 3 et 4). Le Chapitre 2 étudie un modèle Markovien de dynamique de carnet d'ordres, dans lequel l'arrivée d'ordres de marche, d'ordres limites et d'annulations est d'écrite à l'aide d'un processus de Poisson ponctuel. L'état du carnet d'ordres est d'écrit par une marche aléatoire changée de temps dans le quadrant positif et régénérée à chaque fois qu'elle atteint le bord. Ce modèle permet d'obtenir des expressions analytiques pour la distribution des durées entre changements de prix, la distribution et les autocorrelations des changements de prix, ainsi que la probabilité que le prix augmente, conditionnellement à l'état du carnet d'ordres. Nous étudions la limite de diffusion du prix et exprimons la volatilité des changements de prix à l'aide de paramètres décrivant l'intensité des ordres d'achat, de vente et d'annulations. Ces résultats analytiques permettent de mieux comprendre le lien entre volatilité du prix et flux d'ordres. Le Chapitre 3 étudie un modèle plus général de carnet d'ordres pour lequel les arrivées d'ordres et les tailles d'ordres proviennent d'un processus ponctuel stationnaire très général. Nous obtenons un théorème central limite fonctionnel pour la dynamique jointe des files d'attente des ordres de vente et d'achat, et prouvons que, pour un marche liquide, dans lequel les ordres d'achat et de vente arrivent à haute fréquence, la dynamique du carnet d'ordres peut être approximée par un processus à sauts Markovien diffusant dans l'orthant et dont les caractéristiques peuvent être exprimées à l'aide de propriétés statistiques du flux d'ordres sous-jacent. Ce résultat permet d'obtenir des approximations analytiques pour plusieurs quantities d'intérêt telles que la probabilité que le prix augmente ou la distribution de la durée avant le prochain changement de prix, conditionnellement à l'état du carnet d'ordres. Ces quantités sont exprimées en tant que solutions d'équations elliptiques, pour lesquelles nous donnons des solutions explicites dans certains cas importants. Ces résultats s'appliquent à une classe importante de modèles stochastiques, incluant les mod'eles bas'es sur les processus de Poisson, les processus auto-excitants ou la famille de processus ACD-GARCH. Le Chapitre 4 est une étude plus détaillée de la dynamique du prix dans un marche où les ordres de marche, les ordres limites et les annulations arrivent à haute fréquence. Nous étudions d'abord la dynamique discrète du prix à l'échelle de la seconde et nous obtenons des relations analytiques entre les propriétés statistiques des changements de prix dans une journée -distribution des incréments du prix, retour à la moyenne et autocorrelations- et des propriétés du processus décrivant le flux d'ordres et la profondeur du carnet d'ordres. Ensuite nous étudions le comportement du prix à des fréquences vi CONTENTS vii plus faibles pour plusieurs régimes asymptotiques -limites fluides et diffusives- et nous obtenons pour chaque cas la tendance du prix et sa volatilité en fonction des intensités d'arrivées d'ordres d'achat, de vente et d'annulations ainsi que la variance des tailles d'ordres. Ces formules permettent de mieux comprendre le lien entre volatilité du prix d'un côté et le flux d'ordres, décrivant la liquidité, d'un autre cote. Nous montrons que ces résultats sont en accord avec la réalité des marches liquides.

L'analyse de la performance à l'état stationnaire dans de nombreux systèmes de files d'attente est complexe et les résultats sous forme explicite ne sont disponibles que dans des cas particuliers. Nous avons donc développé des approximations pour des critères de performance importants à l'état stationnaire tels que la longueur de la file d'attente, le temps d'attente et le temps de traitement total. Nous analysons d'abord la performance dans des cas à faible et fort trafic. Nous montrons ensuite comment développer une approximation basée sur une interpolation qui est valable pour n'importe quelle condition de trafic. Un avantage de l'approche proposée est qu'elle n'est pas dépendante d’un modèle particulier et donc elle peut être appliquée à d'autres modèles de files d'attente complexes. Nous appliquons cette technique pour trois modèles largement utilisés dans l'évaluation des performances des réseaux stochastiques : le modèle du supermarché, la file d'attente Discriminatory-Processor-Sharing (DPS) et la file d'attente Relative Priority (RP). Le modèle du supermarché est une file d'attente à plusieurs serveurs où lorsqu’un client arrive, deux serveurs sont choisis au hasard dans un ensemble de serveurs. La politique Join-the-Shortest-Queue (JSQ) est ensuite utilisée parmi les deux serveurs sélectionnés. DPS et RP sont deux files d'attente à plusieurs classes et à serveur unique mettant en œuvre des priorités relatives entre les clients des différentes classes. La discipline DPS sert tous les clients simultanément, tandis que RP sert un seul client à la fois de manière non-préemptive. Nous montrons que dans certains cas, l'interpolation est exacte. Nous utilisons ensuite cette approximation pour déduire comment la performance dépend des paramètres des modèles, et nous effectuons des expériences numériques illustrant la précision de l'interpolation dans un grand nombre de cas de figure / The analysis of the steady-state performance in many queuing systems is complex and closed-form results are available only in particular cases. We therefore set out to develop approximations for important performance measures in steady-state such as the queue length vector, waiting time and sojourn time. We first analyse the performance in a light-traffic and heavy-traffic regime. We then show how to develop an interpolation-based approximation that is valid for any load in the system. An advantage of the approach taken is that it is not model dependent and hence could potentially be applied to other complex queuing models. We apply this technique to three widely used models in the performance evaluation of stochastic networks: The supermarket model, the Discriminatory-Processor-Sharing (DPS) queue and the Relative Priority (RP) queue. The supermarket model is a multi-server queue where upon arrival of a customer two servers are selected at random from the available pool of servers. The Join-the-Shortest-Queue policy is then used in isolation with these two servers. DPS and RP are both single-server multi-class queues that implement relative priorities among customers of the various classes. The DPS discipline serves all customers simultaneously while RP serves one customer at a time in a non-preemptive way. We show that in some instances the interpolation approximation is exact. We then use the approximation to draw structural insights onto the performance of the system, and we carry out numerical experiments that illustrate that the interpolation approximation is accurate over a wide range of parameters

Lors d'une communication dans un réseau, les nœuds intermédiaires se contentent en général de retransmettre les paquets de données qu'ils reçoivent. Grâce au codage de réseau (NC), ces nœuds intermédiaires peuvent envoyer des combinaisons linéaires des paquets qu'ils ont reçus. Ceci permet une meilleure exploitation de la capacité du réseau et une plus grande robustesse à l'égard de pertes.Cette thèse s'intéresse à une implantation du NC en lien avec TCP (TCP-NC). Grâce à la redondance introduite par le NC, une partie des pertes liées à des liens sans fils peut être compensée. Elle propose en particulier un mécanisme d'adaptation de la redondance introduite par le codage de réseau. Une première partie de cette thèse est consacrée à l'analyse de la dynamique de TCP-NC avec Random Early Detection (RED) comme mécanisme de gestion des files d'attente en utilisant les outils d'optimisation convexe et issus de l’automatique. Nous caractérisons l'équilibre du réseau et les propriétés de stabilité de TCP-Reno en présence de NC. Dans une seconde partie, cette thèse propose un algorithme d'adaptation de la redondance introduite par NC. Dans TCP-NC avec redondance adaptative (TCP-NCAR), cet ajustement se fait grâce à un schéma de différenciation des pertes, qui estime la répartition des pertes entre erreurs de transmission dues aux liens sans fils et pertes liées à la congestion. Les propriétés d'équilibre et de stabilité de TCP-NCAR/RED sont caractérisées. Les résultats théoriques et de simulation montrent que TCP-NCAR adopte une redondance proche de l'optimum quand les taux de perte de paquets sur les liens sans fils sont petits. En outre, le modèle linéarisé autour de l'équilibre montre que TCP-NCAR augmente la taille de la région de stabilité de TCP-Reno. / Communication networks today share the same fundamental principle of operation: information is delivered to their destination by nodes intermediate in a store-and-forward manner.Network coding (NC) is a technique that allows intermediate nodes to send out packets that are linear combinations of previously received information. The main benefits of NC are the potential throughput improvements and a high degree of robustness, which is translated into loss resilience. These benefits have motivated deployment efforts for practical applications of NC, e.g., incorporating NC into congestion control schemes such as TCP-Reno to get a TCP-NC congestion protocol. In TCP-NC, TCP-Reno throughput is improved by sending a fixed amount of redundant packets, which mask part of the losses due, e.g., to channel transmission errors. In this thesis, we first analyze the dynamics of TCP-NC with random early detection (RED) as active queue management (AQM) using tools from convex optimization and feedback control. We study the network equilibrium point and the stability properties of TCP-Reno when NC is incorporated into the TCP/IP protocol stack. The existence and uniqueness of an equilibrium point is proved, and characterized in terms of average throughput, loss rate, and queue length. Our study also shows that TCP-NC/RED becomes unstable when delay or link capacities increases, but also, when the amount of redundant packets added by NC increases. Using a continuous-time model and neglecting feedback delays, we prove that TCP-NC is globally stable. We provide a sufficient condition for local stability when feedback delays are present. The fairness of TCP-NC with respect to TCP-Reno-like protocols is also studied. Second, we propose an algorithm to dynamically adjust the amount of redundant linear combinations of packets transmitted by NC. In TCP-NC with adaptive redundancy (TCP-NCAR), the redundancy is adjusted using a loss differentiation scheme, which estimates the amount of losses due to channel transmission errors and due to congestion. Simulation results show that TCP-NCAR outperforms TCP-NC in terms of throughput. Finally, we analyze the equilibrium and stability properties of TCP-NCAR/RED. The existence and uniqueness of an equilibrium point is characterized experimentally. The TCP-NCAR/RED dynamics are modeled using a continuous-time model. Theoretical and simulation results show that TCP-NCAR tracks the optimal value for the redundancy for small values of the packet loss rate. Moreover, simulations of the linearized model around equilibrium show that TCP-NCAR increases the size of the TCP-Reno stability region. We show that this is due to the compensator effect of the redundancy adaptation dynamics to TCP-Reno. These characteristics of TCP-NCAR allow the congestion window adaptation mechanism of TCP-Reno to react in a smooth way to channel losses, avoiding some unnecessary rate reductions, and increasing the local stability of TCP-Reno.

La méthodologie de modélisation adaptée a la mesure des performances des architectures parallèles repose sur la décomposition du processus de modélisation en 7 phases: formulation des objectifs, analyse du système, conception du modèle, estimation et mesure des paramétrés d'entrée du modèle, resolution du modèle, validation du modèle et utilisation du modèle pour prédire les performances du système réel

La technologique utilisée dans les réseaux de télécommunication à commutation de paquets est en développement permanent. La tendance actuelle est orientée vers la mutualisation des services voix et données, de leurs infrastructures et des techniques associées (réseaux IP/MPLS, QoS dans Internet). Les méthodes classiques utilisées pour l'évaluation de performances des ces réseaux sont la modélisation analytique et la simulation événementielle. La simulation événementielle requiert des temps de calcul prohibitifs, tandis que les modèles issus des méthodes analytiques manquent parfois de précision. Le travail présenté dans cette thèse définit un cadre de modélisation appelé Simulation Hybride Distribuée qui combine de manière rigoureuse la théorie différentielle du trafic et la simulation événementielle. Dans une première technique, les ressources du réseau sont partitionnées en domaines dont certains sont simulés par événements, et les autres sont modélisés par des équations intégrées numériquement. La seconde technique proposée permet la circulation de trafics simulés par événements sur les ressources du réseau modélisées par des équations. La simulation hybride permet ainsi de prolonger la modélisation analytique au-delà de ses limites théoriques. Elle permet également de concevoir des modèles d'évaluation de performances très généraux et de développer des logiciels plus performants en temps de calculs. Un prototype de simulateur hybride a été conçu. Il permet de modéliser précisément des routeurs Internet Diffserv et MPLS, le protocole TCP ainsi que diverses sources de trafic multimédia (Audio, Vidéo). Pour réduire les temps de calcul, le simulateur peut être parallélisé. En ce sens, un nouveau noyau de communication de l'environnement de parallélisme LANDA a été conçu. Il offre une bibliothèque à la norme MPI et permet d'utiliser simultanément et efficacement (latence, bande passante) plusieurs media de communication haut-débit ainsi que la mémoire commune S MP.

Cette thèse porte sur la modélisation et l'evaluation d'algorithmes de transfert de charge dans des systèmes parallèles et/ou distribués. Après une synthèse des différentes approches possibles du transfert de charge et des problèmes rencontres pour leurs mises en oeuvre et leurs évaluations quantitatives, nous développons plusieurs modèles basés sur une évolution markovienne de la configuration des charges de l'ensemble des processeurs. Les indices de performance étudiés afin de comparer les valeurs obtenues avec transfert et sans transfert sont la saturation mémoire, le débit du système, la charge de travail et le temps de réponse moyen. Dans les deux premiers modèles seuls deux sites se transfèrent des tâches, mais les temps de communication et de transfert sont modélisés. Des valeurs critiques concernant la pertinence ou non du transfert sont obtenues. Lorsque les temps de communication et de transfert sont négligés devant les temps de calculs, deux modèles sont étudies. Le premier permet d'évaluer un algorithme d'équilibrage de charge pour un nombre quelconque de sites homogènes totalement connectés, de capacité mémoire finie. Cette étude permet de prévoir le comportement de systèmes massivement parallèles et des bornes supérieures de bénéfices que l'on peut attendre d'un réel transfert sont explicitées. Le deuxième prend en compte l'architecture du réseau et l'algorithme induit un transfert dés que la différence de charge entre deux sites voisins excède un. Dans le cas de réseaux infinis dont la topologie est régulière, ce modèle est ergodique et converge à vitesse exponentielle vers son régime stationnaire. Des résultats de simulations sont présentés pour différentes architectures et comparés aux solutions des équations de champ moyen, qui donnent de très bonnes approximations dans la plupart des cas pour les quantités d'intérêt pratique. Enfin, l'incidence sur la valeur des indices de performance est étudiée et interprétée.

Ce manuscrit est centré sur la conception, l'amélioration et l'évaluation des protocoles des couches RESEAU, MAC et PHY. En particulier, nous nous focalisons sur la conception de nouveaux protocoles distribués pour une utilisation optimale/améliorée des ressources radio disponibles. Par ailleurs, nous caractérisons les performances des réseaux ad hoc à accès aléatoire au canal en utilisant des paramètres de plusieurs couches avec aptitude de transfert d'information (data forwarding). La majeure partie de nos analyses se base sur le concept d'interaction entre les couches OSI (cross-layer). En effet, cette nouvelle et attractive approche est devenue en peu de temps omniprésente dans le domaine de recherche et développement et dans le domaine industriel. Les métriques de performances qui nous intéressent sont la stabilité des files d'attentes de transfert, le débit, le délai et la consommation d'énergie. Principalement, la compréhension de l'interaction entre les couches MAC/PHY et routage du standard IEEE 802.11e DCF/EDCF, d'une part, et l'interaction entre noeuds en terme d'interférences, d'autre part, constituent le coeur central de notre travail

Dans la première partie de cette thèse nous étudions la mobilité et le temps de transfert d'un message dans les réseaux ad hoc mobiles. Nous obtenons, pour plusieurs modèles de mobilité, la loi stationnaire de la position des noeuds, la distribution du temps nécessaire avant que deux noeuds puissent (à nouveau) communiquer, et le temps durant lequel deux noeuds sont dans leur voisinage mutuel. Nous déduisons de ces résultats des formules pour le temps de transfert d'un message en utilisant d'autres noeuds dans le réseau comme relais. Ces calculs sont effectués pour plusieurs modèles de mobilité et pour deux types de protocoles de routage.La deuxième partie de cette thèse traite d'un système à " Polling " qui consiste en deux files d'attente servies par un serveur. Après avoir servi une file d'attente, le serveur a besoin d'un temps de commutation pour passer d'une file à l'autre, et commencer à servir les clients. Les temps de commutation peuvent être corrélés. Nous obtenons l'expression de plusieurs mesures de performance, notamment le temps d'attente moyen et la taille moyenne de la file d'attente. Grâce à ces expressions, nous comparons deux disciplines de service et au travers d'exemples nous montrons que la corrélation des temps de commutation peut augmenter significativement le temps d'attente moyen et la taille des files d'attente. Cela indique que la corrélation ne peut pas être ignorée et qu'elle a des implications importantes pour des systèmes de communication dans lesquels un canal de communication commun est partagé entre plusieurs utilisateurs et où le temps entre des transferts de données consécutifs est corrélé (par exemple dans les réseaux ad hoc).Dans la troisième et dernière partie nous étudions deux files d'attente en série avec des coûts pour chaque client dans le système. La fonction de valeur est calculée pour le coût moyen quand il n'y a pas d'entrée des clients. Celle-ci peut être utilisée pour l'optimisation des systèmes en série ou pour le calcul complet de la fonction de valeur.

Nous abordons dans cette thèse le problème de l'insensibilité dans les réseaux de files d'attente et quelques applications au partage de ressources informatiques. Tout d'abord, nous montrons que les réseaux de files d'attente symétriques avec le routage de Jackson ou de Kelly sont tous insensibles à la distribution des demandes de service même si à l'arrivée, au départ ou au changement de files d'un client quelconque, les autres clients dans chaque file sont permutés au hasard selon certaine loi dépendante de l'état du réseau. Nous identifions également certaines disciplines de service non symétriques pour lesquellesla propriété d'insensibilité est satisfaite. Ensuite, nous proposons deux nouvelles métriques de débit pour les réseaux de données. Nous montrons quelques propriétés génériques satisfaites par ces deux métriques et nous illustrons leur différence à travers quelques exemples. Enfin, nous montrons que l'équilibrage de sources de trafic élastique détériore la performance en termes de débit, et en présence de contrôle d'admission, de probabilité de blocage.

Le pilotage optimal de production à moyen et à court terme représente de plus en plus une décision importante pour la gestion efficace d'une chaîne logistique. <br /><br />Dans la première partie de ce travail, nous nous intéressons au pilotage optimal de production à moyen terme d'une chaîne logistique à deux étages. Notre objectif est de savoir quel est le bénéfice d'une optimisation globale par rapport à l'optimisation locale. Nous étudions le comportement du système pour deux types de demande (déterministe/stochastique) et par rapport aux deux types d'optimisation. La modélisation est faite à l'aide des outils de la programmation mathématique et de la théorie des files d'attente. Plusieurs analyses ont été réalisées pour pouvoir définir le comportement de chaque modèle afin de pouvoir les<br />comparer. <br /><br />Dans la deuxième partie, nous considérons le problème d'optimisation de la production à court terme appliqué à une raffinerie pétrolière. Nous nous intéressons à l'ordonnancement des activités de chargement/déchargement du pétrole brut dans les réservoirs de stockage en ayant comme objectif la minimisation du coût de reconfiguration. Nous présentons une modélisation générique qui tient compte de tous les modes de préparation de mélanges et des différentes options de distillation. Nous donnons les différentes méthodes développées pour améliorer l'efficacité de la résolution ainsi qu'une nouvelle extension sur la méthode de décomposition de Benders. Nous terminons en comparant les différentes méthodes en terme de critères de qualité de la solution obtenue et du temps de résolution.