Dynamic Allocation of Buffer Space in Smart Multistage Interconnection
Networks

Hassan Diab and Hassan Tabbara

Department of Electrical and Computer Engineering
Faculty of Engineering and Architecture
American University of Beirut
P.O.Box 11-0236, Beirut, Lebanon

Telephone: +(00961)-1-350000 extention 3520
email: diab@aub.edu.lb


Abstract: The performance in Multistage Interconnection Networks
(MINs) depends on the design of the internal buffers in each
Switching Element (SE) and the clock mechanism in synchronous
MINs. Existing models include the big cycle, small cycle, and
the smart cycle, each of which provides a different and more
efficient cycle timing. The smart cycle model provides a superior
throughput compared to other models by making use of output
buffers in each SE and acknowledgement. However, it suffers from
two drawbacks with high traffic loads. First, it may results in
packets delivered out-of-order and hence require their ordering
at the destination nodes. Second, packets may be lost when the
load becomes greater than a fixed value due to input buffer overflow.
To overcome these drawbacks, a dynamic allocation of the input
buffer space in each SE is proposed. A buffer pool is provided
which supplies the required buffer space, thus eliminating lost
and out-of-sequence packets in high load MINs. This paper presents
a simulation study of the proposed scheme. Case studies are presented
which shows the impact of the input buffer length on the overall
network performance with different network loads. The paper also
presents a comparison study between the fixed size buffer and the
dynamic one which shows an increased network throughput and a
reduction in the number of out-of-sequence packets for high loads
when using the dynamic allocation scheme.