Nick McKeown: Publications

The following papers have been categorized into several areas. Within each area, papers are arranged in reverse chronological order (i.e. most recent first).
Broadly speaking, the categories near the top of the list are of more current interest.
Inevitably, the categorization is not perfect. Some papers belong in more than one area, others belong in none. If you can come up with a better way to categorize them, then let me know.

Distributed and Load-Balanced Switches and Routers

• "Optics inside Routers"
  Nick McKeown
  ECOC 2003, Rimini, Italy, September 2003.
  pdf
• "Scaling Internet Routers Using Optics"
  Isaac Keslassy, ShangTse Chuang, Kyoungsik Yu, David Miller, Mark Horowitz, Olav Solgaard, Nick McKeown
  ACM SIGCOMM Aug. 2003, Karlsruhe, Germany.
  pdf, ps
• "Routers with a Single Stage of Buffering"
  Sundar Iyer, Rui Zhang, and Nick McKeown
  ACM SIGCOMM Aug. 2002, Pittsburgh, USA. Also in Computer Communication Review, vol. 32, no. 4, Oct 2002.
  pdf

Parallel Packet Switches and the Fork Join Router

• "Analysis of the Parallel Packet Switch Architecture"
  Sundar Iyer and Nick McKeown
  To appear in IEEE/ACM Transactions on Networking, April 2003. pdf, ps
• "On the Speedup Required for a Multicast Parallel Packet Switch"
  Sundar Iyer and Nick McKeown
  IEEE Communication Letters, June 2001, vol. 5, no. 6, pp. 269-271. pdf, ps
• "Making Parallel Packet Switches Practical"
  Sundar Iyer and Nick McKeown
  IEEE INFOCOM, Alaska, USA, March 2001, vol. 3, pp. 1680-87. pdf, ps
• "Analysis of a Packet Switch with Memories Running Slower than the Line Rate"
  Sundar Iyer, Amr A. Awadallah, and Nick McKeown
  IEEE INFOCOM March 2000, Tel-Aviv, Israel, pp. 529-537.
  9 pages pdf

Buffering Packets and Memory Architectures

• "Designing Packet Buffers for Router Line Cards"
  Sundar Iyer, R. R. Kompella, and Nick McKeown
  Paper in Submission, October 2002. pdf,
• "Analysis of a Statistics Counter Architecture"
  Devavrat Shah, Sundar Iyer, Balaji Prabhakar, and Nick McKeown
  Hot Interconnects, Stanford, August 2001. pdf, ps
  This paper also appeared as:
  "Maintaining Statistics Counters in Router Line Cards" in IEEE Micro, Jan-Feb 2002, pp. 76-81. pdf
• "Analysis of a Memory Architecture for Fast Packet Buffers"
  Sundar Iyer, Ramana Rao Kompella, and Nick McKeown
  IEEE - High Performance Switching and Routing, Dallas, Texas, May 2001, pp. 368-373. pdf, ps
• "Doubling Memory Bandwidths for Network Buffers"
  Youngmi Joo, and Nick McKeown
  IEEE INFOCOM April 1998, Vol 2, pp. 808-815,  San Francisco.
  8 pages pdf

Packet Lookup and Classification

• "Algorithms for Packet Classification"
  Pankaj Gupta and Nick McKeown
  IEEE Network, March 2001.
  29 pages pdf
• "Dynamic Algorithms with Worst-case Performance for Packet Classification"
  Pankaj Gupta and Nick McKeown
  Proceedings IFIP Networking, May 2000, Paris, France.
  12 pages pdf
• "Packet Classification on Multiple Fields"
  Pankaj Gupta, and Nick McKeown
  ACM SIGCOMM '99, September 1999, Harvard University.
  8 pages pdf
• "Packet Classification using Hierarchical Intelligent Cuttings"
  Pankaj Gupta, and Nick McKeown
  Hot Interconnects VII, August 99, Stanford.
  8 pages pdf.
  This paper is also available here, in IEEE Micro, pp. 34-41, vol. 20, no. 1, January/February 2000.
