A Sketch Algorithm to Monitor High Packet Delay in
Network Traffic
Jiaqi Zhu

Kai Zhang

Qun Huang

zhu_jiaqi@pku.edu.cn
Peking University
Beijing, China

ferric@pku.edu.cn
Peking University
Beijing, China

huangqun@pku.edu.cn
Peking University
Beijing, China

ABSTRACTKEYWORDS

Packet delay is a consensual indicator of network conditions.
High delay packets of a flow indicate that there may be network congestion or network anomalies. In this paper, weconsider Intra-Flow Packet Delay (IFPD), which is defined as
the time span between two adjacent packets of a flow. In particular, we aim to detect packets that exhibit high IFPD. The
key challenge is to simultaneously achieve high detection
accuracy and preserve low resource usage. Existing measurement approaches reduce resource overheads by injecting
probe packets or sampling. However, they can only measure
an average delay of some packets but fail to monitor delay
behavior of every single packet. To this end, we propose asketch-based approach. Unfortunately, existing sketch-based
methods cannot be directly applied to our high IFPD detection problem. That is because traditional sketch algorithms
require that the update operation is additive, while measuring IFPD needs to deal with timestamps, which is not additive.
We address this issue in three aspects: (i) using fingerprints
to mitigate hash conflicts; (ii) a conservative update methodthat only selects one bucket to update; (iii) a replacement
strategy that keeps potential flows with high IFPD in thesketch. Our experiments on real world traces demonstratethat our solution identifies high IFPD with nearly 99% recall
rate and 99% precision with 600 KB memory, which outperforms existing sketch-based solutions.

Sketches; Network measurement; Packet Delay;

CCS CONCEPTS• Networks → Network measurement.

Permission to make digital or hard copies of all or part of this work forpersonal or classroom use is granted without fee provided that copies are notmade or distributed for profit or commercial advantage and that copies bear
this notice and the full citation on the first page. Copyrights for componentsof this work owned by others than ACM must be honored. Abstracting withcredit is permitted. To copy otherwise, or republish, to post on servers or toredistribute to lists, requires prior specific permission and/or a fee. Request
permissions from permissions@acm.org.
APNet 2021, June 24–25, 2021, Shenzhen, China, China© 2021 Association for Computing Machinery.
ACM ISBN 978-1-4503-8587-9/21/06. . . $15.00
https://doi.org/10.1145/3469393.3469398

ACM Reference Format:
Jiaqi Zhu, Kai Zhang, and Qun Huang. 2021. A Sketch Algorithm toMonitor High Packet Delay in Network Traffic. In 5th Asia-PacificWorkshop on Networking (APNet 2021) (APNet 2021), June 24–25,
2021, Shenzhen, China, China. ACM, New York, NY, USA, 7 pages.
https://doi.org/10.1145/3469393.3469398

1

INTRODUCTION

Network measurement provides critical information for modern network management in data centers and backbone networks. With various network metrics such as heavy hitters[17] and superspreaders [18], network administrators candiagnose network problems, avoid network attack, and improve the quality of service [8, 21]. Among the measurementtasks, packet delay is a key indicator of network health [4].
For example, an increase of packet delay could imply router
failures in a network because a longer path is selected toreplace the original path.
In this paper, we consider Intra-Flow Packet Delay (IFPD),
which is defined as the time span between two adjacent
packets of one flow. In particular, we aim to detect packets
whose IFPD exceed a pre-defined threshold.
Detecting high IFPD is helpful to monitor network health.
In delay-sensitive networks, the IFPD of each packet should
be low under normal circumstances. However, when network
anomalies occur, a packet arriving at upstream switches willbe blocked or lost. It will cause a high IFPD between thatpacket and its previous packet of the same flow. Therefore,high IFPD can indicate network health.
One simple approach is using a hash table to store all
flowkeys and timestamps. However, it consumes too much resource to be implemented in commodity switches. Therefore,
we need lightweight solutions. Existing lightweight delay
monitoring approaches use sampling methods or probe packets injection [11–13, 16, 19]. These methods focus on making
a summary of inter-server packet delay measurement, andwe can not get every single IFPD from their results. For example, the LDA [11] calculates the average delay of a group of
packets by counting data packets between two injected probe

APNet 2021, June 24–25, 2021, Shenzhen, China, China

