# An Efficient Crosstalk-Free Routing Algorithm Based on Permutation Decomposition for Optical Multi-log2N Switching Networks

Xiaofeng Liu, Youjian Zhao, Yajuan Wu

► To cite this version:

Xiaofeng Liu, Youjian Zhao, Yajuan Wu. An Efficient Crosstalk-Free Routing Algorithm Based on Permutation Decomposition for Optical Multi-log2N Switching Networks. 10th International Conference on Network and Parallel Computing (NPC), Sep 2013, Guiyang, China. pp.207-219, 10.1007/978-3-642-40820-5_18 . hal-01513777

HAL Id: hal-01513777

https://inria.hal.science/hal-01513777

Submitted on 25 Apr 2017

**HAL** is a multi-disciplinary open access
archive for the deposit and dissemination of sci-
entific research documents, whether they are pub-
lished or not. The documents may come from
teaching and research institutions in France or
abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est
destinée au dépôt et à la diffusion de documents
scientifiques de niveau recherche, publiés ou non,
émanant des établissements d'enseignement et de
recherche français ou étrangers, des laboratoires
publics ou privés.

<figure><img src="image_1.png" /></figure>

Distributed under a Creative Commons Attribution 4.0 International License
# An Efficient Crosstalk-Free Routing Algorithm Based on Permutation Decomposition for Optical Multi-log₂N Switching Networks

Xiaofeng Liu¹,³, Youjian Zhao², and Yajuan Wu³

¹ School of Computer Science and Engineering, University of Electronic Science and Technology of China, Chengdu, China

² Department of Computer Science and Technology, Tsinghua University, Beijing, China

³ School of Computer, China West Normal University, Nanchong, China
xhxfliu@163.com,
zhaoyujian@tsinghua.edu.cn,
scwuyajuan@yahoo.com.cn

**Abstract.** Optical switching networks (OSN) based on optical directional couplers (DC) may be the most promising candidate to provide a high switching rate when the speed mismatch problem between links (optical fibers) and switches is increasingly serious. Although such switches have many advantages, the DC suffers from an inherent crosstalk problem that can greatly aggravate the switching performance. Based on semi-permutations, a parallel decomposition algorithm, which is called *multi-decomposition*, is proposed in this paper for solving the optical crosstalk problem in optical multi-log₂N switching networks. According to the number of planes in a multi-log₂N network, the multi-decomposition is performed in parallel to partition a permutation into several sub-permutations, each of which is established without crosstalk within each plane. We demonstrate that our algorithm can completely remove the crosstalk in optical multi-log₂N networks when *n* is even, and that it may be generated only in the stage (*n*-1)/2 (i.e., the middle stage) when *n* is odd, but the corresponding probability of generating crosstalk is to be less than or equal to $\frac{1}{2^{(n+1)/2-1}}$. In addition, our algorithm can achieve a low complexity for decomposition a permutation due to its parallelism so that any permutations can be realized in multi-log₂N networks under the constraint of avoiding crosstalk.

**Keywords:** Permutation, Optical switching, Multi-log₂N networks, Optical crosstalk.

## 1 Introduction

The Internet is an important product of the information age. From a high-level perspective, the entire Internet architecture consists of two parts: communication links and switching nodes. At present, the capacity of these two parts has an
enormous difference. The speed of communication links has been drastically
increased with the advent of dense wavelength-division multiplexing (DWDM)
technologies, but the progress made in the switches has lagged relatively behind.
In order to solve the speed mismatch problem, the optical switches have been
widely explored in recent years.

A multi-log₂N network [1], composed of several single-log₂N networks, pos-
sesses many characteristics which are helpful for photonic switching system. As
an optical directional-coupler (DC) is introduced into this switching network to
replace the old (electronic) switching element (SE), the transmission rate of sig-
nals can achieve several T bps if the state (cross or bar) of the DC has been set
up properly. Meanwhile, A blocking, which is called crosstalk-blocking [2] and
differs from link-blocking, is introduced into this switching system by DCs. This
blocking will occur when two light signals pass through the same DC at the same
time. The crosstalk-blocking limits the scalability of switching networks so that
it is not easy to use DCs to construct a larger switching network [3] because two
signals passing through the same DC interact with each other. Therefore, the
crosstalk-blocking is an important factor to affect the quality of communication
in an optical switching network (OSN). Eliminating the crosstalk-blocking in an
OSN is just the main objective of this paper.

