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.