For several years now, Qrator Labs has been working with different universities to find students interested in specific tasks we deal with, for them to either get new experience or mark a future career path in network and computer engineering.

At the moment, several Qrator Labs employees started out as interns, picking one of the programs provided at the universities they studied. Of course, not everyone chooses computer engineering as a field of specialization — out of 23 students that participated in the university programs during 2019 and 2020, 9 were invited for internships. Only four of them became our colleagues in those years, which makes their stories quite special.

This time we want to elaborate a little bit more about one of our employees — Dmitry Kamaldinov, who is still on the way to his master's degree, although his bachelor was given after the successful defence of a thesis Dmitry picked up because of his Qrator Labs internship.

Of course, such an internship requires a student's willingness to participate in a specific program and the program availability itself, which should be composed by one of our employees and stay in touch with the peculiarities of what we do in Qrator Labs.

Dmitry Kamaldinov, who is now an engineer within the company, found an exciting program at his university and enrolled in it, not yet knowing at the time that it would lead him to choose the specific bachelor's thesis thanks to it, and, furthermore, finding a job at Qrator Labs.

According to his own words, the assigned task was not associated with what Qrator Labs does, and neither with the field Dmitry works in right now. The mission was about accessing the C++ open-source library from Python. Sounds like a good task for a student? You can see the result for yourself: https://github.com/QratorLabs/pysdsl

Sometime after, Dmitry needed to pick up a bachelor's thesis, and here again, it was tied with the company we all work with. Dmitry's particular university department allowed him to choose for any research advisor he wanted, not limiting those only to university professors. After a couple of questions were answered, another mathematician colleague of ours, Artem Shvorin, contacted Dmitry and suggested that one task was to develop an extension of a well-known Space Saving algorithm, appropriate for application to the problems being investigated by the Qrator Core team. The other idea was about another algorithm of a masked decision tree, used to store the specific values and further allowed manipulating the stored data.

Finally, after evaluating both thesis's ideas, Dmitry chose the second one, containing the work around the decision tree.

At first, there was just a basic concept of a tree and some simple proof of concept that Dmitry could speed up and make even better. The other question was how to implement such an algorithm in traffic filtering jobs — a task that was also considered during the thesis defence.
The thesis was devoted to developing a novel algorithm for detecting heavy flows and the study of its applicability to the traffic filtering problem.

While this field of research is interesting itself, with many new articles being published constantly, speaking of traffic analysis, the need for an efficient algorithm becomes quite urgent due to the increase of IPv6 adoption. Recall the number of unique IPv6 addresses is 2^128 that makes impossible any trivial approaches like processing each address separately.

One popular kind of relevant algorithm is sketch-based algorithms that decrease the original keyspace dimension dividing the keys into subsets. While most such algorithms use a fixed splitting, the idea proposed by Artem Shvorin was to consider it changing dynamically during the algorithm run. The structure that manages this process is a decision tree, a binary tree with predicates (prefix masks actually) in its nodes according to which the key is decided to be pushed down either to the left or right subtree.

The key points of the algorithm design Dmitry discussed in his work were efficient updating of the structure when a new key is obtained, keeping the tree stable on stationary flows, efficient search for a new prefix mask if needed. And finally, the strategy of its application to the traffic filtering problem. The final version utilizes well-known ideas (such as rotations widely used to balance many of BST) as well as some new transformations and algorithms that resulted in a reasonable update asymptotic. The algorithm was also shown to work well on some traffic patterns.

At Qrator Labs, we enjoy making science and looking for practical applications to create a high-quality and sought-after product.

Further stories are to come from Qrator Labs academic newcomers, stay tuned.

If you’re interested in working at Qrator Labs, or want to ask us for a possible internship — let us know at hr@qrator.net. Thanks for reading.