TU Darmstadt / ULB / TUbiblio

Model reductions for queueing and agent-based systems with applications in communication networks

KhudaBukhsh, Wasiur Rahman (2018):
Model reductions for queueing and agent-based systems with applications in communication networks.
Darmstadt, Technische Universität, [Online-Edition: http://tuprints.ulb.tu-darmstadt.de/7588],
[Ph.D. Thesis]

Abstract

The dissertation studies two distinct classes of models from applied probability literature and attempts to answer questions that are of asymptotic nature. The answers to those questions are obtained by means of various probability approximations. The two classes of models in question belong to the mathematical branches of queueing theory and Markovian Agent-based Models (MABMs). The unlikely marriage of these two branches of probability theory in this dissertation can be ascribed to a particular communication networking scenario, the mathematical modelling of which has been the main motivation behind this work. The networking scenario consists of two central problems - the uploading problem and the content distribution problem.

In the context of Internet of Things (IoT), collaborative uploading describes a type of crowdsourcing scenario in networked environments where a device utilises multiple paths to upload content to a centralised processing entity such as a cloud service. The uploading problem is an umbrella term for research problems arising from such a collaborative uploading scenario and encompasses questions such as how long it will take for a data chunk to be transported, how many paths we should choose (scheduling), how to split a data chunk optimally (provisioning). Modelling the uploading problem as a scheduling task in a Fork-Join (FJ) system, a parallel queueing system with output synchronisation, we develop the notions of optimal stochastic scheduling, and provisioning. Since an exact analysis of FJs system is infeasible under general settings, the objectives of designing optimal stochastic schedules and provisions are achieved by approximating probabilities of rare events (e.g., long waiting times) with exponential estimates. This is accomplished by making use of martingale techniques and establishing a Large Deviations Principle (LDP) for steady-state waiting times. In order to incorporate possible burstiness or phase-type behaviour, the effects of changing environment are modelled using a Markov-additive process. The resultant theoretical insights are finally used to design optimal collaborative uploading strategies.

In addition to general FJ systems, two special queueing systems are analysed using random time change representation for Markov processes in this dissertation. Unlike FJ systems, these two special queueing systems do not impose an inherent output synchronisation. The first of these two special cases is a parallel queueing system with finite buffers. Preliminary ideas on characterising the total loss process and optimal probabilistic scheduling are presented. As an application to large heterogeneous clusters of parallel servers, we also present a scaling limit as the number of servers increases to infinity using the semigroup operator approach to Markov process convergence. The second queueing system considers a special case of the uploading problem where the paths can transport only one chunk of data at a time. We use multi-scaling techniques from probability theory to derive Quasi-Steady State Approximations (QSSAs) for such a queueing system. The QSSAs are particularly useful when the number of data chunks to transport is much larger compared to the number of available paths.

The second leg of the networking scenario, the distribution problem, concerns distribution of content to a number of end-users. We specifically focus on the large-scale problem when the number of end-users is large. In order to understand the dynamics of the distribution problem better, we model it as an MABM. Three different approximations for MABMs are presented in this dissertation. First, a Functional Central Limit Theorem (FCLT) for key population counts are proved for an Information-Dissemination (ID) process on configuration model random graphs. An ID process is mathematically equivalent to a stochastic compartmental Susceptible-Infected (SI) epidemic process. Second, we devise a state-aggregation procedure based on a local notion of symmetry (automorphism) of the underlying graph for general MABMs ensuring approximate lumpability. Third, as an application, primitive chunk selection strategies for Peer-to-Peer (P2P) live streaming systems, such as the Latest Deadline First (LDF) and the Earliest Deadline First (EDF), are analysed using mean-field theory and an improved mixed strategy, called SchedMix, is proposed.

As the mathematical models are developed in response to the questions arising from the communication networking scenario, special emphasis has been put on exploring how the resultant approximation tools can also be applied to problems in epidemiology, systems and synthetic biology, statistical physics, and other branches of science.

Item Type: Ph.D. Thesis
Erschienen: 2018
Creators: KhudaBukhsh, Wasiur Rahman
Title: Model reductions for queueing and agent-based systems with applications in communication networks
Language: English
Abstract:

The dissertation studies two distinct classes of models from applied probability literature and attempts to answer questions that are of asymptotic nature. The answers to those questions are obtained by means of various probability approximations. The two classes of models in question belong to the mathematical branches of queueing theory and Markovian Agent-based Models (MABMs). The unlikely marriage of these two branches of probability theory in this dissertation can be ascribed to a particular communication networking scenario, the mathematical modelling of which has been the main motivation behind this work. The networking scenario consists of two central problems - the uploading problem and the content distribution problem.

In the context of Internet of Things (IoT), collaborative uploading describes a type of crowdsourcing scenario in networked environments where a device utilises multiple paths to upload content to a centralised processing entity such as a cloud service. The uploading problem is an umbrella term for research problems arising from such a collaborative uploading scenario and encompasses questions such as how long it will take for a data chunk to be transported, how many paths we should choose (scheduling), how to split a data chunk optimally (provisioning). Modelling the uploading problem as a scheduling task in a Fork-Join (FJ) system, a parallel queueing system with output synchronisation, we develop the notions of optimal stochastic scheduling, and provisioning. Since an exact analysis of FJs system is infeasible under general settings, the objectives of designing optimal stochastic schedules and provisions are achieved by approximating probabilities of rare events (e.g., long waiting times) with exponential estimates. This is accomplished by making use of martingale techniques and establishing a Large Deviations Principle (LDP) for steady-state waiting times. In order to incorporate possible burstiness or phase-type behaviour, the effects of changing environment are modelled using a Markov-additive process. The resultant theoretical insights are finally used to design optimal collaborative uploading strategies.

In addition to general FJ systems, two special queueing systems are analysed using random time change representation for Markov processes in this dissertation. Unlike FJ systems, these two special queueing systems do not impose an inherent output synchronisation. The first of these two special cases is a parallel queueing system with finite buffers. Preliminary ideas on characterising the total loss process and optimal probabilistic scheduling are presented. As an application to large heterogeneous clusters of parallel servers, we also present a scaling limit as the number of servers increases to infinity using the semigroup operator approach to Markov process convergence. The second queueing system considers a special case of the uploading problem where the paths can transport only one chunk of data at a time. We use multi-scaling techniques from probability theory to derive Quasi-Steady State Approximations (QSSAs) for such a queueing system. The QSSAs are particularly useful when the number of data chunks to transport is much larger compared to the number of available paths.

The second leg of the networking scenario, the distribution problem, concerns distribution of content to a number of end-users. We specifically focus on the large-scale problem when the number of end-users is large. In order to understand the dynamics of the distribution problem better, we model it as an MABM. Three different approximations for MABMs are presented in this dissertation. First, a Functional Central Limit Theorem (FCLT) for key population counts are proved for an Information-Dissemination (ID) process on configuration model random graphs. An ID process is mathematically equivalent to a stochastic compartmental Susceptible-Infected (SI) epidemic process. Second, we devise a state-aggregation procedure based on a local notion of symmetry (automorphism) of the underlying graph for general MABMs ensuring approximate lumpability. Third, as an application, primitive chunk selection strategies for Peer-to-Peer (P2P) live streaming systems, such as the Latest Deadline First (LDF) and the Earliest Deadline First (EDF), are analysed using mean-field theory and an improved mixed strategy, called SchedMix, is proposed.

As the mathematical models are developed in response to the questions arising from the communication networking scenario, special emphasis has been put on exploring how the resultant approximation tools can also be applied to problems in epidemiology, systems and synthetic biology, statistical physics, and other branches of science.

Place of Publication: Darmstadt
Divisions: 18 Department of Electrical Engineering and Information Technology
18 Department of Electrical Engineering and Information Technology > Institute for Telecommunications > Bioinspired Communication Systems
18 Department of Electrical Engineering and Information Technology > Institute for Telecommunications
DFG-Collaborative Research Centres (incl. Transregio)
DFG-Collaborative Research Centres (incl. Transregio) > Collaborative Research Centres
DFG-Collaborative Research Centres (incl. Transregio) > Collaborative Research Centres > CRC 1053: MAKI – Multi-Mechanisms Adaptation for the Future Internet
DFG-Collaborative Research Centres (incl. Transregio) > Collaborative Research Centres > CRC 1053: MAKI – Multi-Mechanisms Adaptation for the Future Internet > C: Communication Mechanisms
DFG-Collaborative Research Centres (incl. Transregio) > Collaborative Research Centres > CRC 1053: MAKI – Multi-Mechanisms Adaptation for the Future Internet > C: Communication Mechanisms > Subproject C3: Content-centred perspective
Date Deposited: 29 Jul 2018 19:55
Official URL: http://tuprints.ulb.tu-darmstadt.de/7588
URN: urn:nbn:de:tuda-tuprints-75888
Referees: Koeppl, Prof. Heinz and Steinmetz, Prof. Ralf and Aurzada, Prof. Frank
Refereed / Verteidigung / mdl. Prüfung: 28 June 2018
Alternative Abstract:
Alternative abstract Language
Die Dissertation untersucht zwei verschiedene Klassen von Modellen für Warteschlangenund Agenten-basierte Systeme aus der Literatur der angewandten Wahrscheinlichkeitstheorie und versucht Fragen zu beantworten, die weitgehend von asymptotischer Natur sind. Die betrachtete Verflechtung dieser beiden unterschiedlichen Zweige der Wahrscheinlichkeitstheorie ist auf ein bestimmtes Kommunikationsnetzwerkszenario zurückzuführen, dessen mathematische Modellierung die Hauptmotivation dieser Arbeit ist. Das Netzwerkszenario besteht aus zwei zentralen Problemen - dem Hochladeproblem und dem Inhaltsverteilungsproblem. Im Kontext des Internet der Dinge (Internet of Things) beschreibt kollaboratives Hochladen eine Art von Crowdsourcingszenario in vernetzten Umgebungen, in denen ein Gerät mehrere Pfade zum Hochladen von Inhalten in eine zentrale Verarbeitungsentität wie einen Cloud-Service verwendet. Das Hochladeproblem ist ein Sammelbegriff für Forschungsprobleme, die sich aus einem solchen Szenario ergeben, und umfasst unter anderem die Fragen 1) Wie lange dauert es, um einen Datenblock zu transportieren? 2) Wie viele Pfade sollten ausgewählt werden (Scheduling) um einen Datenblock optimal aufzuteilen (Provisionierung)? Indem wir das Hochladeproblem als Scheduling-Task in einem Fork-Join (FJ)-System, nämlich einem parallelen Warteschlangensystem mit Ausgangssynchronisation, modellieren, entwickeln wir die Begriffe des optimalen stochastischen Schedulings und der Provisionierung. Da eine exakte Analyse des FJ-Systems unter allgemeinen Annahmen über die Ankünfte und den bereitgestellten Dienst sich bislang als hoch diffizil herausgestellt hat, werden die Ziele, das optimale stochastische Scheduling und die Provisionierung zu entwerfen, durch Näherungen von Warscheinlichkeiten seltener Ereignisse (z. B. lange Wartezeiten) mit exponentiellen Schätzungen erreicht. Dies wird durch die Nutzung von Martingaltechniken und die Einführung eines Large Deviations Principle (LDP) für stationäre Wartezeiten erzielt. Um ein mögliches Burst- oder Phasenverhalten zu berücksichtigen, werden die Auswirkungen sich ändernder Umgebungsbedingungen mit Hilfe eines Markov-additiven Prozesses modelliert. Die daraus resultierenden theoretischen Erkenntnisse werden schlussendlich verwendet, um optimale Strategien für kollaboratives Hochladen zu entwickeln. Zusätzlich zu allgemeinen FJ-Systemen werden zwei spezielle Warteschlangensysteme unter Verwendung einer zufälligen Zeitänderungsdarstellung für Markov-Prozesse in dieser Dissertation analysiert. Im Gegensatz zu FJ-Systemen erzwingen diese beiden speziellen Warteschlangensysteme keine inhärente Ausgangssynchronisation. Der erste dieser beiden Spezialfälle ist ein paralleles Warteschlangensystem mit endlichen Puffern. Hier werden Methoden zur Charakterisierung des Verlustprozesses und der optimalen probabilistischen Planung in einem solchen endlichen Puffer-Warteschlangensystem vorgestellt. Als Anwendung für große heterogene Cluster von parallelen Servern wird eine Skalierungsgrenze für eine ansteigende Anzahl der Server vorgestellt. Das zweite Warteschlangensystem berücksichtigt einen Spezialfall des Hochladeproblems, bei dem die Pfade keine Pufferungsmöglichkeiten haben. Wir verwenden Multi-Skalierungstechniken aus derWahrscheinlichkeitstheorie, um Quasi-Steady State Approximations (QSSAs) für ein solchesWarteschlangensystem abzuleiten. Die QSSAs sind besonders nützlich, wenn die Anzahl der zu transportierenden Datenblöcke viel größer ist als die Anzahl der verfügbaren Pfade. Der zweite Teil des Netzwerkszenarios, das Inhaltsverteilungsproblem, betrifft die Verteilung von Inhalten in vernetzten Umgebungen zu einer Vielzahl von Endnutzern. Hier gehen wir hauptsächlich auf die Problemstellung für eine große Anzahl von Endnutzern ein. Um die Dynamik des Verteilungsproblems besser zu verstehen, modellieren wir es als ein Markovian Agent-based Model (MABM). In dieser Dissertation werden drei verschiedene Approximationen für MABMs vorgestellt. Zuerst wird ein Functional Central Limit Theorem (FCLT) für wichtige Populationsvariablen für einen Information-Dissemination (ID)-Prozess auf zufälligen Graphen des Konfigurationsmodells bewiesen. Der Information-Dissemination (ID)-Prozess ist mathematisch äquivalent zu einem stochastischen Compartimental Susceptible-Infected (SI) epidemischen Prozess. Zweitens wird ein Zustands-Aggregationsverfahren basierend auf den lokalen Symmetrien des zugrunde liegenden Graphen für generelle MABMs entwickelt, um die approximative Lumpability sicherzustellen. Drittens werden als eine Anwendung primitive Paket-Auswahlstrategien für Peer-to-Peer (P2P) Live-Streaming-Systeme, wie zum Beispiel die Latest Deadline First (LDF) und die Earliest Deadline First (EDF), unter Verwendung der Mean-Field-Theorie analysiert und eine verbesserte gemischte Strategie, das sogenannte SchedMix, wird vorgeschlagen. Während unsere mathematischen Modelle Fragen adressieren, die sich aus dem Kommunikationsnetzwerkszenario ergeben, untersuchen wir die Tragweite der resultierenden Approximationswerkzeuge bei zusätzlicher Anwendung auf Probleme der Epidemiologie, der Systembiologie und synthetischen Biologie, der statistischen Physik und anderer Gebieten der Wissenschaft.German
Export:
Suche nach Titel in: TUfind oder in Google
Send an inquiry Send an inquiry

Options (only for editors)

View Item View Item