Research team
Expertise
The development of mathematical models to assess the performance of large and complex systems, where the main focus lies on the analysis of communication and computer systems. Examples of topics include: Mean field theory: these methods are used to assess the performance of large-scale computing systems that can no longer be analyzed using traditional queueing theory. Mean field theory studies the behavior of large and complex stochastic models using fluid dynamics. The evolution of a mean field model is typically captured by the solution of a set of ordinary, partial or delayed differential equations. In many cases one can show that the mean field model captures the system behavior as the system size tends to infinity. Garbage collection and wear levelling algorithms for flash-based solid state drives (SSDs): these algorithms heavily influence the performance and life-span of an SSD as write and erase operations on SSDs are much slower than reads and each block can only be erased a limited number of times before it becomes unstable. These algorithms are implemented in the FTL layer of the SSD controller. Load balancing and sharing algorithms: these algorithms are used in large distributed systems to balance the workload among the different processing nodes. The main performance measures include the mean response time and the system stability. Algorithms under consideration include randomized algorithms such as join-the-shortest-queue or join-the-least-loaded-queue of a set of randomly selected servers. Random access algorithms: these algorithms are designed such that bandwidth can be shared in a fair manner among a set of network users, examples include tree algorithms, 802.11-type algorithms, CSMA networks, etc. The main focus in this line of work has been on determining the throughput, delay characteristics and fairness. Recent work has focused on hard-core models for CSMA networks characterized by a conflict graph. Caching systems: Caches are omnipresent in current day computer systems and are used to provide faster access to a limited set of frequently requested items, such as webpages, YouTube videos, etc. Queueing theory: this topic focuses on the design of fast numerical algorithms to derive various performance measures of queueing systems such as the queue length and response time distributions, blocking probabilities, etc.
Stochastic and Asymptotic Improvements of Scheduling Algorithms
Abstract
Scheduling is a fundamental component in any computer system. It is the process of arranging and optimizing the execution of (computing) tasks, called jobs. Although there exists an abundance of scheduling algorithms, many systems still rely on the First-Come-First-Served (FCFS) scheduling algorithm as it is considered to be a fair scheduling algorithm that does not require any information on the job sizes or job arrival times. Moreover, given some technical conditions, it can be shown that the response time distribution under FCFS has the best possible decay, which in layman's terms means it is good at avoiding large response times, contrary to other scheduling algorithms that may have a better mean response time (such as Shortest-Remaining-Time-First). For a long time researchers believed that any improvements made to the mean response time of FCFS come at the expense of worsening its tail probabilities (i.e., "There is no such thing as a free lunch"). A very recent, original result showed that this is however not the case. More specifically, it was shown that an algorithm, named NUDGE, can be devised that improves all of the response time distribution quantiles of FCFS. This discovery opened up many new research directions in scheduling, e.g. "How much job size information (if any) is needed to improve upon FCFS?". These new fundamental open problems in scheduling are the topic of this research proposal.Researcher(s)
- Promoter: Van Houdt Benny
Research team(s)
Project type(s)
- Research Project
Mean field models for large scale computer systems with general service times.
Abstract
Markov processes have found widespread use in the analysis of computer systems and beyond. Over time the size of the systems under consideration has grown considerably, e.g., Google has hundreds of thousands of servers located in its various data centers. This growth in the system size has made conventional methods to analyse these Markov processes infeasible. As such, deterministic approximations, also known as mean field or fluid models, have been introduced to analyse such large scale systems. Interestingly, these deterministic models have been shown to correspond to the limit of a sequence of appropriately scaled Markov processes showing that the systems behaviour becomes deterministic as the system size tends to infinity. These Markov processes typically have a countable state space and the limiting system is described by a set of ordinary differential equations. However, in order to analyse large scale computer systems with general job size distributions, one needs to keep track of the age or residual service time of each job. This makes the state space uncountable and the natural candidate for the limiting system becomes a set of partial differential equations (PDEs). The aim of this project is to develop PDE mean field models for large scale computer systems, to establish convergence results and to use these models to gain insight into the system behaviour. The project combines techniques from stochastic modelling, probability, numerical analysis and simulation.Researcher(s)
- Promoter: Van Houdt Benny
- Fellow: Hellemans Tim
Research team(s)
Project type(s)
- Research Project
Load balancing and scheduling in large-scale computer systems.
Abstract
Since the introduction of the very first communication networks, queueing models have played a key role in improving network performance. This has resulted in a large body of queueing theory literature that has found widespread use in many other areas of science and technology. As the area of computer systems and networks is ever evolving, so is the need for new, tailored queueing models. Large-scale systems (e.g., grid computing or cloud computing) have become quite prevalent today and are often composed of many heterogeneous resources. The analysis of such large-scale heterogeneous systems using traditional queueing theory is prohibitively expensive as the required time and memory complexity tends to scale poorly in the system size. The aim of this project is to introduce and analyze new queueing models that provide insight into the performance of existing and novel load balancing and scheduling algorithms for large-scale systems. The problems under consideration include affinity scheduling problems motivated by MapReduce clusters, load balancers that make use of redundancy to mitigate latency caused by server unpredictability, and stateful load balancers. The main envisioned methodology exists in developing fluid approximations that are validated using simulation experiments and that can be shown to become exact as the system size tends to infinity. The project combines techniques from stochastic modelling, probability, dynamical systems, numerical analysis and simulation.Researcher(s)
- Promoter: Van Houdt Benny
Research team(s)
Project type(s)
- Research Project
Mean field models for large scale computer systems with general service times
Abstract
Markov processes have found widespread use in the analysis of computer systems and beyond. Over time the size of the systems under consideration has grown considerably, e.g., Google has hundreds of thousands of servers located in its various data centers. This growth in the system size has made conventional methods to analyse these Markov processes infeasible. As such, deterministic approximations, also known as mean field or fluid models, have been introduced to analyse such large scale systems. Interestingly, these deterministic models have been shown to correspond to the limit of a sequence of appropriately scaled Markov processes showing that the systems behaviour becomes deterministic as the system size tends to infinity. These Markov processes typically have a countable state space and the limiting system is described by a set of ordinary differential equations. However, in order to analyse large scale computer systems with general job size distributions, one needs to keep track of the age or residual service time of each job. This makes the state space uncountable and the natural candidate for the limiting system becomes a set of partial differential equations (PDEs). The aim of this project is to develop PDE mean field models for large scale computer systems, to establish convergence results and to use these models to gain insight into the system behaviour. The project combines techniques from stochastic modelling, probability, numerical analysis and simulation.Researcher(s)
- Promoter: Van Houdt Benny
- Fellow: Hellemans Tim
Research team(s)
Project type(s)
- Research Project
Replenishment policies for production/inventory systems with endogenous lead times.
Abstract
Inventory control has been a popular research topic for a long time. The optimality of various inventory replenishment policies has been studied under a variety of assumptions in demand and lead-time distributions and cost structures. However, its optimality is always studied in a local inventory environment where lead-times are treated exogenously with respect to the replenishment policy. This assumption, however, does not hold in integrated production/inventory systems, where the replenishment policy of the inventory control generates orders that load the production facility. In a finite capacity production environment, the lead-times are load dependent and affected by the current size of the order queue in the production system. In previous research we have studied the impact of traditional replenishment rules in production/inventory systems and we have shown how the inclusion of endogenous lead-times many lead to higher costs. In the proposed research project we aim to propose a class of replenishment policies that are different from the traditional policies and perform better in a production/inventory environment.Researcher(s)
- Promoter: Van Houdt Benny
Research team(s)
Project type(s)
- Research Project
Design and analysis of garbage collection algorithms for flash-based solid state drives.
Abstract
The main objective of this project is to design and to analyze the performance of garbage collection algorithms for flash-based solid state drives that make use of page-, block- or hybrid-mapped flash translation layers. The analysis will mainly focus on the impact of the garbage collection algorithm on the write performance and lifespan of the solid state drive, while different data models, data separation techniques and the use of the TRIM command will be considered.Researcher(s)
- Promoter: Van Houdt Benny
Research team(s)
Project type(s)
- Research Project
A new paradigm for the service process in queueing systems, with applications in computer and communication networks.
Abstract
Our objective is to derive closed-form results and/or fast numerical procedures to assess the main performance characteristics of the proposed queueing models, such as throughput, customer delay, system content, loss characteristics, etc., and to apply these results in a number of relevant areas such as Cognitive Radio, Medium Access Control and server farms.Researcher(s)
- Promoter: Van Houdt Benny
Research team(s)
Project type(s)
- Research Project
Design and analysis of multiple access algorithms for dynamic spectrum access.
Abstract
In order to guarantee quality-of-service, the wireless network spectrum has been licensed in a static manner. This has resulted in a substantial amount of underutilization in some these licensed frequency bands. With the ever-increasing demand for wireless bandwidth, secondary users are now being introduced (using cognitive radios) to take advantage of the remaining free space on these frequency bands. Within this project multiple access algorithms to coordinate the transmissions of these secondary users are developed and analyzed (using analytical methods). This problem is fundamentally different from the traditional (multi-channel) multiple access problem due to the presence of the primary users. The project focuses to a large extent on algorithms with free access (allowing users to join in without difficulty) and tree algorithm to resolve possible conflicts. The main performance measures of interest include the maximum stable throughput, the resulting delay characteristics and the energy consumption of these algorithms.Researcher(s)
- Promoter: Van Houdt Benny
- Fellow: Block Robbe
Research team(s)
Project type(s)
- Research Project
Design and analysis of multiple access algorithms for dynamic spectrum access.
Abstract
In order to guarantee quality-of-service, the wireless network spectrum has been licensed in a static manner. This has resulted in a substantial amount of underutilization in some these licensed frequency bands. With the ever-increasing demand for wireless bandwidth, secondary users are now being introduced (using cognitive radios) to take advantage of the remaining free space on these frequency bands. Within this project multiple access algorithms to coordinate the transmissions of these secondary users are developed and analyzed (using analytical methods). This problem is fundamentally different from the traditional (multi-channel) multiple access problem due to the presence of the primary users. The project focuses to a large extent on algorithms with free access (allowing users to join in without difficulty) and tree algorithm to resolve possible conflicts. The main performance measures of interest include the maximum stable throughput, the resulting delay characteristics and the energy consumption of these algorithms.Researcher(s)
- Promoter: Van Houdt Benny
- Fellow: Block Robbe
Research team(s)
Project type(s)
- Research Project
Scalable dimensioning techniques for optical grids
Abstract
For traditional optical networks various network dimensioning techniques exist to determine the required amount of network resources. Grid users however are not concerned with the exact location of the server that executes their job. As a result, the destination is not known a priori, which implies that traditional solutions cannot be applied directly. Within this project we wish to address this problem using Mean Field models and relaxation techniques for Integer Linear Programming problems.Researcher(s)
- Promoter: Van Houdt Benny
Research team(s)
Project type(s)
- Research Project
Stochastic modeling of optical buffers and switching systems based on Fibre Delay Lines.
Abstract
The main objectives of the proposed project are the derivation of analytic or semi-analytic solutions for adequate stochastic models of optical buffers and switches, allowing fast and efficient calculation of various performance measures, such as packet loss, mean delay, delay jitter, etcetera. Ultimately, these measures quantify the QoS (Quality of Service) the users of the network will experience, and, as such, are of prime importance to network designers and providers.Researcher(s)
- Promoter: Blondia Chris
- Co-promoter: Van Houdt Benny
Research team(s)
Project type(s)
- Research Project
Novel Stochastic models for the evaluation of telecommunication systems.
Abstract
This project aims at developing a series of novel stochastic models to assess the performance of telecommunication systems. The emphasis lies on setting up efficient computational procedures for each of these models. Applications are situated in the area of cable (DOCSIS) access networks, optical switches/buffers, the backbone Internet, etc.Researcher(s)
- Promoter: Van Houdt Benny
Research team(s)
Project type(s)
- Research Project
New Analytical Approaches in Performance Modeling of Telecommunication Systems.
Abstract
The main purpose of this project is to set up several new queueing models as well as developing efficient computational methods that allow us to determine the most significant performance measures (for instance, the waiting time distribution or the number of users that can share a resource without violating the agreement between the end users and the network provider). The choice of these models is driven by the latest developments in the telecommunication field. For a limited number of models we already obtained some preliminary results during the current FWO postdoc fellowship. The emphasis of the ongoing project lies mostly on applying existing models to broadband access networks, while the development of new models is of lesser importance. It is thus fair to state that the scope of this project proposal is somewhat more general.Researcher(s)
- Promoter: Blondia Chris
- Fellow: Van Houdt Benny
Research team(s)
Project type(s)
- Research Project
Design and performance evaluation of medium access control (MAC) algorithms in broadband access networks.
Abstract
The objective of this project is to evaluate the performance of random access algorithms. Such algorithms are deployed in the current and next generation access networks, e.g., HFC networks, to allow for end users to reserve uplink bandwidth. Both a theoretical as well as a practical approach is used. Moreover, we also aim at further developing the theoretical tools, such as queuing theory and stochastic processes, often used within such a context.Researcher(s)
- Promoter: Blondia Chris
- Fellow: Van Houdt Benny
Research team(s)
Project type(s)
- Research Project