Bibliography:

1a. General Textbooks, Overviews, Surveys

• S. Keshav: "An Engineering Approach to Computer Networking", Addison Wesley, 1997, ISBN 0-201-63442-2;
• Jose Duato, S. Yalamanchili, L. Ni: "Interconnection Networks: an Engineering Approach" Morgan Kaufmann Publishers, 2002 (or newer edition in 2003?), ISBN 1-55860-852-4 www.mkp.com/books_catalog/catalog.asp?ISBN=1-55860-852-4
• F. Tobagi: "Fast Packet Switch Architectures for Broadband Integrated Services Networks", IEEE Proceedings, vol. 78, no. 1, Jan. 1990, pp. 133-167.

1b. Network Traffic Characterization

• C. Shannon, D. Moore, K. Claffy: "Beyond Folklore: Observations on Fragmented Traffic", IEEE/ACM Trans. on Networking, vol. 10, no. 6, Dec. 2002, pp. 709-720. [Measurements of IP packet sizes, before and after fragmentation].
• F. Fitzek, M. Reisslein: "MPEG-4 and H.263 Video Traces for Network Performance Evaluation", IEEE Network Magazine, vol. 15, no. 6, Nov./Dec. 2001, pp. 40-54.

2. Input and Output Queueing Performance Analysis

• M. Karol, M. Hluchyj, S. Morgan: "Input versus Output Queueing on a Space-Division Packet Switch", IEEE Trans. on Communications, vol. 35, no. 12, Dec. 1987, pp. 1347-1356 (an early paper; their next-year paper, below, contains almost a superset of these results, so, if reading/referencing a single paper, the next one is preferable).
• M. Hluchyj, M. Karol: "Queueing in High-Performance Packet Switching", IEEE Journal on Sel. Areas in Commun. (JSAC), vol. 6, no. 9, Dec. 1988, pp. 1587-1597.
• J. Hui, E. Arthurs: "A Broadband Packet Switch for Integrated Transport", IEEE Journal on Sel. Areas in Commun. (JSAC), vol. 5, no. 8, Oct. 1987, pp. 1264-1273.

• Y. Yeh, M. Hluchyj, A. Acampora: "The Knockout Switch: a Simple, Modular Architecture for High-Performance Packet Switching", IEEE Jour. Sel. Areas in Communications, vol. 5, no. 8, Oct. 1987, pp. 1274-1283.

3. Off-Line Crossbar Scheduling:

• See Exercise Set 2.
• M. Bonuccelli, I. Gopal, C. Wong: "Incremental Time-Slot Assignment in SS/TDMA Satellite Systems", IEEE Trans. Communications, vol. 39, no. 7, July 1991, pp. 1147-1156.
• I. Gopal, D. Coppersmith, C. Wong: "Minimizing Packet Waiting Time in a Multibeam Satellite System", IEEE Trans. Communications, vol. 30, 1982, pp. 305-316.
• T. Inukai: "An Efficient SS/TDMA Time Slot Assignment Algorithm", IEEE Trans. Communications, vol. 27, Oct. 1979, pp. 1449-1455.
• T. Rodeheffer, J. Saxe: "Smooth Scheduling in a Cell-Based Switching Network", DEC SRC Research Report #150, Feb. 1998.

4. On-Line Crossbar Scheduling:

• 2D RR:
  R. LaMaire, D. Serpanos: "Two-Dimensional Round-Robin Schedulers for Packet Switches with Multiple Input Queues", IEEE/ACM Trans. on Networking, vol. 2, no. 5, Oct. 1994, pp. 471-482.
• PIM:
  T. Anderson, S. Owicki, J. Saxe, C. Thacker: "High-Speed Switch Scheduling for Local-Area Networks", ACM Trans. on Computer Systems, vol. 11, no. 4, Nov. 1993, pp. 319-352.
• iSLIP, Tiny Tera:
  N. McKeown, M. Izzard, A. Mekkittikul, W. Ellersick, M. Horowitz: "Tiny Tera: a Packet Switch Core", IEEE Micro, Jan.-Feb. 1997, pp. 26-33.
  P. Gupta, N. McKeown: "Designing and Implementing a Fast Crossbar Scheduler", IEEE Micro, Jan.-Feb. 1999, pp. 20-28.
  Nick McKeown: "The iSLIP Scheduling Algorithm for Input-Queued Switches", IEEE/ACM Trans. on Networking, vol. 7, no. 2, April 1999, pp. 188-201; available on-line at: http://tiny-tera.stanford.edu/~nickm/papers/ToN_April_99.pdf
