# Strict-Sense Nonblocking Conditions for thelog2⁡N-1 Multirate Switching Fabric for the Discrete Bandwidth Model

Authors: Remigiusz Rajewski
Journal: Mathematical Problems in Engineering
 (2019)

---

## Abstract

The article discusses the strict-sense nonblocking conditions derived for thelog2⁡N-1 multirate switching fabric for the discrete bandwidth model at the connection level. Architecture of the log2⁡N-1 switching fabric was described in previous study; however, conditions for the multirate discrete bandwidth model as well as comparison with different structures have not been published before. Both sufficient and necessary conditions were introduced and proved in this study. A few numerical examples which help to understand an idea of the multirate bandwidth model for the log2⁡N-1 switching fabrics were delivered as well. Additionally a comparison of achieved results to thebanyan switching structures and a comparison of the costs of all mentioned in this study structures expressed as the number of optical elements were done.


---

## Body

## 1. Introduction

Thelog2⁡N-1 switching fabric was formally described in [1], where N denotes the number of inputs/outputs of switching fabric. It was shown that the log2⁡N-1 switching network is a better solution for optical switching than typical banyan-type switching networks. The multiplane version of the mentioned switching architecture is called the multi-log2⁡N-1 switching fabric and it was described in detail in [1] as well. A multiplane switching network is achieved by vertically stacking p copies of the log2⁡N-1 structure. These p planes have to be connected to inputs and outputs of the switching fabric. The idea of a multiplane structure is shown in Figure 1. The exact number of planes p used to build the multi-log2⁡N-1 switching fabric depends strongly on the type of nonblocking conditions. The strict-sense nonblocking (SSNB) and rearrangeable nonBlocking (RNB) conditions for the space-division multi-log2⁡N-1 switching fabric were described in detail and proved in [1]. The multi-log2⁡N-1 switching network was later extended to the MBA(N,e,2) switching fabric (where e is the maximal number of inputs and/or outputs one switching element can have; for details see [2]), whereas the SSNB and RNB conditions for the MBA(N,e,2) switching network were delivered in [2] and [3], respectively.Figure 1
The idea of a multiplane switching network.In [1] it was shown that the log2⁡N-1 switching fabric is a very attractive solution, compared withbanyan [4–6],omega [5–7], andbaseline [5, 6, 8] switching networks. Actually, the attractive element of the solution is the cost of one plane as well as the multiplane switching fabric, where cost is expressed as the number of active and passive optical switching elements.A multirate switching network is a structure in which any connection is associated with a weight representing a certain bandwidth of input and output as well as interstage links. Interstage links just connect inputs with outputs of the switching network. In the discrete bandwidth model, it is assumed that there is a finite number of rates and the lowest rate divides all other rates. The lowest rate is very often called a channel or a basic bandwidth unit. In this study, it is assumed that each interstage link hasbM channels (or rates) and each input and output link has bIO channels (or rates), where bIO⩽bM. A new connection might require an integer number of channels c, where 1⩽c⩽C⩽bIO and C denotes the maximal number of channels demanded by a single request. The discrete bandwidth model will be considered in this study.Different multirate switching networks were described in [9–22]. It should be noted that this type of switching networks has been considered in recent years as an interesting solution [23–27]. This type of structure can be used, for example, in Data Center Networks (DCNs) [28–32], in multiprocessor systems, in UMTS, and in 4G or in 5G networks where bandwidth is a very crucial aspect. By using multirate structures, it is also possible to handle a different network traffic in telecommunication and computer networks generated by many services handled by network providers or companies. Such a different type of traffic could be caused by, for example, video streaming, voice calls in the Voice over IP (VoIP) services, data transmission, websites viewing by home and company users, and so on. Using a new type of switching network structures in DCNs or multiprocessor systems allows building more energy–efficient and cheaper architectures, where the cost could be understood as the number of active and passive optical switching elements [1, 2, 33]. However, the topic of energy–efficiency is not considered in this study and it will be discussed in a future article. In turn, the classification of different types of services enables the proper management of resources and appropriate performance for each of these services. Each service requires different resources, expressed very often in basic bandwidth units or in the number of channels. If sufficient resources are available, each service considered can be realized in such a switching network. It was assumed that one connection represents some service and each service requires a different number of channels c, where the maximal number of channels one service could demand is C, and c⩽C.In turn, the classification of different types of services enables the proper management of resources and appropriate performance for each of these services especially for the UMTS/4G/5G networks. Each service requires different resources, expressed very often in basic bandwidth units or in the number of channels. And for the UMTS/4G/5G networks bandwidth is a very crucial aspect due to many users to be served and restrictions of the available bandwidth. If sufficient resources are available, each service considered can be realized in such a switching network. In this study it was assumed that one connection represents some service and each service requires a different number of channelsc, where the maximal number of channels one service could demand is C, and c⩽C.It should be also noted that a special type of a multirate switching network is an Elastic Optical Network (EON), regarded as a “hot topic” in optical networking and switching [34–43]. Optical networks used currently by network operators and Internet providers will be in the immediate future replaced by EONs. Moreover, EONs will probably also be soon widely used in DCNs [44–47]. In an EON any connection is established on an optical path. Such a path can occupy a bandwidth that is a multiple of a so–called frequency slot unit (FSU) [36]. A frequency slot unit occupies 12.5 GHz of the bandwidth [48] and c adjacent frequency slot units may be assigned to one optical path to set up a connection. This may be modeled by the discrete bandwidth model with a single rate denoting the frequency slot unit and c denoting the number of such units in one connection. The discrete bandwidth model of the log2⁡N-1 switching fabric could be used in EONs; however, SSNB conditions will be different than those described in this study due to assumption that not any free FSUs but only adjacent free FSUs are used in EONs for each connection. Therefore, description of how to adopt the SSNB log2⁡N-1 switching network into EON is not topic of this study and it will be presented in a future article.The remainder of this paper is organized as follows. In Section2, a general model representing the log2⁡N-1 switching fabric is described. This model constitutes a starting point for considerations included in the next sections of this article. In Section 3, the discrete bandwidth model is described. A relation between the number of channels required by a new connection and the number of available channels in inputs’ (outputs’) as well as in interstage links are delivered. A theorem giving the proper number of planes for the strict-sense nonblocking log2⁡N-1 switching fabric is delivered. A proof for sufficient and necessary conditions is included in this section as well. In Section 4 a few numerical examples explaining how to find a proper number of planes for preset switching network’s parameters are shown. In Section 5 achieved results and comparison of the log2⁡N-1 switching fabric with thebanyan structure are presented. The last section constitutes the conclusions and directions of the future work.


