# The Strict-Sense Nonblocking Multiratelogd(N,0,p) Switching Network

Authors: Wojciech Kabaciński; Remigiusz Rajewski
Journal: Mathematical Problems in Engineering
 (2017)

---

## Abstract

This paper considers the nonblocking conditions for a multiratelogd(N,0,p) switching network at the connection level. The necessary and sufficient conditions for the discrete bandwidth model, as well as sufficient and, in particular cases, also necessary conditions for the continuous bandwidth model, were given. The results given for dn-1/2f0≥f1+1 in the discrete bandwidth model are the same as those proposed by Hwang et al. (2005); however, in this paper, these results were extended to other values of f0, f1, and d. In the continuous bandwidth model for B+b>1, the results given in this paper are also the same as those by Hwang et al. (2005); however, for B+b≤1, it was proved that a smaller number of vertically stacked logdN switching networks are needed.


---

## Body

## 1. Introduction

A multirate switching network is a network in which any connection is associated with weightω. Such a weight represents a certain bandwidth of input and output ports and interstage links connecting these input and output ports. The capacity of the links is normalized and is usually equal to 1 for interstage links. Input and output ports’ capacity is in many cases lower than the interstage links’ capacity and is denoted by β, where β≤1. Weight ω is also limited by range [b,B], b<B, where 0<b≤ω≤B≤β≤1.Depending on the possible values ofω, two models of multirate connections are considered in the literature: the discrete bandwidth model and the continuous bandwidth model. In the discrete bandwidth model, it is assumed that there are a finite number of distinct rates {b1,b2,…,bk} and the smallest rate b1 divides all other rates bk, where k=2,…,K. Denote b=b1 and B=max⁡{bk:k=1,2,…,K}. The smallest rate is often called a channel. In this paper, we assumed that each internal link has cM channels and each input or output link has cI/O channels, where cM=⌊1/b⌋, cI/O=⌊β/b⌋, and cI/O≤cM. Every new connection is associated with a positive integer c, where 1≤c≤C≤cI/O and C is the maximal number of channels that one request can demand. In the continuous bandwidth model, connections may occupy any fraction of a link’s transmission capacity from interval [b,B]. Both models are considered in this paper.One of the best known multistage switching networks is the 3-stage Clos network [1]. Nonblocking conditions for single-rate and multicast connections were considered by many authors [2–5]. The first upper bound of nonblocking conditions in the case of the continuous bandwidth model was proposed by Melen and Turner in [6]. This upper bound was later improved by Chung and Ross in [7]. In turn, asymmetrical switch configurations were considered in [8]. More generalized 3-stage Clos switching fabrics were considered by Liotopoulos and Chalasani [9]. The results derived in those papers were limited to b=0 or B∈(1-b,B]. Both sufficient and necessary nonblocking conditions for any B and b>0 were proved in [10, 11] in the case of symmetrical and asymmetrical 3-stage Clos switching networks, respectively. In some papers, the blocking probability at the connection level was also considered [12–14].Another switching network considered in the literature is the vertically stacked Banyan type switching network [15–18]. Multirate logd(N,m,p) switching fabrics were considered in [19, 20], where necessary and sufficient conditions were given for the discrete bandwidth model when 1/b is an integer, and a sufficient condition, as well as a necessary condition for B∈(1-b,β], for the continuous bandwidth model was proved. Better upper bounds, which in some cases are also lower bounds, for log2(N,0,p) switching networks were given in [21, 22]. Multirate log2(N,0,p) switching fabrics with multicast connections were considered in turn in [23]. Some architectures, which may be considered as special cases of log2(N,m,p) networks, like extended delta and Cantor switching fabrics, were considered earlier in [6, 7, 24].The results presented in [19, 20] have been improved by Hwang et al. in [25]. They proved both sufficient and necessary conditions for the strict-sense nonblocking operation of logd(N,m,p) networks for the discrete bandwidth model, but only where d⌊n-1/2⌋cI/O≥cM+1. They also proved sufficient and necessary conditions for the continuous bandwidth model when b+B>1 and sufficient conditions when b+B≤1 (the conditions are also necessary in case b=0).In this paper, we also consider a multiratelogd(N,m,p) switching network, however, only for m=0. The results for m≥1 are under study. First, we extended the results given in [25] for the discrete bandwidth model to the general case. Then, we also introduce sufficient condition for the continuous bandwidth model when b+B≤1. In most cases, these sufficient conditions are also necessary.It should be noted that nowadays multirate switching networks [6–14, 16–19, 23, 24] are getting more popular each day [26–30]. A special kind of such a multirate network is an elastic optical network [31–36] which constitutes a “hot topic” in optical networking and switching. In the future, elastic optical networks will replace the current optical networks used by network operators and will also probably be used in data centers. In the elastic optical network, an optical path may occupy a bandwidth which is a multiple of the so-called frequency slot unit. This frequency slot unit occupies 12.5 GHz of the bandwidth and c adjacent frequency slot units may be assigned to one optical path. This may be described by using the discrete bandwidth model with b denoting the frequency slot unit and c denoting the number of such units in one connection.Multirate type of structure can be used, for example, in data center networks [37–41] or in multiprocessor systems. By using multirate structures, it is also possible to handle network traffic in telecommunication and computer networks generated by many services handled by network providers or companies. Using a new type of switching network structures in data centers or multiprocessor systems allows building more energy-efficient and cheaper architectures, where the cost could be understood as the number of cross points [3, 4] or as the number of active and passive optical switching elements [42]. The topic of energy efficiency is not considered in this paper; however, this paper could be a starting point for such an investigation.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 4G/5G networks. Each service requires different resources, expressed very often in basic bandwidth units or in the number of channels. And for the 4G/5G networks bandwidth is a very crucial aspect. 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 channelsc, where the maximal number of channels one service could demand is C, and c≤C.Motivation of this paper was to improve already known best results for the strict-sense nonblocking multiratelogd(N,0,p) switching network [25]. In the next sections, it is described in detail how better results were achieved. The logd(N,0,p) switching network constitutes nowadays a quite interesting architecture which could be used in optical network nodes especially for d=2, where physical implementation is much easier than that for d≥3, where d denotes the size of one switching element.This paper is organized as follows. In Section2, the model used in this paper is described. In the next section, the nonblocking operation of the considered network is discussed for the discrete bandwidth model. In Section 4, strict-sense nonblocking conditions for the continuous bandwidth model are considered. In the next section, a few numerical examples for both discrete and continuous bandwidth models are presented. In the same section, the results obtained in this paper are compared with the already known upper bounds. The last section includes conclusions.


## 2. Model Description

