Dokument: Reading Between the Packets - Implicit Feedback in Wireless Multihop Networks

Titel:	Reading Between the Packets - Implicit Feedback in Wireless Multihop Networks
URL für Lesezeichen:	https://docserv.uni-duesseldorf.de/servlets/DocumentServlet?id=6582
URN (NBN):	urn:nbn:de:hbz:061-20071219-100941-3
Kollektion:	Dissertationen
Sprache:	Englisch
Dokumententyp:	Wissenschaftliche Abschlussarbeiten » Dissertation
Medientyp:	Text
Autor:	Dr. Scheuermann, Björn [Autor]
Dateien:	[Dateien anzeigen] Adobe PDF [Details] 2,12 MB in einer Datei [ZIP-Datei erzeugen] Dateien vom 19.12.2007 / geändert 19.12.2007
Beitragende:	Prof. Dr. Mauve, Martin [Betreuer/Doktorvater] Prof. Dr. Conrad, Stefan [Gutachter] Prof. Dr. Martini, Peter [Gutachter]
Stichwörter:	Implicit Feedback, Wireless Multihop Networks, Implicit Hop-by-Hop Congestion Control, CXCC, Congestion Control, BarRel, Reliability, Transport Protocol, TCP, Backpressure, BMCC, Multicast, noCoCo, Network Coding, Co-ordinated Coding, Offline Time Synchronization, Log Data Analysis, Timestamp Synchronization
Dewey Dezimal-Klassifikation:	000 Informatik, Informationswissenschaft, allgemeine Werke » 004 Datenverarbeitung; Informatik
Dokumententyp (erweitert):	Dissertation
Beschreibungen:	In this thesis, we consider wireless multihop networks with a single channel and omnidirectional antennas. Such networks exhibit some distinctive and interesting properties. The most central one is that each transmission is a local broadcast, i.e., it can be received by all nodes in the vicinity. It is thus not exclusive between the sender and the intended receiver. This unique environment turned out to be very challenging for existing communication protocols. Therefore, it has most often been seen - and treated - as a handicap. We look at the same properties from a very different angle: they can in fact often provide the basis for novel and unconventional solution approaches, and many challenges can be tackled by being aware of their consequences, and by making use of them in tailored protocol designs. The medium properties can be used to obtain information and to co-ordinate actions implicitly, i.e., without dedicated information exchange. As our first major contribution, we introduce a congestion control scheme that bridges what was traditionally transport layer functionality and medium access scheduling. Implicit hop-by-hop congestion control does not need to exchange any congestion feedback explicitly. It is based on establishing backpressure with very short queues, by not allowing the transmission of a follow-up packet before further forwarding of the previous one has been overheard. This avoids excessive packet inflow. The concept is realized and assessed in the Cooperative Cross-layer Congestion Control (CXCC) protocol. While CXCC provides congestion control, it does not guarantee TCP-like end-to-end reliability. We thus extend the concept of implicit feedback further, and design the Backpressure Reliability (BarRel) transport protocol. BarRel exploits properties of the congestion control approach to infer successful end-to-end packet delivery. In contrast to existing TCP-equivalent transport protocols it does therefore not need a continuous stream of acknowledgments from the destination. Therefore, it largely reduces the amount of control traffic. Implicit hop-by-hop congestion control can also be extended to a multicast setting. We do so in the Backpressure Multicast Congestion Control (BMCC) protocol. Based on implicit feedback and derived from CXCC, it achieves effective source rate adaption at low latencies and minimal control overhead. Following the discussion of BMCC, we look at network coding, i.e., the combination of multiple packets into one (coded) transmission by intermediate routers. Opportunistic network coding has been proposed to practically increase the capacity of wireless multihop networks, but it depends on the spontaneous emergence of situations in which this is possible. Here, we introduce Near-Optimal Co-ordinated Coding (noCoCo) for bidirectional wireless multihop data flows. noCoCo demonstrates how - through implicitly co-ordinated scheduling - the existence of coding opportunities can be guaranteed. Finally, we show that implicitly obtained information can not only be used in the design of protocols, but also to overcome other difficulties. In experiments with network protocols, a common time basis of the nodes' log files is vital for the evaluation of results. Exchanging time information - as time synchronization protocols like NTP do - may, however, interfere with the network traffic generated in the experiment. We thus introduce an alternative in form of a post-facto time synchronization method, which is based on implicitly obtained information. It takes event log files from the participating nodes as its input and uses parallel observations of the same events by multiple nodes to infer the relative deviation of the clocks. This allows to compute globally consistent timestamps, without a need for dedicated communication during the experiment. In dieser Arbeit werden drahtlose Multihop-Netzwerke mit einem einzelnen Übertragungskanal und omnidirektionalen Antennen untersucht. Derartige Netzwerke weisen viele einzigartige und interessante Eigenschaften auf. Die vielleicht bemerkenswerteste ist die Tatsache, dass jegliche Übertragungen von allen Netzwerkknoten in der Umgebung empfangen werden können, also nicht exklusiv zwischen dem Sender und dem tatsächlich angesprochenen Empfänger ablaufen. Unter anderem aus diesem Grund stellen drahtlose Multihop-Netzwerke existierende Kommunikationsprotokolle vor große Schwierigkeiten. Daher wurden die Eigenschaften dieser Netze bislang nahezu ausschließlich als Nachteil gesehen, und auch als solcher behandelt. Hier werden die besonderen Eigenschaften eines drahtlosen Multihop-Netzwerkes aus einer anderen Perspektive betrachtet. Wie sich dabei herausstellt, können sie oft als Basis für neuartige und unkonventionelle Lösungsansätze dienen. Viele der Herausforderungen, die sich aus den Besonderheiten des Netzwerks ergeben, lassen sich bewältigen, indem man diese Besonderheiten in maßgeschneiderten Protokollen gezielt nutzt. Die Eigenschaften des Übertragungsmediums lassen sich nutzen, um implizit Information zu gewinnen oder Vorgänge zu koordinieren, ohne dabei explizit Daten austauschen zu müssen. Als erster zentraler Beitrag dieser Arbeit wird ein neuartiger Überlastkontrollmechanismus vorgestellt. Er vereint Funktionen, die traditionell in der Transportschicht und der Medienzugriffsplanung angesiedelt sind. Die implizite schrittweise Überlastkontrolle benötigt keine explizite Rückmeldung über die gegenwärtige Lastsituation. Sie basiert auf dem Aufbau von Rückstau im Netzwerk mittels sehr kurzer Paketwarteschlangen. Die Übertragung eines Folgepaketes wird verhindert, solange vom Nachfolgeknoten nicht die Daten aus der vorigen Übertragung weitergeleitet wurden. So wird ein Zufluss von Daten, der die verfügbare Transportkapazität übersteigt, vermieden. Dieses Konzept wird im Protokoll Cooperative Cross-layer Congestion Control (CXCC) umgesetzt und evaluiert. CXCC bietet einen Überlastkontrollmechanismus, nicht jedoch TCP-äquivalente Ende-zu-Ende-Zuverlässigkeit. Mit dem Protokoll Backpressure Reliability (BarRel) wird deshalb der Einsatz impliziter Informationsgewinnung weiter ausgedehnt. BarRel nutzt Wissen über die Funktionsweise der Überlastkontrolle, um implizit auf die erfolgreiche Zustellung von Datenpaketen an einen weiter entfernten Zielknoten zu schließen. Im Gegensatz zu existierenden TCP-äquivalenten Transportprotokollen benötigt BarRel daher keinen kontinuierlichen Strom von Bestätigungspaketen und reduziert so den notwendigen Kontrolldatenverkehr stark. Die implizite schrittweise Überlastkontrolle kann auch auf Multicast-Datenübertragungen angewendet werden. Dies wird im Protokoll Backpressure Multicast Congestion Control (BMCC) umgesetzt. Aufbauend auf impliziten Rückmeldungen und abgeleitet von CXCC erzielt es eine effektive Regelung der Quelldatenrate bei geringen Paketlaufzeiten und mit minimalem Kontrolldatenaufkommen. Im Anschluss an die Diskussion von BMCC wendet sich die Arbeit der Technik des Network Coding zu, also der (codierten) Kombination mehrerer Datenpakete in eine einzelne Übertragung durch weiterleitende Netzwerkknoten. Opportunistisches Network Coding ist ein existierender Ansatz, der die Kapazität drahtloser Multihop-Netzwerke erhöhen kann. Es ist jedoch darauf angewiesen, dass Situationen, in denen eine Kombination von Paketen erfolgen kann, auch tatsächlich entstehen. Mit Near-Optimal Co-ordinated Coding (noCoCo) wird eine Technik für bidirektionale Übertragungen in drahtlosen Multihop-Umgebungen vorgestellt. noCoCo zeigt, wie durch implizite Koordination von Übertragungen die Möglichkeit zur Kapazitätssteigerung mittels Network Coding garantiert werden kann. Um die breite Anwendbarkeit des Prinzips des impliziten Informationsaustauschs zu unterstreichen, erfolgt abschließend die Diskussion einer Anwendung außerhalb des Entwurfs eines Netzwerkprotokolls. In Experimenten mit Netzwerkprotokollen ist eine gemeinsame Zeitbasis der Ereignisprotokolle eine unerlässliche Voraussetzung für die Ergebnisauswertung. Diese durch den Austausch von Zeitinformation - etwa mittels NTP - zu realisieren, kann, wegen des damit verbundenen Netzwerkverkehrs, das Experiment beeinflussen und Ergebnisse verfälschen. Hier wird ein Mechanismus vorgeschlagen, der solche Probleme vermeidet. Er identifiziert parallele Beobachtungen der selben Ereignisse durch mehrere Knoten in den unsynchronisierten Ereignisprotokollen und verwendet sie, um die Uhren in Beziehung zueinander zu setzen und schließlich global konsistente Zeitstempel zu errechnen. Kommunikation, die speziell der Zeitsynchronisation dient, ist deshalb während des Experimentes nicht notwendig.
Lizenz:	Urheberrechtsschutz
Fachbereich / Einrichtung:	Mathematisch- Naturwissenschaftliche Fakultät » WE Informatik » Rechnernetze
Dokument erstellt am:	19.12.2007
Dateien geändert am:	19.12.2007
Promotionsantrag am:	09.10.2007
Datum der Promotion:	05.12.2007