## 2. Model Description

Both one plane and multiplanelog2⁡N-1 switching fabrics have a capacity N and are built from n′=log2⁡N-1 stages [1]. If the number of stages n′ is even, two outer stages (the input stage s1 and the output stage sn′), as well as n′-2 inner stages (denoted by sx, where x=2,3,…,n′-2,n′-1), can be found. In turn, if the number of stages n′ in the log2⁡N-1 switching network is odd, one more stage can be identified. This additional stage is called the central stage and it is denoted by sn′+1/2. The log2⁡N-1 switching fabric stages are shown in Figure 2(a).Figure 2
One plane of alog2⁡16-1 switching network: (a) switching elements and links representation, (b) the bipartite graph representation.
(a) (b)In the remaining part of this article, the topology of thelog2⁡N-1 switching network will be represented by a bipartite graph [20, 22, 49–52]. Thus, it is possible to simplify the analysis of occupied channels and planes for the discrete bandwidth model. Such a bipartite graph is built from nodes and edges. Each node corresponds to exactly one input, output, or interstage link in a switching network. In turn, each edge corresponds to exactly one crosspoint in such a switching network. An example of bipartite graph representation of one plane of the switching network from Figure 2(a) is shown in Figure 2(b).A graph of intersecting path will also be used [1, 20, 22, 49]. Such a graph constitutes a subgraph of the bipartite graph, which makes it possible to simplify the analysis of the relationship between intersecting paths and the considered path in the worst-case scenario. An example of a graph of intersecting path of the switching network from Figure 2(a) is shown in Figure 3. There are four such graphs possible. More accurate and comprehensive discussion of these graphs can be found in [1].Figure 3
Four possible intersecting graphs for alog2⁡16-1 switching network: (a) graph 1, (b) graph 2, (c) graph 3, (d) graph 4.
(a) (b) (c) (d)In the space-division switching network represented by a bipartite graph, it is not allowed for two paths (where each path corresponds to a different connection) to meet at the same node of this graph. If it happens, one connection is blocked. To solve this problem, a multiplane structure could be used (see Figure1). Then, each connection could be set up in a separate plane. The number of planes depends on the type of nonblocking or blocking conditions.To simplify further calculations, thek parameter will be used(1)k=n′-1mod⁡2,where mod denotes a modulo operation. k=0 if the number of stages n′ in the log2⁡N-1 switching network is odd and k=1 for an even number of stages n′.Generally, the considered path between inputi and output o in the log2⁡N-1 switching fabric is denoted by i,o. The considered path goes through more than one node in the bipartite graph. Path i,o could be blocked by any of the already set up paths. A total number of paths intersecting with path i,o in the bipartite graph is denoted by A. All blocking paths could be divided into two sets: I and O. The number of blocking connections in these sets is AI and AO, respectively, where(2)A=AI+AO.SetI consists of all nodes of the bipartite graph carrying intersecting paths that could be achieved from the input side of the log2⁡N-1 switching network. It should also be noted that the number of intersecting paths in set I strongly depends on the log2N-1 switching fabric’s capacity. For capacities N=8 and N=16, set I has AI=2 intersecting paths. For N=32, set I has AI=7 intersecting paths. Generally, for greater capacities (N⩾32), each intersecting path could be established from inputs numbered from 0 to 2⌈log2⁡N/2⌉-1, to outputs numbered from 2⌈log2⁡N/2⌉ to N-1, where symbol y denotes the smallest integer greater than or equal to y. Therefore, there are 2⌈log2⁡N/2⌉ intersecting paths; however, it should be mentioned that one of these paths is in fact the considered path i,o. Thus, in set I, for capacity N⩾32, there is a total of AI=2⌈log2⁡N/2⌉-1 intersecting paths. When putting all the above cases together, the number of intersecting paths AI which can intersect with the considered connection i,o is as follows:(3)AI=2forN=8,162log2⁡N/2-1forN⩾32SetO consists of all nodes of the bipartite graph carrying intersecting paths that could be achieved from the output side of the log2⁡N-1 switching fabric. Like for set I, the number of intersecting paths in set O strongly depends on the log2⁡N-1 switching fabric’s capacity. For N=8 in set O there are AO=0 intersecting paths. For capacities N=16 and N=32, set O consists of AO=2 intersecting paths. For greater capacities (N⩾64) each intersecting path could be set up from inputs numbered from 2⌈log2⁡N/2⌉ to N-1, to outputs numbered from 0 to 2⌈log2⁡N/2⌉-1-1. When the number of stages n′ is odd, then each intersecting path from set O could be set up from inputs numbered from 2⌈log2⁡N/2⌉ to N-1, to outputs numbered from 0 to 2⌈log2⁡N/2⌉-1. It should also be noted that one of these paths is the considered path i,o. Thus, using expression (1), in set O there is a number of AO=2⌈log2⁡N/2⌉-k-1 intersecting paths. When putting all the above cases together, the number of intersecting paths AO with the considered connection i,o is as follows:(4)AO=0forN=82forN=16,322log2⁡N/2-k-1forN⩾64SetsI and O are shown in Figures 4(a) and 4(b) for even and odd number of stages n′ in the log2⁡N-1 switching fabric, respectively. Sets I and O are denoted by a blue and a red background, respectively, and the proper nodes of the intersecting paths graph, representing input and output links, are colored blue and red, respectively, as well. It could be seen that, for an odd number of stages n′, both sets I and O are equal to each other (see Figure 4(b)). When the central stage is present (the number of stages n′ is even), it is already included in set I (see Figure 4(a)).Figure 4
SetsI and O in the intersecting paths graph for (a) a log2⁡32-1 switching network, (b) a log2⁡64-1 switching network.
(a) (b)