Thelog2(N,0,p) switching network was proposed in [16]. Such a network is constructed by vertically stacking p copies of log2N networks (the main idea of stacking planes is shown in Figure 1). This architecture was later extended to the log2(N,m,p) switching network in [17]. Such an extended network is obtained by adding m extra stages to the log2N network and vertically stacking p copies of the log2(N,m,1) network. The log2(N,m,p) switching network is a particular case of the logd(N,m,p) switching network which consists of d×d symmetrical switching elements. The logd(N,m,p) switching network is nonblocking in the strict sense when there are a sufficient number of vertically stacked planes p, so any connection between a free input and a free output can be realized regardless of the routing algorithm used.Figure 1
An example oflog2(16,0,2) switching network.The architecture of thelogd(N,0,p) switching network (where d=2, N=16, and p=2) is shown in Figure 2. It consists of p vertically stacked logdN networks composed of d×d switches. These logdN networks are called planes. At each input terminal there is a splitter 1×p and at each output terminal there is a combiner p×1. Throughout the discussion in this paper, bipartite graphs [43–46] will be used to represent the topology of the switching network [16, 18]. In a bipartite graph, which represents the space-division network, two paths are not allowed to intersect at a node. If this happens, this means that one of these two paths is blocked.Figure 2
An example oflog2(16,0,2) switching network.Before we move on to the next part of this paper, we will determine the number of pathsA that may intersect with a given path in one node. Let us assume that we want to set up connection 〈i,o〉 between input terminal i and output terminal o. This connection will be blocked in one plane if another connection is already set up through one of the nodes belonging to path 〈i,o〉. These nodes can belong to the part of the switching network that is reachable from input terminals or to the part of the switching network that is reachable from output terminals. These two parts of the switching network will be denoted as set I. These parts are equal and both of them have n-1/2 or n-2/2 stages for n odd or n even, respectively, where n=logdN. Let us determine(1)x=n-1mod2.When n is odd, we have x=0, or x=1 when n is even. So, the above stage numbers can be superseded to n-1-x/2. The number of paths reachable at the node of stage n-1-x/2 is equal to dn-1-x/2. However, one of these paths is the path which belongs to the considered connection 〈i,o〉, so the number of paths that intersect with the given path 〈i,o〉 is equal to(2)AI=dn-1-x/2-1.When n is even, there is also the central stage n/2 and there are AM additional paths that intersect with the considered path 〈i,o〉, where M denotes a set of these additional paths. The number of these additional paths is equal to(3)AM=d-1·dn-1-x/2.According to formulas (2) and (3), it should also be noted that the number of all paths that can intersect with the considered path 〈i,o〉 is denoted by A and is given by the following equation:(4)A=AI+AM.


## 3. Discrete Bandwidth Model

In the discrete bandwidth model, the capacity of the link is divided into bandwidth units also called channels. A connection may occupyc such channels, where c is usually limited by C, which denotes the maximum number of channels one connection may occupy, and 1≤c≤C≤cI/O≤cM. In the general case, cI/O denotes the number of channels at each input and output link, while cM is the number of such channels in any interstage link. A connection between input i and output o which requests c channels will be denoted by 〈i,o,c〉. This connection can be realized in input i and output o when cI/O-∑kck≥c, where ∑kck denotes the number of channels already occupied by the existing connections at input i (output o). Similarly, an interstage link can be used by the connection when cM-∑jcj≥c, where ∑jcj denotes the number of channels occupied by connections already set up through this interstage link. This means that an interstage link which has(5)zc≥cM-c+1channels occupied is inaccessible for connection 〈i,o,c〉. We will also use the following equations to make the final formulas more transparent:(6)Xi;c=i·cI/Ozc,(7)Yi;c=i-izc·zc,(8)Zc=YA·cI/O;c+cI/O-c.Theorem 1.
Thelogd(N,0,p) switching network is strict-sense nonblocking for the discrete bandwidth model, and 1≤c≤C≤cI/O≤cM if and only if(9)p≥2·XAI;C+x·XAM;C+ZCzC+x·YAM·cI/O;C+ZCzC+1.Proof.
Sufficient and necessary conditions will be proved by showing the worst state in the switching network. Let a new connection be〈i,o,c〉. This connection may be blocked if any node of stages 1 to n-1 carries connections that already occupy z(c) channels. These blocking connections can be set up from AI inputs, and they block 〈i,o,c〉 in nodes of stages 1 to ⌊n-1/2⌋, or to AI outputs (they will block the new connection in stages ⌈n+1/2⌉ to n-1). When n is even, 〈i,o,c〉 may also be blocked in the node of stage n/2 by connections from AM inputs. Since there are cI/O channels at each input or output and z(c) channels block the connection in one plane, the number of planes that may be inaccessible by 〈i,o,c〉 is(10)p1=2·AI·cI/Ozc+x·AM·cI/Ozc=2·XAI;c+x·XAM;c.In the set of AI inputs, we may still have(11)AI·cI/O-AI·cI/Ozc·zc=YAI·cI/O;cfree channels and cI/O-c channels at input i and output o. Therefore, we may have(12)Zc=YAI·cI/O;c+cI/O-cchannels free in input and output ports. Connections in these channels may occupy(13)p2=Zczcadditional planes. Similarly, connections to the set of AI outputs may occupy additional planes, but when n is even, we also have to consider the center stage. It must only be counted once, since connections from inputs of the set of M inputs have to be set up to the set of M outputs, to intersect with the path of the new connection in the node of stage n/2. So, we may have(14)p3=Zc+x·YAM·cI/O;czcadditional planes inaccessible by the new connection. In the worst-case scenario, one more plane is needed to set up connection 〈i,o,c〉. Thus, finally,(15)p≥p1+p2+p3+1=2·AI·cI/Ozc+x·AM·cI/Ozc+Zczc+Zc+x·YAM·cI/O;czc+1planes are needed.
The number of planesp must be maximized through all c and it reaches a maximum at c=C; then, by putting C in respective formulas ((10), (13), and (14)), we obtain conditions given in Theorem 1 (see formula (9)).In the case whenC=cI/O=cM=1, we have the space-division switching network and we may simplify the previous formulas. So, this time, the interstage link is inaccessible by considered connection 〈i,o,C〉 if it has(16)zC=1-1+1=1channels occupied, and expressions (6), (7), and (8) have form as follows, respectively:(17)Xi;C=i1=i,(18)Yi;C=i-i=0,(19)ZC=0+1-1=0.As a result, Theorem 1 in this case is(20)p≥2·AI+x·AM+01+0+01+1=2·AI+x·AM+1.This result corresponds to the results given for space-division switching networks by Lea [16].WhenC=cI/O=1 and cM=v, we obtain the so-called v-dilated switching network presented in Figure 3. v interstage links are inaccessible by a new connection 〈i,o,C〉 when they have(21)zC=v-1+1=vchannels occupied and expressions (6), (7), and (8) have form as follows, respectively:(22)Xi;C=iv,(23)Yi;C=i-iv·v,(24)ZC=YAI;C.Theorem 1 in this case is(25)p≥2·AIv+x·AMv+YAI;Cv+x·YAM;C+YAI;Cv+1.Figure 3
Thev-dilated log2(8,0,1) switching network.The discrete 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 channel used, for example, in the UMTS/4G/5G could be divided into basic bandwidth units (or in fact into the smallest channels or slots). One UMTS/4G/5G channel then will use maximumC small channels/slot.


## 4. Continuous Bandwidth Model

