A virtually nonblocking self-routing permutation network which routes packets in O(log(2)N) time

Asymptotically nonblocking networks are O(log(2) N) depth self-routing perm utation devices in which blocking probability vanishes when N (the number o f network inputs) increases. This behavior does not guarantee, also for ver y large N, that all information always and simultaneously reaches its desti nation (and consequently that a whole permutation passes through the device ) which is a requirement of the PRAM machine. In this work the conditions f or which an asymptotically nonblocking network becomes asymptotically permu tation nonblocking are studied, finally a virtually nonblocking device is o btained by a retransmission procedure which guarantees that all permutation s always pass through this permutation device.