Interconnection Network Seminar (CSE 736)
SUBNET group
Spring 2002

	Office: 239 Bell Hall 
	Office Hours: Thursdays 2:00-4:00pm
	Phone: 645-3180 x 160 
	Email: hungngo@cse.buffalo.edu 

Website: http://www.cse.buffalo.edu/~hungngo/SUBNET/seminars/InterconnectionNet_Spring02/

Grading: to be done on an S/N (or S/U) basis only.

Time and place: Wednesdays 12-3pm, Bell 242

Description:

This seminar aims at introducing the area of Interconnection Networks based on three classes of problems:

1. Deciding how good such and such a network can be designed.
2. Constructing an optimal or near optimal design as determined by (a)
3. Devising novel generic algorithms (routing, fault recovery, ...) to operate on the designs from (b)

Research on classes (a) and (b) has proved to be extremely fruitful pratically and mathematically. In fact, a good understanding of (a) and (b) would almost certainly give us significant insights into how to do (c). Class (a) and class (b) would be classified under the generic name: "complexity of Interconnection Networks". Along with class (c), this classification leads to the name of the seminar.

Traditionally, most of these problems were modelled as graph theoretic problems or combinatorial optimization problems in general. Recent application areas such as optical networks and wireless networks impose a great deal of new contraints on the problems at hand. Traditional techniques which have been successfully used do not seem to apply very well to the new set of problems, leaving many open directions for research. It is likely that the new techniques needed to solve these problems will again be very useful practically and theoretically.

We can not cover every thing related to what described above. However, I hope to cover the more relevant techniques and problems, ranging from classical to modern results, from old problems to new conjectures, ...

Objectives:

• Have fun learning!
• Learn a few essential Mathematical tools to solve Interconnection Network problems.
• Be exposed to some current topics and (open/solved) problems in Interconnection Networks.
• Be able to read, explore and even identify future research problems and directions in Interconnection Networks.

Topics (tentative):

• Essential mathematical tools to solve problems in Interconnection Networks:
  • Linear Algebra
  • Probability and the Probabilistic Method
  • Graph Theory (Matching Theory in particular)
  • Algebraic Graph Theory
  • Approximation Algorithms and NP-Completeness
• Interconection Network Topologies and Essential Properties
• Complexity (of Interconnection Networks)
• Explicit Constructions
• Centralized Routing Algorithms
• Self-routing Algorithms
• Distributed Routing Algorithms
• On-line Routing Algorithms
• Wormhole Routing
• (Approximation) Algorithms for Optical Networks Problems (traffic grooming, wavelength assignments, ...)
• (Approximation) Algorithms for Ad hoc Wireless Network Problems (optimizing power consumption, routing, ...)

Course Load:

• About 50 pages of dense reading per week (i.e. no bed-time reading).
• Each student is expected to do a presentation at some point during the semester, based on:
  • A survey done by the student on a particular topic to be suggested by the instructor or picked by the student but approved by the instructor.
  • A (few) very dense mathematical paper.
  • An open problem solved by the student.

Prerequisites:

• Find learning new things fun.
• Find learning mathematics fun.
• Find solving mathematical puzzles fun.
• Find the instructor funny.

• OK, the real deals are: rudimentary knowledge on linear algebra, algorithms, graph theory, probability theory and networking. They are not entirely essential to follow things presented in the seminars. Related background materials shall be provided in the forms of small tutorials/notes. You'd have to read them though.