Student: Gustaf Lindstedt
Thesis: Simulation & Analysis of Peer-to-Peer Network Quality for Measurement Scheduling: Online algorithms, Application for Network QoS Monitoring
University: KTH, School of Electrical Engineering and Computer Science (EECS)
Year: 2019
Co-advisor: Liam McNamara
Now at: INVIDI Technologies
Links
About the thesis
Programme: Computer Science and Engineering, KTH (30 credits), 2018 (report dated January 2019)
Supervisor: Stefano Markidis (KTH) · Supervisors at RISE SICS: Ian Marsh and Liam McNamara · Examiner: Anders Lansner
Project: CheesePi
CheesePi puts small measurement nodes in people's homes to monitor Internet quality. With peer-to-peer services (BitTorrent, WebRTC calls) becoming common, the quality between homes matters as well as the quality to servers. But in a network of n peers there are n(n−1) paths, and each measurement costs traffic and time. Which link should be measured next to learn the most about the network?
Background
The thesis first looked at real delay data. Ping delays are not normally distributed: they have a sharp minimum (the path's propagation delay) and a long tail from queueing. A gamma distribution fits them well, so simulations used gamma-distributed delays.

It also reviewed earlier measurement platforms (DIMES, Neubot, Dasu) and work on measurement scheduling, and designed a CheesePi scheduling system with a control server, an upload server and a database.

Method
Online statistics. Each node keeps a running model of each link: the mean and variance of its delay, updated with every new measurement without storing old samples. Two online algorithms were compared:
- a uniformly weighted one, where all past samples count equally (stable but slow to react);
- an exponentially weighted one, where recent samples count more (factor α), so it follows changes.
Scheduling by change detection. For each link, the variance estimates are kept in a sliding window managed by ADWIN (adaptive windowing, Bifet and Gavaldà). ADWIN shrinks a window when it detects that the data has changed and lets it grow when the data is stable. A short window means a link is changing, so it gets higher priority for the next measurement.
Evaluation. Simulated networks of three and ten peers, with gamma-distributed delays. The "information" gained is measured as the aggregate error between the nodes' models and the true distributions. Three kinds of degradation were introduced on one link by shifting its delay distribution: a small instant change (10 → 20 ms), a large instant change (10 → 100 ms), and a small gradual change. ADWIN scheduling was compared with round-robin.
Results
- The exponentially weighted online algorithm tracks changes much better than the uniform one, and was used as the basis for scheduling.
- For sudden small and large changes, ADWIN-based scheduling focused measurements on the changed link and converged to the new state faster than round-robin, with lower aggregate error.
- For gradual change, results were inconclusive: a slight advantage per link, but no clear difference in aggregate error.

Conclusions and future work
Keeping sliding windows of each path's estimated variance, and letting ADWIN manage their length, gives a practical basis for measurement scheduling that recovers faster after network changes than round-robin, and could be deployed on CheesePi nodes.
The thesis is clear about its limits: delays were assumed stable apart from the injected changes (no daily or weekly cycles), only increases in delay were tested, changes were modelled simply by shifting a distribution, and ADWIN's window size (20), δ and the weighting α were chosen to fit the test cases. Real deployment would need per-link tuning and tests with real, cyclic traffic. The simulation configurations are published on GitLab.
Thesis
Original entry
Gustaf Lindstedt, Simulation & Analysis of Peer-to-Peer Network Quality for Measurement Scheduling: Online algorithms, Application for Network QoS Monitoring, KTH, 2019, now at INVIDI Technologies, thesis page (co-advised with Liam McNamara).
Project
Related publications
BibTeX
@mastersthesis{Lindstedt1275511,
author = {Lindstedt, Gustaf},
title = {Simulation \& Analysis of Peer-to-Peer Network Quality for Measurement Scheduling: Online algorithms, Application for Network QoS Monitoring},
school = {KTH, School of Electrical Engineering and Computer Science (EECS)},
series = {TRITA-EECS-EX},
number = {2018:776},
pages = {82},
year = {2019},
url = {http://www.diva-portal.org/smash/record.jsf?pid=diva2:1275511},
keywords = {network, measurement, scheduling, peer, simulation, adwin, adaptive, window, mean, variance, online algorithm}
}
Source: DiVA record diva2:1275511
More in Masters theses: ← Pei-Lun Hsu (2021) | Cosar Ghandeharioon (2018) →