Link-Disjoint Broadcasting Algorithm in Wormhole-Routed 3D Petersen-Torus Networks

Abstract

In a network, one-to-all broadcasting is the process of disseminating messages from a source node to all the nodes existing in the network through successive data transmissions between pairs of nodes. Broadcasting is the most primary communication process in a network. A 3D Petersen-Torus (3D PT) network has been proposed recently. the three-dimensionally magnified Petersen-Torus topology, 3D PT, is suitable for establishing a wireless sensor network (WSN) in 3D rectangular or cylindrical structures such as buildings. We propose a link-disjoint broadcasting algorithm for half-duplex 3D PT networks with wormhole routing and prove that the broadcasting algorithm is link-disjoint and the broadcasting step is $l/2+{\log }_2(n-1)+5$ in 3D PT $(\mathrm{l,\; n,\; n})$ .

1. Introduction

In wireless sensor network (WSN), after sensor nodes are deployed, they self-organize and establish routes automatically and transmit their information on their surroundings to a base station (BS). Since each sensor node has a limited and irreplaceable energy resource, energy conservation is the most important performance consideration in a WSN [1]. To decrease the energy consumption of a node, it is very important to effectively transmit collected data to a router through a sink node. For effective message transmission, a routing path should be short, without message congestion. When the routing path is long, the number of nodes used for message transmission increases, leading to additional energy consumption. Further, link congestion results in excessive energy consumption and lower transfer rate.

A routing protocol influenced by node topology is crucial to reducing energy consumption. Topologies used for effective routing include star [2], peer-to-peer (P2P) [3], grid mesh [4], and hexagonal honeycomb [5]. The Petersen-Torus, a topology that connects a Petersen graph in the grid shape, involves lower network costs than both the grid mesh and the honeycomb. 3D PT, the three-dimensionally magnified Petersen-Torus topology, is suitable for establishing a wireless sensor network (WSN) in 3D rectangular or cylindrical structures such as buildings. 3D PT involves lower network costs than the 3D mesh or the 3D honeycomb [6]. This study proposes broadcasting for data transmission in a WSN topology using 3D PT. As the proposed broadcasting is edge-disjoint, it does not cause message congestion. The time complexity, which is $O(n)$ at 3D PT $(n,n,n)$ , is confirmed to be efficient.

It is anticipated that sequential computers will reach their physical limitations in terms of CPU speed and memory size. Over the past years, high performance computing (HPC) has been extensively studied by researchers and applied to a variety of fields ranging from science, engineering, and business. With the development of HPC, there are many computing paradigms including multicomputer, multiprocessor, grid computing, cloud computing, and peer-to-peer (P2P) computing [7]. The interconnection network (structure of interconnecting processors) plays a critical role in improving the system performance of a HPC and wireless sensor network (WSN). A great deal of research on HPC and WSN has dealt with interconnection networks to achieve goals such as low latency, high bandwidth, low hardware cost, and low power consumption. The performance of HPC and WSN can be improved with advancements in hardware implementation technology, routing schemes, broadcasting algorithm, data/task distribution, and many other application parameters [6, 8].

In a network, processors (nodes) often need to communicate with each other for various reasons, such as data migration, message collection, job allocation, and message dissemination. Efficient communication has been recognized to be critical for HPC. Broadcasting is one of the most fundamental tasks in network communication. One essential communication operator is one-to-all broadcast. A broadcasting algorithm is applicable in diversified manners in several fields such as management of shared variables for distributed programming, image processing, data copying in database of large-scale network, and data collection in WSN, and for this, an effective broadcasting algorithm is necessary [9].

In a HPC, according to composition of processor and communication link, interconnection network can be classified into mesh family, hypercube family, and star graph family. The 3D Petersen-Torus network is mesh class and it was announced recently. An interconnection network can be modeled as an undirected graph $G=(V,E)$ , where the node set V represents the processors and the edge set E represents the communication links. Each processor $P_i$ is an element of node set V, and two processors $P_i$ and $P_j$ are connected by communication links ( $P_i$ , $P_j$ ). The number of nodes adjacent to the node $P_i$ is defined as degree of the node.

