Performance modeling and congestion control through discrete-time queueing

Abstract

Die Basis digitaler Systeme ist eine zeitdiskrete Verarbeitung.<br />Es ist daher natürlicher und naheliegender zeitdiskrete Warteschlangensysteme zu verwenden um die Leistung von rechnerbasierten Kommunikationssystemen zu analysieren. Die Verwendung ist weit verbreitet, insbesondere für Zeitschlitz basierte Systeme, um das exakte Verhalten dieser Systeme zu modellieren, was mit zeitkontinuierlichen Warteschlangensystemen wegen der limitierenden Einschränkungen nicht effizienter gelöst werden kann. In solchen Systemen werden alle Aktivitäten durch äquidistante Takt Impulse kontrolliert und synchronisiert, womit der Takt die Zeit in Zeitschlitze konstanter Größe unterteilt.<br />In jedem Netz ist die Last (der Kunde) das einzige Element für das wir uns interessieren, weil sich nur diese verändert (durch Senden und Empfangen). Der wesentlichste Faktor ist die Wartezeit die abgewartet werden muss bis ein erwünschtes Ereignis eintritt. Der Warteraum ist der einzige Bereich in dem für eine unbestimmte Zeit Last bis zur Verarbeitung zurückgehalten wird. Daher konzentrieren wir uns in dieser Dissertation in allen Modellen ausschließlich darauf die Nutzung dieser zu untersuchen.<br />Die digitale Technologie ist überall vorhanden und Anpassungen der Systeme finden laufend statt. Um ein Verständnis für kommende Systeme zu schaffen, besteht ein dauerhafter Bedarf nach gründlichem Verständnis und nach Methoden zur Analyse solcher Systeme mittels Modellierung. Ein Modell ist eine Abstraktion des wirklichen Systems; die Warteschlangen-Theorie verwendet Warteschlangen-Systeme um reale Systeme effizienter als mit anderen Methoden (z.B. Emulation) näherungsweise zu analysieren.<br />Markov-Ketten sind eine weit verbreitete und recht effiziente Technik zur Analyse von Warteschlangensystemen. Man kann damit unterschiedliche Charakteristiken eines Warteschlangensystems erforschen, und die Methode ist analog anwendbar für verschiedene Warteschlangensysteme. Mit Markov-Ketten können die instationäre als auch stationäre Zustandswahrscheinlichkeiten eines Warteschlangensystems bestimmt werden, und daraus die verschiedene Leistungsmerkmale, wie die Anzahl der Kunden im System, der Durchsatz, die Auslastung, oder die Blockierungswahrscheinlichkeit. Auch die (Durch-)Laufzeit, oder die Zeit die benötigt wird um einen bestimmten Zustand zu erreichen, kann mit Markov-Ketten analytisch hergeleitet werden.<br />In dieser Dissertation etablieren wird als erstes ein grundlegendes Verständnis für verschiedene zeitdiskrete Warteschlangensysteme. Danach verwenden wir den zeitdiskreten Modellierungsansatz und konzentrieren uns auf die Warteräume um die Problemfälle Stau und Überlast zu untersuchen. Im Bereich heutiger sich stetig verändernder und mit zunehmend unterschiedlicheren Diensten belasteter Netze, stellt die Entwicklung von effektiven und effizienten Staukontrollstrategien eine nicht leicht zu lösende wissenschaftliche Herausforderung dar. Wir betrachten in dieser Arbeit ausschließlich Zeitschlitz basierte Systeme und untersuchen verschiedene Systeme mittels zeitdiskreter Warteschlangentechnik, wobei Modelle entsprechend der späten als auch der frühen Ankunftshypothese verwendet werden. Schließlich modellieren und analysieren wir die Wartebereiche verschiedener limitierter Warteschlangensysteme um zwei Lastausgleichsstrategien in Hinblick auf die Vermeidung bzw. Verminderung von Überlasten und Stauungen hin zu evaluieren.<br />

The basis of operation of any digital system is time slotting.<br />Discrete-time queueing is more natural and very close to adopt for the performance analysis of a computer communication systems due to time slot characteristics. It is largely used, particularly in slotted systems in order to obtain the exact behavior of these systems, as continuous-time queueing cannot be used more effectively because of its limiting considerations. In these systems, all activities are controlled and synchronized with clocked pulses where clock divides the time into a chain or series of equally sized slots.<br />In any network, customer is an only element in which we are interested and to move around it (sending and receiving), whereas the major factor which affects it is a queueing delay that refrains to obtain the desired results. A waiting area (buffer) is an only place which holds this customer prior to service for an ambiguous time, this is why, in this dissertation we only focus ourself in all our models to investigate it.<br />The technology is very pervasive and upgrades to the equipment are very frequent. To develop the understanding about these emerging systems a continuous need arise to grasp and derive such systems thoroughly and approach them through modeling. A model is an abstraction of a real system and queueing theory uses a queueing model to approximate that system more efficiently than the other methods.<br />Markov chains is a very powerful and efficient technique to model and investigate a queueing system. One can explore many different characteristics of a queueing systems very easily, conveniently and it is acceptable in many queueing systems. Markov chains are more frequently used to calculate the transient or stationary system state probabilities of queueing systems, from which various performance measures such as the number of customers in the system, system throughput, server utilization and the probability of blocking can be obtained. Sometimes the flow time through a queueing system can also be determined using Markov chains, or the time that is needed to reach a certain state.<br />In this dissertation, first we use to develop and understand various queueing systems in discrete-time domain then we use to apply our discrete-time modeling approach by focusing a buffer to address the problem of congestion and overloading in a more advanced way by modeling and analyzing it in discrete-time domain. In performance modeling, congestion control strategies become a challenging field of research in present networks to accommodate the increasingly diverse range of services and types of customers.<br />Throughout in our work, we use slotted systems and approached different systems through discrete-time queueing techniques using late and an early arrival system modeling approach. We used two different techniques of load balancing strategies in discrete-time domain to model and analyze buffer(s) for any queueing system which has limited resources in order to avoid or minimize overloading and congestion.