Gil Einziger

Gil Einziger


Research Focus & Metrics

Academic Career Length

13Years (2014-Present)

(Calculated once Scilit publication data is synced: current year − year of first publication + 1)

Representative Publications

View All Publications
17 October 2019 in IEEE/ACM Transactions on Networking
Verified
Journal Article
Closed access
FMFrancesco Malandrino
Francesco Malandrino
CCCarla Fabiana Chiasserini
Carla Fabiana Chiasserini
GEGil Einziger
Gil Einziger
GSGabriel Scalosub
Gabriel Scalosub

10 June 2019 in IEEE/ACM Transactions on Networking
Verified
Journal Article
Closed access
RBRan Ben Basat
Ran Ben Basat
XCXiaoqi Chen
Xiaoqi Chen
GEGil Einziger
Gil Einziger
RFRoy Friedman
Roy Friedman
YKYaron Kassner
Yaron Kassner
Network management protocols often require timely and meaningful insight about per flow network traffic. This paper introduces Randomized Admission Policy (RAP) -a novel algorithm for the frequency, top-k, and byte volume estimation problems, which are fundamental in network monitoring. We demonstrate space reductions compared to the alternatives, for the frequency estimation problem, by a factor of up to 32 on real packet traces and up to 128 on heavy-tailed workloads. For top-k identification, RAP exhibits memory savings by a factor of between 4 and 64 depending on the workloads' skewness. These empirical results are backed by formal analysis, indicating the asymptotic space improvement of our probabilistic admission approach. In Addition, we present d-way RAP, a hardware friendly variant of RAP that empirically maintains its space and accuracy benefits.

23 April 2018 in IEEE Transactions on Mobile Computing
Verified
Journal Article
Closed access
GEGil Einziger
Gil Einziger
CCCarla Fabiana Chiasserini
Carla Fabiana Chiasserini
FMFrancesco Malandrino
Francesco Malandrino
Vehicular users are emerging as a prime market for targeted advertisement, where advertisements (ads) are sent from network points of access to vehicles, and displayed to passengers only if they are relevant to them. In this study, we take the viewpoint of a broker managing the advertisement system, and getting paid every time a relevant ad is displayed to an interested user. The broker selects the ads to broadcast at each point of access so as to maximize its revenue. In this context, we observe that choosing the ads that best fit the users' interest could actually hurt the broker's revenue. In light of this conflict, we present Volfied, an algorithm allowing for conflict-free, near-optimal ad selection with very low computational complexity. Our performance evaluation, carried out through real-world vehicular traces, shows that Volfied increases the broker revenue by up to 70 percent with provably low computational complexity, compared to state-of-the-art alternatives.

26 June 2019 in IEEE Access
Verified
Journal Article
Open access
GEGil Einziger
Gil Einziger
RFRoy Friedman
Roy Friedman
Bloom filters are space efficient data structures that support approximate membership queries. They are easily extensible but incur significant overheads when extended to support additional functionality such as removals or counting. Our work shows that fingerprint-based hash tables offer a much better tradeoff between accuracy and space. We present TinyTable that supports set membership, removals, and multiplicity queries. TinyTable reduces the required memory by as much as 28% compared to Bloom filter based variants for the set membership, and by as much as 60% for counting and statistics. It is more compact than Bloom filters as long as the false positive ratio is less than 1%.

30 August 2021 in IEEE/ACM Transactions on Networking
Verified
Journal Article
Closed access
RBRan Ben-Basat
Ran Ben-Basat
GEGil Einziger
Gil Einziger
SFShir Landau Feibish
Shir Landau Feibish
JMJalil Moraney
Jalil Moraney
BTBilal Tayh
Bilal Tayh
DRDanny Raz
Danny Raz
The recent introduction of SDN allows deploying new centralized network algorithms that dramatically improve network operations. In such algorithms, the centralized controller obtains a network-wide view by merging measurement data from Network Measurement Points (NMPs). A fundamental challenge is that several NMPs may count the same packet, reducing the accuracy of the measurement. Existing solutions circumvent this problem by assuming that each packet traverses a single NMP or that the routing is fixed and known. This work suggests novel algorithms for three fundamental network-wide measurement problems without making any assumptions on the topology and routing and without modifying the underlying traffic. Specifically, this work introduces two algorithms for estimating the number of (distinct) packets or byte volume in the measurement, estimating per-flow packet and byte counts, and finding the heavy hitter flows. Our work includes formal accuracy guarantees and an extensive evaluation consisting of the realistic fat-tree topology and three real network traces. Our evaluation shows that our algorithms outperform existing works and provide accurate measurements within reasonable space parameters.

25 April 2018 in IEEE/ACM Transactions on Networking
Verified
Journal Article
Closed access
GEGil Einziger
Gil Einziger
BFBenny Fellman
Benny Fellman
RFRoy Friedman
Roy Friedman
YKYaron Kassner
Yaron Kassner
Measurement capabilities are essential for a variety of network applications, such as load balancing, routing, fairness, and intrusion detection. These capabilities require large counter arrays in order to monitor the traffic of all network flows. While commodity SRAM memories are capable of operating at line speed, they are too small to accommodate large counter arrays. Previous works suggested estimators, which trade precision for reduced space. However, in order to accurately estimate the largest counter, these methods compromise the accuracy of the smaller counters. In this paper, we present a closed form representation of the optimal estimation function. We then introduce independent counter estimation buckets, a novel algorithm that improves estimation accuracy for all counters. This is achieved by separating the flows to buckets and configuring the optimal estimation function according to each bucket's counter scale. We prove a tighter upper bound on the relative error and demonstrate an accuracy improvement of up to 57 times on real Internet packet traces.