Analyse von Datenﬂüssen in Netzwerken mit Me- thoden aus ... · Legendre, Adrien-Marie (1752-1833) FranzösischerMathematiker.Erbeschäftigtesich mit der Zahlentheorie, der Geometrie

Regionales Rechenzentrum für Niedersachsen

Fachgebiet Distributed Virtual Reality | Lehrgebiet Rechnernetze

Bachelor-Arbeit

Analyse von Datenflüssen in Netzwerken mit Me-

thoden aus der IP-Verkehrstheorie

Verfasser Stefan FrankeErstprüfer Prof. Dr.-Ing. C. GrimmZweitprüfer Prof. Dr.-Ing. G. von VoigtBetreuer Prof. Dr.-Ing. C. GrimmDatum 8. September 2005

Hannover, den 8. September 2005

Hiermit versichere ich, dass ich diese Arbeit selbstständig verfasst habe und keine an-deren als die angegebenen Quellen und Hilfsmittel verwendet habe.

Stefan Franke

Inhaltsverzeichnis

1 Einleitung 1

1.1 Motivation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1

1.2 Gliederung der Arbeit . . . . . . . . . . . . . . . . . . . . . . . . . . . 1

1.3 Ziel . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2

1.4 Bemerkung . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2

2 Ausgewählte stochastische und statistische Grundlagen 3

2.1 Struktur des IP-Verkehrs . . . . . . . . . . . . . . . . . . . . . . . . . 3

2.1.1 Technische Einflüsse . . . . . . . . . . . . . . . . . . . . . . . 3

2.1.2 Semantische Einflüsse . . . . . . . . . . . . . . . . . . . . . . 6

2.2 Regressionsgeraden . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6

2.3 Langsam wechselnde Funktionen . . . . . . . . . . . . . . . . . . . . . 8

2.4 Stochastische Prozesse . . . . . . . . . . . . . . . . . . . . . . . . . . 8

2.4.1 Stationäre Prozesse und stationäre Zuwächse . . . . . . . . . . 9

2.4.2 Die Brownsche Bewegung . . . . . . . . . . . . . . . . . . . . 10

2.4.3 Die fraktionale Brownsche Bewegung . . . . . . . . . . . . . . 11

2.4.4 α-stabile Prozesse . . . . . . . . . . . . . . . . . . . . . . . . 12

2.4.5 Heavy-Tail-Eigenschaft von Prozessen . . . . . . . . . . . . . 13

2.5 Modellierung von IP-Verkehr . . . . . . . . . . . . . . . . . . . . . . . 15

3 Beschreibung und Bewertung der einzelnen Schätzer 16

3.1 Selbstähnlichkeit, Hurst-Parameter und Langzeitabhängigkeit . . . . . 16

3.2 Generierung von Zeitreihen . . . . . . . . . . . . . . . . . . . . . . . . 19

3.2.1 Fractional Gaussian Noise (FGN) . . . . . . . . . . . . . . . . 19

3.2.2 Fractional Autoregressive Integrated Moving-Average (FARIMA) 20

3.3 Abschätzen des Hurst-Parameters . . . . . . . . . . . . . . . . . . . . 24

3.3.1 Absolute Momente . . . . . . . . . . . . . . . . . . . . . . . . 24

3.3.2 Varianzmethode (Aggregated Variance) . . . . . . . . . . . . . 25

3.3.3 Periodogramm . . . . . . . . . . . . . . . . . . . . . . . . . . 25

i

Inhaltsverzeichnis

3.3.4 Varianz der Restglieder . . . . . . . . . . . . . . . . . . . . . . 28

3.3.5 Verhältnis der Varianz der Restglieder . . . . . . . . . . . . . . 29

3.3.6 R/S-Methode . . . . . . . . . . . . . . . . . . . . . . . . . . . 30

3.3.7 Whittle-Schätzer (Maximum Likelihood Estimator) . . . . . . . 31

3.3.8 Lokaler Whittle-Schätzer . . . . . . . . . . . . . . . . . . . . . 32

3.3.9 Wavelet-Analyse . . . . . . . . . . . . . . . . . . . . . . . . . 32

3.4 Bewertung der Schätzer . . . . . . . . . . . . . . . . . . . . . . . . . . 34

3.4.1 Schätzen von FGN-Reihen . . . . . . . . . . . . . . . . . . . . 35

3.4.2 Schätzen von FARIMA-Reihen . . . . . . . . . . . . . . . . . 35

3.4.3 Ergebnis: Welcher ist der beste Schätzer? . . . . . . . . . . . . 37

4 Auswertung von realem IP-Verkehr 38

4.1 Besonderheit des gemessenen Verkehrs . . . . . . . . . . . . . . . . . 38

4.2 Erstellen der Zeitreihen aus dem gemessenen Verkehr . . . . . . . . . . 38

4.3 Auswertung der Zeitreihen . . . . . . . . . . . . . . . . . . . . . . . . 39

4.3.1 Wahl der geeigneten Diskretisierungen . . . . . . . . . . . . . 39

4.3.2 Schätzen des Heavy-Tail-Verhaltens . . . . . . . . . . . . . . . 41

4.3.3 Schätzen des Hurst-Exponenten . . . . . . . . . . . . . . . . . 42

4.3.4 Hurst-Exponenten mit Fraleigh-Diagrammen ermitteln . . . . . 44

5 Zusammenfassung und Ausblick 48

5.1 Ergebnis der Auswertung . . . . . . . . . . . . . . . . . . . . . . . . . 48

5.2 Vergleich der Ergebnisse mit dem realen IP-Verkehr . . . . . . . . . . . 48

5.3 Ausblick . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 49

A Detaillierte Gra�ken zur Genauigkeit der Schätzer 51

A.1 Ergebnisse der Schätzer für die generierten Zeitreihen . . . . . . . . . . 51

A.2 Ähnlichkeit der ursprünglichen mit den vorhergesagten Zeitreihen . . . 55

A.2.1 FARIMA-Reihen mit α = 2, 0 . . . . . . . . . . . . . . . . . . 55

A.2.2 FARIMA-Reihen mit α = 1, 5 . . . . . . . . . . . . . . . . . . 56

A.2.3 FGN-Reihen mit α = 2, 0 . . . . . . . . . . . . . . . . . . . . 57

B Detaillierte Gra�ken zur Auswertung 59

B.1 Übersicht über die geschätzten Heavy-Tail-Parameter . . . . . . . . . . 59

B.2 Übersicht über die geschätzten Hurst-Exponenten . . . . . . . . . . . . 59

B.3 Fraleigh-Diagramme zur Ermittlung des Hurst-Exponenten . . . . . . . 59

ii

Inhaltsverzeichnis

C Anpassen der Algorithmen 63

C.1 Anpassen der S-PLUS Algorithmen für GNU R . . . . . . . . . . . . . 63

C.2 Einbinden von C-Methoden . . . . . . . . . . . . . . . . . . . . . . . . 64

C.3 Besonderheiten beim Generieren der Zeitreihen mit FARIMA und FGN 65

Literaturverzeichnis 67

iii

Abbildungsverzeichnis

2.1 Das klassische TCP/IP-Modell . . . . . . . . . . . . . . . . . . . . . . 4

2.2 Bestimmung der Reste einer linearen Regression . . . . . . . . . . . . 7

2.3 Verschiedene Pfade eines Random Walk . . . . . . . . . . . . . . . . . 9

2.4 Beispiel einer Brownschen Bewegung . . . . . . . . . . . . . . . . . . 11

3.1 FGN-Zeitreihen mit verschiedenen Hurst-Exponenten . . . . . . . . . . 20

3.2 FARIMA-Zeitreihen mit verschiedenen Hurst-Exponenten und α = 2 . 21

3.3 FARIMA-Zeitreihen mit verschiedenen Hurst-Exponenten und α = 1, 5 22

3.4 Das erste absolute Moment . . . . . . . . . . . . . . . . . . . . . . . . 25

3.5 Die Varianzmethode . . . . . . . . . . . . . . . . . . . . . . . . . . . 26

3.6 Das Periodogramm . . . . . . . . . . . . . . . . . . . . . . . . . . . . 27

3.7 Die Varianz der Restglieder . . . . . . . . . . . . . . . . . . . . . . . . 28

3.8 Das Verhältnis der Varianz der Restglieder . . . . . . . . . . . . . . . . 29

3.9 Die R/S-Methode . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 31

3.10 Die Wavelet-Analyse . . . . . . . . . . . . . . . . . . . . . . . . . . . 34

4.1 Auswahl der geeigneten Intervalle . . . . . . . . . . . . . . . . . . . . 40

4.2 Heavy-Tail-Verhalten bei verschiedenen Intervallen (17.01.05, 15 Uhr) . 42

4.3 Das geschätzte Heavy-Tail-Verhalten an allen drei Tagen . . . . . . . . 43

4.4 Beispiel für das Verhalten des Hurstexponenten (20.01.05 um 17:00 Uhr) 44

4.5 Entwicklung des Hurstexponenten über die einzelnen Tage . . . . . . . 45

4.6 Beispiel zur Ermittlung des Hurstexponenten mit Fraleigh-Diagrammen 46

4.7 Gruppierte Fraleigh-Diagramme vom Freitag (21.01.05) . . . . . . . . 47

5.1 Vergleich von IP-Verkehr und generierten Zeitreihen . . . . . . . . . . 50

A.1 Ergebnisse für die Absoluten Momente . . . . . . . . . . . . . . . . . 51

A.2 Ergebnisse für die Varianzmethode . . . . . . . . . . . . . . . . . . . . 52

A.3 Ergebnisse für die R/S-Methode . . . . . . . . . . . . . . . . . . . . . 52

A.4 Ergebnisse für das Periodogramm . . . . . . . . . . . . . . . . . . . . 52

iv

Abbildungsverzeichnis

A.5 Ergebnisse für das modifizierte Periodogramm . . . . . . . . . . . . . 53

A.6 Ergebnisse für das kumulative Periodogramm . . . . . . . . . . . . . . 53

A.7 Ergebnisse für die Varianz der Restglieder . . . . . . . . . . . . . . . . 53

A.8 Ergebnisse für den Durchschnitt der Varianz der Restglieder . . . . . . 54

A.9 Ergebnisse für das Verhältnis der Varianz . . . . . . . . . . . . . . . . 54

A.10 Ergebnisse für den Whittle-Schätzer . . . . . . . . . . . . . . . . . . . 54

A.11 Ergebnisse für den lokalen Whittle-Schätzer . . . . . . . . . . . . . . . 55

A.12 Ergebnisse für die Wavelet-Analyse . . . . . . . . . . . . . . . . . . . 55

A.13 Vorhersage für FARIMA-Reihen mit α = 2, 0 . . . . . . . . . . . . . . 56

A.14 Vorhersage für FARIMA-Reihen mit α = 1, 5 . . . . . . . . . . . . . . 57

A.15 Vorhersage für FGN-Reihen . . . . . . . . . . . . . . . . . . . . . . . 58

B.1 Heavy-Tail-Parameter α am Montag 17.01.05 . . . . . . . . . . . . . . 60

B.2 Heavy-Tail-Parameter α am Donnerstag 20.01.05 . . . . . . . . . . . . 60

B.3 Heavy-Tail-Parameter α am Freitag 21.01.05 . . . . . . . . . . . . . . 60

B.4 Hurst-Exponent H am Montag 17.01.05 . . . . . . . . . . . . . . . . . 61

B.5 Hurst-Exponent H am Donnerstag 20.01.05 . . . . . . . . . . . . . . . 61

B.6 Hurst-Exponent H am Freitag 21.01.05 . . . . . . . . . . . . . . . . . 61

B.7 Fraleigh-Diagramme vom Montag 17.01.05 . . . . . . . . . . . . . . . 62

B.8 Fraleigh-Diagramme vom Donnerstag 20.01.05 . . . . . . . . . . . . . 62

B.9 Fraleigh-Diagramme vom Freitag 21.01.05 . . . . . . . . . . . . . . . 62

v

Tabellenverzeichnis

3.1 Geschätzte Werte für den Hurst-Parameter bei FGN-Reihen . . . . . . . 35

3.2 Geschätzte Werte für den Hurst-Parameter bei FARIMA-Reihen mitα =2, 0 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 36

3.3 Geschätzte Werte für den Hurst-Parameter bei FARIMA-Reihen mitα =1, 5 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 37

3.4 Geschätzte Werte für das Heavy-Tail-Verhalten . . . . . . . . . . . . . 37

4.1 Dauer der Intervalle und Anzahl der gemessenen Werte . . . . . . . . . 39

4.2 Hurstexponenten für Volumen und Datenrate vom 17.01.2005 um 4:00Uhr . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 41

4.3 Mit Fraleigh-Diagrammen ermittelte Hurstexponenten . . . . . . . . . 46

C.1 Initialisierung des Startvektors . . . . . . . . . . . . . . . . . . . . . . 66

vi

Glossar

Albert-Einstein-Institut Das Albert-Einstein-Institut (AEI) ist für den experimentellenBereich im ‘Max-Planck-Institut für Gravitationsphysik’ zuständig. Es ist unteranderem für den Gravitationswellendetektor in Hannover verantwortlich.

Basisfunktionen Sie bilden die Basis eines Funktionenraumes, eines speziellen Vektor-raumes. Demnach kann jede Funktion aus dem Funktionenraum als eine end-liche oder unendliche Linearkombination von Basisfunktionen dargestellt wer-den. Im letzteren Fall benötigt man eine Norm.

G-WIN Das G-WiN ist der nationale Teil des Deutschen Forschungsnetzes und damitdas Herzstück des ‘Intranet für die Wissenschaft’. Es spannt sich zwischen 27Kernnetzknoten auf, die sich vorwiegend in wissenschaftlichen Einrichtungen,aber auch in Telehäusern befinden. Die betriebliche Verantwortung liegt beimDFN-Verein [Dfn05].

GNU R R ist eine auf vielen Plattformen verfügbare, freie statistische Programmier-sprache. Bei der Entwicklung orientierten sich die Entwickler Ross Ihaka undRobert Gentleman an der in den Bell Laboratories entwickelten Sprache zurVerarbeitung statistischer Daten S. Das Projekt startete im Jahre 1992. Bis heutekonnte sich R in allen wesentlichen Bereichen der angewandten Statistik etablie-re. Im Jahr 2004 erschien die Version 2.0. Bei der Entwicklung ist das aus vielenfreiwilligen Helfern bestehende Team inzwischen eigene Wege gegangen. Zwarlaufen in S geschriebene Programme in der Regel auch in R und umgekehrt. ImKern haben sich jedoch Unterschiede entwickelt. R ist Vorreiter in der Erstellungwissenschaftlich fundierter statistischer Grafiken.

Gamma-Funktion Sie wird in der Mathematik sehr häufig verwendet und ergibt sichinduktiv aus der Funktionalgleichung Γ(x + 1) = x · Γ(x). Sie lautet für gan-ze Zahlen Γ(n) = Fakultät[(n − 1)] und lässt sich auf positive reelle Zahlenübertragen: Γ(x) =

∫∞0 tx1 · e−tdt.

vii

Glossar

Gauss, Karl Friedrich (1777-1855) Deutscher Mathematiker. Er beschäftigte sich haupt-sächlich mit Problemen der Zahlentheorie und Geometrie. Es gibt darüber hin-aus aber noch viele weitere Gebiete der Mathematik, in denen er Probleme löste.

Kendall-Notation Mit Hilfe der Kendall-Notation werden die Eigenschaften einer Be-dienstation in der Verkehrstheorie angegeben. Die Kennzeichnung legt die An-gaben für Ankunftsrate, Bedienrate und Anzahl der Bedieneinheiten fest. Hier-für werden die Abkürzungen M (exponentielle Verteilung), D (deterministischeVerteilung) und G (allgemeine Verteilung), sowie Zahlenangaben verwendet.

Legendre, Adrien-Marie (1752-1833) Französischer Mathematiker. Er beschäftigte sichmit der Zahlentheorie, der Geometrie und der Analysis.

Maximum Transmission Unit Die MTU gibt die maximale Datenmenge an, die als Nutz-last in einem Ethernet-Rahmen verschickt werden kann.

Methode der kleinsten Quadrate Diese Methode wird oft beim Berechnen von Aus-gleichsgeraden benutzt. Hierzu wird zu jedem x-Wert die Differenz von Mess-wert und Ausgleichsgeraden ermittelt (ein sogenannter Rest oder Residuum) unddann über alle Residuen summiert, wobei die Ausgleichsgerade so gewählt wer-den muss, dass diese Summe minimal ist.

RRZN Das Regionale Rechenzentrum für Niedersachsen ist eine Einrichtung, die fürden Betrieb der gesamten IT-Technik der Universität Hannover verantwortlichist. Darüber hinaus werden Dienstleistungen für weitere Hochschulen und Insti-tute zur Verfügung gestellt.

Regression Die Idee einer Regression ist es, eine vorgegebene Funktion (z.B. eine Ge-rade oder ein Polynom fünften Grades) einer Menge von Messdaten möglichstgenau anzupassen.

S-Plus S ist eine Programmiersprache für Statistik, die von John Chambers in den BellLaboratories entwickelt wurde. Das Ziel dieser Sprache ist es, Berechnungenvon und mit Daten zu erleichtern.

Skalierung Hier bedeutet die Skalierung, das die Basisfunktionen der Wavelet-Trans-formation in ihrer Amplitude angepasst werden, sodass aus ihrer Summe eineFunktion f angenähert werden kann.

TCPDump Dies ist ein Network-Sniffer, der ursprünglich aus der UNIX-Welt kommt.Er ermöglicht es, sämtlichen Verkehr eines Netzwerk-Interfaces in einer log-

viii

Glossar

Datei abzuspeichern und ihn eventuell später zu analysieren. Inzwischen gibt esauch eine Portierung nach Windows-Betriebssystemen mit WinDump.

Translation Die Parallelverschiebung oder Translation ist eine geometrische Abbildung,die jeden Punkt der Zeichenebene oder des Raumes in derselben Richtung umdie selbe Strecke verschiebt. Sie kann durch einen Vektor, den so genanntenVerschiebungsvektor, gekennzeichnet werden.

Zeitreihenanalyse Bei der Zeitreihenanalyse werden gemessene Zeitreihen ausgewer-tet, um Vorhersagen für die Zukunft machen zu können; z.B. wie man ein ge-plantes Netzwerk dimensionieren sollte.

Zeitreihe Eine Zeitreihe besteht aus Daten, die zu bestimmten Zeitpunkten gesammeltwurden. Diese Zeitpunkte sind üblicherweise äquidistant. Typische Zeitreihensind tägliche Temperaturmessungen, monatliche Umsatzzahlen oder stündlicherIP-Verkehr.

