CS-534: Packet Switch Architecture Spring 2003

Department of Computer Science © copyright: University of Crete, Greece

Bibliography:

Important, relevant, optional readings, beyond those assigned in class for everyone to read

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, second printing, 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.
• Simulation, Pseudo-Random Number Generators:
  • Sheldon M. Ross: "Simulation", Academic Press, 3rd Edition, 2001, ISBN 0125980531. [Chapter 7 describes how we should determine confidence intervals in our simulations]
  • Xilinx: "Efficient Shift Registers, LFSR Counters, and Long Pseudo-Random Sequence Generators", Application Note XAPP 052, July 1996; www.xilinx.com/bvdocs/appnotes/xapp052.pdf
  • P. Chu, R. Jones: "Design Techniques of FPGA Based Random Number Generator", Mil. Aerosp. Ap. Prog. Dev. Tech. Conf., 1999; http://academic.csuohio.edu:8080/chup/research.htm

1b. Network Traffic Characterization, Benchmarking:

• Network Processing Forum (NPF): Switch Fabric Benchmark Implementation Aggreements; available from http://www.npforum.org/benchmarking/fabric_bm.shtml (under license).
• 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.
• R. Caceres, P. Danzig, S. Jamin, D. Mitzel: "Characteristics of Wide-Area TCP/IP Conversations", ACM SIGCOMM'91 Conference, Zurich, Switzerland, Sep. 1991, pp. 101-112; http://irl.eecs.umich.edu/jamin/papers/traffic/

1c. Background Knowledge on how Switches & Routers are being Used

• QoS: V. Fineberg: "A Practical Architecture for Implementing End-to-End QoS in an IP Network", IEEE Communications Magazine, vol. 40, no. 1, Jan. 2002, pp. 122-130.

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.

Output Queueing Family: the Knockout Switch:

• 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.
• T. Inukai: "An Efficient SS/TDMA Time Slot Assignment Algorithm", IEEE Trans. Communications, vol. 27, Oct. 1979, pp. 1449-1455.
• I. Gopal, D. Coppersmith, C. Wong: "Minimizing Packet Waiting Time in a Multibeam Satellite System", IEEE Trans. Communications, vol. 30, 1982, pp. 305-316.
• 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.
• 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.
• PIM variation for simpler, pipelined hardware:
  S. Mukherjee, F. Silla, P. Bannon, J. Emer, S. Lang, D. Webb: "A Comparative Study of Arbitration Algorithms for the Alpha 21364 Pipelined Router", Proc. of the ACM ASPLOS-X Conf., San Jose, CA USA, Oct. 2002, pp. 223-234.
• 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
  PMC-Sierra, Inc.: "TT1 Chipset - A New Architecture for Switch and Router Design", Dec. 1999 (the Tiny Tera was commercialized by Abrizio Inc, later bought by PMC-Sierra); see www.pmc-sierra.com/pressRoom/pdf/lcs_wp.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.
• W. Dally: "Scalable Switching Fabrics for Internet Routers", Avici Systems Inc. White Paper, available through http://www.avici.com/technology/
• 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:
  [Modern, Detailed Reference:]
  • Jose Duato, S. Yalamanchili, L. Ni: "Interconnection Networks: an Engineering Approach" Morgan Kaufmann Publishers, second printing, 2003, ISBN 1-55860-852-4
    [Quick Survey:]
  • L. Ni, P. McKinley: "A Survey of Wormhole Routing Techniques in Direct Networks", IEEE Computer Magazine, vol. 26, no. 2, Feb. 1993, pp. 62-76.
    [Modern Use:]
  • AVICI Systems, Inc.: the Terabit Switch Router (TSR).

    [Original Papers:]

  • 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].
  • M. Karol, S.J. Golestani, D. Lee: "Prevention of Deadlocks and Livelocks in Lossless Backpressured Packet Networks", IEEE/ACM Tran. on Networking, vol. 11, no. 6, Dec. 2003, pp. 923-934.
  • Li-Shiuan Peh, W. Dally: "Flit-Reservation Flow Control", Proc. Int. Symp. on High-Perf. Comp. Arch. (HPCA), 2000.
