CS-534: Packet Switch Architecture
Fall 2001
Department of Computer Science
© copyright: University of Crete, Greece

5. Switching Fabric Topologies


Subsections in the current document:

Transparencies by prof. Paraskevi Fragopoulou (visiting from Universite de Versailles, France), adapted with additions from the transparencies of spring 2000 semester by prof. George Stamoulis.

Reading Assignments:


Switching Fabric Definition


5.1 Crossbar Revisited


Crossbar Revisited

Number of Crosspoints


5.2 Hypercube


Hypercube

Recursive Construction

Paths in a Hypercube


5.3 Banyan


Butterfly

Banyan

Routable Permutations Theorem

Proof

Reverse Banyan

Internal Blocking in the Banyan

Alternatives


5.4 Benes: Rearrangeably Non-Blocking Fabric


Benes

Reconfigurably Non-Blocking


5.5 Batcher Sorting Networks


Batcher Sorting Networks

Bitonic Sequence: Definition

Bitonic Sorter 1

Bitonic Sorter 2

The overall Batcher Sorter


5.6 Self-Routing Non-Blocking Fabrics based on Sorting Networks


Batcher-Banyan Motivation

The Batcher-Banyan Network

The Starlite Architecture

The Trap Network in Starlite

Parallel Computation of the Prefix Sums

The Second Concentrator

The Sunshine Architecture

The Trap Network in Sunshine

The Output Stages of Sunshine


5.7 Clos Networks


Clos Networks

Properties of the Clos Networks

Condition for Strictly Non-Blocking Clos Networks

Condition for Rearrangeably Non-Blocking Clos Networks

Recursive Clos Networks

Example of Clos Network

Physical (3-D) Construction Considerations

Benes as a case of Clos Network


Up to the Home Page of CS-534
 
© 2001-02 copyright: University of Crete, Greece.
File last updated: 15 Jan. 2002, by M. Katevenis.
Transparencies by prof. Paraskevi Fragopoulou (visiting from Universite de Versailles, France), adapted with additions from the transparencies of spring 2000 semester by prof. George Stamoulis.