Transcript Speidel_beacon_talk_UJx

MEASURING THE ARRIVAL QUALITY OF REAL-TIME
PACKET TRAINS - A GLOBAL PERSPECTIVE
Ulrich Speidel, 'Etuate Cocker, Nevil Brownlee
Department of Computer Science, The University of Auckland
ACADEMIC CONTRIBUTORS TO DATE






Niko Rebenich, Stephen Neville, Aaron Gulliver, University of
Victoria, B.C., Canada
Kashif Nisar, Zeeshan Aziz, Suhaidi Hassan, Universiti Utara
Malaysia
Ming-Chui Dong, Vincent Wong, University of Macau
Raimund Eimann, Zurich, Switzerland (in a private capacity)
Bernhard Platter, Bernhard Ager, ETHZ Zürich
ITS, University of Auckland
Ulrich Speidel – [email protected]
INDUSTRY CONTRIBUTORS TO DATE








Ministry of Lands, Survey, and Natural Resources, Tonga
Connect ISP, Fiji
Ministry of Infrastructure and Planning, Cook Islands
Oyster ISP, Rarotonga
Government of Kiribati
Government of Tuvalu
E.M. Jones Ltd., Tonga
Ministry of Revenue, Tonga
Ulrich Speidel – [email protected]
AGENDA









VoIP and other real-time protocols
Buffering
Causes of variability in packet arrival
Implications of explosive network growth
Possible implications for remote communication
The beacon network – what is it and how does it work?
Why the Pacific Islands are a great test bed – and why
other parts of the world are important, too
Measures of arrival quality: jitter and entropy
Preliminary observations
Ulrich Speidel – [email protected]
WHY ARE REAL-TIME PROTOCOLS IMPORTANT?

Voice over IP (VoIP) telephony / videoconferencing

Telemedicine (e.g. remote surgery / diagnostics /
consultation)

Remote control in industrial applications

Internet of Things

Financial applications (rapid trading)
Ulrich Speidel – [email protected]
VOICE OVER IP AND OTHER REAL-TIME PROTOCOLS
• analog voice signal
is digitally encoded
Transmitter
Packets
• encoded byte
stream is chopped
into a packet train
blah
A/D
Encoder
Internet
Buffer
blah
Decoder
D/A
Receiver
Ulrich Speidel – [email protected]
• packets are
transmitted via
Internet to receiver
• receiver buffers
packets to establish
constant-rate data
flow to decoder
• decoder recovers
analog signal and
replays it
VOICE OVER IP AND OTHER REAL-TIME PROTOCOLS

Delay between signal generation and replay is
undesirable – must be kept as small as possible

Replay delay is composed of three components:
1.
2.
3.
Physical latency of cables or satellite links along
packet paths (fixed for a given path)
Time spent in router queues (variable)
Size of buffer at receiver (governed by variation in
arrival times)
Ulrich Speidel – [email protected]
CAUSES OF VARIABILITY IN PACKET ARRIVAL

Length and number of router queues

Overflowing router queues cause packet drops

Load balancing at routers
Ulrich Speidel – [email protected]
LOAD BALANCING ROUTERS

Load balancing routers send packets to the same destination across
different links

If packets from the same stream are load balanced, it causes them to take
different paths and experience different latencies

In some cases, packets may overtake each other (out-of-order arrivals)
Ulrich Speidel – [email protected]
PACIFIC RIM SUBMARINE CABLES
Which way do packets
travel from Macau to NZ?
What are the possible
latencies?
http://www.submarinecablemap.com/
Ulrich Speidel – [email protected]
LONG-DISTANCE FIBRE OPTICS
"Long fat network"
 Expensive to put in and maintain – prohibitive
for some destinations
 Become a huge resource once installed
 Growing in number around the world
 Denser mesh

Ulrich Speidel – [email protected]
SATELLITE CONNECTIVITY






"Long thin network"
Only commercially viable technology for small remote
locations
Geostationary satellites have a latency of 240-280 ms
between ground stations (compared to around 70 ms for
a trans-Pacific fibre cable)
MEO and LEO satellites promise overall lower latency,
but with large variations
Significant cost given low bandwidth and high latency
Still a growth industry!
Ulrich Speidel – [email protected]
OBSERVATIONS: PING RTT








U. of Auckland to www.u-tokyo.ac.jp: 142-149 ms (20 hops, via
Australia)
U. of Auckland to www.umac.mo: >220 ms (>17 hops, via Australia
and Japan)
U. of Auckland to www.uj.ac.za: >505 ms (>26 hops, via US & UK)
U. of Auckland to www.uvic.ca: 158-160 ms (13 hops, via US)
U. of Auckland to www.ethz.ch: >298 ms (>21 hops, via US)
U. of Auckland to lands.gov.to: 803-1074 ms (21 hops, via US,
Canada and satellite)
U. of Auckland to oyster.co.ck: 585-593 ms (15 hops via Australia
and satellite)
Conclusion: geographic distance and even fibre routes are only a
guide!
Ulrich Speidel – [email protected]
NETWORK GROWTH







