Rein Vesilo
Current Organizations / Institutes
The organizations/institutes from the scholar's latest article
Previous Organizations / Institutes
The organizations / institutes from the scholar's other articles in the past ten years
Rein Vesilo has a total of 22 co-authors. Here are the top co-authors by number of shared publications:
- Edward Omey
Faculty of Economics and Business-Campus Brussels KU Leuven Warmoesberg 26 1000 Brussels Belgium
4 shared publications - Iain B. Collings
School of Engineering, Macquarie University, Sydney, NSW, Australia
3 shared publications - Alan Scheller-Wolf
Tepper School of Business, Carnegie Mellon University, Pittsburgh, Pennsylvania 15213
2 shared publications - Benjamin Berg
Carnegie Mellon University, United States of America
2 shared publications - Linda M. Davis
Institute for Telecommunications Research, University of South Australia
2 shared publications - Mor Harchol-Balter
Computer Science Department, Carnegie Mellon University, Pittsburgh, USA
2 shared publications
Latest Publications
- Open Access
- 26 August 2024
- Published by Springer Nature in Queueing Systems
- Vol. 108 (3-4) , 475-577
Core allocation to minimize total flow time in a multicore system in the presence of a processing time constraint
Data centers are a vital and fundamental infrastructure component of the cloud. The requirement to execute a large number of demanding jobs places a premium on processing capacity. Parallelizing jobs to run on multiple cores reduces execution time. However, there is a decreasing marginal benefit to using more cores, with the speedup function quantifying the achievable gains. A critical performance metric is flow time. Previous results in the literature derived closed-form expressions for the optimal allocation of cores to minimize total flow time for a power-law speedup function if all jobs are present at time 0. However, this work did not place a constraint on the makespan. For many diverse applications, fast response times are essential, and latency targets are specified to avoid adverse impacts on user experience. This paper is the first to determine the optimal core allocations for a multicore system to minimize total flow time in the presence of a completion deadline (where all jobs have the same deadline). The allocation problem is formulated as a nonlinear optimization program that is solved using the Lagrange multiplier technique. Closed-form expressions are derived for the optimal core allocations, total flow time, and makespan, which can be fitted to a specified deadline by adjusting the value of a single Lagrange multiplier. Compared to the unconstrained problem, the shortest job first property for optimal allocation is maintained; however, a number of other properties require revising and other properties are only retained in a modified form (such as the scale-free and size-dependence properties). It is found that with a completion deadline the optimal solution may contain groups of simultaneous completions. In general, all possible patterns of single- and group-completion need to be considered, producing an exponential search space. However, the paper determines analytically that the optimal completion pattern consists of a sequence of single completions followed by a single group of simultaneous completions at the end, which reduces the search space dimension to being linear. The paper validates the Lagrange multiplier approach by verifying constraint qualifications.
- 26 August 2024
- Published by Springer Nature in Queueing Systems
- Vol. 108 (3-4) , 475-577
Open AccessCore allocation to minimize total flow time in a multicore system in the presence of a processing time constraint
Data centers are a vital and fundamental infrastructure component of the cloud. The requirement to execute a large number of demanding jobs places a premium on processing capacity. Parallelizing jobs to run on multiple cores reduces execution time. However, there is a decreasing marginal benefit to using more cores, with the speedup function quantifying the achievable gains. A critical performance metric is flow time. Previous results in the literature derived closed-form expressions for the optimal allocation of cores to minimize total flow time for a power-law speedup function if all jobs are present at time 0. However, this work did not place a constraint on the makespan. For many diverse applications, fast response times are essential, and latency targets are specified to avoid adverse impacts on user experience. This paper is the first to determine the optimal core allocations for a multicore system to minimize total flow time in the presence of a completion deadline (where all jobs have the same deadline). The allocation problem is formulated as a nonlinear optimization program that is solved using the Lagrange multiplier technique. Closed-form expressions are derived for the optimal core allocations, total flow time, and makespan, which can be fitted to a specified deadline by adjusting the value of a single Lagrange multiplier. Compared to the unconstrained problem, the shortest job first property for optimal allocation is maintained; however, a number of other properties require revising and other properties are only retained in a modified form (such as the scale-free and size-dependence properties). It is found that with a completion deadline the optimal solution may contain groups of simultaneous completions. In general, all possible patterns of single- and group-completion need to be considered, producing an exponential search space. However, the paper determines analytically that the optimal completion pattern consists of a sequence of single completions followed by a single group of simultaneous completions at the end, which reduces the search space dimension to being linear. The paper validates the Lagrange multiplier approach by verifying constraint qualifications.
- 15 October 2022
- Published by Springer Nature in Journal of Mathematical Sciences
- Vol. 267 (2) , 180-195
Revisiting the Product of Random Variables
- 15 October 2022
- Published by Springer Nature in Journal of Mathematical Sciences
- Vol. 267 (2) , 180-195
Revisiting the Product of Random Variables
- 3 March 2021
- Published by Cambridge University Press (CUP) in Probability in the Engineering and Informational Sciences
- Vol. 36 (3) , 690-731
SCALING PROPERTIES OF QUEUES WITH TIME-VARYING LOAD PROCESSES: EXTENSIONS AND APPLICATIONS
New computing and communications paradigms will result in traffic loads in information server systems that fluctuate over much broader ranges of time scales than current systems. In addition, these fluctuation time scales may only be indirectly known or even be unknown. However, we should still be able to accurately design and manage such systems. This paper addresses this issue: we consider anM/M/1 queueing system operating in a random environment (denotedM/M/1(R)) that alternates between HIGH and LOW phases, where the load in the HIGH phase is higher than in the LOW phase. Previous work on the performance characteristics ofM/M/1(R) systems established fundamental properties of the shape of performance curves. In this paper, we extend monotonicity results to include convexity and concavity properties, provide a partial answer to an open problem on stochastic ordering, develop new computational techniques, and include boundary cases and various degenerateM/M/1(R) systems. The basis of our results are novel representations for the mean number in system and the probability of the system being empty. We then apply these results to analyze practical aspects of system operation and design; in particular, we derive the optimal service rate to minimize mean system cost and provide a bias analysis of the use of customer-level sampling to estimate time-stationary quantities.
- 3 March 2021
- Published by Cambridge University Press (CUP) in Probability in the Engineering and Informational Sciences
- Vol. 36 (3) , 690-731
SCALING PROPERTIES OF QUEUES WITH TIME-VARYING LOAD PROCESSES: EXTENSIONS AND APPLICATIONS
New computing and communications paradigms will result in traffic loads in information server systems that fluctuate over much broader ranges of time scales than current systems. In addition, these fluctuation time scales may only be indirectly known or even be unknown. However, we should still be able to accurately design and manage such systems. This paper addresses this issue: we consider anM/M/1 queueing system operating in a random environment (denotedM/M/1(R)) that alternates between HIGH and LOW phases, where the load in the HIGH phase is higher than in the LOW phase. Previous work on the performance characteristics ofM/M/1(R) systems established fundamental properties of the shape of performance curves. In this paper, we extend monotonicity results to include convexity and concavity properties, provide a partial answer to an open problem on stochastic ordering, develop new computational techniques, and include boundary cases and various degenerateM/M/1(R) systems. The basis of our results are novel representations for the mean number in system and the probability of the system being empty. We then apply these results to analyze practical aspects of system operation and design; in particular, we derive the optimal service rate to minimize mean system cost and provide a bias analysis of the use of customer-level sampling to estimate time-stationary quantities.
- Open Access
heSRPT: Optimal Parallel Scheduling of Jobs With Known Sizes
When parallelizing a set of jobs across many servers, one must balance a trade-off between granting priority to short jobs and maintaining the overall efficiency of the system. When the goal is to minimize the mean flow time of a set of jobs, it is usually the case that one wants to complete short jobs before long jobs. However, since jobs usually cannot be parallelized with perfect efficiency, granting strict priority to the short jobs can result in very low system efficiency which in turn hurts the mean flow time across jobs. In this paper, we derive the optimal policy for allocating servers to jobs at every moment in time in order to minimize mean flow time across jobs. We assume that jobs follow a sublinear, concave speedup function, and hence jobs experience diminishing returns from being allocated additional servers. We show that the optimal policy, heSRPT, will complete jobs according to their size order, but maintains overall system efficiency by allocating some servers to each job at every moment in time. We compare heSRPT with state-of-the-art allocation policies from the literature and show that heSRPT outperforms its competitors by at least 30%, and often by much more.
Open AccessheSRPT: Optimal Parallel Scheduling of Jobs With Known Sizes
When parallelizing a set of jobs across many servers, one must balance a trade-off between granting priority to short jobs and maintaining the overall efficiency of the system. When the goal is to minimize the mean flow time of a set of jobs, it is usually the case that one wants to complete short jobs before long jobs. However, since jobs usually cannot be parallelized with perfect efficiency, granting strict priority to the short jobs can result in very low system efficiency which in turn hurts the mean flow time across jobs. In this paper, we derive the optimal policy for allocating servers to jobs at every moment in time in order to minimize mean flow time across jobs. We assume that jobs follow a sublinear, concave speedup function, and hence jobs experience diminishing returns from being allocated additional servers. We show that the optimal policy, heSRPT, will complete jobs according to their size order, but maintains overall system efficiency by allocating some servers to each job at every moment in time. We compare heSRPT with state-of-the-art allocation policies from the literature and show that heSRPT outperforms its competitors by at least 30%, and often by much more.
- Open Access
heSRPT: Parallel Scheduling to Minimize Mean Slowdown
Modern data centers serve workloads which are capable of exploiting parallelism. When a job parallelizes across multiple servers it will complete more quickly, but jobs receive diminishing returns from being allocated additional servers. Because allocating multiple servers to a single job is inefficient, it is unclear how best to allocate a fixed number of servers between many parallelizable jobs. This paper provides the first optimal allocation policy for minimizing the mean slowdown of parallelizable jobs of known size when all jobs are present at time 0. Our policy provides a simple closed form formula for the optimal allocations at every moment in time. Minimizing mean slowdown usually requires favoring short jobs over long ones (as in the SRPT policy). However, because parallelizable jobs have sublinear speedup functions, system efficiency is also an issue. System efficiency is maximized by giving equal allocations to all jobs and thus competes with the goal of prioritizing small jobs. Our optimal policy, high-efficiency SRPT (heSRPT), balances these competing goals. heSRPT completes jobs according to their size order, but maintains overall system efficiency by allocating some servers to each job at every moment in time. Our results generalize to also provide the optimal allocation policy with respect to mean flow time. Finally, we consider the online case where jobs arrive to the system over time. While optimizing mean slowdown in the online setting is even more difficult, we find that heSRPT provides an excellent heuristic policy for the online setting. In fact, our simulations show that heSRPT significantly outperforms state-of-the-art allocation policies for parallelizable jobs.
Open AccessheSRPT: Parallel Scheduling to Minimize Mean Slowdown
Modern data centers serve workloads which are capable of exploiting parallelism. When a job parallelizes across multiple servers it will complete more quickly, but jobs receive diminishing returns from being allocated additional servers. Because allocating multiple servers to a single job is inefficient, it is unclear how best to allocate a fixed number of servers between many parallelizable jobs. This paper provides the first optimal allocation policy for minimizing the mean slowdown of parallelizable jobs of known size when all jobs are present at time 0. Our policy provides a simple closed form formula for the optimal allocations at every moment in time. Minimizing mean slowdown usually requires favoring short jobs over long ones (as in the SRPT policy). However, because parallelizable jobs have sublinear speedup functions, system efficiency is also an issue. System efficiency is maximized by giving equal allocations to all jobs and thus competes with the goal of prioritizing small jobs. Our optimal policy, high-efficiency SRPT (heSRPT), balances these competing goals. heSRPT completes jobs according to their size order, but maintains overall system efficiency by allocating some servers to each job at every moment in time. Our results generalize to also provide the optimal allocation policy with respect to mean flow time. Finally, we consider the online case where jobs arrive to the system over time. While optimizing mean slowdown in the online setting is even more difficult, we find that heSRPT provides an excellent heuristic policy for the online setting. In fact, our simulations show that heSRPT significantly outperforms state-of-the-art allocation policies for parallelizable jobs.
- 31 January 2019
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Wireless Communications Letters
- Vol. 8 (3) , 845-848
Stochastic Geometry Analysis of Multi-User Asynchronous OFDM Wireless Networks
This letter develops an analytical framework for the analysis of asynchronous orthogonal frequency division multiplexing (OFDM)-based wireless networks. We assume that the transmitters have different timing misalignments with respect to a typical receiver, which results in a loss of orthogonality between different OFDM sub-carriers. Moreover, the position of a used sub-carrier, within the available spectrum, is taken into consideration in order to make the analysis more precise. A frequency selective wireless channel is considered, in order to appropriately characterize the impact of misaligned multi-user interference on the coverage probability of a typical user. The analysis is conducted by using the mathematical tool of stochastic geometry and by considering a social interaction-based connectivity model. With the aid of the proposed analytical framework, the impact of the considered connectivity model is studied and discussed. The developed approach is validated via Monte Carlo simulations.
- 31 January 2019
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Wireless Communications Letters
- Vol. 8 (3) , 845-848
Stochastic Geometry Analysis of Multi-User Asynchronous OFDM Wireless Networks
This letter develops an analytical framework for the analysis of asynchronous orthogonal frequency division multiplexing (OFDM)-based wireless networks. We assume that the transmitters have different timing misalignments with respect to a typical receiver, which results in a loss of orthogonality between different OFDM sub-carriers. Moreover, the position of a used sub-carrier, within the available spectrum, is taken into consideration in order to make the analysis more precise. A frequency selective wireless channel is considered, in order to appropriately characterize the impact of misaligned multi-user interference on the coverage probability of a typical user. The analysis is conducted by using the mathematical tool of stochastic geometry and by considering a social interaction-based connectivity model. With the aid of the proposed analytical framework, the impact of the considered connectivity model is studied and discussed. The developed approach is validated via Monte Carlo simulations.
- 1 October 2018
- Published by Springer Nature in Lithuanian Mathematical Journal
- Vol. 58 (4) , 480-499
Semi-Heavy Tails
- 1 October 2018
- Published by Springer Nature in Lithuanian Mathematical Journal
- Vol. 58 (4) , 480-499
Semi-Heavy Tails
- Open Access
- 1 January 2018
- Published by National Library of Serbia in Publications de l'Institut Mathematique
- Vol. 104 (118) , 69-88
Approximations in bivariate renewal theory
We construct approximations to the renewal function for a bivariate renewal process. Suppose (X, Y ), (X1, Y1), (X2, Y2),... denote i.i.d. positive random vectors with common distribution function F(x, y) = P(X ≤ x, Y ≤ y). Let S(1)n = X1 + X2 + ... + Xn and S(2)n = Y1 + Y2 + ... + Yn denote the partial sums where we set S10 = S20 = 0. Associated with {(Xi, Yi)}, we define, respectively, the univariate and bivariate renewal counting processes: Ni(x) = min{n ≥ 1 : S(i)n > x} (i = 1, 2) and N(x,y) = min{N1(x),N2(y)}. The bivariate renewal function is given by U(x, y) = EN(x, y) = Σ∞0 F*n(x,y). From the practical point of view it is hard to find explicit expressions for the renewal function U(x, y). Recently, Mitov and Omey (2014) introduced a new method to obtain approximations for univariate renewal functions based on expansions of Laplace-Stieltjes transforms. In this paper we generalize these approximations to the bivariate case and apply them to regularly varying increments. We show that the approximation along the diagonal is different from off the diagonal.
- 1 January 2018
- Published by National Library of Serbia in Publications de l'Institut Mathematique
- Vol. 104 (118) , 69-88
Open AccessApproximations in bivariate renewal theory
We construct approximations to the renewal function for a bivariate renewal process. Suppose (X, Y ), (X1, Y1), (X2, Y2),... denote i.i.d. positive random vectors with common distribution function F(x, y) = P(X ≤ x, Y ≤ y). Let S(1)n = X1 + X2 + ... + Xn and S(2)n = Y1 + Y2 + ... + Yn denote the partial sums where we set S10 = S20 = 0. Associated with {(Xi, Yi)}, we define, respectively, the univariate and bivariate renewal counting processes: Ni(x) = min{n ≥ 1 : S(i)n > x} (i = 1, 2) and N(x,y) = min{N1(x),N2(y)}. The bivariate renewal function is given by U(x, y) = EN(x, y) = Σ∞0 F*n(x,y). From the practical point of view it is hard to find explicit expressions for the renewal function U(x, y). Recently, Mitov and Omey (2014) introduced a new method to obtain approximations for univariate renewal functions based on expansions of Laplace-Stieltjes transforms. In this paper we generalize these approximations to the bivariate case and apply them to regularly varying increments. We show that the approximation along the diagonal is different from off the diagonal.
- Open Access
An Event-Triggered Machine Learning Approach for Accelerometer-Based Fall Detection
The fixed-size non-overlapping sliding window (FNSW) and fixed-size overlapping sliding window (FOSW) approaches are the most commonly used data-segmentation techniques in machine learning-based fall detection using accelerometer sensors. However, these techniques do not segment by fall stages (pre-impact, impact, and post-impact) and thus useful information is lost, which may reduce the detection rate of the classifier. Aligning the segment with the fall stage is difficult, as the segment size varies. We propose an event-triggered machine learning (EvenT-ML) approach that aligns each fall stage so that the characteristic features of the fall stages are more easily recognized. To evaluate our approach, two publicly accessible datasets were used. Classification and regression tree (CART), k-nearest neighbor (k-NN), logistic regression (LR), and the support vector machine (SVM) were used to train the classifiers. EvenT-ML gives classifier F-scores of 98% for a chest-worn sensor and 92% for a waist-worn sensor, and significantly reduces the computational cost compared with the FNSW- and FOSW-based approaches, with reductions of up to 8-fold and 78-fold, respectively. EvenT-ML achieves a significantly better F-score than existing fall detection approaches. These results indicate that aligning feature segments with fall stages significantly increases the detection rate and reduces the computational cost.
Open AccessAn Event-Triggered Machine Learning Approach for Accelerometer-Based Fall Detection
The fixed-size non-overlapping sliding window (FNSW) and fixed-size overlapping sliding window (FOSW) approaches are the most commonly used data-segmentation techniques in machine learning-based fall detection using accelerometer sensors. However, these techniques do not segment by fall stages (pre-impact, impact, and post-impact) and thus useful information is lost, which may reduce the detection rate of the classifier. Aligning the segment with the fall stage is difficult, as the segment size varies. We propose an event-triggered machine learning (EvenT-ML) approach that aligns each fall stage so that the characteristic features of the fall stages are more easily recognized. To evaluate our approach, two publicly accessible datasets were used. Classification and regression tree (CART), k-nearest neighbor (k-NN), logistic regression (LR), and the support vector machine (SVM) were used to train the classifiers. EvenT-ML gives classifier F-scores of 98% for a chest-worn sensor and 92% for a waist-worn sensor, and significantly reduces the computational cost compared with the FNSW- and FOSW-based approaches, with reductions of up to 8-fold and 78-fold, respectively. EvenT-ML achieves a significantly better F-score than existing fall detection approaches. These results indicate that aligning feature segments with fall stages significantly increases the detection rate and reduces the computational cost.
- Open Access
- 5 June 2017
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Access
- Vol. 5, 10182-10192
Collaborative Spectrum Sharing Through Non-Collaborative Gaming for Next-Generation Small Cells
Existing spectrum-sharing schemes either allow the secondary-network users (SUs) to utilize the spectrum when primary-network users (PUs) remain idle, or require the SUs to coordinate with the PUs, causing signaling overhead. In this paper, we propose a game-theoretic spectrum-sharing scheme, which enables the SUs and PUs to utilize the spectrum simultaneously, without compromising the quality of service (QoS) of the PUs and ensuring reduced signaling overhead. We formulate a multi-priority non-cooperative power-control game by considering a scenario where multiple small cell base stations belonging to either the primary network or secondary network utilize the available spectrum resources at the same time. The base stations are empowered to adjust their transmit powers in an automated manner based on measured interference, until their transmit powers are stabilized. As a key idea, a game parameter, dynamic price coefficient, is designed to give the primary network priority over the secondary network for accessing the spectrum. We determine appropriate bounds for the game parameters to ensure the existence and uniqueness of the Nash equilibrium of the proposed game. Furthermore, we propose a novel dual-mode solution to reduce the real-time signaling overhead between the networks, by minimizing the information exchange during the game required to reach an equilibrium point. Extensive simulation results are presented to prove the convergence of the game to a Nash equilibrium, along with a throughput performance analysis.
- 5 June 2017
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Access
- Vol. 5, 10182-10192
Open AccessCollaborative Spectrum Sharing Through Non-Collaborative Gaming for Next-Generation Small Cells
Existing spectrum-sharing schemes either allow the secondary-network users (SUs) to utilize the spectrum when primary-network users (PUs) remain idle, or require the SUs to coordinate with the PUs, causing signaling overhead. In this paper, we propose a game-theoretic spectrum-sharing scheme, which enables the SUs and PUs to utilize the spectrum simultaneously, without compromising the quality of service (QoS) of the PUs and ensuring reduced signaling overhead. We formulate a multi-priority non-cooperative power-control game by considering a scenario where multiple small cell base stations belonging to either the primary network or secondary network utilize the available spectrum resources at the same time. The base stations are empowered to adjust their transmit powers in an automated manner based on measured interference, until their transmit powers are stabilized. As a key idea, a game parameter, dynamic price coefficient, is designed to give the primary network priority over the secondary network for accessing the spectrum. We determine appropriate bounds for the game parameters to ensure the existence and uniqueness of the Nash equilibrium of the proposed game. Furthermore, we propose a novel dual-mode solution to reduce the real-time signaling overhead between the networks, by minimizing the information exchange during the game required to reach an equilibrium point. Extensive simulation results are presented to prove the convergence of the game to a Nash equilibrium, along with a throughput performance analysis.