Soutenance mémoire
Classification
Les systèmes de files d’attente avec rappels sont identifiés par la nature stochastique du processus des arrivées, la distribution du temps de service, le nombre de serveurs qui composent l’espace de service, la capacité et la discipline d’attente ainsi que la spécification concernant le processus de répétition d’appels.
La notation de Kendall correspondante à ce type de système (avec rappels) est A/B/c/m/O/H, où A et B décrivent respectivement, la distribution du temps inter arrivées et la distribution du temps de service, c est le nombre de serveurs identiques et indépendants, (m-c) est la capacité de la file d’attente .
Les propriétés de monotonie de la chaine de Markov induite
Souvent, il y a une grande difficulté d’obtenir des résultats explicites pour la plupart des systèmes d’attente. Cette difficulté repose sur la complexité intrinsèque de l’espace d’états et de la dynamique d’évolution sur cet espace. Il est alors crucial de pouvoir comparer ces systèmes à des systèmes de performances bien connues. Pour cela, il est nécessaire de disposer d’outils de comparaison et, comme la comparaison se fait sur des systèmes aléatoires, la théorie adoptée est celle de la comparaison stochastique.
L’idée clé de la comparaison stochastique, est de concevoir une nouvelle chaîne de Markov telle que les indices de celle-ci soient une borne supérieure ou inférieure des indices de performance de la chaîne de Markov originale. La nouvelle chaîne de Markov est celle d’un modèle simplifié du modèle original. En fait, ces bornes et les critères de simplification sont basés sur la notion d’ordres stochastiques. Un ordre stochastique est simplement, une relation d’ordre définie sur un espace des fonctions de répartition. Nous nous intéressons particulièrement aux ordres dits intégraux, définis par une famille de fonction. Ces ordres sont importants pour l’évaluation de performances car ils permettent de comparer différentes fonctions de récompense (par exemple le nombre de clients dans un système, le taux de perte, la probabilité de panne,…).
L’ouvrage de référence, ouvrage historique écrit par Stoyan [40], développe les bases de cette théorie. Il présente les principaux outils qui seront utilisés dans ce chapitre. Plus récemment, les ouvrages de Szelki [41] et Shaked et Shantikumar [39] exposent les derniers résultats de recherche concernant cette théorie.
Autres modèles
L’analyse des modèles avec arrivées par groupe se trouve dans [25], et celle des systèmes avec rappels et clients non-persistants est réalisée dans [19]. Les systèmes à multiserveurs sont décrits par Hanschke [28] ainsi que par Boots et Tijms [8]. Les modèles avec population des clients potentiels finie ont fait l’objet des investigations de Artalejo [2] et également de Falin et Artalejo [21]. Ces dernières années, on observe un grand intérêt pour les systèmes de files d’attente avec rappels et arrivées négatives, où l’arrivée d’un client négatif a pour effet la suppression d’un ou plusieurs clients dans le système, Artalejo [3], Artalejo et Gomez-Corral [4]. Un autre axe de recherche concerne les systèmes de files d’attente avec rappels où le flux d’appels primaires est modélisé comme BMAP (Batch Markovian Arrival Process), Dudin et Klimenok [18].
Interruption de service dans les systèmes d’attente avec rappels
L’interruption de service est un événement qui empêche la continuité du service des clients. Son influence ne peut pas être étudiée sans spécifier l’interaction entre le processus d’interruption et le processus de service. Cette interaction peut être sans préemption, c’est-à-dire qu’elle n’intervient pas pendant le service d’un client, ou avec préemption dans le cas contraire. En outre, après chaque interruption avec préemption, le client reprend le service à partir du point d’interruption ou dès le début Gaver [26].
Les modèles de files d’attente à interruption de service ont plusieurs applications dans les réseaux de télécommunication, et de nombreuses études ont été menées dans ce sens. En général, les interruptions peuvent être dues à diverses causes : la possibilité de vacance du serveur, les pannes du serveur ou l’arrivée de clients de haute priorité.
Modèles d’attente avec rappels et vacances du serveur
Les systèmes de files d’attente avec vacances peuvent être classifiés selon la discipline de service. En effet, on a
– Discipline de service exhaustif (complet) :
Chaque fois que le serveur retourne d’une vacance, il sert tous les clients se trouvant dans la file d’attente, et ceci avant de commencer une autre vacance.
– Discipline de service avec barrière :
Lorsque le serveur retourne d’une vacance, il sert seulement les clients qui étaient en attente à son arrivée.
– Discipline de service limité (N-Policy) :
A son retour de la vacance, le serveur servira au plus N clients et puis commencera une autre vacance.
– Discipline de service limité :
Après la période d’activité d’une durée fixe, le serveur prend une vacance même s’il y a des clients dans la file.
En outre, dans le cas d’un service complet, si le serveur, qui retourne d’une vacance, trouve la file d’attente vide, il exécute l’une des deux actions suivantes :
➤ Sous le schéma de vacances multiples, le serveur commence immédiatement une autre vacance et continue à prendre des vacances successives jusqu’à ce qu’il trouve au moins un client dans la file ;
➤ Sous le schéma de vacance unique, le serveur attend jusqu’à la fin de la prochaine période d’activité pendant laquelle un client au moins sera servi, avant de commencer une autre vacance (autrement dit, il y a exactement une seule vacance à la fin de chaque période d’activité).
Une comparaison des différentes politiques de service dans les modèles avec vacances est donnée dans [42].
Exemples d’application
Considérons quelques exemples d’application.
Systèmes téléphoniques modernes
Dans les échanges téléphoniques modernes, les lignes des abonnés sont connectées aux modules qui traitent les appels arrivants et ceux sortants. Dans le cas du blocage (les canaux sont occupés), les appels sortants sont placés en attente dans un tampon (de capacité infinie) tandis que les appels arrivants sont refusés et plus tard réinitialisés pour établir la connexion. Lorsque l’un des canaux se libère, un appel sortant (s’il se trouve dans le tampon) l’occupe immédiatement. De ce fait, les appels arrivants ne réussissent pas à établir la connexion aussi longtemps qu’il y a des appels dans le tampon. Ce comportement implique que les appels sortants possèdent une priorité relative sur les appels arrivants.
Réseaux LAN avec le protocole CSMA non persistant et CSMA persistant
Supposons qu’un LAN possède des utilisateurs non persistants et des utilisateurs persistants connectés par un bus. Les utilisateurs persistants sont contrôlés par l’unité centrale de façon que chaque fois lorsque le canal est libre, un utilisateur persistant l’occupe pour envoyer ces paquets. Les utilisateurs non persistants essayent la retransmission indépendamment après une durée de temps. Ce système se présente comme un système avec rappels et priorité, ou les clients type 1 sont ceux persistants, les clients type 2 sont ceux non persistants et le serveur est le bus.
Réseau cellulaire mobile
On considère un réseau cellulaire mobile, où chaque cellule est servie par une station de base différente. Une cellule particulière peut s’occuper de plusieurs communications actives simultanément. La station de base dans une cellule manipule deux types d’appels. Le premier est un appel d’origine (initié dans la cellule en question). Habituellement, un abonné avec un appel d’origine bloqué refait sa tentative après une durée de temps. Un autre type d’appels, “handoff“, apparait lorsqu’un abonné détenteur de la ligne de communication entre en cellule en question des cellules adjacentes. Si la station de base ne parvient pas à attribuer un canal libre jusqu’à ce que l’abonne sort de la région de recouvrement des cellules, il souffre de la panne durant la conversation. La dégradation de la qualité de service téléphonique dans ce cas est plus sérieuse que dans le cas d’un appel d’origine. Par conséquent, la station de base peut donner la priorité aux appels “handoff“ en attribuant une file. Dans un réseau cellulaire mobile, la perte d’un appel “handoff“ est un facteur important pour la qualité de service. Ce système peut être modélisé comme un système avec rappels, deux types de clients et perte géométrique.
Téléphone dans une banque
Prenant l’exemple d’un banquier qui doit s’occuper d’une ligne d’attente et d’un téléphone. Un tel employé prête attention au téléphone seulement quand il n’y a aucun client dans la banque. Un client arrivant et trouvant ce banquier inoccupé sera servi immédiatement ; autrement, il attend avec une probabilité q dans une file d’attente ou avec la probabilité complémentaire p=1-q décide de téléphoner plus tard jusqu’à ce qu’il obtienne son service.
|
Table des matières
Introduction générale
Chapitre 1: Systèmes de files d’attente avec rappels
1.1. Introduction
1.2. Classification
1.3. Modèle gènèral
1.4. Modèle d’attente avec rappels de type M/G/1
1.4.1. Description du modèle
1.4.2. Chaine de Markov induite
1.4.3. Distribution conjointe de l’état du serveur et du nombre de clients en orbite
1.4.4. Période d’activité et temps d’attente
1.5. Les propriétés de monotonie de la chaine de Markov induite
1.5.1. Motonie interne et externe de l’opérateur de transition
1.5.2. Inégalités stochastiques pour la distribution stationnaire du nombre de clients dans le système. Les propriétés de monotonie de la chaine de Markov induite
1.5.3. Inégalités stochastiques pour le nombre moyen de clients servis durant la période d’activité
1.6. Autres modèles
1.7. Conclusion
Chapitre 2: Interruption de service dans les systèmes d’attente avec rappels
2.1. Introduction
2.2. Modèles d’attente avec rappels et vacances du serveur
2.2.1. Description du modèle
2.2.2. Analyse du modèle
2.2.3. Mesures de performance
2.3. Modèles d’attente avec rappels et priorité
2.3.1. Modèle d’attente avec rappels de type et priorité relative
2.4. Modèles avec rappels et serveur sujet à des pannes aléatoires
2.4.1. Modèle d’attente avec rappels de type M/G/1 et serveur non fiable
2.4.2. Modèle M/G/1 avec rappels et deux types de pannes actives
2.5. Conclusion
Chapitre 3: Systèmes de files d’attente avec rappels et interruptions de service dans la modélisation des phénomènes réels
3.1. Introduction
3.2. Systèmes réels modélisables comme systèmes d’attente avec rappels et priorité relative
3.2.1. Modèle 1
3.2.2. Modèle 2
3.2.3. Exemples d’application
3.3. Systèmes réels modélisables comme systèmes d’attente avec rappels et priorité absolue
3.3.1. Bureaux d’information
3.3.2. Réseaux de communication
3.4. Systèmes réels modélisables comme systèmes de files d’attente avec rappels et vacances du serveur
3.4.1. Exemples d’application
3.5. Systèmes réels modélisables comme un système de files d’attente avec rappels et serveur sujet à des pannes
3.5.1. Transmission des messages à travers des réseaux fac-similes
3.5.2. Réseaux informatiques avec infection virale
3.5.3. Interaction hôte-parasite (application biologique)
3.6. Conclusion
Chapitre 4: Modèle d’attente avec rappels et priorité absolue
4.1. Introduction
4.2. Description mathématique du modèle
4.3. Condition d’érgodicité
4.4. Distribution stationnaire de l’état du système
4.5. Mesures de performances
4.6. Illustration numérique
4.7. Conclusion
Chapitre 5: Monotonie de la chaîne de Markov induite d’un modèle M/G/1 avec rappels et priorité absolue
5.1. Introduction
5.2. Les propriétés de monotonie de la chaine de Markov induite
5.3. Inégalités stochastiques pour la distribution stationnaire
5.4. Applications numériques
5.5. Conclusion
Conclusion Générale
