Source author record

Azer Bestavros

Azer Bestavros appears in the imported research catalog. Authorship, coauthor and topic links are available while profile ownership is still unclaimed.

ResearcherUnclaimed source record

Data Structures and Algorithms Databases Distributed, Parallel, and Cluster Computing Formal Languages and Automata Theory Logic in Computer Science Networking and Internet Architecture Operating Systems Programming Languages Software Engineering

Catalog footprint

What is connected

5works

9topics

4close collaborators

Actions

Connect this record

Open graph Browse works

Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.

preprint2020arXiv

Akita: A CPU scheduler for virtualized Clouds

Clouds inherit CPU scheduling policies of operating systems. These policies enforce fairness while leveraging best-effort mechanisms to enhance responsiveness of all schedulable entities, irrespective of their service level objectives (SLOs). This leads to unpredictable performance that forces cloud providers to enforce strict reservation and isolation policies to prevent high-criticality services (e.g., Memcached) from being impacted by low-criticality ones (e.g., logging), which results in low utilization. In this paper, we present Akita, a hypervisor CPU scheduler that delivers predictable performance at high utilization. Akita allows virtual machines (VMs) to be categorized into high- and low-criticality VMs. Akita provides strong guarantees on the ability of cloud providers to meet SLOs of high-criticality VMs, by temporarily slowing down low-criticality VMs if necessary. Akita, therefore, allows the co-existence of high and low-criticality VMs on the same physical machine, leading to higher utilization. The effectiveness of Akita is demonstrated by a prototype implementation in the Xen hypervisor. We present experimental results that show the many advantages of adopting Akita as the hypervisor CPU scheduler. In particular, we show that high-criticality Memcached VMs are able to deliver predictable performance despite being co-located with low-criticality CPU-bound VMs.

preprint2016arXiv

Using Alloy to Formally Model and Reason About an OpenFlow Network Switch

Openflow provides a standard interface for separating a network into a data plane and a programmatic control plane. This enables easy network reconfiguration, but introduces the potential for programming bugs to cause network effects. To study OpenFlow switch behavior, we used Alloy to create a software abstraction describing the internal state of a network and its OpenFlow switches. This work is an attempt to model the static and dynamic behaviour a network built using OpenFlow switches.

preprint2015arXiv

A Divide-and-Conquer Algorithm for Betweenness Centrality

The problem of efficiently computing the betweenness centrality of nodes has been researched extensively. To date, the best known exact and centralized algorithm for this task is an algorithm proposed in 2001 by Brandes. The contribution of our paper is Brandes++, an algorithm for exact efficient computation of betweenness centrality. The crux of our algorithm is that we create a sketch of the graph, that we call the skeleton, by replacing subgraphs with simpler graph structures. Depending on the underlying graph structure, using this skeleton and by keeping appropriate summaries Brandes++ we can achieve significantly low running times in our computations. Extensive experimental evaluation on real life datasets demonstrate the efficacy of our algorithm for different types of graphs. We release our code for benefit of the research community.

preprint2012arXiv

The Filter-Placement Problem and its Application to Minimizing Information Multiplicity

In many information networks, data items -- such as updates in social networks, news flowing through interconnected RSS feeds and blogs, measurements in sensor networks, route updates in ad-hoc networks -- propagate in an uncoordinated manner: nodes often relay information they receive to neighbors, independent of whether or not these neighbors received the same information from other sources. This uncoordinated data dissemination may result in significant, yet unnecessary communication and processing overheads, ultimately reducing the utility of information networks. To alleviate the negative impacts of this information multiplicity phenomenon, we propose that a subset of nodes (selected at key positions in the network) carry out additional information filtering functionality. Thus, nodes are responsible for the removal (or significant reduction) of the redundant data items relayed through them. We refer to such nodes as filters. We formally define the Filter Placement problem as a combinatorial optimization problem, and study its computational complexity for different types of graphs. We also present polynomial-time approximation algorithms and scalable heuristics for the problem. Our experimental results, which we obtained through extensive simulations on synthetic and real-world information flow networks, suggest that in many settings a relatively small number of filters are fairly effective in removing a large fraction of redundant information.

preprint2011arXiv

A Domain-Specific Language for Incremental and Modular Design of Large-Scale Verifiably-Safe Flow Networks (Preliminary Report)

We define a domain-specific language (DSL) to inductively assemble flow networks from small networks or modules to produce arbitrarily large ones, with interchangeable functionally-equivalent parts. Our small networks or modules are "small" only as the building blocks in this inductive definition (there is no limit on their size). Associated with our DSL is a type theory, a system of formal annotations to express desirable properties of flow networks together with rules that enforce them as invariants across their interfaces, i.e, the rules guarantee the properties are preserved as we build larger networks from smaller ones. A prerequisite for a type theory is a formal semantics, i.e, a rigorous definition of the entities that qualify as feasible flows through the networks, possibly restricted to satisfy additional efficiency or safety requirements. This can be carried out in one of two ways, as a denotational semantics or as an operational (or reduction) semantics; we choose the first in preference to the second, partly to avoid exponential-growth rewriting in the operational approach. We set up a typing system and prove its soundness for our DSL.