# Fault Tolerance of Optical Hypercube Interconnection Networks withr-Communication Pattern

Authors: Xianyong Li; Yajun Du; Yongquan Fan
Journal: Wireless Communications and Mobile Computing
 (2021)

---

## Abstract

As power grids and optical interconnection networks are interdependent, the reliabilities of the optical networks are critical issues in power systems. The optical networks hold prominent performance including wide bandwidth, low loss, strong anti-interference capability, high fidelity, and reliable performance. They are regarded as promising alternatives to electrical networks for parallel processing. This paper is aimed at taking the first step in understanding the communication efficiencies of optical networks. For that purpose, on optical networks, we propose a series of novel notions including communication pattern,r-communication graph, reduced diameter, enhanced connectivity, r-diameter, and r-connectivity. Using these notions, we determine that the r-diameter and r-connectivity of the optical n-dimensional hypercube network are n/r and n1+n2+⋯+nr, respectively. Since the parameter r is variable, we can adjust different values of r on the basis of the wavelength resources and load of the optical networks, achieving enhanced communication efficiencies of these networks. Compared with the electric n-dimensional hypercube network, the proposed communication pattern on the optical hypercube network not only reduces the maximum communication delay of the conventional electrical hypercube significantly but also improves its fault tolerance remarkably.


---

## Body

## 1. Introduction

With information explosion in power systems, power grids need to keep reliability requirement to rapidly handle fault information from these systems. The fault tolerance of power grids is an efficient measure to assess the reliabilities of the corresponding power systems. Habib et al. [1] considered the problem on the power grid-optical network interconnection to avoid or reduce cascading failures in power systems. Chai et al. [2] summarized the health monitoring of power grids based on the fiber optic sensing technology. They also discussed the intelligent fault diagnosis of power grids by fiber optic sensing technology. Corrêa et al. [3] proposed a heuristic algorithm to improve the reliability of optical links in the power grid. Sun et al. [4] divided the signal-to-noise ratio into the feedback signal and compensating signal based on confidence interval. They further creatively proposed confidence interval-based model predictive control of the transmit power. Their model ensured the reliability requirements in real-world industrial environment. Sun et al. [5] proposed an end-to-end data delivery reliability model to assess the reliability performance of wireless sensor networks. In smart grids, Sun et al. [6] proposed a novel link quality prediction method based on the long short-term memory (LSTM) network and confidence interval lower boundary. In real-world experiments, their method is superior to existing link quality prediction methods for reliability requirements. Sripetch and Saengudomlert [7] designed an optimal optical network including backbone and access networks on the basis of existing power grids. Thus, the reliability and topology structure design of optical interconnection networks are important research issues in power systems.Due to a variety of appealing properties, ranging from extremely high bandwidth to extremely low power consumption and latency, optical networks are widely regarded as promising alternatives to conventional electrical networks for parallel processing [8, 9]. By establishing dedicated light paths for a selected set of transmitter-receiver pairs employed a standard optical technique (wavelength division multiplexing (WDM) technique [10], say), every processor in an optically connected multicomputer can send multiple data packets simultaneously to different processors, greatly enhancing the network throughput; this is especially the case for multiprocessor systems-on-chip, leading to the emergence of optical networks-on-chip (ONOCs). As thus, multifarious optical networks, such as hypercube [11], hypermeshes [12–17], k-ary n-cube [18], and multimesh hypercubes [11, 19–21], had been massively studied and demonstrated in practice. In particular, hypercubes have excellent graph-theoretic properties including regularity, symmetry, small diameter, strong connectivity, and relatively small link complexity, as well as simple yet efficient routing strategies. They have been taken as popular interconnection networks for multicomputer systems [22–25] and have been nominated as optical networks [11, 19, 21]. Researchers also proposed and studied a lot of variations with lower diameters on the hypercube by changing or adding the links in the hypercubes, such as the Möbius cubes [26], enhanced hypercube [27], locally twisted cubes [25], shuffle cube [28], and spined cube [29]. These abundant graph structural models have provided rich theoretical fundaments for the designs of the optical network structures and communication patterns. As optical networks possess enhanced communicating capability as compared to their electrical counterparts, it is of practical importance to investigate the communication efficiencies of optical networks. To our knowledge, however, no work on this issue has been reported in the literature.This paper is aimed at taking the first step in understanding the communication efficiencies of optical networks. To capture a communication pattern for an optical network, the notion of communication graph is introduced. Furthermore, the reduced diameter and enhanced connectivity of an optical network with a communication pattern are defined. Under a natural communication pattern, known as ther-communication pattern, the reduced diameter and enhanced connectivity of an optical hypercube network are determined. The obtained results show that this enhanced pattern not only reduces the maximum communication delay of the conventional hypercube network significantly but also improves its fault tolerance remarkably.The subsequent materials are organized as follows. Section2 introduces new notions and terminologies. Section 3 formulates and proves the main results in this work. This work is closed by Section 4.


## 2. New Notations and Terminologies

