Overview of Morris's counters

We are glad to present you an article written by Qrator Labs' engineer Dmitry Kamaldinov. If you want to be a part of our Core team, write us at hr@qrator.net.

## 1 Introduction

On implementing streaming algorithms, counting of events often occurs, where an event means something like a packet arrival or a connection establishment. Since the number of events is large, the available memory can become a bottleneck: an ordinary $$n$$-bit counter allows to take into account no more than $$2^n - 1$$ events.
One way to handle a larger range of values using the same amount of memory would be approximate counting. This article provides an overview of the well-known Morris algorithm and some generalizations of it.

Another way to reduce the number of bits required for counting mass events is to use decay. We discuss such an approach here, and we are going to publish another blog post on this particular topic shortly.

In the beginning of this article, we analyse one straightforward probabilistic calculation algorithm and highlight its shortcomings (Section 2). Then (Section 3), we describe the algorithm proposed by Robert Morris in 1978 and indicate its most essential properties and advantages. For most non-trivial formulas and statements, the text contains our proofs, the demanding reader can find them in the inserts. In the following three sections, we outline valuable extensions of the classic algorithm: you can learn what Morris's counters and exponential decay have in common, how to improve the accuracy by sacrificing the maximum value, and how to handle weighted events efficiently.

Qrator Labs' Value Partnership Programs

Why is it valuable to get into the Qrator Labs partnership program?

In Qrator Labs, we firmly believe that working together brings a better result. Which is the reason why, for years, we were trying to find meaningful partnerships with all kinds of companies. They either seek to provide their existing customers with the top-notch DDoS mitigation technology developed at Qrator Labs with many additional ecosystem solutions or want to succeed the other way around. By getting their product available for Qrator Labs' customers by integrating into the Qrator anycast filtering network.

Cybersecurity Newsletter, February 14 - 28

Greetings, fellow newsletter subscriber! Once again, we are back with the best stories and articles published on the topic of cybersecurity in two weeks, between 14 and 28 February, the year 2021.

Cybersecurity Newsletter, February 8 - 14

Hello and welcome back to the regular cyber and infosecurity letter! This time we are going through the relevant articles published 8 - 14 February 2021.

Cybersecurity Newsletter, February 1 - 7

Greetings, fellow subscribers! As usual on Sundays, we are back with the most relevant and interesting articles published between February 1 and 7, 2021.

Cybersecurity Newsletter, January 18 - 31

Welcome back to the cybersecurity newsletter! This time, we are looking at the two weeks of the most relevant stories starting with January 18.

Welcome back to the regular cybersecurity newsletter brought to you by Qrator Labs! With this letter, we want to look back at the previous two weeks that started the year 2021 and pick only the most relevant stories.

10(+) years in the Labs

At the beginning of the year 2021, Qrator Labs is celebrating its 10 year anniversary. On January 19 our company marks the official passing of a formal 10 years longevity mark, entering its second decade of existence.

Everything started a little bit earlier - when at the age of 10 Alex saw the Robotron K 1820 - in 2008, when Alexander Lyamin - the founder and CEO of Qrator Labs, approached the Moscow State University superiors, where he worked as a NOC engineer at the time, with an idea of a DDoS-attack mitigation research project. The MSU's network was one of the largest in the country and, as we know now, it was the best place to hatch a future technology.

That time MSU administration agreed, and Mr Lyamin took his own hardware to the university, simultaneously gathering a team. In two years, by summer 2010, the project turned out to be that successful. It courted the DDoS attack of a bandwidth exceeding the MSU's upstream bandwidth capability. And on June 22 MSU superiors gave Mr Lyamin a choice - to shut down or find money to incorporate.

Alexander Lyamin chose to incorporate with his own means, which effectively meant that the needed infrastructure must be built from scratch. The initial design should be distributed instead of concentrated within one network, which resources were not enough for this specific task. And by September 1, 2010, those first server sites were ready and running.

Cybersecurity Newsletter, December 14 - 20

Hello and welcome into the last letter on cyber and networking security for the year 2020!  We want to wish you a Merry Christmas and a Happy New Year.

Now let's take a look at the articles and papers covering the week of December 14 to 20.

Cybersecurity Newsletter, November 30 - December 13

Greetings fellow subscriber! This week we are going to scroll through the two-weeks events in cybersecurity, everything that happened between November 30 and December 13, 2020.