packets. This information is not sufficient for our purpose
to detect high IFPD.
In this paper, we propose a sketch-based approach to detect high IFPD. Even though sketch techniques have been
widely used in heavy hitter detection and superspreader detection, they cannot handle high IFPD detection well. The key
problem is that traditional sketches require the update operation to be additive. Hash conflicts can lead to replacement of
the demanded timestamp of a flow, and thus result in lower
estimation. To deal with this issue, we raise a new sketch thatworks well in high IFPD detection as our main contribution.
The key ideas about our method are: (i) using fingerprints
to mitigate hash conflicts; (ii) a conservative update methodthat only selects one bucket to update; (iii) a replacement
strategy that keeps potential flows with high IFPD in thesketch. Our experiments on real world traces demonstratethat our solution identifies high IFPD with nearly 99% recall
rate and 99% precision with 600 KB memory, which outperforms existing sketch-based solutions.
The structure of this paper is as follows. In Section 2 weformulate the definition of IFPD and the problem of high
IFPD detection. In Section 3, we first analyse the limitationsof existing sketches, and then raise our new sketch. In Section 4, we test the solutions against real world dataset, andverify our sketch’s outstanding performance. Related work
is represented in Section 5, and finally are our conclusions
and future work in Section 6.

2

PROBLEMThis paper addresses high Intra-Flow Packet Delay (IFPD)
detection in a network device. We first formulate our problem. We consider the arrival network traffic of the device asa stream of packets. Each packet is modeled as a tuple (x, t),where x is the flowkey (e.g., source/destination address pairsor 5-tuples) and t is the timestamp when the packet arrives
at the device. Packets with the same flowkey x forming asequence are referred as a flow. For a flow x with k packets,
we represent the flow as
f x = ((x, t 1 ), (x, t 2 ), ..., (x, tk ))Note that packets in a flow x are recorded in a chronologicalorder (i.e., ∀i < j, ti < t j ). We define the intra-flow packet
delay of the i-th packet for i = 2, 3, · · · , k as:
D ix = ti − ti−1
Given a threshold θ , our primary goal is to report all packets whose D ix exceeds θ in an efficient manner. Specifically,
our detection approach aims to achieve following properties:• High accuracy: For each arriving packet, our algorithm
computes an estimation of its IFPD as D est . If D est exceeds
θ , we will consider the packet as a high IFPD packet. Our
goal is not only detecting most of the high IFPD packets,

Jiaqi Zhu, Kai Zhang, and Qun Huang

but also keeping a low false positive rate. Besides, we expect that the delay estimation of those reported high IFPD
packets is accurate, which means the difference between
D est and real IFPD should be small.
• Low resource usage: Since the commodity switches only
have limited memory space [10], we can not store all
flowkeys and timestamps in it. Besides, the computation
resources are also restricted in switches, and some complex operations based on pointers can not be implemented
in switches. Therefore, our algorithm should use small
memory resources and computation resources.

3

ALGORITHM DESIGNThis paper follows the line of sketch-based measurement [3, 5,
6, 16, 17]. Sketches are a family of data structures comprisingof multiple buckets. They make a trade-off between accuracy
and memory usage by allowing each bucket to accommodate
multiple flows, and mitigate the errors due to hash conflicts
with multiple independent hash functions. Given their highaccuracy and resource efficiency, sketch-based algorithms
have been widely used in various network measurementtasks, such as flow size estimation (e.g., Count-Min Sketch[5], Count Sketch [3], CU Sketch [6]), heavy hitter and heavychanger detection (e.g., MV Sketch [17]).

3.1

Limitations of Existing Sketch
Algorithms

Unfortunately, existing sketch algorithms fail to apply to
our high IFPD detection problem. The key issue is that traditional sketch algorithms require the update operation to be
additive (e.g., summing up byte count of packets). However,monitoring IFPD needs to deal with non-additive timestamps.
On hash conflicts, we can only replace the timestamp stored
in the bucket. Assuming a high IFPD packet (x, tcur r ) andits previous arriving packet is (x, tpr e ). In the time intervalfrom tpr e to tcur r , it is highly probable that the stored tpr e isreplaced by other flows due to hash conflicts. That will leadto a low estimation of IFPD, and fail in high IFPD detection.
Take Count-Min Sketch [5] as an example. Its structure is a
two-dimensional d × w array of buckets. Let B(i, j) represent
the bucket at the i-th row and the j-th column, where 1 ≤i ≤ d and 1 ≤ j ≤ w. Count-Min Sketch is associatedwith d pairwise-independent hash functions, denoted by
h 1 , h 2 , ..., hd . Each hash function corresponds to one row in
the array. For a key x, the hash function hi will hash x into
one of the w buckets in row i, where (1 ≤ i ≤ d).
We can apply Count-Min Sketch to detect high IFPD packets. Each bucket B(i, j) has a field t to store the timestamp.
When a packet arrives, we update certain buckets and compute the IFPD of that packet. Algorithm 1 shows its detail.
The B(i, j).t in all buckets are initially set to 0. For the packet

