Reading between the packets [Elektronische Ressource] : implicit feedback in wireless multihop networks / vorgelegt von Björn Scheuermann

Björn Scheuermann

Sujets

• Informatik

Informations

• Publié par: heinrich-heine-universitat_dusseldorf
• Publié le: 01 janvier 2007
• Nombre de lectures: 18
• Langue: English
• Poids de l'ouvrage: 2 Mo

Extrait

Reading Between the Packets
—
Implicit Feedback in
Wireless Multihop Networks
Inaugural-Dissertation
zur
Erlangung des Doktorgrades der
Mathematisch-Naturwissenschaftlichen Fakult¨at
der Heinrich-Heine-Universit¨at Dus¨ seldorf
vorgelegt von
Bj¨orn Scheuermann
aus Mannheim
Oktober 2007Aus dem Institut fur¨ Informatik
der Heinrich-Heine-Universit¨at Dus¨ seldorf
Gedruckt mit der Genehmigung der
Mathematisch-Naturwissenschaftlichen Fakult¨at der
Heinrich-Heine-Universit¨at Dusse¨ ldorf
Referent: Prof. Dr. Martin Mauve
Heinrich-Heine-Universit¨at Dusse¨ ldorf
1. Koreferent: Prof. Dr. Stefan Conrad
Heinrich-Heine-Universit¨at Dusse¨ ldorf
2. Koreferent: Prof. Dr. Peter Martini
Rheinische Friedrich-Wilhelms-Universit¨at Bonn
Tag der mundlic¨ hen Prufung¨ : 5. Dezember 2007Abstract
In this thesis, we consider wireless multihop networks with a single channel and omni-
directional 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 re-
ceived 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 exist-
ing communication protocols. Therefore, it has most often been seen—and treated—as
a handicap.
Welookatthesamepropertiesfromaverydifferentangle: theycaninfactoftenprovide
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. Im-
plicit 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 al-
lowing 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.
iiiAbstract
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 multi-
hop 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 bidi-
rectional wireless multihop data flows. noCoCo demonstrates how—through implicitly
co-ordinated scheduling—the existence of coding opportunities can be guaranteed.
Finally, we showthatimplicitlyobtainedinformationcannotonlybeusedinthedesign
of protocols, but also to overcome other difficulties. In experiments with network pro-
tocols, 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 in-
troduce 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.
ivZusammenfassung
In dieser Arbeit werden drahtlose Multihop-Netzwerke mit einem einzelnen
¨Ubertragungskanal und omnidirektionalen Antennen untersucht. Derartige Netzwerke
weisen viele einzigartige und interessante Eigenschaften auf. Die vielleicht bemerkens-
¨werteste ist die Tatsache, dass jegliche Ubertragungen von allen Netzwerkknoten in
der Umgebung empfangen werden konnen, also nicht exklusiv zwischen dem Sender und¨
demtatsachlichangesprochenenEmpfangerablaufen.UnteranderemausdiesemGrund¨ ¨
stellen drahtlose Multihop-Netzwerke existierende Kommunikationsprotokolle vor große
Schwierigkeiten.DaherwurdendieEigenschaftendieserNetzebislangnahezuausschließ-
lich als Nachteil gesehen, und auch als solcher behandelt.
HierwerdendiebesonderenEigenschafteneinesdrahtlosenMultihop-Netzwerkesausei-
ner anderen Perspektive betrachtet. Wie sich dabei herausstellt, konnen sie oft als Basis¨
fur¨ neuartige und unkonventionelle L¨osungsansatze¨ dienen. Viele der Herausforderun-
gen, die sich aus den Besonderheiten des Netzwerks ergeben, lassen sich bewalti¨ gen,
indem man diese Besonderheiten in maßgeschneiderten Protokollen gezielt nutzt. Die
¨Eigenschaften des Ubertragungsmediums lassen sich nutzen, um implizit Information
zu gewinnen oder Vorgange zu koordinieren, ohne dabei explizit Daten austauschen zu¨
musse¨ n.
¨Als erster zentraler Beitrag dieser Arbeit wird ein neuartiger Uberlastkontrollmecha-
nismus vorgestellt. Er vereint Funktionen, die traditionell in der Transportschicht und
¨der Medienzugriffsplanung angesiedelt sind. Die implizite schrittweise Uberlastkontrolle
benotigt¨ keine explizite Ruc¨ kmeldung ub¨ er die gegenw¨artige Lastsituation. Sie basiert
auf dem Aufbau von Ruckstau im Netzwerk mittels sehr kurzer Paketwarteschlangen.¨
¨DieUbertragungeinesFolgepaketeswirdverhindert,solangevomNachfolgeknotennicht
¨die Daten aus der vorigen Ubertragung weitergeleitet wurden. So wird ein Zufluss von
Daten, der die verfugb¨ are Transportkapazit¨at ub¨ ersteigt, vermieden. Dieses Konzept
wird im Protokoll Cooperative Cross-layer Congestion Control (CXCC) umgesetzt und
evaluiert.
vZusammenfassung
¨CXCC bietet einen Uberlastkontrollmechanismus, nicht jedoch TCP-¨aquivalente Ende-
zu-Ende-Zuverlassigkeit. Mit dem Protokoll Backpressure Reliability (BarRel) wird des-¨
halb der Einsatz impliziter Informationsgewinnung weiter ausgedehnt. BarRel nutzt
¨Wissen uber die Funktionsweise der Uberlastkontrolle, um implizit auf die erfolgrei-¨
che Zustellung von Datenpaketen an einen weiter entfernten Zielknoten zu schließen.
Im Gegensatz zu existierenden TCP-aquivalenten Transportprotokollen benotigt Bar-¨ ¨
Rel daher keinen kontinuierlichen Strom von Bestatigu¨ ngspaketen und reduziert so den
notwendigen Kontrolldatenverkehr stark.
¨DieimpliziteschrittweiseUberlastkontrollekannauchaufMulticast-Datenubertragung-¨
en angewendet werden. Dies wird im Protokoll Backpressure Multicast Congestion Con-
trol (BMCC) umgesetzt. Aufbauend auf impliziten Ruckmeldungen und abgeleitet von¨
CXCCerzielteseineeffektiveRegelungderQuelldatenratebeigeringenPaketlaufzeiten
und mit minimalem Kontrolldatenaufkommen.
Im Anschluss an die Diskussion von BMCC wendet sich die Arbeit der Technik des Net-
workCodingzu,alsoder(codierten)KombinationmehrererDatenpaketeineineeinzelne
¨Ubertragung durch weiterleitende Netzwerkknoten. Opportunistisches Network Coding
ist ein existierender Ansatz, der die Kapazitat drahtloser Multihop-Netzwerke erhohen¨ ¨
kann. Es ist jedoch darauf angewiesen, dass Situationen, in denen eine Kombination
von Paketen erfolgen kann, auch tatsachlich entstehen. Mit Near-Optimal Co-ordinated¨
¨Coding (noCoCo) wird eine Technik fur¨ bidirektionale Ubertragungen in drahtlosen
Multihop-Umgebungen vorgestellt. noCoCo zeigt, wie durch implizite Koordination von
¨Ubertragungen die Moglic¨ hkeit zur Kapazitatss¨ teigerung mittels Network Coding ga-
rantiert werden kann.
Um die breite Anwendbarkeit des Prinzips des impliziten Informationsaustauschs zu
unterstreichen,erfolgtabschließenddieDiskussioneinerAnwendungaußerhalbdesEnt-
wurfs eines Netzwerkprotokolls. In Experimenten mit Netzwerkprotokollen ist eine ge-
meinsame Zeitbasis der Ereignisprotokolle eine unerl¨assliche Voraussetzung fur¨ die Er-
gebnisauswertung. Diese durch den Austausch von Zeitinformation – etwa mittels NTP
– zu realisieren, kann, wegen des damit verbundenen Netzwerkv