In this paper, we propose an efficient algorithm to eliminate the crosstalk-
blocking (abbreviated as crosstalk) of optical multi-log₂N switching networks.
The central idea of the proposed algorithm is based on the concept of a semi-
permutation in the literature [4], but we extend this concept to multiple de-
composition of a permutation for the crosstalk-free routing in optical multi-
log₂N switching networks, i.e., a permutation is first partitioned into two semi-
permutations, and is further divided into four quarter-permutations and so on.
By so doing, any two different optical signals traversing down two node-disjoint
(or DC-disjoint) paths cannot generate the optical crosstalk problem within each
plane. Thus this multiple decomposition algorithm is named *multi-decomposition*
in the remainder of the paper.

This paper is followed by four sections. Section 2 describes the crosstalk
and its common solutions. A basic network model and all related preliminaries
associated with this work are illustrated in section 3. Section 4 presents the
multi-decomposition in detail and then conclusions are given in section 5.

## 2 Crosstalk and Related Researches

Crosstalk and signal attenuation are the major problems that have been hinder-
ing the development of OSNs all the time. The signal attenuation problem can
be solved by a semiconductor optical amplifier (SOA). However, the crosstalk
cannot be removed by the SOA because the crosstalk is also amplified when the
desirable signal is amplified. Thus we must find the other methods to remove
the crosstalk in an OSN.

Indeed, it is almost impossible to eliminate the optical crosstalk totally unless
only one optical signal passes through a DC at any given time, as shown in
<figure><img src="image_2.png" /><figcaption>Fig. 1. Traversing ways in a DC</figcaption></figure>

Fig. 1. Both *space domain approach* [5] and *time domain approach* [6] are based on this idea. Essentially, the former adds the number of DCs, while at most only one of the two inputs and outputs is active at a time in a DC. Therefore, hardware cost has been sacrificed to trade the crosstalk-free routing. For the latter, a permutation is decomposed into several sub-permutations such that all connections of each sub-permutation can be established simultaneously without crosstalk, i.e., each time slot is required to route each sub-permutation and all the connections corresponding the permutation are established within several time slots in a time-division multiplexed fashion. As such, this approach uses time cost to exchange the crosstalk-free routing. In addition to these two approaches above, *wavelength dilation* [7] is the other one that eliminates the crosstalk in an OSN. A technology of *wavelength grouping method* (WGM) [7] is proposed in this approach, in which the wavelengths are partitioned into several groups so that the wavelengths in each group are widely separated, with nearby wavelengths placed in different groups, i.e., the wavelengths are selected should be far enough apart (a few nanometers) so as not to interact with each other. A drawback of this approach is that a specific structure is required to select and separate the wavelength, and then result in increasing the hardware cost. This method is adopted in [8][9] to remove the crosstalk of optical multi-log₂N networks.

The existing methods above removing the crosstalk focus usually on the single-log₂N network ([9] is an exception), and they sacrifice either time cost or hardware cost. Moreover, due to the unique path property of a log₂N network, some sub-permutations can be realized within a log₂N network in a single pass whereas the others cannot [4]. In fact, the spirit of all of these approaches mentioned above is to avoid two light signals with the same wavelength passing through a common DC at the same time, and the proposed approach in this paper is no exception. However, our algorithm uses the idea of multiple decomposition of any permutation to realize the crosstalk-free routing within each plane of a multi-log₂N network and does not increase time cost and hardware cost for optical multi-log₂N switching networks.

# 3 Basic Network Model and Preliminaries

## 3.1 Multi-log₂N Network Model