Broadcasting is performed by successive calling to transmit a message and has several limitations [10]: first, just two nodes participate in a call; second, a call is fully done in unit time; third, each node may take part in one call in unit time; and, fourth, a call appears between the neighboring two nodes. The third condition depends upon whether or not routing equipment supports one-port communication or all-port communication. The one-port communication means that one node holding a message in unit time transmits the message just to the one neighboring node, while the all-port communication means that one node holding a message in unit time transmits the message to all the neighboring nodes. In this paper, we assume a communication model where each communication channel is half duplex and each node has all-port capability. While store-and-forward routing was used in the first generation networks, most new generation multicomputers use wormhole-like routing [11]. Machines adopting such technology include the Cray T3D [12], MIT's J-Machine [13], and Intel Touchstone DELTA [14]. Such networks are known to be insensitive to the routing distance if the communication path is contention free. This study is on condition of distance-insensitivity wormhole routing that distance between nodes does not influence communication latency. Therefore the fourth condition is neglected, and it is important not to cause link contention in broadcasting.

The broadcasting algorithm of 3D PT $(k,n,n)$ , proposed in this study, is divided into two stages. A basic module refers to a bundle of 10 nodes that take the form of a Petersen graph in 3D PT. In the first stage, a message is transmitted from the source node that possessed it to the k basic module(s) in a different 2D space. In the second stage, the k node(s) possessing the message transmits it to every basic module located in the same 2D space. In this stage, the divide-and-conquer method, which continuously divides 2D basic modules into four areas, is used. As the divided areas do not overlap, the transmitted message does not cause congestion. Once eight basic modules exist in the divided area, not including the targeted basic module, the division process terminates. When the division process stops, the message is transmitted to the eight basic modules that take the form of a complete graph. In the final stage, every basic module that includes one node with a message transmits the message from the nodes including that message to the other nodes.

For broadcasting, constructing the spanning tree in a network is frequently used. Using the binary tree is suitable for either hypercube class or star graph class network, where the more the number of nodes is, the more the degree is. Using the binomial tree is also available in a more improved way. Time complexity of a one-to-all broadcasting algorithm of the all-port model in a 3D mesh class network is as follows: a broadcasting algorithm of [15] in $2^k\times 2^k\times z\hspace{0.17em}\hspace{0.17em}(1<z<8)$ torus is $k+1$ , and that of [16] in ${(\alpha +1)}^k\times {(\alpha +1)}^k\times {(\alpha +1)}^k(\alpha =6)$ torus is $3k+1$ . A broadcasting algorithm of [17] in $k\times k\times k$ torus is $3\lceil {\log }_{7}k\rceil +2$ . Besides, there are several algorithms for broadcasting in mesh class [18–20]. Section 2 introduces the 3D Petersen-Torus network and analyzes a broadcasting algorithm in the Petersen graph. Section 3 proposes a one-to-all broadcasting algorithm and proves that broadcasting is edge-disjoint. And, finally, conclusion is made.

2. Relevant Studies

2.1. 3D PT $(l,m,n)$ Network

Consider 3D PT $(l,m,n)=(Vpt,Ept)$ . The Petersen graph is set as a basic module, and the address of the basic module is indicated by $(z,x,y)$ , while the node address is indicated by $(z,x,y,p)$ . It is assumed that $(z,x,y,0),(z,x,y,1),\dots ,(z,x,y,9)$ belong to the basic model $(z,x,y)$ . z is a coordinate of the z-axis of the basic module, x is a coordinate of the x-axis of the basic module, y is a coordinate of the y-axis of the basic module, and p is the address of the node in the Petersen graph of the basic module. The node of 3D PT $(l,m,n)$ is defined as

$$\begin{array}{l}Vpt=\{\left(z,x,y,p\right),\mathrm{0}\le z<l,\mathrm{0}\le x<m,\\ \hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\mathrm{0}\le y<n,\mathrm{0}\le p\le \mathrm{9}\}.\end{array}$$

(1)

The edge of 3D PT $(l,m,n)$ is divided into an internal edge and an external edge, as mentioned below. Edges connecting the nodes belonging to the same basic module are called internal edges, and, for internal edges, those of the Petersen graph are used as they are. Edges connecting nodes in different basic modules are called external edges and are defined below [6]. In the equations expressing the following edges, the symbol “/” is a modulation operator.

• (1)

The vertical edge is $((z,x,y,\mathrm{6}),(z,x,(y+\mathrm{1})/n,\mathrm{9}))$ .

(2)

The horizontal edge is $((z,x,y,\mathrm{1}),(z,(x+\mathrm{1})/m,y,\mathrm{4}))$ .

(3)

