Packet-switched self-routing multistage interconnection network having contention-free fanout, low-loss routing, and fanin buffering to efficiently realize arbitrarily low packet loss

摘要

A new class of packet-switched extended generalized-shuffle self- routing multistage interconnection networks provides a continuous performance-cost tradeoff between, on the one hand, the knockout switch or buffered crossbar and, on the other hand, the tandem banyan network. Multiple copies of the new networks may be serially cascaded back-to-back, and connected in parallel. A particular concentrator circuit in the network concentrates active communications packets randomly distributed on many lines onto selected lines. Another, second, network communicates synchronization information communicable point-to-point and multipoint while performing arithmetic and logical operations on the synchronization information so communicated. A hybrid parallel combination of both the first and second networks serves to efficiently communicate information point-to-point while simultaneously communicating synchronization information both point-to-point and multipoint.