# An Efficient Method for Detecting Supernodes Using Reversible Summary Data Structures in the Distributed Monitoring Systems

Authors: Aiping Zhou; Jin Qian
Journal: Security and Communication Networks
 (2022)

---

## Abstract

Supernode detection has many applications in detecting network attacks, assisting resource allocation, etc. As 5G/IoT networks constantly grow, big network traffic brings a great challenge to collect massive traffic data in compact and real-time way. Previous works focus on detecting supernodes in a measurement point, while only a few works consider it in the distributed monitoring system. Moreover, they are not able to measure two types of node cardinalities simultaneously and reconstruct labels of supernodes efficiently due to large calculation and memory cost. To address these problems, we propose a novel reversible and distributed traffic summarization called RDS to simultaneously measure source and destination cardinalities for detecting supernodes in the distributed monitoring system. The basic idea of our approach is that each monitor generates a summary data structure using the coming packets and sends the summary data structure to the controller; then, the controller aggregates the received summary data structures, estimates node cardinalities, and reconstructs labels of supernodes according to the aggregated summary data structure. The experimental results based on real network traffic demonstrate that the proposed approach can detect up to 96% supernodes with a low memory requirement in comparison with state-of-the-art approaches.


---

## Body

## 1. Introduction

Traffic measurement provides valuable information for network security and network management, such as traffic accounting, load balancing, and anomaly detection [1–5], where measuring cardinality is an important task of traffic measurement. Cardinality measurement is a prerequisite for detecting supernodes, which have been paid extensive attention to by both academic and industrial organizations, despite many efforts in detecting supernodes over recent decades.The cardinality of a node indicates the number of distinct other nodes it communicates with. We consider two types of node cardinalities: source cardinality and destination cardinality, where source cardinality indicates the number of distinct destinations that a node connects to and destination cardinality indicates the number of distinct sources that a node is connected to [6]. Supernodes are defined as the nodes whose cardinalities are more than the predefined threshold, where nodes with large source cardinality are supersources and nodes with large destination cardinality are superdestinations. A packet stream in traffic measurement can be modeled as the set of two-tuple (s, d), where s is a source which consists of some source fields from packet header, such as source address, source port, and source address and source port pair, and d is a destination which consists of some destination fields from packet header, such as destination address, destination port, and destination address and destination port pair. The problem we solve in this paper is called supernode detection, which is to report nodes whose cardinalities exceed the predefined threshold in a measurement period. For each source s, the cardinality SC (s) of s is the number of distinct destination d. If SC (s) is more than the predefined threshold of source cardinalities, s is a supersource. Similarly, for each destination d, the cardinality DC (d) of d is the number of distinct source s, and d is a superdestination as DC (d) is more than the predefined threshold of destination cardinalities.There are three basic tasks in traffic measurement, that is, flow size, flow persistence, and flow cardinality. Flow size is the number of elements contained in packets with the same flow label, where elements may be the entire packets, bytes in payload, and the specific content in packets. Flow persistence is the number of timeslots in which its packets occur. Flow cardinality is the number of distinct flows with the same source or destination. The measurement of flow cardinality is different from that of flow size and flow persistence. Measuring flow cardinality only counts once when the same flow appears several times, whereas measuring flow size and flow persistence needs to count the number of occurrences of one same flow. Let the measurement period be 10 minutes. Considering a case where a number of 1000 distinct hosts send 100000 packets to a server in one measurement period and these packets constitute a flow whose flow label is server address, the flow size is obviously 100000. If these packets occur in 20 timeslots, its persistence is only 20 as the measurement period is divided into 100 timeslots. Meanwhile, its cardinality is 1000, which may indicate the beginning of an attack.Of particular importance are heavy hitters with large flow size, persistent items with large flow persistence, and supernodes with large flow cardinality. Heavy hitter detection has been extensively studied [7–14], and it has many applications, such as traffic accounting and load balancing. Persistent item detection is widely used in anomaly detection, stealthy network attack, etc. [15–18]. In this paper, we focus on supernode detection, which is a more challenging work since it is difficult to only count distinct flows appearing in one measurement period. It is important for many applications [19–24], such as DDoS attack detection and network scanning detection. For DDoS attack, the attacker makes use of infected hosts to launch a large number of requests to the targeted server in a short period, leading to consuming its resources on a large scale and making it unable to provide normal services, where the targeted server with large cardinality is a victim called superdestination. For network scanning, a malicious host attempts to connect to a large of distinct destination addresses or ports so as to discover the vulnerability in the network system, where the malicious host with large cardinality is an attacker called supersource.There have been many efforts on cardinality estimation. A simple method is to maintain distinct connections between any two hosts in the network [25, 26]. The method can measure the cardinality of each host accurately, but it is not practical to process massive network traffic due to large memory overhead [27, 28]. Sampling-based methods [29, 30] and data stream-based methods [31–33] are proposed to tackle the challenges caused by big network traffic. However, the estimation accuracy of sampling-based methods depends on the sampling rate, that is, they maintain a small number of distinct connections at the small sampling rate, but the accuracy of cardinality estimation decreases; on the contrary, the accuracy of cardinality estimation increases at the high sampling rate, but the memory overhead also increases. Data stream-based methods demonstrate great superiority on memory utilization and measurement accuracy, where various types of summary data structures have been widely used in traffic measurement due to the excellent compression efficiency and acceptable accuracy.However, the existing data stream-based methods still encounter challenges regarding supernode detection. First, when massive network traffic constantly generates at a high rate, they are difficult to store a large number of flows due to limited system resources on measurement points. Therefore, there need to be compact data structure by which network traffic is efficiently compressed. Second, they cannot well support supernode detection in the distributed monitoring systems, including distributed traffic collection and aggregation, centralized cardinality estimation, and supernode detection where distributed traffic collection and aggregation is to merge network traffic from multiple measurement points and centralized cardinality estimation and supernode detection are to identify supernodes based on estimated cardinality using the aggregated data structure. Since the connections established by supernodes may span the entire network, there may be a small number of its connections observed at one measurement point, while its aggregation from multiple measurement points will have a large cardinality. Hence, there is necessary a traffic collection approach, which can handle data in a distributed manner to measure node cardinalities and detect supernodes. Third, it is difficult to measure two types of node cardinalities simultaneously. Usually, they can only measure one type of node cardinality, since their summary data structures are two-dimensional bit arrays with the fixed row size or column size. Though we can measure various types of cardinalities using existing summary data structures, multiple instances of summary data structure need to be established by distinct keys, which is likely to cause excessive memory consumption. Besides, big network traffic brings great challenges to simultaneously measure two kinds of supernode cardinalities due to its one-pass requirement. Thus, it is essential to design a cardinality estimation approach for detecting supersources and destinations simultaneously. Fourth, they are unable to reconstruct labels of supernodes efficiently due to large calculation cost and unavoidable false positives and false negatives. Consequently, it is vital to reconstruct their labels for detecting supernodes efficiently and accurately.Likewise, we also confront some challenges in detecting supernodes. First of all, it is not easy to count cardinalities of each node from multiple measurement points, since a number of connections may cross the entire network and are not simply added. In addition, to simultaneously measure two types of cardinalities for supersources and destinations, source and destination addresses need to be compressed into summary data structure once. Finally, it is very difficult to efficiently recover labels of supernodes by only summary data structure without storing source and destination addresses. These challenges in detecting supernodes motivate our work.To solve the challenges, we propose a novel solution of supernode detection, and it obtains many flows whose cardinalities are larger than the predefined threshold at the end of one measurement period. The proposed method maps each flow to one bit of two-dimensional bit arrays, aggregates the generated two-dimensional bit arrays, estimates node cardinalities using probabilistic counting algorithm, reconstructs flow labels of supernode by inverse calculation, and detects supernodes. It mainly includes four steps: (i) update operation is used to extract flow labels (e.g., source and destination pairs) from packet stream and compress them into two-dimensional bit arrays using a group of hash functions. Then, the generated two-dimensional bit arrays are aggregated into one two-dimensional bit array with the same size at the end of each measurement period. It supports distributed traffic collection and centralized analysis. (ii) Estimation operation can be used to simultaneously measure source and destination cardinalities by only utilizing summary data structure once, and the minimal estimated cardinalities are taken as their estimations in order to mitigate the overestimation problem. (iii) Reconstruction operation is used to efficiently create supersources and destinations by inverse calculation without storing the information associated with sources and destinations. (iv) Detection operation is used to identify supersources and destinations under the guidance of abnormal rows and columns without searching the entire possible abnormal rows and columns through reconstruction operation. Our main contributions are summarized as follows.In this paper, we design a novel reversible and distributed summary data structure to be suitable for supernode detection with accuracy and memory size guarantees in the distributed monitoring system. It is able to effectively handle a large amount of network traffic arriving by a group of hash functions, simultaneously estimate two types of source and destination cardinalities by probabilistic counting method, and efficiently detect supersources and destinations by reconstructing flow labels of supernodes based on the aggregated summary data structure. We theoretically analyze the computation, space complexity, and estimation accuracy of our method. We conduct extensive experiments on real traffic traces from WIDE to evaluate the performance of our method. The experimental results demonstrate that our method achieves superior performance compared to state-of-the-art methods in accurately and efficiently detecting supersources and destinations.The rest of this paper is organized as follows: Section2 summarizes related works; Section 3 formulates the problem; Section 4 presents our method and its theoretical analysis; Section 5 evaluates performance and conducts experiments; Section 6 concludes this work.


