Research Interests

• My research interests span the areas of network and memory algorithms, system architecture, and component design. I have a specific interest in algorithms for packet processing, switching and router design and in the theory and architecture of scalable load balancing systems using high speed memories.
• The following publications are in approximate reverse chronological order.
• The table below is a classification of my research work.

Distributed Algorithms for Buffered Crossbars
(What: How do we use Buffered Crossbars (crossbars with on chip memory) to simplify scheduling?)
(How: Using Distributed Algorithms)

1. ``Practical Algorithms for Performance Guarantees in Buffered Crossbars"
   Shang-Tse Chuang, Sundar Iyer, Nick McKeown.
   To appear in IEEE INFOCOM, 2005.
   Paper: pdf


Note: This paper uses the same mathematical counting technique which has been used in multiple previous papers on packet switching. Please see, "S-T. Chuang, A. Goel, N. McKeown, and B. Prabhakar, Matching Output Queueing with a Combined Input Output Queued Switch., IEEE J. Select. Areas Commun., 17, No. 6, pp. 1030. 1039."


2. ``Attaining Statistical and Deterministic Switching Guarantees using Buffered Crossbars",
   with Shang-Tse Chuang, Nick McKeown.
   In preparation for IEEE/ACM Transactions on Networking.

100% Throughput for Greedy Policies
(What: Can a greedy scheduling policy such as maximum size matching give 100% throughput?)
(How: Using Chernoff Bounds/Lyapunov Functions)

1. (Invited paper) ``Maximum Size Matchings and Input Queued Switches",
   Sundar Iyer, Nick McKeown,
   40th Annual Allerton Conference on Communication, Control, and Computing, Monticello, Illinois, October 2002.
   Paper: pdf, ps

Emulation of OQ Routers
(What: How can we analyze router behaviour so that it behaves exactly like a perfect router?)
(What: How do we identify tradeoff in router design between memory and switching bandwidth?)
(How: Using Constraint Sets/The Pigeonhole Principle)

1. ``Routers with a Single Stage of Buffering",
   Sundar Iyer, Rui Zhang, Nick McKeown
   ACM SIGCOMM, Pittsburgh, USA, Sep. 2002.
   Computer Communication Review, vol. 32, no. 4, Oct 2002.
   Paper: pdf



2. ``Techniques for Fast Shared Memory Switches",
   Sundar Iyer, Nick McKeown
   Stanford University HPNG Technical Report - TR01-HPNG-081501, Stanford, CA, Aug 2001.
   Note: Part of this technical report is subsumed by the Sigcomm paper above.
   Paper: pdf, ps
   
   Note: Regarding papers 1, 2 above, a very nice related and independent work in this area is - A. Prakash, S. Sharif, and A. Aziz, "An O(log^2 N) parallel algorithm for output queuing", IEEE Infocom, New York, NY, June 2002.



3. ``Using Constraint Sets to Achieve Delay Bounds in CIOQ Switches",
   Sundar Iyer, Nick McKeown
   To appear in IEEE Communication Letters, 2003.
   Paper: pdf,

Memory Architectures for Line Cards
(What: Can we build a scalable networking memory architecture which has no "cache" misses?)
(How: Using Difference Equations, adversarial queueing patterns to analyze and build for the worst case)

1. "Designing Buffers for Router Line Cards",
   Sundar Iyer, R. R. Kompella, and Nick McKeown,
   Stanford University HPNG Technical Report - TR02-HPNG-031001, Stanford, CA, Mar. 2002. (Submitted to IEEE/ACM Transactions on Networking, Nov. 2002)
   
   An overview part of this work (only preliminary results and without proofs) was presented as
   "Techniques for Fast Packet Buffers",
   Sundar Iyer, R. R. Kompella, and Nick McKeown,
   IEEE - GBN Workshop, Anchorage, Alaska, April 2001.
   Abstract: ps, pdf, text


Note: A seminal paper, which analyzes the properties of longest queues was first described in, H. Gail, G. Grover, R. Guerin, S. Hantler, Z. Rosberg, M. Sidi, "Buffer size requirements under longest queue first,. Proceedings IFIP'92, vol.C-5, 1992." One of our results (without any pipeline lookahead), has similarities to this result.


