VOL. E105-B NO. 12
DECEMBER 2022
The usage of this PDF file must comply with the IEICE Provisions
on Copyright.
The author(s) can distribute this PDF file for research andeducational (nonprofit) purposes only.
Distribution by anyone other than the author(s) is prohibited.

IEICE TRANS. COMMUN., VOL.E105–B, NO.12 DECEMBER 2022

1530

PAPER

Accurate Parallel Flow Monitoring for Loss Measurements∗
Kohei WATABE†a) , Member, Norinosuke MURAI† , Shintaro HIRAKAWA† ,and Kenji NAKAGAWA†b) , Nonmembers

SUMMARY End-to-end loss and delay are both fundamental metrics
in network performance evaluation, and accurate measurements for theseend-to-end metrics are one of the keys to keeping delay/loss-sensitive applications (e.g., audio/video conferencing, IP telephony, or telesurgery)comfortable on networks. In our previous work [1], we proposed a parallel
flow monitoring method that can provide accurate active measurements ofend-to-end delay. In this method, delay samples of a target flow increase byutilizing the observation results of other flows sharing the source/destination
with the target flow. In this paper, to improve accuracy of loss measurements,
we propose a loss measurement method by extending our delay measurement method. Additionally, we improve the loss measurement method sothat it enables to fully utilize information of all flows including flows withdifferent source and destination. We evaluate the proposed method throughtheoretical and simulation analyses. The evaluations show that the accuracyof the proposed method is bounded by theoretical upper/lower bounds, and
it is confirmed that it reduces the error of loss rate estimations by 57.5% on
average.
key words: active measurement, packet loss, parallel measurement, probe
packet, QoS monitoring

1.

Introduction

When we evaluate network performance, it is important toaccurately measure metrics along an end-to-end path. Endto-end packet loss and delay are both fundamental metrics for network performance evaluations. Internet Service
Providers (ISPs) normally monitor these metrics to keep theservice levels of their networks. ISPs are under an obligation
to keep network performance in compliance with Service
Level Agreements (SLAs). Additionally, it is well known
that real-time applications including audio/video conferencing, IP telephony, and telesurgery are sensitive to end-toend packet loss and delay. Advanced SLAs which stipulate
metrics including delay/loss along an end-to-end path arerequired for delay/loss-sensitive applications, though mostof current SLAs stipulate only packet loss of each link monitored by a Management Information Base (MIB). Hence,
the accurate measurement of end-to-end metrics is important for SLA monitoring, in order to provide advanced SLAs
Manuscript received September 21, 2021.
Manuscript revised December 31, 2021.
Manuscript publicized June 29, 2022.
† The authors are with the Graduate School of Engineering,
Nagaoka University of Technology, Nagaoka-shi, 940-2188 Japan.
∗ An earlier and short version of this paper was presented at the
15th International Conference on Network and Service Management (CNSM 2019) [2].
a) E-mail: k_watabe@vos.nagaokaut.ac.jpb) E-mail: nakagawa@nagaokaut.ac.jp
DOI: 10.1587/transcom.2021EBP3160

for delay/loss-sensitive applications.
It is valuable to measure the end-to-end metrics on a network without relying on the information inside the network
such as MIB. If we are interested in end-to-end metrics acrossmultiple ISPs, no one will have access to all the relevant network equipment. From the viewpoint of network researchers
who do not have direct access to the network equipment, it
is useful to achieve the measurement only from the information that can be accessed from the outside. In addition, it isdifficult to accurately estimate a fine-grained loss rate along
an end-to-end path due to the time synchronization problem.
In measurements of end-to-end metrics for networks,an active measurement in which probe packets are injected
into a network is commonly used, and various measurement
tools for active measurements have been proposed in prior
works [3]–[8]. The literature details attempts to improvemeasurement accuracy without increasing the number ofprobe packets [9]–[11] since increasing the number of probe
packets leads to greater communication overheads and the
intrusiveness problem [8], [12]. In the modern Internet, alarge delay (that exceeds 150 [ms] as mentioned in ITU-T
Recommendation G.114 [13]) rarely occurs. Packet losses
are also rare events as ITU-T Recommendation Y.1541 [14]defines QoS class with upper bounds 1.0×10−5 of end-to-end
loss rate for emerging applications. It is difficult to capturesuch rare events using a limited number of probe packets of asingle flow, even if active measurements are easy to perform.
While most of the prior works utilize only one probe
flow to measure the end-to-end metric regarding one path, we
proposed a parallel flow monitoring method in which delay
on a flow is accurately measured by utilizing the observation
results of other flows sharing the source/destination [1], [8].
In daily operations, ISPs are monitoring end-to-end metricsof the multiple paths on their network in parallel. The method
in [1] utilizes this parallel monitoring.
In this paper, based on the delay measurement method
in [1], we propose a loss measurement method that fully
utilizes flows, including flows with different sources anddestinations. We extend the delay measurement method to aloss measurement with a weighted loss estimator. In the proposed method, information regarding lost probe packets inthe other probe flows is utilized in estimating the loss rate ona path of the target probe flow. As we mentioned above, it isdifficult to capture packet loss events by the limited numberof probe packets in a target probe flow since the packet losses
are rare events. Even if a target probe flow fails to capture loss

Copyright © 2022 The Institute of Electronics, Information and Communication Engineers

