Sundar Iyer: Publications


Research Interests

  • My current research interests span the areas of algorithms, networking, symbolic analysis, and distributed systems. Past interests include embedded system architecture, and memory algorithms and architectures for high performance ASIC/SoC design. The following publications are in approximate reverse chronological order. The table below is a classification of my research work.

 
Publications - Network Architecture
 

Algorithms for
Embedded Memory 		Algorithmic Memory Memory Certification  
An Analytical Framework
for Router Architectures 		Parallel Packet Switches Emulation of OQ Routers  
Deterministic Achitectures
for Packet Processing 		Memory Architectures
for Line Cards 		Memory Architectures for Statistics
and State Maintainence 		Packet Classification
and Content Processing
Greedy/Distributed Algorithms
for Packet Switching 		Greedy Policies Distributed Algorithms
for Buffered Crossbars 		 
Algorithms for
Internet Routing 		Deflection Routing    

Algorithms for Memory Performance
(What: How do we speedup embedded memory?)
(How: Using Algorithmic Memory)



  1. ``Algorithmic Memory: An Order of Magnitude Performance Increase for Next Generation SoC”
    Sundar Iyer, Shang-Tse Chuang,
    DesignCon, Jan. 2012.
    Paper: pdf,
    2. Note: This is the main paper which expostulates some of the work done at Memoir, and is available as an Industry conference publication. Most of the work and the follow on work is unpublished in Academic literature, as its owned by Memoir (now Cisco).

  2. ``Versatile Refresh: LowComplexity Refresh Scheduling for High-throughput Multi-banked eDRAM”
    Mohammad Alizadeh, Adel Javanmard, Shang-Tse Chuang, Sundar Iyer, Yi Lu
    SIGMETRICS, June 2012.
    3. Paper: pdf,

Algorithms for Memory Certification
(What: How do we certify memory?)
(How: Using techniques to reduce testing effort)



  1. ``MemSecure: Enabling Orders of Magnitude Reduction in Embedded Memory Certification and Trust Effort”
    Kartik Mohanram, Sundar Iyer
    GOMAC Tech, Mar. 2013.
    2. Paper: pdf,

  2. ``MemPack: An Order of Magnitude Reduction in the Cost, Risk, and Time for Memory Compiler Certification”
    Kartik Mohanram, Mathew Wartell, Sundar Iyer
    DATE, Mar. 2013.
    Paper: pdf,


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
    2. 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
    2. 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"
    3. 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)

(Note: The 'Complete' Reports were written after completion of the PPS papers, whereas the 'partial' reports were papers which were submitted when the PPS project was in progress)

Complete Reports
  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


Partial Reports
  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.

Last modified: Thu Apr 2nd 19:07:03 PDT 2015