ACM SIGMETRICS Performance Evaluation Review

Journal Information
ISSN : 0163-5999
Total articles ≅ 3,236
Current Coverage

Latest articles in this journal

Leandros Tassiulas
ACM SIGMETRICS Performance Evaluation Review, Volume 49, pp 69-70;

The proliferation of novel mobile applications and the associated AI services necessitates a fresh view on the architecture, algorithms and services at the network edge in order to meet stringent performance requirements. Some recent work addressing these challenges is presented. In order to meet the requirement for low-latency, the execution of computing tasks moves form the cloud to the network edge, closer to the end-users. The joint optimization of service placement and request routing in dense mobile edge computing networks is considered. Multidimensional constraints are introduced to capture the storage requirements of the vast amounts of data needed. An algorithm that achieves close-to-optimal performance using a randomized rounding technique is presented. Recent advances in network virtualization and programmability enable realization of services as chains, where flows can be steered through a pre-defined sequence of functions deployed at different network locations. The optimal deployment of such service chains where storage is a stringent constraint in addition to computation and bandwidth is considered and an approximation algorithm with provable performance guarantees is proposed and evaluated. Finally the problem of traffic flow classification as it arises in firewalls and intrusion detection applications is presented. An approach for realizing such functions based on a novel two-stage deep learning method for attack detection is presented. Leveraging the high level of data plane programmability in modern network hardware, the realization of these mechanisms at the network edge is demonstrated.
Elene Anton, Urtzi Ayesta, Matthieu Jonckheere, Ina Maria Verloop
ACM SIGMETRICS Performance Evaluation Review, Volume 49, pp 55-56;

We analyze the performance of redundancy in a multi-type job and multi-type server system where PS is implemented. We characterize the stability condition, which coincides with that of a system where each job type only dispatches copies into its least-loaded servers, and those copies need to be fully served. We then investigate the impact of redundancy in the stability condition by comparing that to the stability condition of a non-redundant system in which a job arrival is routed to only one randomly selected compatible server. We observe that if server loads are sufficiently heterogeneous redundancy can considerably improve the stability region of the system.
Qingzhao Zhang, David Ke Hong, Ze Zhang, Qi Alfred Chen, Scott Mahlke, Z. Morley Mao
ACM SIGMETRICS Performance Evaluation Review, Volume 49, pp 43-44;

Safety compliance is paramount to the safe deployment of autonomous vehicle (AV) technologies in real-world transportation systems. As AVs will share road infrastructures with human drivers and pedestrians, it is an important requirement for AVs to obey standard driving rules. Existing AV software testing methods, including simulation and road testing, only check fundamental safety rules such as collision avoidance and safety distance. Scenario-dependent driving rules, including crosswalk and intersection rules, are more complicated because the expected driving behavior heavily depends on the surrounding circumstances. However, a testing framework is missing for checking scenario-dependent driving rules on various AV software. In this paper, we design and implement a systematic framework AVChecker for identifying violations of scenario-dependent driving rules in AV software using formal methods. AVChecker represents both the code logic of AV software and driving rules in proposed formal specifications and leverages satisfiability modulo theory (SMT) solvers to identify driving rule violations. To improve the automation of systematic rule-based checking, AVChecker provides a powerful user interface for writing driving rule specifications and applies static code analysis to extract rule-related code logic from the AV software codebase. Evaluations on two open-source AV software platforms, Baidu Apollo and Autoware, uncover 19 true violations out of 28 real-world driving rules covering crosswalks, traffic lights, stop signs, and intersections. Seven of the violations can lead to severe risks of a collision with pedestrians or blocking traffic.
Hsiao-Wuen Hon
ACM SIGMETRICS Performance Evaluation Review, Volume 49, pp 39-40;

