Routing and wavelength assignment for exchanged crossed cubes on ring-topology optical networks

Abstract

The exchanged crossed cube, denoted by $\textit{ECQ}(s, t)$, is a novel graph with fewer edges and smaller diameter compared to other variations of the corresponding hypercube. The ring topology, denoted by $R_n$, is one of the most popular topologies in Wavelength division multiplexing optical networks. This paper addresses the routing and wavelength assignment problem for realizing $\textit{ECQ}(s, t)$ communication pattern on $R_n$, where $n=s+t+1$. We propose an embedding scheme. Base on the embedding scheme, a wavelength assignment algorithm using $2^{s+t-2}+\lfloor 2^t/3\rfloor$ wavelengths is devised. We show that the wavelength assignment algorithm uses no more than 1.25 times of wavelengths compared to the optimal wavelength number, i.e., it is a factor 1.25 approximation algorithm. Moreover, the number of additional required wavelengths is no more than $\lfloor 2^{t-1}/3\rfloor$.

1 Introduction

Owing to many promising features, such as extremely high bandwidth, extremely small communication delay and extremely low power consumption, optical networks have been extensively adopted as the communication media between processors within parallel computers, e.g., optical network-on-chip approach (Liu and Yan 2013; Shacham et al. 2008; Ye et al. 2012). Moreover, optical networks also have intensive applications in web browsing and video conference (Yu et al. 2014a).

Wavelength division multiplexing (WDM in short) technique has been widely exploited in optical networks. In WDM optical networks, the bandwidth of an optical link is divided into multiple communication channels, each represented by its designated wavelengths. This way, multiple data streams can be transmitted simultaneously through a same optical link, greatly enhancing the communication efficiency.

A WDM optical networks consists of routing nodes interconnected by point-to-point links. An optical link is usually assumed to be bidirectional. It is implemented by a pair of unidirectional optical fibers with reversed directions. Because of the high cost for optoelectrical conversions at intermediate nodes, wavelength converters are not considered is this paper. In this case, end-to-end lightpaths are usually set up between each pair of source–destination nodes. For more details of WDM optical networks, please refer to Sivalingam and Subramaniam (2000). On the other hand, ring topology has many advantages, such as ease in operation, administration and maintenance, and therefore, it has been considered as one of most promising topologies in WDM optical networks (Chen and Shen 2010; Liu and Wu 2017; Yu et al. 2014a; Yuan and Melhem 1998).

Because the wavelength resource is restricted in WDM optical networks, and therefore, methods of minimizing the number of required wavelengths is important. The primary issue, to be addressed in this paper, is the routing and wavelength assignment (RWA) problem (Zang et al. 2000). In the RWA problem, a proper lightpath and its corresponding wavelength are selected for each connection of a given communication pattern, which satisfies the wavelength continuity constraint and the distinct wavelength constraint so that the number of required wavelengths is minimized. In recent years, the study of the RWA problem for various communication patterns realized on a variety of optical network topologies has received considerable interest (Chen and Shen 2010; Chen et al. 2011; Liu 2015; Liu and Wu 2017; Yu et al. 2014a, b, 2012; Yuan and Melhem 1998; Zhang et al. 2013, 2014). Some applications of the RWA problem on WDM optical networks are also discussed, such as fast Fourier transform computation (Chen et al. 2006) and bitonic sorting (Zhang et al. 2015).

The array-based network is composed of four different types of topologies, i.e., linear array, ring, mesh and torus (Chen and Shen 2010; Yuan and Melhem 1998). Yuan and Melhem studied the RWA problems for hypercube communication patterns on array-based networks (Yuan and Melhem 1998). Their results are improved by Chen and Shen in 2010. They also addressed the RWA problems for hypercube communication patterns on three-degree and four-degree chordal rings in Chen et al. (2011). Yu et al. investigated the RWA problems for ternary n-cube communication patterns on linear array (Yu et al. 2012), ring (Yu et al. 2014a) and mesh (Yu et al. 2014b), respectively. Zhang et al. tackled the RWA problems for both half-duplex and full-duplex crossed cube (Zhang et al. 2013) and locally twisted cube Zhang et al. (2014) communication patterns on linear arrays, respectively. Liu et al. explored the RWA problems for exchanged hypercube communication patterns on linear arrays (Liu 2015) and rings (Liu and Wu 2017), respectively. On the other hand, the RWA problems for realizing hypercube (Zhang et al. 2015) and ternary n-cube (Yu et al. 2013) communication patterns under the dynamic wavelength strategies have been discussed, recently.

The exchanged hypercube, denoted by EH (s, t), is an edge-diluted variation of the hypercube proposed by Loh et al. (2005). It effectively reduces the number of edges from the corresponding hypercube while still preserving numerous desirable properties. The crossed cube $\textit{CQ}_n$, proposed by Efe (1992), is another famous variation of the hypercube with smaller diameter (nearly half that of the corresponding hypercube). Base on the exchanged hypercube and the crossed cube, Li et al. (2013) proposed a novel interconnection networks called exchanged crossed cube $\textit{ECQ}(s, t)$. It retains most of the desirable properties of the exchanged hypercube, while combines many attractive features of the crossed cube. Some related works on exchanged crossed cube have been studied, such as connectivity (Ning et al. 2015), super connectivity (Ning 2016), cycles embedding (Zhou et al. 2017) and optimal path embedding (Zhou et al. 2017). To the best of our knowledge, however, the RWA problem for realizing exchanged crossed cube communication patterns on ring-topology WDM optical networks has not been investigated.