## 2. Related Work

Network traffic measurement has been extensively applied in many fields, where the per-flow [34–39], heavy hitter [9–12], persistent item [16, 17], and supernode measurement [19–21] are still hot topics.Much prior work focuses on per-flow size and cardinality measurement. The task of per-flow size measurement is to count the number of elements in each flow, where flows can be TCP flows, UDP flows, or any other types defined according to the specific application requirements, and elements may be packets, bytes, or occurrences for certain events. The simple method allocates a counter for each flow to measure its size. When each packet arrives, the corresponding counter is increased by an integer, for instance, one at the packet level, the number of bytes at the byte level, or the number of accesses to websites. However, there are a large number of flows in high-speed networks, leading to enormous memory consumption. Therefore, many strategies to improve memory utilization were proposed, for instance, CAESAR [40] and virtual sketch [41], which make flows share counters or sketches to reduce memory consumption. Compared to per-flow size measurement, per-flow cardinality is difficult to be measured, since it counts the number of distinct elements in each flow. Per-flow size measurement is not able to be used in that of its cardinality directly. Most existing mechanisms were that distinct elements in each flow share the same bit vector, such as [42–44], which create a virtual bit vector for each flow, each bit of which is selected from the same bit vector using hash functions, so as to reduce memory cost.Heavy hitter measurement is to find flows whose sizes are more than the predefined threshold in the measurement period. The universal approach is to keep track of a small set of flows, trying to retain large flows in the set while replacing small ones with new flows, such as Lossy Counting [45] and Space Saving [46]. Persistent item measurement is to find flows that occur in many timeslots. Supernode measurement is to find flows whose cardinalities are more than the predefined threshold in the measurement period, and it has been used to find attackers or victims. Supernode detection can be treated as a special case of heavy hitter detection through identifying each source or destination with a large number of connections. However, the existing solutions [47] of heavy hitter detection cannot be directly used to solve the problems of supernode identification, since they are not able to filter repetitive connections in the data streams using counters allocated to each flow. We discuss the existing solutions to detect supernodes below.The traditional approaches maintain all distinct connections for each source or destination to detect DDoS attackers or targets in the measurement period. Although they can detect supernodes accurately, they cause great memory usage due to a large number of flows in high-speed networks.Flow sampling-based approaches are used to monitor a set of flows whose hash values are smaller than the predefined sampling rate [48]. Therefore, the flows with many connections are very probable to be sampled. Flow sampling-based approaches improve memory efficiency, but the accuracy of supernode identification depends on the sampling rate. Moreover, they maintain the sampled flows at high calculation and memory access cost.Data streaming-based approaches are used to detect supernodes. Most existing solutions usually design summary data structures that fit in fast memory, and they encode flow labels extracted from arriving packets to be stored in the summary data structures. However, they cannot recover supernodes merely using the summary data structures in fast memory due to their irreversibility. Sketches are one type of summary data structures, which are designed to detect supernodes and solve irreversibility [49]. Wang et al. [20] proposed a double connection degree sketch (DCDS) that is used to reconstruct host addresses with large cardinalities based on Chinese Remainder Theorem. Liu et al. [21] designed a vector bloom filter for supernode detection, which extracts several bits directly from flow labels. However, the calculation cost is obvious for large address space.Some network-wide measurement systems solve the problem of supernode detection [50, 51]. The proposed summary data structures can be a component of network-wide measurement systems.Besides, some variants of supernode detection are proposed in the literature [52, 53]. Zhou et al. [52] proposed the solution of persistent spread problem, which counts the number of distinct elements in each flow persistently occurring in the predefined measurement periods. Huang et al. [53] further solved the k-persistent spread problem, which measures the number of distinct elements in each flow appearing in at least k out of t measurement periods.


## 3. Problem Formulation

In this paper, we consider a distributed monitoring system composed of the controller and a set of monitors, as shown in Figure1. Let P = p1, p2, …, pt, … be a sequentially arriving packet stream generated by network traffic packets, where pt = (st, dt) is some fields of the tth packet, in which st and dt are the corresponding source and destination, respectively. Source or destination space consists of distinct source or destination over one measurement period, which are denoted as S and D. A source can be any combination of source fields in the packet header, such as source IP, source port, or their combination. Similarly, a destination can be any combination of destination fields in the packet header, such as destination IP, destination port, or their combination. The source and destination are determined according to the specific application requirement. In this work, we use the source and destination pair of one packet as its flow label. The whole measurement time is partitioned into many measurement periods T with equal length. At the beginning of one measurement period, the monitor extracts some fields from the arriving packets and compresses them into summary data structures. At the end of one measurement period, the monitor sends the generated data structures to the controller and resets data structures. Then, the controller aggregates the received data structures and detects supernodes.Figure 1
The distributed monitoring system.For any sources ∈ S, its cardinality is defined as the number of distinct destinations that s connects to in one measurement period. Similarly, for any destination d ∈ D, its cardinality is defined as the number of distinct sources that connects to d in one measurement period. Supernodes are divided into two types: supersources and superdestinations. Supersources or superdestinations are the hosts whose cardinality exceeds the predefined threshold θ1D1 or θ2D2 in one measurement period, where D1 or D2 denotes the sum of source or destination cardinality in one measurement and θ1 and θ2 are constants, 0 < θ1 and θ2 < 1. Supersources and superdestinations are expressed as(1)SS=s|SCs>θ1D1,s∈S,(2)SD=d|DCd>θ2D2,d∈D,where SC (s) indicates the cardinality of source s, DC (d) indicates the cardinality of destination d, D1 is computed as ∑s∈SSCs, and D2 is computed as ∑d∈DDCd.Supernode detection is widely used in many areas. For example, port scanning attacks are performed by trying to connect to numerous distinct destination addresses or ports for the existence of vulnerable services. In this case, the attacker with large cardinality is a supersource. Besides, Distributed Denial-of-Service (DDoS) attacks are launched by using a large number of connected devices as attackers to send a lot of requests to a victim such as server, so that legitimate users are not able to utilize its resources. Similarly, the victim with high cardinality is a superdestination.The goal of this work is to design a distributed monitoring framework which consists of updating module and detecting module. The former stores information associated with cardinalities of flows by summary data structures on each monitor. The latter aggregates the generated data structures from each monitor, estimates source and destination cardinality, reconstructs supersource and destination candidates, and identifies supersources and destinations on the controller. We perform theoretical analysis and performance evaluation.


## 4. Our Algorithm

In this section, we first introduce a novel summary data structure. Then, we define the main operations of our algorithm, containing updating and aggregating summary data structures, estimating cardinality, reconstructing sources and destinations, and detecting supersources and superdestinations. Theoretical analysis on updating complexity and estimation accuracy is performed. Next, we elaborate them in detail. The framework of our method is shown in Figure2.Figure 2
Framework of our method.


### 4.1. Data Structure

The summary data structure is denoted as follows:(3)B=B1,B2,…,BH.EachBi (1≤i ≤ H) is a two-dimensional bit array with the size of ni × mi, each bit of which is denoted as Bi[ j][k] (0 ≤ j ≤ ni − 1 and 0 ≤ k ≤ mi − 1), as shown in Figure 3. Each Bi (1 ≤ i ≤ H) with different sizes is used to store sufficient flow information and effectively trace attackers or victims. We use a row hash function fi and a column hash function hi to locate the index in each Bi (1 ≤ i ≤ H). The row and column hash functions are expressed as(4)fi:0,1,…,N−1⟶0,1,…,ni−1,(5)hi:0,1,…,M−1⟶0,1,…,ni−1,where N and M are the size of source space and destination space and ni and mi indicate the number of rows and columns in each Bi (1 ≤ i ≤ H).Figure 3
Data structure.To recover abnormal sources by simple computation, the row hash functionfi and column hash function hi are defined as(6)fix≡cimodni,1≤i≤H,(7)hix≡ci′modmi,1≤i≤H,where ci and ci′ are the values of modulus operation, n1, n2, …, nH are selected as pair-wise coprime integers to make the summary data structure reversible, and m1, m2, …, mH are also pair-wise coprime integers.The monitors use the same summary data structureB as the controller. Let the number of monitors be R. The summary data structure on the monitors is indicated as follows:(8)Br=B1r,B2r,…,BHr,r=1,2,…,R.


### 4.2. Updating Summary Data Structures