In the continuous bandwidth model, a connection may occupy any fraction of the link capacity. This fraction is called the weight of a connection and is denoted byω. A connection from input i to output o of weight ω will be denoted by 〈i,o,ω〉. Weight ω is limited by interval [b,B], b<B, and 0<b≤ω≤B≤β≤1, where β denotes the normalized bandwidth of input and output links. Input i (output o) is accessible by the new connection 〈i,o,ω〉 if β-∑kωk≤ω,  where ∑kωk denotes the total weight of all connections already set up at input i (output o). An interstage link is accessible by this new connection when 1-∑jωj≤ω, where ∑jωj denotes the total weight of all connections already set up through this interstage link. Similarly as in [3, 22], the following functions will be used:(26)ζi;j=ij,ijis  not  an  integer  orij=0;0,forj=0;ij-1,ijis  an  integer  andij>0;(27)ϕ1i;j=i-j·ζi;j,forζi;j≠0,i-j·ζj;j>b;0,forζi;j≠0,i-j·ζi;j≤b;i,forζi;j=0;(28)ϕ2i;j=jϕ1i;j,forϕ1i;j≥b;0,forϕ1i;j<b;(29)ϕ3i=i,fori≥b;0,fori<b.In these equations,ζ(β;1-ω) denotes the number of connections that can be set up in one input (output) link of the smallest weight which will block a connection of weight ω in one interstage link. In turn, ϕ1(β;1-ω) denotes a bandwidth in an input (output) link which remains after setting up ζ(β;1-ω) connections of weight 1-ω+ϵ, where ϵ→0, in this link. ϕ2(β;1-ω) denotes the number of connections of weight ϕ1(β;1-ω), so that ϕ2(β;1-ω)+1 such connections may block one interstage link for a new connection of weight ω. ϕ3(i) indicates whether weight i can be used by the next connection or not.We will also use the following equations to make our final formulas more transparent:(30)αi;β;B=i-ϕ2β;1-B+1iϕ2β;1-B+1ϕ1β;1-B;(31)γi;β;B=i·ϕ1β;1-B;(32)δ=1-Bb,1-Bbis  not  an  integer;1+1-Bb,1-Bbis  an  integer.Theorem 2.
Thelogd(N,0,p) switching network is strict-sense nonblocking for the continuous bandwidth case, and 0<b<B≤β≤1 if(33)p≥2ψAI+xψAM+1,where ψ(i) is given in the following formula:(34)ψi=iβb,for1-b<B;iβ/b+AI/i·β-B/b2,for1-2b<B≤12,14<b<12i·ζβ;1-B,for  otherB’s,ϕ1β;1-B<b;i·ζβ;1-B+iϕ2β;1-B+1+ζαi;β;B+AIiϕ3β-B;1-B+iAMζϕ1αAI;β;B+ϕ3β-B;1-B+ϕ1αAM;β;B;1-B;1-B,for  otherB’s,b≤ϕ1β;1-B<2borϕ1β;1-B=2b,ζβ;1-B>0;iβ/b+AI/i·β-B/bδ,for  otherB’s,ϕ1β;1-B=2b,ζβ;1-B=0;i·ζβ;1-B+ζγi;β;B+AIi·ϕ3β-B;1-B+iAM·ζϕ1γAI;β;B+ϕ3β-B;1-B+ϕ1γAM;β;B;1-B;1-B,for  otherB’s,ϕ1β;1-B>2b.Proof.
Sufficient conditions will be proved by showing the worst state in the switching network. Suppose we want to add the new connection denoted by〈i,o,ω〉, where 0<b≤ω≤B≤β≤1. The connection path from input terminal i will be inaccessible for the new connection of weight ω if there is a node in the connecting path 〈i,o〉 which already carries connections of the total weight greater than 1-ω. In the worst-case scenario, this sum of weights should be as small as possible, say 1-ω+ϵ, where ϵ is close to but greater than 0. However, in the worst-case scenario, when 1-ω<b, the path is inaccessible if a connection of weight b is set up through at least one of its nodes. When 1-ω≥B, it is not possible that one connection will occupy weight 1-ω+ϵ. In this case, at least two connections must be set up. When 1-ω<2b, the total weight of the blocking connections is equal to 2b. In other cases, it is always possible to set up one or more connections of the total weight 1-ω+ϵ. Therefore, three cases can be distinguished:(i)
Case 1: for1-ω<b(ii)
Case 2: forB≤1-ω<2b(iii)
Case 3: for other values of1-ω
Case  1  (1-ω<b). A plane is inaccessible for a new connection 〈i,o,ω〉 if there is a node on the connecting path 〈i,o〉 which already carries a connection of weight b. In the worst-case scenario, each of such connections can be set up through a different plane. In one input link, ⌊β/b⌋ connections of weight b can be set up. If ⌊β/b⌋ is not an integer, there is some free bandwidth at this input terminal, but its weight is lower than b and it cannot be used to set up the next connection in this link. The connecting path of connection 〈i,o,ω〉 may be blocked by another connecting path from input or output terminals. Connection 〈i,o,ω〉 may be blocked in the node of stage k, where 1≤k≤⌊n-1-x/2⌋, so there are AI such paths from the input terminals. Connection 〈i,o,ω〉 may also be blocked in the node of stage l, where ⌊n+1+x/2⌋≤l≤n-1, so there are AI such paths to the output terminals, too. Thus, there are 2·AI available inputs and outputs, and connections of weight b from these inputs or to these outputs may block(35)p1=2·AI·βbplanes. When n is even, there is also the central stage n/2 and x=1 (when n is odd, x=0). So, there may be additional(36)p2=x·AM·βbplanes blocked. In the worst-case scenario, one more plane is needed to set up connection 〈i,o,ω〉. Therefore, finally,(37)p≥p1+p2+1=2·AIβb+x·AMβb+1planes are needed.
Case  2 (B≤1-ω<2b). A plane is inaccessible for a new connection 〈i,o,ω〉, if there is a node on the connecting path 〈i,o〉 which already carries two connections of weight b. Similar to the previous case, there may be ⌊β/b⌋ connections of weight b at each input terminal other than i and ⌊β-ω/b⌋ connections of weight b at input terminal i. Thus, there are AI·⌊β/b⌋+⌊β-ω/b⌋ connections, and 2 connections make a node inaccessible for the new connection 〈i,o,ω〉. The same situation occurs at every output terminal. Therefore,(38)p1=2·AI·β/b+β-ω/b2planes are needed. When n is even, then there is also the central stage. Connections passing through the node which belongs to this stage block(39)p2=AM·β/b2planes. It should be noted that since AM=(d-1)·dn-1-x/2, AM is always even and there will be no bandwidth of weight b available for the next connection from inputs counted in AM. There may only be a free bandwidth of weight b at inputs counted in AI or in input i; however, one connection of such weight will not block the new connection. So, in the worst-case scenario, one more plane is needed to set up connection 〈i,o,ω〉. Therefore, finally,(40)p≥p1+p2+1=2·AI·β/b+β-ω/b2+x·AM·β/b2+1planes are needed.
Case  3 (other values of 1-ω). A plane is inaccessible for a new connection 〈i,o,ω〉, if there is a node on its connecting path that already carries connections of the total weight greater than 1-ω. When 1-ω<B, only one connection of such weight may be set up. In the other case, at least two connections must be set up and their total weight should be greater than 1-ω. At each input or output terminal, ζ(β;1-ω) such connections may be set up and(41)p1=AI·ζβ;1-ωplanes may be blocked for the new connection. However, there is still a free bandwidth of weight β-ω at input terminal i and at output terminal o, too. When β-ω≤1-ω, a connection of weight greater than 1-ω at these terminals cannot be set up. So, there is still a free bandwidth of weight ϕ1(β;1-ω) at each input and output terminal, except i and o. It may be used by subsequent connections, provided that ϕ1(β;1-ω)≥b. If b≤ϕ1(β;1-ω)<2b or ϕ1(β;1-ω)=2b and ζ(β;1-ω)>0, several connections of such weight, which pass through one node, may make the plane inaccessible by the new connection. The minimum number of these connections is denoted by ϕ2(β;1-ω)+1. Therefore, the next(42)p2=AIϕ2β;1-ω+1planes will be inaccessible by the new connection. However, there can still be some free bandwidth of weight ϕ3(β-ω) at input terminal i and free bandwidth of weight(43)αAI;β;ω=AI-ϕ2β;1-ω+1·AIϕ2β;1-ω+1·ϕ1β;1-ωat input terminals not counted in p2. The same situation occurs at the output terminals. When this weight is greater than 1-ω, it may block(44)p3=ζαAI;β;ω+ϕ3β-ω;1-ωadditional planes. We still have a free bandwidth of weight ϕ1(α(AI;β;ω)+ϕ3(β-ω);1-ω) but this bandwidth is lower than or equal to 1-ω and cannot block a plane for the new connection. When ϕ1(β;1-ω)>2b, the total weight of the free bandwidth at the input terminals is equal to(45)γAI;β;ω=AI·ϕ1β;1-ω.Connections using this bandwidth and the free bandwidth of weight ϕ3(β-ω) at input terminal i will occupy not more than(46)p4=ζγAI;β;ω+ϕ3β-ω;1-ωplanes. The weight of all the remaining bandwidth is now ϕ1(γ(AI;β;ω)+ϕ3(β-ω);1-ω). The same situation occurs at the output terminals, including o. When n is even, similar considerations may be used to receive the number of planes ψ(AM) blocked by the connections from inputs counted in AM (it should be noted that, in AM, we have no input i and output o, so ϕ3(β-ω) cannot be considered). Thus, there are(47)p1′=AM·ζβ;1-ω,forϕ1β,1-ω<b;p2′=AMϕ2β;1-ω+1,forb≤ϕ1β;1-ω<2b;p3′=ζαAM;β;ω;1-ω,forb≤ϕ1β;1-ω<2borϕ1β;1-ω=2b,ζβ;1-ω>0;p4′=ζγAM;β;ω;1-ω,forϕ1β;1-ω>2bplanes.
Nevertheless, at each input terminal counted in the central stage, there may be a free bandwidth of weightϕ1(α(AM;β;ω);1-ω) or ϕ1(γ(AM;β;ω);1-ω), depending on ϕ1(β;1-ω) being higher or lower than 2b. Therefore, we may have additional(48)p5=ζϕ1αAI;β;ω+ϕ3β-ω;1-ω+ϕ1αAM;β;ω;1-ω;1-ωplanes inaccessible when b≤ϕ1(β;1-ω)<2b or ϕ1(β;1-ω)=2b and ζ(β;1-ω)>0, or there may be(49)p6=ζϕ1γAI;β;ω+ϕ3β-ω;1-ω+ϕ1γAM;β;ω;1-ω;1-ωplanes inaccessible when ϕ1(β;1-ω)>2b. It is also possible that ϕ1(β;1-ω)=2b and ζ(β;1-ω)=0. In this case, ϕ1(β;1-ω) is always equal to β, so in the worst state there can be only ⌊β/b⌋=2 connections at each input (output) terminal, and each of them has weight b, or one connection of weight b≤ω≤B. Therefore, in the worst-case scenario, only connections of weight b may be considered. There are AI such input (output) terminals. At input i and output o, we have a free bandwidth of weight β-ω which may be used by ⌊β-ω/b⌋ connections of weight b. At one interstage link, there are Z connections of weight b which make a plane inaccessible for connection 〈i,o,ω〉. So,(50)p7=2·AIβ/b+β-ω/bδplanes are needed. Similarly, in the central stage, there are(51)p7′=AMβ/bδinaccessible planes. In a particular case, δ=2 and we have the same formula as these from Case 2. In the worst state, one more plane is needed to set up connection 〈i,o,ω〉. So, finally, the number of planes needed for other values of 1-ω is(52)p≥2·p1+x·p1′+1,forϕ1β,1-ω<b;2·p1+p2+p3+x·p1′+p2′+p3′+p5+1,forb≤ϕ1β;1-ω<2borϕ1β;1-ω=2b,ζβ;1-ω>0;2·p1+p4+x·p1′+p4′+p6+1,forϕ1β;1-ω>2b;2·p7+x·p7′+1forϕ1β;1-ω=2b,ζβ;1-ω=0.Combining all cases together and using ψ(i), we can write(53)p≥maxb≤ω≤B2·ψAI+x·ψAM+1.In Case 2, we have(54)ψAM=AM·β/b+AI/AM·β-B/b2,but since AM>AI, we have ⌊AI/AM⌋=0. It should be noted that, for Cases 1 and 2, the given conditions are also necessary. In Case 3 and for ϕ1(β;1-ω)>2b, our conditions are also sufficient. For ϕ1(β;1-ω)≤2b, the conditions given in Theorem 2 are also necessary.
The number of planesp must be maximized through all ω and it reaches a maximum at ω=B, so putting B in the respective formulas, we obtain the conditions given in Theorem 2.