## 3. Discrete Bandwidth Model

For the discrete bandwidth model, the capacity of any link is divided into basic bandwidth units, also called channels. A given connection can occupyc such channels, where c is limited by C, and C denotes the maximal number of channels that could be occupied by a single connection. Generally, the number of channels available at each input or at each output link is denoted by bIO, and the number of channels available at each interstage link is denoted by bM. The relationship between the mentioned numbers of channels is 1⩽c⩽C⩽bIO⩽bM.In the remaining part of this study, a single connection established between input linki and output link o, which requires c channels, will be denoted by 〈i,o,c〉. A new connection 〈i,o,c〉 could be set up if(5)bIO-∑ycy⩾c,where ∑ycy denotes the number of channels in the input link i (output link o) occupied by y already set up connections. In a similar way, an interstage link could be used to establish connection i,o,c when(6)bM-∑ycy⩾c,where ∑ycy denotes the number of channels in the interstage link occupied by y already set up connections. It means that the interstage link which has(7)dc=bM-c+1occupied channels is inaccessible for connection i,o,c.Moreover, to clarify further calculation and formulas,E(i;c) designation will be used. E(i;c) is given by the following expression:(8)Ei;c=i-idcdc,where symbol y denotes the greatest integer value lower than or equal to y.Theorem 1.
The multi-log2⁡N-1 switching network is strict-sense nonblocking for the discrete bandwidth model and for condition 1⩽c⩽C⩽bIO⩽bM if and only if(9)p⩾p1+p2+p3+p4+1,where(10)p1=AI·bIOdC,(11)p2=AO·bIOdC,(12)p3=EAIbIO;C+bIO-CdC,(13)p4=EAObIO;C+bIO-CdC.Proof.
The necessary and sufficient conditions will be proved using the worst-case scenario in the multi-log2⁡N-1 switching fabric.
The considered connection is denoted byi,o,c. This connection could be blocked in any bipartite graph node if in this node, except connection 〈i,o,c〉, other connections are set up, which occupy d(c) channels altogether in an interstage link. These blocking connections could originate in sets I and O. The number of blocking paths in these sets is determined by expressions (3) and (4), respectively. According to the assumption for the discrete bandwidth model (see Section 1), in each input and output link there are bIO available channels and d(c) channels block the considered connection (there are no free channels required by connection i,o,c). It should be noted that d(c) channels block the considered connection i,o,c in one plane. The number of planes in which connection i,o,c is blocked by the intersecting paths originating in set I is(14)p1=AI·bIOdc.The number of planes in which the considered connection is blocked by the intersecting paths originating in set O is(15)p2=AO·bIOdc.It should be also mentioned that, in the worst-case scenario, in set I there are(16)EAIbIO;c=AI·bIO-AI·bIOdc·dcfree channels and in set O there are(17)EAObIO;c=AO·bIO-AO·bIOdc·dcfree channels. Additionally, it should be taken into account that there could be bIO-c free channels at input link i, and exactly the same number of free channels could be at output link o. Thus, blocking connections from the above-mentioned additional free channels can occupy(18)p3=EAIbIO;c+bIO-cdcand(19)p4=EAObIO;c+bIO-cdcadditional planes from input and output side of the switching network, respectively.
In the worst-case scenario, besides planesp1,p2,p3, and p4, one more plane is needed to set up the considered connection i,o,c. Therefore, finally (20)p⩾p1+p2+p3+p4+1planes are needed, where p1,p2,p3, and p4 are given by expressions (14), (15), (18), and (19), respectively.
The number of planesp must be maximized for all c. The maximum will be achieved if c=C. Thus, using C in expressions (14), (15), (18), and (19), the conditions given inTheorem1 will be obtained.
A well known switching theory method based on finding the worst-case scenario in switching fabrics [1, 2, 20] was used in the proof. It allowed the determination of the necessary as well as the sufficient conditions.The discrete bandwidth model could be adopted in all systems where channels are used. Thus, for example, this model will work for the UMTS system, the 4G system, the 5G system, and so on. It could be assumed that each kind of channels used, for example, in the UMTS/4G/5G, could be divided into basic bandwidth units (or in fact into smallest channels or slots). One UMTS/4G/5G channel then will use maximumC small channels/slots.


