Introduction

Mixture Model

Evaluation

Conclusions

An Empirical Mixture Model for Large-Scale RTT
Measurements
Romain Fontugne1,2
1

Johan Mazel1,2National Institute of Informatics

2

Kensuke Fukuda1,3
JFLI

3

SokendaiJune 9, 20151

Introduction

Mixture Model

Evaluation

Conclusions

Introduction

RTT: Round Trip Time
• Time to send a packet andreceive its acknowledgment• Key indicator of network

conditions• Important for server

selection, overlay network,
geolocation...

2

Introduction

Mixture Model

Evaluation

Conclusions

Motivations
Monitor Internet-wide delays over time
• Measure millions of hosts RTTs• Assess network performance at large-scale• Report significant RTT fluctuations

3

Introduction

Mixture Model

Evaluation

RTT Estimation

RTT from passive measurements• Measure traffic at backbone network• RTT estimation from TCP traffic

Advantages• Non-Intrusive (Ping the entire IP space)• Monitor RTT experienced by Internet users

Conclusions

Introduction

Mixture Model

Evaluation

Conclusions

RTT Estimation in the network

ISPInternetA

B
Measurement point

5

Introduction

Mixture Model

Evaluation

Conclusions

RTT Estimation in the network

ISPInternetA

B
Measurement pointAθSEQ

Based on Karn’s algorithm• For a certain host AθACKB}δ

• Compute delay samplesδ = θACK − θSEQ

• Ignore retransmitted packets
Measurement
pointIntroduction

Mixture Model

Evaluation

Conclusions

Problem: Understanding RTT from numerous hosts?

ISPInternet

Introduction

Mixture Model

Evaluation

Conclusions

Problem: Understanding RTT from numerous hosts?

Internetmedian500

RTTI N400#hosts

300
250
200
150
100
50010−1

median#hosts

ISP

300

RTTOUT

200
100

01012

1010
RTT (ms)

310• Multimodal distributions

410010−1100• Median value is misleading! (Don’t use it!)

101102
RTT (ms)

103

104

Introduction

Mixture Model

Evaluation

Conclusions

Monitoring RTT
median500#hosts400300RTTOUT

200
100
010−1100

101
102
RTT (ms)

103

104

Find and monitor typical RTTs
• Identify usual RTTs experienced by Internet hosts• Characterize, and monitor spatial and temporal dynamics ofRTTs• Detect abnormal RTTs fluctuations for both host populationor specific hosts

7Introduction

Mixture Model

Evaluation

Conclusions

Proposed Model
Temporal Tracking

Mixture Model

A'Day d'Graph Construction

BAA' .25
T = B' .0C' .0D' .0BCDEA.0.0.0.0

B.25.0.0.0.0.22.03.0.0.0.07 .18

RTTDay dCA'B'C'DEdD'd'

1. Uncover the daily RTT distributions using a mixture model
2. Link RTT distributions from similar sub-population of IPs
across time
3. Formalize RTTs time evolution in a graph for further
systematical analysis
8Introduction

Mixture Model

Evaluation

Conclusions

Mixture Model
median500

components• Dirichlet process mixture model• log-normal distribution

RT TOU T200100300
25020015010050010−1median0# hosts• Unknown number of mixed

300

100

25

RT TIN

101102
RTT (ms)

103

104

RTTOUT20
pdf

Identify RTT sub-populations:# hosts

400

15105

→ Obtain the mean and std. deviationof typical RTTs (µ, σ)

010−1

100

101

102

103

104

25

RTTI N

pdf

20
15
10
5
0
10−1

100

101
102
RTT (ms)

103

104

Introduction

Mixture Model

Evaluation

Temporal Tracking

Number of components from d and d 0 might differ• IPs from E moved to D 0 ?

• or they are not active in day d 0 ?

Conclusions

Introduction

Mixture ModelEvaluation

Conclusions

Temporal Tracking (cont.)

Connect distributions from different days:• See components as probability density functions• Compute probability of IPs to fall in A and A’, A and B’, ....

→ Transition matrix from day d to day d 0Introduction

Mixture Model

Evaluation

Conclusions

Graph Construction

Temporal Tracking

Mixture Model

A'Day d'Graph Construction

BA
A' .25
T = B' .0
C' .0
D' .0

BCDEA.0.0.0.0

B.25.0.0.0.0.22.03.0.0.0.07 .18

RTTDay dC

A'
B'C'DEdD'd'Graph from transition matrix
1. Nodes: identified modes / typical RTTs for one day
2. Edges: relate modes with similar IPs

12Introduction

Mixture Model

Evaluation

Conclusions

Evaluation

Dataset: MAWI Archive• transit link between the WIDE network (ASN2500) and theInternet• 15 minutes of traffic everyday from Jan. 2001 to Mar. 2014
• 4678 traces (pcap files)• RTT estimates from 12 millions unique IP addresses• Separate RTTs to hosts inside the WIDE network (RTTIN )and outside (RTTOUT )13

Introduction

Mixture Model

Evaluation

Conclusions

Longitudinal Study(b) CDF of 10µ , the modeled RTT ofmodes per day.

the identified modes (milliseconds).

cdf(a) CDF of the number of identified

cdf

4 6 8 10 12 14# components

1.00.80.6
0.4
RT TOU T0.2
RT TIN
0.0
10−1 100 101 102 103 104 105 106
10µ1.0
0.8
0.6
0.4
0.2
0.00

RT TOU T
RT TIN2→ RTTOUT contains more components and higher RTTs
→ RTTIN = 500ms (102.7 ) satellite link!
14Introduction