The diagonal edge is $((z,x,y,\mathrm{2}),(z,(x\mathrm{\hspace{0.17em}\hspace{0.17em}}+\mathrm{1})/m,(y\mathrm{\hspace{0.17em}\hspace{0.17em}}+\mathrm{1})/n,\mathrm{3}))$ .

(4)

The reverse diagonal edge is $((z,x,y,\mathrm{7}),(z,(x-\mathrm{1}+\mathrm{\hspace{0.17em}\hspace{0.17em}}m)/m,(y+\mathrm{1})/n,\mathrm{8}))$ .

(5)

The dimensional edge is $((z,x,y,\mathrm{0}),((z+\mathrm{1})/l,x,y,\mathrm{5}))$ .

Figure 1(a) is 3D PT $(\mathrm{5,5},5)$ , which indicates the basic module with points. The dimensional edge is $((z,x,y,0),((z+1)/l,x,y,5))$ . For neatness, in Figure 1(a), wraparound edges are omitted at all basic modules. But wraparound edges are drawn at seven basic modules. In the basic module of 3D PT $(l,m,n)$ , nodes 1 and 4 are adjacent to horizontal edges, nodes 6 and 9 are adjacent to vertical edges, nodes 2 and 3 are adjacent to diagonal edges, nodes 7 and 8 are adjacent to reverse diagonal edges, and nodes 0 and 5 are adjacent to dimensional edges.

Figure 1

3D Petersen-Torus network.

2.2. Edge-Disjoint Broadcast on Petersen Graph

This section examines the broadcast of the Petersen graph, which is the basis of the broadcast of the 3D PT. Petersen graph is a regular graph, a node- and edge-symmetry graph, degree 3, diameter 2, connectivity 3, and girth 5 [21].

Lemma 1.

The one-to-all broadcasting in the Petersen graph is edge-disjoint and broadcasting time complexity is 2.

Proof.

The process of receiving a message on condition of 2 of the broadcasting step in all nodes is as shown in Figure 2(a), with node 0 in the Petersen graph as a start node. Figure 2(a) shows the Petersen graph in a form of a spanning tree. A message is transmitted from root node to child nodes and the message is transmitted from the three child nodes to each terminal node as shown in Figure 2(a); therefore the broadcasting step is 2. The Petersen graph is a node- (edge-) symmetry graph; therefore the broadcasting step from a certain node to all nodes of the Petersen graph is 2. As shown in Figure 2(a), the paths are edge-disjoint with each other in the ① and ② steps, and the demonstration is omitted.

Figure 2

Broadcasting step in the Petersen graph.

Lemma 2.

In the Petersen graph, three broadcasting paths to transmit a message from node 2 to nodes 3, 7, and 8 are edge-disjoint.

Proof.

Figure 2(b) shows the Petersen graph in a form of a spanning tree. As shown in Figure 2(b), the three paths indicated in a solid line are edge-disjoint with each other, and the demonstration is omitted.

3. Edge-Disjoint Broadcast on 3D PT Network

In this section, a broadcasting algorithm is proposed. The time complexity (here after referred to as broadcasting time) of the suggested algorithm is calculated, and it is demonstrated that the algorithm is edge-disjoint. $U(z,x,y,p)$ is assumed to be a source node with an initial message. The broadcasting process is divided into three stages. First, a message is transferred from the source node to l nodes with the address of $(z^{\prime },x,y,2)$  (here, $0\le z^{\prime }<l$ ). Next, a message from l nodes with an address of $(z^{\prime },x,y,2)$ is transferred to $l(mn\text{-}1)$ nodes with an address of $(z^{\prime },x^{\prime },y^{\prime },2)$  (here, $0\le x^{\prime }<m,0\le y^{\prime }<n$ ). Once this transfer is completed, the node, where $p=2$ in all the basic modules in a network, has a message. Finally, as shown in Figure 2(a), all nodes with a message transfer it to all the other nodes present in the basic modules to which they belong. The broadcasting process is shown in Figure 3. In the next section, the symbol “%” signifies the modulation operator and “→” signifies the path created by the routing algorithm that is presented in [6].

Figure 3

Broadcast stage in 3D PT network.

Stage 1.

Consider

