FI97843C - Method for switching route confirmation signals in a digital crossover - Google Patents

Description

97843

Method for switching route confirmation signals in a digital crossover switch - Förfarande for koppling av dubblerade signaler i en digital korskoppling

The invention relates to a method according to the preamble of claim 1 for configuring the cross-connection of digital signals connected to a digital time-space-time (TST) cross-connect in situations of change of cross-connect need and for route verification of such signals in a TST cross-switch. The invention also relates to a circuit arrangement implementing the method.

The synchronous digital hierarchy (SDH) comprises an extensive set for transmitting time-division signals in a telecommunications network whose backbone transmission network is evolving into a remote-controlled crossover network. The first level of SDH signals is a Synchronous Transport Module (STM-1) with a transmission rate of 155,520 Mhit / s. The basic STM-1 frame consists of bytes (8 bits), which are 2430 in the frame, including the control blocks. In this case, 63 TU 12 (Tributary Unit) 2 Mbit / s signals are transmitted in the STM-1 frame, which may contain a normal 2 Mbit / s signal for a 30-channel PCM ice system. Each byte of the frame forms a 64 kbit / s channel. SDH signals, i.e. transport modules, are formed from the signals of the subsystems by interleaving bytes.

The SDH cross switch (DXC, Digital Cross Connect) can transmit traffic between different SDH level-20s as well as switch traffic between different signals. In addition, it must be able to handle the flexible reconfiguration of the network, i.e. the rerouting of connections, and guarantee the rapid introduction of va-ray connections in the event of a network failure.

Digital cross-linking has been extensively studied to find an architecture that meets optimal conditions. A structure that satisfies the conditions of capacity, non-blocking and feasibility is a TST (Time Space Time) structure, i.e. a time-space-time cross-connection, as disclosed, for example, in our patent PCT / FI / 00174 (or the corresponding FI-921834). This patent sets out in some detail the general principles of a TST crossover. Although the method disclosed in PCT / FI / 00174 works quite well, there is a need for an even more efficient control method for switching, especially in larger cross-switches.

It is an object of the present invention to provide a method according to which an algorithm calculates the configuration of a TST switching structure both for connections between two points and for backup connections of subnetworks.

2 97843

The invention proposes a method according to claim 1, wherein the solution is aided by a new structuring of the problem, in practice 63 a switching matrix, and the method focuses on solving only the connections of the first TS stage and in addition only those signals that need to be rearranged.

Other preferred embodiments of the invention are set out in the dependent claims. Preferred solutions for the circuit arrangement implementing the method are set out in claims 9-11.

The signals to be switched are preferably multiplexed sub-signals of high speed signals, i.e. in an SDH system this means that the sub-signals are essentially 2 Mbit / s VC-12 virtual containers, with the main signals being 155 Mbit / s STM-1 signals.

In fact, the power of the algorithm can be seen in the fact that the algorithm rearranges only those connections for which rearrangement is necessary. This is accomplished in part by setting the coupling problem in a new way. In this case, the coupling problem is presented in Brochure-15 as an imaginary matrix. The algorithm keeps track of all reconfigurations made to the connections to meet the need for cross-connection. Once all the rearrangements have been made, the accounts provide all the necessary information needed to make the cross-connection based on the control information of the switches.

In the method according to the invention, difficult switching situations are solved in the recursion-20 step, in which the position of the switching in the imaginary matrix is moved randomly from the forced to a new position, after which the operation is continued according to the basic method.

The switching field of the cross-switch requires a calculation algorithm to configure the connections. Point-to-point connections, i.e. point-to-point connections, can be configured using known algorithms. Instead, the PPTST algorithm according to the invention goes a step further and also provides a solution for path protection (PP). If necessary, the PPTST algorithm also calculates point-to-point connections (general distribution).

Experiments have shown that the method according to the invention is faster or at least as fast as the known calculation methods, even when the signals to be switched include route confirmation signals.

The algorithm according to the invention can also be used to route signals between two points through a three-stage Benes switching field.

3,97843

The invention will now be described by way of example with reference to the accompanying drawings.

Figure 1 shows an overview of the imaginary matrix used as a starting point for the algorithm according to the invention.

Figure 2 illustrates the switching of route confirmation signals through the status switch.

5 Figure 3 shows an overview of the income table.

Figure 4 shows the data structure of the algorithm for the selected time interval (Time = T), in which case the auxiliary tables of the algorithm are shown around the imaginary switching matrix.

Figure 5 is a reduced flow diagram of the algorithm used in the method according to the invention.

Figure 6 shows a flow chart of the first processing step of route confirmation signals.

Figures 7a and 7b illustrate the processing of common point-to-point signals in the FindEven process.

Figure 8 shows a flow chart of the FindEven process.

Figure 9 illustrates the BestSwap process used in the shift process using switching-15 matrices.

Figure 10 shows a flow chart of the shift process.

Figure 11 illustrates the HallSwap situation of the shift process.

Figure 12 illustrates the FillerSwap situation of the shift process.

Figure 13 illustrates the BestReplace situation of the shift process.

20 Figure 14 illustrates the ReplaceSwap situation of the shift process.

Figure 15 illustrates the ReleaseSwap situation of the shift process.

Figure 16 illustrates the PPSwap situation of the shift process.

Figure 17 shows a simplified flow chart of the PPSwap process.

The following is an exemplary embodiment based on the processing of VC-12 signals. However, it should be noted that the method according to the invention can process higher class signals, whereby they are split into several 4 97843 VC-12 signals which are connected to a TST switch. The last stage of the TST switch is then used to resolve the reconnection of the higher class signal.