• "Routing Lookups in Hardware at Memory Access Speeds"
  Pankaj Gupta, Steven Lin, and Nick McKeown
  IEEE INFOCOM April 1998, Vol 3, pp. 1240-1247, San Francisco.
  8 pages pdf

Scheduling and Arbitration Algorithms for Crossbar Switches

• "Using Constraint Sets to Achieve Delay Bounds in CIOQ Switches"
  Sundar Iyer and Nick McKeown
  To appear in IEEE Communication Letters, 2003.
• "Maximum Size Matching and Input Queued Switches"
  Sundar Iyer and Nick McKeown
  Proceedings of the 40th Annual Allerton Conference on Communication, Control and Computing.
  11 pages pdf
• "Maintaining Packet Order in Two-Stage Switches"
  Isaac Keslassy and Nick McKeown
  Proceedings of IEEE INFOCOM '02, New York, June 2002.
  10 pages pdf
• "Analysis of Scheduling Algorithms That Provide 100% Throughput in Input-Queued Switches"
  Isaac Keslassy and Nick McKeown
  Proceedings of the 39th Annual Allerton Conference on Communication, Control, and Computing.
  Monticello, Illinois, October 2001.
  10 pages pdf
• "iSLIP: A Scheduling Algorithm for Input-Queued Switches"
  Nick McKeown
  IEEE Transactions on Networking, Vol 7, No.2, April 1999.
  22 pages pdf
• "Design and Implmentation of a Fast Crossbar Scheduler"
  Pankaj Gupta and Nick McKeown
  Hot Interconnects VI, Stanford University, August 1998.
  Also published in:
  IEEE Micro Magazine, Jan-Feb 1999.
  8 pages pdf
• "Matching Output Queueing with a Combined Input Output Queued Switch"
  Shang-Tse Chuang, Ashish Goel, Nick McKeown, Balaji Prabhakar
  Computer Systems Technical Report CSL-TR-98-758. March 1998.
  Also published in: Proceedings of INFOCOM '99, 1169-1178, IEEE, April 1999, and
  IEEE Journal on Selected Areas in Communications, vol.17, n.6, Dec.1999, pp. 1030-1039.
  17 pages pdf
• "On the Speedup Required for Combined Input and Output Queued Switching."
  Balaji Prabhakar and Nick McKeown
  Computer Systems Technical Report CSL-TR-97-738. November 1997.
  8 pages pdf
  Also published in: Automatica, Vol. 35, no. 12, December 1999
• "ATM Input-Buffered Switches with Guaranteed-Rate Property,"
  Anthony Hung, George Kesidis, and Nick McKeown
  Proc. IEEE ISCC '98, Athens, Jul 1998, pp 331-335
  5 pages pdf
• "A Practical Scheduling Algorithm to Achieve 100% Throughput in Input-Queued Switches."
  Adisak Mekkittikul, and Nick McKeown
  IEEE Infocom 98, Vol 2, pp. 792-799, April 1998, San Francisco.
  8 pages pdf
• "Matching Output Queueing with Combined Input and Output Queueing"
  Nick McKeown, Balaji Prabhakar, and Mingyan Zhu
  Proceedings of the 35th Annual Allerton Conference on
  Communication, Control, and Computing.
  Monticello, Illinois, October 1997.
  10 pages pdf
• "Multicast Scheduling for Input-Queued Switches"
  Rietsh Ahuja, Balaji Prabhakar, Nick McKeown
  IEEE Journal on Selected Areas in Communications, Vol 15, No. 15, pp. 885-866, June 1997.
  20 pages pdf
• "Tetris Models for Multicast Switches"
  Balaji Prabhakar, Nick McKeown and Jean Mairesse
  Proceedings of the Princeton Conference, Princeton, March 1996.
  6 pages pdf