$$\begin{array}{l}U\left(z,x,y,p\right)⟶\left(z,x,y,\mathrm{2}\right)⟶\left(z,x,y,\mathrm{2}\right)\\ \phantom{U\left(z,x,y,p\right)}⟶\left(\left(z+\mathrm{1}\right)\%l,x,y,\mathrm{2}\right)\\ \phantom{U\left(z,x,y,p\right)}⟶\left(\left(z+\mathrm{2}\right)\%l,x,y,\mathrm{2}\right)\\ \phantom{U\left(z,x,y,p\right)}⟶\left(\left(z+\mathrm{3}\right)\%l,x,y,\mathrm{2}\right)\\ \phantom{U\left(z,x,y,p\right)}⟶\cdots ⟶\left(\left(z+\frac{l}{\mathrm{2}}\right)\mathrm{\hspace{0.17em}\hspace{0.17em}}\%l,x,y,\mathrm{2}\right)\end{array}$$

(a)

$$\begin{array}{ll}& ⟶\left(z,x,y,2\right)⟶\left(\left(z-1+l\right)\%l,x,y,2\right)\\ ⟶\left(\left(z-\mathrm{2}+l\right)\mathrm{\hspace{0.17em}\hspace{0.17em}}\%l,x,y,\mathrm{2}\right)\\ ⟶\left(\left(z-\mathrm{3}\mathrm{\hspace{0.17em}\hspace{0.17em}}+\mathrm{\hspace{0.17em}\hspace{0.17em}}l\right)\mathrm{\hspace{0.17em}\hspace{0.17em}}\%l,x,y,\mathrm{2}\right)\\ ⟶\cdots ⟶\left(\left(z\mathrm{\hspace{0.17em}\hspace{0.17em}}-\frac{l}{\mathrm{2}}+\mathrm{\hspace{0.17em}\hspace{0.17em}}l\right)\%l,x,y,\mathrm{2}\right).\end{array}$$

(b)

Processes ( a ) and ( b ) proceed simultaneously and get completed at time $\lfloor l/\mathrm{2}\rfloor$ . Consequently, the broadcasting time of Stage 1 is $\lfloor l/\mathrm{2}\rfloor +1$ . Once this stage is completed, only one node has a message in all the subgraphs (the two-dimensional maps in Figure 3) with the same value of z. The number of nodes with a message is l.

Stage 2.

In Stage 2, l nodes simultaneously transfer the message to one node in all the other basic modules, each with a different value of z. When comparing two cases, where $z=0$ and $0<z<l-1$ , it is observed that the results of both cases are the same. Seeing just a case of $z=0$ , transfer process is as follows. The source node is $U(0,x,y,2)$ , while the destination node is $V(0,x^{\prime },y^{\prime },2)$ . Take $dx=|x-x^{\prime }|$ and $dy=|y-y^{\prime }|$ . $dx$ is an x-axis distance of the basic module to which node U and node V belong, while $dy$ is a y-axis distance. Broadcasting uses a divide-and-conquer technique. With a basic module having the initial message as an axis, it is divided into 4 areas, and the message is transmitted to each basic module located in the center of the 4 areas. With 4 basic modules having a message as an axis, each area is divided again into four subareas, and the message is transmitted to basic modules located in the center of each area. The said division and message transmission are repeated until $dx(dy)<1$ . Once division is finished, a message is transmitted from a basic module having a message to the 8 neighboring basic modules. This process is as shown in Figure 4. The numbers in the circle indicate the order that the message is transmitted from one basic module to another basic module. A subgraph on condition of $z=0$ , where the basic module is indicated in dots, is as shown in Figure 4, a node- (edge-) symmetry graph. Therefore nodes with messages are randomly selected. It is assumed that $m=n$ . Consider

$$\begin{array}{l}U\left(\mathrm{0},x,y,\mathrm{2}\right)⟶\left(\mathrm{0},x+\left(\frac{m}{\mathrm{4}}\right),y+\left(\frac{n}{\mathrm{4}}\right),\mathrm{2}\right)\\ \hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{0.17em}\hspace{0.17em}⟶\left(\mathrm{0},x+\left(\frac{m}{\mathrm{8}}\right),y+\left(\frac{n}{\mathrm{8}}\right),\mathrm{2}\right)\\ \hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{0.17em}\hspace{0.17em}⟶(\mathrm{0},x+\left(\frac{m}{\mathrm{16}}\right),y+\left(\frac{n}{\mathrm{16}}\right),\mathrm{2})\mathrm{\hspace{0.17em}\hspace{0.17em}}\\ \hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{0.17em}\hspace{0.17em}⟶\cdots \end{array}$$

(c)