The invention defines a calculation algorithm for a TST cross-connect field, by means of which path protection signals (path protection or pp signals) can be determined in a digital cross-switch DXC. The calculation algorithm uses a timer function to stop execution if no solution is found for the calculation. Abbreviations are used in the following explanation: PP means the same as SNCP (Sub-network connection protection), TST means Time-Space-Time-10 switch architecture (TST, Time-Space-Time), and PPTST means route secured TST switching. DXC stands for Digital Cross Connect.

In this example, the PPTST algorithm only processes VC-12 signals (VC, Virtual Container) because the VC-4 signals and the VC-4 backup algorithms do not use a timer-15, so they do not pose problems in terms of blocking. However, the TST structure requires special processing of VC-12 signals in the case of SNCP, also referred to herein as route verification, PP. The PPTST algorithm solves the difficulties previously encountered in cross-switch configuration.

In general, the algorithm is limited only by the time factors of the TST connection itself.

20 The configuration must be calculated by a real processor, which is slow in the current state of the art, and yet must meet the requirements set by the network operator for connection times. The function of the timer function is to interrupt the counting if the time limits are exceeded.

The algorithm requires a conversion level that can also be applied to the general DXC-25 TST algorithm as well as the Game algorithm. The purpose of the conversion layer is to handle configuration requests and control needs of ASICs. The conversion layer also filters out unnecessary requests, such as VC-4 connections, because no algorithm is required to configure them. Other requests constitute a configuration problem for the VC-12 signals of the TST connection, which must be solved by the PPTST algorithm.

30 The problem with the algorithm is basically that 63 configurations for the state (S) and time (T) switches have to be found through the TST switching field. These 63 solutions correspond to the number of VC-12 signals in the same STM-1 frame. The PPTST algorithm aims to solve the main TST constraint. The connection through the state switch S must be completely unambiguous, i.e. the signal must be routed through ports that are not used by other signals. The easiest way to present this S-connection problem is with 63 matrices with a size of 16 * 16. The input port corresponds to a matrix column, and the output port corresponds to a matrix row. In this case, the structure of the algorithm can be simply described as follows: 5 The signals are represented by a matrix 63 in which the time slot distribution corresponds to the original. The algorithm rearranges the contents of these 63 matrices so that each signal uses the ports individually. Because gates refer to rows and columns, the constraint can be expressed in the form: the signal should use a unique row and column.

10 The set-up mode switching is unobstructed when all outputs of the mode switch are active. In other words, the input side time switch is connected to all the time slots or channels so that the state of the switch inputs connected to all of the time slots are supplied to various outputs. Unless there is a time slot coming that should be routed to a particular output, then of course this output does not need to be used. Thus, the space in front of the switch 15 the input side of the time switch is to distribute the channels evenly by time slots so that the space switch can switch them to the correct, desired outputs. More specifically, the state switch must avoid a blocking situation in which there would be more than one channel to be routed to the same slot in the same time slot. With the method according to the invention, the coupling matrix is formed in such a way that the cross-coupling operates unimpeded.

20 Figure 1 shows the basic structure of the PPTST algorithm, the table of which has 16 rows corresponding to the outputs, i.e. output 1 ... output 16, and 16 * 63 columns corresponding to the inputs and time slots, i.e. (inputl ... inputl6) * (timel ... time63 ). However, this structure is complemented by other structures to speed up the execution of the algorithm. Namely, in practice, each connection can be thought of as the intersection point (x) of the time matrix. In this case, the task of the algorithm must be to ensure that each row and each column has at most one cross (x) in the case of a normal point-to-point connection, i.e. a connection from one output to one output.

The matrix of Figure 1 performs rearrangements with two types of signals, which are signals between two points and route confirmation or pp signals.

30 A signal between two points must be connected between one input port and one output port, ie it reserves the intersection between one column and one row. (In the case of a bidirectional connection, the return direction naturally occupies a second intersection point. For simplicity, this is not considered separately in this specification, as both directions can be resolved in the same principle and in practice 6 97843 mirror image.) The pp signal is entirely a bidirectional connection that is protected. Thus, three input ports and three output ports, i.e. three intersection points, must be reserved for the pp signal. Figure 2 shows the structure of the pp signal. It can be briefly mentioned here that the pp signals of choice are present at the sa-5 miles at the gates of the state switch so that a confirmatory connection can be made quickly without any special calculation, i.e. only by updating the control data of the switch. The selection and broadcasting are combined in the same pp block so as to minimize the required switching capacity.

Symmetric signal ports are usually used for the pp signal because a two-to-10-way connection uses the same ports in both the transmission direction division phase (1 -> 2) and the reception direction selection phase (2 -> 1). Using the notations in Figure 2, this can be expressed as a condition for the state switch S-switch: Xin = Xout; Yin = Yout; and Zin = Zout. In the case of a one-way secured signal, only one half of the pp signal is in use, i.e. only connections from one point to two 15 points are made in the switch. Two one-way verified signals can be combined to form one complete pp signal if the ports used meet the above condition Xin = Xout; Yin = Yout; and Zin = Zout.

The algorithm according to the invention starts from the principle structure of Figure 1. The algorithm mentions the signals coming to the input ports in the T-switch so that the signals come in a new order. The input ports are shown in columns, and 63 matrices corresponding to the above-mentioned TST constraint are formed in the calculation method. The algorithm can be divided into three main tasks: 1. solving route confirmation or pp signals; 2. solve ordinary easy signals between two points (look for even 25 solutions); 3. solve ordinary awkward signals between two points by shifting.