Updating operation is used to collect flow information from massive network traffic. At the beginning of one measurement period, all bits inB and each Br (1 ≤r ≤ R) are initialed. Then, each monitor updates the corresponding bit in each Bir1≤i≤H by the row hash function fi (1 ≤i ≤ H) and column hash function hi (1 ≤i ≤ H) when a packet arrives. At the end of one measurement period, the controller aggregates the generated summary data structures from each monitor. The updating process is described in Algorithm 1.Algorithm 1: Updating summary data structures.
Input: initialize Br = B1r,B2r,…,BHr, 1 ≤ r ≤ ROutput: the updated B = (B1, B2, …, BH)(1)
for each packet arriving at the monitor rdo(2)
extract its flow label (st, dt)(3)
computefi (st), 1 ≤ i ≤ H(4)
computehi (dt), 1 ≤ i ≤ H(5)
Birfisthidt ← 1, 1 ≤ i ≤ H, 1 ≤ r ≤ R(6)
end for(7)
Bi[j][k] ← Bi1jk⊕⋯⊕BiRjk, 1 ≤ i ≤ HWhen packet stream arrives sequentially, each monitor extracts its flow label (st, dt) from one packet and sets the corresponding bit in each Bir (1 ≤ i ≤ H, 1 ≤ r ≤ R) by the row hash function fi (st) (1 ≤ i ≤ H) and column hash function hi (dt) (1 ≤ i ≤ H) to one, which is denoted as follows:(9)Birfisthidt=1,1≤r≤R,1≤i≤H.At the end of one measurement period, each monitor sends the generated summary data structure to the controller. Then, the controller performs the bitwise-OR operations on the same bits in eachBir (1 ≤ i ≤ H and 1 ≤ r ≤ R). If one bit in Birjk (1 ≤ r ≤ R) is one, the corresponding bit in each Bi (1 ≤ i ≤ H) in B is set to one. The bitwise-OR operation is denoted as follows:(10)Bijk=Bi1jk⊕⋯⊕BiRjk,where Birjk (1 ≤ r ≤ R) indicates the corresponding bit in the ith bit array Bir in Br and ⊕ is a bitwise-OR operator.


### 4.3. Estimating Source and Destination Cardinality

Estimating operation is used to obtain an approximate estimation of cardinality based on the aggregated data structureB = (B1, B2, …, BH). Estimating operation is shown in Algorithm 2. For each source s ∈ S, we compute the hash value fi(s) of source s to locate the row in each Bi (1 ≤ i ≤ H) of B. The flows associated with source s are mapped to H rows Bi(s) = Bi [ fi (s)] [·] (1 ≤ i ≤ H). As a result, we obtain H bit vectors Bi (s) (1 ≤ i ≤ H) to store the cardinality information of source s. The source cardinality for each bit vector Bi (s) (1 ≤ i ≤ H) is estimated as (11) by the probabilistic counting algorithm.(11)SCis=−nilnUBisni,where UBis is the number of zero bits in each bit vector Bi(s) (1 ≤ i ≤ H).Algorithm 2: Estimating cardinality.
Input: the updated B = (B1, B2, …, BH)Output: the estimated source and destination cardinality(1)
for one source s ∈ Sdo(2)
computefi(s), 1 ≤ i ≤ H(3)
Bi(s) ⟵ Bi[ fi(s)][·], 1 ≤ i ≤ H(4)
compute the numberUBis of zero bits in each Bi (s)(5)
SCis ⟵ −nilnUBis/ni , 1 ≤ i ≤ H(6)
SCs ⟵ mini=1NSCis(7)
end for(8)
for one destination d ∈ Ddo(9)
computehi(d), 1 ≤ i ≤ H(10)
Bi (d) ⟵ Bi [·] [hi (d)], 1i ≤ i ≤ H(11)
compute the numberUBid of zero bits in each Bi (d)(12)
DCid ⟵ −milnUBid/mi, 1 ≤ i ≤ H(13)
DCd ⟵ mini=1NDCid(14)
end forIf other sources are not mapped to thefi (s)th row, the estimated source cardinality is very close to its real value. Actually, each Bi (s) (1 ≤ i ≤ H) may contain noise caused by other sources, so that the source cardinality may be overestimated. Therefore, we use the minimum value of estimated source cardinalities SCi (s) (1 ≤ i ≤ H) as its estimation [40], which is denoted as follows:(12)SCs=mini=1NSCis.Similarly, for each destinationd ∈ D, we calculate the hash value hi (d) of destination d to locate the column in each Bi (1 ≤ i ≤ H) of B. The flows associated with destination d are hashed to H bit vectors Bi (d) = Bi [·] [hi (d)] (1 ≤ i ≤ H). Therefore, the destination cardinality for each bit vector Bi (d) (1 ≤ i ≤ H) is estimated as (13) by the probabilistic counting algorithm.(13)DCid=−milnUBidmi,where UBid is the number of zero bits in each bit vector Bi (d) (1 ≤ i ≤ H).We use the minimum value of estimated destination cardinalities DCi (d) (1 ≤ i ≤ H) as its estimation, which is denoted as follows:(14)DCd=mini=1NDCid.


### 4.4. Reconstructing Sources and Destinations

Reconstructing operation is to recover abnormal sources and destinations. For ease of understanding, we first consider the simple situation. Suppose that there is only one abnormal row in eachBi (1 ≤ i ≤ H), which is denoted as ci (1 ≤ i ≤ H). According to the predefined row hash function fi, we can map a source s to the fi (s)th row in each Bi (1 ≤ i ≤ H), that is, fi (s) ≡ ci (mod mi) (1 ≤ i ≤ H). The problem of finding abnormal source s is converted to the solution of equations fi (s) ≡ ci (mod mi) (1 ≤ i ≤ H). Based on the Chinese Remainder Theorem (CRT) [44], the solutions are denoted as follows:(15)s≡∑i=1HMiMi−1cimodM,where M=m1m2⋯mH, Mi=M/mi, and MiMi−1≡1modmi.Similarly, we assume only one abnormal column in eachBi (1 ≤ i ≤ H), which is denoted as ci′ (1 ≤ i ≤ H). The problem of finding abnormal destination d is converted to the solution of equations hid≡ci′modni (1 ≤ i ≤ H). Therefore, the solutions are expressed as follows using the CRT:(16)d≡∑i=1HNiNi−1ci′modN,where N=n1n2⋯nH, Ni=N/ni, and NiNi−1≡1modni.For the general situation, we assumew abnormal rows in each Bi (1 ≤ i ≤ H). There are wH combinations consisting of one abnormal row or column in each Bi (1 ≤ i ≤ H). We use the CRT to solve the reversible problem for each combination. The entire abnormal sources or destinations are the union of solutions with each combination. However, the reverse calculations cause large computational overhead and increase false positive rate and false negative rate due to a few false combinations and hash collisions.We design a strategy to establish relations between two consecutive rows to which sources are mapped by row hash functions. Taking one sources as example, we obtain the row index fi (s) (1 ≤ i ≤ H) and the next row index fi + 1 (s) (1 ≤ i ≤ H − 1) using row hash function fi (1 ≤ i ≤ H). Therefore, the row index fi (s) is associated with the next row index fi + 1 (s) (1 ≤ i ≤ H − 1) by one hash table, that is, Ti [fi (s)] = fi + 1 (s) (1 ≤ i ≤ H − 1). However, different sources may be mapped to the same rows, leading to hash collisions. Assuming another source s´, Ti [fi (s)] = {fi + 1 (s), fi + 1 (s´)} (1 ≤ i ≤ H − 1). We conduct row combinations based on the hash table to reduce computational overhead and improve false positive rate and false negative rate. After that, we can accurately recover sources from row combinations using inverse calculation. Similarly, supposing that there are two destinations d and d´ mapped to the same columns, Ti [hi (d)] = {hi + 1 (d), hi + 1 (d´)} (1 ≤ i ≤ H − 1). Likewise, we conduct column combinations based on the hash table and recover destinations using inverse calculation to reduce computational overhead and improve false positive rate and false negative rate.As a result, it reduces false positive rate generated by false row combinations. Supersources and destinations show abnormal rows and columns at high probability.


### 4.5. Detecting Supersources and Superdestinations

