Low cost complexity of a general multicast network

摘要

This paper presents a new multicasting network constructed with a bit-level cost complexity of O(N log N) and a bit-level time complexity of O(log 2 N) using comparators with bit-level O(1) time and cost complexities. The requested addresses for connection and the addresses of the source nodes to be connected to, are sorted together in a pipeline fashion (worm-hole routed) bit-serially most-significant-bit first through the network. This network achieves sorting by recirculating its inputs through its 3(1+log N) stages. Input items of the network are constructed of leading addresses (request or adversely nodes addresses), return addresses, and data packets. Packets are broadcast during the process of sorting between two equal leading addresses.