Multi-log₂N networks are vertically stacked with multiple log₂N networks, N demultiplexers and N multiplexers. The log₂N network has been composed of N(= 2n) inputs and outputs and n(= log₂N) stages. Each stage consists of N/2 2 × 2 DCs and any adjacent stages are connected by N interstage fiber links. Planes are vertically stacked to N demultiplexers (resp. multiplexers) in input
(resp. output) stage. $N$ denotes the number of source inputs and destination outputs labeled by $0, 1, \dots, N-1$ from top to bottom, $n(= \log_2 N)$ denotes the number of stages numbered by $0, 1, \dots, n-1$ from left to right, and $m$ indicates the number of planes contained in a multi-log$_2 N$ network. Since all $\log_2 N$ networks including *baseline*, *omega*, and *banyan*-type [10] have the topologically equivalent feature [11], we use an $N \times N$ ($N = 2n$) baseline network as the representative of routing planes in our work. An example of an $8 \times 8$ baseline network is shown in Fig. 2, and the corresponding multi-log$_2 N$ network is illustrated in Fig. 3.

<figure><img src="image_3.png" /><figcaption>Fig. 2. An $8 \times 8$ baseline network</figcaption></figure>

<figure><img src="image_4.png" /><figcaption>Fig. 3. An $N \times N$ multi-log$_2 N$ network ($N = 8, m = 2$)</figcaption></figure>

## 3.2 Related Preliminaries

For a $\log_2 N$ network, let $u$ and $v$ be any two SEs in stage $i$, $S_j(u)$ and $S_j(v)$ are the two sets of SEs to which $u$ and $v$ can reach in stage $(i+j)$ ($0 \le i < n-1, 1 \le j \le n-i-1$). Sets $S_j(u)$ and $S_j(v)$ certainly can satisfy one of the following properties:$S_j(u) \cap S_j(v) = \emptyset$ or $S_j(u) = S_j(v)$ [8]. For $S_j(u)$ and $S_j(v)$, the equality $S_j(u) = S_j(v)$ holds, which implies that SEs $u$ and $v$ are
sure to share the same SE in stage $(i + j)$, hence light signals passing through SEs $u$ and $v$ must generate the crosstalk phenomenon at the shared SE in stage $(i + j)$. Therefore, we call SEs $u$ and $v$ possessing $(i, j)$-buddy if the equality $S_j(u) = S_j(v)$ holds.

A theorem can be obtained immediately from the description of $(i, j)$-buddy above.

**Theorem 1.** Let $u$ and $v$ be two different DCs in stage $i$. Two optical signals going through $u$ and $v$ do not generate crosstalk in stage $(i+j)$ ($0 \le i < n-1, 1 \le j \le n-i-1$) if $u$ and $v$ do not have the $(i, j)$-buddy property.

*Proof.* if $u$ and $v$ don't have the $(i, j)$-buddy property, then optical signals going through $u$ and $v$ do not share any SEs in stage $(i + j)$, so there is no reason to occur crosstalk in stage $(i + j)$. □

# 4 Multi-decomposition Algorithm of a Permutation

## 4.1 Decomposition of a Permutation

A permutation is usually adopted to describe a mapping between inputs and outputs for a switching network. For an $N \times N$ network, suppose there is a permutation $P$ which maps input $x_i$ to output $y_i$, i.e., $P(x_i) = y_i$ where $x_i, y_i \in \{0, 1, \dots, N-1\}$ for $0 \le i < N-1$. We use the representation as equation (1) to denote this permutation.

$$P = \begin{pmatrix} x_0 & x_1 & \cdots & x_{N-1} \\ y_0 & y_1 & \cdots & y_{N-1} \end{pmatrix} \qquad (1)$$

The semi-permutation [4] is the basis of the multi-decomposition algorithm, so we proceed with the concept of semi-permutation first.

**Definition 1 ([4]).** For any permutation $P$ of $\{0, 1, \dots, N-1\}$, a partial permutation $\begin{pmatrix} x_{i_1} & x_{i_2} & \cdots & x_{i_{\lfloor N/2 \rfloor}} \\ y_{i_1} & y_{i_2} & \cdots & y_{i_{\lfloor N/2 \rfloor}} \end{pmatrix}$ is referred to as a semi-permutation, if $\{\lfloor \frac{x_{i_1}}{2} \rfloor, \lfloor \frac{x_{i_2}}{2} \rfloor, \dots, \lfloor \frac{x_{i_{\lfloor N/2 \rfloor}}}{2} \rfloor\} = \{0, 1, \dots, N/2-1\}$ and $\{\lfloor \frac{y_{i_1}}{2} \rfloor, \lfloor \frac{y_{i_2}}{2} \rfloor, \dots, \lfloor \frac{y_{i_{\lfloor N/2 \rfloor}}}{2} \rfloor\} = \{0, 1, \dots, N/2-1\}$.