For detecting supersources, we should identify abnormal rows generated by supersources at high probability in eachBi (1 ≤ i ≤ H). We view each row Bi [j] [·] (1 ≤ i ≤ H, 0 ≤ j ≤ ni − 1) as one bit vector. For each row Bi [j] [·] (1 ≤ i ≤ H, 0 ≤ j ≤ ni − 1), its cardinality is estimated as (17) by the probabilistic counting algorithm.(17)RCij=−nilnUBij⋅ni,where UBij⋅ is the number of zero bits in each row Bi [j] [·] (1 ≤ i ≤ H, 0 ≤ j ≤ ni − 1). If the cardinality RCij of each row Bi [j] [·] (1 ≤ i ≤ H, 0 ≤ j ≤ ni − ) is more than the predefined threshold αi which is the ratio of summation of source cardinalities in a measurement period, the row Bi [j] [·] (1 ≤ i ≤ H, 0 ≤ j ≤ ni − 1) is defined as one abnormal row. Similarly, for detecting superdestinations, we should identify abnormal columns caused by superdestinations at high probability in each Bi (1 ≤ i ≤ H). For each column Bi [·] [j] (1 ≤ i ≤ H, 0 ≤ j ≤ ni − ), its cardinality is estimated as (18) by the probabilistic counting algorithm.(18)CCij=−milnUBi⋅jmi,where UBi⋅j is the number of zero bits in each column Bi [·] [j] (1 ≤ i ≤ H, 0 ≤ j ≤ mi − 1). If the cardinality CCij of each column Bi [·] [j] (1 ≤ i ≤ H, 0 ≤ j ≤ mi − 1) is more than the predefined threshold βi which is the ratio of summation of destination cardinalities, the column Bi [·] [j] (1 ≤ i ≤ H, 0 ≤ j ≤ mi − 1) is defined as one abnormal column.After that, we obtain abnormal rows and columns in eachBi (1 ≤ i ≤ H). Therefore, supersources and superdestinations can be identified by reconstructing operation. The detection operation is shown in Algorithm 3.Algorithm 3: Detecting supersources and superdestinations.
Input: the updated B = (B1, B2, …, BH)Output: supersources and destinations(1)
fori = 1 to Hdo(2)
compute the numberUBij⋅ of zero bits in each Bi [ j] [·](3)
RCij ← −nilnUBij⋅/ni , 0 ≤ j ≤ ni − 1(4)
ifRCij > αithen(5)
the rowBi [j] [·] is an abnormal row(6)
end if(7)
compute the numberUBi⋅j of zero bits in each Bi [·] [j](8)
CCij ← −milnUBi⋅j/mi, 0 ≤ j ≤ mi − 1(9)
ifCCij > βithen(10)
the columnBi [·] [j] is an abnormal column(11)
end if(12)
end for(13)
Obtain supersources and destinations by inverse calculation


### 4.6. Theoretical Analysis

In the updating process, there need to be 2H hash calculations to determine the row and column in H two-dimensional bit arrays and 2H memory accesses for each packet. For the aggregation operation, it executes H + 2 memory accesses. Therefore, the time complexity to update a packet is O (H). For simplicity, we only consider the size of summary data structures. Each monitor needs miniH memory to store the related cardination information, and the controller needs the same memory size to detect supernodes. Since the distributed monitoring system consists of the controller and multiple monitors, the required memory space is mini (H + 1). Therefore, the space complexity is O (miniH).We only derive the deviation and standard error of source cardinality estimationSC^i in each two-dimensional bit array Bi (1 ≤ i ≤ H) according to the linear-time probabilistic counting algorithm as follows.LetVBis=UBis/ni; the estimation of source cardinality in each two-dimensional bit array Bi (1 ≤ i ≤ H) is denoted as follows:(19)SC^i=−nilnVBis.The Taylor series oflnVBis at VBis=e−SCi/ni is expressed as follows:(20)lnVBis=−SCini+VBis−e−SCi/nie−SCi/ni−12⋅VBis−e−SCi/ni2e−2SCi/ni+⋯.We take the first three items of (20), and the estimation of source cardinality in each two-dimensional bit array Bi (1 ≤ i ≤ H) is approximately represented as follows:(21)SC^i=niSCini−VBis−e−SCi/nie−SCi/ni+12⋅VBis−e−SCi/ni2e−2SCi/ni.The mathematical expectation of source cardinality estimation is denoted as follows:(22)ESC^i=SCi+12⋅niEVBis−e−SCi/ni2e−2SCi/ni.SinceEVBis−e−SCi/ni2=1/nie−SCi/ni1−1+SCi/nie−SCi/ni, we obtain (23)ESC^i=SCi+eSCi/ni−SCi/ni−12.The mathematical expectation of relative error is denoted as follows:(24)ESC^i−SCiSCi=eSCi/ni−SCi/ni−12SCi.Letri=SCi/niri=SCi/ni. Equation (24) is transformed as follows:(25)ESC^i−SCiSCi=eti−ti−12SCi.Figure4 illustrates the relationship among these parameters, namely, the source cardinality SCi, the ratio ti, and the relative error. When the source cardinality SCi is constant, we can see that the relative error decreases as the ratio ti decreases. Therefore, we can select the column number ni of summary data structure to obtain the required relative error for each SCi.Figure 4
The parameters SCi and ti impact on the relative error of source cardinality estimation.To derive the variance of the ratioSC^i/SCi, we take the first two items of (20) as the approximate estimation of source cardinality in each two-dimensional bit array Bi (1 ≤ i ≤ H), which is represented as follows:(26)SC^i=niSCini−VBis−e−SCi/nie−SCi/ni.The variance of the ratioSC^i/SCi is denoted as follows:(27)VarSC^iSCi=ni2VarVBis−e−SCi/niSCi2e−2SCi/ni.SinceVarVBis−e−SCi/ni=EVBis−e−SCi/ni2, we obtain (28) according to the previous formula:(28)VarSC^iSCi=nieSCi/ni−SCi/ni−1SCi2.Therefore, the standard error of the ratioSC^i/SCi is denoted as follows:(29)StdESC^iSCi=nieSCi/ni−ni−SCi1/2SCi.Letri=SCi/ni; equation (11) is transformed as follows:(30)StdESC^iSCi=nieti−ti−11/2SCi.Figure5 shows the relationship among these parameters, namely, the source cardinality SCi, the standard error of the ratio SC^i/SCi, and the ratio ti. When the source cardinality SCi is constant, we can also see that the standard error of the ratio SC^i/SCi decreases as the ratio ti decreases. Therefore, we can select the column number ni of summary data structure to obtain the required standard error for each SCi.Figure 5
The parameters SCi and ti impact on the standard error of the ratio SC^i/SCi.


## 4.1. Data Structure

The summary data structure is denoted as follows:(3)B=B1,B2,…,BH.EachBi (1≤i ≤ H) is a two-dimensional bit array with the size of ni × mi, each bit of which is denoted as Bi[ j][k] (0 ≤ j ≤ ni − 1 and 0 ≤ k ≤ mi − 1), as shown in Figure 3. Each Bi (1 ≤ i ≤ H) with different sizes is used to store sufficient flow information and effectively trace attackers or victims. We use a row hash function fi and a column hash function hi to locate the index in each Bi (1 ≤ i ≤ H). The row and column hash functions are expressed as(4)fi:0,1,…,N−1⟶0,1,…,ni−1,(5)hi:0,1,…,M−1⟶0,1,…,ni−1,where N and M are the size of source space and destination space and ni and mi indicate the number of rows and columns in each Bi (1 ≤ i ≤ H).Figure 3
Data structure.To recover abnormal sources by simple computation, the row hash functionfi and column hash function hi are defined as(6)fix≡cimodni,1≤i≤H,(7)hix≡ci′modmi,1≤i≤H,where ci and ci′ are the values of modulus operation, n1, n2, …, nH are selected as pair-wise coprime integers to make the summary data structure reversible, and m1, m2, …, mH are also pair-wise coprime integers.The monitors use the same summary data structureB as the controller. Let the number of monitors be R. The summary data structure on the monitors is indicated as follows:(8)Br=B1r,B2r,…,BHr,r=1,2,…,R.


## 4.2. Updating Summary Data Structures

Updating operation is used to collect flow information from massive network traffic. At the beginning of one measurement period, all bits inB and each Br (1 ≤r ≤ R) are initialed. Then, each monitor updates the corresponding bit in each Bir1≤i≤H by the row hash function fi (1 ≤i ≤ H) and column hash function hi (1 ≤i ≤ H) when a packet arrives. At the end of one measurement period, the controller aggregates the generated summary data structures from each monitor. The updating process is described in Algorithm 1.Algorithm 1: Updating summary data structures.
Input: initialize Br = B1r,B2r,…,BHr, 1 ≤ r ≤ ROutput: the updated B = (B1, B2, …, BH)(1)
for each packet arriving at the monitor rdo(2)
extract its flow label (st, dt)(3)
computefi (st), 1 ≤ i ≤ H(4)
computehi (dt), 1 ≤ i ≤ H(5)
Birfisthidt ← 1, 1 ≤ i ≤ H, 1 ≤ r ≤ R(6)
end for(7)
Bi[j][k] ← Bi1jk⊕⋯⊕BiRjk, 1 ≤ i ≤ HWhen packet stream arrives sequentially, each monitor extracts its flow label (st, dt) from one packet and sets the corresponding bit in each Bir (1 ≤ i ≤ H, 1 ≤ r ≤ R) by the row hash function fi (st) (1 ≤ i ≤ H) and column hash function hi (dt) (1 ≤ i ≤ H) to one, which is denoted as follows:(9)Birfisthidt=1,1≤r≤R,1≤i≤H.At the end of one measurement period, each monitor sends the generated summary data structure to the controller. Then, the controller performs the bitwise-OR operations on the same bits in eachBir (1 ≤ i ≤ H and 1 ≤ r ≤ R). If one bit in Birjk (1 ≤ r ≤ R) is one, the corresponding bit in each Bi (1 ≤ i ≤ H) in B is set to one. The bitwise-OR operation is denoted as follows:(10)Bijk=Bi1jk⊕⋯⊕BiRjk,where Birjk (1 ≤ r ≤ R) indicates the corresponding bit in the ith bit array Bir in Br and ⊕ is a bitwise-OR operator.