1

APNet 2021, June 24–25, 2021, Shenzhen, China, China

1
C M

Figure 1(b) shows the recall of reported high IFPD withdifferent thresholds and different sizes. It shows that therecall gradually decreases as the threshold increases, so
CM Sketch does not detect very high IFPD packets.

S k e tc h

0 .8

0 .8

0 .6

0 .6

R e c a ll

D e te c te d F ir s t P a c k e t R a te

A Sketch Algorithm to Monitor High Packet Delay in Network Traffic

0 .4
0 .2

3 0 0 K B
4 0 0 K B
5 0 0 K B
6 0 0 K B

0 .4
0 .2

0

Because of those limitations, we need to design new sketchbased algorithms to solve high IFPD detection problem.

0
3 0 0
4 0 0
5 0 0
M e m o ry U s a g e (K B )

6 0 0

3 0 0

( a ) D e t e c t F ir s t P a c k e t o f a F lo w

4 0 0
5 0 0
6 0 0
T h r e s h o ld (m s )( b ) R e c a ll o f H ig h I P F D

7 0 0

D e t e c t io n

Figure 1: First Packet Detection and High IPFD Detection Recall of CM Sketch
arriving at the current time (x, tcur r ), we first hash x into dbuckets. We choose the minimum timestamp tmin from alld hashed buckets and update those buckets by current time
tcur r (Lines 2~4). If tmin equals 0, it indicates that flow x is
not in the sketch, and packet (x, tcur r ) is the initial packet.
We then set D est = 0 in this condition (Lines 6~7). Otherwise, those buckets were updated when the previous packet
of flow x arrived, and tmin is an estimation of its arrival time.
D est can be computed by D est = tcur r − tmin (Lines 8~10).
Algorithm 1 CM Sketch compute IFPD
Input : packet (x, tcur r )Output : delay estimation D est
1: for i = 1 to d do2:j ← hi (x)3:tmin ← min{tmin , B(i, j).t}4:
B(i, j).t ← tcur r
5: end for
6: if tmin = 0 then7:
D est ← 0
8: else9:
D est ← tcur r − tmin
10: end if
11: return D est
However, there are two limitations to this solution:• The initial timestamp 0 can be easily flushed due to hashconflicts. The algorithm cannot accurately distinguishwhether packet (x, t) is the initial packet, and will incorrectly give IFPD of the initial packets. Figure 1(a) shows
the proportion of initial packets successfully detected by
CM-Sketch of different sizes. It shows that more than 40%of the packets are missed.
• If (x, tcur r ) is a high IFPD packet and its previous packet
arrived at tpr e . During the interval from tpr e to tcur r , thetpr e stored in buckets can be replaced due to hash conflicts. As a result, high IFPD packets are hardly detected.

3.2

Our Solution

