Programmable Data Plane Switch based Heavy Hitter Flow Detection using Packet-Count and Packet-Size features Adarsha K. Sasidhar1 , Krishna M. Sivalingam1 (Fellow, IEEE) and Gauravdeep Shami2 (Member, IEEE), Marc Lyonnais2 (Senior Member, IEEE) and Rodney Wilson2 1 Department of Computer Science and Engineering, Indian Institute of Technology Madras, Chennai, India 2 External Research, Global Research and Development, Ciena Corporation, Ottawa, Canada Email: {cs22s017@cse, skrishnam@cse}.iitm.ac.in, {gshami,mlyonnai,rwilson}@ciena.com
arXiv:2609.05998v1 [cs.NI] 5 Sep 2026
Abstract In data networks carrying large numbers of flows, Heavy Hitters (HHs) or Elephant flows are the flows exceeding predetermined thresholds (e.g. number of packets or bytes) in a given time window. Such HH flows need to be handled differently in order to minimize their impact on other smaller flows. HH detection techniques have been shown to be more effective when implemented in programmable data plane switches. In recent work, it was shown that the inter-packet gap can be used to identify heavy hitters. Such schemes use a limited-size hash table for storing flow state information and using this for the detection. However, when hash collisions occur, it is possible that a valid HH flow in the table can be replaced by a non-HH flow resulting in missing detection of HH flows. To address this problem, this paper incorporates a flow’s medium-term Packet Count (PC) feature. In order to limit the packet count field size in the hash table, counting is done only till hash collision occurs so as to reduce the range of values to be stored and thus, the required number of bits. Also, another flow’s medium-term feature, Packet Size (PS) is incorporated independently. The proposed scheme has been implemented in the P4 language and tested on Intel Tofino hardware. Performance evaluation has been performed using CAIDA and MAWI-based real-life traffic traces. The results show that in several scenarios cases, we can significantly reduce the False Negatives for HHs by using the packet count data effectively and efficiently. Index Terms Software Defined Networking, P4 language, Heavy Hitter detection, Programmable Data Plane devices, Flow Classification, Hardware Switches, Intel Tofino Switch
1
Programmable Data Plane Switch based Heavy Hitter Flow Detection using Packet-Count and Packet-Size features I. I NTRODUCTION In data networks, multiple flows exist simultaneously, where a flow is defined as a long-term data session between a source and a destination. The term “Heavy Hitters (HHs)” has been used to denote long-standing flows with large traffic volumes [1]. In Data Center Networks (DCNs), these flows are classified into two types and are referred to as “elephant” flows and mice flows [2]. In order to improve network utilization and flow-level performance, it is necessary to classify flows based on their traffic volume. This has applications in data mining, information retrieval, databases, security and so on. Several earlier works to detect HHs used flow counters (raw counters or some optimized data structures), which divide the network stream into a fixed number of time slots [3]. HHs are defined as flows consuming more than a fraction of link capacity in a particular interval. This may lead to inaccuracies since the traffic trends from earlier time slots were not considered. Many of the current flow classification schemes use counterbased approaches and accumulation-based approaches. In counter-based approaches for HH detection [4], part of the traffic information is recorded in a table where the flow’s table location is obtained by hashing some of the flow’s header fields. The hash tables are limited in size due to memory constraints. When there is a hash collision due to multiple flows mapping to the same table location, the smallest flow is replaced by the new flow. Here, when the memory space is limited, heavy flows may be mistakenly replaced by small ones. In accumulation-based approaches, a special data structure (e.g. Sketch [3]) is used. This hashes each flow to the corresponding memory entries in a table and records the accumulated information of all traffic in real time. It has lower memory consumption and faster update speed and detection. When multiple flows hash to the same memory entry (called a bucket), the sketches resolve the hash collision by keeping the accumulated value of flow information. Due to the accumulation of traffic values over time, small flows may be incorrectly identified as heavy ones. Both approaches require a large memory capacity to store flow information and also require fast feedback. This limits the statistical information size, resulting in identifying small flows as large ones, causing an overestimation problem [5]. Some approaches have been proposed to use machine learning (ML) techniques for HH detection ( [6]). These techniques require the control plane’s significant involvement, increasing the switch-controller latency. Also, it requires additional training time and the availability of datasets. Implementing ML techniques on the switch is difficult or not possible due
to limited set of operations available on the switch and thus require approximations. In some recent works, various flow state features such as packet size distribution, byte count, and flow duration were considered for HH detection [1], [6]. The per-flow Inter-Packet Gap (IPG) metric was used for HH detection in the research work titled ‘HH-IPG’ [7]. We consider HH-IPG as the baseline approach. In this paper, we further improve HH detection performance by combining IPG and packet counters. In HH-IPG [7], a table T with m slots and an associated hash function h() are used to obtain and store the weighted Inter-Packet Gap (IPG) of the flows. Each slot consists of four fields: flow-id, last noted weighted IPG (IPGω−1,i ), last noted f l,i timestamp (TSf ), a dimensionless metric for the flow to store flow’s throughput state (τfi ). Due to the limited hash table size, hash collisions occur. When this happens, the weighted IPG will increase, and if its value is higher than a pre-defined threshold, the previous entry will be replaced by the new entry. Here, some HH flows may not be detected if only IPG metric is used. In order to reduce the number of false negatives and increase the accuracy, we propose to include the Packet Count (PC) metric along with IPG. PC is defined as the number of packets belonging to each flow and is used only when hash collisions occur. The PC value will be reset to zero after each hash overwriting. The advantage of checking PC only during collision is that the smaller number of bits will suffice to hold the count value. This paper contributes to the flow classification problem in Programmable Data Plane (PDP) devices. The key contributions of this paper are: (i) developed three versions of the proposed IPG+PC approach; (ii) detailed heavy hitter detection algorithm and P4 pipeline, improving the ones proposed in [7]; (iii) implementation in Intel Tofino [8] switch and a python based simulation model; (iv) analysis with real-life traffic traces in the simulation model; (v) comparison of our approach with the baseline work and the double hashing; (vi) use of the packet count value for deciding heavy hitters during hash collision rather than after regular time intervals as in traditional approaches; (vii) analysis of the trade-off of dynamic memory requirement versus algorithm performance by the proposed approach. An implementation-based study using the MAWI20 dataset ( [9]) shows that considering PC till hash collision along with IPG reduces the number of false negatives for the HHs by up to 12%. Specifically, on 10:00 AM packet trace with a time window of 5 seconds, considering PC and IPG reduced the false negatives by 12.35% compared with using only the
2
IPG metric. Also, for this trace, the F1 score for the baseline approach was 0.84276, which is improved to 0.875843 in version 1, to 0.881888 in version 2, and to 0.912665 in version 3 of the proposed approach. Similarly, the study using the CAIDA19 dataset [10] shows that considering PC along with IPG reduced false negatives by 4.18% compared to using only the IPG metric. Below are the further inclusions and analysis performed in addition to our previous work ( [11]): (i) Section II-A provides a relavant background for our work; (ii) Section III-D provides the proposed algorithm; (iii) Section IV-D discusses finetuning algorithm to optimize the results as per requirements of the specific application; (iv) Section IV-E: analysis of the effect of hash function being used in the proposed algorithm; (v) Section IV-F: observation of dynamic memory requirements of the proposed approach; (vi) Section IV-G: comparison of our approach with double hashing; (vii) Section IV-H analysis on CAIDA dataset; (viii) Section IV-I: another feature packet size is used in place of packet count feature to perform classification along with IPG. II. BACKGROUND This section presents the relevant background and preceding research. A. SDN, PDP switches, P4 language, PISA The router or switch is a network device that can forward packets from one device to another. In traditional switches, the data plane refers to the tasks related to receiving a message (e.g., forwarding process of network packets), and the control plane refers to the actions that control the data plane (e.g., routing process). The control plane determines how the network should behave, while the data plane implements that behavior on individual packets [12]. Traditional switches have hard-wired functions as they are made of Application-Specific Integrated Circuits (ASICs). Hence, these switches can be configured but are not programmable in the field. To address this, a new controller-based network type called Software Defined Networking (SDN) is introduced, which introduced the idea of separation of the control plane and data plane. SDN is a network operational model that uses controllers that centralize some network functions and give operators programmatic control over their networks, making the networks’ control plane programmable and flexible. The OpenFlow standard was introduced with SDN to provide switch abstraction by standardizing what a switch does based on commonly used switches. In OpenFlow, the control plane is separated from the networking devices and implemented in a remote software-based controller. OpenFlow provides a standard way for the controller to communicate with the switches (e.g., to populate packet forwarding rules on the switch). OpenFlow is implemented using ASICs and supports only a fixed set of protocols. The data plane switches became less intelligent and cheaper. Also, the controller-switch communication resulted in increased latency. In OpenFlow, the controller can be programmed to change the switch behavior. However, the data plane switches are not
programmable; this led to the development of Programmable Data Plane (PDP) switches. PDP switches can perform some computations inside the data plane switch itself. This reduces the switch-controller latency as they do not entirely depend on the controller. In PDP switches, the behavior of the switch (e.g., how to process packets) can be defined by network operators via software, unlike traditional switches where it is hardwired in underlying ASICs. It also allows rapid deployment as the necessary changes are made using software updates rather than designing new hardware. PDP switches were developed on Protocol Independent Switch Architecture (PISA) ( [13]) whose components are a programmable parser, match action pipeline, a programmable deparser, ingress and egress pipelines. The programmable parser parses the headers and extracts the header values, which are passed to the ingress block to look up in the match table for a match. On a match, the associated set of actions is executed and the packet is sent to the egress block, which has another match-action pipeline. After egress, the packet is sent to the deparser. Deparser attaches all the headers to the packet payload and it sends packet to the egress port. A high-level programming language like P4 is introduced to program the PDP switches, making it easier for network operators to add new functionality to existing routers and switches. P4 (Programming Protocol-Independent Packet Processors) is a data plane programming language that specifies how packets should be processed in the network [14]. With P4, instead of acting as mere forwarding entities, the data plane in switches can process a packet and perform necessary action. P4 supports basic data types, arithmetic operations (addition, subtraction), bit-wise operations (left shift, right shift, and, or, not), logical operations (logical and, logical or), and ternary operation. P4 does not have looping statements and floating point numbers to ensure packet processing happens at the line rate. Similarly, conditional statements cannot be used in the action blocks of P4 language. The match-action pipeline is the only way to implement any logic. A P4 target is the specific hardware or software platform that interprets and executes the P4 code to perform packet processing tasks. The P4 targets can be either software based (e.g., simulated environments like Behavioral Model v2 (BMv2), p4c-behavioral or software switches like Open vSwitch (OVS)) or hardware based (e.g., Barefoot Tofino and Tofino 2, NetFPGA SUME, Pensando Capri, AMD Pensando second generation ELBA, NVIDIA Mellanox Spectrum). P4 target we used is Intel Tofino ( [8]) which is the P4-programmable ethernet switch ASICs built using PISA. B. Limitations in Programmable Data Plane (PDP) switch implementations While PDP switches like Tofino offer better performance and flexibility for SDN and network automation, they have some limitations as they need to achieve line rate switching speed. Ideally, we expect flexibility with respect to what the switch can do in any PDP switch, giving the network operators control over how the switch behaves by writing P4 code and modifying the switch behavior. The traditional
3
switches, which are made up of ASICs, were able to achieve line rate, but they offered no flexibility. On the other hand, programmable switches such as Tofino, offer flexibility by providing programmatic control over the network achieving line rate speeds but have many limitations. P4 does not have floating point numbers, and it does not supports loops, pointers, or dynamic memory allocation. The Tofino switch has a fixed number of match-action pipeline stages (hence, no loops), and it supports up to a specified number of states in the Finite State Machines (FSMs) supported in the ingress parser. The P4 language for Tofino supports only limited operations and reduced domain specific instruction set. It does not support multiplications and divisions for the register actions, because of which bit operations supported in recent targets like Tofino have to be used to approximate these operations. However, the comparison operations are limited to a fixed number of bits. Also, there are access limitations to memory registers; the register can be accessed once per packet lifetime in the Tofino switch ASIC. To resolve this, packet resubmission can be used along with the packet metadata to differentiate the actual packets from the resubmitted ones. However, the packet resubmission may raise concerns with respect to increased congestion and throughput. The Tofino switch also has a limited stateful memory (MB’s of SRAM in Tofino). All the logic from any proposed algorithms has to be implemented using a match action pipeline. PDP switches have been considered for solving different problems using hardware-based algorithm implementations [7], [15]–[17]. C. HH detection In data networks, network traffic flow consists of long lived flows or elephant flows or heavy hitters (HHs) and short lived flows or mice flows. The elephant flows are the flows exceeding the pre-determined threshold (wrt. number of packets or bytes) in a time window. Also, In DCNs, the majority of flows are small, with only a few kilobytes (KB) in size. From the analysis of DCN flows, it was shown that 99% of flows are smaller than 100 megabytes (MB). However, more than 90% of bytes are in flows between 100 MB and 1 gigabyte (GB) [18]. Even the observations from Peer-to-Peer (P2P) systems also show that the distribution of flow sizes is highly skewed, with less than 10% of the end host Internet Protocol (IP) addresses contributing around 99% of the total traffic volume [19]. Hence, mice flows are numerous, where as elephant flows being less in quantity contribute to most of the traffic. Elephant flows throttle the mice flows and other elephant flows by consuming a disproportionate amount of buffer and link capacity. This results in either a drop or delay in the mice packets. Despite this, the Equal Cost Multi-Path (ECMP) routing used in DCNs uses a five-tuple to hash and decide a route, and it treats the elephants and mice the same and does not consider the flow characteristics while routing. However, flow type must be predicted and handled differently. This could help balance the load, improve link utilization, and identify congestion and security attacks (e.g., Distributed Denial-of-
Service (DDoS) detection). Many network management applications like accounting, network capacity planning (e.g., to improve link utilization), load balancing, caching, congestion control (by dynamically scheduling HHs), anomaly detection, etc, and networking measurements benefit from it. In traditional network devices, HH detection algorithms run in the switch/router’s control plane, not the data plane, as the computational power is higher in the control plane. With the advent of the Programmable Data Plane (PDP) devices and the P4 (Programming Protocol-Independent Packet Processors) language, HH detection can be done on the data plane itself. One popular P4 target is the Intel Tofino [8] chip, which improves efficiency and performance of HH detection [1], [20]; as the data plane is faster, closer to packets and hence reduces the control plane latency. D. Inter-Packet Gap (IPG) metric The work presented in [7] (referred to as HH-IPG) proposes an algorithm and a P4 pipeline design using per-flow Inter Packet Gap (IPG) metric to detect Heavy Hitters (HH) entirely in the data plane. The IPG metric is considered by observing that the smaller the flow’s IPG, the number of packets in the flow in a time window would be more and hence heavier the flow and higher its throughput. Since the flow’s features value were directly used in decision making, involvement of control plane for HH detection is much lower when compared with the algorithms that use ML based techniques such as [21]. The implementation is based on a hash table (T ) with m entries and a corresponding hash function (h). The hash function inputs are the following packet header fields: source IP address, destination IP address, source port and destination port. The output is the hash table slot where information regarding the given mapped flow is maintained. Each entry in the table stores the weighted IPG value for this flow along with its calculated throughput state (explained later). If the throughput is above a certain threshold, then a flow is classified as a heavy-hitter. Since the number of entries in T is limited, it is possible to have hash collisions when two different flows map to the same slot in T . In such cases, a HH flow in the hash table might be replaced by a new flow which is not HH leading to a false negative. It is shown that failing to detect a HH flow can impact the behavior of network-control applications, such as load balancing in [7]. Hence, reducing the number of false negatives is an important requirement. Based on preliminary studies of the HH-IPG scheme on some data sets ( [9], [10], we observed that some of the heavy hitters were indeed being replaced by newer flows. In order to avoid this problem, another flow feature, namely, the flow’s packet count (PC) was also measured. For the MAWI20 dataset [9] and using the simulation code of [7], Table I presents a snapshot the packet count values for the flows stored in the table at a given time instant. The values represent the sequence of PC values printed whenever hash collision was observed. As seen, there are some flows which have high packet counts (the values shown in bold at Table I). Our hypothesis is that these flows with high PC values are potential HHs and should not be replaced in the hash table. This observation provided
4
the motivation to consider the PC metric in addition to the IPG metric, till hash collision for improving HH detection performance. The next section presents the details of the proposed scheme. TABLE I: Packet Count values when Hash Collision occurs 35, 13, 61, 19, 3073, 13, 9, 29, 7, 22, 15, 19, 32, 13, 17, 7, 11, 22, 22, 11, 22, 59, 13, 10, 22, 5, 13, 14, 22, 13, 17, 16, 7, 10926, 21, 93, 2, 15, 22, 2, 307, 6, 22, 6, 3, 23, 167, 11, ...., 7, 70, 1326, 7, 15, 22, 22, 5, 40, 5074, ...., 38, 5, 21, 11, 27, 83, 22, 5, 1415, 16, 5, 31, 709, 22, 9, 7, 22, 19, 15, 24, 22, 15, 383, 13,
III. AUGMENTING DETECTION USING PACKET C OUNT The proposed approach is implemented by adding an extra field Packet Count(PC) in the data structure used to keep track of flows in the HH-IPG paper [7].
ω−1 IPGω + (1 − α) IPGcf f = α IPGf
(1)
Here, IPGω−1 is the last noted weighted IPG, α ∈ [0, 1] is f the relative weight factor, and IPGcf is the current IPG which is the difference between last noted timestamp and the current timestamp. Also, small timeslot Tωt is used to update τfi . The timestamp wraps around after every Tωt . More details about Tωt , τth , α, and also how to choose them can be found in [7]. In the proposed approach, we use the flow’s IPG feature for HH decision making as done in [7], augmented with the packet counter (PC) feature. If τfi ≥ τth for a flow, then switch reports to controller that this flow is HH. In addition, at each hash collision, we check the packet counter (PC) value. If the PC is higher than the threshold PCth , the given flow is also reported to the controller as HHs. In traditional packet counter based approaches, the HH decision is positive if the current PC value is greater than the threshold over some time duration or if this flow is among the Top-k PC valued flows. In this work, we use the PC value when hash collision occurs. B. Hash Table insertion
A. Hash Table structure Let P = {P1 , P2 , P3 , . . . , PN } be a network stream with N packets and let F = {f1 , f2 , f3 , . . . , fM } be the set of network flows. There are M flows (fi ) in the network in P . For each flow f ∈ F , the throughput state is denoted by τf . A pre-defined threshold τth is set by the network administrator. A flow is defined as a heavy hitter if τf ≥ τth .
flow id
h(.) h(.) h(.)
897
3857
2
39
, 888, 3867, 2, 40
5279
7319
1
31
, 5289, 7319, 1, 31
9772
8798
1
2037
, 2037
,
, 0, 1
.....
, 9772, 6574,
h(.)
flow id
203
6798
0
8
Fig. 1: One example slot in the Data Structure. To store each flow’s details, a hash table T is used with m slots and an associated hash function h(.), as shown in Fig. 1. Each slot consists of five fields: flow id, last noted weighted IPG (IPGω−1,i ), last noted timestamp (TSl,i f f ), a dimensionless metric for the flow to store flow’s throughput state (τfi ), and the Packet Count (PCif ); where i ∈ {1,2,...,m}. Here, f indicates the flow to which the entry belongs, i indicates the slot number. Also, in IPGω−1,i , ω − 1 means previous noted weighted IPG f for considered slot and weight. To insert flow state values in T, the corresponding flow identifier (id) is required. This is defined by four fields: source IP address, destination IP address, source port and destination port. The hash function h(.) is applied on fid to determine the slot in T for a given flow. Each time the existing flow is replaced by another flow during hash collision, the PC value will be reset to 1. The τfi is used to decide whether the flow is HH or not. If τfi ≥ τth for a flow, then algorithm considers flow as HH. τth is the threshold considered for the decision; threshold for IPG is considered to be 10, 000µs. The weighted IPG of flow f (as defined in [7]) is computed as:
h(.) h(.)
203
6798
0
8
9931
8918
1
56
,
, 2763, 295, 1, 9
,
,
, 0, 1
Fig. 2: Hash table updates. During insertion into the hash table, there can be three possible cases for each incoming packet, as described below. An example of three possible cases is shown in Fig. 2. These are suitably modified from the original scheme ( [7]). Case 1: The flow’s hashed slot value is empty, implying that this is the first packet of the particular flow. The flow values (flow id of the current flow, IPGinit , TSc , 0, 1) are inserted in this slot. This initializes the flow id to hashed value of current packet’s four fields: source IP, destination IP, source port and destination port. Next, IPGω−1,i is set to f IPGinit . Here, IPGinit is the initial IPG value which is equal to IPGth given by (PacketSize/HHth ) [7]). Other fields set are: timestamp field to the current time stamp TSc , τfi to 0, and packet count to 1. For example, in Fig. 2, when the first packet of the flow f7 enters the programmable switch, the hash function is used to find its slot. Here it gets hashed to an empty slot. So we insert
5
f7 , IPGinit , TSc , 0, 1 into the slot to perform the specified initialization. Case 2: There is an entry in the slot hashed to, with the same flow id. Here, we increment the packet count by 1, update timestamp, and calculate the IPG and update IPGω−1,i based f on this IPG as per Equation 1. Also, τfi is updated by one, l,i only when the current time stamp, TSc < TSl,i f , where TSf is the last noted timestamp. If this condition is not true, then τfi is not changed. For example, in Fig. 2, when packet of f2 arrives, the slot already has an entry with the same flow id. PC is incremented to 9 from 8. Since TSc < TSl,i f , it indicates that timestamp has been wrapped around. Hence, τfi is updated with 1 and current IPG is calculated as IPGcf = TSc + Twt − TSl,i f . Then, c IPGω−1,i is calculated using this IPG in Equation 1 and f f l,i updated at the slot. In case of f1 , TSc < TSf fails. So τfi is not changed and IPGcf = TSc − TSl,i f . Equation 1 gives ω−1,i IPGf to be updated at the slot. Then, PC is incremented. Case 3: There is already an entry in the hashed slot but with a different flow id. This is the case where hash collision occurs. Here, if IPGω−1,i ≤ IPGth , then IPGω−1,i is linearly f f increased by adding a predefined and table size dependent constant k [7], and the packet count is incremented by 1. If IPGω−1,i > IPGth , we check if the packet count of the f existing entry exceeds the predefined threshold of PC. If yes, it will be marked as a Heavy Hitter by changing τf value. Otherwise, the existing entry will be replaced by new entry. In Fig. 2, consider f3 , here as IPGω−1,i ≤ IPGth holds, f ω−1,i IPGf is linearly increased by adding 10, as k=10 is considered. For f4 and f5 , since the condition IPGω−1,i ≤ IPGth f i fails, condition PCf > PCth is tested for an existing entry. For f5 , since the PC exceeds the threshold, f8 is marked as HH by changing τfi value to τth . However, for f4 , PCif > PCth fails. Hence, f4 will replace the existing entry. C. P4 implementation The proposed P4 pipeline implementation of the proposed HH detection scheme is shown in Fig. 3. The pipeline design of [7] has been improved by adding the stages required for the inclusion of PC. There is an access limitation to registers in the P4 ASIC. In a packet’s lifetime, the register can be accessed only once. In the proposed pipeline, the register is accessed to check the flow ID initially. Hence, to re-access the register to replace the entry, packet re-submission is used [7]. Based on how the stored Packet Count (PC) value is used in decision making, three versions of the algorithm have been defined. Version 1 (V1): During hash collision, if an existing current entry is being replaced, the packet count value of the existing flow in table is compared with packet count threshold. If the packet count value is greater, then the flow is considered as HH and reported to the controller. In Fig. 3, this is shown by the red decision making box. Version 2 (V2): For an existing flow (with no hash collision), it is classified as HH only if the flow’s packet count has crossed the packet count threshold and IPG has crossed the
IPG threshold. In Fig. 3, this is shown by the green decision making box. Version 3 (V3): This combines both the above versions, by considering both IPG and PC features. Thus, both collision and collision-less cases are considered. D. Proposed Algorithm The proposed algorithm is presented in Algorithm 1. The algorithm is built by improving the one presented in [7]. Here, input Pj is a packet where 1 ≤ j ≤ N of flow f , m is the total number of slots in the table [7], P Cfi is packet count of flow f in index i of hash table. Algorithm 1 Proposed algorithm for HH detection using Inter Packet Gap and Packet Count. Input: Packet Pj , m. 1: Get table index i from h(f), where i belongs to (1,2,...m). 2: if flag=false then 3: f lag ← true i i 4: fi , IPGω−1,i , TSl,i f f , τf , PCf = f, IPGinit , TSc ,0,1; 5: else if f = fi then 6: PCif = PCif + 1 7: if TSc > TSl,i f then 8: IPGcf = TSc − TSl,i f ; ω−1,i 9: IPGf = α.IPGω−1,i + (1 − α).IPGcf ; f l,i 10: TSf = TSc 11: else 12: IPGcf = TSc + Twt − TSl,i f ; ω−1,i ω−1,i 13: IPGf = α.IPGf + (1 − α).IPGcf ; 14: TSl,i f = TSc 15: match on IPGω−1,i , set metadata.tau as an acf tion; 16: τfi = τfi + metadata.tau; 17: end if 18: else 19: if IPGω−1,i <= IPGth then f ω−1,i 20: IPGf = IPGω−1,i + k; f 21: else 22: if PCif > PCth then 23: Set τfi to value above threshold to mark flow as HH. 24: end if i i 25: fi , IPGω−1,i , TSl,i f f , τf , PCf = f, IPGinit , TSc ,0,1; 26: end if 27: end if
IV. I MPLEMENTATION - BASED A NALYSIS In this section, we discuss various analysis performed on our proposed solution along with the obtained results. The publicly available dataset MAWI20 [9] is used in the performance evaluation. The Measurement and Analysis on the WIDE Internet (MAWI) traces are 15 minutes long and are collected from the backbone a Japanese academic network. Each trace
6
True
Extract flow id f & table index (i) flag:false
Increment Increase
, PC Update for slot i
True
True
Save Ingress TSc as metadata
,
,
Update
Insert new entry
if
if
False
Packet out
False
False
Update
Ingress Deparser
flag:true
if
Ingress Parser
Packet in
if
False
Compute
Increment PC, Compute
True
Resubmit; Insert new entry for f
Re-Submission
Fig. 3: The proposed P4 pipeline for HH detection.
has over 500 million packets. The traces are split into 1, 5, and 10 second chunks for the analysis. Also, the proposed algorithm is evaluated on the publicly available CAIDA dataset [10]. CAIDA’s passive traces dataset contains real data traces collected from high-speed monitors on a commercial backbone link. In the CAIDA data set, specifically, the restricted access 2019 CAIDA data consists of more than 2 billion packets that span 1 hour. We used a fraction of this dataset, consisting of 29 million packets, in our analysis.
Control Plane P4 Runtime
Push rules
Data Plane Packet In
P4 Code
,
and forwarding ut tO cke
H)
(H
Pa
Pa ck
et O ut
(N
on H
H)
Fig. 4: High level system architecture. The high level system architecture overview of placement of our algorithm is shown in Fig. 4. Every time a packet enters the switch, the data plane where the proposed algorithm resides will make the decision whether the packet belongs to a Heavy Hitter flow or not. The necessary tables to make these decisions will be pushed by the control plane using the Equation 1. The proposed approach has been implemented in P4 code for the target Intel Tofino1 WEDGE-100B switch, setup in the International Center for Advanced Internet Research (iCAIR), Northwestern University. Initially, during network setup, the control plane pushes the normal packet forwarding rules and
pushes the τ values for the corresponding IPG values [7]. We compiled the proposed algorithm on Tofino using P4 Studio SDE 9.13.4. Using the P4 Insight tool, it was seen that the algorithm used 11 stages and 385 clock cycles, out of which 217 cycles are due to the latency introduced by the proposed algorithm. The Tofino hardware resources used by the proposed algorithm is presented in the Table II. These are the worst case figures among all 11 stages. In addition, storage for the hash table was required: this had m memory slots with each slot containing a 32-bit flow ID, 16-bit weighted IPG, 16-bit last timestamp value, 8-bit τ value, (72 bits similar to [7]) and an extra Packet Count value of l bits. The l value depends on the threshold for Packet Count; for example, if threshold is 1024, l is 10 bits. Hence total memory occupied is m ∗ (72 + l) bits. The resource requirements of the proposed algorithm are thus seen to be well within the resource availability and hence we can additionally implement normal switching and custom functions based on requirement along with proposed algorithm. For the detailed performance studies provided below, the mechanisms has been implemented using a standalone Pythonbased program on a machine with 12-core, 12th Gen Intel® CoreTM i7-12700 CPU up to 4.9 GHz and 16 GB DDR5 memory. The artifacts for both targets are made available in our Github repository [22]. The standard machine learning (ML) evaluation metrics for heavy hitter detection algorithms were considered as in [7], [5]. These include : True Positive (TP) : Count of correctly classified Heavy Hitter(HH) flows. False Positive (FP): Count of non-Heavy Hitter flows detected as Heavy hitter. FN (False Negative): Count of Heavy Hitters detected as Non-HH.
7
TABLE II: Tofino Resources used by the proposed algorithm Resource Exact Match Input Crossbar Hash Distribution Unit Exact Match Result Bus Action Data Bus Bytes
Max usage (%) 10.2 50.0 25.0 6.3
Precision: Ratio of true heavy flows found over all reported flows. Precision quantifies how many of the instances the model labeled as HH were actually a HH. A high precision means that when the model predicts a flow as HH, it is likely to be a HH. TP (2) Pr = TP + FP Recall: Ratio of true heavy flows found over all real heavy flows. Recall indicates how many of the actual HHs the model correctly identified. A high recall means that the model is good at finding all relevant cases. TP (3) TP + FN F1 score: Harmonic average of Precision and Recall. The F1 score balances precision and recall. A high F1 score suggests a good balance between correctly identifying HHs and not missing any. 2 ∗ R ∗ Pr F1 = (4) R + Pr A new metric called revenue was defined as: R = |TP| − |FP| − |FN| to capture the number of false negatives. As mentioned earlier, the objective is to reduce the number of false negatives, i.e. missing detection of heavy hitter flows that can negatively impact overall network performance. R=
600
Revenue
400 HH-IPG V1 V2 V3
200
0
False Negative
500
HH-IPG V1 V2 V3
400
300
200
100 −200 0 2000
4000
6000
8000
10000
12000
14000
2000
4000
6000
8000
10000
12000
Packet Count Threshold
Packet Count Threshold
(a) 10:00 trace
(b) 16:15 trace
14000
Fig. 5: Varying Packet Count Threshold, for HH threshold of 10 Mbps and 5 second time window: (a) Revenue, and (b) False Negatives.
Mean usage (%) 3.1 11.1 9.4 2.3
maximum revenue, and hence we can choose any value in this range to be used as the packet count threshold. Note that revenue does not change for original HH-IPG since it does not consider packet count. All three versions are seen to provide better performance than the IPG-based algorithm, with suitable PCth values chosen. The low revenue values for V2 and V3 for very high thresholds are as expected, since the PC value is used in decision making along with IPG metric. Hence, setting high PCth values (e.g., beyond 8000 in considered case) makes the algorithm miss heavy hitters. This increases the False Negative count, thereby reducing revenue. The V1 variant uses the PC value only during hash collision and hence performs better. By choosing a suitable value for PCth , packet count till hash collision helps in improving the HH detection when used together with the IPG metric. From the experiments, it was observed that V1 is either consistently better than or as good as HH-IPG, regardless of the packet threshold values. B. Varying HH threshold Next, the impact of heavy hitter threshold (HHth ) was studied. Fig. 6 and Fig. 7 present the revenue and false negatives results for varying HH threshold values respectively. We chose the best (PCth ) from the experimentation results of Section IV-A. Here, it is observed that V1 performs better than HH-IPG when for HH thresholds are in the range of 713 Mbps. Also, the packet count threshold value is set as per the observations done from experiments conducted setting HH threshold as 10 Mbps. The packet count threshold is expected to be changed with the change in the heavy hitter cutoff. Here, the same packet count threshold is still giving the better results in considerable range of 7-13 Mbps, despite the packet count threshold value being calculated for 10 Mbps as heavy hitter threshold. This shows the flexibility of the proposed algorithm. We can also observe that the objective of reducing missed HHs has been achieved by V1 in all the cases. C. ML metrics
A. Obtaining PC Thresholds To determine suitable packet count (PCth ) threshold values, the HH flows were captured for different PCth values. The changes in revenue for various threshold values were measured. Further, the impact of the threshold on reducing false negatives is studied. The results for a subset of traces from MAWI20 dataset [23] are shown in Fig. 5, where we captured HH flows for different PCth values in the steps of 100 between 1,100 and 20,000. Here, α = 0.99 as in the original HH-IPG algorithm for small-duration time windows [7]. Packet thresholds in the range of 2000 to 6000 yielded
In Fig. 8, the comparison of ML metrics is presented on MAWI dataset, with each 15-minute long trace divided into 5 sec time window traces. We fixed the packet count threshold as 2700. Similar to earlier discussion, the proposed algorithm versions are performing better than the baseline approach when the HHth is 10 Mbps which is the originally considered threshold while finding best PCth . Along with that, we can also observe here that V1 performs better for the HH thresholds ranging from 5 to 13 Mbps in terms of all the three ML metrics. Hence, the proposed algorithm can give better results despite some errors with respect to the packet count threshold value. We can observe here that V1 performs better
8
1400 HH-IPG V1 V2 V3
6000 5000
1250
HH-IPG V1 V2 V3
1200 1000
Revenue
3000 2000
Revenue
1000
4000
Revenue
HH-IPG V1 V2 V3
1500
750 500
800 600 400
1000
250 200
0 0 −1000
0 −250 5.0
7.5
10.0
12.5
15.0
17.5
20.0
22.5
25.0
5.0
7.5
10.0
12.5
15.0
17.5
20.0
22.5
25.0
5.0
7.5
10.0
12.5
15.0
17.5
20.0
22.5
25.0
HH Threshold
HH Threshold
HH Threshold
(a) 10:00 trace, Packet Count threshold: 1100, Time Window: 1sec
(b) 10:00 trace, Packet Count threshold: 2700, Time Window: 5sec
(c) 16:15 trace, Packet Count threshold: 2800, Time Window: 5sec
Fig. 6: Revenue obtained, varying HH Threshold.
HH-IPG V1 V2 V3
600
3000
2000
500 400 300 200
500
1000
7.5
10.0
12.5
15.0
17.5
20.0
22.5
25.0
300 200
0
0 5.0
400
100
100 0
HH-IPG V1 V2 V3
600
False Negative
4000
HH-IPG V1 V2 V3
700
False Negative
False Negative
5000
5.0
7.5
10.0
12.5
15.0
17.5
20.0
22.5
25.0
5.0
7.5
10.0
12.5
15.0
17.5
20.0
22.5
25.0
HH Threshold
HH Threshold
HH Threshold
(a) 10:00 trace, Packet Count threshold: 1100, Time Window: 1sec
(b) 10:00 trace, PC threshold: 2700, Window: 5 seconds
(c) 16:15 trace, PC threshold: 2800, Window: 5 seconds.
Fig. 7: Missed HHs observed, varying HH Threshold.
0.95
1.00
1.0
0.90
0.95
0.9
0.85
0.90
0.7
0.85
f1 score
Recall
Precision
0.8
0.80 0.75
0.6
0.70
HH-IPG V1 V2 V3
0.5 0.4 5.0
7.5
HH-IPG V1 V2 V3
0.65 0.60 10.0
12.5
15.0
17.5
20.0
22.5
25.0
5.0
7.5
10.0
12.5
15.0
17.5
20.0
22.5
0.80 0.75 0.70 0.65
HH-IPG V1 V2 V3
0.60 0.55
25.0
5.0
7.5
10.0
12.5
15.0
17.5
HH Threshold
HH Threshold
HH Threshold
(a) Precision
(b) Recall
(c) F1 score
20.0
22.5
25.0
Fig. 8: Comparison of various ML metrics for 10:00 traces.
for the HH thresholds ranging from 5 to 13 Mbps. For higher HH thresholds, V1 does not show any significant improvement whereas V2 shows better results. In Fig. 9, ML metrics are compared for 16:15 trace divided into 5 sec time window traces with fixed packet count threshold 2800. The trends are seen to be similar. The comparison of F1 score for initial 5 sec traces with the specific case of PCth as 2700 and HHth as 10 Mbps is presented in Fig. 10 and in Table III. For the overall 15-minute trace, the F1 score of the proposed scheme is reasonably higher compared with the HH-IPG algorithm. Quantitatively, the F1 score for the baseline approach was 0.84276 for the considered trace, which increased to 0.875843 in version 1, to 0.881888 in version 2, and to 0.912665 in version 3 of the proposed approach with best PCth . It is also observed that the F1 score is not always higher for all the small time windows. It is
seen that in some of the small time windows, only the IPG metric gives better results. However, the overall aggregated results across the larger trace duration show that the PC feature improves the F1 score. D. Optimizing the results based on requirements The heavy hitter detection algorithm has versatile applications (Section I). Hence, based on application, we may need to optimize our results for a particular evaluation metric. As an example, consider a machine learning tool which is flagging the possible threats which later will be investigated manually by a threat hunter. Here, false positives are acceptable to certain extent as it will be discarded by threat hunter later; but false negatives are not acceptable. Similarly, there might be some application that requires optimization with respect to
9
1.0
1.00
0.95
0.95
0.90
0.9
0.7
0.85
0.85
f1 score
0.8
Recall
Precision
0.90
0.80 0.75
0.6
0.5 5.0
7.5
0.75
0.70
HH-IPG V1 V2 V3
HH-IPG V1 V2 V3
0.65 0.60 10.0
12.5
15.0
17.5
20.0
22.5
25.0
0.80
5.0
7.5
10.0
12.5
15.0
17.5
20.0
22.5
HH-IPG V1 V2 V3
0.70 0.65
25.0
5.0
7.5
10.0
12.5
15.0
17.5
HH Threshold
HH Threshold
HH Threshold
(a) Precision
(b) Recall
(c) F1 score
20.0
22.5
25.0
Fig. 9: Comparison of various ML metrics for 16:15 traces. TABLE III: F1 score comparison for 5 second window traces Win. # 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
HH-IPG 0.7692 0.9090 0.6666 0.7500 0.6667 0.9333 1.0000 0.7500 0.8333 0.8889 0.8000 0.7500 0.8889 0.6667 0.8000
HH-IPG Ver1 Ver2 Ver3
V1 0.7692 1.0000 0.7059 0.8889 0.6000 1.0000 0.9090 0.6667 1.0000 0.8889 0.7272 0.7500 0.8889 0.7272 0.9230
V2 0.7692 0.9090 0.6667 0.8571 0.7500 0.9333 1.0000 0.7500 0.7272 0.8889 0.8889 0.8571 0.8889 0.7500 0.8000
V3 0.7692 1.0000 0.7059 1.0000 0.6667 1.0000 0.9090 0.6667 0.9230 0.8889 0.8000 0.7500 0.8889 0.8000 0.9230
0.90
600
0.85 400
0.8
0.80 HH-IPG V1 V2 V3
200
F1 Score
Revenue
1.0
Total Flows 8,345 12,493 8,206 8,721 8,493 8,495 8,083 8,166 8,604 8,395 8,387 8,673 8,166 8,955 8,201
HH-IPG V1 V2 V3
0.75 0.70 0.65
0
F1 Scores
0.60 0.55
−200
0.6
0.50 2000
4000
6000
8000
10000
12000
14000
2000
4000
6000
8000
10000
12000
Packet Count Threshold
Packet Count Threshold
(a) wrt. Revenue
(b) wrt. F1 score
14000
0.4
Fig. 11: Finding the optimal packet count threshold value (a) wrt. Revenue, and (b) wrt. F1 score 0.2
0.0 8345
12493
8206
8721
8493
8495
for experimentation, which results in the exact same value of true heavy hitters and the total number of flows.
Total Flows
Fig. 10: F1 score for 10:00 trace with 5 sec window.
the F1 score metric. Taking this into account, we are testing whether our algorithm can accommodate such requests by optimizing our algorithm with respect to a different metric, the F1 score, in this section. To do so, we plot the F1 score values obtained by our algorithm for various packet count thresholds. Comparing the above results with the earlier results where optimization is done with respect to revenue metric, we can observe that the algorithm behaves similarly as shown in Fig. 11. The pattern is similar because the same dataset is used
E. Comparison of results for various hash functions To understand the impact of the hash function being used on the results of our algorithm, we observe the HH detection by our algorithm while using 3 different hash functions. Considering the computational limitations of PDP switches, we limit our study to the linear functions. We used 3 different hash functions: (i) Modulo Hashing or Division Method (Hash 1); (ii) Multiplicative Hashing (Hash 3); (iii) Direct Mapping (Hash 2). The results for how each version behaves for these different linear hash functions are presented in Fig. 12. Here, we can observe that the algorithm gives similar results despite the hash function being used and also the packet count threshold value for which the algorithm
10
0.90 0.85
0.85 DS500 DS1000 DS1500 DS2000 DS2500 DS3000 DS5000
HH-IPG V1 V2
0.70
HH-IPG V1 V2
0.75 0.70
F1 Score
0.75
F1 Score
0.80
0.80
0.75
0.65
0.65
0.60
0.60
F1 Score
0.85
0.80
F1 Score
0.95
0.90
0.90
0.85
DS500 DS1000 DS1500 DS2000 DS2500 DS3000 DS5000
0.80 0.75 0.70 0.65 0.60
0.70
0.55 4000
6000
8000
10000
12000
2000
4000
6000
8000
10000
12000
4000
6000
8000
10000
12000
2000
4000
6000
8000
Packet Count Threshold
Packet Count Threshold
Packet Count Threshold
Packet Count Threshold
(a) Hash 1
(b) Hash 3
(a) Version 1
(b) Version 2
gives the best result also follows a similar pattern giving the better results around the range 2200 to 5500. Also, regardless of the hash function being used, each algorithm behaves almost similarly. This is observed from the experimentation results shown in Fig. 13, where, for the chosen hash function, a comparison of how the F1 score varies with different algorithms is presented.
12000
0.90
0.90
0.85
0.85
0.80 HH-IPG Ver1 Ver2
0.75
0.80
0.70
0.70
0.65
0.65
0.60
HH-IPG Ver1 Ver2
0.75
0.60 2000
4000
6000
8000
10000
12000
2000
4000
6000
8000
10000
12000
Packet Count Threshold
Packet Count Threshold
(a) Hash Size 3000 entries
(b) Hash Size 5000 entries
Fig. 15: Comparison of F1 score for the table size of (a) 3000 (b) 5000
0.90 0.875 0.85
0.850
10000
Fig. 14: Comparison of how each algorithm behaves wrt. different Table Sizes
F1 Score
Fig. 12: Comparison of how each algorithm behaves wrt. chosen Hash functions (a) Hash 1 and (b) Hash 3
0.80
0.825 Hash2 Hash1 Hash3
0.800 0.775
F1 Score
F1 Score
2000
F1 Score
2000
Hash2 Hash1 Hash3
0.75 0.70 0.65
0.750
0.60
0.725 2000
4000
6000
8000
10000
12000
2000
4000
6000
8000
Packet Count Threshold
Packet Count Threshold
(a) Version 1
(b) Version 2
10000
12000
Fig. 13: Comparison of how selected algorithm (i.e (a) Version 1 and (b) Version 2) behaves wrt. different Hash functions.
In Fig. 15, comparison of behavior of different algorithms for different table sizes has been provided. Here, we can observe that despite the increase in the F1 score, the pattern remains similar irrespective of the table size chosen; for properly chosen thresholds, the proposed algorithms give better results than the HH-IPG. G. Double hashing
F. Comparison of results for various data structure size For any algorithm running in a PDP switch, the memory utilization by the algorithm is very important, as the dynamic memory available for the custom algorithm will be limited in many PDP switches. Hence, we study the behavior of the algorithm for various allocated memory sizes for the custom data structure being used in our algorithm. We considered data structure sizes to be 500, 1000, 1500, 2000, 2500, 3000, and 5000 entries. The analysis results are shown in Fig. 14. Here, we can observe that with an increase in the allotted size of the data structure, the F1 score increases. The results follow the expectation that given the more memory storage for data structure, details of a relatively larger number of flows can be saved in the data structure. Thus, there will be less hash collisions, and the F1 score will be better. More heavy hitters can be captured at a given time instance, and hence the results will be better. Also, from Fig. 14, we can observe that for our algorithm as well as for HH-IPG, after reaching the F1 score around 0.9; the gain by having higher memory space for the data structure will relatively decrease as we increase the table size and hence conveys that we can reasonably use table size around 3000.
As another common solution for the hash collision is using double hash, we made use of two hash functions to see whether the double hash approach could give better results. The approach used for this is that the modulo hashing (Hash 1) is applied first on the 5-tuple to get the hash table index. Here, if an entry already exists in the table with a different flow ID in the hashed entry; the second hash function ’Multiplicative hashing’ is used. In our approach, there will be no deletion of the entry in the hash table, avoiding the deletion problem that occurs when using double hashing. Any existing entry can just be replaced by a new entry in case of hash collision at both the hash functions. The replacement is done in place of the entry pointed by the second hash function. The comparison of result of using double hashing during hash collision is provided in Fig. 16. The HH-dHash in Fig. 16 corresponds to the result of double hashing, which improved F1 score of HH-IPG algorithm from 0.842767 to 0.85322. The proposed algorithm can perform better than using double hashing. The proposed algorithm can achieve F1 score above 0.9, with the proper choice of packet count threshold. The above mentioned analysis is done by simulation. But we also need to consider that in case of implementation of double hashing on real programmable switch, there will be limitations on using the hash table making adverse effects on the switch
11
dataset. The packet count threshold values in range 1k to 1.7k are giving better results. The earlier discussed inferences are hence applicable. The proposed algorithm reduces false negatives by 4.18% for this trace.
0.85
HH-IPG HH-dHash Ver1 Ver2
0.70
25 0.8 20 0.6
0.65
False Negative
0.75
F1 Score
F1 Score
0.80
HH-IPG V1
0.4
0.2
0.60
0 4
4000
6000
8000
10000
6
12000
Packet Count Threshold
Fig. 16: Comparison of proposed approach against using double hash
functioning. For example, in case of Tofino switch, to get into a different entry in the hash table after applying second hash function; the packet needs to be recirculated. This is because of the architectural limitation of the Tofino switch. When a packet enters the Tofino switch, only one table entry can be fetched per packet in the packet’s lifetime. Hence, recirculation is necessary, which will increase the traffic on the switch. The increase in traffic hinders the standard functionality of the switch, causing a decrease in performance compared with the above-shown simulation results. In simulation, we directly fetch the second entry in case of hash collision. Note that the accuracy and F1 measurement metrics will remain the same, but the time of processing, traffic congestion, and so on will be affected. H. Results on CAIDA dataset
0.50 2600
F1 Score
0.40 HH-IPG V1 V2 V3
0.35 0.30 0.25 0.20
False Negatives
0.45 2400 HH-IPG V1 V2 V3
2200
2000
HH-IPG V1 10
5
0.0
2000
15
HH Threshold
8
10
12
14
4
6
8 10 HH Threshold
12
(a) F1 Score
(b) False Negatives
14
Fig. 18: Impact of Heavy Hitter Threshold on CAIDA data trace Also, the analysis of the impact of the heavy hitter threshold (τth ) was studied. The result is presented in Fig. 18, for the time window of 5 seconds. From the results of Fig. 17, the best packet count threshold of 3100 is chosen for version 1 of algorithm and 1100 for version 2 respectively. As earlier, here also we can observe that the proposed approach results is fewer missed heavy hitters and hence better F1 score. Version 2 and 3 overlaps with the HH-IPG and Version 1 respectively and hence not shown in the results. Therefore, despite choosing packet count threshold by the analysis keeping threshold at a particular point; with the same packet count threshold, the proposed approach yields better results over a range of heavy hitter thresholds. I. Using Packet Size An alternative option for using the packet count (PC) feature is to use the packet byte count or Packet Size (PS) feature. The algorithm using the PS feature is expected to be more accurate than the one with the PC feature for each packet, as the PS value may differ rather than being a constant increment, as in the case of PC. This comes at the cost of an increase in the number of bits required to store the PS value.
1800
0.15 1600 0.10 500
1000
1500
2000
2500
3000
3500
4000
500
1000
1500
2000
2500
3000
3500
Packet Count Threshold
Packet Count Threshold
(a) F1 Score
(b) False Negatives
4000
0.40
Fig. 17: Analysis on CAIDA data trace
0.35
F1 score
0.30
The proposed algorithm performed as expected even on the CAIDA dataset, and few results are provided in this section. The analysis is performed by varying the packet count threshold, for the HH threshold of 1 Mbps and a time window of 5 seconds. The number of heavy-hitters was relatively smaller in the CAIDA dataset compared to MAWI20, and therefore we considered 1 Mbps instead of 10 Mbps as the HH threshold. The result is presented in Fig. 17. The trace considered consisted of an overall of 2884 heavy hitters, with an average of 216,453 flows per time window. We can observe that the resulting pattern is similar to earlier results on the MAWI
0.25 0.20 0.15
HH-IPG PSV1 PSV2 PSV3
0.10 0.05 0.00
0.25
0.50
0.75
1.00
1.25
1.50
Packet Size Threshold
1.75
2.00 1e6
Fig. 19: F1 score comparison for packet size feature on CAIDA data trace
12
The analysis is performed by using the PS value in place of the PC, exactly as per the explanations provided for the PC. The result on a subset of CAIDA dataset is provided in Fig. 19. Results shows similar patterns as that of PC, while the improvement of F1 score is better. The usage of PS in place of a PC is more helpful when, in an application network, the packet sizes vary too much. This is because the PS gives better picture of this variance than the PC. Quantitatively, for the considered CAIDA trace, there were about 1400 true heavy hitters. The IPG and PC approach improved the F1 score by 2.986% while the IPG and PS approach further improved it by 5.5521%. But this comes at the cost of storing values up to 1,000,000 per table entry for packet size, compared with values up to 5000 in the case of packet count. These values are for the thresholds used in algorithm and hence the maximum value that might be stored in that field. V. C ONCLUSIONS This paper presented an enhanced heavy hitter detection algorithm that considered packet count feature in addition to the existing inter-packet gap feature. The objective was to reduce the number of false negatives by considering packet count whenever two flows were mapped to the same table slot in the flow hash table structure. The proposed algorithm was implemented in the P4-enabled Intel Tofino 1 switch and a python based simulator and analyzed using data from public real life datasets. From the performance studies, it was seen that many actual heavy hitter flows have been correctly identified by our modified algorithm, but were missed by the existing IPG-based algorithm. The proposed approach is also shown to be flexible with respect to different parameters. Funding Declaration This work was supported by Ciena Corporation, Ottawa, Canada. Authors’ Contribution Statement Adarsha K Shashidhar and Krishna M Sivalingam wrote the main manuscript text, with design, implementation and performance studies inputs from Adarsha K Shashidhar, Krishna Sivalingam, Gauravdeep Shami, Marc Lyonnais and Rodney Wilson. The software implementation and experiments were conducted primarily by Adarsha K Shashidhar. Acknowledgments The authors thank Dr. Jim Chen and Fei Yeh of Northwestern University for providing access to the Tofino switches at the International Center for Advanced Internet Research (iCAIR), Northwestern University. Conflict of Interest Statement On behalf of all authors, the corresponding author states that there is no conflict of interest.
Data Availability Statement The simulation results that support the findings of this study are available from the authors but restrictions apply to the public availability of these data and so are not publicly available. Data are, however, available from the authors upon reasonable request and with permission from Ciena Corporation and IIT Madras. R EFERENCES [1] V. Sivaraman, S. Narayana, O. Rottenstreich, S. Muthukrishnan, and J. Rexford, “Heavy-Hitter detection entirely in the data plane,” in Proceedings of the ACM SOSR, Santa Clara, CA, USA, Apr. 2017, p. 164–176. [Online]. Available: https://doi.org/10.1145/3050220.3063772 [2] T. Benson, A. Akella, and D. A. Maltz, “Network traffic characteristics of data centers in the wild,” in Proceedings of the ACM SIGCOMM, Melbourne, Australia, Nov. 2010, p. 267–280. [3] Z. Liu, A. Manousis, G. Vorsanger, V. Sekar, and V. Braverman, “One Sketch to Rule Them All: Rethinking Network Flow Monitoring with UnivMon,” in Proceedings of the ACM SIGCOMM, Florianopolis, Brazil, Aug. 2016, p. 101–114. [Online]. Available: https://doi.org/10. 1145/2934872.2934906 [4] R. Ben-Basat, G. Einziger, R. Friedman, and Y. Kassner, “Heavy hitters in streams and sliding windows,” in Proceedings of IEEE INFOCOM, San Francisco, CA, USA, Apr. 2016, p. 1–9. [5] J. Huang, W. Zhang, Y. Li, L. Li, Z. Li, J. Ye, and J. Wang, “ChainSketch: An Efficient and Accurate Sketch for Heavy Flow Detection,” IEEE/ACM Transactions on Networking, vol. 31, no. 2, pp. 738–753, 2023. [6] R. Kamath and K. M. Sivalingam, “Machine Learning based Flow Classification in DCNs using P4 Switches,” in Proc. International Conference on Computer Communications and Networks (ICCCN), Athens, Greece, Jul. 2021, pp. 1–10. [Online]. Available: https: //doi.org/10.1109/ICCCN52240.2021.9522272 [7] S. K. Singh, C. E. Rothenberg, M. C. Luizelli, G. Antichi, P. H. Gomes, and G. Pongrácz, “HH-IPG: Leveraging Inter-Packet Gap Metrics in P4 Hardware for Heavy Hitter Detection,” IEEE Transactions on Network and Service Management, vol. 20, no. 3, pp. 3536–3548, 2023. [8] Intel, “Intel® TofinoTM series,” https://www.intel.com/content/www/us/ en/products/details/network-io/intelligent-fabric-processors/tofino.html, last Accessed on April 25, 2025. [9] T. Aldhyani, “Network dataset,” 2020. [Online]. Available: https: //dx.doi.org/10.21227/hf8d-x031 [10] “The CAIDA UCSD Anonymized Internet Traces on IPv6 Day and IPv6 Launch Day,” https://www.caida.org/catalog/datasets/passive ipv6day and ipv6launch dataset, last Accessed on April 21, 2025. [11] K. Adarsha, K. M. Sivalingam, G. Shami, M. Lyonnais, and R. Wilson, “Heavy hitter flow detection using p4-based programmable data plane switches,” in 2024 IEEE International Conference on Advanced Networks and Telecommunications Systems (ANTS), Guwahati, India, Dec. 2024, pp. 1–6. [12] L. Peterson, C. Cascone, B. O’Connor, T. Vachuska, and B. Davie, “Software-Defined Networks: A Systems Approach,” https://sdn. systemsapproach.org/intro.html, Nov. 2021, last Accessed on April 21, 2025. [13] P. Bosshart, G. Gibb, H.-S. Kim, G. Varghese, N. McKeown, M. Izzard, F. Mujica, and M. Horowitz, “Forwarding metamorphosis: Fast programmable match-action processing in hardware for SDN,” Computer Communication Review, vol. 43, no. 4, p. 99 – 110, 2013. [14] P. Bosshart, D. Daly, G. Gibb, M. Izzard, N. McKeown, J. Rexford, C. Schlesinger, D. Talayco, A. Vahdat, G. Varghese, and D. Walker, “P4: Programming Protocol-Independent Packet Processors,” SIGCOMM Comput. Commun. Rev., vol. 44, no. 3, p. 87–95, jul 2014. [15] X. Zhang, L. Cui, F. P. Tso, and W. Jia, “pHeavy: Predicting Heavy Flows in the Programmable Data Plane,” IEEE Transactions on Network and Service Management, vol. 18, no. 4, pp. 4353–4364, 2021. [16] M. Seufert, K. Dietz, N. Wehner, S. Geißler, J. Schüler, M. Wolz, A. Hotho, P. Casas, T. Hoßfeld, and A. Feldmann, “Marina: Realizing ML-Driven Real-Time Network Traffic Monitoring at Terabit Scale,” IEEE Transactions on Network and Service Management, vol. 21, no. 3, pp. 2773–2790, 2024. [17] S. Mittal and P. Tammana, “Efficient In-Network Traffic Classification Using Programmable Switches With AdaFlow,” IEEE Transactions on Network and Service Management, vol. 22, no. 6, pp. 5532–5549, 2025.
13
[18] A. Greenberg, J. R. Hamilton, N. Jain, S. Kandula, C. Kim, P. Lahiri, D. A. Maltz, P. Patel, and S. Sengupta, “VL2: a scalable and flexible data center network,” in Proceedings of the ACM SIGCOMM, Barcelona, Spain, Oct. 2009, p. 51–62. [Online]. Available: https://doi.org/10.1145/1592568.1592576 [19] S. Sen and J. Wang, “Analyzing peer-to-peer traffic across large networks,” IEEE/ACM Transactions on Networking, vol. 12, no. 2, p. 219–232, Apr. 2004. [Online]. Available: https://doi.org/10.1109/TNET. 2004.826277 [20] R. Harrison, Q. Cai, A. Gupta, and J. Rexford, “Network-Wide Heavy Hitter Detection with Commodity Switches,” in Proc. of ACM SOSR, 2018. [21] D. Barradas, N. Santos, L. Rodrigues, S. Signorello, F. M. V. Ramos, and A. Madeira, “FlowLens: Enabling Efficient Flow Classification for ML-based Network Security Applications,” in Proc. of NDSS, 2021. [22] GitHub repo, “HH detection using packet count till hash collision and IPG,” https://github.com/Adhu2/HH Detection, 2024, last Accessed on April 21, 2025. [23] R. Fontugne, P. Borgnat, P. Abry, and K. Fukuda, “MAWILab: Combining Diverse Anomaly Detectors for Automated Anomaly Labeling and Performance Benchmarking,” in Proc. of ACM CoNEXT, Dec. 2010.