Let $L_n$ and $R_n$ denote a linear array topology and a ring topology, respectively. In Liu and Chang (2018), we addressed the RWA problem for realizing $\textit{ECQ}(s, t)$ communication patterns on $L_n$, where $n=s+t+1$. We prove that the congestion for $\textit{ECQ}(s, t)$ on $L_n$ is equal to $2^{s+t-1}+\lfloor 2^t/3\rfloor$, which is the lower bound of the optimal wavelength number. An optimal wavelength assignment algorithm achieving this bound is also provided. However, when considering a ring topology in the RWA problem, it is hard to devise an optimal wavelength assignment algorithm (Chen and Shen 2010; Liu and Wu 2017; Yu et al. 2014a; Yuan and Melhem 1998). Instead in this paper, we use an approximation algorithm (Vazirani 2013) to address the RWA problem.

To address the RWA problem for realizing $\textit{ECQ}(s, t)$ communication patterns on $R_n$, the rest of this paper is organized as follows. Section 2 introduces some preliminary knowledge. Section 3 proposes an embedding scheme and design a wavelength assignment algorithm. Finally, we conclude the paper in Sect. 4.

2 Preliminaries

In Sects. 2.1 and 2.2, the exchanged crossed cube and the ring topology are introduced, respectively. In Sect. 2.3, we detail the concepts about embedding schemes and congestions. In Sect. 2.4, we give formal definition of the RWA problem for realizing exchanged crossed cube communications patterns on ring-topology WDM optical networks, and describe its restricted constraints.

2.1 The exchanged crossed cube

The following definitions are given by Efe to define the crossed cube.

Definition 1

(Efe 1992) Two binary strings $x=x_1x_0$ and $y=y_1y_0$ are pair related, denoted by $x\!\sim \!y$, if and only if $(x,y)\in \{(00,00),(10,10),(01,11),(11,01)\}$.

Let G be a graph and $b\in \{0,1\}$. We use $G^{\langle b\rangle }$ to denote the graph obtained from G by prefixing every vertex with a label b. Let n be a nonnegative integer. The n-dimensional crossed cube, denoted by $\textit{CQ}_n$, is a graph defined inductively as follows:

Definition 2

(Efe 1992) $\textit{CQ}_1$ is the complete graph on two nodes with labels 0 and 1. For $n \ge 2$, $\textit{CQ}_n$ consists of two subcubes $\textit{CQ}_{n-1}^{\langle 0\rangle }$ and $\textit{CQ}_{n-1}^{\langle 1\rangle }$ such that two vertices $u=0u_{n-2}\cdots u_1u_0\in V(\textit{CQ}_{n-1}^{\langle 0\rangle })$ and $v=1v_{n-2}\cdots v_1v_0\in V(\textit{CQ}_{n-1}^{\langle 1\rangle })$ are joined by an edge if and only if

• (i) $u_{n-2}=v_{n-2}$ if n is even, and

• (ii) $u_{2i+1}u_{2i} \sim v_{2i+1}v_{2i}$ for $0\le i<\lfloor (n-1)/2\rfloor$.

Let $k \ge 1$ and $u=u_{k-1}\cdots u_0\in \{0,1\}^k$ be a binary string of length k. For $0\le i\le j<k$, we use $u_{j,i}$ to denote the substring $u_ju_{j-1}\cdots u_i$ of u and let Dec$(u_{j,i})$ stand for the decimal of $u_{j,i}$. We use $\oplus$ to stand for the exclusive-OR operator. For $0\le i<j$, let $[i,j]=\{i,i+1,\ldots ,j\}$. For positive integers s and t, the exchanged crossed cube $\textit{ECQ}(s, t)$ is an undirected graph defined as follows.

Definition 3

(Li et al. 2013) The vertex set of exchanged crossed cube $\textit{ECQ}(s, t)$ is

$V= \{u=u_{s+t}\cdots u_1u_0|\,u_i\in \{0,1\}$ for $i\in [0,s+t]\}.$ The edge set is composed of three types of disjoint sets $E_1,E_2$ and $E_3$ described below:

$E_1=\{(u,v)\in V\times V|\,u\oplus v=1\}$.

$E_2$ includes the edges (u, v) for $u_{s+t,t+1}=v_{s+t,t+1}$, $u_0=v_0=1$, and there exists an $\ell \in [1,t]$ such that $u_{t,\ell +1}=v_{t,\ell +1}$, $u_\ell \ne v_\ell$, $u_{\ell -1}=v_{\ell -1}$ if $\ell$ is even, and $u_{2i}u_{2i-1} \sim v_{2i}v_{2i-1}$ for $1\le i<\lfloor (\ell +1)/2\rfloor$.

$E_3$ includes the edges (u, v) for $u_{t,1}=v_{t,1}$, $u_0=v_0=0$, and there exists an $\ell \in [t+1,t+s]$ such that $u_{s+t,\ell +1}=v_{s+t,\ell +1}$, $u_\ell \ne v_\ell$, $u_{\ell -1}=v_{\ell -1}$ if $\ell -t$ is even, and $u_{2i+t}u_{2i+t-1} \sim v_{2i+t}v_{2i+t-1}$ for $1\le i<\lfloor (\ell -t+1)/2\rfloor$.

Accordingly, $\textit{ECQ}(s, t)$ contains $2^{s+t+1}$ vertices. It is obvious that a vertex u with the rightmost bit 0 (respectively, rightmost bit 1) has degree $s+1$ (respectively, $t+1$). Figure 1 depicts $\textit{ECQ}(1, 3)$, where the dashed lines, bold lines and solid lines correspond to $E_1$, $E_2$ and $E_3$, respectively. We can see that each vertex u in $\textit{ECQ}(1, 3)$ with $u_0=0$ is of degree 2, and with $u_0=1$ is of degree 4.

Fig. 1

An exchange crossed cube $\textit{ECQ}(1, 3)$