Since $2(k-1) \le x_{i_k}, y_{i_k} \le 2k-1, k = 1, 2, \dots, N/2$, a semi-permutation ensures that the crosstalk can be removed in the first stage and last stage of a $\log_2 N$ network, but the crosstalk cannot be always removed in the intermediate stages. Besides, this approach needs several passes to establish a permutation in a single-$\log_2 N$ network, and hence the routing time is increased.

To eliminate the crosstalk of each stage in an optical multi-$\log_2 N$ switching network, we give the definition of the multi-decomposition based on semi-permutation (i.e., Definition 1) as follows.
**Definition 2.** For any permutation $P$ of $\{0, 1, \dots, N-1\}$, let
$$ \begin{pmatrix} x_{i_1} x_{i_2} \cdots x_{i_{\frac{N}{m}}} \\ y_{i_1} y_{i_2} \cdots y_{i_{\frac{N}{m}}} \end{pmatrix} $$

be a partial permutation of $P$, where $m$ is an integral power of 2. $\{\lfloor \frac{x_{i_1}}{m} \rfloor, \lfloor \frac{x_{i_2}}{m} \rfloor, \dots, \lfloor \frac{x_{i_{\frac{N}{m}}}}{m} \rfloor\} = \{0, 1, \dots, N/m-1\}$ and $\{\lfloor \frac{y_{i_1}}{m} \rfloor, \lfloor \frac{y_{i_2}}{m} \rfloor, \dots, \lfloor \frac{y_{i_{\frac{N}{m}}}}{m} \rfloor\} = \{0, 1, \dots, N/m-1\}$ are used to partition this partial permutation such that the resulting sub-permutation is smaller than semi-permutation in size.

This decomposition method is referred to as *multi-decomposition* for the multiple decompositions. The resulting partial permutation of multi-decomposition of a permutation is still called sub-permutation from now on.

Note that $m$ denotes the number of sub-permutations into which the full permutation is divided, and each sub-permutation contains $N/m$ connections of the full permutation. An example is given to understand this partition process as follows.

*Example 1.* For $N = 16, m = 4$, and a permutation

$$ P = \begin{pmatrix} 0 & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & 10 & 11 & 12 & 13 & 14 & 15 \\ 1 & 0 & 9 & 5 & 6 & 8 & 10 & 13 & 15 & 2 & 3 & 4 & 7 & 11 & 14 & 12 \end{pmatrix} $$

Step 1. Run the multi-decomposition algorithm ($m = 2$) to get two semi-permutations $P_1$ and $P_2$.

$$ P_1 = \begin{pmatrix} 0 & 3 & 5 & 6 & 8 & 10 & 12 & 15 \\ 1 & 5 & 8 & 10 & 15 & 3 & 7 & 12 \end{pmatrix} $$

$$ P_2 = \begin{pmatrix} 1 & 2 & 4 & 7 & 9 & 11 & 13 & 14 \\ 0 & 9 & 6 & 13 & 2 & 4 & 11 & 14 \end{pmatrix} $$

Step 2. For all semi-permutations, run the multi-decomposition algorithm ($m = 4$) again in parallel to get four quarter-permutations, $P_{11}, P_{12}, P_{21}$ and $P_{22}$.

$$ P_{11} = \begin{pmatrix} 0 & 5 & 8 & 12 \\ 1 & 8 & 15 & 7 \end{pmatrix}, P_{12} = \begin{pmatrix} 3 & 6 & 10 & 15 \\ 5 & 10 & 3 & 12 \end{pmatrix} $$

$$ P_{21} = \begin{pmatrix} 1 & 7 & 11 & 13 \\ 0 & 13 & 4 & 11 \end{pmatrix}, P_{22} = \begin{pmatrix} 2 & 4 & 9 & 14 \\ 9 & 6 & 2 & 14 \end{pmatrix} $$