$$\begin{array}{l}U\left(\mathrm{0},x,y,\mathrm{2}\right)⟶\left(\mathrm{0},x+\left(\frac{m}{\mathrm{4}}\right),y-\left(\frac{n}{\mathrm{4}}\right),\mathrm{2}\right)\\ \hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{0.17em}\hspace{0.17em}⟶\left(\mathrm{0},x+\left(\frac{m}{\mathrm{8}}\right),y-\left(\frac{n}{\mathrm{8}}\right),\mathrm{2}\right)\\ \hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{0.17em}\hspace{0.17em}⟶\left(\mathrm{0},x+\left(\frac{m}{\mathrm{16}}\right),y-\left(\frac{n}{\mathrm{16}}\right),\mathrm{2}\right)\\ \hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{0.17em}\hspace{0.17em}⟶\cdots \end{array}$$

(d)

$$\begin{array}{l}U\left(\mathrm{0},x,y,\mathrm{2}\right)⟶\left(\mathrm{0},x-\left(\frac{m}{\mathrm{4}}\right),y+\left(\frac{n}{\mathrm{4}}\right),\mathrm{2}\right)\mathrm{\hspace{0.17em}\hspace{0.17em}}\\ \hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{0.17em}\hspace{0.17em}⟶(\mathrm{0},x-\left(\frac{m}{\mathrm{8}}\right),y+\left(\frac{n}{\mathrm{8}}\right),\mathrm{2})\mathrm{\hspace{0.17em}\hspace{0.17em}}\\ \hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{0.17em}\hspace{0.17em}⟶\left(\mathrm{0},x-\left(\frac{m}{\mathrm{16}}\right),y+\left(\frac{n}{\mathrm{16}}\right),\mathrm{2}\right)\\ \hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{0.17em}\hspace{0.17em}⟶\cdots \end{array}$$

(e)

$$\begin{array}{l}U\left(\mathrm{0},x,y,\mathrm{2}\right)⟶\left(\mathrm{0},x-\left(\frac{m}{\mathrm{4}}\right),y-\left(\frac{n}{\mathrm{4}}\right),\mathrm{2}\right)\mathrm{\hspace{0.17em}\hspace{0.17em}}\\ \hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{0.17em}\hspace{0.17em}⟶\left(\mathrm{0},x-\left(\frac{m}{\mathrm{8}}\right),y-\left(\frac{n}{\mathrm{8}}\right),\mathrm{2}\right)\\ \hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{0.17em}\hspace{0.17em}⟶\left(\mathrm{0},x-\left(\frac{m}{\mathrm{16}}\right),y-\left(\frac{n}{\mathrm{16}}\right),\mathrm{2}\right)\\ \hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{0.17em}\hspace{0.17em}⟶\cdots .\end{array}$$

(f)

Processes ( c ) , ( d ) , ( e ) , and ( f ) proceed simultaneously. A message is transmitted from $U(0,x,y,2)$ to 4 basic modules on condition of $dx(dy)=\lfloor n/4\rfloor$ . In the next step, $dx$ is a half of dx of the previous step, $\text{dx}(dy)=\lfloor n/8\rfloor$ . To meet $dx(dy)<1$ , the division time should be done in $\lfloor {\log }_{\mathrm{2}}(n-1)\rfloor -1$ . When $dx(dy)<1$ , division should be stopped and a message is transmitted to the 8 neighboring basic modules. To transmit a message to the neighboring basic modules, the message should be transmitted to all nodes of the basic modules to which the node having the message belongs. Finally, transmit a message to the neighboring basic modules. Once this process is completed, only one node has a message in all the basic modules of 3D PT.

Figure 4

Broadcast in the nodes, where $z=0$ .

Stage 3.

A message is transferred from the node $(z,x,y,2)$ in all the basic modules to all the other nodes in the basic module to which it belongs, as shown in Figure 2(a). Broadcasting occurs along an edge-disjoint path and the broadcasting time is 2.

Theorem 3.

On 3D PT $(l,n,n)$ , the broadcasting step is $l/\mathrm{2}+{\log }_2(n-1)+5$ and the broadcasting algorithm is edge-disjoint.

Proof.

