eprintid: 12132
rev_number: 6
eprint_status: archive
userid: 1
dir: disk0/00/01/21/32
datestamp: 2011-07-07 15:11:41
lastmod: 2014-04-03 22:44:47
status_changed: 2012-08-15 09:00:14
type: doctoralThesis
metadata_visibility: show
creators_name: Al-Shabibi, Ali
title: MultiPaths Revisited - A novel approach using OpenFlow-enabled devices
title_de: Neu erarbeitete Multipaths - Ein neuer Ansatz mit OpenFlow fähigen Geräten
ispublished: pub
subjects: ddc-004
divisions: i-130700
adv_faculty: af-11
keywords: Communication systems , Protocols , Monitoring , Computer network performance , Communication system routing , Congestion Control , Selfish Routing
cterms_swd: IT-Abteilung
cterms_swd: Kommunikationssystem
cterms_swd: Netzwerk
cterms_swd: Routing
cterms_swd: Eigennütziges Routing
cterms_swd: Überlastkontrolle
cterms_swd: RFCN
abstract: This thesis presents novel approaches enhancing the performance of computer networks using multipaths. Our enhancements take the form of congestion- aware routing protocols. We present three protocols called MultiRoute, Step- Route, and finally PathRoute. Each of these protocols leverage both local and remote congestion statistics and build different representations (or views) of the network congestion by using an innovative representation of congestion for router-router links. These congestion statistics are then distributed via an aggregation protocol to other routers in the network. For many years, multipath routing protocols have only been used in simple situations, such as Link Aggregation and/or networks where paths of equal cost (and therefore equal delay) exist. But, paths of unequal costs are often discarded to the benefit of shortest path only routing because it is known that paths of unequal length present different delays and therefore cause out of order packets which cause catastrophic network performances. Further, multipaths become highly beneficial when alternative paths are selected based on the network congestion. But, no realistic solution has been proposed for congestion-aware multipath networks. We present in this thesis a method which selects alternative paths based on network congestion and completely avoids the issue of out of order packets by grouping packets into flows and binding them to a single path for a limited duration. The implementation of these protocols relies heavily on OpenFlow and NOX. OpenFlow enables network researchers to control the behavior of their network equipment by specifying rules in the routers flow table. NOX provides a simple Application Programming Interface (API) to program a routers flow table. Therefore by using OpenFlow and NOX, we are able to define new routing protocols like the ones which we will present in this thesis. We show in this thesis that grouping packets together, while not optimal, still provides a significant increase in network performance. More precisely we show that our protocols can, in some cases, achieve up to N times the throughput of Shortest Path (SP), where N is the number of distinct paths of identical throughput from source to destination. We also show that our protocols provide more predictable throughput than simple hash-based routing algorithms. Todays networks provide more and more connections between any source- destination pair. Most of these connections remain idle until some failure occurs. Using the protocols proposed in this thesis, networks could leverage the added bandwidth provided by these currently idle connections. Therefore, we could increase the overall performance of current networks without replacing the existing hardware.
abstract_translated_text: Diese Arbeit pr ̈asentiert neuartige Ans ̈atze, um die Leistung von Comput- ernetzwerken durchmultipathszu verbessern. Unsere Verbesserungen haben die Form von congestionaware routing protocols. Wir pr ̈asentieren drei Protokolle mit den Bezeichnungen MultiRoute, Step-Route und nally PathRoute. Jede dieser Protokolle lokale und entfernte Verkehrsstatistiken und bilden Repr ̈asen- tierungen (oder Abbildungen) des Netzwerkverkehrs durch das Nutzen einer in- novativen Representation des Verkehrsaufkommens von Router-Router Verbin- dungen. Diese Verkehrsstatistiken werden dann durch ein Aggregationspro- tokoll zu anderen Routern im Netzwerk verteilt. Lange Jahre wurden multipath routing Protokolle nur in einfachen Situa- tionen, so wie Link Aggregation benutzt und/oder Netzwerken bei denen Pfade mit selben Kosten (und deshalb die selben Verz ̈ogerungen) vorherrschen. Je- doch sind Pfade mit unterschiedlichen Kosten oftmals zumnutzen des ku ̈rzesten und einzigroutenden Pfades ausgesondert. Dies geschieht da es bekannt ist, dass Pfade von unterschiedlichen L ̈angenanderezeigen und deshalb katastrophale Netzwerk Leistungen bewirken. Desweiteren werden multipaths hochgradig nu ̈tzlich, wenn alternative Pfade basierend auf Netzwerkauslastung ausgesucht werden. Jedoch wurde keine realistische L ̈osung fu ̈r auslastungsbewusste mul- tipath Netzwerke. Wir presentieren in dieser Arbeit eine Methode, die alterna- tive Pfade basierend auf Netzwerkauslastung selektiert und das Problem von out-of-order Packeten durch Gruppierung von Packeten in fliesst umgeht und sie fu ̈r eine begrenzte Zeit in einen einzelnen Pfad bindet. Die Implementierung dieser Protokolle ist stark von OpenFlow und NOX abh ̈angig. OpenFlow erm ̈oglicht Netzwerk Forschern das Verhalten ihrer Net- zwerkausru ̈stung durch Festlegung von Regeln in den fliesst Tabellen der Routern zu kontrollieren. NOX bietet eine einfaches Application Programming Inter- face (API), um fliesst Tabellen von Routern zu programmieren. Aufgrund dessen sind wir in der Lage neue Protokolle wie die, die wir in dieser Arbeit presentieren werden zu definieren. Wir demonstrieren in dieser Arbeit, dass die Gruppierung von Packeten eine signifikante Netzwerkleistungssteigerung liefert, auch wenn diese nicht op- timal ist. Genauer gesagt zeigen wir auf wie unsere Protokolle in einigen F ̈allen bis zu N mal den Durchlauf des Shortest Path erreichen, wobei N die Zahl der verschiedenen Pfade des identischen Durchlaufes von Quelle zum Ziel sind. Desweiteren zeigen wir, dass unsere Protokolle mehr vorhersehbahren Durch- lauf als einfache hash-basierte Leitweg Algorythmen liefern. Heutige Netzwerke liefern immer mehr Verbindungen zwischen s ̈amtlichen Quell-Ziel Paaren. Die meisten dieser Verbindungen bleiben ungenutzt bis ir- gend ein Fehler stattfindet. Mit den Protokollen die in dieser Arbeit vorgeschla- gen werden, k ̈onnte sich der zus ̈atzlichen Bandbreite dieser derzeitig ungenutz- ten Verbindungen bedient werden. Folglich k ̈onnten wir die Gesamtleistung von bestehenden Netzwerken steigern, ohne die hardware zu ersetzen.
abstract_translated_lang: ger
class_scheme: ccs
class_labels: H.3.4
date: 2011
date_type: published
id_scheme: DOI
id_number: 10.11588/heidok.00012132
ppn_swb: 1650963068
own_urn: urn:nbn:de:bsz:16-opus-121329
date_accepted: 2011-07-06
advisor: HASH(0x55e0f7f407e0)
language: eng
bibsort: ALSHABIBIAMULTIPATHS2011
full_text_status: public
citation:   Al-Shabibi, Ali  (2011) MultiPaths Revisited - A novel approach using OpenFlow-enabled devices.  [Dissertation]     
document_url: https://archiv.ub.uni-heidelberg.de/volltextserver/12132/1/thesis.pdf