April 22, 2004, 3pm, Douglas Auditorium
"Loop-free routing in Ad-hoc Networks using Labels"
J.J. Garcia-Luna-Aceves, UCSC

In this talk I will introduce the concept of "feasible labels" as a tool to maintain loop-free routing in computer networks, and ad hoc networks in particular. Using such labels eliminates the need to use either sequence numbers or source-routed data packets like AODV and DSR do, respectively. As an example, I present the Feasible Label Routing (FLR) protocol for mobile ad hoc networks, which uses path information to establish routes to destinations on demand. FLR enables loop-free incremental (hop-by-hop) routing of data packets using only the addresses of their destinations.  Instantaneous loop freedom is attained by using path information for a destination as labels with which routers are ordered lexicographically with respect to the destination, i.e., FLR ensures that the labels of routers for a given destination become ``smaller'' the closer they are to the destination. Simulation experiments in Qualnet show that the performance of FLR is far better than the performance of the ad-hoc on-demand distance vector (AODV) protocol, the dynamic source routing (DSR) protocol, and the optimized link state routing (OLSR) protocol, in terms of the packet delivery ratio and average delivery latencies achieved, as well as the overhead incurred in the network.


J.J.  Garcia-Luna-Aceves received the M.S. and Ph.D. degrees in electrical engineering from the University of Hawaii, Honolulu, HI, in 1980 and 1983, respectively.  He is the Baskin Professor of Computer Engineering at the University of California, Santa Cruz (UCSC). Dr. Garcia-Luna-Aceves directs the Computer Communication Research Group (CCRG), which is part of the Information Technologies Institute of the Baskin School of Engineering at UCSC.  He has been a Visiting Professor at Sun Laboratories and a consultant on protocol design for Nokia.  Prior to joining UCSC in 1993, he was a Center Director at SRI International (SRI) in Menlo Park, California.

Dr. Garcia-Luna-Aceves has published a book and more than 250 refereed papers and three U.S patents, and has directed more than 18 Ph.D. theses at UCSC.  He has been Program Co-Chair of ACM MobiHoc 2002 and ACM Mobicom 2000; Chair of the ACM SIG Multimedia; General Chair of ACM Multimedia '93 and ACM SIGCOMM '88; and Program Chair of IEEE MULTIMEDIA '92, ACM SIGCOMM '87, and ACM SIGCOMM '86. He has served in the IEEE Internet Technology Award Committee, the IEEE Richard W. Hamming Medal Committee, and the National Research Council Panel on Digitization and Communications Science of the Army Research Laboratory Technical Assessment Board.  He has been on the editorial boards of the IEEE/ACM Transactions on Networking, the Multimedia Systems Journal, and the Journal of High Speed Networks. He received the SRI International Exceptional-Achievement Award in 1985 and 1989, and is a senior member of the IEEE.