The first subtask deals with all pp signals. Parts of the pp signals are assembled in the same time matrix, and different pp signals are placed in 63 time matrices. This task does not take into account the usual signals between two points.

30 The second sub-problem solves most of the common connections. Most of the standard connections can be placed directly in a slot matrix where those ports are not yet busy. This can best be described by making even exchanges at the input ports between the two signals at a time, so that

<«H.fr HIM I · t I M

7 97843 both fall into the most probable final time slot of the configuration solution. This can be said to “look for even solutions”.

The third subtask of the algorithm focuses on cumbersome ordinary connections. With these signals, there is no obvious time slot at the input ports for which there would be a free output-5 port, i.e. the output of the S-switch is already reserved. A second connection must then be made to the desired output port, and this requires re-arranging the already solved ordinary input signals in order to find a free output port for a cumbersome connection.

In this rearrangement, the so-called “pull-push” according to the Hall theorem is applied, in which overlapping connections are transferred from one time matrix 10 to another until a free output port is found. This subtask deals only with ordinary connections, because the inclusion of pp signals in shifts would mean that a convergent solution to the problem could not easily be found, but could lead to an avalanche-like increase in the number of shifts. For each transmission, the pp signal does not affect only one port, but can affect multiple connections. In addition, the avalanche 15 can expand and cause the need to change both regular and pp connections, so that more overlaps are formed, i.e. unresolved cases, because only the primary overlap is considered in the shift. Such a process would also be time consuming, and the time factor actually prevents the use of a more complex routine for the shifting of pp signals. Thus, pp signals are included in this shift process only when no other solution can be found dy.

When the rig is considered one of the different shifts (exchanges) made in the basic structure of Figure 1, the target configuration can be more easily demonstrated. In the first time switch stage, this book is used for the final reordering of the signals. The information of the final order destination ports is then used to control the status switch. The last time switch stage, in turn, uses the final signal distribution requested when arranging the target time intermediate information.

The intersections of the basic data structure containing 63 time matrices in Figure 1 are clarified by the example of the input table in Figure 3. The size of the input table is 30 16 * 63, and initially it contains all the input signals, which are distributed according to their input times. The destination of the VC-12 virtual containers is represented by the port and time slot number. The income table determines the basic structure because it forms the x-axis of the basic structure. This is done by placing the income table next to the structure, and the income table becomes, in chronological order, on the x-axis as the input row of the basic structure. The contents of input-35 line then indicate the target port. The connection can be thought of as the intersection of a column and a row in the basic data structure. The configuration is calculated by manipulating the input rows. Mention multiplication does not clear the table inputs, but merely rearranges the positions of the values.

Figure 3 shows example signals. Input 4 (input 4) is a standard two-point connection input signal arriving in slot 4 and targeting time-5 slot 41 at output port 3. In the figure, the intersection point is correspondingly marked with 3.41. The pp signal is in three time slots. In Fig. 3, the broadcast signal (1 2) is in the input line 1 in the time slot 11, and it targets the outputs 5 and 8, the time slots 11 and 61, respectively; the marking of the intersection point is 5 / 8.11 / 61, respectively. The parts of the selection signal are on the input knives 5 and 8, in the time slots 14 and 6. As shown in Fig. 3, the selection signals 10 target the output port 1 and the time slot 32 (1,32).

The central data structure of the algorithm is the income table according to Figure 3. It is the same as the basic data structure in Figure 1. The basic data structure is not physically necessary per se, and can be thought of as an imaginary data structure. However, the rapid execution of the algorithm requires a control data field that is equal to the basic structure of Figure 1, but has another meaning, which will be explained below in connection with the output queue (OutputQueue). The presentation of the signals and the structures related to the input table are discussed below. In general, the port value in this example is 0 to 16, and the time value is 0 to 63, respectively, with a zero value indicating that no signal is present, and the numbers 1 to 16 represent ports. It should be noted here that the value of the port is only a logical value of 20, and in itself is in no way related to the placement of the device, and thus to the location of the circuit boards, for example.

The one-way signal between the two points is represented in the input table by two numbers, as already mentioned, and is written in the format “port, time”. Instead, the pp signal requires a two-part representation in the input table. The second 25 relates to incoming selection signals and the other to an outgoing broadcast signal. The selection signals are identical because they have the same destination, i.e., the target output port and time slot. The universal distribution part of the pp signal has two objects and is thus represented by two port numbers and two time slot numbers, as in Figure 3. In the input table, this representation is further associated with the identification field pp number (PPNumber), which quickly indicates the difference between the two-point signal and the pp signal. . This data field has a number: when it is non-zero between 1 ... 315, it means a pp signal, and a value of zero means a normal signal. The numbering of pp signals also facilitates the processing of pp signals in switching operations. For dial signals, the notation is “pp number, port, time slot”, and for broadcast signals, the form is “pp number, active port, active time slot, confirming port, confirming interval”.

9 97843

An input structure for the receiving interface is obtained from the conversion layer, which corresponds to the input table and contains the connection requests of all signals. In addition, a table must be obtained in which all pp signals are in numerical order. The form of the PP queue element PP is: “pp number, signal port, signal input time slot, signal 5 output time slot, active port, active input time slot, active output time slot, confirming port, confirming input time slot, confirming output time slot”.

An imaginary matrix is not needed for the algorithm, and the algorithm does not use this matrix, but the basic idea of the algorithm is better seen with a large matrix.

