Interconnection Networks

Lecture Notes

1. Course Descriptor
2. Unit 1 Course Overview
3. Unit 2 Switching vs. Routing
4. Unit 3 Router Architecture
5. Unit 4 Software based IP forwarding
6. Unit 5 Hardware based IP forwarding
7. Unit 6 Packet classification
8. Unit 7 Network processors (Guest lecture, delivered by Michael Hathaway of Austin Ventures)
9. Unit 8 Scheduling
10. Unit 9 Fabrics
11. Unit 10 Array routing
12. Unit 10 Butterfly routing
13. Unit 11 What is a Venture Capitalist? (Guest lecture, delivered by Venu Shamapant of Austin Ventures)
14. Midterm on 3.26.02 - here are some sample questions
15. Unit 12 Matching theory
16. Unit 13 SLIP - Here is some C code simulating max size matching on a 2x2 switch
17. Unit 14 Stability
18. Unit 15 Digital systems engineering pdf, ps

Here is a partial list of papers we will be covering.

Assignments

• Homework 0: Biodata
• Miniproject 1: Heuristics for fast packet classification
  • Link to website
• Miniproject 2: Measuring the performance of hierarchical unbuffered fabrics
  • Here is the project definition
• Miniproject 3: Approximate Birkhoff - von Neumann decompositions
  • Here is the project definition Note: I fixed a small problem with the description, posted the update 12:30pm, 4/3/02.
  • Here is some code that may be of help. Note: I've added a fair bit of documentation to the code (as of 12:30pm, 4/3/02) should be easier to understand now.
• Miniproject 4: Scheduling for packet-switched cellular networks
  • Here is the project definition
  • Here is some code you should build on
  • ADDED MAY 7, 2002: I've updated the code, the new file is here. You are to turn in results on the three cell models I have in this file; you are welcome to tinker around with others.
• IMPORTANT: Please read this for details about the final project.

Resources

• Other classes
  • Jon Turner, Washington University: Design and analysis of switching systems
  • Nick McKeown, Stanford University: Packet Switching Architectures
  • Pravin Varaiya, University of California at Berkeley: Switching: architectures, control, performance
  • Bill Dally, Stanford University: Advanced Computer Organization: Interconnection Networks
• Document viewing:
  • Use Aladdin Ghostscript to view postscript on Win95/WinNT.
  • Use Adobe Acrobat to view pdf files; you can download Acrobat here
  • You can convert Postscript to PDF via ps2pdf
• The ECE Learning Resource Center.
• Getting started with UNIX, vi, g++, gdb.
• Click here to subscribe to the EE382N Email list