Step 3. Multi-decomposition ends when the number of sub-permutations is $m$, or else goes to step 2. Since $m$ is equal to 4 in this example, the multi-decomposition algorithm should be stop.

Fig. 4 illustrates the switching of these four quarter-permutations in a multi-log$_2N$ network ($N = 16, m = 4$).

Now, we answer the following two questions about the multi-decomposition. The first one is how many times the multi-decomposition algorithm should be performed when a full permutation needs to be decomposed, i.e., what is the proper value of $m$? The other is the effectiveness of this algorithm. The proper
<figure><img src="image_5.png" /><figcaption>**Fig. 4.** Switching of four quarter-permutations in a multi-log₂N network (N = 16, m = 4)</figcaption></figure>

value of *m* is determined by the number of copies in a multi-log₂N network. Since the rearrangeable nonblocking (RNB) network is considered in our work, the number of copies which is needed to build a rearrangeable nonblocking multi-log₂N network is 2[**n**/2] [1]. Therefore, the value of *m* is taken 2[**n**/2] in this paper. For the second one, we use the following theorem to give an answer.

**Theorem 2.** For a multi-log₂N network, any permutation *P* can be partitioned into *m* sub-permutations, where *n* = log₂N and *m* = 2[**n**/2].

*Proof.* The multi-decomposition is implemented by an iterative manner. A permutation is first partitioned into two semi-permutations, and then each semi-permutation is further partitioned into its own two semi-permutations and so on. This partitioning process cannot stop until the number of sub-permutations is equal to *m*. According to this partitioning process, this theorem is essentially equivalent to a proposition that "Any permutation can be decomposed into two semi-permutations." This proposition can be easily proved by using the P. Hal-l's distinct system representative [12]. The detailed proof can be found in [4], so we can use a method similar to one in [4] to prove this theorem. Due to space limitation, the detailed proof is omitted here. □

Theorem 2 guarantees the feasibility of the multi-decomposition of permu-
tations. Next, we prove that the multi-decomposition is effective in removing
the crosstalk problem. We first give the following concepts of *input set* (IS) and
*output set* (OS).

**Definition 3.** For an $N \times N$ ($N = 2n$) multi-log$_2$N network, there are $n$ ($= \log_2 N$) stages.
(1) If $n$ is even, the $N$ inputs (resp. outputs) of the multi-log$_2N$ network are divided equally into $i = 2^{n/2}$ input (resp. output) sets from top to bottom. These sets are referred to as $I_0, I_1, \dots, I_{i-1}$ and $O_0, O_1, \dots, O_{i-1}$, respectively. As shown in Fig. 5(a).

(2) If $n$ is odd, the $N$ inputs (resp. outputs) of the multi-log$_2N$ network are divided equally into $i = 2^{(n+1)/2}$ input (resp. output) sets from top to bottom. These sets are also referred to as $I_0, I_1, \dots, I_{i-1}$ and $O_0, O_1, \dots, O_{i-1}$, respectively. As shown in Fig. 5(b).

<figure><img src="image_6.png" /><figcaption>Fig. 5. The diagram of input and output sets</figcaption></figure>

Note that the order of input and output ports in each set is consecutive and ascending, and that the number of ports is equal. An important fact obtained from Definition 2 and 3 is that different connections of a sub-permutation always start from different ISs and end in different OSs. Thus every sub-permutation does not have any crosstalk in the input and output stage. The following theorem tells us that the optical crosstalk does not occur in the intermediate stages, either.

**Theorem 3.** For an $N \times N$ ($N = 2n$) multi-log$_2N$ network, $n = \log_2 N$, and $m = 2^{\lceil n/2 \rceil}$. Multi-decomposition guarantees that

(1) The crosstalk never occurs in the optical multi-log$_2N$ network when $n$ is even;

(2) The crosstalk may be possible only in the center stage (i.e., stage-$(n-1)/2$) when $n$ is odd, but the probability of generating crosstalk is less than or equal to $\frac{1}{2^{\lceil(n+1)/2\rceil-1}}$.