WATABE et al.: ACCURATE PARALLEL FLOW MONITORING FOR LOSS MEASUREMENTS

events, the proposed method can estimate the loss statistics
on the path of the target probe flow since another probe flow
may capture loss events. Therefore, the proposed method
transcends a fundamental accuracy bound of conventional
active measurements of the loss statistics. The method andnetwork tomography are totally different from our method
because our method estimates loss statistics along a path. Tomography estimates link-level statistics from statistics along
a path. The proposed method does not compete with tomography. This is because the statistics along a path can be used
as tomography inputs. By combining the proposed method
and tomography, it may be possible to improve the accuracyof tomography. Additionally, we improve the accuracy of theextended method by fully utilizing information of all flows
with a recursive conversion of the information of the otherflows. The proposed method utilizes the information of allprobe flows that share a part of the path with a target probe
flow though the method in [1] only utilizes information offlows that has the same source/destination with a target probe
flows.
The proposed method is extremely versatile under mild
assumptions. The method does not require any internal information of a measured network, including the topology ofthe measured network, and it only uses delay and loss ofeach flow. Note that the method does not assume that all
possible paths in a network are simultaneously monitored.
It can appropriately perform when only a part of paths in a
network are monitored.
In summary, this paper makes the following contributions.
• Parallel loss measurements: We propose a parallel
monitoring method for packet loss. The method extends the delay measurement method that utilizes parallel active probe flows to a loss measurement, thereby
improving measurement accuracy of loss statistics.
• A recursive conversion technique: Our loss measurement includes a novel technique called recursive
conversion that is different from the previous delay
measurement method [1] to improve accuracy in loss
measurements. The technique enables us to fully utilize
information of all probe flows for a measurement.
• Theoretical accuracy analysis: We provide a theoretical analysis of the accuracy of our method. The
upper and lower bounds of the accuracy of the method
are calculated.
• Simulation-based evaluations: We confirm that our
method provides accurate measurements through simulations. It is also confirmed that the simulation results
are consistent with analytical results.
The rest of the paper is organized as follows. First, we
mention a network model and assumptions in Sect. 2. Next,
Sect. 3 summarizes the parallel flow monitoring method fora delay measurement in our previous study [1]. In Sect. 4, we
explain a proposed loss measurement method that fully utilizes information regarding all flows in a network. In Sects. 5

1531

and 6, we provide theoretical analysis and simulation-based
evaluation of the proposed method, respectively. After discussing some related works in Sect. 7, we conclude the paper
and mention future works in Sect 8.
2.

A Network Model and Assumptions

Since the method we propose in this paper is based on themethod [1], most of the assumptions are inherited from [1]to this paper. A wired network considered within the scopeof this work is represented by a directed graph. A packet isdelivered from a source to a destination along a path. Paths
are stable in a measurement period (generally within several
minutes) since paths are not changed frequently. Packets
are delayed and may be lost at nodes or links on a path.
We assume that an end-to-end delay consists of propagation
delay and queueing delay since both delays are dominant in
the modern Internet [15]. Propagation delay can be regarded
to be a constant for a path while queueing delay dynamicallychanges reflecting traffic status.
In this paper, we assume that most of the loss events arecaused by buffer overflows in interfaces placed on links withcongestions. Inevitably, packet loss events highly depend onqueueing delay. We assume that links with large queueing
delay, i.e. links with many packet loss events, are sparseamong all links in a network, and the ratio of periods withlarge queueing delay on a link to other periods is small. The
validity of the assumption can be confirmed since the average
link utilization of the modern Internet is maintained low [16].
Note that we do not assume a congested link is unique, andwe do not need to know the topology of a network.
Though the metric we want to measure is loss statistics
along a path in wired packet networks, we utilize delay information to improve accuracy of loss measurements. To measure packet loss and packet delay on paths, probe packets are
periodically injected for all or a part of paths on a network. A
delay or loss experienced by a probe packet can be obtainedby matching the packets at the source and the destination.
Generally, end-to-end delays on networks are the order ofmilliseconds. If we want to accurately measure end-to-end
delays along with loss statistics, time synchronization on theorder of microseconds like GPS network time synchronization is assumed on all senders and receivers. If we want tomeasure only loss statistics, strict time synchronization is not
required. In our previous method [1], the time synchronization lag is treated like a propagation delay and is subtracted
from the delay experienced by probe packets. Since sample
conversion/uniting is executed based on the queuing delaythat does not include the propagation delay and the time synchronization lag, the lag does not deteriorate the accuracy ofthe measurement.
3.

Parallel Flow Monitoring for Delay

Since we assume sparseness of congested links, queueing delay processes within a congestion period on multiple paths
that have common links frequently overlap (see Fig. 1), andIEICE TRANS. COMMUN., VOL.E105–B, NO.12 DECEMBER 2022

1532

Fig. 3Fig. 1

Overlap of queueing delay processes in a congestion period.

4.

Clusters for each common link that causes a large delay.

Parallel Flow Monitoring for Loss Statistics

In this paper, we will extend the method of [1], which wasmentioned in Sect. 3, to a loss measurement and improve its
accuracy by utilizing information of all flows including flows
with different source and destination. By utilizing all flows,
the proposed method makes it possible to capture loss events
that occur with extremely low probability, such as 1.0 × 10−5
defined as the strictest QoS class in ITU-T Recommendation
Y.1541.
4.1

