Tracey Ho

Bell Laboratories, Murray Hill, NJ

Abstract: Allowing coding across different information streams in a network, i.e. network coding, has been shown to offer advantages in terms of capacity and decentralized operation.  In this talk, we present new approaches for setting up network codes on general cyclic graphs.  These allow distributed asynchronous operation (for multi-source multicast) and online operation (for multiple unicasts). Our multicast algorithms attain an intermediate point in the trade-off between reducing coordination and optimizing resource usage, the extremes of which are given by existing centralized/synchronous iterative

approaches and completely decentralized random approaches.  Our algorithms find an acyclic subset of connections between links, and set up a network code over these connections.  Our approach for multiple unicast sessions considers the sessions one at a time, and decides whether and how to phase each in, possibly by coding with existing sessions. Throughput-competitiveness is shown, extending the results of Awerbuch et al. on online routing.Portions of this work have been done jointly with Ralf Koetter, Ben Leong, Muriel Medard and Niranjan Ratnakar.

Bio: Tracey Ho is a postdoctoral associate at the Wireless Research Laboratory, Bell Laboratories.  She received a Ph.D. in Electrical Engineering and Computer Science in 2004 from the Massachusetts Institute of Technology, where she also received Bachelor's and Master's degrees. She will be joining the Caltech faculty in fall 2005. Her research interests are in network coding, networking, distributed/autonomous systems, coding and information theory, and machine learning.

T. Ho, R. Koetter, M. Médard, M. Effros, J. Shi, and D. Karger, "Toward a Random Operation of Networks", IEEE Transactions on Information Theory, submitted.

T. Ho, M. Médard, R. Koetter, "An Information Theoretic View of Network Management", IEEE Transactions on Information Theory, to appear.