Main idea. As discussed in §3.1, our key issue is to deal withthe hash conflicts for timestamps. First, we use a fingerprintbased approach to mitigate errors caused by hash conflicts.
We assign a fingerprint to each flow. Even if two flows arehashed to the same bucket, they are likely to have different fingerprints and can be distinguished. Second, for thed hashed buckets of a packet, we select only one to update.
As mentioned in §3.1, the timestamp of high IFPD is easily
replaced during a delay interval. We want to conservatively
reduce the probability of that by only updating one bucket.
Third, we use a replacement strategy if all d buckets havestored fingerprints and timestamps but none matches thecoming packet. In this situation, we expect to keep the buckets storing high IFPD flows. Those buckets update slowly,
so their timestamps should be small. Therefore, our strategy
will replace the bucket storing the largest timestamp.
Data structure. Figure 2 shows our sketch structure. It comprises of d rows, each of which contains w buckets. Eachbucket B(i, j) consists of two components: (i) f p, which storesthe fingerprint of a flow that may have high IPFD packets; (ii)t, which stores the timestamp of the newest arrived packet,
and the packet belongs to the flow whose fingerprint is stored
in f p. All components in the buckets are set to 0 initially.
Processing procedure. When a packet (x, tcur r ) arrives, we
compute the IFPD and update buckets. The details are shownin Algorithm 2. It first computes the fingerprint f px , andthen uses d hash functions to hash x into one bucket eachrow (Lines 1~3). We check each of the d hashed buckets fromrow 1 to row d. Specifically, there are three cases:• Case 1: B(i, j) stores the same fingerprint as f px . In thissituation, we consider that the timestamp of flow x isstored in that bucket. Therefore, we compute delay D est =tcur r − B(i, j).t and update B(i, j).t by tcur r (Lines 4~7).
• Case 2: B(i, j) is an empty packet. It indicates (x, tcur r ) is
the first packet of flow x, because if not, bucket B(i, j)will be occupied by a previous arriving packet of flow
x. Therefore, we set D est = 0 and store timestamp andfingerprint in B(i, j) (Lines 8~12). Note that Case 1 andCase 2 never happen together. If B(i, j) is empty, there will
not be a hashed bucket B(i ′, j ′) that stores f px and i < i ′.
Because we check those buckets from row 1 to row d, andf px should have been stored in B(i, j) since i < i ′.

APNet 2021, June 24–25, 2021, Shenzhen, China, China

Jiaqi Zhu, Kai Zhang, and Qun Huang

fp=5
t=20

packetd rows(x, t)

fp: fingerprint
t: timestamp

fp=5
t=20
fp=9
t=14

(x, 25)
fp=2
fp=2
t=12

fp=9
t=14
fp=2
t=25

Figure 3: Example of our sketch: Case 2
w colsFigure 2: structure of our solution• Case 3: All of the d hashed buckets have stored fingerprints
and timestamps, while none of them store the same fingerprint as f px . In this case, we choose one bucket to be
replaced with (x, tcur r ). We will find the bucket bkt whose
field t is largest among those d buckets. We use tcur r −bkt .t
as an estimation of IFPD, and update the timestamp andfingerprint stored in bkt (Lines 15~19).
Algorithm 2 Update and compute IFPD
Input : packet (x, tcur r )Output : delay estimation D est
1: f px ← f inдerprint(x)2: for i = 1 to d do3:j ← hi (x)4:
if B(i, j).f p = f px then5:
D est ← tcur r − B(i, j).t6:
B(i, j).t ← tcur r
7:
return D est
8:else if B(i, j).f p = 0 && B(i, j).t = 0 then9:
D est ← 0
10:
B(i, j).t ← tcur r
11:
B(i, j).f p ← f px
12:return D est
13:
end if
14: end for
15: bkt ← the bucket which has largest t among those dbuckets
16: D est ← tcur r − bkt .t
17: bkt .t ← tcur r
18: bkt .f p ← f px
19: return D est
Note that we choose to update only one bucket each time.
This differs from previous sketches, all of whose rows are
updated in one operation. It can be considered as a conservative update method to keep the timestamp of potential
flows that have IFPD packets. Assuming that a flow fh which

fp=5
t=20

fp=6
t=25
fp=9
t=14

(x, 25)
fp=6
fp=2
t=12

fp=9
t=14
fp=2
t=12