For each edge $(u,v)\in E(\textit{ECQ}(s,t))$, it can be regarded as two reversed directed edges and denoted by $\langle u,v\rangle$ and $\langle v,u\rangle$, respectively. For the sake of distinction, we use ${\hat{E}}(\textit{ECQ}(s,t))$ to denote such a set, i.e., ${\hat{E}}(\textit{ECQ}(s,t))=\{\langle u,v\rangle ,\langle v,u\rangle |\,(u,v)\in E(\textit{ECQ}(s,t))\}$.

Lemma 1

(Li et al. 2013) ECQ(s, t) is isomorphic to ECQ(t, s).

By Lemma 1, hereafter, we may assume without loss of generality that $s \le t$. Let $\textit{ECQ}_i(s, t)$ be a subgraph of $\textit{ECQ}(s, t)$ induced by edges in $E_i$ for $i\in [1, 3]$. According to Definition 3, we have following proposition.

Proposition 1

The subgraph $\textit{ECQ}_2(s, t)$ (respectively, $\textit{ECQ}_3(s, t)$) contains $2^s$ (respectively, $2^t$) disjoint copies of $\textit{CQ}_t$ (respectively, $\textit{CQ}_s$). Also, $\textit{ECQ}_1(s, t)$ forms a perfect matching between nodes in ECQ$_2(s, t)$ and ECQ$_3(s, t)$.

Denote by $\textit{CQ}_t^{s+t,t+1}$ for $\textit{CQ}_t$ in $\textit{ECQ}_2(s,t)$ in which all vertices $u\in CQ_t$ have the same bits in $u_{s+t,t+1}$. Similarly, $\textit{CQ}_s^{t,1}$ denotes those $\textit{CQ}_s$ in $\textit{ECQ}_3(s,t)$ for all vertices $u\in CQ_s$ having the same bits in $u_{t,1}$. For brevity, $\textit{CQ}_t^{s+t,t+1}$ and $\textit{CQ}_s^{t,1}$ are also denoted by $\textit{CQ}_t^x$ and $\textit{CQ}_s^y$, respectively, where $x=\mathrm{Dec}(u_{s+t,t+1})$ and $y=\mathrm{Dec}(u_{t,1})$. For example, subgraphs $\textit{ECQ}_2(1,3)$ and $\textit{ECQ}_3(1,3)$ are shown in Fig. 2a and b, respectively. Note that $\textit{ECQ}_2(1,3)$ contains $\textit{CQ}_3^0$ and $\textit{CQ}_3^1$, and $\textit{ECQ}_3(1,3)$ contains $\textit{CQ}_1^i$ for $i\in [0, 7]$.

Fig. 2

Two subgraphs of $\textit{ECQ}(1, 3)$

2.2 The ring topology

The ring topology, denoted by $R_n$, is a cycle with $2^n$ nodes, where $n=s+t+1$. The nodes (respectively, the links) in $R_n$ are labeled clockwise from 1 to $2^n$ (respectively, from $\ell _1$ to $\ell _{2^n}$). For instance, Fig. 3 shows a ring topology $R_3$, where the nodes (respectively, the links) are labeled clockwise from 1 to 8 (respectively, from $\ell _1$ to $\ell _8$). In this paper, nodes and links in $R_n$ represent routing nodes and optical links in a ring-topology WDM optical network, respectively. To consider directional links, we use ${\hat{E}}(R_n)=\{\langle i, (i+1)$mod $2^n \rangle ,\langle (i+1)$ mod $2^n,i\rangle |i\in [1,2^n]\}$ to denote the directional version of $E(R_n)$.

Fig. 3

A ring topology $R_3$

The linear array, denoted by $L_x$, is a path with $2^x$ nodes (Liu 2015; Yu et al. 2012, 2013; Zhang et al. 2014), where x is a nonnegative integer. Let $E_n'$ be a link subset of $R_n$ comprising eight links, where $E_n'=\{\ell _{2^{s+t-2}}, \ell _{2^{s+t-1}}, \ell _{3\times 2^{s+t-2}}, \ell _{2^{s+t}}, \ell _{5\times 2^{s+t-2}},$ $\ell _{6\times 2^{s+t-2}}, \ell _{7\times 2^{s+t-2}}, \ell _{2^{s+t}}\}$. Let $R_n'$ denote the subgraph of $R_n$ obtained by removing the links in $E_n'$ from $R_n$, i.e., $R_n'= R_n - E_n$. It is clear that the subgraph $R_n'$ is composed of eight disjointed copies of $L_{s+t-2}$, denoted by $L_{s+t-2}^0, L_{s+t-2}^1,\ldots , L_{s+t-2}^7$ clockwise. Figure 4 shows the subgraph $R_n'$ of $R_n$. Note that the nodes on $L_{s+t-2}^i$ are labeled clockwise in the consecutive order from $i \times 2^{s+t-2}+1$ to $(i+1) \times 2^{s+t-2}$, where $i\in [0, 7]$.

Fig. 4

Subgraph $R_n'$ of $R_n$

2.3 Embedding schemes and congestions

Let $G=(V_G,E_G)$ be the guest graph and $H=(V_H,E_H)$ the host graph, where $|V_G|=|V_H|$. An embedding scheme of G in H is an ordered pair $\varPhi =(\varPsi ,\varOmega )$, where $\varPsi$ is a bijection from $V_G$ to $V_H$, and $\varOmega$ is a mapping from $E_G$ to a set of paths in H such that, for every edge $e=(u,v)\in E_G$, there is a path $\varOmega (e)$ from $\varPsi (u)$ to $\varPsi (v)$ in H. In this paper, we consider that G is the exchanged crossed cube $\textit{ECQ}(s, t)$ and H is the ring topology $R_n$, where $n=s+t+1$.

Definition 4

(Chen and Shen 2010; Liu 2015; Yu et al. 2012; Zhang et al. 2014) The congestion of a link $\ell \in E_H$ under embedding scheme $\varPhi$ of G in H, denoted by $Cong(G,H,\varPhi ,\ell )$, is the number of paths $\varOmega (e)$ for all $e\in E_G$ passing through $\ell$, namely,

