Improving resource sharing in computer networks with stochastic scheduling
Institution:
NiceDisciplines:
Directors:
Abstract EN:
In the current thesis we propose several new contributions to improve the performance of computer networks. The obtained results concern the resource sharing problems in the Internet routers, Web servers and operating systems. We study several stochastic scheduling algorithms which decrease the mean waiting time in the system with efficient resource sharing and provide the possibility to introduce the Quality of Service and flow differentiation to the networks. We show the effectiveness of the proposed algorithms and study the possibility of their implementation in the router queues. The most important obtained results are the following. For the Two Level Processor Sharing scheduling discipline with the hyper-exponential job size distribution with two phases we find an approximation for the optimal value of the threshold that minimizes the expected sojourn time. With the simulation results (NS-2) we show that TLPS improves significantly the system performance when the found approximation of the optimal threshold is used. We study the Discriminatory Processor Sharing policy and show the monotonicity of the expected sojourn time in the system depending on the weight vector under certain conditions on the system. We apply the Gittins optimality result to characterize the optimal scheduling discipline in a multi-class single server queue. The found policy minimizes the mean sojourn time in the system between all non-anticipating scheduling policies. In several cases of practical interest we describe the policy structure and provide the simulation results (NS-2). For the the congestion control problem in the networks we propose a new flow-aware algorithm to improve the fair resource sharing of the bottleneck capacity.
Abstract FR:
Dans la thèse présente, nous proposons plusieurs contributions pour améliorer la performance dans les réseaux d'ordinateurs. Les résultats obtenus concernent les problèmes de partage de ressources dans les routeurs d'Internet, les serveurs Web et les systèmes d'exploitation. Nous étudions quelques algorithmes qui diminuent le temps moyen de séjour dans le système avec un partage des ressources efficace et qui fournissent la possibilité d'introduire la différentiation entre les flux dans les réseaux. Nous montrons l'efficacité des algorithmes proposés et nous étudions la possibilité de leur application dans les files d'attente de routeurs. Nous notons les résultats obtenus les plus importants. Pour la politique de service à temps partagé à deux niveaux avec le temps de service hyper-exponentielle avec deux phases nous trouvons une expression de l'approximation de la valeur de seuil optimal qui minimise le temps moyen de séjour dans le système. Avec les résultats de simulations nous montrons que la politique TLPS améliore la performance dans le système quand la valeur approchée du seuil est utilisé. Nous appliquons le résultat de Gittins pour caractériser la politique optimale pour l'ordonnancement dans une file d'attente multi-classe avec un serveur unique. La politique trouvé minimise le temps moyen de séjour dans le système entre toutes les politiques non-anticipatoires. Nous introduisons un nouvel algorithme d'élimination de paquets sensible aux flux pour les routeurs de l'Internet, qui améliore la performance du réseau et l'équité entre les flux. Dans la thèse présente, nous proposons plusieurs contributions pour améliorer la performance dans les réseaux d'ordinateurs. Les résultats obtenus concernent les problèmes de partage de ressources dans les routeurs d'Internet, les serveurs Web et les systèmes d'exploitation. Nous étudions quelques algorithmes qui diminuent le temps moyen de séjour dans le système avec un partage des ressources efficace et qui fournissent la possibilité d'introduire la différentiation entre les flux dans les réseaux. Nous montrons l'efficacité des algorithmes proposés et nous étudions la possibilité de leur application dans les files d'attente de routeurs. Nous notons les résultats obtenus les plus importants. Pour la politique de service à temps partagé à deux niveaux avec le temps de service hyper-exponentielle avec deux phases nous trouvons une expression de l'approximation de la valeur de seuil optimal qui minimise le temps moyen de séjour dans le système. Avec les résultats de simulations nous montrons que la politique TLPS améliore la performance dans le système quand la valeur approchée du seuil est utilisé. Nous appliquons le résultat de Gittins pour caractériser la politique optimale pour l'ordonnancement dans une file d'attente multi-classe avec un serveur unique. La politique trouvé minimise le temps moyen de séjour dans le système entre toutes les politiques non-anticipatoires. Nous introduisons un nouvel algorithme d'élimination de paquets sensible aux flux pour les routeurs de l'Internet, qui améliore la performance du réseau et l'équité entre les flux.