Next, we consider the structure of the algorithm, which is illustrated by Figure 4 10. It shows an imaginary coupling matrix, which in this case describes the couplings conducted via the state switch (S) in time slot T. Looking at Figure 4, it should be noted that the central square matrix is completely imaginary and only separately named structures are needed for the algorithm according to the invention.

15 The PP compilation routine uses the PPBooking accounting table, which is the same size as the InputTable. The elements in the accounting table are numbers that correspond to pp numbers. Compared to a basic structure with both input and output axes, the accounting table can be one-dimensional, as pp signals utilize the ports symmetrically. The three input ports in question have the same number as the output ports. The accounting table is shown in Figure 4, its size is 16 * 63, and the values of its elements are between 0 ... 315.

Figure 4 also shows an OutputReference table with a size of 16 * 63. Its elements indicate how many signals are aiming for the same output port in the same time slot.

25 The output queue table (OutputQueue) is (16 * 16) * 63 in size. Its elements indicate the input ports of signals entering the same output port in the same time slot. When the signal is a pp selection signal, the element contains the numbers of the two input ports. The output queue table also contains the pp signal number (PPNumber). The element has the format “pp number, input port, input port2”.

30 The Overlap variable Overlap indicates the number of overlaps, ie how many requests that collide with the same port. This value indicates the sum of the overlaps for all time slots, although in Figure 4 only one time slot (Time = T) is shown for the sake of clarity in other respects.

97843 ίο

The route confirmation indicator TimePP indicates whether this time interval contains pp signals. A value of Yes indicates a pp signal, and a value of no indicates that there are no pp signals in the time slot. The Time-PP values are compiled into a TimePPQueue table of length 63. The Swap-Record table contains numbers indicating the position of the original time slot of the 5 signals in the corresponding input table InputTable. SwapRecord has a size of 16 * 63 and the values of its elements are between 0 ... 63.

Consider the situation in time slot T shown in Figure 4. There is a common connection between the input port 3 and the output port 4, the pp number of which is 0 in both the input table and the output queue, and the structures refer to each other. This relationship is seen as a cross (x) between the input table and the 10 output queues in the thought matrix. The OutputReferen-ce value 1 of the output port 4 indicates that only one connection uses this output port, i.e. there is no overlap for this output, and thus there is only one element in the output queue.

The only pp signal in the input table InputTable is easy to detect based on the pp number: in time slot T, input ports 2, 7 and 9 have a pp signal with sequence number 4.

15 The universal distribution section in input port 2 tends to output ports 7 and 9, as shown by the Port value (7/9) in the table. The target port of the selection signal is output port 2. However, the selection signals do not increase the OutputReference value because only one of these signals is switched through the field.

OutputReference indicates an overlap for output port 5. There are two elements in the output queue 20 indicating the two input signals in question, i.e. input ports 4 and 14. In this time slot T there are two more overlaps. Kim looks at all 63 time slots, with a total of 24 overlaps, as shown by the variable Overlap in Figure 4, i.e., there are 21 more overlaps in time slots T other than Figure 4.

25 The pendulum holding table PPBooking shows that the pp signal number 4 is assembled placed in the time interval T. The zeros in the table indicate the locations for other possible pp signals. SwapRecord indicates from which time slot the relevant signals have been transmitted in each case. In it, the signal on input port 1 is originally from time slot T, and the pp broadcast signal of input port 2 is originally from time slot 1, and so on.

30 The result of the algorithm, ie the output, is now the rearranged input table InputTable and the rearrangement table SwapRecord. SwapRecord notify in other words, how a first or input side time switch (T) is transferred to the respective signal so that it could reach the space stage (S) through. The input table can be used to determine to which output port of the status switch the signal must be connected.

11 97843

The income table also shows what the final departure time slot is. The contents of these tables are derived as conversion layer control information. In addition, the algorithm should give the transformation layer some information about the success of the calculation.

All three procedures of the algorithm try to solve the configuration with the least possible execution work, and they cover most of the possible configuration types. Each part of the algorithm handles only the information that needs reorganization. The data compilation and the three main parts of the algorithm are shown in Figure 5.

The algorithm starts at block 51, after which the route confirmation or pp signals 10 are assembled in block 52. In decision block 53, it is examined whether all pp routings have been resolved. After the PP solution, in block 54, basic information is generated for reordering the overlapping connections. We then proceed to block 55, where even solutions for ordinary easy connections are calculated. After that, the still overlapping awkward connections are resolved in block 56 by shifting.

15 In decision block 57 it is examined whether all the solutions have been made, and in block 59 the algorithm ends. If it is found in decision blocks 53 and 57 that no solutions are found, the process proceeds to block 58, which issues an error message to the conversion layer, i.e., the requestor of the PPTST algorithm.

The compilation of the route confirmation signals 52 shown in Figure 5 is shown in more detail in Figure 6. Initially, the pp signals are randomly distributed in the input table (InputTable). The purpose of PPCollection is now to assemble the parts of the pp signal, i.e. the signals in the same time slot. The placement process is carried out by first filling in time slots 1 ... 63 which do not have pp signals. Then, after the initial block 60, all pp signals marked in the pp sequence PPQueue are processed in the main loop of Fig. 6, marked with an arrow B.