• FIRM:
  D. Serpanos, P. Antoniadis: "FIRM: a Class of Distributed Scheduling Algorithms for High-Speed ATM Switches with Multiple Input Queues", IEEE Infocom 2000 Conference, Tel Aviv, Israel, March 2000.
• Multicast:
  R. Ahuja, B. Prabhakar, N. McKeown: "Multicast Scheduling for Input-Queued Switches", IEEE Jour. Sel. Areas in Communications, vol. 15, no. 5, June 1997, pp. 855-866; available on-line at: http://tiny-tera.stanford.edu/~nickm/papers/IEEE_JSAC_MAY_96.pdf
• With QoS Guarantees:
  Anthony Kam, Kai-Yeung Siu: "Linear-Complexity Algorithms for QoS Support in Input Queued Switches with No Speedup", IEEE Jour. Sel. Areas in Communications, vol. 17, no. 6, June 1999, pp. 1040-1056.
• Off-Line, with QoS Guarantees:
  See the Rodeheffer and Saxe paper in the previous category: DEC SRC Research Report #150.

5. Speedup Required to Emulate Output Queueing:

• S. Chuang, A. Goel, N. McKeown, B. Prabhakar: "Matching Output Queueing with a Combined Input Output Queued Switch", IEEE Jour. Sel. Areas in Communications, vol. 17, no. 6, June 1999, pp. 1030-1039; Stanford CSL-TR-98-758, on-line: http://elib.stanford.edu
• P. Krishna, N. Patel, A. Charny, R. Simcoe: "On the Speedup Required for Work-Conserving Crossbar Switches", IEEE J. Sel. Areas in Communications, vol. 17, no. 6, June 1999, pp. 1057-1066.
• S. Iyer, N. McKeown: "Making Parallel Packet Switches Practical", IEEE INFOCOM Conf., Alaska, USA, March 2001; available on-line through http://tiny-tera.stanford.edu/~nickm/papers/ in PDF or Postscript.
  Background paper: S. Iyer, A. Awadallah, N. McKeown: "Analysis of a Packet Switch with Memories Running Slower than the Line Rate", IEEE INFOCOM Conf., Tel-Aviv, Israel, March 2000; available on-line through http://tiny-tera.stanford.edu/~nickm/papers/ in PDF.

6. Switching Fabric Topologies

• M. Marcus: "The Theory of Connecting Networks and their Complexity: a Review", IEEE Proceedings, vol. 65, no. 9, Sep. 1977, pp. 1263-1271. [An excellent survey of old-known fabric topologies, mostly from the telephony era].
• [See also the general overview and survey paper listed earlier:] F. Tobagi: "Fast Packet Switch Architectures for Broadband Integrated Services Networks", IEEE Proceedings, vol. 78, no. 1, Jan. 1990, pp. 133-167.
• Section 5.6 ("Batcher-Banyan Switches") from the book: C. Partridge: "Gigabit Networking", Addison-Wesley, 1994, ISBN 0-201-56333-9.
• Sections 12.1 ("Switch Performance Measures"), 12.2 ("Time- and Space-Division Switching"), and 12.3 ("Modular Switch Designs") from the book: J. Walrand, P. Varaiya: "High Performance Communication Networks", Morgan Kaufmann, 2nd edition, Oct. 1999, ISBN 1-55860-574-6.
• C.-L. Wu, T.-Y. Feng: "On a Class of Multistage Interconnection Networks", IEEE Trans. on Computers, vol. 29, no. 8, Aug. 1980, pp. 694-702. [Reviews the banyan, omega, indirect binary n-cube, and flip networks, and proves their topological equivalence].
• C. Leiserson: "Fat-Trees: Universal Networks for Hardware-Efficient Supercomputing", IEEE Trans. on Computers, vol. 34, no. 10, Oct. 1985, pp. 892-901.
• V. Benes: "Optimal Rearrangeable Multistage Connecting Networks", Bell Systems Technical Journal, vol. 43, no. 7, July 1964, pp. 1641-1656.
• K. Batcher: "Sorting Networks and their Applications", AFIPS Proc. 1968 Spring Joint Computer Conf., vol. 32, 1968, pp. 307-314.

7. Bufferless, Self-Routing Fabrics and Deflection Routing