Increase in number of users
Users create more traffic (volume of traffic estimated to
increase by a factor of 1000 per 20 years)
New protocols and applications appear
Topology changes: links are added / upgraded, routers are
added / upgraded. Hop counts tend to increase over time.
Multiple path alternatives are increasingly common,
physically shortest paths aren't necessarily the ones chosen
for routing (commercial factors).
Network mesh grows denser
Load balancing used increasingly to improve reliability
Ulrich Speidel – [email protected]
IRREGULAR PACKET ARRIVAL
Need to buffer more
 Real-time services such as VoIP, video
conferencing, and remote manipulation may
become impractical
 Downloads and streaming video/audio would still
work
 Significant economic impact (outsourced call
centre industry)
 Effects are most likely to be felt between remote
endpoints first

Ulrich Speidel – [email protected]
WHICH EFFECT WILL WIN?

Technological progress or the forces of chaos it
unleashes?
more traffic
more powerful
routers
more congestion
extra bandwidth
new links
more malware
more users
more efficient codecs
Ulrich Speidel – [email protected]
more inefficient routing
less predictable packet
arrivals
CAN WE PREDICT A TREND?

Basic idea: Pick a sample application, e.g., VoIP

Repeatedly use the application over time between remote end
points where deterioration is likely to be seen early

See whether you observe any long-term changes

Do this for multiple pairs of endpoints so you can ascertain
whether a change is specific to a particular endpoint or pair of
endpoints
Ulrich Speidel – [email protected]
FUNDAMENTAL CHALLENGES

Applications don't stay stable


Network topology changes & observation points shift


Accept as part of the observable & observe between multiple endpoints
Effects seen may be local rather than remote


Use synthetic reproducible traffic instead, from a software whose behaviour we
can control
Compare observations of multiple endpoints in vicinity
Effects seen may apply to a particular path (pair of endpoints) only

Have more than just a few endpoints
Ulrich Speidel – [email protected]
THE BEACON NETWORK

Basic idea:
"Run a global network of beacon computers that act pair-wise
as endpoints"

To date (April 2013), 16 beacons operate in Canada, Cook
Islands, Fiji, Kiribati, Macau, Malaysia, New Zealand,
Switzerland, Tonga, and Tuvalu

…and the network is growing!
Ulrich Speidel – [email protected]
THE BEACON NETWORK
Ulrich Speidel – [email protected]
BEACON SOFTWARE

Software is a C program that runs one experiment and
then shuts down

Scheduled via cron jobs & configured via command
line parameters

Writes plain text logs

Requires sufficient privileges to run raw sockets (to
determine TTL of received packets)
Ulrich Speidel – [email protected]
BEACON UDP EXPERIMENTS

Beacon exchanges 10,000 UDP packets of 110 bytes with a partner beacon

Packets transmitted every 20 ms

Transmit time logged at transmitting end (2 timestamps)

Packets are timestamped and serial-numbered

At receiving end, packets are logged with arrival time stamp, serial number,
arrival sequence number, and TTL observed

This experiment typically runs 3 times a day between selected beacon pairs

Unidirectional option also exists
Ulrich Speidel – [email protected]
BEACON TCP EXPERIMENTS

Two beacons exchange a predefined set of data via TCP

Two modes available: VoIP (constant payload rate) and
Download (maximum payload rate)

Transmitting end logs nothing except fact that experiment took
place + config

Receiving end logs data arrival at application layer plus TTL and
size of packets involved in communication (from raw socket)
Ulrich Speidel – [email protected]
A QUESTION OF TIMING

Less interested in total latency than in its variability (jitter)

Sending and receiving beacons need clocks that are
sufficiently stable for the duration of an experiment

But: No need for perfect synchronisation (NTP is sufficient)
Ulrich Speidel – [email protected]
BEACON HARDWARE

PC or Mac platform with Ubuntu/BSD/OSX

Doesn't need to be overly fast – we use 600 MHz ALIX boards
among others

Must have real-time clock, but GPS / atomic clock
synchronisation is not required

VM's are not a good idea – tend to spend too much time away
from task at hand
Ulrich Speidel – [email protected]
LOCATION, LOCATION!

Would like to observe longer paths (both in hops and in
latency)

Higher likelihood of out of order arrivals if path latencies
differ substantially

Interested in "user experience", so beacons don't need
to be near the backbone