## 5. Comparison and Results

### 5.1. Examples for Discrete Bandwidth Model

In the following few examples, the worst-case scenarios in switching fabrics with different parameters are shown for the discrete bandwidth model.Example 1.
Let us consider a switching network withd=2, n=4, cI/O=3, and cM=6, and let the maximum number of channels occupied by one connection be C=2. In this example, the switching fabric requires p=3 planes to be strict-sense nonblocking. The worst state in this switching network is shown in Figure 4. The plane will be inaccessible for connection 〈i,o,2〉 if there is a node on the connecting path 〈i,o〉 which already carries connections of the total number of occupied channels greater than or equal to z(C)=5. In this example, there is also a central stage, so p1=1 plane is inaccessible by 〈i,o,2〉 (in Figure 4, it is plane 1). In the set of AI inputs, there are still Y(AI·cI/O;AM)=3 free channels and 1 free channel at input i, but these Z(C)=4 free channels cannot block a plane for 〈i,o,2〉; therefore, p2=0. There is also a central stage and Y(AM·cI/O;C)=1 free channel. So, p3=1 plane is inaccessible by the new connection (in Figure 4, it is plane 2). Similarly, at the output terminals, there are also Z(C)=4 free channels, but it is still possible to set up connection 〈i,o,2〉 and we need only one additional plane (in Figure 4, it is plane 3). Finally, p≥p1+p2+p3+1=3 planes are needed.Figure 4
The worst state in the switching network withd=2, n=4, cI/O=3, cM=6, C=2, and p=3; filled cells denote occupied channels; empty cells denote free channels.Example 2.
This time, let us consider a switching network withd=2, n=4, cI/O=4, and cM=9, and let the maximum number of channels occupied by one connection be C=3. The switching network, according to Theorem 1, requires p≥2 planes. The worst state in the switching network is shown in Figure 5. The plane will be inaccessible for connection 〈i,o,3〉 if there is a node on the connecting path 〈i,o〉 which already carries a connection of the total number of occupied channels greater than or equal to z(C)=7. We also have a central stage, so p1=1 plane is needed (in Figure 5, it is plane 1). In the set of AI, we have Y(AI·cI/O;C)=4 free channels and 1 free channel at input i. But these Z(C)=5 channels cannot block a plane for 〈i,o,3〉 and p2=0. In the central stage, there is Y(AM·cI/O;C)=1 free channel, but, together with Z(C)=5 channels, the 6 mentioned channels (5 + 1) cannot block a plane for connection 〈i,o,3〉; therefore, p3=0. Similarly, at the output terminals, there are Z(C)=5 free channels and it is still possible to set up a new connection in the same plane with them. So, we only need one additional plane (in Figure 5, it is plane 2). Finally, p≥p1+p2+p3+1=2 planes are needed.Figure 5
The worst state in the switching network withd=2, n=4, cI/O=4, cM=9, C=3, and p=2; filled cells denote occupied channels; empty cells denote free channels.Example 3.
Let us consider a switching network with parametersd=2, n=6, cI/O=3, and cM=12, and let the maximum number of channels occupied by one connection be C=3. In this example, the switching fabric contains 3 planes. The worst state in the switching network is shown in Figure 6. The plane will be again inaccessible for connection 〈i,o,3〉 if there is a node on the connecting path 〈i,o〉 which already carries a connection of the total number of occupied channels greater than or equal to z(C)=10. There is also a central stage and p1=1 plane is inaccessible by 〈i,o,3〉 (in Figure 6, it is plane 1). We have the set of AI inputs and there are still Y(AI·cI/O;C)=9 free channels. In this example, there are no free channels at input i and output o, so Z(C) is also equal to 9 and these free channels cannot block a plane for 〈i,o,3〉; therefore, p2=0. In the central stage, there are Y(AI·cI/O;C)=2 free channels. So, p3=1 plane is inaccessible by the new connection (in Figure 6, it is plane 2). At the input terminal, there is now only one free channel and it will not block a plane for the next connection. At the output terminals, there are Z(C)=9 free channels, but it is still possible to set up connection 〈i,o,3〉 and we only need one additional plane (in Figure 6, it is plane 3). Finally, p≥p1+p2+p3+1=3 planes are needed.Figure 6
The worst state in the switching network withd=2, n=6, cI/O=3, cM=12, C=3, and p=3; filled cells denote occupied channels; empty cells denote free channels.