*Proof.* (1) $M$ is equal to $2^{n/2}$ if $n$ is even. According to Definition 3, $N$ input and output ports are divided evenly into ISs and OSs, and every sub-permutation contains $N/m(= 2^{n/2})$ connections. As stated previously, the crosstalk is never generated in the input stage and output stage (by Definition 2 and 3). We now prove that the crosstalk does not occur in the intermediate stages. We first consider the first $n/2$ stages. If the crosstalk has occurred in stage $j$ ($1 \le$
$j \le \frac{n}{2} - 1$), there are at least two different DCs $u$ and $v$ in the same IS of a plane satisfying the (0, j)-buddy (by Theorem 1), but only one connection in a sub-permutation starts from an IS within each plane at any time. This contradiction proves our conclusion that no crosstalk occurs in the first $n/2$ stages. In the last $n/2$ stages, the crosstalk can also be avoided, which can be proved by contradiction. Once the crosstalk is generated, some connections in the same plane will be routed to the same OS, but this case is also impossible. In fact, these two cases are entirely symmetrical.

(2) If $n$ is odd, $m = 2^{(n-1)/2}$. The crosstalk does not occur in the first $(n-1)/2$ stages and last $(n-1)/2$ stages, but it possibly emerges in the center stage. Take the Fig. 5(b) as an example, two connections $(2 \to 3)$ and $(7 \to 5)$ share a common DC at the middle stage, now the crosstalk has occurred, but no DC can be shared in the first $(n-1)/2$ stages and last $(n-1)/2$ stages. Following a similar argument to the first case ($n$ is even), we can prove that when $n$ is odd, the crosstalk is never generated in the first $(n-1)/2$ stages and last $(n-1)/2$ stages. Here we fix our attention on the proof of the probability of generating crosstalk in the middle stage. $\square$

For brevity and clarity, we introduce the following definitions of *buddy input set* (BIS) and *buddy output set* (BOS). The set BIS is comprised of all input sets $I_k$ sharing a common DC at the center stage, and the set BOS is comprised of all output sets $O_k$ sharing the same DC at the center stage. For example, $I_0$ and $I_1$ belong to $BIS_0$ because they share the same DC a in the center stage, i.e., $BIS_0 = \{I_0, I_1\}$; similarly, $BOS_0 = \{O_0, O_1\}$. As shown in Fig. 6.

<figure><img src="image_7.png" /><figcaption>**Fig. 6.** The baseline network when $n$ is odd ($n = 5$)</figcaption></figure>
According to the previous definitions, some good characteristics of the multi-decomposition are summarized as follows:

- It is impossible that two (or more) connections in each plane start from the same IS and head for the same OS (by Definition 3);

- Two connections sharing the same DC in the center stage should come from the same BIS and head for the same BOS;

- According to the distinct BISs, all DCs in the center stage are partitioned into $i/2$ sections (as the dashed boxes in Fig. 6) such that at most one DC possibly generates the crosstalk within each section at any time.

These characteristics imply that all DCs in the same section are mutually exclusive in generating crosstalk, and that the corresponding DCs among distinct sections are mutually exclusive in generating crosstalk as well. Thus, these $i/2$ sections possess the identical statistical nature, we may take the first DC $a$ (the shadow box in Fig. 6) in the first section as the representative to discuss the probability of generating crosstalk.

Any inputs in each IS can be connected to arbitrary OS with equivalent probability, i.e., $P\{I_k \to O_j\} = 1/i(0 \le k, j < i)$, so the probability of generating crosstalk in SE $a$ is

$$ 
\begin{aligned}
P_{\text{crosstalk}}(a) &= P\{(I_0 \to O_0, I_1 \to O_1) \cup (I_0 \to O_1, I_1 \to O_0)\} \\
&= P\{(I_0 \to O_0, I_1 \to O_1) + P\{(I_0 \to O_1, I_1 \to O_0)\}\} \\
&= P\{I_0 \to O_0\}P\{I_1 \to O_1|I_0 \to O_0\} + \\
&\qquad P\{I_0 \to O_1\}P\{I_1 \to O_0|I_0 \to O_1\} \\
&= \frac{1}{i} \times \frac{1}{i-1} + \frac{1}{i} \times \frac{1}{i-1} \\
&= \frac{2}{i(i-1)}
\end{aligned} 
\quad (2) $$