## 4. Numerical Examples

Three examples will be described in order to analyze the proof from Section3. These examples show how to find the proper number of planes p for the strict-sense nonblocking log2⁡N-1 switching network. Of course, examples with more channels bIO available at each input and output and more channels in interstage links bM are possible as well; however, to increase clarity they are not presented in the examples below.


### 4.1. Example 1

In this example alog2⁡16-1 switching fabric built from n′=3 stages is investigated. At each input and output link there are bIO=4 available channels, and at each interstage link there are bM=6 available channels. Moreover, the maximal number of channels that can be occupied by a new connection is C=2. Therefore, a log2⁡16-1 switching fabric is nonblocking in strict-sense if it is built from a minimum of p=5 planes. The worst-case scenario is shown in Figure 5. One plane cannot be used to set up connection i,o,2 if in a bipartite graph in connection path i,o there can be found any node that handles d(C)=5 channels occupied by other already set up connections.Figure 5
The worst-case scenario in alog2⁡16-1 switching network for n′=3, bIO=4, bM=6, C=2, and p=5 (filled cells denote occupied channels, nonfilled (white) cells denote free channels): (a) plane 1, (b) plane 2, (c) plane 3, (d) plane 4, (e) plane 5.
(a) (b) (c) (d) (e)All intersecting paths from setI block p1=1 plane (see Figure 5(a)). In turn, all intersecting paths from set O block p2=1 plane (see Figure 5(b)).It should be noted that at the considered inputi there are 2 free channels which together with 3 unused channels in set I can block p3=1 additional plane (see Figure 5(c)). A similar situation occurs at the output side of log2⁡16-1 switching fabric. In set O, there are 3 free channels that were not used by the blocking connections originating in set O. These 3 channels together with 2 channels at the considered output o can block another p4=1 additional plane (see Figure 5(d)).The considered connectioni,o,2 has to be set up in an additional plane; therefore, one more plane is needed (see Figure 5(e)). Thus, a log2⁡16-1 switching network is SSNB if the total number of planes is p=p1+p2+p3+p4+1=5.


### 4.2. Example 2

In this example alog2⁡16-1 switching fabric built from n′=3 stages is investigated. At each input and output link there are bIO=4 available channels, and at each interstage link there are bM=10 available channels. Moreover, the maximal number of channels a new connection can occupy is C=3. Therefore, log2⁡16-1 switching fabric is nonblocking in strict-sense if it is built from a minimum of p=3 planes. The worst-case scenario is shown in Figure 6. One plane cannot be used to set up connection 〈i,o,3〉 if in a bipartite graph in connection path 〈i,o〉 there can be found any node that handles d(C)=8 channels occupied by other already set up connections.Figure 6
The worst-case scenario in alog2⁡16-1 switching network for n′=3, bIO=4, bM=10, C=3, and p=3 (filled cells denote occupied channels, nonfilled (white) cells denote free channels): (a) plane 1, (b) plane 2, (c) plane 3.
(a) (b) (c)All intersecting paths from setI block p1=1 plane (see Figure 6(a)). In turn, all intersecting paths from set O block p2=1 plane (see Figure 6(b)).It should be noted that at the considered inputi there is only one free channel and there are no free channels in set I. However, one channel cannot block the considered connection i,o,3; therefore, p3=0. A similar situation occurs at the output side of log2⁡16-1 switching fabric. In set O there are no free channels and there is only one free channel at the considered output o. However, this one channel cannot block the considered connection i,o,3; therefore, p4=0.The considered connectioni,o,3 has to be set up in an additional plane; therefore, one more plane is needed (see Figure 6(c)). Thus, a log2⁡16-1 switching network is SSNB if the total number of planes is p=p1+p2+p3+p4+1=3.


