204 Pages
English
Gain access to the library to view online
Learn more

Traffic-adaptive routing [Elektronische Ressource] / Nils Kammenhuber

Gain access to the library to view online
Learn more
204 Pages
English

Informations

Published by
Published 01 January 2008
Reads 31
Language English
Document size 12 MB

Exrait

Lehrstuhl für Netzwerkarchitekturen
Fakultät für Informatik
Technische Universität München
Traffic-Adaptive Routing
Nils Kammenhuber
Vollständiger Abdruck der von der Fakultät für Informatik
der Technischen Universität München
zur Erlangung des akademischen Grades eines
Doktors der Naturwissenschaften (Dr. rer. nat.)
genehmigten Dissertation.
Vorsitzender: Univ.-Prof. Dr. Chr. Scheideler
Prüfer der Dissertation: 1. Univ.-Prof. A. Feldmann, Ph. D., Technische Universität Berlin
2. Univ.-Prof. Dr. Th. Fuhrmann
3. Prof. B. M. Maggs, Ph. D., Carnegie Mellon University
(schriftliche Beurteilung)
Die Dissertation wurde am 19.12.2007 bei der Technischen Universität München eingereicht
und durch die Fakultät für Informatik am 19.06.2008 angenommen.2Abstract
Traffic in the Internet is known to change over time and exhibit volatile behaviour. One
major challenge in communication networks is the problem of handling these traffic
demands that are bursty and hard to predict. Current traffic engineering techniques
operate on time scale of several hours, which is too slow to react to quick phenomena
such as flash crowds or BGP reroutes. The obvious solution, load sensitive routing, is
frowned upon, since routing decisions at short time scales can lead to oscillations. This
has prevented load sensitive routing from being deployed since the early experiences
in Arpanet, the predecessor of today’s Internet.
However, recent theoretical results have shown that a re-routing policy based on
game theory provably avoids such oscillation and, in addition, can be shown to con-
verge quickly. In the main part of our work, we describe REPLEX, a distributed dy-
namic traffic engineering algorithm based on this policy. Exploiting the fact that most
underlying routing protocols support multiple equal-cost routes to a destination, it dy-
namically changes the proportion of traffic that is routed along each path. These traffic
proportions are carefully adapted utilising information from periodic measurements
and information exchanged between the routers. The required signalling overhead is
small. Moreover, it can, under some circumstances, be avoided altogether.
We evaluate our algorithm in extensive simulations employing traffic loads that mimic
realistic bursty TCP traffic whose characteristics are consistent with self-similarity. The
simulations show quick convergence and no oscillations with reasonably chosen pa-
rameters. Comparative simulations on realistic network topologies show that REPLEX
achieves performance improvements that are as good, if not better than those attained
with traditional traffic engineering methods.
Since REPLEX as well as many other applications rely on collecting traffic statistics,
we furthermore describe an algorithm that enables a router to perform this task in an
efficient way. Our Expand-and-Collapse algorithm (EaC) is a heuristic that is partic-
ularly aimed at platforms like network processors: Under severe memory constraints,
it finds the most popular paths in search trees such as those are used in most packet
classification algorithms. EaC allows to efficiently find the largest traffic contributors.
In addition, can be applied in a wide number of other contexts as well, due to its gener-
icity. Our theoretical and simulation-based analyses show good performance.
A sound understanding for the behaviour of the workload traffic is a vital factor
in the construction of load-adaptive dynamic routing and traffic engineering systems.
We therefore also describe two methodologies for studying the characteristics of Web
traffic, which is still a major part of today’s Internet traffic. Our contributions involve
on the one hand a methodology for estimating Web traffic demands on a global scale,
3through the combination of local measurements and log files from a content distribu-
tion network. The traffic matrices we derived are among the largest of their kind and
reveal changes over time that grow larger as the time elapses. The other method that we
present is a model-based analysis of Web search traffic and the Web traffic imposed by
subsequent clicks that follow the search result. Our analysis confirms previous findings
and reveals new interesting aspects of Web search related user behaviour.
4Zusammenfassung
Es ist allgemein bekannt, dass Datenverkehr im Internet zeitlichen Änderungen und
stark schwankendem Verhalten unterworfen ist. Eine der vordringlichsten Herausfor-
derungen beim Betrieb von Datennetzwerken stellt daher der Umgang mit stoßartig
wechselndem und kaum voraussagbaren Verkehrsaufkommen dar. Heutige Methoden
des Traffic Engineering (deutsch: Verkehrslenkung) reagieren auf Verkehrsänderungen
binnen einiger Stunden, was zum Gegensteuern bei schnell auftretenden Phänomenen
wie Flash Crowds oder Instabilitäten von BGP nicht ausreichend ist. Die naheliegende
Lösung, das Routing lastabhängig zu gestalten, ist jedoch allgemein verpönt: Interagie-
rende Routingentscheidungen auf kurzen Zeitskalen können zu Oszillationen führen
– ein Effekt, der bereits im Arpanet, dem Vorgänger des heutigen Internets, beobach-
tet wurde, und aufgrunddessen der Einsatz lastabhängigen Routings heute gemieden
wird.
Kürzlich erschienene theoretische Arbeiten haben jedoch eine spieltheoretische Re-
Routing-Strategie aufgezeigt, die solche Oszillationen beweisbar vermeidet, und von
der sich darüberhinaus zeigen lässt, dass sie schnell konvergiert. Im Hauptteil unserer
Arbeit beschreiben wir REPLEX, einen auf dieser Strategie basierenden verteilten dyna-
mischen Traffic-Engineering-Algorithmus. Durch Ausnutzen der Tatsache, dass viele
Routingprotokolle zu einem Ziel mehrere gleichberechtigte Routen mit äquivalenten
Kosten zulassen (englisch: multipath equal-cost routes), passt REPLEX die jeweiligen
Anteile der einzelnen Routen am Gesamtaufkommen eines Datenstroms zu einem Ziel
dynamisch an. Die entsprechenden Verhältnisse werden permanent auf Basis periodi-
scher Messungen sowie zwischen den Routern ausgetauschten Informationen ange-
passt. Der hierfür erforderliche zusätzliche Informationsaufwand ist klein und kann
darüberhinaus unter bestimmten Bedingungen sogar vollständig entfallen.
Wir evaluieren unseren Algorithmus umfassend mit Hilfe von Netzwerksimulatio-
nen. Dabei verwenden wir Prüflasten, die realistischen und stark schwankenden TCP-
Verkehr simulieren, und der konsistent mit selbstähnlichem Verhalten ist. Unsere Si-
mulationen zeigen schnelle Konvergenz und das Ausbleiben von Oszillationen bei Ver-
wendung vernünftiger Parameter für unseren Algorithmus. Vergleichsmessungen auf
realistischen Netzwerktopologien zeigen, dass die durch REPLEX ermöglichten Lei-
stungsverbesserungen mindestens so gut oder sogar besser sind als die mit traditio-
nellen Traffic-Engineering-Verfahren erreichbaren.
Da sowohl REPLEX als auch viele andere Anwendungen auf das Sammeln von Ver-
kehrsstatistiken angewiesen sind, präsentieren wir desweiteren einen Algorithmus, mit
dem diese Aufgabe auf effiziente Art und Weise von einem Router durchgeführt wer-
den kann. Unser Expand-and-Collapse-Algorithmus (EaC) ist eine insbesondere auf
5Architekturen wie Netzwerkprozessoren ausgerichtete Heuristik, welche unter sehr re-
striktiven Speichervoraussetzungen die populärsten Pfade in Suchbäumen, welche ty-
pischerweise in Paketklassifikationsalgorithmen zur Anwendung kommen, findet. Er
erlaubt hierdurch ein effizientes Auffinden der dominierenden Verkehrsbeiträger, kann
jedoch aufgrund seiner Allgemeinheit auch in völlig anderen Kontexten zur Anwen-
dung kommen. Sowohl theoretische als auch simulationsbasierte Analysen zeigen eine
gute Performance.
Eine Grundvoraussetzung für den Entwurf dynamischer lastabhängiger Routing-
und Traffic-Engineering-Systeme ist ein tiefgreifendes Verständnis des zu routenden
Verkehrs. Daher beschreiben wir desweiteren zwei Analysemethoden für WWW-Ver-
kehr, welcher auch heute noch einen großen Anteil am Gesamtverkehrsaufkommen
stellt. Unsere Beiträge umfassen zum Einen eine Methodik zur Abschätzung von Web-
verkehrsströmen auf weltweiter Ebene, wobei eine Kombination lokaler Messungen
und Logdateien eines Content-Distribution-Netzwerks zum Einsatz kommt. Die von
uns erstellten Verkehrsmatrizen können mit zu den größten ihrer Art gezählt wer-
den und weisen eine zeitliche Variabilität auf, welche mit wachsendem zeitlichem Ab-
stand zunehmend größer wird. Die andere von uns präsentierte Methode ist eine mo-
dellbasierte Analyse von Web-Suchanfragen und den einer Suchanfrage nachfolgen-
den Klicks. Unsere Analyse bestätigt frühere Ergebnisse und liefert interessante neue
Aspekte bezüglich des Nutzerverhaltens im Kontext von Websuchmaschinen.
6Notation and Usage
Typographic Conventions
• Words from program code, language keywords, file names, program calls, com-
mands, console input, console output etc. are printed intypewriter font.
• Whenever a notion is introduced and explained, it is printed in italics, and it will
also appear on the margin. This occurrence will show up in the index in boldface.
• Software and other registered or trademarked products are written in a sans-sérif
font when they are introduced.
Index Usage
• An index entry “A, see B→C” means that for looking up A, the reader should look
up the entry B and consult its sub-entry C.
• Index entries that point to footnotes are marked with n preceding the page num-
ber.
• Index entries that point to figures are marked with f preceding the page number.
• Index entries that point to the glossary are marked with g preceding the page
number.
• Index entries that are printed in boldface point to the definition or explanation of
the expression in question.
Spelling
We shall use British spelling throughout this work. For example, we write centred and
fibre (not centered or fiber); we write naïve instead of naive; we write optimise, colour and
acknowledgement instead of optimize, color and acknowledgment, etc. Exceptions to this are
made for the spelling of established terms, trademarks, or notions, e. g., routing instead
1of routeing.
1In British English, routing without an e actually refers to drilling large holes into pieces of wood — an
aspect which this thesis admittedly does not cover to a great extent.
7License
This work, in its entirety, is licensed under the Creative Commons license CC-BY-
ND 3.0. In summary, this means:
• You can freely copy, distribute and transmit the work . . .
• . . . provided that you clearly specify that it is the work of Nils Kammenhuber (but
not in any way that suggests that you endorse me or my use of the work)
• . . . and provided that you do not alter or transform this work (apart from simple
non-destructive format conversions, e. g., PDF to PostScript).
• You may not build upon this work (i. e., you are not allowed to derive own works
from it).
You can find the full text of the license at
http://creativecommons.org/licenses/by-nd/3.0/legalcode.
A summarised version can be found at
http://creativecommons.org/licenses/by-nd/3.0/.
Chapter 2 (Background)
Moreover, I release Chapter 2 (Background; pages 19 to 29) additionaly under the Cre-
ative Commons License CC-BY-SA 3.0. In summary, this means:
• You also can alter, transform, or derive own work built on Chapter 2 of this work
(not the other parts!), . . .
• . . . provided that you clearly specify that your derivative builds on a work by Nils
Kammenhuber (but not in any way that suggest that you endorse me or my use
of the work),
• . . . and provided that you release the derivative under the same license, i. e., CC-
BY-SA 3.0.
You can find the full text of the license at
http://creativecommons.org/licenses/by-sa/3.0/legalcode.
A summarised version can be found at
http://creativecommons.org/licenses/by-sa/3.0/.
Citations
In addition to the licenses above, I grant you the right to extract pictures, tables, short
text passages etc. from this work and incorporate them into your own scientific or jour-
nalistic texts, provided that you do not alter my works, that you do not cite my works
in any misleading way, and provided that you clearly specify that they are the works
of Nils Kammenhuber (but not in any way that suggest that you endorse me or my use
of the work).
8Contents
Abstract 3
Zusammenfassung 5
About This Document 7
Typographic Conventions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7
Index Usage . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7
Spelling . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7
License . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8
Contents 9
1 Introduction 13
Overview . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16
Published Work . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17
2 Background 19
2.1 Routing . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19
2.1.1 IP addresses . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19
2.1.2 Prefixes and routes . . . . . . . . . . . . . . . . . . . . . . . . . . . 20
2.2 Routing protocols . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21
2.2.1 Interdomain and intradomain routing . . . . . . . . . . . . . . . . 21
2.2.2 BGP: The interdomain routing protocol . . . . . . . . . . . . . . . 22
2.2.3 Intradomain routing protocols . . . . . . . . . . . . . . . . . . . . 22
2.2.4 MPLS . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 24
2.3 Traffic engineering . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25
2.3.1 Problem description . . . . . . . . . . . . . . . . . . . . . . . . . . 25
2.3.2 TE metrics . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 26
2.3.3 TE in practice: Traditional TE . . . . . . . . . . . . . . . . . . . . . 27
2.3.4 TE in practice: TE with MPLS . . . . . . . . . . . . . . . . . . . . . 28
2.4 Traffic demands, traffic matrices . . . . . . . . . . . . . . . . . . . . . . . . 28
3 Characteristics of interdomain Web traffic 31
3.1 Related Work . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 32
3.2 Background: CDNs and Terminology . . . . . . . . . . . . . . . . . . . . 33
3.2.1 Terminology . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 33
3.2.2 Content delivery . . . . . . . . . . . . . . . . . . . . . . . . . . . . 33
9Contents
3.3 Interdomain Web traffic demands . . . . . . . . . . . . . . . . . . . . . . . 35
3.3.1 Motivation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 36
3.3.2 Examples . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 37
3.3.3 Applications . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 37
3.4 Using CDNs to estimate publisher demands . . . . . . . . . . . . . . . . 38
3.5 Realisation ideas . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 40
3.5.1 Estimating traffic ratios . . . . . . . . . . . . . . . . . . . . . . . . 40
3.5.2 From publisher demands to Web traffic demands . . . . . . . . . 41
3.6 Implementation details . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 42
3.6.1 CDN log evaluation . . . . . . . . . . . . . . . . . . . . . . . . . . 42
3.6.2 Estimating flow ratios between CDN and publisher . . . . . . . . 43
3.6.3 Mapping publisher demands to Web traffic demands . . . . . . . 46
3.7 Data sets . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 48
3.7.1 CDN Data . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 48
3.7.2 Data from three user sets . . . . . . . . . . . . . . . . . . . . . . . 49
3.7.3 DNS data . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 50
3.7.4 BGP data . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 50
3.8 Experimental results . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 50
3.8.1 Estimating CDN publisher demands . . . . . . . . . . . . . . . . . 50
3.8.2 Estimating relationships between CDN and publisher flows . . . 53
3.8.3 Mapping of publisher demands to Web traffic demands . . . . . 59
3.9 Summary and open questions . . . . . . . . . . . . . . . . . . . . . . . . . 61
4 Characteristics of Web search related traffic 63
4.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 63
4.2 Related Studies . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 64
4.3 Terminology . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 65
4.4 Search clickstreams . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 65
4.4.1 Search queries . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 66
4.4.2 Sessions (User Web search clickstreams) . . . . . . . . . . . . . . . 66
4.4.3 Query terms . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 67
4.5 Search characteristics . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 68
4.5.1 Dataset . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 68
4.5.2 Query session characteristics . . . . . . . . . . . . . . . . . . . . . 68
4.6 A state model for Web search . . . . . . . . . . . . . . . . . . . . . . . . . 70
4.6.1 States and transitions . . . . . . . . . . . . . . . . . . . . . . . . . . 71
4.6.2 From HTTP logs to Markov states . . . . . . . . . . . . . . . . . . 72
4.6.3 A refinement for interdomain traffic analyses . . . . . . . . . . . . 74
4.7 Model-Based Analysis . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 74
4.8 Summary and Outlook . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 76
10