In block 62, the first pp signal is selected from the pp number pp sequence. In block 63, a time interval is selected. In decision block 64, the PPBooking table checks whether the selected time slot is free. If not, proceed to loop A, where decision block 67 checks to see if all 63 slots have been processed, and if so, block 30 selects the next 30 slots. When a free time slot is found in block 64, the process proceeds to block 65, where the pp signal is transferred to the free time slot and a corresponding entry is made in the accounting table PPBooking. In decision block 66, it is checked whether the process has processed all pp signals. When there are still signals left, we go to block 79, where the next pp signal in the pp queue is taken as pp number + 1, and continue in loop B. When all pp signals have been processed, the process ends in block 61.

In the process described above, only pp signals compete for space in the selected time slot, since no other ordinary signals are processed at this stage. When free space has been found for the entire pp-sig-5 signal, corresponding entries are made in block 65 and at the same time parts of the pp signal are transferred to the target time slot in the input table Input-Table. At the same time, any original signals in the target time slot are transmitted to the locations of the pp portions.

In loops A and B, there may be cases where no free space is directly found in the 10 available 63 time slots. This proceeds to the permutation process indicated by the arrow C in Fig. 6. In this first-order permutation, block 67 is first moved to block 69 and a new time interval is selected. Then, in block 70, it is considered whether the transmission of the already arranged pp signal can give space to another pp signal. If no space is found, in step 72 it is checked whether all time slots have been processed, and in block 73 a new time slot is taken. First-order permutation means that the transfer is made when the already arranged pp signal and the pp signal being processed overlap on one of the gates. In block 71, the previously processed signal is deleted and transferred to a new free time slot (i.e., time slots) and the pp accounting table is updated accordingly. The current signal is now set to the .70 freed time slot. From block 71, the process proceeds to block 65. If the first-order permutation is not successful, the second-order permutation, shown by arrow D in Figure 6, is moved.

The second-order permutation works in the loop formed by blocks 74-75-76-77 in the same way as explained above for blocks 69-70-72-73, but now no immediate free time slot is available, nor do the pp signals hit only to one common port as above, but to two common ports. These two common output ports may belong to one or two pp signals. A free time slot is now requested for these signals. If new vacancies are found, they can be cleared for the pp signal in question, which is thus transferred to 30 free time matrices. If no solution is found in loop D, the process proceeds to block 78, which issues an error message, and then the process is terminated in step 61.

Following the pp compilation routine, changes have been made to the time slots in the income table. These changes must be in sync with the different signals and must match the contents of the SwapRe-cord table. The new locations of the pp signals must also be updated in the pp queue, 35 so that backup connections and switching changes can be made quickly.

I 4 il t H If. li IM - 13 97843

After assembling the pp signals, the algorithm calculates the usual easy connections for which the input table contains only one signal for each input port and time slot. Overlapping or overlapping ordinary connections must be moved so that each output port is used only once. In the ControlSetup process (54 in Figure 5), the reorganization control information is first generated. The OutputReference table indicates the number of output ports that are the targets of the input table in each time slot. For pp selection signals, only the second is considered. At the same time, in the output queue, the OutputQueue section of each output port is filled with the corresponding input port numbers. If the connection belongs to a pp signal, the pp number is also entered in the output queue.

10 The overlap counter is incremented for each overlap. The state of the TimePP route confirmation pointer is set to ON when the time slot contains a pp signal, as already mentioned in connection with Fig. 4.

The algorithm then proceeds to the process FindEven (55 in Figure 5), which solves the usual easy signals between two points, i.e. finds even solutions, which is illustrated by the two time slots Time = T and Time = S shown in Figures 7a and 7b. Thanks to symmetry, ordinary signals have a corresponding free output port in the second time slot. This is because when looking at all time slots, only 63 VC12 signals can be reserved for a given port, in which case one overlap of one output port then means that there is at least one unused slot in the same output port. Due to the overlapping time interval, there is also at least one free output gate. The free output port in the second time slot S can be used immediately or the free output port in the overlapping time slot T indirectly, for the second overlapping signal by means of the FindEven exchange. Using a free port is only even if one shift steps the Overlap counter down by at least one.

25 with an even-numbered solutions FindEven (55 in Figure 5) is a more detailed block diagram of Figure 8. The process begins at step 80 and first block 82 OutputRefe-rence table, a first element, and as indicated by arrow A twisted loop processing of all the elements 1 ... 1008 (= 16 * 63). When the element number> 1 of the OutputReference table is indicated in block 83, this means the possibility of a Find-.30 Even operation for an overlapping output port (Output), in which case the process goes to loop B. In loop B, an empty (= 0) element OutputReference [Output] is retrieved from other time slots Time] from the OutputReference table (Figure 7, Time = S). In block 86, it is determined which inputs (Overlapnnputs) produce the overlap and the time interval = 1 is set as the first time slot to be examined. Decision-87 in block 87 examines whether all time slots have been processed. If not, proceed to block 88, 14 97843 to see if the value of the table element is = 0. If the element is not empty, the next time slot is selected in block 89.

When an empty time slot in block 88 is found, in this example time slot S, it is examined in block 90 whether the input port Input is free in the new time slot S. In block 91 it is examined whether the time slot S has the element OutputRefereence [Output] [T ] empty, which means that an immediate switch between time slots T and S is possible in block 92. This state of the FindEven process is shown in Figure 7a, where input ports 6 and 10 are intended to be connected to output port 4 in time slot T. Input port 6 of time slot S is empty. In the event that the input ports of the new time slot S10 are not empty, an indirect FindEven can be made if the content points to an output port that is not used in the original time slot T. This latter situation is shown in Figure 7b, where the input table Input-Table port 6 the content in slot S points to an empty output port 8. The process is terminated in step 81 after the entire OutputReference table has been traversed.