Fig. 2 Conversion of delay samples in congestion periods of multiple
flows whose start and end times are respectively almost the same.

the samples within the congestion periods can be converted.
In the method in [1], the ith sample for Flow A is expressedby (tAi , xAi ) where tAi and xAi denote injection time and experienced delay of the ith probe packet, respectively. A
congestion period is observed as consecutive samples thatare larger than a threshold xth . The set of samples within
the jth congestion periods on the path of Flow A is denoted
as XA, j . If there are congestion periods of multiple flows
whose start and end times are respectively almost the same(i.e., they are closer than a constant probe interval δ), thesamples in the congestion periods are converted each otheras shown in Fig. 2. After the conversion, clustering process
starts. Delay samples in the congestion periods are formatted to n-dimensional vectors, and the vectors are divided
into clusters for each common link that causes a large delay(Fig. 3). A clustering technique in machine learning is utilized to divide them into clusters. A queueing delay processcaptured by probe flows in the same cluster are determined
to be overlapped, and the delay samples are converted between each other, by modifying the injection time and delay
to that of the target flow. By the conversions, the number ofdelay samples of each flow increases, thereby improving theaccuracy of the delay measurement.

Extension to Loss Measurements

The proposed method achieves accurate loss measurements
by uniting samples of loss events. As with the method in [1],the uniting in the proposed method is based on delay information, though the metric we want to measure in the proposed
method is loss statistics. In the proposed method, samples
that capture loss events are recorded for each congestion
period, and samples are united each other at the time of conversion of delay samples (Fig. 4). Since we assumed that themain cause of packet loss is buffer overflows, most of packet
loss events occur within congestion periods. Therefore, we
can consider that loss events within a congestion period occur at the link which causes the congestion. First of all, a
set LA, j of samples of loss events between the first and last
samples in delay samples XA, j are recorded. A loss sample
in LA, j is defined as (tAi , ∞) that corresponds to a lost probe
packet within the jth congestion period of Flow A. Based on
the method in [1], samples XA, j for delay are converted eachother, thereby obtaining samples XA, j which includes converted samples. When the samples XB,k are converted to thejth congestion period on the path of Flow A, samples LB,k ofloss events are united to samples LA, j of loss events within
the jth congestion period on the path of Flow A. As a result,the samples LA, j which includes united samples within thejth congestion period on the path of Flow A are updated toLA, j ∪ LB,k . Note that XA, j and LA, j respectively include
converted and united samples from other flows while XA, j
and LA, j represent the original samples of Flow A.
Using delay samples XA, j and loss samples LA, j that
include converted/united samples, we can accurately obtainvarious statistics regarding delay and loss. These samples

WATABE et al.: ACCURATE PARALLEL FLOW MONITORING FOR LOSS MEASUREMENTS

Fig. 4

United samples of loss events.d

allow us to calculate not only the loss rate of packets foreach flow over the entire measurement period but also theloss rate of any partial period in any granularity. By extracting a period when end-to-end delay exceeds a certain
threshold, it is possible to detect congestion that occurred in
an extremely short time. By calculating the loss rate within
the short congestion, we can analyze the loss rate in detailfor each individual congestion. Fine-grained measurement
causes difficult estimation of the loss along a path from thelink level measurement including MIB. This is because delay
experienced by a packet before reaching each link is different, so that a packet sent at time t is not associated with theloss rate at time t on a link. In addition, even for long-term
measurements, packet loss events for each link are not independent, so it is not possible to simply calculate a loss
rate along a path. Moreover, it is noteworthy that the proposed method simultaneously measures delay and loss along
a path. The obtained samples are also useful for analyzing
the relationship between delay and loss along a path. The
following is an example of an estimator of loss rate on eachpath.
To provide an unbiased estimator of loss rate on each
path, samples should be weighted since the samples of loss
events in the proposed method are biased on a time-space,
while most of the conventional loss measurements using
active probes assume that probe packets are uniformly distributed. The weight ws of a sample s is given as|XA, j ∪ LA, j |ws =|XA, j ∪ LA, j |
Then,
Õ Õ
j s ∈ LA, j

fors ∈ LA, j .

ws|XA | + |LA |provides an estimator of loss rate on the path of Flow A,
where |XA | and |LA | denote the number of all delay samples
and loss samples of Flow A, respectively.
The communication overhead of the proposed method
is completely the same as the conventional method that measures delay and loss. The number of probe packets is not increased by the proposed method. Both the proposed method
and the conventional method aim to measure loss statistics

1533