Figure 4: Example of our sketch: Case 3
has high IFPD packets and a flow fl whose most packets are
low IFPD packets, and fh and fl hash into the same bucket
b. If we update all d buckets each time, then the timestampof fh stored in bucket b will be easily replaced by fl , since
timestamps of fl update more frequently. However, if weonly update one of the d buckets, then the timestamps of fl
may be updated in one of the other d − 1 buckets other thanbucket b. In this way, the timestamps of fh are more likely
to be kept in the sketch.
Example. We use an example to illustrate our algorithm.
Here we assume a 3 × 3 sketch structure in which buckets
B(1, 2), B(2, 3) and B(3, 1) already record some flows. We
consider a packet (x, 25). The hash values of x in the threerows are h 1 (x) = 2, h 2 (x) = 3, h 3 (x) = 1, respectively.
All the hashed buckets have already stored a flow. In Example 1 shown as Figure 3, the fingerprints of the incoming
packet and B(3, 1) are identical. Hence we just report IFPD as
25 − 12 = 13, and update B(3, 1) with the newest timestamp
25. Example 2 shown as Figure 4 demonstrates another case,where none of the candidate buckets matches the incoming packet by fingerprint. The bucket B(1, 2) is chosen to
be updated because of its largest timestamp 20. We computethe IFPD as 25 − 20 = 5 and replace B(1, 2) with the newcomer’s fingerprint and timestamp.
Space optimization. We further reduce the memory usageby optimizing timestamps stored in buckets. Recall that the
network timestamps are supplied as microseconds, represented by 64-bit integers. However, network measurements
do not need such accurate timestamps, but focus on intervalsof seconds. For each interval, we can record the start time
ts . When a packet (x, tcur r ) comes, its relative time tcur r − ts

A Sketch Algorithm to Monitor High Packet Delay in Network Traffic

APNet 2021, June 24–25, 2021, Shenzhen, China, China

is stored instead of tcur r . Thus a packet’s time can be represented by a 32-bit integer. All algorithms mentioned above
can use this method to optimize space usage.

4.1

Experimental Setup

Baseline. We use Count-Min sketch as a baseline algorithm
to detect high IFPD. To partially resolve its limitations, we
also add a Bloom Filter [2] to record flows that have occurred,and determine whether a newest coming packet (x, t) is thefirst packet of flow x. Above algorithms are abbreviated as
CM and CM-BF in the following details.
Implementation. We implement baseline algorithms andour method in C++. AwareHash with different initial seeds
are used as hash functions in all the implementations.
Dataset. We use public network traffic traces collected by theequinix-nyc Internet data collection monitor from CAIDA[1]. We divide each trace into segments of 2 seconds, anduse 5-tuple as flowkey. There are about 1,000,000 packets of
90,000 flows in each segment.

Parameter settings. For our method and baseline algorithms, we set d = 4. The fingerprint consists of 16 bits. All
three algorithms store related timestamps in 32-bit integers.
Threshold selection. We survey the distribution of IFPD
and find that about 5.8% of them exceed 200ms, while about
31.6% flows contain such high IFPD packets. Therefore, ourO u r M e th o d

0 .8

0 .8

0 .6

0 .6

R e c a ll

1

0 .4
0 .2

0 .4
0 .2

0
0
2 0 0 3 0 0 4 0 0 5 0 0 6 0 0 7 0 0
2 0 0 3 0 0 4 0 0 5 0 0 6 0 0 7 0 0
T h r e s h o ld ( m s )T h r e s h o ld ( m s )1
1 0 -1
0 .8
0 .6
0 .4
0 .2
0
2 0 0 3 0 0

4 0 0 5 0 0

6 0 0 7 0 0

1 0 -2
1 0 -3
1 0 -42 0 0 3 0 0

T h r e s h o ld ( m s )4 0 0 5 0 0

6 0 0 7 0 0

T h r e s h o ld ( m s )Figure 5: Experiment 1 (Accuracy for high IFPD detection)
experiments test against thresholds ranging from 200ms to700ms. Details of the proportions under different thresholds
are shown in Table 1.
Table 1: Proportion of High IFPD and Flows with HighIFPD under Different Thresholds

Evaluation metrics. We use the following four metrics toevaluate the accuracy of high IFPD detection:
P• Precision : T PT+F
P . It is the ratio of the number of truehigh IFPD returned to the total number of all high
IFPD returned. High precision indicates the algorithm
detects high IFPD accurately.
P• Recall = T PT+F
N . It is the ratio of the number of truehigh IFPD returned to the actual number of true high
IFPD. High recall indicates the algorithm catches mostof the high IFPD.
2×pr ecision×r ecall• F 1−score = pr ecision+r ecall . It is the harmonic meanof precision and recall.
|D e −D e |• Relative error = |R1 | Σe,e ∈R esDt e . Here R is theeset of true high IFPD packets returned, D est
is theeestimated IFPD of packet e, and D is the real IFPD of
packet e.

C M -B F

R e la tiv e E r r o r