• F. Tobagi, T. Kwok, F. Chiussi: "Architecture, Performance, and Implementation of the Tandem Banyan Fast Packet Switch", IEEE Jour. Sel. Areas in Communications, vol. 9, no. 8, Oct. 1991, pp. 1173-1193.
• A. Huang, S. Knauer: "Starlite: A Wideband Digital Switch", Proc. IEEE GLOBECOM '84 Conf., Atlanta GA USA, Dec. 1984, pp. 121-125.
• J. Giacopelli, J. Hickey, W. Marcus, W. Sincoskie, M. Littlewood: "Sunshine: a High Performance Self-Routing Broadband Packet Switch Architecture", IEEE Jour. Sel. Areas in Communications, vol. 9, no. 8, Oct. 1991, pp. 1289-1298.
• T. Lee: "Nonblocking Copy Networks for Multicast Packet Switching", IEEE Jour. Sel. Areas in Communications, vol. 6, no. 9, Dec. 1988, pp. 1455-1467.

8. Buffered Switching Fabrics with Internal Backpressure

• Early, communications-oriented switches with single-lane backpressure:
  • J. Turner: "Design of an Integrated Services Packet Network", IEEE Jour. Sel. Areas in Communications, vol. 4, no. 8, Nov. 1986, pp. 1373-1380. [Proposes a banyan or Benes fabric with small buffers in each switching element, and single-lane backpressure in the fabric].
  • J. Turner: "Design of a Broadcast Packet Switching Network", IEEE Trans. on Communications, vol. 36, no. 6, June 1988, pp. 734-743. [Adds multicast to the previous design].
• Wormhole routing for multiprocessor interconnection networks with "virtual channel" (multi-lane) backpressure:
  • W. Dally, C. Seitz: "Deadlock-Free Message Routing in Multiprocessor Interconnection Networks", IEEE Trans. on Computers, vol. 36, no. 5, May 1987, pp. 547-553. [Introduces wormhole routing: switches contain buffering and use backpressure; variable-size packets are segmented into flits; virtual channel backpressure to avoid deadlocks].
  • W. Dally: "Virtual-Channel Flow Control", IEEE Tran. on Parallel and Distributed Systems, vol. 3, no. 2, March 1992, pp. 194-205. Earlier version: 17th Int. Symp. on Computer Architecture (ISCA), ACM SIGARCH, Seattle WA USA, May 1990, pp. 60-68. [Uses virtual channel (multi-lane) backpressure to improve performance (reduce HOL blocking effects); simulates banyan wormhole routing networks].
  • Li-Shiuan Peh, W. Dally: "Flit-Reservation Flow Control", Proc. Int. Symp. on High-Perf. Comp. Arch. (HPCA), 2000.
• Buffered Crossbar with CIOQ, backpressure, and WFQ:
  • D. Stephens, Hui Zhang: "Implementing Distributed Packet Fair Queueing in a Scalable Switch Architecture", IEEE INFOCOM'98 Conference, available on line through http://www-2.cs.cmu.edu/People/hzhang/publications.html in ps.gz or in pdf.
• Lucent's ATLANTA chip set (3-stage buffered switching fabric with internal backpressure):
  • F. Chiussi, J. Kneuer, V. Kumar: "Low-Cost Scalable Switching Solutions for Broadband Networking: The ATLANTA Architecture and Chip Set", IEEE Communications Magazine, vol. 35, no. 12, December 1997, pp. 44-53.
• The ATLAS I (credit-based) multi-lane backpressure protocol (a considerable improvement over virtual channel wormhole backpressure):
  • M. Katevenis, D. Serpanos, E. Spyridakis: "Switching Fabrics with Internal Backpressure using the ATLAS I Single-Chip ATM Switch", Proceedings of the IEEE GLOBECOM'97 Conference, Phoenix, AZ USA, Nov. 1997, pp. 242-246; available on-line at http://archvlsi.ics.forth.gr/atlasI/, in Postscript (230 KBytes), or gzip'ed Postscript (53 KBytes). A longer version with more details appeared in the Proceedings of HPCA-4 (4th IEEE Int. Symposium on High-Performance Computer Architecture), Las Vegas, NV USA, Feb. 1998, pp. 47-56, by the same authors and under the title "Credit-Flow-Controlled ATM for MP Interconnection: the ATLAS I Single-Chip ATM Switch", available on-line in Postscript (230 KBytes), or gzip'ed Postscript (58 KBytes). [Presents the protocol, its simulation results, and explains the reasons for the improved performance].
  • G. Kornaros, D. Pnevmatikatos, P. Vatsolaki, G. Kalokerinos, C. Xanthaki, D. Mavroidis, D. Serpanos, M. Katevenis: "Implementation of ATLAS I: a Single-Chip ATM Switch with Backpressure", Proc. IEEE Hot Interconnects 6 Symposium, Stanford, California, USA, 13-15 August 1998, pp. 85-96; http://archvlsi.ics.forth.gr/atlasI/hoti98/ . An abbreviated version of this appeared in IEEE Micro, vol. 19, no. 1, Jan/Feb. 1999, pp. 30-41, by the same authors and under the title "ATLAS I: Implementing a Single-Chip ATM Switch with Backpressure". [Contains a cost and benefit evaluation of the ATLAS I backpressure mechanism].
