Many switch architects require that a switch fabric is capable of
delivering 100% throughput for input traffic that does not oversubscribe
any input or any output. It has already been shown that any maximal
algorithm can achieve this goal with a speedup of 2. However, from
an implementation viewpoint, the buffering point in a switch requires
complex memory designs in order to transfer cells at a speedup of 2.
In fact, many current buffer designs only allow a speedup of 1.6.

Our motivation in this project is to prove that a maximal matching
algorithm can provide 100% throughput while running at a speedup of
less than 2. The maximal matching algorithm could be newly created
or an existing algorithm, like WFA, WWFA, iSLIP, etc.

Here is a list of ideas in which we propose to approach the problem

1) Create a simulation environment that can exhaustively run all
   combinations for a small switch size for a given maximal algo to
   give us insight into what input traffic pattern creates the worst
   pattern. The algos we might want to consider would be WWFA and ISLIP.
2) Create the worst traffic pattern for a given algorithm in order to
   generate a necessity case.
3) Use Markov chains to analyze a small switch. This might intuitively
   help us solve for a switch of size N.
4) We have already created a traffic pattern that requires a speedup of
   1.5 for WWFA. Here is the pattern for a 3x3 switch:

     1/2  1/2  0
      0   1/2  1/2
     1/2   0   1/2

5) Help from the TAs to find other approaches. :)

Tentative Schedule(~6 weeks)

  -> 1-2 weeks: Run exhaustive 3x3 switch simulation with input granularities of
                1/2, 1/3, 1/6 etc.
  -> 3-6 weeks: Try to devise some new maximal algo as described above.

  Actually, it would be good if the TAs can guide the exact schedule.