In this section, we compare our new sketch to baseline algorithms based on Count-Min sketch. Evaluation on real world
dataset shows that our sketch achieves high accuracy in detecting high IFPD. Section 4.1 describes our experimental
setup. Section 4.2 evaluates the accuracy of these algorithms
under different thresholds and different memory usage.

P r e c is io n

EXPERIMENTS

F 1 S c o re

4

C M

1

threshold (ms) IFPD proportion flow proportion
100
10.0%
40.2%
200
5.8%
31.6%
300
3.3%
22.8%
400
2.1%
16.8%
500
1.3%
12.2%
600
0.9%
9.3%
700
0.7%
7.3%

4.2

Experiment Results

Experiment 1 (Accuracy for high IFPD detection). Figure 5 compares our sketch to baseline algorithms with different thresholds using 400 KB memory. The precision of
CM is low, because it cannot determine whether a packet isthe flow’s initial packet. The precision of CM-BF is nearly
100%, because it assures that the estimated IFPD of all packets except the first one are smaller than their actual value.
However, the recall rate of both CM and CM-BF decreases
rapidly as the threshold increases. The reason is that fora high IFPD, within its time interval, the flow information
stored in the bucket are likely to be replaced due to hashconflicts. CM and CM-BF seldom detect quite high IFPD, andAPNet 2021, June 24–25, 2021, Shenzhen, China, China
C M -B F

1

0 .8

0 .8

0 .6

0 .6

0 .4
0 .2

1

3 0 0
4 0 0
5 0 0
6 0 0
M e m o ry U s a g e (K B )R e la tiv e E r r o r

0 .8
0 .6
0 .4
0 .2
0

latency curve with interpolation to decrease relative error.
Lossy Difference Sketch (LDS) [16] extends this method witha sketch to support measuring under multiple flows. Others
like Order Preserving Aggregator (OPA) [19] and FineComb[13] make further enhancement. Inter packet delay is also referenced in some researches. They use it to analyze network
attack [21] and estimate end-to-end packet delay [14].

0 .4
0 .2

0

F 1 S c o re

O u r M e th o d

1

R e c a ll

P r e c is io n

C M

Jiaqi Zhu, Kai Zhang, and Qun Huang

3 0 0

4 0 0

5 0 0

6 0 0

M e m o ry U s a g e (K B )0
1 0 -1

3 0 0
4 0 0
5 0 0
6 0 0
M e m o ry U s a g e (K B )1 0 -2
1 0 -3
1 0 -4
1 0 -5

3 0 0

4 0 0

5 0 0

6 0 0

M e m o ry U s a g e (K B )Figure 6: Experiment 2 (Memory usage for high IFPD
detection)

Sketches and filters. Sketches are broadly employed in
network measurement. We compare our sketch with classic Count-Min Sketch [5], which is simple but compact forsummarizing large-scale streaming data. Bloom Filter [2]is introduced to handle the corner case about initial packet
better. There are other sketches like Count Sketch [3] andCU Sketch [6] based on Count-Min Sketch. Sketches withnew structure like SketchLearn [9], MV-Sketch [17], Elastic
Sketch [22] and so on are delicately designed and well applied in heavy hitter detection and heavy changer detection.
Our method is also inspired by the structure of filters dealing
with AMQ problems, including Bloom Filter [2], Counting
Bloom Filter [15], Cuckoo Filter [7] and Vacuum Filter [20].

6
the problem is revealed under high threshold. Our method
has stable recall rate and precision as the threshold increases,
because it keeps potential flows containing higher IFPD.
Experiment 2 (Memory usage for high IFPD detection).
Figure 6 compares our sketch to baseline algorithms with
700ms threshold using different memory. The precision andrecall rate increase as memory usage increases, because of
the mitigation of hash conflicts. With 600 KB memory used,
our method achieves precision and recall rate of nearly 99%.
In fact, at least 2 MB memory is needed for a hash map
to calculate IFPD, assuming the load factor is 0.75 and no
separate chaining. More memory will be used if hash conflicts
occur and separate chaining is involved. In contrast, ourmethod requires less than half memory as a hash map do,but still performs well.
In conclusion, the first experiment shows that the performance of our method is stable as threshold changes; thesecond experiment shows that our method performs wellwith little memory usage. Therefore, our method is acceptable. Meanwhile, the relative error of our method is always
lower, presenting better estimation of high IFPD packets.

5

RELATED WORK