Mixture ModelEvaluation

Conclusions

Geolocation
Example: RTTOUT from 2014/03/21 to 2014/03/31→ Cluster modes using community mining (Louvain algorithm)

Introduction

Mixture Model

Evaluation

Conclusions

Geolocation
Example: RTTOUT from 2014/03/21 to 2014/03/31→ Cluster modes using community mining (Louvain algorithm)
JPC5C4C3C2
C1C0

KR

97%
98%

US
8%
87%
73%
91%

CA

EU
73%

CN
3%

4%
11%

RTT

289 ms
175 ms
149 ms108 ms
44 ms
19 ms

Table: Hosts geolocation breakdown using Maxmind Geo-IP
15

Introduction

Mixture Model

Evaluation

Conclusions

Application 1Look at communities RTT fluctuations:141210µ108642001/01

01/0801/15

01/2201/29

02/05

02/12

02/19

02/26 03/05
Date

03/12

03/19

03/26

04/02

04/09

04/16

04/2304/30• RTT fluctuation = avg. RTT day2 - avg. RTT day1(normalized)• ≈ 0 means the RTTs are stable• if deviate from 0 means RTTs of numerous hosts have changed→ RTT fluctuation depicts important RTT changes

Introduction

Mixture Model

Evaluation

Conclusions

RTT fluctuations & BGP updates?
• BGP Route Information Base (RIB) from Route Views Project• Ratio of IPs affected by a BGP route vs. RTT fluctuations:abs(RT T f luctuation)

3.0
2.5
2.0
1.5
1.0
0.5
0.0
0.0

0.1
0.2
0.3
0.4
BGP affected host ratio

0.5→ 66% of the BGP updates affecting > 15% clustered IPs exhibit> 0.15 RTT fluctuations (similar to Rimondini et al. PAM’14)
17

Introduction

Mixture Model

Evaluation

RTT fluctuations & network congestion?
• Assuming MAWI throughput is proportional to networkcongestion• Compare MAWI throughput and RTT fluctuationsabs(RT T f luctuation)

3.0
2.5
2.0
1.5
1.0
0.5
0.0
100 200 300 400 500 600 700 800 900Mbps→ higher RTT fluctuations when average throughput is higher
than 500 Mbps

Conclusions

Introduction

Mixture Model

Evaluation

Conclusions

RTT fluctuations: Example
Tohoku earthquake (2011/03/07-2011/03/14)
40010µ300
200
100003/0703/09

03/11
Date

03/13

March 12 2011:• 20ms RTT increase for all hosts outside of Japan• RTT inside Japan are unchanged→ Impact of damaged trans-Pacific links and intra-AS routechangeIntroduction

Mixture Model

Evaluation

Conclusions

Application 2
Consistency check141210µ10Single Host RTT8642001/01 01/08 01/15 01/22 01/29 02/05 02/12 02/19 02/26 03/05 03/12 03/19 03/26 04/02 04/09 04/16 04/23 04/30
Date• Verify if a host is consistent with “its” cluster• Compare the host RTTs with the identified RTT distributions• Take into account the RTT variance• Consistency score:• ≈ 1 means the host behaves like other hosts• ≈ 0 means the host deviates from other hosts
20Introduction

Mixture Model

Evaluation

Conclusions

Consistency check: Examples
Consistency

Anomaly

180

RTT

1.0
0.8

140

0.4

130
120

0.6

125
120

0.4

115
110

0.2

110

0.2

105

18

1420bFe25144014220401r0Mar
Ma

401
82211r1
Ma0152r2

Ma0.0

4100bFe18(c) TLD DNS server affected by route change
215

200195

1101

82r0

Ma

10102

r1

Ma

101

rMa

2
12101r
Ma

2
14101
62

r1
Ma

Ma

101

82

r1

r2

Mar0

Ma

401

42401

12r1

Ma

401

82

r1

Ma01

52r2

Ma

0.0

4

125

1.0

120

0.8

115

0.6

0.4

110

0.4

0.2

105

0.2

0.0

100

10102(e) RTT fluctuation during the Tohoku earthquake

RTT

20501

14200.80.662251.0Consistency

210

r0bFe(d) Amazon host experiencing suspicious RTT peak

220

190

1420

Consistency

100

RTT0.81300.6RTTRTT

150

135

Consistency

Consistency

160

Ma

1.0140170bFe

BGP Update

145n
Ja

06

20

14n
Ja

13

1420n
Ja

20

1420n
Ja

27

1420b
Fe

03

1420bFe10140.020(f) Suspicious RTT fluctuations identified with theconsistency check→ Proposed model gives more insights than simple RTT analysis

21

Introduction

Mixture ModelEvaluation

Conclusions

Discussions
Implementation• Low memory usage and computational complexity• Suitable to sampled traffic• Accuracy decreases with distance (Tokyo 6= Osaka, FR = UK )Empirical Approach• Monitor RTT experienced by Internet users• Cluster IP based on RTT values (not AS)

Possible applications• DDoS detection?
• BGP hijack?

• → Difficult to evaluate
22

Introduction

Mixture Model

Evaluation

Conclusions

Conclusions
Proposed mixture model• Coarse view of numerous hosts RTTs
• Track typical RTTs time evolution• Formalize RTT dynamics in a graphApplications• Provides insights into the delays experienced by a large

population of IP hosts• Reference to find hosts deviating from their population

R. Fontugne, J. Mazel, K. Fukuda. ”An Empirical Mixture Model for
Large-Scale RTT Measurements”, INFOCOM 201523