For a graphG, let dG and κG denote its diameter and connectivity, respectively, see Ref. [30] for fundamental graph-theoretic notions and terminologies.An optical network can be represented as a graphG=V,E, where every node stands for the unity of a processor, the local memory owned by the processor, and the optical router to which the local memory is connected. There is an edge between two nodes if and only if a direct light path can be set up between the two optical routers associated to them. A light path can be established between a pair of nonadjacent nodes by properly setting the states of a set of optical routers on the path, leading to an enhanced communicating capability. For example, a linear array graph [31] contains N processors and N−1 communication edges (see Figure 1). The wavelength resource is restricted. By the WDM technology [10], about sixty wavelengths per fiber can be achieved. Then, any two processors can be established an optical path of length one to communicate data each other by a wavelength in a fiber. Figure 2 shows the new optical paths (complementary edges, see the dashed lines) that the processor 1 communicates with other processors in linear array graph in Figure 1. In the following, we will consider r optical paths of length one between any two nodes in the optical hypercube. Adding this type of optical paths in the optical hypercube, we call the graph by r-communication graph for the optical hypercube. To capture the communicating capability of an optical network, we first introduce the notion of communication pattern as follows.Definition 1.
A communication pattern on an optical networkG=V,E, denoted C, is defined as the set of all node pairs for which light paths are allowed to be established. The communication graph for the communication pattern is defined as the graph GC=V,C.Figure 1
Linear array graph withN processors.Figure 2
Linear array graph withN processors established some new optical paths from processor 1. The dashed lines express new optical paths that the processor 1 communicates with other processors.In the design of parallel algorithms for an optical network, it is infeasible to set up light paths between all of its node pairs because of the limited wavelength resources. Rather, it is desired that light paths are set up only between node pairs that are relatively close to each other. To capture this feature of optical networks, let us introduce a new notion as follows.Definition 2.
Ther-communication pattern on an optical network G=V,E, denoted Cr, is defined as the set of all node pairs where their distances are at least r. The r-communication graph is denoted by Gr=V,Cr.The diameter of a network is a measure of the maximum communication delay between a pair of nodes. For an optical network, the establishment of light paths between nonadjacent node pairs is conducive to the reduction of its diameter, leading to the notion ofreduced diameter, which is formulated as follows.Definition 3.
The reduced diameter of an optical networkG=V,E endowed with a communication pattern C, denoted by dCG, is defined as dCG=dGC.Obviously, for the graphG with the communication pattern Cr, we have dCrG=dGCr.Definition 4.
Ther-diameter of an optical network G=V,E, denoted by drG, is defined as drG=dGr.The connectivity of a network is a gauge of its fault tolerance, i.e., its capability of working properly in the presence of faulty elements. For an optical network, the establishment of light paths between nonadjacent node pairs contributes to the enhancement of its connectivity, leading to the notion ofenhanced connectivity, which is formulated as follows.Definition 5.
The enhanced connectivity of an optical networkG=V,E endowed with a communication pattern C, denoted by κCG, is defined as κCG=κGC.Definition 6.
Ther-connectivity of an optical network G=V,E, denoted by κrG, is defined as κrG=κGr.Ann-dimensional hypercube network (n-cube, for short), denoted Qn, is a graph with 2n nodes, where the nodes can be one-to-one labeled as n-length 0-1 string so that two nodes are adjacent if and only if their labels differ in exactly one bit position.Definition 7.
Ther-communication graph for an optical n-cube network, denoted Qnr, can be constructed recursively as follows. For n=1, Q1r is simply Q1. For n≥2, Qnr is formed from two disjoint copies of Qn−1r by performing the following operations: adding prefix 0 to the labels of all nodes of one copy to get a graph 0Qn−1r, adding prefix 1 to the labels of all nodes of the other copy to get a graph 1Qn−1r, and adding an edge between a node u=0a1a2⋯an−1 of 0Qn−1r and a node v=1b1b2⋯bn−1 of 1Qn−1r if and only if a1a2⋯an−1 and b1b2⋯bn−1 differ in at most r−1 bit positions. We shall call the edge as a cube edge or a non-cube edge depending on whether a1a2⋯an−1 and b1b2⋯bn−1 are identical or not.Figure3 presents the 2-communication graphs of the optical 2-cube, 3-cube, and 4-cube networks, respectively.Figure 3
Q22, Q32, and Q42, where the complementary edges are shown with dashed edges.


## 3. The Abilities of the Fault Tolerance and Communication of the Opticaln-Cube Network

