Matching algorithms for three-stage bufferless Clos network switches

Three-stage Clos network switches is an attractive solution to future broadband packet routers due to their modularity and scalability. Most of the three-stage Clos network switches assume either all modules are space switches without memory (bufferless), or employ shared memory modules in the first and third stages (buffered). The former is also referred to as the space-space-space (S³) Clos network switch, while the latter is referred to as the memory-space-memory (MSM) Clos network switch. In this article we provide a survey of recent literature concerning switching schemes in the S³ Clos network switch. The switching problem in the S³ Clos network switch can be divided into two major parts, namely port-to-port matching (scheduling) and route assignment between the first and third stages. Traditionally, researchers have proposed algorithms to solve these issues separately. Recently, a new class of switching algorithms, called Matching Algorithms for Clos (MAC), has been proposed to solve the scheduling and route assignment simultaneously. We focus on the MAC schemes and show that the new class of algorithms can achieve high performance and maintain good scalability.