## 4.3. Estimating Source and Destination Cardinality

Estimating operation is used to obtain an approximate estimation of cardinality based on the aggregated data structureB = (B1, B2, …, BH). Estimating operation is shown in Algorithm 2. For each source s ∈ S, we compute the hash value fi(s) of source s to locate the row in each Bi (1 ≤ i ≤ H) of B. The flows associated with source s are mapped to H rows Bi(s) = Bi [ fi (s)] [·] (1 ≤ i ≤ H). As a result, we obtain H bit vectors Bi (s) (1 ≤ i ≤ H) to store the cardinality information of source s. The source cardinality for each bit vector Bi (s) (1 ≤ i ≤ H) is estimated as (11) by the probabilistic counting algorithm.(11)SCis=−nilnUBisni,where UBis is the number of zero bits in each bit vector Bi(s) (1 ≤ i ≤ H).Algorithm 2: Estimating cardinality.
Input: the updated B = (B1, B2, …, BH)Output: the estimated source and destination cardinality(1)
for one source s ∈ Sdo(2)
computefi(s), 1 ≤ i ≤ H(3)
Bi(s) ⟵ Bi[ fi(s)][·], 1 ≤ i ≤ H(4)
compute the numberUBis of zero bits in each Bi (s)(5)
SCis ⟵ −nilnUBis/ni , 1 ≤ i ≤ H(6)
SCs ⟵ mini=1NSCis(7)
end for(8)
for one destination d ∈ Ddo(9)
computehi(d), 1 ≤ i ≤ H(10)
Bi (d) ⟵ Bi [·] [hi (d)], 1i ≤ i ≤ H(11)
compute the numberUBid of zero bits in each Bi (d)(12)
DCid ⟵ −milnUBid/mi, 1 ≤ i ≤ H(13)
DCd ⟵ mini=1NDCid(14)
end forIf other sources are not mapped to thefi (s)th row, the estimated source cardinality is very close to its real value. Actually, each Bi (s) (1 ≤ i ≤ H) may contain noise caused by other sources, so that the source cardinality may be overestimated. Therefore, we use the minimum value of estimated source cardinalities SCi (s) (1 ≤ i ≤ H) as its estimation [40], which is denoted as follows:(12)SCs=mini=1NSCis.Similarly, for each destinationd ∈ D, we calculate the hash value hi (d) of destination d to locate the column in each Bi (1 ≤ i ≤ H) of B. The flows associated with destination d are hashed to H bit vectors Bi (d) = Bi [·] [hi (d)] (1 ≤ i ≤ H). Therefore, the destination cardinality for each bit vector Bi (d) (1 ≤ i ≤ H) is estimated as (13) by the probabilistic counting algorithm.(13)DCid=−milnUBidmi,where UBid is the number of zero bits in each bit vector Bi (d) (1 ≤ i ≤ H).We use the minimum value of estimated destination cardinalities DCi (d) (1 ≤ i ≤ H) as its estimation, which is denoted as follows:(14)DCd=mini=1NDCid.


## 4.4. Reconstructing Sources and Destinations

Reconstructing operation is to recover abnormal sources and destinations. For ease of understanding, we first consider the simple situation. Suppose that there is only one abnormal row in eachBi (1 ≤ i ≤ H), which is denoted as ci (1 ≤ i ≤ H). According to the predefined row hash function fi, we can map a source s to the fi (s)th row in each Bi (1 ≤ i ≤ H), that is, fi (s) ≡ ci (mod mi) (1 ≤ i ≤ H). The problem of finding abnormal source s is converted to the solution of equations fi (s) ≡ ci (mod mi) (1 ≤ i ≤ H). Based on the Chinese Remainder Theorem (CRT) [44], the solutions are denoted as follows:(15)s≡∑i=1HMiMi−1cimodM,where M=m1m2⋯mH, Mi=M/mi, and MiMi−1≡1modmi.Similarly, we assume only one abnormal column in eachBi (1 ≤ i ≤ H), which is denoted as ci′ (1 ≤ i ≤ H). The problem of finding abnormal destination d is converted to the solution of equations hid≡ci′modni (1 ≤ i ≤ H). Therefore, the solutions are expressed as follows using the CRT:(16)d≡∑i=1HNiNi−1ci′modN,where N=n1n2⋯nH, Ni=N/ni, and NiNi−1≡1modni.For the general situation, we assumew abnormal rows in each Bi (1 ≤ i ≤ H). There are wH combinations consisting of one abnormal row or column in each Bi (1 ≤ i ≤ H). We use the CRT to solve the reversible problem for each combination. The entire abnormal sources or destinations are the union of solutions with each combination. However, the reverse calculations cause large computational overhead and increase false positive rate and false negative rate due to a few false combinations and hash collisions.We design a strategy to establish relations between two consecutive rows to which sources are mapped by row hash functions. Taking one sources as example, we obtain the row index fi (s) (1 ≤ i ≤ H) and the next row index fi + 1 (s) (1 ≤ i ≤ H − 1) using row hash function fi (1 ≤ i ≤ H). Therefore, the row index fi (s) is associated with the next row index fi + 1 (s) (1 ≤ i ≤ H − 1) by one hash table, that is, Ti [fi (s)] = fi + 1 (s) (1 ≤ i ≤ H − 1). However, different sources may be mapped to the same rows, leading to hash collisions. Assuming another source s´, Ti [fi (s)] = {fi + 1 (s), fi + 1 (s´)} (1 ≤ i ≤ H − 1). We conduct row combinations based on the hash table to reduce computational overhead and improve false positive rate and false negative rate. After that, we can accurately recover sources from row combinations using inverse calculation. Similarly, supposing that there are two destinations d and d´ mapped to the same columns, Ti [hi (d)] = {hi + 1 (d), hi + 1 (d´)} (1 ≤ i ≤ H − 1). Likewise, we conduct column combinations based on the hash table and recover destinations using inverse calculation to reduce computational overhead and improve false positive rate and false negative rate.As a result, it reduces false positive rate generated by false row combinations. Supersources and destinations show abnormal rows and columns at high probability.


## 4.5. Detecting Supersources and Superdestinations

For detecting supersources, we should identify abnormal rows generated by supersources at high probability in eachBi (1 ≤ i ≤ H). We view each row Bi [j] [·] (1 ≤ i ≤ H, 0 ≤ j ≤ ni − 1) as one bit vector. For each row Bi [j] [·] (1 ≤ i ≤ H, 0 ≤ j ≤ ni − 1), its cardinality is estimated as (17) by the probabilistic counting algorithm.(17)RCij=−nilnUBij⋅ni,where UBij⋅ is the number of zero bits in each row Bi [j] [·] (1 ≤ i ≤ H, 0 ≤ j ≤ ni − 1). If the cardinality RCij of each row Bi [j] [·] (1 ≤ i ≤ H, 0 ≤ j ≤ ni − ) is more than the predefined threshold αi which is the ratio of summation of source cardinalities in a measurement period, the row Bi [j] [·] (1 ≤ i ≤ H, 0 ≤ j ≤ ni − 1) is defined as one abnormal row. Similarly, for detecting superdestinations, we should identify abnormal columns caused by superdestinations at high probability in each Bi (1 ≤ i ≤ H). For each column Bi [·] [j] (1 ≤ i ≤ H, 0 ≤ j ≤ ni − ), its cardinality is estimated as (18) by the probabilistic counting algorithm.(18)CCij=−milnUBi⋅jmi,where UBi⋅j is the number of zero bits in each column Bi [·] [j] (1 ≤ i ≤ H, 0 ≤ j ≤ mi − 1). If the cardinality CCij of each column Bi [·] [j] (1 ≤ i ≤ H, 0 ≤ j ≤ mi − 1) is more than the predefined threshold βi which is the ratio of summation of destination cardinalities, the column Bi [·] [j] (1 ≤ i ≤ H, 0 ≤ j ≤ mi − 1) is defined as one abnormal column.After that, we obtain abnormal rows and columns in eachBi (1 ≤ i ≤ H). Therefore, supersources and superdestinations can be identified by reconstructing operation. The detection operation is shown in Algorithm 3.Algorithm 3: Detecting supersources and superdestinations.
Input: the updated B = (B1, B2, …, BH)Output: supersources and destinations(1)
fori = 1 to Hdo(2)
compute the numberUBij⋅ of zero bits in each Bi [ j] [·](3)
RCij ← −nilnUBij⋅/ni , 0 ≤ j ≤ ni − 1(4)
ifRCij > αithen(5)
the rowBi [j] [·] is an abnormal row(6)
end if(7)
compute the numberUBi⋅j of zero bits in each Bi [·] [j](8)
CCij ← −milnUBi⋅j/mi, 0 ≤ j ≤ mi − 1(9)
ifCCij > βithen(10)
the columnBi [·] [j] is an abnormal column(11)
end if(12)
end for(13)
Obtain supersources and destinations by inverse calculation


