FAULT-TOLERANT, HIGHLY-SCALABLE CELL SWITCHING ARCHITECTURE

Generally speaking, the cell switching architecture of the present invention offers a powerful, simple, and in many ways elegant solution to the problem of providing cost-effective, high-bandwidth, fault-tolerant cell switching. The architecture is based on a network of switching elements connected in a hypercube topology to form a switch fabric. The generalized hypercube is D dimensional, where D≧3 when all radices in the radix set are 2 and D≧2 when at least one of the radices is greater than 2. A fully-populated switch is fully symmetric: each switching element has the same number and kind of connections to both its neighbors and to the outside world as every other switching element. In an exemplary embodiment, each switching element is connected to one data source and one data sink, e.g., a Utopia bus or other broadband connection. In the same exemplary embodiment, links between switching elements are bidirectional and synchronous, operating in accordance with a Cell Exchange Cycle (CEC). Buffer space for a limited number N of cells is provided within each switching element. Multipath routing allows a switching element to forward a cell along any of multiple paths. Retrograde and lateral motion, i.e., motion other than in a forward direction toward the cell's destination, is also allowed to relieve temporary local congestion.