publications

2026

1. NSDI

   Latency-Aware Caching with Delayed Hits: From Bursty Traffic to Pipeline Architectures

   N. Keren, G. Einziger, and G. Scalosub

   In Proceedings of the 23rd USENIX Symposium on Networked Systems Design and Implementation (NSDI), 2026

   Abs Bib

   Modern computing systems rely on caching to reduce access latency and optimize resource utilization. However, in heterogeneous storage and cloud environments, non-uniform access latencies across storage tiers, network locations, and intermediary caches undermine traditional caching. Moreover, modern cache algorithms that attempt to capture multiple access patterns, recency, frequency, and burstiness, often become complex and difficult to maintain. As a key contribution, we propose an adaptive caching architecture that treats caching strategies as a pipeline of simple, orthogonal policies, each focused on a distinct access bias. This modular design is easier to expand, debug, and integrate, and it self-adjusts the memory resources allocated to each stage to optimize overall workload performance. New heuristics can be introduced dynamically without disrupting existing behaviors. In addition, in latency-aware caching, one often encounters the phenomenon of delayed hits, where items not yet available in the cache are requested repeatedly. We introduce the Least Bursty Used (LBU) heuristic, which retains items exhibiting high burstiness even when they are neither recent nor frequent, thereby mitigating delayed hits that degrade request latency. We embed LBU within our pipeline and derive the Recency-Frequency-Burstiness (RFB) policy, which balances resources among recency, frequency, and burstiness. Evaluations on thirteen real-world storage traces from IBM, Twitter and Meta using latencies drawn from real-life deployments show that RFB reduces average request latency by 10% compared to the best state-of-the-art alternative, while maintaining consistent performance, with a low standard deviation across bursty and non-bursty workloads.

   @inproceedings{keren2026latency,
     themes = {caching},
     title = {Latency-Aware Caching with Delayed Hits: From Bursty Traffic to Pipeline Architectures},
     author = {Keren, N. and Einziger, G. and Scalosub, G.},
     booktitle = {Proceedings of the 23rd USENIX Symposium on Networked Systems Design and Implementation (NSDI)},
     pages = {2389--2405},
     year = {2026},
   }

2. uASC

   μ-ops, I Did it Again: A Second Look at Port Assignment on Intel CPUs (WiP)

   Y. Oziel, T. Laor, S. Levy, C. Maurice, Y. Oren, T. Rokicki, and G. Scalosub

   In Proceedings of the 2nd Microarchitecture Security Conference (uASC), 2026

   Abs Bib

   Modern Intel CPUs use a superscalar, out-of-order execution (OoOE) pipeline that maximizes instruction throughput through instruction-level parallelism (ILP). A critical component affecting system performance is the process in which μ-ops are mapped to execution ports, which lays at the core of the ability to perform OoOE. Significant effort has been undertaken in the attempt to reverse-engineer and model this process. Our work revisits this question from a security perspective, focusing on potential vulnerabilities stemming from μ-op port assignment and execution. Using carefully designed code gadgets, we expose behaviors that contradict state-of-the-art models. In this Work In Progress, we ask: Which undocumented behaviors in Intel’s port assignment algorithm affect instruction scheduling? By extending the micro-benchmarks used by Abel and Reineke, we identify corner cases that strongly deviates from the common case, where the CPU adopts at least three different port assignment strategies. These depend not only on the instruction and the microarchitectural generation, but, surprisingly, also on immediate operands.

   @inproceedings{oziel26uops,
     themes = {security},
     title = {$\mu$-ops, I Did it Again: A Second Look at Port Assignment on Intel CPUs (WiP)},
     author = {Oziel, Y. and Laor, T. and Levy, S. and Maurice, C. and Oren, Y. and Rokicki, T. and Scalosub, G.},
     booktitle = {Proceedings of the 2nd Microarchitecture Security Conference (uASC)},
     year = {2026},
   }

2025

1. NAIC

   T3P: Topology-Tailored Tensor Parallelism

   S. Ben-Yohana, C. Avin, and G. Scalosub

   In Proceedings of the 2nd Workshop on Networks for AI Computing (NAIC), 2025

   Abs Bib

   As deep learning models continue to grow in scale and complexity, methods of distributed machine learning training, and particularly those used for large language models (LLMs), have become a critical ingredient in making such computations efficient and feasible. In such contexts, tensor parallelism (TP) is widely employed to distribute computations across multiple accelerators. However, since TP mandates frequent and high-volume communication between devices, the underlying network characteristics significantly influence performance. Previous work was mostly either model-agnostic or topology-agnostic and did not pick provably optimal configurations. This study presents Topology-Tailored Tensor Parallelism, T3P, an efficient algorithm that identifies the communication-optimal TP sharding configuration (within the considered search space) based on both the model architecture and the network topology. In particular, we show that T3P is optimal for any given resharding cost model.

   @inproceedings{benyohana2025tttp,
     themes = {networking_ai},
     author = {Ben-Yohana, S. and Avin, C. and Scalosub, G.},
     title = {{T3P}: Topology-Tailored Tensor Parallelism},
     booktitle = {Proceedings of the 2nd Workshop on Networks for AI Computing (NAIC)},
     pages = {81--88},
     year = {2025},
   }

2024

1. TNSM

   SOAR: minimizing network utilization with bounded in-network computing

   R. Segal, C. Avin, and G. Scalosub

   IEEE Transactions on Network and Service Management, 2024

   Abs Bib

   In-network computing via smart networking devices is a recent trend in modern datacenter networks. State-of-the-art switches with near line-rate computing and aggregation capabilities enable acceleration and improved resource utilization for modern applications like large-scale distributed and federated machine learning, as well as big data analytics. We study the problem of activating a \em limited number of in-network computing devices within a network, aiming at reducing the overall cost incurred by such a deployment. Such limitations on the number of in-network computing elements arise, e.g., in incremental upgrades of network infrastructure, and are also due to requiring specialized middleboxes, or FPGAs, for supporting heterogeneous workloads, and multiple tenants. We present an efficient optimal algorithm for placing such devices in tree networks with arbitrary link rates, and further evaluate its performance in various scenarios and for various tasks, including federated/distributed ML and big data analytics. Our results show that even a small fraction of network devices supporting in-network aggregation leads to a significant reduction in network utilization cost. Furthermore, we show that various intuitive strategies for performing such placements are significantly inferior compared with our solution, for varying workloads, tasks, and link rates.

   @article{segal2024soar,
     themes = {networking_ai},
     title = {SOAR: minimizing network utilization with bounded in-network computing},
     author = {Segal, R. and Avin, C. and Scalosub, G.},
     journal = {IEEE Transactions on Network and Service Management},
     volume = {21},
     number = {2},
     pages = {1832--1851},
     year = {2024},
   }

2023

1. SIGMETRICS

   Go-to-Controller is Better: Efficient and Optimal LPM Caching with Splicing

   I. Gozlan, C. Avin, G. Einziger, and G. Scalosub

   Proceedings of the ACM on Measurement and Analysis of Computing Systems (POMACS), 2023

   Abs Bib

   Data center networks must support huge forwarding policies as they handle the traffic of the various tenants. Since such policies cannot be stored within the limited memory available at commodity switches, SDN controllers can manage the memory available at the switch as a cache, updating and changing the forwarding rules in the cache according to the policy and workloads dynamics. Most policies, such as Longest-prefix-match (LPM) policies, include dependencies between the forwarding rules, which introduce consistency constraints on the structure of the cached content, affecting the performance in terms of throughput and delay. Previous work suggested the concept of splicing to address such deficiencies, where modified Go-to-Controller rules can be inserted into the cache to improve performance while maintaining consistency. We present the first optimal algorithm for determining the cache content with splicing, as well as several efficient heuristics with some performance guarantees. We evaluate our solutions using traces derived from real systems and traffic, and show that splicing can reduce the cache miss ratio by as much as 30%, without increasing the cache size. We further propose a new metric which can provide a quick estimate as to the potential benefits of splicing compared to classical LPM-caching.

   @article{gozlan2023goto,
     themes = {caching},
     title = {Go-to-Controller is Better: Efficient and Optimal LPM Caching with Splicing},
     author = {Gozlan, I. and Avin, C. and Einziger, G. and Scalosub, G.},
     journal = {Proceedings of the ACM on Measurement and Analysis of Computing Systems (POMACS)},
     volume = {7},
     number = {1},
     pages = {10:1--10:33},
     year = {2023},
   }

2. ToN

   Dynamic Service Provisioning in the Edge-cloud Continuum with Bounded Resources

   I. Cohen, C.-F. Chiasserini, P. Giaccone, and G. Scalosub

   IEEE/ACM Transactions on Networking, 2023

   Abs Bib

   We consider a hierarchical edge-cloud architecture in which services are provided to mobile users as chains of virtual network functions. Each service has specific computation requirements and target delay performance, which require placing the corresponding chain properly and allocating a suitable amount of computing resources. Furthermore, chain migration may be necessary to meet the services’ target delay. We model and formalize the problem of finding a feasible chain placement and resource allocation, while minimizing the migration, bandwidth, and computation costs. We tackle this problem by partitioning it into a (i) CPU allocation problem, and a (ii) placement problem. For the CPU allocation problem, we find an optimal solution. For the placement problem, we show that even finding a feasible solution is NP-hard, and envision an algorithm that is guaranteed to find a feasible solution while leveraging a bounded amount of resource augmentation. Our algorithms are incorporated into a solution framework that aims to minimize both the cost and the required resource augmentation. The results, obtained through trace-driven, large-scale simulations, show that our framework can provide a close-to-optimal solution while running several orders of magnitude faster than an ILP solver.

   @article{cohen2023dynamic,
     themes = {edge_cloud},
     title = {Dynamic Service Provisioning in the Edge-cloud Continuum with Bounded Resources},
     author = {Cohen, I. and Chiasserini, C.-F. and Giaccone, P. and Scalosub, G.},
     journal = {IEEE/ACM Transactions on Networking},
     volume = {31},
     number = {6},
     pages = {3096--3111},
     year = {2023},
   }