$Cong(G, H, \varPhi , \ell )=|\{e\in E_G|\ell \in \varOmega (e)\}|$.

The congestion of G in H under $\varPhi$ is defined as

$Cong(G, H, \varPhi )=\max _{\ell \in E_H}Cong(G, H, \varPhi , \ell )$.

The congestion of G in H is defined as

$Cong(G, H)=\min _\varPhi {Cong(G, H, \varPhi )}$.

Let $\lambda _\varPhi (G, H)$ represents number of required wavelengths for realizing a communication G on WDM optical network H under embedding scheme $\varPhi$. The following lemma shows that both $Cong(G, H, \varPhi )$ and Cong(G, H) are lower bounds of $\lambda _\varPhi (G, H)$.

Lemma 2

(Chen and Shen (2010); Yu et al. (2014a); Zhang et al. (2013)) $\lambda _\varPhi (G, H) \ge Cong(G, H, \varPhi ) \ge Cong(G, H)$.

The generalized cubes include some hypercube variants as special cases such as crossed cubes, Möbius cubes and locally twisted cubes (Zhang et al. 2014). Let $GQ_x$ denote an x-dimensional generalized cube, where x is a positive integer. We use a binary string $u = u_{x-1}u_{x-2}\cdots u_0$ to represent a vertex gq in $GQ_x$, and use num(gq) to denote the assigned number of gq by an embedding scheme. Let $gq_x^i$ ($0\le i\le 2^x-1$) denote the vertex in $GQ_x$, where Dec$(u_{x-1}\cdots u_0)=i$. The natural embedding, denoted by $\varPhi _N$, is an embedding scheme of $GQ_x$ in $L_x$ so that the bijection from V($GQ_x$) to V($L_x$) is strictly increasing. That is, if $j < k$ then $num(gq_x^j) < num(gq_x^k)$, where j and k are nonnegative integer. In 2014, Zhang et al. proved that the natural embedding is an optimal scheme for embedding $GQ_x$ into $L_x$. In the following lemma, we describe related results of the natural embedding on x-dimensional crossed cube $\textit{CQ}_x$.

Lemma 3

(Zhang et al. 2014) Cong(CQ$_x$, $L_x$) = Cong(CQ$_x$,$L_x$,$\varPhi _N$) = $\lfloor 2^{x+1}/3\rfloor$, where x is a positive integer.

In Liu and Chang (2018), we have shown the following lemma.

Lemma 4

(Liu and Chang 2018) Cong(ECQ(y, z), $L_x$) = $2^{y+z-1}+\lfloor 2^z/3\rfloor$, where x, y and z are positive integers such that x=y+z+1 and $y \le z$.

From Lemma 4 and based on the relationship between Lemmas 3.1 and 3.2 in Yu et al. (2014a), we can obtain that

$Cong(\textit{ECQ}(y, z), R_x) \ge 1/2 \times Cong(\textit{ECQ}(y, z), L_x) = 2^{y+z-2}+(\lfloor 2^z/3\rfloor /2)$. Since Cong($\textit{ECQ}(y, z)$, $L_x$) is integer-valued, therefore, we have the following corollary.

Corollary 1

Cong(ECQ(s, t), $R_n$) $\ge 2^{s+t-2}+\lceil \lfloor 2^t/3\rfloor /2\rceil$, where n, s and t are positive integers such that n=s+t+1 and s $\le$ t.

Based on Lemma 2 and Corollary 1, it is straightforward to obtain the following lemma.

Lemma 5

$\lambda _\varPhi (\textit{ECQ}(s, t), R_n) \ge 2^{s+t-2}+\lceil \lfloor 2^t/3\rfloor /2\rceil$, where n, s and t are positive integers such that n=s+t +1 and s $\le$ t.

Since Lemma 5 considers any embedding scheme $\varPhi$, therefore, we have following corollary.

Corollary 2

The optimal wavelength number for realizing ECQ(s, t) communication pattern on WDM optical network $R_n$ is at least $2^{s+t-2}+\lceil \lfloor 2^t/3\rfloor /2\rceil$, where $n=s+t+1$.

2.4 The RWA problem for realizing $\textit{ECQ}(s, t)$ on $R_n$

Both routing and wavelength assignment are considered in this problem. The input to this problem includes the communication patterns represented by $\textit{ECQ}(s, t)$, and the WDM optical network represented by $R_n$, where $n=s+t+1$. The problem is to find an embedding scheme $\varPhi$ = ($\varPsi$,$\varOmega$) of $\textit{ECQ}(s, t)$ on $R_n$ such that the number of required wavelengths is minimum. The routing between each pair of vertices u and v for $e = (u, v) \in \textit{ECQ}(s, t)$ can be determined by a shortest lightpath $\varOmega (e)$ from vertex $\varPsi (u)$ to vertex $\varPsi (v)$ on $R_n$. Under this embedding scheme, we then deal with wavelength assignment for each link on $R_n$. The output of this problem is the assigned wavelengths to links on $R_n$.

Note that the wavelength assignment to links on $R_n$ must fulfill both the wavelength continuity constraint and the distinct wavelength constraint. The wavelength continuity constraint requires that all links along a lightpath from the source node to the destination node must use the same wavelength, while the distinct wavelength constraint requires that all lightpaths passing through the same link must be assigned distinct wavelengths. For instance, Fig. 5a (respectively, Fig. 5b) shows a lightpath $2\rightarrow 3\rightarrow 4\rightarrow 5$ on $R_3$, which satisfies (respectively, violates) the wavelength continuity constraint.

Fig. 5

Examples for wavelength continuity constraint