Packet delay. Packet delay is an important indicator of network health. Researches measure the latency in different
granularities with different methods. Loss Difference Aggregator (LDA) [11] slices a flow into packet segments andgets the average delay of each segment. Reference Latency
Interpolation (RLI) [12] adopts similar idea, and smooths the

CONCLUSION AND FUTURE WORKIn this paper, we aim to detect packets with high intra-flow
packet delay (IFPD). We follow the line of sketch-based algorithms to achieve high detection accuracy with low resource
usage. We propose a new sketch algorithm to address thelimitation in the high IFPD detection problem with three
key ideas (i) using fingerprints to detect hash conflicts; (ii)a conservative update method; (iii) a replacement strategy.
The evaluation driven by real world traces shows that our
method is capable of detecting high IFPD with almost perfectprecision and recall rate.
We will continue to explore into IFPD monitoring. First,
the algorithm needs mathematical analysis about its theory
and performance. Second, our method will be implemented
on hardware devices. Third, detecting thresholds to various
types of flows can be different. If more attention is paid to theflow types, high IFPD will better reveal network conditions.

ACKNOWLEDGMENTS
This work was supported by the Key-Area Research and Development Program of Guangdong Province 2020B0101390001,
Joint Funds of the National Natural Science Foundation ofChina (U20A20179), National Natural Science Foundationof China (61802365), and “FANet: PCL Future Greater-Bay
Area Network Facilities for Large-scale Experiments andApplications (No. LZC0019)”.

REFERENCES[1] 2018. The CAIDA Anonymized Internet Traces. https://www.caida.
org/data/overview/index.xml.

A Sketch Algorithm to Monitor High Packet Delay in Network Traffic[2] Burton H Bloom. 1970. Space/time trade-offs in hash coding withallowable errors. Commun. ACM 13, 7 (1970), 422–426.
[3] Moses Charikar, Kevin Chen, and Martin Farach-Colton. 2002. Finding frequent items in data streams. In International Colloquium on
Automata, Languages, and Programming. Springer, 693–703.
[4] Baek-Young Choi, Sue Moon, Zhi-Li Zhang, Konstantina Papagiannaki,
and Christophe Diot. 2007. Analysis of point-to-point packet delay inan operational network. Computer Networks 51, 13 (2007), 3812–3827.
https://doi.org/10.1016/j.comnet.2007.04.004[5] Graham Cormode and Shan Muthukrishnan. 2005. An improved data
stream summary: the count-min sketch and its applications. Journalof Algorithms 55, 1 (2005), 58–75.
[6] Cristian Estan and George Varghese. 2002. New directions in traffic
measurement and accounting. In Proceedings of the 2002 conference
on Applications, technologies, architectures, and protocols for computercommunications. 323–336.
[7] Bin Fan, Dave G Andersen, Michael Kaminsky, and Michael D Mitzenmacher. 2014. Cuckoo filter: Practically better than bloom. In Proceedings of the 10th ACM International on Conference on emerging
Networking Experiments and Technologies. 75–88.
[8] Chuanxiong Guo, Lihua Yuan, Dong Xiang, Yingnong Dang, Ray
Huang, Dave Maltz, Zhaoyi Liu, Vin Wang, Bin Pang, Hua Chen,
Zhi-Wei Lin, and Varugis Kurien. 2015. Pingmesh: A Large-Scale
System for Data Center Network Latency Measurement and Analysis.
In Proceedings of the 2015 ACM Conference on Special Interest Groupon Data Communication (London, United Kingdom) (SIGCOMM ’15).
Association for Computing Machinery, New York, NY, USA, 139–152.
https://doi.org/10.1145/2785956.2787496[9] Qun Huang, Patrick P. C. Lee, and Yungang Bao. 2018. Sketchlearn:
Relieving User Burdens in Approximate Measurement with AutomatedStatistical Inference. In Proceedings of the 2018 Conference of the ACM
Special Interest Group on Data Communication (Budapest, Hungary)(SIGCOMM ’18). Association for Computing Machinery, New York, NY,
USA, 576–590. https://doi.org/10.1145/3230543.3230559[10] Daehyeok Kim, Yibo Zhu, Changhoon Kim, Jeongkeun Lee, and Srinivasan Seshan. 2018. Generic External Memory for Switch Data Planes.
In Proceedings of the 17th ACM Workshop on Hot Topics in Networks (Redmond, WA, USA) (HotNets ’18). Association for Computing Machinery,
New York, NY, USA, 1–7. https://doi.org/10.1145/3286062.3286063[11] Ramana Rao Kompella, Kirill Levchenko, Alex C Snoeren, and George
Varghese. 2009. Every microsecond counts: tracking fine-grain latencies with a lossy difference aggregator. ACM SIGCOMM Computer
Communication Review 39, 4 (2009), 255–266.
[12] Myungjin Lee, Nick Duffield, and Ramana Rao Kompella. 2010. Not
all microseconds are equal: Fine-grained per-flow measurements withreference latency interpolation. In Proceedings of the ACM SIGCOMM
2010 conference. 27–38.
[13] Myungjin Lee, Sharon Goldberg, Ramana Rao Kompella, and George
Varghese. 2011. Fine-Grained Latency and Loss Measurements in the
Presence of Reordering. In Proceedings of the ACM SIGMETRICS Joint
International Conference on Measurement and Modeling of Computer
Systems (San Jose, California, USA) (SIGMETRICS ’11). Association for
Computing Machinery, New York, NY, USA, 329–340. https://doi.org/
10.1145/1993744.1993778[14] N. M. Piratla, A. P. Jayasumana, and H. Smith. 2004. Overcoming
the effects of correlation in packet delay measurements using interpacket gaps. In Proceedings. 2004 12th IEEE International Conference
on Networks (ICON 2004) (IEEE Cat. No.04EX955), Vol. 1. 233–238 vol.1.
https://doi.org/10.1109/ICON.2004.1409134[15] O. Rottenstreich, Y. Kanizo, and I. Keslassy. 2014. The VariableIncrement Counting Bloom Filter. IEEE/ACM Transactions on Networking 22, 4 (2014), 1092–1105. https://doi.org/10.1109/TNET.2013.