3. TNSM

   High Throughput VMs Placement with Constrained Communication Overhead and Provable Guarantees

   I. Cohen, G. Einziger, M. Goldstein, Y. Sa’ar, G. Scalosub, and E. Waisbard

   IEEE Transactions on Network and Service Management, 2023

   Abs Bib

   Placement of VMs in the cloud is one of the most fundamental problems in systems research. Traditionally, placement algorithms assume that the schedulers have complete information about the currently available resources at each host. However, this assumption is in many cases unrealistic, as gathering fresh status information from each of the thousands of hosts in a large data center incurs excessive communication overhead, which results in long queueing delays. Efforts to resolve this problem by employing several parallel schedulers typically exhibit collisions when several schedulers are simultaneously trying to place VMs on the same host. Our work analyzes the performance of various placement algorithms and provides empirical evidence that using multiple randomized schedulers obtains high throughput, while significantly decreasing both the communication overhead, and the number of collisions between schedulers. We, therefore, introduce Adaptive Partial State Random (APSR) – an efficient parallel random resource management algorithm that samples only from a small number of hosts and dynamically adjusts the degree of parallelism to provide provable guarantees on the probability of collisions between distinct schedulers. We formally analyze APSR, evaluate it on real workloads, and integrate it into the popular OpenStack cloud management platform. Our evaluation shows that APSR matches the throughput provided by other parallel schedulers, while achieving up to 13x lower decline ratio and a reduction of over 85% in communication overheads.

   @article{cohen2023highthroughput,
     themes = {edge_cloud},
     title = {High Throughput VMs Placement with Constrained Communication Overhead and Provable Guarantees},
     author = {Cohen, I. and Einziger, G. and Goldstein, M. and Sa'ar, Y. and Scalosub, G. and Waisbard, E.},
     journal = {IEEE Transactions on Network and Service Management},
     volume = {20},
     number = {3},
     pages = {3148--3161},
     year = {2023}
   }

4. TCC

   Virtual Service Embedding with Time-Varying Load and Provable Guarantees

   C.-F. Chiasserini, G. Einziger, F. Malandrino, and G. Scalosub

   IEEE Transactions on Cloud Computing, 2023

   Abs Bib

   Deploying services efficiently while satisfying their quality requirements is a major challenge in network slicing. Effective solutions place instances of the services’ virtual network functions (VNFs) at different locations of the cellular infrastructure and manage such instances by scaling them as needed. In this work, we address the above problem and the very relevant aspect of sub-slice reuse among different services. Further, unlike prior art, we account for the services’ finite lifetime and time-varying traffic load. We identify two major sources of inefficiency in service management: (i) the overspending of computing resources due to traffic of multiple services with different latency requirements being processed by the same virtual machine (VM), and (ii) the poor packing of traffic processing requests in the same VM, leading to opening more VMs than necessary. To cope with the above issues, we devise an algorithm, called REShare, that can dynamically adapt to the system’s operational conditions and find an optimal trade-off between the aforementioned opposite requirements. We prove that REShare has low algorithmic complexity and is asymptotic 2-competitive under a non-decreasing load. Numerical results, leveraging real-world scenarios, show that our solution outperforms alternatives, swiftly adapting to time-varying conditions and reducing service cost by over 25%.

   @article{chiasserini2023virtual,
     themes = {edge_cloud},
     title = {Virtual Service Embedding with Time-Varying Load and Provable Guarantees},
     author = {Chiasserini, C.-F. and Einziger, G. and Malandrino, F. and Scalosub, G.},
     journal = {IEEE Transactions on Cloud Computing},
     volume = {11},
     number = {3},
     pages = {2693--2710},
     year = {2023}
   }

5. SYSTOR

   On Latency Awareness with Delayed Hits (Poster)

   N. Keren, G. Einziger, and G. Scalosub

   In Proceedings of the 16th ACM International Conference on Systems and Storage (SYSTOR), 2023

   Abs Bib

   We consider a new locality pattern in the form of burstiness to improve cache effectiveness in workflows where items are requested in possibly infrequent yet costly batches. Adding a cache that handles only bursty items to existing State-Of-The-Art algorithms shows a significant improvement in overall average time per query.

   @inproceedings{keren2023latency,
     themes = {caching},
     title = {On Latency Awareness with Delayed Hits (Poster)},
     author = {Keren, N. and Einziger, G. and Scalosub, G.},
     booktitle = {Proceedings of the 16th ACM International Conference on Systems and Storage (SYSTOR)},
     pages = {144},
     year = {2023}
   }

2022

1. ToN

   False Negative Awareness in Indicator-Based Caching Systems

   I. Cohen, G. Einziger, and G. Scalosub

   IEEE/ACM Transactions on Networking, 2022

   Abs Bib

   Distributed caching systems such as content distribution networks often advertise their content via lightweight approximate indicators (e.g., Bloom filters) to efficiently inform clients where each datum is likely cached. While false-positive indications are necessary and well understood, most existing works assume no false-negative indications. Our work illustrates practical scenarios where false-negatives are unavoidable and ignoring them significantly impacts system performance. Specifically, we focus on false-negatives induced by indicator staleness, which arises whenever the system advertises the indicator only periodically, rather than immediately reporting every change in the cache. Such scenarios naturally occur, e.g., in bandwidth-constraint environments or when latency impedes each client’s ability to obtain an updated indicator. Our work introduces novel false-negative aware access policies that continuously estimate the false-negative ratio and sometimes access caches despite negative indications. We present optimal policies for homogeneous settings and provide approximation guarantees for our algorithms in heterogeneous environments. We further perform an extensive simulation study with multiple real system traces. We show that our false-negative aware algorithms incur a significantly lower service cost than existing approaches or match the cost of these approaches while requiring an order of magnitude fewer resources (e.g., caching capacity or bandwidth).

   @article{cohen2022falsenegative,
     themes = {caching},
     title = {False Negative Awareness in Indicator-Based Caching Systems},
     author = {Cohen, I. and Einziger, G. and Scalosub, G.},
     journal = {IEEE/ACM Transactions on Networking},
     volume = {30},
     number = {6},
     pages = {2674--2687},
     year = {2022},
   }

2. CompCommun

   Bounded Delay Scheduling with Packet Dependencies

   M. Markovitch and G. Scalosub

   Computer Communications, 2022

   Abs Bib

   A common situation occurring when dealing with multimedia traffic is having large data frames fragmented into smaller IP packets, and having these packets sent independently through the network. For real-time multimedia traffic, dropping even few packets of a frame may render the entire frame useless. Such traffic is usually modeled as having inter-packet dependencies. We study the problem of scheduling traffic with such dependencies, where each packet has a deadline by which it should arrive at its destination. Such deadlines are common for real-time multimedia applications, and are derived from stringent delay constraints posed by the application. The figure of merit in such environments is maximizing the system’s goodput, namely, the number of frames successfully delivered. We study online algorithms for the problem of maximizing goodput of delay-bounded traffic with inter-packet dependencies, and use competitive analysis to evaluate their performance. We present competitive algorithms for the problem, as well as matching lower bounds that are tight up to a constant factor. We further present the results of a simulation study which further validates our algorithmic approach and shows that insights arising from our analysis are indeed manifested in practice.

   @article{markovitch2022bounded,
     themes = {buffer_scheduling},
     title = {Bounded Delay Scheduling with Packet Dependencies},
     author = {Markovitch, M. and Scalosub, G.},
     journal = {Computer Communications},
     volume = {182},
     pages = {98--109},
     year = {2022}
   }

3. INFOCOM

   Constrained In-network Computing with Low Congestion in Datacenter Networks

   R. Segal, C. Avin, and G. Scalosub

   In Proceedings of IEEE INFOCOM 2022, the 41st Annual Joint Conference of the IEEE Computer and Communications Societies, 2022

   Abs Bib

   Distributed computing has become a common practice nowadays, where recent focus has been given to the usage of smart networking devices with in-network computing capabilities. State-of-the-art switches with near-line rate computing and aggregation capabilities enable acceleration and improved performance for various modern applications like big data analytics and large-scale distributed and federated machine learning. In this work, we formulate and study the theoretical algorithmic foundations of such approaches, and focus on how to deploy and use constrained in-network computing capabilities within the data center. We focus our attention on reducing the network congestion, i.e., the most congested link in the network, while supporting the given workload(s). We present an efficient optimal algorithm for tree-like network topologies and show that our solution provides as much as an x13 improvement over common alternative approaches. In particular, our results show that having merely a small fraction of network devices that support in-network aggregation can significantly reduce the network congestion, both for single and multiple workloads.

   @inproceedings{segal2022constrained,
     themes = {networking_ai},
     title = {Constrained In-network Computing with Low Congestion in Datacenter Networks},
     author = {Segal, R. and Avin, C. and Scalosub, G.},
     booktitle = {Proceedings of IEEE INFOCOM 2022, the 41st Annual Joint Conference of the IEEE Computer and Communications Societies},
     pages = {1639--1648},
     year = {2022},
   }

2021

1. ToN

   Access Strategies for Network Caching

   I. Cohen, G. Einziger, R. Friedman, and G. Scalosub

   IEEE/ACM Transactions on Networking, 2021

   Abs Bib

   Having multiple data stores that can potentially serve content is common in modern networked applications. Data stores often publish approximate summaries of their content to enable effective utilization. Since these summaries are not entirely accurate, forming an efficient access strategy to multiple data stores becomes a complex risk management problem. This paper formally models this problem as a cost minimization problem, while taking into account both access costs, the inaccuracy of the approximate summaries, as well as the penalties incurred by failed requests. We introduce practical algorithms with guaranteed approximation ratios and further show that they are optimal in various settings. We also perform an extensive simulation study based on real data and show that our algorithms are more robust than existing heuristics. That is, they exhibit near-optimal performance in various settings, whereas the efficiency of existing approaches depends upon system parameters that may change over time, or be otherwise unknown.

   @article{cohen2021access,
     themes = {caching},
     title = {Access Strategies for Network Caching},
     author = {Cohen, I. and Einziger, G. and Friedman, R. and Scalosub, G.},
     journal = {IEEE/ACM Transactions on Networking},
     volume = {29},
     number = {2},
     pages = {609--622},
     year = {2021}
   }

2. CoNEXT

   SOAR: minimizing network utilization with bounded in-network computing

   R. Segal, C. Avin, and G. Scalosub

   In Proceedings of CoNEXT 2021, the 17th International Conference on emerging Networking EXperiments and Technologies, 2021

   Abs Bib

   In-network computing via smart networking devices is a recent trend for modern datacenter networks. State-of-the-art switches with near line rate computing and aggregation capabilities are developed to enable, e.g., acceleration and better utilization for modern applications like big data analytics, and large scale distributed and federated machine learning. We formulate and study the problem of activating a limited number of in-network computing devices within a network, aiming at reducing the overall network utilization for a given workload. Such limitations on the number of in-network computing elements per workload arise, e.g., in incremental upgrades of network infrastructure, and are also due to requiring specialized middleboxes, or FPGAs, that should support heterogeneous workloads, and multiple tenants. We present an optimal and efficient algorithm for placing such devices in tree networks with arbitrary link rates, and further evaluate our proposed solution in various scenarios and for various tasks. Our results show that having merely a small fraction of network devices support in-network aggregation can lead to a significant reduction in network utilization. Furthermore, we show that various intuitive strategies for performing such placements exhibit significantly inferior performance compared to our solution, for varying workloads, tasks, and link rates.

   @inproceedings{segal2021soar,
     themes = {networking_ai},
     title = {SOAR: minimizing network utilization with bounded in-network computing},
     author = {Segal, R. and Avin, C. and Scalosub, G.},
     booktitle = {Proceedings of CoNEXT 2021, the 17th International Conference on emerging Networking EXperiments and Technologies},
     pages = {16--29},
     year = {2021}
   }

3. IFIP Networking

   Parallel VM Deployment with Provable Guarantees

   I. Cohen, G. Einziger, M. Goldstein, Y. Sa’ar, G. Scalosub, and E. Waisbard

   In Proceedings of IFIP Networking 2021, the 20th International Federation for Information Processing (IFIP) Networking ConferencePoster appeared in IEEE INFOCOM 2020. , 2021

   Abs Bib

   Network Function Virtualization (NFV) carries the potential for on-demand deployment of network algorithms in virtual machines (VMs). In large clouds, however, VM resource allocation incurs delays that hinder the dynamic scaling of such NFV deployment. Parallel resource management is a promising direction for boosting performance, but it may significantly increase the communication overhead and the decline ratio of deployment attempts. Our work analyzes the performance of various placement algorithms and provides empirical evidence that state of the art parallel resource management dramatically increases the decline ratio of deterministic algorithms, but hardly affects randomized algorithms. We therefore introduce APSR – an efficient parallel random resource management algorithm that requires information only from a small number of hosts and dynamically adjusts the degree of parallelism to provide provable decline ratio guarantees. We formally analyze APSR, evaluate it on real workloads, and integrate it into the popular OpenStack cloud management platform. Our evaluation shows that APSR matches the throughput provided by other parallel schedulers, while achieving up to 13x lower decline ratio and a reduction of over 85% in communication overheads.

   @inproceedings{cohen2021parallel,
     themes = {edge_cloud},
     title = {Parallel VM Deployment with Provable Guarantees},
     author = {Cohen, I. and Einziger, G. and Goldstein, M. and Sa'ar, Y. and Scalosub, G. and Waisbard, E.},
     booktitle = {Proceedings of IFIP Networking 2021, the 20th International Federation for Information Processing (IFIP) Networking Conference},
     year = {2021},
   }

4. ICDCS

   On the Power of False Negative Awareness in Indicator-based Caching Systems

   I. Cohen, G. Einziger, and G. Scalosub

   In Proceedings of ICDCS 2021, the 41st IEEE International Conference on Distributed Computing Systems, 2021

   Abs Bib

   Distributed caching systems such as content distribution networks often advertise their content via lightweight approximate indicators (e.g., Bloom filters) to efficiently inform clients where each datum is likely cached. While false-positive indications are necessary and well understood, most existing works assume no false-negative indications. Our work illustrates practical scenarios where false-negatives are unavoidable and ignoring them has a significant impact on system performance. Specifically, we focus on false-negatives induced by indicator staleness, which arises whenever the system advertises the indicator only periodically, rather than immediately reporting every change in the cache. Such scenarios naturally occur, e.g., in bandwidth-constraint environments or when latency impedes each client’s ability to obtain an updated indicator. Our work introduces novel false-negative aware access policies that continuously estimate the false-negative ratio and sometimes access caches despite negative indications. We present optimal policies for homogeneous settings and provide approximation guarantees for our algorithms in heterogeneous environments. We further perform an extensive simulation study with multiple real system traces. We show that our false-negative aware algorithms incur a significantly lower access cost than existing approaches or match the cost of these approaches while requiring an order of magnitude fewer resources (e.g., caching capacity or bandwidth).

   @inproceedings{cohen2021power,
     themes = {caching},
     title = {On the Power of False Negative Awareness in Indicator-based Caching Systems},
     author = {Cohen, I. and Einziger, G. and Scalosub, G.},
     booktitle = {Proceedings of ICDCS 2021, the 41st IEEE International Conference on Distributed Computing Systems},
     pages = {46--56},
     year = {2021}
   }

5. INFOCOM

   Self-adjusting Advertisement of Cache Indicators with Bandwidth Constraints

   I. Cohen, G. Einziger, and G. Scalosub

   In Proceedings of IEEE INFOCOM 2021, the 40th Annual Joint Conference of the IEEE Computer and Communications SocietiesAlso appeared in the Highlights Track in SYSTOR 2021. , 2021

   Abs Bib

   Cache advertisements reduce the access cost by allowing users to skip the cache when it does not contain their datum. Such advertisements are used in multiple networked domains such as 5G networks, wide area networks, and information-centric networking. The selection of an advertisement strategy exposes a trade-off between the access cost and bandwidth consumption. Still, existing works mostly apply a trial-and-error approach for selecting the best strategy, as the rigorous foundations required for optimizing such decisions is lacking.Our work shows that the desired advertisement policy depends on numerous parameters such as the cache policy, the workload, the cache size, and the available bandwidth. In particular, we show that there is no ideal single configuration. Therefore, we design an adaptive, self-adjusting algorithm that periodically selects an advertisement policy. Our algorithm does not require any prior information about the cache policy, cache size, or work-load, and does not require any apriori configuration. Through extensive simulations, using several state-of-the-art cache policies, and real workloads, we show that our approach attains a similar cost to that of the best static configuration (which is only identified in retrospect) in each case.

   @inproceedings{cohen2021selfadjusting,
     themes = {caching},
     title = {Self-adjusting Advertisement of Cache Indicators with Bandwidth Constraints},
     author = {Cohen, I. and Einziger, G. and Scalosub, G.},
     booktitle = {Proceedings of IEEE INFOCOM 2021, the 40th Annual Joint Conference of the IEEE Computer and Communications Societies},
     year = {2021},
   }

2019

1. ToN

   Reducing Service Deployment Cost Through VNF Sharing

   F. Malandrino, C.-F. Chiasserini, G. Einziger, and G. Scalosub

   IEEE/ACM Transactions on Networking, 2019

   Abs Bib

   Thanks to its computational and forwarding capabilities, the mobile network infrastructure can support several third-party (“vertical”) services, each composed of a graph of virtual (network) functions (VNFs). Importantly, one or more VNFs are often common to multiple services, thus the services deployment cost could be reduced by letting the services share the same VNF instance instead of devoting a separate instance to each service. By doing that, however, it is critical that the target KPI (key performance indicators) of all services are met. To this end, we study the VNF sharing problem and make decisions on 1) when sharing VNFs among multiple services is possible, 2) how to adapt the virtual machines running the shared VNFs to the combined load of the assigned services, and 3) how to prioritize the services traffic within shared VNFs. All decisions aim to minimize the cost for the mobile operator, subject to requirements on end-to-end service performance, e.g., total delay. Notably, we show that the aforementioned priorities should be managed dynamically and vary across VNFs. We then propose the FlexShare algorithm to provide near-optimal VNF-sharing and priority assignment decisions in polynomial time. We prove that FlexShare is within a constant factor from the optimum and, using real-world VNF graphs, we show that it consistently outperforms baseline solutions.

   @article{malandrino2019reducing,
     themes = {edge_cloud},
     title = {Reducing Service Deployment Cost Through VNF Sharing},
     author = {Malandrino, F. and Chiasserini, C.-F. and Einziger, G. and Scalosub, G.},
     journal = {IEEE/ACM Transactions on Networking},
     volume = {27},
     number = {6},
     pages = {2363--2376},
     year = {2019}
   }

