1996 IEEE Symp. on High Performance Computer Architecture (HPCA-2)

On the Multiplexing Degree Required to Embed Permutations
in a Class of Networks with Direct Interconnects

	Chunming Qiao and Yousong Mei
        Department of Electrical and Computer Engineering
        State University of New York at Buffalo
        Buffalo, New York 14260
	qiao@photon.eng.buffalo.edu

Abstract

Each physical link in a directly interconnected network 
can be multiplexed to create several virtual channels.
There are two approaches
for establishing a connection in such a multiplexed network. One is called
Path Multiplexing (PM), 
in which the same channel has to be used on each
link along a path and the other is Link Multiplexing (LM), 
in which different channels may
be used on different links along a path. 

In this paper, we study the problem of embedding permutations 
in a multiplexed network with a focus on comparing the LM approach
with the PM approach. Specifically, we determine the threshold (minimal)
multiplexing degrees needed for a network to be rearrangeably nonblocking in 
LM and PM, respectively. 
We found that PM and LM are equally good in linear arrays,
and LM is only slightly better than PM in rings, meshes and tori.
Given that LM requires more sophisticated switches to interchange virtual
channels, PM may be more cost-effective in the implementations of networks
with multiplexed optical interconnects.