Figure 6 shows two lightpaths $2\rightarrow 3\rightarrow 4$ and $3\rightarrow 4\rightarrow 5$ passing through the same link $\langle 3, 4\rangle$ on $R_3$. Figure 6a (respectively, Fig. 6b) shows an example which satisfies (respectively, violates) the distinct wavelength constraint.

Fig. 6

Examples for distinct wavelength constraint

3 The proposed algorithms

In Sect. 3.1, we first propose an embedding scheme $\alpha$. Then a lower bound of the number of required wavelengths based on embedding scheme $\alpha$ is derived. In Sect. 3.2, we describe a wavelength assignment algorithm $\beta$. Performance of the wavelength assignment algorithm compared to the optimal wavelength number is also analyzed.

3.1 The embedding scheme

Let $u=u_{s+t}\cdots u_{t+1}u_t\cdots u_1u_0$ be a vertex in $V(\textit{ECQ}(s,t))$. We partition $V(\textit{ECQ}(s,t))$ into 8 disjoint vertex subsets as follows:

$$\begin{aligned} S_0= & {} \{u|u_{s+t}=0, u_t=0 \text{ and } u_0=1\},\\ S_1= & {} \{u|u_{s+t}=0, u_t=1 \text{ and } u_0=1\},\\ S_2= & {} \{u|u_{s+t}=0, u_t=1 \text{ and } u_0=0\},\\ S_3= & {} \{u|u_{s+t}=1, u_t=1 \text{ and } u_0=0\},\\ S_4= & {} \{u|u_{s+t}=1, u_t=1 \text{ and } u_0=1\},\\ S_5= & {} \{u|u_{s+t}=1, u_t=0 \text{ and } u_0=1\},\\ S_6= & {} \{u|u_{s+t}=1, u_t=0 \text{ and } u_0=0\}, \text{ and }\\ S_7= & {} \{u|u_{s+t}=0, u_t=0 \text{ and } u_0=0\}. \end{aligned}$$

In Fig. 7, we uses $\textit{ECQ}(1, 3)$ as an example to illustrate the partition mentioned above.

Fig. 7

Partition $V(\textit{ECQ}(s, t))$ into 8 disjoint subset

Clearly, the subgraph induced by $S_m$ ($m\in \{0, 1, 4, 5\}$) comprises $2^{s-1}$ disjoint $(t-1)$-dimensional crossed cubes, and the subgraph induced by $S_m$ ($m\in \{2, 3, 6, 7\}$) comprises $2^{t-1}$ disjoint $(s-1)$-dimensional crossed cubes. If $s\ge 2$, for the subgraph induced by $S_m$ ($m\in \{0, 1, 4, 5\}$), we denote the $(t-1)$-dimensional crossed cube by $\textit{CQ}_{t-1}^{m,i}$, where i ($i\in [0,2^{s-1}-1])$ is the decimal of $u_{s+t-1,t+1}$, and the vertex u in $\textit{CQ}_{t-1}^{m,i}$ is represented by $cq_{t-1}^{m,i,j}$, where j ($j\in [0,2^{t-1}-1])$ is the decimal of $u_{t-1,1}$. In particular, if $s=1$, $\textit{CQ}_{t-1}^{m,0}$ is the unique $(t-1)$-dimensional crossed cube, and the vertex u in $\textit{CQ}_{t-1}^{m,0}$ is denoted by $cq_{t-1}^{m,0,j}$, where j ($j\in [0,2^{t-1}-1])$ is the decimal of $u_{t-1,1}$. Similarly, for $m\in \{2, 3, 6, 7\}$, we can define the $(s-1)$-dimensional crossed cube $\mathrm {CQ}_{s-1}^{m,i}$ and the vertex $cq_{s-1}^{m,i,j}$, where $i\in [0,2^{t-1}-1]$ and $j\in [0,2^{s-1}-1]$.

Figure 8 shows Algorithm A, which describes embedding scheme $\alpha$. Given an exchanged crossed cube $\textit{ECQ}(s, t)$, the embedding scheme $\alpha$ assign numbers to vertices in $\textit{ECQ}(s, t)$. Let $e=(u, v)$ be an edge in $\textit{ECQ}(s, t)$, the path $\varOmega _\alpha (e)$ will go through a shortest path from node $\varPsi _\alpha (u)$ to node $\varPsi _\alpha (v)$ in $R_n$. Note that $\varPsi _\alpha (u)=num(u)$ and $\varPsi _\alpha (v)=num(v)$.

Fig. 8

Embedding scheme $\alpha$

Figure 9 shows the numbers assigned to the vertices in $\textit{ECQ}(1, 3)$ by the embedding scheme $\alpha$.

Fig. 9

Numbers assigned to vertices in $\textit{ECQ}(1, 3)$

Corollary 3

Under the embedding scheme $\alpha$, vertices belong to subset $S_m$ ($m\in [0, 7]$) are embedded in $L_{s+t-2}^m$ of $R_n$.

Proof

It is clear that vertices belong to subset $S_m$ ($m\in [0, 7]$) are numbered by the embedding scheme $\alpha$ from $m \times 2^{s+t-2}+1$ to $(m+1) \times 2^{s+t-2}$. From the description of $L_{s+t-2}^m$ ($m\in [0, 7]$) in Sect. 2.2, nodes of $L_{s+t-2}^m$ ($m\in [0, 7]$) are labeled from $m \times 2^{s+t-2}+1$ to $(m+1) \times 2^{s+t-2}$. Thus this corollary is true. $\square$

Proposition 2

Under the embedding scheme $\alpha$, for $m\in \{0, 1, 4, 5\}$ and $i\in [0,2^{s-1}-1]$, vertices in each $\textit{CQ}_{t-1}^{m,i}$ are embedded by the natural embedding in a disjointed linear subarray $L_{t-1}$ of $L_{s+t-2}^m$.