### 5.2. Examples for Continuous Bandwidth Model

In the following few examples, the worst-case scenarios in switching fabrics with different parameters are shown for the continuous bandwidth model.Example 1.
Let us consider a switching network withd=2, n=6, and β=0.5, and let connection weights be between b=0.4 and B=0.5. In this example, the nonblocking conditions are determined by Case 2, because 1-2b<B≤1/2 and 1/4<b<1/2. This switching network contains 5 planes. The worst state in the switching network is shown in Figure 7. A plane will be inaccessible for connection 〈i,o,0.5〉 if there is a node on the connecting path 〈i,o〉 which already carries connections of the total weight higher than 0.5. Two such connections can be set up in two input terminals. In both of these input terminals, there is still a free bandwidth of weight lower than 0.4 and it cannot be used by the next connection in this link. In both input terminal i and output terminal o, there is no free bandwidth, because connection 〈i,o,0.5〉 occupies the whole link capacity. Therefore, there are p1=2 planes inaccessible by connection 〈i,o,0.5〉 (in Figure 7, these are planes 1 and 2). In this case, there is also a central stage. Similarly, there are p2=2 additional inaccessible planes (in Figure 7, these are planes 3 and 4). But in the worst state, one more plane is needed to set up connection 〈i,o,0.5〉 (in Figure 7, this is plane 5). So, finally, we need p≥p1+p2+1=5 planes.Figure 7
The worst state in the switching network withd=2, n=6, β=0.5, B=0.5, b=0.4, and p=5.Example 2.
Let us this time consider a switching network withd=2, n=5, and β=0.75, and let connection weights be between b=0.2 and B=0.4. In this example, the nonblocking conditions are determined by Case 3, because B has a different value and ϕ1(β;1-B)<b. The switching network, according to Theorem 2, contains p≥7 planes. The worst state in the switching network is shown in Figure 8. The plane will be inaccessible for connection 〈i,o,0.4〉 if there is a node on the connecting path 〈i,o〉 which already carries a set of connections of the weight higher than 0.6. One such set of connections can be set up in one input terminal. In this input terminal, there is free bandwidth of weight lower than 0.2 (because ϕ1(0.75;0.6)=0) and it cannot be used by a new connection in this link. Therefore, p1=3 planes will be inaccessible by connection 〈i,o,0.4〉 (in Figure 8, these are planes 1, 2, and 3). The same situation occurs at the output terminals (in Figure 8, these are planes 4, 5, and 6). In this example, there is no central stage and ϕ1(β;1-B)<b, so there are no other unconsidered terminals, except terminals i and o. In both of them, it is possible to set up a connection of weight 0.2, but the plane will be still accessible for connection 〈i,o,0.4〉. Thus, one additional plane is needed (in Figure 8, this is plane 7). Finally, there are p≥2p1+1=7 planes.Figure 8
The worst state in the switching network withd=2, n=5, β=0.75, B=0.4, b=0.2, and p=7.Example 3.
In this example, we consider a switching network withd=2, n=5, and β=1.00, and the connection weights are between b=0.2 and B=0.75. The nonblocking conditions are determined by Case 3, because B has different values and b≤ϕ1(β;1-B)<2b. This switching network contains 23 planes. The worst state is shown in Figure 9. The plane will be inaccessible for connection 〈i,o,0.75〉 if there is a node on the connecting path 〈i,o〉 which already carries a set of connections of the total weight greater than 0.25. Three such sets of connections can be set up in one input terminal, so p1=9 (in Figure 9, these are planes from 1 to 9). In one of these input terminals, there is a free bandwidth of weight higher than 0.2 (because ϕ1(1.00;0.25)=0.25) and it can be used by the next connection in this link. However, this bandwidth from one link cannot block connection 〈i,o,0.75〉, but ϕ2(β;1-B)+1=2 such connections can make a plane inaccessible to a new connection. So, there is another p2=1 inaccessible plane (in Figure 9, this is plane 10). But there is free bandwidth α(AI;β;B)=0.25 at the input terminals not considered in p2. We also have some free bandwidth ϕ3(β-B)=0.25 at input terminal i, so p3=1 plane will be inaccessible for connection 〈i,o,0.75〉 (in Figure 9, this is plane 11). The same situation occurs at the output terminals (in Figure 9, these are planes from 12 to 22). In this example, there is no central stage, so, in the worst state, one more plane is needed (in Figure 9, this is plane 23). So, finally, there are p≥2(p1+p2+p3)+1=23 planes.Figure 9
The worst state in the switching network withd=2, n=5, β=1.00, B=0.3, b=0.2, and p=23.


### 5.3. Comparison and Results for Continuous Bandwidth Model

