summer semester 2001

Instructor: Hagit Attiya
First meeting: Monday, July 23, 2001, 12:30-14:30 (this is the correct time).
Place: Taub 401 (seminar room).

To The matching List

Required background: computer networks, probability, and algorithms.

Course topic: Most proejcts address the architecture of fast packet switches, in particular, issues related to parallel architectures, queuing and routing using sorting networks. The goal of the projects is two-fold.  First, to learn about current switch architectures and to evaluate design choices. Second, to gain experience in writing simulation software.

Projects should be written in C++ (possibily also Java); you may use your home or work environment (except for project #5), provided that a similar environment is available at the department (so we can later run your project).

All projects should include:

1. A GUI that allows to specify the relevant configuration and parameters.
2. A simulator, which includes a source for generating traffic based on distribution parameters.
3. A GUI that displays the resulting statistics.

Schedule:

Suggested projects:

1. Incremental clock synchronization. (possible for groups of 2)

   In (this version of) the clock synchronization problem, processors have access to local clocks, that run at the rate of real-time;  some clock may be corrupted and read wrong values.  The clocks are not initialized and processors need to adjust them to be as close as possible (using an additive adjustment factor).  A related issue is to allow processors to join the system, without causing already-running processors to move their clock back. Most algorithms for this problem require processors to read current clock values from all other processors (in one communication round), remove extreme values, and average.

   In our setting, however, a processor can get only a few (constant number of) clock values in each communication round. A simple algorithm was suggested for this setting, which increrements/decrements the adjustment factor, depending on whether the received clcock value is larger/bigger than the current clock.

   The purpose of this project is to explore clock synchronization algorithms in this situation and compare them with unrestricted clock synchronization algorithms, by means of simulation.

   Links:

   • A paper by Srikanth and Toueg (PDF file through the ACM Digital Library) describing another clock synchronization algorithm, which does not wait to recieve clock values from all processors.
   • Final project presentation (by Greg Fidelman and Anna Reitman).

2. Crossbar-based switching. (only for groups of 3)

   Do a simulation study of crossbar-based switching systems, considering different queuing strategies (for example, single fifo queue at each input, odd-even queue pair at each input, virtual output queues) and crossbar control mechanisms (for example, iterative matching with and without weights, iSlip, most urgent-cell first). How do they perform for uniform random traffic? How do they perform in cases where one output is overloaded? In this case, consider if traffic to other outputs is affected negatively and if each input gets an appropriate share of the output bandwidth.
   Try to find worst-case traffic patterns that stress each system configuration to the greatest extent. Study how the systems perform in these cases and suggest design changes that could lead to better worst-case performance.

   Links:

   • A tutorial on ATM switches (part 1, part 2).
   • Jon Turner‘s course on Design and Analysis of Switching Systems
   • Another course on digital switching (Stanford).
   • Final project presentation (by Eli Cohen, Barak Pinhas and Hanna Sender).

3. Banyan-style switching. (only for groups of 3)

   Similar to project number 3, but for switching systems using sorting networks (Banyan, Banyan with Buffers, Batcher,  Batcher-Banyan, Buffered Batcher-Banyan, Distributed Batcher-Banyan ).

   Links:

   • Follow the links for project #2.

4. Input/Output queuing in switches

   This combines projects #2 and #3, but explores different queuing strategies (for example, single fifo queue at each input, odd-even queue pair at each input, virtual output queues) for switching systems. Consider crossbar-based and Banyan-style switching systems in the same framework and compare queuing strategies.

   Links:

   • The paper on iSLIP, by Nick McKeown.
   • The paper “On the Speedup Required for Combined Input and Output Queued Switching”, by Balaji Prabhakar and Nick McKeown.
   • Also, follow the links for project #2.

5. Web server statistics.

   The goal of the project is to estimate the transfer time of a file by a Web server.
   The project will (slightly) modify the Apache server, in a Linux environment. See more here (.doc file).

   This project is supervised by Ronit Nossenson, ronitt@cs.technion.ac.il.

Matching List

Please contact these people directly.

1. Barak Pinhas (sadigado@techst02.technion.ac.il)
2. Kashi Nitzan (sfrhzkpx@techst02.technion.ac.il)