Online Packet Admission and Oblivious Routing in Sensor Networks

Mohamed Aly, Phd student, pitt CS Department

Tuesday, November 14, 2006, Noon
Noon - SENSQ 5317
Free pizza for attendees starting at 11:45 a.m.

Advisors: Kirk Pruhs and Panos K. Chrysanthis

Abstract

The concept of Oblivious Routing for general undirected networks was introduced by Racke when he showed that there exists an oblivious routing algorithm with polylogarithmic competitive ratio (w.r.t. edge congestion) for any undirected graph. In a following result, Racke and Rosen presented admission control algorithms achieving a polylogarithmic fraction (in the size of the network) of the optimal number of accepted messages. Both these results assume that the network incurs a cost only after it is accepted and the message is routed. Admission control and routing algorithms for sensor networks under energy constraints, however, need to account for the energy spent in checking for feasible routes prior to the acceptance of a message and hence, it is unclear if these algorithms achieve polylogarithmic bounds under this condition. In this work, we address the problem of oblivious routing in sensor networks. We first show that an oblivious routing algorithm cannot have a polylogarithmic competitive ratio without a packet-admission protocol. Then, we present a set of lower bound conditions that prevent any distributed oblivious routing algorithm from being polylogarithmic competitive. We also show two O(log n)-competitive algorithms on tree and grid networks, respectively. At the end, we discuss practical applications of our results. (Joint work with John Augustine)

Biography of Speaker

Mohamed Aly is a PhD candidate at the Computer Science Department of the University of Pittsburgh. He pursues research in both theory and systems. His theoretical research interests lie in approximation and online algorithms, scheduling algorithms, randomized algorithms, combinatorial optimization, and distributed algorithms. Mohamed is mainly am interested in solving algorithmic problems arising in computer systems and communications networks. Application areas he has already worked on include sensor networks, communications networks, and data streams. Mohamed received his bachelor in Computer Science and Engineering (June, 2002) from the Computer Science & Automatic Control Department, Alexandria Faculty of Engineering, Egypt. Before starting his study at Pitt. in August 2004, he worked for two years at the IT Department of the New Library of Alexandria (Bibliotheca Alexandrina, Egypt), where he worked as a software engineer for 6 months then as a systems and network administrator for one and half years.