Looking at Large Networks: Coding vs. Queueing

Speaker: Dr. Sanjay Shakkottai, University of Texas, Austin

Traditionally, network buffer resources have been used at routers to queue transient packets to prevent packet drops. In contrast, we propose a scheme for large multi-hop networks where intermediate routers have no buffers for queueing transient packets. In the proposed scheme, network storage resources (memory) are used only at source and destination nodes to encode/decode packets using random linear coding over time. Our scheme utilizes the observation that for large networks with many flows through each router, if packet loss occurs in a flow path, it will very likely occur only at only one link in the path. Unfortunately, the location of this congested link varies with time, hence, preventing static buffer allocation strategies from exploiting this observation. We propose network coding as a means of "sharing" memory across links along a flow path.
We call this spatial buffer multiplexing -- where buffering and coding implemented at the source compensates for packet loss at any downstream bufferless link. Using many-sources large deviations analysis, we show that to obtain comparable packet drop probabilities (QoS), spatial buffer multiplexing requires much less buffers as compared to traditional queueing.


Sanjay Shakkottai received his Ph.D. from the University of Illinois at Urbana-Champaign in 2002. He is currently with The University of Texas at Austin, where he is an Assistant Professor in the Department of Electrical and Computer Engineering. He received the NSF CAREER award in 2004. His research interests include wireless and sensor networks, stochastic processes and queueing theory.

Presented On: March 16th, 2007
Video: Click here to see the video