In [1]:
import matplotlib.pyplot as plt
import numpy as np
plt.style.use('ggplot')
In [2]:
import subprocess
hosts = ('uni-due.de', 'whitehouse.gov', 'oceania.pool.ntp.org')
log = []
for host in hosts:
process = subprocess.Popen(['ping', '-c', "50", host], stdout=subprocess.PIPE)
for line in process.stdout:
# die zeile ist ein raw string, muss also dekodiert werden
line = line.decode('utf-8')
# in der zeile ist bereits ein zeilenumbruch vorhanden
print(line, end='')
log.append((host, line))
In [3]:
import re
data = []
for host, line in log:
# Der regulaere Ausdruck findet Zeitangaben (time=) bei Bedarf durch . getrennt
m = re.search('time=(\d+(\.\d+)?)', line)
if m:
groups = m.groups()
time = float(groups[0])
data.append((host, time))
print(data)
In der Aufgabenstellung war z.B. nach dem Mittelwert und der Varianz gefragt. Gerade bei der Varianz ergaben sich Schwierigkeiten.
Wikipedia:
Sie beschreibt die erwartete quadratische Abweichung der Zufallsvariablen von ihrem Erwartungswert.
Zum Erwartungswert ist eine entsprechende Quellenangabe vorhanden. Ansonsten ist folgendes Video zu empfehlen: Zufallsgröße, Erwartungswert, Faires Spiel, ...
Da im Beispiel alle Möglichkeiten und deren Wahrscheinlichkeit bekannt sind kann der Erwartungswert einfach bestimmt werden: $\sum_{i \in I} x_i P(X = x_i)$
Da hier aber nicht von bekannten möglichen Werten ausgegangen wird ist eine unkorrigierte Stichprobenvarianz das Mittel der Wahl.
$s^2 = \frac{1}{n} \sum_{i = 1}^n (x_i - \overline{x})^2$
In [4]:
import itertools
# Die zu gruppierenden Daten muessen zunaechst nach demselben Schluessel
# sortiert werden, siehe http://stackoverflow.com/questions/773/how-do-i-use-pythons-itertools-groupby
data = sorted(data, key=lambda t: t[0])
for host, g in itertools.groupby(data, key=lambda t: t[0]):
rtt = [e[1] for e in g]
max_rtt = max(rtt)
min_rtt = min(rtt)
# alternativer durchschnitt: sum(rtt) / len(rtt)
# aber achtung vor rundungsfehlern!
mean_rtt = np.mean(rtt)
# zur varianzberechnung siehe
# http://www.frustfrei-lernen.de/mathematik/varianz-berechnen.html
variance = (1 / len(rtt)) * sum([np.power(x - mean_rtt, 2) for x in rtt])
# die standardvarianz ist die wurzel der varianz
std_deviation = np.sqrt(variance)
print(' Host: %s' % host)
print(' Max RTT: %f' % max_rtt)
print(' Min RTT: %f' % min_rtt)
print(' Durchschnitt RTT: %f' % mean_rtt)
print(' Varianz: %f' % variance)
print('Standardabweichung: %f' % std_deviation)
print()
In [5]:
import matplotlib.pyplot as plt
times = [e[1] for e in data]
plt.hist(times, 10, normed=1, facecolor='orange', alpha=0.75)
plt.xlabel('RTT')
plt.ylabel('Wahrscheinlichkeit')
plt.title('Histogramm der Round trip times')
plt.grid(True)
x_min, x_max, y_min, y_max = plt.axis()
plt.axis((x_min - 10, x_max + 10, y_min - .005, y_max + .005))
plt.show()
In [6]:
def ecdf(values):
# 1. sortieren der werte
values = sorted(values)
# 2. reduzieren der werte auf eindeutigkeit
unique_values = sorted(list(set(values)))
# 3. ermittlung wie viele werte <= x sind fuer jede eindeutige zeit
cumsum_values = []
for u in unique_values:
cumsum_values.append((u, len([1 for _ in values if _ <= u])))
# 4. ermittlung der prozentualen anteile wie viele werte <= x sind
y = np.round([c / len(values) for t, c in cumsum_values], decimals=2)
# fuer jedes eindeutige x wird ein punkt dargestellt
plt.plot(unique_values, y, color='#e53935', linestyle=' ', marker='.')
# von x bis x + 1 wird ein einzelner strich geplottet
for i in range(len(unique_values)):
x_0 = unique_values[i]
x_1 = unique_values[i + 1] if i < len(unique_values) - 1 else unique_values[i] + 1
plt.plot([x_0, x_1], [y[i], y[i]], color='#1e88e5', linestyle='-')
ecdf(times)
plt.title('ECDF aller Pingwerte')
x_min, x_max, y_min, y_max = plt.axis()
plt.axis((x_min - 10, x_max + 10, y_min - .02, y_max + .02))
plt.show()
In [7]:
for host in hosts:
times = [t for h, t in data if h == host]
ecdf(times)
plt.title('ECDF zum Host %s' % host)
x_min, x_max, y_min, y_max = plt.axis()
plt.axis((x_min - 10, x_max + 10, y_min - .02, y_max + .02))
plt.show()
Es sollte simuliert werden wie die Gesamtverlustwahrscheinlichkeit bei einer zweiteiligen Strecke mit jeweils Teilverlustwahrscheinlichkeiten von $p_{ab} = 1\%$ und $p_{bc} = 2\%$ sind. Über einen Ereignisbaum kann man sich das ganz gut bildlich vorstellen.
Insgesamt bestehen $100^2$ Möglichkeiten. Bei einer von 100 Möglichkeiten geht das Paket auf der ersten Teilstrecke verloren. Nach jeder dieser 100 Möglichkeiten gibt es noch einmal 100 Möglichkeiten in denen das Paket verloren gehen kann. Am ersten Baum gibt es eine Möglichkeit des Paketverlustes. Daraus folgen für die Gesamtverlustwahrscheinlichkeit 100 Fehlschläge. Für jede andere der 99 Möglichkeiten gibt es 2 Möglichkeiten in denen das Paket widerum verloren gehen kann.
Demzufolge ist die Gesamtwahrscheinlichkeit die Wahrscheinlichkeit der ersten Strecke $\dfrac{1}{100}$ plus $\dfrac{99}{100} * \dfrac{2}{100}$ die Wahrscheinlichkeit der zweiten Strecke (0.02) (Summen- und Produktregel).
$p_{ges} = \dfrac{1}{100} + \dfrac{99}{100} * \dfrac{2}{100} = 0,0298 = 2,98\%$
Siehe: http://www.mathematik-wissen.de/mehrstufige_zufallsexperimente.htm
In [8]:
import random
iterations = (100, 1000, 10000, 1000000)
loss_ab = 0.01
loss_bc = 0.02
for i in iterations:
# 0 <= random.random() < 1
# 1 fuer pakete, die erfolgreich sind, 0 fuer fehlschlaege
# filterung a -> b
pakets = [1 if random.random() >= loss_ab else 0 for x in range(0, i)]
# filterung b -> c
pakets = [1 if random.random() >= loss_bc and p else 0 for p in pakets]
print('Verlust: {:3.4f}% bei {:8d} Paketen'.format((1 - float(sum(pakets)) / i) * 100, i))
print('\nBei einem kalkulierten Verlust von: {:3.4f}%'.format((0.01 + 0.02 * (1 - 0.01)) * 100))
Sollten n beliebige Strecken mit gegebenen Verlustwahrscheinlichkeiten gegeben sein, kann die folgende Methode verwendet werden:
In [9]:
def loss(p_i):
p_i = list(p_i)
if len(p_i) < 2:
return p_i[0]
_p = []
# P(0) hinzufuegen
_p.append(p_i[0])
for i in range(1, len(p_i)):
# alle anderen wahrscheinlichkeiten basieren auch auf dem vorgaenger
_p.append(p_i[i] * (1 - sum(_p)))
return sum(_p)
print(loss((0.01, 0.02)))
print(loss((0.5, 0.4, 0.3, 0.2)))
In [10]:
import math
import random
mu_ab = 42
mu_bc = 42
counts = (100, 1000, 10000, 100000)
delay = {
'ab': [],
'bc': []
}
data = []
# fuer jede teilstrecke werden zufallswerte bestimmt
# Beispiel: delay['ab'] = [[1.0, 42.3, 60.1, 34.3], [...], [...], [..]] (numpy array!)
for count in counts:
delay['ab'].append(np.array([-mu_ab * math.log(random.uniform(0, 1)) for i in range(0, count)]))
delay['bc'].append(np.array([-mu_bc * math.log(random.uniform(0, 1)) for i in range(0, count)]))
# In Python werden arrays durch addition zusammengefuegt
# [1, 2] + [3, 4] = [1, 2, 3, 4]
# es soll aber jede verzoegerung a -> b -> c addiert werden, daher werden
# numpy arrays verwendet.
# np.array([1, 2]) + np.array([3, 4]) = [4, 6]
# Beispiel: data = [([1.0, 42.3, 60.1, 34.3], 100), [...], [...], [..]]
# ..Liste von 2-Tupeln bestehend aus einem numpy array und dem dazugehoerigen label
data = [(delay['ab'][i] + delay['bc'][i], counts[i]) for i in range(0, len(counts))]
for values, label in data:
# sortieren der werte zur darstellung als cdf
xs = sorted(values)
# erstellen der gleichmaeszigen werte fuer die y-achse
ys = np.arange(1, len(xs) + 1) / float(len(xs))
plt.plot(xs, ys, label=label)
# hinzufuegen einer legende. label muss vorher durch plt.plot gegeben sein
plt.legend(bbox_to_anchor=(1.05, 1), loc=2, borderaxespad=0.)
# padding hinzufuegen
x_min, x_max, y_min, y_max = plt.axis()
plt.axis((x_min - 10, x_max + 10, y_min - .02, y_max + .02))
plt.show()
Zur Veranschaulichung werden die Daten noch einmal als Histogramm dargestellt.
In [11]:
import math
import random
plt.hist([d[0] for d in data], bins=20, normed=True, label=[d[1] for d in data])
plt.legend(bbox_to_anchor=(1.05, 1), loc=2, borderaxespad=0.)
plt.show()
In [12]:
for i in range(0, len(counts)):
xs, label = delay['ab'][i] + delay['bc'][i], str(counts[i])
plt.hist(xs, bins=80, normed=True, label=label)
plt.legend(bbox_to_anchor=(1.05, 1), loc=2, borderaxespad=0.)
plt.show()
In [13]:
# plotten der werte wie zuvor zum vergleich mit den erlang verteilungen
for values, label in data:
xs = sorted(values)
ys = np.arange(1, len(xs) + 1) / float(len(xs))
plt.plot(xs, ys, label=label)
# erzeugen der gleichmaeszigen x werte fuer die erlang verteilung <=> min <= x <= max
# des letzten elementes
e_x = np.linspace(min(data[-1][0]), max(data[-1][0]), len(data[-1][0]))
e_y = {
'erlang.1': [1 - math.exp(-1 / mu_ab * i) * (1 + 1 / mu_ab * i) for i in e_x],
'erlang.2': [1 - math.exp(-1 / (2 * mu_ab) * i) * (1 + 1 / (2 * mu_ab) * i) for i in e_x]
}
for label in e_y:
plt.plot(e_x, e_y[label], label=label)
# hinzufuegen einer legende. label muss vorher durch plt.plot gegeben sein
plt.legend(bbox_to_anchor=(1.05, 1), loc=2, borderaxespad=0.)
# padding hinzufuegen
x_min, x_max, y_min, y_max = plt.axis()
plt.axis((x_min - 10, x_max + 10, y_min - .02, y_max + .02))
plt.show()
Supernodes bilden ein Overlay, da Sie den Datenverkehr an die Klienten regeln und anderen Supernode bekannt sind. Erst durch Supernodes wird das eigentlich Netz realisiert.
Siehe Wikipedia Empirische Verteilungsfunktion
Ausgangsdaten: 6, 2, 7, 12, 1, 11, 1, 1, 2, 3
sort: 1, 1, 1, 2, 2, 3, 6, 7, 11, 12
table:
1 2 3 6 7 11 12 3 2 1 1 1 1 1
cumsum 3 5 6 7 8 9 10 /10 .3 .5 .6 .7 .8 .9 .10
Es soll die Sprachsample-Verlustrate $p_{voice}$ in Abhängigkeit der Paketverlustrate $p_{loss}$ für die Replikationsgrade $R = 1, 2, 3, 4$ dargestellt werden. Im Skript ist das auf Folie 16 - 18 dargestellt. Hier kann auch die Formel verwendet werden: $p_{voice} = p_{loss}^R$. Für die Paketverlustrate $p_{loss}$ werden Werte von 0% bis 100% verwendet.
In [14]:
# plr = packet loss rate
p_loss = np.linspace(0., 1., 100)
# replikationsgrade
degrees = [d for d in range(1, 11)]
for degree in degrees:
p_voice = p_loss ** degree
plt.plot(p_loss, p_voice, label=str(degree))
# legende hinzufuegen
plt.legend(bbox_to_anchor=(1.05, 1), loc=2, borderaxespad=0., title='Degree')
# padding hinzufuegen
x_min, x_max, y_min, y_max = plt.axis()
plt.axis((x_min - .02, x_max + .02, y_min - .02, y_max + .02))
plt.ylabel('Sample loss rate')
plt.xlabel('Packet loss rate')
plt.show()
In [15]:
import math
for degree in degrees:
p_voice = p_loss ** degree
mos = [4 * math.exp(-4.2 * x) + 1 for x in p_voice]
plt.plot(p_loss, mos, label=str(degree))
plt.legend(bbox_to_anchor=(1.05, 1), loc=2, borderaxespad=0., title='Degree')
x_min, x_max, y_min, y_max = plt.axis()
plt.axis((x_min - .02, x_max + .02, y_min - .1, y_max + .1))
plt.ylabel('MOS')
plt.xlabel('Packet loss rate')
plt.show()
In [16]:
import random
packet_count = 100000
degree = 4
loss = 0.09
packet_time_delta = 20
delay_sender_receiver = 13
# Jedes Paket kommt an
packets = []
sample_delay = [0 for x in range(packet_count)]
for i in range(packet_count):
packets.append(random.uniform(0, 1) > loss)
loss_without_rep = sum([1 for x in packets if not x]) / float(packet_count) * 100
print('Paketverlust ohne Replikation: {:.3f}%'.format(loss_without_rep))