An algorithm that uses forward planning to expedite conflict-free traffic assignment in time-multiplex switching systems

In multichannel telecommunication networks, switching systems, and processo r-memory interconnects, the need for conflict-free traffic assignment arise s whenever packets (or requests) are to be directed from input buffers (pro cessors) to specific outlets (modules), This paper presents an algorithm, based on forward planning, which can be u sed in the above-mentioned applications for scheduling conflict-free transf ers of packets from inputs to outputs. The performance of the algorithm is evaluated in the sense of throughput and delay and is compared with that of system of distinct representatives (SDR), an earlier proposed algorithm fe aturing 100% assignment efficiency, Then, its worst-case computational comp lexity is compared with that of SDR and several suboptimal (but low complex ity) algorithms reported in literature. The proposed forward planning algorithm is shown to have the lowest order o f computational complexity and permits simpler buffer organization and acce ss modes. Moreover, it is shown that forward planning of packet transmissio ns offers significant performance improvements if the finite capacity of bu ffers is taken into account.