On the other hand, at most one DC generates crosstalk possibly in each section in any given time. Then the probability of generating crosstalk in each section, which is denoted by $P_{\text{crosstalk}}(\text{section})$, is equal to $P_{\text{crosstalk}}(a)$. Therefore the probability of generating crosstalk in entirely plane is

$$ 
\begin{aligned}
P_{\text{crosstalk}}(\text{plane}) &= P\{\bigcup_{k=0}^{i/2} P_{\text{crosstalk}}(\text{section}_k)\} \\
&\le \bigcup_{k=0}^{i/2} P_{\text{crosstalk}}(\text{section}_k) \\
&= \bigcup_{k=0}^{i/2} P_{\text{crosstalk}}(a) \\
&= \frac{1}{i-1}
\end{aligned} 
\quad (3) $$

Now, substituting $i = 2^{(n+1)/2}$ into expression (3), we obtain $P_{\text{crosstalk}}(\text{plane}) \le \frac{1}{2^{(n+1)/2}-1}$.
## 4.2 Implementation of the Multi-decomposition and Its Analysis

In this subsection, we will discuss the implementation of the multi-decomposition algorithm of permutations and its time complexity.

There is a permutation as the equation (1), in which input $x_i$ is mapped to output $y_i$ ($0 \le i \le N - 1$). Based on the semi-permutation [4], we design the decomposition algorithm of a permutation as Algorithm 1 in order to design our multi-decomposition algorithm. The Algorithm 1 contains three parameters that are $P$, $N$ and $k$. These parameters denote the permutation to be decomposed, the number of requests and the decomposition levels, respectively.

**Algorithm 1:** Dichotomy-of-permutation (*P*, *N*, *k*)

**Input:** Any permutation *P* contains *N* request pairs.

**Output:** Two sub-permutations $P_1$ and $P_2$

1. Two vertex sets $V_I = \{A_{i_0}, A_{i_1}, \dots, A_{i_{N/2^k-1}}\}$ and $V_O = \{A_{o_0}, A_{o_1}, \dots, A_{o_{N/2^k-1}}\}$ are built from the permutation *P*, where $A_{i_j} = \{x_{j \cdot 2^k}, x_{j \cdot 2^k+1}, \dots, x_{j \cdot 2^k+2^k-1}\}$, $A_{o_j} = \{y_{j \cdot 2^k}, y_{j \cdot 2^k+1}, \dots, y_{j \cdot 2^k+2^k-1}\}$, $0 \le j < N/2^k$

2. Construct a bipartite graph $G = (V_I, V_O, E)$ based on $V_I$ and $V_O$. A edge $e \in E$ is associated with a request pair $(x_j, y_j)$, where $x_j \in A_{i_j}$ and $y_j \in A_{o_j}$.

3. Traverse the bipartite graph and color the two adjacent edges of the same vertex with different colors, then all edges with the same color are grouped into forming a sub-permutation. Since the chromatic number of the bipartite graph is two [4], the permutation can be partitioned into two sub-permutations $P_1$ and $P_2$.

The multi-decomposition algorithm can be implemented by calling Algorithm 1 repeatedly. Let $m$ be the integral power of 2, i.e., $m = 2^k(1 \le k \le n)$. The multi-decomposition algorithm becomes semi-permutation decomposition in [4] when $k$ is 1. One exactly connection is established in each plane when $k$ equals to $n$, thus the crosstalk and blocking can be avoided undoubtedly. In the other cases, Algorithm 1 is called repeatedly $k$ rounds and is executed $2^{i-1}(1 \le i \le k)$ times in parallel in each round. The corresponding algorithm is demonstrated as Algorithm 2. As the Example 1 mentioned earlier, $N = 16$, $m = 4(= 2^2)$, and the Algorithm 1 has been called 2 rounds. Two semi-permutations are obtained after the first round, and four quarter-permutations are got after the second round.

A permutation is partitioned into $m$ sub-permutations, and the decomposition process is similar to that of building a binary tree with $m$ sub-permutations as leaves. Furthermore, this process is carried out in parallel, so the time complexity of Algorithm 2 is $O(log_2m)$. On the other hand, the Algorithm1 has
**Algorithm 2.** multi-decomposition of permutations