• "Scheduling Multicast Cells in an Input-Queued Switch"
  Nick McKeown and Balaji Prabhakar
  Proceedings of IEEE Infocom '96, San Francisco, Vol 1, pp. 271-278, March 1996.
  11 pages pdf
• "A Starvation-free Algorithm for Achieving 100% Throughput in an Input-Queued Switch"
  Adisak Mekkittikul and Nick McKeown
  ICCCN '96, pp. 226-231, October 1996.
  6 pages pdf
• "Designing a Multicast Switch Scheduler"
  Balaji Prabhakar and Nick McKeown
  Proceedings of the 33rd Annual Allerton Conference on
  Communication, Control, and Computing. pp. 984-993.
  Monticello, Illinois, October 1995.
  10 pages pdf
• "Achieving 100% Throughput in an Input-Queued Switch (Extended Version)"
  Nick McKeown, Adisak Mekkittikul, Venkat Anantharam and Jean Walrand
  IEEE Transactions on Communications, Vol.47, No.8, August 1999.
  22 pages pdf
• "Achieving 100% Throughput in an Input-Queued Switch"
  Nick McKeown, Venkat Anantharam and Jean Walrand
  Proceedings of IEEE Infocom '96, Vol 1, pp. 296-302, San Francisco, March 1996.
  7 pages pdf
• "A Quantitative Comparison of Scheduling Algorithms for Input-Queued Switches"
  Nick McKeown and Thomas E. Anderson
  Computer Networks and ISDN Systems, Vol 30, No 24, pp 2309-2326, December 1998.
  16 pages pdf
• "8 Tb/s ATM Interconnection through optical WDM networks"
  Adisak Mekkittikul, D. Sadot, L.G. Kazovsky, Nick McKeown
  High-Speed Semiconductor Laser Sources, San Jose, CA, Vol. 2684, pp. 186-98, 1-2 February, 1996.
• "8 Tb/s ATM Interconnection through optical WDM networks"
  Adisak Mekkittikul, D. Sadot, L.G. Kazovsky, Nick McKeown; Proceedings of the SPIE 96, Vol. 2684, pp. 186-98, February 1996.
• "A Fast Scheduling Algorithm for Input-Queued Switches"
  Nick McKeown, Jean Walrand
  Proceedings of 7th IEEE LAN/MAN Workshop, Florida, March 1995.
• "Scheduling Algorithms for Input-Queued Cell Switches"
  Nick McKeown
  PhD Thesis, University of California at Berkeley, May 1995.
  WHOLE THESIS (119 pages): pdf
  Part 1: pdf
  Part 2: pdf
  Part 3: pdf
  Part 4: pdf
  Part 5: pdf
• "Scheduling Non-uniform Traffic in High Speed Packet Switches and Routers"
  Adisak Mekkittikul
  PhD Thesis (181 pages), Stanford University, November 1998. pdf
• "Scheduling Cells in an Input-Queued Switch"
  Nick McKeown, Pravin Varaiya, and Jean Walrand
  IEE Electronics Letters, Dec 9th 1993, pp.2174-5
  4 pages ps

The Tiny Tera A Small, High Bandwidth Network Switch

• "A 50 Gb/s 32*32 CMOS crossbar chip using asymmetric serial links"
  Kun-Yung Ken Chang, Shang-Tse Chuang, McKeown, N., Horowitz, M.
  1999 Symposium on VLSI Circuits. Digest of Technical Papers, page 19.
• "The Tiny Tera: A Packet Switch Core"
  Nick McKeown, Martin Izzard, Adisak Mekkittikul, Bill Ellersick and Mark Horowitz
  Hot Interconnects V, Stanford University, August 1996.
  Also appeared in: IEEE Micro Jan/Feb 1997, pp 26-33.
  13 pages pdf
• "A 2 Gb/s Asymmetric Serial Link for High-Bandwidth Packet Switches"
  Ken K.-Y. Chang, William Ellersick, Shang-Tse Chuang, Stefanos Sidiropoulos, Mark Horowitz, Nick McKeown
  Hot Interconnects VI, pp. 171-179, Stanford University, August 1997.
  9 pages pdf