2. "Analysis of a Memory Architecture for Fast Packet Buffers",
   Sundar Iyer, R. R. Kompella, and Nick McKeown,
   IEEE - High Performance Switching and Routing, Dallas, Texas, May 2001.
   

Architectures for Statistics and State Maintainence
(What: Can we build a scalable memory architecture for statistics and state maintainence?)
(How: Using Potential Functions to derive sufficient conditions on the architecture)

1. (Invited Paper) "Maintaining Statistics Counters in Line Cards"
   Devavrat Shah, Sundar Iyer, Balaji Prabhakar, and Nick McKeown,
   IEEE Micro, Jan-Feb, 2002
   Paper: pdf
   An earlier and more elaborate version appears in a conference paper as
   "Analysis of a Statistics Counter Architecture" in
   IEEE Hot Interconnects, Stanford University, Aug 2001
   Paper: pdf, ps



2. "Maintaining State on Router Line Cards"
   
Sundar Iyer, Nick McKeown,
In Preparation for IEEE Communication Letters

Deflection Routing
(What: How can we tackle link overload on the backbone?)
(How: Use deflection routing to divert ephemereal overload on parallel/alternate paths)

1. ``An Approach to Alleviate Link Overload as Observed on an IP Backbone",
   Sundar Iyer, Supratik Bhattacharrya, Nina Taft, Christophe Diot,
   IEEE INFOCOM, San Francisco, USA, March 2003.
   Also available as Sprint ATL Technical Report, TR02-ATL-071127, July 2002.
   Paper: pdf



2. ``A Measurement Based Study of Load Balancing on an IP Backbone",
   Sundar Iyer, Supratik Bhattacharrya, Nina Taft, Nick McKeown, Christophe Diot,
   Sprint ATL Technical Report, TR02-ATL-051027, May 2002.

Parallel Packet Switches
(What: Can we build a large router using multiple smaller routers?)
(What: aka. Can we build a large router with memories running slower than the line rate?)
(How: Using Constraint Sets to derive algorithms which prevent blocking in the switch fabric)

1. ``Analysis of the Parallel Packet Switch Architecture",
   Sundar Iyer and Nick McKeown,
   IEEE/ACM Transactions on Networking, April 2003.
   Paper: pdf



2. "The Parallel Packet Switch Architecture",
   (This is a detailed report which subsumes the three PPS papers below)
   Sundar Iyer,
   M. S. Thesis Report, May 2000, Stanford University, Stanford, USA.
   Paper: pdf, ps

1. ``Making parallel packet switches practical",
   Sundar Iyer and Nick McKeown,
   IEEE INFOCOM, Alaska, USA, March 2001.
   Paper: pdf, ps
   Note: A similar practical algorithm on a different switch fabric, was independently described in detail in - C.S. Chang, D.S. Lee and C. M. Lien, "Load balanced Birkhoff-von Neumann switches, part II: multi-stage buffering," Computer Communications, Vol. 25, pp. 623-634, 2002.



2. ``Analysis of a packet switch with memories running slower than the line-rate",
   Sundar Iyer, Amr A. Awadallah, and Nick McKeown,
   IEEE INFOCOM, Tel-Aviv, Israel, March 2000.
   Paper: pdf, ps



3. ``On the speedup required for a multicast parallel packet switch",
   Sundar Iyer and Nick McKeown,
   IEEE Communication Letters, June 2001.
   Paper: pdf, ps

Packet Classification and Content Processing
(What: How can we build a scalable hardware architecture which can support different levels of classification requirements?)
(How: By abstracting the classification primitives in hardware and using parallelism)

1. ``ClassiPI: An Architecture for Fast and Flexible Packet Classification",
   Sundar Iyer, R. R. Kompella and Ajit Shelat,
   IEEE NETWORK, Mar.-Apr. 2001.
   Paper: pdf (submitted version), pdf (printed version)
   Note: Read the submitted version, since some printing errors crept in the printed version),



2. Sundar Iyer, Ajay Desai, Ajay Tambe, Ajit Shelat ``ClassiPI: A Classifier for Next Generation Content/Policy Based Switches.",
   IEEE Hot Chips 12, Stanford, USA. August 2000.