**Input:** *N* requests contained by a permutation *P*;

**Output:** *M* sub-permutations, *m* = 2^*k*; *k* is a natural number.

For *i* = 1 to *k* do

For *j* = 1 to 2^(*i*−1) do in parallel

`{P[j, 1], P[j, 2]}=Dichotomy-of-permutation (P[j], N, i);`

End parallel

End for

O(*N*) time complexity, so the overall complexity of Algorithm 2 is O(Nlog₂*m*). We will further improve Algorithm 1 by parallelism in the future so that the time cost can be reduced much.

5 Conclusions

In this paper, we proposed an efficient algorithm called multi-decomposition to remove the crosstalk in optical multi-log₂N switching networks. A permutation is partitioned into several sub-permutations by using our decomposition algorithm, which ensures that each sub-permutation can be connected without crosstalk within each plane of optical multi-log₂N networks. Compared with other approaches, our algorithm does not increase the time cost and hardware cost. Although semi-permutation [4] is the foundation of our algorithm, we have extended the concept of semi-permutation to multiple decomposition of a permutation and successfully solved the crosstalk problem of optical multi-log₂N switching networks.

We have proved the validity of the multi-decomposition algorithm. The crosstalk can be entirely removed in optical multi-log₂N networks when *n* (= log*N* ) is even. If *n* is odd, crosstalk may be possible only in the middle stage (i.e., stage-(n-1)/2), but the probability of generating crosstalk is proved to be less than or equal to 1/(2((n+1)/2)-1). What's more, our algorithm has low time complexity to decompose a permutation due to its parallelism so that any permutations can be routed without crosstalk in an optical multi-log₂N switching network.

**Acknowledgments.** This work is supported by National Natural Science Foun-
dation of China (No.61073167),National High Technology Development Program
of China (No.2011AA010704),Projects in the National Science & Technology Pil-
lar Program(2011BAK08B05-02) and Major Training Program of China West
Normal University (09A003).

References

1. Lea, C.T.,: Multi-log₂N networks and their applications in high-speed electronic and photonic switching systems. IEEE Transactions on Communications 18(10),1740–1749 (1990)
2. Vaez, M.M., Lea, C.T.: Strictly nonblocking directional-coupler-based switching networks under crosstalk constraint. IEEE Transactions on Communications 48(2), 316–323 (2000)

3. Hinton, H.S.: An introduction to photonic switching fabrics. Plenum, New York, (1993)

4. Yang, Y., Wang, J., Pan, Y.: Permutation capability of optical multistage interconnection networks. Journal of Parallel and distributed Computing 60(1), 72–91 (2000)

5. Padmanabhan, K., Netravali, A.N.: dilated networks for photonic switching. IEEE Transactions on Communications com-35(12), 1357-1365 (1987)

6. Qiao, C.: A time domain approach for avoiding crosstalk in optical blocking multi-stage interconnection networks. Jouranl of Lighwave Technology 12(10), 1854–1862 (1994)

7. Sharony, J., Cheung, K.W., Stern, T.E.: The wavelength dilation concept in light-wave networks – Implementation and system considerations. IEEE Journal of Light-wave Technology 11(5/6), 900-907 (1993)

8. Zheng, S.Q., Gumaste, A.,Hong Shen: A parallel self-routing rearrangeable non-blocking multi-log₂N photonic switching networks. IEEE Transactions on Networking 18(2), 529–539 (2010)

9. Wong, T.S., Lea, C.T.: Crosstalk reduction through wavelength assignment in WDM photonic switching networks. IEEE Transactions on Communications 49(7), 1280–1287 (2001)

10. Goke, G.R., Lipovski, G.J.: Banyan networks for partitioning multiprocessor systems. In: Proceedings of 1st International Symposium on Computer Architecture, pp.21–28. ACM Press, New York (1973)

11. Wu, C.L., Feng, T.Y.: On a class of multistage interconnection networks. IEEE Transactions On Computers C-29(8), 694–702 (1980)

12. Hall, P.: On representatives of subsets. Journal London Mathematical Society 10(1), 26–30 (1935)