• "The Tiny Tera: A Small High-Bandwidth ATM Switch"
  Nick McKeown, Martin Izzard, Adisak Mekkittikul;
  Proceedings of SPIE 96, Vol. 2917, pp. 387-397, Boston, November 1996.
• "The Tiny Tera: A Small High-Bandwidth Packet Switch Core"
  Nick McKeown, Martin Izzard, Adisak Mekkittikul, Bill Ellersick, Mark Horowitz
  Proceedings of Hot Inteconnects IV, pp. 161-173, Stanford, August 1996.

Other papers on Switches and Routers

• "The performance of circuit switching in the Internet"
  Pablo Molinero-Fernández, Nick McKeown
  OSA Journal of Optical Networking, Vol. 2, No. 4, March 2003
  14 pages pdf
• "Is IP going to take over the world (of communications)?"
  Pablo Molinero-Fernández, Nick McKeown, Hui Zhang
  HotNets-I, Princeton, NJ, October 2002
  Also appeared in ACM Computer Communications Review, Vol. 33, No. 1, January 2003
  6 pages pdf
• "TCP Switching: Exposing circuits to IP"
  Pablo Molinero-Fernández, Nick McKeown
  IEEE Micro, Vol. 22, No. 1, Jan/Feb 2002
  8 pages pdf
• "TCP Switching: Exposing circuits to IP"
  Pablo Molinero-Fernández, Nick McKeown
  Hot Interconnects IX, Stanford University, August 2001
  6 pages ps , pdf
• "A Fast Switched Backplane for a Gigabit Switched Router"
  Nick McKeown
  Business Communications Review, December 1997. html
• "A Simulation Study of IP Switching"
  Steven Lin, and Nick McKeown
  Proceedings of ACM Sigcomm, September 1997.
  10 pages pdf
• "Output-buffer ATM Packet Switching for Integrated-Services Communication Networks"
  George Kesidis, and Nick McKeown
  Presented at ICC '97, Montreal, Canada, Aug 1997.
  5 pages pdf
• "The Bay Bridge: A High Speed Bridge/Router"
  Nick McKeown, Richard Edell, and My T. Le
  IFIP Workshop, Stockholm, Sweden, 1992.
  18 pages pdf
• "Architecture and Performance of The BayBridge: A High Speed Bridge/Router between FDDI and SMDS"
  Nick McKeown, Richard Edell, and My T. Le
  29 pages pdf
• "A High Performance SMDS Interface at STS-3c Rate"
  My T. Le, Nick McKeown, and Richard Edell
  22 pages pdf

 

Other miscellaneous papers

• "Monitoring very high speed links"
  G. Iannaccone, C. Diot, I. Graham, N. McKeown.
  ACM Sigcomm Internet Measurement Workshop IMW 2001, California 2001.
  8 pages pdf
• "Congestion Control and Periodic Behavior"
  Anna Gilbert, Youngmi Joo and Nick McKeown.
  Presented at LANMAN Workshop 2001.
  11 pages pdf
• "Billing Users and Pricing for TCP"
  Richard Edell, Nick McKeown, and Pravin Varaiya
  IEEE JSAC Special Issue on Advances in the Fundamentals of Networking
  September 1995.
  14 pages pdf
• "Xdistribute: A Process Distribution System"
  Karl Petty, and Nick McKeown
  9 pages pdf
• "Automatic Vehicle Control Developments in the PATH Program"
  Steven E. Schladover, Charles A. Desoer, J. Karl Hedrick, Masayoshi Tomizuka, Jean Walrand, Wei-Bin Zhang, Donn H. McMahon, Huei Peng, Shahab Sheikholeslam and Nick McKeown
  IEEE Transactions on Vehicular Technology, Vol. 40, No.1, pp. 114-130, February 1991.