### 4.3. Example 3

In this example alog2⁡64-1 switching fabric built from n′=5 stages is investigated. At each input and output link there are bIO=3 available channels and at each interstage link there are bM=11 available channels. Moreover, the maximal number of channels a new connection can occupy is C=3. Therefore, a log2⁡64-1 switching fabric is nonblocking in strict-sense if it is built from a minimum of p=5 planes. The worst-case scenario is shown in Figures 7, 8, and 9. One plane cannot be used to set up connection 〈i,o,3〉 if in a bipartite graph in connection path 〈i,o〉 there can be found any node which handles d(C)=9 channels occupied by other already set up connections.Figure 7
The worst-case scenario in alog2⁡64-1 switching network for n′=5, bIO=3, bM=11, C=3, and p=5, part 1 (filled cells denote occupied channels, nonfilled (white) cells denote free channels): (a) plane 1, (b) plane 2.
(a) (b)Figure 8
The worst-case scenario in alog2⁡64-1 switching network for n′=5, bIO=3, bM=11, C=3, and p=5, part 2 (filled cells denote occupied channels, nonfilled (white) cells denote free channels): (a) plane 3, (b) plane 4.
(a) (b)Figure 9
The worst-case scenario in alog2⁡64-1 switching network for n′=5, bIO=3, bM=11, C=3, and p=5, part 3 (filled cells denote occupied channels, nonfilled (white) cells denote free channels): plane 5.All intersecting paths from setI block p1=2 planes (see Figures 7(a) and 7(b)). In turn, all intersecting paths from set O block p2=2 planes (see Figures 8(a) and 8(b)).It should be noted that at the considered inputi there are no free channels and there are 3 free channels in set I. However, these 3 channels cannot block the considered connection i,o,3; therefore, p3=0. A similar situation occurs at the output side of log2⁡64-1 switching fabric. In set O there are 3 free channels and there are no free channels at the considered output o. However, these 3 channels cannot block the considered connection 〈i,o,3〉; therefore, p4=0.The considered connectioni,o,3 has to be set up in an additional plane; therefore, one more plane is needed (see Figure 9). Thus, a log2⁡64-1 switching network is SSNB if the total number of planes is p=p1+p2+p3+p4+1=5.


## 4.1. Example 1

In this example alog2⁡16-1 switching fabric built from n′=3 stages is investigated. At each input and output link there are bIO=4 available channels, and at each interstage link there are bM=6 available channels. Moreover, the maximal number of channels that can be occupied by a new connection is C=2. Therefore, a log2⁡16-1 switching fabric is nonblocking in strict-sense if it is built from a minimum of p=5 planes. The worst-case scenario is shown in Figure 5. One plane cannot be used to set up connection i,o,2 if in a bipartite graph in connection path i,o there can be found any node that handles d(C)=5 channels occupied by other already set up connections.Figure 5
The worst-case scenario in alog2⁡16-1 switching network for n′=3, bIO=4, bM=6, C=2, and p=5 (filled cells denote occupied channels, nonfilled (white) cells denote free channels): (a) plane 1, (b) plane 2, (c) plane 3, (d) plane 4, (e) plane 5.
(a) (b) (c) (d) (e)All intersecting paths from setI block p1=1 plane (see Figure 5(a)). In turn, all intersecting paths from set O block p2=1 plane (see Figure 5(b)).It should be noted that at the considered inputi there are 2 free channels which together with 3 unused channels in set I can block p3=1 additional plane (see Figure 5(c)). A similar situation occurs at the output side of log2⁡16-1 switching fabric. In set O, there are 3 free channels that were not used by the blocking connections originating in set O. These 3 channels together with 2 channels at the considered output o can block another p4=1 additional plane (see Figure 5(d)).The considered connectioni,o,2 has to be set up in an additional plane; therefore, one more plane is needed (see Figure 5(e)). Thus, a log2⁡16-1 switching network is SSNB if the total number of planes is p=p1+p2+p3+p4+1=5.


## 4.2. Example 2