ix

1 Einleitung

1.1 Motivation

Jedem Netzwerkverantwortlichen stellt sich irgendwann die Frage, wie groß die Daten-ströme sind oder werden, die sein Netzwerk bewältigen muss. Bisher löste man diesesProblem durch das so genannte Overprovisioning. Hierbei wird grob abgeschätzt, wiehoch die Verkehrsspitzen sind, dann werden diese Spitzen noch mit einem Faktor vonca. 1,5 multipliziert (eine Art Sicherheitszuschlag) und nach diesen zu erwartenden Da-tenströmen wird das Netzwerk schließlich dimensioniert. Dieses Abschätzen ist nichtnur ungenau, es hat auch höhere Investitionen zur Folge als eigentlich nötig wären. Beiimmer mehr und immer größer werdenden Netzwerken dürften diese zusätzlichen Aus-gaben immer stärker ins Gewicht fallen.

In den letzten Jahren haben sich Überlegungen herauskristallisiert, ob es nicht eine IP-Verkehrstheorie als Gegenstück bzw. Ergänzung zur klassischen Verkehrstheorie für pa-ketvermittelten Verkehr gibt. Hierzu wurden viele Modelle und Methoden, die in dieserArbeit näher erläutert werden, zusammengetragen.

1.2 Gliederung der Arbeit

In Kapitel 2 werden zunächst grundlegende mathematische Modelle und Konzepte vor-gestellt, sowie die charakteristischen Eigenschaften von IP-Verkehr beschrieben, bevorim Abschnitt 2.5 auf dessen Modellierung eingegangen wird.

In Kapitel 3 setzt sich die Modellierung durch weitere Konzepte fort. Hier werden Ver-fahren beschrieben, mit denen man den so genannten Hurst-Exponenten bzw. die Lang-zeitabhängigkeit schätzen kann. Im letzten Abschnitt dieses Kapitels befindet sich eineBewertung der einzelnen Schätzer.

Nachdem alle Konzepte und Methoden erläutert wurden, befindet sich in Kapitel 4 dieAuswertung durch die hier vorgestellten Methoden von realem IP-Verkehr, der am Re-chenzentrum der Universität Hannover aufgezeichnet wurde.

1

1 Einleitung

1.3 Ziel

Ziel dieser Arbeit ist es, einen Überblick über die Methoden und Modelle zu erstel-len, die für die Untersuchung von realem IP-Verkehr bezüglich seiner Vorhersagbarkeitrelevant sind. Des Weiteren soll diese Arbeit ein Leitfaden sein, wie man bestimmteParameter eines gemessenen IP-Verkehrs bestimmt, mit denen man Aussagen über denzukünftigen Verkehr erhält. Wie nun eine entsprechende Dimensionierung eines Netz-werkes für den zu erwartenden Verkehr vorgenommen wird, ist nicht Gegenstand dieserArbeit. Informationen darüber finden sich zum Beispiel in [FTD03].

1.4 Bemerkung

Als Quellen für diese Arbeit dienten ausschließlich das Buch Verkehrstheorie in IP-Netzen von Christian Grimm und Georg Schlüchtermann ([GrSc05]), welches im Sep-tember 2005 erscheint, sowie die Web-Seite [Taq05] von Murad Taqqu und ein Vortragvon Fraleigh, Tobagi und Diot [FTD03]. Überall dort, wo andere Quellen angegebensind, wurden diese aus [GrSc05] übernommen, um den Leser direkt auf die Original-Literatur zu verweisen.

2

2 Ausgewählte stochastische und

statistische Grundlagen

Zunächst müssen die wichtigsten Eigenschaften des IP-Verkehrs erörtert werden. Dieserleichtert das Verstehen der stochastischen Konzepte zur Modellierung von langzeit-abhängigen Prozessen. Dann wird allgemein auf stochastische Prozesse eingegangen,um abschließend in diesem Kapitel die Brownsche Bewegung darzustellen, auf der alleweiteren Konzepte in dieser Arbeit aufbauen.

2.1 Struktur des IP-Verkehrs

Es existieren viele verschiedene Einflüsse, die für die Struktur des IP-Verkehrs verant-wortlich sind. Diese Einflüsse lassen sich grob in zwei Gebiete unterteilen. Das eine isttechnischer Natur und beinhaltet Größen wie zum Beispiel die Protokolle, die verwen-det werden. Der andere Bereich ist eher semantischer Natur und stellt den Einfluss desBenutzers auf den IP-Verkehr dar. Im Folgenden sollen diese Bereiche kurz erläutertwerden. Dabei ist die Darstellung hier nur so genau, wie es zum weiteren Verständnisnötig ist.

2.1.1 Technische Ein�üsse

Die technische Beeinflussung des IP-Verkehrs beruht im Wesentlichen auf der Art derverwendeten Protokolle und der Paketvermittlung. Bei der Paketvermittlung wird jedegesendete Protocol Data Unit (PDU) unabhängig von den vorhergehenden über dengünstigsten Link geschickt. Dabei hat jede PDU die komplette Bandbreite des jeweili-gen Links für sich. Sollten bei einer Kommunikation Wartezeiten entstehen, so könnendie frei werdenden Links durch PDUs anderer Kommunikationen genutzt werden. Inder Praxis kann man auch häufig beobachten, dass die PDUs vermehrt denselben Linknutzen. Dies liegt daran, dass die Router nicht für jede PDU den optimalen Link zumEmpfänger neu berechnen. Daher geschieht der Transport in so genannten Bursts. Dies

3

2 Ausgewählte stochastische und statistische Grundlagen

ist auch mit ein Grund, warum bei einem Ausfall eines Links nicht nur eine PDU son-dern gleich mehrere betroffen sind.

Es gibt zahlreiche Protokolle, die in der Netzwerkkommunikation benutzt werden. DieEntscheidung für ein Protokoll hat auch Auswirkungen auf den dadurch entstehendenIP-Verkehr. Offensichtlich wird dies, wenn man verbindungslose und verbindungsori-entierte Protokolle betrachtet. Die verbindungslosen Protokolle senden ihre PDUs ohneauf eine Bestätigung zu warten. Dabei ist es egal, ob PDUs verloren gehen oder nicht(z.B. VoIP oder Videostreaming). Die verbindungsorientierten Protokolle (z.B. TCP)müssen zuerst eine Verbindung aufbauen, dann die eigentlichen Daten übermitteln undzuletzt auch noch die Verbindung abbauen. Dabei muss prinzipiell der Empfang jederPDU vom Empfänger bestätigt werden.

Des Weiteren gibt es auch noch die verschiedenen Schichten in der Kommunikationin IP-Netzen. Jede Schicht ist auf unterschiedliche Weise implementiert und bietet ver-schiedene Freiheitsgrade, mit denen man den Verkehr beeinflussen kann (z.B. die Längevon Timeouts für den Empfang von Bestätigungen). In Abbildung 2.1 ist eine Übersichtder verschiedenen Schichten gegeben.

Abbildung 2.1: Das klassische TCP/IP-Modell

Im Folgenden werden kurz die Eigenschaften der verschiedenen Schichten des TCP/IP-Modells und die Möglichkeiten, den Verkehr zu beeinflussen, dargestellt.

Bitübertragung: In dieser Schicht werden alle Parameter, die für die physikalischeÜbertragung von Signalen notwendig sind, spezifiziert. Hierzu gehören zum Bei-spiel Signalpegel, Art der verwendeten Modulation und Übertragungsmedium.Damit die verschiedenen Endgeräte miteinander kommunizieren können, müssendie Spezifikationen strikt eingehalten werden und bieten somit keine Möglichkeit,auf den IP-Verkehr weiteren Einfluss zu nehmen.

Sicherung: Die Protokolle in dieser Schicht bestimmen, wie auf die einzelnen Übertra-gungsmedien zugegriffen wird. Grundsätzlich kann man hier zwischen Weitver-kehrsnetzen (WAN) und lokalen Netzen (LAN, WLAN) unterscheiden. In lokalen

4


Netzen wird heutzutage fast ausnahmslos das Ethernet-Protokoll verwendet. Die-ses Protokoll hat ein nicht deterministisches Verhalten und eignet sich besondersgut, um die Best-Effort-Eigenschaft des Internetverkehrs zu erfüllen. Es gibt keinezentrale Steuerung mehr und jedes Interface kann die komplette Kanalkapazitätbis zum nächsten Interface nutzen. Es gibt zahlreiche mathematische Modelle, diediesen Verkehr sehr gut beschreiben. Sie müssten auch erst dann wieder angepasstwerden, wenn im Ethernet-Protokoll eine Art Priorisierung für zum Beispiel Echt-zeitanwendungen verankert wird. In Weitverkehrsnetzen wird die leitungsvermit-telnde SDH-Technik sowie ATM eingesetzt. Auch für diese Protokolle existierenmathematische Modelle.

Vermittlung: Auf der Vermittlungsschicht arbeitet das Internet Protocol (IP). Auf die-ser Ebene geschieht das Routing zwischen Sender und Empfänger über die ein-zelnen Router. Somit ist das IP für das Versenden der Daten und Ermitteln deskürzesten bzw. schnellsten Links zuständig. Die Größe der dabei verschicktenIP-Pakete entsprciht in der Praxis in den meisten Fällen der Maximum Transmis-sion Unit (MTU). Sie wird von der maximalen Nutzlast (1.500 Bytes) in einemEthernet-Rahmen bestimmt. Dadurch wird ein mögliches Teilen der IP-Paketevermieden. Da die Router theoretisch für jedes einzelne Paket einen anderen Link,auf dem es übertragen werden soll, wählen können und dieses auch machen, umdie Last gleichmäßig im Netz zu verteilen, ist ihr Verhalten entscheidend fürdie Modellierung des Verkehrs. Darüber hinaus existieren in den Routern Warte-schlangen, die durch eine eventuelle Priorisierung von einfachen FIFO-Modellen(First In, First Out) abweichen können, und somit zu komplexeren Modellen füh-ren.

Transport: Hier gibt es zwei Protokolle, die für die Ende zu Ende Kommunikationzuständig sind. Zum einen das User Datagram Protocol (UDP), das die Daten le-diglich mit einer Adresse und einer Fehlererkennung versieht. Es wird hauptsäch-lich im Bereich von Video-, Audiostreaming und in lokalen Netzen (Network-File-System, NFS) verwendet. Das andere Protokoll ist das Transmission ControlProtocol (TCP). Es stellt eine Reihe an Funktionalitäten zur Verfügung, die seineModellierung recht schwierig gestalten. Dazu gehören der verbindungsorientier-te Datentransport, zuverlässige Kommunikation, Congestion Control und FlowControl. Eine weitere für das Modell wichtige Eigenschaft ist der so genannteSlow-Start.

Anwendung: Die Protokolle in der Anwendungsschicht werden in der Anwendung im-plementiert und greifen auf darunter liegende Transportprotokolle zu. Bei der Im-

5


plementierung des Anwendungsprotokolls und der Wahl des Transportprotokollswird das Sendeverhalten der jeweiligen Anwendung maßgeblich beeinflusst. Einweiterer Einfluss auf das Sendeverhalten geht vom jeweiligen Benutzer der An-wendung aus (zum Beispiel das Verhalten eines Nutzers, der sich Internetseitenanschaut). Anwendungsprotokolle sind unter anderem HTTP, RTP oder FTP, aberauch Protokolle zum Austausch von Netzwerkinformationen wie DNS, ICMPoder RADIUS gehören dazu.

2.1.2 Semantische Ein�üsse

Zu den semantischen Einflüssen auf den IP-Verkehr zählt das Verhalten der Nutzer derverschiedenen Anwendungen. Durch ihre Nutzung steuern sie ebenfalls den anfallendenIP-Verkehr. Dies beginnt allein damit, dass sie sich bei ihrem Internet-Service-Provideran- und abmelden, wenn sie zum Beispiel eine Modem-, ISDN- oder DSL-Verbindungnutzen. Dann ist es relevant, wann sie welche Anwendungen wie lange laufen lassenund wie intensiv sie genutzt werden. Hier existiert ein Unterschied darin, ob ein Benut-zer eines Internet-Browsers sich nur gelegentlich eine Seite mit überwiegend Text imInternet anschaut oder das Videostreaming eines Nachrichtensenders dauerhaft nutzt.

Das große Problem bei diesen Einflüssen ist, dass sie, wenn überhaupt, nur sehr schwerim Modell zu berücksichtigen sind. Daher ist es stets ratsam, IP-Verkehr nicht nur theo-retisch zu modellieren, sondern auch mit realem Verkehr zu vergleichen. Wie genau manIP-Verkehr nun modelliert, wird im Abschnitt 2.5 näher erläutert.

2.2 Regressionsgeraden

Regressionsgeraden oder auch Ausgleichsgeraden sind ein probates Mittel, um aus sta-tistischen Daten, die durch Messfehler oder Ähnliches beeinflusst sind, bestimmte Grö-ßen zu ermitteln. Da viele der im Abschnitt 3.3 vorgestellten Schätzmethoden mit Re-gressionsgeraden arbeiten, soll hier kurz eine der verbreitetsten und hier verwendetenMethoden vorgestellt werden. Es ist die Methode der kleinsten Quadrate.

Die Formeln für die hier betrachtete Regression mit Hilfe der kleinsten Quadrate wur-den von Gauss und Legendre unabhängig voneinander entwickelt. Ausgehend vom all-gemeinen Fall muss der Ausdruck

R2 ≡∑

i

(yi − f (xi, a1, a2, ..., an))2 (2.1)

6


minimiert werden, wobei R2 die Summe der Quadrate der Abweichung der Funktionf von den Messwerten ist. Die Abweichung zwischen der Funktion f und den Mess-werten lässt sich auf unterschiedliche Weise berechnen, zum einen die Abweichung iny-Richtung, also der vertikale Abstand, und zum anderen der rechtwinklige Abstand,also der kürzest mögliche Abstand (siehe Abbildung 2.2). Da die vertikale Abweichungwesentlich leichter zu berechnen ist und die Ergebnisse denen des Abstandes zur Funkti-on f äußerst ähnlich sind, wird fast überall, so wie auch im Folgenden, mit der vertikalenAbweichung gerechnet.

(a) vertikale Reste (b) rechtwinklige Reste

Abbildung 2.2: Bestimmung der Reste einer linearen Regression

Wir wollen uns hier auf die lineare Regression beschränken, das heißt, wir suchen ei-ne Gerade (oder auch Polynom ersten Grades), welche wir den Messwerten anpassenwollen. Somit vereinfacht sich der obige Ausdruck mit f(x, a, b) = a+ bx zu

R2(a, b) ≡∑

i

(yi − (a+ bxi))2 . (2.2)

Um diesen Ausdruck zu minimieren, setzen wir die folgenden notwendigen Bedingun-gen für ein Minimum an:

∂R2

∂a= −2

∑i

(yi − (a+ bxi)) = 0, (2.3)

∂R2

∂b= −2

∑i

(yi − (a+ bxi))xi = 0. (2.4)

Bei nichtlinearen Regressionen kann man entweder durch geeignete Skalierung derAchsen (z.B. logarithmische Auftragung) das Regressionsproblem auf ein lineares zu-rückführen oder man verwendet die entsprechenden Formeln für logarithmische, expo-nentielle, polynomielle Regression basierend auf den kleinsten Quadraten.

7


2.3 Langsam wechselnde Funktionen

Um bestimmte Eigenschaften des IP-Verkehrs zu modellieren, benötigen wir die so ge-nannten langsam wechselnden Funktionen, die im Allgemeinen mit L(x) bezeichnetwerden. Diese Funktionen gehören zu den Klassen Rp mit p ∈ R. Eine langsam wech-selnde Funktion ist über den Grenzwert

limx→∞

L(tx)L(x)

= tp, für alle t > 0 (2.5)

definiert. Daraus folgt nun, dass sich die Funktionen L(x) und L(tx) im Unendlichengleich verhalten, unabhängig von der Wahl der Skalierung t. Nun noch einige Beispiele:

• Jede konstante Funktion gehört zur Klasse R0.

• Für jedes p ∈ R findet man die Funktionen in der Klasse Rp, die die Funktionenxp, xp log(1 + x), (x log(1 + x))p und xp log(log(e+ x)) beinhaltet.

• Die Funktionen 2 + cosx und sin(log(1 + x)) gehören zu keiner der KlassenRp.

• Es existieren auch Funktionen, die stark oszillieren, sodass lim infx→∞ L(x) = 0und lim supx→∞ L(x) = ∞. Ein Beispiel für eine solche Funktion ist

L(x) = e

hlog(1+x)

12 cos

�log(1+x)

12

�i. (2.6)

2.4 Stochastische Prozesse

Ein stochastischer Prozess ist eine Familie von stochastischen Zufallsvariablen. Er wirdmit