2. INFOCOM

   Access Strategies for Network Caching

   I. Cohen, G. Einziger, R. Friedman, and G. Scalosub

   In Proceedings of IEEE INFOCOM 2019, the 38th Annual Joint Conference of the IEEE Computer and Communications Societies, 2019

   Abs Bib PDF

   Having multiple data stores that can potentially serve content is common in modern networked applications. Data stores often publish approximate summaries of their content to enable effective utilization. Since these summaries are not entirely accurate, forming an efficient access strategy to multiple data stores becomes a complex risk management problem. This paper formally models this problem, and introduces practical algorithms with guaranteed approximation ratios, and in particular we show that our algorithms are optimal in a variety of settings. We also perform an extensive simulation study based on real data, and show that our algorithms are more robust than existing heuristics. That is, they exhibit near optimal performance in various settings whereas the efficiency of existing approaches depends upon system parameters that may change over time, or be otherwise unknown.

   @inproceedings{cohen2019access,
     themes = {caching},
     title = {Access Strategies for Network Caching},
     author = {Cohen, I. and Einziger, G. and Friedman, R. and Scalosub, G.},
     booktitle = {Proceedings of IEEE INFOCOM 2019, the 38th Annual Joint Conference of the IEEE Computer and Communications Societies},
     pages = {28--36},
     year = {2019},
   }

