Queueing analysis of network edge nodes based on multi-dimensional state diagrams

Abstract

The field of communication networks is evolving very quickly.<br />The rapid growth in the number of users demands higher bandwidth networks with high speed components. To satisfy this need, tools are required to analyze the various network components so that questions such as "how much", "how many" and "how long" can be adequately answered before these components can be deployed. One such tool is the analysis of queueing systems using a state diagram approach. State diagrams are very useful for understanding the working and the analysis of a wide range of systems. However, their complexity has been a major factor in their limited use for analyzing large systems. Several techniques are developed in this study to depict complex multi-dimensional state diagrams in a standard and comprehendible manner. Most networks and their components can be represented with equivalent queueing models.<br />This study focuses on one of the most important components of the network - the edge nodes - by developing their equivalent queueing models and using the state diagram depiction techniques developed in this study to analyze their behavior and limitations.<br />An ingress edge node performs two main tasks. It aggregates data coming from multiple streams connected to its input and then sends this aggregated data through its output towards the destination. This study concentrates on analyzing these two parts. First the commonly used strategy of serving multiple incoming requests in a cyclic manner is studied by modelling the node as a finite capacity multi-queue system with non-exhaustive cyclic service. Several models are proposed and analyzed, from the simple two- and three-queue systems, and their generalization as n-queue systems, to more complicated models such as those having priority queues and non-zero switchover times. Then the architectures of optical edge nodes are investigated and a queueing model is developed for an optical edge switch. This model is then analyzed to study the various characteristic measures of the switch, which can be used to dimension these switches.<br />

Die Technik der Kommunikationsnetze entwickelt sich sehr rasch weiter. Die kontinuierlich zunehmende Anzahl der Nutzer von Informationssystemen verlangt stetig nach breitbandigeren Netzen und schnelleren Netzkomponenten. Um diese Weiterentwicklung effizient voranzubringen werden Werkzeuge benötigt mit deren Hilfe neue Netzkomponenten analysiert werden können, noch bevor diese tatsächlich gebaut werden. Insbesondere sind Antworten auf die Fragen "wie viel übertragungskapazität", "wie viele Anschlüsse" und "wie lange dauert die Verarbeitung" von entscheidender Bedeutung. Ein dazu geeignetes Verfahren ist die Analyse mittels Wartesystemen (queueing systems) basierend auf Zustandsdiagrammen (state diagrams). Letzere unterstützen sowohl das Verständniss als auch die analytische Betrachtung einer großen Gruppe von Systemen. Allerdings hindert die damit im allgemeinen verbundene hohe Komplexität deren Anwendung bei der Analyse großer Systeme. Mehrere Methoden zur allgemein verständlichen Darstellung komplexer Wartesysteme wurden deshalb während der Studie entwickelt. Die meisten Netze sowie deren Komponenten können mithilfe von äquivalenten Wartemodellen dargestellt und analysiert werden. Diese Studie konzentriert sich hierbei auf eine der enscheidensten und komplexesten Netzkomponenten, die sogenannten Zugangsknoten (edge nodes). Die äquivalenten Wartemodelle hierfür werden entwickelt und Verhalten als auch Grenzen der damit modelierten Systeme mithilfe der entwickelten Zustandsdiagramm-Darstellungen analysiert.<br />Ein Zugangsknoten erfüllt zwei wesentliche Aufgaben: erstens vereint er die Datenströme mehrerer Eingänge und zweitens übergibt er diese als Gesamteinheit (aggregate) dem Netz so, dass alle gemeinsam an ihr Ziel geleitet werden. Die Studie konzentriert sich auf diese beiden Aufgaben.<br />Als erstes werden die üblichen Strategien zur Behandlung mehrerer gleichzeitiger übertragungs anforderungen mittels zyklische Verarbeitungssystemen (Round Robin) als Wartesysteme mit parallelen Eingangspuffern endlicher Kapazität und nicht erschöpfendem Abfertigungsstrategie (non-exhaustive cyclic service) modeliert und analyisert. Mehrere Modelle werden hierzu vorgestellt und analysiert, vom einfachen zwei/drei Warteschlangensystem, deren Verallgemeinerung zum n-Warteschlangensystem, bis hin zu den wesentlich schwierigeren Modellen mit priorisierten Warteschlangen sowie end-lichen Umschaltzeiten beim Wechsel der gerade bedienten Warteschlange. Danach werden die Architekturen optischer Zugangsknoten untersucht und ein entsprechendes Wartemodel entwickelt. Aus der Analyse dieses Wartemodelles werden Gleichungen für die verschiedenen Charakteristika (performance metrics) dieser Zugangsknotenarchitektur abgeleitet, welche zur Dimensionierung eines derartigen Zugangsknotens verwendet werden können.