on N paths by obtaining samples of N probe flows. The number of injected probes and the number of probes that passthrough each link are exactly the same. Both the proposed
and the conventional method gather information of probe
after a measurement from each endpoint to a measurement
server. Because we consider the situation that a measurement server provides various packet-level statistics including
delay distribution, loss duration, and so on. The calculationof these statistics requires packet-level delay/loss information. The communication overhead for the gathering process
is common for both methods, and it is small compared tothe overhead of probe packets. For example, each endpoint
sends just 1 packet for the gathering process per 100 probe
packets. The number of packets for the gathering process is
proportional to the number of probe packets. Namely, lessnumber of probe packets also reduces the number of packets
for the gathering process.
The computational complexity of the proposed method
is the same as the method in [1]. A measurement server
checks the delay/loss status of each packet in reports fromendpoints. The computational complexity of the process
is O(N P), where N and P denote the number of flows
and the number of probe packets in a flow, respectively.
The conventional method finishes after this process, thenthe computational complexity of the conventional methodis O(N P). Since the proposed method requires additional
processes for conversion and uniting processes, the computational complexity of the proposed method is roughly
O(N P + N 2 M 2 + N M L + L 3 K 3 ), where M denotes the maximum number of congestion periods of a flow. L and K
denote the maximum number of samples in a congestion
period and the maximum number of flows in a link, respectively. Since we assume sparseness of congested links M
and L are significantly smaller than P. Moreover, in general
networks, N, L, and K are small compared to P. Needlessto say, the proposed method requires a longer processing
time compared to the conventional method. However, therequirement of the processing time is not severe, since thepacket-level statistics are calculated after a measurement period in an offline manner.
4.2

Recursive Conversion Technique to Utilize All Probe
Flows

By repeatedly converting samples obtained from each probe
flow, the proposed method utilizes information of all probe
flows that include flows with different sources and destinations. Even if both source and destination are different, flowsthat share a part of paths includes information of the target
flow. By checking whether conversion of samples is possible
for all pairs of congestion periods of all probe flows, trees that
represent dependency of conversions are generated for eachcongestion period (see Fig. 5). The proposed method recursively converts/unites samples from the leaves to the root of
the tree. In the case of Fig. 5, the samples of Flow D can beconverted/united to the samples of Flow B since Flow D and
Flow B share their destinations in Fig. 10. These samples

IEICE TRANS. COMMUN., VOL.E105–B, NO.12 DECEMBER 2022

1534

Fig. 5

An example of a dependency tree for a recursive conversion.

including samples converted/united from Flow D can be converted/united to the samples of Flow A that share the sourcewith Flow B. As a result, the samples of Flow D that shareneither sources nor destinations can be converted/united tothe samples of Flow A through the samples of Flow B.
In the evaluation we will perform in Sect. 6, we measure the loss rate of the full-meshed paths, but the proposed
method can also be applied to a subset of the universal path
set. However, if the following conditions do not hold, theaccuracy improvements by the proposed method will not bebenefited.
• Two or more paths are measured at the same time.
• At least one link is included in multiple paths.
• In all path pairs that share a link, at least one pair hascommon a source or a destination.
If the number of measured paths or the number of sharedlinks is small, the accuracy improvement may be limited.
However, the accuracy of the proposed method is guaranteed
to be equal to or higher than the conventional method in themeasurement for any subset of paths.
The computational complexity of the conversion process of the proposed method is O(N M) for each congestion
period, where N and M denote the number of flows andthe maximum number of samples in a congestion period,
respectively.
5.

Theoretical Accuracy

With an assumption regarding the injection time of probe
packets, we provide a theoretical analysis of accuracy
bounds. We assume that an injection time of a probe packet
follows a uniform distribution on a measurement period [0,T]and these injection times are independent and identically distributed (i.i.d.). If we decide times of probe packets in such amanner, an injection time of a packet that is decided later may
be injected earlier than the first decided packet, namely, theorder of decision will not correspond to the order of packet
injection. However, the order of the injection is not important in the discussion of this section. The assumption ofi.i.d. injection time is not always suitable for probe injectionof conventional loss measurements or simulation settings in
Sect. 6. However, the theoretical analysis under the assumption gives us a fundamental insight since the probe injection
under the assumption corresponds Poisson process, one of
the most basic probe injections, when T → ∞. The theoretical analysis for the Poisson process is a lough approximationof analysis for periodical probe injection that we will performin Sect. 6.

Under the assumption, an estimator of conventional loss
measurements can be modeled by a binomial distribution. In
conventional loss measurements, probe packets are injected,
and the number |LA | of loss samples is observed. If weassume the packet injection times of probe packets follow
a uniform distribution on a measurement period, the trials
to inject probe packets investigating loss events can be regarded as Bernoulli trials. Then, the number |LA | of loss
samples follows a binomial distribution B(n, p), where n andp represent the number |XA | + |LA | of probe packets and theground truth of the loss rate on path A, respectively. The
conventional estimator p̂ for path A is the random variable|LA | (i.e., the number of loss samples) divided by the total
number |XA | + |LA | of probe packets.
When we evaluate the accuracy of the conventional
method by using Root Mean Squared Errors (RMSE), we
can analytically calculate the accuracy. From the definitionof Mean Squared Errors (MSE), MSE can be expressed as asum of variance Var[ p̂] and bias E[ p̂] − p of the estimator.
MSE = E[( p̂ − p)2 ]= Var[ p̂] + (E[ p̂] − p)2 .
Since the conventional estimator with uniformly distributed
probe packets is an unbiased estimator, MSE is equal to thevariance of the estimator p̂. As we mentioned above, theestimator is the random variable |LA | that follows a binomial
distribution divided by a constant |XA | + |LA |. Since thevariance of |LA | ∼ B(n, p) is np(1 − p), MSE can be derived
as follows:
MSE =p(1 − p).
|XA | + |LA |(1)