In this example alog2⁡16-1 switching fabric built from n′=3 stages is investigated. At each input and output link there are bIO=4 available channels, and at each interstage link there are bM=10 available channels. Moreover, the maximal number of channels a new connection can occupy is C=3. Therefore, log2⁡16-1 switching fabric is nonblocking in strict-sense if it is built from a minimum of p=3 planes. The worst-case scenario is shown in Figure 6. One plane cannot be used to set up connection 〈i,o,3〉 if in a bipartite graph in connection path 〈i,o〉 there can be found any node that handles d(C)=8 channels occupied by other already set up connections.Figure 6
The worst-case scenario in alog2⁡16-1 switching network for n′=3, bIO=4, bM=10, C=3, and p=3 (filled cells denote occupied channels, nonfilled (white) cells denote free channels): (a) plane 1, (b) plane 2, (c) plane 3.
(a) (b) (c)All intersecting paths from setI block p1=1 plane (see Figure 6(a)). In turn, all intersecting paths from set O block p2=1 plane (see Figure 6(b)).It should be noted that at the considered inputi there is only one free channel and there are no free channels in set I. However, one channel cannot block the considered connection i,o,3; therefore, p3=0. A similar situation occurs at the output side of log2⁡16-1 switching fabric. In set O there are no free channels and there is only one free channel at the considered output o. However, this one channel cannot block the considered connection i,o,3; therefore, p4=0.The considered connectioni,o,3 has to be set up in an additional plane; therefore, one more plane is needed (see Figure 6(c)). Thus, a log2⁡16-1 switching network is SSNB if the total number of planes is p=p1+p2+p3+p4+1=3.


## 4.3. Example 3

In this example alog2⁡64-1 switching fabric built from n′=5 stages is investigated. At each input and output link there are bIO=3 available channels and at each interstage link there are bM=11 available channels. Moreover, the maximal number of channels a new connection can occupy is C=3. Therefore, a log2⁡64-1 switching fabric is nonblocking in strict-sense if it is built from a minimum of p=5 planes. The worst-case scenario is shown in Figures 7, 8, and 9. One plane cannot be used to set up connection 〈i,o,3〉 if in a bipartite graph in connection path 〈i,o〉 there can be found any node which handles d(C)=9 channels occupied by other already set up connections.Figure 7
The worst-case scenario in alog2⁡64-1 switching network for n′=5, bIO=3, bM=11, C=3, and p=5, part 1 (filled cells denote occupied channels, nonfilled (white) cells denote free channels): (a) plane 1, (b) plane 2.
(a) (b)Figure 8
The worst-case scenario in alog2⁡64-1 switching network for n′=5, bIO=3, bM=11, C=3, and p=5, part 2 (filled cells denote occupied channels, nonfilled (white) cells denote free channels): (a) plane 3, (b) plane 4.
(a) (b)Figure 9
The worst-case scenario in alog2⁡64-1 switching network for n′=5, bIO=3, bM=11, C=3, and p=5, part 3 (filled cells denote occupied channels, nonfilled (white) cells denote free channels): plane 5.All intersecting paths from setI block p1=2 planes (see Figures 7(a) and 7(b)). In turn, all intersecting paths from set O block p2=2 planes (see Figures 8(a) and 8(b)).It should be noted that at the considered inputi there are no free channels and there are 3 free channels in set I. However, these 3 channels cannot block the considered connection i,o,3; therefore, p3=0. A similar situation occurs at the output side of log2⁡64-1 switching fabric. In set O there are 3 free channels and there are no free channels at the considered output o. However, these 3 channels cannot block the considered connection 〈i,o,3〉; therefore, p4=0.The considered connectioni,o,3 has to be set up in an additional plane; therefore, one more plane is needed (see Figure 9). Thus, a log2⁡64-1 switching network is SSNB if the total number of planes is p=p1+p2+p3+p4+1=5.


## 5. Results and Comparison