• Buffered Crossbars (CICQ) - Crosspoint Queues with backpressure to the VOQ's in the Input Buffers:
  • 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.
  • IBM Zurich 4 Tb/s Byte-Sliced Buffered Crossbar:
    F. Abel, C. Minkenberg, R. Luijten, M. Gusat, I. Iliadis: "A Four-Terabit Packet Switch Supporting Long Round-Trip Times", IEEE Micro Magazine, vol. 23, no. 1, Jan./Feb. 2003, pp. 10-24. An earlier version appeared as Research Report RZ 3430, IBM Zurich Research Lab, (# 93609) Jan. 2002, 10 pages; preprint available on-line through domino.watson.ibm.com/library
  • Variable Packet Size Buffered Crossbars, Weighted Max-Min Fairness in Buffered Crossbars:
    M. Katevenis, N. Chrysos, e.a.: "Buffered Crossbar (CICQ) Switch Architecture", http://archvlsi.ics.forth.gr/bufxbar/
• Lucent's ATLANTA chip set (3-stage buffered switching fabric with internal backpressure; middle stage is bufferless):
  • www.agere.com/metro_regional_transport/switch_fabric.html
  • 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 (QFC) Alliance: "Quantum Flow Control: A cell-relay protocol supporting an Available Bit Rate Service", version 2.0, July 1995; originally at http://www.qfc.org but no longer there --copy at http://archvlsi.ics.forth.gr/~kateveni/534/qfc/
  • 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. Switching Fabrics with Inverse Multiplexing, Packet Resequencing:

• Byte Sliced (bit-sliced) Crossbars:
  • See the Stanford Tiny Tera Crossbar referenced above
  • See the IBM Zurich 4 Tb/s Buffered Crossbar referenced above
• 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.
• G. Sapountzis, M. Katevenis: "Benes Switching Fabrics with O(N)-Complexity Internal Backpressure", Proc. IEEE Workshop on High Performance Switching and Routing (HPSR 2003), Torino, Italy, June 2003, pp. 11-16; http://archvlsi.ics.forth.gr/bpbenes/

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.
• A. Tang, J. Wang, S. Low: "Is Fair Allocation Always Inefficient", Proc. IEEE Infocom Conference, 2004; on line netlab.caltech.edu/~aotang/pub/04/infocom04.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

M. Katevenis, Iakovos Mavroidis, G. Sapountzis, E. Kalyvianaki, Ioannis Mavroidis, G. Glykopoulos: "Wormhole IP over (Connectionless) ATM", IEEE/ACM Transactions on Networking, to be published (expected: Oct. 2001); preprint available on-line through http://archvlsi.ics.forth.gr/wormholeIP.

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

• S. Melvin, M. Nemirovsky, E. Musoll, J. Huynh, R. Milito, H. Urdaneta, K. Saraf: "A Massively Multithreaded Packet Processor" (Porthos NP), NP2: Workshop on Network Processors, in conjunction with HPCA-9, Anaheim, CA, USA, Feb. 2003.
• NP2: 2nd Workshop on Network Processors (in conjunction with HPCA 9).
• 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).

FPGA + Embedded Core Technologies:

• Example 1: Altera Stratix (FPGA + Memory + DSP + High Speed I/O + off-chip RAM interfaces).
• Example 2: Altera Excalibur (FPGA + Embedded Processor).
• Xilinx FPGA Crosspoint: bufferless crosspoint switch; up to 1024x1024 (x155-200 Mbps); reconfiguration time in the hundreds of microseconds.

15. Cluster, System, and smaller Area Networks

• "Unsnarling the Interconnect Tangle", IEEE Spectrum Online, Jan. 2003 (light, overview article).
• PCI: see in particular "PCI Express", and the Work Group on "PCI Express Advanced Packet Switching".
• RapidIO: Embedded System Interconnect.
• HyperTransport: Chip-to-Chip Interconnect.
• Infiniband
• VIA
• OctigaBay Systems Co: their 12K multiprocessor includes an interconnection fabric built out of 48x48 switches with 16 Gb/s links.
• NPF (Network Processing Forum): open specs for PHY-NP-fabric interfaces (streaming interface "NPSI" (ex-"CSIX")).
• Processor-Memory Interconnection Switches:
  • A. Charlesworth: "The SUN Fireplane Interconnect", IEEE Micro Magazine, vol. 22, no. 1, Jan./Feb. 2002, pp. 36-45.
  • S. Mukherjee e.a.: "The ALPHA 21364 Network Architecture", IEEE Micro Magazine, vol. 22, no. 1, Jan./Feb. 2002, pp. 26-35.
• Networks-on-Chip (NoC):
  • A. Radulescu, K. Goossens: "Communication Services for Networks on Silicon", in Domain-Specific Processors: Systems, Architectures, Modeling, and Simulation (S. Bhattacharyya e.a. editors), Marcel Dekker, 2003 [PDF] [PS]; this and other interesting papers by Kees Goossens available on-line.
  • WISHBONE System-on-Chip (SoC) Interconnect Architecture for Portable IP Cores
  • IBM CoreConnect
  • ARM AMBA
  • OCCN (On-Chip Communication Network) Architecture
• Storage interconnects and Storage Area Networks: M. LoBue: "Surveying Today's Most Popular Storage Interfaces" (pp. 48-55); R. Griswold: "Storage Topologies" (pp. 56-63); both in IEEE Computer Magazine, Dec. 2002.
  • SCSI and iSCSI; Fibre Channel; FireWire (IEEE 1394); Serial ATA.
• Controller Area Networks (CAN):
  • ODVA: Open DeviceNet Vendor Association.
  • The "CAN" standard: introductory article, the www.can-cia.de site.

16. Optical Switching

• Chiaro Networks, Inc.: Optical Phased Array Crossbar: White Paper [PDF]
• Optical Burst Switching:
  • C. Qiao: "Labeled Optical Burst Switching for IP-over-WDM Integration", IEEE Communications Magazine, vol. 38, no. 9, Sep. 2000, pp. 104-114.
  • S. Verma, H. Chaskar, R. Ravikanth: "Optical Burst Switching: a Viable Solution for Terabit IP Backbone", IEEE Network Magazine, vol. 14, no. 6, Nov./Dec. 2000, pp. 48-53.
  • I. Baldine, G. Rouskas, H. Perros, D. Stevenson: "JumpStart: a Just-in-Time Signaling Architecture for WDM Burst-Switched Networks", IEEE Communications Magazine, vol. 40, no. 2, Feb. 2002, pp. 82-89.
• Other:
  • 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.

---

Up to the Home Page of CS-534

© copyright University of Crete, Greece. Last updated: 12 Feb. 2004, by M. Katevenis.