Backpressure Routing Made Practical

Download PDF.

“Backpressure Routing Made Practical” by S. Moeller, A. Sridharan, B. Krishnamachari, and O. Gnawali. In INFOCOM IEEE Conference on Computer Communications Workshops , 2010, Mar. 2010, pp. 1 -2.


Current data collection protocols for wireless sensor networks are mostly based on quasi-static minimum-cost routing trees. We consider an alternative, highly-agile approach called backpressure routing, in which routing and forwarding decisions are made on a per-packet basis. Although there is a considerable theoretical literature on backpressure routing, it has not been implemented on practical systems to date due to concerns about packet looping and large packet delays. Addressing these concerns, we present the Backpressure Collection Protocol (BCP) for sensor networks, the first ever implementation of dynamic backpressure routing in wireless networks. In particular, we demonstrate for the first time that replacing the traditional FIFO queue service in backpressure routing with LIFO queues reduces the average end-to-end packet delays for delivered packets drastically (98% under low load). Under static network settings, BCP shows a more than 60% improvement in max-min rate over the state of the art Collection Tree Protocol (CTP). We also empirically demonstrate the superior delivery performance of BCP in network settings of extreme external interference.

Download PDF.

BibTeX entry:

   author = {S. Moeller and A. Sridharan and B. Krishnamachari and O. Gnawali},
   title = {Backpressure Routing Made Practical},
   booktitle = {INFOCOM IEEE Conference on Computer Communications
	Workshops , 2010},
   number = {},
   pages = {1 -2},
   month = mar,
   year = {2010}