Premium
A contention resolution algorithm for input‐buffered batcher‐banyan networks
Author(s) -
Awdeh Ra'Ed Y.,
Mouftah H. T.
Publication year - 1994
Publication title -
international journal of communication systems
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.344
H-Index - 49
eISSN - 1099-1131
pISSN - 1074-5351
DOI - 10.1002/dac.4500070106
Subject(s) - computer science , banyan , overhead (engineering) , algorithm , binary number , process (computing) , simple (philosophy) , computer network , arithmetic , mathematics , philosophy , epistemology , operating system
A simple algorithm for resolving output contentions in an input‐buffered Batcher‐banyan network is described. The basic idea in this algorithm is to let the binary nodes of the Batcher network participate in the arbitration process. The proposed algorithm is completely distributed and parallel; thus it scales well to large size switches. Furthermore, our algorithm is fair and requires an overhead that is significantly less than that due to the well‐known three‐phase algorithm. Two variations of the algorithm are described.