## 4.6. Theoretical Analysis

In the updating process, there need to be 2H hash calculations to determine the row and column in H two-dimensional bit arrays and 2H memory accesses for each packet. For the aggregation operation, it executes H + 2 memory accesses. Therefore, the time complexity to update a packet is O (H). For simplicity, we only consider the size of summary data structures. Each monitor needs miniH memory to store the related cardination information, and the controller needs the same memory size to detect supernodes. Since the distributed monitoring system consists of the controller and multiple monitors, the required memory space is mini (H + 1). Therefore, the space complexity is O (miniH).We only derive the deviation and standard error of source cardinality estimationSC^i in each two-dimensional bit array Bi (1 ≤ i ≤ H) according to the linear-time probabilistic counting algorithm as follows.LetVBis=UBis/ni; the estimation of source cardinality in each two-dimensional bit array Bi (1 ≤ i ≤ H) is denoted as follows:(19)SC^i=−nilnVBis.The Taylor series oflnVBis at VBis=e−SCi/ni is expressed as follows:(20)lnVBis=−SCini+VBis−e−SCi/nie−SCi/ni−12⋅VBis−e−SCi/ni2e−2SCi/ni+⋯.We take the first three items of (20), and the estimation of source cardinality in each two-dimensional bit array Bi (1 ≤ i ≤ H) is approximately represented as follows:(21)SC^i=niSCini−VBis−e−SCi/nie−SCi/ni+12⋅VBis−e−SCi/ni2e−2SCi/ni.The mathematical expectation of source cardinality estimation is denoted as follows:(22)ESC^i=SCi+12⋅niEVBis−e−SCi/ni2e−2SCi/ni.SinceEVBis−e−SCi/ni2=1/nie−SCi/ni1−1+SCi/nie−SCi/ni, we obtain (23)ESC^i=SCi+eSCi/ni−SCi/ni−12.The mathematical expectation of relative error is denoted as follows:(24)ESC^i−SCiSCi=eSCi/ni−SCi/ni−12SCi.Letri=SCi/niri=SCi/ni. Equation (24) is transformed as follows:(25)ESC^i−SCiSCi=eti−ti−12SCi.Figure4 illustrates the relationship among these parameters, namely, the source cardinality SCi, the ratio ti, and the relative error. When the source cardinality SCi is constant, we can see that the relative error decreases as the ratio ti decreases. Therefore, we can select the column number ni of summary data structure to obtain the required relative error for each SCi.Figure 4
The parameters SCi and ti impact on the relative error of source cardinality estimation.To derive the variance of the ratioSC^i/SCi, we take the first two items of (20) as the approximate estimation of source cardinality in each two-dimensional bit array Bi (1 ≤ i ≤ H), which is represented as follows:(26)SC^i=niSCini−VBis−e−SCi/nie−SCi/ni.The variance of the ratioSC^i/SCi is denoted as follows:(27)VarSC^iSCi=ni2VarVBis−e−SCi/niSCi2e−2SCi/ni.SinceVarVBis−e−SCi/ni=EVBis−e−SCi/ni2, we obtain (28) according to the previous formula:(28)VarSC^iSCi=nieSCi/ni−SCi/ni−1SCi2.Therefore, the standard error of the ratioSC^i/SCi is denoted as follows:(29)StdESC^iSCi=nieSCi/ni−ni−SCi1/2SCi.Letri=SCi/ni; equation (11) is transformed as follows:(30)StdESC^iSCi=nieti−ti−11/2SCi.Figure5 shows the relationship among these parameters, namely, the source cardinality SCi, the standard error of the ratio SC^i/SCi, and the ratio ti. When the source cardinality SCi is constant, we can also see that the standard error of the ratio SC^i/SCi decreases as the ratio ti decreases. Therefore, we can select the column number ni of summary data structure to obtain the required standard error for each SCi.Figure 5
The parameters SCi and ti impact on the standard error of the ratio SC^i/SCi.


## 5. Experiment and Evaluation

In this section, we evaluate the performance of our algorithm in comparison with other ones. The experiments are extensively conducted on real traffic data. All algorithms are implemented using C++ on a server with Intel E-2224 CPU and 32 GB memory. The influence of parameters on the algorithm performance is discussed.


### 5.1. Datasets

To evaluate the performance of our algorithm, we select the traffic trace in the first three minutes from traffic traces without packet header over 15 minutes published by MAWI [54], which are divided into three traffic traces with one minute called data1, data2, and data3, respectively. Table 1 shows the statistical information of three traffic traces used in our experiments, where #packet denotes the number of packets in the traffic trace, |SIP| denotes the number of distinct source IP addresses (SIP for short), |DIP| denotes the number of distinct destination IP addresses (DIP for short), and |(SIP, DIP)| denotes the number of distinct source IP address and destination IP address pairs. As shown in Table 1, the average number of packets, source IP addresses, destination IP addresses, and source IP address and destination IP address pairs in three traffic traces is 2.4M, 39K, 212K, and 676K.Table 1
Statistics of datasets.
Dataset#packet|SIP||DIP||(SIP, DIP)|data12.4M39K212K658Kdata22.4M39K212K660Kdata32.3M39K215K711KIn this paper, we use SIP and DIP as sources and destinations, respectively. Figure6 shows the cardinality distribution in three traffic traces, where the x-coordinates indicate the logarithm of source or destination cardinality and the y-coordinates indicate the logarithm of number of sources or destinations. We can see that the number of sources or destinations decreases as source or destination cardinality increases. As shown in Figures 6(a), 6(c), and 6(e), the sources with low cardinality are obviously more than ones with high cardinality. The number of sources whose cardinality is less than 10 is about 93 percent of overall sources. As shown in Figures 6(b), 6(d), and 6(f), we obtain similar results, that is, the destinations with low cardinality are apparently more than ones with high cardinality. The destinations whose cardinality is less than 10 are about 98 percent of overall destinations. The cardinality approximatively obeys the heavy-tailed distribution.Figure 6
Cardinality distribution. (a) Distribution of source cardinality under data1. (b) Distribution of destination cardinality under data1. (c) Distribution of source cardinality under data2. (d) Distribution of destination cardinality under data2. (e) Distribution of source cardinality under data3. (f) Distribution of destination cardinality under data3.
(a)(b)(c)(d)(e)(f)In the experiments, we assume that there are three monitors in distributed monitoring systems, each of which processes the 20-second traffic trace for each traffic trace. For detecting supersources and destinations, we evaluate the performance of our algorithm compared with the compact spread estimator (CSE) [42], double connection degree sketch (DCDS) [20], and SpreadSketch (SS) [49] in terms of estimation accuracy, detection precision, and memory cost. The CSE constructs a virtual bit vector from the shared one-dimensional bit array for each host by a group of hash functions. It can provide good accuracy in a small memory. The DCDS constructs multiple two-dimensional bit arrays, only sets several bits selected in a bit array for each coming packet by a group of hash functions, and then reconstructs abnormal hosts by simple inverse calculation. The SS constructs an invertible sketch that is formed by the combination of count-min sketch and multiresolution bitmap, and multiple sketches can be merged to provide a network-wide measurement view for recovering superspreaders and their estimated fan-outs by simple computations and small memory.We also need to know true supersources and destinations obtained using three traffic traces in advance. Table2 shows the number of true supersources and destinations when the predefined thresholds are 0.1 and 0.01 percent of the overall source and destination cardinality for three traffic traces, where |SS| and |SD| denote the number of true supersources and destinations separately.Table 2
True supersources and destinations.
Dataset|SS||SD|data19198data29172data38377


### 5.2. Influence of Parameters on Estimation Accuracy

