Embedding N × N Crossbar Switches into ILLIAC(N, N ？ 1) Torus Networks for Optical Interconnection Networks

A focus of research for crossbar switches has been to reduce the number of switch elements, each of which not only occupies a relatively large area but also costs a lot when implemented with optical devices. We point out that conventional crossbar switches, where is the switch size, actually function as switches and thus have redundant switch elements to be removed. We show that ILLIAC torus networks, which have a less number of switching elements than crossbar switches of an identical switch size, are equivalent to true crossbar switches. We describe in detail how the crossbar switches can be embedded into the equivalent torus networks. We also discuss switch control complexity of the equivalent torus networks and show that it can be reduced to (1). 1. Introduction The crossbar switch (XBS) is the practical choice for implementing switching fabrics in optical networks [1]. There are two typical configurations of conventional optical XBSs [2]. The first type, which uses transfer switches and constitutes a full-mesh network, is strict-sense nonblocking but suffers from a large power loss, crosstalk, and wiring area to be out of the scope in this paper. We consider the second type of optical XBSs that is composed of switching elements, each of which has two connection states (i.e., bar and cross), and is wide-sense nonblocking. We refer to the optical switching element, typically implemented with an optical directional coupler, as a cell for simplicity. An XBS has up to cells, where is the switch size. A focus of research has been to reduce the number of cells (or simply crosspoints) required for optical XBSs, because each individual optical cell occupies a relatively large space, consumes power, and costs a lot [3]. In 1968, Kautz et al. devised different switches with fewer than cells, all of which were derived from XBSs, for example, triangular switches with crosspoints [4], while they are rearrangeably nonblocking unlike XBSs. In 1988, Smyth gave a pruned XBS with cells, preserving wide-sense nonblocking capability [5]. In 2008 Obara suggested in a letter a new pruned XBS with cells embedded into ILLIAC torus networks [6]. In his discussion, however, the question of how conventional XBSs can be transformed into the ILLIAC torus networks has been left open. In this paper, we begin with some definitions and notations for XBSs necessary to later discussion. Then we describe the transformation process and discuss switch control complexity of the equivalent torus networks. 2. Definitions and Notations for XBSs We consider a conventional XBS composed of