15 The switching operation of the FindEven process differs slightly from the PPCollection process. Depending on the nature of the signals to be exchanged, now the control data fields must also be updated at the same time as the exchange takes place. This also applies to the shift process PullPush (56 in Figure 5), which will be explained below with reference to the block diagram of Figure 10.

20 The third main step of the algorithm is the processing of cumbersome signals, which requires a slightly more complicated process, although its principle is relatively clear. Hall's theorem (“In sets sX there exists an individual solution if each value of k gives k different solutions in any combination of k sets s”) implicitly states that when an overlapping connection is shifted out of time slot, 25 after a finite number of shifts it has an non-overlapping connection when consider the output gates of the first term. However, this presupposes that the signals in question are point-to-point signals. The hall theorem defines the rules of “push swaps”. Push transfers as such do not necessarily use the shortest path to a solution. Although the data structure or input table InputTable selected for the PPTST algorithm 30 allows a short path, maintaining this short path can be difficult. Due to pp signals, it is difficult to find a solution, and in some cases the solution is impossible, i.e. a block is created. The backup concept, in which the backup is implemented with a state switch, inherently includes the possibility of blocking when delivered in the TST architecture. But for the connection between the two points 35, the use of a pure push sequence is more manageable, albeit with a longer solution path. “Pull swap” processing is needed, in 5,984,843 selected PPTST algorithms, to facilitate the maintenance of a push sequence on the short path of a good solution despite pp signals.

The purpose of the combined push and pull procedure, i.e. shifts, is to identify the best final time interval in which the route of the substitution connection to the starting point, i.e. the overlapping output, can be found. The replacement circuit, which is usually associated with the second output, is then shifted to an overlapping time slot, and the Hall push sequence allows the switching steps between the first and last circuit to be rearranged until the last overlapping output is resolved. An efficient Hall-type application is based on knowing the first and last linkers of the sequence. If the last or final coupling is not known, the rearrangements of the Hall-type push sequence would rotate in the local loops until suddenly one final solution is found, at which point a solution for the rearrangement sequence is found.

The straightforward application of the Hall theorem, i.e. the push sequence, is also impossible due to the 15 pp signals. For this reason, an exit routine must be attached to the algorithm that allows the shift process to break the deadlock caused by rarely transmitted pp signals. Another possibility would be to allow easy transmission of pp signals, i.e. to have the same importance as normal connections. In this case, however, the convergence of the sequence could be jeopardized due to the avalanche phenomenon, which was already dealt with in the past 20 min.

The shift routine is continued until the variable Overlap = 0, i.e. when all overlapping ports have been resolved. The process of Figure 10 begins at step 100, after which, in block 102, the first element from the OutputReference table is selected. It is then examined whether the element OutputReference [Output] [T]> 1. If this is not the case, rotate sil-25 and select the next element in block 105 until Overlap = 0 is obtained in block 104, and the process is terminated in step 101. If the situation cannot be resolved , the process explores different switching options, or it ends when the set timer expires.

If the element OutputReference [Output] [T]> 1 in block 103, it indicates an overlap, and the process moves to the actual shift application indicated by arrow C in the figure. For shift, some critical control values can be obtained in an overlapping time slot: those outputs that are not used , and those revenues that cause duplication. These inputs and outputs form a set of connections for which selections are made in the shift sequence. In block 106 it is examined whether the locking state 35 is activated, and if so, in block 107 the state is changed, i.e. the time slot is changed, and 16 97843 otherwise in block 108 a new time slot T + 1 is selected. The shift process then selects a switching option for one signal and using the priority list below with 8 different priority types. These cases are illustrated in Figures 7a, 7b, 9, 11-16. Thus, the process has moved to sub-loop B shown in Figure 10.5 If the pp signals do not interfere, an alternative is found in the sequence that ultimately reduces the Overlap value. When the pp signal is interfered with, some alternatives may allow deviation from the best path of the sequence, and the sequence is terminated so that a better starting point can be found for linear shifting. Each option has a different priority, and the algorithm uses 10 different options, depending on how they are available. These eight options are also retrieved in the time slot T other than the one being processed. In block 109, one of the eight options is selected, and in block 110 it is examined whether BestSwap or FindEven are available, and if there are no options, the process continues to block 111 to check if locking is activated. If there is no lock, it is examined in block 112 whether all time slots have been examined, i.e. whether the first time slot T has been returned. The next time slot is moved via block 113. If there is a second result in decision blocks 110-112, we move from loop B to decision block 114, where it is examined whether there are still options available and whether there is any time left in the preset counter. If the calculation can be continued, in block 115, the highest priority changeover-20 condition is changed and the output Output and time interval T are set according to the option.

Loop C is re-rotated until the rearrangement sequence can resolve at least one overlap found in block 103. Shifts are continued in loop C because the Output and T values are set according to the selected processing option. In other words, unless the overlap is resolved by switching, then the ‘25 Output and T values are reset so that the reordering sequence follows the overlapping output, so that block 103 cannot break the loop in the middle of the ongoing reordering sequence. The locations of the overlapping or overlapping signals are switched with the FillerSwap option from time slot T to time slot S, as seen in the priority list and Figure 12. The changed Output and T values are shown in the priority list below 30. Loop C can be terminated successfully when dealing with the FindEven option (Figures 7a, 7b) or the BestSwap option (Figure 9). The failed attempt is terminated with the ReleaseSwap option (Figure 15), leaving loop C. The PPSwap option can also end with the termination of loop C. Block 116 generates an error message and the process is terminated in step 101 when the options to be processed no longer exist or when the set timer has expired (block 114).

