### Princeton-Rutgers Seminar Series in Information Sciences & Systems

Title: Worst Case Buffer Bounds On Tracking of Arbitrary Fluid
Policies in Switch Networks

Speaker: **Vahid Tarokh**, Harvard University

Date: March 29, 2004, 4:30 - 5:30pm

Location: DIMACS Center, CoRE Bldg, Room 433, Rutgers University, Busch Campus, Piscataway, NJ

Abstract:

In this talk, we will first consider the problem of bounding
the additional buffer size required to packetize fluid policies for
input queued, crossbar switches. We establish universal worst case
bounds that do not depend on the particular distribution of the input
traffic, require no speedup, and guarantee 100% throughput.
Specifically, for an (N x N) input queued, crossbar switch, an on-line
packetizing algorithm is presented that guarantees
100% throughput with a buffer requirement of (N-1)2 packets per input
port with no speedup. Analogous results for (N x 1) and (N x M)
switches will be discussed. We then consider switch networks as the
simplest network examples. A negative result will be discussed
indicating that in contrast to crossbar switches, for a Banyan network
packetizing arbitrary fluid policies with finite backlog requires
speedup. Bounds on the required speedup will be presented. We then
introduce the concept of look-ahead into this problem and for the case
of processor sharing (N x 1 case) , we compute sharp bounds quantifying
the trade-offs between look-ahead, speedup and delay.

This work is based on a number of joint papers with Michael Rosenblum,
Constantine Caramanis, Raymond Yim and Michel Goemans.

Biography:

Vahid Tarokh received the PhD in Electrical Engineering from the
University of Waterloo, Ontario, Canada in 1995. He then worked at AT&T
Labs-Research and AT&T wireless services until August 2000 as member ,
principal memeber of technical staff, and finally the head of the
Department of Wireless Communications and Signal Processing. In
September 2000, he joined Department of EECS at MIT as an associate
professor where he worked until June 2002. Since July 2002, he is
employed by Harvard University as a Professor of electrical engineering.
His research is mostly limited to problems in communications and
networking.