In Tables1–3, we compared our results with the sufficient conditions proposed in [25], where T2 means Theorem 2. In these tables, when n grows, the number of the required planes also grows, but, in the cases for d=2, our results are better than or equal to those in [25]. For any case, except for Case 3 when ϕ1(β;1-B)>2b and d≥3, our results show that fewer planes are required than in [25].Table 1
Number of planesp for b=0.2, B=0.4, and β=0.75 (Case  3 for ϕ1(β;1-B)<b).
n d = 2 d = 3 d = 4 d=5 [25] T2 [25] T2 [25] T2 [25] T2 3 3 3 7 5 9 7 11 9 4 6 5 14 11 24 19 36 29 5 9 7 21 17 39 31 61 49 6 14 11 44 35 99 79 186 149 7 19 15 67 53 159 127 311 249 8 29 23 134 107 399 319 936 749Table 2
Number of planesp for b=0.2, B=0.75, and β=1.00 (Case  3 for b≤ϕ1(β;1-B)<2b).
n d = 2 d = 3 d = 4 d=5 [25] T2 [25] T2 [25] T2 [25] T2 3 9 9 17 15 25 23 33 29 4 17 16 41 36 73 65 113 99 5 25 23 65 57 121 107 193 169 6 41 37 137 120 313 275 593 519 7 57 51 209 183 505 443 993 869 8 89 79 425 372 1273 1115 2993 2619Table 3
Number of planesp for b=0.2, B=0.5, and β=1.00 (Case  3 for ϕ1(β;1-B)>2b).
n d = 2 d = 3 d = 4 d=5 [25] T2 [25] T2 [25] T2 [25] T2 3 5 5 9 9 13 13 17 17 4 9 9 21 21 37 37 57 57 5 13 13 33 33 61 61 97 97 6 21 21 69 69 157 157 297 297 7 29 29 105 105 253 253 497 497 8 45 45 213 213 637 637 1497 1497In Table4, the number of planes for different d is compared when n=5, b=0.2, and β=1.00. In this table, we have Cases 1 and 3. As it can be seen from this table, for Case 3 for ϕ1(β;1-B)<b, we always get a better result than the ones given in [25]. For Case 3, for b≤ϕ1(β;1-B)<2b and for ϕ1(β;1-B)=2b and ζ(β;1-B)>0 when d>2, we always get better results too. In Case 3, for ϕ1(β;1-B)>2b, our results are in the upper bound and they are the same as those proposed in [25].Table 4
Number of planesp for n=5, b=0.2, and β=1.00 (c1: Case  1; c3a: Case  3 for ϕ1(β;1-B)<b; c3b: Case  3 for b≤ϕ1(β;1-B)<2b or for ϕ1(β;1-B)=2b and ζ(β;1-B)>0; c3c: Case  3 for ϕ1(β;1-B)>2b).
B d = 2 d = 3 d = 4 d=5 [25] T2 [25] T2 [25] T2 [25] T2 0.25 9 9 c3b 23 21 c3b 41 39 c3b 65 61 c3b 0.30 11 9 c3b 25 23 c3b 45 41 c3b 71 65 c3b 0.35 11 11 c3b 27 25 c3b 49 47 c3b 75 73 c3b 0.40 11 11 c3b 29 25 c3b 51 47 c3b 81 73 c3b 0.45 13 13 c3c 31 31 c3c 57 57 c3c 89 89 c3c 0.50 13 13 c3c 33 33 c3c 61 61 c3c 97 97 c3c 0.55 15 13 c3a 37 33 c3a 69 61 c3a 109 97 c3a 0.60 17 13 c3a 41 33 c3a 77 61 c3a 121 97 c3a 0.65 19 17 c3b 47 41 c3b 87 77 c3b 139 121 c3b 0.70 21 19 c3a 55 49 c3a 101 91 c3a 161 145 c3a 0.75 25 23 c3b 65 57 c3b 121 107 c3b 193 169 c3b 0.80 33 31 c3a 83 81 c3a 153 151 c3a 243 241 c3a 0.85 31 31 c1 81 81 c1 151 151 c1 241 241 c1 0.90 31 31 c1 81 81 c1 151 151 c1 241 241 c1 0.95 31 31 c1 81 81 c1 151 151 c1 241 241 c1 1.00 31 31 c1 81 81 c1 151 151 c1 241 241 c1In Tables5 and 6, switching networks for Case 2 are compared. As it can be seen from Table 5, for Case 2, our results are better than the ones given in [25]. In Table 6, for Cases 2 and 3, for ϕ1(β;1-B)=2b and ζ(β;1-B)>0, we always get better results than in [25]. In other cases in these tables (it is always Case 3 for ϕ1(β;1-B)>2b), our results are in the upper bound; however, they are not worse than the ones proposed in [25].Table 5
Number of planesp for n=6, B=0.50, and β=0.50 (c2: Case  2 for 1-2b≤B<1/2 and 1/4<b<1/2 or for ϕ1(β;1-B)=2b and ζ(β;1-B)=0; c3c: Case  3 for ϕ1(β;1-B)>2b).
B d = 2 d = 3 d = 4 d=5 [25] T2 [25] T2 [25] T2 [25] T2 0.05 9 9 c3c 33 33 c3c 77 77 c3c 147 147 c3c 0.10 9 9 c3c 33 33 c3c 77 77 c3c 147 147 c3c 0.15 9 9 c3c 33 33 c3c 77 77 c3c 147 147 c3c 0.20 9 9 c3c 33 33 c3c 77 77 c3c 147 147 c3c 0.25 9 7 c2 33 23 c2 77 53 c2 147 99 c2 0.30 9 5 c2 33 18 c2 77 39 c2 147 75 c2 0.35 9 5 c2 33 18 c2 77 39 c2 147 75 c2 0.40 9 5 c2 33 18 c2 77 39 c2 147 75 c2 0.45 9 5 c2 33 18 c2 77 39 c2 147 75 c2Table 6
Number of planesp for n=6, B=0.50, and β=1.00 (c2: Case  2; c3b: Case  3 for ϕ1(β;1-B)=2b and ζ(β;1-B)>0; c3c: Case  3 for ϕ1(β;1-B)>2b).
b d = 2 d = 3 d = 4 d=5 [25] T2 [25] T2 [25] T2 [25] T2 0.05 21 21 c3c 69 69 c3c 157 157 c3c 297 297 c3c 0.10 21 21 c3c 69 69 c3c 157 157 c3c 297 297 c3c 0.15 21 21 c3c 69 69 c3c 157 157 c3c 297 297 c3c 0.20 21 21 c3c 69 69 c3c 157 157 c3c 297 297 c3c 0.25 21 17 c3b 69 52 c3b 157 119 c3b 297 223 c3b 0.30 21 17 c2 69 52 c2 157 119 c2 297 223 c2 0.35 21 17 c2 69 52 c2 157 119 c2 297 223 c2 0.40 21 17 c2 69 52 c2 157 119 c2 297 223 c2 0.45 21 17 c2 69 52 c2 157 119 c2 297 223 c2


## 5.1. Examples for Discrete Bandwidth Model

In the following few examples, the worst-case scenarios in switching fabrics with different parameters are shown for the discrete bandwidth model.Example 1.
Let us consider a switching network withd=2, n=4, cI/O=3, and cM=6, and let the maximum number of channels occupied by one connection be C=2. In this example, the switching fabric requires p=3 planes to be strict-sense nonblocking. The worst state in this switching network is shown in Figure 4. The plane will be inaccessible for connection 〈i,o,2〉 if there is a node on the connecting path 〈i,o〉 which already carries connections of the total number of occupied channels greater than or equal to z(C)=5. In this example, there is also a central stage, so p1=1 plane is inaccessible by 〈i,o,2〉 (in Figure 4, it is plane 1). In the set of AI inputs, there are still Y(AI·cI/O;AM)=3 free channels and 1 free channel at input i, but these Z(C)=4 free channels cannot block a plane for 〈i,o,2〉; therefore, p2=0. There is also a central stage and Y(AM·cI/O;C)=1 free channel. So, p3=1 plane is inaccessible by the new connection (in Figure 4, it is plane 2). Similarly, at the output terminals, there are also Z(C)=4 free channels, but it is still possible to set up connection 〈i,o,2〉 and we need only one additional plane (in Figure 4, it is plane 3). Finally, p≥p1+p2+p3+1=3 planes are needed.Figure 4
The worst state in the switching network withd=2, n=4, cI/O=3, cM=6, C=2, and p=3; filled cells denote occupied channels; empty cells denote free channels.Example 2.
This time, let us consider a switching network withd=2, n=4, cI/O=4, and cM=9, and let the maximum number of channels occupied by one connection be C=3. The switching network, according to Theorem 1, requires p≥2 planes. The worst state in the switching network is shown in Figure 5. The plane will be inaccessible for connection 〈i,o,3〉 if there is a node on the connecting path 〈i,o〉 which already carries a connection of the total number of occupied channels greater than or equal to z(C)=7. We also have a central stage, so p1=1 plane is needed (in Figure 5, it is plane 1). In the set of AI, we have Y(AI·cI/O;C)=4 free channels and 1 free channel at input i. But these Z(C)=5 channels cannot block a plane for 〈i,o,3〉 and p2=0. In the central stage, there is Y(AM·cI/O;C)=1 free channel, but, together with Z(C)=5 channels, the 6 mentioned channels (5 + 1) cannot block a plane for connection 〈i,o,3〉; therefore, p3=0. Similarly, at the output terminals, there are Z(C)=5 free channels and it is still possible to set up a new connection in the same plane with them. So, we only need one additional plane (in Figure 5, it is plane 2). Finally, p≥p1+p2+p3+1=2 planes are needed.Figure 5
The worst state in the switching network withd=2, n=4, cI/O=4, cM=9, C=3, and p=2; filled cells denote occupied channels; empty cells denote free channels.Example 3.
Let us consider a switching network with parametersd=2, n=6, cI/O=3, and cM=12, and let the maximum number of channels occupied by one connection be C=3. In this example, the switching fabric contains 3 planes. The worst state in the switching network is shown in Figure 6. The plane will be again inaccessible for connection 〈i,o,3〉 if there is a node on the connecting path 〈i,o〉 which already carries a connection of the total number of occupied channels greater than or equal to z(C)=10. There is also a central stage and p1=1 plane is inaccessible by 〈i,o,3〉 (in Figure 6, it is plane 1). We have the set of AI inputs and there are still Y(AI·cI/O;C)=9 free channels. In this example, there are no free channels at input i and output o, so Z(C) is also equal to 9 and these free channels cannot block a plane for 〈i,o,3〉; therefore, p2=0. In the central stage, there are Y(AI·cI/O;C)=2 free channels. So, p3=1 plane is inaccessible by the new connection (in Figure 6, it is plane 2). At the input terminal, there is now only one free channel and it will not block a plane for the next connection. At the output terminals, there are Z(C)=9 free channels, but it is still possible to set up connection 〈i,o,3〉 and we only need one additional plane (in Figure 6, it is plane 3). Finally, p≥p1+p2+p3+1=3 planes are needed.Figure 6
The worst state in the switching network withd=2, n=6, cI/O=3, cM=12, C=3, and p=3; filled cells denote occupied channels; empty cells denote free channels.