(Xt)t∈I oder (Xt)t∈[0,∞[ (2.7)

bezeichnet. Er beschreibt eine zeitliche Abfolge von Zufallsvariablen, wobei der Para-meterraum t des Prozesses und der Zustandsraum der einzelnen Zufallsvariablen sowohlstetig als auch diskret sein können. Durch diese Eigenschaft ergeben sich so genanntePfade für einen Prozess, da die Zufallsvariablen für ein und denselben Zeitpunkt ver-schiedenen Werte annehmen können (siehe Abbildung 2.3).

Bevor wir auf spezielle Prozesse eingehen, sollen hier noch einige Beispiele für einfachestochastische Prozesse angeführt werden:

8


-20

-10

0

10

20

30

40

50

60

0 100 200 300 400 500

Random Walk 1Random Walk 2Random Walk 3

Abbildung 2.3: Verschiedene Pfade eines Random Walk

• Wir betrachten hier den klassischen Münzwurf. Ein Spieler hat ein gewisses Start-kapital und wirft immer wieder eine Münze. Zeigt die Münze „Kopf“, gewinnt ereinen Euro, und bei „Zahl“ verliert er einen Euro. Zeichnet man nun sein Gut-haben gegenüber den Versuchen auf, so erhält man einen so genannten RandomWalk, der bei einem weiteren Spieler ganz anders aussehen kann. Dieser Prozessist sowohl wert- als auch zeitdiskret.

• Zu einem beliebigen Zeitpunkt t ≥ 0 werden die momentanen Anrufversuche ineiner Vermittlungsstelle aufgezeichnet. Dieser Prozess ist ebenfalls wertdiskret,aber er ist zeitstetig.

2.4.1 Stationäre Prozesse und stationäre Zuwächse

Bevor wir uns besonderen Prozessen widmen, mit denen wir IP-Verkehr modellierenkönnen, müssen wir noch kurz erläutern, was stationäre Prozesse und stationäre Zu-wächse sind.

Stationäre Prozesse: Bei einem im engeren Sinne stationären Prozess ändern sich dieendlich dimensionalen Randverteilungen bei einer festen Zeitverschiebung nicht.Also gilt für einen Prozess (Xt)t∈I für jede Zeitauswahl t0 < t1 < ... < tn undVerschiebung h mit ti + h ∈ I

Ft0+h,...,tn+h = Ft0,...,tn. (2.8)

Offensichtlich muss also auch F0 = Ft gelten, so dass die Startverteilung dieeindimensionalen Randverteilungen bestimmt. Hieraus folgt nun, dass sowohlm(t) = E(Xt) = E(X0) als auch V ar(Xt) = V ar(X0) konstant sind. Für

9


zweidimensionale Randverteilungen gilt analog F0,t−s = Fs,t, so dass für dieKovarianz gilt:

K(s, t) = Cov(Xs, Xt) = Cov(X0, Xt−s) = K(0, t− s). (2.9)

Stationäre Zuwächse: Hat ein Prozess (Xt)t∈I stationäre Zuwächse, so bedeutet dies,dass für alle Zeiten t ∈ I und Verschiebungen h mit t+ h ∈ I die Verteilung derDifferenz Xt+h − Xt unabhängig von t und allein von h abhängig ist. Also giltfür alle s, t ∈ I und s < t mit s+ h, t+ h ∈ I

FXt+h−Xt= FXs+h−Xs

= FXh−X0 . (2.10)

Allgemein gilt auch, dass ein Prozess mit stationären Zuwächsen nicht zwingendstationär sein muss.

2.4.2 Die Brownsche Bewegung

Die Brownsche Bewegung ist ein spezieller und grundlegender Prozess. Die endlichdimensionalen Randverteilungen sind hier endliche Normalverteilungen, es sind Grenz-verteilungen nach dem zentralen Grenzwertsatz. Die Brownsche Bewegung besitzt eben-falls die Markov-Eigenschaft. Einige weitere Eigenschaften der Brownschen Bewegungsind:

1. X0 = 0 P -f.s. (dabei bedeutetP -f.s. eine Eigenschaft, die bis auf eine P-Nullmengegilt, d.h. bis auf eine Menge N mit P (N) = 0).

2. (Xt)t∈[0,∞[ hat unabhängige Zuwächse, d.h. für alle s < t < u < v sind dieZufallsvariablen (Xt −Xs) und (Xv −Xu) stochastisch unabhängig.

3. für alle t ∈ [0,∞[ ist Xt normalverteilt mit E(Xt) = 0 und V ar(Xt) = t. Somitist die Brownsche Bewegung kein stationärer Prozess.

Eine weitere besondere Eigenschaft der Brownschen Bewegung ist, dass jeder Pfad injedem Punkt stetig ist. Allerdings ist er nirgends differenzierbar, weshalb man ihn nichtzeichnen kann. Die Darstellung in Abbildung 2.4 kann also nur eine Näherung sein.

Weiter oben wurde bereits erwähnt, dass die Brownsche Bewegung die Markov-Eigen-schaft aufweist, also gedächtnislos ist. Somit ist der Folgezustand lediglich von dem

10


0

0.2

0.4

0.6

0.8

1

0 20 40 60 80 100 120 140 160 180 200

Abbildung 2.4: Beispiel einer Brownschen Bewegung

aktuellen Zustand abhängig, aber nicht von vorherigen Zuständen. Mit bedingten Wahr-scheinlichkeiten ausgedrückt, gilt für alle Zeitpunkte t0 < t1 < ... < tn < tn+1

P (Xtn+1 = kn+1|Xtn= kn, ..., Xt0 = k0) = P (Xtn+1 = kn+1|Xtn

= kn). (2.11)

Weitere Ausführungen zur Brownschen Bewegungen kann man zum Beispiel im BuchWahrscheinlichkeitstheorie [GäSt80], S.317ff, nachlesen.

2.4.3 Die fraktionale Brownsche Bewegung

Die fraktionale Brownsche Bewegung (kurz FBM vom englischen fractional brownianmotion) ist ein Prozess (Xt)t∈R mit stationären Zuwächsen, Gauß-verteilten Randver-teilungen und dem Mittelwert Null. Des Weiteren gilt für diesen Prozess, der mit B(H)

t

bezeichnet wird,

E(X2t ) = σ2|t|2H , für ein σ > 0 und 0 < H < 1. (2.12)

Die FBM ist genau wie die Brownsche Bewegung überall stetig. Dies lässt sich miteinem Ergebnis von Kolmogorov [GäSt80] (S.281, Korollar 7.2.51) zeigen, das besagt,dass ein Prozess genau dann stetige Pfade hat, wenn es δ > 1, ν > 1 und c > 0 gibt und

E(|Xt1 −Xt2 |δ) ≤ c|t1 − t2|ν für alle t1, t2 ∈ R (2.13)

erfüllt ist. Für eine FBM ergibt sich nun auf Grund ihrer H-sssi-Eigenschaft (siehe Ab-schnitt 3.1) und mit einem δ > 1

H

E(|B(H)t2 −B

(H)t1 |δ) = E(|X1|δ)|t2 − t1|Hδ (2.14)

11


und somit auch die Stetigkeit der FBM. Betrachtet man nun noch den Differenzialquo-tienten

B(H)t1 −B

(H)t2

t1 − t2(2.15)

für t1 → t2, so ergibt sich aus der Beziehung

E

∣∣∣∣∣B(H)t2 −B

(H)t1

t2 − t1

∣∣∣∣∣2 = σ2|t2 − t1|2H−2 →∞ falls t2 → t1, (2.16)

dass die FBM nirgends differenzierbar ist. Zuletzt wollen wir die FBM in drei verschie-dene Kategorien unterteilen:

1. antipersistent: Von antipersistenten FBMs spricht man dann, wenn sie einen Hurst-Exponenten mit 0 < H < 1

2 aufweisen. Die rechte Seite in der Gleichung (2.16)strebt bei kleinem H wesentlich schneller gegen ∞. Die hierbei auftretende ne-gative Autokorrelation sorgt für ein sehr starkes „ZickZack“ bei den Pfaden.

2. chaotisch: Chaotische FBMs haben einen Hurst-Exponenten mit H = 12 und ent-

sprechen somit der Brownschen Bewegung.

3. persistent: Diese FBMs haben einen Hurst-Exponenten mit 12 < H < 1.

2.4.4 α-stabile Prozesse

Die Klasse der α-stabilen Prozesse ist eine Erweiterung der Brownschen und der frak-tionalen Brownschen Bewegungen. Waren die BM und FBM noch auf Gauß- oder nor-malverteilte Randverteilungen beschränkt, so gilt dies nicht mehr für die α-stabilen Pro-zesse. Als Randverteilungen dienen hier die α-stabilen Verteilungen, die sich besondersdazu eignen, die so genannten G-verteilten Ankunftsprozesse zu modellieren. Das Gsteht hier für „generell“ und stammt aus der Kendall-Notation für Prozesse.

Eine Verteilung G ist genau dann stabil, wenn für unabhängige und G-verteilte Zufalls-variablen ξ, ξ1 und ξ2 die Beziehung

c1ξ1 + c2ξ2d= b(c1, c2)ξ + a(c1, c2) (2.17)

für alle c1, c2 ≥ 0 und b(c1, c2) > 0 in Verteilung gilt. Diese Beziehung resultiertaus dem zentralen Grenzwertsatz unter der Annahme, dass für stabile Verteilungen dieVarianz nicht mehr existiert (also nicht mehr endlich ist). Die Darstellung dieser Vertei-lungen gestaltet sich im Allgemeinen recht schwierig, weshalb man auf die Spektraldar-stellung

ΦG(t) = E(eiξt) = eiγt−c|t|α·(1−iβsign(t)·z(t,α)), t ∈ R (2.18)

12


der Verteilungen ausweicht, wobei γ ∈ R, c < 0, α ∈]0, 2[, β ∈ [−1, 1] und

z(t, α) =

tan(

πα2

), falls α 6= 1

− 2π log |t| , falls α = 1

. (2.19)

Abschließend einige Bemerkungen zu den α-stabilen Prozessen. Eine wesentlich aus-führlichere und genauere Darstellung findet man in [EKM98].

1. Wir können die Spektraldarstellung vereinfachen, indem nur die Fälle mit γ = 0betrachten, da sie für unsere Zwecke ausreichend sind.

2. Der wichtigste Parameter ist α, da er das Aussehen der Verteilung maßgeblichbestimmt.

3. Die Zahl α wird das charakteristische Moment und die zugehörige Verteilungα-stabile Verteilung genannt.

4. Für α = 2 erhalten wir die Normalverteilung, sie ist also ein Spezialfall der α-stabilen Verteilungen, mit der Spektraldarstellung

ΦG(t) = e−ct2 . (2.20)

5. Einen weiteren Spezialfall erhalten wir mit α = 1. Er führt uns zu den so genann-ten Cauchy-Gesetzen bzw. Cauchy-Verteilungen. Hier lautet die Spektraldarstel-lung

ΦG(t) = e−c|t|·(1+iβ 2π

sign(t) log(t)) (2.21)

6. Für ein konstantes α bestimmen die Größen c und β die Gestalt der Verteilung. ckann man als eine Art Skalierungsfaktor betrachten. Für Gauß-Verteilungen giltc = σ2

2 . β ist entscheidend für den Wertebereich der Verteilung. Für β = 0 istdie Spektraldarstellung reellwertig und die Zufallsvariable symmetrisch α-stabil(sαs). Für β = 1 und α < 1 ist die Zufallsvariable positiv.

2.4.5 Heavy-Tail-Eigenschaft von Prozessen

Prozessen mit Heavy-Tail-Eigenschaft liegen die so genannten Heavy-Tail-Verteilungenoder auch subexponentiellen Verteilungen zu Grunde. Sei Fξ eine Verteilungsfunktioneiner Zufallsvariablen ξ und ξ1, ..., ξn sowie ξ seien unabhängig und identisch verteilt.

13


Dann bezeichnen wir F c∗n als die komplementäre Verteilungsfunktion der Summen-variablen Sn = ξ1 + ... + ξn, also F c∗n(t) = P (Sn > t). Die Verteilung F ist nunsubexponentiell (F ∈ S), wenn

limx→∞

F c∗n(x)F c(x)

= n (2.22)

gilt. Für das Maximum der Zufallsvariablen Mn = max(ξ1, ..., ξn), wobei dieses erneuteine Zufallsvariable ist, ergibt sich für große x das interessante Ergebnis

P (Mn > x) ∼ P (Sn > x). (2.23)

Für alle subexponentiellen Verteilungen F und für alle ε > 0 gilt eεxF c(x) →∞, wennx gegen ∞ strebt. Dies bedeutet nun, dass die komplementäre Verteilungsfunktion (siebestimmt die Eigenschaften des „Tail“) nicht so stark fällt, wie jede positive Potenzder Exponentialfunktion steigt. Daher kommt auch der Name „subexponentiell“. EineVerteilungsfunktion ist also dann heavy-tail, wenn

F cξ (x) ∼ x−αL(x), für x→∞, α ∈]0, 2[, (2.24)

wobei L ∈ R0 eine langsam wechselnde Funktion ist (siehe auch Abschnitt 2.3). Häuf-ig wird auch die integrierte (komplementäre) Verteilungsfunktion FI verwendet, umSprünge oder abruptes Verhalten auszugleichen. Sie ist wie folgt definiert:

FI,ξ(t) =1µ

∫ t

0F c

ξ (x)dx, t ≥ 0. (2.25)

Folgende subexponentielle Verteilungen sind für die Modellierung von IP-Verkehr in-teressant. Für sie gilt außerdem F ∈ S und FI ∈ S. Dies gilt jedoch nicht für allesubexponentiellen Verteilungen. Zusätzlich wird die komplementäre Verteilungsfunk-tion (Fξ(t) = 1 − F c

ξ (t)) und Dichte fξ(x) (die Ableitung der Verteilungsfunktion)angegeben.

• Pareto-Verteilung

fξ(x) = ακα

(1

κ+ x

)α+1

, F cξ (t) =

(κ

κ+ t

)α

, für α, κ > 0

• Weibull-Verteilung

fξ(x) = aτtτ−1e−atτ

, F cξ (t) = e−atτ

, für a > 0, 0 < τ < 1

14


• Lognormalverteilung (F cξ ist nicht in geschlossener Form darstellbar)

fξ(x) =1√

2πσx· e−

(log x−µ)2

2σ2 , für µ ≥ 0, σ > 0

• Benktander Typ I

F cξ (t) =

(1 + 2

(β

α

)log t

)· e−β(log t)2−(α+1) log t, für α, β > 0

• Benktander Typ II

F cξ (t) = e

α

β t−(1−β)e−α tβ

β , für α > 0, 0 < β < 1

• Burr-Verteilung

fξ(x) = κατxτ−1

(1

κ+ xτ

)α+1

, F cξ (t) =

(κ

κ+ tτ

)α

, für α, κ, τ > 0

• Loggammaverteilung (F cξ ist nicht in geschlossener Form darstellbar)

fξ(x) =αβ

Γ(β)(log x)β−1x−α−1, für α, β > 0

2.5 Modellierung von IP-Verkehr

Zur Modellierung des IP-Verkehrs werden hier die beiden stochastischen Prozesse Frac-tional Gaussian Noise (FGN) und Fractional Autoregressive Integrated Moving Average(FARIMA) verwendet. Eine genauere Erläuterung der Prozesse steht in den Abschnitten3.2.1 und 3.2.2, hier soll nur ein kurzer Überblick gegeben werden.

Der Prozess FGN wird auch fraktionales weißes Rauschen genannt, er ist eng mit derFBM verwandt. Er ist sehr gut geeignet, um die so genannte Langzeitabhängigkeit(Abschnitt 3.1) zu modellieren, die sehr stark durch das Benutzerverhalten geprägtist. Neben der Langzeitabhängigkeit gibt es auch die Kurzzeitabhängigkeit. Sie wirdvor allem durch die TCP- und IP-Protokolle beeinflusst. Diese Protokolle entschei-den, wie die einzelnen Pakete über das Netzwerk geschickt werden, also über wel-che Knoten im Netzwerk ihr Weg läuft. Diese Kurzzeitabhängigkeit wird durch dieFARIMA-Modelle berücksichtigt, die sie zusätzlich zur Langzeitabhängigkeit model-liert. Durch die FARIMA-Modelle hat man auch die Möglichkeit, eventuelle Heavy-Tail-Eigenschaften zu modellieren.

15

3 Beschreibung und Bewertung der

einzelnen Schätzer

Um den so genannten Hurst-Parameter in paketvermittelten Datenflüssen vorhersagenzu können, müssen gemessene Daten, die sinnvollerweise für den Knoten, an dem ge-messen wurde, repräsentativ sind, analysiert werden. Hierfür stehen mehrere Methodenzur Verfügung, die im Abschnitt 3.3 näher erläutert werden. Zunächst wird aber im Ab-schnitt 3.1 der Hurst-Parameter und die damit verbundene Langzeitabhängigkeit (oder:„long-range dependence“ (LRD)) eingeführt und im Abschnitt 3.2 die Generierung vonTestdatensätzen erläutert. Diese werden benötigt, um Aussagen über die Genauigkeitder Schätzer machen zu können (Abschnitt 3.4).

Die passenden Algorithmen zu den unten stehenden Methoden stammen von [Taq05].Sie sind dort in S-Plus implementiert und wurden für die vorliegende Arbeit für GNUR (Open Source Implementierung von S) angepasst (nähere Erläuterungen hierzu imAnhang C).

3.1 Selbstähnlichkeit, Hurst-Parameter undLangzeitabhängigkeit

Selbstähnlichkeit und der Hurst-Parameter

Das Verhalten für große Zeiten beim IP-Verkehr, also die langfristige Entwicklung derProzesse, mit denen wir den Verkehr modellieren, lässt sich als selbstähnlich beschrei-ben. Ein Prozess (Xt)t∈[0,∞[ ist genau dann exakt selbstähnlich, wenn es für jeden Stre-ckungsfaktor a > 0 ein b(a) > 0 gibt, so dass die Verteilungen

(Xat0 , ..., Xatn) und b(a) (Xt0 , ..., Xtn

) (3.1)

übereinstimmen. Nun kann man den Faktor b(a) in aH umschreiben, sodass für allea > 0 und alle Zeitpunkte t0, ..., tn die Randverteilungen von

(Xat0 , ..., Xatn) und aH (Xt0 , ..., Xtn

) (3.2)

16

3 Beschreibung und Bewertung der einzelnen Schätzer

übereinstimmen. Ein Ergebnis von Lamperti ([Lam62]) besagt, dass sich ein exakt selb-stähnlicher Prozess durch ein H charakterisieren lässt, wenn bestimmte Vorraussetzun-gen gelten. Diesen Wert H nennt man Hurst-Exponent oder Hurst-Parameter. Zu die-sem Zusammenhang gibt es noch ein paar Bemerkungen, die wir später benötigen wer-den:

• Einen Prozess (Xt)t∈I , der die Gleichungen (3.1) oder (3.2) erfüllt, nennt manH-ss-Prozess, wobei hier „ss“ für „self-similar“ steht.

• Sei bei einem selbstähnlichen Prozess t die Zeitvariable und Xt die so genannteRaumvariable. Dann bedeutet die Gleichung (3.2), dass sich ein Strecken der Zeitmit dem Faktor a und ein Strecken des Raumes mit dem Faktor aH gegenseitigbedingen.

• Hat ein H-ss-Prozess stationäre Zuwächse, so wird er mit H-sssi-Prozess bezeich-net („stationary innovations“). Hat ein solcher Prozess auch ein existierendes ers-tes Moment und ist t > 0 so gilt wegen der Selbstähnlichkeit

E(X2t) = 2HE(Xt) (3.3)

und auf Grund der stationären Zuwächse

E(X2t) = E(X2t −Xt) + E(Xt) = E(Xt) + E(Xt) = 2E(Xt) (3.4)

Aus den Gleichungen (3.3) und (3.4) folgt sofort, dass E(Xt) = 0 für alle t ∈ R,wenn man H 6= 1 annimmt.

• Da für einen H-sssi-Prozess X−t = X−t − X0 = X0 − Xt = −Xt gilt, folgtwegen σ2 = Va(X1) = E(X2

1 ) im Falle H < 1

E(X2

t

)= E

(X2|t|sign(t)

)= t2HE

(X2

1

)= t2Hσ2, (3.5)

wenn er ein endliches zweites Moment besitzt. Dies wird ein Standardprozessgenannt, wenn σ2 = 1 ist. Des Weiteren gilt wegen den stationären Zuwächsenfür E(|X1|) <∞

E(|X2|) = E(|X2−X1 +X1|) ≤ E(|X2−X1|)+E(|X1|) = 2E(|X1|). (3.6)

Aus der Selbstähnlichkeit ergibt sich für solch einen Prozess

E(|X2|) = 2HE(|X1|), (3.7)

woraus 2H ≤ 2 und somit auch H ≤ 1 folgt.

17


• Der Hurst-Exponent lässt sich auch wie folgt durch die Größen α (siehe auchα-stabile Prozesse im Abschnitt 2.4.4) und d (siehe auch FARIMA-Reihen imAbschnitt 3.2.2) berechnen:

H = d+1α

(3.8)

Langzeitabhängigkeit

Ausgehend von einem H-sssi-Prozess (Xt)t∈[0,∞[ mit 0 < H < 1, Zuwächsen ∆(n) =Xn+1 −Xn und der Autokorrelation r(n) = E(∆(0)∆(n))) lässt sich diese Autokor-relation auch als

r(n)

∼ H(2H − 1)n2H−2E(X21 ), für n→∞ und H 6= 1

2

= 0 für n ≥ 1 und H = 12

(3.9)

schreiben. Bildet man aus den Autokorrelationskoeffizienten r(n) die Reihe∑∞

n=0 |r(n)|so ist diese für alle H < 1

2 endlich und wir haben eine negative Korrelation. Für H = 12

ist∑∞

n=0 |r(n)| = 0 und somit ist (∆(n))n∈Z unkorreliert. Ist 12 < H < 1 so ist die

Summe nicht mehr endlich und es liegt eine positive Korrelation vor. Nun lassen sichhieraus verschiedene Definitionen für die Langzeitabhängigkeit ableiten:

1. Einen diskreten Prozess oder eine Zeitreihe nennt man langzeitabhängig, wennfür ein H ∈]12 , 1[ die Asymptotik r(n) ∼ O(n2H−2) bzw. r(m)(n) ∼ k2H−2 fürzusammengesetzten Verkehr jeweils mit n,m→∞ gilt.

2. Man sagt, ein Prozess ist im weiteren Sinne langzeitabhängig, wenn∑

n∈N |r(n)|= ∞ für diskrete Prozesse und

∫∞0 |r(t)|dt für stetige Prozesse gilt. Auch hier

kann r(n) durch r(m)(n) ersetzt werden.

3. Die obigen Definitionen für die Langzeitabhängigkeit gelten nur bei existierenderVarianz der Prozesse. Ist diese nicht mehr gegeben, verallgemeinern wir dieseProzesse zu α-stabilen Prozessen mit 0 < α ≤ 2, wobei die Varianz nur fürα = 2 existiert. Die Bedingung für Langzeitabhängigkeit lautet hier H > 1

α .Für Prozesse mit existierender Varianz deckt sich die Aussage mit den bisherigen.Es muss noch erwähnt werden, dass es für α ≤ 1 keine H-sssi-Prozesse gibt, da0 < H < 1 beschränkt ist.

4. Alternativ zu 3. wurde von Heyde und Yang ([HeYa97]) ein weiterer Zugang zurLangzeitabhängigkeit von Prozessen ohne existierende Varianz gegeben. Eine sta-tionäre Folge mit dem Erwartungswert Null nennt man langzeitabhängig im Sinne

18


der Allan-Varianz (LRD-SAV) wenn der Quotient

(∑m

k=1Xk)2∑m

k=1X2k

→∞ (3.10)

in Wahrscheinlichkeit für m → ∞. Auch hier lässt sich ein Zusammenhang mitden α-stabilen Prozessen zeigen. Wenn der obige Prozess ein H-sssi-Prozess istund E(|X1|δ) < ∞ für ein δ ∈]0, 2[, so ist der Prozess genau dann LRD-SAV,wenn H > 1

δ . Dies untermauert, dass es sinnvoll ist, die Langzeitabhängigkeit fürα-stabile Prozesse wie in 3. zu definieren.

3.2 Generierung von Zeitreihen

Um die Genauigkeit der Schätzer für den Hurst-Exponenten bewerten zu können, be-nötigen wir Zeitreihen mit wohldefinierten Parametern für die Selbstähnlichkeit. ImFolgenden betrachten wir die beiden Methoden „fractional autoregressive integratedmoving-average“ (FARIMA) und „fractional Gaussian noise“ (FGN), mit denen selb-stähnliche Zeitreihen generiert werden können.

3.2.1 Fractional Gaussian Noise (FGN)

Diese Zeitreihe, auch „fraktionales weißes Rauschen“ genannt, lässt sich am anschau-lichsten über die fraktionale Brownsche Bewegung BH , welche im Abschnitt 2.4.3 er-klärt wurde, einführen. Das fraktionale weiße Rauschen ist die Zeitreihe Xi, die durchdie stationären Zuwächse der fraktionalen Brownschen Bewegung gegeben ist, also

Xi = BH(i+ 1)−BH(i), i ≥ 1. (3.11)

Dies ist erneut eine stationäre Gauß-Zeitreihe mit dem Mittelwert Null und der Kovari-anzfunktion γ(h) = E(XiXi+h), die durch γ(h) = 2−1((h+1)2H−2h2H + |h−1|2H)gegeben ist. Für H 6= 1

2 und h→∞ genügt sie der Gleichung

γ(h) ∼ H(2H − 1)h2H−2 (3.12)

und wennH = 12 dann ist γ(h) = 0 für alle positiven h. Der Hurst-ExponentH mit 1

2 <

H < 1 ist ein Maß für Langzeitabhängigkeit, das bedeutet, dass dieXi positiv korreliertsind. Die Dichte des Spektrums dieser Zeitreihe, also ihre Fourier-Transformierte, lautet

f(λ) = CH

(2 sin

λ

2

)2 ∞∑k=−∞

1|λ+ 2πk|2H+1

∼ CH |λ|1−2H (3.13)

19


-4

-3

-2

-1

0

1

2

3

4

0 1000 2000 3000 4000 5000

(a) H = 0, 6

-4

-3

-2

-1

0

1

2

3

4

0 1000 2000 3000 4000 5000

(b) H = 0, 7

-4

-3

-2

-1

0

1

2

3

4

0 1000 2000 3000 4000 5000

(c) H = 0, 8

-4

-3

-2

-1

0

1

2

3

0 1000 2000 3000 4000 5000

(d) H = 0, 9

Abbildung 3.1: FGN-Zeitreihen mit verschiedenen Hurst-Exponenten

mit λ→ 0 und CH konstant.

Mehrere FGN-Zeitreihen für verschiedene Hurst-Exponenten sind in Abbildung 3.1 dar-gestellt. Eine ausführliche Darstellung des fraktionalen weißen Rauschens findet manunter anderem sowohl in [SaTa92] als auch [SaTa94].

3.2.2 Fractional Autoregressive Integrated Moving-Average(FARIMA)

Im Abschnitt 3.2.1 wurde das fraktionale weiße Rauschen erläutert. Dieses eignet sichzur Modellierung von IP-Verkehr, wenn man große Zeitskalen betrachtet. Für kleineZeitintervalle ist dieses Modell jedoch nicht mehr genau genug. Um auch in diesemBereich genaue Aussagen machen zu können, führen wir die FARIMA-Modelle ein.FARIMA-Zeitreihen sind lineare Prozesse von der grundlegenden Form

Xi =∞∑

j=−∞ci−j · εj =

∞∑j=−∞

cj · εi−j, (3.14)

20


wobei die Zuwächse εj stochastische Zufallsvariablen sind, die nicht notwendigerwei-se Gauß-verteilt sein müssen. Die Unterschiede werden weiter unten erläutert. In denAbbildungen 3.2 und 3.3 kann man deutlich erkennnen, wie sich der α-Parameter (cha-rakteristisch für das Heavy-Tail-Verhalten) auf die Zeitreihen auswirkt.

-4

-3

-2

-1

0

1

2

3

4

0 1000 2000 3000 4000 5000

(a) H = 0, 6

-4

-3

-2

-1

0

1

2

3

4

0 1000 2000 3000 4000 5000

(b) H = 0, 7

-4

-3

-2

-1

0

1

2

3

4

0 1000 2000 3000 4000 5000

(c) H = 0, 8

-4

-3

-2

-1

0

1

2

3

4

5

6

0 1000 2000 3000 4000 5000

(d) H = 0, 9

Abbildung 3.2: FARIMA-Zeitreihen mit verschiedenen Hurst-Exponenten undα = 2

Normalverteilte FARIMA-Serie

Allgemein werden diese Zeitreihen mit FARIMA(p, d, q) bezeichnet. Wir wollen unszunächst dem Spezialfall einer FARIMA(0, d, 0) Serie widmen. Diese Prozesse sinddurch Xi = ∆−dεi, i ≥ 1 definiert, wobei die εi iid-Gauß-Zufallsvariablen sind, wobei„iid“ für independent, identically distributed steht. ∆−d wird als

∆−d =∞∑i=0

bi(−d) ·Bi (3.15)

interpretiert, mit Bεi = εi−1 (Rückwärtsoperator) und bi(−d) ist gegeben durch

bi(−d) =Γ(i+ d)

Γ(d) · Γ(i+ 1)und i = 1, 2, ... , (3.16)

21


-120

-100

-80

-60

-40

-20

0

20

40

60

80

0 1000 2000 3000 4000 5000

(a) H = 0, 6

-120

-100

-80

-60

-40

-20

0

20

40

60

80

0 1000 2000 3000 4000 5000

(b) H = 0, 7

-120

-100

-80

-60

-40

-20

0

20

40

60

80

0 1000 2000 3000 4000 5000

(c) H = 0, 8

-120

-100

-80

-60

-40

-20

0

20

40

60

80

0 1000 2000 3000 4000 5000

(d) H = 0, 9

Abbildung 3.3: FARIMA-Zeitreihen mit verschiedenen Hurst-Exponenten undα = 1, 5

wobei Γ hier die Gammafunktion bezeichnet. Nun kann man zeigen, dass die Autoko-varianzfunktion γ(h) mit −1

2 ≤ d ≤ 12 sich wie

γ(h) = EXi · Ei+h ∼ Cdh2d−1 für h→∞ (3.17)

mit Cd = Γ(1−2d)π sinπd verhält. Nun kann man auch die Dichte des Spektrums dieses

Prozesses angeben durch

f(λ) = Cd

(2 sin

λ

2

)2 ∞∑k=−∞

1|λ+ 2πk|2d+2

∼ Cd|λ|−2d für λ→ 0. (3.18)

Wenn man jetzt den allgemeinen Fall einer FARIMA(p, d, q)-Zeitreihe betrachtet, stelltman fest, dass diese Serien sich in ihrer Asymptotik bei der Kovarianzfunktion undder spektralen Dichte genauso wie FARIMA(0, d, 0)-Reihen verhalten, auch wenn dieFunktionen schwieriger werden. Eine allgemeine FARIMA-Reihe lässt sich durch

Xi − φ1Xi−1 − ...− φpXi−p = ∆−dεi − θ1∆−dεi−1 − ...− θq∆−dεi−q (3.19)

22


definieren. Dabei sind φi und θi die „autoregressive“- bzw. „moving average“-Koeffizi-enten. Sie verursachen jedoch kurzzeitabhängige Komponenten, die das spätere Schät-zen des Hurst-Exponenten beeinflussen können. Weitere Informationen zu diesen FA-RIMA-Reihen findet man in [SaTa94] in den Abschnitten 7.12 und 7.13.

FARIMA-Serie (nicht normalverteilt) mit Zuwächsen von endlicher Varianz

Anstelle der normalverteilten Zuwächse εi aus dem vorherigen Abschnitt, kann man sichauch Zufallsvariablen vorstellen, die zum Beispiel exponential- oder lognormalverteiltsind. Die kumulativen Verteilungsfunktionen sind für die Exponentialverteilung durch

F (x) = P (ε ≤ x) =

0 für x < 0

1− e−λx für x ≥ 0(3.20)

und für die Lognormalverteilung durch

F (x) = Φ(

ln(x)− µ

σ

)(3.21)

gegeben, wobei Φ die Verteilungsfunktion einer Normalverteilung ist. Sowohl im Er-wartungswert als auch in der Varianz verhalten sich diese Zeitreihen wie die Reihenmit normalverteilten Zuwächsen. Allerdings sind die einzelnen Zustände der Zufalls-variablen nur schwer zu ermitteln, da die Linearkombinationen von exponential- bzw.lognormalverteilten Größen nicht wieder eine exponential- oder lognormalverteilte Zu-fallsvariable ergeben.

FARIMA-Serie mit Zuwächsen von unendlicher Varianz

Diese FARIMA-Serien lassen sich am besten zur Modellierung von IP-Verkehr nutzen.Zuwächse εi mit einer unendlichen Varianz erhält man mit α-stabilen Prozessen, zumBeispiel mit der Pareto-Verteilung. Die Pareto-Verteilung hat die Verteilungsfunktion

F (x) = 1− 1xα

mit x ≥ 1. (3.22)

Die α-stabilen Prozesse genügen darüber hinaus der Bedingung P (ε > x) ∼ Cx−α fürx → ∞, wobei für uns die Annahme 1 < α ≤ 2 gilt. Für den Spezialfall mit α = 2haben wir normal-verteilte Zuwächse vorliegen. Desweiteren gilt die Langzeitabhängig-keit nur für d ∈ [0, 1 − 1

α [ und mit H = d + 1α haben wir auch eine Verbindung zum

Hurst-Exponenten. Weiterführende Darstellungen findet man zum Beispiel in [BrDa91].

23


3.3 Abschätzen des Hurst-Parameters

Nun wollen wir uns einigen Methoden widmen, mit denen man den Hurst-Parameter ei-ner Zeitreihe schätzen kann. Hierzu werden im Allgemeinen bestimmte Eigenschaften(also mathematische Größen) einer Zeitreihe gegenüber der Zeit oder den Frequenzeneiner Zeitreihe in einem meist doppelt logarithmischen Diagramm aufgetragen. Den ei-gentlichen Wert für den Hurst-Parameter kann man dann als Steigung einer Ausgleichs-geraden ablesen bzw. ermitteln. Alle im Folgenden von den einzelnen Schätzern produ-zierten Grafiken wurden aus der weiter oben erstellten FARIMA-Zeitreihe mitH = 0, 8und α = 2 (siehe Abbildung 3.2(c)) abgeleitet.

3.3.1 Absolute Momente

Bei der Methode der Absoluten Momente, wird die jeweilige Zeitreihe in Blöcke X(m)t

unterteilt. Für jeden Block kann man dann das n-te Moment berechnen und mittels derGleichung (3.23) diesen Wert nochmals über alle Blöcke mitteln.

AM (m)n =

1Nm

N

m∑k=1

∣∣∣X(m)t − µ

∣∣∣n (3.23)

Die Werte für die einzelnen Blöcke trägt man nun in ein doppelt logarithmisches Dia-gramm ein und wählt eine Ausgleichsgerade mit der Methode der kleinsten Quadrate(Abbildung 3.4). Die Steigung a der Geraden ist durch a = n(H − 1) gegeben, woraussich mit Leichtigkeit der Hurst-Exponent berechnen lässt.

In den meisten Fällen wird hier nur das erste absolute Moment benutzt, wobei diesesVerfahren auch mit den höheren Momenten funktioniert. Benutzt man das zweite Mo-ment, so nähern wir uns der Varianzmethode an, die im Abschnitt 3.3.2 behandelt wird.

Dieses Verfahren des ersten absoluten Momentes wurde von Higuchi in [Hig88] abge-wandelt. Statt disjunkter Blöcke von Daten benutzt er ein Datenfenster, welches über dieZeitreihe gleitet. Der mathematische Zusammenhang ist in der Gleichung (3.24) darge-stellt, wobei [x] die Gaußklammer mit g = [x] ist, wenn g die größte ganze Zahl mitg ≤ x ist.

L(m) =N − 1m3

m∑i=1

[N − 1m

]−1 [N−i

m ]∑k=1

∣∣∣∣∣∣i+km∑

j=i+(k−1)m+1

Xj

∣∣∣∣∣∣ (3.24)

Dieses Verfahren von Higuchi ist offensichtlich rechenaufwendiger, liefert aber geradefür kurze Zeitreihen gute Werte für den Hurst-Exponenten.

24


Abbildung 3.4: Das erste absolute Moment

3.3.2 Varianzmethode (Aggregated Variance)

Die Varianzmethode funktioniert analog zur Methode der absoluten Momente, nur dassman sich hier auf die Varianz, also das zweite Moment, beschränkt. Auch hier nimmtman eine in disjunkte Blöcke geteilte Zeitreihe X(m)

t an, von der man mit Hilfe von

V ar(X(m)

)=

1Nm

N

m∑k=1

(X

(m)k − µ

)2(3.25)

die mittlere Varianz der Blöcke berechnet, wobei µ das Mittel über alle Daten ist. Trägtman hier die Varianz der Blöcke gegenüber der Zeit in einem doppelt logarithmischenDiagramm auf (Abbildung 3.5) und bildet eine Ausgleichsgerade durch die Punkte, soist die Steigung β gegeben durch β = 2H − 2. Somit lässt sich der Hurst-Exponentdurch H = 1 + β

2 berechnen. Die gestrichelte Linie hat eine Steigung von β = −1und stellt den unteren Grenzwert für die Langzeitabhängigkeit dar (1 ≥ H ≥ 0, 5 bzw.0 ≥ β ≥ −1).

3.3.3 Periodogramm

Das Periodogramm einer Zeitreihe mit der Länge N wird in Abhängigkeit zu den Fre-quenzen einer solchen Reihe bestimmt und ist durch

I(λ) =1

2πN

∣∣∣∣∣N∑

k=1

Xk · e−ikλ

∣∣∣∣∣2

(3.26)

25


Abbildung 3.5: Die Varianzmethode

gegeben. Diese Berechnung liefert uns die Spektraldichte der Zeitreihe, wenn sie eineendliche Varianz aufweist, und basiert auf der Fourier-Transformation. Trägt man dieSpektraldichte gegen die Frequenz in einem doppelt logarithmischen Diagramm auf,so kann man anhand der Steigung der Ausgleichsgeraden den Wert 1 − 2H errechnen.Hierbei muss man beachten, das die Spektraldichte ihre Proportionalität zu |λ|1−2H nurfür Frequenzen nahe des Ursprungs aufweist (In der Praxis werden nur die unteren 10%der Frequenzen zur Berechnung vonH benutzt). Für den Fall einer unendlichen Varianzder Zeitreihe gibt es zwar noch keinen theoretischen Beweis dafür, dass diese Methodeauch dann den Hurst-Parameter schätzt. Empirische Untersuchungen weisen aber daraufhin, dass auch dann verlässliche Werte ermittelt werden (siehe [KlMi96a], [KlMi96b]und [KoMi00]).

Modi�ziertes Periodogramm

Im Bild 3.6 ist sehr schön zu sehen, dass sich viele der Periodogramm-Werte am rechtenEnde befinden. Dies hat natürlich einen gewissen Einfluss auf das Ergebnis der Aus-gleichsgeraden. Um diesen Einfluss zu minimieren, kann man den Logarithmus derFrequenzen in gleich große Bereiche einteilen, innerhalb derer man zuerst über diePeriodogramm-Werte mittelt, und dann eine Ausgleichsgerade durch die gemitteltenWerte konstruiert. Allerdings hat sich gezeigt, dass dies keine wirkliche Verbesserungfür die geschätzten Parameter bringt.

26


Abbildung 3.6: Das Periodogramm

Kontinuierliches Periodogramm

Das kontinuierliche Periodogramm soll hier nur der Vollständigkeit halber erwähnt wer-den. Es berechnet das Periodogramm einer Zeitreihe für verschiedene „Grenzfrequen-zen“. Somit erhält man natürlich auch verschiedene Werte für den Hurst-Parameter.

Kumulatives Periodogramm

Das kumulative Periodogramm entsteht, indem man jeweils die einzelnen Werte, begin-nend bei einer kleinen unteren Grenzfrequenz νL, bis zur aktuellen Frequenz aufsum-miert und in das Diagramm einträgt. Die Ergebnisse verhalten sich dann proportional zu|ν|2−2H . Der Graph des Periodogramms verläuft so wesentlich ruhiger. Allerdings ver-birgt sich ein zusätzlicher Fehler in dieser Methode, da über diskrete Werte summiertwird, die Proportionalität zu |ν|2−2H aber nur für das Integral gegeben ist. In [Taq05]schlägt Murad Taqqu deshalb

FL(νk) :=2πN

k∑j=L+1

I(νj), L < k (3.27)

zur Berechnung des kumulativen Periodogramms vor, wobei νL die untere Grenzfre-quenz ist. Nun kann man das kumulative Periodogramm für L < k ≤ M berechnen.Wählt man k genügend klein, so gilt

FL(νk) ∼ C1

(ν2−2H

k − ν2−2HL

). (3.28)

27


Mit der Methode der kleinsten Quadrate wird nun den Werten wieder eine Funktionzugeordnet und somit der Hurst-Exponent näherungsweise bestimmt. Diese Funktionverläuft in einem doppelt logarithmischen Diagramm nicht mehr linear (wie bei allenanderen Schätzern zuvor), weshalb auf eine grafische Ausgabe des Ergebnisses verzich-tet wurde.

3.3.4 Varianz der Restglieder

Zunächst benötigt man für diese Methode die Partialsummen Yt =∑t

k=1Xk (hier istdie Partialsumme des ersten Blockes exemplarisch angegeben) der einzelnen Blöcke ei-nes zusammengesetzten Verkehrs. Nun wird wieder eine Gerade at+b in einem doppeltlogarithmischen Diagramm den Partialsummen angepasst. Mittels Yt − (at + b) kannder jeweilige Rest einer Partialsumme berechnet werden. Anschließend wird durch

1m

m∑t=1

(Yt − at− b)2 (3.29)

die Varianz der Reste geschätzt, wobei Yt als Summe der Zufallsvariablen (Verkehr) biszum Zeitpunkt t angenommen werden kann.

Nun kann man zeigen, dass sich die Varianz der Störung (also des Restes) in 3.29 in derVerteilung genau wiem2H verhält (siehe [TTW95] für eine exakte Herleitung). Folglichkann man die Größe 2H in dem Diagramm 3.7 als Steigung der Ausgleichsgeradenablesen.

Abbildung 3.7: Die Varianz der Restglieder

28


3.3.5 Verhältnis der Varianz der Restglieder

Diese Methode basiert auf der Berechnung der Varianz der Restglieder (siehe Abschnitt3.3.4). Hier wird diese Varianz auf zwei verschiedene Weisen berechnet (s.u.) und an-schließend ihr Verhältnis ermittelt. Trägt man dieses Verhältnis in einem doppelt loga-rithmischen Diagramm auf (Abbildung 3.8), so kann man an Hand der Steigung einerAusgleichsgeraden den α-Parameter, der das Heavy-Tail-Verhalten charakterisiert, er-mitteln und somit lässt sich auch der Hurst-Exponent berechnen (siehe Abschnitt 3.2.2).

Abbildung 3.8: Das Verhältnis der Varianz der Restglieder

Ausgehend von einem zusammengesetzten Verkehr der Länge N mit der Blockgröße mberechnet man für alle möglichen Blockgrößen mit 1 < m ≤ N den

Erwartungswert E(Xi), der durch

E(Xi) =1N

N∑i=1

Xi (3.30)

definiert ist und bildet anschließend den jeweiligen Rest zur Ausgleichsgeradendurch die Erwartungswerte für jeden Block. Für diese Reste wird dann die Varianzberechnet. Nun wird noch der

Median für jede mögliche Blockgröße ermittelt. Er ist durch

Xi =

XN+12

für N ungerade,

12

(XN

2+XN

2+1

)für N gerade,

(3.31)

29


für eine geordnete Zufallsvariable Xi mit der Länge N definiert. Auch für dieMediane wird eine Ausgleichsgerade ermittelt und die jeweiligen Reste zur Gera-den bestimmt, von denen dann die Varianz für die unterschiedlichen Blockgrößenberechnet wird.

Nun setzt man die Varianzen der verschiedenen Blockgrößen ins Verhältnis und trägtdieses in einem doppelt logarithmischen Diagramm auf. Anhand der Steigung einer er-neuten Ausgleichsgeraden lässt sich der α-Parameter ermitteln.

3.3.6 R/S-Methode

Die R/S-Methode wurde zuerst von Hurst in [Hur51] genauer untersucht. Auch hier wirdeine gegebene Zeitreihe Xk mit N Werten in L Blöcke der Länge k = N

L eingeteilt.Des Weiteren können die Partialsummen Yt =

∑tk=1Xk gebildet werden, die man als

aufsummierten Verkehr auffasst. Nun definiert man noch den angepassten Wertebereich

R(l, k) = max1≤j≤k

(Yl+j −Yl−j

k(Yl+k −Y − l))− min

1≤j≤k(Yl+j −Yl−

j

k(Yl+k −Y − l))

(3.32)

und mit Xl,k = 1k

∑k+lj=k+1Xj (der Mittelwert eines jeden Blockes) die Standardabwei-

chung der Zeitreihe durch

S(l, k) =

√√√√1k

l+k∑j=l+1

(Xj − Xl,k

)2, (3.33)

so dass man den so genannten reskalierten angepassten Wertebereich durch den Bruch

Q(l, k) =R(l, k)S(l, k)

(3.34)

berechnen kann. Nimmt man nun stationäre Zuwächse für die Zeitreihe an, so sind dieGrößen R(l, k) und S(l, k) für alle l gleich. Des Weiteren weisen sie die Proportionali-täten R(k) ∼ kH = kd+ 1

α und S(k) ∼ k1α− 1

2 auf, so dass gilt

Q(k) =R(k)S(k)

∼ kd+ 12 . (3.35)

Auch hier wird der Logarithmus von Q(k) gegen den Logarithmus von k aufgetragenum d bestimmen zu können.

30


Abbildung 3.9: Die R/S-Methode

3.3.7 Whittle-Schätzer (Maximum Likelihood Estimator)

Der Whittle-Schätzer basiert auf dem Periodogramm, das in Abschnitt 3.3.3 näher be-schrieben wurde. Hierzu wählt man einen Vektor η = (σ2,H, η3, ..., ηm)T , von dem dieSpektraldichte f(η, ·) abhängig ist. Der eigentliche Schätzer ist hier der Vektor η, derdie Funktion

Q(η) :=∫ π

−π

I(λ)f(λ, η)

dλ+∫ π

−πlog f(λ, η)dλ (3.36)

minimiert, wobei I(λ) wieder das Periodogramm der Zeitreihe ist. Die Funktion Q lässtsich durch wenige Annahmen vereinfachen. Wir werden die Funktion f renormieren, sodass f = c ·f∗. Daraus folgt, dass für den zweiten Term in (3.36)

∫ π−π log f(λ, η)dλ = 0

gilt. Der erste Term wird nun durch den Faktor c dividiert. Da dieser aber von allenanderen Parametern unabhängig ist, hat er keinen Einfluss auf die Minimierung vonQ. Darüber hinaus wird in aktuellen Anwendungen nicht das Integral berechnet, son-dern lediglich über die Frequenzen λi = 2πj

N mit j = 1, 2, ..., (N−12 ), die man bei der

Fourier-Transformation der Zeitreihe als Ergebnis erhält, summiert. Somit ergibt sichzur Minimierung die Funktion

Q∗(λ) =

N−12∑

j=1

I(λj)f∗(λj , η)

. (3.37)

Hat man sehr große Datensätze, so dauert die Berechnung mit dem Whittle Schätzerrecht lange. Dies kann man umgehen, indem man erneut von zusammengesetztem Ver-

31


kehr ausgeht und

X(m)k =

1m

mk∑j=m(k−1)+1

Xj (3.38)

bildet. Allerdings führt dies bei kürzeren Zeitreihen zu einem größeren Fehler.

3.3.8 Lokaler Whittle-Schätzer

Der lokale Whittle-Schätzer wurde von P.M. Robinson ([Rob95]) entwickelt. Es ist einhalbparametrischer Schätzer, so dass wir zu Berechnung von H nur Frequenzen nahedes Ursprungs im Spektrum verwenden können. Die spektrale Dichte der Zeitreihe ge-nügt dann

f(λ) ∼ g(H) · |λ|1−2H für λ→ 0. (3.39)

Genau wie der Whittle-Schätzer (Abschnitt 3.3.7) basiert auch der lokale Whittle--Schätzer auf dem Periodogramm einer Zeitreihe, allerdings benötigen wir zur Berech-nung noch eine weitere Größe m ≤ N

2 mit 1m + m

N → 0 für N →∞. Mit der Gleichung(3.39) ergibt sich analog zu der zu minimierenden Gleichung des Whittle-Schätzers

Q(g,H) :=1m

m∑j=1

(I(λj)

g(H) · λ1−2Hj

+ log g(H) · λ1−2Hj

). (3.40)

Ersetzt man g(H) durch den für g(H) geschätzten Wert G = 1m

∑mj=1

I(λj)

λ1−2Hj

, so lässt

sich Q(g,H) zu

R(H) := Q(G,H)− 1 = log

1m

m∑j=1

I(λj)λ1−2H

j

− (2H − 1)m

m∑j=1

log λj (3.41)

vereinfachen. Jenes H , das R(H) minimiert, entspricht dem Hurst-Parameter der zu-grunde liegenden Zeitreihe. Zu dem Parameter m lässt sich noch sagen, dass er mög-lichst groß gewählt werden sollte, um eine schnelle Annäherung von H an den Hurst-Parameter zu erreichen. Weist die zu untersuchende Zeitreihe im nicht idealen Fall auchKurzzeitabhängigkeit auf, was natürlich die spektrale Dichte beeinflusst, so dürfen nurFrequenzen ganz nahe am Ursprung bei der Berechnung betrachtet werden, wofür einkleines m benötigt wird.

3.3.9 Wavelet-Analyse

Die Wavelet-Analyse ist das neueste Verfahren, um den Hurst-Exponenten zu berech-nen. Es wurde u.a. von Flandrin [Fla92] und Abry et al. [AbVe98, AFT01+] entwickelt

32


und geht auf die Wavelet-Transformation zurück, mittels derer man die Daten bzw.das Signal in eine Folge von Wavelet-Koeffizienten überführen kann, aus denen mandann den Hurst-Parameter ableitet. Die Wavelet-Transformation ist ähnlich der Fourier-Transformation. Auch hier benötigen wir so genannte Basisfunktionen (bei der Fourier-Transformation sind es die Sinus- und Kosinusfunktionen), die Wavelets genannt wer-den. Der Vorteil der Wavelet-Transformation gegenüber der Fourier-Transformation istdie zeitliche Lokalität der Basisfunktionen und die geringere Laufzeit. Sie wird haupt-sächlich in Kompressionsverfahren verwendet.

Allgemein besteht eine Basis für die Wavelet-Transformation aus einer Skalenfunktionψj,i(x) = 2

j

2ψ(2jx − i) und einer Waveletfunktion ϕj,i(x) = 2j

2ϕ(2jx − i), für dieeine geeignete Skalierung und Translation gewählt werden muss. Der Parameter i gibtdie Translation und der Parameter j die Skalierung der beiden Funktionen der Basis an.Eine Funktion f , die sich in diesem Funktionenraum befindet, lässt dich durch die Basiswie folgt zusammensetzen

f(x) =∞∑

i=−∞Aj0,i · ψj0,i(x) +

∞∑j=j0

∞∑i=−∞

Dj,i · ϕj,i(x). (3.42)

Dabei werden die Aj,i als Skalenkoeffizienten und die Dj,i als Wavelet-Koeffizientenbezeichnet. Sie lassen sich folgendermaßen berechnen:

Aj,i =∫ ∞

−∞f(x) · ψj,i(x)dx und Dj,i =

∫ ∞

−∞f(x)ϕj,i(x)dx. (3.43)

Um den Hurst-Exponenten zu schätzen, nehmen wir einen stationären Gauß-Prozess(Xt)t∈R an, dessen Quadrat integrierbar ist, also

∫∞−∞X2

t dt < ∞. Des Weiteren wähltman ein Wavelet mit m ≥ 1 verschwindenden Momenten, das heißt, das Integral überdas Produkt von dem Wavelet und der m-ten Potenz der Variablen ist Null. Mit einerSchrittanzahl n an der Stelle k lassen sich die Wavelet-Koeffizienten durch

DXn,k =

1√n

∫ ∞

−∞Xt · ϕ

(t

n− k

)dt (3.44)

berechnen. Unter unserer Annahme, dass Xt ein Gauß-Prozess ist und Langzeitabhän-gigkeit vorliegt, kann man zeigen, dass

E((DX

n,k

)2) ∼ C(ϕ,H, f

)n2H−1, (3.45)

wobei C(ϕ,H, f) > 0 eine Konstante ist. Nun benötigt man noch die Beobachtung desProzesses für die Zeiten t ∈ [0, N ] und eine Schrittanzahl nj mit j = 1, 2, ..., J . Jetztkann man

SN (nj) =1Nj

Nj∑k=1

(DX

n,k

)2(3.46)

33


definieren, wobei Nj =⌊

Nnj

⌋die zur Schrittanzahl vorhanden Koeffizienten sind. Man

kann SN (nj) als empirisches Mittel von(DX

n,k

)2ansehen. Mit der Beziehung aus Glei-

chung (3.45) und einer doppelt logarithmischen Auftragung von SN (nj) gegen nj wiein Abbildung 3.10 lässt sich der Hurst-ExponentH als Steigung der Regressionsgeradenablesen.

Abbildung 3.10: Die Wavelet-Analyse

3.4 Bewertung der Schätzer

Die im Abschnitt 3.3 beschriebenen Schätzer arbeiten nach unterschiedlichen Verfahren,so dass es auf der Hand liegt, dass sie nicht alle gleich gut bzw. gleich gut geeignetsind, um bestimmte Größen in gegebenen Zeitreihen zu ermitteln. Um hiervon einenEindruck zu erhalten, wurden mit den Methoden aus dem Abschnitt 3.2 Zeitreihen fürverschiedene Hurst-Exponenten generiert. Um statistische Ausnahmen zu relativieren,wurden jeweils für den gleichen Hurst-Exponenten 10 verschiedene Zeitreihen durchverschiedene Startvektoren für den Zufallsgenerator in den Algorithmen erzeugt, wobeisich die 10 Startvektoren für einen neuen Hurst-Parameter H jeweils wiederholen.

Dann wurde jeweils der Hurst-Exponent (gegebenenfalls durch Berechnungen aus wei-teren ermittelten Größen durch die Algorithmen) der einzelnen Zeitreihen geschätzt. DerDurchschnitt der einzelnen Ergebnisse ist in den Tabellen 3.1, 3.2 und 3.3 dargestellt.Wie stark die einzelnen Ergebnisse schwanken, kann man den Grafiken im Anhang A.2entnehmen. Alle Methoden liefern einen geschätzten Wert für den Hurst-Parameter. Le-

34


diglich die Methode, die mit dem Verhältnis der Varianzen der Restglieder arbeitet, lie-fert uns einen Wert für α, also für die Heavy-Tail-Eigenschaft.

3.4.1 Schätzen von FGN-Reihen

Für die FGN-Reihen liefern 9 der insgesamt 12 in Tabelle 3.1 aufgeführten Schätzerbrauchbare Ergebnisse. Lediglich die Schätzer

• Absolute Momente,

• Varianzmethode und

• R/S-Methode

sind hier ungenau, wobei sie für kleineH (0, 6 ≤ H ≤ 0, 8) auch noch akzeptable Werteliefern und bei steigendem H zunehmend ungenauer werden. Auch das Verfahren, wel-ches das Verhältnis α der Varianz berechnet (Kap. 3.3.5), ermittelt hier gute Werte fürdas Heavy-Tail-Verhalten (α = 2) des fraktionalen weißen Rauschens. Eine Übersichtüber alle geschätzten Werte für α befindet sich in Tabelle 3.4.

Vorgabe für H 0, 6 0, 7 0, 8 0, 9 0, 967Absolute Momente 0,60 0,70 0,79 0,87 0,92Varianzmethode 0,60 0,70 0,79 0,87 0,92Periodogramm 0,60 0,70 0,80 0,91 0,97↪→ modi�ziert 0,59 0,69 0,79 0,90 0,97↪→ kumulativ 0,61 0,71 0,83 0,91 0,96Varianz der Restglieder 0,60 0,70 0,80 0,90 0,96↪→ Durchschnitt 0,59 0,69 0,79 0,89 0,96R/S-Methode 0,62 0,69 0,75 0,80 0,83Whittle-Schätzer 0,60 0,70 0,80 0,90 0,97↪→ lokal 0,60 0,70 0,80 0,90 0,97Wavelet-Analyse 0,61 0,71 0,81 0,91 0,98

Tabelle 3.1: Geschätzte Werte für den Hurst-Parameter bei FGN-Reihen

3.4.2 Schätzen von FARIMA-Reihen

Zunächst müssen wir die Reihen ohne Langzeitabhängigkeit (α = 2) in Tabelle 3.2 vondenen mit Langzeitabhängigkeit (α < 2) in Tabelle 3.3 unterscheiden, da die Genauig-keit der einzelnen Schätzer signifikante Unterschiede aufweist.

35


FARIMA-Reihe mit α = 2

Die FARIMA-Reihen ohne Langzeitabhängigkeit werden von den Schätzern ähnlich gutvorhergesagt wie die Reihen mit fraktionalem weißen Rauschen. Allerdings konnte dasmodifizierte Periodogramm seine Ergebnisse verbessern. Ansonsten sind es auch hierwieder die Schätzer

• Absolute Momente,

• Varianzmethode und

• R/S-Methode,

die schlechte bzw. ungenaue Ergebnisse liefern. Auch das Verhalten, dass die Ergeb-nisse mit steigendem H immer ungenauer werden, kann man bei diesen drei Methodenbeobachten.


Tabelle 3.2: Geschätzte Werte für den Hurst-Parameter bei FARIMA-Reihen mitα = 2, 0

FARIMA-Reihe mit α = 1, 5

Allgemein können wir hier die Spalte für H = 0, 6 in Tabelle 3.3 aus unserer Betrach-tung herausnehmen, da wegen der Bedingung H > 1

α keine Langzeitabhängigkeit, dieuns ja gerade auf Grund der Vorhersagen für den IP-Verkehr interessiert, vorliegt. Einzigdas Verhältnis der Varianzen, also der Wert für α, sowie der Hurst-Exponent durch dieVarianz der Restglieder wird annähernd richtig ermittelt. Das Verhältnis der Varianzen

36


liefert lediglich bei größeren Werten für H etwas ungenauere Ergebnisse. Alle anderenSchätzer ermitteln hier generell ein zu kleines H .


Tabelle 3.3: Geschätzte Werte für den Hurst-Parameter bei FARIMA-Reihen mitα = 1, 5

Vorgabe für H 0,6 0,7 0,8 0,9 0,967

FGN-Reihen (α = 2) 1,98 1,99 1,99 1,99 1,99FARIMA-Reihen (α = 2) 1,99 1,99 2,00 2,01 2,01FARIMA-Reihen (α = 1, 5) 1,48 1,48 1,48 1,48 1,48

Tabelle 3.4: Geschätzte Werte für das Heavy-Tail-Verhalten

3.4.3 Ergebnis: Welcher ist der beste Schätzer?

Es gibt nicht „den besten Schätzer“. Der eine Schätzer eignet sich gut für FARIMA-Zeitreihen, der ander wiederum für FGN-Zeitreihen. Es bietet sich an, immer mehrereSchätzer zu kombinieren, um eine möglichst präzise Aussage treffen zu können. Einenguten Einstieg bekommt man mit dem Verhältnis der Varianzen. Dieser Schätzer liefertein gutes Ergebnis, wenn es darum geht, Langzeitabhängigkeit auszuschließen. Nunkann man mehrere weitere Methoden benutzen, um den Hurst-Exponenten zu schätzen.Wenn mehrere der oben erwähnten „guten“ Schätzer ähnliche Ergebnisse liefern, sokann man sich recht sicher sein, dass der Hurst-Exponent hinreichend genau bestimmtist.

Handelt es sich wissentlich um langzeitabhängige Zeitreihen oder um unbekannte Zeitrei-hen, ist man mit der Varianz der Restglieder nach den Tabellen in Abschnitt 3.4 amgenauesten.

37

4 Auswertung von realem IP-Verkehr

Der IP-Verkehr, der für diese Auswertung herangezogen wurde, wurde am RegionalenRechenzentrum für Niedersachsen (kurz: RRZN) am zentralen Router, der die Verbin-dung zum G-WIN herstellt, gemessen. Die Messung fand an drei verschiedenen Tagen(Montag, Donnerstag und Freitag) im Januar 2005 statt. Es wurde zu jeder vollen Stundejeweils fünf Minuten lang der ein- bzw. ausgehende IP-Verkehr der Universität Hanno-ver mittels TCPDump aufgezeichnet.

4.1 Besonderheit des gemessenen Verkehrs

Der hier gemessene Verkehr weist eine Besonderheit auf. Auch wenn diese sich nichtmaßgeblich auf die Resultate auswirkt, wie wir später sehen werden, sollte sie trotzdemkurz erwähnt werden, da sie nicht unbedingt typisch für allgemeine Datenströme imInternet ist.

Das der Universität Hannover angegliederte Albert-Einstein-Institut (AEI) ist in der phy-sikalischen Grundlagenforschung tätig und sendet seine Messergebnisse, die von einemGravitationswellendetektor stammen, zu einem Max-Planck-Institut in Berlin. Dadurchwird ein Datenstrom mit recht konstantem und nicht unerheblichen Volumen hervor-gerufen. Da zunächst nicht bekannt war, ob sich dieser IP-Verkehr auf die Ergebnisseauswirkt oder nicht, wurden die Auswertungen weiter unten in diesem Kapitel sowohlfür den ursprünglichen Verkehr als auch für den von diesem Datenstrom bereinigtenVerkehr erstellt.

4.2 Erstellen der Zeitreihen aus dem gemessenenVerkehr

Nachdem der IP-Verkehr mit TCPDump aufgezeichnet wurde, konnten die verschie-denen Zeitreihen erstellt werden. Da die Aufzeichnung nicht immer genau zur vollenStunde begann, sondern durchaus bis zu einer Sekunde verzögert, wurden die ersten

38


und letzten beiden Sekunden einer jeden Messung abgeschnitten, um sie vergleichbarzu machen. Dann wurden die Anzahl der IP-Pakete und das Datenvolumen für eine In-tervalldauer von 10 µs berechnet. Hieraus liessen sich dann durch einfaches Summierenauch die Zeitreihen für die größeren Intervalle erstellen. Als nächstes wurden dann dieDatenraten des IP-Verkehrs aus Intervalldauer und Datenvolumen berechnet und die zu-gehörige Varianz für die unterschiedlichen Intervalle ermittelt. Eine mögliche Betrach-tung der Zwischenankunftszeiten wurde im Rahmen dieser Arbeit nicht durchgeführt.

4.3 Auswertung der Zeitreihen

In diesem Abschnitt sollen die Zeitreihen ausgewertet werden. Hierzu müssen zunächstdie Intervalle bestimmt werden, die hierfür geeignet sind (Abschnitt 4.3.1). Dann wer-den wir den Parameter α für das Heavy-Tail-Verhalten bestimmen und anschließend denHurst-Exponenten ermitteln, der uns Aufschluss über die Langzeitabhängigkeit des IP-Verkehrs gibt. Im Abschnitt 4.3.4 wollen wir den Hurst-Exponenten mit einer weiterenMethode verifizieren, bevor wir letztendlich die Ergebnisse bewerten.

4.3.1 Wahl der geeigneten Diskretisierungen

Die von TCPDump aufgezeichneten Pakete wurden innerhalb bestimmter Intervalle auf-summiert, sowohl die Anzahl als auch das Volumen und die daraus resultierende Daten-rate. Die Intervalle wurden wie in der Tabelle 4.1 dargestellt festgelegt. Zusätzlich istdie Anzahl der Werte innerhalb eines Intervalls angegeben.

10 µs 20 µs 40 µs 80 µs 100 µs 200 µs29.600.000 14.800.000 7.400.000 3.700.000 2.960.000 1.480.000

400 µs 800 µs 1 ms 2 ms 4 ms 8 ms

740.000 370.000 296.000 148.000 74.000 37.000

10 ms 20 ms 40 ms 80 ms 100 ms 200 ms

29.600 14.800 7.400 3.700 2.960 1.480

400 ms 800 ms 1 s 2 s 4 s 8 s

740 370 296 148 74 37

Tabelle 4.1: Dauer der Intervalle und Anzahl der gemessenen Werte

Entscheidend ist nun, dass nur die Intervalle zur Vorhersage des Hurst-Exponenten be-nutzt werden, die verlässliche Werte liefern. Wenn wir die großen Intervalle betrachten,haben wir nur wenige Werte, die zur Auswertung herangezogen werden können. Dies

39


legt nahe, dass die Vorhersage der Langzeitabhängigkeit ungenau wird, wenn bei sowenigen Werten überhaupt eine Langzeitabhängigkeit festgestellt werden kann. WeitereUngenauigkeiten lassen sich darin begründen, das Regressionsgeraden, die auf wenigeWerte angewendet werden, auch keine genauen Ergebnisse liefern können.

Werden die Intervalle zu kurz, so werden theoretisch Datenmengen innerhalb eines In-tervalls übertragen, die physikalisch gar nicht möglich sind. Nehmen wir als Beispieleinen Ethernet-Rahmen. Dieser kann eine maximale Größe von 1.518 Byte annehmen(wenn man die 8 Bytes für „Preamble“ und „Start of Frame“ vernachlässigt). Die Band-breite des Routers, an dem die Daten gemessen wurden, beträgt zurzeit 155 MBit/s.Daraus ergibt sich eine Übertragungsdauer t für den Rahmen von

t =1.518 · 8 Bit

155MBit

s

=12.144

155.000.000s = 78, 35 µs.

Es ist offensichtlich, dass die Verteilung des Volumens bei Intervallgrößen unter 80 µszu falschen Ergebnissen führen muss. Aber auch eine Intervallgröße von 80 µs führt zueinem falschen Ergebniss, da in keiner Weise sichergestellt ist, dass die Übertragungeines Rahmens immer am Anfang des Intervalls beginnt. Hier benötigen wir eine Heu-ristik, die uns eine minimale Intervallgröße liefert, bei der die durch Intervallgrenzengeteilten Rahmen sich nicht auf die Verteilung der Datenmenge auswirken.

Abbildung 4.1: Auswahl der geeigneten Intervalle

40


In der Abbildung 4.1 ist eine Folge von verschieden großen Rahmen für steigende In-tervalldauern dargestellt. Die Anzahl der Rahmen eines Intervalls entspricht der Summeder Rahmen, die innerhalb des Intervalls ihren Sendebeginn haben. Aus der entsprechen-de Summe des Datenvolumens und der Intervalldauer wurden die Datenraten ermittelt.Sowohl die Datenrate als auch das Volumen sind in jedem Intervall durch Balken dar-gestellt (Anzahl der Rahmen in hellgrau, Volumen in dunkelgrau). Hier kann man sehrdeutlich erkennen, dass auch bei einer Intervallgröße von 200 µs die rechnerische Da-tenrate über der physikalisch möglichen Datenrate liegt. Als Heuristik bietet sich nunder Vergleich der geschätzten Hurst-Exponenten für Datenrate und -volumen an. Erstwenn beide identisch sind, ist die minimale Intervalldauer erreicht. Diese muss aberimmer geringer werden, wenn die Bandbreite des Links erhöht wird. In der Abbildungwürden dann die Balken für die Rahmen entsprechend kürzer werden.

Als letzten Punkt gilt es hier anzuführen, dass ebenso die Zeitreihen für die Anzahl derPakete in einem Intervall zu ungenauen Ergebnissen führen, da das Datenvolumen einesRahmens zwar nach oben hin beschränkt aber keinesfalls konstant ist. Die Zeitreihen fürdas Datenvolumen und die Datenrate liefern hier wesentlich genauere Werte. Sowohldie Datenrate als auch das Volumen liefern exakt die gleichen Werte, wenn man dieIntervalle unterhalb der 400 µs vernachlässigt. Dort weichen diese beiden Größen wegender oben aufgeführten Gründe von einander (zum Teil erheblich) ab. In Tabelle 4.2 sinddie Werte für eine Messung beispielhaft angegeben.

Intervalldauer Volumen Datenrate

10 µs 0,6914391 0,689612920 µs 0,638169 0,63773940 µs 0,6306932 0,630678280 µs 0,6441017 0,6440951

100 µs 0,650156 0,6501488200 µs 0,6753171 0,6753084400 µs 0,7034313 0,7034313800 µs 0,7363776 0,7363776

......

...

Tabelle 4.2: Hurstexponenten für Volumen und Datenrate vom 17.01.2005 um4:00 Uhr

4.3.2 Schätzen des Heavy-Tail-Verhaltens

Mit dem Verhältnis der Varianzen lässt sich das Heavy-Tail-Verhalten des gemessenenIP-Verkehrs ermitteln. Dies ist neben dem Hurst-Exponenten die zweite charakteristi-

41


sche Größe von selbstähnlichem Verkehr. In der Abbildung 4.2 sind die Werte für eineMessung sowohl mit als auch ohne den Verkehr vom AEI beispielhaft dargestellt. EineÜbersicht über alle berechneten Werte für α befindet sich im Anhang B.1.

0.2

0.4

0.6

0.8

1

1.2

1.4

1.6

1.8

2

2.2

10 100 1000 10000 100000 1e+006 1e+007

alph

a

Intervalldauer in Microsekunden

Mit AEIOhne AEI

Abbildung 4.2: Heavy-Tail-Verhalten bei verschiedenen Intervallen (17.01.05,15 Uhr)

Wir verwenden hier die günstigen Intervalle, die wir in Abschnitt 4.3.1 herausgearbeitethaben. Innerhalb dieser Intervalle nehmen wir das kleinste α als Parameter für die Mes-sung, da das Heavy-Tail-Verhalten dann stärker ins Gewicht fällt. Somit erhalten wir dieEntwicklung dieses Parameters über die drei Tage, an denen der IP-Verkehr aufgezeich-net wurde (Abbildung 4.3).

4.3.3 Schätzen des Hurst-Exponenten

Mit den Zeitreihen und dem Wissen über die günstigen Intervalle können wir nun mitden Algorithmen den Hurst-Exponenten für jede Messung und Intervallgröße bestim-men. Durch die im Abschnitt 4.3.2 ermittelten Parameter für das Heavy-Tail-Verhaltenkönnen wir auch abschätzen, wie genau der Hurst-Exponent berechnet wurde, da dieSchätzer umso genauer arbeiten, wenn α gegen 2 strebt. Wir beschränken uns dabei aufdie RS-Methode, die Methode der Absoluten Momente und die Methode der Varianz derRestglieder (Residuen). Diese drei Methoden wurden ausgewählt, um die ganze Breiteder Schätzgenauigkeit, wie sie im Abschnitt 3.4 festgestellt wurde, nutzen zu können. Eswird erwartet, wenn der gemessene Verkehr die selben Eigenschaften wie der generierteVerkehr aufweist, dass der RS-Schätzer eher ein zu kleines H liefert, der Schätzer fürdie Varianz der Residuen einen recht genauen Wert für den Hurst-Exponenten ermitteltund die Werte für die Absoluten Momente sich in der Mitte der beiden anderen Schätzerbefinden. Als Beispiel (Abbildung 4.4(a) und 4.4(b)) dient uns hier die Messung vom20.01.05 um 17:00 Uhr.

42


0

0.5

1

1.5

2

2.5

0 5 10 15 20 25

alph

a

Uhrzeit der Messung

Mit AEIOhne AEI

(a) Montag, 17.01.05

0

0.5

1

1.5

2

2.5

0 5 10 15 20 25

alph

a

Uhrzeit der Messung

Mit AEIOhne AEI

(b) Donnerstag, 20.01.05

0

0.5

1

1.5

2

2.5

0 5 10 15 20 25

alph

a

Uhrzeit der Messung

Mit AEIOhne AEI

(c) Freitag, 21.01.05

Abbildung 4.3: Das geschätzte Heavy-Tail-Verhalten an allen drei Tagen

Dieses Bild gibt alle geschätzten Hurst-Exponenten wieder. Aus dem vorherigen Ab-schnitt wissen wir aber, dass die Intervalle, die kleiner als 400 µs sind, vernachlässigtwerden können. Genauso können die größeren Intervalle vernachlässigt werden, da siezu wenige Werte enthalten. Die Grafik legt nahe, dass Intervalle, die größer als 100mssind, ungenaue Werte liefern, da die geschätzten Werte für den Hurstexponenten hierausbrechen. Die um diese Intervalle bereinigten Grafiken für unser Beispiel sind in denAbbildungen 4.4(c) und 4.4(d) dargestellt. Die Grafiken für alle Messungen befindensich im Abschnitt B.2.

In der Abbildung 4.5 ist eine Übersicht über die Hurst-Exponenten aller Messungen dar-gestellt. Diese Werte wurden ermittelt, indem das Maximum von den durch die Varianzder Restglieder ermittelten Hurst-Exponenten für das Volumen des IP-Verkehrs einerMessung bestimmt wurde. Sowohl die kurzen als auch die langen Intervalle, die wir be-reits ausgeschlossen haben, wurden dabei nicht berücksichtigt. Es wurden die Werte fürdas Volumen des IP-Verkehrs gewählt, da nur diese Zeitreihen den wirklich auftreten-den Verkehr genau genug wiedergeben. Die Anzahl der Pakete ist, wie bereits erwähnt,

43


0

0.2

0.4

0.6

0.8

1

1.2

10 100 1000 10000 100000 1e+006

Hur

stex

pone

nt


RS - VolumenRS - Pakete

Abs. Momente - VolumenAbs. Momente - Pakete

Var. d. Residuen - VolumenVar. d. Residuen - Pakete

(a) alle Intervalle mit AEI

0

0.2

0.4

0.6

0.8

1

1.2

10 100 1000 10000 100000 1e+006

Hur

stex

pone

nt





(b) alle Intervalle ohne AEI

0

0.2

0.4

0.6

0.8

1

1.2

1000 10000 100000

Hur

stex

pone

nt





(c) günstige Intervalle mit AEI

0

0.2

0.4

0.6

0.8

1

1.2

1000 10000 100000

Hur

stex

pone

nt





(d) günstige Intervalle ohne AEI

Abbildung 4.4: Beispiel für das Verhalten des Hurstexponenten (20.01.05 um17:00 Uhr)

wegen der nicht konstanten Größe der Pakete diesbezüglich ungenau. Da die Amplitu-de der Zeitreihen mit steigendem Hurst-Exponenten zunimmt, wenn auch nur minimalgegenüber dem Einfluss durch das Heavy-Tail-Verhalten, wurde jeweils das Maximumder Werte gewählt. Der Verlauf des Hurst-Exponenten, der durch die anderen beidenSchätzmethoden berechnet wurde, erfüllt ebenfalls in den meisten Fällen die Erwartung(siehe hierzu auch Abschnitt B.2).

4.3.4 Hurst-Exponenten mit Fraleigh-Diagrammen ermitteln

Eine weitere Möglichkeit, den Hurst-Exponenten von IP-Verkehr zu messen, bieten unsdie so genannten Fraleigh-Diagramme. In diesen Diagrammen wird die Varianz derDatenraten gegenüber den einzelnen Intervalldauern logarithmisch aufgetragen. DieseKurven weisen einen markanten Knick auf, wie in dem Beispiel in Abbildung 4.6 gutzu erkennen ist (hier bei einer Intervalldauer von 0,1s). Die Steigung der Kurve für

44


0.6

0.7

0.8

0.9

1

1.1

1.2

1.3

1.4

0 5 10 15 20 25

Hur

stex

pone

nt

Uhrzeit der Messung

mit AEI-Verkehrohne AEI-Verkehr

(a) Montag, 17.01.05

0.6

0.7

0.8

0.9

1

1.1

1.2

1.3

1.4

0 5 10 15 20 25

Hur

stex

pone

nt

Uhrzeit der Messung


(b) Donnerstag, 20.01.05

0.6

0.7

0.8

0.9

1

1.1

1.2

1.3

1.4

0 5 10 15 20 25

Hur

stex

pone

nt

Uhrzeit der Messung


(c) Freitag, 21.01.05

Abbildung 4.5: Entwicklung des Hurstexponenten über die einzelnen Tage

Intervalldauern, die größer sind als das Intervall mit der Knickstelle, entspricht demHurst-Exponenten für die jeweilige Messung des IP-Verkehrs. Da dieser Wert durchdie großen Intervalldauern festgelegt wird, beschreibt er die Langzeitabhängigkeit derMessdaten. Der Hurst-Exponent für die kleinen Intervalldauern (also links der Knick-stelle) beschreibt demzufolge die Kurzzeitabhängigkeit der Messdaten.

Wir wollen diese Methode hier nutzen, um unsere Ergebnisse aus dem vorherigen Ab-schnitt zu überprüfen. Um die jeweiligen Hurst-Exponenten zu schätzen, wird in diesemFall der Wavelet-Schätzer (Abschnitt 3.3.9) verwendet. In unserem Fall liegen jedoch zuwenige Werte in dem relevanten Bereich, so dass die Verwendung des Wavelet-Schätzersbzw. die Verwendung irgendeines Schätzers sehr ungenaue Werte liefern würde. Daherbeschränken wir uns hier auf eine grobe qualitative Überprüfung.

In der Tabelle 4.3 sind die Messungen eines jeden Tages gruppiert, die einen ähnli-chen Hurst-Exponenten (also eine ähnliche Steigung bei den Varianzen für große In-tervalle) aufweisen. In der jeweils linken Spalte sind die Messungen mit hohen Hurst-

45


1e+013

1e+014

1e+015

1e+016

1e+017

1e-005 0.0001 0.001 0.01 0.1 1 10

Var

ianz

der

Dat

enra

te


Abbildung 4.6: Beispiel zur Ermittlung des Hurstexponenten mit Fraleigh-Diagrammen

Montag Donnerstag

02 - 04 Uhr 00 - 01 Uhr 05 Uhr 01 - 08 Uhr 00 Uhr 09 Uhr06 Uhr 07 Uhr 08 Uhr 19 Uhr 10 - 13 Uhr 14 Uhr

19 - 21 Uhr 09 - 16 Uhr 17 Uhr 21 Uhr 15 - 18 Uhr 23 Uhr18 Uhr 20 Uhr

22 - 23 Uhr 22 Uhr

Freitag

00 - 01 Uhr 00 Uhr 10 Uhr06 Uhr 03 - 05 Uhr 14 - 15 Uhr08 Uhr 07 Uhr 18 Uhr11 Uhr 09 Uhr 20 - 22 Uhr23 Uhr 12 - 13 Uhr

16 - 17 Uhr19 Uhr

Tabelle 4.3: Mit Fraleigh-Diagrammen ermittelte Hurstexponenten

Exponenten, in der jeweils mittleren Spalte die mit mittlerem Hurst-Exponenten und inder jeweils rechten Spalte die mit kleinem Hurst-Exponenten zusammengefasst. In derAbbildung 4.7 sind die entsprechenden Fraleigh-Diagramme für Freitag (21.01.05 ohneAEI) gruppiert dargestellt. Es ist zu erkennen, dass innerhalb eines Diagramm die Stei-gung ähnlich ist, sich aber zwischen den Diagrammen durchaus unterscheidet. Natürlichgibt es auch Ausnahmen, die aber wegen der Ungenauigkeit (begründet durch die weni-gen Werte) nicht überraschend sind. Da wir eine nur grob qualitative und keine exaktequantitative Überprüfung durchführen, können wir diese Ausnahmen vernachlässigen.

46


1e+012

1e+013

1e+014

1e+015

1e+016

1e+017

1e-005 0.0001 0.001 0.01 0.1 1 10

Var

ianz

Intervalldauer in Sekunden

(a) hoher Hurst-Exponent

1e+012

1e+013

1e+014

1e+015

1e+016

1e+017

1e-005 0.0001 0.001 0.01 0.1 1 10

Var

ianz


(b) mittlerer Hurst-Exponent

1e+012

1e+013

1e+014

1e+015

1e+016

1e+017

1e-005 0.0001 0.001 0.01 0.1 1 10

Var

ianz


(c) niedriger Hurst-Exponent

Abbildung 4.7: Gruppierte Fraleigh-Diagramme vom Freitag (21.01.05)

47

5 Zusammenfassung und Ausblick

5.1 Ergebnis der Auswertung

Allgemein lässt sich feststellen, dass alle ermittelten Werte im Rahmen der Erwartungenliegen und plausibel sind. So weist der gemessene IP-Verkehr sowohl eine ausgepräg-te Langzeitabhängigkeit als auch ein leichtes Heavy-Tail-Verhalten auf. Gerade wegendieser Erwartung wurden die oben erläuterten Methoden verwendet, da die klassischeVerkehrstheorie hier nicht genau genug ist.

Die im Abschnitt 4.3.1 gesuchten günstigen Intervalle muss man in unserem Fall wahr-scheinlich noch ein wenig mehr einschränken. Bei Intervallen, die weniger als 10000Werte beinhalten, variieren die Ergebnisse stark untereinander, sodass man davon aus-gehen kann, dass der Schätzer nicht genügend Werte zur Verfügung hat. Dies gilt sowohlfür das Heavy-Tail-Verhalten als auch für die Langzeitabhängigkeit. Berücksichtigt mandies, so kann man die statistischen Ausreißer in den Abbildungen 4.3 und 4.5 minimie-ren.

Heavy-Tail-Verhalten: Das Heavy-Tail-Verhalten ist nicht besonders ausgeprägt, abervorhanden. Die ermittelten Werte für α sind im Tagesvergleich sehr ähnlich. Mit derneuen strikteren Einschränkung der Intervalle kann man das Heavy-Tail-Verhalten hierzwischen α = 1, 8 und α = 1, 9 ansiedeln.

Hurst-Parameter: Der Hurst-Exponent des gemessenen Verkehrs variiert zwar ein we-nig über den Tag, er liegt aber in etwa zwischen H = 0, 8 und H = 0, 9. Die Fraleigh-Diagramme haben zusätzlich die geschätzten Werte für den Hurst-Exponenten qualitativbestätigt. Auch hier zeigt der Tagesvergleich durchaus einen ähnlichen Verlauf.

5.2 Vergleich der Ergebnisse mit dem realen IP-Verkehr

Nachdem alle Parameter ermittelt wurden, soll der reale Verkehr den Zeitreihen, die mitHilfe der ermittelten Parameter erstellt wurden, gegenübergestellt werden. In der Ab-bildung 5.1 befindet sich oben ((a) und (b)) der gemessene IP-Verkehr (20.01.05, 17:00

48


Uhr mit der Intervalldauer 20 µs). In der Mitte ((c) und (d)) ist eine FARIMA-Zeitreihemit den Parametern H = 0, 88, α = 1, 9 und Pareto-verteilten Zuwächsen dargestellt.Auf den ersten Blick sehen sich die Daten nicht sonderlich ähnlich. Wenn man aber denVerkehr vom AEI aus den gemessenen Daten heraus rechnet bzw. einen konstanten Da-tenstrom dem generierten Verkehr hinzu rechnet, sind die beiden Zeitreihen durchausähnlich. Somit sind diese FARIMA-Reihen, die „normalen“ IP-Verkehr sehr gut simu-lieren können, nur bedingt geeignet, um Sonderfälle zu modellieren. In unserem Fallbieten sich FARIMA-Reihen mit Gauss-verteilten Zuwächsen an (unten in der Abbil-dung). Nachdem die generierte Zeitreihe skaliert (Faktor 10) und nach oben verschobenwurde (um 90), ähnelt sie der gemessenen Reihe.

5.3 Ausblick

Nachdem wir gesehen haben, dass sich die Methoden auf realen IP-Verkehr anwendenlassen, muss man für weitere Analysen in diesem Bereich noch ein paar Bedingungennennen, damit die Ergebnisse noch verlässlicher werden.

Für zukünftige Aufgaben wird es sinnvoller sein, nicht viele kurze Messungen durch-zuführen, sondern den IP-Verkehr über einen längeren Zeitraum aufzuzeichnen. Wennman trotzdem unterschiedliche Tageszeiten vergleichen möchte, sollte man sich auf we-nige charakteristische Zeiten beschränken (z.B. großer und geringer Datenstrom). Willman die Fraleigh-Diagramme auch quantitativ nutzen, so muss der IP-Verkehr zwin-gend über einen längeren Zeitraum beobachtet werden, damit genügend Werte für diegroßen Intervalle zur Berechnung des Hurst-Exponenten vorliegen. Wenn man bedenkt,dass die Langzeitabhängigkeit zum erstan Mal bei einer Messung bemerkt wurde, dieüber vier Jahre gedauert hat, erscheinen die obigen Anforderungen an die Analyse vonIP-Verkehr durchaus schlüssig.

49


20

40

60

80

100

120

140

160

180

200

0 2000 4000 6000 8000 10000 12000 14000

Da

ten

rate

[M

Bp

s]

Intervall

(a) IP-Verkehr

20

40

60

80

100

120

140

160

180

200

8000 8500 9000 9500 10000

Da

ten

rate

[M

Bp

s]Intervall

(b) IP-Verkehr

20

30

40

50

60

70

80

90

100

110

0 2000 4000 6000 8000 10000 12000 14000

Da

ten

rate

[M

Bp

s]

Intervall

(c) FARIMA (Pareto)

20

40

60

80

100

120

140

160

180

200

8000 8500 9000 9500 10000

Da

ten

rate

[M

Bp

s]

Intervall

(d) FARIMA (Pareto)

20

40

60

80

100

120

140

160

180

200

0 2000 4000 6000 8000 10000 12000 14000

Da

ten

rate

[M

Bp

s]

Intervall

(e) FARIMA (Gauss)

20

40

60

80

100

120

140

160

180

200

8000 8500 9000 9500 10000

Da

ten

rate

[M

Bp

s]

Intervall

(f) FARIMA (Gauss)

Abbildung 5.1: Vergleich von IP-Verkehr und generierten Zeitreihen

50

A Detaillierte Gra�ken zur

Genauigkeit der Schätzer

Hier werden ausführlich die Grafiken gezeigt, die im Kapitel 3.4 zur Bewertung derSchätzer geführt haben. Zunächst werden im Abschnitt A.1 die Ergebnisse der Schätzerfür die generierten Zeitreihen grafisch dargestellt. Dann werden im Abschnitt A.2 Dia-gramme der generierten Zeitreihen denen beispielhaft gegenübergestellt, die mit demgeschätzten Hurst-Exponenten erstellt wurden, um zu zeigen, wie genau die Vorhersagebasierend auf den Schätzern ist.

A.1 Ergebnisse der Schätzer für die generiertenZeitreihen

Die folgenden Grafiken zeigen die geschätzten Werte für den Hurstexponenten jeweilsfür FARIMA-Reihen mit α = 1, 5, α = 2, 0 und FGN-Reihen mit α = 2, 0. Die Zeitrei-hen weisen eine Länge von 100.000 Einträgen und eine Standardabweichung von 1 auf.

0.4

0.5

0.6

0.7

0.8

0.9

1

1 2 3 4 5 6 7 8 9 10

(a) FARIMA mit α = 2, 0

0.4

0.5

0.6

0.7

0.8

0.9

1

1 2 3 4 5 6 7 8 9 10

(b) FARIMA mit α = 1, 5

0.4

0.5

0.6

0.7

0.8

0.9

1

1 2 3 4 5 6 7 8 9 10

(c) FGN mit α = 2, 0

Abbildung A.1: Ergebnisse für die Absoluten Momente

51

A Detaillierte Gra�ken zur Genauigkeit der Schätzer

0.4

0.5

0.6

0.7

0.8

0.9

1

1 2 3 4 5 6 7 8 9 10


0.4

0.5

0.6

0.7

0.8

0.9

1

1 2 3 4 5 6 7 8 9 10


0.4

0.5

0.6

0.7

0.8

0.9

1

1 2 3 4 5 6 7 8 9 10


Abbildung A.2: Ergebnisse für die Varianzmethode

0.4

0.5

0.6

0.7

0.8

0.9

1

1 2 3 4 5 6 7 8 9 10


0.4

0.5

0.6

0.7

0.8

0.9

1

1 2 3 4 5 6 7 8 9 10


0.4

0.5

0.6

0.7

0.8

0.9

1

1 2 3 4 5 6 7 8 9 10


Abbildung A.3: Ergebnisse für die R/S-Methode

0.4

0.5

0.6

0.7

0.8

0.9

1

1 2 3 4 5 6 7 8 9 10


0.4

0.5

0.6

0.7

0.8

0.9

1

1 2 3 4 5 6 7 8 9 10


0.4

0.5

0.6

0.7

0.8

0.9

1

1 2 3 4 5 6 7 8 9 10


Abbildung A.4: Ergebnisse für das Periodogramm

52


0.4

0.5

0.6

0.7

0.8

0.9

1

1 2 3 4 5 6 7 8 9 10


0.4

0.5

0.6

0.7

0.8

0.9

1

1 2 3 4 5 6 7 8 9 10


0.4

0.5

0.6

0.7

0.8

0.9

1

1 2 3 4 5 6 7 8 9 10


Abbildung A.5: Ergebnisse für das modi�zierte Periodogramm

0.4

0.5

0.6

0.7

0.8

0.9

1

1 2 3 4 5 6 7 8 9 10


0.4

0.5

0.6

0.7

0.8

0.9

1

1 2 3 4 5 6 7 8 9 10


0.4

0.5

0.6

0.7

0.8

0.9

1

1 2 3 4 5 6 7 8 9 10


Abbildung A.6: Ergebnisse für das kumulative Periodogramm

0.4

0.5

0.6

0.7

0.8

0.9

1

1 2 3 4 5 6 7 8 9 10


0.4

0.5

0.6

0.7

0.8

0.9

1

1 2 3 4 5 6 7 8 9 10


0.4

0.5

0.6

0.7

0.8

0.9

1

1 2 3 4 5 6 7 8 9 10


Abbildung A.7: Ergebnisse für die Varianz der Restglieder

53


0.4

0.5

0.6

0.7

0.8

0.9

1

1 2 3 4 5 6 7 8 9 10


0.4

0.5

0.6

0.7

0.8

0.9

1

1 2 3 4 5 6 7 8 9 10


0.4

0.5

0.6

0.7

0.8

0.9

1

1 2 3 4 5 6 7 8 9 10


Abbildung A.8: Ergebnisse für den Durchschnitt der Varianz der Restglieder

1.4

1.5

1.6

1.7

1.8

1.9

2

2.1

1 2 3 4 5 6 7 8 9 10


1.4

1.5

1.6

1.7

1.8

1.9

2

2.1

1 2 3 4 5 6 7 8 9 10


1.4

1.5

1.6

1.7

1.8

1.9

2

2.1

1 2 3 4 5 6 7 8 9 10


Abbildung A.9: Ergebnisse für das Verhältnis der Varianz

0.4

0.5

0.6

0.7

0.8

0.9

1

1 2 3 4 5 6 7 8 9 10


0.4

0.5

0.6

0.7

0.8

0.9

1

1 2 3 4 5 6 7 8 9 10


0.4

0.5

0.6

0.7

0.8

0.9

1

1 2 3 4 5 6 7 8 9 10


Abbildung A.10: Ergebnisse für den Whittle-Schätzer

54


0.4

0.5

0.6

0.7

0.8

0.9

1

1 2 3 4 5 6 7 8 9 10


0.4

0.5

0.6

0.7

0.8

0.9

1

1 2 3 4 5 6 7 8 9 10


0.4

0.5

0.6

0.7

0.8

0.9

1

1 2 3 4 5 6 7 8 9 10


Abbildung A.11: Ergebnisse für den lokalen Whittle-Schätzer

0.4

0.5

0.6

0.7

0.8

0.9

1

1 2 3 4 5 6 7 8 9 10


0.4

0.5

0.6

0.7

0.8

0.9

1

1 2 3 4 5 6 7 8 9 10


0.4

0.5

0.6

0.7

0.8

0.9

1

1 2 3 4 5 6 7 8 9 10


Abbildung A.12: Ergebnisse für die Wavelet-Analyse

A.2 Ähnlichkeit der ursprünglichen mit denvorhergesagten Zeitreihen

Es wurden mit den geschätzten Werten für den Hurst-Exponenten neue Zeitreihen gene-riert. Einige von ihnen werden hier den ursprünglichen Zeitreihen, von denen der Hurst-Exponent geschätzt wurde, gegenübergestellt. Hieran kann man erkennen, wie gut sichsolche Zeitreihen basierend auf den geschätzten Parametern vorhersagen lassen. Ge-zeigt wird hier lediglich eine Auswahl mit größeren Abweichungen in der Vorhersage.Zur genaueren Betrachtung wird an Stellen mit geringer Amplitude eine Vergrößerunggegeben.

A.2.1 FARIMA-Reihen mit α = 2, 0

Anhand der Grafiken in Abbildung A.13 kann man sehen, dass die vorhergesagte Zeitrei-he sich weder in ihrer Gestalt noch in der Amplitude von der ursprünglichen Zeitreihe

55


unterscheidet. Dies gilt sowohl für kleine als auch größere Abweichungen des Hurst-Exponenten.

-10

-8

-6

-4

-2

0

2

4

6

8

0 20000 40000 60000 80000 100000

(a) H = 0, 967 (0-100.000)

-8

-6

-4

-2

0

2

4

6

0 20000 40000 60000 80000 100000

(b) H = 0, 8869 (0-100.000)

-6

-4

-2

0

2

4

6

8

30000 32000 34000 36000 38000 40000

(c) H = 0, 967 (30.000-40.000)

-4

-3

-2

-1

0

1

2

3

4

5

6

30000 32000 34000 36000 38000 40000

(d) H = 0, 8869 (30.000-40.000)

-2

-1

0

1

2

3

4

5

6

35000 35200 35400 35600 35800 36000

(e) H = 0, 967 (35.000-36.000)

-3

-2

-1

0

1

2

3

4

5

35000 35200 35400 35600 35800 36000

(f) H = 0, 8869 (35.000-36.000)

Abbildung A.13: Vorhersage für FARIMA-Reihen mit α = 2, 0

A.2.2 FARIMA-Reihen mit α = 1, 5

An diesen Beispielen (Abbildung A.14) ist zu erkennen, dass sich auch hier eine Ände-rung des Hurst-Exponenten nicht maßgeblich auf das Erscheinungsbild der Vorhersageauswirkt, solange man von einem konstanten Wert für α ausgehen kann. Da man α al-

56


lerdings für eine unbekannte Zeitreihe auch schätzen muss, liegen hier bei nur kleinenAbweichungen größere Fehler in der Amplitude vor.

-600

-400

-200

0

200

400

600

0 20000 40000 60000 80000 100000

(a) H = 0, 8 (0-100.000)

-600

-400

-200

0

200

400

600

0 20000 40000 60000 80000 100000

(b) H = 0, 6591 (0-100.000)

-60

-40

-20

0

20

40

60

80

100

30000 32000 34000 36000 38000 40000

(c) H = 0, 8 (30.000-40.000)

-60

-40

-20

0

20

40

60

80

100

30000 32000 34000 36000 38000 40000

(d) H = 0, 6591 (30.000-40.000)

-15

-10

-5

0

5

10

15

20

35000 35200 35400 35600 35800 36000

(e) H = 0, 8 (35.000-36.000)

-15

-10

-5

0

5

10

15

20

35000 35200 35400 35600 35800 36000

(f) H = 0, 6591 (35.000-36.000)

Abbildung A.14: Vorhersage für FARIMA-Reihen mit α = 1, 5

A.2.3 FGN-Reihen mit α = 2, 0

Auch bei den FGN-Reihen machen sich größere Abweichungen beim Hurst-Exponentennur kaum bemerkbar. Die hier verglichenen Reihen weichen in Gestalt und Amplitudenur wenig voneinander ab (siehe Abbildung A.15).

57


-4

-3

-2

-1

0

1

2

3

4

5

0 20000 40000 60000 80000 100000

(a) H = 0, 9 (0-100.000)

-5

-4

-3

-2

-1

0

1

2

3

4

5

0 20000 40000 60000 80000 100000

(b) H = 0, 7164 (0-100.000)

-4

-3

-2

-1

0

1

2

3

4

30000 32000 34000 36000 38000 40000

(c) H = 0, 9 (30.000-40.000)

-4

-3

-2

-1

0

1

2

3

4

30000 32000 34000 36000 38000 40000

(d) H = 0, 7164 (30.000-40.000)

-3

-2

-1

0

1

2

3

33000 33200 33400 33600 33800 34000

(e) H = 0, 9 (33.000-34.000)

-3

-2

-1

0

1

2

3

33000 33200 33400 33600 33800 34000

(f) H = 0, 7164 (33.000-34.000)

Abbildung A.15: Vorhersage für FGN-Reihen

58

B Detaillierte Gra�ken zur

Auswertung

B.1 Übersicht über die geschätztenHeavy-Tail-Parameter

In den Abbildungen B.1 bis B.3 sind die mit dem Verhältnis der Varianz der Residuenermittelten Parameter des Heavy-Tail-Verhaltens für die Datenraten dargestellt.

B.2 Übersicht über die geschätzten Hurst-Exponenten

In den Abbildungen B.4 bis B.6 sind die mit der Varianz der Residuen ermittelten Hurst-Parameter für die Datenraten dargestellt.

B.3 Fraleigh-Diagramme zur Ermittlung desHurst-Exponenten

In den Abbildungen B.7 bis B.9 sind die Fraleigh-Diagramme für sämtliche Messungendargestellt.

59

B Detaillierte Gra�ken zur Auswertung

0

0.5

1

1.5

2

2.5

3

3.5

10 100 1000 10000 100000 1e+006 1e+007

alph

a


(a) Mit AEI

0

0.5

1

1.5

2

2.5

3

3.5

10 100 1000 10000 100000 1e+006 1e+007

alph

a


(b) Ohne AEI

Abbildung B.1: Heavy-Tail-Parameter α am Montag 17.01.05

0

0.5

1

1.5

2

2.5

3

3.5

10 100 1000 10000 100000 1e+006 1e+007

alph

a


(a) Mit AEI

0

0.5

1

1.5

2

2.5

3

3.5

10 100 1000 10000 100000 1e+006 1e+007

alph

a


(b) Ohne AEI

Abbildung B.2: Heavy-Tail-Parameter α am Donnerstag 20.01.05

0

0.5

1

1.5

2

2.5

3

3.5

10 100 1000 10000 100000 1e+006 1e+007

alph

a


(a) Mit AEI

0

0.5

1

1.5

2

2.5

3

3.5

10 100 1000 10000 100000 1e+006 1e+007

alph

a


(b) Ohne AEI

Abbildung B.3: Heavy-Tail-Parameter α am Freitag 21.01.05

60


0

0.5

1

1.5

2

2.5

10 100 1000 10000 100000 1e+006 1e+007

Hur

stex

pone

nt


(a) Mit AEI

0

0.5

1

1.5

2

2.5

10 100 1000 10000 100000 1e+006 1e+007

Hur

stex

pone

nt


(b) Ohne AEI

Abbildung B.4: Hurst-Exponent H am Montag 17.01.05

0

0.5

1

1.5

2

2.5

10 100 1000 10000 100000 1e+006 1e+007

Hur

stex

pone

nt


(a) Mit AEI

0

0.5

1

1.5

2

2.5

10 100 1000 10000 100000 1e+006 1e+007

Hur

stex

pone

nt


(b) Ohne AEI

Abbildung B.5: Hurst-Exponent H am Donnerstag 20.01.05

0

0.5

1

1.5

2

2.5

10 100 1000 10000 100000 1e+006 1e+007

Hur

stex

pone

nt


(a) Mit AEI

0

0.5

1

1.5

2

2.5

10 100 1000 10000 100000 1e+006 1e+007

Hur

stex

pone

nt


(b) Ohne AEI

Abbildung B.6: Hurst-Exponent H am Freitag 21.01.05

61


1e+012

1e+013

1e+014

1e+015

1e+016

1e+017

10 100 1000 10000 100000 1e+006 1e+007

Var

ianz


(a) Mit AEI

1e+012

1e+013

1e+014

1e+015

1e+016

1e+017

10 100 1000 10000 100000 1e+006 1e+007

Var

ianz


(b) Ohne AEI

Abbildung B.7: Fraleigh-Diagramme vom Montag 17.01.05

1e+012

1e+013

1e+014

1e+015

1e+016

1e+017

10 100 1000 10000 100000 1e+006 1e+007

Var

ianz


(a) Mit AEI

1e+012

1e+013

1e+014

1e+015

1e+016

1e+017

10 100 1000 10000 100000 1e+006 1e+007

Var

ianz


(b) Ohne AEI

Abbildung B.8: Fraleigh-Diagramme vom Donnerstag 20.01.05

1e+012

1e+013

1e+014

1e+015

1e+016

1e+017

10 100 1000 10000 100000 1e+006 1e+007

Var

ianz


(a) Mit AEI

1e+012

1e+013

1e+014

1e+015

1e+016

1e+017

10 100 1000 10000 100000 1e+006 1e+007

Var

ianz


(b) Ohne AEI

Abbildung B.9: Fraleigh-Diagramme vom Freitag 21.01.05

62

C Anpassen der Algorithmen

C.1 Anpassen der S-PLUS Algorithmen für GNU R

Bei der Zuweisung von Namen an Funktionen oder Variablen an Objekte ist in S-PLUSsowohl ein Unterstrich als auch ein Pfeil zulässig. In GNU R funktioniert die Zuweisungnur mit einem Pfeil, dieser ist bei beiden Sprachen in beide Richtungen möglich.

#### S−PLUSname_ f u n c t i o n ( arg1 , arg2 , . . . )xyz _ 12345

#### GNU Rname <− f u n c t i o n ( arg1 , arg2 , . . . )xyz <− 12345

Die Funktion ltsreg() wird unterschiedlich geschrieben. Die Argumente sind in bei-den Fällen gleich. Generell unterscheiden beide Sprachen zwischen Groß- und Klein-schreibung.

#### S−PLUSl t s r e g ( )

#### GNU Rl t s R e g ( )

Die Funktion rstab() in S-PLUS wird durch rstable() in GNU R ersetzt. Das Ar-gument index entspricht dabei dem Argument tail. Für tail=1 wird mit der Cauchy-Verteilung und für tail=2 wird mit der Normalverteilung gerechnet.

#### S−PLUSr s t a b ( n , index , skewness =0)

63


#### GNU Rr s t a b l e ( n =1 , l o c =0 , d i s p =1 / s q r t ( 2 ) ,

skew =0 , t a i l =2 , eps =1 .0 e−6 )

Die Funktion nlminb() wird in GNU R durch optim() ersetzt. Dabei entspricht dasArgument start dem Argument par und objective entspricht fn. Zusätzlich gibtes in optim() das Argument method=�L-BFGS-B�, damit diese Funktion das gleicheErgebnis wie nlminb() liefert.

#### S−PLUSnlminb ( s t a r t = p , o b j e c t i v e = minfunc ,

n1 = n , m = m, l 1 = l , p e r i = pgram ,lower = c ( − I n f , 0 ) , upper = c ( I n f , 1 ) )$ p a r a m e t e r s

#### GNU Roptim ( par = p , fn = minfunc , method="L−BFGS−B" ,

n1 = n , m = m, l 1 = l , p e r i = pgram ,lower = c ( − I n f , 0 ) , upper = c ( I n f , 1 ) )$par

Weitere Anpassungen müssen auch noch in den Funktionen assign() und remove()

gemacht werden. Das Argument frame wird durch pos und das Argument w durchwhere ersetzt. Dabei darf dem Argument pos keine Null zugewiesen werden. Anstelleder Null funktionieren die Algorithmen mit einer Eins.

#### S−PLUSa s s i g n ( " bBb " , r e s u l t , frame = 0)remove ( " bBb " , frame = 0)a s s i g n ( " ype r " , p e r ( y ) [ 2 : ( nha l fm + 1 ) ] , w = 1)remove ( " ype r " , frame = 1)

#### GNU Ra s s i g n ( " bBb " , r e s u l t , pos = 1)remove ( " bBb " , pos = 1)a s s i g n ( " ype r " , p e r ( y ) [ 2 : ( nha l fm + 1 ) ] , where = 1)remove ( " ype r " , pos = 1)

C.2 Einbinden von C-Methoden

In den hier verwendeten Algorithmen werden recht häufig Methoden eingebunden, diein C geschrieben wurden. Um diese in die R-Algorithmen einbinden zu können, sindweitere Anpassungen nötig.

64


#### S−PLUSi f ( ! i s . l o a d e d (C . symbol ( " d u r b i n _FGN. o " ) ) )

dyn . load ( " Pfad / d u r b i n _FGN. o " )normal <− rnorm ( num + 1 , 0 , 1 )o u t<−rep ( 0 , num+1).C( " durbinFGN " ,

n = as . i n t e g e r ( num ) ,h = as . double ( h ) ,s igma = as . double ( s igma ) ,normal = as . double ( normal ) ,o u t p u t = as . double ( o u t ) ) $ o u t [ 2 : ( num + 1 ) ]

#### GNU Ri f ( ! i s . l o a d e d ( symbol .C( " d u r b i n _FGN" ) ) )

dyn . load ( " Pfad / d u r b i n _FGN. so " )normal <− rnorm ( num + 1 , 0 , 1 )o u t<−rep ( 0 , num+1).C( " durbinFGN " ,

n = as . i n t e g e r ( num ) ,h = as . double ( h ) ,s igma = as . double ( s igma ) ,normal = as . double ( normal ) ,o u t p u t = as . double ( o u t ) ) $ o u t [ 2 : ( num + 1 ) ]

Die Objekt-Dateien, die hier eingebunden werden, lassen sich komfortabel mit

R CMD SHLIB C Q u e l l t e x t . c

aus dem C-Quellcode unter Linux oder Unix erstellen. Um den C-Quellcode mit R unterWindows nutzen zu können, muss man sich mit einem entsprechenden Compiler eine.dll-Datei erzeugen und diese in R einbinden. Weitere Hinweise hierzu befinden sichin den Manuals zu R.

C.3 Besonderheiten beim Generieren der Zeitreihen mitFARIMA und FGN

In den Methoden zur Erstellung der Zeitreihen wird innerhalb der Funktionen rnorm()

und rstable() ein Zufallszahlengenerator verwendet, um die Verteilungsfunktionen zumodellieren. Damit die Zeitreihen reproduzierbar werden, muss dem Zufallszahlenge-nerator ein definierter Startvektor übergeben werden. Dieser 127-dimensionale Vektorheißt in R Random.seed. Es genügt allerdings, diesem Vektor mit

65


s e t . s e ed ( i n t )

eine Integerzahl int zu übergeben. Für die hier generierten Zeitreihen wurden die Zah-len aus Tabelle C.1 verwendet, wobei die Zeitreihen entsprechend nummeriert wurden.

1 2 3 4 5 6 7 8 9 10

124 316 478 521 649 663 700 833 901 958

Tabelle C.1: Initialisierung des Startvektors

66

Literaturverzeichnis

[AFT01+] P. Abry, P. Flandrin, M.S. Taqqu, D. Veitch. Self-Similarity and Long-RangeDependence through the Wavelet Lens, In: Long-Range Dependence: Theo-ry and Application (eds: P. Doukhan, G. Oppenheim and M. Taqqu), Birk-häuser New York, S. 527-556 (2001)

[AbVe98] P. Abry, D. Veitch. Wavelet Analysis for Long Range Dependent Traffic,IEEE Transactions on Information Theory 44(1), S. 2-15 (1998)

[BrDa91] P.J. Brockwell, R.A. Davis. Time Series: Theory and Methods, Springer-Verlag, New York, 2nd Edition (1991)

[Dfn05] Gigabit-Wissenschaftsnetz (G-WiN), aufhttp://www.dfn.de/content/gigabitwissenschafts/ (2005)

[EKM98] P. Embrechts, C. Klüppelberg, T. Mikosch. Modelling Extremal Events,Springer-Verlag, Berlin-New York (1998)

[Fla92] P. Flandrin. Wavelet analysis and synthesis of fractional Brownian motion,IEEE Transactions on Information Theory 38, S. 910-917 (1992)

[FTD03] C. Fraleigh, F. Tobagi, and C. Diot. Provisioning IP Backbone Networksto Support Latency Sensitive Traffic, IEEE Infocom, San Francisco (März2003)

[GäSt80] Gässler, Stute. Wahrscheinlichkeitstheorie, Springer-Verlag, Berlin-Heidelberg (1980)

[GrSc05] C. Grimm, G. Schlüchtermann. IP-Verkehrstheorie, Hüthig (voraussichtlich2005)

[HeYa97] C.C. Heyde, Y. Yang. On defining long-range dependence, Appl. Prob. 34,S. 939-944 (1997)

67


[Hig88] T. Higuchi. Approach to an irregular time series on the basis of the fractaltheory, Physica D., 31, S. 277-283 (1988)

[Hur51] H.E. Hurst. Long-term capacity of reservoirs, Trans. Soc. Civil. Eng. 116,S. 770-799 (1951)

[KlMi96a] C. Klüppelberg, T. Mikosch. The integrated periodogram for stable proces-ses, The Annals of Statistics 24,2, S. 1855-1879 (1996)

[KlMi96b] C. Klüppelberg, T. Mikosch. Self-normalized and randomly centered spec-tral estimates, In: P.M. Robinson und M. Rosenblatt (eds.), Athens Confe-rence on Apllied Probability and Time Series Analysis. Vol.II: Time SeriesAnalysis in Memory of E.J. Hannan, New York Springer-Verlag. LectureNotes in Statistics 115, S. 259-271 (1996)

[KoMi00] P. Kokoszka, T. Mikosch. The integrated periodogram for long-memoryprocesses with finite or infinite variance, Stochastic Processes and their Ap-plication 86, S. 49-80 (2000)

[Lam62] J.W. Lamperti. Semi-stable stochastic processes, Trans. Amer. Math. Soc.104, S. 62-78 (1962)

[PBS94+] C.K. Peng, S.V. Buldyrev, M. Simons, H.E. Stanley und A.L. Goldberger.Mosaic organization of DNA nucleotides, Physical Review E 49, S. 1685-1689 (1994)

[Rob95] P.M. Robinson. Gaussian semiparametric estimation of long range depen-dence, The Annals of Statistics 23, S. 1630-1661 (1995)

[SaTa92] G. Samorodnitski, M.S. Taqqu. Linear models with long-range dependenceabd finite or infinite variance, in D. Brillinger, P. Caines, J. Geweke, E.Parzen, M. Rosenblatt and M.S. Taqqu (Editoren) New Directions in TimeSeries Analysis, Part II, Seite 325-340, New York (1992). IMA Volumes inMathematics and its Applications, Volume 46, Springer-Verlag

[SaTa94] G. Samorodnitski, M.S. Taqqu. Stable Non-Gaussian Processes: Stocha-stic Models with Infinite Variance, Chapman and Hall, New York, London(1994)

[Taq05] M.S. Taqqu. Statistical methods for long-range dependence, aufhttp://math.bu.edu/people/murad/ (2005)

68


[TTW95] M.S. Taqqu, V. Teverovsky, W. Willinger. Estimators for long-range depen-dence: An empirical study, Fractals, 3(4), S. 785-798 (1995)

69

Documents

Analyse von Datenﬂüssen in Netzwerken mit Me- thoden aus ... · Legendre, Adrien-Marie (1752-1833) FranzösischerMathematiker.Erbeschäftigtesich mit der Zahlentheorie, der Geometrie