Reading List

Papers 1-10: Assigned 2000-03-30 (week 8) -- Presentations: 2000-04-17,18 (week 10)
Papers 11-20: Assigned 2000-05-16 (week 12) -- Presentations: 2000-05-24,25 (week 13)

1. Clock Synchronization

L. Dennison, W. Dally, D. Xanthopoulos: "Low-Latency Plesiochronous Data Retiming", Proc. Conf. on Adv. Research in VLSI, Chapel Hill, NC, USA, March 1995, pp. 304-315.

Background Paper:
D. Messerschmitt: "Synchronization in Digital System Design", IEEE Jour. Sel. Areas in Communications, vol. 8, no. 8, Oct. 1990, pp. 1404-1419.

2. Output Queueing Family: 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. Crossbar Scheduling: 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.

4. 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.

5. Crossbar Scheduling: iSLIP, Tiny Tera

P. Gupta, N. McKeown: "Designing and Implementing a Fast Crossbar Scheduler", IEEE Micro, Jan.-Feb. 1999, pp. 20-28.

Background Paper:
N. McKeown, M. Izzard, A. Mekkittikul, W. Ellersick, M. Horowitz: "Tiny Tera: a Packet Switch Core", IEEE Micro, Jan.-Feb. 1997, pp. 26-33.

For more information on the iSLIP algorithm, see:
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

6. Crossbar Scheduling: 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.

7. Internal Speedup with Input and Output Queues

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

8. Flow Classification

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

9. Flow Classification

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.

10. 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

11. Sorting Networks and Multicast

T. Lee: "Nonblocking Copy Networks for Multicast Packet Switching", IEEE Jour. Sel. Areas in Communications, vol. 6, no. 9, Dec. 1988, pp. 1455-1467.

12. Fat Trees

C. Leiserson: "Fat-Trees: Universal Networks for Hardware-Efficient Supercomputing", IEEE Trans. on Computers, vol. 34, no. 10, Oct. 1985, pp. 892-901.

13. Wormhole Routing

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.

14. Wormhole Flow Control

Li-Shiuan Peh, W. Dally: "Flit-Reservation Flow Control", Proc. Int. Symp. on High-Perf. Comp. Arch. (HPCA), 2000.

15. Routing vs. Switching, SAR, Cut-Through

M. Katevenis, Iakovos Mavroidis, Ioannis Mavroidis, G. Glykopoulos: "Wormhole IP over (Connectionless) ATM", Univ. of Crete and FORTH, Heraklion, Crete, Greece, http://archvlsi.ics.forth.gr/wormholeIP/arch98/wIP_98.html, July 1998, 33 pages.

16. Flow Control - Buffer Management

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.

17. Flow Control - Buffer Management

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.

18. Crossbar Scheduling 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.

19. Weighted Round-Robin Scheduling

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.

20. Weighted Round-Robin Scheduling

A. Ioannou, M. Katevenis: "Pipelined Heap (Priority Queue) Management for Advanced Scheduling in High-Speed Networks", FORTH and Univ. of Crete, Heraklion, Crete, Greece, submitted for publication, April 2000.

Added Later (after the end of Spring 2000 semester):

21. Off-Line Smooth Static Crossbar Schedule Construction

T. Rodeheffer, J. Saxe: "Smooth Scheduling in a Cell-Based Switching Network", DEC SRC Research Report #150, Feb. 1998.

22. Buffer Management Survey

M. Arpaci, J. Copeland: "Buffer Management for Shared-Memory ATM Switches", IEEE Communications Surveys, Vol. 3, No. 1, First Quarter 2000.

23. Routing Table Lookup, Flow Classification

M. O'Connor, C. Gomez (Silicon Access Networks): "The iFlow Address Processor", IEEE Micro Magazine, March-April 2001, pp. 16-23.
IEEE Network Magazine, March-April 2001: a collection of 3 articles on the topic:
- Gupta & McKeown, 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)
- Survey and Taxonomy paper, 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.

[ Up to the Home Page of CS-534 ]