## 5.2. Examples for Continuous Bandwidth Model

In the following few examples, the worst-case scenarios in switching fabrics with different parameters are shown for the continuous bandwidth model.Example 1.
Let us consider a switching network withd=2, n=6, and β=0.5, and let connection weights be between b=0.4 and B=0.5. In this example, the nonblocking conditions are determined by Case 2, because 1-2b<B≤1/2 and 1/4<b<1/2. This switching network contains 5 planes. The worst state in the switching network is shown in Figure 7. A plane will be inaccessible for connection 〈i,o,0.5〉 if there is a node on the connecting path 〈i,o〉 which already carries connections of the total weight higher than 0.5. Two such connections can be set up in two input terminals. In both of these input terminals, there is still a free bandwidth of weight lower than 0.4 and it cannot be used by the next connection in this link. In both input terminal i and output terminal o, there is no free bandwidth, because connection 〈i,o,0.5〉 occupies the whole link capacity. Therefore, there are p1=2 planes inaccessible by connection 〈i,o,0.5〉 (in Figure 7, these are planes 1 and 2). In this case, there is also a central stage. Similarly, there are p2=2 additional inaccessible planes (in Figure 7, these are planes 3 and 4). But in the worst state, one more plane is needed to set up connection 〈i,o,0.5〉 (in Figure 7, this is plane 5). So, finally, we need p≥p1+p2+1=5 planes.Figure 7
The worst state in the switching network withd=2, n=6, β=0.5, B=0.5, b=0.4, and p=5.Example 2.
Let us this time consider a switching network withd=2, n=5, and β=0.75, and let connection weights be between b=0.2 and B=0.4. In this example, the nonblocking conditions are determined by Case 3, because B has a different value and ϕ1(β;1-B)<b. The switching network, according to Theorem 2, contains p≥7 planes. The worst state in the switching network is shown in Figure 8. The plane will be inaccessible for connection 〈i,o,0.4〉 if there is a node on the connecting path 〈i,o〉 which already carries a set of connections of the weight higher than 0.6. One such set of connections can be set up in one input terminal. In this input terminal, there is free bandwidth of weight lower than 0.2 (because ϕ1(0.75;0.6)=0) and it cannot be used by a new connection in this link. Therefore, p1=3 planes will be inaccessible by connection 〈i,o,0.4〉 (in Figure 8, these are planes 1, 2, and 3). The same situation occurs at the output terminals (in Figure 8, these are planes 4, 5, and 6). In this example, there is no central stage and ϕ1(β;1-B)<b, so there are no other unconsidered terminals, except terminals i and o. In both of them, it is possible to set up a connection of weight 0.2, but the plane will be still accessible for connection 〈i,o,0.4〉. Thus, one additional plane is needed (in Figure 8, this is plane 7). Finally, there are p≥2p1+1=7 planes.Figure 8
The worst state in the switching network withd=2, n=5, β=0.75, B=0.4, b=0.2, and p=7.Example 3.
In this example, we consider a switching network withd=2, n=5, and β=1.00, and the connection weights are between b=0.2 and B=0.75. The nonblocking conditions are determined by Case 3, because B has different values and b≤ϕ1(β;1-B)<2b. This switching network contains 23 planes. The worst state is shown in Figure 9. The plane will be inaccessible for connection 〈i,o,0.75〉 if there is a node on the connecting path 〈i,o〉 which already carries a set of connections of the total weight greater than 0.25. Three such sets of connections can be set up in one input terminal, so p1=9 (in Figure 9, these are planes from 1 to 9). In one of these input terminals, there is a free bandwidth of weight higher than 0.2 (because ϕ1(1.00;0.25)=0.25) and it can be used by the next connection in this link. However, this bandwidth from one link cannot block connection 〈i,o,0.75〉, but ϕ2(β;1-B)+1=2 such connections can make a plane inaccessible to a new connection. So, there is another p2=1 inaccessible plane (in Figure 9, this is plane 10). But there is free bandwidth α(AI;β;B)=0.25 at the input terminals not considered in p2. We also have some free bandwidth ϕ3(β-B)=0.25 at input terminal i, so p3=1 plane will be inaccessible for connection 〈i,o,0.75〉 (in Figure 9, this is plane 11). The same situation occurs at the output terminals (in Figure 9, these are planes from 12 to 22). In this example, there is no central stage, so, in the worst state, one more plane is needed (in Figure 9, this is plane 23). So, finally, there are p≥2(p1+p2+p3)+1=23 planes.Figure 9
The worst state in the switching network withd=2, n=5, β=1.00, B=0.3, b=0.2, and p=23.


## 5.3. Comparison and Results for Continuous Bandwidth Model