To compare the multiplanelog2⁡N-1 switching fabric with the multiplanebanyan switching network of the same capacity N, the number of planes p is not enough as a comparison parameter due to differences in the construction of one plane in each mentioned structure and a different measure parameter has to be used.The multiplanebanyan network is built of p vertically staked planes, similarly to the multiplane log2⁡N-1 switching fabric; more than one plane is needed to ensure SSNB conditions. Therefore, to compare different structures to each other very often, the number of crosspoints in the switching network is used [6, 53–55]. However, for optical networks such a parameter is still not enough. Therefore, in this article it was assumed, similarly to that in [1, 2], that the cost of the optical switching network is expressed as the number of active ϕa (semiconductor optical amplifiers) and passive ϕp (optical splitters and optical combiners) optical switching elements. It results from the fact that the size and/or number of passive and active optical elements depends strongly on the capacity of a particular optical switching element which is used to build a switching network. And what is more, sometimes not only one type of switching elements is used to build a switching fabric. Therefore, counting ϕp and ϕa allows us to compare one–plane structures with multiplane structures as well as different multiplane structures with each other.It should also be noted that the cost of a whole switching fabric is the cost of one plane multiplied by the number of such planes plus additional passive optical elements (optical splitters at the input side and optical combiners at the output side of the switching network) used to connect these planes to inputs and outputs of the switching fabric (as it can be seen in Figure1). A detailed description of one plane’s cost of the multiplanebanyan switching fabric is given in [56] and the cost of one plane of a multiplane log2⁡N-1 switching fabric is given in [1]. Therefore, taking into account the number of planes p given inTheorem1, the exact cost of a multiplane log2⁡N-1 switching fabric can be calculated.It should be noted that the total cost of a switching network is expressed as the sum of partial costs; one is the cost given as the number of passive optical elementsϕp and the second cost is given as the number of active optical elements ϕa. However, the cost of one optical splitter or optical combiner is not equal to the cost of one semiconductor optical amplifier. Generally, one active optical element is about 10 times more expensive than a passive optical element. Thus, in this article a normalized cost was introduced and it is given as(21)ψ=ϕa+0.1ϕp.Tables1, 2, and 3 show the partial cost of different switching fabrics expressed as the number of passive optical elements ϕp, the partial cost of different switching fabrics expressed as the number of active optical elements ϕa, and the normalized cost of different switching network’s structures ψ. For both partial costs (ϕp and ϕa) there is also an additional column where some percentage values are given. It should be understood what part of the cost of the multiplanebanyan switching network constitutes the cost of the multiple log2⁡N-1 switching fabric. If the percentage value is higher than 100% then thebanyan switching network is cheaper, and if this value is lower than 100% then the log2⁡N-1 switching fabric is built of a fewer number of optical elements. For example for the partial cost expressed in passive optical elements, when the capacity is N=64, then ϕp for a 10-planebanyan switching network is 9 600 and ϕp for a 13-plane log2⁡16-1 is 6 016, which constitutes 63% of 9 600. In both cases the number of planes (10 and 13) makes a switching fabric SSNB. The bold font for the normalized cost was used to show which structure is cheaper.Table 1
The number of passive optical elementsϕp, active optical elements ϕa, and the normalized cost ψ for a given capacity N for different SSNB switching fabrics where bIO=4,bM=6, and C=2.
N ϕ p ϕ a ψ banyan log 2 ⁡ N - 1 % banyan log 2 ⁡ N - 1 % banyan log2⁡N-1 8 48 134 279% 48 144 300% 52.8 157.4 16 480 528 110% 384 500 130% 452.0 552.8 32 2 688 2 240 83% 2 240 2 016 90% 2 508.8 2 240.0 64 9 600 6 016 63% 7 680 7 488 98% 8 640.0 8 089.6 128 23 552 21 120 90% 19 712 24 320 123% 22 067.2 26432.0 256 85 504 59 392 69% 69 632 70 400 101% 78 182.4 76 339.2 512 280 576 207 872 74% 248 832 233 472 94% 276 889.6 254 259.2 1 024 948 224 587 776 62% 819 200 678 912 83% 914 022.4 737 689.6 2 048 2 465 792 1 974 272 80% 2 207 744 2 179 072 99% 2 454 323.2 2 376 499.2 4 096 8 413 184 5 488 640 65% 7 372 800 6 205 440 84% 8 214 118.4 6 754 304.0 8 192 24 018 944 18 391 040 77% 21 938 176 20 054 016 91% 24 340 070.4 21893 120.0 16 384 79 003 648 51 216 384 65% 70 647 808 57 098 240 81% 78 548 172.8 62 219 878.4Table 2
The number of passive optical elementsϕp, active optical elements ϕa, and the normalized cost ψ for a given capacity N for different SSNB switching fabrics where bIO=4,bM=10, and C=3.
N ϕ p ϕ a ψ banyan log 2 ⁡ N - 1 % banyan log 2 ⁡ N - 1 % banyan log2⁡N-1 8 48 84 175% 48 96 200% 52.8 104.4 16 288 304 106% 256 300 117% 284.8 330.4 32 1 152 1 216 106% 960 1 120 117% 1 075.2 1 241.6 64 4 736 3 200 68% 3 840 4 032 105% 4 313.6 4 352.0 128 14 336 11 904 83% 12 544 14 080 112% 13 977.6 15 270.4 256 52 736 34 816 66% 45 056 42 240 94% 50 329.6 45 721.6 512 153 600 122 368 80% 138 240 141 312 102% 153 600.0 153 548.8 1 024 534 528 350 208 66% 471 040 412 672 88% 524 492.8 447 692.8 2 048 1 523 712 1 189 888 78% 1 396 736 1 347 584 96% 1 549 107.2 1 466 572.8 4 096 5 136 384 3 358 720 65% 4 620 288 3 870 720 84% 5 133 926.4 4 206 592.0 8 192 14 450 688 11 165 696 77% 13 418 496 12 451 840 93% 14 863 564.8 13 568 409.6 16 384 47 742 976 31 227 904 65% 43 581 440 35 373 056 81% 48 355 737.6 38 495 846.4Table 3
The number of passive optical elementsϕp, active optical elements ϕa, and the normalized cost ψ for a given capacity N for different SSNB switching fabrics where bIO=3,bM=11, and C=3.
N ϕ p ϕ a ψ banyan log 2 ⁡ N - 1 % banyan log 2 ⁡ N - 1 % banyan log 2 ⁡ N - 1 8 48 42 88% 48 48 100% 52.8 52.2 16 128 96 75% 128 100 78% 140.8 109.6 32 1 152 704 61% 960 672 70% 1 075.2 742.4 64 3 456 2 432 70% 3 072 2 880 93% 3 417.6 3 123.2 128 10 752 8 192 76% 8 960 10 240 114% 10 035.2 11 059.2 256 32 256 26 624 83% 28 672 30 976 108% 31 897.6 33 638.4 512 116 736 81 920 70% 101 376 98 304 97% 113 049.6 106 496.0 1 024 358 400 247 808 69% 327 680 279 552 85% 363 520.0 304 332.8 2 048 1 073 152 786 432 73% 946 176 917 504 97% 1 053 491.2 996 147.2 4 096 3 301 376 2 375 680 72% 3 047 424 2 641 920 87% 3 377 561.6 2 879 488.0 8 192 10 190 848 7 340 032 72% 9 158 656 8 388 608 92% 10 177 740.8 9 122 611.2 16 384 31 424 512 21 594 112 69% 29 360 128 23 674 880 81% 32 502 579.2 25 834 291.2It may look a little bit strange that for some capacity (like, for example,N=128 in Table 1 or N=128 and N=256 in Table 3) thebanyan switching fabric is a cheaper solution than the log2⁡128-1 switching fabric; however, it results directly from the SSNB conditions, i.e., the number of planes needed to build a particular SSNB switching network. It should also be noted that the required number of planes depends on parameters: bIO, bM, and C; it can be clearly seen in Tables 1, 2, and 3. In the case when bIO=4, bM=6, C=2, and N=128, the number of planes is 11 and 19 for the multiplanebanyan and multi-log2⁡128-1 switching network, respectively. Because one plane is built of passive and active optical elements, in the case when there are more planes it could mean that such a solution is then more expensive, like it is, for example, for N=128, bIO=4, bM=6, and C=2 for the multi-log2⁡128-1 switching network (see Table 1) or for N=256, bIO=3, bM=11, and C=3 for the multi-log2⁡256-1 switching network (see Table 3).It can be seen that forbIO=4, bM=6, and C=2 the multiplanebanyan network is a cheaper solution than the multiplane log2⁡N-1 switching fabric only for capacities N=8, N=16, and N=128. For other capacities, the multiplane log2⁡N-1 is always a cheaper solution. For bIO=4, bM=10, and C=3 the multiplanebanyan network is a cheaper solution for capacities N⩽128. For greater capacity (N⩾256) the multi-log2⁡N-1 switching fabric is always a cheaper solution. In turn, for bIO=3, bM=11, and C=3, the multiplanebanyan network is a cheaper solution only for capacities N=128 and N=256. For other capacities, the multi-log2⁡N-1 switching fabric is always a cheaper solution.Switching networks of larger capacity, with hundreds or even thousands of interfaces, are commonly used in backbone network’s nodes or in DCNs (for example, line cards). In turn, switching networks of smaller size are very often used in end devices like, for example, access points or home–user routers. It should be noted that the multiplanelog2⁡N-1 switching fabric and the multiplanebanyan switching network are dedicated to be used in backbone networks and so the difference in cost becomes a more significant factor.Switching structures can also be compared with each other using other parameters like, for example, power consumption or latency. In this case, however, the results depend not only on the structure itself but on the physical implementation as well, and the physical implementation of a switching fabric strongly depends on the technology in which the switching network is realized. Some optical paths can be lengthened to align latency in the switching fabric; therefore latency for each path could be the same in the whole structure. Because of that, a latency as a comparison parameter is not considered in this study.