In a similar manner, we are able to calculate the upperbounds of MSE of the proposed estimator. In the proposed
method, when we measure the loss rate on a path, we convert and unite samples in congestion periods from the otherflows. In the most inaccurate case of the proposed method,no samples are converted/united from the other flows, andthe sampling rate is the same as the conventional method.
Namely, the upper bound of MSE in the proposed method is
MSE of the conventional estimator shown in Eq. (1).
On the other hand, the upper bounds of MSE of the
proposed method are the MSE when all samples in the flowsthat share a part of paths with target flow are converted/
united. By conversion and uniting process, the sampling
rate increase in a pseudo manner. If the number of converted/united flows is m in a congestion period, the sampling
rate increases m+1 times in the congestion period comparing
to the original rate. Though the pseudo increase of sampling
rate is temporal, the temporal increase has the same effectas constantly increasing the rate of probe packet injection.
Because we assume that most of the packet loss events arecaused by buffer overflows. Consequently, the lower boundof MSE of the proposed method can be derived by
MSElb =

p(1 − p),mmax (|XA | + |LA |)(2)

WATABE et al.: ACCURATE PARALLEL FLOW MONITORING FOR LOSS MEASUREMENTS

where mmax denotes the maximum number of flows that passlinks contained in the path of Flow A.
6.

Table 1

Packet size
Traffic pattern
Traffic intensity

User(Bursty)

Packet size
Traffic pattern

Evaluations

Traffic intensity

Simulation Settings

The network we simulated resembles Internet2 topology [18] with 9 nodes and 13 links whose capacities are
15.552 [Mbps] (see Fig. 10). The numerical values written beside the links in Fig. 10 indicate propagation delay inms (milisecond), and we set them proportional to the distance between the nodes in Internet2. The topology of thissimulation resembles the topology of Internet2 core transport network, but the assumptions of the proposed method
shown in Sect. 2 are applicable to more general wired networks. Note that the simulation results are not limited tocore transport networks.
2 types of user flows and 1 type of probe flow listed inTable 1 stream between all pairs of 9 nodes (i.e. 9 × 8 = 72
flows for each type in the entire network). Phases of packet
injection are randomized while probe packets are injectedperiodically. The probe packets are commonly used for the
proposed method and the conventional method. The communication overheads of the proposed method and the conventional method are completely equivalent in the simulation
since the probe packets used by both methods are the same.
Since the capacity of all the links are 15.552 [Mbps], if two
or more flows of bursty traffic are joined at the link, traffic intensity on a link temporally exceeds the link capacity,
thereby occurring a buffer overflow due to temporal capacity
shortage. Though the congested links are sparse, congestions
on multiple links can occur at the same time. Each node isconfigured with a drop-tail queue whose maximum size is1024 for all interfaces. The simulation time is 1005.0 [s] andwe only use the data from 5.0 [s] to 1005.0 [s].
To achieve valid evaluations through the simulation, it
is important that the statistics regarding probe packet losses
are accurately emulated in the simulation. First, the essential thing is to make the loss rate, which is one of the mostimportant statistics, realistic. In the above simulation settings, we tuned the traffic intensity in the simulation so thatthe loss rate corresponds to QoS classes defined by ITUT Recommendation Y.1541 [14]. Also, since the proposed
method unites loss events observed on multiple flows in acongestion period, it is very important that the duration of
the loss events in a congestion period is reasonable. In theabove simulation settings, the duration of loss events at Link
3-2, which has the highest loss rate, ranges from 0.14 s to
1.01 s. The duration of the loss events in our simulationis consistent with the distribution of duration of loss events
reported in [19], which is one of the few studies regarding
the duration of loss events.

Types of traffic in our simulations.

User(Stationary)

We perform ns-3 [17] simulations to confirm that the numberof captured loss events increases and accuracy of a loss rateestimation is improved.
6.1

1535

Bursty period
Idle period
Probe

Packet size
Traffic pattern
Packet intervals δ

600 [Byte]
Poisson arrivals
388.8 [Kbps](4% of a link capacity)
500 [Byte]
On/off process with periodic
arrivals in bursty periods
10,000 [Kbps] in bursty periods
0 [bps] in idle periods
Exponential distribution
with mean 1.0 [s]Exponential distribution
with mean 100.0 [s]
74 [Byte]
Periodic arrivals
200 [ms]

The parameters of the proposed method are set as follows. The delay threshold xth to distinguish congestion period is set to 0.01 [s]. We use Minimum Entropy Clustering (MEC) [20] for clustering, and its radius parameter r is
set to 0.1.
These improvements in accuracy have an extremely
large impact on practical measurements. As a typical example, we focus on Link 3-2 where the most loss eventswere observed. The RMSE of Link 3-2 in the proposed
method and the conventional method are 0.28 × 10−3 and0.72 × 10−3 , respectively. Since the loss rate on the path is
1.5 × 10−3 , the ratio of RMSE to the loss rate is 47% and19%, respectively. Assuming unbiased estimation and errors following a normal distribution, the probability that theconventional estimator is in range [1.0 × 10−3, 2.0 × 10−3 )is 51%. In other words, the first digit of the estimator is
not correct with a probability of 49%. In contrast, the first
digit of the proposed estimator is correct with a probabilityof 91%. After all, when we estimate a loss rate 1.0 × 10−3 ofclasses 0-4 defined in ITU-T Recommendation Y.1541, theaccuracy improvement by the proposed method has a large
impact on the measurement. This tendency is even more
pronounced for smaller loss rates. For Link 2-1 with the loss
rate 2.1 × 10−4 , the ratio of RMSE to the loss rate is 27% for
the proposed estimator, while it is 93% for the conventional
estimator.
6.2