2018

1. CompNet

   Queueing in the Mist: Buffering and Scheduling with Limited Knowledge

   I. Cohen and G. Scalosub

   Computer Networks, 2018

   Abs Bib

   Scheduling and managing queues with bounded buffers are among the most fundamental problems in computer networking. Traditionally, it is often assumed that all the properties of each packet are known immediately upon arrival. However, as traffic becomes increasingly heterogeneous and complex, such assumptions are in many cases invalid. In particular, in various scenarios information about packet characteristics becomes available only after the packet has undergone some initial processing. In this work, we study the problem of managing queues with limited knowledge. We start by showing lower bounds on the competitive ratio of any algorithm in such settings. The techniques used in our proofs, which make use of a carefully crafted Markov process, may be of independent interest, and can potentially be used in other similar settings as well. Next, we use the insight obtained from these bounds to identify several algorithmic concepts appropriate for the problem, and use these guidelines to design a concrete algorithmic framework. We analyze the performance of our proposed algorithm, and further show how it can be implemented in various settings, which differ by the type and nature of the unknown information. We further validate our results and algorithmic approach by an extensive simulation study that provides further insights as to our algorithmic design principles in face of limited knowledge.

   @article{cohen2018queueing,
     themes = {buffer_scheduling},
     title = {Queueing in the Mist: Buffering and Scheduling with Limited Knowledge},
     author = {Cohen, I. and Scalosub, G.},
     journal = {Computer Networks},
     volume = {147},
     pages = {204--220},
     year = {2018}
   }

2017

1. CompNet

   Towards Optimal Buffer Management for Streams with Packet Dependencies

   G. Scalosub

   Computer Networks, 2017

   Abs Bib

   We study the problem of managing a FIFO queue where traffic is an interleaving of multiple streams that have inter-packet dependencies. This situation is common when dealing with multimedia streaming traffic, where large data frames are fragmented into smaller IP packets sent independently through the network. The main difficulty in such systems is to decide which packets to discard in case of overflow, where the system’s goal is to maximize the goodput, namely, the number of frames that are successfully delivered. Previous results for this problem in the presence of bounded buffers obtained a competitive ratio which was exponential in the number of packets each data frame is decomposed into. We show both randomized and deterministic algorithms with polynomial competitive ratio in all system parameters thus exhibiting an exponential improvement over the best previously known algorithm for the problem.

   @article{scalosub2017towards,
     title = {Towards Optimal Buffer Management for Streams with Packet Dependencies},
     author = {Scalosub, G.},
     journal = {Computer Networks},
     volume = {129},
     number = {1},
     pages = {207--214},
     year = {2017}
   }

2. IWQoS

   Queueing in the Mist: Buffering and Scheduling with Limited Knowledge

   I. Cohen and G. Scalosub

   In Proceedings of IWQoS 2017, the 25th IEEE/ACM International Symposium on Quality of Service, 2017

   Abs Bib PDF

   Scheduling and managing queues with bounded buffers are among the most fundamental problems in computer networking. Traditionally, it is often assumed that all the properties of each packet are known immediately upon arrival. However, as traffic becomes increasingly heterogeneous and complex, such assumptions are in many cases invalid. In particular, in various scenarios information about packet characteristics becomes available only after the packet has undergone some initial processing. In this work, we study the problem of managing queues with limited knowledge. We start by showing lower bounds on the competitive ratio of any algorithm in such settings. Next, we use the insight obtained from these bounds to identify several algorithmic concepts appropriate for the problem, and use these guidelines to design a concrete algorithmic framework. We analyze the performance of our proposed algorithm, and further show how it can be implemented in various settings, which differ by the type and nature of the unknown information. We further validate our results and algorithmic approach by a simulation study that provides further insights as to our algorithmic design principles in face of limited knowledge.

   @inproceedings{cohen2017queueing,
     title = {Queueing in the Mist: Buffering and Scheduling with Limited Knowledge},
     author = {Cohen, I. and Scalosub, G.},
     booktitle = {Proceedings of IWQoS 2017, the 25th IEEE/ACM International Symposium on Quality of Service},
     year = {2017},
   }

