New data structure allows rapid tracking and policing of network data

October 5, 2017, Agency for Science, Technology and Research (A*STAR), Singapore

To protect networks from malicious threats, cyber-security solutions must track all the data flowing through the network—just like security guards checking travelers in airports. However, it is hard to design a solution that works fast enough to process all the information in real time, and to block threats before they can strike. Now, A*STAR researchers have designed a way to structure data that is robust against cyber-attacks and allows it to be processed in record time.

The team's work improves on widely-used data structures called 'hash tables'. "A hash table maps values to specific locations, labeled with indices," explains Vrizlynn Thing from the A*STAR's Institute for Infocomm Research, who led the study. "To find a value, the hash table performs computations to quickly identify the indices and thus, its location. The challenges are that millions of values need to be stored, and the values are generated and transmitted extremely quickly."

Traditional hash tables are becoming inefficient as the internet grows and data flows get larger. Researchers have developed data structures known as Cuckoo and Peacock, but when they are under attack, these hash tables fill up quickly, eroding performance.

The new data structure developed by Thing and her team is called REX. "The name REX stands for Resilient and Efficient data Structure (X for structure)" says Thing. Jokingly, Thing explained that this data structure was named REX (after Tyrannosaurus Rex) to signify a stronger creature than the Cuckoo and Peacock as it outperforms both tables.

REX works by exploiting some inherent characteristics of internet traffic. For example, it takes into account the 'heavy-tail' behavior of data flows (there are a few large 'elephant flows' which contribute to a larger percentage of the total volume than the many small 'mice flows'), by employing a hierarchy of sub-tables increasing in size from top to bottom. This structure effectively segregates the different types of flows.

"We also utilized the special processing property of computer RAM," says Thing. "Our design features both fast, expensive Static RAM and slower, cheaper Dynamic RAM." The faster SRAM is used to process the few large, important flows, allowing fast tracking and frequent updates, while DRAM handles the low priority flows in secondary sub-tables.

In tests using real recorded network traffic, REX was faster and more efficient at analyzing data than Cuckoo and Peacock. "We will further investigate the efficiency and scalability of this new data for security analysis in larger scale environments," says Thing.

Explore further: Making and breaking passwords

More information: Dinil Mon Divakaran et al. REX: Resilient and efficient data structure for tracking network flows, Computer Networks (2017). DOI: 10.1016/j.comnet.2017.03.004

Related Stories

Making and breaking passwords

March 24, 2016

The issue of choosing a good password is still key for cyber security because users tend to pick passwords that are easy to remember rather than secure. So what are the key attributes of a good password?

Network traffic anomaly detection

December 27, 2016

"Diagnosing unusual events (called "anomalies") in a large-scale network like Internet Service Providers and enterprise networks is critical and challenging for both network operators and end users," explain Hiroyuki Kasai ...

Small units on a big surface = fewer calories

January 19, 2016

How does the size of the table we eat at influence how much we eat? This is the question that researchers posed and answered in a new study published in the Journal of the Association for Consumer Research. They found that ...

Recommended for you

Physicists discover new class of pentaquarks

March 26, 2019

Tomasz Skwarnicki, professor of physics in the College of Arts and Sciences at Syracuse University, has uncovered new information about a class of particles called pentaquarks. His findings could lead to a new understanding ...

Study finds people who feed birds impact conservation

March 26, 2019

People in many parts of the world feed birds in their backyards, often due to a desire to help wildlife or to connect with nature. In the United States alone, over 57 million households in the feed backyard birds, spending ...

Matter waves and quantum splinters

March 25, 2019

Physicists in the United States, Austria and Brazil have shown that shaking ultracold Bose-Einstein condensates (BECs) can cause them to either divide into uniform segments or shatter into unpredictable splinters, depending ...


Please sign in to add a comment. Registration is free, and takes less than a minute. Read more

Click here to reset your password.
Sign in to get notified via email when new comments are made.