17 97843

The following is a list of the 8 options available and their priority values starting with the highest priority and their impact on the baseline and time slot values:

Option_priority image_set_value_interval

BestS wap 7 9 Outputk = Output ^ Tk = Tk., 5 FindEven 6 7a, 7b Outputk = Output ^ Tk = Tk_,

HallSwap 5 11 Outputk = Output Tk = Tk.,

FillerSwap 4 12 Outputk = Output ^ Tk = Sk_,

BestReplace 3 13 Outputk = Output ^ Tk = Tk_,

ReplaceSwap 2 14 Outputk = Output ^ Tk = Tk_, 10 ReleaseSwap 1 15 Outputk = Output ^ Tk = Tk.! PPSwap 0 16 Outputk = Output ^ Tk = Tk_,

The subscript k-1 means the start and time value of the exchange already performed and the subscript k the following value. T denotes the overlapping time slot and S the time slot in which the replacement connection is made.

15 The locked shift sequence is activated in block 109 if there are no pp signals in the time slots of the overlapping output ports and its substitute connection, i.e. if TimePP = OFF (Figure 4) in both time slots. The locked state also requires that the OutputReference table in the duplicate output be zero for the second time slot. In the locked state, exchanges are made only between these two time slots, which means that no other time slots are considered at all. Thus, the sequence does not proceed on a more uncertain and in some cases useless path. The locked sequence requires a maximum of 16 switching operations to resolve an overlapping or overlapping connection when the DXC is 16 * 16 in size.

One of the most important rules of shifting is not shown in Figure 10. By Ni-25, if any coupling shifted in a shifting sequence causes a new overlap or overlap, it must not be shifted again immediately upon entering another time slot. The next mobile connection is another connection, preferably a new one that has just been examined. The shifted connection also changes the associated input and output states. Thus, transmissions are not allowed without a time slot change, i.e., identical connections are not sal-30 Iita. This rule causes the push sequence to try new combinations, i.e. it rearranges the time slot connections. This rule also applies to both exchange-related signals. On the other hand, pp signals usually prevent the shift sequence from following a straightforward solution search, because if a transmitted signal directed to an output hits a pp signal using that output, then the transmitted normal switching 35 must not be immediately retransmitted due to the rule mentioned here. As a result, the rule needs to be supplemented with a release option implemented by the lowest priority options in the list, BestReplace, ReplaceSwap, ReleaseSwap, and PPSwap.

The PPSwap option involves a more complex sequence of actions than the other 5 options. PPSwap means that the pp signal is transmitted to another time slot. The target time interval of the pp signal is calculated according to the same principles as in the PPCollection routine. The entire PPCollection routine is not needed because only one signal is now processed. Figure 17 shows such a modified routine. Processing of the eight shift options listed above begins after output 170 by first setting in block 172 the number of the pp signal to be shifted out of the overlapping time slot T. The block 17 indicates whether the overlapping output shown in Fig. 16 is used in time slot T. If not, the process ends at block 185, which generates an error message, and the process ends at step 171. Otherwise, the process proceeds to block 174, where space for the pp signal is retrieved, i.e., elements 15 of the PPBooking table are examined and it is explained if there is a free output port for the pp signal. is not T. Search for those pp signals that may need to be moved out of time slot S. When free space is found, in block 180, signal transfers take place, the process ends in step 171.

If no free object is found in decision block 174, a new time slot, other than T, is selected for consideration in block 175. Then, in block 176, it is examined whether the exchange produced a successful result. If not, all time slots in block C are examined in succession until block 176 can be moved to block 177.

If no result is obtained in the first permutation loop C after all 63 time slots have been traversed, decision block 178 proceeds to the second permutation loop, and in block 181 a new time slot other than T is first selected for consideration. Then in block 25 182 it is examined whether the exchange produced a successful result. If not, the slot D is sequentially examined for all time slots until block 182 can be moved to block 177. If no result is obtained in the second permutation loop D after all 63 time slots have been traversed, decision block 183 proceeds to block 185, which returns an error message stating that no PPSwap options were found. , and the process ends in step 171. If the second permutation round produces a positive result, the process proceeds to block 177.

In block 177 of Figure 17, the pp signal or pp signals are transferred to a new time slot or time slots, respectively, and the corresponding data in the PPBooking table is updated. The process then proceeds to block 180, and the process ends at step 171.

19 97843

The PPSwap options found in the loops of the process of Figure 17 are ordered with respect to the input Input that causes the overlap in the original time slot T. If this input is in the target time slot, i.e. time slot S, then the pp signal becomes the PPSwap process selection (Figure 16). This input Input also cannot be connected to the 5 overlapping outputs Output. Such a situation is shown in Figure 16.

The central importance of the last transfer option, the PPSwap process, is that the order of the pp signals is changed without taking into account the connections of ordinary signals. Such an operation potentially causes an increase in the number of overlaps or overlaps, i.e. the value of the Overlap variable increases, as the new placement of pp-signals causes overlaps with ordinary signals already resolved.

The PPTST algorithm of the present invention seeks to solve the entire configuration table lock. The time requirements set for the task led to an algorithm according to the invention, which balances the processing power allocated to different tasks. As such, the algorithm 15 satisfies the execution time requirements well.

The algorithm solves the entire connection configuration, but the solution can just as well be solved with a single connection solution, because the algorithm solves only those connections that require computation. Thus, the connection request can be given in different forms, i.e. so that it concerns only one signal, several signals or the whole configuration matrix, i.e. 16 * 63 signals.