Our algorithm has three parameters,H, mi, and ni, where H denotes the number of hash functions and ni and mi denote the number of rows and columns in two-dimensional bit arrays Bi (1 ≤ i ≤ H). Updating, estimating, and reconstructing processes use hash functions, and the parameter H impacts the processing time. H changes from 2 to 6. Both ni and mi determine the size of memory consumed by our algorithm. According to the coupon collection issue, the source and destination cardinality can be accurately estimated when they are less than nilnni and milnmi. In the experiments, source IP addresses and destination IP addresses are used as sources and destinations. Therefore, ni is a prime from 400 to 800 and mi is also a prime from 3000 to 7000.We evaluate the accuracy of cardinality estimation by the average relative error (ARE for short), which is the mean value of difference between the true cardinality of hosts and their cardinality estimated divided by the true cardinality. ARE is expressed as follows:(31)ARE=1n∑i=1nc^i−cici,where ci denotes the true cardinality of host i, c^i denotes the estimated cardinality of host i, and n indicates the number of distinct hosts. The smaller the ARE is, the more accurate the estimated cardinality is.Figure7 shows the influence on the performance of our algorithm under different traffic traces. As shown in Figure 7(a), we can see that the ARE of our algorithm decreases as H increases. As shown in Figures 7(b) and 7(c), we obtain similar results. Since distinct sources and destinations are mapped to two-dimensional bit arrays by many hash functions, hash collisions are significantly reduced. Besides, the estimation error caused by hash collisions is reduced because the minimum estimation in each two-dimensional bit array is used as the cardinality estimation.Figure 7
The influence of parameter H on cardinality estimation under different traffic traces. (a) data1. (b) data2. (c) data3.
(a)(b)(c)Figure8 shows the influence of parameter ni on the estimation accuracy under different traffic traces. As shown in Figure 8(a), we can see that the ARE obviously decreases as ni varies from 400 to 600 and slowly decreases as ni changes from 600 to 800. As shown in Figures 8(b) and 8(c), we obtain similar results. When other parameters are fixed, the size of memory consumed increases as ni increases. Therefore, the probability that distinct sources are mapped to the same bits in two-dimensional bit arrays are reduced to improve the estimation accuracy.Figure 8
The influence of parameterni on cardinality estimation under different traffic traces. (a) data1. (b) data2. (c) data3.
(a)(b)(c)Based on the above analysis, we select (H) = 4, ni = 600, and mi = 5000 in the experiments.Figure9 shows the influence of parameter mi on the estimation accuracy under different traffic traces. As shown in Figure 9(a), we can see that the ARE obviously decreases as mi varies from 3000 to 5000 and slowly decreases as mi changes from 5000 to 7000 using data1. As shown in Figures 9(b) and9(c), we obtain the similar results. Since the size of memory consumed increases, the probability of hash collisions is reduced. Therefore, we improve the cardinality estimation accuracy as mi increases.Figure 9
The influence of parametermi on cardinality estimation under different traffic traces. (a) data1. (b) data2. (c) data3.
(a)(b)(c)


### 5.3. Estimation Accuracy

Figure10 shows the cardinality estimation accuracy under three traffic traces for CSE, DCDS, SS, and our method called RSD. We can see that RSD has the minimum ARE of source cardinality estimation for each traffic trace from Figure 10(a). Similarly, RSD also has the minimum ARE of destination cardinality estimation for each traffic trace (Figure 10(b)). CSE, DCDS, SS, and RSD approximately estimate the cardinality of hosts using probabilistic methods, and their estimation accuracy depends on the memory utilization. RSD can simultaneously and accurately estimate the cardinality of sources and destinations based on the same summary data structure generated by the controller in comparison with CSE, DCDS, and SS. However, the deviation between the estimated cardinality and the theoretical value still exists due to hash collisions.Figure 10
Cardinality estimation accuracy. (a) Source cardinality. (b) Destination cardinality.
(a)(b)


### 5.4. Detection Precision

We evaluate the performance of our algorithm called RSD compared with CSE, DCDS, and SS under different traffic traces. The reconstructed sources or destinations may not be true supersources or destinations by false combinations of abnormal rows or columns. Therefore, we use the false positive rate and false negative rate to evaluate the detection precision of four algorithms. The false positive rate (FPR for short) is the number of not corrected identified supernodes divided by the number of supernodes identified. The false negative rate (FNR) is the number of not identified supernodes divided by the number of true supernodes. The FPR and FNR are expressed as(32)FPR=B−AB,(33)FNR=A−BA,where A is the set of true supernodes and B is the set of identified supernodes.Figure11 shows the detection precision of three algorithms under data1. The FPR and FNR of detecting supersources are shown in Figures 11(a) and 11(b). We can see that RSD has the lowest FPR and FNR for supersources in comparison with DCDS, CSE, and SS. The FPR changes from 0.04 to 0.15 and the FNR varies from 0.06 to 0.25 as the threshold θ1 increases. The FPR and FNR of detecting superdestinations are shown in Figures 11(c) and 11(d). We can see that RSD has the lowest FPR and FNR for superdestinations compared to DCDS, CSE, and SS. The FPR changes from 0.05 to 0.18 and the FNR varies from 0.08 to 0.24 as the threshold θ2 increases. Although there are some false positive and false negative due to the reconstruction of supersources and destinations using false combinations of abnormal rows and columns in two-dimensional bit arrays, RSD mitigates wrong reconstruction of supersources and destinations using the extra hash table that conducts the combinations of abnormal rows and columns. In general, RSD can simultaneously identify supersources and destinations based on their accurate cardinality estimation, and it outperforms DCDS, CSE, and SS in terms of FPR and FNR. Figure 12 shows the detection precision of three algorithms under data2. As shown in Figures 11(a)–11(d), we can obtain similar results.Figure 11
Detection precision under data1. (a) False positive rate of supersources. (b) False negative rate of supersources. (c) False positive rate of superdestinations. (d) False negative rate of superdestinations.
(a)(b)(c)(d)Figure 12
Detection precision under data2. (a) False positive rate of supersources. (b) False negative rate of supersources. (c) False positive rate of superdestinations. (d) False negative rate of superdestinations.
(a)(b)(c)(d)


### 5.5. Memory Cost

Figure13 shows the memory cost of four algorithms under different traffic traces. The memory cost of our algorithm called RSD includes the summary data structure, arrays, and hash table. The memory cost slightly increases when the extra bit arrays and hash table are created in the updating and reconstruction process. For simplicity, we treat the size of summary data structure as the memory cost. CSE, DCDS, and SS need to establish the data structure twice to simultaneously measure supersources and destinations, leading to high memory cost. Besides, DCDS uses the additional two-dimensional bit arrays to reduce the FPR caused by wrong combinations of abnormal rows and columns. CSE can only measure the cardinalities of supersources and destinations by constructing multiple virtual one-dimensional bit arrays and not reconstruct supersources and destinations. SS can measure the cardinalities of candidate supersources and destinations through building two-dimensional sketches, each bucket of which consists of a multiresolution bitmap, a label field, and a register. However, RSD can reduce the memory cost in supersource and destination detection by constructing row and column hash functions. In brief, the memory cost of RSD is superior to that of the three algorithms CSE, DCDS, and SS.Figure 13
Memory cost under different traffic traces.


## 5.1. Datasets

To evaluate the performance of our algorithm, we select the traffic trace in the first three minutes from traffic traces without packet header over 15 minutes published by MAWI [54], which are divided into three traffic traces with one minute called data1, data2, and data3, respectively. Table 1 shows the statistical information of three traffic traces used in our experiments, where #packet denotes the number of packets in the traffic trace, |SIP| denotes the number of distinct source IP addresses (SIP for short), |DIP| denotes the number of distinct destination IP addresses (DIP for short), and |(SIP, DIP)| denotes the number of distinct source IP address and destination IP address pairs. As shown in Table 1, the average number of packets, source IP addresses, destination IP addresses, and source IP address and destination IP address pairs in three traffic traces is 2.4M, 39K, 212K, and 676K.Table 1
Statistics of datasets.
Dataset#packet|SIP||DIP||(SIP, DIP)|data12.4M39K212K658Kdata22.4M39K212K660Kdata32.3M39K215K711KIn this paper, we use SIP and DIP as sources and destinations, respectively. Figure6 shows the cardinality distribution in three traffic traces, where the x-coordinates indicate the logarithm of source or destination cardinality and the y-coordinates indicate the logarithm of number of sources or destinations. We can see that the number of sources or destinations decreases as source or destination cardinality increases. As shown in Figures 6(a), 6(c), and 6(e), the sources with low cardinality are obviously more than ones with high cardinality. The number of sources whose cardinality is less than 10 is about 93 percent of overall sources. As shown in Figures 6(b), 6(d), and 6(f), we obtain similar results, that is, the destinations with low cardinality are apparently more than ones with high cardinality. The destinations whose cardinality is less than 10 are about 98 percent of overall destinations. The cardinality approximatively obeys the heavy-tailed distribution.Figure 6
Cardinality distribution. (a) Distribution of source cardinality under data1. (b) Distribution of destination cardinality under data1. (c) Distribution of source cardinality under data2. (d) Distribution of destination cardinality under data2. (e) Distribution of source cardinality under data3. (f) Distribution of destination cardinality under data3.
(a)(b)(c)(d)(e)(f)In the experiments, we assume that there are three monitors in distributed monitoring systems, each of which processes the 20-second traffic trace for each traffic trace. For detecting supersources and destinations, we evaluate the performance of our algorithm compared with the compact spread estimator (CSE) [42], double connection degree sketch (DCDS) [20], and SpreadSketch (SS) [49] in terms of estimation accuracy, detection precision, and memory cost. The CSE constructs a virtual bit vector from the shared one-dimensional bit array for each host by a group of hash functions. It can provide good accuracy in a small memory. The DCDS constructs multiple two-dimensional bit arrays, only sets several bits selected in a bit array for each coming packet by a group of hash functions, and then reconstructs abnormal hosts by simple inverse calculation. The SS constructs an invertible sketch that is formed by the combination of count-min sketch and multiresolution bitmap, and multiple sketches can be merged to provide a network-wide measurement view for recovering superspreaders and their estimated fan-outs by simple computations and small memory.We also need to know true supersources and destinations obtained using three traffic traces in advance. Table2 shows the number of true supersources and destinations when the predefined thresholds are 0.1 and 0.01 percent of the overall source and destination cardinality for three traffic traces, where |SS| and |SD| denote the number of true supersources and destinations separately.Table 2
True supersources and destinations.
Dataset|SS||SD|data19198data29172data38377