Proof

Under the embedding scheme $\alpha$, for each $m\in \{0, 1, 4, 5\}$ and $i\in [0,2^{s-1}-1]$, vertices in each $\textit{CQ}_{t-1}^{m,i}$ are numbered consecutively from $(m\times 2^{s+t-2}+i\times 2^{t-1}+1)$ to $(m\times 2^{s+t-2}+(i+1)\times 2^{t-1})$. Therefore, for each $m\in \{0, 1, 4, 5\}$ and $i\in [0,2^{s-1}-1]$, $\textit{CQ}_{t-1}^{m,i}$ are embedded in a disjointed linear subarray $L_{t-1}$ of $L_{s+t-2}^m$.

On the other hand, for each $m\in \{0, 1, 4, 5\}$ and $i\in [0,2^{s-1}-1]$, we have $num(cq_{t-1}^{m,i,j})<num(cq_{t-1}^{m,i,k})$, where $0\le j<k\le 2^{t-1}-1$. From the description of the natural embedding in Sect. 2.3, thus, the proposition follows. $\square$

Proposition 3

Under the embedding scheme $\alpha$, for $m\in \{2, 3, 6, 7\}$ and $i\in [0,2^{t-1}-1]$, vertices in each $\textit{CQ}_{s-1}^{m,i}$ are embedded by the natural embedding in a disjointed linear subarray $L_{s-1}$ of $L_{s+t-2}^m$.

Proof

The proof is similarly to that of Proposition 2. $\square$

Base on Propositions 2 and 3, we use $L_{t-1}^{m,i}$ ($m\in \{0, 1, 4, 5\}$ and $i\in [0,2^{s-1}-1]$) to denote the linear subarray $L_{t-1}$ (of $L_{s+t-2}^m$), on which the vertices in $\textit{CQ}_{t-1}^{m,i}$ are embedded.

Corollary 4

For $m\in \{0, 1, 4, 5\}$, $i\in [0,2^{s-1}-1]$, there exits a link f ($f\in L_{t-1}^{m,i}$), on which the congestion contributed by edges in $\textit{CQ}_{t-1}^{m,i}$ under the embedding scheme $\alpha$, is at least $\lfloor 2^t/3\rfloor$.

Proof

From Lemma 3 and Propositions 2, it is straightforward to obtain this corollary. $\square$

Definition 5

(Zhang et al. 2013) Two length-(d+1) binary strings $u=u_du_{d-1}\cdots u_0$ and $v=v_dv_{d-1}\cdots v_0$ are pair related, denoted by $u\!\sim \!v$, if either

• (1) $d=1, (u_1,u_0)\in R=\{(00,00),(10,10),(01,11),$ $(11,01)\}$, or

• (2) $d>1$, $u_d=v_d$ when d is even, and ($u_{2i+1}u_{2i},v_{2i+1}v_{2i}$)

$\in R$ for all $0 \le i < \lfloor d/2 \rfloor$.

For $0\le i < j\le d$, let $u_{j,i}$ be a substring $u_ju_{j-1}\cdots u_i$ of u. In the following, we use $\tilde{u}_{j,i}$ to denote the pair related substring of $u_{j,i}$. Let a and b be two binary string, we use $a \parallel b$ to denote the concatenation of a and b. Let $u^{0,x}=0u_{s+t-1:t+1}^00u_{t-1:1}^01$ be a binary string of length $s+t+1$, which represent a vertex in $S_0$ such that Dec$(u_{s+t-1:t+1}^0\parallel u_{t-1:1}^0)=x$, where $x\in [0,2^{s+t-2}-1]$. In the following, we also define vertex $u^{i,x}$ in $S_i$ ($i\in [1,7]$ and $x\in [0,2^{s+t-2}-1]$) as follows:

$$\begin{aligned} u^{1,x}= & {} 0u_{s+t-1:t+1}^01 \tilde{u}_{t-1:1}^01\\ u^{2,x}= & {} 0u_{s+t-1:t+1}^01 \tilde{u}_{t-1:1}^00\\ u^{3,x}= & {} 1{\tilde{u}}_{s+t-1:t+1}^01 \tilde{u}_{t-1:1}^00\\ u^{4,x}= & {} 1{\tilde{u}}_{s+t-1:t+1}^01 \tilde{u}_{t-1:1}^01\\ u^{5,x}= & {} 1{\tilde{u}}_{s+t-1:t+1}^00 {u}_{t-1:1}^01\\ u^{6,x}= & {} 1{\tilde{u}}_{s+t-1:t+1}^00 {u}_{t-1:1}^00\\ u^{7,x}= & {} 0u_{s+t-1:t+1}^00 {u}_{t-1:1}^00 \end{aligned}$$

From Definition 3, we can find that, for each x ($x\in [0,2^{s+t-2}-1]$), the vertex set $\{u^{m,x}| m\in [0, 7]\}$ forms a cycle in $\textit{ECQ}(s, t)$. We use cycle(x) to denote the cycle. Figure 10 shows cycle(x) in $\textit{ECQ}(s, t)$. For example in $\textit{ECQ}(1, 3)$, cycle(1) $=\{00011,01111,01110, 1110, 11111,10011, 10010, 00010 \}$.

Fig. 10

cycle(x) in $\textit{ECQ}(s, t)$

Let $e^{m,x}=(u^{m,x}, u^{(m+1)mod7,x})$ ($m\in [0, 7]$ and $x\in [0, 2^{s+t-2}-1]$) be an edge in cycle(x), then we have following proposition.

Proposition 4

The paths, $\varOmega _\alpha (e^{0,x}),\cdots ,$ and $\varOmega _\alpha (e^{7,x})$, form a cycle in $R_n$, where $x\in [0, 2^{s+t-2}-1]$.

Proof