In Tables1–3, we compared our results with the sufficient conditions proposed in [25], where T2 means Theorem 2. In these tables, when n grows, the number of the required planes also grows, but, in the cases for d=2, our results are better than or equal to those in [25]. For any case, except for Case 3 when ϕ1(β;1-B)>2b and d≥3, our results show that fewer planes are required than in [25].Table 1
Number of planesp for b=0.2, B=0.4, and β=0.75 (Case  3 for ϕ1(β;1-B)<b).
n d = 2 d = 3 d = 4 d=5 [25] T2 [25] T2 [25] T2 [25] T2 3 3 3 7 5 9 7 11 9 4 6 5 14 11 24 19 36 29 5 9 7 21 17 39 31 61 49 6 14 11 44 35 99 79 186 149 7 19 15 67 53 159 127 311 249 8 29 23 134 107 399 319 936 749Table 2
Number of planesp for b=0.2, B=0.75, and β=1.00 (Case  3 for b≤ϕ1(β;1-B)<2b).
n d = 2 d = 3 d = 4 d=5 [25] T2 [25] T2 [25] T2 [25] T2 3 9 9 17 15 25 23 33 29 4 17 16 41 36 73 65 113 99 5 25 23 65 57 121 107 193 169 6 41 37 137 120 313 275 593 519 7 57 51 209 183 505 443 993 869 8 89 79 425 372 1273 1115 2993 2619Table 3
Number of planesp for b=0.2, B=0.5, and β=1.00 (Case  3 for ϕ1(β;1-B)>2b).
n d = 2 d = 3 d = 4 d=5 [25] T2 [25] T2 [25] T2 [25] T2 3 5 5 9 9 13 13 17 17 4 9 9 21 21 37 37 57 57 5 13 13 33 33 61 61 97 97 6 21 21 69 69 157 157 297 297 7 29 29 105 105 253 253 497 497 8 45 45 213 213 637 637 1497 1497In Table4, the number of planes for different d is compared when n=5, b=0.2, and β=1.00. In this table, we have Cases 1 and 3. As it can be seen from this table, for Case 3 for ϕ1(β;1-B)<b, we always get a better result than the ones given in [25]. For Case 3, for b≤ϕ1(β;1-B)<2b and for ϕ1(β;1-B)=2b and ζ(β;1-B)>0 when d>2, we always get better results too. In Case 3, for ϕ1(β;1-B)>2b, our results are in the upper bound and they are the same as those proposed in [25].Table 4
Number of planesp for n=5, b=0.2, and β=1.00 (c1: Case  1; c3a: Case  3 for ϕ1(β;1-B)<b; c3b: Case  3 for b≤ϕ1(β;1-B)<2b or for ϕ1(β;1-B)=2b and ζ(β;1-B)>0; c3c: Case  3 for ϕ1(β;1-B)>2b).
B d = 2 d = 3 d = 4 d=5 [25] T2 [25] T2 [25] T2 [25] T2 0.25 9 9 c3b 23 21 c3b 41 39 c3b 65 61 c3b 0.30 11 9 c3b 25 23 c3b 45 41 c3b 71 65 c3b 0.35 11 11 c3b 27 25 c3b 49 47 c3b 75 73 c3b 0.40 11 11 c3b 29 25 c3b 51 47 c3b 81 73 c3b 0.45 13 13 c3c 31 31 c3c 57 57 c3c 89 89 c3c 0.50 13 13 c3c 33 33 c3c 61 61 c3c 97 97 c3c 0.55 15 13 c3a 37 33 c3a 69 61 c3a 109 97 c3a 0.60 17 13 c3a 41 33 c3a 77 61 c3a 121 97 c3a 0.65 19 17 c3b 47 41 c3b 87 77 c3b 139 121 c3b 0.70 21 19 c3a 55 49 c3a 101 91 c3a 161 145 c3a 0.75 25 23 c3b 65 57 c3b 121 107 c3b 193 169 c3b 0.80 33 31 c3a 83 81 c3a 153 151 c3a 243 241 c3a 0.85 31 31 c1 81 81 c1 151 151 c1 241 241 c1 0.90 31 31 c1 81 81 c1 151 151 c1 241 241 c1 0.95 31 31 c1 81 81 c1 151 151 c1 241 241 c1 1.00 31 31 c1 81 81 c1 151 151 c1 241 241 c1In Tables5 and 6, switching networks for Case 2 are compared. As it can be seen from Table 5, for Case 2, our results are better than the ones given in [25]. In Table 6, for Cases 2 and 3, for ϕ1(β;1-B)=2b and ζ(β;1-B)>0, we always get better results than in [25]. In other cases in these tables (it is always Case 3 for ϕ1(β;1-B)>2b), our results are in the upper bound; however, they are not worse than the ones proposed in [25].Table 5
Number of planesp for n=6, B=0.50, and β=0.50 (c2: Case  2 for 1-2b≤B<1/2 and 1/4<b<1/2 or for ϕ1(β;1-B)=2b and ζ(β;1-B)=0; c3c: Case  3 for ϕ1(β;1-B)>2b).
B d = 2 d = 3 d = 4 d=5 [25] T2 [25] T2 [25] T2 [25] T2 0.05 9 9 c3c 33 33 c3c 77 77 c3c 147 147 c3c 0.10 9 9 c3c 33 33 c3c 77 77 c3c 147 147 c3c 0.15 9 9 c3c 33 33 c3c 77 77 c3c 147 147 c3c 0.20 9 9 c3c 33 33 c3c 77 77 c3c 147 147 c3c 0.25 9 7 c2 33 23 c2 77 53 c2 147 99 c2 0.30 9 5 c2 33 18 c2 77 39 c2 147 75 c2 0.35 9 5 c2 33 18 c2 77 39 c2 147 75 c2 0.40 9 5 c2 33 18 c2 77 39 c2 147 75 c2 0.45 9 5 c2 33 18 c2 77 39 c2 147 75 c2Table 6
Number of planesp for n=6, B=0.50, and β=1.00 (c2: Case  2; c3b: Case  3 for ϕ1(β;1-B)=2b and ζ(β;1-B)>0; c3c: Case  3 for ϕ1(β;1-B)>2b).
b d = 2 d = 3 d = 4 d=5 [25] T2 [25] T2 [25] T2 [25] T2 0.05 21 21 c3c 69 69 c3c 157 157 c3c 297 297 c3c 0.10 21 21 c3c 69 69 c3c 157 157 c3c 297 297 c3c 0.15 21 21 c3c 69 69 c3c 157 157 c3c 297 297 c3c 0.20 21 21 c3c 69 69 c3c 157 157 c3c 297 297 c3c 0.25 21 17 c3b 69 52 c3b 157 119 c3b 297 223 c3b 0.30 21 17 c2 69 52 c2 157 119 c2 297 223 c2 0.35 21 17 c2 69 52 c2 157 119 c2 297 223 c2 0.40 21 17 c2 69 52 c2 157 119 c2 297 223 c2 0.45 21 17 c2 69 52 c2 157 119 c2 297 223 c2


## 6. Conclusions

In this paper, we investigated the nonblocking behavior of multiratelogd(N,0,p) switching networks. In the discrete bandwidth model, we extended the conditions proposed in [25] and we showed numerical examples for this model too. In the continuous bandwidth model, we have proved that, for B+b≤1, fewer planes are needed for the multirate logd(N,0,p) switching network to be nonblocking in the strict sense than it was previously known. The results that we obtained have been compared in Tables 1–6. We also showed a few numerical examples for the continuous bandwidth case. For 1-b<B≤β, our results confirm those known earlier. Although, in the proof of Theorem 2, only the sufficient conditions were considered, it should be noted that, for Cases 1, 2, and 3 with ϕ1(β,1-ω)≤2b, they are also necessary conditions. This means that we can show the blocking state in the switching network composed of fewer planes than it was given in Theorem 2. For Case 3 with ϕ1(β,1-ω)>2b, our result constitutes the upper bound.Presented multirate switching networks can be used, for example, in data centers or in 4G/5G networks where bandwidth is a crucial aspect. The discrete model allows describing the behavior of a multiservice system where each service could require different basic bandwidth units (channels). In case where bandwidth could have any fraction of an available bandwidth, this means that some services could use any size of a bandwidth and the continuous model is then used.The nonblocking operation oflogd(N,m,p) switching networks is currently under study.



---

*Source: 1575828-2017-02-07.xml*