A two-stage distributed shared memory architecture and its scheduling algorithms

The performance of a high-speed router is limited by the random access rate of memories and the switching rate of the inner switch architecture. This paper proposes a two-stage distributed shared memory architecture (TSDSM) and its scheduling algorithms which can emulate the FCFS and the PIFO output-queued (OQ) scheduling algorithms. The lower bound of the memories of the TSDSM is analyzed. We also prove that our algorithms can emulate the QQ scheduling algorithms. The most advantage of the TSDSM over other switching architectures is that the access rate of the memories is commercially available and the switch can work without speedup.