Proposal for EE384y
Guido Appenzeller <appenz@cs.stanford.edu>
Matthew Holliman  <holliman@stanford.edu>


   Quantitative Analysis of a Massive Parallel Gigabit Switch
              built with Commodity Hardware

                              or

                       Can Google Route?

1.) Motivation

The current design paradigm for high-end router is based on a
centralized switching fabric built from highly optimized, custom
hardware. The continuing decline in prices for PC hardware and
specifically Gigabit Ethernet cards makes it seem possible to take a
different approach. We propose to evaluate the feasability and
expected performance of a distributed router using a large number of
commodity PCs and Network interfaces. The potential benefits of such a
distributed architecture have been proven previously for other
computation and bandwidth intensive applications such as Google or
Beowulf Clusters for scientific computing.

Currently the price of a stripped down PC is approximately $250 and
Copper Gigabit Ethernet Cards for as low as $35. The effective
transfer rate of a 66MHz, 64 bit PCI bus is up to 4 Gbit. It seems
feasible to build a 2x2 or even 4x4 switch that can route traffic at 1
GBit/s for $400. These building blocks can be connected to form
larger, distributed switching fabrics. A fabric of 100 such building
blocks has properties that are very different from traditional routers
such as a very high aggregate memory bandwith (> 100 GByte/s) and
total computational power (> 100,000 MIPS).

2.) Research Areas and Deliverables

The project aims to build a quantitative model of this architecture,
study its advantages and disadvantages compared to traditional routers
and whether it could be attractive as a design approach for routers.
There are two main research areas:

 (i)  Component (individual node) and system (cluster) architecture
      definition.  This aspect will include consideration of the
      hardware/ software interaction on an individual node, and the
      resulting implications for the cluster layout.

 (ii) Quantitative analysis of expected system performance.  We
      anticipate several aspects to this deliverable, including:

      * Analysis of expected node capacity (viz. maximum effective
        PCI bus utilization, impact of memory subsystem, interrupt
        processing rate, cache utilization, computation required for
        forwarding decision, etc.).  What are the bottlenecks, what
        is the expected routing capacity of an individual node, and
        what CPU power is available to applications?

      * Depending on the architecture proposed, the data flow through
        the system is likely to be more complex than in a
        conventional NxN crossbar switch.  For example, in some sense
        the distributed approach trades off latency for aggregate
        bandwidth.  An analysis of the cluster performance should
        attempt to characterize the performance relative to a
        conventional switch.  Can we bound the expected delay
        introduced for a packet passing through the system?

      * Evaluation of the capacity for scalability and fault
        tolerance in the architecture.  How much can the system
        scale, and how tolerant can it be to individual node failures
        in the fabric?