## 6. Conclusions

In this article, a theorem of strict-sense nonblocking conditions for thelog2⁡N-1 switching fabric for the discrete bandwidth model was delivered. This type of a switching network was described in detail in a few papers; however, multirate traffic has not been considered before. The multirate log2⁡N-1 optical switching network could be used, for example, in DCNs, in multiprocessor systems or in UMTS/4G/5G networks where bandwidth is a very crucial aspect. The discrete bandwidth model allows us to describe the behavior of a multiservice system where each service could require different basic bandwidth units (channels).The theorem proposed in this article was proved with the use of a method known in switching networks, based on finding the worst-case scenario in a switching fabric. It allowed for the determination of the necessary, as well as the sufficient conditions. A few numerical examples were given to illustrate how the proper number of planes was calculated for the strict-sense nonblockinglog2⁡N-1 switching fabric. The results obtained in this article’s results were discussed and compared to thebanyan switching network’s architecture as well. What is more, the cost (expressed as the number of passive and active optical switching elements) of both switching fabrics discussed in this study was also compared. From the results it is clearly visible that for an optical core network’s nodes the multi-log2⁡N-1 switching fabric is a cheaper solution than the multiplanebanyan-type switching network.It should be noted that both switching networks compared in this article could be built of switching elements of different sizes. Nevertheless, such a detailed comparison is a more complex task due to architectural differences of compared architectures like thebanyan switching fabric built of d×d switching elements (where d⩾2), the MBA(N,e,2) switching fabric [2], and it constitutes a future work.The strict-sense nonblocking condition for thelog2⁡N-1 multirate switching network for the continuous bandwidth model is under study now as well.



---

*Source: 2096598-2019-04-08.xml*