In the past fifteen years, the most significant paradigm shift in the computing industry is the migration to cloud computing, which brings unprecedented opportunities of digital transformation to business, society, and human life. The implication of this is profound. It means that cloud computing platforms have become part of the basic infrastructure of the world. Therefore, the non-functional properties of cloud computing platforms, including availability, reliability, performance, efficiency, security, sustainability, etc., become immensely important. The distributed nature, massive scale, and high complexity of cloud computing platforms ranging from storage to networking, computing and beyond present huge challenges to achieve effective and efficient building and operation of such software systems. There is huge wealth of various types of data available throughout the entire development lifecycle of software systems. This is manifested even stronger with the paradigm shift to cloud computing as much more data are available on system runtime and workloads. Leveraging the amount of data, AI for System is to utilize AI/ML technologies to design and build high-quality cloud systems at scale. In this talk, I will first introduce the concept of AI for System and its research landscape. Then using a few projects at Microsoft as examples [1-10], I will talk about the work from Microsoft Research on AI for System and its impact. I will also discuss the research challenges and opportunities in AI for System moving forward.
Noémie Périvier, Chamsi Hssaine, Samitha Samaranayake, Siddhartha Banerjee
ACM SIGMETRICS Performance Evaluation Review, Volume 49, pp 73-74;

The advent of ride-hailing platforms such as Lyft and Uber has revolutionized urban mobility in the past decade. Given their increasingly important role in today's society, recent years have seen growing interest in integrating these services with mass transit options, in order to leverage the on-demand and flexible nature of the former, with the sustainability and cost-effectiveness of the latter. Our work explores a set of operational questions that are critical to the success of any such integrated marketplace: Given a set of trip requests, and the ability to utilize ride-hailing services, which mass-transit routes should the transit agency operate? How frequently should it operate each route? And how can ride-hailing trips be used to both help connect passengers to these routes, and also cover trips which are not efficiently served by mass transit? We study these under a model in which a Mobility-on-Demand provider (the platform ) has control of a vehicle fleet comprising both single-occupancy and high-capacity vehicles (e.g., cars and buses, respectively). The platform is faced with a number of trip requests to fill during a short time window, and can service these trip requests via different trip options : it can dispatch a car to transport the passenger from source to destination; it can use a car for the first and last legs of the trip, and have the passenger travel by bus in between; or it can use more complicated trips comprising of multiple car and bus legs. Given a set of rewards for matching passengers to trip options, and costs for operating each line (i.e., a bus route and associated frequency), the goal of the platform is to determine the optimal set of lines to operate (given a fixed budget for opening lines), as well as the assignment of passengers to trip options utilizing these lines, in order to maximize the total reward. We refer to this as the Real-Time Line Planning Problem (RLpp). We first demonstrate the computational limits of RLpp by showing that no constant-factor approximation is possible if we relax either one of two assumptions: (i) access to a pre-specified set of feasible lines, and (ii) no bus-to-bus transfers. These assumptions are practically motivated and common in the literature, but our work is the first to formally demonstrate their necessity.
Bo Sun, Ali Zeynali, Tongxin Li, Mohammad Hajiesmaili, Adam Wierman, Danny H.K. Tsang
ACM SIGMETRICS Performance Evaluation Review, Volume 49, pp 67-68;

We introduce and study a general version of the fractional online knapsack problem with multiple knapsacks, heterogeneous constraints on which items can be assigned to which knapsack, and rate-limiting constraints on the assignment of items to knapsacks. This problem generalizes variations of the knapsack problem and of the one-way trading problem that have previously been treated separately, and additionally finds application to the real-time control of electric vehicle (EV) charging. We introduce a new algorithm that achieves a competitive ratio within an additive factor of the best achievable competitive ratios for the general problem and matches or improves upon the best-known competitive ratio for special cases in the knapsack and one-way trading literatures. Moreover, our analysis provides a novel approach to online algorithm design based on an instance-dependent primal-dual analysis that connects the identification of worst-case instances to the design of algorithms. Finally, in the full version of this paper, we illustrate the proposed algorithm via trace-based experiments of EV charging.
Ahmad Hazimeh, Adrian Herrera, Mathias Payer
ACM SIGMETRICS Performance Evaluation Review, Volume 49, pp 81-82;

