Broadband packet switches based on dilated interconnection networks

A theoretical foundation for the study of a broad spectrum of fast packet switching techniques is developed. Based on this framework, the authors investigate the complexity of various packet switch designs and demonstrate the advantage of dilation as a switch-design technique. For a given loss probability requirement, it is shown that for an N×N switch, the required number of switch elements for both the parallel-banyan network and the tandem-banyan network is of order N(log N)², whereas the complexity of a dilated-banyan network is of order N log N (log log N). In addition, it is shown that the parallel banyan networks in a Batcher-parallel-banyan network can be replaced by a dilated-banyan network without sacrificing the nonblocking property