In Stage 1, broadcasting step is $\lfloor l/\mathrm{2}\rfloor +1$ . In Stage 2, initially, $dx(dy)=\lfloor n/4\rfloor$ , and in the next step, $dx$ is a half of $dx$ of the previous step, $dx(dy)=\lfloor n/8\rfloor$ . To meet $dx(dy)<1$ , the division time should be done in $\lfloor {\log }_{\mathrm{2}}(n-1)\rfloor -1$ . When $dx(dy)<1$ , division should be stopped and a message is transmitted to the 8 neighboring basic modules. To transmit a message to the neighboring basic modules, the message should be transmitted to all nodes of the basic modules to which the node having the message belongs. As described in Lemma 1, the step is 2 and the broadcasting step to transmit a message to the neighboring basic modules is 1. In Stage 3, broadcasting step is 2 according to Lemma 1. Adding up the broadcasting step $T=\lfloor l/\mathrm{2}\rfloor +1+\lfloor {\log }_{\mathrm{2}}(n-1)\rfloor -1+2+1+2$ . In the worst case, $T=l/\mathrm{2}+{\log }_{\mathrm{2}}(n-1)+5$ . In Stage 1, all nodes existing on the paths except for subpath $(z,x,y,2)\to ((z+1)/l,x,y,2)$ for ( a ) and subpath $(z,x,y,2)\to ((z-1+l)/l,x,y,2)$ for ( b ) are edge-disjoint with different addresses on the z-axis. When subpath $(z,x,y,2)\to ((z+1)/l,x,y,2)$ for ( a ) is unfolded, $(z,x,y,2)\to (z,x,y,1)\to (z,x,y,0)\to ((z+1)/l,x,y,5)\to ((z+1)/l,x,y,6)\to ((z+1)/l,x,y,2)$ , and when subpath $(z,x,y,2)\to ((z-1+l)/l,x,y,2)$ for ( b ) is unfolded, $(z,x,y,2)\to (z,x,y,6)\to (z,x,y,5)\to ((z-1+l)/l,x,y,0)\to ((z-1+l)/l,x,y,1)\to ((z-1+l)/l,x,y,2)$ . These two paths are edge-disjoint. Therefore Stage 1 is edge-disjoint.

In Stage 2, all nodes do not have identical values of x and y at the same unit time on the broadcasting paths except for subpath $U(0,x,y,2)\to (0,x+(m/4),y+(n/4),2)$ for ( c ) , subpath $U(0,x,y,2)\to (0,x+(m/4),y-(n/4),2)$ for ( d ) , subpath $U(0,x,y,2)\to (0,x-(m/4),y+(n/4),2)$ for ( e ) , and subpath $U(0,x,y,2)\to (0,x-(m/4),y-(n/4),2)$ for ( f ) . Therefore, the paths are edge-disjoint with each other. When subpath $U(0,x,y,2)\to (0,x+(m/4),y+(n/4),2)$ for ( c ) is unfolded, $U(0,x,y,2)\to U(0,x+1,y+1,3)\to \cdots \to (0,x+(m/4),y+(n/4),2)$ . When subpath $U(0,x,y,2)\to (0,x+(m/4),y-(n/4),2)$ for ( d ) is unfolded, $U(0,x,y,2)\to (0,x,y,1)\to (0,x,y,8)\to (0,x+1,y-1,7)\to \cdots \to (0,x+(m/4),y-(n/4),2)$ . When subpath $U(0,x,y,2)\to (0,x-(m/4),y+(n/4),2)$ for ( e ) is unfolded, $U(0,x,y,2)\to (0,x,y,6)\to (0,x,y,7)\to (0,x-1,y+1,8)\to \cdots \to (0,x-(m/4),y+(n/4),2)$ . When subpath $U(0,x,y,2)\to (0,x-(m/4),y-(n/4),2)$ for ( f ) is unfolded,  $U(0,x,y,2)\to (0,x,y,3)\to (0,x-1,y-1,2)\to \cdots \to (0,x-(m/4),y-(n/4),2)$ . The above four paths are edge-disjoint at the starting node U under Lemma 2. Therefore, ( c ) , ( d ) , ( e ) , and ( f ) paths are edge-disjoint. The paths of Stage 3 are edge-disjoint under Lemma 1.

4. Conclusion

Once a new network is designed, various algorithms are proposed for its realization. The algorithms essential for this realization are routing and broadcasting algorithms. Routing algorithms for a 3D PT network have been proposed for design-related studies. In this paper, we proposed an algorithm for one-to-all broadcasting algorithm in an all-port wormhole-routed 3D PT network. This algorithm is based on the divide-and-conquer technique and utilizes the attribute of the 3D PT network that it can be continuously divided into 4 areas. The broadcasting step is $l/2+{\log }_2(n-1)+5$ and broadcasting path is disjoint to be effectively used in wormhole-routed 3D PT. This algorithm is used in copying task or data being in a node to another node. Application algorithms such as data migration and task allocation in 3D PT are required to be further studied.