• Hop-by-Hop Credit-Based (Multi-Lane Backpressure) Flow Control:
  • C. Ozveren, R. Simcoe, G. Varghese: "Reliable and Efficient Hop-by-Hop Flow Control", IEEE Journal on Sel. Areas in Communications, vol. 13, no. 4, May 1995, pp. 642-650.
  • Quantum Flow Control Alliance: "Quantum Flow Control: A cell-relay protocol supporting an Available Bit Rate Service", version 2.0, July 1995; www.qfc.org
  • H.T. Kung, T. Blackwell, A. Chapman: "Credit-Based Flow Control for ATM Networks: Credit Update Protocol, Adaptive Credit Allocation, and Statistical Multiplexing", Proceedings of the ACM SIGCOMM '94 Conference, London, UK, Aug.-Sep. 1994, pp. 101-114.
  • M. Katevenis: "Fast Switching and Fair Control of Congested Flow in Broad-Band Networks", IEEE Journal on Selected Areas in Communications, vol. 5, no. 8, Oct. 1987, pp. 1315-1326.

9. Inverse Multiplexing and Packet Resequencing

• J. Duncanson: "Inverse Multiplexing", IEEE Communications Magazine, vol. 32, no. 4, April 1994, pp. 34-41.
• F. Chiussi, D. Khotimsky, S. Krishnan: "Generalized inverse multiplexing for switched ATM connections", Proc. IEEE GLOBECOM Conf., Sydney, Australia, Nov 1998, pp. 3134-3140; available on-line through Bell Labs Data Networking Systems Research in .ps format.
• D. Khotimsky: "A packet resequencing protocol for fault-tolerant multipath transmission with non-uniform traffic splitting", Proc. IEEE GLOBECOM Conf., Rio de Janeiro, Brasil, Dec 1999, pp. 1283-1289; available on-line through Bell Labs Data Networking Systems Research in .ps format.

10. Packet-Dropping Flow Control: Buffer Management

• M. Arpaci, J. Copeland: "Buffer Management for Shared-Memory ATM Switches", IEEE Communications Surveys, Vol. 3, No. 1, First Quarter 2000.
• S. Floyd, V. Jacobson: "Random Early Detection Gateways for Congestion Avoidance", IEEE/ACM Trans. on Networking, vol. 1, no. 4, Aug. 1993, pp. 397-413.
• B. Suter, T. Lakshman, D. Stiliadis, A. Choudhury: "Buffer Management Schemes for Supporting TCP in Gigabit Routers with Per-Flow Queueing", IEEE Jour. Sel. Areas in Communications, vol. 17, no. 6, June 1999, pp. 1159-1169.

11. Weighted Round-Robin Scheduling

• Hui Zhang: "Service Disciplines For Guaranteed Performance Service in Packet-Switching Networks", Proceedings of the IEEE, vol. 83, no. 10, October 1995; available on line through http://www-2.cs.cmu.edu/People/hzhang/publications.html in ps.gz or in pdf.
• D. Stephens, J. Bennett, Hui Zhang: "Implementing Scheduling Algorithms in High-Speed Networks", IEEE Jour. Sel. Areas in Communications, vol. 17, no. 6, June 1999, pp. 1145-1158 (available on line as above). [Uses a menu of discrete rates, groups together all flows of similar rate, and performs WRR among the groups and RR within the groups; for fixed-size packets, a similar method was independently proposed in:]
  • M. Katevenis e.a.: "Multi-Queue Management and Scheduling for Improved QoS in Communication Networks", Proc. EMMSEC'97 Florence, Italy, Nov. 1997, pp. 906-913; http://archvlsi.ics.forth.gr/muqpro/classSch.html
