{'fraction_non_alphanumeric': 0.040917238395450896, 'fraction_numerical': 0.008715000927127759, 'mean_word_length': 3.9305195794606127, 'pattern_counts': {'":': 0, '<': 3, '<?xml version=': 0, '>': 2, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 11, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
Bisection (Band)Width of Product Networks with Application to Data Centers

The bisection width of interconnection networks has always been important in parallel computing, since it bounds the amount of information that can be moved from one side of a network to another, i.e., the bisection bandwidth. Finding its exact value has proven to be challenging for some network families. For instance, the problem of finding the exact bisection width of the multidimensional torus was posed by Leighton and has remained open for almost 20 years. In this paper we provide the exact value of the bisection width of the torus, as well as of several d-dimensional classical parallel topologies that can be obtained by the application of the Cartesian product of graphs. To do so, we first provide two general results that allow to obtain upper and lower bounds on the bisection width of a product graph as a function of some properties of its factor graphs. We also apply these results to obtain bounds for the bisection bandwidth of a d-dimensional BCube network, a recently proposed topology for data centers.


Introduction
The bisection width and the bisection bandwidth of interconnection networks have always been two important parameters of a network. The first one reflects the smallest number of links which have to be removed to split the network in two equal parts, while the second one bounds the amount of data that can be moved between these parts. In general, both values are derivable one from the other, which is the reason why most previous work has been devoted to only one of then (in particular, the bisection width).
The bisection width has been a typical goodness parameter to evaluate and compare interconnection networks for parallel architectures [13,6,4]. This interest has been transferred to the Network-On-Chip topologies, as the natural successors of the parallel architectures of the 90's [12,14,21,18]. The bisection (band)width is also nowadays being used as a reference parameter on the analysis of the latest topologies that are being deployed in data centers. This can be seen in recent papers which propose new topologies, like BCube [10] or DCell [11]. The bisection (band)width is used to compare these new topologies with classical topologies, like grids, tori, and hypercubes, or with other datacenter topologies, like trees and fat trees.
Finding the exact value of the bisection width is hard in general. Computing it has proven to be challenging even for very simple families of graphs. For instance, the problem of finding the exact bisection width of the multidimensional torus was posed by Leighton [13,Problem 1.281] and has remained open for almost 20 years. One general family of interconnection networks, of which the torus is a subfamily, is the family of product networks. The topology of these networks is obtained by combining factor graphs with the Cartesian product operator. This technique allows to build large networks from the smaller factor networks. Many popular interconnection networks are instances of product networks, like the grid and the hypercube. In this paper we derive techniques to bound the bisection width of product networks, and apply these techniques to obtain the bisection width of some product network families.

Related work
To our knowledge, Youssef [19,20] was among the first to explore the properties of product networks as a family. He presented the idea of working with product networks as a divide-and-conquer problem, obtaining important properties of a product network in terms of the properties of its factor graphs.
The bisection width of arrays and tori was explored by Dally [5] and Leighton [13] in the early 90s, presenting exact results for these networks when the number of nodes per dimension was even. The case when there are odd number of nodes per dimension was left open. Rolim et al. [17] gave the exact values for the bisection width of 2 and 3dimensional grids and tori, but left open the question for longer number of dimensions.
For the special case in which all the factors are isomorphic, Efe and Fernández [8] provided a lower bound on the bisection width of a product graph as a function of a new parameter of a factor network they defined, the maximal congestion. Nakano [15] presented the exact value of the bisection width for the Cartesian product of isomorphic paths and cliques (i.e., square grids and Hamming graphs). If the factor graphs have k nodes, he proved that the d-dimensional square grid has bisection width k d−1 when k is even, and (k d −1) (k−1) when k is odd. Similarly, the square Hamming graph has bisection width k d+1 when k is even, and (k +1) (k d −1) 4 when k is odd. The exact bisection width of the d-dimensional square grid was found independently by Efe and Feng [7].
For the present paper it is very relevant the work of Azizoglu and Egecioglu. In [1] and [3] they studied the relationship between the isoperimetric number and the bisection width of different product networks. In the former paper, they find the exact value of the bisection width of the cylinders (products of paths and rings) with even number of nodes in its largest dimension. In the latter reference they found the exact bisection width of the grid A (d) k1,k2,...,k d , with k i nodes along dimension i, and where

Contributions
In this paper we present two theorems that allow to derive lower and upper bounds on the bisection width of a product network as a function of some simple parameters of its factor graphs. Then, we apply these results to obtain the exact value of the bisection width for several families of product networks. The families presented are of interest because they have been proposed as interconnection networks for parallel architectures, but their bisection width has never been derived exactly.
One of the most interesting contribution of this paper is the exact value of the bisection width of the torus, since, as mentioned before, this problem has been open for almost 20 years. We find here that the exact value of the bisection width of a ddimensional torus T (d) k1,k2,...,k d , that has k i nodes along dimension i, and where k 1 ≥ k 2 ≥ . . . ≥ k d , is exactly twice the bisection width of the grid of similar dimensions A (d) k1,k2,...,k d . I.e., where α is the smallest index for which k i is even (α = d if no index is even), and C i = d j=i+1 k j . Since this value will appear frequently, we will use the following notation throughout the rest of the paper, (1) k1,...,k d ) = 2Ψ(α). In addition to the result for the torus, we provide the exact value for the bisection width of products of complete binary trees (CBT) of any size (mesh connected trees [9]), products of extended CBT (which are CBT with the leaves connected with a path [9]), products of CBT and paths, and products of extended CBT and rings. To obtain the bisection bandwidth of these networks, we assume that every edge removed by the bisection width is in fact a duplex link with bandwidth of T in each direction. This directly implies that for any of these networks G, the bisection bandwidth is computed as BBW (G) = 2T · BW (G).
The general upper and lower bound results are also used to derive bounds on the bisection bandwidth of a topology proposed for datacenters, the BCube. A BCube is the Cartesian product of factors networks formed by k nodes connected via a k-port switch (where the switch is not considered to be a node). An essential difference of this topology from the previous one is that edges do not connect nodes directly, and the direct relation between bisection width and bisection bandwidth does not hold anymore. In networks with switches like this one, the switching capacity s of the switch comes into play as well. Since the bisection bandwidth is the parameter of interest in datacenters, we derive bounds on its value for two cases: when the bottleneck for the bisection bandwidth is fully at the switches, and when it is fully at the links. Table 1 summarizes the results for the bisection bandwidth obtained for the different parallel topologies and for BCube. As can be seen there, for the former the values obtained are exact, while for the latter upper and lower bounds do no match exactly. However, they differ by less than a factor of two.
The rest of the paper is organized as follows. Section 2 presents some basic definitions used in the rest of sections. In Section 3 we provide the general results to derive bounds on the bisection bandwidth of product networks. Section 4 and Section 5 present our results for the bisection bandwidth of some classical parallel topologies. Bounds on the bisection bandwidth of the BCube network are presented in Section 6. Finally, in Section 7 we present our conclusions and some open problems.

Graphs and bisections
In this section we present definitions and notation that will be used along the text. Given a graph 3 G, we denote its sets of vertices and edges as V (G) and E(G), respectively. In some cases, when it is clear from the context, only V or E will be used, omitting the graph G. Unless otherwise stated, the graphs considered are undirected.
Given a graph G with n nodes, we use S(G) to denote a subset of V (G) such that |S(G)| ≤ n 2 . We also use ∂ G S(G) to denote the set of edges connecting S(G) and The graph G may be omitted from this notation when it is clear from the context.
The main object of this work is to calculate the bisection width and bisection bandwidth of different product networks. These bisections can be defined as follows.
Definition 1. The bisection width of an n-node graph G, denoted BW (G), is the smallest number of edges that have to be removed from G to partition it in two halves. Formally, BW (G) = min S:|S|= n 2 |∂ G S|.
Definition 2. The bisection bandwidth of a network G, denoted BBW (G), is the minimal amount of traffic which can be transferred between any two halves of the network when its links are transmitting at full speed.
As mentioned above, unless otherwise stated we assume that all the links in a network G are duplex and have the same capacity T in each direction. Then, we can generally assume that the relation between the bisection bandwidth and the bisection width is BBW (G) = 2T · BW (G).

Factor and product graphs
We define first the Cartesian product of graphs.
We define now some of the basic factor graphs that will be considered.
Definition 6. The r-complete graph of k vertices denoted rK k , is a graph such that V (rK k ) = {0, 1, . . . , k − 1} and where E(rK k ) is a multiset such that each pair of vertices i, j ∈ V (rK k ) is connected with r parallel edges. (i.e., each e ∈ E(rK k ) has multiplicity r).
Using these and other graphs as factors, we will define, across the text, different d-dimensional Cartesian product graphs. For convenience, for these graphs we will use the general notation G (d) k1,...,k d , where G is the name of the graph, the superscript (d) means that it is a d-dimensional graph, and k 1 , . . . k d are the number of vertices in each dimension. (Superscript and subscripts may be omitted when clear from the context.) It will always hold that k 1 ≥ k 2 ≥ . . . ≥ k d , i.e., the factor graphs are sorted by decreasing number of vertices. We will often use n to denote the number of nodes a the graph G (d) k1,...,k d , i.e., n = k 1 k 2 · · · k d , and we will always use α to denote the index of the lowest dimension with an even number of vertices (if there is no such dimension, α = d, where d is the index of the lowest dimension). According to this notation we will present different d-dimensional product graphs as follows.
k1,...,k d , is the Cartesian product of d r-complete graphs of k 1 , . . . , k d nodes, respectively. I.e., rH Observe that the Hamming graph [2] is the particular case of the r-Hamming graph, with r = 1. For brevity, we use H k1,...,k d , to denote the Hamming graph.

Boundaries and partitions
We define now the dimension-normalized boundary [3].
k1,...,k d , any subset S of nodes, and any dimension i, it holds that Let us define the lexicographic-order. Consider graph H (d) k1,...,k d , we say that vertex x = (x 1 , x 2 , . . . , x d ) precedes vertex y = (y 1 , y 2 , . . . , y d ) in lexicographic-order if there exists an index i ∈ [1, d] such that x i < y i and x j = y j for all j < i. Azizoglu and Egecioglu [2] proved the following result.

Theorem 1 ([2]). Consider a d-dimensional Hamming graph H
Table 2 summarizes the basic notation used in this paper.

Bounds on the bisection width of product graphs
In this section we present general bounds on the bisection width of product graphs as well as presenting two important parameters, the normalized congestion and the central cut, which are used to obtain them. These bounds will be used in the upcoming sections to find the bisection width of several instances of product graphs.
Normalized congestion of graph G of multiplicity r mr(G) Congestion of graph G with multiplicity r E Set of all possible embeddings Mr of rKn onto G T Links capacity s Switching capacity

Lower bound
We start by defining the normalized congestion of a graph. Let G be a graph with n nodes. Then, an embedding of graph rK n onto G is a mapping of the edges of rK n into paths in G. We define the congestion of G with multiplicity r, denoted m r (G), as the minimum (over all such embeddings) of the maximum number of embedded paths that contain an edge from G. To formally define this concept, we first define the congestion of an edge e ∈ E(G) under the embedding M r of rK n onto G, denoted c Mr (e), as where E is the set of all possible embeddings of rK n onto G. Then, using Eqs. (5) and (3), we define the normalized congestion with multiplicity r of G as Having defined the normalized congestion, we proceed to extend Theorem 1 to r-Hamming graphs.
Theorem 2. Consider a d-dimensional r-Hamming graph rH (d) . Let S be any vertex subset of V (rH (d) ) andS the set of first |S| vertices of rH (d) in lexicographic order, then B rH (S) ≤ B rH (S).
Proof. We prove the theorem by contradiction. Assume that there is a set of vertices X =S such that |X| = |S| and B rH (S) > B rH (X). Then, applying Observation 1 to both X andS, we obtain that which contradicts Theorem 1 and proves the theorem.
We now present the following lemma.
LetS be a subset of the vertices of graph rH k1,k2,...,k d , such thatS are the first n 2 vertices of rH in lexicographic order, and n is the number of vertices of rH. Then, the dimension-normalized boundary ofS is Proof. We will derive first the value of B H (S), and then use Observation 1 to prove the claim. It was shown in [3], that ∂ H iS = ∅ for all i > α. 5 The number of edges in each dimension i ∈ [1, α] on the boundary ofS in H is Then, from the definition of B H (S), we obtain that Finally, from Observation 1, we derive Using Definition 3, Lemma 1, and Eq. (5), we obtain the following theorem.
Let β r (G i ) be the normalized congestion with multiplicity r of G i (for any r), for all i ∈ [1, d]. Consider any subset S ⊂ V (G) and the subsetS which contains the first |S| vertices of G, in lexicographic order. Then, Then, for S ⊂ V (G) as defined, Finally, using Theorem 2, we can state that From this theorem, we derive a corollary for the case of |S| = n 2 :

Upper bound
Having proved the lower bound on the bisection width, we follow with the upper bound. We define first the central cut of a graph G. Consider a graph G with n nodes, and a partition of V (G) into three sets S − , S + , and S, such that |S − | = |S + | = n 2 (observe that if n is even then S = ∅, otherwise |S| = 1). Then, the central cut of G, denoted CC(G), is Observe that, for even n, the central cut is the bisection width. Now we use the definition of central cut in the following theorem.
Proof. It was shown in [3] how to bisect A (d) by cutting exactly BW (A (d) ) = Ψ(α) links. Furthermore, this bisection satisfies that, if the paths P ki in dimension i are cut, each of them can be partitioned into subpaths P + and P − of size ki 2 (connected by a link if k i is even or by a node with links to both if k i is odd) so that the cut separates P + or P − from the rest of the path. Each path is then cut by removing one link. We map the sets S + and S + of the partition that gives the central cut of G i to P + and P − , respectively. Then, any cut of a paths P ki in dimension i becomes a cut of G i with at most CC(G i ) links removed.
Then, if S is the subset of V (G) that ends at one side of the bisection described above, we have that which also holds if the paths in dimension i are not cut. Applying this to all dimensions, we obtain This yields, proving Theorem 4.

Bisection width of products of CBTs and paths
In this section we will obtain the bisection bandwidth of product graphs which result from the Cartesian product of paths and CBTs. We will present, first, the different factor graphs we are using and the product graphs we are bisecting, then, we will compute the congestion and central cut of these factor graphs and, finally, calculate the bisection width of these product graphs.

Factor and product graphs
In this section we will work with paths, which were defined in Section 2, and CBTs, which we define now. Combining these factor graphs through the Cartesian product, we obtain the product networks that we define below.
Definition 11. A d-dimensional mesh-connected trees and paths, denoted MCTP (d) k1,k2,...,k d , is the Cartesian product of d graphs of k 1 , k 2 , . . . , k d vertices, respectively, where each factor graph is a complete binary tree or a path. I.e., MCTP We also define the d-dimensional mesh-connected trees [9], denoted MCT

Congestion and central cut of paths and CBTs
The bisection widths of the aforementioned product graphs can be calculated using the bounds defined in Section 3. To do so, we need to compute first the values of the normalized congestion and central cut of their factor graphs, it is, of a path and of a CBT.
We will start by computing the congestion of a path and of a CBT and, then, their central cuts. We present the following lemma.
Lemma 2. The congestion of P k with multiplicity r, denoted m r (P k ), has two possible values, depending on whether the number of vertices k is even or odd, as follows, Proof. This proof is illustrated in Figure 1 where it can be seen that there are two possible cases, depending on whether k is even or odd. The congestion m r (P k ) is defined as the minimum congestion over all embeddings of rK k onto P k . As there is only one possible path between every pair of vertices, the congestion of an edge will always be the same for any embedding M r of rK k into P k . Let M r be an embedding of rK k onto P k . Then, m r (P k ) = min If we fix e = (i, i+1) ∈ E(P k ), i ∈ [0, k −1], the congestion of e follows the equation: The value of i that maximizes c Mr (e) is i = k 2 − 1. As k is an integer, depending on whether k is even or odd, k 2 will be exact or not. Hence, we consider two possible cases, Using these values in Eq.   Corollary 3. The normalized congestion of a path is β r (P k ) = r 4 . The value of the congestion of a CBT will be exactly the same obtained for a path with an odd number of nodes. CBTs share the property of the path of having only one possible routing between two nodes. As can be seen in Figure 2, the possible cuts are similar. We present Lemma 3 for the congestion of a CBT.
Proof. Let CBT 2 j −1 be a complete binary tree of j levels with k = 2 j − 1 nodes. Whichever edge we cut results on two parts, one of them being another complete binary tree, let us call it A and assume it has l < j levels; and the other being the rest of the previous complete binary tree, let us call it B. The number of nodes in A will be 2 l − 1 while the number of nodes in B will be k − 2 l + 1. For any embedding M of rK k into CBT k , the congestion of any edge e follows the equation The value of l which maximizes the equation is l = j − 1, which is equivalent to cut one of the links of the root. This divides the tree into subgraphs of sizes k+1 2 and k−1 2 . Then, the final value for congestion will be m r (CBT k ) = r k 2 − 1 4 Corollary 4. The normalized congestion of a CBT is β r (CBT k ) = r 4 . The central cut of both the path and CBT can be easily deduced from Figures 1(a), 1(b) and 2, being CC(P k ) = CC(CBT k ) = 1.

Bounds on the bisection width of products of CBTs and paths
Having computed both the congestion and the central cut of the possible factor graphs, we can calculate now the lower and upper bound on the bisection width of a product of CBTs and paths. We will start by the lower bound on the bisection width. Proof. As we can see in Corollaries 3 and 4, the normalized congestion of both factor graphs is the same value r/4. Then, we can apply Corollary 2, so which yields, We follow now by presenting an upper bound on the bisection width of d-dimensional mesh-connected trees and paths. Proof. Obviously, as this graph can also be embedded into a d-dimensional array, we can use Theorem 4. We know that the central cut of both CBTs and paths is 1 independently of their sizes or number of levels, and hence also max i {CC(G ki )} = 1 (where G ki is either a CBT or a path). Then, From the results obtained from Lemma 4 and Lemma 5 the proof of Theorem 5 follows.
Theorem 5. The bisection width of a d-dimensional mesh-connected trees and paths MCTP We can also present the following corollary for the particular case of the d-dimensional mesh-connected trees MCT

Products of rings and extended trees
Similarly to what was done in Section 4, in this section we will obtain a result for the bisection bandwidth of the product graphs which result from the Cartesian product of rings and extended complete binary trees, a.k.a. XTs.

Factor and product graphs
The factor graphs which are going to be used in this section are rings and XTs. We define them below.
Definition 13. The extended complete binary tree (a.k.a. XT) of k vertices, denoted X k , is a complete binary tree in which the leaves are connected as a path. More formally, Combining these graphs as factor graphs in a Cartesian product, we can obtain the three following different kinds of product graphs: Definition 14. A d-dimensional mesh-connected extended trees and rings, denoted MCXR (d) k1,k2,...,k d , is the Cartesian product of d graphs of k 1 , k 2 , . . . , k d vertices, respectively, where each factor graph is a extended complete binary tree or a ring. I.e., MCXR k1,k2,...,k d , is the Cartesian product of d rings of k 1 , k 2 , . . . , k d vertices, respectively. I.e., T And, as happened in Section 4 with MCT (d) , we also define the d-dimensional mesh-connected extended trees, denoted MCX

Congestion and central cut of rings and XTs
The congestion and central cut of both a ring and an XT are needed to calculate the bounds obtained in Section 3. We present the following lemma for the congestion of a ring. Lemma 6. The congestion of R k with multiplicity r = 2 has two possible upper bounds depending on whether the number of vertices k is even or odd, as follows, Proof. While a path had only one possible routing, for R k we have two possible routes connecting each pair of nodes. If we embed rK k , for r = 2, into R k , we can route each of the parallel edges connecting two nodes through each of the possible routings. This yields, if k is odd. Similarly to what happened with paths and CBTs, the congestion of rings and XTs is the same. The extended complete binary tree X k has a Hamiltonian cycle [9], so we can find a ring R k contained onto it. Consequently, the congestion of an XT and a ring with the same number of nodes will be the same. Then, the normalized congestion of both factor graphs will also be the same.
Corollary 7. The normalized congestion with multiplicity r = 2 of an XT is β 2 (X k ) = 1/4. Due to these similarities, central cuts of both graphs are also going to be the same. As can be easily deduced from Figures 3(a), 3(b) and 4, CC(R k ) = CC(X k ) = 2.

Bounds on the bisection width of products of XTs and rings
As we did in Section 4, once we have computed the results for the normalized congestion and central cut of the different factor graphs, we can calculate the lower and upper bounds on the bisection width of products of XTs and rings. We will start by the lower bound on the bisection width presenting the following lemma. Proof. The normalized congestion of both factor graphs is β 2 (R k ) = β 2 (X k ) = 1 4 . Then, applying Corollary 2 with r = 2, Which yields, We calculate now the upper bound on the bisection width of a d-dimensional meshconnected rings and XTs. Proof. The d-dimensional mesh-connected XTs and rings graph can also be embedded into a d-dimensional array, so then, we can use Theorem 4. As happened with the congestion, the value of the central cut of both XTs and rings is the same, concretely, CC(R k ) = CC(X k ) = 2, independently of their sizes or number of levels. Hence, max i {CC(G ki )} = 2 (where G ki is either a ring or an XT). Then, From Lemma 7 and Lemma 8, Theorem 6 follows. From the bisection width of the d-dimensional mesh-connected XTs and rings, we can derive the following corollaries for the particular cases where all the factor graphs are rings, Torus T (d) , or XTs, mesh-connected extended trees MCX (d) .

BCube
We devote this section to obtain bounds on the bisection width of a d-dimensional BCube [10]. BCube is different from the topologies considered in the previous sections because it is obtained as the combination of basic networks formed by a collection of k nodes (servers) connected by a switch. These factor networks are combined into multidimensional networks in the same way product graphs are obtained from their factor graphs. This allows us to study the BCube as an special instance of a product network. The d-dimensional BCube can be obtained as the d dimensional product of one-dimensional BCube networks, each one of k nodes.

Factor and product graphs
We first define a Switched Star network and how a d-dimensional BCube network is built from it.
Definition 16. A Switched Star network of k nodes, denoted SS k , is composed of k nodes connected to a k-ports switch. It can be seen as a complete graph K k where all the edges have been replaced by a switch.
Combining this network d times as a factor network in the Cartesian product, we obtain a d-dimensional BCube.
k , is the Cartesian product of d SS k (the switches are not considered nodes for the Cartesian product). I.e., BC The main reason for obtaining the bisection width of a d-dimensional BCube is to be able to bound its bisection bandwidth. However, as the d-dimensional BCube is not a typical graph, the bisection width can have different forms depending on where the communication bottleneck is located in a BCube network.
We present two possible models for SS k . The first one, Model-A or star-like model, denoted by SSA k , consists of k nodes connected one-to-one to a virtual node which represents the switch. The second one, Model-B or hyperlink model, denoted by SSB k , consists of k nodes connected by a hyperlink. While the two presented models are logically equivalent to a complete graph, they have a different behavior from the traffic point of view. We show this with two simple examples.
Let us consider that we have a SS 3 where the links have a speed of 100 Mbps while the switch can switch at 1 Gbps. Under these conditions, the links become the bottleneck of the network and, even when the switches would be able to provide a bisection bandwidth of 1 Gbps, the effective bisection bandwidth is only of 200 Mbps in both directions.
Consider the opposite situation now, where the BCube switch only supports 500 Mbps of internal traffic while the links transmit at 1 Gbps. In this case, the switches are the bottleneck of the network and the bisection bandwidth is only 500 Mbps, although the links would be able to support up to 2 Gbps.
The first example illustrates an scenario where we would bisect the network by removing the links that connect the servers to the switches, which corresponds to Model A. On the other hand, what we find in the second example is a typical scenario for Model B, where we would do better by removing entire switches when bisecting the network. In particular, being s the switching capacity of a switch, and T the traffic supported by a link, we will choose Model-A when s ≥ k 2 · 2T and Model-B when s ≤ 2T . (Note that this does not cover the whole spectrum of possible values of s, T , and k.)

Congestion and central cut of BCube
We will compute now the congestion and central cut of both models in order to be able to calculate the respective lower and upper bounds. We start by the congestion and central cut of Model-A.
Model-A is also called star-like model. The name of star-like comes from the fact that the factor graph can be seen as a star with the switch in the center. If we set r = 1, the congestion of every link of the star is easily found to be m r (SSA k ) = k − 1 6 as shown in Figure 5(b).
The central cut, which is also trivial and can be found in Figure 5(c), will depend on whether the number of nodes k is even or odd, Having computed the congestion and the central cut for Model-A, we will compute them now for Model-B. We also call Model-B hyperlink model 7 due to the fact that all the servers from the BCube are connected by a hyperlink so no switch is needed.
Calculating the congestion of a Model-B BCube will be easy then. If we set r = 1 there will be only one edge to be removed, the congestion of the graph will be total amount of edges of its equivalent K k , i. e., m r (SSB k ) = k(k−1) 2 . Corollary 11. The normalized congestion of SSB k is As for Model-A, the central cut is easily computed. As there is only one hyperlink, its central cut will be CC(BCB k ) = 1. Both m r (SSB k ) and CC(BCB k ) are shown in Figures 6(b) and 6(c). Having computed the congestion and central cut of both models, we can calculate the lower and upper bounds on the bisection width of each one of them.
We will start by the lower and upper bounds on the bisection width of model A and, then, we will calculate both bounds for model B.
We first present the following lemma for the lower bound on the bisection width of a Model-A BCube.
k , is lower bounded by k d+1 4(k−1) if k is even, and by k+1 Proof. Using the value of the normalized congestion of a Model-A BCube in Corollary 2, it follows that After proving the lower bound on the bisection width of a Model-A d-dimensional BCube, we follow with the upper bound. if k is odd.
Proof. The Cartesian product of Model-A star-like factor graphs can be embedded into a d-dimensional array, so Theorem 4 will be extremely useful again. If we use the values of the central cut of Model-A in Theorem 4, is immediate to compute the following upper bound if k is odd. Now, from the combination of Lemma 9 and Lemma 10 we can state Theorem 7: Let us calculate now the bounds of a Model-B d-dimensional BCube. As we did with Model A, we will first prove the lower bound and then the upper one. For the lower bound we present the following lemma. Proof. As for model A, the d-dimensional BCube resulting from the Cartesian product of Model-B graphs can be embedded into a d-dimensional array. Thanks to this fact, we can use the computed value of its central cut in Theorem 4 to obtain the upper bound on the bisection width, Combining the previous lemmas we can state the following theorem.

Conclusions
Exact results for the bisection bandwidth of various d-dimensional classical parallel topologies have been provided in this paper. These results consider any number of dimensions and any size, odd or even, for the factor graphs. These multidimensional graphs are based on factor graphs such as paths, rings, complete binary trees or extended complete binary trees. Upper and lower bounds on the bisection width of a ddimensional BCube are also provided. Some of the product networks studied had factor graphs of the same class, like the d-dimensional torus, mesh-connected trees or meshconnected extended trees, while some other combined different factor graphs, like the mesh connected trees and paths or mesh-connected extended trees and rings. See Ta