This section is intended to determine ther-diameter and r-connectivity of Qn, reflecting the abilities of the fault tolerance and communication of this network.By Definition7, we can easily obtain the following result.Lemma 8.
Qnr has 2n nodes and is n1+n2+⋯+nr-regular.In the next, we will discuss ther-diameter and r-connectivity of Qn.Theorem 9.
drQn=n/r.Proof.
For a pair of nodes ofQnr whose labels differ in exactly k bit positions, it is easy to construct a k/r-length path connecting them. Thus, we have
(1)drQn=dQnr≤max1≤k≤nkr=nr.
For the two verticesu=0n and v=1n of Qnr, on the other hand, it can be seen that every path connecting them has the length at least n/r, implying that drQn=dQnr≥n/r. The proof is completed.Lemma 10.
κnQn=2n−1.Proof.
κnQn=κQnn=κKn=2n−1.Lemma 11.
Forr<n, we have κrQn=n1+n2+⋯+nr.Proof.
By induction onn. The assertion is obviously true for n≤3. Suppose the assertion is true for n=k≥3. Let S be a node subset of G=Qk+1r, S=k+11+k+12+⋯+k+1r−1. Then, it suffices to show that G\S is connected. For that purpose, let G0=0Qkr, G1=1Qkr, S0=S∩VG0, S1=S∩VG1. Without loss of generality, assume ∣S0∣≤∣S1∣. Then, it is easily verified that
(2)S0≤S2=k+11+k+12+⋯+k+1r−12<k1+k2+⋯+kr.
It follows from the inductive hypothesis thatG0\S0 is connected. Now, let us distinguish between two possibilities.Case 1.
∣S0∣≤k1+k2+⋯+kr−1. As every node of G1 has 1+k1+k2+⋯+kr−1 neighbors in G0, it follows that every node of G1\S1 has a neighbor in G0\S0, implying that G\S is connected.Case 2.
∣S0∣>k1+k2+⋯+kr−1. Then,
(3)S1=∣S∣−∣S0∣<k+11+k+12+.+k+1r−1−k1+k2+⋯+kr−1=k1+k2+⋯+kr.It follows from the inductive hypothesis thatG1\S1 is also connected. We proceed by treating two subcases, respectively.Case 1.
r<k+1/2. Then,
(4)VG0=2k=k+10+k+11+⋯+k+1k+12≥k+10+k+11+⋯+k+1r>S.So, there is an edge betweenG0\S0 and G1\S1, and thus, G\S is connected.Case 2.
r≥k+1/2. If either G1\S1 is empty or there is an edge between G0\S0 and G1\S1, G\S is already connected. Now, suppose that G1\S1 is not empty and there is no edge between G0\S0 and G1\S1. Then, the label of every node of G1\S1 differs from the label of any node of G0\S0 in at least r bit positions, leading to that
(5)1≤∣VG1\S1∣≤k2r−1+k2r+⋯+kk.So,r=k+1/2 and ∣S1∣=2k−1. Let u denote the node in graph G1\S1. As u has k0+k1+⋯+kk−1/2 neighbors in G0\S0, we have
(6)S0=S−S1=k+11+k+12+⋯+k+1k+1/2−2k=k+11+k+12+⋯+k+1k+1/2−k0+k1+⋯+kk≥k0+k1+⋯+k+1k−1/2.That is,(7)k1+k2+⋯+k+1k+1/2≥2k,contradicting the fact that
(8)k1+k2+⋯+kk+1/2<k0+k1+⋯+kk=2k.It follows by combining the above discussions that the assertion holds forn=k+1. By the inductive principle, the assertion holds for all n.By combining Lemmas10 and 11, we get the following.Theorem 12.
For arbitraryr, κrQn=n1+n2+⋯+nr.In particular, by Theorem12, let r=1, we obtain the 1-connectivity of Qn as follows.Corollary 13 (see [19]).
(9)κ1Qn=κQn=n.It follows that the 1-connectivity is just the traditional connectivity. Therefore,r-connectivity is an extension of the traditional connectivity. Because the value r is variable, we can choose different values of r on the basis of the wavelength resources and load of the optical networks, achieving enhanced communication efficiencies. For optical hypercube network Qnr>1, its r-connectivity (r-diameter) is obviously more (lower) than the traditional connectivity (diameter), and thus compared with the electrical hypercube, this communication pattern not only reduces the maximum communication delay dramatically but also improves its fault tolerance markedly. In the optical hypercube network with r-communication pattern, when the number of fault nodes is no more than n1+n2+⋯+nr, the network still works properly; when the dimension n is a fixed, the larger the value of r is, the stronger the reliability and availability of the network are.


## 4. Concluding Remarks

For the purpose of understanding the enhanced communication efficiencies of optical networks, the notion of communication graph has been introduced. Furthermore, ther-diameter and r-connectivity of an optical network have been defined. Next, the r-diameter and r-connectivity of an optical hypercube network have been figured out. The obtained results show that this communication pattern not only reduces the maximum communication delay of the conventional electrical hypercube network dramatically but also improves its fault tolerance markedly.Towards this direction, numerous works have yet to be done. First, it is worthwhile to calculate ther-diameter and r-connectivity of other kinds of optical networks. Second, it is necessary to introduce some other standards that can measure the performance of optical networks. Third, novel optical networks that are especially suited to multiprocessor systems-on-chip should be designed and analyzed. Last, but not least, conventional parallel algorithms, ranging from parallel sorting to parallel matrix multiplication, to parallel discrete Fourier transform, and to parallel solution of linear systems, must be adapted to optical networks. In the future, the optical hypercube interconnection networks with r-communication pattern may be used in power grids of power systems to improve the performance of communication networks.



---

*Source: 5358760-2021-12-20.xml*