Simulation Results

We evaluate the accuracy of the loss rate estimation of the
proposed method. The simulation was repeated 10 times
by changing the phase of the probe packet injection time.
Figure 6 shows the loss rate on the paths where loss eventswere captured at least once by stationary user flows. Root
Mean Squared Errors (RMSE) between the estimator of loss
rate and loss rate experienced by packets of the stationary
user flows are calculated. Note that the loss rate experienced
by packets with Poisson arrivals corresponds to the time
average of the loss process due to PASTA (Poisson Arrivals
See Time Averages) property [21]. The result is shown inIEICE TRANS. COMMUN., VOL.E105–B, NO.12 DECEMBER 2022

1536

Fig. 6

Fig. 9Estimators of packet loss rate in the proposed and conventional methods.

Fig. 7

RMSE of loss rate estimations.

Fig. 8MAPE of loss rate estimations.

The number of loss events that are captured by probe flows for each path.

Fig. 7. Note that we use RMSE instead of MSE to make iteasier to compare with the estimator. The maximum loss
rate experienced by stationary user flows was about 1.7 ×
10−3 . The conventional estimator in this section is simply
calculated as the ratio of the number of loss samples to thetotal number of samples. Note that it is not the method in [1].
The simple estimator is adapted by many prior works [10],[11], [22]. The results on paths in which any loss event is not
captured by the stationary user flow are omitted in Fig. 7. In
the results of no recursive conversion in Fig. 7, only samplesof flows that have the same source/destination with a target
probe flow are converted.
We can confirm that RMSE of each probe flow is reduced by the proposed method. Compared to the conventional method, the proposed method without recursive
conversion provides 31.3% reduction of RMSE on average. Since the proposed method with recursive conversion achieves 57.5% reduction of RMSE on average, it canbe confirmed that recursive conversion achieves further improvement in accuracy. Therefore, the proposed method canWATABE et al.: ACCURATE PARALLEL FLOW MONITORING FOR LOSS MEASUREMENTS

Fig. 10

Network topology on our evaluations.
Fig. 11

improve the accuracy of the loss rate measurement, though
the number of probe packets in the entire network does notincrease compared to that of the conventional method. The
accuracy improvement is caused by the increase of samples that capture loss events. The increase of the samples
is shown in Fig. 9. “Expected” in Fig. 9 represents the expected number of loss events experienced by probe packets
on a path. The recursive conversion unites samples from
more flows than the no recursive conversion, thereby increasing the number of captured loss events. In principle,
it is impossible for the conventional method to estimate theloss rate less than 2.0 × 10−4 since the number of the probe
packets per flow is 5000 in the simulation. However, theproposed method overcomes this fundamental limitation in
accuracy. We also calculate Mean Absolute Percentage Error (MAPE) and show the results in Fig. 8. We got a similar
result with the result of RMSE.
To analyze the ratio of inappropriate samples to the expected samples by an ideal measurement, we confirm thenumber of loss samples before and after the clustering process in the proposed method. In the proposed method, as inour previous method [1], after converting/uniting samples,
inappropriate samples are excluded in the clustering process. To simplify the analysis, we consider the worst-casetrials with the most loss samples united, focusing on Link 32, which causes the most loss events. We depict the numberof the loss samples in the worst-case trial in Fig. 11. In
Fig. 11, “Before clustering” and “After clustering” represent
the number of loss samples before and after the clustering
process. “Ideal” in Fig. 11 indicates the expected number ofloss samples if we achieve perfect uniting. We can confirm
that more loss samples were counted than expected due tofalsely uniting loss samples before the clustering process.
However, loss samples that may be falsely united are excluded (a little excessively) in the clustering process. As aresult, the final samples obtained by the proposed method
do not include false loss samples. Although excessive exclusion is not desirable, the estimator of the proposed method
is more accurate than that of the conventional method while
maintaining the unbiased estimator. The above results, inwhich the false loss samples are sufficiently excluded, areconsistent with the result in Fig. 6 and Fig. 7.
6.3

1537

Analytical Results

In this section, we compare the simulation results with thetheoretical upper/lower bounds of the proposed method that

The number of loss samples before and after clustering process.

we mentioned in Sect. 5. In the simulation settings of Sect. 6,
we count the number of flows that pass through each link andcalculate the maximum number mmax of flows that pass links
contained in a path. Fig. 12 shows the results of the squareroot of Eqs. (1) and (2) based on mmax in the simulation.
The two types of red bars are the same as the results of the
proposed method shown in Fig. 7. The black lines show theupper/lower bounds of RMSE.
We can confirm that most of the results fall between
upper and lower bounds in Fig. 12. Comparing the results ofFig. 6 and Fig. 12, the proposed method achieves a similar accuracy with the theoretical lower bounds in the measurementof paths with a relatively small loss rate such as Flow ID 0-3.
On the other hand, it can be confirmed that RMSE of a partof paths with a large loss rate does not close to the lower
bounds. This is because paths with a large loss rate have arelatively long delay period, and there is a high probability
that other delays will occur during the delay period. The
samples that observe the other delays are removed as shownin Fig. 3. In addition, since Eq. (1) represents the mean ofMSE, the RMSE of the measurement results of some paths
exceeds the upper bound due to the randomness of the measured values.
7.