## 5.2. Influence of Parameters on Estimation Accuracy

Our algorithm has three parameters,H, mi, and ni, where H denotes the number of hash functions and ni and mi denote the number of rows and columns in two-dimensional bit arrays Bi (1 ≤ i ≤ H). Updating, estimating, and reconstructing processes use hash functions, and the parameter H impacts the processing time. H changes from 2 to 6. Both ni and mi determine the size of memory consumed by our algorithm. According to the coupon collection issue, the source and destination cardinality can be accurately estimated when they are less than nilnni and milnmi. In the experiments, source IP addresses and destination IP addresses are used as sources and destinations. Therefore, ni is a prime from 400 to 800 and mi is also a prime from 3000 to 7000.We evaluate the accuracy of cardinality estimation by the average relative error (ARE for short), which is the mean value of difference between the true cardinality of hosts and their cardinality estimated divided by the true cardinality. ARE is expressed as follows:(31)ARE=1n∑i=1nc^i−cici,where ci denotes the true cardinality of host i, c^i denotes the estimated cardinality of host i, and n indicates the number of distinct hosts. The smaller the ARE is, the more accurate the estimated cardinality is.Figure7 shows the influence on the performance of our algorithm under different traffic traces. As shown in Figure 7(a), we can see that the ARE of our algorithm decreases as H increases. As shown in Figures 7(b) and 7(c), we obtain similar results. Since distinct sources and destinations are mapped to two-dimensional bit arrays by many hash functions, hash collisions are significantly reduced. Besides, the estimation error caused by hash collisions is reduced because the minimum estimation in each two-dimensional bit array is used as the cardinality estimation.Figure 7
The influence of parameter H on cardinality estimation under different traffic traces. (a) data1. (b) data2. (c) data3.
(a)(b)(c)Figure8 shows the influence of parameter ni on the estimation accuracy under different traffic traces. As shown in Figure 8(a), we can see that the ARE obviously decreases as ni varies from 400 to 600 and slowly decreases as ni changes from 600 to 800. As shown in Figures 8(b) and 8(c), we obtain similar results. When other parameters are fixed, the size of memory consumed increases as ni increases. Therefore, the probability that distinct sources are mapped to the same bits in two-dimensional bit arrays are reduced to improve the estimation accuracy.Figure 8
The influence of parameterni on cardinality estimation under different traffic traces. (a) data1. (b) data2. (c) data3.
(a)(b)(c)Based on the above analysis, we select (H) = 4, ni = 600, and mi = 5000 in the experiments.Figure9 shows the influence of parameter mi on the estimation accuracy under different traffic traces. As shown in Figure 9(a), we can see that the ARE obviously decreases as mi varies from 3000 to 5000 and slowly decreases as mi changes from 5000 to 7000 using data1. As shown in Figures 9(b) and9(c), we obtain the similar results. Since the size of memory consumed increases, the probability of hash collisions is reduced. Therefore, we improve the cardinality estimation accuracy as mi increases.Figure 9
The influence of parametermi on cardinality estimation under different traffic traces. (a) data1. (b) data2. (c) data3.
(a)(b)(c)


## 5.3. Estimation Accuracy

Figure10 shows the cardinality estimation accuracy under three traffic traces for CSE, DCDS, SS, and our method called RSD. We can see that RSD has the minimum ARE of source cardinality estimation for each traffic trace from Figure 10(a). Similarly, RSD also has the minimum ARE of destination cardinality estimation for each traffic trace (Figure 10(b)). CSE, DCDS, SS, and RSD approximately estimate the cardinality of hosts using probabilistic methods, and their estimation accuracy depends on the memory utilization. RSD can simultaneously and accurately estimate the cardinality of sources and destinations based on the same summary data structure generated by the controller in comparison with CSE, DCDS, and SS. However, the deviation between the estimated cardinality and the theoretical value still exists due to hash collisions.Figure 10
Cardinality estimation accuracy. (a) Source cardinality. (b) Destination cardinality.
(a)(b)


## 5.4. Detection Precision

We evaluate the performance of our algorithm called RSD compared with CSE, DCDS, and SS under different traffic traces. The reconstructed sources or destinations may not be true supersources or destinations by false combinations of abnormal rows or columns. Therefore, we use the false positive rate and false negative rate to evaluate the detection precision of four algorithms. The false positive rate (FPR for short) is the number of not corrected identified supernodes divided by the number of supernodes identified. The false negative rate (FNR) is the number of not identified supernodes divided by the number of true supernodes. The FPR and FNR are expressed as(32)FPR=B−AB,(33)FNR=A−BA,where A is the set of true supernodes and B is the set of identified supernodes.Figure11 shows the detection precision of three algorithms under data1. The FPR and FNR of detecting supersources are shown in Figures 11(a) and 11(b). We can see that RSD has the lowest FPR and FNR for supersources in comparison with DCDS, CSE, and SS. The FPR changes from 0.04 to 0.15 and the FNR varies from 0.06 to 0.25 as the threshold θ1 increases. The FPR and FNR of detecting superdestinations are shown in Figures 11(c) and 11(d). We can see that RSD has the lowest FPR and FNR for superdestinations compared to DCDS, CSE, and SS. The FPR changes from 0.05 to 0.18 and the FNR varies from 0.08 to 0.24 as the threshold θ2 increases. Although there are some false positive and false negative due to the reconstruction of supersources and destinations using false combinations of abnormal rows and columns in two-dimensional bit arrays, RSD mitigates wrong reconstruction of supersources and destinations using the extra hash table that conducts the combinations of abnormal rows and columns. In general, RSD can simultaneously identify supersources and destinations based on their accurate cardinality estimation, and it outperforms DCDS, CSE, and SS in terms of FPR and FNR. Figure 12 shows the detection precision of three algorithms under data2. As shown in Figures 11(a)–11(d), we can obtain similar results.Figure 11
Detection precision under data1. (a) False positive rate of supersources. (b) False negative rate of supersources. (c) False positive rate of superdestinations. (d) False negative rate of superdestinations.
(a)(b)(c)(d)Figure 12
Detection precision under data2. (a) False positive rate of supersources. (b) False negative rate of supersources. (c) False positive rate of superdestinations. (d) False negative rate of superdestinations.
(a)(b)(c)(d)


## 5.5. Memory Cost

Figure13 shows the memory cost of four algorithms under different traffic traces. The memory cost of our algorithm called RSD includes the summary data structure, arrays, and hash table. The memory cost slightly increases when the extra bit arrays and hash table are created in the updating and reconstruction process. For simplicity, we treat the size of summary data structure as the memory cost. CSE, DCDS, and SS need to establish the data structure twice to simultaneously measure supersources and destinations, leading to high memory cost. Besides, DCDS uses the additional two-dimensional bit arrays to reduce the FPR caused by wrong combinations of abnormal rows and columns. CSE can only measure the cardinalities of supersources and destinations by constructing multiple virtual one-dimensional bit arrays and not reconstruct supersources and destinations. SS can measure the cardinalities of candidate supersources and destinations through building two-dimensional sketches, each bucket of which consists of a multiresolution bitmap, a label field, and a register. However, RSD can reduce the memory cost in supersource and destination detection by constructing row and column hash functions. In brief, the memory cost of RSD is superior to that of the three algorithms CSE, DCDS, and SS.Figure 13
Memory cost under different traffic traces.


## 6. Conclusion

In this paper, we propose a novel method for detecting supernodes in the distributed monitoring systems. It constructs two-dimensional reversible summary data structures to collect information associated with cardinalities according to the specific application requirements. At the end of each measurement period, the generated summary data structures are aggregated to produce the summary data structure with the same size. On the basis of the aggregated summary data structure, it estimates node cardinalities and reconstructs supersources and destinations. Compared to other algorithms, the proposed method can simultaneously measure two types of node cardinalities using the same summary data structures, detect supersources and destinations efficiently, and reconstruct labels of supersources and destinations with small computational complexity. We perform theoretical analysis and conduct extensive experiments on real traffic traces. The experimental results illustrate that our method has good estimation accuracy, detection precision, and memory cost. In the future, we will deploy our method and study superchanger detection problem in the practical distributed monitoring systems and study variants of supernode detection.



---

*Source: 3271433-2022-06-30.xml*