This is the post-print version of the following article: Kohei Watabe, Norinosuke Murai, Shintaro Hirakawa, and Kenji Nakagawa, ``Accurate Measurement Technique of Packet Loss Rate in Parallel Flow Monitoring,'' in Proceedings of the 28th
International Conference on Computer Communications and Networks (ICCCN 2019) Poster Session, 2019. The original publication is available at https://doi.org/10.1109/ICCCN.2019.8847064 (DOI: 10.1109/ICCCN.2019.8847064). (c) 2019
IEEE. Personal use of this material is permitted. Permission from IEEE must be obtained for all other users, including reprinting/republishing this material for advertising or promotional purposes, creating new collective works for resale orredistribution to servers or lists, or reuse of any copyrighted components of this work in other works.

Accurate Measurement Techniqueof Packet Loss Rate in Parallel Flow Monitoring
1st Kohei Watabe,

2nd Norinosuke Murai,

3rd Shintaro Hirakawa,

4th Kenji Nakagawa

Graduate School of Engineering, Nagaoka University of Technology
Nagaoka, Niigata, Japank watabe@vos.nagaokaut.ac.jp

Flow A
Flow BLinkNode31452

Flow C
Flow D
Delay

Converted samples
Samples of Flow A(Target flow)

ConvertDelay

Abstract—In our previous research, we have proposed aparallel flow monitoring method in which the end-to-end delayis accurately measured. The method increases delay samples ofa target flow by utilizing the observation results of other flows
sharing the source/destination with the target flow. In this paper,
we extend this method to loss measurement, and enable it to
fully utilize information of all flows including flows with different
source and destination. Through NS-3 simulations, we confirmedthat the proposed method reduces error of loss rate estimations
by 57.5% on average.
Index Terms—Active Measurement, Packet Loss Rate, Parallel
Measurement, Probe Packet, QoS Monitoring

Samples of Flow B(Converted flow)

I. I NTRODUCTION
As a measurement technique of end-to-end metrics (e.g.
delay, loss rate, etc.) for networks, an active measurement inwhich probe packets are injected into a network is commonlyused, and various measurement tools for active measurements
have been proposed in prior works [1]–[3]. In the modernInternet, a large delay (that exceeds 150 [ms] as mentioned
in ITU-T Recommendation G.114 [4]) or packet loss are rare
events. Hence, it is difficult to capture such rare events using
a limited number of the probe packets on the path, and they
are still hard to measure. While most of prior works utilize
only one probe flow for a measurement of one path in aparallel path monitoring, we have proposed a parallel flow
monitoring method in which delay on a flow is accuratelymeasured by utilizing the observation results of flows sharing
the source/destination [5], [6].
Based on the delay measurement method in reference [5],we propose a loss measurement method that fully utilizes
flows, including flows with different source and destination inthis paper. We extend the delay measurement method to loss
measurement with a weighted loss estimator. In the proposed
method, when a loss rate on a path of a target probe flow
is estimated, information regarding lost probe packets of theother probe flows is utilized. Even if a target probe flow fails
to catch loss events, the proposed method can estimate the loss
rate on the path of the target probe flow since another probe
flow may catch loss events. Therefore, the proposed method
transcends a fundamental accuracy bound of conventional
active measurement of loss rate.
This work was partly supported by JSPS KAKENHI Grant Number
JP17K00008 and JP18K18035.

Packet injection time
The distance of start/end time of congestion periods are within

Fig. 1. Conversion of samples in parallel flow monitoring.
m th congestion of Flow D
56

k th congestion of Flow B
1

6j th congestion of Flow Al th congestion of Flow C5144

Recursive conversion

Fig. 2. An example of a dependency tree for a recursive conversion.

II. A SSUMPTIONSIn this paper, we assume that most of loss events arecaused by a buffer overflow in interfaces included in links withcongestions. Propagation delay can be regarded as a constantfor a path while queueing delay dynamically changes reflecting
traffic status. Inevitably, loss events highly depend on queueing
delay. We assume that links with large queueing delay, i.e.
links with many loss events, are sparse among all links in anetwork, and a ratio of periods with large queueing delay on
a link to the other periods is small.
III. PARALLEL F LOW M ONITORING FOR D ELAY
Since we assume sparsity of congested links, queueing
delay processes within a congestion period on multiple paths
that have common links frequently overlap, and the samples
within the congestion periods can be converted (see Fig. 1).

the proposed method is O(N L) for each congestion, where Nand L denote the number of flows and the maximum numberof samples in a congestion, respectively.

8-0

4-0

3-0

2-0

0-80-4

Conventional
Proposed(No recursive conversion)
Proposed(Recursive conversion)

0-3

RMSE

0.001
0.00090.00080.00070.00060.00050.00040.00030.00020.00010Flow ID

Fig. 3. RMSE of a loss rate estimation.