Since for each x ($x\in [0,2^{s+t-2}-1]$), the path $\varOmega _\alpha (e^{m,x})$ ($m\in [0, 7]$) will go through a shortest path from node $\varPsi _\alpha (u^{m,x})$ to node $\varPsi _\alpha (u^{(m+1)mod7,x})$ in $R_n$. Recall that vertex $u^{m,x}$ belongs to subset $S_m$ ($m\in [0,7]$). From Corollary 3, vertex $u^{m,x}$ ($m\in [0, 7]$) is embedded on linear subarray $L_{s+t-2}^m$ of $R_n$. Therefore, the eight paths $\varOmega _\alpha (e^{0,x}), \varOmega _\alpha (e^{1,x}), \cdots$, and $\varOmega _\alpha (e^{7,x})$ will form a cycle in $R_n$. $\square$

The main idea of Proposition 4 is illustrated in Fig. 11.

Fig. 11

Paths $\varOmega _\alpha (e^{i,x})$ ($i\in [0,7]$) form a cycle in $R_n$

Corollary 5

Under the embedding scheme $\alpha$, the congestion of link $\ell$ ($\ell \in R_n$) contributed by edges in each cycle(x) ($x\in [0, 2^{s+t-2}]$) is equal to 1.

Proof

From Proposition 4, it is straightforward to obtain this corollary. $\square$

Lemma 6

Cong(ECQ(s, t), $R_n, \alpha ) \ge 2^{s+t-1}+\lfloor 2^t/3\rfloor ,$ where $n=s+t+1$.

Proof

From Corollary 4, for $m\in \{0, 1, 4, 5\}$ and $i\in [0,2^{s-1}-1]$, there exits a link f ($f\in L_{t-1}^{m,i}$), on which the congestion contributed by edges in $\textit{CQ}_{t-1}^{m,i}$, is at least $\lfloor 2^t/3\rfloor$. From Corollary 5, the congestion of link f contributed by edges in each cycle(x) ($x\in [0,2^{s+t-2}-1]$) is 1. Since we have $2^{s+t-2}$ such cycles in $\textit{ECQ}(s, t)$, hence, the congestion of link f contributed by edges in these cycles is at least $2^{s+t-2}$. Therefore, the congestion of link f under the embedding scheme $\alpha$ is at least $2^{s+t-1}+\lfloor 2^t/3\rfloor$, i.e., Cong($\textit{ECQ}(s, t)$,$R_n,\alpha ,f) \ge 2^{s+t-1}+\lfloor 2^t/3\rfloor .$ From Definition 4, we obtain that

$$\begin{aligned}&\hbox {Cong}(\textit{ECQ}(s, t),R_n, \alpha )\\&\qquad = \max _{\ell \in E(R_n)}\hbox {Cong}(\textit{ECQ}(s, t),R_n, \alpha , \ell )\\&\qquad \ge \hbox {Cong}(\textit{ECQ}(s, t), R_n, \alpha , f)\\&\qquad \ge 2^{s+t-1}+\lfloor 2^t/3\rfloor \end{aligned}$$

$\square$

Theorem 1

$\lambda _\alpha (\textit{ECQ}(s, t), R_n) \ge 2^{s+t-1}+\lfloor 2^t/3\rfloor$.

Proof

From Lemmas 2 and 6, therefore, it is straightforward to obtain this theorem. $\square$

3.2 The wavelength assignment algorithm

Let DSL$_1$ and DSL$_2$ denote two directed link sets. For each x ($x\in [0,2^{s+t-2}-1]$), we use $cycle_1(x)$ and $cycle_2(x)$ to denote the two reversed direction cycles corresponding to cycle(x). Let $e_d$ be an directed edge in ${\hat{ECQ}}$(s,t), we also use ${\hat{E}}(\varOmega (e_d))$ to denote the directional links on the directional path $\varOmega (e_d)$. In 2013, Zhang et al. proposed the wavelength assignment algorithm for implementing a half-duplex or full-duplex crossed cube communication patterns on a linear array WDM optical network. In that paper, an algorithm called Assign_$\textit{CQ}_n$_$L_n$ was introduced to deal with the half-duplex case, which provides an optimal wavelength assignment for realizing a half-duplex crossed cube $\textit{CQ}_n$ on a linear array $L_n$.

Figure 12 shows Algorithm B, which describes wavelength assignment algorithm $\beta$. Given an exchanged crossed cube $\textit{ECQ}(s, t)$ and the assigned numbers for all vertex in V($\textit{ECQ}(s, t)$), the wavelength assignment algorithm $\beta$ will assign wavelengths to directed links in ${\hat{E}}(R_n)$. Note that the wavelengths assigned in Step 1 are numbered $1,2,\ldots ,2^{s+t-2}$. In Step 2 (respectively Step 3), Assign_$\textit{CQ}_n$_$L_n$ in Zhang et al. (2013) is invoked using two parameters $\textit{CQ}_{t-1}$ and $L_{t-1}$ (respectively, $\textit{CQ}_{s-1}$ and $L_{s-1}$) as inputs, and the wavelengths assigned in these two steps are numbered $2^{s+t-2}+1,2^{s+t-2}+2,\ldots ,2^{s+t-2}+\lfloor 2^t/3\rfloor$.

Fig. 12

Wavelength assignment algorithm $\beta$

Theorem 2

The wavelength assignment algorithm $\beta$ requires $2^{s+t-2}+\lfloor 2^t/3\rfloor$ wavelength.

Proof

