Parallel Routing Algorithms for NonblockingElectronic and Photonic Switching NetworksEnyue Lu, Member, IEEE, and S.Q. Zheng, Senior Member, IEEEAbstract—We study the connection capacity of a class of rearrangeable nonblocking (RNB) and strictly nonblocking (SNB) networkswith/without crosstalk-free constraint, model their routing problems as weak or strong edge-colorings of bipartite graphs, and proposeefficient routing algorithms for these networks using parallel processing techniques. This class of networks includes networksconstructed from Banyan networks by horizontal concatenation of extra stages and/or vertical stacking of multiple planes. We presenta parallel algorithm that runs in Oðlg2NÞ time for the RNB networks of complexities ranging from OðN lg NÞ to OðN1:5lg NÞ crosspointsand parallel algorithms that run in Oðminfdlg N;ffiffiffiffiffiNpgÞ time for the SNB networks of OðN1:5lg NÞ crosspoints, using a completelyconnected multiprocessor system of N processing elements. Our algorithms can be translated into algorithms with an Oðlg N lg lg NÞslowdown factor for the class of N-processor hypercubic networks, whose structures are no more complex than a single plane in theRNB and SNB networks considered.Index Terms—Banyan network, crosstalk, optical switching, rearrangeable nonblocking network, strictly nonblocking network, switchcontrol, self-routing, graph coloring, parallel algorithm.æ1INTRODUCTIONTO build a large IP router with capacity of 1 Tb/s andbeyond, either electronic or optical switching can beused. The deployment of optical fibers as a transmissionmedium has prompted searching for the solution to theproblem of speed mismatching between transmission andswitching. Optical routers have better scalability thanelectronic routers in terms of switching capacity. However,the required optical technologies are immature for all-optical switching to happen any time soon. A hybridapproach in which optical signals are switched, but bothswitch control and routing decisions are carried outelectronically, becomes more practical. Advances in elec-tro-optic technologies provide a promising choice to meetthe increasing demands for high channel bandwidth andlow com munication latency in optical communication.However, due to the nature of optical devices, opticalswitches hold their own challenges [26].1.1 Crosstalk in Photonic SwitchingA switching network usually comprises a number ofswitching elements (SEs), grouped into several stagesinterconnected by a set of links. Without loss of generality,we assume that an SE is of size 2  2, i.e., it has two inputsand two outputs. The two inputs (respectively, outputs) ofan SE intending to be connected with the same output(respectively, input) causes output link conflict(respectively,input link conflict). If an I/O connection path does not haveany link conflict with other connection paths, it is called aconflict-free path. Nonblocking switching networks havebeen favored in switching systems because they can be usedto set up any conflict-free one-to-one I/O connection paths.There are three types of nonblocking networks: strictlynonblocking (SNB), wide-sense nonblocking (WSNB),andrearrangeable nonblocking (RNB) [3], [13]. In both SNB andWSNB networks, a connection can be established from anyidle input to any idle output without disturbing existingconnections. In SNB networks any of available conflict-freepaths for a connection can be chosen and in WSNBnetworks, however, a rule must be followed to chooseone. The high degree of connection capability in SNB andWSNB networks is at a high hardware cost. RNB networks,usually constructed with lower hardware cost, can establisha conflict-free path for the connection from any idle input toany idle output if the rearrangement of existing connectionsis allowed.In an electrical switching network, links are wires andSEs are simple crossbar switches. In an optical switchingnetwork, links are implemented by optical waveguides andSEs can be implemented by electro-optical SEs such ascommon lithium-niobate (LiNbO3) SEs (e.g., [11], [12], [28]).Each electro-optical SE is a directional coupler with twoinputs and two outputs. Depending on the amount ofvoltage at the junction of two waveguides, optical signalscarried on either of two inputs can be coupled to either oftwo outputs. An electronically controlled optical SE canhave switching speed ranging from hundreds of picose-conds to tens of nanoseconds [27]. However, due to thenature of optical devices, optical switches introduce addi-tional challenges. One problem is path dependent loss, thesubstantial signal loss is directly proportional to connectiondiameter, the number of SEs on the longest connection path.702 IEEE TRANSACTIONS ON PARALLEL AND DISTRIBUTED SYSTEMS, VOL. 16, NO. 8, AUGUST 2005. E. Lu is with the Department of Mathematics and Computer Science,Richard A. Henson School of Sc ience and Technology, Sa lisburyUniversity, 1101 Camden Ave., Salisbury, MD 21801.Email: [email protected].. S.Q. Zheng is with the Department of Computer Science, Erik JonssonSchool of Engineering and Computer Science, Box 830688, MS EC 31,University of Texas at Dallas, Richardson, TX 75083-0688.Email: [email protected] received 16 Sept. 2003; revised 1 June 2004; accepted 30 Oct.2004; published online 22 June 2005.For information on obtaining reprints of this article, please send e-mail to:[email protected], and reference IEEECS Log Number TPDS-0170-0903.1045-9219/05/$20.00 ß 2005 IEEE Published by the IEEE Computer SocietyAnother problem is crosstalk,1which is caused by undesiredcoupling between signals with the same wavelength carriedin two waveguides so that two signal channels interferewith each other within an SE.The crosstalk problem in photonic switching networksadds a new dimension of blocking, called node conflict ,which happens when more than one connection with thesame wavelength passes through the same SE at the sametime. A technique called space dilation was introduced toavoid node conflict by increasing the number of SEs in aswitching network (e.g., [15], [16], [24], [29], [30], [31], [33]).1.2 Motivation and Main ResultsIn a switching network, when more than one input requestto be connected with the same output, output contentionoccurs. Output contentions can be resolved by switchscheduling. For a set of connection requests without outputcontentions, the process of establishing conflict-free con-nection paths to satisfy