The algorithm ignores AU-4 signals because they can be processed without special computation when using the entire port, i.e., all time slots of the port, and no other signals can then be routed to the same state switch ports. Thus, route verification measures at the AU-4 level can be performed without special calculation. At the AU-4 level, route routing 25 means copying the entire content to another A U-4 signal, which can be implemented by routing both backup signals simultaneously and using two output ports instead of the normal one.

A particular feature of the algorithm of the present invention is the use of timers to monitor that the process is not stuck in a solution loop if the PP-30 TST algorithm is unable to resolve all possible switching cases when there are pp signals requiring path verification among the signals. At least two time limit values are required, one monitoring the calculation time of the individual connections and the other the calculation time of the entire connection matrix.

Claims (11)

2o 97843 1. A method for a digital time-space-time (TST) for the configuration of cross-connection of the digital signals connected -ristikytkimeen between the cross-coupling of the input and output ports, characterized in that illustrate the cross-coupling problem, 5 is formed by the input side time switch and space switch as regards time slot basis imaginary switch matrices (Figure 4), which the number corresponds to the number of sub-signals received and cross-connected at each input, the column of the switching matrix corresponding to the given input port (Input) and the row to the given output port (Output), and the configuration solution only one signal to be cross-connected, ie only one separate signal is connected to the respective output port of the state switch, in which case a) the input signals to be verified by the route are processed sequentially; one and searching for free space for portions of each signal to be routed in the selected same time slot (52); 15 after which b) the point-to-point signals causing the overlapping output port charge are marked in the switching control table (54); c) the overlapping point-to-point signals are resolved one overlapping signal at a time (55) by placing the signal under consideration in a time slot where a free output port is found; but if no solution is found for the respective overlapping signal, proceeding to the next step, where d) the remaining overlapping point-to-point signals are resolved one overlapping signal at a time (56) by swapping the positions of the signal under consideration and the already resolved signal meeting the preselected criteria; 25 e) followed by ristikytkentäkonfiguraatio complement output side time switch with suitable circuits. Method according to claim 1, characterized in that before starting steps a) to e) the time slot-specific switching matrix is provided with auxiliary tables in which: 30. the input table (InputTable) indicates the existence and identifier (PPNumber) of the signal to be verified per input port for the signal at the input port desired output port (Port) and time slot (Time); - the accounting table (PPBooking) indicates the existence and identifier (PPNumber) of the signal to be routed (PP) per input port; 35. the output reference table (OutputReference) indicates per output port the number of signals destined for the same output port in the same time slot; - the output queue table (OutputQueue) indicates for each output port the input ports (Port) of signals reaching the same 97843 output port in the same time slot and the ID of the signal to be verified for a possible route (PPNumber); and - the SwapRecord indicates the initial time interval (Time) of the signal per input port in the corresponding input table (InputTable); 5. The overlap variable indicates the total number of overlaps of the switching matrices of all time slots; and - a route confirmation indicator (TimePP) indicates whether there are route confirmation signals in the time slot in question. Method according to Claim 1 or 2, characterized in that the signals to be switched are multiplexed sub-signals of high-speed signals, preferably 2 Mbit / s VC-12 virtual containers of the SDH system, the main signals being 155 Mbit / s STM-1 signals. , and that the higher class signals are split into a plurality of VC-12 signals before switching, which are again combined in the crossover output time switch. Method according to one of the preceding claims 1 to 3, characterized in that in step a) the route verifiable signal (PP) selected in the initial step (62) is processed and then in turn all other route verifiable signals in the loop (loop B: 63, 64, 65, 66, 79): - retrieving (loop A: 64, 67, 68) a free time slot for the signal (PP) from the accounting table-2G (PPBooking); but if no free time slot is found - a first permutation is performed (loop C: 70, 72, 73) in which one already processed signal (PP) is placed in the new time slot; but if no solution is found - a second permutation is performed (loop D: 75, 76, 77) in which one or two already processed signals (PP) sharing the two ports of the route-verified signal are placed in a new time slot, after which - the changes are recorded ( PPBooking). Method according to one of the preceding claims 1 to 4, characterized in that in step d) the signal selected in the initial step (102) and then alternately all other signals in the loop (loop A: 30 103, 104, 105) are processed as a shift process, wherein the preselected criteria (BestSwap, FindEven, HallSwap, Filters wap, BestReplace, ReplaceSwap, ReleaseSwap, PPSwap) is fetched in loops (loop B: 109, 110, 111, 112, 113; and loop C: 106, 107, 108, 114, 115 ). 97843 A method according to claim 5, characterized in that in addition to step d), if necessary, a forced time slot change is performed for the still overlapping sub-signals of the route-confirmed signals (PP) and the operation of step d) is repeated. A method according to claim 6, characterized in that the forced exchange 5 is performed by random selection. Method according to one of the preceding claims, characterized in that in each step a) to d) the operation is monitored by a calculator, and that the signal processing is interrupted if a predetermined maximum calculation time is exceeded. Circuit arrangement 10 implementing a method according to one of the preceding claims 1 to 8, characterized in that the auxiliary tables (InputTable, PPBooking, OutputReference, OutputQueue, SwapRecord, Overlap, TimePP) describing the connection data of each time slot of the imaginary switching matrix are implemented with ASIC circuit (s) and / or other spiral (s). Circuit arrangement according to Claim 9, characterized in that the cross-switch 15 has 16 input ports and 16 output ports. Circuit arrangement according to Claim 9 or 10, characterized in that there are 63 imaginary switching matrices.