Clearly, all edges in $\textit{ECQ}(s,t)$ have been taken into account by Algorithm B. In Step 1, we first reset DLS$_1$ and DLS$_2$ to be empty sets. Then there are $2^{s+t-2}$ iterations to be performed, and each iteration requires one unused wavelength. Hence, the total wavelengths assigned in this step is $2^{s+t-2}$. In Step 2 (respectively, Step 3), edges in $\textit{CQ}_{t-1}^{m,i}$ (respectively, $\textit{CQ}_{s-1}^{m,i}$), are considered, and Assign_$\textit{CQ}_n$_$L_n$ in Zhang et al. (2013) is invoke to assign wavelengths. According to the results in Zhang et al. (2013), it follows that $\lfloor 2^t/3\rfloor$ (respectively, $\lfloor 2^s/3\rfloor$) wavelengths are required for each $\textit{CQ}_{t-1}^{m,i}$ (respectively, $\textit{CQ}_{s-1}^{m,i}$) in Step 2 (respectively, Step 3). Recall that we have assumed $s\le t$. By Propositions 2 and 3, the wavelengths assigned by Step 2 and 3 can be reused, and hence, only $\lfloor 2^t/3\rfloor$ wavelengths are required for these two steps. Therefore, it is obvious that wavelength assignment algorithm $\beta$ requires $2^{s+t-2}+\lfloor 2^t/3\rfloor$ wavelengths. $\square$

In wavelength assignment algorithm $\beta$, six wavelengths are allocated for $\textit{ECQ}(1, 3)$. Figure 13 shows the wavelength assignment to directed edges in $\textit{ECQ}(1, 3)$. Figure 14 shows the wavelength assignment to directed links in ${\hat{E}}(R_5)$.

Fig. 13

Wavelength assignment to directed edges in ECQ(1, 3)

Fig. 14

Wavelength assignment to directed links in ${\hat{E}}(R_5$)

Corollary 6

The wavelength assignment algorithm $\beta$ uses minimum number of wavelengths under the embedding scheme $\alpha$.

Proof

From Theorems 1 and 2, therefore, the corollary follows. $\square$

Lemma 7

The wavelength assignment algorithm $\beta$ uses no more than additional $\lfloor 2^{t-1}/3\rfloor$ wavelengths, compared to the optimal wavelength number.

Proof

From Corollary 2 and Theorem 2, we can obtain that the difference of the required wavelengths between the wavelength assignment algorithm $\beta$ and the optimal wavelength number is no more than $(2^{s+t-2}+\lfloor 2^t/3\rfloor )-(2^{s+t-2}+\lceil \lfloor 2^{t}/3\rfloor /2\rceil )=\lfloor 2^{t-1}/3\rfloor$, and therefore, this lemma is proved. $\square$

Let r denotes the proportion of required wavelengths of wavelength assignment algorithm $\beta$ to the optimal wavelength number, we obtain the following theory.

Theorem 3

The wavelength assignment algorithm $\beta$ is a factor 1.25 approximation algorithm for the RWA problem of realizing ECQ(s,t) communication pattern on WDM optical network $R_n$, where $n=s+t+1$.

Proof

From Corollary 2 and Theorem 2, we have

$$\begin{aligned} r\le & {} (2^{s+t-1}+\lfloor 2^t/3\rfloor )/(2^{s+t-2}+\lceil \lfloor 2^{t}/3\rfloor /2\rceil )\\= & {} 1+(\lfloor 2^{t-1}/3\rfloor )/(2^{s+t-2}+\lceil \lfloor 2^{t}/3\rfloor /2\rceil ) \end{aligned}$$

Since $s\ge 1$, we have

$$\begin{aligned}&1+(\lfloor 2^{t-1}/3\rfloor )/(2^{s+t-2}+\lceil \lfloor 2^{t}/3\rfloor /2\rceil )\\&\quad \le 1+\lfloor 2^{t-1}/3\rfloor /(2^{t-1}+\lceil \lfloor 2^{t}/3\rfloor /2\rceil )\\&\quad \le 1+\lfloor 2^{t-1}/3\rfloor /(3\times \lfloor 2^{t-1}/3\rfloor + \lfloor 2^{t-1}/3\rfloor )\\&\quad = 1+\lfloor 2^{t-1}/3\rfloor /(4\times \lfloor 2^{t-1}/3\rfloor )\\&\quad =1.25 \end{aligned}$$

Thus, we obtain that $r\le 1.25$, and this complete the proof. $\square$

Let d denotes the upper bound on difference of the required wavelengths between the wavelength assignment algorithm $\beta$ and the optimal wavelength number. From Lemma 7, it is clear that $d=\lfloor 2^{t-1}/3\rfloor$. For ease of comparison, the relation between s, t, r and d is described in Table 1.

Table 1 Relation between s, t, p and d

4 Conclusion and future works

In this paper, we study the RWA problem for realizing exchanged crossed cube communication patterns on ring-topology WDM optical networks. We first design an embedding scheme $\alpha$. Based on this embedding scheme, we then propose a wavelength assignment algorithm $\beta$, that uses $2^{s+t-2}+\lfloor 2^t/3\rfloor$ wavelengths. We prove that the wavelength assignment algorithm $\beta$ uses minimum number of wavelengths under the embedding scheme $\alpha$. Moreover, we also show that the wavelength assignment algorithm $\beta$ is a factor 1.25 approximation algorithm, and it uses no more than additional $\lfloor 2^{t-1}/3\rfloor$ wavelengths, compared to the optimal wavelength number.

For future research, it would be worthwhile to consider the RWA problem for other types of communication patterns, such as locally exchanged twisted cubes (Chang et al. 2016), exchanged folded hypercubes (Qi et al. 2015), Fibonacci cubes (Hsu 1993) and enhanced cubes (Tzeng and Wei 1991). It will also be promising to investigate other WDM optical network topologies, such as linear array, meshes, and torus. When solving the RWA problem, the dynamic wavelength assignment strategy can be used to reduce the required wavelengths tremendously (Yu et al. 2013; Zhang et al. 2015). Therefore, addressing these RWA problems by using the dynamic wavelength assignment strategy will also be an interesting research direction.