Related Works

There is a rich collection of literature that aims at measuring end-to-end metrics [3], [8]–[10], [23]–[27]. Some prior
works [9], [10] tried to estimate high quantile of end-to-end
delays by active measurements. Choi et al. [9] proposeda scheme that estimates high quantile with bounded errors.
The scheme allows us to know the minimum number ofprobe packets needed to bound the error of quantile estimation within a prescribed accuracy. Sommers et al. [10] also
proposed an estimator of high quantile. Since the estimator provides confidence intervals, we can tune the numberof probe packets to achieve the required accuracy. Someworks [3], [25], [27] focus on loss measurements. Sommers et al. [3], [25] tackled the problem to estimate a mean
loss duration by a statistical approach using back-to-backpackets. Baccelli et al. [27] and Parker et al. [22] provided
how to chose the best probing on an active measurement.
The effect of probe packets on the path quality has been
also studied [4], [7], [8], [12], [21]. References [4], [21]showed that an arrival process of the probe packets affects

IEICE TRANS. COMMUN., VOL.E105–B, NO.12 DECEMBER 2022

1538

Fig. 12Upper/lower bounds of theoretical accuracy of the proposed method.

accuracy of end-to-end delay/loss measurement. Degradation of measurement accuracy caused by probe traffic load
were studied in references [7], [8], [12]. The limitation of
single flow measurements can be understood by these works.
The optimum probe rate that does not affect the path quality
has been investigated in these works [6], [7], [11], and the
proposed method provides a method to maximize the accuracy by utilizing the probe packets with this optimum proberate.
In recent years, research on measurements with network
telemetry has been actively studied. Network telemetry is amodern and excellent method. However, it depends on thefunctions of network devices, so it is not always available.
Active measurements, including the proposed method, canbe performed easily by sending packets to a network, andthe measurements do not depend on the functions inside
networks. Hence, traditional active measurements are still
a powerful tool for network measurements, especially for
researchers who do not have direct access to the functions of
network devices. In addition, active measurements are also
effective for measurements across multiple organizations,such as Internet-wide measurements.
8.

Conclusions and Future Works

We proposed a loss measurement method that fully utilizes
flows, including flows with different sources and destinations in this paper. We extended the delay measurement
method [1] that utilizes parallel active probe flows to loss
measurements. Additionally, our method includes a recursive conversion technique that enables us to fully utilize
information of all probe flows for a measurement though themethod [1] only utilize information of flows that have thesame source/destination with a target probe flow.
We provided the theoretical analysis and the simulationbased evaluation for the proposed method. We show thatthe accuracy of the proposed method is bounded by upper and lower bounds in the theoretical analysis. Throughsimulation-based evaluation using ns-3 simulator, we confirmed that the proposed method can reduce estimation errors
by 57.5% on average.
As future research, we plan to develop highly accuratedelay/loss tomography using the parallel monitoring method.
Additionally, we also have a plan to implement the proposed
method for a real network, and evaluate the effectiveness ofthe method. Our future work includes the reduction of thecomputational complexity of the proposed method.
References[1] K. Watabe, S. Hirakawa, and K. Nakagawa, “A parallel flow monitoring technique that achieves accurate delay measurement,” IEICE
Trans. Commun., vol.E102-B, no.4, pp.865–875, April 2019.
[2] K. Watabe, N. Murai, S. Hirakawa, and K. Nakagawa, “Accurate
loss estimation technique utilizing parallel flow monitoring,” Proc.
15th International Conference on Network and Service Management(CNSM 2019) Short paper, Halifax, NS, Canada, 2019.
[3] J. Sommers, P. Barford, N. Duffield, and A. Ron, “A geometricapproach to improving active packet loss measurement,” IEEE/ACM
Trans. Netw., vol.16, no.2, pp.307–320, 2008.
[4] K. Watabe, Y. Honma, and M. Aida, “Probe interval designs that
improve accuracy of CoMPACT monitor,” Simulation Modelling
Practice and Theory, vol.19, no.1, pp.56–68, 2011.
[5] A. Abdelkefi, Y. Jiang, B.E. Helvik, G. Biczók, and A. Calu, “Assessing the service quality of an internet path through end-to-end
measurement,” Computer Networks, vol.70, no.9, pp.30–44, 2014.
[6] S. Lee, K. Levanti, and H.S. Kim, “Network monitoring: Present
and future,” Computer Networks, vol.65, no.2, pp.84–98, 2014.
[7] K. Watabe and K. Nakagawa, “Intrusiveness-aware estimation forhigh quantiles of a packet delay distribution,” Proc. 2015 IEEE International Conference on Communications (ICC 2015), London, UK,
pp.6169–6174, 2015.
[8] K. Watabe, S. Hirakawa, and K. Nakagawa, “Accurate delay measurement for parallel monitoring of probe flows,” Proc. 2017 13th International Conference on Network and Service Management (CNSM
2017), Tokyo, Japan, 2017.
[9] B.Y. Choi, S. Moon, R. Cruz, Z.L. Zhang, and C. Diot, “Quantile
sampling for practical delay monitoring in internet backbone networks,” Computer Networks, vol.51, no.10, pp.2701–2716, 2007.
[10] J. Sommers, P. Barford, N. Duffield, and A. Ron, “Accurate andefficient SLA compliance monitoring,” ACM SIGCOMM Computer
Communication Review, vol.37, no.4, pp.109–120, 2007.
[11] F. Baccelli, S. Machiraju, D. Veitch, and J. Bolot, “On optimal
probing for delay and loss measurement,” Proc. 7th ACM Conferenceon Internet Measurement (IMC 2007), San Diego, CA, USA, pp.291–
302, 2007.
[12] M. Roughan, “Fundamental bounds on the accuracy of network performance measurements,” ACM SIGMETRICS Performance Evaluation Review, vol.33, no.1, pp.253–264, 2005.
[13] “One-way Transmission Time,” ITU-T Recommendation G.114,
2003.
[14] “Network Performance Objectives for IP-based Services,” ITU-T
Recommendation Y.1541, 2011.
[15] H. Pucha, Y. Zhang, Z.M. Mao, and Y.C. Hu, “Understanding network delay changes caused by routing events,” ACM SIGMETRICS
Performance Evaluation Review, vol.35, no.1, pp.73–84, 2007.
[16] “CAIDA: The Cooperative Association for Internet Data Analysis.”

