IEEE Copyright Notice

This material is presented to ensure timely dissemination of scholarly and technical work. Copyright and all rights therein are retained by authors or by other copyright holders. All persons copying this information are expected to adhere to the terms and constraints invoked by each author's copyright. In most cases, these works may not be reposted without the explicit permission of the copyright holder.

ACM Copyright Notice

These are the authors' versions of the work. The copyright is with ACM. They are posted here by permission of ACM for your personal use. Not for redistribution. See individual publication details for information on the publication of the definitive versions.

Springer-Verlag LNCS Copyright Notice

The copyright of these contributions has been transferred to Springer-Verlag Berlin Heidelberg New York. The copyright transfer covers the exclusive right to reproduce and distribute the contribution, including reprints, translations, photographic reproductions, microform, electronic form (offline, online), or any other reproductions of similar nature. Online available from Springer-Verlag LNCS series.

Work that appeared before the 1st of September 2003 was published while the authors were with the Lehrstuhl Praktische Informatik IV at the University of Mannheim.

Reading Between the Packets - Implicit Feedback in Wireless Multihop Networks

Author(s): Björn Scheuermann.
Title: Reading Between the Packets - Implicit Feedback in Wireless Multihop Networks
Published: PhD thesis, Heinrich Heine University, Düsseldorf, Germany, December 2007
Keyword(s): 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
Abstract: 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 receivedby 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 providethe basis for novel and unconventional solution approaches, and many challenges can be tackledby being aware of their consequences, and by making use of themin tailored protocol designs. The medium properties can be used to obtain information and to co-ordinateactions implicitly, i.e., without dedicated information exchange.As our first major contribution, we introduce a congestion control scheme that bridges whatwas traditionally transport layer functionality and medium access scheduling. Implicithop-by-hop congestion control does not need to exchange any congestion feedback explicitly. It is based on establishing backpressurewith very short queues, by not allowing the transmission of a follow-up packet beforefurther 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 thusextend the concept of implicit feedback further, and design theBackpressure Reliability (BarRel) transport protocol. BarRel exploits properties of the congestioncontrol approach to infer successful end-to-end packet delivery. In contrast to existing TCP-equivalent transportprotocols 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. Wedo so in the Backpressure Multicast Congestion Control (BMCC) protocol. Based onimplicit feedback and derived from CXCC, it achieves effective source rate adaption atlow 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 increasethe capacity of wireless multihop networks, but it depends on thespontaneous emergence of situations in which this is possible. Here, we introduceNear-Optimal Co-ordinated Coding (noCoCo) for bidirectional wireless multihop data flows.noCoCo demonstrates how---through implicitlyco-ordinated scheduling---the existence of coding opportunities can be guaranteed.Finally, we show that implicitly obtained information can not only be used inthe design of protocols, but also to overcome other difficulties. In experimentswith network protocols, a common time basis of the nodes' log files is vital for the evaluation ofresults. 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 fromthe participating nodes as its input and uses parallel observations of the same eventsby multiple nodes to infer the relative deviation of the clocks. This allows to compute globally consistenttimestamps, without a need for dedicated communication during the experiment.
Bib entry: [XML] [BibTeX]
Download: [PDF]
Verantwortlich für den Inhalt: E-Mail sendenWE Informatik