While doing so, want to avoid measuring purely local
effects
Ulrich Speidel – [email protected]
WHY HAVE BEACONS ALL OVER THE WORLD?

Want long-term global trend, not just local effects

Want a "developed world" baseline but also see what it is like in remote
places on the fringe – many of our beacons run in the Pacific for that reason
(need I mention Africa?)

Long paths generally are of interest – both in terms of latency and number
of hops

A lot of international traffic passes through "hub regions" (North America,
Europe, SE Asia). What effect do these regions have on traffic that passes
through them?

Last but not least: We're looking for input (and your own experiments)!
Ulrich Speidel – [email protected]
BEACON CHALLENGES

Proper timing without proper timebase

Precise timing on multitasking computers

Getting two beacons to communicate (firewalls, ports, policies/politics)

Scheduling

Data volume backhaul (each beacon contributes ~3MB / experiment / day)

Data processing & presentation (currently UDP only)

Coordination with many partners, each with a unique network setup

Making it longitudinal
Ulrich Speidel – [email protected]
PACKET TRAIN QUALITY

Subjective approaches, e.g., Mean Opinion Score (MOS) –
reliably replicable only with very large sample

Objective approaches, e.g., jitter measurements. But is jitter
really random?

Stop & recap: What do real-time protocols need again?
Ulrich Speidel – [email protected]
WHAT RTP'S NEED

Regular packet arrival

In-order arrival

Low packet loss

So how do we come to grips with the "regular"?

Answer: Information theory can help!

But first, a quick look at initial observations…
Ulrich Speidel – [email protected]
PACKET LOSS
Ulrich Speidel – [email protected]
OUT-OF-ORDER ARRIVALS
Ulrich Speidel – [email protected]
LOSS VS OUT-OF-ORDER
Ulrich Speidel – [email protected]
JITTER

Knowing (logged) transmit & receive times tt and tr, we can compute
average latency t for the experiment:
1 n 1
t   (t r  tt )
n i 0

Note this includes any clock offset between transmitter and receiver clock

Can then compute jitter as average absolute deviation from the average
latency:
1 n 1
J   | t r  tt  t |
n i 0

Clock offset disappears

Gives a guide as to buffer size required
Ulrich Speidel – [email protected]
JITTER ISN'T ALWAYS A CLEAR MEASURE

Consider the following simplified scenario:

Assume uncongested routers but differences in latency, blue router load balances

Have two paths/latencies -> high jitter, but not really queue-induced

Jitter ignores systematic patterns in arrivals

A good entropy estimator (i.e., not Shannon) can detect the difference
Ulrich Speidel – [email protected]
COMPLEMENT: ENTROPY (RATE)

Entropy: "measure of disorder in a system". Usually given in the form
of an entropy rate rather than absolute entropy

Entropy rate: number of bits of actual information required to
represent an object divided by number of bits actually used to
represent it.

Dimensionless ("bits/bit")

Examples: Shannon entropy, Lempel-Ziv compression ratios, Tentropy, …

"Really unpredictable arrivals" = high entropy
Ulrich Speidel – [email protected]
ENTROPY HOW-TO

Map inter-arrival times of successive UDP packets to symbol bins, e.g.:



t < 17 ms: "A"
17 ms < t < 19 ms: "B"
19 ms < t < 21 ms: "C"
…

Form string from these symbols: "CCCBDCACF…"

Determine entropy rate for string (e.g., as Lempel-Ziv compression ratio or Tentropy)

"Perfect" string will be "CCCCCCC…" – highly compressible, low entropy

Chaotic arrivals generate many new pattern combinations: harder to
compress, higher entropy
Ulrich Speidel – [email protected]
ENTROPY VS. JITTER
Ulrich Speidel – [email protected]
ENTROPY VS. JITTER
5 bin T-entropy TO2-NZ3 vs. transit jitter
1
0
0.2
0.4
0.6
0.8
1
Jitter [s]
0.1
0.01
0.001
T-entropy [bits/symbol]
Ulrich Speidel – [email protected]
1.2
1.4
1.6
BUT IT AIN'T ALWAYS THAT WAY
Ulrich Speidel – [email protected]
WHERE IS ENTROPY INTRODUCED?
Ulrich Speidel – [email protected]
CHANGING TTLS – THE SMOKING GUN
Ulrich Speidel – [email protected]
PICKING A TREND?
Ulrich Speidel – [email protected]
CONCLUSIONS

Real-time traffic and best-effort protocols are uneasy companions

We propose to use a large beacon network to measure arrival shape
of packet trains

Our beacons already see interesting effects

Effects are strongly path-specific and sometimes not easily explained

Jitter and entropy are both useful for arrival shape evaluation

A lot of work remains to be done!
Ulrich Speidel – [email protected]