WATABE et al.: ACCURATE PARALLEL FLOW MONITORING FOR LOSS MEASUREMENTS[17] T.R. Henderson, M. Lacage, G.F. Riley, G. Dowell, and J.B. Kopena,“Network simulations with the Ns-3 simulator,” Proc. ACM SIGCOMM 2008, Seattle, WA, USA, p.527, 2008.
[18] “Internet2 Network NOC.”[19] Y. Zhang and N. Duffield, “On the constancy of internet path properties,” Proc. 1st ACM SIGCOMM Workshop on Internet Measurement (IMW 2001), San Francisco, CA, USA, pp.197–211, 2001.
[20] H. Li, K. Zhang, and T. Jiang, “Minimum entropy clustering andapplications to gene expression analysis.,” Proc. 2004 IEEE Computational Systems Bioinformatics Conference (CSB 2004), Stanford,
CA, USA, pp.142–151, 2004.
[21] F. Baccelli, S. Machiraju, D. Veitch, and J. Bolot, “The role of PASTA
in network measurement,” ACM SIGCOMM Computer Communication Review, vol.36, no.4, pp.231–242, 2006.
[22] B.M. Parker, S.G. Gilmour, and J. Schormans, “Measurement ofpacket loss probability by optimal design of packet probing experiments,” IET Communications, vol.3, no.6, pp.979–991, 2009.
[23] J.C. Bolot, “Characterizing end-to-end packet delay and loss in theinternet,” J. High Speed Netw., vol.2, no.3, pp.289–298, 1993.
[24] K.P. Gummadi, S. Saroiu, and S.D. Gribble, “King: Estimating
latency between arbitrary internet end hosts,” Proc. 2nd ACM SIGCOMM Workshop on Internet Measurment (IMW 2002), Marseille,
France, pp.5–18, 2002.
[25] J. Sommers, P. Barford, N. Duffield, and A. Ron, “Improving accuracy in end-to-end packet loss measurement,” ACM SIGCOMM
Computer Communication Review, vol.35, no.4, pp.157–168, 2005.
[26] L. De Vito, S. Rapuano, and L. Tomaciello, “One-way delay measurement: State of the art,” IEEE Trans. Instrum. Meas., vol.57,
no.12, pp.2742–2750, 2008.
[27] F. Baccelli, S. Machiraju, D. Veitch, and J. Bolot, “Probing for loss:
The case against probe trains,” IEEE Commun. Lett., vol.15, no.5,
pp.590–592, 2011.

Kohei Watabe
received his B.E. and M.E.
degrees in Engineering from Tokyo Metropolitan University, Tokyo, Japan, in 2009 and 2011,
respectively. He also received the Ph.D. degreefrom Osaka University, Japan, in 2014. He was a
JSPS research fellow (DC2) from April 2012 toMarch 2014. He was an Assistant Professor of
the Graduate School of Engineering, Nagaoka
University of Technology, from April 2014 to
October 2019. He has been an Associate Professor of the Graduate School of Engineering,
Nagaoka University of Technology, since November 2019. He is a memberof the IEEE and the IEICE.

Norinosuke Murai
received his B.E. and
M.E. degrees in Engineering from Nagaoka University of Technology, Niigata, Japan, in 2017and 2019, respectively.

1539
Shintaro Hirakawa
received his B.E. and
M.E. degrees in Engineering from Nagaoka University of Technology, Niigata, Japan, in 2016
and 2018, respectively.

Kenji Nakagawa
received the B.S., M.S.,
and D.S. degrees from Tokyo Institute of Technology, Tokyo, Japan, 1980, 1982, and 1986,
respectively. In 1985, he joined Nippon Telegraph and Telephone Corporation (NTT). Since
1992, he has been an Associate Professor with
Nagaoka University of Technology, where he has
been a Professor since 2012. In 2022, he retired
from the Nagaoka University of technology andnow he is a Professor Emeritus. His research interests include information theory, performance
evaluation of networks, and queueing theory.