Speculative protocol processing for high-speed packet forwarding [Elektronische Ressource] / Jürgen Foag

Sujets

• Informatik

Informations

• Publié par: technische_universitat_munchen
• Publié le: 01 janvier 2004
• Nombre de lectures: 24
• Langue: English
• Poids de l'ouvrage: 1 Mo

Extrait

Lehrstuhl fur¨ Integrierte Schaltungen
Technische Universitat¨ Munchen¨
Speculative Protocol-Processing for High-Speed Packet
Forwarding
Jur¨ gen FoagLehrstuhl fur¨ Integrierte Schaltungen
Technische Universitat¨ Munchen¨
Speculative Protocol-Processing for High-Speed Packet
Forwarding
Jur¨ gen Foag
Vollstandiger¨ Abdruck der von der Fakultat¨ fur¨ Elektrotechnik und Informationstechnik
der Technischen Universitat¨ Munchen¨ zur Erlangung des akademischen Grades eines
Doktor-Ingenieurs
genehmigten Dissertation.
Vorsitzender: Univ.-Prof. Dr.-Ing. Jor¨ g Eberspacher¨
Prufer¨ der Dissertation:
1. Univ.-Prof. Dr.-Ing. Ingolf Ruge, em.
2. Univ.-Prof. Dr.-Ing. Erik Maehle, Universitat¨ zu Lubeck¨
3. Univ.-Prof. Dr. sc. techn. (ETH) Andreas Herkersdorf
Die Dissertation wurde am 18.09.2003 bei der Technischen Universitat¨ Munchen¨
eingereicht und durch die Fakultat¨ fur¨ Elektrotechnik und Informationstechnik
am 26.02.2004 angenommen.ii
Rien n’est plus fort qu’une idee dont l’heure est venue !´
(Victor Hugo)
To Lydia, Mareike, Anyesse and everyone who will follow ...
with all my love !iii
Acknowledgments
I would like to express my sincere appreciation and gratitude to my supervisor, Prof. Ingolf
Ruge, chair of the Institute for Integrated Circuits at the Technical University of Munich.
He encouraged me in research of integrated circuits in the application field of High-Speed
Networking.
I am also indebted to Prof. Erik Maehle and Prof. Andreas Herkersdorf for accepting to
act as competent co-referees for this dissertation. Their insights and constructive criticism
inspire for further activities in the challenging area of network processors.
Thanks also to Prof. Eberspacher¨ for serving as the chair for the oral defense of my disser-
tation.
Likewise, this work drew inspiration and invaluable support from Dr. Thomas Wild and Dr.
Walter Stechele. They have listened patiently my ideas of speculative protocol processing.
This work also benefited from discussions with Dr. Oliver Denk, Gregory Gagarin, Dr.
Iyad Kanj, Oliver Laub, Dr. Damien Magoni, Osnat Mokryn and Maresa Praxenthaler.
I would like to also thank my colleagues at the Institute for Integrated Circuits, namely
Stephan Herrmann, Wolfgang Kohtz, Dr. Torsten Mahnke, Dr. Nuria Pazos, Stephan Stilk-
erich and Armin Windschiegl.
This work was influenced in particular by experiences I have made in the S/390 Micro-
processor Development of IBM Boblingen,¨ Germany. Special thanks are denoted to Ralph
Koester.
This work would never have been realized without the love, help, support and female in-
spirations of my family Lydia, Mareike, Anyesse as well as my sisters Isabell, Monika, Ute
and Regina. Finally, I am indebted to my mother Lieselotte and my father Lorenz (†) for
all they gave to me during my life.iv
Kurzfassung
Netzprozessoren sind Bausteine, die in zunehmendem Maße in Internetroutern eingesetzt
werden. Neben der flexiblen Unterstutzung¨ von Protokollen und Diensten zeichnen sich durch eine hohe Leistungsfahigk¨ eit aus. Die Flexibilitat¨ wird durch
eingebettete Prozessoren mit optimiertem Instruktionssatz realisiert. Eine hohe Perfor-
manz wird durch geeignete Systemarchitekturen erzielt, die sowohl Multiprozessierung
als auch Multithreading unterstutzen.¨ Wesentliche Performanzmetriken bei Netzwerkkom-
ponenten sind Datendurchsatz und Bearbeitungslatenz. Wahrend¨ bisherige Netzprozes-
soren auf hohe Datendurchsatzwerte optimiert sind, wird die Bearbeitungslatenz von ar-
chitektureller Seite des Netzprozessors in der Regel vernachlassigt.¨ Dies kann sich bei
Echtzeitanwendungen, z.B. Internettelefonie, als nachteilig erweisen. Stattdessen sollen
eine beschleunigte Paketweiterleitung und somit verkurzte¨ Latenzen in Netzknoten mit-
tels geeigneter Dienstarchitekturmodelle, wie z.B. Differentiated Services, und veranderten¨
Weiterleitungsprinzipien wie Multiprotocol Label Switching ermoglicht¨ werden.
Zentraler Bestandteil dieser Arbeit ist eine Protokollbearbeitungsmethode fur¨ Netzwerk-
prozessoren, die auf kurze Verzogerungszeiten¨ bei der Protokollverarbeitung fokussiert ist.
Die Methode besteht aus 2 Teilen: mittels Protokollstapelpradiktion¨ wird aus einer Menge
von in der Vergangenheit empfangenen Paketen der Protokollstapel des als nachstes¨ emp-
fangenen Pakets vorhergesagt. Die Bearbeitung von unterschiedlichen Netzwerkschichten
zugehorigen¨ Funktionen dieses Pakets wird durch spekulative Protokollbearbeitung gle-
ichzeitig in parallelen Bearbeitungseinheiten begonnen. Im Falle einer korrekten Vorher-
sage ist die Bearbeitungslatenz verkurzt.¨ Anderenfalls ergeben sich hohere¨ Bearbeitungs-
dauern. Zusammengefasst wird fur¨ die Bearbeitungsdauer eine im statistischem Mittel
reduzierte Latenz erwartet.
Im ersten Teil der Arbeit wird eine abstrakte Konzeptevaluierung durchgefuhrt.¨ Hierzu
werden netzwerk- und implementierungsspezifische Merkmale separiert und die das
Konzept beeinflussenden Parameter extrahiert. In einzelnen Szenarien wird dann der
quantitative Einfluss jeweils eines Parameters auf Latenzreduktion und zusatzlichen¨
Prozessierungsaufwand hin analysiert. Es wird unter anderem gezeigt, dass mittels
einer hohen Vorhersagegute¨ wesentlich die Latenzreduktion erhoht¨ und der zusatzliche¨and gesenkt werden kann.
Um das Verhalten der Bearbeitungslatenz im Internet-spezifischen Anwendungsfall zu
analysieren, wird ein System spezifiziert, das das spekulative Bearbeitungskonzept imple-
mentiert. Hierbei handelt es sich nicht um ein optimiertes Netzwerkprozessorsystem, das
mit kommerziell erhaltlichen¨ Bausteinen vergleichbar ist. Stattdessen dient es zur Bestim-
mung der erzielbaren Latenzreduktion unter implementierungsspezifischen Aspekten, z.B.
Verwendung einer aufgeteilten Busarchitektur. Da das Konzept eine hohe Latenzreduktion
an Einsatzorten mit komplexer Paketbearbeitung verspricht, wird hierfur¨ der Zugangsbere-
ich zu Internetdomanen¨ gewahlt.¨ Als Pradiktionsalgorithmus¨ wird ein Verfahren verwen-v
det, das auf dem am haufigsten¨ aufgetretenen Ereignis basiert. Das dynamische Verhal-
ten ermoglicht¨ eine selbststandige¨ Anpassung an veranderte¨ Netzwerkverkehrscharakteris-
tiken. Zum Zweck der schnellen Vorhersagetransienz und zur Vermeidung von moglichen¨
Vorhersageregisteruberl¨ aufen¨ ist es um einen zyklischen Rucksetzungsmechanismus¨ er-
weitert.
Sowohl fur¨ die Systemsimulation als auch die Simulation der Vorhersageeinheit werden ak-
tuelle Netzwerkverkehrsstatistiken verwendet. Basierend auf Verkehrsstatistiken von 2002
ergaben sich bei der Simulation der zweistufigen Vorhersageeinheit Raten fur¨ korrekte
Vorhersagen von 82 % fur¨ die erste und ca. 98 % fur¨ erste und zweite Vorhersagestufe
zusammen. Grundsatzlich¨ laßt¨ sich feststellen, dass die mittlere Zeitdauer zur Berech-
nung einer neuen Vorhersage deutlich geringer ist als die Bearbeitungslatenz eines
Pakets. Dies ermoglicht¨ eine Aktualisierung der Vorhersagetabellen fur¨ jedes Paket. Fur¨ die
Systemsimulation wird als Referenzimplementierung ein Modell verwendet, dass die Bear-
beitung in parallelen Prozessoren pseudo-parallel, d.h. zeitversetzt entsprechend bestehen-
der Datenabhangigk¨ eiten und deren Auflosung,¨ ausfuhrt.¨ Fur¨ die exemplarisch gewahlte¨
Systemumgebung am Netzwerkedge ergaben sich Werte zwischen 6,4 und 22,5 % fur¨ die
Latenzreduktionen. Als Nachteil ergibt sich jedoch eine hohere¨ Auslastung der eingebet-
teten Prozessoren im Fall der spekulativen Bearbeitungsmethode.
Abschliessend wird die Protokollbearbeitungsmethode aus Anwendungssicht betrach-
tet. Fehlvorhersagen verursachen langere¨ Bearbeitungsdauern und generieren fol-
glich Verzogerungsschw¨ ankungen, die sich auf Echtzeitanwendungen wie IP-Telefonie
nachteilig auswirken konnen.¨ Zur Kompensation von Verzogerungsschw¨ ankungen wird ein
netzwerkknoteninterner Ansatz gemacht, der im Warteschlangensystem implementiert ist.
Hierzu wird ein als Referenz gewahlter¨ weighted-fair-queuing Algorithmus um zwei Priori-
tatsw¨ arteschlangen erweitert. In diese werden Pakete mit einer bzw. mit zwei Fehlvorher-
sagen abgelegt. Die Untersuchungen zeigen, dass hierdurch zeitliche Schwankungen bei
Paketen, die schnelle Paketweiterleitung erfordern, ausgeglichen werden konnen.¨ Zuletzt
wird die Latenzreduktion des spekulativen Netzprozessors gegenuber¨ pseudoparallelen
Referenzimplementierungen auf 13,4 bis 14,9 % abgeschatzt.¨
Zusammenfassend wird festgestellt, dass das Konzept der Protokollvorhersage und speku-
lativen Paketbearbeitung gewinnbringend in Routern am Internetrandbereich und zwischen
den Domanen¨ von Internetdiensteanbietern eingesetzt werden kann, um deren Bear-
beitungsdauern zu verringern.vi
Resum´ e´
Les processeurs reseaux´ sont des composants qui sont de plus en plus utilises´ dans les
routeurs de l’Internet. En plus de fournir un support flexible pour les protocoles et les
services, les processeurs reseaux´ fournissent de hautes performances.