APNet 2021, June 24–25, 2021, Shenzhen, China, China
2272604[16] Josep Sanjuàs-Cuxart, Pere Barlet-Ros, Nick Duffield, and Ramana Rao
Kompella. 2011. Sketching the delay: tracking temporally uncorrelated flow-level latencies. In Proceedings of the 2011 ACM SIGCOMM
conference on Internet measurement conference. 483–498.
[17] Lu Tang, Qun Huang, and Patrick PC Lee. 2019. Mv-sketch: A fastand compact invertible sketch for heavy flow detection in network
data streams. In IEEE INFOCOM 2019-IEEE Conference on Computer
Communications. IEEE, 2026–2034.
[18] L. Tang, Q. Huang, and P. P. C. Lee. 2020. SpreadSketch: Toward
Invertible and Network-Wide Detection of Superspreaders. In IEEE
INFOCOM 2020 - IEEE Conference on Computer Communications. 1608–
1617. https://doi.org/10.1109/INFOCOM41043.2020.9155541[19] J. Wang, S. Lian, W. Dong, Y. Liu, and X. Li. 2014. Every Packet
Counts: Fine-Grained Delay and Loss Measurement with Reordering.
In 2014 IEEE 22nd International Conference on Network Protocols. 95–106.
https://doi.org/10.1109/ICNP.2014.30[20] Minmei Wang and Mingxun Zhou. 2019. Vacuum filters: more spaceefficient and faster replacement for bloom and cuckoo filters. Proceedings of the VLDB Endowment (2019).
[21] Xinyuan Wang, Douglas S. Reeves, and S. Felix Wu. 2002. Inter-Packet
Delay Based Correlation for Tracing Encrypted Connections throughStepping Stones. In Computer Security — ESORICS 2002, Dieter Gollmann, Günther Karjoth, and Michael Waidner (Eds.). Springer Berlin
Heidelberg, Berlin, Heidelberg, 244–263.
[22] Tong Yang, Jie Jiang, Peng Liu, Qun Huang, Junzhi Gong, Yang Zhou,
Rui Miao, Xiaoming Li, and Steve Uhlig. 2018. Elastic Sketch: Adaptive and Fast Network-Wide Measurements. In Proceedings of the 2018
Conference of the ACM Special Interest Group on Data Communication (Budapest, Hungary) (SIGCOMM ’18). Association for Computing
Machinery, New York, NY, USA, 561–575. https://doi.org/10.1145/
3230543.3230544