3. ESOCC

   MIKELANGELO: MIcro KErneL virtualizAtioN for hiGh pErfrmance cLOud and HPC Systems

   N. Struckmann, Y. Sandoval, N. Har’El, F. Chen, S. Fan, J. Cinkelj, G. Berginc, P. Chronz, N. Gilboa, G. Scalosub, K. Meth, and J. Kennedy

   In Proceedings of the 6th European Conference on Service-Oriented and Cloud Computing (ESOCC), 2017

   Abs Bib

   MIKELANGELO is a project, targeted to disrupt the core underlying technologies of Cloud computing, enabling even bigger uptake of Cloud computing, HPC in the Cloud and Big Data technologies under one umbrella. The vision of it is to improve responsiveness, agility and security of the virtual infrastructure through packaged applications, using lean guest operating system OSv and superfast hypervisor SuperKVM. In short, the work will concentrate on improvement of virtual I/O in KVM, using additional virtio expertise, integrated with the light-weight operating system OSv and with enhanced Security. The HPC in the Cloud focus will be provided through involvement of a large HPC centre, with the ability and business need to cloudify their HPC business. The Consortium consists of hand-picked experts (e.g., the original creator of KVM - Avi Kivity) who participate in the overall effort to reduce one of the last performance hurdles in the virtualisation (I/O). Other layers of inefficiency are addressed through OSv (thin operating system). Such approach will allow for use of MIKELANGELO stack on heterogeneous infrastructures, with high responsiveness, agility and improved security. The targeted audience are primarily SMEs (e.g. simulation dependent SMEs) and data center operators who either benefit from higher performance or flexibility, introduced by the software stack. Four real world use-cases with clear owners, serve as validators and also directly contribute to the exploitation of project results.

   @inproceedings{struckmann2017mikelangelo,
     title = {MIKELANGELO: MIcro KErneL virtualizAtioN for hiGh pErfrmance cLOud and HPC Systems},
     author = {Struckmann, N. and Sandoval, Y. and Har'El, N. and Chen, F. and Fan, S. and Cinkelj, J. and Berginc, G. and Chronz, P. and Gilboa, N. and Scalosub, G. and Meth, K. and Kennedy, J.},
     booktitle = {Proceedings of the 6th European Conference on Service-Oriented and Cloud Computing (ESOCC)},
     pages = {175--180},
     year = {2017}
   }

2016

1. JNCA

   Large Profits or Fast Gains: A Dilemma in Maximizing Throughput with Applications to Network Processors

   K. Kogan, A. Lopez-Ortiz, S. Nikolenko, G. Scalosub, and M. Segal

   Journal of Network and Computer Applications, 2016

   Abs Bib

   We consider the fundamental problem of managing a bounded size queue buffer where traffic consists of packets of varying size, each packet requires several rounds of processing before it can be transmitted out, and the goal is to maximize the throughput, i.e., total size of successfully transmitted packets. Our work addresses the tension between two conflicting algorithmic approaches: favoring packets with fewer processing requirements as opposed to packets of larger size. We present a novel model for studying such systems and study the performance of online algorithms that aim to maximize throughput.

   @article{kogan2016large,
     themes = {buffer_scheduling},
     title = {Large Profits or Fast Gains: A Dilemma in Maximizing Throughput with Applications to Network Processors},
     author = {Kogan, K. and Lopez-Ortiz, A. and Nikolenko, S. and Scalosub, G. and Segal, M.},
     journal = {Journal of Network and Computer Applications},
     volume = {74},
     pages = {31--43},
     year = {2016}
   }

2014

1. TMC

   On Quality of Monitoring for Multichannel Wireless Infrastructure Networks

   H. Nguyen, G. Scalosub, and R. Zheng

   IEEE Transactions on Mobile Computing, 2014

   Abs Bib

   Passive monitoring utilizing distributed wireless sniffers is an effective technique to monitor activities in wireless infrastructure networks for fault diagnosis, resource management, and critical path analysis. In this paper, we introduce a quality of monitoring (QoM) metric defined by the expected number of active users monitored, and investigate the problem of maximizing QoM by judiciously assigning sniffers to channels based on the knowledge of user activities in a multichannel wireless network. Two types of capture models are considered. The user-centric model assumes the frame-level capturing capability of sniffers such that the activities of different users can be distinguished while the sniffer-centric model only utilizes the binary channel information (active or not) at a sniffer. For the user-centric model, we show that the implied optimization problem is NP-hard, but a constant approximation ratio can be attained via polynomial complexity algorithms. For the sniffer-centric model, we devise stochastic inference schemes to transform the problem into the user-centric domain, where we are able to apply our polynomial approximation algorithms. The effectiveness of our proposed schemes and algorithms is further evaluated using both synthetic data as well as real-world traces from an operational WLAN.

   @article{nguyen2014quality,
     title = {On Quality of Monitoring for Multichannel Wireless Infrastructure Networks},
     author = {Nguyen, H. and Scalosub, G. and Zheng, R.},
     journal = {IEEE Transactions on Mobile Computing},
     volume = {13},
     number = {3},
     pages = {664--677},
     year = {2014}
   }

2. INFOCOM-WKSHP

   Bounded Delay Scheduling with Packet Dependencies

   M. Markovitch and G. Scalosub

   In Proceedings of the 1st IEEE INFOCOM 2014 Workshop on Communication and Networking Techniques for Contemporary Video, 2014

   Abs Bib PDF

   A common situation occurring when dealing with multimedia traffic is having large data frames fragmented into smaller IP packets, and having these packets sent independently through the network. For real-time multimedia traffic, dropping even few packets of a frame may render the entire frame useless. Such traffic is usually modeled as having inter-packet dependencies. We study the problem of scheduling traffic with such dependencies, where each packet has a deadline by which it should arrive at its destination. Such deadlines are common for real-time multimedia applications, and are derived from stringent delay constraints posed by the application. The figure of merit in such environments is maximizing the system’s goodput, namely, the number of frames successfully delivered. We study deterministic online algorithms for the problem of maximizing goodput of delay-bounded traffic with inter-packet dependencies, and use competitive analysis to evaluate performance. We present a competitive algorithm for the problem, as well as matching lower bounds that are tight up to a constant factor. We further present the results of a simulation study which further validates our algorithmic approach and shows that insights arising from our analysis are indeed manifested in practice.

   @inproceedings{markovitch2014bounded,
     title = {Bounded Delay Scheduling with Packet Dependencies},
     author = {Markovitch, M. and Scalosub, G.},
     booktitle = {Proceedings of the 1st IEEE INFOCOM 2014 Workshop on Communication and Networking Techniques for Contemporary Video},
     pages = {257--262},
     year = {2014},
   }

3. INFOCOM

   Cellular Multi-Coverage with Non-uniform Rates

   O. Gurewitz, Y. Sandomirsky, and G. Scalosub

   In Proceedings of IEEE INFOCOM 2014, the 33rd Annual Joint Conference of the IEEE Computer and Communications Societies, 2014

   Abs Bib PDF

   Recent advances in the standardization of 4G cellular networks introduce the notion of multi-coverage, where multiple base stations may collaboratively satisfy the demands of mobile users. We provide a theoretical model for studying such multi-coverage environments, in highly heterogeneous settings, where users demands and profits may vary, as can base stations’ capacities and the rates with which they can service the users. Whereas previous works provided solutions that were only applicable to scenarios where rates are uniform throughout the network, or allowed a mobile user to be serviced by at most one base station, we present several algorithms for the multi-coverage problem in the presence of non-uniform rates, and analyze their performance. We complete our study by a simulation study that further validates our results and provides further insight into algorithm design, depending on the users’ characteristics.

   @inproceedings{gurewitz2014cellular,
     title = {Cellular Multi-Coverage with Non-uniform Rates},
     author = {Gurewitz, O. and Sandomirsky, Y. and Scalosub, G.},
     booktitle = {Proceedings of IEEE INFOCOM 2014, the 33rd Annual Joint Conference of the IEEE Computer and Communications Societies},
     pages = {1330--1338},
     year = {2014},
   }

4. COMSNETS

   Balancing Work and Size with Bounded Buffers

   K. Kogan, A. Lopez-Ortiz, S. Nikolenko, G. Scalosub, and M. Segal

   In Proceedings of COMSNETS 2014, the 6th International Conference on Communication Systems and Networks, 2014

   Abs Bib PDF

   We consider the fundamental problem of managing a bounded size queue buffer where traffic consists of packets of varying size, each packet requires several rounds of processing before it can be transmitted out, and the goal is to maximize the throughput, i.e., total size of successfully transmitted packets. Our work addresses the tension between two conflicting algorithmic approaches: favoring packets with fewer processing requirements as opposed to packets of larger size. We present a novel model for studying such systems and study the performance of online algorithms that aim to maximize throughput.

   @inproceedings{kogan2014balancing,
     title = {Balancing Work and Size with Bounded Buffers},
     author = {Kogan, K. and Lopez-Ortiz, A. and Nikolenko, S. and Scalosub, G. and Segal, M.},
     booktitle = {Proceedings of COMSNETS 2014, the 6th International Conference on Communication Systems and Networks},
     year = {2014},
   }

2013

1. TMC

   Cell Selection in 4G Cellular Networks

   D. Amzallag, R. Bar-Yehuda, D. Raz, and G. Scalosub

   IEEE Transactions on Mobile Computing, 2013

   Abs Bib

   Cell selection is the process of determining the cell(s) that provide service to each mobile station. Optimizing these processes is an important step toward maximizing the utilization of current and future cellular networks. We study the potential benefit of global cell selection versus the current local mobile SNR-based decision protocol. In particular, we study the new possibility available in OFDMA-based systems, such as IEEE 802.16m and LTE-Advanced, of satisfying the minimal demand of a mobile station simultaneously by more than one base station. We formalize the problem as an optimization problem, and show that in the general case this problem is not only NP-hard but also cannot be approximated within any reasonable factor. In contrast, under the very practical assumption that the maximum required bandwidth of a single mobile station is at most an (r)-fraction of the capacity of a base station, we present two different algorithms for cell selection. The first algorithm produces a (1-r)-approximate solution, where a mobile station can be covered simultaneously by more than one base station. The second algorithm produces a \frac1-r2-r-approximate solution, while every mobile station is covered by at most one base station. We complete our study by an extensive simulation study demonstrating the benefits of using our algorithms in high-loaded capacity-constrained future 4G networks, compared to currently used methods. Specifically, our algorithms obtain up to 20 percent better usage of the network’s capacity, in comparison with the current cell selection algorithms.

   @article{amzallag2013cell,
     title = {Cell Selection in 4G Cellular Networks},
     author = {Amzallag, D. and Bar-Yehuda, R. and Raz, D. and Scalosub, G.},
     journal = {IEEE Transactions on Mobile Computing},
     volume = {12},
     number = {7},
     pages = {1443--1455},
     year = {2013}
   }

2. TCS

   Competitive Buffer Management with Packet Dependencies

   A. Kesselman, B. Patt-Shamir, and G. Scalosub

   Theoretical Computer Science, 2013

   Abs Bib

   We introduce the problem of managing a FIFO buffer of bounded space, where arriving packets have dependencies among them. Our model is motivated by the scenario where large data frames must be split into multiple packets, because maximum packet size is limited by data-link restrictions. A frame is considered useful only if sufficiently many of its constituent packets are delivered. The buffer management algorithm decides, in case of overflow, which packets to discard and which to keep in the buffer. The goal of the buffer management algorithm is to maximize throughput of useful frames. This problem has a variety of applications, e.g., Internet video streaming, where video frames are segmented and encapsulated in IP packets sent over the Internet. We study the complexity of the above problem in both the offline and online settings. We give upper and lower bounds on the performance of algorithms using competitive analysis.

   @article{kesselman2013competitive,
     themes = {buffer_scheduling},
     title = {Competitive Buffer Management with Packet Dependencies},
     author = {Kesselman, A. and Patt-Shamir, B. and Scalosub, G.},
     journal = {Theoretical Computer Science},
     volume = {489-490},
     pages = {75--87},
     year = {2013}
   }

3. TPDS

   Buffer Management for Aggregated Streaming Data with Packet Dependencies

   G. Scalosub, J. Liebeherr, and P. Marbach

   IEEE Transactions on Parallel and Distributed Systems, 2013

   Abs Bib

   In many applications, the traffic traversing the network has interpacket dependencies due to application-level encoding schemes. For some applications, e.g., multimedia streaming, dropping a single packet may render useless the delivery of a whole sequence. In such environments, the algorithm used to decide which packet to drop in case of buffer overflows must be carefully designed, to avoid goodput degradation. We present a model that captures such interpacket dependencies, and design algorithms for performing packet discard. Traffic consists of an aggregation of multiple streams, each of which consists of a sequence of interdependent packets. We provide two guidelines for designing buffer management algorithms, and demonstrate their effectiveness. We devise an algorithm according to these guidelines and evaluate its performance analytically, using competitive analysis. We also perform a simulation study that shows that the performance of our algorithm is within a small fraction of the performance of the best known offline algorithm.

   @article{scalosub2013buffer,
     themes = {buffer_scheduling},
     title = {Buffer Management for Aggregated Streaming Data with Packet Dependencies},
     author = {Scalosub, G. and Liebeherr, J. and Marbach, P.},
     journal = {IEEE Transactions on Parallel and Distributed Systems},
     volume = {24},
     number = {3},
     pages = {439--449},
     year = {2013}
   }

2012

1. ToN

   Providing Performance Guarantees in Multipass Network Processors

   I. Keslassy, K. Kogan, G. Scalosub, and M. Segal

   IEEE/ACM Transactions on Networking, 2012

   Abs Bib

   Current network processors (NPs) increasingly deal with packets with heterogeneous processing times. In such an environment, packets that require many processing cycles delay low-latency traffic because the common approach in today’s NPs is to employ run-to-completion processing. These difficulties have led to the emergence of the Multipass NP architecture, where after a processing cycle ends, all processed packets are recycled into the buffer and recompete for processing resources. In this paper, we provide a model that captures many of the characteristics of this architecture, and we consider several scheduling and buffer management algorithms that are specially designed to optimize the performance of multipass network processors. In particular, we provide analytical guarantees for the throughput performance of our algorithms. We further conduct a comprehensive simulation study, which validates our results.

   @article{keslassy2012providing,
     themes = {buffer_scheduling},
     title = {Providing Performance Guarantees in Multipass Network Processors},
     author = {Keslassy, I. and Kogan, K. and Scalosub, G. and Segal, M.},
     journal = {IEEE/ACM Transactions on Networking},
     volume = {20},
     number = {6},
     pages = {1895--1909},
     year = {2012},
   }

2. JPDC

   Distributed Approximation of Cellular Coverage

   B. Patt-Shamir, D. Rawitz, and G. Scalosub

   Journal of Parallel and Distributed Computing, 2012

   Abs Bib

   We consider the following model of cellular networks. Each base station has a given finite capacity, and each client has some demand and profit. A client can be covered by a specific subset of the base stations, and its profit is obtained only if its demand is provided in full. The goal is to assign clients to base stations, so that the overall profit is maximized subject to base station capacity constraints. In this work, we present a distributed algorithm for the problem, that runs in polylogarithmic time, and guarantees an approximation ratio close to the best known ratio achievable by a centralized algorithm.

   @article{pattshamir2012distributed,
     title = {Distributed Approximation of Cellular Coverage},
     author = {Patt-Shamir, B. and Rawitz, D. and Scalosub, G.},
     journal = {Journal of Parallel and Distributed Computing},
     volume = {72},
     number = {3},
     pages = {402--408},
     year = {2012}
   }

2011

1. ToA

   Rate vs. Buffer Size: Greedy Information Gathering on the Line

   A. Rosén and G. Scalosub

   ACM Transactions on Algorithms, 2011

   Abs Bib

   We consider packet networks with limited buffer space at the nodes, and are interested in the question of maximizing the number of packets that arrive to destination rather than being dropped due to full buffers. We initiate a more refined analysis of the throughput competitive ratio of admission and scheduling policies in the Competitive Network Throughput model [Aiello et al. 2005], taking into account not only the network size but also the buffer size and the injection rate of the traffic. We specifically consider the problem of information gathering on the line, with limited buffer space, under adversarial traffic. We examine how the buffer size and the injection rate of the traffic affect the performance of the greedy protocol for this problem. We establish upper bounds on the competitive ratio of the greedy protocol in terms of the network size, the buffer size, and the adversary’s rate, and present lower bounds which are tight up to constant factors. These results show, for example, that provisioning the network with sufficiently large buffers may substantially improve the performance of the greedy protocol in some cases, whereas for some high-rate adversaries, using larger buffers does not have any effect on the competitive ratio of the protocol.

   @article{rosen2011rate,
     themes = {buffer_scheduling},
     title = {Rate vs. Buffer Size: Greedy Information Gathering on the Line},
     author = {Rosén, A. and Scalosub, G.},
     journal = {ACM Transactions on Algorithms},
     volume = {7},
     number = {3},
     year = {2011}
   }

2. INFOCOM

   Providing Performance Guarantees in Multipass Network Processors

   I. Keslassy, K. Kogan, G. Scalosub, and M. Segal

   In Proceedings of IEEE INFOCOM 2011, the 30th Annual Joint Conference of the IEEE Computer and Communications Societies, 2011

   Abs Bib PDF Slides

   Current network processors (NPs) increasingly deal with packets with heterogeneous processing times. As a consequence, packets that require many processing cycles can significantly delay low-latency traffic, because the common approach in today’s NPs is to employ run-to-completion processing. These difficulties have led to the emergence of the Multipass NP architecture, where after a processing cycle ends, all processed packets are recycled into the buffer and re-compete for processing resources. In this work we provide a model that captures many of the characteristics of this architecture, and consider several scheduling and buffer management algorithms that are specially designed to optimize the performance of multipass network processors. In particular, we provide analytical guarantees for the throughput performance of our algorithms. We further conduct a comprehensive simulation study that validates our results.

   @inproceedings{keslassy2011providing,
     title = {Providing Performance Guarantees in Multipass Network Processors},
     author = {Keslassy, I. and Kogan, K. and Scalosub, G. and Segal, M.},
     booktitle = {Proceedings of IEEE INFOCOM 2011, the 30th Annual Joint Conference of the IEEE Computer and Communications Societies},
     pages = {3191--3199},
     year = {2011},
   }

2010

1. JDA

   Online Time-Constrained Scheduling in Linear and Ring Networks

   J. Naor, A. Rosén, and G. Scalosub

   Journal of Discrete Algorithms, 2010

   Abs Bib

   We consider the problem of scheduling a sequence of packets over a linear network, where every packet has a source and a target, as well as a release time and a deadline by which it must arrive at its target. The model we consider is bufferless, where packets are not allowed to be buffered in nodes along their paths other than at their source. This model applies to optical networks where opto-electronic conversion is costly, and packets mostly travel through bufferless hops. The offline version of this problem was previously studied in M. Adler et al. (2002). In this paper we study the online version of the problem, where we are required to schedule the packets without knowledge of future packet arrivals. We use competitive analysis to evaluate the performance of our algorithms. We present the first online algorithms for several versions of the problem. For the problem of throughput maximization, where all packets have uniform weights, we give an algorithm with a logarithmic competitive ratio, and present some lower bounds. For other weight functions, we show algorithms that achieve optimal competitive ratios.

   @article{naor2010online,
     themes = {buffer_scheduling},
     title = {Online Time-Constrained Scheduling in Linear and Ring Networks},
     author = {Naor, J. and Rosén, A. and Scalosub, G.},
     journal = {Journal of Discrete Algorithms},
     volume = {8},
     number = {4},
     pages = {346--355},
     year = {2010}
   }

2. MobiHoc

   On Quality of Monitoring for Multi-channel Wireless Infrastructure Networks

   A. Chhetri, H.A. Nguyen, G. Scalosub, and R. Zheng

   In Proceedings of MobiHoc 2010, the 11th ACM International Symposium on Mobile Ad Hoc Networking and Computing, 2010

   Abs Bib PDF

   Passive monitoring utilizing distributed wireless sniffers is an effective technique to monitor activities in wireless infrastructure networks for fault diagnosis, resource management and critical path analysis. In this paper, we introduce a quality of monitoring (QoM) metric defined by the expected number of active users monitored, and investigate the problem of maximizing QoM by judiciously assigning sniffers to channels based on knowledge of user activities in a multi-channel wireless network. Two capture models are considered. The first one, called the user-centric model assumes frame-level capturing capability of sniffers such that the activities of different users can be distinguished. The second one, called the sniffer-centric model only utilizes binary channel information (active or not) at a sniffer. For the user-centric model, we show that the implied optimization problem is NP-hard, but a constant approximation ratio can be attained via polynomial complexity algorithms. For the sniffer-centric model, we devise a stochastic inference scheme that transforms the problem into the user-centric domain, where we are able to apply our polynomial approximation algorithms. The effectiveness of our proposed scheme and algorithms is further evaluated using both synthetic data as well as real-world traces from an operational WLAN.

   @inproceedings{chhetri2010quality,
     title = {On Quality of Monitoring for Multi-channel Wireless Infrastructure Networks},
     author = {Chhetri, A. and Nguyen, H.A. and Scalosub, G. and Zheng, R.},
     booktitle = {Proceedings of MobiHoc 2010, the 11th ACM International Symposium on Mobile Ad Hoc Networking and Computing},
     pages = {111--120},
     year = {2010},
   }

3. INFOCOM

   Buffer Management for Aggregated Streaming Data with Packet Dependencies

   G. Scalosub, J. Liebeherr, and P. Marbach

   In Proceedings of IEEE INFOCOM 2010 Mini-conference, the 29th Annual Joint Conference of the IEEE Computer and Communications Societies, 2010

   Abs Bib PDF

   In many applications the traffic traversing the network has inter-packet dependencies due to application-level encoding schemes. For some applications, e.g., multimedia streaming, dropping a single packet may render useless the delivery of a whole sequence. In such environments, the algorithm used to decide which packet to drop in case of buffer overflows must be carefully designed, to avoid goodput degradation. We present a model that captures such inter-packet dependencies, and design algorithms for performing packet discards. Traffic consists of an aggregation of multiple streams, each of which consists of a sequence of inter-dependent packets. We provide two guidelines for designing buffer management algorithms for this problem, and demonstrate the effectiveness of these criteria. We devise an algorithm according to these guidelines and evaluate its performance analytically, using competitive analysis. We also present a simulation study that shows that the performance of our algorithm is within a small fraction of the performance of the best offline algorithm.

   @inproceedings{scalosub2010buffer,
     title = {Buffer Management for Aggregated Streaming Data with Packet Dependencies},
     author = {Scalosub, G. and Liebeherr, J. and Marbach, P.},
     booktitle = {Proceedings of IEEE INFOCOM 2010 Mini-conference, the 29th Annual Joint Conference of the IEEE Computer and Communications Societies},
     pages = {241--245},
     year = {2010},
   }

2009

1. ToA

   Jitter Regulation for Multiple Streams

   D. Hay and G. Scalosub

   ACM Transactions on Algorithms, 2009

   Abs Bib

   For widely used interactive communication, it is essential that traffic is kept as smooth as possible; the smoothness of the traffic is typically captured by its delay jitter, that is, the difference between the maximal and minimal end-to-end delays. The task of minimizing the jitter is done by jitter regulators that use a limited-size buffer in order to shape the traffic. In many real-life situations regulators must handle multiple streams simultaneously and provide low jitter on each of them separately. Moreover, communication links have limited capacity, and these may pose further restrictions on the choices made by the regulator. This article investigates the problem of minimizing jitter in such an environment, using a fixed-size buffer. We show that the offline version of the problem can be solved in polynomial time, by introducing an efficient offline algorithm that finds a release schedule with optimal jitter. When regulating M streams in the online setting, we take a competitive analysis point of view and note that, in the upcapacitated case, previous results in Mansour and Patt-Shamir [2001] can be extended to an online algorithm that uses a buffer of size 2⋅M⋅B and obtains the optimal jitter possible with a buffer of size B (and an offline algorithm). The question arises whether such a resource augmentation is essential. We answer this question in the affirmative, by proving a lower bound that is tight up to a factor of 2, thus showing that jitter regulation does not scale well as the number of streams increases unless the buffer is sized-up proportionally.

   @article{hay2009jitter,
     themes = {buffer_scheduling},
     title = {Jitter Regulation for Multiple Streams},
     author = {Hay, D. and Scalosub, G.},
     journal = {ACM Transactions on Algorithms},
     volume = {6},
     number = {1},
     year = {2009}
   }

2. ToA

   Bicriteria Approximation Tradeoff for the Node-Cost Budget Problem

   Y. Rabani and G. Scalosub

   ACM Transactions on Algorithms, 2009

   Abs Bib

   We consider an optimization problem consisting of an undirected graph, with cost and profit functions defined on all vertices. The goal is to find a connected subset of vertices with maximum total profit, whose total cost does not exceed a given budget. The best result known prior to this work guaranteed a (2, O(\log n)) bicriteria approximation, that is, the solution’s profit is at least a fraction of 1/O(\log n) of an optimum solution respecting the budget, while its cost is at most twice the given budget. We improve these results and present a bicriteria tradeoff that, given any \varepsilon ∈(0,1], guarantees a (1 + \varepsilon, O(1/\varepsilon \log n))-approximation.

   @article{rabani2009bicriteria,
     title = {Bicriteria Approximation Tradeoff for the Node-Cost Budget Problem},
     author = {Rabani, Y. and Scalosub, G.},
     journal = {ACM Transactions on Algorithms},
     volume = {5},
     number = {2},
     year = {2009}
   }

3. IPDPS

   Competitive Buffer Management with Packet Dependencies

   A. Kesselman, B. Patt-Shamir, and G. Scalosub

   In Proceedings of IPDPS 2009, the 23rd IEEE International Parallel and Distributed Processing Symposium, 2009

   Abs Bib PDF Slides

   We introduce the problem of managing a FIFO buffer of bounded space, where arriving packets have dependencies among them. Our model is motivated by the scenario where large data frames must be split into multiple packets, because maximum packet size is limited by data-link restrictions. A frame is considered useful only if sufficiently many of its constituent packets are delivered. The buffer management algorithm decides, in case of overflow, which packets to discard and which to keep in the buffer. The goal of the buffer management algorithm is to maximize throughput of useful frames. We study the complexity of the above problem for various settings in both the offline and online settings. We give upper and lower bounds on the performance of algorithms using competitive analysis.

   @inproceedings{kesselman2009competitive,
     title = {Competitive Buffer Management with Packet Dependencies},
     author = {Kesselman, A. and Patt-Shamir, B. and Scalosub, G.},
     booktitle = {Proceedings of IPDPS 2009, the 23rd IEEE International Parallel and Distributed Processing Symposium},
     year = {2009},
   }

4. INFOCOM

   Toward Optimal Utilization of Shared Random Access Channels

   J. Naor, D. Raz, and G. Scalosub

   In Proceedings of IEEE INFOCOM 2009, the 28th Annual Joint Conference of the IEEE Computer and Communications Societies, 2009

   Abs Bib PDF Slides

   We consider a multipacket reception channel shared by several communication applications. This is the case, for example, in a single radio mesh network where neighboring cells use the same radio channel. In such scenarios, unlike the common multiple access model, several transmissions may succeed simultaneously, depending on the actual locations of the sending and receiving stations, and thus channel utilization may be greater than 1. Our goal is to derive a decentralized access control mechanism that maximizes the channel utilization, while taking into account fairness among the different users. We focus on a simple case where each user can adjust a single parameter that determines its transmission probability in any time slot, and develop such a protocol for the general problem, where users are distributed arbitrarily, based on strong motivation which is derived from analytical bounds for homogeneous interferences. We further show, using extensive simulations, that this protocol achieves a high utilization of radio resources compared to any other protocol (not necessary based on a simple parameter), while maintaining fairness between all users.

   @inproceedings{naor2009toward,
     title = {Toward Optimal Utilization of Shared Random Access Channels},
     author = {Naor, J. and Raz, D. and Scalosub, G.},
     booktitle = {Proceedings of IEEE INFOCOM 2009, the 28th Annual Joint Conference of the IEEE Computer and Communications Societies},
     pages = {2061--2069},
     year = {2009},
   }

2008

1. WINE

   Homogeneous Interference Game in Wireless Networks

   J. Naor, D. Raz, and G. Scalosub

   In Proceedings of WINE 2008, the 4th International Workshop on Internet and Network Economics, 2008

   Abs Bib PDF Supp Slides

   We consider the problem of joint usage of a shared wireless channel in an interference-bound environment, and focus on a distributed setting where there is no central entity managing the various transmissions. In such systems, unlike other multiple access environments, several transmissions may succeed simultaneously, depending on spatial interferences between the different stations. We use a game theoretic view to model the problem, where the stations are selfish agents aiming at maximizing their success probability. We show that when interferences are homogeneous, system performance suffers an exponential degradation in performance at an equilibrium, due to the selfishness of the stations. However, when using a proper penalization scheme for aggressive stations, we can ensure the system’s performance value is at least 1/e of the optimal value, while still being at equilibrium.

   @inproceedings{naor2008homogeneous,
     title = {Homogeneous Interference Game in Wireless Networks},
     author = {Naor, J. and Raz, D. and Scalosub, G.},
     booktitle = {Proceedings of WINE 2008, the 4th International Workshop on Internet and Network Economics},
     pages = {514--521},
     year = {2008},
   }

2. OPODIS

   Distributed Approximation of Cellular Coverage

   B. Patt-Shamir, D. Rawitz, and G. Scalosub

   In Proceedings of OPODIS 2008, the 12th International Conference on Principles of Distributed Systems, 2008

   Abs Bib PDF

   We consider the following model of cellular networks. Each base station has a given finite capacity, and each client has some demand and profit. A client can be covered by a specific subset of the base stations, and its profit is obtained only if its demand is provided in full. The goal is to assign clients to base stations, so that the overall profit is maximized subject to base station capacity constraints. In this work we present a distributed algorithm for the problem, that runs in polylogarithmic time, and guarantees an approximation ratio close to the best known ratio achievable by a centralized algorithm.

   @inproceedings{pattshamir2008distributed,
     title = {Distributed Approximation of Cellular Coverage},
     author = {Patt-Shamir, B. and Rawitz, D. and Scalosub, G.},
     booktitle = {Proceedings of OPODIS 2008, the 12th International Conference on Principles of Distributed Systems},
     pages = {331--345},
     year = {2008},
   }

3. ICNP

   Competitive Analysis of Buffer Policies with SLA Commitments

   B. Patt-Shamir, G. Scalosub, and Y. Shavitt

   In Proceedings of ICNP 2008, the 16th IEEE International Conference on Network Protocols, 2008

   Abs Bib PDF Slides

   We consider an abstraction of the problem of managing buffers where traffic is subject to service level agreements (SLA). In our abstraction of SLAs, some packets are marked as committed and the others are marked as excess. The service provider must on one hand deliver all committed packets, and on the other hand can get extra revenue for any excess packet delivered. We study online algorithms managing a buffer with limited space, whose task is to decide which packets should be delivered and which should be dropped. Using competitive analysis, we show how to utilize additional buffer space and link bandwidth so that the number of excess packets delivered is comparable to the best possible by any off-line algorithm, while guaranteeing that no committed packet is ever lost.

   @inproceedings{pattshamir2008competitive,
     themes = {buffer_scheduling},
     title = {Competitive Analysis of Buffer Policies with SLA Commitments},
     author = {Patt-Shamir, B. and Scalosub, G. and Shavitt, Y.},
     booktitle = {Proceedings of ICNP 2008, the 16th IEEE International Conference on Network Protocols},
     pages = {197--206},
     year = {2008},
   }

4. SWAT

   Bicriteria Approximation Tradeoff for the Node-Cost Budget Problem

   Y. Rabani and G. Scalosub

   In Proceedings of SWAT 2008, the 11th Scandinavian Workshop on Algorithm Theory, 2008

   Abs Bib PDF Slides

   We consider an optimization problem consisting of an undirected graph, with cost and profit functions defined on all vertices. The goal is to find a connected subset of vertices with maximum total profit, whose total cost does not exceed a given budget. The best result known prior to this work guaranteed a (2,O(log n)) bicriteria approximation, i.e. the solution’s profit is at least an O(log n) fraction of an optimum solution respecting the budget, while its cost is at most twice the given budget. We improve these results and present a bicriteria tradeoff that, given any 0 < eps <= 1, guarantees a (1+eps,O(log n)/eps)-approximation.

   @inproceedings{rabani2008bicriteria,
     title = {Bicriteria Approximation Tradeoff for the Node-Cost Budget Problem},
     author = {Rabani, Y. and Scalosub, G.},
     booktitle = {Proceedings of SWAT 2008, the 11th Scandinavian Workshop on Algorithm Theory},
     pages = {90--101},
     year = {2008},
   }

5. INFOCOM

   Cell Selection in 4G Cellular Networks

   D. Amzallag, R. Bar-Yehuda, D. Raz, and G. Scalosub

   In Proceedings of IEEE INFOCOM 2008, the 27th Annual Joint Conference of the IEEE Computer and Communications Societies, 2008

   Abs Bib PDF Slides

   Cell selection is the process of determining the cell(s) that provide service to each mobile station. Optimizing these processes is an important step towards maximizing the utilization of current and future cellular networks. In this paper we study the potential benefit of global cell selection versus the current local mobile SNR-based decision protocol. In particular, we study the new possibility that is feasible in OFDMA-based systems, of satisfying the minimal demand of a mobile station simultaneously by more than one base station. We formalize the problem as an optimization problem, called the all-or-nothing demand maximization problem, and show that when the demand of a single mobile station can exceed the capacity of a base station, this problem is not only NP-hard but also cannot be approximated within any reasonable factor. In contrast, under the very practical assumption that the maximum required bandwidth of a single mobile station is at most an r-fraction of the capacity of a base station, we present two different algorithms for cell selection. The first algorithm guarantees a satisfaction of at least a (1-r)-fraction of an optimal assignment, where a mobile station can be covered simultaneously by more than one base station. The second algorithm guarantees a satisfaction of at least a (1-r)/(2-r)-fraction of an optimal assignment, while every mobile station is covered by at most one base station. Using an extensive simulation study we show that the cell selections determined by our algorithms achieve a better utilization of high-loaded capacity-constrained future 4G networks than the current SNR-based scheme. Specifically, our algorithms are shown to obtain up to 20% better usage of the network’s capacity, in comparison with the current cell selection algorithms.

   @inproceedings{amzallag2008cell,
     title = {Cell Selection in 4G Cellular Networks},
     author = {Amzallag, D. and Bar-Yehuda, R. and Raz, D. and Scalosub, G.},
     booktitle = {Proceedings of IEEE INFOCOM 2008, the 27th Annual Joint Conference of the IEEE Computer and Communications Societies},
     pages = {700--708},
     year = {2008},
   }

2007

1. SPAA

   Rate vs. Buffer Size: Greedy Information Gathering on the Line

   A. Rosén and G. Scalosub

   In Proceedings of SPAA 2007, the 19th Annual ACM Symposium on Parallel Algorithms and Architectures, 2007

   Abs Bib PDF Slides

   We consider packet networks with limited buffer space at the nodes, and are interested in the question of maximizing the number of packets that arrive to destination rather than being dropped due to full buffers. We initiate a more refined analysis of the throughput competitive ratio of admission and scheduling policies in the Competitive Network Throughput model introduced by Aiello et al. (2003), taking into account not only the network size but also the buffer size and the injection rate of the traffic. We specifically consider the problem of information gathering on the line, with limited buffer space, under adversarial traffic. We examine how the buffer size and the injection rate of the traffic affect the performance of the greedy protocol for this problem. We establish upper bounds on the competitive ratio of the greedy protocol in terms of the network size, the buffer size, and the adversary’s rate, and present lower bounds which are tight up to constant factors. These results show, for example, that provisioning the network with sufficiently large buffers may substantially improve the performance of the greedy protocol in some cases, whereas for some high-rate adversaries, using larger buffers does not have any effect on the competitive ratio of the protocol.

   @inproceedings{rosen2007rate,
     title = {Rate vs. Buffer Size: Greedy Information Gathering on the Line},
     author = {Rosén, A. and Scalosub, G.},
     booktitle = {Proceedings of SPAA 2007, the 19th Annual ACM Symposium on Parallel Algorithms and Architectures},
     pages = {305--314},
     year = {2007},
   }

2005

1. ESA

   Jitter Regulation for Multiple Streams

   D. Hay and G. Scalosub

   In Proceedings of ESA 2005, the 13th Annual European Symposium on Algorithms, 2005

   Abs Bib PDF Slides

   For widely-used interactive communication, it is essential that traffic is kept as smooth as possible; the smoothness of the traffic is typically captured by its delay jitter, i.e., the difference between the maximal and minimal end-to-end delays. The task of minimizing the jitter is done by jitter regulators that use a limited-size buffer in order to shape the traffic. In many real-life situations regulators must handle multiple streams simultaneously and provide low jitter on each of them separately. Moreover, communication links have limited capacity, and these may pose further restrictions on the choices made by the regulator. This paper investigates the problem of minimizing jitter in such an environment, using a fixed-size buffer. We show that the offline version of the problem can be solved in polynomial time, by introducing an efficient offline algorithm that finds a release schedule with optimal jitter. When regulating M streams in the online setting, we take a competitive analysis point of view and note that previous results by Mansour and Patt-Shamir (2001) can be extended to an online algorithm that uses a buffer of size 2MB and obtains the optimal jitter possible with a buffer of size B (and an offline algorithm). The question arises whether such a resource augmentation is essential. We answer this question in the affirmative, by proving a lower bound that is tight up to a factor of 2, thus showing that jitter regulation does not scale well as the number of streams increases unless the buffer is sized-up proportionally.

   @inproceedings{hay2005jitter,
     title = {Jitter Regulation for Multiple Streams},
     author = {Hay, D. and Scalosub, G.},
     booktitle = {Proceedings of ESA 2005, the 13th Annual European Symposium on Algorithms},
     pages = {496--507},
     year = {2005},
   }

2. INFOCOM

   Online Time-Constrained Scheduling in Linear Networks

   J. Naor, A. Rosén, and G. Scalosub

   In Proceedings of IEEE INFOCOM 2005, the 24th Annual Joint Conference of the IEEE Computer and Communications Societies, 2005

   Abs Bib PDF Slides

   We consider the problem of scheduling a sequence of packets over a linear network, where every packet has a source and a target, as well as a release time and a deadline by which it must arrive at its target. The model we consider is bufferless, where packets are not allowed to be buffered in nodes along their paths other than at their source. This model applies to optical networks where opto-electronic conversion is costly, and packets mostly travel through bufferless hops. The offline version of this problem was previously studied by Adler et al. (2002). In this paper we study the online version of the problem, where we are required to schedule the packets without knowledge of future packet arrivals. We use competitive analysis to evaluate the performance of our algorithms. We present the first online algorithms for several versions of the problem. For the problem of throughput maximization, where all packets have uniform weights, we give an algorithm with a logarithmic competitive ratio, and present some lower bounds. For other weight functions, we show algorithms that achieve optimal competitive ratios.

   @inproceedings{naor2005online,
     title = {Online Time-Constrained Scheduling in Linear Networks},
     author = {Naor, J. and Rosén, A. and Scalosub, G.},
     booktitle = {Proceedings of IEEE INFOCOM 2005, the 24th Annual Joint Conference of the IEEE Computer and Communications Societies},
     pages = {855--865},
     year = {2005},
   }