The Klose network (sometimes the Klos network ) is a type of multi-stage (in other terminology, multi-tier [1] ) switching network , first formally described by Charles Klose in 1953 [2] . Such a network is a theoretical version of a practical multi-stage telephone switching system.
Content
General Description
The Klose network has three cascades (tiers): an input cascade, an intermediate (middle) cascade, and an output cascade. Each cascade consists of a number of cross-switches - the so-called. “Crossbar”, or, in other terminology, switching elements (CE) [3] [4] , as shown in the figure below.
Each call (connection request) gets to the incoming FE, after which it can be routed through any available mid-tier FE to the corresponding outgoing FE. In this case, the mid-tier FE is available for a new call if both the line connecting it to the incoming FE and the line connecting it to the outgoing FE are free.
A key advantage of Klose networks is that they have a much smaller number of switching points compared to a cross-switch. In practical terms, the Klose network was very profitable for implementation in electromechanical telephone exchanges, but with the advent of VLSI, its value decreased, although its principles were also used in digital fast packet switches, for example, in the NEC ATOM switch [5] [6] .
Klose network drawing from an English article
Klose's network is defined by three integers n , m , and r . The number n is equal to the number of lines connected to each of the r FE of the incoming cascade. Each FE of the input stage has m outputs, and the middle stage also contains m FE. Thus, the dimension of the FE of the incoming cascade will be n x m , i.e., n inputs and m outputs. There is strictly one connection between each FE of the incoming cascade and each FE of the middle cascade, the same is true for the connections of the middle cascade with the outgoing cascade. The outgoing (third) cascade contains r QEs, each of which has dimension m x n .
Block Chances
The closure probabilities of the Klose network are determined by the relative values of m and n .
Klose's strictly non-blocking networks ( m ≥ 2 n - 1) - original Klose layout of 1953
If m ≥ 2 n - 1, then the Clos network is strictly non-blocking in the sense that the free input of the incoming FE can always be connected to the free output of the outgoing CE without the need to reconnect existing connections. This conclusion forms the basis of the classic article by Claus 1953 . Suppose that there is a free line on an incoming FE, which should be connected to a free line on a specific outgoing FE. In the worst case, an incoming QE is already serving an n - 1 connection, the same can be said for an outgoing QE, that is, it is serving an n - 1 connection. Suppose also for the worst case that each of these compounds passes through an excellent CE of the middle tier. Therefore, in the worst case, 2 n - 2 CEs of the middle tier are not able to establish a new connection. Thus, in order for the Klose network to be strictly non-blocking, one more CE of the middle tier is required, and their total number should be 2 n - 1.
Klose networks that are non-blocking during switching ( m ≥ n )
If m ≥ n , then the Klose network is called “non-blocking upon switching”. This means that the free port of the input FE can always be connected to the free port of the output FE, but for this, it may be necessary to reconnect existing connections by installing them through other FEs of the central (middle) cascade of the Clos network [7] .
To prove this point, it is enough to consider the case with m = n , when the Clos network is fully involved, that is, r × n connections are served. The proof shows how any permutation of r × n input lines for r × n output lines can be divided into smaller permutations, each of which can be implemented by a separate FE in the Clos network, where m = n .
The proof uses Hall's theorem [8] , called the “marriage theorem”, because of its clarification with the involvement of “boys” and “girls”. So, it is assumed that there are r boys and r girls. The theorem establishes that if in a subset of k boys (for each k , so 0 ≤ k ≤ r ) each boy is familiar with k or more girls, then each boy can marry a girl with whom he is familiar. It is clear that this is a necessary condition for a wedding to take place, and, surprisingly, this is enough.
In the context of the Klose network, each boy is an incoming QE, and each girl is an outgoing QE. It is said that the boy is familiar with the girl in the case when the inbound and outbound QEs serve the same connection. Each set of k boys must be familiar with at least k girls, because k incoming QEs serve k × n connections, and their service requires at least k outgoing QEs. From here, each inbound QE will be paired with an outbound QE that serves the same one-to-one connection. These r connections can be served by one mid-tier FE. If we now remove this CE of the middle tier from the Clos network, then m decreases by 1, and we have a smaller Clos network. Then the process is repeated again until m becomes equal to 1, and each connection will be served by the CE of the middle stage.
Blocking Probabilities - Lee and Jacobus Approximations
Real telephone switching systems are rarely strictly non-blocking due to the high cost of their implementation; they usually have a low probability of blocking, which can be calculated using the Lee or Jacobeus approximations [9] provided that the existing connections are not switched over. In this case, the potential number of other active connections in each input or output switch will be u = n - 1.
In the Lee approximation, it is assumed that each inner line between the cascades is already occupied by a compound with probability p , and that this line is completely independent of other lines. In this case, the probability of blocking will be overestimated, especially for small r . The probability that this extension is busy is p = uq / m , where q is equal to the probability of busy incoming or outgoing lines. Conversely, the probability that the line is free is 1 - p . The probability that the path connecting the incoming QE to the outgoing QE through the QE of the middle tier is free is equal to the probability that both lines are free, namely (1 - p ) 2 . Consequently, the probability of its inaccessibility will be 1 - (1 - p ) 2 . The blocking probability, or the probability that there are no such free paths, will then be [1 - (1 - p ) 2 ] m .
The Jacobeus approximation is more accurate, and in order to show how it is displayed, we assume that the CE of the middle cascade already serves a certain number of calls. This reflects the fact that only the “relative” configurations of incoming and outgoing QEs matter. There are i connections entering the network through the same incoming QE, and free lines must be allocated for their maintenance, and there are j connections leaving the Klose network through the same outgoing QE, and their maintenance also requires lines. Therefore, 0 ≤ i ≤ u , and 0 ≤ j ≤ u .
Let A be equal to the number of switching methods for j connections proceeding to m FE of the middle tier. Let B be equal to the number of these switching methods, which is expressed in blocking. This is equal to the number of cases in which the remaining m - j CEs of the middle cascade coincide with m - j from i incoming compounds, which is the number of subsets containing m - j from these compounds. Then the probability of blocking will be:
- {\ displaystyle \ beta _ {ij} = {\ frac {B} {A}} = {\ frac {\ left ({\ begin {array} {c} i \\ mj \ end {array}} \ right) } {\ left ({\ begin {array} {c} m \\ j \ end {array}} \ right)}} = {\ frac {i! j!} {(i + jm)! m!}} }
If f i is the probability that i of other connections are already served by an incoming QE, and g j is equal to the probability that j of other connections are already served by an outgoing QE, then the total probability of blocking will be:
It can be calculated using the values of f i and g j , each of which has a binomial distribution. After algebraic transformations, the probability of blocking can be expressed as:
Klose networks with more than three cascades
Klose's network can be built from any number of odd cascades. By replacing each FE of the central tier with a 3-stage Clos network, we obtain a 5-stage Clos network. By repeating this process, you can get Clos networks, consisting of 7, 9, 11 and so on cascades.
Benes Network ( m = n = 2)
A network of this type, non-blocking during re-switching, where m = n = 2, is generally called a “ Benes network”, and even those networks that were analyzed and discussed before it. The number of inputs and outputs of such a network is N = r × n = 2 r . Such networks have cascades, each of which consists of N / 2 FE 2 × 2. The following is a 8 × 8 Benes network (that is, where N = 8); she has 5 cascades, each of which contains N / 2 = 4 FE 2 × 2, and in total this network contains 20 FE 2 × 2. The three central cascades consist of two smaller 4 × 4 Benes networks, while in the central stage each of the 2 × 2 FEs can be considered as a 2 × 2 Benes network. In this example, the recursive component of networks of this type is visible.
Literature
- Podlazov V.S., Sokolov V.V. Generalized networks of Klose (Rus.) // Automation and Telemechanics, ed. Academic Publishing Center "Science" RAS. - 2009. - No. 10 . - S. 158-171 . - ISSN 0005-2310 .
Notes
- ↑ V. P. Vidomenko, “Klose networks 40 years later”, 2nd conference “Information Networks and Systems (KISS-93)” November 18-20, 1993, Abstracts, State. University of Telecommunications (GUT) them. prof. M. A. Bonch-Bruevich , St. Petersburg, 1993, pp. 42-44;
- ↑ Clos, Charles. A study of non-blocking switching networks (Eng.) // Bell Labs Technical Journal : journal. - 1953. - March ( vol. 32 , no. 2 ). - P. 406-424 . - ISSN 00058580 .
- ↑ Razhivin Igor. Telecommunication Explanatory Dictionary “Digital Wireline Telecommunications for Open Systems”: Digital Wireline telecommunications on Open Systems (OSI). (2003). - Covers, among other things, ATM technology. Date of treatment July 8, 2012. Archived February 4, 2012.
- ↑ A. N. Nazarov, I. A. Razzhivin, M.V. Simonov. ATM: Technical solutions for networking. - Reference edition. - M .: Hot Line - Telecom, 2001. - S. 376. - ISBN 5-93517-040-X .
- ↑ Principles of designing switches . Kunegin Sergey Vladimirovich. Date of treatment July 8, 2012. Archived on October 7, 2012.
- ↑ Output-buffer switch architecture for asynchronous transfer mode, Suzuki, H .; Nagano, H .; Suzuki, T .; Takeuchi, T .; Iwasaki, S. ICC '89, BOSTONICC. Conference record. (eng.) . IEEE Xplore, Digital Library. Date of treatment July 8, 2012. Archived on October 7, 2012.
- ↑ Václav E. Beneš, Mathematical Theory of Connecting Networks and Telephone Traffic, Academic Press , 1965.
- ↑ Philip Hall. On Representatives of Subsets ( Neopr .) // Journal of the London Mathematical Society. - 1935. - T. 10 . - S. 26-30 . - DOI : 10.1112 / jlms / s1-10.37.26 .
- ↑ Hui, JY: “Switching and Traffic Theory for Integrated Broadband Networks,” Kluwer Academic Publishers, 1990.