Gustaf Lindstedt: Simulation & Analysis of Peer-to-Peer Network Quality for Measurement Scheduling: Online algorithms, Application for Network QoS Monitoring

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.

Histograms of measured ping delays to two web sites
Measured delay distributions to two sites: a sharp lower bound and a long right tail.

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.

The scheduling system design
CheesePi nodes fetch schedules from a control server and upload results; both share 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.
Aggregate error after a small change: round-robin versus ADWIN scheduling
Three-node network, small change at iteration 100: ADWIN-based scheduling (red and light blue) brings the error down faster than round-robin.

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

Full text (DiVA)

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) →

← All supervised theses