In the method in reference [5], when congestion periods of
two flows whose start and end times are respectively almost
the same (i.e., they are closer than a constant probe intervalδ), the samples within the congestion periods of each flow
are mutually converted. A congestion period is observed asconsecutive samples that are larger than a threshold xth . The
jth congestion periods on the path of Flow A can be observed
by XA,j .
IV. PARALLEL F LOW M ONITORING FOR L OSS R ATE
The proposed method achieves accurate loss rate measurements by converting samples of loss events. First of all,samples LA,j of loss events between first and last samples arerecorded with XA,j . Based on the method in reference [5],samples XA,j for delay are converted each other, thereby
obtaining samples XA,j which includes converted samples.
When the samples XA,j are converted to the kth congestion
period on the path of Flow B, samples LA,j of loss events
are also converted to samples of loss events within the kth
congestion period on the path of Flow B. As a result, thesamples LB,k which includes converted samples within thekth congestion period on the path of Flow B are updated toLB,k ∪ LA,k . Note that XA,j and LA,j includes converted
samples from other flows while XA,j and LA,j represent
original samples of Flow A.
To provide an unbiased estimator of loss rate on each path,samples should be weighted since the samples of loss eventsin the proposed method are biased on a time-space, while mostof conventional loss measurements using active probes assume
that probe packets are uniformly distributed. The weight of asample s is given as |XA,j ∪LA,j |/|XA,j ∪LA,j | for s ∈ LA,j .
∑s |XA ∪ LA |/|XA | provides an estimator of loss rate on thepath of Flow A.
By repeatedly converting samples obtained from each probe
flow, the proposed method utilizes information of all probe
flows that include flows with different source and destination.
Even if both source and destination are different, flows thatshare a part of paths includes information of the target flow.
By checking whether conversion of samples is possible forall pairs of congestion periods of all probe flows, trees that
represent dependency of each conversion are generated foreach congestion period (see Fig. 2). The proposed method
recursively converts from the leaves to the root of the tree.
The computational complexity of the conversion process ofV. E VALUATIONS
We perform ns-3 [7] simulations to confirm that the numberof captured loss events increase and accuracy of a loss rateestimation is improved. The network we simulated resembles
Internet2 topology [8] with 9 nodes and 13 links whose capacities are 15.552 [Mbps]. 3 types of traffic (Poisson, exponential
ON-OFF, and periodical probe traffic) stream between all pairsof 9 nodes. Queue management in each interface of nodes isdrop-tail policy, and the maximum queue size is set to 1024. A
buffer overflow can occur due to temporal capacity shortage
when multiple ON-OFF traffic join together at an interface.
The simulation time is 1005 [s] and we only use the datafrom 5 [s] to 1005 [s]. The threshold xth is set to 0.01 [s].
We evaluate an accuracy of a loss rate estimation of theproposed method. The simulation was repeated 10 times bychanging the phase of the probe packet injection time. Root
Mean Squared Errors (RMSE) of loss rate measurements arecalculated, and the result is shown in Fig. 3. In no recursive
conversion of Fig. 3, only samples of flows that has 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. 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 can be confirmedthat recursive conversion achieves further improvement inaccuracy.
VI. C ONCLUSIONSWe proposed a loss measurement method that fully utilizes
flows, including flows with different source and destinationin this paper. The proposed method is based on the delay
measurement method in reference [5]. Through simulations
on ns-3 simulator, we confirmed that the proposed method
can reduce estimation errors by 57.5% on average.
R EFERENCES[1] J. Sommers, P. Barford, N. Duffield, and A. Ron, “A Geometric Approachto Improving Active Packet Loss Measurement,” IEEE/ACM Transactions
on Networking, vol. 16, no. 2, pp. 307–320, 2008.
[2] A. Abdelkefi, Y. Jiang, B. E. Helvik, G. Biczó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.
[3] S. Lee, K. Levanti, and H. S. Kim, “Network Monitoring: Present andFuture,” Computer Networks, vol. 65, no. 2, pp. 84–98, 2014.
[4] “One-way Transmission Time,” ITU-T Recommendation G.114, 2003.
[5] K. Watabe, S. Hirakawa, and K. Nakagawa, “Accurate Delay Measurement for Parallel Monitoring of Probe Flows,” in Proceedings of 201713th International Conference on Network and Service Management(CNSM 2017), Tokyo, Japan, 2017.
[6] ——, “A Parallel Flow Monitoring Technique that Achieves Accurate Delay Measurement,” IEICE Transactions on Communications, vol. E102-B,
no. 4, 2019.
[7] T. R. Henderson, M. Lacage, G. F. Riley, G. Dowell, and J. B. Kopena,“Network Simulations with the ns-3 Simulator,” in Proceedings of ACM
SIGCOMM 2008, Seattle, WA, USA, 2008, p. 527.
[8] “Internet2 Network NOC.” [Online]. Available:
https://docs.globalnoc.iu.edu/i2network/