High scalability and low running costs have made fuzz testing the de facto standard for discovering software bugs. Fuzzing techniques are constantly being improved in a race to build the ultimate bug-finding tool. However, while fuzzing excels at finding bugs in the wild, evaluating and comparing fuzzer performance is challenging due to the lack of metrics and benchmarks. For example, crash count---perhaps the most commonly-used performance metric---is inaccurate due to imperfections in deduplication techniques. Additionally, the lack of a unified set of targets results in ad hoc evaluations that hinder fair comparison. We tackle these problems by developing Magma, a ground-truth fuzzing benchmark that enables uniform fuzzer evaluation and comparison. By introducing real bugs into real software, Magma allows for the realistic evaluation of fuzzers against a broad set of targets. By instrumenting these bugs, Magma also enables the collection of bug-centric performance metrics independent of the fuzzer. Magma is an open benchmark consisting of seven targets that perform a variety of input manipulations and complex computations, presenting a challenge to state-of-the-art fuzzers. We evaluate seven widely-used mutation-based fuzzers (AFL, AFLFast, AFL++, FairFuzz, MOpt-AFL, honggfuzz, and SymCC-AFL) against Magma over 200,000 CPU-hours. Based on the number of bugs reached, triggered, and detected, we draw conclusions about the fuzzers' exploration and detection capabilities. This provides insight into fuzzer performance evaluation, highlighting the importance of ground truth in performing more accurate and meaningful evaluations.
Jing Tang, Xueyan Tang, Andrew Lim, Kai Han, Chongshou Li, Junsong Yuan
ACM SIGMETRICS Performance Evaluation Review, Volume 49, pp 63-64;

Monotone submodular maximization with a knapsack constraint is NP-hard. Various approximation algorithms have been devised to address this optimization problem. In this paper, we revisit the widely known modified greedy algorithm. First, we show that this algorithm can achieve an approximation factor of 0.405, which significantly improves the known factors of 0.357 given by Wolsey and (1-1/e)/2-0.316 given by Khuller et al. More importantly, our analysis closes a gap in Khuller et al.'s proof for the extensively mentioned approximation factor of (1-1/√e)≈0.393 in the literature to clarify a long-standing misconception on this issue. Second, we enhance the modified greedy algorithm to derive a data-dependent upper bound on the optimum, which enables us to obtain a data-dependent ratio typically much higher than 0.405 between the solution value of the modified greedy algorithm and the optimum. It can also be used to significantly improve the efficiency of algorithms such as branch and bound.
Kamiar Asgari, Michael J. Neely
ACM SIGMETRICS Performance Evaluation Review, Volume 49, pp 75-76;

This paper considers online convex optimization (OCO) problems where decisions are constrained by available energy resources. A key scenario is optimal power control for an energy harvesting device with a finite capacity battery. The goal is to minimize a time-average loss function while keeping the used energy less than what is available. In this setup, the distribution of the randomly arriving harvestable energy (which is assumed to be i.i.d.) is unknown, the current loss function is unknown, and the controller is only informed by the history of past observations. A prior algorithm is known to achieve O(√T) regret by using a battery with an O(√T) capacity. This paper develops a new algorithm that maintains this asymptotic trade-off with the number of time steps T while improving dependency on the dimension of the decision vector from O(√n) to O(√log(n)). The proposed algorithm introduces a separation of the decision vector into amplitude and direction components. It uses two distinct types of Bregman divergence, together with energy queue information, to make decisions for each component.
Grzegorz Kielanski, Benny Van Houdt
ACM SIGMETRICS Performance Evaluation Review, Volume 49, pp 29-30;

The supermarket model is a popular load balancing model where each incoming job is assigned to a server with the least number of jobs among d randomly selected servers. Several authors have shown that the large scale limit in case of processor sharing servers has a unique insensitive fixed point, which naturally leads to the belief that the queue length distribution in such a system is insensitive to the job size distribution as the number of servers tends to infinity. Simulation results that support this belief have also been reported. However, global attraction of the unique fixed point of the large scale limit was not proven except for exponential job sizes, which is needed to formally prove asymptotic insensitivity. The difficulty lies in the fact that with processor sharing servers, the limiting system is in general not monotone. In this paper we focus on the class of hyperexponential distributions of order $2$ and demonstrate that for this class of distributions global attraction of the unique fixed point can still be established using monotonicity by picking a suitable state space and partial order. This allows us to formally show that we have asymptotic insensitivity within this class of job size distributions. We further demonstrate that our result can be leveraged to prove asymptotic insensitivity within this class of distributions for other load balancing systems.
Back to Top Top