• Several more publications by Hui Zhang e.a.: see http://www-2.cs.cmu.edu/People/hzhang/publications.html#scheduling
• F. Chiussi, A. Francini: "A Distributed Scheduling Architecture for Scalable Packet Switches", IEEE Jour. Sel. Areas in Communications, vol. 18, no. 12, December 2000, pp. 2665-2683.
• A. Ioannou, M. Katevenis: "Pipelined Heap (Priority Queue) Management for Advanced Scheduling in High Speed Networks", Proc. IEEE Int. Conf. on Communications (ICC'2001), Helsinki, Finland, June 2001, pp. 2043-2047; http://archvlsi.ics.forth.gr/muqpro/heapMgt.html

12. Wormhole IP over ATM

13. Routing Table Lookup, Flow Classification

• Andreas Moestedt, Peter Sjodin: "IP Address Lookup in Hardware for High-Speed Routing", Proc. IEEE Hot Interconnects 6 Symposium, Stanford, California, USA, August 1998, pp. 31-39; available on-line at: http://www.sics.se/~am/HotI.ps
• P. Gupta, N. McKeown: "Packet Classification on Multiple Fields", ACM SIGCOMM '99 Conference, Harvard Univ., Sept. 1999, pp. 147-160; available on-line at: http://tiny-tera.stanford.edu/~nickm/papers/Sigcomm99.pdf
• T. Lakshman, D. Stiliadis: "High-Speed Policy-based Packet Forwarding using Efficient Multi-Dimensional Range Matching", ACM SIGCOMM '98 Conference, Vancouver, BC, Canada, Sept. 1998, pp. 203-214.
• M. O'Connor, C. Gomez (Silicon Access Networks): "The iFlow Address Processor", IEEE Micro Magazine, March-April 2001, pp. 16-23.
• D. Shah, P. Gupta: "Fast Updating Algorithms for Ternary CAM's", IEEE Micro, Jan.-Feb. 2001, pp. 36-47.
• IEEE Network Magazine, March-April 2001: a collection of 3 articles on the topic:
  • P. Gupta, N. McKeown: "Algorithms for Packet Classification", pp. 24-32 (looks more detailed and more recent than previous articles of theirs, incl. IEEE Micro of Jan-Feb. 2000 and perhaps SIGCOMM'99).
  • PMC-Sierra, pp. 33-41 (describes a hardware architecture)
  • M. Ruiz-Sanchez, E. Biersack, W. Dabbous: "Survey and Taxonomy of IP Address Lookup Algorithms", pp. 8-23 (detailed; mostly tree-based longest-prefix algorithms).
• Pankaj Gupta has founded a company, Sahasra Networks, to commercialize his research. A newspaper-style article on it can be found at http://www.lightreading.com/document.asp?site=lightreading&doc_id=7661.

14. Network Processors

• NP1: 1st Workshop on Network Processors (in conjunction with HPCA 8).
• "NP Summit" held during Networld+Interop, May 2000 (see e.g. "What is a NP" by Vitesse).
• ... more links to be added....
• Intel Network Processors.
• IBM PowerNP Network Processors
• Motorola/C-Port "C-5" Network Processor: summary page, Data Sheet (PDF).

• Example 1: Altera Stratix (FPGA + Memory + DSP + High Speed I/O + off-chip RAM interfaces).
• Example 2: Altera Excalibur (FPGA + Embedded Processor).

15. Cluster, System, and smaller Area Networks

• Infiniband
• VIA
• Serial ATA
• RapidIO: Embedded System Interconnect.
• NPF (Network Processing Forum): open specs for PHY-NP-fabric interfaces (streaming interface "NPSI" (ex-"CSIX")).
• Controller Area Networks (CAN):
  • ODVA: Open DeviceNet Vendor Association.
  • The "CAN" standard: introductory article, the www.can-cia.de site.

16. Optical Switching

• B. Mukherjee: "WDM Optical Communication Networks: Progress and Challenges", IEEE Jour. Sel. Areas in Communications, vo. 18, no. 10, Oct. 2000, pp. 1810-1824.
• S. Yao, B. Mukherjee, S. Dixit: "Advances in Photonic Packet Switching: An Overview", IEEE Communications Magazine, vol. 38, no. 2, Feb. 2000, pp. 84-94.